The dichotomy between structure and randomness, arithmetic progressions, and the primes

By Terence Tao. 2005

86 citations recorded by the source corpus.

A famous theorem of Szemer\'edi 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\'edi 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 Green-Tao theorem requires surprisingly little technology from analytic number theory, relying instead almost exclusively on manifestations of this dichotomy such as Szemer\'edi's 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.

Subfields: Algebra and Number Theory, Discrete Mathematics and Combinatorics

View Paper: https://www.semanticscholar.org/paper/9586e030ec330b893c213630fb1f79a02a53df09

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algebra and Number Theory

In Discrete Mathematics and Combinatorics

Citations in the corpus

Some open problems on multiple ergodic averages (2011, background): “Books and survey articles on related topics: [1, 4, 8, 23, 24, 26, 27, 28, 66, 67, 71, 89, 92, 93, 94, 95, 96, 102, 110, 126, 130, 131, 132, 133, 135, 157, 159, 167, 169, 170, 172, 179, 180, 182, 187, 188].”
New bounds for Szemeredi's theorem, II: A new bound for r_4(N) (2006, background): “Part I of the series [12] or the lecture notes [9] may be consulted for further discussion, and [27] gives a more general discussion of structure theorems and inverse theorems.”