Szemerédi's Theorem

Post-publication activity

Szemerédi's theorem states that any "positive fraction" of the positive integers will contain arbitrarily long arithmetic progressions $a, a+r, a+2r, \ldots, a+(k-1)r\ .$ More precisely,

Theorem (Szemerédi's theorem) Let $A \subset {\Bbb Z^+}$ be a subset of the positive integers of positive upper density, i.e., $d^*(A) := \limsup_{N \to \infty} \frac{\# \{ n \in A: n \leq N \}}{N} > 0\ .$ Then for any integer $k \geq 1\ ,$ the set $A$ contains at least one arithmetic progression $a, a+r, a+2r, \ldots, a+(k-1) r$ of length $k\ ,$ where $a, r$ are positive integers.

Intuitively, this theorem is saying that long arithmetic progressions are so prevalent that it is impossible to eradicate them from a set of positive integers unless one shrinks the set so much that it has density zero. This deep fact is rather striking, given that many other patterns (e.g., geometric progressions $a, a r, a r^2 $ with $ r>1 $) are much easier to eradicate (for instance, the set of squarefree numbers has positive upper density $ 6/\pi^2 \ ,$ but clearly contains no $ a r^2 $). One notable feature of the theorem is that there is almost no assumption made on the set $A\ ,$ other than one of size; the set $A$ could be very structured (e.g. an infinite arithmetic progression) or very irregular (e.g. a randomly generated set), and yet one has long arithmetic progressions in either case. In fact, understanding this dichotomy between structure and randomness is the key to all the known proofs of Szemerédi's theorem: it is possible to generate arithmetic progressions from structure and from randomness, but for two completely different reasons, and so one must somehow separate the structure from the randomness in order to proceed. The depth of this theorem can also be discerned from Behrend's counterexample to a natural stronger version of this theorem, which will be discussed later.

Szemerédi's theorem was initially conjectured by Erdős and Turán [ET] in 1936, but was only proven in full generality by Szemerédi [Sz2] in 1975. Several further important proofs of this theorem, using different types of analysis, were subsequently given, including an ergodic-theory proof by Furstenberg [F] in 1977, a Fourier-analytic and combinatorial proof by Gowers [Go2] in 2002, and proofs based on hypergraphs given by Gowers [Go3], [Go4] and by Nagle, Rődl, Schacht, and Skokan [NRS], [RSc], [RSk], [RSk2]. These proofs have also led to a number of deep and powerful generalisations and variants of the above theorem. Despite this multitude of proofs, though, the theorem is still considered quite deep and difficult.

Szemerédi's theorem was a major landmark in additive number theory for several reasons. Not only did it solve a well-known conjecture in the subject, the powerful methods introduced in order to prove this theorem have turned out to be tremendously useful in many other problems, and have stimulated development and progress in multiple fields of mathematics. Also, the theorem itself has been applied to prove many other results; for instance, it was a key component in the argument of Green and Tao [GT] demonstrating that the prime numbers contain arbitrarily long arithmetic progressions. (The primes have density zero, so Szemerédi's theorem does not apply directly; instead, the argument in [GT] combines Szemerédi's theorem with an additional transference argument, together with some number-theoretic estimates.)

This theorem can be easily deduced from Szemerédi's theorem (since, by the pigeonhole principle, at least one of the color classes will have positive upper density), but it is far more difficult to deduce Szemerédi's theorem from van der Waerden's theorem. For example, the hypotheses of van der Waerden's theorem imply that at least one color class will contain arbitrarily long geometric progressions, but as noted above there are sets with upper density larger than $1/2$ that do not even have 3 term geometric progressions.

van der Waerden's theorem is similar in spirit to Ramsey's theorem [Ram] for colorings of complete graphs, which appeared at about the same time; indeed these two theorems initiated the field of Ramsey theory, in which one seeks to establish the existence of various structures inside a color class of a larger structure.

Van der Waerden's proof of his theorem was elementary and quite short, but it was also highly recursive in nature, and so the effective bounds that the proof provided were very weak. For instance, if one colored the positive integers into $r$ colors and requested an arithmetic progression of length $k$ which was monochromatic (i.e. contained inside a single color class), then the proof did assert that such a progression would exist, and that all elements of that progression would be less than a certain finite quantity $W(k,r)$ depending on $k$ and $r$ (with the best such $W(k,r)$ known as the van der Waerden number of $k$ and $r$), but the upper bound on $W(k,r)$ provided by the proof grew incredibly quickly; even for $r=2\ ,$ the growth rate was like an Ackermann function in $k\ .$ (This growth rate was not improved until 1988, when Shelah [Sh] provided a growth rate which was primitive recursive, though still rather rapidly growing; the best upper bound currently known on $W(k,r)$ for general $k$ is $2^{2^{r^{2^{k+9}}}}\ ,$ due to Gowers [Go2] in 2001, and which was obtained via Szemerédi's theorem.)

