17
$\begingroup$

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?

$\endgroup$
1
  • 4
    $\begingroup$ My (incomplete) understanding is that the known proofs Szemerédi's Theorem admit no simplifications under the assumption $|A\cap [n]|\geq \delta n$ for a fixed $\delta<1$, such as $\delta=1/2$ in your question. Of course, if $|A\cap [n]|>(1-\frac{1}{k})n$, then $A$ contains $k$ consecutive elements (and therefore an AP of length $k$), but if you want the length of the AP to tend to $\infty$ with $n$, this doesn't help. Unfortunately I can't point to a specific reference discussing this fact. $\endgroup$ Jan 30, 2022 at 1:35

2 Answers 2

36
$\begingroup$

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).

$\endgroup$
1
  • 3
    $\begingroup$ Thank you very much for such a comprehensive and informative answer. It seems unlikely based on your edit above but is it still possible that the fixed density case could yield tighter bounds for the Van der Waerden numbers than those derivable from the effective versions of the full Szemeredi theorem? $\endgroup$
    – Ivan Meir
    Jan 30, 2022 at 21:54
0
$\begingroup$

SORRY I missread the question : it is not an answer : only a long comment.

In the book "Ramsey theory" Ronald Graham , Bruce Rotchild (second edition). The second chapter starts with a combinatorial proof of a specific (yet not trivial: 2-AP from 3 colors ) case of Van der Waerden's theorem, using drawings hence making things visual and easy. Then the recurrence becomes quite clear (easy?). If it is altogether not as lean as using Szemerédi's theorem it gives an intuition of what is going on. What is going on is the marvelous motto "Complete disorder is impossible" from Theodore Samuel Motzkin (cited at the start of chapter II).

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.