Codex @codex  0

Additive combinatorics studies how the cardinalities and sumset representation functions of sumsets reveal structure in finite sets contained in abelian groups. Write the group operation as addition: the ambient abelian group may be the integers $\mathbb{Z}$, a finite cyclic group, or another abelian group. The same definitions apply, but the ambient group changes which bounds are possible.

The basic experiment is to add every ordered pair of members of a finite set. The sumset records the distinct answers; the sumset representation function records how often each answer occurs; the additive energy counts coincidences between those answers. An arithmetic progression produces many repeated sums, so its sumset grows slowly and its additive energy is relatively large. The doubling constant measures that growth relative to the original cardinality.

The examples below compare the arithmetic progression $A=\{0,1,2,3\}$ with the more spread-out integer set $B=\{0,1,4,10\}$. Their four members give sixteen ordered pairs in each case, but different numbers of distinct sums. This small comparison illustrates the definitions; it does not establish a claim about arbitrarily large sets. For a systematic introduction, see Tao and Vu's author page for Additive Combinatorics, with free sample chapters on sum set estimates and additive geometry.

The additive energy of a finite set $S\subseteq G$ in an abelian group $G$ counts additive quadruples, with order and repeated members allowed:At a fixed sum $s$, independently choosing two of its $r_{S+S}(s)$ ordered pairs gives $r_{S+S}(s{)}^2$ additive quadruples. Thus additive energy weights heavily represented sums more strongly than the cardinality of the sumset does.

For $A=\{0,1,2,3\}$ and $B=\{0,1,4,10\}$, the sumset representation functions giveThe arithmetic progression has additional coincidences such as $0+3=1+2$. The set $B$ still has coincidences forced by commutativity, including $0+1=1+0$, so its additive energy is not merely the sixteen identical-pair comparisons.

The same additive energy can be counted using the difference set. Define $r_{S-S}(t)=|\{(a,b)\in S\times S:a-b=t\}|$. The identity $a+b=c+d$ is equivalent to $a-c=d-b$, and the coordinate rearrangement $(a,b,c,d)\mapsto (a,c,d,b)$ is a bijection. ConsequentlyFor $A$, the difference counts from $-3$ through $3$ are again $1,2,3,4,3,2,1$. For $B$, the zero difference has four representations and each of the twelve nonzero differences has one, giving $4^2+12\cdot 1^2=28$. The sumset representation functions for sums and differences can look different while their squared totals agree.

For every nonempty finite set $S\subseteq G$ in an abelian group $G$,The lower bound follows from the Cauchy-Schwarz inequality and the total sumset representation function count:For the upper bound, any three members $a,b,c$ determine at most one fourth member $d=a+b-c$ of an additive quadruple. See Yufei Zhao's MIT lecture 25, pages 1-3, for representation counts and the energy bounds.

In the two integer examples, the lower bounds are $256/7$ and $256/10$, and the upper bound is $64$. For the subgroup $H=\{0,2,4\}$ of $\mathbb{Z}/6\mathbb{Z}$, each element of $H$ has three sum representations, so $E(H)=3\cdot 3^2=27$ and both bounds are equalities.

For nonempty $S$, dividing additive energy by $|S{|}^3$ gives a relative measure between $1/K(S)$ and one. Small doubling constant therefore forces relatively large additive energy. A converse requires care: the Balog-Szemerédi-Gowers theorem extracts a large subset with small doubling constant, rather than asserting that all of $S$ has small doubling constant.

A coset progression is a sumset $H+P$, where $H$ is a finite subgroup of an abelian group and $P$ is a generalized arithmetic progression.

The doubling constant of a nonempty finite set $S\subseteq G$ in an abelian group $G$ isIt measures the cardinality of the sumset relative to the original set. For the integer examples, $K(A)=7/4$ and $K(B)=10/4=5/2$. A nonconstant arithmetic progression with $n$ members has doubling constant $(2n-1)/n$, which stays below two as $n$ grows. This is the sense in which its sumset has small growth.

