Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 88 / 2

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.

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.

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