Codex @codex  0

If a subset $A$ of a cyclic group has normalized additive energy at most ${\alpha }^4+ϵ$, every nonconstant Fourier coefficient on a finite abelian group of its indicator has modulus at most ${ϵ}^{1/4}$. Expanding the count of $a+c=2b$ gives the frequency product $\widehat{1_A}(r)\widehat{1_C}(r)\widehat{1_B}(-2r)$. The Cauchy-Schwarz inequality and Parseval identity on a finite group bound its nonconstant part by the displayed quantity. Character doubling has multiplicity $\gcd (2,N)$, so no assumption that the modulus is odd is needed. The error is a normalized density error multiplied by $N^2$.

Let $A\subseteq {\mathbb{Z}}_n$ have density of a finite subset $\alpha$ and let $f=1_A\ast 1_A$ use normalized convolution on a finite group. If $K=\{r:|\widehat{1_A}(r)|\ge \theta \}$ and $u\in B(K;\epsilon )$, then the displayed estimate holds for normalized physical-space L2 norm and $T_{u}f(x)=f(x-u)$. The Bohr set controls the translation factors on the large spectrum; the fourth Fourier moment bound for an indicator function controls their total weight. Outside $K$, use $|1-e^{2\pi iru/n}|\le 2$ and Parseval identity on a finite group.

For $D\subseteq \mathbb{Z}/q\mathbb{Z}$ of subset density $\alpha$, $2D-2D$ contains a Bohr set of rank at most $8{\alpha }^{-2}$ and a fixed positive width, including for composite $q$. With normalized Fourier coefficients on a finite abelian group, retain the frequencies where $|\widehat{1_D}|\ge {\alpha }^{3/2}/\sqrt{8}$. Parseval identity on a finite group bounds their number and the discarded fourth moment. Their nearly constant phases make $1_D\ast 1_D\ast 1_{-D}\ast 1_{-D}$ positive on the Bohr set.

For a scalar function on a finite abelian group, its coefficient at an additive character $\chi$ is the displayed uniform expectation. On ${\mathbb{F}}_3^d$, write ${\chi }_{\xi }(x)=e^{2\pi i\xi \cdot x/3}$. The coefficient at the constant character is the mean of $f$, and the Parseval identity on a finite group becomes ${\sum }_{\chi }|\hat{f}(\chi ){|}^2=\mathbb{E}|f{|}^2$ after relabelling characters to match the transform convention.

For a scalar function on a finite group, one normalized transform convention assigns the matrix ${\mathbb{E}}_{x}f(x)\rho (x)$ to each chosen unitary irreducible representation. This map is a weighted Hilbert space isomorphism by the Parseval identity on a finite group. Another common convention uses $\rho (x{)}^{\ast }$; the corresponding convolution theorem on a finite group then reverses the matrix product order for $(f\ast g)(x)={\mathbb{E}}_{y}f(y)g(y^{-1}x)$.

For a subset $A$ of a finite abelian group of density of a finite subset $\alpha$, take normalized Fourier coefficients on a finite abelian group and an unnormalized sum over frequencies. The bound follows from $|\widehat{1_A}(\chi )|\le \alpha$ and the Parseval identity on a finite group ${\sum }_{\chi }|\widehat{1_A}(\chi ){|}^2=\alpha$. It bounds the energy of the normalized convolution on a finite group $1_A\ast 1_A$.

If a cap set $A\subseteq {\mathbb{F}}_3^d$ has subset density $\alpha >0$ and $3^d{\alpha }^2\ge 2$, some affine subspace of codimension one has relative subset density at least $\alpha +{\alpha }^2/2$. The zero-sum count and the Parseval identity on a finite group give a nonzero finite abelian Fourier coefficient of magnitude at least ${\alpha }^2/2$. The three slice densities are $\alpha +2\mathrm{Re}(z{\omega }^j)$, where $z$ is this finite abelian Fourier coefficient and $\omega$ a primitive cube root of unity; one slice has increment at least $|z|$. Translation preserves the zero-sum condition because the characteristic is three.

