The corners theorem
ProvedFamousTheorems.corners_theoremThe corners theorem. For every and all sufficiently large , every set with contains a corner, three points with .
Due to Ajtai and Szemerédi, it is a two-dimensional density Ramsey theorem. It implies Roth's theorem on three-term arithmetic progressions, and its proof via the triangle removal lemma is a model argument of additive combinatorics.
Formalization note. Mathlib's corners_theorem_nat. The threshold cornersTheoremBound (ε / 9) comes from the triangle removal lemma, and IsCornerFree expresses the absence of nontrivial corners.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem corners_theorem {n : ℕ} {ε : ℝ} (hε : 0 < ε) (hn : cornersTheoremBound (ε / 9) ≤ n) (A : Finset (ℕ × ℕ))
(hAn : A ⊆ Finset.range n ×ˢ Finset.range n) (hAε : ε * n ^ 2 ≤ A.card) :
¬ IsCornerFree (A : Set (ℕ × ℕ)) := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `corners_theorem_nat`. Proof here reduces to that Mathlib result.