Past exam of the mathematics course of the University of Cambridge / 2009 / iii / Paper 13 (Additive Combinatorics)

Put $e_N(t)=e^{2\pi it/N}$ and use normalized averages ${\mathbb{E}}_x=N^{-1}{\sum }_{x\in \mathbb{Z}/N\mathbb{Z}}$. Our convention for Fourier coefficients on a finite abelian group isThe underlying orthogonality of complex exponentials is ${\mathbb{E}}_x{e}_N(rx)=1$ for $r=0$ and zero otherwise. For nonzero $r$ this is the finite geometric series with ratio $e_N(r)\ne 1$; its sum vanishes because that ratio has $N$th power one. The identical orthogonality statement holds when averaging over $r$ instead of $x$.

Using this orthogonality to sum the definition over $r$ proves Fourier inversion on a finite group:Indeed $\mathbb{E}f\overline{g}={\sum }_r\overline{\hat{g}(r)}{\mathbb{E}}_{x}f(x)e_N(-rx)={\sum }_r\hat{f}(r)\overline{\hat{g}(r)}$. This proves the Parseval identity on a finite group and its squared-norm case:For normalized convolution on a finite group, write $(f\ast g)(x)={\mathbb{E}}_{y}f(y)g(x-y)$. Changing variables $x=y+z$ in its transform givesthe convolution theorem on a finite group. Linearity of the transform follows directly from its definition. Translation ${\tau }_{t}f(x)=f(x+t)$ gives $\widehat{{\tau }_{t}f}(r)=e_N(rt)\hat{f}(r)$ by changing variables. Complex conjugation gives $\hat{\overline{f}}(r)=\overline{\hat{f}(-r)}$; for $\tilde{f}(x)=\overline{f(-x)}$, the corresponding identity is $\hat{\tilde{f}}(r)=\overline{\hat{f}(r)}$. Finally $\hat{f}(0)=\mathbb{E}f$ and $|\hat{f}(r)|\le \mathbb{E}|f|$ by the triangle inequality. These identities establish the basic normalized Fourier analysis on a finite abelian group needed below, with all normalizations fixed.

For completeness, pointwise multiplication has the dual convolution formula $\widehat{fg}(r)={\sum }_s\hat{f}(s)\hat{g}(r-s)$: insert the inversion formula for $g$ into the defining average and collect its frequencies. If $c\ne 0$ modulo $N$, the change of variables $u=cx$ gives $\widehat{f(c\cdot )}(r)=\hat{f}(r{c}^{-1})$. These also follow directly from the same additive character orthogonality.

Assume $A$ is nonempty, so $0<\alpha \le 1$, and put $a=1_A$. By the Parseval identity on a finite group, ${\sum }_r|\hat{a}(r){|}^2=\alpha$. Select the nonzero frequenciesThen $|R|{\alpha }^3/4\le \alpha$, giving $|R|\le 4{\alpha }^{-2}$. Outside $R\cup \{0\}$, the fourth Fourier moment has the boundThe fourfold normalized convolution on a finite group $H=a\ast a\ast 1_{-A}\ast 1_{-A}$ has transform $|\hat{a}(r){|}^4$, so Fourier inversion on a finite group gives $H(x)={\sum }_r|\hat{a}(r){|}^4{e}_N(rx)$. It is real and nonnegative, and $H(x)>0$ implies $x\in 2A-2A$ because the convolution counts representations, with a positive normalization.

Use the Bohr set in phase-distance conventionOn this set all retained additive characters have positive real part. The zero-frequency contribution is $\hat{a}(0{)}^4={\alpha }^4$, and the total absolute contribution of the discarded frequencies is at most ${\alpha }^4/4$. HenceThereforeThis is an explicit Bogolyubov lemma. In the chord-distance convention for a Bohr set, the phase-radius $1/10$ corresponds to chord radius $2\sin (\pi /10)>1/10$; alternatively the same positivity proof works directly at chord radius $1/10$. Thus the requested lower bound on width holds in either convention. If $R$ is empty, the Bohr set is the whole group. Nonemptiness of $A$ is necessary for the density statement.