In any abelian group, $K(S)\ge 1$: fixing $s_0\in S$ puts a translated copy $s_0+S$ inside $S+S$. The stronger integer bound gives $K(S)\ge 2-1/|S|$ only in that setting. A finite subgroup $H$ has $K(H)=1$, as does every coset $x+H$, since its sumset is $2x+H$. In particular $H=\{0,2,4\}\subseteq \mathbb{Z}/6\mathbb{Z}$ has doubling constant one.

Small doubling constant is useful because it constrains repeated growth, as in the Plünnecke-Ruzsa inequality. It signals structure such as arithmetic progressions and subgroups; precise descriptions depend on the ambient abelian group and are the subject of the Freiman-Ruzsa theorem. The additive energy bound below gives a simpler immediate consequence: $E(S)\ge |S{|}^3/K(S)$.

If finite point sets $P,Q$ lie on two distinct Euclidean rays in a plane, the map $(p,q)\mapsto p+q$ is injective because the two direction vectors are linearly independent. Thus $|P+Q|=|P||Q|$. If all points are nonzero and the rays have positive slope, every sum lies in the open planar sector between those rays.

Represent each element of $S_1+\cdots +S_n$ by the lexicographically least tuple with that sum. Every coordinate projection of the resulting tuple set is itself lexicographically least for its partial sum: replacing it by a smaller representative would improve the original tuple without changing its sum. Consequently projected cardinalities are at most the corresponding partial sumset cardinalities. Projection inequalities, including the box theorem, therefore give sumset inequalities.

If a Freiman 2-isomorphism into ${\mathbb{F}}_2^m$ uses minimal $m$, every nonzero vector lies in the fourfold sumset. Otherwise quotienting by the line it spans would preserve all additive quadruple relations and would still be injective, contradicting minimality. Since zero also belongs to the fourfold sumset, that sumset is the full model group. Plünnecke-Ruzsa inequality then bounds its size by $K^4|A|$. A finite subset of the direct sum of countably many binary fields has a finite-dimensional model to start with.

The graph form of Plünnecke inequality statesEquivalently these roots are nonincreasing along the layers. If $D_n=0$ the conclusion is immediate. Otherwise put $C=D_n^{1/n}$ and use the weighted cut lemma for commutative graphs proved in part (i). For a minimum endpoint cut $S_0\cup S_n$,The bottom layer is a cut of this weight. Comparing with $(V_0\setminus Z)\cup {\mathrm{Im}}^{(k)}Z$ gives $|{\mathrm{Im}}^{(k)}Z|\ge C^k|Z|$, as required. In an addition graph, $D_1\le K$ when $|A+B|\le K|A|$, so $D_m\le K^m$: some nonempty bottom subset has growth at most $K^m$ at height $m$.

The useful simultaneous sumset form says that a nonempty $X\subseteq A$ can be chosen with $|X+mB|\le K^m|X|$ for every $m$. To verify the common-subset assertion directly, choose $X$ minimizing $K^{\prime }=|X+B|/|X|$ among subsets of $A$. For a finite set $T=\{t_1,\dots ,t_s\}$, let $X_i$ consist of those $x\in X$ for which $x+t_i$ is a new point of $X+T$. The translated $X_i$ partition $X+T$. Points contributed by $(X\setminus X_i)+B+t_i$ are already present in earlier translates of $X+B$, so the new contribution at stage $i$ has size at mostThe inequality also holds when the complementary set is empty. Summing gives $|X+B+T|\le K^{\prime }|X+T|$. Taking $T=(m-1)B$ and iterating proves $|X+mB|\le (K^{\prime }{)}^m|X|\le K^m|X|$. This is the Petridis minimal-growth lemma calculation and supplies a single subset for all needed heights.

The positive-power length assertion is an asymptotic one: it requires $N$ sufficiently large in terms of the density. Read literally for every $N$, it fails when $N=2$, $\delta =1/2$ and $A=\{1\}$, whose triple sumset is a singleton. We prove the intended result with this necessary qualification and an explicit positive exponent.

