Van der Waerden's theorem states that any colouring of the integers in a finite number of colours has monochromatic arithmetic progressions of arbitrary length. Szemerédi's Theorem is a dramatic strengthening of this result and says that any set of positive integers with positive natural density contains arbitrary length arithmetic progressions. Clearly the latter theorem implies the former but not the other way round.
The proof of Van der Waerden's theorem although elementary is not simple and perhaps quite challenging to discover. However it would follow from the following theorem:
Theorem:
Let $A$ be subset of the integers such that $|A\cap [n]|\geq n/2$ for all $n>0$. Then $A$ contains an arithmetic progression of arbitrary length.
This is weaker than Szemeredi's theorem but seems only slightly stronger than Van der Waerden. Hence my question:
Is there a proof of the above theorem that is substantially simpler than the proof of Szemeredi's Theorem?
Best Answer
As (implicitly) observed already in Szemerédi's celebrated paper
Szemerédi, Endre, On sets of integers containing no (k) elements in arithmetic progression, Acta Arith. 27, 199-245 (1975). ZBL0303.10056.
(and perhaps previously), Szemerédi's theorem for a fixed density $0 < \delta_0 < 1$ (such as $\delta_0 = 1/2$), when combined with van der Waerden's theorem, implies Szemerédi's theorem for arbitrary density $\delta > 0$. This is because, once one is given a subset $A$ of integers in $\{1,\dots,N\}$ of density $\delta$, it is not difficult to use the probabilistic method to find $O_{\delta,\delta_0}(1)$ translates of $A$ (by shifts randomly selected between $-N$ and $N$) which cover this interval to density at least $\delta_0$. If one can find a sufficiently long arithmetic progression inside this union of translates, then by van der Waerden's theorem, at least one of these translates also contains a long progression, which gives Szemerédi's theorem for that density $\delta$.
As a consequence of this argument, the gap in difficulty between Szemerédi's theorem for a fixed density $0 < \delta_0 < 1$ (but arbitrary lengths $k$) and for arbitrary densities (and arbitrary lengths) is basically no greater than the difficulty required to prove van der Waerden's theorem (which can be proved in a page or two).
EDIT: the situation is very different if instead one fixes the length $k$ of the progression. As pointed out in comments, Szemerédi's theorem is now easy for very large densities such as $\delta > 1-1/k$, and the difficulty increases as the density lowers (although several proofs of Szemerédi's theorem proceed by a downward induction on density now commonly known as the density increment argument). However, in most proofs, the increase in difficulty as $\delta$ decreases is negligible compared to the increase in difficulty as $k$ increases; for instance the $k=3$ case of the theorem, first established by Roth, is substantially easier than the $k>3$ cases. So the van der Waerden reduction given above, which trades the small-$\delta$ difficulty for the large-$k$ difficulty, is generally not useful in practice (in particular, it is largely incompatible with any attempt to induct on $k$, which tends to be a key component of most approaches to this theorem).