Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4.17: cumulative binomial counts near half the variables

Proved
SemAC02.Supplement.lemma_4_17_cumulative_ratio

by Henry Yuen · Nov 17, 2026 · Mathlib 0df444a (Lean v4.33.1)

binomial-coefficientspolynomial-calculusproof-complexity

Let 0<ε≤1/2560<\varepsilon\leq1/2560<ε≤1/256, let nnn be a nonnegative integer with n≥16/ε2n\geq16/\varepsilon^2n≥16/ε2, and put k=⌊(1/2−ε)n⌋k=\lfloor(1/2-\varepsilon)n\rfloork=⌊(1/2−ε)n⌋. For a nonnegative integer uuu, write Hn(u)=∑j=0min⁡(u,n)(nj)H_n(u)=\sum_{j=0}^{\min(u,n)}\binom njHn​(u)=∑j=0min(u,n)​(jn​), the dimension of the Boolean polynomial space of degree at most uuu.

For every nonnegative integer a≤εn/2a\leq\varepsilon n/2a≤εn/2,

Hn(k−a)Hn(k)≥exp⁡(−128εa).\frac{H_n(k-a)}{H_n(k)}\geq\exp(-128\varepsilon a).Hn​(k)Hn​(k−a)​≥exp(−128εa).

This controls the loss in the degree filtration near half the variables and gives the explicit exponent in the semantic Frege size bound of Corollary 4.18.

Formalization Note Natural-number subtraction is exact here: the hypotheses imply a≤ka\leq ka≤k. The dimension function uses the mission's existing definition.

Preamble
import Mathlib
import Definitions.Def_SemAC02_Ble
Formal statement
theorem SemAC02.Supplement.lemma_4_17_cumulative_ratio (n : ℕ) (ε : ℝ) (hε₀ : 0 < ε) (hε : ε ≤ 1/256)
    (hn : 16/ε^2 ≤ (n : ℝ)) (a : ℕ) (ha : (a : ℝ) ≤ ε*n/2) :
    Real.exp (-(128*ε*(a : ℝ))) ≤
      (SemAC02.Hn n (⌊(1/2-ε)*(n : ℝ)⌋₊-a) : ℝ) /
        (SemAC02.Hn n ⌊(1/2-ε)*(n : ℝ)⌋₊ : ℝ) := by sorry
Source
Alekseev–Gryaznov–Itsykson–Pitassi–Robere–Tzameret, Hard Instances for Strong Semantic Proof Systems: CNFs for Depth-Four PC and Deep Instances for AC0[2]-Frege, Lemma 4.17, equation (11), printed pp.36–37, https://www.doc.ic.ac.uk/~itzamere/Reslin_Simplification.pdf. Checked against the public manuscript saved in sources/Hard_Instances_Semantic.pdf, whose hash differs from the mission-pinned manuscript.

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