Past exam of the mathematics course of the University of Cambridge / 2001 / iii / Paper 76 (Combinatorial Number Theory)

Put $e(t)=e^{2\pi it}$ and let $P(n)=\theta n^k+\cdots$ be a real polynomial of degree $k\ge 2$. A standard form of Weyl inequality is: if $(a,q)=1$ and $|\theta -a/q|\le q^{-2}$, then for every $\eta >0$The implied constant is uniform in all lower coefficients. For degree one the finite geometric series bound is $|\sum e(\theta n+\beta )|\le \min (N,(2\Vert \theta \Vert {)}^{-1})$, where $\Vert t\Vert$ is distance to the nearest integer.

Here is the Weyl differencing proof. Extend $z_n=e(P(n))$ by zero outside $[1,N]$. Expanding $|\sum z_n{|}^2$ by differences of indices gives a sum of correlations ${\sum }_n{z}_{n+h}\overline{z_n}$. Repeated Cauchy-Schwarz inequality and this correlation identity yield, after $k-1$ steps, with $p=2^{k-1}$,The interval $I(\mathbf{h})$ ensures that every shifted argument remains in $[1,N]$. For completeness, the induction is the following: at stage $j$, the factor is $N^{2^j-j-1}$ and there is a sum over $j$ shifts. Squaring, Cauchy-Schwarz over those $O(N^j)$ shifts supplies $N^j$; expanding the square of each remaining interval sum introduces the next shift. The new factor is $N^{2^{j+1}-j-2}$, as asserted for stage $j+1$.

The final differenced phase is linear, of slope $k!\theta h_1\cdots h_{k-1}$. Zero products contribute $O_k(N^{k-1})$ to the sum. For nonzero products the finite geometric series bound applies. Grouping by $r=|h_1\cdots h_{k-1}|\le N^{k-1}$, the subpower bound for the divisor function bounds the number of representations by $O_{k,\rho }(N^{\rho })$ for any chosen $\rho >0$. The divisor input is elementary: for $t=k-1$, the number of ordered factorizations of $r$ is ${\prod }_{p^v\parallel r}\left(\genfrac{}{}{0ex}{}{v+t-1}{t-1}\right)$. For all sufficiently large primes this is bounded factorwise by $p^{ϵv}$, and for the finitely many smaller primes the polynomial in $v$ is bounded by a constant times $p^{ϵv}$. Multiplication gives $O_{t,ϵ}(r^{ϵ})$. ThusThe reduced denominator of $k!a/q$ is between $q/k!$ and $q$. Its approximation error is bounded by a constant depending on $k$ times the inverse square of that denominator. Split the $r$-range into blocks of length a sufficiently small fixed multiple of $q$. Within a block the values $k!\theta r$ are separated modulo one by a constant multiple of $1/q$: rational differences have spacing at least $1/q$, while the approximation error in a block difference is smaller than half that spacing. At most a bounded number of values occupy each distance interval of width $1/q$. Summing reciprocals of their ordered distances proves the reciprocal fractional-part sum near a rational estimateFor $q>N^k$, the proposed inequality follows from $|S|\le N$. Otherwise the last display and the differencing estimate giveChoose $\rho$ sufficiently small, absorb the logarithm into a further arbitrarily small power of $N$, and take $p$th roots. This proves the stated Weyl inequality.

For the recurrence assertion, a rational $a=u/v$ gives an integer $a{m}^2$ with $m=v$. For irrational $a$, Weyl differencing implies that $a{m}^2$ is an equidistributed sequence modulo one. One way to avoid a rate issue for unusually good rational approximations is to keep a fixed differencing range $H$: the Van der Corput inequality for finite scalar sequences gives, for each nonzero integer $j$, a limsup bound ${\mathrm{limsup}}_N|N^{-1}{\sum }_{m\le N}e(ja{m}^2){|}^2\ll 1/H$, because every fixed nonzero difference has irrational linear slope and its geometric average tends to zero. Let $H\to \infty$ and apply the Weyl criterion. Hence some $m$ always enters the open $ϵ$-neighborhood of zero.

Finally, $U_m=\{a\in \mathbb{R}/\mathbb{Z}:\Vert a{m}^2\Vert <ϵ\}$ are open sets covering the compact circle group. A finite subcover has a largest index $N$. That single $N$ works for every real $a$. This is uniform square recurrence on the circle; the compactness step gives existence, not an explicit quantitative bound.