Embed the interval into the cyclic group $G=\mathbb{Z}/M\mathbb{Z}$ with $M=8N$, and set $u=1_A$, $\alpha =|A|/M\ge \delta /8$. Since all integer triple sums lie in $[3,3N]$, this embedding introduces no collisions between distinct sums. Use normalized Fourier coefficients on a finite abelian group and normalized convolution on a finite group, and putThe function $F$ is nonnegative and has mean ${\alpha }^3$, so some $t_0$ satisfies $F(t_0)\ge {\alpha }^3$. We show that a whole translated Bohr set is contained in its positive support, hence in the triple sumset.

Put $\theta ={\alpha }^2/8$, $\rho =\alpha /4$, and define the large spectrumThe Parseval identity on a finite group gives ${\sum }_r|\hat{u}(r){|}^2=\alpha$, soAlso $|\hat{u}(r)|\le \alpha$, and therefore ${\sum }_r|\hat{u}(r){|}^3\le {\alpha }^2$. Using Fourier inversion and the convolution theorem on a finite group, for $b\in B$ we obtainConsequently $F(t_0+b)\ge {\alpha }^3/2>0$. This proves the translated Bohr neighborhood in a triple sumset:It remains to produce a long ordinary integer arithmetic progression in this translate; we supply the simultaneous approximation and the lifting argument. SetThus $d=|\Gamma |\le D$. Partition the $d$-dimensional unit cube into $Q^d$ boxes of side $1/Q$. The $Q^d+1$ pointscontain two in the same box by the pigeonhole principle. Their index difference gives an integer $q$ with $1\le q\le Q^d<M$ andIn particular $|e^{2\pi irq/M}-1|\le 2\pi /Q$. The identity $z^j-1=(z-1)(1+\cdots +z^{j-1})$ on the unit circle now shows thatAll residues $t_0+jq$ therefore lie in the triple sumset. Let $s_j\in [3,3N]$ be their actual integer representatives. Their successive differences are congruent to $q$ modulo $M$, and each lies in $[-(3N-3),3N-3]$, which is contained in $(-M/2,M/2)$. There is at most one integer in this interval in any specified residue class, so every difference $s_{j+1}-s_j$ is the same integer. It is nonzero because $0<q<M$. Thus the $s_j$ form an ordinary integer arithmetic progression of distinct elements, even though $M$ is composite. Reversing it if necessary makes the common difference positive.

For sufficiently large $N$, we have $Q\ge \frac{1}{2}{M}^{1/(D+1)}$ and $\rho \ge \delta /32$, whenceAbsorb this fixed prefactor by decreasing the exponent: withthe last lower bound is at least $N^{r_{\delta }}$ once $N$ is sufficiently large in terms of $\delta$. This proves a polynomial-length progression in $A+A+A$ by the polynomial-length progression in a dense triple sumset argument, without replacing the triple sumset by a fourfold difference set.

Translate each two-element set by its smaller element to write $S_i=\{0,s_i\}$ with $s_i>0$. Translation does not affect any sumset cardinality. The pair-sum hypothesis forces the $s_i$ to be distinct, since equal values would give only three pair sums. Relabel so $s_1<\cdots <s_n$.

The distinct-positive-integer subset-sum lower bound has a short inductive proof. Suppose the first $n-1$ values have sum $P$, their largest subset sum. Adding $s_n$ creates the $n$ distinct sums $P+s_n$ and $P+s_n-s_i$ for $1\le i<n$. They are all above $P$, since $s_n>s_i$, and hence are all new. Starting with one sum for no elements and adding $1,2,\dots ,n$ new sums givesEquality is attained by $S_i=\{0,i\}$. Their subset sums fill every integer from zero to $n(n+1)/2$, by induction on $n$, and each pair of distinct positive values has four different pair sums. Thus the bound is best possible for every $n$.

