What is the shortest route to Roth's theorem?

There's a short-cut in Roth's approach if one only cares to get $o(N)$. Adolf Hildebrand told me so, and here is my shortest writeup.

Notation: Let $r(N),\rho(N)$ be the largest cardinality and density of a subset of $[N]$ that is free of 3-term APs, and let $\rho=\lim \rho(N)$, which must exist by Fekete's subadditive lemma since $r(N+M)\leq r(N)+r(M)$. Let $A\subset [N]$ witness $r(N)$, and let $S(x) = \sum_{a\in A} e( a x)$ (where $e(ax)=\exp(2\pi i a x)$, naturally). Let $T(x)=\sum_{n=1}^N e(nx)$.

Lemmata: Now $r(N)=|A|=I:=\int_0^1 S(x)^2 S(-2x)dx$, since $A$ is 3-free. By Parseval, $|A|=\int_0^1 |S(x)|^2dx$. By expanding $S(x)^2 T(-2x)$ and exchanging integration and summation, $(|A|/2)^2 \leq I_0:=\int_0^1 S(x)^2 T(-2x)$.

Main Engine: As long as $0< M\leq N$, $$\sup_{x\in {\mathbb R}} |S(x)-\rho(M) T(x)| \leq N(\rho(M)-\rho(N)) + 10 M \sqrt{N}.$$ Proof is by circle method; set $E(x):=S(x)-\rho(M)T(x)$. Three steps are

  • $|E(a/q)|\leq N(\rho(M)-\rho(N))+2Mq$, the hard one;
  • $|E(a/q+\beta)| \leq N(\rho(M)-\rho(N))+2Mq +2\pi|\beta|NMq$;
  • $|E(x)| \leq N(\rho(M)-\rho(N))+10M\sqrt{N}$.

Main Lemma: By Main Engine and Lemmata, $\Delta:=|I-\rho(M)I_0|$ is at most $(N(\rho(M)-\rho(N))+10M\sqrt{N})|A|$. By Lemmata, $\Delta$ is at least $|A|(\rho(M)\rho(N)N/4-1)$. Therefore, $$\rho(N)\rho(M)\leq 4(\rho(M)-\rho(N))+50M/\sqrt{N}.$$

Conclusion: Let $N\to\infty$ and then $M\to\infty$ to get $\rho^2\leq 0$.

The step labeled "the hard one" in the Main Engine is tricky, and uses the fact that we can restrict $A$ to arithmetic progressions and still get a 3-free set. The length of the progressions we restrict to is connected to $M$.

I suppose the point is that a write-up can be almost arbitrarily short or extremely long, depending on what the reader can be trusted to fill in.


The most direct argument I know is the original argument of Szemerédi. It is background-free: no regularity lemma, no Fourier analysis. It is also very intuitive. There is a sketch by Ernie Croot at http://people.math.gatech.edu/~ecroot/szemeredi.pdf


On a slightly cheeky note, it seems that the shortest path to the best available bound, subject to peer review, is outlined in the following paper of Bloom-Sisak! Congratulations.