Lemma 4.11: normalised multiplication-image rank is nonincreasing
ProvedSemAC02.Supplement.lemma_4_11_normalized_rank_monotonicitylinear-algebrapolynomial-calculusproof-complexity
Let , with variables partitioned into blocks of variables. Let consist of Boolean assignments having at most one in each block, and let be the algebra of -valued functions on . Write for functions represented by polynomials of total degree at most , and . For put .
For all integers ,
The ratio is constant for degrees at least . This normalised rank estimate supplies the degree comparison in the proof of the product-approximation Lemma 4.9.
Formalization Note The algebra and its degree filtration use the mission's existing function-space model on . The assertion Antitone includes all nonnegative degrees.
Preamble
import Mathlib import Definitions.Def_SemAC02_nDivision
Formal statement
theorem SemAC02.Supplement.lemma_4_11_normalized_rank_monotonicity (n h : ℕ) (hn : 1 ≤ n) (hh : 1 ≤ h)
(a : SemAC02.nDivOmega n h → ZMod 2) :
Antitone (fun k : ℕ =>
(Module.finrank (ZMod 2) ((SemAC02.BleF0 n h k).map (LinearMap.mulLeft (ZMod 2) a)) : ℝ) /
(SemAC02.HF0 n h k : ℝ)) := 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, §4.2.1, Lemma 4.11 (Normalised rank monotonicity), printed p.32, https://www.doc.ic.ac.uk/~itzamere/Reslin_Simplification.pdf. Checked against the public manuscript saved in sources/Hard_Instances_Semantic.pdf; its hash differs from the mission-pinned manuscript.