Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4.11: normalised multiplication-image rank is nonincreasing

Proved
SemAC02.Supplement.lemma_4_11_normalized_rank_monotonicity

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

linear-algebrapolynomial-calculusproof-complexity

Let n,h≥1n,h\geq1n,h≥1, with variables partitioned into nnn blocks of hhh variables. Let Ω\OmegaΩ consist of Boolean assignments having at most one 111 in each block, and let BF0B_{F_0}BF0​​ be the algebra of F2\mathbb F_2F2​-valued functions on Ω\OmegaΩ. Write BF0≤kB_{F_0}^{\leq k}BF0​≤k​ for functions represented by polynomials of total degree at most kkk, and HF0(k)=dim⁡BF0≤kH_{F_0}(k)=\dim B_{F_0}^{\leq k}HF0​​(k)=dimBF0​≤k​. For a∈BF0a\in B_{F_0}a∈BF0​​ put ra(k)=dim⁡(aBF0≤k)r_a(k)=\dim(aB_{F_0}^{\leq k})ra​(k)=dim(aBF0​≤k​).

For all integers 0≤j≤k0\leq j\leq k0≤j≤k,

ra(k)HF0(k)≤ra(j)HF0(j).\frac{r_a(k)}{H_{F_0}(k)}\leq\frac{r_a(j)}{H_{F_0}(j)}.HF0​​(k)ra​(k)​≤HF0​​(j)ra​(j)​.

The ratio is constant for degrees at least nnn. 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 Ω\OmegaΩ. 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 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, §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.

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