5
$\begingroup$

Applying topological dynamics to prove Van der Waerden's theorem on the existence of monochromatic arithmetic progression has now become a somewhat classical example of the power of topological dynamics techniques.

However, since the statement of the theorem is purely algebraic or number theoretic, I wonder whether there is a proof without using the machinery from dynamics and I guess such a proof might give more insight on the matter of the fact.

Thanks!

ps: How come there is no "topological dynamics"tag?

$\endgroup$
  • 1
    $\begingroup$ I think the Wikipedia article explains the classical proof pretty well. You do a double induction of the number of colors and the length of the progression you need. $\endgroup$ – MJD Mar 26 '12 at 2:39
  • $\begingroup$ A nice explanation of proof of vdW is given in Khinchin's book Three pearls of number theory. (Original: Три жемчужины теории чисел.) $\endgroup$ – Martin Sleziak Oct 19 '15 at 7:45
6
$\begingroup$

In historical order, there are four types of proof.

  1. Classical double induction argument (van der Waerden's proof and variants). Can be presented in finitary or "effective" form but leads to huge bounds that are not primitive recursive.

  2. Ergodic theory argument (Furstenburg and his school). This approach either does not produce explicit bounds or, when unwound, gives worse bounds than the classical method. It generalizes more readily and the first proofs of some of the "density" strengthenings of vdW in higher dimensions were done with ergodic theory.

  3. Shelah's single-induction argument for vdW and Hales-Jewett theorems. This gave an upper bound that is a tower of exponential functions. The height of the tower is approximately the length of the progression. This gigantic bound is much less huge than the classical non-primitive recursive proofs. Was considered a spectacular result but I don't know if it has since been adapted to prove the density analogues.

  4. Gowers' proofs that developed an analytic-algebraic-probabilistic context in which to understand and generalize the van der Waerden, Hales-Jewett, Szemerédi and other theorems of the same type. This approach proves iterated exponential bounds like $2^{2^{cn^d}}$ for some constants depending on the density (or the same with another $2$ in the tower, but the difference compared to the Shelah bounds is that height of the tower is independent of the length of the progression). Gowers also proves lower bounds of unbounded tower type for some of the constructions used in earlier proofs of generalized van der Waerden theorems but the true growth rate of the vdW numbers is not known.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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