Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 11 (Additive Combinatorics)

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.

For disjoint nonempty vertex sets $U,W$, define their edge density of a bipartite graph by $d(U,W)=e(U,W)/(|U||W|)$. They form an $\epsilon$-regular pair of vertex sets if every $X\subseteq U$, $Y\subseteq W$ with $|X|\ge \epsilon |U|$, $|Y|\ge \epsilon |W|$ satisfies $|d(X,Y)-d(U,W)|\le \epsilon$.

The Szemerédi regularity lemma asserts that, given $\epsilon >0$ and a positive integer $m_0$, there are $M,n_0$ such that every graph on $n\ge n_0$ vertices has a set partition $V_0,V_1,\dots ,V_k$ withand at most $\epsilon k^2$ irregular ordered pairs $(V_i,V_j)$ with $1\le i\ne j\le k$.

Assume $0<\epsilon \le 1/2$, which suffices since a smaller regularity parameter gives the claim for a larger one. Treat the exceptional vertices as singleton cells in the full partition $\mathcal{P}$, and use equitable regularity energyHere the adjacency indicator function defines density even for diagonal cells. Clearly $0\le q\le 1$. If ${\mathcal{P}}^{\prime }$ refines $\mathcal{P}$, weighted averaging of densities gives the refinement variance identity for regularity energyTo verify it, expand each square and use ${\sum }_{A^{\prime },B^{\prime }}|A^{\prime }||B^{\prime }|d(A^{\prime },B^{\prime })=|A||B|d(A,B)$.

For every irregular ordered pair of nonexceptional cells, choose witnesses $X_{ij},Y_{ij}$ of relative sizes at least $\epsilon$ and density discrepancy greater than $\epsilon$. Split each $V_i$ along all witnesses involving it; symmetry allows at most one witness for each other cell, hence at most $2^k$ atoms in each $V_i$. In the witness rectangle, the weighted Cauchy-Schwarz inequality in the variance identity contributes more than ${\epsilon }^4|V_i||V_j|/n^2$.

If more than $\epsilon k^2$ pairs are irregular and the equal cell size is $L$, the energy increase is greater thanRestore equal cell sizes by cutting each witness atom into pieces of size $\ell =\lfloor L/4^k\rfloor$, with leftover vertices added to $V_0$ as singleton cells. This operation is a further refinement, so the energy does not decrease. There are at most $k{2}^k$ atoms, and fewer than $\ell$ leftover vertices in each, giving at most $k{2}^k\ell \le n{2}^{-k}$ new exceptional vertices.

Here is a uniform bound ensuring that the iteration is legitimate. Put $R=\lceil 4{\epsilon }^{-5}\rceil$ and chooseStart with $k_0$ equal classes and fewer than $k_0$ exceptional vertices. Taking $n\ge 2k_0/\epsilon$ makes the initial exception at most $\epsilon n/2$. At every refinement the number of nonexceptional cells does not decrease: each old cell loses at most $L{2}^{-k}\le L/2$ vertices and is cut into pieces of size at most $L/4^k$. Thus each of the at most $R$ rounds adds at most $\epsilon n/(2R)$ exceptional vertices.

When $L\ge 2\cdot 4^k$, the new cell count is at mostusing $|V_0|\le \epsilon n\le n/2$. Define $K_0=k_0$ and $K_{j+1}=4K_j{4}^{K_j}$, and take $M=K_R$. Choosing $n_0\ge \max \{2k_0/\epsilon ,4M{4}^M\}$ ensures $L\ge n/(2M)\ge 2\cdot 4^M$ at every stage. All rounds are therefore defined, with cell count between $m_0$ and $M$ and exceptional size at most $\epsilon n$.

If the lemma still failed after $R$ refinements, the energy would have increased by more than $R{\epsilon }^5/4\ge 1$, impossible because it lies in $[0,1]$. Hence some stage has the required regular pairs. This completes the energy-increment proof of Szemerédi regularity, including the equal-size and exceptional-set conditions.

For this Cartesian product, the requested $U^2$ norm is the box norm, with complex conjugates:Equivalently it is ${\mathbb{E}}_{y,y^{\prime }}|K(y,y^{\prime }){|}^2$, where $K(y,y^{\prime })={\mathbb{E}}_{x}f(x,y)\overline{f(x,y^{\prime })}$. This makes its nonnegativity explicit.

Apply the Cauchy-Schwarz inequality first in $x$:The right-hand expectation is nonnegative, since it came from ${\mathbb{E}}_x|{\mathbb{E}}_{y}f(x,y)v(y){|}^2$. A second application in $(y,y^{\prime })$ givesTaking fourth roots proves the bilinear correlation bound for the box norm