Vinogradov's three-primes theorem states that every sufficiently large odd positive integer is a sum of three primes, with repetitions allowed. The parity restriction is a genuine local obstruction to the main asymptotic, not merely a technical convenience.

Let $n$ be large and define the prime-weighted exponential sumwhere $\Lambda$ is the Von Mangoldt function. Character orthogonality gives the Hardy-Littlewood circle method identityThe task is to extract a positive main term from rational neighborhoods and make the remaining integral smaller.

Take $Q=(\log n{)}^B$, with a fixed sufficiently large $B$, and use major arcs $|\theta -a/q|\le Q/n$ around reduced fractions with $q\le Q$. They are disjoint once $n$ is large relative to $Q^3$. The minor arcs are their complement. On a major arc put $\theta =a/q+\beta$. The Siegel–Walfisz theorem, followed by partial summation in each residue class, givesuniformly on these arcs after choosing the underlying logarithmic error exponent sufficiently large. The reduced residue-class sum is the Ramanujan sum $c_q(a)=\mu (q)$ when $(a,q)=1$. Prime powers dividing $q$ and the partial-summation factor $1+n|\beta |$ are absorbed in the stated error choice.

Cubing and integrating produces the singular series and singular integral:The last identity is Fourier inversion for the volume of the simplex $t_1+t_2+t_3=n$, $t_i\ge 0$; the upper bounds $t_i\le n$ do not restrict its interior. The tails and approximation errors are $o(n^2)$. Since $\mu (q{)}^3=\mu (q)$ on squarefree $q$, multiplicativity givesFor even $n$ the factor at $2$ vanishes. For odd $n$ it is $2$, andThe lower bound is uniform in odd $n$. The product converges because the sums of the local deviations converge. It describes how congruence restrictions alter the otherwise random prime-summand density.

For the minor arcs, a Type I/II prime-sum estimate provides the necessary cancellation. One useful form, obtainable from Vaughan's identity and bilinear estimates, iswhen $|\theta -a/q|\le q^{-2}$. Dirichlet's approximation theorem supplies a denominator $q\le n/Q$ with $|\theta -a/q|\le Q/(qn)$. On the minor arcs its denominator must exceed $Q$, so both denominator-dependent terms are at most $n/\sqrt{Q}$. Choosing $B$ large gives ${\sup }_{\mathfrak{m}}|S(\theta )|=o(n/\log n)$. The mechanism is to split $\Lambda$ into short-divisor Type I sums and bilinear Type II sums; geometric-sum bounds treat Type I, while Cauchy-Schwarz exposes correlations and rational spacing in Type II. The displayed estimate is the substantive analytic input, rather than a consequence of bounding each summand separately.

Meanwhile Parseval identity and the elementary prime-weight second moment giveThereforeCombining the two regions yields $R_{\Lambda }(n)=\frac{1}{2}\mathfrak{S}(n)n^2+o(n^2)$. Proper prime powers account for only $O(n^{3/2}(\log n{)}^4)$: there are $O(\sqrt{n}\log n)$ such choices for one coordinate, at most $n$ choices for another, and each weight is at most $\log n$. Hence they cannot account for the positive main term. The weighted count using primes alone is positive for every sufficiently large odd $n$, proving the asserted representation. The conclusion is the sufficiently-large three-prime theorem; no verification of every small odd integer is supplied by this argument.

The sumset form of Plünnecke's inequality states: for nonempty finite sets $A,B$ in an abelian group, if $|A+B|\le K|A|$, there is a nonempty $X\subseteq A$ such thatHere $0B=\{0\}$. The same $X$ can be used for every $m$. This sumset statement follows from an elementary minimal-growth argument.

Choose $X$ minimizing $\kappa =|X+B|/|X|$ among nonempty subsets of $A$. Then $\kappa \le K$ and $|Y+B|\ge \kappa |Y|$ for every $Y\subseteq X$, including the empty set. We prove the Petridis minimal-growth lemmafor each finite set $C$. Enumerate $C=\{c_1,\dots ,c_t\}$. Put $C_i=\{c_1,\dots ,c_i\}$ and defineThe disjoint new contributions to $X+C$ have sizes $|X_i|$, so $|X+C|={\sum }_i|X_i|$. For $y\in Y_i$, the point $y+c_i$ was already present in $X+C_{i-1}$, hence $y+B+c_i\subseteq X+B+C_{i-1}$. Consequently the new contribution at stage $i$ to $X+B+C$ has size at mostSumming proves the lemma. Starting with $C=\{0\}$ and then taking $C=(m-1)B$ gives inductively $|X+mB|\le {\kappa }^m|X|\le K^m|X|$, proving the stated Plünnecke inequality.