Count a three-term arithmetic progression as an ordered triple $(x,x+d,x+2d)$, allowing $d=0$. Inserting Fourier inversion on a finite group into its normalized count and using additive character orthogonality in $x,d$ givesIndeed the two frequency constraints are $r+s+t=0$ and $s+2t=0$, so the surviving frequencies are $(r,s,t)=(t,-2t,t)$. The term at zero is ${\alpha }^3$.

For odd $N$, let $f=a-\alpha$ be the balanced indicator function of a finite subset, and put $M={\max }_{s\ne 0}|\hat{f}(s)|$. Its zero coefficient is zero, and its other coefficients equal those of $a$. Since $-2r\ne 0$ when $r\ne 0$, the Parseval identity on a finite group givesThe assumed deficit $T<{\alpha }^3/2$ therefore forcesThus $c=1/2$ and $C=2$ suffice. This is the large Fourier coefficient from a deficit of three-term progressions estimate; no generalized von Neumann theorem is needed. For the remaining prime $N=2$, the count is $T={\mathbb{E}}_{x,d}a(x)a(x+d)={\alpha }^2$, so the deficit hypothesis is impossible. The zero common difference was included throughout.

Write $e(t)=e^{2\pi it}$. We first prove the needed cancellation of quadratic exponential sums, rather than invoke equidistribution without proof. The number $\sqrt{2}$ is irrational: writing it as a reduced fraction would make its numerator even from $u^2=2v^2$, and then its denominator even as well, a contradiction. Thus $2hr\sqrt{2}$ is irrational for nonzero integers $h,r$.

Fix $h\ne 0$ and set $z_n=e(h\sqrt{2}{n}^2)$ for $1\le n\le L$, extending it by zero otherwise. For integers $L\ge H\ge 1$, each term appears exactly $H$ times in the shifted sum, soFor any complex numbers $w_1,\dots ,w_J$, nonnegativity of ${\sum }_j|w_j-J^{-1}{\sum }_i{w}_i{|}^2$ gives $|{\sum }_j{w}_j{|}^2\le J{\sum }_j|w_j{|}^2$. Apply this special Cauchy-Schwarz inequality to the displayed outer sum, and then expand the inner squared modulus. This givesFor fixed $H$ and large $L$, each correlation is the geometric serieswhose absolute value is at most $2/|1-e(2hr\sqrt{2})|$, independently of $L$. This follows by multiplying the geometric sum by $1-e(2hr\sqrt{2})$; its denominator is nonzero by irrationality. Divide the inequality by $L^2$ and let $L\to \infty$, keeping $H$ fixed. It gives a limit superior at most $1/H$. Taking arbitrarily large $H$ provesThis is the quadratic instance of the Van der Corput inequality for finite scalar sequences, with its proof supplied here.

To turn cancellation into the particular approximation, put $\epsilon =10^{-8}$ and choose an integer $M>2/{\sin }^2(\pi \epsilon )$. The Fejér kernel is the explicit finite trigonometric polynomialThe expansion follows by counting pairs of indices with difference $h$. Its constant coefficient is one, so the cancellation just proved givesIf $\Vert t{\Vert }_{\mathbb{R}/\mathbb{Z}}\ge \epsilon$, the geometric-series formula givesFor all sufficiently large $L$, the displayed average exceeds $1/2$. Consequently at least one $n\in \{1,\dots ,L\}$ satisfiesIt is a positive integer, as required. Every auxiliary cancellation and kernel identity used in this existence proof has been derived; a smooth cutoff or an unproved Weyl criterion is unnecessary.

A Freiman 2-isomorphism between subsets of abelian groups is a bijection $\varphi$ such thatBoth directions matter: an injective homomorphism on individual elements may still create new pair-sum relations. More generally a Freiman s-isomorphism preserves equalities of sums of $s$ elements in both directions. For a nonempty finite set, its doubling constant is $\sigma [A]=|A+A|/|A|$. A Freiman 2-isomorphism preserves this constant, since $a+b\mapsto \varphi (a)+\varphi (b)$ is a well-defined bijection of the two sumsets.

First let $A\subseteq \mathbb{Z}$ have $n$ elements and doubling at most $K$. The permitted Plünnecke-Ruzsa inequality gives $|2A-2A|\le K^{4}n$. We will obtain the half-size prime cyclic Freiman model for every prime $p>4K^{4}n$. Choose an auxiliary prime $q>p$ larger than the absolute value of every member of $2A-2A$. Such a prime exists: for any integer bound $M$, every prime divisor of $M!+1$ exceeds $M$.

