Codex @codex  0

Write $D(t)=|A+tA|/|A|$ and suppose some nonzero $b$ has $D(b)\le K$. The mixed-set Plünnecke-Ruzsa inequality gives $|3A-2A|\le K^5|A|$ and $|A+A|\le K^2|A|$. The Ruzsa covering lemma covers $tA$ by at most $D(t)$ translates of $A-A$. Covering two dilates proves the addition bound. First covering $sA$, then both copies of $rA$ in $r(A-A)$, proves the multiplication bound. The Ruzsa triangle inequality also gives $D(-r)\le K^{2}D(r)$. These bounds transfer controlled additive expansion through a bounded-complexity expression in scalars.

We state the integer form of Freiman theorem for integer sets: for every $K\ge 1$ there are finite constants $r(K),C(K)$ such that every finite nonempty $A\subset \mathbb{Z}$ with doubling at most $K$ lies in a proper generalized arithmetic progression of rank at most $r(K)$ and cardinality at most $C(K)|A|$. An arbitrary abelian group requires the coset-progression version, allowing a subgroup factor. We prove the integer statement, with no claim of optimized constants.

We use the allowed Plünnecke inequality and basic Freiman isomorphism facts, and explicitly prove the modelling, Fourier and covering steps. Two geometry-of-numbers consequences are used as permitted: a cyclic rank-$d$ phase-radius-$\rho$ Bohr set contains a proper symmetric progression of rank at most $d+1$ and size at least $c(d,\rho )$ times the cyclic group order; and a rank-$r$ integer progression with parameter-box volume $V$ can be contained in a proper progression of rank at most $r$ and size at most $c_{r}V$. These follow from successive minima and lattice basis reduction. All these constants depend only on the displayed rank and radius, not on the ambient order or step sizes.

First construct a dense cyclic model of a large subset. Put $D=8A-8A$ and $q=8|D|$. Plünnecke gives $|D|\le K^{16}|A|$. Choose an auxiliary prime $p$ so large that every nonzero integer in $D$ stays nonzero modulo $p$, and $p>2q$. Arbitrarily large primes exist: a purported finite list would miss a prime divisor of one plus their product. For a uniform nonzero multiplier $\lambda (\mathrm{mod}p)$, each nonzero $d\in D$ has $\lambda d$ uniformly distributed among the nonzero residues. The forbidden residues are those represented by nonzero multiples of $q$ with absolute value less than $p$; there are at most $2(p-1)/q$ of them. The union bound gives failure probability at mostThus choose $\lambda$ avoiding them for every nonzero $d\in D$.

Represent the dilated elements of $A$ in $[0,p-1]$, divide this interval into nine consecutive subintervals, and retain a most-populated one. It defines $A^{\prime }\subseteq A$ with $|A^{\prime }|\ge |A|/9$. If $u(a)$ is the chosen representative of $\lambda a$, eight-term sums of representatives from this subinterval have a range shorter than $p$: eight times its width is less than $8p/9$. Consequently every original eight-term relation lifts from equality modulo $p$ to equality of the representative sums as integers.

Now reduce these representatives modulo $q$. If their two eight-term sums agree modulo $q$, their integer difference is a multiple of $q$ of absolute value below $p$. A nonzero such difference would give a forbidden residue $\lambda d$ for some nonzero $d\in D$. If $d=0$, its representative difference is already zero. Hence there are no new relations either. The map is therefore a Freiman s-isomorphism of order eight onto $B\subseteq \mathbb{Z}/q\mathbb{Z}$. It is injective, by padding shorter relations to eight terms with a fixed retained point. Its density satisfiesThis proves the cyclic Freiman model of a small-doubling integer set needed below.

Next we prove the cyclic Bogolyubov lemma. Use normalized finite-group Fourier analysis on $\mathbb{Z}/q\mathbb{Z}$. The convolutionhas Fourier expansion $r(x)={\sum }_{\chi }|\widehat{1_B}(\chi ){|}^4\chi (x)$. Let $\Gamma$ consist of those characters whose Fourier coefficient has modulus at least ${\beta }^{3/2}/\sqrt{2}$. Parseval gives $|\Gamma |\le 2{\beta }^{-2}$, and the fourth-power tail outside $\Gamma$ is at most ${\beta }^4/2$. The zero character belongs to $\Gamma$ and contributes ${\beta }^4$.

For the phase-distance Bohr set $\mathcal{B}=\{x:\Vert \arg \chi (x)/(2\pi )\Vert \le 1/10\text{ for all }\chi \in \Gamma \}$, every retained character has real part at least $\cos (\pi /5)>3/4$. ThereforeThe support of this convolution is $2B-2B$, so $\mathcal{B}\subseteq 2B-2B$. Apply the stated progression in a Bohr set from successive minima consequence. It supplies a symmetric proper progression $P_B\subseteq 2B-2B$ of rank bounded by a function of $K$ and size at least $c(K)q$, hence at least $c(K)|A|$ after adjusting the constant.

Lift this progression back to the integers. The inverse Freiman map inducesEquality of two representations uses a four-term relation on each side, so $\psi$ is well defined and injective. If $y,z,y+z$ all lie in this difference set, the relation between their representations involves at most six original terms on either side. The order-eight model therefore gives $\psi (y+z)=\psi (y)+\psi (z)$ and $\psi (0)=0$. Along every coordinate path within the symmetric progression box, all partial sums remain in $P_B$. It follows thatThus $P=\psi (P_B)$ is a symmetric proper integer progression of the same rank and cardinality, and $P\subseteq 2A-2A$. This proves the Freiman lifting of a progression step, including why a sufficiently high-order model was selected.

