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

For a finite nonempty set $A$, its additive energy iswhere $r_{A+A}(s)$ counts ordered representations. Since ${\sum }_s{r}_{A+A}(s)=|A{|}^2$, Cauchy-Schwarz givesThus $|A+A|\le K|A|$ implies $E(A,A)\ge |A{|}^3/K$: a small doubling constant forces many additive quadruples.

A polynomial form of the Balog-Szemerédi-Gowers theorem gives the converse after passing to a subset. There are absolute constants $c,C>0$ such that if $E(A,A)\ge \eta |A{|}^3$, $0<\eta \le 1$, then some $A^{\prime }\subseteq A$ satisfiesThe exponent and constants here need not be optimal.

Precisely, a graph form of the Balog-Szemerédi-Gowers theorem states the following. If $A,B$ are finite sets of size $n$ in an abelian group, $\Gamma \subseteq A\times B$ has at least $\delta n^2$ edges, and its restricted sumsethas size at most $Kn$, then there are $A^{\prime }\subseteq A$, $B^{\prime }\subseteq B$ with $|A^{\prime }|,|B^{\prime }|\ge c{\delta }^{C}n$ andThese are uniform absolute constants, valid for $0<\delta \le 1$ and $K\ge 1$.

To apply this theorem to additive energy, let $n=|A|$ and retain the sums with $r_{A+A}(s)\ge \eta n/2$. The discarded sums contribute at most $(\eta n/2){\sum }_{s}r(s)=\eta n^3/2$ to the additive energy. Since $r(s)\le n$, the retained pairs number at least $\eta n^2/2$. There are at most $2n/\eta$ retained sums. They therefore define a bipartite graph of density at least $\eta /2$ with restricted sumset size at most $2n/\eta$. The graph theorem supplies large subsets $A^{\prime },B^{\prime }$ with polynomially bounded $|A^{\prime }+B^{\prime }|$.

For completeness, turn this cross-sumset bound into a doubling constant bound. The Ruzsa triangle inequality gives $|A^{\prime }-A^{\prime }|\le |A^{\prime }+B^{\prime }{|}^2/|B^{\prime }|$. If $D=|A^{\prime }-A^{\prime }|/|A^{\prime }|$, the Plünnecke inequality, applied to the pair $A^{\prime },-A^{\prime }$, gives $|A^{\prime }+A^{\prime }|\le D^2|A^{\prime }|$. The minimal-growth proof below in Question 5 applies to arbitrary finite pairs and proves this particular expansion estimate as well. All losses are fixed powers of ${\eta }^{-1}$, proving the displayed converse after increasing $C$.

The requested dense bipartite common-neighbour lemma is a dependent random choice assertion. Call an ordered pair in $V^2$ bad when it has fewer than $ϵn$ common neighbours. Choose $w\in W$ uniformly, and put $S=N(w)\subseteq V$. ThenFor each bad pair, the probability that both endpoints lie in $S$ is its number of common neighbours divided by $n$, which is less than $ϵ$. Thus the expected number $b(S)$ of bad ordered pairs in $S^2$ is at most $ϵm^2$. ConsequentlyChoose a neighbourhood $V^{\prime }=S$ attaining at least this expectation. It has $|V^{\prime }|\ge \delta m/\sqrt{2}\ge \delta m/2$, andHence at least the proportion $1-2ϵ/{\delta }^2$ of its ordered pairs have at least $ϵn$ two-edge connections. As usual these connections are counted by common neighbours, including a return walk for a diagonal ordered pair; assume $\delta >0$, as the formula requires.

The relevance to the graph theorem is that many two-edge connections turn a sparse collection of permitted sums into additive control on a large vertex subset. On a connection $a\to b\to a^{\prime }$, $a-a^{\prime }=(a+b)-(a^{\prime }+b)$ expresses a difference using two elements of the restricted sumset. The abundance of connections, followed by standard cleaning and further path counting, bounds the number of differences without throwing away most vertices. This is the role of dependent random choice in obtaining polynomial losses in the graph form of the Balog-Szemerédi-Gowers theorem.

Write $e(t)=\exp (2\pi it)$. A sequence in the circle group is an equidistributed sequence if, for every interval $I\subseteq \mathbb{R}/\mathbb{Z}$,where $|I|$ is its normalized length. Equivalently, averages of every continuous function along the sequence tend to its circle integral. Trigonometric polynomials approximate continuous functions, and interval indicators can be squeezed between continuous functions with arbitrarily close integrals. The nonconstant additive characters have integral zero. These facts give the Weyl criterion:This is the link between equidistribution and cancellation in exponential sums.