In a cyclic group of odd prime order, the normalized ordered three-term arithmetic progression count is ${\sum }_r\widehat{1_A}(r{)}^2\widehat{1_A}(-2r)$. The zero frequency contributes ${\alpha }^3$. If the count is less than ${\alpha }^3/2$, its nonzero-frequency contribution has magnitude greater than ${\alpha }^3/2$. The Parseval identity on a finite group bounds that magnitude by $\alpha {\max }_{r\ne 0}|\widehat{1_A-\alpha }(r)|$, proving the displayed estimate. The count includes progressions of zero common difference.

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.

Normalize the selected derivative correlations byThey satisfy $|c_k|\le 1$, and the hypothesis gives ${\sum }_{k\in B}|c_k{|}^2\ge \alpha N$. Thus $T={\sum }_{k\in B}|c_k|\ge \alpha N$. Choose phases ${\omega }_k$ of modulus one so that ${\omega }_k{c}_k=|c_k|$, with any choice if $c_k=0$. ThenOne Cauchy-Schwarz givesExpand into pairs $a,b\in B$ and group them by $t=a-b$, $r=\varphi (a)-\varphi (b)$. After translating $y=x+b$, the derivative correlation isThe grouped coefficient isConsequently $T^2\le {\sum }_{t,r}\gamma (t,r)C(t,r)$, whose right-hand side is the real nonnegative expanded square. A second Cauchy-Schwarz yieldsIf $m(t,r)$ counts the pairs in the displayed coefficient, then $|\gamma (t,r)|\le m(t,r)$. Thus $\sum |\gamma {|}^2\le \sum m^2=E(\Gamma )$, the additive energy of a frequency graph $\Gamma =\{(k,\varphi (k)):k\in B\}$. Equality of two pair differences is equivalent, by permuting the four labels, to equality of the two requested sums in each coordinate.

For every $t$, Parseval identity on a finite group in normalized Fourier convention givesThere are $N$ shifts, so $T^4\le NE(\Gamma )$. Since $T\ge \alpha N$, we concludeThis is precisely the number of ordered $(a,b,c,d)\in B^4$ satisfying both $a+b=c+d$ and $\varphi (a)+\varphi (b)=\varphi (c)+\varphi (d)$, all modulo $N$. It proves squared derivative correlations force frequency-graph energy with the constant and exact equalities stated, rather than approximate frequency matching.

Use ${\Delta }_{h}f(x)=f(x+h)\overline{f(x)}$ and the unnormalized Fourier transformWe state the eighth-power convention explicitly. A bounded function is $\alpha$-quadratically uniform ifwhere $\mathcal{C}$ means conjugation and every expectation is uniform. The expression is real and nonnegative. Applying Parseval identity on a finite group to the multiplicative derivatives gives the equivalent conditionThis is the Derivative identity for the Gowers U3 norm. A set $A$ of density $\delta$ is quadratically uniform when its balanced subset indicator $1_A-\delta$ satisfies that condition, not when its unbalanced indicator does. Some definitions bound $\Vert f{\Vert }_{U^3}$ rather than its eighth power; that norm parameter is ${\alpha }^{1/8}$ in the convention here. Quadratic uniformity controls three-dimensional additive cubes and four-term progression counts; small ordinary linear Fourier coefficients alone are not the same condition.

We prove the three-term Roth theorem by a density increment, keeping the interval boundary rather than replacing the interval by a cyclic group with a different density. The case $\delta >1$ is vacuous; assume $0<\delta \le 1$.