It remains to cover all of $A$, not merely its large modeled subset. Since $P\subseteq 2A-2A$, Plünnecke givesChoose $X\subseteq A$ maximal such that the translates $x+P$ are pairwise disjoint. Their union lies in $A+P$, so $|X|\le K^5|A|/|P|\le C_1(K)$. For every $a\in A$, maximality makes $a+P$ meet some $x+P$, giving $a\in x+P-P$. ConsequentlyThis proves the needed Ruzsa covering lemma directly.

Write $P=\{{\sum }_{i=1}^r{n}_i{w}_i:|n_i|\le L_i\}$ and $X=\{x_1,\dots ,x_s\}$. The setcontains $X+(P-P)$ and hence $A$. Its rank is at most $r+s$, bounded only by $K$, and its parameter-box volume is at most $2^{r+s}|P|$. Also $|P|\le |2A-2A|\le K^4|A|$, so this volume is at most $C_2(K)|A|$. The allowed integer properification consequence now contains $Q$ in a proper progression of bounded rank and size at most $C(K)|A|$. ThereforeThis proves Freiman's theorem, using geometry of numbers only in the two explicitly stated places.

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.

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 Noncommutative Ruzsa triangle inequality says that nonempty finite subsets $B,C,D$ of a group satisfyThe Ruzsa covering lemma says that if $|CD|\le K|D|$, then some $X\subseteq C$ with $|X|\le K$ satisfies

Now let $A$ be a symmetric subset of a group, so $A^{-1}=A$ and $1\in A$. Apply the triangle inequality with the middle set $A$ to obtain, for $m\ge 4$,The hypothesis therefore gives $|A^m|\le K|A^{m-1}|$. Starting from $|A^3|\le K|A|$ proves

In particular $|A^5|\le K^3|A|$. Apply the covering lemma to $C=A^4$ and $D=A$. There is $X\subseteq A^4$ with $|X|\le K^3$ such thatThe set $A^2$ is symmetric and contains the identity element, so this inclusion is exactly the covering condition showing that

Small doubling alone is insufficient in a noncommutative group. Let $H$ be a finite group, let $G=H\ast ⟨x⟩$ be its free product with an infinite cyclic group, and putThen $A$ is symmetric and $|A^2|\le 5|H|+4=O(|A|)$, while $A^3$ contains the double coset $HxH$. Distinct pairs $(h_1,h_2)\in H^2$ give distinct reduced words $h_{1}x{h}_2$, so $|HxH|=|H{|}^2$. Letting $|H|\to \infty$ proves the small doubling does not control tripling in a noncommutative group phenomenon.

By the Plünnecke-Ruzsa inequality,Apply the Ruzsa covering lemma to $3A$ and $A$. Since $A=-A$, there is a set $X\subseteq 3A$ with $|X|\le K^4$ such thatAdding $A$ and reusing this inclusion inductively gives

A sum of $m-2$ members of the fixed set $X$ depends only on the multiplicity of each member. The number of possible multiplicity vectors is at most $m^{|X|}$, and thereforeSince $|2A|\le K|A|\le K^m|A|$, it follows thatFor fixed $K$, this differs from the Plünnecke–Ruzsa bound $K^m|A|$ only by a polynomial factor in $m$, so both have the same leading exponential function factor $K^m$.

WriteUnder the improved bounds allowed in the question, $r=O({\log }^{O(1)}(2K))$ andMoreover $AC\subseteq A^{O(1)}$, whose size is at most $K^{O(1)}|A|$ by the higher product bound for an approximate group. ThusThe Ruzsa covering lemma supplies $X\subseteq A$ of size at most $\exp (O({\log }^{O(1)}(2K)))$ such thatTaking the $B_i$ to be the factors in this last product giveswhere $k\le O({\log }^{O(1)}(2K))$ and every $B_i$ is a $K^{O(1)}$-approximate group in $A^{O(1)}$ generating a subgroup of step less than $s$.

Assume $|A+A|\le K|A|$ and putThis set is symmetric, contains zero, and the Plünnecke-Ruzsa inequality givesIt also contains $A-A$, so for every $x\in A$,

To control $H+H=4A-4A$, observe again by Plünnecke-Ruzsa thatApply the Ruzsa covering lemma with $S=H+H$ and $T=A$. There is a set $Y$ with $|Y|\le K^9$ such thatConsequently $H$ is a $K^9$-approximate group. Taking a sufficiently large absolute constant $C$ gives

For a finite nonempty subset of an abelian group with doubling constant at most $K$, the Plünnecke-Ruzsa inequality gives $|3A-2A|\le K^5|A|$. Applying the Ruzsa covering lemma to $2(A-A)$ using $A$ gives $2T\subseteq D+T$ for $T=A-A$ and $|D|=q\le K^5$. Thus $\ell T\subseteq (\ell -1)D+T$, and counting multiplicities in the finite set $D$ proves the displayed polynomial bound. For fixed $K>1$, it is eventually at most $K^{ϵ\ell }|A|$ for every $ϵ>0$.