Apply Plünnecke's inequality with the summand set also equal to $A$. There is a nonempty $X\subseteq A$ satisfying $|X+mA|\le C^m|X|$ for every $m\ge 0$.

We need the Ruzsa triangle inequality in a form whose short proof also fixes the signs. For every $z\in R-S$, choose one representation $z=r_z-s_z$. The mapis injective into $(R+X)\times (S+X)$: its difference recovers $z$, then the fixed representation recovers $x$. ThereforeUse $R=rA$ and $S=sA$ and the common set $X$ from the previous part:ThusThe shared minimizing subset is important; applying separate growth estimates with unrelated subsets would not justify this bound.

One quantitative form of the Balog-Szemerédi-Gowers theorem is: if a nonempty finite set $A$ in an abelian group has $|A|=n$ and additive energy $E(A)\ge \eta n^3$, where $0<\eta \le 1$, then there is $B\subseteq A$ with $|B|\ge c_{\eta }n$ and both $|B-B|$ and $|B+B|$ bounded by $K_{\eta }|B|$. The constants depend only on $\eta$. We prove explicit, nonoptimal polynomial bounds, thereby proving the required Balog–Szemerédi statement.

Let $r(s)=|\{(a,a^{\prime })\in A^2:a+a^{\prime }=s\}|$. Then $E(A)={\sum }_{s}r(s{)}^2$. Declare $S=\{s:r(s)\ge \eta n/2\}$ to be the set of popular sums. The remaining sums contribute at most $(\eta n/2){\sum }_{s}r(s)=\eta n^3/2$. Since $r(s)\le n$, it follows that ${\sum }_{s\in S}r(s)\ge \eta n^2/2$. Also $|S|\le 2n/\eta$. Form a bipartite graph on two copies of $A$, joining $a$ to $a^{\prime }$ when $a+a^{\prime }\in S$. Its density is at least $\rho =\eta /2$.

We prove the needed four-step path lemma for a dense bipartite graph. Call an ordered pair of left vertices bad if its number of common right neighbors is less than $\tau n$, where $\tau ={\rho }^2/32$. For a uniformly chosen right vertex $y$, let $U=N(y)$ and let $b(U)$ count bad ordered pairs in $U^2$. ThenConsequently some $y$ satisfiesFor this $U$, $|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; the retained set $B$ has $|B|\ge |U|/2\ge \rho n/4$. For any $a,b\in B$, at least $|U|/2$ middle vertices $u\in U$ are good partners of both. Each such $u$ supplies at least $(\tau n{)}^2$ walks $a,v,u,w,b$ of four edges. Hence every pair in $B$ has at leastsuch walks. Repetition of vertices is allowed; it does not affect the counting argument.

Each walk has edge labelsall in $S$, and $a-b=s_1-s_2+s_3-s_4$. For a fixed pair $a,b$, these four labels determine $v,u,w$, so distinct walks have distinct label quadruples. For each element of $B-B$, fix one representing pair $a,b$. Label quadruples for distinct differences cannot overlap. ThereforeUsing $\rho =\eta /2$ and $|S|\le 2n/\eta$ yieldsThis proves the small-difference-set form of the Balog-Szemerédi-Gowers theorem. To obtain a small sumset too, write $K=2^{24}{\eta }^{-10}$ and apply the already proved Plünnecke inequality to starting set $-B$ and summand set $B$. Some nonempty $X\subseteq -B$ has $|X+2B|\le K^2|X|$. For any fixed $x\in X$, $x+2B\subseteq X+2B$, whence $|B+B|\le K^2|B|$. Thus the conventional small-sumset conclusion also follows with constants depending only on $\eta$.

For $k\ge 2$, the following precise cardinality-controlled cyclic Freiman model suffices. If $A\subseteq \mathbb{Z}$ is nonempty, $|A|=n$ and $D=kA-kA$ has $|D|\le Cn$, there is $A^{\prime }\subseteq A$ withHere ${\cong }_k$ means a bijection preserving and reflecting all equalities of $k$-term sums, a Freiman s-isomorphism of order $s=k$. The same construction works for $k=1$ if only injectivity is needed.

