2 edited tags
1

# What is the shortest route to Roth's theorem?

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://www.dpmms.cam.ac.uk/~bjg23/AddCombinatorics/notes1.pdf. 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?