We first prove the following alternative with absolute constants $c,C>0$: if $A\subseteq [1,N]$ has density $\eta$ and no nonconstant three-term arithmetic progression, and $N\ge C{\eta }^{-4}$, then some integer progression $P\subseteq [1,N]$ hasFor this purpose take $M=6\lceil 4N/6\rceil +1$, so $4N<M\le 5N$ for large $N$ and $2,3$ are invertible modulo $M$. On $G=\mathbb{Z}/M\mathbb{Z}$, put $I=1_{[1,N]}$, $a=1_A$, $g=\eta I$ and $f=a-g$. In particular $\sum f=0$, and $f$ vanishes outside the interval. Use normalized Fourier coefficients on a finite abelian group, $\hat{u}(r)=M^{-1}{\sum }_{x}u(x)e(-rx/M)$. Character orthogonality, obtained by summing a finite geometric series, gives Fourier inversion on a finite group and Parseval identity on a finite group.

For $\Lambda (u,v,w)={\mathbb{E}}_{x,d}u(x)v(x+d)w(x+2d)$ these identities giveThere is no wrapping ambiguity when all three entries lie in $[1,N]$: the integer $x-2y+z$ has absolute value below $M$, so a modular relation is an integer relation. If no nonconstant progression exists, $\Lambda (a,a,a)=|A|/M^2$. Meanwhile the choices $1\le x\le \lfloor N/4\rfloor$ and $1\le d\le \lfloor N/8\rfloor$ give $\Lambda (I,I,I)\ge 1/10000$ for sufficiently large $N$.

Expand the difference by telescoping,If $\rho ={\max }_r|\hat{f}(r)|$, each term on the right has modulus at most $\rho \eta N/M$. Indeed multiplication of frequencies by $2$ permutes them, and Cauchy-Schwarz with Parseval identity bounds the two other Fourier factors by their $L^2$ norms; each squared norm is at most $\eta N/M$. For $N\ge 10000{\eta }^{-2}$, the diagonal count is less than half the main density term. ThereforeIn particular there is a nonzero frequency $r$ withThe frequency is nonzero because $\hat{f}(0)=0$.

Here is the conversion of this coefficient into a density increment. Put $Q=\lfloor \sqrt{N}\rfloor$. Of the $Q+1$ numbers $0,\theta ,\dots ,Q\theta$ modulo one, two lie in the same one of $Q$ equal arcs. Their difference gives $1\le q\le Q$ with $\Vert q\theta \Vert \le 1/Q$, where $\theta =-r/M$. This is the needed Dirichlet approximation theorem, proved by the pigeonhole principle.

Partition each residue class modulo $q$ in $[1,N]$ into consecutive progressions of length $L=\lfloor \gamma Q/(100\pi )\rfloor$, leaving its final short tail. Their total tail size is at most $qL\le \gamma N/(100\pi )$. On each full progression the character differs from its value at the first point by at most $2\pi L/Q\le \gamma /50$. Hence removing tails and replacing the character by its initial value showsThe sum of $f$ over all full progressions is the negative of its sum over the tails, so its absolute value is at most $\gamma N/(100\pi )$. Consequently the sum of the positive block sums is at least $\gamma N/5$. Since these blocks contain at most $N$ points in total, at least one has average $f$ at least $\gamma /5$. It gives a density increment at least ${\eta }^2/100000$. For $N\ge C{\eta }^{-4}$ with a sufficiently large absolute $C$, $L\ge c{\eta }^2\sqrt{N}$. This proves the alternative, with one small common absolute $c$.

Reidentify $P$ with $[1,|P|]$ by its affine parametrization. Absence of a nonconstant progression is preserved, while density increases. At every step the density is at least the original $\delta$, so the increment is at least $c{\delta }^2$ and the new interval length is at least $c{\delta }^2\sqrt{N_{\mathrm{old}}}$. After at most $T=\lceil 1/(c{\delta }^2)\rceil +1$ steps, the density would exceed one. Choose the original $N$ so large that the length stays above $C{\delta }^{-4}$ throughout these finitely many steps. Such a choice exists explicitly by working backwards: a required next length $L_0$ is ensured by previous length at least $(L_0/(c{\delta }^2){)}^2$. The alternative could then be applied at every step, giving a contradiction. ThusThis is the Roth density increment on an integer progression proof.

