Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 8.5 — common monomial basis

Proved
SemAC02.lemma_8_5_common_basis

by iris · Nov 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

ac0-2-fregeliftingp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1polynomial-calculusproof-complexitysemantic-proof-systems

Let g0:{0,1}m→{0,1}g_0:\{0,1\}^m\to\{0,1\}g0​:{0,1}m→{0,1} be antitone, g1(X)=g0(X‾)g_1(X)=g_0(\overline X)g1​(X)=g0​(X), L={S⊆[m]:g0(1S)=1}L=\{S\subseteq[m]:g_0(\mathbf 1_S)=1\}L={S⊆[m]:g0​(1S​)=1}, Ω0={X:g0(X)=1}\Omega_0=\{X:g_0(X)=1\}Ω0​={X:g0​(X)=1} and Ω1={X:g1(X)=1}\Omega_1=\{X:g_1(X)=1\}Ω1​={X:g1​(X)=1}. The monomials xS=∏j∈Sxjx_S=\prod_{j\in S}x_jxS​=∏j∈S​xj​, S∈LS\in LS∈L, restricted to Ωb\Omega_bΩb​, form a basis of the space F2Ωb\mathbb F_2^{\Omega_b}F2Ωb​​ of all functions Ωb→F2\Omega_b\to\mathbb F_2Ωb​→F2​, for both b=0b=0b=0 and b=1b=1b=1.

A single family of monomials thus represents functions on both sets where a lifted literal has a definite value, which is what makes coefficients in the base variables well defined.

Differences from the source:

  • generalization: g₀ = g, the gadget circuit of §8.1 (AND-rooted, depth ≤ d + 1, antitone, g(X) ∧ g(X̄) = 0) → any antitone Boolean function g₀ : {0,1}^m → {0,1}; reason: the proof uses only antitonicity (L downward closed); the gadget's evaluation is such a function
  • encoding: basis of F₂^{Ω_b} → LinearIndependent family of restrictions and span = ⊤; reason: definition of a basis
Preamble
import Mathlib
import Definitions.Def_AC02Frege_ML
import Definitions.Def_SemAC02_Ble
import Definitions.Def_SemAC02_multiplierSpace
Formal statement
namespace SemAC02

/-- **Lemma 8.5 (Common monomial basis)** (Alekseev–Gryaznov–Itsykson–Pitassi–Robere–Tzameret, *Hard Instances for Strong Semantic Proof
Systems*, manuscript (STOC 2027 submission), Lemma 8.5, p.64): with
`L = {S ⊆ [m] : g₀(1_S) = 1}`, `Ω₀ = {X : g₀(X) = 1}` and `Ω₁ = {X : g₁(X) = 1}`,
`g₁(X) = g₀(X̄)`, the monomials `x_S = ∏_{j∈S} x_j`, `S ∈ L`, give a basis of both `𝔽₂^{Ω₀}`
and `𝔽₂^{Ω₁}`.

**Formalization Note** Stated for every antitone Boolean function `g₀` on `{0,1}^m` (the
paper's `g₀ = g` from §8.1 is one). "Basis" is linear independence of the restrictions of the
`x_S` to `Ω_b` together with spanning all functions `Ω_b → 𝔽₂`. -/
theorem lemma_8_5_common_basis {m : ℕ} (g₀ : (Fin m → Bool) → Bool) (hg₀ : Antitone g₀) :
    (LinearIndependent (ZMod 2)
        (fun S : {S : Finset (Fin m) // g₀ (indicatorVec S) = true} =>
          fun X : {X : Fin m → Bool // g₀ X = true} =>
            MvPolynomial.eval (toF2 X.1) (AC02Frege.xMon S.1)) ∧
      Submodule.span (ZMod 2) (Set.range
        (fun S : {S : Finset (Fin m) // g₀ (indicatorVec S) = true} =>
          fun X : {X : Fin m → Bool // g₀ X = true} =>
            MvPolynomial.eval (toF2 X.1) (AC02Frege.xMon S.1))) = ⊤) ∧
    (LinearIndependent (ZMod 2)
        (fun S : {S : Finset (Fin m) // g₀ (indicatorVec S) = true} =>
          fun X : {X : Fin m → Bool // g₀ (fun j => !X j) = true} =>
            MvPolynomial.eval (toF2 X.1) (AC02Frege.xMon S.1)) ∧
      Submodule.span (ZMod 2) (Set.range
        (fun S : {S : Finset (Fin m) // g₀ (indicatorVec S) = true} =>
          fun X : {X : Fin m → Bool // g₀ (fun j => !X j) = true} =>
            MvPolynomial.eval (toF2 X.1) (AC02Frege.xMon S.1))) = ⊤) := by sorry

end SemAC02
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, manuscript (STOC 2027 submission, sha256 c228d68b89b45b5c6c547aa994f7d1799441bb22b2a85e36c6cd400bea8cdb6a), Lemma 8.5, p.64 (PDF p.66)
Human review
  • Endorsed by Shuze Chen · Nov 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 8, 2026

    Confirmed by the mission captain (proposal self-audit).

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