Roth's theorem on 3-term arithmetic progressions
ProvedFamousTheorems.roth_theorem_3apRoth's theorem. For every there is such that for all , every set with contains a nontrivial three-term arithmetic progression with .
Equivalently, sets of natural numbers without 3-term progressions have density zero. This is the case of Szemerédi's theorem. Roth proved it by Fourier analysis in 1953, and it has driven major developments in additive combinatorics, including the Kelley–Meka bounds.
Formalization note. Derived from Mathlib's roth_3ap_theorem_nat, which obtains Roth's theorem from the corners theorem with cornersTheoremBound (ε / 3). ThreeAPFree A means contains no with other than .
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem roth_theorem_3ap (ε : ℝ) (hε : 0 < ε) :
∃ N : ℕ, ∀ n ≥ N, ∀ A : Finset ℕ, A ⊆ Finset.range n → ε * n ≤ A.card → ¬ ThreeAPFree (A : Set ℕ) := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `roth_3ap_theorem_nat`. Proof here reduces to that Mathlib result.