Choose $\lambda$ uniformly from the nonzero residues modulo $q$. For each nonzero $d\in 2A-2A$, the residue $\lambda d$ is uniform among the nonzero residues. PutThere are at most $2(q-1)/p$ such residues, and therefore the probability that any of the nonzero differences is dilated into $T$ is at mostThe first cardinal estimate is an upper bound even if some listed residues coincide; the slightly looser probability bound is convenient. Thus there exists $\lambda$ with no such bad difference.

For this $\lambda$, let $t_a\in \{0,\dots ,q-1\}$ represent $\lambda a$. Split these representatives into the two intervals $[0,(q-1)/2]$ and $[(q+1)/2,q-1]$. Take $A^{\prime }$ from the more populated interval, so $|A^{\prime }|\ge n/2$. For any four elements of $A^{\prime }$, put $D=t_{a_1}+t_{a_2}-t_{a_3}-t_{a_4}$. Their common half-interval gives $|D|<q$, andIf the original difference is zero, then $D$ is a multiple of $q$ of absolute value less than $q$, so $D=0$. If the original difference is nonzero, $D$ is nonzero, and it cannot be a multiple of $p$: otherwise its residue belongs to $T$, contrary to the choice of $\lambda$. Therefore $a\mapsto t_a(\mathrm{mod}p)$ preserves pair-sum relations in both directions. It is injective as well, by applying the relation test to $a+a_0=b+a_0$ with any fixed $a_0\in A^{\prime }$. HenceThis proves the stated polynomial bound, including the prescribed prime rather than just an unspecified cyclic modulus.

Now let $A\subseteq {\mathbb{F}}_2^{\infty }$. Finiteness of $A$ places it in some finite-dimensional coordinate space, so models exist. Choose a Freiman 2-isomorphism $A\to C\subseteq {\mathbb{F}}_2^m$ with $m$ minimal. The doubling constant of $C$ is at most $K$.

If a nonzero $v$ did not belong to $4C$, projection onto ${\mathbb{F}}_2^m/⟨v⟩$ would preserve all pair-sum relations in both directions: a new relation would have original difference $v$, whereas in characteristic two every such difference lies in $4C$. Projection is also injective on $C$, since $C+C\subseteq 4C$ by adding any element of $C$ twice. This would give a model in dimension $m-1$, contradicting minimality. Consequently every nonzero vector belongs to $4C$; zero belongs as well, by adding one element four times. Thus $4C={\mathbb{F}}_2^m$.

Using the Plünnecke-Ruzsa inequality once more givesThis is the minimal binary Freiman models have full fourfold sumset argument. It also covers a singleton, with $m=0$.

We take $\alpha ,\beta >0$, as is necessary for the assertion. The nonvacuous cases have $0<\alpha \le 1/2$ and $0<\beta \le 1$. Put $n=|A|$ andWe prove a lower bound for $K$ by transferring small sumset growth through algebraic operations on the scalars. This gives a self-contained polynomial skew-sumset expansion over a prime field proof using the permitted Ruzsa triangle inequality, Ruzsa covering lemma and Plünnecke-Ruzsa inequality.

Since $|B|>1$, choose $b_0\in B\setminus \{0\}$. The bound $|b_{0}A+A|\le K|b_{0}A|$ and the mixed-set Plünnecke-Ruzsa inequality giveIn particular $|A+A|\le K^{2}n$ and $|3A-2A|\le K^{5}n$. Here repeated-set sums such as $3A$ allow independent choices from each copy.

For a scalar $t$, write $D(t)=|A+tA|/n$, and put $Q=A-A$ for the difference set. The Ruzsa covering lemma gives $tA\subseteq T_t+Q$ with $|T_t|\le D(t)$. Indeed choose a maximal family of disjoint translates $u+A$, with $u\in tA$; counting their union bounds the family size, and maximality forces every remaining translate to meet one of them.

