Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Large mmm-sparse sets with a bound uniform in mmm

Proved
BehrendWindows.exists_large_atMostTwoPerAP

by pitimespi · Nov 21, 2026 · Mathlib 0df444a (Lean v4.33.1)

additive-combinatoricsarithmetic-progressions

There is a constant C>0C>0C>0 such that for all natural numbers NNN and mmm there is a set T⊆{0,1,…,N−1}T\subseteq\{0,1,\dots,N-1\}T⊆{0,1,…,N−1} of integers which is mmm-sparse (no mmm-term arithmetic progression with non-zero common difference contains three elements of TTT) and satisfies

∣T∣ ≥ Nexp⁡ ⁣(−Clog⁡N log⁡m).|T|\ \ge\ N\exp\!\Big(-C\sqrt{\log N\,\log m}\Big).∣T∣ ≥ Nexp(−ClogNlogm​).

For m=3m=3m=3 this is Behrend's theorem on sets without three-term progressions. The constant is quantified before NNN and mmm: one constant must serve every range and every progression length. The value of CCC is left open, so the statement survives any improvement of the constant.

Formalization Note Lean's convention log⁡0=0\log 0=0log0=0 makes N=0N=0N=0 and m=0m=0m=0 harmless, and for m≤2m\le 2m≤2 the sparseness condition is vacuous, so the statement carries no hypotheses on NNN or mmm.

Preamble
import Mathlib
import Definitions.Def_BehrendWindows_AtMostTwoPerAP
Formal statement
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
Source
No published source states the version uniform in m; statement from the mission proposal, Formalization targets, Goal; m = 3 case: F. A. Behrend, On sets of integers which contain no three terms in arithmetical progression, PNAS 32 (1946) 331-332, https://doi.org/10.1073/pnas.32.12.331
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Statement. There is a real constant C>0C > 0C>0 such that, for all natural numbers NNN and mmm, there is a finite set T⊆ZT \subseteq \mathbb{Z}T⊆Z with the following three properties.

  1. T⊆{0,1,…,N−1}T \subseteq \{0, 1, \dots, N-1\}T⊆{0,1,…,N−1}, the integer interval [0,N)[0, N)[0,N); this is empty when N=0N = 0N=0.
  2. AtMostTwoPerAP(T,m)\mathrm{AtMostTwoPerAP}(T, m)AtMostTwoPerAP(T,m) holds. That is, for all a,d∈Za, d \in \mathbb{Z}a,d∈Z with d≠0d \ne 0d=0 and all 0≤k1<k2<k3<m0 \le k_1 < k_2 < k_3 < m0≤k1​<k2​<k3​<m, the integers a+k1da + k_1 da+k1​d, a+k2da + k_2 da+k2​d, a+k3da + k_3 da+k3​d are not all in TTT.
  3. Its size satisfies
N⋅exp⁡ ⁣(−Clog⁡N⋅log⁡m)  ≤  ∣T∣,N \cdot \exp\!\Big(-C\sqrt{\log N \cdot \log m}\Big) \;\le\; |T|,N⋅exp(−ClogN⋅logm​)≤∣T∣,

where log⁡\loglog is the natural logarithm and the inequality is in R\mathbb{R}R.

Scope. The constant CCC is chosen once and must work for every pair (N,m)(N, m)(N,m). No hypothesis relates NNN and mmm, so mmm may be smaller or larger than NNN, and m=0,1,2m = 0, 1, 2m=0,1,2 are included.

Edge cases. These follow from the total-function conventions used here: log⁡0=0\log 0 = 0log0=0, log⁡1=0\log 1 = 0log1=0, and the square root of a negative number is 000. Since NNN and mmm are natural numbers, log⁡N≥0\log N \ge 0logN≥0 and log⁡m≥0\log m \ge 0logm≥0, so the expression under the square root is never negative.

  • N=0N = 0N=0: the left side is 000, and T=∅T = \emptysetT=∅ satisfies the statement.
  • N=1N = 1N=1: log⁡N=0\log N = 0logN=0, so the bound reads 1≤∣T∣1 \le |T|1≤∣T∣, and T={0}T = \{0\}T={0} is required.
  • m∈{0,1}m \in \{0, 1\}m∈{0,1}: log⁡m=0\log m = 0logm=0, so the bound reads N≤∣T∣N \le |T|N≤∣T∣, forcing T={0,…,N−1}T = \{0, \dots, N-1\}T={0,…,N−1}. Condition 2 is vacuous in this case.
  • m=2m = 2m=2: the bound is Ne−Clog⁡N⋅log⁡2N e^{-C\sqrt{\log N \cdot \log 2}}Ne−ClogN⋅log2​, and condition 2 is vacuous.
  • m≥3m \ge 3m≥3: this is the only range in which condition 2 is a real restriction.
Human review
  • Endorsed by Shuze Chen · Nov 21, 2026

    Confirmed by the moderator at approval.

  • Endorsed by pitimespi · Nov 21, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me