Szemerédi's theorem

Template:Short description 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<ref name="erdos turan">Template:Cite journal</ref> 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.

StatementEdit

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

<math>\limsup_{n \to \infty}\frac{|A\cap \{1, 2, 3, \dotsc, n\}|}{n} > 0.</math>

Szemerédi's theorem asserts that a subset of the natural numbers with positive upper density contains an arithmetic progression 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 <math>\delta \in (0, 1]</math>, there exists a positive integer

<math>N = N(k,\delta)</math>

such that every subset of {1, 2, ..., N} of size at least <math>\delta N</math> 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

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

HistoryEdit

Van der Waerden's theorem, a precursor of Szemerédi's theorem, was proved 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<ref>Template:Cite journal</ref> via an adaptation of the Hardy–Littlewood circle method. Szemerédi<ref>Template:Cite journal</ref> next proved the case k = 4 through combinatorics. Using an approach similar to the one he used for the case k = 3, Roth<ref>Template:Cite journal</ref> gave a second proof for k = 4 in 1972.

The general case was settled in 1975, also by Szemerédi,<ref>Template:Cite journal</ref> who developed an ingenious and complicated extension of his previous combinatorial argument for k = 4 (called "a masterpiece of combinatorial reasoning" by Erdős<ref>Template:Cite encyclopedia</ref>). Several other proofs are now known, the most important being those by Hillel Furstenberg<ref>Template:Cite journal.</ref><ref>Template:Cite journal</ref> in 1977, using ergodic theory, and by Timothy Gowers<ref name="gowers">Template:Cite journal</ref> in 2001, using both Fourier analysis and combinatorics while also introducing what is now called the Gowers norm. Terence Tao has called the various proofs of Szemerédi's theorem a "Rosetta stone" for connecting disparate fields of mathematics.<ref>Template:Cite encyclopedia</ref>

Quantitative boundsEdit

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

<math>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}}}},</math>

where <math>n = \lceil \log k\rceil</math>. The lower bound is due to O'Bryant<ref name="obryant">Template:Cite journal</ref> building on the work of Behrend,<ref>Template:Cite journal</ref> Rankin,<ref>Template:Cite journal</ref> and Elkin.<ref>Template:Cite journal</ref><ref>Template:Cite encyclopedia</ref> The upper bound is due to Gowers.<ref name="gowers"/>

For small k, there are tighter bounds than the general case. When k = 3, Bourgain,<ref>Template:Cite journal</ref><ref>Template:Cite journal</ref> Heath-Brown,<ref>Template:Cite journal</ref> Szemerédi,<ref>Template:Cite journal</ref> Sanders,<ref>Template:Cite journal</ref> and Bloom<ref>Template:Cite journal</ref> established progressively smaller upper bounds, and Bloom and Sisask then proved the first bound that broke the so-called "logarithmic barrier".<ref>Template:Cite arXiv</ref> The current best bounds are

<math> N 2^{-\sqrt{8\log N}} \leq r_3(N) \leq N e^{-c(\log N)^{1/9}} </math>, for some constant <math>c>0 </math>,

respectively due to O'Bryant,<ref name="obryant"/> and Bloom and Sisask<ref>Template:Cite arXiv</ref> (the latter built upon the breakthrough result of Kelley and Meka,<ref>Template:Cite arXiv</ref> who obtained the same upper bound, with "1/9" replaced by "1/12").

For k = 4, Green and Tao<ref>Template:Cite encyclopedia</ref><ref>Template:Cite journal</ref> proved that

For k=5 in 2023 and k≥5 in 2024 Leng, Sah and Sawhney proved in preprints <ref>Template:Cite arXiv</ref><ref>Template:Cite arXiv</ref><ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> that:

Extensions and generalizationsEdit

A multidimensional generalization of Szemerédi's theorem was first proven by Hillel Furstenberg and Yitzhak Katznelson using ergodic theory.<ref>Template:Cite journal</ref> Timothy Gowers,<ref>Template:Cite journal</ref> Vojtěch Rödl and Jozef Skokan<ref>Template:Cite journal</ref><ref>Template:Cite journal</ref> with Brendan Nagle, Rödl, and Mathias Schacht,<ref>Template:Cite journal</ref> and Terence Tao<ref>Template:Cite journal</ref> provided combinatorial proofs.

Alexander Leibman and Vitaly Bergelson<ref>Template:Cite journal</ref> generalized Szemerédi's to polynomial progressions: If <math>A \subset \mathbb{N}</math> is a set with positive upper density and <math>p_1(n),p_2(n),\dotsc,p_k(n)</math> are integer-valued polynomials such that <math>p_i(0) = 0</math>, then there are infinitely many <math>u, n \in \mathbb{Z}</math> such that <math>u + p_i(n) \in A</math> for all <math>1 \leq i \leq k</math>. 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.<ref>Template:Cite journal</ref> The finite field analog can be used as a model for understanding the theorem in the natural numbers.<ref>Template:Cite journal</ref> The problem of obtaining bounds in the k=3 case of Szemerédi's theorem in the vector space <math>\mathbb{F}_3^n</math> is known as the cap set problem.

The Green–Tao theorem asserts the prime numbers contain arbitrarily 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.<ref>Template:Cite journal</ref><ref>Template:Cite journal</ref>

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