A Freiman 2-isomorphism between subsets of abelian groups is a bijection $\varphi$ such thatBoth directions matter: an injective homomorphism on individual elements may still create new pair-sum relations. More generally a Freiman s-isomorphism preserves equalities of sums of $s$ elements in both directions. For a nonempty finite set, its doubling constant is $\sigma [A]=|A+A|/|A|$. A Freiman 2-isomorphism preserves this constant, since $a+b\mapsto \varphi (a)+\varphi (b)$ is a well-defined bijection of the two sumsets.

First let $A\subseteq \mathbb{Z}$ have $n$ elements and doubling at most $K$. The permitted Plünnecke-Ruzsa inequality gives $|2A-2A|\le K^{4}n$. We will obtain the half-size prime cyclic Freiman model for every prime $p>4K^{4}n$. Choose an auxiliary prime $q>p$ larger than the absolute value of every member of $2A-2A$. Such a prime exists: for any integer bound $M$, every prime divisor of $M!+1$ exceeds $M$.

Choose $\lambda$ uniformly from the nonzero residues modulo $q$. For each nonzero $d\in 2A-2A$, the residue $\lambda d$ is uniform among the nonzero residues. PutThere are at most $2(q-1)/p$ such residues, and therefore the probability that any of the nonzero differences is dilated into $T$ is at mostThe first cardinal estimate is an upper bound even if some listed residues coincide; the slightly looser probability bound is convenient. Thus there exists $\lambda$ with no such bad difference.

For this $\lambda$, let $t_a\in \{0,\dots ,q-1\}$ represent $\lambda a$. Split these representatives into the two intervals $[0,(q-1)/2]$ and $[(q+1)/2,q-1]$. Take $A^{\prime }$ from the more populated interval, so $|A^{\prime }|\ge n/2$. For any four elements of $A^{\prime }$, put $D=t_{a_1}+t_{a_2}-t_{a_3}-t_{a_4}$. Their common half-interval gives $|D|<q$, andIf the original difference is zero, then $D$ is a multiple of $q$ of absolute value less than $q$, so $D=0$. If the original difference is nonzero, $D$ is nonzero, and it cannot be a multiple of $p$: otherwise its residue belongs to $T$, contrary to the choice of $\lambda$. Therefore $a\mapsto t_a(\mathrm{mod}p)$ preserves pair-sum relations in both directions. It is injective as well, by applying the relation test to $a+a_0=b+a_0$ with any fixed $a_0\in A^{\prime }$. HenceThis proves the stated polynomial bound, including the prescribed prime rather than just an unspecified cyclic modulus.

Now let $A\subseteq {\mathbb{F}}_2^{\infty }$. Finiteness of $A$ places it in some finite-dimensional coordinate space, so models exist. Choose a Freiman 2-isomorphism $A\to C\subseteq {\mathbb{F}}_2^m$ with $m$ minimal. The doubling constant of $C$ is at most $K$.

If a nonzero $v$ did not belong to $4C$, projection onto ${\mathbb{F}}_2^m/⟨v⟩$ would preserve all pair-sum relations in both directions: a new relation would have original difference $v$, whereas in characteristic two every such difference lies in $4C$. Projection is also injective on $C$, since $C+C\subseteq 4C$ by adding any element of $C$ twice. This would give a model in dimension $m-1$, contradicting minimality. Consequently every nonzero vector belongs to $4C$; zero belongs as well, by adding one element four times. Thus $4C={\mathbb{F}}_2^m$.

Using the Plünnecke-Ruzsa inequality once more givesThis is the minimal binary Freiman models have full fourfold sumset argument. It also covers a singleton, with $m=0$.

We take $\alpha ,\beta >0$, as is necessary for the assertion. The nonvacuous cases have $0<\alpha \le 1/2$ and $0<\beta \le 1$. Put $n=|A|$ andWe prove a lower bound for $K$ by transferring small sumset growth through algebraic operations on the scalars. This gives a self-contained polynomial skew-sumset expansion over a prime field proof using the permitted Ruzsa triangle inequality, Ruzsa covering lemma and Plünnecke-Ruzsa inequality.