In 1936, Erdős and Turán [ET] investigated the problem further, motivated in part by an old conjecture (proven in 2004) that the primes contained arbitrarily long arithmetic progressions. They proposed two conjectures which would imply van der Waerden's theorem. The first (weaker) conjecture was the statement that became Szemerédi's theorem; the second (stronger) conjecture, which they attribute to Szekeres, asserted an extremely quantitative bound, in particular that given any $k \geq 1$ there existed an $\varepsilon > 0\ ,$ such that any subset of $\{1,\ldots,n\}$ of cardinality at least $n^{1-\varepsilon}$ would necessarily contain at least one arithmetic progression of length $k\ ,$ if $n$ was sufficiently large depending on $k\ .$ They noted that this conjecture was in particular more than sufficient to guarantee that the primes contained arbitrarily long arithmetic progressions.

The stronger of these conjectures was disproven (even when $k=3\ ,$ which is the first non-trivial case) by Salem and Spencer [SS] in 1942, with improvements to the counterexample given by Behrend [Be] and Moser [M]. Remarkably, Behrend's 1946 counterexample is still the best known for the $k=3$ problem (higher $k$ variants of this example were constructed by Rankin [Ran]). It is based, ultimately, on the simple observation that a sphere in any dimension is convex and thus cannot contain any arithmetic progressions of length three. By working with a suitable discrete analogue $\{ x \in {\Bbb Z}^d: |x|^2 = r^2 \}$ of a sphere and then transplanting that set to the integers, Behrend was able to create, for arbitrarily large $n\ ,$ a subset of $\{1,\ldots,n\}$ of cardinality at least $n \exp( - c \sqrt{\log n} )$ for some absolute constant $c > 0\ ,$ which did not contain any arithmetic progressions of length three. In particular, the size of this set is asymptotically larger than $n^{1-\varepsilon}$ for any fixed $\varepsilon > 0\ .$ This type of counterexample rules out a number of elementary approaches to Szemerédi's theorem (e.g. using arguments based only on the pigeonhole principle, or the Cauchy-Schwarz inequality), and strongly suggests that the proof of these conjectures must be somehow "iterative" in nature.

The cases $k < 3$ of Szemerédi's theorem are trivial. The $k=3$ case was first settled by Roth [R] in 1953. This argument employed methods from Fourier analysis (or more specifically, the Hardy-Littlewood circle method). Roughly speaking, the idea was to assume for contradiction that one had a set of integers of positive density which contained no arithmetic progressions of length three, and then to use Fourier analysis to construct a new set of integers with even higher density which still contained no such progressions. Eventually one would be forced to construct a set of density exceeding $1\ ,$ which was of course absurd.

Roth's elegant argument failed to extend to the case of general $k\ ,$ for reasons which were not fully understood until the work of Gowers [Go2] much later. The $k=4$ case was first established by Szemerédi [Sz] in 1969 by an elementary but intricate combinatorial argument. Even with this breakthrough, the higher $k$ case continued to prove to be quite difficult, and it was only in 1975 that Szemerédi [Sz2] was able to establish his theorem in full generality. This problem was given a cash prize of $1000 by Paul Erdős, who was well-known for assigning prizes to difficult problems; Szemerédi was first mathematician to ever collect a prize of that magnitude from Erdős. (In 1984, Frankl and Rődl[FR] solved another problem to which Erdős offered $1000, although they only accepted $500 due to Erdős' financial situation[Ba].) Erdős later offered $3000 for a proof of a stronger conjecture (sometimes mis-attributed to [ET]), namely that any set $A$ of positive integers whose sum of reciprocals $\sum_{n \in A} \frac{1}{n}$ was divergent, would necessarily contain arbitrarily long progressions; this conjecture remains open to this day, even if one only seeks a single progression of length three. However, in the special case that the set $A$ consists of the prime numbers or a relatively dense subset thereof, the result was established in [GT].

