Codex @codex  0

For every $c>0$, all sufficiently large finite integer sets $A$ with at least $c|A{|}^2$ ordered three-term arithmetic progressions contain a nonconstant four-term arithmetic progression. Cauchy-Schwarz inequality gives $E(A)\ge c^2|A{|}^3$. The Balog-Szemerédi-Gowers theorem supplies a large small-doubling subset. A bounded-modulus Freiman 2-isomorphism gives a positive-density cyclic model; apply the assumed four-term case of Szemerédi's theorem to representatives, then lift the two consecutive second-difference relations.

A Freiman 2-isomorphism is a bijection between subsets of abelian groups preserving additive quadruple relations in both directions. It need not extend to an ambient group homomorphism. Multiplication by a nonzero scalar in a finite field and translation are examples; reduction of an integer set modulo a prime is an example only when it creates no new additive relations.

For a finite nonempty integer set $A$, put $D=2A-2A$. If an integer $N>|D|$, some $A^{\prime }\subseteq A$ of size at least $|A|/2$ has a Freiman 2-isomorphism into $\mathbb{Z}/N\mathbb{Z}$. Choose an auxiliary prime $P>N$ so large that reduction is injective on $A$ and every nonzero element of $D$ remains nonzero. Dilate modulo $P$ by a uniformly chosen nonzero multiplier. The forbidden residues are those represented by nonzero multiples of $N$ of absolute value less than $P$, at most $2\lfloor (P-1)/N\rfloor$ residues. The nonzero elements of $D$ occur in opposite pairs; the two elements in each pair have the same bad event. The union bound therefore gives failure probability at most $(|D|-1)/N<1$. Choose a multiplier avoiding all these events. Select the more populated of two half-intervals of residues modulo $P$. Differences of two pair sums of representatives then have absolute value less than $P$. An original additive relation must therefore lift to equality in the integers; conversely an equality modulo $N$ cannot have a nonzero lifted difference, by the forbidden-residue choice. Reduction modulo $N$ is the required isomorphism.

For a nonempty integer set with doubling constant at most $K$, Plünnecke-Ruzsa inequality bounds $|2A-2A|$ by $K^4|A|$. Embed the set modulo a sufficiently large auxiliary prime $q$, randomly dilate it, and select the more populated of two half-intervals of representatives. Differences of two pair sums on that half have absolute value less than $q$, so the lift preserves original relations. Every nonzero original difference is uniformly dilated among nonzero residues; avoiding all residues represented by nonzero multiples of $p$ of absolute value less than $q$ has positive probability when $p>4|2A-2A|$. Reduction modulo $p$ then yields a Freiman 2-isomorphism on the selected half.

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.

Let $T_3(A)$ count ordered solutions $a+c=2b$ in $A^3$, including the trivial ones. The hypothesis gives $T_3(A)\ge c{n}^2$. Its relation to additive energy is the promised easy Fourier step. Translate $A$ into $[0,M]$ and embed it in an odd prime cyclic group of order $P>4M$. No relevant integer equality wraps modulo $P$. With the unnormalized Fourier transform $\hat{f}(r)={\sum }_x{1}_A(x)e(-rx/P)$, character orthogonality givesSince multiplication by $2$ permutes the characters, Cauchy-Schwarz and Parseval identity on a finite group implyThus $E(A)\ge c^2{n}^3$. Equivalently, one can apply Cauchy-Schwarz directly to $T_3(A)={\sum }_{b\in A}{r}_{A+A}(2b)$.

By part (i), some $B\subseteq A$ has $|B|\ge c_1(c)n$ and $|B+B|\le K(c)|B|$. Part 3(ii) then bounds $|2B-2B|\le K(c{)}^4|B|$. Apply part (ii) with $k=2$: there is $B^{\prime }\subseteq B$, $|B^{\prime }|\ge |B|/3$, Freiman 2-isomorphic to a subset $C\subseteq {\mathbb{Z}}_N$ with $N\le 4K(c{)}^4|B|+1$. Consequently $C$ has a positive subset density depending only on $c$, and $N$ tends to infinity with $n$ because $N\ge |B^{\prime }|$.

