Order is ubiquitous


Ramsey theory is the branch of mathematics that investigates the order inherent in any mathematical structure. Its theorems assert that sufficiently large mathematical structures must necessarily contain substructures possessing a higher degree of order than the original structure. The essence of this powerful collection of theorems was perhaps best stated by the American mathematician T. S. Motzkin: ``Complete disorder is impossible.''

I don't study Ramsey theory per se. Neither do most mathematicians but still most of us hit it one way or the other. Here is a most striking instance of it. Consider the set of natural numbers; 1,2,3,... The density of its subset A among the n first positive integers is just the cardinality of elements of A no greater than n divided by n. Upper density is the lim sup of this ratio as n goes to infinity. So even numbers have upper density 1/2, while the primes have zero by the Prime Number Theorem. Note that upper density existing for a set is a much weaker property than the density existing (upper and lower densities being the same number).

An arithmetic progression is an equally spaced set of integers: a, a+b, a+2b, ..., a and b integers, b>0.

Szemeredi's Theorem says that any subset of the natural numbers with positive upper density has arbitrarily long arithmetic progressions in it.

In other words, no matter how screwy subset of the naturals you pick up (at random or assemble it as fiendish a way as you can fathom) as long as it has upper density say one billionth, it has arbitrarily large perfectly ordered (in this case periodic) structures inside it. A most original proof of this theorem was given by Furstenberg and Katznelson in the eighties. It involves so many conceptual breakthroughs that many model theorist view it as one of the deepest proofs of the 20th century mathematics. It is about multiple recurrence and makes essential use of ergodic theoretic arguments. This theorem is an example of the infinite Ramsey theory. The fact that in every group of six people there are either three mutual acquaintances or three mutual strangers is a simple example of the finite theory.

The above is just the beginning of an exciting story. In 2004 Green and Tao established the converse of Dirichlet's theorem: they proved that primes contain arbitrarily long arithmetic progressions. Since primes are a set of zero density, the upper density assumption above is not necessary for "ordered subsets" to exist. Apart from settling a long standing question their stunning result also surprised by its form: the proof is like the ergodic theoretic proof (of the Szemeredi's Theorem), only more refined (and has far longer reach). Indeed many Dynamcs methods, entropy etc. are now well on their way into Analytic Number Theory as illustrated e.g. by the recent proof of the notorius Erdös Discrepancy problem.