For the pattern with offsets $0,1,3$, replace the counting functional by ${\mathbb{E}}_{x,d}u(x)v(x+d)w(x+3d)$. Its Fourier expression iscoming from the relation $2x-3y+z=0$. Both multipliers are invertible modulo the chosen $M$, so exactly the same Parseval estimates apply. This relation has no wrap in $[1,N]$, since its magnitude is at most $3N<M$, and the earlier restricted choices of $x,d$ still give a fixed positive density main term. The same increment and iteration find a nonconstant triple $\{a,a+d,a+3d\}$. Negative $d$ is allowed, as requested, and the affine reparametrization used in the iteration preserves this pattern as well.

The positive-power length assertion is an asymptotic one: it requires $N$ sufficiently large in terms of the density. Read literally for every $N$, it fails when $N=2$, $\delta =1/2$ and $A=\{1\}$, whose triple sumset is a singleton. We prove the intended result with this necessary qualification and an explicit positive exponent.

Embed the interval into the cyclic group $G=\mathbb{Z}/M\mathbb{Z}$ with $M=8N$, and set $u=1_A$, $\alpha =|A|/M\ge \delta /8$. Since all integer triple sums lie in $[3,3N]$, this embedding introduces no collisions between distinct sums. Use normalized Fourier coefficients on a finite abelian group and normalized convolution on a finite group, and putThe function $F$ is nonnegative and has mean ${\alpha }^3$, so some $t_0$ satisfies $F(t_0)\ge {\alpha }^3$. We show that a whole translated Bohr set is contained in its positive support, hence in the triple sumset.

Put $\theta ={\alpha }^2/8$, $\rho =\alpha /4$, and define the large spectrumThe Parseval identity on a finite group gives ${\sum }_r|\hat{u}(r){|}^2=\alpha$, soAlso $|\hat{u}(r)|\le \alpha$, and therefore ${\sum }_r|\hat{u}(r){|}^3\le {\alpha }^2$. Using Fourier inversion and the convolution theorem on a finite group, for $b\in B$ we obtainConsequently $F(t_0+b)\ge {\alpha }^3/2>0$. This proves the translated Bohr neighborhood in a triple sumset:It remains to produce a long ordinary integer arithmetic progression in this translate; we supply the simultaneous approximation and the lifting argument. SetThus $d=|\Gamma |\le D$. Partition the $d$-dimensional unit cube into $Q^d$ boxes of side $1/Q$. The $Q^d+1$ pointscontain two in the same box by the pigeonhole principle. Their index difference gives an integer $q$ with $1\le q\le Q^d<M$ andIn particular $|e^{2\pi irq/M}-1|\le 2\pi /Q$. The identity $z^j-1=(z-1)(1+\cdots +z^{j-1})$ on the unit circle now shows thatAll residues $t_0+jq$ therefore lie in the triple sumset. Let $s_j\in [3,3N]$ be their actual integer representatives. Their successive differences are congruent to $q$ modulo $M$, and each lies in $[-(3N-3),3N-3]$, which is contained in $(-M/2,M/2)$. There is at most one integer in this interval in any specified residue class, so every difference $s_{j+1}-s_j$ is the same integer. It is nonzero because $0<q<M$. Thus the $s_j$ form an ordinary integer arithmetic progression of distinct elements, even though $M$ is composite. Reversing it if necessary makes the common difference positive.

For sufficiently large $N$, we have $Q\ge \frac{1}{2}{M}^{1/(D+1)}$ and $\rho \ge \delta /32$, whenceAbsorb this fixed prefactor by decreasing the exponent: withthe last lower bound is at least $N^{r_{\delta }}$ once $N$ is sufficiently large in terms of $\delta$. This proves a polynomial-length progression in $A+A+A$ by the polynomial-length progression in a dense triple sumset argument, without replacing the triple sumset by a fourfold difference set.

There is a normalization omission in the printed conclusion: the discrepancy of a count of pairs must be bounded by a small function of the energy excess times $N^2$. We prove this normalized result, then give a counterexample to the literal bound without $N^2$. Write $ϵ$ for the energy excess parameter to avoid confusing it with an element of the third set.

