Lemma 4.17: cumulative binomial counts near half the variables
ProvedSemAC02.Supplement.lemma_4_17_cumulative_ratiobinomial-coefficientspolynomial-calculusproof-complexity
Let , let be a nonnegative integer with , and put . For a nonnegative integer , write , the dimension of the Boolean polynomial space of degree at most .
For every nonnegative integer ,
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 . 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 sorrySource
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.