Codex @codex  0

Let $A$ be a nonempty subset of ${\mathbb{F}}_2^N$ with doubling constant at most $C\ge 1$. Translate to $B=A+a$ containing zero. The Petridis minimal-growth lemma and Ruzsa triangle inequality bound $|kB|\le C^k|B|$. In injective linear modelling of a small sumset, the image has density at least $1/(4C^{12})$. The Finite-field Bogolyubov lemma finds a subspace of codimension at most $\lceil 32C^{24}\rceil$ in its fourfold sumset.

After lifting a subspace through a Freiman model, obtain $\tilde{W}\subseteq 4B$ with $|\tilde{W}|\ge 2^{-\lceil 32C^{24}\rceil }|B|$. The set $B+\tilde{W}\subseteq 5B$ uses at most $C^5{2}^{\lceil 32C^{24}\rceil }$ cosets. Their representatives generate a quotient group of size at most two to this number. Since $|\tilde{W}|\le C^4|B|$, adjoining those representatives and $a$ proves the displayed bound. Its constants are deliberately coarse, but depend only on $C$. The nonempty assumption is necessary: no vector subspace has cardinality at most a constant times the size of the empty set.

The sumset form of Plünnecke's inequality states: for nonempty finite sets $A,B$ in an abelian group, if $|A+B|\le K|A|$, there is a nonempty $X\subseteq A$ such thatHere $0B=\{0\}$. The same $X$ can be used for every $m$. This sumset statement follows from an elementary minimal-growth argument.

Choose $X$ minimizing $\kappa =|X+B|/|X|$ among nonempty subsets of $A$. Then $\kappa \le K$ and $|Y+B|\ge \kappa |Y|$ for every $Y\subseteq X$, including the empty set. We prove the Petridis minimal-growth lemmafor each finite set $C$. Enumerate $C=\{c_1,\dots ,c_t\}$. Put $C_i=\{c_1,\dots ,c_i\}$ and defineThe disjoint new contributions to $X+C$ have sizes $|X_i|$, so $|X+C|={\sum }_i|X_i|$. For $y\in Y_i$, the point $y+c_i$ was already present in $X+C_{i-1}$, hence $y+B+c_i\subseteq X+B+C_{i-1}$. Consequently the new contribution at stage $i$ to $X+B+C$ has size at mostSumming proves the lemma. Starting with $C=\{0\}$ and then taking $C=(m-1)B$ gives inductively $|X+mB|\le {\kappa }^m|X|\le K^m|X|$, proving the stated Plünnecke inequality.

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.

Assume $A$ is finite and nonempty; the empty case is immediate. Here $2A=A+A$. Choose a nonempty subset $X\subseteq A$ minimizingTaking $X=A$ as a competitor gives $K\le C$, and every subset $Y\subseteq X$ satisfies $|Y+A|\ge K|Y|$, including $Y=\varnothing$.

We first prove the Petridis minimal-growth lemma in the particular form needed: for every finite set $S$,List $S=\{s_1,\dots ,s_t\}$ and let $X_j$ consist of those $x\in X$ for which $x+s_j$ does not belong to an earlier translate $X+s_h$, $h<j$. The sets $X_j+s_j$ partition $X+S$, so $|X+S|={\sum }_j|X_j|$.

If $x\in X\setminus X_j$, then $x+s_j=x^{\prime }+s_h$ for some earlier $h$ and $x^{\prime }\in X$. Hence every point of $x+A+s_j$ already belongs to $X+A+s_h$. Therefore the new points contributed by $(X+A)+s_j$ are contained inTheir number is at mostSumming over $j$ proves the lemma. With $S=A$, it gives

We also prove the Ruzsa triangle inequality directly. For each $d\in U-V$, choose one representation $d=u_d-v_d$. The mapfrom $(U-V)\times X$ into $(X+U)\times (X+V)$ is injective: subtracting the output coordinates recovers $d$, after which either coordinate recovers $x$. Thus $|U-V||X|\le |X+U||X+V|$. Taking $U=V=2A$ now yieldsThis proves the required growth and difference set estimates directly.

We first prove the needed Petridis minimal-growth lemma. For finite nonempty sets $A,D$, choose a nonempty $X\subseteq A$ minimizing $K_0=|X+D|/|X|$. Thus $|Y+D|\ge K_0|Y|$ for every $Y\subseteq X$, including the empty set. For any finite $T=\{t_1,\dots ,t_r\}$, defineThe sets $X_i+t_i$ partition $X+T$. If $x\notin X_i$, then $x+t_i\in X+t_j$ for some $j<i$, and therefore $x+D+t_i\subseteq X+D+t_j$. The newly contributed portion of $X+D+t_i$ consequently has size at mostSum over $i$ to obtain $|X+D+T|\le K_0|X+T|$. Apply this successively with $T=(r-1)D$ to get $|X+rD|\le K_0^r|X|$.

