A famous theorem of Szemerédi asserts that all subsets of the integers with positive upper density will contain arbitrarily long arithmetic progressions. There are many different proofs of this deep theorem, but they are all based on a fundamental dichotomy between structure
and randomness, which in turn leads (roughly speaking) to a decomposition of any object into a structured (low-complexity) component and a random (discorrelated) component. Important examples of these types of decompositions include the Furstenberg structure theorem and the Szemerédi regularity lemma. One recent application of this dichotomy is the result of Green and Tao establishing that the prime numbers contain arbitrarily long arithmetic progressions (despite
having density zero in the integers). The power of this dichotomy is evidenced by the fact that the GreenTao theorem requires surprisingly little technology from analytic number theory, relying
instead almost exclusively on manifestations of this dichotomy such as Szemerédis theorem.
In this paper we survey various manifestations of this dichotomy in combinatorics, harmonic analysis, ergodic theory, and number theory. As we hope to emphasize here, the underlying
themes in these arguments are remarkably similar even though the contexts are radically different. |