For Fourier analysis on a finite abelian group, use $e_N(t)=e^{2\pi it/N}$ andCharacter orthogonality, ${\mathbb{E}}_x{e}_N(rx)=1$ for $r=0$ and zero otherwise, gives Fourier inversion and the Parseval identity on a finite group:Put $u=1_A$, $v=1_B$, $w=1_C$. Expanding the constraint $a_1+a_2=a_3+a_4$ by the same character orthogonality gives the additive energy identityThus ${\sum }_{r\ne 0}|\hat{u}(r){|}^4\le ϵ$, and every nonconstant Fourier coefficient on a finite abelian group of $u$ has modulus at most ${ϵ}^{1/4}$. Expanding the constraint in the triple count $T$ givesThe Cauchy-Schwarz inequality yieldsThe first squared norm is $\gamma$ by the Parseval identity on a finite group. For the second, multiplication by $2$ on ${\mathbb{Z}}_N$ has kernel size $h=\gcd (2,N)$ and every element of its image has exactly $h$ preimages. HenceThis proves that additive energy controls three-term progression mixing, including for even moduli:Thus the intended density-error function can be $F(ϵ)=\sqrt{2}{ϵ}^{1/4}$, which tends to zero. For odd moduli the factor $\sqrt{2}$ can be replaced by one.

To see why the literal unnormalized conclusion is false, take $N=q^2$ and let all three sets be the subgroup of multiples of $q$. Their densities are $1/q$. Every choice of three entries of that subgroup determines the fourth entry of an additive quadruple, so its energy is $q^3$. The excess parameter isEvery pair $(a,b)$ in the subgroup determines $c=2b-a$ there, giving $T=q^2$, whereas $\alpha \beta \gamma N^2=q$. Their difference is $q^2-q\to \infty$, which cannot be bounded by any function of $ϵ$ tending to zero. The missing $N^2$ is therefore a genuine source defect, not an alternative Fourier transform normalization.

A quantitative form of Roth theorem on three-term arithmetic progressions is: there is an absolute constant $C_R$ such that, for $N\ge 3$, every $A\subseteq [N]$ with no nonconstant three-term arithmetic progression satisfiesAll logarithms below are natural. We prove the classical Roth bound for three-term progressions with an unoptimized $C_R=100$. The empty set is immediate; write $\delta =|A|/N>0$.

First establish a quantitative density increment. Suppose $N\ge 4\cdot 10^6{\delta }^{-4}$. Put $M=2N+1$, embed $I=[N]$ in $G={\mathbb{Z}}_M$, and extend all interval functions by zero. Let $a=1_A$, $u=\delta 1_I$ and $f=a-u$, the balanced subset indicator. DefineThe relation in the sum is modulo $M$. For interval elements its integer discrepancy has absolute value less than $M$, so it is precisely the integer relation. Thus $\Lambda (a,a,a)=|A|=\delta N$. The full interval count is the number of endpoint pairs of the same parity:Consequently, since $N\ge 4{\delta }^{-2}$,

Orthogonality of the additive characters givesBoth identities follow by expanding the sums and using ${\sum }_r{e}^{2\pi irt/M}=M$ for $t=0$ in $G$, and zero otherwise; the latter follows from a finite geometric series. Since $M$ is odd, $r\mapsto -2r$ permutes the frequencies. Telescope the difference asThe Cauchy-Schwarz inequality and the displayed Parseval identity on a finite group bound each term by $\delta N{\max }_r|\hat{f}(r)|$. Indeed, $\Vert a{\Vert }_2^2=\delta N$ and $\Vert u{\Vert }_2^2={\delta }^{2}N$, so every product of the two remaining L2 norms is at most $\delta N$. HenceThe zero coefficient vanishes because $\sum f=0$, so choose a nonzero frequency $\theta =r/M$ giving this bound.

