Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5.3: expansion pseudo-reduction operator (explicit s ≥ 1)

Proved
SemAC02.Supplement.lemma_5_3_expansion_pseudo_reduction

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

expansionpolynomial-calculusproof-complexity

Let F=F0∪⋃u∈LFuF=F_0\cup\bigcup_{u\in L}F_uF=F0​∪⋃u∈L​Fu​ be a finite clustered polynomial representation over F2\mathbb F_2F2​, with its variables partitioned into right clusters. Assume the representation is respectful, the background axioms have a common Boolean zero, all axioms are multilinear of degree at most KKK, and its incidence graph is an (s,c)(s,c)(s,c) boundary expander, where s≥1s\ge1s≥1, c>0c>0c>0, and K+1≤cs/2K+1\le cs/2K+1≤cs/2. Fix a degree-compatible monomial order, and let R(t)R(t)R(t) be the local normal form modulo the background axioms and the axiom clusters in Sup⁡s(N(t))\operatorname{Sup}_s(N(t))Sups​(N(t)).

The linear extension to Boolean polynomials of degree at most KKK is a pseudo-reduction operator: it annihilates the axioms, does not increase degree, fixes 111, and satisfies

R(p)=0⟹R(xp)=0R(p)=0\quad\Longrightarrow\quad R(xp)=0R(p)=0⟹R(xp)=0

whenever xpxpxp has degree at most KKK. For each k≤Kk\le Kk≤K, its image dimension is the dimension of the span of the local normal forms of background-standard monomials of degree at most kkk.

This supplies the expansion operator used in the random-formula and graph-pigeonhole lower bounds.

Formalization Note The statement includes s≥1s\ge1s≥1 explicitly because the mission's expansion parameters are real-valued. Without this convention, the original statement has a vacuous-expansion counterexample for 0<s<10<s<10<s<1. The polynomial representative is defined on all multilinear monomials and factors through the background quotient; its rank is computed on the standard monomial basis.

Preamble
import Mathlib
import Definitions.Def_SemAC02_Supplement_expansionRank
import Definitions.Def_SemAC02_Supplement_IsPseudoRed
open MvPolynomial AC02Frege SemAC02 SemAC02.Supplement
Formal statement
theorem SemAC02.Supplement.lemma_5_3_expansion_pseudo_reduction {σ L T : Type} [Finite σ] [DecidableEq σ] [Fintype L] [DecidableEq L]
    [Fintype T] [DecidableEq T]
    (P : ClusteredRep σ L T) (m : MonomialOrder σ) (hm : IsDegCompatible m)
    (hml : ∀ p∈P.axioms, IsMultilinear p)
    (hzero : ∃ y : σ → Bool, ∀ g∈P.F0, eval (toF2 y) g=0)
    (hP : P.IsRespectful) (s c : ℝ) (hs : 1 ≤ s) (hc : 0 < c)
    (hexp : IsBdryExp P.graph s c) (K : ℕ)
    (hdeg : ∀ p∈P.axioms, p.totalDegree ≤ K) (hK : (K : ℝ)+1 ≤ c*s/2) :
    ∃ R : Ble σ K →ₗ[ZMod 2] MvPolynomial σ (ZMod 2),
      IsPseudoRed P.axioms R ∧
      (∀ p : Ble σ K, (R p).totalDegree ≤ (p : MvPolynomial σ (ZMod 2)).totalDegree) ∧
      (∀ (t : Finset σ) (ht : t.card ≤ K),
        R ⟨xMon t,Submodule.subset_span ⟨t,ht,rfl⟩⟩=expOp P m s t) ∧
      (∀ k : ℕ, k ≤ K → rankLe R k=expRank P m s k) ∧
      R ⟨xMon ∅,Submodule.subset_span ⟨∅,Nat.zero_le K,rfl⟩⟩=1 := by sorry
Source
Alekseev–Gryaznov–Itsykson–Pitassi–Robere–Tzameret, Hard Instances for Strong Semantic Proof Systems, Definition 5.2 and Lemma 5.3, printed p.39; rank representation in Definition 5.2 and §5.2. https://www.doc.ic.ac.uk/~itzamere/Reslin_Simplification.pdf. Explicit s ≥ 1 repairs the real-valued parameter corner case. Construction checked against Mikša–Nordström, A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds, JACM 71(6), 2024, Observation 2.10, Lemmas 4.29–4.33 and proof of Theorem 4.11, https://jakobnordstrom.se/docs/publications/GeneralizedMethodPCdegree_JACM.pdf.

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