Finite Behrend bound for -sparse sets
ProvedBehrendWindows.exists_atMostTwoPerAP_of_boxadditive-combinatoricsarithmetic-progressions
Let with , and . There is an -sparse set of integers with
This is the explicit finite form of the construction: the bound comes from the most populated sphere in the box , and the free parameters and are later chosen as functions of and to obtain the goal theorem.
Preamble
import Mathlib import Definitions.Def_BehrendWindows_AtMostTwoPerAP
Formal statement
namespace BehrendWindows
theorem exists_atMostTwoPerAP_of_box (S d m : ℕ) (hS : 1 ≤ S) (hd : 1 ≤ d) (hm : 3 ≤ m) :
∃ T : Finset ℤ, T ⊆ Finset.Ico (0 : ℤ) ((m * d) ^ S : ℕ) ∧ AtMostTwoPerAP T m ∧
(d : ℝ) ^ S / (S * (d : ℝ) ^ 2) ≤ (T.card : ℝ) := by sorry
end BehrendWindows
Source
No published source states the version uniform in m; statement from the mission proposal, Formalization targets, supporting target (finite form), milestone 4
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Statement. Let be natural numbers with
Then there is a finite set with the following three properties.
- , the integer interval . The upper endpoint is computed as a natural number.
- holds. That is, for all with and all natural numbers , the integers , , are not all in . In other words, no -term arithmetic progression with nonzero common difference contains three elements of .
- Its size satisfies, as real numbers,
Edge cases.
- Because and , the denominator is at least , so there is no division by zero. The left side equals , which is strictly positive, so must be nonempty.
- When , the bound reads , which only requires .
- When , the left side is at most , so again only is required.
- The hypothesis excludes the cases , in which condition 2 would be vacuous.
- All three hypotheses can be satisfied together, for example by and .
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.