Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 16 (Arithmetic Combinatorics)

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.

Assume $n>0$; the empty case is immediate. Write $r(s)=\#\{(a,b)\in A^2:a-b=s\}$. The additive energy in the hypothesis is ${\sum }_{s}r(s{)}^2$: rearranging $x+y=z+w$ gives $x-z=w-y$. Since $r(s)\le n$, the energy is at most $n^3$, so the substantive range is $0<\alpha \le 1$.

Let $S=\{s:r(s)\ge \alpha n/2\}$. The contribution of the other differences to the energy is at most $(\alpha n/2){\sum }_{s}r(s)=\alpha n^3/2$. ConsequentlyMake a bipartite graph with two copies of $A$, joining a left vertex $a$ to a right vertex $b$ when $a-b\in S$. Put $\rho =\alpha /2$. This graph has at least $\rho n^2$ edges, and $|S|\le n/\rho$.

We prove the needed dense-graph selection rather than quote the Balog-Szemerédi-Gowers theorem. A pair of left vertices is bad if it has fewer than $\tau n$ common right neighbours, where $\tau ={\rho }^2/32$. Choose a right vertex $y$ uniformly, let $U=N(y)$, and let $b(U)$ be the number of ordered bad pairs in $U$. Averaging the degrees gives $\mathbb{E}|U|\ge \rho n$. Every bad pair lies in fewer than $\tau n$ of these neighbourhoods, so $\mathbb{E}b(U)\le \tau n^2$. Therefore some $y$ satisfiesFor this neighbourhood, $|U|\ge \rho n/2$ and $b(U)\le \rho n|U|/16\le |U{|}^2/8$. Delete vertices having more than $|U|/4$ bad partners in $U$. At most half are deleted, so the remaining set $B$ has $|B|\ge |U|/2\ge \rho n/4$.

For any $b,b^{\prime }\in B$, at least $|U|/2$ vertices $v\in U$ are good partners of both. Each such $v$ has at least $\tau n$ common neighbours with $b$ and at least $\tau n$ with $b^{\prime }$. Independently choosing those neighbours gives at leastfour-edge walks $b,u,v,w,b^{\prime }$. Repeated vertices cause no difficulty. This proves the four-step path lemma for a dense bipartite graph in the required form.

The labels of such a walk are $s_1=b-u$, $s_2=v-u$, $s_3=v-w$, $s_4=b^{\prime }-w$, all in $S$, andFor a fixed pair $(b,b^{\prime })$, its label tuple uniquely recovers $u=b-s_1$, $v=u+s_2$, and $w=v-s_3$, so distinct walks have distinct label tuples. Choose one pair representing each element of the difference set $B-B$. Tuples belonging to different differences are disjoint because their alternating sum determines that difference. HenceWe have obtained explicit constants for the small-difference-set form of the Balog-Szemerédi-Gowers theorem:

We first prove the needed Petridis minimal-growth lemma. For finite nonempty sets $A,D$, choose a nonempty $X\subseteq A$ minimizing $K_0=|X+D|/|X|$. Thus $|Y+D|\ge K_0|Y|$ for every $Y\subseteq X$, including the empty set. For any finite $T=\{t_1,\dots ,t_r\}$, defineThe sets $X_i+t_i$ partition $X+T$. If $x\notin X_i$, then $x+t_i\in X+t_j$ for some $j<i$, and therefore $x+D+t_i\subseteq X+D+t_j$. The newly contributed portion of $X+D+t_i$ consequently has size at mostSum over $i$ to obtain $|X+D+T|\le K_0|X+T|$. Apply this successively with $T=(r-1)D$ to get $|X+rD|\le K_0^r|X|$.

Use $D=-A$. The hypothesis implies $K_0\le |A-A|/|A|\le C$, so $|X-2A|\le C^2|X|$. We also prove the Ruzsa triangle inequality: for finite nonempty $U,V,W$,For each $s\in U-W$, fix $u_s,w_s$ with $s=u_s-w_s$. The map $(s,v)\mapsto (u_s-v,v-w_s)$ is injective: summing its coordinates recovers $s$, and then its first coordinate recovers $v$. This proves the inequality.