Suppose every positive-shift difference sequence were equidistributed. Fix $m\ne 0$ and set $z_n=e(m\varphi (n))$. For every fixed $h\ge 1$, the Weyl criterion would giveThe omitted final $h$ terms change a normalized average by at most $h/N$.

Here is the needed Van der Corput inequality for finite scalar sequences. Extend $z_n$ by zero outside $[1,N]$ and average $H$ consecutive translates of the sum. Cauchy-Schwarz givesIndeed, apply Cauchy-Schwarz to $H{\sum }_n{z}_n={\sum }_t{\sum }_{j=0}^{H-1}{z}_{t-j}$ and expand the squared inner sum. Taking $N\to \infty$ first leaves a bound $1/H$; then let $H\to \infty$. Every nonzero Fourier average of $\varphi$ vanishes, so the Weyl criterion makes $\varphi$ equidistributed. This is the differencing obstruction to equidistribution. By contraposition, a non-equidistributed sequence has a non-equidistributed difference for some positive $h$, hence for some $h\ne 0$ as requested.

For $\varphi (n)=\sqrt{2}{n}^2$, the difference is ${\Delta }_h\varphi (n)=-2h\sqrt{2}n-h^2\sqrt{2}$. For any nonzero integer $m$, its exponential sum is a constant phase times a geometric progression with ratio $e(-2mh\sqrt{2})\ne 1$. Its normalized magnitude is at most $2/(N|1-e(-2mh\sqrt{2})|)$, which tends to zero. Thus every positive-shift difference is equidistributed, and the contraposition just established proves

We use the normalized Gowers U3 norm on an interval, for which a quadratic phase has norm one. Let ${\mathcal{C}}_N$ consist of integer tuples $(x,h_1,h_2,h_3)$ whose eight vertices $x+{\omega }_1{h}_1+{\omega }_2{h}_2+{\omega }_3{h}_3$, $\omega \in \{0,1{\}}^3$, all lie in $[1,N]$. If $\mathcal{C}$ denotes complex conjugation, defineEquivalently, choose a prime $8N<M<16N$, extend $f$ by zero to $G=\mathbb{Z}/M\mathbb{Z}$, call that extension $F$, and put $I=1_{[1,N]}$. ThenThe large ambient modulus prevents wraparound in cubes supported on the interval, so the ratio is independent of the chosen such $M$. This also proves nonnegativity and the norm properties by the Gowers uniformity norm on $G$. Some conventions omit the denominator; their interval norm differs by a fixed bounded factor, and the quadratic-phase norm is then $\Vert I{\Vert }_{U^3(G)}$.

For $f_0(x)=e(\alpha x^2)$, the exponent in every conjugated cube product is a third additive difference of a quadratic polynomial and is zero. Thus $\Vert f_0{\Vert }_{U^3(N)}=1$ in the normalized interval convention.

The generalized von Neumann inequality for four-term progressions connects this norm to counting arithmetic progressions. For functions bounded by one on a cyclic group of prime order greater than three,Three applications of Cauchy-Schwarz prove the bound. Zero extension and division by the number of interval progressions give the analogous interval estimate up to an absolute constant. In particular, if $g=1_A-\alpha 1_{[1,N]}$, where $\alpha =|A|/N$, has small Gowers U3 norm on an interval, expansion of the progression count shows that it differs from ${\alpha }^4$ times the count for $[1,N]$ by $O(\Vert g{\Vert }_{U^3(N)}{N}^2)$. A large Gowers U3 norm detects structure capable of changing four-term progression counts; quadratic phases are the basic example.

For the remaining proof use the ambient $G$ just specified, define ${\partial }_{h}F(x)=F(x+h)\overline{F(x)}$, and take averages uniformly on $G$. For frequencies not on the character grid, an exponential is evaluated at the chosen integer representatives; the general proof below selects actual characters $\theta =k/M$. The printed question does not define $G$ or the interval normalization, so these conventions make the assertion precise. If instead ${\partial }_{h}f(x)=f(x)\overline{f(x+h)}$ is used, conjugate the correlations and reverse every frequency sign; the quadratic example then has $\theta (h)=-2\alpha h$.

