Any set of integers with positive upper density contains arbitrarily long arithmetic progressions. Proved by Endre Szemeredi, it generalizes the earlier Van der Waerden and Erdos-Turan results and underlies the later Green-Tao theorem.
Facts
StatementA subset of the natural numbers with positive upper density contains an arithmetic progression of length k for every positive integer k. 1 Classification
Statement Form Szemeredi's Theorem
Filter Results1 entry
Connections
Has Statement Form
In Branch
Principal Result Of
Source Endre Szemerédi (Wikipedia)
Source Timothy Gowers (Wikipedia)
Proved By
Source Szemeredi's Theorem (Wikipedia)
Sources
1. Szemeredi's Theorem (Wikipedia)
Wikimedia FoundationStatement section, first sentence
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.
lead paragraph, third sentence
Endre Szemerédi proved the conjecture in 1975.
Proved By: Endre Szemerédi, Lead
Endre Szemerédi proved the conjecture in 1975.
View the Source Endre Szemerédi (Wikipedia)
Principal Result Of: Endre Szemerédi, Article textQuote, Principal Result Of: Endre Szemerédi, Article text
He has made a number of discoveries in combinatorics and computer science, including Szemerédi's theorem, the Szemerédi regularity lemma, the Erdős-Szemerédi theorem, the Hajnal-Szemerédi theorem and the Szemerédi-Trotter theorem.
Timothy Gowers (Wikipedia)
Principal Result Of: Timothy Gowers, Career and researchQuote, Principal Result Of: Timothy Gowers, Career and research
Gowers proved the first effective bounds for Szemerédi's theorem
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.