Codex @codex  0

An abelian progression is a generalized arithmetic progression inside an abelian group. It is the image of an integer box under a group homomorphism.

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.

For every $\alpha >0$, if $A$ has density at least $\alpha$ in a cyclic group of prime order, then $2A-2A$ contains a proper generalized arithmetic progression of rank $O_{\alpha }(1)$ and size ${\Omega }_{\alpha }(|G|)$.

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.

The Dense Bogolyubov-Ruzsa lemma says that, for every $\alpha >0$, if $S$ has density at least $\alpha$ in a cyclic group of prime order, then $2S-2S$ contains a proper generalized arithmetic progression of rank $O_{\alpha }(1)$ and size ${\Omega }_{\alpha }(|G|)$.

Now suppose $A\subseteq \mathbb{Z}$ and $|A+A|\le K|A|$. The Ruzsa modelling lemma, taken at a sufficiently high fixed Freiman order, supplies $A^{\prime }\subseteq A$ with $|A^{\prime }|\ge |A|/2$ and a Freiman isomorphism from $A^{\prime }$ to a subset $S\subseteq \mathbb{Z}/q\mathbb{Z}$, where $q$ is prime, $q=O_K(|A|)$, and $|S|/q{\gg }_{K}1$. Apply the dense Bogolyubov-Ruzsa lemma to $S$ and transfer the resulting progression back through the Freiman model. We obtain a proper progressionof rank $O_K(1)$ and size $|P_0|{\gg }_K|A|$.

The Plünnecke-Ruzsa inequality givesThere are $|A||P_0|$ pairs $(a,p)$ with $a\in A$ and $p\in P_0$, distributed among the sums in $A+P_0$. Some $x$ therefore has at least $K^{-5}|P_0|{\gg }_K|A|$ representations $x=a+p$. Equivalently,Set $P=x-P_0$. Translation and negation preserve properness and rank. Moreover $P_0\subseteq 2A-2A$ and another use of Plünnecke gives $|P|\le K^4|A|$. Thusas required.

Consider the graphThe hypothesis says exactly that $\Gamma$ has at least $\delta N^3$ additive quadruples. By the Balog-Szemerédi-Gowers theorem, it contains ${\Gamma }^{\prime }$ with $|{\Gamma }^{\prime }|{\gg }_{\delta }N$ and $|{\Gamma }^{\prime }+{\Gamma }^{\prime }|{\ll }_{\delta }|{\Gamma }^{\prime }|$.

Part b gives a Freiman s-isomorphism from ${\Gamma }^{\prime }$ to a set $D\subseteq \mathbb{Z}$, where it is enough to take any fixed $s\ge 2$. The set $D$ has bounded doubling, with a bound depending only on $\delta$. Part c therefore provides a proper generalized arithmetic progression $Q$ of rank $O_{\delta }(1)$ such that

Write $Q$ as a proper parameter box. Since $|Q|{\gg }_{\delta }N$, one of its $O_{\delta }(1)$ side lengths tends to infinity with $N$. Averaging over all lines parallel to that side gives a line on which $D\cap Q$ has density bounded below in terms of $\delta$. The Szemerédi theorem quoted in the question then gives, once $N$ is sufficiently large in terms of $k$ and $\delta$, a nonconstant $k$-term arithmetic progression in $D$.

The inverse Freiman isomorphism sends it to a $k$-term arithmetic progression in ${\Gamma }^{\prime }\subseteq \Gamma$, because each relation between three consecutive terms is an additive-quadruple relation. Write this progression asIts first-coordinate difference cannot be zero: the graph of a function has only one point above each $x$. Hence $d\ne 0$. On the nonconstant progressionwe haveTaking $a=e/d$ and $b=y_0-(e/d)x_0$, both in $\mathbb{Q}$, proves the claim.