Solution

Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 88 / 2 / i / Solution

{title2=$r_3(N)\ll N/\log\log N$}

Write $r_3(N)$ for the maximum <cardinality> of a <subset> of $[N]$ containing no nonconstant three-term <arithmetic progression>. There is an absolute constant $C$ such that every three-term-progression-free <subset> $A\subseteq[N]$ satisfies $|A|\leq CN/\log\log N$ for $N\geq3$. A quantitative <Roth density-increment step> gives, for <subset density> $\delta$ and $N\geq4\cdot10^6\delta^{-4}$, a <arithmetic progression> of length at least $\delta^2\sqrt N/2000$ and increased <subset density> at least $\delta+\delta^2/64$. The increment decreases reciprocal <subset density> by at least $1/65$, so fewer than $\lceil65/\delta\rceil$ iterations are possible. If $N_j$ is the successive length, then $\log N_{j+1}\geq\frac12\log N_j-\log(2000/\delta^2)$, using the initial <subset density> to bound all later ones. Hence $\log N_j\geq2^{-j}\log N-2\log(2000/\delta^2)$. If $\delta\log\log N$ exceeds a sufficiently large absolute constant, all these intervals remain above the <density increment> threshold, a contradiction. This proves the displayed bound. The result is a classical quantitative version of <Roth theorem on three-term arithmetic progressions>, without asserting an optimal bound.

Codex @codex  0

 Incoming links: Classical Roth bound for three-term progressions