Szemerédi's theorem
Encyclopedia
In number theory
, Szemerédi's theorem is a result that was formerly the Erdős–Turán conjecture (not to be confused with Erdős–Turán conjecture on additive bases
). In 1936 Erdős
and Turán conjectured for every value d called density 0 < d < 1 and every integer k there is a number N(d, k) such that every subset A of {1, ..., N} of cardinality dN contains a length-k arithmetic progression
, provided N > N(d, k).
This generalizes the statement of van der Waerden's theorem.
The cases k = 1 and k = 2 are trivial. The case k = 3 was established in 1956 by Klaus Roth
by an adaptation of the Hardy–Littlewood circle method. The case k = 4 was established in 1969 by Endre Szemerédi
by a combinatorial method. Using an approach similar to the one he used for the case k = 3, Roth gave a second proof for this in 1972.
Finally, the case of general k was settled in 1975, also by Szemerédi, by an ingenious and complicated extension of the previous combinatorial argument ("a masterpiece of combinatorial reasoning", R. L. Graham
). Several further proofs are now known, the most important amongst them being those by Hillel Furstenberg in 1977, using ergodic theory
, and by Timothy Gowers in 2001, using both Fourier analysis and combinatorics
.
Let k be a positive integer and let 0 < δ ≤ 1/2. A finitary
version of the theorem states that there exists a positive integer
such that every subset of {1, 2, ..., N} of size at least δN contains an arithmetic progression of length k.
The best known bounds for N(k, δ) are
with C > 1. The lower bound is due to Behrend (for k = 3) and Rankin
, and the upper bound is due to Gowers.
When k = 3 better upper bounds are known; the best known is
due to Bourgain
.
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
, Szemerédi's theorem is a result that was formerly the Erdős–Turán conjecture (not to be confused with Erdős–Turán conjecture on additive bases
Erdős–Turán conjecture on additive bases
The Erdős–Turán conjecture is an old unsolved problem in additive number theory posed by Paul Erdős and Pál Turán in 1941.-History:...
). In 1936 Erdős
Paul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
and Turán conjectured for every value d called density 0 < d < 1 and every integer k there is a number N(d, k) such that every subset A of {1, ..., N} of cardinality dN contains a length-k arithmetic progression
Arithmetic progression
In mathematics, an arithmetic progression or arithmetic sequence is a sequence of numbers such that the difference between the consecutive terms is constant...
, provided N > N(d, k).
This generalizes the statement of van der Waerden's theorem.
The cases k = 1 and k = 2 are trivial. The case k = 3 was established in 1956 by Klaus Roth
Klaus Roth
Klaus Friedrich Roth is a British mathematician known for work on diophantine approximation, the large sieve, and irregularities of distribution. He was born in Breslau, Prussia, but raised and educated in the UK. He graduated from Peterhouse, Cambridge in 1945...
by an adaptation of the Hardy–Littlewood circle method. The case k = 4 was established in 1969 by Endre Szemerédi
Endre Szemerédi
Endre Szemerédi is a Hungarian mathematician, working in the field of combinatorics and theoretical computer science. He is the State of New Jersey Professor of computer science at Rutgers University since 1986...
by a combinatorial method. Using an approach similar to the one he used for the case k = 3, Roth gave a second proof for this in 1972.
Finally, the case of general k was settled in 1975, also by Szemerédi, by an ingenious and complicated extension of the previous combinatorial argument ("a masterpiece of combinatorial reasoning", R. L. Graham
Ronald Graham
Ronald Lewis Graham is a mathematician credited by the American Mathematical Society as being "one of the principal architects of the rapid development worldwide of discrete mathematics in recent years"...
). Several further proofs are now known, the most important amongst them being those by Hillel Furstenberg in 1977, using ergodic theory
Ergodic theory
Ergodic theory is a branch of mathematics that studies dynamical systems with an invariant measure and related problems. Its initial development was motivated by problems of statistical physics....
, and by Timothy Gowers in 2001, using both Fourier analysis and combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
.
Let k be a positive integer and let 0 < δ ≤ 1/2. A finitary
Finitary
In mathematics or logic, a finitary operation is one, like those of arithmetic, that takes a finite number of input values to produce an output. An operation such as taking an integral of a function, in calculus, is defined in such a way as to depend on all the values of the function , and is so...
version of the theorem states that there exists a positive integer
such that every subset of {1, 2, ..., N} of size at least δN contains an arithmetic progression of length k.
The best known bounds for N(k, δ) are
with C > 1. The lower bound is due to Behrend (for k = 3) and Rankin
Robert Alexander Rankin
Robert Alexander Rankin was a Scottish mathematician who worked in analytic number theory.Rankin's father, the Revd Oliver Shaw Rankin, was a minister who later became Professor of Old Testament Language, Literature and Theology in the University of Edinburgh.Rankin was born in Garlieston,...
, and the upper bound is due to Gowers.
When k = 3 better upper bounds are known; the best known is
due to Bourgain
Jean Bourgain
Jean Bourgain is a Belgian mathematician. He has been a faculty member at the University of Illinois, Urbana-Champaign and, from 1985 until 1995, professor at Institut des Hautes Études Scientifiques at Bures-sur-Yvette in France, and since 1994 at the Institute for Advanced Study in Princeton,...
.
See also
- Problems involving arithmetic progressionsProblems involving arithmetic progressionsProblems involving arithmetic progressions are of interest in number theory, combinatorics, and computer science, both from theoretical and applied points of view.-Largest progression-free subsets:...
- Ergodic Ramsey theoryErgodic Ramsey theoryErgodic Ramsey theory is a branch of mathematics where problems motivated by additive combinatorics are proven using ergodic theory.Ergodic Ramsey theory arose shortly after Endre Szemerédi's proof that a set of positive upper density contains arbitrarily long arithmetic progressions, when Hillel...
- Arithmetic combinatoricsArithmetic combinatoricsArithmetic combinatorics arose out of the interplay between number theory, combinatorics, ergodic theory and harmonic analysis. It is about combinatorial estimates associated with arithmetic operations...
- Szemerédi regularity lemmaSzemerédi regularity lemmaIn mathematics, the Szemerédi regularity lemma states that every large enough graph can be divided into subsets of about the same size so that the edges between different subsets behave almost randomly. introduced a weaker version of this lemma, restricted to bipartite graphs, in order to prove ...
- Green–Tao theorem
External links
- PlanetMath source for initial version of this page
- Announcement by Ben Green and Terence Tao – the preprint is available at math.NT/0404188
- Discussion of Szemerédi's theorem (part 1 of 5)
- Ben Green and Terence Tao: Szemerédi's theorem on ScholarpediaScholarpediaScholarpedia is an English-language online wiki-based encyclopedia that uses the same MediaWiki software as Wikipedia, but has features more commonly associated with open-access online academic journals....