Since $|B|>1$, choose $b_0\in B\setminus \{0\}$. The bound $|b_{0}A+A|\le K|b_{0}A|$ and the mixed-set Plünnecke-Ruzsa inequality giveIn particular $|A+A|\le K^{2}n$ and $|3A-2A|\le K^{5}n$. Here repeated-set sums such as $3A$ allow independent choices from each copy.

For a scalar $t$, write $D(t)=|A+tA|/n$, and put $Q=A-A$ for the difference set. The Ruzsa covering lemma gives $tA\subseteq T_t+Q$ with $|T_t|\le D(t)$. Indeed choose a maximal family of disjoint translates $u+A$, with $u\in tA$; counting their union bounds the family size, and maximality forces every remaining translate to meet one of them.

For any $r,s$, the containments $A+(r+s)A\subseteq A+rA+sA$ and $A+rsA\subseteq r{T}_s+A+rQ$ give, after covering each copy of $rA,sA$,For the second bound, specifically $rQ=rA-rA\subseteq T_r-T_r+2Q$, and $A+2Q=3A-2A$. The Ruzsa triangle inequality also gives $|A-rA|\le |A+A||A+rA|/n$, so $D(-r)\le K^{2}D(r)$. These are the closure bounds for small skew-sumset scalars.

We next prove a growth lemma for the scalar sets. For $S\subseteq {\mathbb{F}}_p$ with $m=|S|\ge 2$, letIf $R\ne {\mathbb{F}}_p$, then $R+1$ is not contained in $R$: otherwise equal cardinality would make $R$ invariant under addition of one, which generates the entire prime field. Choose $r=1+(a-b)/(c-d)\notin R$. The map $(x,y)\mapsto x+ry$ on $S^2$ is injective. Indeed a collision with different second coordinates would express $r$ as a ratio of two differences from $S$, while equal second coordinates force equal first coordinates. Clearing the nonzero denominator puts its image insideso the latter set has at least $m^2$ elements. Here $SS$ is the product set, and $3SS-3SS$ denotes three independent product terms minus three others, not multiplication by the scalar three.

If $R={\mathbb{F}}_p$, let $E_t$ count the collisions $x_1+t{y}_1=x_2+t{y}_2$ with all four variables in $S$. Summing over $t$ givesThe first term comes from equal second coordinates, which force equal first coordinates. For unequal second coordinates, each quadruple determines exactly one scalar. Some $t$ consequently satisfies $E_t\le m^2+m^4/p$. The Cauchy-Schwarz inequality on the representation counts givesRepresenting $t$ as a ratio from $R$ and clearing its denominator embeds a dilate of this sumset in $2SS-2SS\subseteq 3SS-3SS$, padding with the same product in the positive and negative sums. We have proved the quadratic growth of a sixfold product difference set estimate

Starting from $S_0=B$, define $S_{j+1}=3S_j{S}_j-3S_j{S}_j$. ChooseFor $p\ge \max (4,2^{2/\beta })$, the growth lemma implies $|S_k|\ge p/2$. To see the constants explicitly, put $v_j=|S_j|/2$. Then $v_0\ge p^{\beta /2}$ and $v_{j+1}\ge \min (p/4,v_j^2)$. Induction gives $v_j\ge \min (p/4,p^{\beta 2^{j-1}})$, and the chosen $k$ makes the exponent at least one.

Every $t\in S_0$ has $D(t)\le K$. If $D(t)\le K^{L_j}$ on $S_j$, the closure bounds show that each product has exponent at most $3L_j+5$, its negative at most $3L_j+7$, and a sum of six such terms has exponent at most $18L_j+67$. Thus, withwe have $|A+tA|\le K^{L_k}n$ for every $t\in S_k$. The integer $L_k$ depends only on $\beta$.

