Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 11 / 1 / Solution

The Roth theorem on three-term arithmetic progressions says that, for every $\delta >0$, every sufficiently long integer interval contains a nonconstant three-term arithmetic progression in every subset of subset density at least $\delta$. We prove this by a density increment, giving the intermediate Fourier and partition arguments.

Let $A\subseteq I=[N]$ have subset density $\alpha >0$ and contain no nonconstant three-term arithmetic progression. Embed $I$ in the odd-order cyclic group $G=\mathbb{Z}/M\mathbb{Z}$, where $M=2N+1$, and extend its indicator function by zero. Use normalized Fourier coefficients on a finite abelian groupFor the normalized progression count,the orthogonality of characters and Fourier inversion giveThere is no modular wraparound when $x,y,z\in I$, since both $x+z$ and $2y$ lie between $2$ and $2N$. Only constant progressions occur in $A$, so $T(1_A,1_A,1_A)=\alpha N/M^2$. In the interval $I$, endpoints of the same parity have an integer midpoint, giving at least $N^2/2$ ordered progressions.

Put $b=\alpha 1_I$ and $f=1_A-b$, so $\hat{f}(0)=0$. If $N\ge 4{\alpha }^{-2}$, the difference in progression counts satisfiesTelescope the difference in the other order as $T(f,1_A,1_A)+T(b,f,1_A)+T(b,b,f)$. By Parseval identity and the Cauchy-Schwarz inequality, each term has absolute value at mostIndeed $\Vert 1_A{\Vert }_2^2=\alpha N/M$, $\Vert b{\Vert }_2^2={\alpha }^{2}N/M$, and multiplication by $-2$ permutes the frequencies because $M$ is odd. It follows that a nonzero frequency $r$ satisfiesThus the unnormalized Fourier correlation has absolute value at least $\beta N$.

Write $\theta =r/M$ and $q=\lfloor \sqrt{N}\rfloor$. To prove the needed case of the Dirichlet approximation theorem, place the $q+1$ fractional parts $0,\theta ,\dots ,q\theta$ in $q$ equal subintervals of $[0,1)$. The pigeonhole principle gives $1\le d\le q$ with $\Vert d\theta {\Vert }_{\mathbb{R}/\mathbb{Z}}\le 1/q$. Set $\eta =\beta /(16\pi )$ and $L=\lfloor \eta q\rfloor$, taking $N$ large enough that $\eta q\ge 2$. Every residue-class chain in $[N]$ of step $d$ has length at least $q$. Divide each chain into blocks of length $L$, adjoining a final shorter remainder to its preceding block. This partitions $I$ into arithmetic progressions $P$ with $L\le |P|<2L$.

The linear phase $e^{-2\pi i\theta x}$ varies by at most $4\pi L/q\le \beta /4$ on each cell. Replace it there by its value at one endpoint. Since $|f(x)|\le 1$, the total error in the Fourier correlation is at most $\beta N/4$. Consequently, writing $D(P)={\sum }_{x\in P}f(x)$,But ${\sum }_{P}D(P)=0$, so the positive discrepancies sum to at least $3\beta N/8$. Some cell therefore has $D(P)/|P|\ge 3\beta /8\ge \beta /4$. As $q\ge \sqrt{N}/2$ and $L\ge \eta q/2$, this proves the one-frequency density increment on an integer interval:

Finally, reindex this arithmetic progression as a new integer interval. An affine reindexing preserves three-term arithmetic progressions, so the new subset is again progression-free. Starting with density at least $\delta$, each step raises it by at least ${\delta }^2/144$ and retains an interval of length at least $c\sqrt{N}$, where $c={\delta }^2/(2304\pi )$.

Let $R(\delta )$ be a size threshold large enough for all the preceding estimates. It works at every later density $\alpha \ge \delta$. Choose $J=\lceil 144/{\delta }^2\rceil$ and initial size at least $(R(\delta )/c^2{)}^{2^J}$. After $j\le J$ steps the size is at leastThus all $J$ increments are permitted. They would give density at least $\delta +J{\delta }^2/144>1$, a contradiction. This proves the Roth theorem on three-term arithmetic progressions.