Apply it with $U=W=2A$ and $V=X$. Both right-hand factors have cardinality $|X-2A|$, givingThus $\boxed{K=C^4\text{ suffices}}$. This is the required case of the Plünnecke-Ruzsa inequality, proved here using the minimal-growth argument and the explicit injection. If $A$ is empty the conclusion holds directly.

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

Take $R=\{r\ne 0:|\hat{f}(r)|\ge {\eta }^{3/2}/\sqrt{2}\}$. The Parseval identity on a finite group givesFor $x$ in the Bohr set in phase-distance convention $\mathcal{B}=\{x:\Vert rx/N{\Vert }_{\mathbb{R}/\mathbb{Z}}\le 1/6\text{ for every }r\in R\}$, all large-frequency terms have real part at least half their magnitude. Since $F$ is real,Thus $\mathcal{B}\subseteq 2A-2A$. This proves the cyclic Bogolyubov lemma needed here, rather than citing it.

We now find an arithmetic progression in a cyclic Bohr set. Put $m=|R|$. If $m=0$, the whole group lies in $2A-2A$ and the result is immediate. Otherwise set $Q=\lfloor N^{1/(m+1)}\rfloor$. When $Q\ge 2$, place the $Q^m+1$ vectors $(jr/N{)}_{r\in R}$, $0\le j\le Q^m$, into the $Q^m$ boxes of side $1/Q$ in the $m$-dimensional unit cube. Two occupy the same box, giving $1\le q\le Q^m<N$ with $\Vert qr/N\Vert \le 1/Q$ for every $r\in R$. The arithmetic progressionlies in $\mathcal{B}$. Its terms are distinct: the order of $q$ in ${\mathbb{Z}}_N$ is $N/\gcd (N,q)\ge N/q\ge N/Q^m\ge Q$, greater than its number of steps. Its length is at least $Q/6\ge N^{1/(m+1)}/12$.

Let $D=\lceil 2{\theta }^{-2}\rceil$. Since $m\le D$, the exponent $1/(m+1)$ is at least $1/(D+1)$. If $Q=1$, then $N^{1/(m+1)}<2$ and the singleton $\{0\}$ already exceeds the required lower bound. This also covers $N=1$. Therefore one may takeThe arithmetic progression here is a set of distinct elements in the cyclic group; this part does not impose the additional integer nonwrapping condition used in Question 3.

The expectations use normalized counting measure on a finite abelian group $G$. This is the finite-group convention implicit in the averaging notation; an arbitrary infinite group has no normalized counting probability measure on all its points. For $h\in G$, define ${\Delta }_{h}f(x)=f(x)\overline{f(x+h)}$, and let $\mathcal{C}$ denote complex conjugation. The Gowers U3 norm isAveraging first over $h_3$ gives the Derivative identity for the Gowers U3 normIndeed, if $u(x)={\Delta }_{h_1}{\Delta }_{h_2}f(x)$, the average over $(x,h_3)$ is ${\mathbb{E}}_{x,h_3}u(x)\overline{u(x+h_3)}=|{\mathbb{E}}_{x}u(x){|}^2$. The eighth root is consequently well-defined. Homogeneity follows because the cube has four unconjugated and four conjugated factors, so $\Vert af{\Vert }_{U^3}=|a|\Vert f{\Vert }_{U^3}$. If the norm is zero, every squared term in the finite average vanishes. Taking $h_1=h_2=0$ gives ${\mathbb{E}}_x|f(x){|}^4=0$, so $f=0$ pointwise. This proves positive definiteness.