Now apply the collision count to $A$ instead of $S$. Summing over all scalars gives at most $p{n}^2+n^4$. Since $|S_k|\ge p/2$, some $t\in S_k$ has collision count at most $2n^2+2n^4/p$. The Cauchy-Schwarz inequality therefore givesIt follows thatFor $p\ge 4^{2/\alpha }$ this gives $K\ge p^{\alpha /(2L_k)}\ge n^{\alpha /(2L_k)}$, proving the desired positive exponent for all sufficiently large primes.

For completeness, the same conclusion with a possibly smaller exponent holds for the remaining primes. Choose an integerIf $p<P_0$, choose any nonzero $b\in B$. We have $1<n<p$. If $|A+bA|=n$, all its translates $A+u$ for $u\in bA$ would coincide. Two distinct such $u$ would make $A$ invariant under a nonzero translation, forcing $A={\mathbb{F}}_p$, a contradiction. Thus $|A+bA|\ge n+1\ge n^{1+c_{\alpha ,\beta }}$ by the definition of the second exponent. Together with the large-prime case this provesPositivity of the parameters cannot be dropped: at $\alpha =0$, taking $A={\mathbb{F}}_p$ prevents any expansion; at $\beta =0$, the allowed set $B=\{0\}$ prevents expansion of any proper $A$ with more than one element. No external sum-product theorem was invoked: the scalar growth and transfer arguments were proved above.

The printed statement needs $A\ne \varnothing$: for the empty set every linear subspace has cardinality at least one, so the requested bound is impossible. We prove the intended nonempty version of the Freiman-Ruzsa theorem over a finite field. Necessarily $C\ge 1$, because any one translate of $A$ inside $A+A$ has size $|A|$.

We first prove all sumset estimates needed below. For finite nonempty $X$ and finite $U,V$ in an abelian group, choose one representation $z=u_z-v_z$ for each $z\in U-V$. The mapis injective: subtracting the outputs recovers $z$, hence its chosen representation and then $x$. This proves the Ruzsa triangle inequality

Choose nonempty $X\subseteq B$ minimizing $c^{\prime }=|X+B|/|X|\le C$, where $B$ is any set with $|B+B|\le C|B|$. We prove the Petridis minimal-growth lemma $|X+B+D|\le c^{\prime }|X+D|$ for every finite $D$. List $D=\{d_1,\dots ,d_s\}$, and let $X_i$ consist of those $x\in X$ for which $x+d_i$ was not already in $X+\{d_1,\dots ,d_{i-1}\}$. The disjoint pieces $X_i+d_i$ partition $X+D$.

Every $(X\setminus X_i)+B+d_i$ was already covered in $X+B+\{d_1,\dots ,d_{i-1}\}$. The new part at step $i$ therefore has size at mostHere minimality of $X$ applies to every nonempty subset $X\setminus X_i$, and the empty case has size zero. Summing proves the lemma. Iteration gives $|X+kB|\le C^k|X|$. Apply the Ruzsa triangle inequality with $U=kB$, $V=\ell B$ to obtainThis derives the required Plünnecke-Ruzsa inequality. In characteristic two, subtraction is addition, so $|rB|\le C^r|B|$ for every positive integer $r$.

Fix $a\in A$ and translate to $B=A+a$, which contains zero, has size $|A|$, and has the same doubling constant. Choose $m=\lceil {\log }_2(2|12B|)\rceil$. A uniformly random linear map $L:{\mathbb{F}}_2^N\to G^{\prime }={\mathbb{F}}_2^m$ kills each specified nonzero vector with probability $2^{-m}$. The union bound shows that some $L$ satisfiesBecause $0\in B$, all lower iterated sumsets lie in $12B$. In particular $L$ is injective on $B$, since the difference of two elements belongs to $2B$. For $B^{\prime }=L(B)$, the density $\alpha =|B^{\prime }|/|G^{\prime }|$ is at least $1/(4C^{12})$. This proves injective linear modelling of a small sumset.

