Szemerédi's theorem

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.

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]

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] Sanders,[20] and Bloom[21] established progressively smaller upper bounds, and Bloom and Sisask then proved the first bound that broke the so-called ``logarithmic barrier".[22] The current best bounds are

${\displaystyle N2^{-{\sqrt {8\log N}}}\leq r_{3}(N)\leq Ne^{-c(\log N)^{1/11}}}$, for some constant ${\displaystyle c>0}$,

due to O'Bryant,[11] and Kelley and Meka[23] respectively.

For k = 4, Green and Tao[24][25] proved that

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

for some c > 0.

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

Alexander Leibman and Vitaly Bergelson[32] 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.[33] The finite field analog can be used as a model for understanding the theorem in the natural numbers.[34] 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.[35][36]

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

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

• 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.

• 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.