Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 11 / 4

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.