For the triangle inequality, we prove the needed Gowers-Cauchy-Schwarz inequality. For eight functions $F_{\omega }$ on a product of finite sets $X_1\times X_2\times X_3$, form the box norm multilinear averageFix a coordinate $j$. After averaging its two variables separately, this is $\mathbb{E}A\overline{B}$, where $A$ uses all vertices with ${\omega }_j=0$ and $B$ those with ${\omega }_j=1$, with the remaining parity conjugations. The Cauchy-Schwarz inequality giveswhere $S_j^b$ replaces the function at each vertex by the original function with its $j$th index set to $b$. Each right-hand average is a squared absolute value averaged over the other coordinates, hence nonnegative. Apply this operation successively for $j=1,2,3$, to every resulting factor. The eight final families each use one original $F_{\omega }$ at all vertices. Taking roots gives the box Cauchy-Schwarz inequalityNow take $X_j=G$ and $F_{\omega }(a,b,c)=f_{\omega }(a+b+c)$. With $x=a_0+b_0+c_0$ and $h_j=x_j^1-x_j^0$, these independent variables induce uniform $(x,h_1,h_2,h_3)$: each such tuple has exactly $|G{|}^2$ preimages. Therefore each box norm is the corresponding $U^3$ norm, and the mixed cube obeysExpand the eight factors in the cube expression for $f+g$. Its $2^8$ mixed terms are bounded by this inequality, and their bounds sum to $(\Vert f{\Vert }_{U^3}+\Vert g{\Vert }_{U^3}{)}^8$. Thus $\boxed{\Vert f+g{\Vert }_{U^3}\le \Vert f{\Vert }_{U^3}+\Vert g{\Vert }_{U^3}}$, completing the norm proof.

Two consequences will be useful below. Multiplication by a character of a finite abelian group leaves the norm unchanged, because the alternating character product around a three-dimensional cube equals one. Alsowhere the last inequality uses the $h=0$ term and $\Vert u{\Vert }_{U^2}^4={\sum }_{\chi }|\hat{u}(\chi ){|}^4\ge |\mathbb{E}u{|}^4$. Hence $\Vert f{\Vert }_{U^3}\ge |G{|}^{-1/8}\Vert f{\Vert }_2$.

Index the functions as $g_0,g_1,g_2,g_3$ and write $\Lambda ={\mathbb{E}}_{x,d}{\prod }_{j=0}^3{g}_j(x+jd)$. We first control $g_0$. Change variables to $y=x+3d$, average over $d$, and apply Cauchy-Schwarz in $y$, discarding the bounded factor $g_3(y)$. Expand the squared inner average with the second copy of $d$ written $d+h$, then put $x=y-3d$. This yieldsThe right side is real and nonnegative because it arose as an average of squared absolute values. Next use $y=x+2d$ and apply Cauchy-Schwarz in $(h,y)$, discarding the bounded $g_2$ derivative. Expanding with a displacement $k$ in $d$ givesFinally use $y=x+d$ and Cauchy-Schwarz in $(h,k,y)$, discarding the bounded $g_1$ double derivative. Expansion with displacement $r$ givesAll these changes of variables are bijections without any division in $G$.

Put $t_j=|G[j]|$, where $G[j]=\{z:jz=0\}$ is the torsion subgroup killed by an integer $j$. The variables $2k$ and $3h$ are uniform on $2G$ and $3G$, whose indices are $t_2,t_3$. Since the last squared integrand is nonnegative, its restricted average is at most $t_2{t}_3$ times the unrestricted average over the two increments. By part (i), that unrestricted average is $\Vert g_0{\Vert }_{U^3}^8$. Hence $|\Lambda |\le (t_2{t}_3{)}^{1/8}\Vert g_0{\Vert }_{U^3}$.

To control $g_1$, apply the same three eliminations in the order of slopes $3,0,2$. The surviving $g_1$ has increments $-2h,k,-r$. The last increment is uniform, and only the first is restricted to $2G$, so the resulting bound is $|\Lambda |\le t_2^{1/8}\Vert g_1{\Vert }_{U^3}$. Reversing the arithmetic progression by $(x,d)\mapsto (x+3d,-d)$ treats $g_3$ and $g_2$ respectively. This proves the four-term progression bound with torsion factors:For a fixed finite group, this positive constant tends to zero with $\alpha$. In ${\mathbb{Z}}_N$, $t_j=\gcd (j,N)$, so $\boxed{\beta =6^{1/8}\alpha \text{ suffices uniformly in }N}$. If multiplication by two and three are bijective, the sharper $\beta =\alpha$ holds.

