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 That is, rk(N) grows less than linearly with N. Van der Waerden's theorem, a precursor of Szemerédi's theorem, was proved in 1927.
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]).
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 rk(N).
The lower bound is due to O'Bryant[11] building on the work of Behrend,[12] Rankin,[13] and Elkin.
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".
For k = 4, Green and Tao[25][26] proved that For k=5 in 2023 and k≥5 in 2024 Leng, Sah and Sawhney proved in preprints [27][28][29] that: A multidimensional generalization of Szemerédi's theorem was first proven by Hillel Furstenberg and Yitzhak Katznelson using ergodic theory.
Alexander Leibman and Vitaly Bergelson[36] generalized Szemerédi's to polynomial progressions: If
[37] The finite field analog can be used as a model for understanding the theorem in the natural numbers.
[38] The problem of obtaining bounds in the k=3 case of Szemerédi's theorem in the vector space
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.