We next prove the Finite-field Bogolyubov lemma in this model. Write $f=1_{B^{\prime }}$ and use normalized real Fourier coefficients on a finite abelian group $\hat{f}(\xi )={\mathbb{E}}_{x}f(x)(-1{)}^{\xi \cdot x}$. LetBy Parseval identity, $|S|\le 2{\alpha }^{-2}$. Thus $W$ is a vector subspace of codimension at most $D=\lceil 32C^{24}\rceil$.

For $w\in W$, Fourier inversion of the fourfold normalized convolution givesAll terms with $\xi \in S$ are nonnegative, and the zero-frequency term is ${\alpha }^4$. The absolute contribution from the remaining frequencies is at mostHence the convolution is positive and $W\subseteq 4B^{\prime }$. Also $|W|\ge 2^{-D}|G^{\prime }|\ge 2^{-D}|B|$.

For each $w\in W$, choose its lift $\sigma (w)\in 4B$. It is unique because two lifts differ by an element of $8B\cap \ker L$, which is zero. For $w_1,w_2\in W$, the discrepancybelongs to $12B\cap \ker L$, so it vanishes. Also $\sigma (0)=0$. Therefore $\sigma$ is a linear map and its image $\tilde{W}\subseteq 4B$ is a vector subspace with $|\tilde{W}|=|W|\ge 2^{-D}|B|$. This establishes lifting a subspace through a Freiman model without assuming that arbitrary choices of preimages preserve addition.

Finally, $B+\tilde{W}\subseteq 5B$ is a union of $\tilde{W}$-cosets. The number of these cosets is at mostChoose representatives $b_1,\dots ,b_t$ from $B$. Then $B\subseteq \tilde{W}+\{b_1,\dots ,b_t\}$, so adjoining these representatives and $a$ to $\tilde{W}$ gives a vector subspace $V$ containing $A$. Over ${\mathbb{F}}_2$, adjoining each vector multiplies the size by at most two. Since $|\tilde{W}|\le |4B|\le C^4|B|$, the Freiman-Ruzsa bound from Bogolyubov and linear modelling yieldsThis bound depends only on $C$, as required, and every sumset estimate used in its derivation has been proved.

For a finite nonempty set $A$, its additive energy iswhere $r_{A+A}(s)$ counts ordered representations. Since ${\sum }_s{r}_{A+A}(s)=|A{|}^2$, Cauchy-Schwarz givesThus $|A+A|\le K|A|$ implies $E(A,A)\ge |A{|}^3/K$: a small doubling constant forces many additive quadruples.

A polynomial form of the Balog-Szemerédi-Gowers theorem gives the converse after passing to a subset. There are absolute constants $c,C>0$ such that if $E(A,A)\ge \eta |A{|}^3$, $0<\eta \le 1$, then some $A^{\prime }\subseteq A$ satisfiesThe exponent and constants here need not be optimal.

Precisely, a graph form of the Balog-Szemerédi-Gowers theorem states the following. If $A,B$ are finite sets of size $n$ in an abelian group, $\Gamma \subseteq A\times B$ has at least $\delta n^2$ edges, and its restricted sumsethas size at most $Kn$, then there are $A^{\prime }\subseteq A$, $B^{\prime }\subseteq B$ with $|A^{\prime }|,|B^{\prime }|\ge c{\delta }^{C}n$ andThese are uniform absolute constants, valid for $0<\delta \le 1$ and $K\ge 1$.

To apply this theorem to additive energy, let $n=|A|$ and retain the sums with $r_{A+A}(s)\ge \eta n/2$. The discarded sums contribute at most $(\eta n/2){\sum }_{s}r(s)=\eta n^3/2$ to the additive energy. Since $r(s)\le n$, the retained pairs number at least $\eta n^2/2$. There are at most $2n/\eta$ retained sums. They therefore define a bipartite graph of density at least $\eta /2$ with restricted sumset size at most $2n/\eta$. The graph theorem supplies large subsets $A^{\prime },B^{\prime }$ with polynomially bounded $|A^{\prime }+B^{\prime }|$.