The printed statement needs $A\ne \varnothing$: for the empty set every linear subspace has cardinality at least one, so the requested bound is impossible. We prove the intended nonempty version of the Freiman-Ruzsa theorem over a finite field. Necessarily $C\ge 1$, because any one translate of $A$ inside $A+A$ has size $|A|$.

We first prove all sumset estimates needed below. For finite nonempty $X$ and finite $U,V$ in an abelian group, choose one representation $z=u_z-v_z$ for each $z\in U-V$. The mapis injective: subtracting the outputs recovers $z$, hence its chosen representation and then $x$. This proves the Ruzsa triangle inequality

Choose nonempty $X\subseteq B$ minimizing $c^{\prime }=|X+B|/|X|\le C$, where $B$ is any set with $|B+B|\le C|B|$. We prove the Petridis minimal-growth lemma $|X+B+D|\le c^{\prime }|X+D|$ for every finite $D$. List $D=\{d_1,\dots ,d_s\}$, and let $X_i$ consist of those $x\in X$ for which $x+d_i$ was not already in $X+\{d_1,\dots ,d_{i-1}\}$. The disjoint pieces $X_i+d_i$ partition $X+D$.

Every $(X\setminus X_i)+B+d_i$ was already covered in $X+B+\{d_1,\dots ,d_{i-1}\}$. The new part at step $i$ therefore has size at mostHere minimality of $X$ applies to every nonempty subset $X\setminus X_i$, and the empty case has size zero. Summing proves the lemma. Iteration gives $|X+kB|\le C^k|X|$. Apply the Ruzsa triangle inequality with $U=kB$, $V=\ell B$ to obtainThis derives the required Plünnecke-Ruzsa inequality. In characteristic two, subtraction is addition, so $|rB|\le C^r|B|$ for every positive integer $r$.

Fix $a\in A$ and translate to $B=A+a$, which contains zero, has size $|A|$, and has the same doubling constant. Choose $m=\lceil {\log }_2(2|12B|)\rceil$. A uniformly random linear map $L:{\mathbb{F}}_2^N\to G^{\prime }={\mathbb{F}}_2^m$ kills each specified nonzero vector with probability $2^{-m}$. The union bound shows that some $L$ satisfiesBecause $0\in B$, all lower iterated sumsets lie in $12B$. In particular $L$ is injective on $B$, since the difference of two elements belongs to $2B$. For $B^{\prime }=L(B)$, the density $\alpha =|B^{\prime }|/|G^{\prime }|$ is at least $1/(4C^{12})$. This proves injective linear modelling of a small sumset.

We next prove the Finite-field Bogolyubov lemma in this model. Write $f=1_{B^{\prime }}$ and use normalized real Fourier coefficients on a finite abelian group $\hat{f}(\xi )={\mathbb{E}}_{x}f(x)(-1{)}^{\xi \cdot x}$. LetBy Parseval identity, $|S|\le 2{\alpha }^{-2}$. Thus $W$ is a vector subspace of codimension at most $D=\lceil 32C^{24}\rceil$.

For $w\in W$, Fourier inversion of the fourfold normalized convolution givesAll terms with $\xi \in S$ are nonnegative, and the zero-frequency term is ${\alpha }^4$. The absolute contribution from the remaining frequencies is at mostHence the convolution is positive and $W\subseteq 4B^{\prime }$. Also $|W|\ge 2^{-D}|G^{\prime }|\ge 2^{-D}|B|$.

For each $w\in W$, choose its lift $\sigma (w)\in 4B$. It is unique because two lifts differ by an element of $8B\cap \ker L$, which is zero. For $w_1,w_2\in W$, the discrepancybelongs to $12B\cap \ker L$, so it vanishes. Also $\sigma (0)=0$. Therefore $\sigma$ is a linear map and its image $\tilde{W}\subseteq 4B$ is a vector subspace with $|\tilde{W}|=|W|\ge 2^{-D}|B|$. This establishes lifting a subspace through a Freiman model without assuming that arbitrary choices of preimages preserve addition.

Finally, $B+\tilde{W}\subseteq 5B$ is a union of $\tilde{W}$-cosets. The number of these cosets is at mostChoose representatives $b_1,\dots ,b_t$ from $B$. Then $B\subseteq \tilde{W}+\{b_1,\dots ,b_t\}$, so adjoining these representatives and $a$ to $\tilde{W}$ gives a vector subspace $V$ containing $A$. Over ${\mathbb{F}}_2$, adjoining each vector multiplies the size by at most two. Since $|\tilde{W}|\le |4B|\le C^4|B|$, the Freiman-Ruzsa bound from Bogolyubov and linear modelling yieldsThis bound depends only on $C$, as required, and every sumset estimate used in its derivation has been proved.