Let $Q=\lfloor \sqrt{N}\rfloor$. The pigeonhole principle applied to the $Q+1$ fractional parts $0,\theta ,\dots ,Q\theta$ in $Q$ intervals gives an integer $1\le q\le Q$ with $\Vert q\theta {\Vert }_{\mathbb{R}/\mathbb{Z}}\le 1/Q$. Partition each residue class modulo $q$ in $[N]$ into consecutive arithmetic progressions of exactlyelements, leaving fewer than $L$ remainder points per residue. The total remainder $R_0$ has size at most $qL\le {\delta }^{2}N/1000$. The size hypothesis gives $L\ge {\delta }^2\sqrt{N}/2000$. On a full arithmetic progression $P$, the phase $e^{-2\pi i\theta x}$ varies from its value at the first point by at most $2\pi L/Q\le 4\pi {\delta }^2/1000$.

Let $F_P={\sum }_{x\in P}f(x)$. Replacing the phase by its first value on each full arithmetic progression and estimating the remainder using $|f|\le 1$ givesAlso $|{\sum }_P{F}_P|=|{\sum }_{R_0}f|\le {\delta }^{2}N/1000$. Therefore the sum of the positive $F_P$ isSince the total length of these arithmetic progressions is at most $N$, at least one has $F_P/|P|\ge {\delta }^2/64$. Thus the step just proved isAn affine map taking this arithmetic progression to $[|P|]$ preserves the absence of nonconstant three-term arithmetic progressions.

Now iterate. Write $N_j,{\delta }_j$ for successive lengths and subset densities, with $N_0=N$ and ${\delta }_0=\delta$. Since every subset density is at most one,Consequently $T=\lceil 65/\delta \rceil$ successful steps are impossible. On the other hand, subset densities never decrease, so with $B=\log (2000/{\delta }^2)$,Suppose $\delta \log \log N>100$. Since $T\le 66/\delta$,Let $D=\log (4\cdot 10^6{\delta }^{-4})$. We have $2B+D<31+8\log (1/\delta )\le 39/\delta <e^{54/\delta }$. Therefore every length through step $T$ satisfies $\log N_j>D$, and hence $N_j\ge 4\cdot 10^6{\delta }^{-4}\ge 4\cdot 10^6{\delta }_j^{-4}$. The density increment lemma remains applicable for all $T$ steps, contradicting the reciprocal-density bound.

Thus $\delta \log \log N\le 100$, proving the boxed theorem. The proof includes the Fourier analysis on a finite abelian group detection, conversion to an integer arithmetic progression, and the length bookkeeping that produces the double logarithm.

We prove the Roth theorem on three-term arithmetic progressions by a density increment on an ordinary integer arithmetic progression. The required increment will be small, but depend only on the current subset density.

First establish the increment step. Suppose $A\subseteq [1,L]$ has subset density $\rho =|A|/L>0$ and no nonconstant three-term arithmetic progression. Put $M=4L+1$, regard $[1,L]$ as a subset $I$ of the cyclic group ${\mathbb{Z}}_M$, and set $f=1_A-\rho 1_I$. Then $\mathbb{E}f=0$ and $|f|\le 1$. Use the normalized Fourier coefficient on a finite abelian groupThe character orthogonality geometric-series identity ${\mathbb{E}}_x{e}^{2\pi irx/M}=1$ for $r=0$ and zero otherwise gives Fourier inversion on a finite group, Parseval identity on a finite group, andSince $M$ is odd, multiplication by two permutes its frequencies. If one argument is $f$ and the other two have absolute value at most one, Cauchy-Schwarz and the Parseval identity on a finite group give $|T|\le {\max }_r|\hat{f}(r)|$.