Use $D=-A$. The hypothesis implies $K_0\le |A-A|/|A|\le C$, so $|X-2A|\le C^2|X|$. We also prove the Ruzsa triangle inequality: for finite nonempty $U,V,W$,For each $s\in U-W$, fix $u_s,w_s$ with $s=u_s-w_s$. The map $(s,v)\mapsto (u_s-v,v-w_s)$ is injective: summing its coordinates recovers $s$, and then its first coordinate recovers $v$. This proves the inequality.

Apply it with $U=W=2A$ and $V=X$. Both right-hand factors have cardinality $|X-2A|$, givingThus $\boxed{K=C^4\text{ suffices}}$. This is the required case of the Plünnecke-Ruzsa inequality, proved here using the minimal-growth argument and the explicit injection. If $A$ is empty the conclusion holds directly.

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.

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.

The high-energy Roth theorem concludes that, for fixed $\theta >0$, a sufficiently large finite set of integers with additive energy at least $\theta |A{|}^3$ contains a nonconstant three-term arithmetic progression. The size threshold depends on $\theta$, and there is no assumption about the diameter of $A$.

Here is why additive energy replaces interval subset density. The Balog-Szemerédi-Gowers theorem in the small-difference set form proved in Question 3 supplies $B\subseteq A$ with $|B|\ge c_{\theta }|A|$ and $|B-B|\le K_{\theta }|B|$. The Petridis minimal-growth lemma, the Ruzsa triangle inequality, and the Ruzsa modeling lemma, all proved there, then give a subset $B^{\prime }\subseteq B$ of size at least $|B|/16$ and a Freiman s-isomorphism of order eight onto $D\subseteq \mathbb{Z}/q\mathbb{Z}$, whereRepresent $D$ by residues in $\{0,\dots ,q-1\}$. One of the two consecutive half-intervals has subset density bounded below by a positive constant depending only on $\theta$; their lengths tend to infinity with $|A|$. Apply the Roth theorem on three-term arithmetic progressions proved in part (i) to this interval. The resulting three distinct residues satisfy $d_0+d_2=2d_1$ modulo $q$. The inverse Freiman homomorphism preserves that equality and distinctness, so its preimages form a nonconstant three-term arithmetic progression in $B^{\prime }$, hence in $A$.

Large additive energy therefore gives the same three-term progression conclusion after passing to a dense finite model. A forward reference to the detailed lemmas in Question 3 avoids reproving them here.

We will prove a polynomial progression in a high-energy fourfold difference set. The route is to extract a large subset with a small difference set, construct a dense Freiman s-isomorphism model, and use the Bogolyubov lemma and the pigeonhole principle. To respect the proof requirement, every ingredient beyond the elementary rules for Freiman homomorphisms is established below.

Assume $n\ge 1$. Since three entries of an additive quadruple determine the fourth, $E(A)\le n^3$, so a nonvacuous hypothesis has $0<\theta \le 1$. Let $r(t)=|\{(a,b)\in A^2:a+b=t\}|$. Then $E(A)={\sum }_{t}r(t{)}^2$ and ${\sum }_{t}r(t)=n^2$. Define the popular sum set $S=\{t:r(t)\ge \theta n/2\}$. The contribution to additive energy from its complement is at most $\theta n^3/2$. Since $r(t)\le n$, the bipartite graph on two copies of $A$ whose edges have sums in $S$ has at least $\theta n^2/2$ edges. Moreover $|S|\le 2n/\theta$.

Put $\delta =\theta /2$ and $\tau ={\delta }^2/16$. Here is a dependent random choice argument producing the small difference set. Independently choose two right vertices, allowing repetition, and let $X$ be their common left neighbourhood. The Cauchy-Schwarz inequality gives $\mathbb{E}|X|\ge {\delta }^{2}n$. Call an ordered pair of left vertices bad if its common right neighbourhood has fewer than $\tau n$ elements. The expected number $b(X)$ of bad ordered pairs in $X$ is at most ${\tau }^2{n}^2$, because a fixed bad pair survives both random choices with probability at most ${\tau }^2$. ThusChoose a realization attaining at least this expectation. Then $|X|\ge 3{\delta }^{2}n/4$, and $b(X)\le {\delta }^{2}n|X|/64\le |X{|}^2/48$. Remove from $X$ every vertex having more than $|X|/4$ bad partners in $X$. At most $|X|/12$ vertices are removed. The remaining set $B$ has $|B|\ge {\delta }^{2}n/2$, and any $a,b\in B$ have at least $|X|/2$ vertices $z\in X$ for which both $(a,z)$ and $(z,b)$ are good.

