On Isoperimetric Stability

../

corollary_1: Lev's corollary that in an abelian group of exponent 2 or 3, a finite non-empty A whose edge boundary with respect to a finite non-empty S is at most (1 - gamma) n |A|, with n the rank of the subgroup H generated by S, has at least |H|^gamma elements.

theorem_1: Lev's theorem that in a homocyclic group G of exponent 2, 3 or 4 and rank n, a non-empty set A whose edge boundary with respect to a generating set is at most (1 - gamma) n |A| has at least |G|^gamma elements.

theorem_2: Lev's theorem that if S is a finite non-empty independent set in an abelian group, with n = |S| and d the least order of an element of S, then a finite non-empty A with edge boundary at most (1 - gamma) n |A| has at least 4^((1 - 1/d) gamma n) elements.

theorem_3: Lev's theorem that for a finite non-empty downset A of non-negative integer vectors, the average number of non-zero coordinates of a vector in A is at most one half of log_2 |A|.

theorem_4: Lev's theorem that for a finite non-empty subset A of an abelian group whose least order of a non-zero element is p, every independent subset of the set of gamma-popular differences of A has at most log_2 |A| / (2 (1 - 1/p) gamma) elements, and at most log_3 |A| / gamma in exponent 3.

---

Vsevolod F. Lev, On Isoperimetric Stability. Discrete Analysis 2018:14, 11 pp. DOI 10.19086/da.3699; arXiv:1709.05539. The arXiv record names arXiv's non-exclusive distribution license (arXiv:1709.05539), every other right reserved. The copy read for this card is arXiv:1709.05539v2 (4 August 2018), which carries the journal's typesetting and pagination and prints the notice "Licensed under a Creative Commons Attribution License (CC-BY)" (p. 1); the term above follows the arXiv record.

Overview

The paper studies an edge-isoperimetric stability question in an abelian group $G$. For finite $A,S\subseteq G$, it defines

$$\partial_S(A)=|\{(a,s)\in A\times S:a+s\notin A\}|$$

and asks how large $A$ must be when $\partial_S(A)\le (1-\gamma)|S||A|$ with real $\gamma\in(0,1]$. Its central hypothesis is that $S$ is independent, meaning that $\sum_{s\in S}k(s)s=0$ with integer coefficients forces every summand to vanish, equivalently $\bigoplus_{s\in S}\langle s\rangle$ is direct.

The principal result, Theorem 2 in Section 1 (p. 3), states that if $A$ and $S$ are finite and nonempty, $S$ is independent, $n=|S|$, and $d=\min_{s\in S}\operatorname{ord}(s)$, then

$$\partial_S(A)\le(1-\gamma)n|A|\quad\Longrightarrow\quad |A|\ge 4^{(1-1/d)\gamma n}.$$

When all elements of $S$ have infinite order, the asserted interpretation is $|A|\ge4^{\gamma n}$. Example 3 shows that the base $4$ cannot in general be increased: boxes $[0,t-1]^n\subseteq C_m^n$ with $1<t<m$ have $\partial_S(A)=(1-\gamma)n|A|$ for $\gamma=1-1/t$ and $|A|=b^{\gamma n}$ with $b=t^{t/(t-1)}$, which equals $4$ at $t=2$. Example 2 shows optimality of the factor $1-1/d$ when $d=2$, and that for $d=3$ it cannot be replaced by a number larger than $\log3/\log4\approx0.792$.

For homocyclic groups of exponent $2$, $3$, or $4$, Theorem 1 gives the stronger conclusion $|A|\ge |G|^\gamma$ when $S$ generates $G$ and $\partial_S(A)\le(1-\gamma)(\operatorname{rk}G)|A|$. This is deduced in Section 3 from the cited result [L15, Corollary 1.10], not proved independently from first principles in this paper. Corollary 1 extends the conclusion to arbitrary $S$ in groups of exponent $2$ or $3$, with $G$ replaced by $H=\langle S\rangle$. Examples 1–3 delimit these statements: replacing rank by $|S|$ can fail, and the $|G|^\gamma$ conclusion does not extend uniformly to larger exponents.