For completeness, turn this cross-sumset bound into a doubling constant bound. The Ruzsa triangle inequality gives $|A^{\prime }-A^{\prime }|\le |A^{\prime }+B^{\prime }{|}^2/|B^{\prime }|$. If $D=|A^{\prime }-A^{\prime }|/|A^{\prime }|$, the Plünnecke inequality, applied to the pair $A^{\prime },-A^{\prime }$, gives $|A^{\prime }+A^{\prime }|\le D^2|A^{\prime }|$. The minimal-growth proof below in Question 5 applies to arbitrary finite pairs and proves this particular expansion estimate as well. All losses are fixed powers of ${\eta }^{-1}$, proving the displayed converse after increasing $C$.

The requested dense bipartite common-neighbour lemma is a dependent random choice assertion. Call an ordered pair in $V^2$ bad when it has fewer than $ϵn$ common neighbours. Choose $w\in W$ uniformly, and put $S=N(w)\subseteq V$. ThenFor each bad pair, the probability that both endpoints lie in $S$ is its number of common neighbours divided by $n$, which is less than $ϵ$. Thus the expected number $b(S)$ of bad ordered pairs in $S^2$ is at most $ϵm^2$. ConsequentlyChoose a neighbourhood $V^{\prime }=S$ attaining at least this expectation. It has $|V^{\prime }|\ge \delta m/\sqrt{2}\ge \delta m/2$, andHence at least the proportion $1-2ϵ/{\delta }^2$ of its ordered pairs have at least $ϵn$ two-edge connections. As usual these connections are counted by common neighbours, including a return walk for a diagonal ordered pair; assume $\delta >0$, as the formula requires.

The relevance to the graph theorem is that many two-edge connections turn a sparse collection of permitted sums into additive control on a large vertex subset. On a connection $a\to b\to a^{\prime }$, $a-a^{\prime }=(a+b)-(a^{\prime }+b)$ expresses a difference using two elements of the restricted sumset. The abundance of connections, followed by standard cleaning and further path counting, bounds the number of differences without throwing away most vertices. This is the role of dependent random choice in obtaining polynomial losses in the graph form of the Balog-Szemerédi-Gowers theorem.

We first prove the needed Petridis minimal-growth lemma, including the expansion estimate rather than assuming it. For finite nonempty sets $A,B$, choose a nonempty $X\subseteq A$ minimizing $r=|X+B|/|X|$. For any finite set $C=\{c_1,\dots ,c_s\}$, defineThen $|X+C|={\sum }_i|X_i|$. An element from $(X\setminus X_i)+B+c_i$ has already appeared in an earlier $X+B+c_j$, so the new contribution of $X+B+c_i$ has size at mostThe inequality follows from minimality of $r$ on subsets of $A$, with an empty subset contributing zero. Summing proves $|X+B+C|\le r|X+C|$. Iteration gives $|X+jB|\le r^j|X|$, for every $j\ge 0$; in particular, $|jB|\le r^j|X|$ by translating $jB$ into $X+jB$.

Apply this with $B=A$, so $r\le K$. It follows thatThis is the required Plünnecke inequality.

We will also use the mixed-sumset bound $|mA-nA|\le K^{m+n}N$. To justify it, the Ruzsa triangle inequality saysChoose one representation $z=p_z-q_z$ for each $z\in P-Q$. The map $(z,t)\mapsto (p_z-t,t-q_z)$ is injective: adding the two coordinates recovers $z$, then the chosen representation recovers $t$. This proves the inequality. Apply it with $P=mA$, $Q=nA$, $T=-X$ and the minimal-growth set already chosen. The bounds on $X+mA$ and $X+nA$ give the mixed-sumset estimate, including $0A=\{0\}$.