The Gowers U3 norm derivative identity isLet $\kappa =\Vert F{\Vert }_{U^3(G)}^8$. Since $\Vert I{\Vert }_{U^3(G)}\ge \mathbb{E}I=N/M\ge 1/16$, by repeated Cauchy-Schwarz, the interval hypothesis gives $\kappa \ge 16^{-8}{\delta }^8$. Also $\Vert {\partial }_{h}F{\Vert }_{U^2}^4\le 1$. Therefore the sethas density at least $\kappa /2$ in $G$.

Use normalized Fourier coefficients on a finite abelian group $\hat{g}(k)={\mathbb{E}}_{x}g(x)e(-kx/M)$. The Gowers U2 norm and Parseval identity giveFor $g={\partial }_{h}F$, the final mean is at most one. Thus each $h\in H$ has a frequency $\theta (h)=k_h/M$ withThe derivative is identically zero unless $h$ is represented by an integer in $[-N+1,N-1]$, so $H$ lies in the requested interval of shifts. Its size is $\gg {\delta }^{8}M\gg {\delta }^{8}N$. Keep one such frequency for each shift; these same choices will satisfy the energy conclusion below.

Write $\beta =|H|/M\gg {\delta }^8$ and $\eta =(\kappa /2{)}^{1/2}\gg {\delta }^4$. Choose unit complex numbers $b_h$ so thatis real and nonnegative. Cauchy-Schwarz, using $|F|\le 1$, bounds $T^2$ byAfter setting $y=x+k$, each summand is a unit phase times the Fourier coefficient on a finite abelian group of ${\partial }_{h-k}F$ at frequency $\theta (h)-\theta (k)$.

Let $r(d,\xi )$ count pairs $(h,k)\in H^2$ with $h-k=d$ and $\theta (h)-\theta (k)=\xi$. Grouping terms, another Cauchy-Schwarz and the Parseval identity yieldwhere $E_{\theta }(H)=\sum r(d,\xi {)}^2$ is the additive energy of a frequency graph. The last inequality uses ${\sum }_{\xi }|\widehat{{\partial }_{d}F}(\xi ){|}^2=\mathbb{E}|{\partial }_{d}F{|}^2\le 1$ for each $d$.

ThusThe bound proves that derivative correlations force additive frequency energy. This energy counts exactly the ordered quadruples satisfying the two requested additive relations, after relabelling the difference equality as a sum equality. Shift equalities initially hold modulo $M$, but the shifts lie in $[-N,N]$ and $M>8N$, so they are also integer equalities. Frequency equalities hold in $\mathbb{R}/\mathbb{Z}$, as required. Consequently a common exponent $C=48$ works for both conclusions, after adjusting absolute implicit constants and using $0<\delta \le 1$.

For the quadratic phase, the multiplicative derivative on the overlap is ${\partial }_h{f}_0(x)=e(2\alpha hx+\alpha h^2)$. Hence an explicit choice isTake $|h|\le \lfloor N/2\rfloor$. The correlation magnitude is $(N-|h|)/M\ge 1/32$, and every additive quadruple of shifts satisfies the frequency relation. The interval of shifts has $\gg N^3$ such quadruples by Cauchy-Schwarz. These particular real frequencies need not belong to the grid used to prove existence for general $f$; evaluating them at the interval's integer coordinates gives the stated exact formula.

A genuinely nonlinear example is the bracket-linear frequency functionIt has $\gg N^3$ exact additive quadruples, yet agrees with any affine function $ah+b(\mathrm{mod}1)$ at only $o(N)$ shifts, uniformly in the affine function. The question permits giving this example without proof, but the mechanism is useful. For a pair with sum $s$, the value $\lfloor \sqrt{2}{h}_1\rfloor +\lfloor \sqrt{2}{h}_2\rfloor$ has only two possibilities, $\lfloor \sqrt{2}s\rfloor$ or $\lfloor \sqrt{2}s\rfloor -1$. There are $O(N)$ pair classes, so Cauchy-Schwarz produces $\gg N^3$ collisions with both additive relations.

