On Isoperimetric Stability

On Isoperimetric Stability, Discrete Analysis 2018:14, 11 pp.

Let $A$ be a subset of the Hamming cube $\{0,1\}^n$. If we regard the cube as a graph in the usual way, by joining two points $x$ and $y$ if they differ in exactly one coordinate, then the edge boundary of $A$ is defined to be the set of all edges that join a point in $A$ to a point in its complement $\{0,1\}^n\setminus A$. The edge-isoperimetric inequality in the cube tells us that if $A$ has cardinality $2^d$, then the size of the edge boundary of $A$ is minimized when $A$ is a subcube of dimension $d$, in which case the number of edges between $A$ and its complement is $2^d(n-d)$. We can regard the graph as a Cayley graph, where the group is $\mathbb F_2^n$ and the generating set $S$ consists of the $n$ standard basis vectors. Then we find that the size of the edge boundary is always at least $|A|(|S|-\log_2|A|)$, an inequality that continues to hold when the size of $A$ is not a power of 2. As a consequence, if the size of the edge boundary is at most $(1-\gamma)|A||S|$, then $A$ must have size at least $2^{\gamma|S|}$.

The purpose of this paper is to prove a similar statement for Abelian groups in general. Given an Abelian group $G$, a subset $A\subset G$, and a generating set $S$ of $G$, define the edge boundary to be the set of pairs $(a,s)\in A\times S$ such that $a+s\notin A$. The precise statement proved is that if the size of the edge boundary is at most $(1-\gamma)|A||S|$, then $A$ must have size at least $4^{(1-1/d)\gamma|S|}$, where $d$ is the exponent of $G$ – that is, the smallest order of any element of $G$. Note that when $G=\mathbb F_2^n$ , then $d=2$, and we recover the statement above. Note also that in this case we can rewrite the lower bound for the size of $A$ as $|G|^\gamma$, a bound that is shown to be valid for groups of exponent 3 or 4 as well. However, for larger exponents the lower bound of $|G|^\gamma$ does not hold, and examples show that we have to settle for the weaker bound $4^{(1-1/d)\gamma|S|}$ proved in this paper.

The reason that groups of low exponent are a special case is connected with the notion of a dissociated set, which is a subset $X$ of an Abelian group $G$ with the property that if $Y$ and $Z$ are finite subsets of $X$ with $\sum_{x\in Y}x=\sum_{x\in Z}x$, then $Y=Z$. Equivalently, it is a subset $X$ with a kind of linear independence property: if $x_1,\dots,x_n$ are distinct elements of $X$ and $\epsilon_1,\dots,\epsilon_n$ are coefficients taken from the set $\{-1,0,1\}$ such that $\sum_i\epsilon_ix_i=0$, then $\epsilon_1=\dots=\epsilon_n=0$. For groups of exponent 2 or 3, all possible integer coefficients can be replaced by ones that belong to the set $\{-1,0,1\}$, so this is just normal independence over the integers (and therefore, when these groups are considered as vector spaces, linear independence), but for groups of higher exponent that ceases to be the case. For example, in the group $\mathbb F_5^n$, the set $\{e_1,\dots,e_n,2e_1,\dots,2e_n\}$ is dissociated but not independent.

These notions lead naturally to notions of dimension for subsets of Abelian groups: given a finite subset $E$, we define $\mathrm{dim}_D(E)$ to be the size of the largest dissociated subset of $E$ and $\mathrm{dim}_I(E)$ to be the size of the largest independent subset. A corollary of the main results of this paper is a sharp bound for the dimension of the popular difference set of a set $A$, which is defined as follows. Given a parameter $\gamma>0$, we set $P_\gamma(A)$ to be the set of all group elements $g$ such that $|A\cap(A-g)|\geq\gamma|A|$. Popular difference sets play an important role in additive combinatorics. A result of Shkredov and Yekhanin states that $\mathrm{dim}_D(P_\gamma(A))$ is at most $C\gamma^{-1}\log|A|$, for some absolute constant $C$. (To see why the factor $\gamma^{-1}$ is necessary, consider an arbitrary union of $\gamma^{-1}$ subspaces of $\mathbb F_2^n$ of the same dimension.) In this paper it is shown that if $p$ is the smallest order of a non-zero element of $G$, then $\mathrm{dim}_I(P_\gamma(A)) \le (2(1-1/p))^{-1}\gamma^{-1}\log_2|A|$, which is refined to $\mathrm{dim}_I(P_\gamma(A)) \le \gamma^{-1}\log_3|A|$ in the special case $p=3$. These estimates are sharp when $G$ is homocyclic of exponent $p=2$ or $3$, when the two notions of dimension coincide.

One of the proof ingredients in the paper is a result that stands on its own. A down-set in $\mathbb Z_{\geq 0}^n$ is a subset $A$ with the property that if $x\in A$ and $y_i\leq x_i$ for every $i$, then $y\in A$. The paper gives an upper bound of $\frac 12\log_2|A|$ for the average number of non-zero coordinates of a vector in a down-set. It is a simple exercise to prove that this bound is sharp.