The auxiliary combinatorial result is Theorem 3 (equivalently Theorem $3'$): every finite nonempty downset $A\subseteq\mathbb Z_{\ge0}^n$ satisfies

$$\frac1{|A|}\sum_{a\in A}w(a)\le\frac12\log_2|A|,$$

where $w(a)$ is the number of nonzero coordinates. Equality occurs for the boxes $[0,l_1]\times\cdots\times[0,l_n]$ with every $l_i\in\{0,1\}$. Section 2 proves this by double induction on $n$ and $|A|$. After splitting the top coordinate layer from the remainder, inequalities (2) and (3) invoke the induction hypotheses, while inequality (4) reduces the required recombination to

$$1+\tfrac12\tau\log_2\tau\le\tfrac12(\tau+1)\log_2(\tau+1),\qquad \tau\ge1.$$

Section 3 develops coordinate compressions along the independent generators. Claim 1 shows that compression in one direction preserves compression already achieved in another; Claim 2 shows that compression does not increase any directed boundary contribution and hence does not increase $\partial_S(A)$. Corollary 2 transports Theorem 3 to compressed subsets of a direct sum of cyclic groups. In the proof of Theorem 2, equations (6) and (7) express the boundary through occupied and full cyclic cosets, equation (8) compares these quantities using the least order $d$, and equation (9), together with Corollary 2, sandwiches the average support size between $(1-1/d)\gamma n$ and $\frac12\log_2|A|$.

The main application concerns popular differences. For finite $A\subseteq G$,

$$P_\gamma(A)=\{g:r_A(g)\ge\gamma|A|\},\qquad r_A(g)=|\{(a,a')\in A^2:g=a-a'\}|.$$

Theorem 4 (p. 4) bounds, for finite nonempty $A$ and real $\gamma\in[0,1)$ as printed (while $P_\gamma$ is defined for $\gamma\in(0,1]$), the maximum size $\dim_I(P_\gamma(A))$ of an independent subset by

$$\dim_I(P_\gamma(A))\le \frac{\gamma^{-1}\log_2|A|}{2(1-1/p)},$$

where $p$ is the least order of a nonzero group element; for exponent $3$ it gives the sharper $\dim_I(P_\gamma(A))\le\gamma^{-1}\log_3|A|$. Section 4 proves this by observing that an independent $S\subseteq P_\gamma(A)$ supplies at least $\gamma|A||S|$ internal Cayley edges, then applying Theorem 2 or Corollary 1. Example 4 shows sharpness for homocyclic groups of exponents $2$ and $3$, up to the displayed lower-order term.

The paper explicitly distinguishes independence from dissociativity. It cites Shkredov–Yekhanin [SY11, Theorem 3.1] for the qualitative estimate

$$\dim_D(P_\gamma(A))\ll\gamma^{-1}\log|A| \tag{1}$$

in finite abelian groups. Since independent sets are dissociated, $\dim_I\le\dim_D$, with equality in exponent $2$ or $3$; thus Theorem 4 supplies sharp constants only in those exponents and does not control dissociated dimension in general groups. Section 5 records, as an unnumbered observation credited to Thomas Bloom (personal communication) rather than a principal theorem, that dissociated $S$ and the same small-boundary hypothesis imply $|A|>\exp(c\gamma^2|S|)$ for some unspecified absolute $c>0$; the paper indicates only that this follows from Hölder's inequality and basic Fourier analysis, and gives no proof. Finally, equation (10) extends the projection inequality obtained in the proof of Theorem 3 to arbitrary finite nonempty subsets of $\mathbb Z^n$. The structural classification of small-boundary sets and improvements for exponent at least $5$ are left open in Section 5.

Relation to E963

For E963, write

$$d_D(X):=\max\{|D|:D\subseteq X\text{ is dissociated}\},\qquad f(N)=\min_{|X|=N}d_D(X).$$

The paper’s definition of dissociated is exactly the one needed here: all subset sums of $D$ are distinct, equivalently there is no nonzero relation $\sum_{d\in D}\varepsilon_dd=0$ with $\varepsilon_d\in\{-1,0,1\}$. Its principal notion of independence is substantially stronger over $\mathbb R$: an independent set has no nontrivial integer relation at all, hence is linearly independent over $\mathbb Q$. Thus

$$d_I(X)\le d_D(X),$$

and equality need not hold; for example, $\{1,2\}$ is dissociated but satisfies the integer relation $2\cdot1-2=0$. Consequently, Theorem 4’s upper bound on independent dimension cannot be converted into an upper bound on the dissociation number relevant to E963.

There is nevertheless a precise popular-difference consequence. If $B\subset\mathbb R$ is finite, $0<\gamma<1$, and an independent set $S$ of nonzero reals lies in $P_\gamma(B)$, then the counting argument of Section 4 gives

$$\partial_S(B)\le(1-\gamma)|S||B|.$$

Because every nonzero real has infinite order, the infinite-order case of Theorem 2 yields

$$|B|\ge4^{\gamma|S|},\qquad |S|\le\frac{1}{2\gamma}\log_2|B|.$$

This can control the rationally independent part of a set of frequently occurring differences, but not its largest dissociated subset. For dissociated $S$, the unnumbered observation at the beginning of Section 5 (Bloom's, stated there without proof, for the abelian group $G$ of the paper's setting with no further hypothesis stated) instead gives only

$$|B|>\exp(c\gamma^2|S|),$$

or $|S|<c^{-1}\gamma^{-2}\log|B|$, with an unspecified absolute constant. This is the paper’s result most directly aligned with E963’s notion.

A possible use in E963 would be a counterexample strategy: if an $N$-element set $X\subset\mathbb R$ could be embedded in a popular-difference set $P_\gamma(B)$ with $\gamma$ bounded away from zero and $|B|$ sufficiently small, the Section 5 estimate would bound $d_D(X)$ from above. Alternatively, in a lower-bound argument it could control a high-multiplicity portion of the relation or difference structure. The paper supplies neither such an embedding nor a decomposition that covers an arbitrary $X$ by controlled popular-difference pieces.

Accordingly, the connection is limited. All principal inequalities run from many internal translations to an upper bound on independent or dissociated dimension; E963 asks for a universal lower bound on dissociated dimension of an arbitrary real set. The compression argument and Theorem 3 might become useful if families of additive relations can be encoded as monotone multisets, but no such reduction is established. In particular, the paper neither proves $f(N)\ge\lfloor\log_2N\rfloor$ nor constructs a set violating it.

Bears on. #963: the argument of Theorem 4, with Theorem 2 read for elements of infinite order, bounds from above the size of an independent set of nonzero reals inside a popular-difference set $P_\gamma(B)$ of reals; the unproved Section 5 remark bounds from above the size of a dissociated set $S$ for which some $A$ has $\partial_S(A)\le(1-\gamma)|A||S|$. The paper gives no bound on $f(N)$, and the limitations are stated in the relation section above.

Read status. Claims checked: Theorems 1-4, Theorem 3′, Corollaries 1 and 2, Examples 1-4, inequality (10) and the Section 5 remark were read clause by clause on the printed pages. The proofs (pp. 5-10) were read but not checked step by step; Theorem 1 rests on [L15, Corollary 1.10], which was not checked.

Results. Theorem 1 (p. 2, with Examples 1-3); Corollary 1 (p. 2); Theorem 2 (p. 3); Theorem 3 (p. 3, with Theorem 3′ on p. 4, Corollary 2 on p. 8 and inequality (10) on p. 10); Theorem 4 (p. 4, with Example 4, the comparison with dissociated sets and the Section 5 remark). Claims 1 and 2 (p. 7) are proof steps of Theorem 2, summarized on its page.

No file of this source is held, and the card cites the edition it names above.