Choose an auxiliary prime $P$ larger than $N$ and every nonzero absolute value in $D$, and large enough to embed the finite set $A$ injectively modulo $P$. Multiply its residues by a uniformly chosen nonzero residue $u$. For a fixed $d\in D\setminus \{0\}$, $ud$ is uniform among the $P-1$ nonzero residues. The forbidden residues areof number at most $2(P-1)/N$. The union bound says that the probability some nonzero $d\in D$ enters $\mathcal{F}$ is at most $2(|D|-1)/N<1$. Fix a multiplier avoiding every forbidden event.

Let $\tilde{a}\in \{0,\dots ,P-1\}$ represent $ua(\mathrm{mod}P)$. Partition that range into $k+1$ half-open intervals of length $P/(k+1)$ and retain the most populated interval; it supplies $A^{\prime }$ with $|A^{\prime }|\ge n/(k+1)$. Define the model map by $\theta (a)=\tilde{a}(\mathrm{mod}N)$. For two $k$-term sums of retained representatives, their difference $T$ has $|T|<P$. If the original sums are equal, then $T\equiv 0(\mathrm{mod}P)$, hence $T=0$, so the model preserves the equality.

Conversely, if the model sums are equal, then $T$ is a multiple of $N$. If their original difference $d\in D$ were nonzero, it would satisfy $ud\equiv T(\mathrm{mod}P)$ with $0<|T|<P$, contradicting the forbidden-event choice. If $T=0$ directly, $ud\equiv 0$ implies $d=0$ too by the choice of $P$. Thus the equality is reflected. Padding equal one-term images with $k-1$ copies of a fixed retained element shows that the map is injective. This proves the Freiman s-isomorphism and the claimed bound on the cyclic modulus, independently of the diameter of $A$.

Let $T_3(A)$ count ordered solutions $a+c=2b$ in $A^3$, including the trivial ones. The hypothesis gives $T_3(A)\ge c{n}^2$. Its relation to additive energy is the promised easy Fourier step. Translate $A$ into $[0,M]$ and embed it in an odd prime cyclic group of order $P>4M$. No relevant integer equality wraps modulo $P$. With the unnormalized Fourier transform $\hat{f}(r)={\sum }_x{1}_A(x)e(-rx/P)$, character orthogonality givesSince multiplication by $2$ permutes the characters, Cauchy-Schwarz and Parseval identity on a finite group implyThus $E(A)\ge c^2{n}^3$. Equivalently, one can apply Cauchy-Schwarz directly to $T_3(A)={\sum }_{b\in A}{r}_{A+A}(2b)$.

By part (i), some $B\subseteq A$ has $|B|\ge c_1(c)n$ and $|B+B|\le K(c)|B|$. Part 3(ii) then bounds $|2B-2B|\le K(c{)}^4|B|$. Apply part (ii) with $k=2$: there is $B^{\prime }\subseteq B$, $|B^{\prime }|\ge |B|/3$, Freiman 2-isomorphic to a subset $C\subseteq {\mathbb{Z}}_N$ with $N\le 4K(c{)}^4|B|+1$. Consequently $C$ has a positive subset density depending only on $c$, and $N$ tends to infinity with $n$ because $N\ge |B^{\prime }|$.

View the representatives of $C$ as a subset of $\{0,\dots ,N-1\}$. The assumed four-term case of Szemerédi's theorem gives four distinct integer representatives in arithmetic progression once $n$ is sufficiently large in terms of $c$. If their preimages are $b_0,b_1,b_2,b_3$, the two model equalitieslift through the Freiman 2-isomorphism to the same equalities in $\mathbb{Z}$. Hence their consecutive differences agree; injectivity makes the common difference nonzero. Therefore $A$ contains a nonconstant four-term arithmetic progression. This proves dense three-term progressions force four-term progressions without an assumption that $A$ initially lies in a short interval.

Use ${\Delta }_{h}f(x)=f(x+h)\overline{f(x)}$ and the unnormalized Fourier transformWe state the eighth-power convention explicitly. A bounded function is $\alpha$-quadratically uniform ifwhere $\mathcal{C}$ means conjugation and every expectation is uniform. The expression is real and nonnegative. Applying Parseval identity on a finite group to the multiplicative derivatives gives the equivalent conditionThis is the Derivative identity for the Gowers U3 norm. A set $A$ of density $\delta$ is quadratically uniform when its balanced subset indicator $1_A-\delta$ satisfies that condition, not when its unbalanced indicator does. Some definitions bound $\Vert f{\Vert }_{U^3}$ rather than its eighth power; that norm parameter is ${\alpha }^{1/8}$ in the convention here. Quadratic uniformity controls three-dimensional additive cubes and four-term progression counts; small ordinary linear Fourier coefficients alone are not the same condition.

