Lemma 4.3 — the ideal of the majority
ProvedAC02Frege.lemma_4_3_majority_idealac0-2-fregemajority-liftingp2o-gran-per-chapterp2o-plan-paperp2o-v1polynomial-calculusproof-complexity
Fix one block of variables , let , and work in the Boolean ring of multilinear polynomials in these variables, where (products multilinearized). A monomial is light if and heavy if , and is the span of the light monomials. Let , be the inputs with at most , at least ones.
- The multilinear polynomial is a sum of heavy monomials, and for every heavy monomial . The ideal is exactly the span of the heavy monomials, which is also the space of functions vanishing on ; and the light monomials form a basis of the quotient by .
- Every nonzero polynomial vanishing on has degree at least . Consequently is injective on , and is a basis of .
- Every polynomial has a unique expansion with .
This one-block lemma is what makes the majority basis of the lifted variables a basis.
Differences from the source:
- encoding: ℓ odd, m = (ℓ − 1)/2 (standing assumption of §4) → hypothesis Odd ℓ, m = ℓ / 2; reason: same instances
- encoding: the Boolean ring of one block, its ideal ⟨h⟩ and the quotient by ⟨h⟩ → multilinear MvPolynomial (Fin ℓ) (ZMod 2); ⟨h⟩ = range of q ↦ ML(h q); "light monomials form a basis of the quotient" as: light monomials linearly independent, light span + ⟨h⟩ contains every multilinear p, light span ∩ ⟨h⟩ = 0; reason: these three conditions say exactly that the images of the light monomials form a basis of the quotient
- encoding: {h x_σ : |σ| ≤ m} is a basis of ⟨h⟩ → the family ML(h x_σ), |σ| ≤ m, is linearly independent and its span equals ⟨h⟩; reason: definition of a basis
- encoding: "every polynomial p", "sum of heavy monomials" → every multilinear p; every monomial s in the support of h has exponent sum > m; reason: functions are identified with their multilinear polynomials
Preamble
import Mathlib import Definitions.Def_AC02Frege_ML import Definitions.Def_AC02Frege_lift
Formal statement
namespace AC02Frege
open MvPolynomial
/-- Alekseev–Gryaznov–Pitassi–Robere–Shekhovtsov–Tzameret, *Progress on AC0[2]-Frege Lower Bounds*, manuscript (sha256 88d149fa…), Lemma 4.3, p.20 (the ideal of the majority). In the Boolean ring of one block
(multilinear polynomials in the `ℓ = 2m + 1` variables `x_a`, `a : Fin ℓ`), with
`h = Maj_ℓ`, `⟨h⟩ = {ML(h q)}`, `H₀` / `H₁` the inputs with at most `m` / at least `m + 1`
ones, and `V_{≤m}` the polynomials of degree at most `m`:
(i) `h` is a sum of heavy monomials, `x_σ h = x_σ` for every heavy `x_σ`; `⟨h⟩` is the span of
the heavy monomials and also the space of functions vanishing on `H₀`; the light monomials form a
basis of the quotient by `⟨h⟩` (they are linearly independent, span everything together with
`⟨h⟩`, and their span meets `⟨h⟩` only in `0`).
(ii) Every nonzero polynomial vanishing on `H₁` has degree at least `m + 1`; `v ↦ hv` is
injective on `V_{≤m}`; `{h x_σ : |σ| ≤ m}` is a basis of `⟨h⟩`.
(iii) Every `p` has a unique expansion `p = u + hv` with `deg u, deg v ≤ m`.
**Formalization Note** `m = ℓ / 2`; `|σ|` is `σ.card`; a monomial's degree is the sum of its
exponents; products are multilinearized. Points of the cube are `x : Fin ℓ → ZMod 2`. -/
theorem lemma_4_3_majority_ideal {ℓ : ℕ} (hℓ : Odd ℓ) :
let m := ℓ / 2
let h := majOne ℓ
let ideal : Set (MvPolynomial (Fin ℓ) (ZMod 2)) := Set.range (fun q => ML (h * q))
let heavy : Submodule (ZMod 2) (MvPolynomial (Fin ℓ) (ZMod 2)) :=
Submodule.span (ZMod 2) {p | ∃ σ : Finset (Fin ℓ), m < σ.card ∧ p = xMon σ}
let light : Submodule (ZMod 2) (MvPolynomial (Fin ℓ) (ZMod 2)) :=
Submodule.span (ZMod 2) {p | ∃ σ : Finset (Fin ℓ), σ.card ≤ m ∧ p = xMon σ}
let H0 : Set (Fin ℓ → ZMod 2) := {x | (Finset.univ.filter (fun a => x a = 1)).card ≤ m}
let H1 : Set (Fin ℓ → ZMod 2) := {x | m < (Finset.univ.filter (fun a => x a = 1)).card}
-- (i)
(IsMultilinear h ∧
(∀ s ∈ h.support, m < s.sum (fun _ e => e)) ∧
(∀ σ : Finset (Fin ℓ), m < σ.card → ML (xMon σ * h) = xMon σ) ∧
ideal = (heavy : Set (MvPolynomial (Fin ℓ) (ZMod 2))) ∧
ideal = {p | IsMultilinear p ∧ ∀ x ∈ H0, eval x p = 0} ∧
LinearIndependent (ZMod 2) (fun σ : {σ : Finset (Fin ℓ) // σ.card ≤ m} => xMon σ.1) ∧
(∀ p, IsMultilinear p → ∃ u ∈ light, ∃ w ∈ ideal, p = u + w) ∧
(∀ u ∈ light, u ∈ ideal → u = 0)) ∧
-- (ii)
((∀ p : MvPolynomial (Fin ℓ) (ZMod 2), IsMultilinear p → p ≠ 0 →
(∀ x ∈ H1, eval x p = 0) → m + 1 ≤ p.totalDegree) ∧
(∀ v w : MvPolynomial (Fin ℓ) (ZMod 2), IsMultilinear v → v.totalDegree ≤ m →
IsMultilinear w → w.totalDegree ≤ m → ML (h * v) = ML (h * w) → v = w) ∧
LinearIndependent (ZMod 2)
(fun σ : {σ : Finset (Fin ℓ) // σ.card ≤ m} => ML (h * xMon σ.1)) ∧
ideal = (Submodule.span (ZMod 2)
(Set.range (fun σ : {σ : Finset (Fin ℓ) // σ.card ≤ m} => ML (h * xMon σ.1))) :
Set (MvPolynomial (Fin ℓ) (ZMod 2)))) ∧
-- (iii)
(∀ p : MvPolynomial (Fin ℓ) (ZMod 2), IsMultilinear p →
∃! uv : MvPolynomial (Fin ℓ) (ZMod 2) × MvPolynomial (Fin ℓ) (ZMod 2),
IsMultilinear uv.1 ∧ IsMultilinear uv.2 ∧ uv.1.totalDegree ≤ m ∧ uv.2.totalDegree ≤ m ∧
p = uv.1 + ML (h * uv.2)) := by sorry
end AC02Frege
Source
Alekseev, Gryaznov, Pitassi, Robere, Shekhovtsov, Tzameret, Progress on AC0[2]-Frege Lower Bounds (manuscript dated November 3, 2026, STOC 2027 submission, sha256 88d149fa2bcae702e55a6b72efecda2b4137fd18dca3e23a056c3db5da0ece61), Lemma 4.3, p.20
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.