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