Szemerédi's proof was very sophisticated (though elementary), and introduced a number of important new tools, most notably what is now known as the Szemerédi regularity lemma for graphs, which roughly speaking allows one to approximate any large dense graph in a certain statistical sense by a bounded complexity random graph. (This lemma has since had an enormous number of applications in combinatorics and computer science; see [KS] for a survey.) Two years later, in 1977, Furstenberg [F] introduced a dramatically different proof of that theorem, recasting the problem as one in dynamical systems, and then using methods from ergodic theory to solve the problem. More specifically, Furstenberg showed that Szemerédi's theorem was logically equivalent to the following, very different-looking, result:

Theorem (Furstenberg recurrence theorem) Let $(X, {\mathcal B}, \mu)$ be a probability space (thus ${\mathcal B}$ is a $\sigma$-algebra of subsets of $X\ ,$ and $\mu: {\mathcal B} \to [0,1]$ is a probability measure on $X$), let $T: X \to X$ be a measure-preserving bijection (thus $\mu(T(E)) = \mu(E)$ for all measurable $E$); we refer to $(X,{\mathcal B},\mu,T)$ as a measure-preserving system. Then for any set $E \subset X$ of positive measure and every integer $k \geq 1$ there exist infinitely many positive integers $n$ such that the set $E \cap T^n E \cap \ldots \cap T^{(k-1)n} E$ has positive measure. In fact, we have the slightly stronger statement \[ \displaystyle\liminf_{N \to\infty} \frac{1}{N} \sum_{n=1}^N \mu(E \cap T^n E \cap \ldots \cap T^{(k-1)n} E ) > 0.\]

The question of whether the sequence in the above equation was convergent (i.e. if the limit inferior could be replaced with a limit), and what that limit was, turned out to be surprisingly difficult, and was only settled in 2005 by Host and Kra [HK]. (A different proof was given in 2007 by Ziegler [Z] and a geometric interpretation of the limit was given by Ziegler in [Z2]; a third proof was given very recently in [T]). The $k=2$ case of this theorem is the classical Poincaré recurrence theorem, while the $k=1$ case is trivial. Just as Szemerédi's theorem is remarkable for requiring very few assumptions on the set $A\ ,$ Furstenberg's theorem is remarkable for requiring very few assumptions on the probability space $(X,\mu)\ ,$ the shift map $T\ ,$ or the set $E\ .$

The equivalence of Szemerédi's theorem and the Furstenberg recurrence theorem is due to a more general principle, first formulated in [F], and now known as the Furstenberg correspondence principle. Roughly speaking, the correspondence links sets $A$ of integers with sets $E$ in a measure-preserving system $(X,{\mathcal B},\mu,T)$ by looking at finite segments $\{ n \in A: 1 \leq n \leq N\}$ of $A$ and "taking limits"' as $N \to \infty$ in a certain weak topology. The proof of the Furstenberg recurrence theorem is shorter than the original proof of Szemerédi's theorem, and relies primarily on an induction on the $\sigma$-algebra ${\mathcal B}\ .$ A key theme in the proof is the dichotomy between two types of properties in a measure-preserving system, namely periodicity (or more precisely, almost periodicity) and mixing (or more precisely, weak mixing). Very roughly speaking, when there is periodicity, then we expect $T^n E$ to be close to $E$ for many $n\ ,$ whereas when we have mixing, we expect $T^n E$ to become "independent" of $E$ for large $n\ .$ The key insights are that periodicity and mixing can both be used to create recurrence, and that arbitrary measure-preserving systems can be decomposed into periodic and mixing components (the precise statement of this is now known as the Furstenberg structure theorem). For more details see [FKO], [F2]. Furstenberg's method led to a vast number of generalisations and other developments, some of which we will discuss below.