A dependence on torsion is necessary if a bound uniform over all finite abelian groups is intended. In $G={\mathbb{F}}_2^m$, choose independent random signs $f(x)$. A cube with eight distinct vertices has sign product of expectation zero. Each of the twenty-eight possible collisions has probability $1/|G|$, so the expectation of $\Vert f{\Vert }_{U^3}^8$ is at most $28/|G|$. Some sign function therefore has norm at most $(28/|G|{)}^{1/8}$. But with factors $(f,1,f,1)$, every arithmetic progression is $(x,x+d,x,x+d)$ and its product is $f(x{)}^2=1$. Thus unbounded torsion obstructs uniform control of four-term progressions. The stated fixed-group bound, and the uniform cyclic-group bound needed in part (iii), are unaffected.

Let $\eta =|A|/N$ and $g=1_A-\eta$. In the norm convention, the quadratic uniformity of a set meansIf uniformity is parametrized instead by $\Vert g{\Vert }_{U^3}^8\le \alpha$, replace the parameter below by ${\alpha }^{1/8}$. We prove the genuine-progression conclusion by placing nonnegative weights on a region where wrapping and repeated entries are impossible.

First suppose $N\ge 16$. Put $M=\lfloor N/16\rfloor$, $J=\{0,\dots ,M-1\}$, $t=M/N$, and let $w=1_J\ast 1_J$ be the normalized convolution on a finite group. Define the weighted countBoth weights are nonnegative. Their supports require $0\le x\le 2M-2$ and $M\le d\le 3M-2$ in the ordinary representatives. In particular $d\ge 1$ and $x+3d\le 11M-8<N$. Every contributing arithmetic progression is therefore a set of four distinct integers in $\{0,\dots ,N-1\}$, with no modular wrap.

The averages of both weights are $t^2$. The convolution theorem on a finite group and the Parseval identity on a finite group giveTranslation multiplies coefficients by phases, so $w(d-M)$ has the same Fourier coefficient sum. Telescoping the product of the four indicators around ${\eta }^4$ produces four error terms, each with one factor $g$ and all other factors bounded by one.

To bound a weighted error, expand both weights in their finite Fourier series. For frequencies $r,s$, the extra character is $e^{2\pi i(rx+sd)/N}$. Write it asand absorb these two characters into the functions at slopes zero and one. Even if the balanced factor is one of those functions, its $U^3$ norm remains at most $\alpha$ by the character invariance proved in part (i). The cyclic bound of part (ii), with $C_0=6^{1/8}$, therefore bounds each unweighted Fourier term by $C_0\alpha$. Summing absolute coefficients costs at most $t^2$. ConsequentlySince $t\ge 1/32$ and $\eta \ge \delta$, this is positive whenever $\alpha <{\delta }^4/(4096C_0)$. A positive count supplies the required genuine arithmetic progression. This is the argument that triangular weights count genuine four-term progressions; it avoids losing powers of $\log N$ by cutting off a sharp interval.

For completeness, treat $4\le N<16$. If $A$ is a proper nonempty subset, then $\eta (1-\eta )\ge \delta /N$. The norm bound from part (i) givesChoose $\alpha$ below this bound as well. Then quadratic uniformity forces $A={\mathbb{Z}}_N$, which contains $\{0,1,2,3\}$. Thus, for every $N\ge 4$, a sufficient threshold isThe restriction $N\ge 4$ is necessary: for $N=1,2,3$, the full group has balanced subset indicator zero and is quadratically uniform for every positive parameter, but no subset has four elements. The printed conclusion needs this elementary size qualification.