Szemerédi's theorem

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.

Contents 1 Statement 2 History 3 Quantitative bounds 4 Extensions and generalizations 5 See also 6 Notes 7 Further reading 8 External links Statement A subset A of the natural numbers is said to have positive upper density if {displaystyle limsup _{nto infty }{frac {|Acap {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 rk(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, rk(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 rk(N). The best known general bounds are {displaystyle CNexp left(-n2^{(n-1)/2}{sqrt[{n}]{log N}}+{frac {1}{2n}}log log Nright)leq r_{k}(N)leq {frac {N}{(log log N)^{2^{-2^{k+9}}}}},} where {displaystyle n=lceil log krceil } . 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 {8log 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 Asubset 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,nin mathbb {Z} } such that {displaystyle u+p_{i}(n)in A} for all {displaystyle 1leq ileq 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.