-sparse sets: at most two points on every -term progression
DefinitionBehrendWindows_AtMostTwoPerAPA finite set is -sparse if no arithmetic progression of terms with non-zero common difference contains three elements of . Precisely, is -sparse when for all , all with , and all natural numbers ,
For the condition is vacuous. A set is -sparse exactly when it contains no non-trivial three-term arithmetic progression (a Salem–Spencer set), and an -sparse set is -sparse for every .
Formalization Note The positions are natural numbers cast to . The hypothesis is essential: with every non-empty set would fail the condition for .
import Mathlib
namespace BehrendWindows
/-- `T` is `m`-sparse: no arithmetic progression of `m` terms with non-zero
common difference contains three elements of `T`. -/
def AtMostTwoPerAP (T : Finset ℤ) (m : ℕ) : Prop :=
∀ a d : ℤ, d ≠ 0 → ∀ k₁ k₂ k₃ : ℕ, k₁ < k₂ → k₂ < k₃ → k₃ < m →
¬ (a + k₁ * d ∈ T ∧ a + k₂ * d ∈ T ∧ a + k₃ * d ∈ T)
end BehrendWindows
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Definition. For a finite set of integers and a natural number , the proposition holds if and only if, for all integers with and all natural numbers with
the three integers , , do not all belong to .
Put another way, no arithmetic progression of terms with nonzero common difference contains three of its terms in . Here is any integer, can be positive or negative, and the indices are counted from .
Edge cases.
- If , no indices with exist, so the condition is vacuously true for every , including and arbitrarily large intervals.
- For , the condition says that contains no three-term arithmetic progression with .
- The condition is monotone in : a larger allows more triples of indices, so the condition is stronger.
- If , the condition holds for every .