Szemerédi's theorem (positive upper density)
ProvedErdos3.szemeredi_positive_upper_densitySzemerédi's theorem. If has positive upper density,
then contains arithmetic progressions of every finite length. Conjectured by Erdős and Turán (1936), proved by Roth for (1953) and by Szemerédi in general (1975). A set of positive upper density has divergent reciprocal sum, so this is the density case of the goal.
import Mathlib import Definitions.Def_Erdos142Basic
namespace Erdos3
open Erdos142
theorem szemeredi_positive_upper_density (A : Set ℕ)
(hA : ∃ δ : ℝ, 0 < δ ∧ ∃ᶠ N : ℕ in Filter.atTop, δ * N ≤ ((A ∩ Set.Iio N).ncard : ℝ)) :
∀ k : ℕ, ∃ S ⊆ A, IsAPOfLength S k := by
sorry
end Erdos3Read-back
What the Lean code literally says, in plain math · Aristotle (Harmonic) — same agent that drafted the statement; NOT an independent auditor
Non-blind read-back. This read-back was written by the same agent that drafted the Lean statement, with full knowledge of the source and of the intended meaning. It is not blind, independent auditor testimony and must not be treated as such; it was produced this way on the explicit instruction of the proposal owner. Reviewers should compare it against the Lean code themselves.
Statement. Let be any set. Assume there is a real such that for infinitely many natural numbers ,
where is the number of elements (the set is finite, so this is its true size). Then for every natural number there is a subset that is an arithmetic progression of length .
Definitions used (from the imported definition file Erdos142Basic). For a set of natural numbers and , is an arithmetic progression of length means: there exist natural numbers such that has exactly elements (cardinality taken in ) and
The cardinality condition forces as soon as (with the set is the singleton ). Length is satisfied only by , length by any singleton.
Remarks. The hypothesis is equivalent to having positive upper density. It is satisfiable (e.g. with ). The cases of the conclusion are trivial (, or a singleton, which exists since the hypothesis forces ).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.