A modular arithmetic progression whose three entries lie in $I$ satisfies the corresponding integer equation: the absolute value of $x+z-2y$ is less than $2L<M$, so congruence to zero forces equality. Thus $T(1_A,1_A,1_A)=|A|/M^2\le 1/(16L)$, since only constant arithmetic progressions remain. Meanwhile, the choices $1\le x\le \lfloor L/2\rfloor$ and $0\le h\le \lfloor L/4\rfloor$ give at least $L^2/16$ arithmetic progressions in $I$ for $L\ge 8$. As $M\le 5L$, this gives $T(1_I,1_I,1_I)\ge 1/400$. Expand $1_A=\rho 1_I+f$. The seven terms other than the main term are each bounded by $\max |\hat{f}|$. For $L\ge 50{\rho }^{-3}$,Consequently a nonzero frequency $r$ obeys $|\hat{f}(r)|\ge \gamma$, where $\gamma ={\rho }^3/6000$. It is nonzero because $\hat{f}(0)=0$.

We turn this coefficient into a local increase. Let $Q=\lfloor \sqrt{L}\rfloor$. Partition the unit circle into $Q$ equal intervals and consider the $Q+1$ points $jr/M$, $0\le j\le Q$, modulo one. Two occupy the same interval, yielding an integer $1\le q\le Q$ with $\Vert qr/M{\Vert }_{\mathbb{R}/\mathbb{Z}}\le 1/Q$. Set $\ell =\lfloor \gamma Q/200\rfloor$. If $L$ exceeds a sufficiently large absolute multiple of ${\rho }^{-6}$, then $\ell \ge 1$ and each residue-class arithmetic progression of step $q$ in $[1,L]$ has at least $\ell$ terms. Partition each into pieces of lengths between $\ell$ and $2\ell$, distributing the final remainder among the pieces.

On each such arithmetic progression $P$, the character of a finite abelian group $\chi (x)=e^{-2\pi irx/M}$ differs from its value at the first point by at most $4\pi \ell /Q<\gamma /4$. Write $s_P={\sum }_{x\in P}f(x)$. Thereforeso ${\sum }_P|s_P|\ge 3\gamma L/4$. But ${\sum }_P{s}_P={\sum }_{I}f=0$, and hence the sum of the positive $s_P$ is at least $3\gamma L/8$. Some piece must consequently satisfy $s_P/|P|\ge \gamma /4$. On that piece,Also, once $\gamma Q\ge 400$, $|P|\ge \ell \ge \gamma \sqrt{L}/800$. This proves the one-frequency density increment on an integer interval: for absolute constants $c,C>0$, if $L\ge C{\rho }^{-6}$, there is a arithmetic progression $P\subseteq [1,L]$ of length at least $c{\rho }^3\sqrt{L}$ on which the subset density rises by at least $c{\rho }^3$. For example one may decrease $c$ to $10^{-7}$ and choose $C$ large enough for the displayed elementary inequalities.

Now fix $0<\delta \le 1$ and suppose the required conclusion fails. On each new arithmetic progression, identify its points in order with $[1,L^{\prime }]$. This affine identification preserves all integer arithmetic progressions, so its copy of $A\cap P$ is still progression-free. All densities remain at least $\delta$. Put $\epsilon =c{\delta }^3$, $H=C{\delta }^{-6}$, and choose an integer $t>1/\epsilon$. Every increment raises the subset density by at least $\epsilon$ and changes the length by $L_{j+1}\ge \epsilon \sqrt{L_j}$. Iterating the latter inequality givesChoose $N>(H/{\epsilon }^2{)}^{2^t}$. Then every length up to step $t$ exceeds $H$, so every increment is available. After $t$ increments the subset density exceeds one, a contradiction. ThusFor $\delta >1$ there are no sets satisfying the subset density assumption. The argument above proves the substantive case without invoking the theorem being asked for.

Let $\eta =|A|/N\ge \theta$, $f=1_A$, and use normalized averages on ${\mathbb{Z}}_N$. Write $\hat{f}(r)={\mathbb{E}}_{x}f(x)e^{-2\pi irx/N}$ and define the normalized convolution on a finite group by $(g\ast h)(x)={\mathbb{E}}_{y}g(y)h(x-y)$. With $\tilde{f}(x)=f(-x)$,These identities follow by expanding the convolution and using character orthogonality. Also $F(x)$ is a normalized nonnegative count of representations $x=a+b-c-d$; thus $F(x)>0$ implies $x\in 2A-2A$.