To see why no long affine agreement occurs, three agreement points force the corresponding lattice points $(h,\lfloor \sqrt{2}h\rfloor )$ to be collinear: eliminating the affine slope gives $\sqrt{3}$ times an integer determinant equal to an integer, and irrationality makes that determinant zero. A rational line of slope $p/q$ contains agreement shifts in one residue class modulo $q$, and closeness of $\lfloor \sqrt{2}h\rfloor$ to $\sqrt{2}h$ bounds their span by $1/|\sqrt{2}-p/q|$. Lines with $q$ large have arbitrarily small possible density; for bounded $q$, irrationality of $\sqrt{2}$ bounds the number uniformly. Thus the maximum agreement is $o(N)$.

Use the phase-distance convention for a Bohr set:where the norm is distance to the nearest integer. This is the Bohr set in phase-distance convention; the alternative condition $|e(rx/N)-1|\le \rho$ has a different radius and corresponding constants. Assume $d\ge 1$, as $1/d$ requires.

For each residue $x$, form $t_x=(rx/N{)}_{r\in R}$ in the $d$-dimensional torus. Around these $N$ points place translates of a box of side length $ϵ$ in each coordinate. For $0<ϵ\le 1$, their volumes sum to $N{ϵ}^d$. If $ϵ>N^{-1/d}$, two boxes overlap, and their distinct indices differ by a nonzero $q$ with every phase distance less than $ϵ$. Thus the Bohr set contains a nonzero element at the stated threshold. For larger radii the entire group is already present.

Letting the box width decrease to $N^{-1/d}$ and using the finite number of possible nonzero $q$, obtain a nonzero $q$ with $\Vert rq/N\Vert \le N^{-1/d}$ for every $r\in R$. By the triangle inequality, $jq$ lies in $B(R,ϵ)$ whenever $0\le j<ϵN^{1/d}$. Since $N$ is prime, these multiples are distinct up to length $N$. Therefore, in the usual radius range $0<ϵ\le 1/2$, the arithmetic progressionhas the requested length. For literally unrestricted $ϵ>0$, the correct lower bound is $\min (N,\lceil ϵN^{1/d}\rceil )$: a progression of distinct residues cannot exceed $N$. For example, $d=1$, $ϵ=2$ makes the uncapped printed bound impossible. If $R$ is empty, the Bohr set is the whole group and has a progression of length $N$; the displayed exponent is simply inapplicable.

Now transfer the dense integer set to a larger cyclic group. Choose a prime $8N<p<16N$, using Bertrand's postulate, and regard $A$ as a subset of $G=\mathbb{Z}/p\mathbb{Z}$. Its density $\alpha =|A|/p$ is at least $1/1600$. Normalize Fourier coefficients on a finite abelian group and convolution byThe Fourier inversion and Parseval identity formulas are $f(x)={\sum }_r\hat{f}(r)e(rx/p)$ and ${\sum }_r|\hat{f}(r){|}^2=\mathbb{E}|f{|}^2$; convolution turns into multiplication of Fourier coefficients on a finite abelian group.

For $f=1_A$, set $R=\{r:|\hat{f}(r)|\ge {\alpha }^{3/2}/2\}$. Then Parseval identity boundsAlso, with $\tilde{f}(x)=f(-x)$, the nonnegative convolution $Q=f\ast f\ast \tilde{f}\ast \tilde{f}$ is supported exactly on the modular set $2A-2A$, andThe frequencies outside $R$ contribute in absolute value at most $({\alpha }^3/4){\sum }_r|\hat{f}(r){|}^2={\alpha }^4/4$. For $x\in B(R,1/6)$, the real part of each phase from $R$ is at least $1/2$; moreover $0\in R$ and $|\hat{f}(0){|}^4={\alpha }^4$. Hence $Q(x)\ge {\alpha }^4/4>0$. We have proved the cyclic Bogolyubov lemma with explicit phase radius:The previous Bohr set argument gives a modular arithmetic progression of length at least $p^{1/D}/6$. The remaining step is lifting a short modular progression to an integer progression. Every one of its elements has a unique integer lift belonging to $2A-2A\subseteq [-2N,2N]$. Successive lifted differences lie in $[-4N,4N]$ and are congruent to the same residue. Since $p>8N$, at most one integer in this difference interval represents that residue, so every successive difference is the same. The lifts form a genuine integer arithmetic progression, not merely a modular one.

For sufficiently large $N$, the constants can be absorbed into half the exponent. ThusNo attempt to optimize this absolute constant is needed.

