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 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.
A subset A of the natural numbers is said to have positive upper density if
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 , there exists a positive integer
![\delta \in (0,1]](https://wikimedia.org/api/rest_v1/media/math/render/svg/d0590fccb82a0ae667ed13dd0bbf0dff27ff2d9c)
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
That is, rk(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 was established in 1953 by Klaus Roth via an adaptation of the Hardy–Littlewood circle method. Endre Szemerédi proved the case k = 4 through combinatorics. Using an approach similar to the one he used for the case k = 3, Roth gave a second proof for this in 1972.
...
Wikipedia