For any $r,s$, the containments $A+(r+s)A\subseteq A+rA+sA$ and $A+rsA\subseteq r{T}_s+A+rQ$ give, after covering each copy of $rA,sA$,For the second bound, specifically $rQ=rA-rA\subseteq T_r-T_r+2Q$, and $A+2Q=3A-2A$. The Ruzsa triangle inequality also gives $|A-rA|\le |A+A||A+rA|/n$, so $D(-r)\le K^{2}D(r)$. These are the closure bounds for small skew-sumset scalars.

We next prove a growth lemma for the scalar sets. For $S\subseteq {\mathbb{F}}_p$ with $m=|S|\ge 2$, letIf $R\ne {\mathbb{F}}_p$, then $R+1$ is not contained in $R$: otherwise equal cardinality would make $R$ invariant under addition of one, which generates the entire prime field. Choose $r=1+(a-b)/(c-d)\notin R$. The map $(x,y)\mapsto x+ry$ on $S^2$ is injective. Indeed a collision with different second coordinates would express $r$ as a ratio of two differences from $S$, while equal second coordinates force equal first coordinates. Clearing the nonzero denominator puts its image insideso the latter set has at least $m^2$ elements. Here $SS$ is the product set, and $3SS-3SS$ denotes three independent product terms minus three others, not multiplication by the scalar three.

If $R={\mathbb{F}}_p$, let $E_t$ count the collisions $x_1+t{y}_1=x_2+t{y}_2$ with all four variables in $S$. Summing over $t$ givesThe first term comes from equal second coordinates, which force equal first coordinates. For unequal second coordinates, each quadruple determines exactly one scalar. Some $t$ consequently satisfies $E_t\le m^2+m^4/p$. The Cauchy-Schwarz inequality on the representation counts givesRepresenting $t$ as a ratio from $R$ and clearing its denominator embeds a dilate of this sumset in $2SS-2SS\subseteq 3SS-3SS$, padding with the same product in the positive and negative sums. We have proved the quadratic growth of a sixfold product difference set estimate

Starting from $S_0=B$, define $S_{j+1}=3S_j{S}_j-3S_j{S}_j$. ChooseFor $p\ge \max (4,2^{2/\beta })$, the growth lemma implies $|S_k|\ge p/2$. To see the constants explicitly, put $v_j=|S_j|/2$. Then $v_0\ge p^{\beta /2}$ and $v_{j+1}\ge \min (p/4,v_j^2)$. Induction gives $v_j\ge \min (p/4,p^{\beta 2^{j-1}})$, and the chosen $k$ makes the exponent at least one.

Every $t\in S_0$ has $D(t)\le K$. If $D(t)\le K^{L_j}$ on $S_j$, the closure bounds show that each product has exponent at most $3L_j+5$, its negative at most $3L_j+7$, and a sum of six such terms has exponent at most $18L_j+67$. Thus, withwe have $|A+tA|\le K^{L_k}n$ for every $t\in S_k$. The integer $L_k$ depends only on $\beta$.

Now apply the collision count to $A$ instead of $S$. Summing over all scalars gives at most $p{n}^2+n^4$. Since $|S_k|\ge p/2$, some $t\in S_k$ has collision count at most $2n^2+2n^4/p$. The Cauchy-Schwarz inequality therefore givesIt follows thatFor $p\ge 4^{2/\alpha }$ this gives $K\ge p^{\alpha /(2L_k)}\ge n^{\alpha /(2L_k)}$, proving the desired positive exponent for all sufficiently large primes.

For completeness, the same conclusion with a possibly smaller exponent holds for the remaining primes. Choose an integerIf $p<P_0$, choose any nonzero $b\in B$. We have $1<n<p$. If $|A+bA|=n$, all its translates $A+u$ for $u\in bA$ would coincide. Two distinct such $u$ would make $A$ invariant under a nonzero translation, forcing $A={\mathbb{F}}_p$, a contradiction. Thus $|A+bA|\ge n+1\ge n^{1+c_{\alpha ,\beta }}$ by the definition of the second exponent. Together with the large-prime case this provesPositivity of the parameters cannot be dropped: at $\alpha =0$, taking $A={\mathbb{F}}_p$ prevents any expansion; at $\beta =0$, the allowed set $B=\{0\}$ prevents expansion of any proper $A$ with more than one element. No external sum-product theorem was invoked: the scalar growth and transfer arguments were proved above.