The Fourier-analytic method of Roth, which treated the $k=3$ case, was finally extended to the $k=4$ case by Gowers [Go] in 1998, and then to the general case by Gowers [Go2] in 2001. (An earlier argument of Roth [R2] combined Szemerédi's arguments with those in [R] to produce a hybrid proof of the $k=4$ case of Szemerédi's theorem.) Gowers realised that classical Fourier analysis, which relied on linear phases such as $e^{2\pi i n \theta}\ ,$ were suitable tools for detecting arithmetic progressions of length three, but already for progressions of length four one needed to work with a generalised notion of Fourier analysis, in which quadratic phases such as $e^{2\pi i n^2 \theta}$ made an appearance. (The reason for this is technical, but is related to the fact that a function $f: {\Bbb R} \to {\Bbb R}$ is linear, then its values on two points of an arithmetic progression can be extrapolated to evaluate the value on the third (i.e. two points determine a line). For quadratic $f\ ,$ this property is no longer true, however it remains true that the values on three points on an arithmetic progression can be extrapolated to evaluate the value on the fourth.) Gowers' proofs then proceeded by developing this generalised Fourier analysis and combining them with several innovative new tools, including what is now known as the Balog-Szemerédi-Gowers lemma which is now of fundamental importance in additive combinatorics and number theory. Gowers' argument also gave fairly reasonable quantitative bounds on quantities such as the van der Waerden number $W(k,r)\ .$ (Szemerédi's original argument used van der Waerden's theorem inside the proof, and so did not provide a better bound on that theorem; the argument of Furstenberg was infinitary and thus provided no explicit bound at all, although recently [T] it was shown that a quantitative bound could, in principle, be extracted from this type of argument.) Further variants and extensions of Gowers' argument were carried out more recently by Green and Tao [GT2], at least in the cases $k \leq 4\ .$

A fourth type of proof, based on the theory of graphs and hypergraphs, was introduced by Ruzsa and Szemerédi [RS] in 1978, who observed that Roth's theorem could in fact be deduced from a more abstract graph-theoretical result which is now known as the triangle removal lemma; this lemma asserts that if a graph $G$ on $n$ vertices contains at most $\varepsilon n^3$ triangles, then all of these triangles can be deleted at the cost of removing at most $c(\varepsilon) n^2$ edges, where $c(\varepsilon)$ is a quantity which goes to zero as $\varepsilon$ goes to zero. They then showed that this removal lemma followed easily from the regularity lemma introduced earlier by Szemerédi. It was then natural to generalize these observations to tackle the full strength of Szemerédi's theorem, but this required one to exchange the familiar setting of graphs to the more difficult setting of hypergraphs (in which each "edge" does not connect just two vertices, but can connect three or more vertices together). One of the key difficulties was to obtain a sufficiently strong analogue of the Szemerédi regularity lemma for hypergraphs. After some preliminary steps in this direction [C], [FR2], this program was completed by Gowers [Go3], [Go4] and by Nagle, Rődl, Schacht, and Skokan [NRS], [RSc], [RSk], [RSk2] in 2006. More recently, there have been further developments of the hypergraph regularity method, providing some slightly different reproofs of Szemerédi's theorem [T2], [T4], [I], [ES].

Very recently, it has been realised that these four approaches to proving Szemerédi's theorem are interrelated. For example, connections between the regularity lemma approach and the Fourier-analytic approach were uncovered in [Gr2], while connections between hypergraphs and ergodic theory were uncovered in [T4], and connections between the Fourier-analytic and ergodic approaches were uncovered in [GT2] and exploited systematically in [GT3]. The result in [GT] uses ideas and tools from all four methods.

Generalisations

Szemerédi's theorem has been generalised and strengthened in many different directions. The following list is only a representative sample of some of these.

Firstly, one can "bootstrap" Szemerédi's theorem to yield not just a single progression of length $k\ ,$ but in fact many such progressions. Indeed, an averaging argument of Varnavides [V] gives