Define the normalized progression averageWe first prove the needed four-term progression bound with torsion factors, valid for the arbitrary cyclic modulus in the question:For the factor at slope zero, write $y=x+3d$, $t=d$, and apply Cauchy-Schwarz to discard $f_3(y)$:For concise bookkeeping put $D_{h}f(x)=f(x)\overline{f(x+h)}$, the conjugate of the preceding derivative convention, and $F_{i,h}=D_{-(3-i)h}{f}_i$. Expanding the square with $t,t+h$ and setting $z=y-t$ gives ${\mathbb{E}}_{z,t,h}{F}_{0,h}(z-2t)F_{1,h}(z-t)F_{2,h}(z)$. Another Cauchy-Schwarz, now in $(z,h)$, discards $F_{2,h}$ and yieldsExpand with $t,t+k$, set $w=z-t$, and apply Cauchy-Schwarz a third time to discard $D_{-k}{F}_{1,h}(w)$. The remaining $t$-average is a full average over $x=w-t$, soNegating $h,k$ does not change the average. The nonnegative integrand depends only on $2k$ and $3h$. Averaging over the subgroups $2{\mathbb{Z}}_N$ and $3{\mathbb{Z}}_N$ costs at most their indices $t_2=\gcd (2,N)$ and $t_3=\gcd (3,N)$ compared with unrestricted increments. The unrestricted expression is exactly $\Vert f_0{\Vert }_{U^3}^8$, obtained by expanding the last squared average. Thus the bound is $(t_2{t}_3{)}^{1/8}\Vert f_0{\Vert }_{U^3}\le 6^{1/8}\Vert f_0{\Vert }_{U^3}$.

Reversing the progression handles slope three. To isolate slope one, eliminate slopes three, zero and two successively in the same calculation; the surviving increments have coefficients $-2,1,-1$, so only the index $t_2$ is needed. Reversal handles slope two. This proves the minimum-over-factors bound, without assuming that $2$ or $3$ is invertible modulo $N$.

If $\delta =0$, the requested lower bound is zero and is immediate. Otherwise let $g=1_A-\delta$. Telescoping the product of four copies of $1_A=\delta +g$ against the constant product ${\delta }^4$ gives four error terms, each with one factor $g$ and three factors bounded by one. HenceIn particular, choosing $\alpha \le {\delta }^{32}/(6\cdot 8^8)$ givesThese are ordered modular progression parameters $(x,d)$, as requested; small-order differences and $d=0$ are included. A claim of distinct nontrivial progressions would need a separate subtraction and size condition.

Normalize the selected derivative correlations byThey satisfy $|c_k|\le 1$, and the hypothesis gives ${\sum }_{k\in B}|c_k{|}^2\ge \alpha N$. Thus $T={\sum }_{k\in B}|c_k|\ge \alpha N$. Choose phases ${\omega }_k$ of modulus one so that ${\omega }_k{c}_k=|c_k|$, with any choice if $c_k=0$. ThenOne Cauchy-Schwarz givesExpand into pairs $a,b\in B$ and group them by $t=a-b$, $r=\varphi (a)-\varphi (b)$. After translating $y=x+b$, the derivative correlation isThe grouped coefficient isConsequently $T^2\le {\sum }_{t,r}\gamma (t,r)C(t,r)$, whose right-hand side is the real nonnegative expanded square. A second Cauchy-Schwarz yieldsIf $m(t,r)$ counts the pairs in the displayed coefficient, then $|\gamma (t,r)|\le m(t,r)$. Thus $\sum |\gamma {|}^2\le \sum m^2=E(\Gamma )$, the additive energy of a frequency graph $\Gamma =\{(k,\varphi (k)):k\in B\}$. Equality of two pair differences is equivalent, by permuting the four labels, to equality of the two requested sums in each coordinate.

For every $t$, Parseval identity on a finite group in normalized Fourier convention givesThere are $N$ shifts, so $T^4\le NE(\Gamma )$. Since $T\ge \alpha N$, we concludeThis is precisely the number of ordered $(a,b,c,d)\in B^4$ satisfying both $a+b=c+d$ and $\varphi (a)+\varphi (b)=\varphi (c)+\varphi (d)$, all modulo $N$. It proves squared derivative correlations force frequency-graph energy with the constant and exact equalities stated, rather than approximate frequency matching.