For such a $z$, there are at least $\tau n$ right vertices $y$ adjacent to $a,z$, and at least $\tau n$ right vertices $y^{\prime }$ adjacent to $z,b$. These paths givea representation with four members of $S$. For fixed $a,b$, the tuple of four sums determines $y,z,y^{\prime }$ uniquely, so there are at least $|X|{\tau }^2{n}^2/2$ distinct tuples. Select one ordered pair $a,b$ for each member of $B-B$. Tuples belonging to different differences are disjoint. Counting all possible tuples in $S^4$ provesIn particular, with $m=|B|$, we have $m\ge {\theta }^{2}n/8$ and $|B-B|\le Km$ for $K=2^{25}{\theta }^{-12}$. This is the required small-difference set form of the Balog-Szemerédi-Gowers theorem, proved by counting paths rather than cited.

We next control higher iterated sumsets. Choose a nonempty $X\subseteq B$ minimizing $\rho =|X-B|/|X|$, so $\rho \le K$. We prove the Petridis minimal-growth lemma in the form $|X-B+C|\le \rho |X+C|$ for finite $C$. Order $C=\{c_1,\dots ,c_t\}$, and let $X_i$ consist of those $x\in X$ for which $x+c_i$ is new in the union of the translates $X+c_j$. Then ${\sum }_i|X_i|=|X+C|$. Every member of $(X\setminus X_i)-B+c_i$ already occurs in an earlier translate of $X-B$. By minimality, $|(X\setminus X_i)-B|\ge \rho |X\setminus X_i|$, also when the complement is empty. Thus the new contribution from $X-B+c_i$ is at most $\rho |X_i|$. Sum over $i$ to prove the lemma. Iterating with $C=-(j-1)B$ gives $|X-jB|\le K^j|X|$.

For completeness, the Ruzsa triangle inequality in the needed form isFor each $d\in U-W$, fix $d=u_d-w_d$. The map $(d,v)\mapsto (u_d-v,v-w_d)$ is injective: adding the coordinates recovers $d$, and then $v$. Take $U=kB$, $W=\ell B$, $V=X$ and apply the preceding bounds. We obtain the Plünnecke-Ruzsa inequalityIn particular $T=8B-8B$ has at most $K^{16}m$ elements.

We now prove a slightly wasteful version of the Ruzsa modeling lemma, avoiding any assumption about the diameter of $B$. Set $q=8|T|$. Choose a prime $p$ larger than all $|t|$, $t\in T$, and much larger than $q$. Arbitrarily large primes exist by the elementary argument that a prime divisor of one plus the product of all primes up to a given bound exceeds that bound. For a uniformly chosen nonzero multiplier $r$ modulo $p$, each nonzero $t\in T$ has $rt$ uniform among the nonzero residues. Call a multiplier forbidden if some such $rt$ agrees modulo $p$ with $jq$, where $|jq|<p$. There are at most $2p/q+1\le 3p/q$ such residues. For $p\ge 4$, a union bound therefore makes the probability of being forbidden less thanChoose a nonforbidden $r$. Represent $rB$ by integers in $[0,p-1]$ and partition that interval into sixteen consecutive pieces of diameter less than $p/16$. One piece contains the images of a subset $B^{\prime }\subseteq B$ with $|B^{\prime }|\ge m/16$. Let $\varphi (b)$ be the integer representative of $rb$ in that piece, reduced modulo $q$.

A difference of eight sums of these representatives has absolute value less than $p/2$. If its original difference in $B$ is zero, it is a multiple of $p$, hence zero. Conversely, if its reduction modulo $q$ is zero, it equals $jq$ with $|jq|<p$; our choice of $r$ forces its original difference to be zero. This proves that $\varphi$ is a Freiman s-isomorphism of order eight. Injectivity follows by padding a one-term equality to eight terms with a fixed element. Consequently $D=\varphi (B^{\prime })\subseteq G=\mathbb{Z}/q\mathbb{Z}$ has subset densityNo primality of $q$ is needed.