A counterexample comes from dense integer sets with only logarithmic-length progressions. To show that $A$ itself need not have such a progression, choose a random subset $B\subseteq [1,N]$ by independent inclusion with probability $p_0=0.02$. Its size has mean $0.02N$ and variance at most $0.02N$, so Chebyshev's inequality shows $\mathbb{P}(|B|<0.01N)\le 200/N$. There are at most $N^2$ increasing arithmetic progressions of any fixed length $L\ge 2$, and each belongs to $B$ with probability $p_0^L$. Taking $L=\lceil 4\log N/\log (1/p_0)\rceil$ makes the union bound at most $N^{-2}$. For large $N$, some realization has at least $0.01N$ elements and no length-$L$ arithmetic progression. Take a subset of exactly $0.01N$ elements. It retains that avoidance. Such a set has no progression longer than $O(\log N)$, and therefore no progression of length $N^c$ for any fixed $c>0$, eventually. Interpret the prescribed exact cardinality on values of $N$ where it is integral, or use its integer part.

We first prove the needed Petridis minimal-growth lemma, including the expansion estimate rather than assuming it. For finite nonempty sets $A,B$, choose a nonempty $X\subseteq A$ minimizing $r=|X+B|/|X|$. For any finite set $C=\{c_1,\dots ,c_s\}$, defineThen $|X+C|={\sum }_i|X_i|$. An element from $(X\setminus X_i)+B+c_i$ has already appeared in an earlier $X+B+c_j$, so the new contribution of $X+B+c_i$ has size at mostThe inequality follows from minimality of $r$ on subsets of $A$, with an empty subset contributing zero. Summing proves $|X+B+C|\le r|X+C|$. Iteration gives $|X+jB|\le r^j|X|$, for every $j\ge 0$; in particular, $|jB|\le r^j|X|$ by translating $jB$ into $X+jB$.

Apply this with $B=A$, so $r\le K$. It follows thatThis is the required Plünnecke inequality.

We will also use the mixed-sumset bound $|mA-nA|\le K^{m+n}N$. To justify it, the Ruzsa triangle inequality saysChoose one representation $z=p_z-q_z$ for each $z\in P-Q$. The map $(z,t)\mapsto (p_z-t,t-q_z)$ is injective: adding the two coordinates recovers $z$, then the chosen representation recovers $t$. This proves the inequality. Apply it with $P=mA$, $Q=nA$, $T=-X$ and the minimal-growth set already chosen. The bounds on $X+mA$ and $X+nA$ give the mixed-sumset estimate, including $0A=\{0\}$.

The Ruzsa covering lemma states: if $S,T$ are finite, $T\ne \varnothing$, and $|S+T|\le L|T|$, then there is $D\subseteq S$, $|D|\le L$, such that $S\subseteq D+T-T$. Choose $D$ maximal with the translates $d+T$, $d\in D$, pairwise disjoint. They lie in $S+T$, so $|D||T|\le |S+T|$. Maximality says each $s+T$ meets some $d+T$, which writes $s=d+t_1-t_2$. This proves both assertions.

Let $T=A-A$. The mixed-sumset bounds give $|T|\le K^{2}N$ and $|2T+A|=|3A-2A|\le K^{5}N$. Apply the Ruzsa covering lemma to $S=2T$ and the set $A$. There is $D\subseteq 2T$ of size $q\le K^5$ withInduction then gives $\ell T\subseteq (\ell -1)D+T$. The number of possible sums of $\ell -1$ elements from the $q$-element set $D$ is at most the number of multiplicity vectors, namely $\left(\genfrac{}{}{0ex}{}{\ell +q-2}{q-1}\right)$. Since $A-a_0\subseteq T$ for any $a_0\in A$, we obtain the explicit polynomial growth of iterated sumsetsFor fixed $K>1$, this polynomial in $\ell$ is eventually smaller than $K^{ϵ\ell }$. For example, take $q_{\ast }=\lceil K^5\rceil$ and choose ${\ell }_0(K,ϵ)$ so that $2\log K+q_{\ast }\log (\ell +q_{\ast })\le ϵ\ell \log K$ for every $\ell \ge {\ell }_0$; such a threshold exists because $\log \ell /\ell \to 0$. ThereforeFor $K=1$, a finite integer set has $|A+A|\ge 2|A|-1$ (list the increasing sums $a_1+a_1,\dots ,a_1+a_N,a_2+a_N,\dots ,a_N+a_N$). Thus $N=1$, and the asserted bound holds for every $\ell$. Nonemptiness is implicit in the doubling constant hypothesis.