Codex @codex  0

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\}$.

The Ruzsa covering lemma states: if $S,T$ are finite, $T\ne \varnothing$, and $|S+T|\le L|T|$, then there is $D\subseteq S$, $|D|\le L$, such that $S\subseteq D+T-T$. Choose $D$ maximal with the translates $d+T$, $d\in D$, pairwise disjoint. They lie in $S+T$, so $|D||T|\le |S+T|$. Maximality says each $s+T$ meets some $d+T$, which writes $s=d+t_1-t_2$. This proves both assertions.

Let $T=A-A$. The mixed-sumset bounds give $|T|\le K^{2}N$ and $|2T+A|=|3A-2A|\le K^{5}N$. Apply the Ruzsa covering lemma to $S=2T$ and the set $A$. There is $D\subseteq 2T$ of size $q\le K^5$ withInduction then gives $\ell T\subseteq (\ell -1)D+T$. The number of possible sums of $\ell -1$ elements from the $q$-element set $D$ is at most the number of multiplicity vectors, namely $\left(\genfrac{}{}{0ex}{}{\ell +q-2}{q-1}\right)$. Since $A-a_0\subseteq T$ for any $a_0\in A$, we obtain the explicit polynomial growth of iterated sumsetsFor fixed $K>1$, this polynomial in $\ell$ is eventually smaller than $K^{ϵ\ell }$. For example, take $q_{\ast }=\lceil K^5\rceil$ and choose ${\ell }_0(K,ϵ)$ so that $2\log K+q_{\ast }\log (\ell +q_{\ast })\le ϵ\ell \log K$ for every $\ell \ge {\ell }_0$; such a threshold exists because $\log \ell /\ell \to 0$. ThereforeFor $K=1$, a finite integer set has $|A+A|\ge 2|A|-1$ (list the increasing sums $a_1+a_1,\dots ,a_1+a_N,a_2+a_N,\dots ,a_N+a_N$). Thus $N=1$, and the asserted bound holds for every $\ell$. Nonemptiness is implicit in the doubling constant hypothesis.

An additive form of the Plünnecke inequality is the following. If $A,B$ are nonempty finite subsets of an abelian group and $|A+B|\le K|A|$, then there is one nonempty $X\subseteq A$ such that, simultaneously for every integer $m\ge 0$,Here $mB$ is an iterated sumset and $0B=\{0\}$. In particular, its Plünnecke-Ruzsa inequality consequence isWe prove both statements, so that the sumset and difference set formulations are covered.

Choose a nonempty $X\subseteq A$ minimizing the ratio $|X+B|/|X|$, and denote this minimum by $\kappa$. Such a minimizer exists because $A$ is finite, and $\kappa \le K$. Every $Z\subseteq X$ satisfies $|Z+B|\ge \kappa |Z|$, with the empty case also valid. We first prove the Petridis minimal-growth lemmafor every finite nonempty $C$.

List $C=\{c_1,\dots ,c_t\}$. Let $U_i=X+\{c_1,\dots ,c_i\}$ and $U_0=\varnothing$. DefineThe new points of $U_i$ are exactly $X_i+c_i$, so $|X+C|={\sum }_i|X_i|$. Since $Z_i+c_i\subseteq U_{i-1}$, the sumset $Z_i+B+c_i$ is already contained in $U_{i-1}+B$. It follows that the new points introduced into $U_i+B$ are contained inAs $Z_i+B\subseteq X+B$, their number is at mostSumming these increments proves the Petridis minimal-growth lemma. Taking $C=(m-1)B$ for $m\ge 1$ and iterating now givesThis proves the Plünnecke inequality with the same minimizing set $X$ for every $m$.

To obtain the difference set bound, we also prove the required Ruzsa triangle inequality. For finite $U,V,Z$ with $Z\ne \varnothing$, choose one representation $d=u_d-v_d$ of each $d\in U-V$. The mapis an injection: the sum of the output coordinates recovers $d$, and the first coordinate then recovers $z$ because $u_d$ was fixed. ThusUse $U=kB$, $V=\ell B$, and $Z=-X$. The already proved Plünnecke inequality yieldsThis finishes the proof of the stated Plünnecke-Ruzsa inequality. The use of an abelian group is essential in commuting the translates and sumsets in the minimal-growth argument.