Here is the cyclic Bogolyubov lemma with all its Fourier analysis on a finite abelian group details. Use $\hat{f}(r)={\mathbb{E}}_{x}f(x)e(-rx/q)$, $f=1_D$, and normalized convolution on a finite group. A finite geometric series proves orthogonality, and expanding the finite sums proves the Parseval identity on a finite group, Fourier inversion on a finite group, and $\widehat{f\ast g}=\hat{f}\hat{g}$. For $\tilde{f}(x)=f(-x)$, the nonnegative functionhas support exactly $2D-2D$ and Fourier coefficients on a finite abelian group $|\hat{f}(r){|}^4$. Put $\Gamma =\{r\ne 0:|\hat{f}(r)|\ge {\alpha }^{3/2}/\sqrt{8}\}$. The Parseval identity on a finite group gives $|\Gamma |\le 8{\alpha }^{-2}$. The total fourth moment of the frequencies outside $\Gamma \cup \{0\}$ is at most ${\alpha }^4/8$.

If $\Vert rx/q\Vert \le 1/16$ for every $r\in \Gamma$, then $\mathrm{Re}e(rx/q)\ge \cos (\pi /8)>3/4$. The zero frequency contributes ${\alpha }^4$ with no loss. Separating the large and small frequencies in Fourier inversion on a finite group yieldsThus $2D-2D$ contains the Bohr set expressed in distance coordinates by $\Vert rx/q\Vert \le 1/16$. This is consistent with the existing character-distance convention for a Bohr set: here it is enough that each character lies in the corresponding short arc around one.

We finally prove the needed nonwrapping progression in a cyclic Bohr set, including for composite $q$. Write $d=|\Gamma |$ and $Q=\lfloor q^{1/(d+1)}\rfloor$. Partition the $d$-dimensional unit cube into $Q^d$ boxes. The $Q^d+1$ points with coordinates $jr/q$ modulo one, $0\le j\le Q^d$, give by the pigeonhole principle an integer $1\le t\le Q^d$ with $\Vert rt/q\Vert \le 1/Q$ for all $r\in \Gamma$. ThenThese points are distinct modulo $q$, since their integer representatives lie between zero and $Q^{d+1}/16\le q/16$. Their number is at least $q^{1/(d+1)}/32$. For $d=0$ the same argument simply chooses $t=1$.

The Freiman s-isomorphism induces a bijection $\Phi :2B^{\prime }-2B^{\prime }\to 2D-2D$: define it on a representation by taking the same two positive and two negative images. Equality of representations uses an order-four relation, and injectivity uses the converse relation. If three consecutive members $y_{j-1},y_j,y_{j+1}$ of $P$ satisfy $y_{j-1}+y_{j+1}=2y_j$, their preimages satisfy the same equality, since its expansion is an equality of eight-term sums in $B^{\prime }$. Hence the inverse image of $P$ is an ordinary arithmetic progression in $2B^{\prime }-2B^{\prime }\subseteq 2A-2A$, with distinct terms.

To remove the multiplicative constant from the length bound, let $R=\lceil 8{\alpha }_0^{-2}\rceil$ and $\beta =1/(R+1)$. The length just proved is at least $c_{\theta }{n}^{\beta }$, where $c_{\theta }={\theta }^{2\beta }/32>0$. Choose $N_0\ge 3$ so that $c_{\theta }{n}^{\beta }\ge n^{\beta /2}$ for $n\ge N_0$, and set $\gamma =\min \{\beta /2,\log 3/\log N_0\}$. For $2\le n<N_0$, two distinct members of $A$ give a nonzero $u\in A-A$, and $\{-u,0,u\}\subseteq 2A-2A$ has length three, at least $n^{\gamma }$. For $n=1$, the singleton $\{0\}$ suffices. In every nonempty case,with $\gamma >0$ depending only on $\theta$. If empty sets are permitted, the required length is zero and there is no substantive assertion.

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.

Choose a nonempty $X\subseteq A$ for which $|X+A|/|X|$ is minimal, and write this minimum as $K^{\prime }$. Since $X=A$ is an available choice, $K^{\prime }\le K$. The Petridis minimal-growth lemma givesfor every finite $C$. Taking $C=(t-1)A$ and iterating yieldsfor every integer $t\ge 1$.

The Plünnecke-Ruzsa inequality says that if $A,B$ are finite nonempty subsets of an abelian group andthen for all nonnegative integers $m,n$,

Choose a nonempty $X\subseteq A$ minimizingthen $K^{\prime }\le K$. We first prove the Petridis minimal-growth lemmafor every finite $C$, by induction on $|C|$. Remove $c\in C$, write $C^{\prime }=C\setminus \{c\}$, and letThe new points contributed to $X+C$ by $X+c$ are exactly $|X\setminus X^{\prime }|$. Moreover, $X^{\prime }+B+c\subseteq (X+B+c)\cap (X+B+C^{\prime })$, soThe induction hypothesis, the identity $|X+B|=K^{\prime }|X|$, and minimality, which gives $|X^{\prime }+B|\ge K^{\prime }|X^{\prime }|$, yieldIteration with $C=(r-1)B$ gives