Lemma 5.3: expansion pseudo-reduction operator (explicit s ≥ 1)
ProvedSemAC02.Supplement.lemma_5_3_expansion_pseudo_reductionLet be a finite clustered polynomial representation over , 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 , and its incidence graph is an boundary expander, where , , and . Fix a degree-compatible monomial order, and let be the local normal form modulo the background axioms and the axiom clusters in .
The linear extension to Boolean polynomials of degree at most is a pseudo-reduction operator: it annihilates the axioms, does not increase degree, fixes , and satisfies
whenever has degree at most . For each , its image dimension is the dimension of the span of the local normal forms of background-standard monomials of degree at most .
This supplies the expansion operator used in the random-formula and graph-pigeonhole lower bounds.
Formalization Note The statement includes explicitly because the mission's expansion parameters are real-valued. Without this convention, the original statement has a vacuous-expansion counterexample for . The polynomial representative is defined on all multilinear monomials and factors through the background quotient; its rank is computed on the standard monomial basis.
import Mathlib import Definitions.Def_SemAC02_Supplement_expansionRank import Definitions.Def_SemAC02_Supplement_IsPseudoRed open MvPolynomial AC02Frege SemAC02 SemAC02.Supplement
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