Theorem (Varnavides' theorem) Let $k \geq 1$ and $0 < \delta < 1\ .$ Then there exists $N(k,\delta) > 0$ with the following property: if $n > N(k,\delta)\ ,$ then any subset $A$ of $\{1,\ldots,n\}$ of cardinality at least $\delta n$ will contain at least $n^2 / N(k,\delta)$ arithmetic progressions of length $k\ .$

Szemerédi's theorem can also be extended to multiple dimensions, asserting that any subset of a lattice of positive Banach density will contain arbitrarily shaped "constellations":

Theorem (Furstenberg-Katznelson theorem) [FK] Let $d \geq 1\ ,$ and let $A \subset {\Bbb Z}^d$ be a set of positive upper Banach density, thus $d^*(A) = \limsup_{N \to \infty} \#(A \cap [-N,N]^d) / (2N+1)^d > 0\ .$ Then for any $v_1,\ldots,v_k \in {\Bbb Z}^d\ ,$ there exist infinitely many $a \in {\Bbb Z}^d$ and positive integers $r$ such that $a+rv_1, \ldots, a+rv_k \in A\ .$

Note that Szemerédi's original theorem is the case when $d=1$ and $v_i=i-1$ for $1 \leq i \leq k\ .$

A significantly stronger (and more difficult) generalisation of this theorem replaces ${\Bbb Z}^d$ by an arbitrary set $F^d\ ,$ as follows:

Theorem (Density Hales-Jewett theorem) [FK3] Let $F \subset {\Bbb Z}$ and $0 < \delta < 1\ .$ If $d$ is sufficiently large depending on $\# F$ and $\delta\ ,$ then any subset $A$ of $F^d$ of cardinality at least $\delta (\# F)^d$ will contain at least one set of the form $\{ a + tr: t \in F \}$ where $a, r \in {\Bbb Z}^d$ with $r$ non-zero.

This significantly generalises the classical Hales-Jewett theorem [HJ]. There is an equivalent formulation of this theorem in which $F$ is an arbitrary finite set (not necessarily consisting of integers), and the set $\{ a + tr: t \in F \}$ is replaced by a combinatorial line, but we will not state this version here as it requires some further notation. We do however note that this theorem implies a version of Szemerédi's theorem for finite abelian groups:

Corollary Let $k \geq 1$ and $0 < \delta < 1\ .$ If $G$ is a finite group of sufficiently large order depending on $k$ and $\delta\ ,$ then for any subset $A$ of $G$ of cardinality $\# A \geq \delta \# G$ there exists $a, r \in G$ with $r$ non-zero such that $a, a+r, \ldots, a+(k-1) r \in A\ .$

The $k=3$ case of this corollary was established by Meshulam [Me].

In another direction, Bergelson and Leibman [BL] established an extension of the Furstenberg-Katznelson theorem for polynomials:

Theorem (Bergelson-Leibman theorem) [BL] Let $d \geq 1\ ,$ and let $A \subset {\Bbb Z}^d$ be a set of positive upper Banach density, thus $\limsup_{N \to \infty} \#(A \cap [-N,N]^d) / (2N+1)^d > 0\ .$ Then for any polynomials $P_1,\ldots,P_k: {\Bbb Z} \to {\Bbb Z}^d$ with $P_1(0)=\ldots=P_k(0) = 0\ ,$ there exist infinitely many $a \in {\Bbb Z}^d$ and positive integers $r$ such that $a+P_1(r),\ldots,a+P_k(r) \in A\ .$

This theorem can be extended in a rather technical manner involving measure-preserving shift operators which generate a nilpotent group. On the other hand, these results fail once the group generated by the shifts ceases to be nilpotent. See [L], [BL2].

Let $k$ and $A$ be as in Szemerédi's theorem. The set $R_k$ of all possible $r$ generated by that theorem has been studied by several authors (see [BHMP]). The arguments in [F] or [FKO] can be modified to yield the assertion that $R_k$ is syndetic, i.e. it has bounded gaps. In [FK2] it was shown that $R_k$ is an $IP^*$-set, which means that given any infinite set $B$ of positive integers, $R_k$ contains at least one element which can be expressed as the sum of distinct elements of $B\ .$

Now take $\varepsilon > 0\ ,$ and consider the set $R_{k,\varepsilon}$ of all $r$ such that $d^*( A \cap (A-r) \cap \ldots \cap (A-(k-1)r) ) > d^*(A)^k - \varepsilon\ .$ For $k \leq 4$ it is known that $R_{k,\varepsilon}$ is syndetic, but this claim breaks down for $k > 4\ ;$ see [BHK]. (The case $k=2$ is known as the Khintchine recurrence theorem.)

In a rather different direction, Szemerédi's theorem has been shown to follow from some general theorems in graph and hypergraph theory. For instance, the $k=3$ case of this theorem follows from the triangle removal lemma mentioned earlier. A typical result of this type is

Theorem (Hypergraph removal lemma) Let $G = (V,E)$ be a $k$-uniform hypergraph (i.e. each edge has exactly $k$ vertices), then for any $\delta > 0$ there exists an $\varepsilon > 0$ if $H = (W,F)$ is any $k$-uniform hypergraph which contains at most $\varepsilon (\# V)^{\# W}$ copies of $G\ ,$ then it is possible to delete at most $\delta (\# V)^k$ edges in $H$ to create a hypergraph with no copy of $G$ whatsoever.

For a proof see [Go4], [RSk2], [T2], [T4], [ES], or [I]. Several refinements of this theorem, with applications to property testing of hypergraphs, are currently being pursued.

Let $r_k(n)$ denote the size of the largest subset of $\{1,\ldots,n\}$ which does not contain any arithmetic progressions of length $n\ .$ The exact size of $r_k(n)$ is still unknown; Szemerédi's theorem asserts that $r_k(n) =o(n)$ for each $k\ .$ For $k=3\ ,$ the best known lower and upper bounds for $r_3(n)$ are \[\displaystyle n \exp(-C\sqrt{\log n}) \leq r_3(n) \leq C n \frac{(\log \log n)^{1/2}}{\sqrt{\log n}}\] for some absolute constant $C > 0\ ,$ due to Behrend [Be] and Bourgain [Bo] respectively. (In a recent unpublished paper, Bourgain has improved the upper bound to $C n \frac{(\log \log n)^2}{(\log n)^{2/3}}\ .$) For general $k\ ,$ the best known bounds are \[\displaystyle n \exp(-C\log^{1/(\lfloor \log_2(k-1) \rfloor+1)} n) \leq r_k(n) \leq n / (\log_2 \log_2 n)^{1/2^{k+9}}\] due to Rankin [Ran] and Gowers [Go2] respectively, though for $k=4$ the upper bound has been improved to $n \exp( -C \sqrt{\log \log n} )$ by Green and Tao [GT4].

Szemerédi's theorem asserts that dense subsets of the integers contain long arithmetic progressions. It turns out that one can replace the integers with certain other sets, most notably the set of primes, using a transference principle: see [Gr], [GT].

References

[Ba] L. Babai, Paul Erdös (1913-1996): his influence on the theory of computing, STOC '97 (El Paso, TX), 383-401, ACM, New York, 1999.
[Be] F. A. Behrend, On sets of integers which contain no three terms in arithmetic progression, Proc. Nat. Acad. Sci. 32 (1946), 331--332.
[BHK] V. Bergelson, B. Host and B. Kra, Multiple recurrence and nilsequences, Inventiones Math., 160, 2, (2005) 261-303.
[BHMP] V. Bergelson, B. Host, R. McCutcheon, F. Parreau, Aspects of uniformity in recurrence, Colloq. Math. 85 (2000), 549--576.
[BL] V. Bergelson and A. Leibman, Polynomial extensions of van der Waerden's and Szemerédi's theorems, J. Amer. Math. Soc. 9 (1996), 725--753.
[BL2] V. Bergelson, A. Leibman, Failure of Roth theorem for solvable groups of exponential growth, Ergodic Theory and Dynam. Systems 24 (2004), 45--53.
[Bo] J. Bourgain, On triples in arithmetic progression, GAFA 9 (1999), 968--984.
[C] F. Chung, Regularity lemmas for hypergraphs and quasi-randomness, Random Struct. Alg. 2 (1991), 241--252.
[ES] G. Elek, B. Szegedy, Limits of Hypergraphs, Removal and Regularity Lemmas. A Non-standard Approach, preprint.
[ET] P. Erdős, P. Turán, On some sequences of integers, J. London Math. Soc. 11 (1936), 261--264.
[FR] P. Frankl, V. Rődl, Hypergraphs do not jump, Combinatorica 4 (1984), no. 2-3, 149--159.
[FR2] P. Frankl, V. Rődl, The uniformity lemma for hypergraphs, Graphs Combinat. 8 (4) (1992), 309--312.
[FR3] P. Frankl, V. Rődl, Extremal problems on set systems, Random Struct. Algorithms 20 (2002), no. 2, 131-164.
[F] H. Furstenberg, Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions, J. Analyse Math. 31 (1977), 204-256.
[F2] H. Furstenberg, Recurrence in Ergodic theory and Combinatorial Number Theory, Princeton University Press, Princeton NJ 1981.
[FK] H. Furstenberg, Y. Katznelson, An ergodic Szemerédi theorem for commuting transformations, J. Analyse Math. 34 (1978), 275-291.
[FK2] H. Furstenberg, Y. Katznelson, An ergodic Szemerédi theorem for IP-systems and combinatorial theory, J. d'Analyse Math. 45 (1985), 117-168.
[FK3] H. Furstenberg, Y. Katznelson, A density version of the Hales-Jewett theorem, J. d'Analyse Math., 57 (1991), 64-119.
[FKO] H. Furstenberg, Y. Katznelson and D. Ornstein, The ergodic-theoretical proof of Szemerédi's theorem, Bull. Amer. Math. Soc. 7 (1982), 527-552.
[Go] T. Gowers, A new proof of Szemerédi's theorem for arithmetic progressions of length four, Geom. Func. Anal. 8 (1998), 529-551.
[Go2] T. Gowers, A new proof of Szemerédi's theorem, Geom. Func. Anal. 11 (2001), 465-588.
[Go3] T. Gowers, Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs, Combin. Probab. Comput. 15 (2006), no. 1-2, 143-184.
[Go4] T. Gowers, Hypergraph regularity and the multidimensional Szemerédi theorem, preprint.
[Gr] B. Green, Roth's theorem in the primes, Annals of Math, 161 (2005), no. 3, 1609-1636.
[Gr2] B. Green, A Szemerédi-type regularity lemma in abelian groups,} Geom. Func. Anal. 15 (2005), no. 2, 340-376.
[Gr3] B. Green, Montréal lecture notes on quadratic Fourier analysis, preprint.
[GT] B. Green and T. Tao, The primes contain arbitrarily long arithmetic progressions, preprint.
[GT2] B. Green, T. Tao, An inverse theorem for the Gowers $U^3(G)$ norm, preprint.
[GT3] B. Green, T. Tao, Linear equations in primes, preprint.
[GT4] B. Green, T. Tao, New bounds for Szemerédi's theorem, II: A new bound for $r_4(N)$, preprint.
[HJ] A.W. Hales, R.I. Jewett, Regularity and positional games, Trans. Amer. Math. Soc. 106 (1963), 222-229.
[HK] B. Host, B. Kra, Nonconventional ergodic averages and nilmanifolds, Annals of Math. 161, 1 (2005) 397-488.
[I] Y. Ishigami, A Simple Regularization of Hypergraphs, preprint.
[KLR] Y. Kohayakawa, T. Luczsak, V. Rődl, Arithmetic progressions of length three in subsets of a random set, Acta Arith. 75 (1996), no. 2, 133-163.
[KS] J. Komlòs, M. Simonovits, Szemerédi's regularity lemma and its applications in graph theory, Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), 295-352, Bolyai Soc. Math. Stud., 2, Jànos Bolyai Math. Soc., Budapest, 1996.
[K] B. Kra, Ergodic methods in additive combinatorics, preprint.
[L] A. Leibman, Multiple recurrence theorem for nilpotent group actions, Geom. and Func. Anal. 4 (1994), 648-659.
[LS] L. Lovász, B. Szegedy, Szemerédi's lemma for the analyst, preprint.
[Me] R. Meshulam, On subsets of finite abelian groups with no 3-term arithmetic progressions, J. Combin. Theory Ser. A. 71 (1995), 168-172.
[M] L. Moser, On non-averaging sets of integers, Canadian J. Math. 5 (1953), 245-252.
[NRS] B. Nagle, V. Rődl, M. Schacht, The counting lemma for regular $k$-uniform hypergraphs, Random Structures and Algorithms, 2006, vol. 28, no. 22, 113 - 179.
[Ram] F.P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. 30 (1930), 264-285.
[Ran] R.A. Rankin, Sets not containing more than a given number of terms in arithmetical progression, Proc. Roy. Soc. Edinburgh Sect. A 65 (1960), 332-344.
[RSc] V. Rődl, M. Schacht, Regular partitions of hypergraphs, preprint.
[RSk] V. Rődl, J. Skokan, Regularity lemma for uniform hypergraphs, Random Structures and Algorithms, 2004, vol. 25, no. 1, 1-42.
[RSk2] V. Rődl, J. Skokan, Applications of the regularity lemma for uniform hypergraphs, Random Structures and Algorithms, 2006, vol. 28, no. 2, 180-194.
[R] K.F. Roth, On certain sets of integers, J. London Math. Soc. 28 (1953), 245-252.
[R2] K.F. Roth, Irregularities of sequences relative to arithmetic progressions, IV. Period. Math. Hungar. 2 (1972), 301-326.
[RS] I. Ruzsa, E. Szemerédi, Triple systems with no six points carrying three triangles, Colloq. Math. Soc. J. Bolyai, 18 (1978), 939-945.
[SS] R. Salem, D. Spencer, On sets of integers which contain no three in arithmetic progression, Proc. Nat. Acad. Sci. (USA) 28 (1942), 561-563.
[Sh] S. Shelah, Primitive recursive bounds for van der Waerden numbers, J. Amer. Math. Soc. 1 (1988), 683-697.
[Sz] E. Szemerédi, On sets of integers containing no four elements in arithmetic progression, Acta Math. Acad. Sci. Hungar. 20 (1969), 89-104.
[Sz2] E. Szemerédi, On sets of integers containing no $k$ elements in arithmetic progression, Acta Arith. 27 (1975), 299-345.
[T] T. Tao, A quantitative ergodic theory proof of Szemerédi's theorem, preprint.
[T2] T. Tao, A variant of the hypergraph removal lemma, J. Combin. Thy. A 113 (2006), 1257-1280.
[T3] T. Tao, Szemerédi's regularity lemma revisited, Contrib. Discrete Math. 1 (2006), 8-28.
[T4] T. Tao, A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal lemma, preprint.
[T5] T. Tao, The ergodic and combinatorial approaches to Szemerédi's theorem, preprint.
[T6] T. Tao, Norm convergence of multiple ergodic averages for commuting transformations, preprint.
[TV] T. Tao, V. Vu, Additive combinatorics, Cambridge University Press, Cambridge 2006.
[vdW] B. L. van der Waerden, Beweis einer Baudetschen Vermutung, {Nieuw. Arch. Wisk.} 15 (1927), 212-216.
[V] P. Varnavides, On certain sets of positive density, J. London Math. Soc. 34 (1959) 358-360.
[Z] T. Ziegler, Universal characteristic factors and Furstenberg averages, J. Amer. Math. Soc. 20 (2007), 53-97.
[Z2] T. Ziegler, A non-conventional ergodic theorem for a nilsystem, Ergodic Theory Dynam. Systems 25 (2005), 1357-1370.

Internal references

Jan A. Sanders (2006) Averaging. Scholarpedia, 1(11):1760.
Olaf Sporns (2007) Complexity. Scholarpedia, 2(10):1623.
James Meiss (2007) Dynamical systems. Scholarpedia, 2(2):1629.

Szemerédi's Theorem

Contents

History

Generalisations

References

Further reading

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

Focal areas

Activity

Tools