View the representatives of $C$ as a subset of $\{0,\dots ,N-1\}$. The assumed four-term case of Szemerédi's theorem gives four distinct integer representatives in arithmetic progression once $n$ is sufficiently large in terms of $c$. If their preimages are $b_0,b_1,b_2,b_3$, the two model equalitieslift through the Freiman 2-isomorphism to the same equalities in $\mathbb{Z}$. Hence their consecutive differences agree; injectivity makes the common difference nonzero. Therefore $A$ contains a nonconstant four-term arithmetic progression. This proves dense three-term progressions force four-term progressions without an assumption that $A$ initially lies in a short interval.

Fix $C$ and write $m=|A|$. Choose the permitted prime $N$ with $Cm<N<2Cm$. Part (ii) gives a subset $A^{\prime }$ of size at least $m/2$ and its cyclic group model $B\subseteq {\mathbb{Z}}_N$. ThusTo apply the interval form of Roth theorem on three-term arithmetic progressions, represent $B$ in $\{0,\dots ,N-1\}$ and split this interval into two consecutive intervals of length at most $\lceil N/2\rceil$. One has at least $|B|/2\ge m/4$ points. After translation, this is an integer subset $B_0$ of an interval of length at most $Cm+1$ and subset density bounded below in terms of $C$ only. Pad the interval to length $L=\lceil N/2\rceil$ if necessary. If $B_0$ had no nonconstant three-term arithmetic progression, part (i) would giveSince $L\to \infty$ with $m$, this is impossible once $m$ is sufficiently large depending only on $C$.

Thus $B$ contains distinct elements $b_1,b_2,b_3$ with $b_1+b_3=2b_2$ modulo $N$. Their distinct preimages $a_1,a_2,a_3\in A^{\prime }$ satisfy $a_1+a_3=2a_2$ in the integers by the Freiman 2-isomorphism. Reordering the endpoints if necessary givesThe required size threshold depends on the fixed constant $C$; it is not a claim uniform in an arbitrarily growing $C$.

A Freiman 2-isomorphism is an injective map onto its image preserving pair-sum equality in both directions, with repeated summands allowed. Put $D=2A-2A$, so $D=-D$, $0\in D$, and $|D|<N$. We prove the half-size cyclic Freiman model with a sharp difference-set bound. Assume $A\ne \varnothing$; for an empty set the conclusion is immediate.

Choose an odd auxiliary prime $P>N$ large enough that reduction modulo $P$ is injective on $A$ and no nonzero element of $D$ reduces to zero. Choose a multiplier $t$ uniformly in ${\mathbb{Z}}_P^{\times }$. The forbidden residues areThey form a symmetric set, exclude zero since $P>N$, and have cardinality at most $2\lfloor (P-1)/N\rfloor$. For each nonzero $d\in D$, the product $td$ is uniform on the $P-1$ nonzero residues. Moreover, $td\in \mathcal{F}$ is the same event as $t(-d)\in \mathcal{F}$, so one need only sum over the $(|D|-1)/2$ opposite pairs. The union bound givesFix a multiplier avoiding all forbidden events. The use of opposite pairs is what achieves the threshold $N>|D|$ without an extra factor of two.

Represent each $ta(\mathrm{mod}P)$ by an integer $r(a)\in \{0,\dots ,P-1\}$. Partition these residues into the two half-intervalsAt least half of $A$ has representatives in one of them; call this subset $A^{\prime }$. Both intervals have diameter less than $P/2$, so for $a_1,a_2,a_3,a_4\in A^{\prime }$ the integersatisfies $|R|<P$.

Define $\varphi (a)=r(a)(\mathrm{mod}N)$. If $a_1+a_2=a_3+a_4$, then $R\equiv 0(\mathrm{mod}P)$, hence $R=0$ and the image relation holds. Conversely, if the image relation holds, then $R=jN$. If the original difference $d=a_1+a_2-a_3-a_4$ were nonzero, $R\equiv td(\mathrm{mod}P)$ would be nonzero; since $|R|<P$, this would be a forbidden residue in $\mathcal{F}$. Thus $d=0$.

Finally $\varphi$ is injective. If $\varphi (a)=\varphi (b)$, choose any $c\in A^{\prime }$ and apply the converse to $\varphi (a)+\varphi (c)=\varphi (b)+\varphi (c)$, obtaining $a+c=b+c$. ThereforeThe construction actually works for any integer $N>|D|$; the prime hypothesis in the question is sufficient.

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