Large -sparse sets with a bound uniform in
ProvedBehrendWindows.exists_large_atMostTwoPerAPThere is a constant such that for all natural numbers and there is a set of integers which is -sparse (no -term arithmetic progression with non-zero common difference contains three elements of ) and satisfies
For this is Behrend's theorem on sets without three-term progressions. The constant is quantified before and : one constant must serve every range and every progression length. The value of is left open, so the statement survives any improvement of the constant.
Formalization Note Lean's convention makes and harmless, and for the sparseness condition is vacuous, so the statement carries no hypotheses on or .
import Mathlib import Definitions.Def_BehrendWindows_AtMostTwoPerAP
namespace BehrendWindows
theorem exists_large_atMostTwoPerAP :
∃ C : ℝ, 0 < C ∧ ∀ N m : ℕ, ∃ T : Finset ℤ,
T ⊆ Finset.Ico (0 : ℤ) N ∧ AtMostTwoPerAP T m ∧
(N : ℝ) * Real.exp (-C * Real.sqrt (Real.log N * Real.log m)) ≤ (T.card : ℝ) := by sorry
end BehrendWindows
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Statement. There is a real constant such that, for all natural numbers and , there is a finite set with the following three properties.
- , the integer interval ; this is empty when .
- holds. That is, for all with and all , the integers , , are not all in .
- Its size satisfies
where is the natural logarithm and the inequality is in .
Scope. The constant is chosen once and must work for every pair . No hypothesis relates and , so may be smaller or larger than , and are included.
Edge cases. These follow from the total-function conventions used here: , , and the square root of a negative number is . Since and are natural numbers, and , so the expression under the square root is never negative.
- : the left side is , and satisfies the statement.
- : , so the bound reads , and is required.
- : , so the bound reads , forcing . Condition 2 is vacuous in this case.
- : the bound is , and condition 2 is vacuous.
- : this is the only range in which condition 2 is a real restriction.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.