23
$\begingroup$

Roth first proved that any subset of the integers with positive density contains a three term arithmetic progression in 1953. Since then, many other proofs have emerged (I can think of eight off the top of my head).

A lot of attention has gone into the bounds in Roth's theorem, and in particular what kind of bounds different proofs get you (e.g. Fourier analysis gives log type bounds, regularity lemma arguments give Ackermann type bounds, etc.)

Also, some proofs are more amenable to generalisation (to longer arithmetic progressions) than others.

My question is

If we are only concerned with brevity and directness (i.e. not with a deeper theoretical understanding or sharp quantitative bounds), what is the shortest proof of Roth's theorem?

Running through the arguments I know, it seems like the shortest one may be Roth's original one (with a couple of simplifications): show there is a large Fourier coefficient and deduce some sort of density increment argument and iterate it - a good exposition is in Tao and Vu, or Ben Green's notes at http://people.maths.ox.ac.uk/greenbj/notes.html . With all details fleshed out, this could probably be done in 8 pages or an hour lecture.

The odd thing is that this proof also gives fairly good quantitative bounds; if $r_3(N)$ is the size of the largest subset of $\{1,...,N\}$ without three term arithmetic progressions, then even a crude version of this argument gives $$ r_3(N)=O\left(\frac{N}{\log\log N^c}\right)$$ whereas all Roth needs is $o(N)$. Hence my second question,

Is it inevitable that the most direct and simple proofs would also lead to fairly good quantitative bounds?

Finally, an exercise in Tao and Vu mentions that Behrend's example of a lower bound for $r_3(N)$ shows that simple pigeonhole type arguments couldn't be used to prove Roth's theorem. Hence,

What other proof techniques wouldn't work with Roth's theorem?

$\endgroup$
3
  • 1
    $\begingroup$ You have probably thought about this more than I have, but isn't the proof through Szemerédi's regularity lemma easier and shorter? The lemma itself is simple to prove by energy increment (page and a half in Bollobas?), the triangle removal lemma is a quick corollary, and then Roth's theorem falls out. I would imagine the whole thing fits in three pages of LaTeX. However this "direct and simple proof" leads to poor bounds. $\endgroup$
    – Pietro
    Nov 23, 2010 at 4:44
  • $\begingroup$ I'd considered it, but I recalled the proof of SRL to be longer, and then the two subsequent corollaries to be lengthy if straightforward. I'll take a second look. $\endgroup$ Nov 23, 2010 at 6:10
  • 2
    $\begingroup$ Though this is not shortest, Tom Sanders recently found a very very nice argument that gives a significantly better bound, arxiv.org/abs/1011.0104 $\endgroup$ Nov 23, 2010 at 22:18

4 Answers 4

17
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ By the way, the Main lemma is strong enough to get from there to $\rho(N) \ll N / \log\log N$. The "shortcut" is just in the Conclusion step. $\endgroup$ Nov 25, 2010 at 15:53
13
$\begingroup$

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

$\endgroup$
2
8
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Obviously "shortest" is pretty subjective here because it depends on which results you take as given, how small your writing is etc. I remember learning the Fourier proof of the theorem for an exam and getting the proof down to a (comprehensible) 2 pages. But I don't remember what results I was relying on as lemmas etc.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.