Szemerédi's theorem

In arithmetic combinatorics, Szemerédi's theorem is a result concerning arithmetic progressions in subsets of the integers. In 1936, Erdős and Turán conjectured^[1] that every set of integers A with positive natural density contains a k-term arithmetic progression for every k. Endre Szemerédi proved the conjecture in 1975.

Statement[]

A subset A of the natural numbers is said to have positive upper density if

${\displaystyle \limsup _{n\to \infty }{\frac {|A\cap \{1,2,3,\dotsc ,n\}|}{n}}>0}$.

Szemerédi's theorem asserts that a subset of the natural numbers with positive upper density contains infinitely many arithmetic progressions of length k for all positive integers k.

An often-used equivalent finitary version of the theorem states that for every positive integer k and real number ${\displaystyle \delta \in (0,1]}$, there exists a positive integer

${\displaystyle N=N(k,\delta )}$

such that every subset of {1, 2, ..., N} of size at least δN contains an arithmetic progression of length k.

Another formulation uses the function r_k(N), the size of the largest subset of {1, 2, ..., N} without an arithmetic progression of length k. Szemerédi's theorem is equivalent to the asymptotic bound

${\displaystyle r_{k}(N)=o(N)}$.

That is, r_k(N) grows less than linearly with N.

History[]

Van der Waerden's theorem, a precursor of Szemerédi's theorem, was proven in 1927.

The cases k = 1 and k = 2 of Szemerédi's theorem are trivial. The case k = 3, known as Roth's theorem, was established in 1953 by Klaus Roth^[2] via an adaptation of the Hardy–Littlewood circle method. Endre Szemerédi^[3] proved the case k = 4 through combinatorics. Using an approach similar to the one he used for the case k = 3, Roth^[4] gave a second proof for this in 1972.

The general case was settled in 1975, also by Szemerédi,^[5] who developed an ingenious and complicated extension of his previous combinatorial argument for k = 4 (called "a masterpiece of combinatorial reasoning" by Erdős^[6]). Several other proofs are now known, the most important being those by Hillel Furstenberg^[7][8] in 1977, using ergodic theory, and by Timothy Gowers^[9] in 2001, using both Fourier analysis and combinatorics. Terence Tao has called the various proofs of Szemerédi's theorem a "Rosetta stone" for connecting disparate fields of mathematics.^[10]

Quantitative bounds[]

It is an open problem to determine the exact growth rate of r_k(N). The best known general bounds are

${\displaystyle CN\exp \left(-n2^{(n-1)/2}{\sqrt[{n}]{\log N}}+{\frac {1}{2n}}\log \log N\right)\leq r_{k}(N)\leq {\frac {N}{(\log \log N)^{2^{-2^{k+9}}}}},}$

where ${\displaystyle n=\lceil \log k\rceil }$. The lower bound is due to O'Bryant^[11] building on the work of Behrend,^[12] Rankin,^[13] and Elkin.^[14][15] The upper bound is due to Gowers.^[9]

For small k, there are tighter bounds than the general case. When k = 3, Bourgain,^[16][17] Heath-Brown,^[18] Szemerédi,^[19] and Sanders^[20] provided increasingly smaller upper bounds. The current best bounds are

${\displaystyle N2^{-{\sqrt {8\log N}}}\leq r_{3}(N)\leq C{\frac {(\log \log N)^{4}}{\log N}}N}$

due to O'Bryant^[11] and Bloom^[21] respectively.

For k = 4, Green and Tao^[22][23] proved that

${\displaystyle r_{4}(N)\leq C{\frac {N}{(\log N)^{c}}}}$

for some c > 0.

Extensions and generalizations[]

A multidimensional generalization of Szemerédi's theorem was first proven by Hillel Furstenberg and Yitzhak Katznelson using ergodic theory.^[24] Timothy Gowers,^[25] Vojtěch Rödl and Jozef Skokan^[26][27] with Brendan Nagle, Rödl, and Mathias Schacht,^[28] and Terence Tao^[29] provided combinatorial proofs.

Alexander Leibman and Vitaly Bergelson^[30] generalized Szemerédi's to polynomial progressions: If ${\displaystyle A\subset \mathbb {N} }$ is a set with positive upper density and ${\displaystyle p_{1}(n),p_{2}(n),\dotsc ,p_{k}(n)}$ are integer-valued polynomials such that ${\displaystyle p_{i}(0)=0}$, then there are infinitely many ${\displaystyle u,n\in \mathbb {Z} }$ such that ${\displaystyle u+p_{i}(n)\in A}$ for all ${\displaystyle 1\leq i\leq k}$. Leibman and Bergelson's result also holds in a multidimensional setting.

The finitary version of Szemerédi's theorem can be generalized to finite additive groups including vector spaces over finite fields.^[31] The finite field analog can be used as a model for understanding the theorem in the natural numbers.^[32] The problem of obtaining bounds in the k=3 case of Szemerédi's theorem in the vector space ${\displaystyle \mathbb {F} _{3}^{n}}$ is known as the cap set problem.

The Green–Tao theorem asserts the prime numbers contain arbitrary long arithmetic progressions. It is not implied by Szemerédi's theorem because the primes have density 0 in the natural numbers. As part of their proof, Ben Green and Tao introduced a "relative" Szemerédi theorem which applies to subsets of the integers (even those with 0 density) satisfying certain pseudorandomness conditions. A more general relative Szemerédi theorem has since been given by David Conlon, Jacob Fox, and Yufei Zhao.^[33][34]

The Erdős conjecture on arithmetic progressions would imply both Szemerédi's theorem and the Green–Tao theorem.

See also[]

• Problems involving arithmetic progressions
• Ergodic Ramsey theory
• Arithmetic combinatorics
• Szemerédi regularity lemma

Notes[]

Further reading[]

• Tao, Terence (2007). "The ergodic and combinatorial approaches to Szemerédi's theorem". In Granville, Andrew; Nathanson, Melvyn B.; Solymosi, József (eds.). Additive Combinatorics. CRM Proceedings & Lecture Notes. Vol. 43. Providence, RI: American Mathematical Society. pp. 145–193. arXiv:math/0604456. Bibcode:2006math......4456T. ISBN 978-0-8218-4351-2. MR 2359471. Zbl 1159.11005.

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 Scholarpedia
• Weisstein, Eric W. "SzemeredisTheorem". MathWorld.
• Grime, James; Hodge, David (2012). "6,000,000: Endre Szemerédi wins the Abel Prize". Numberphile. Brady Haran.