Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Boolean-sum representations (16) and the classes VFnc\mathrm{VF}_{nc}VFnc​, VPnc\mathrm{VP}_{nc}VPnc​, VNPnc\mathrm{VNP}_{nc}VNPnc​, closure under factors

Definition
NCFactorClosure607_Circuits_Supplement_Classes

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

algebraic-complexitycomplexity-classesnoncommutative-algebrap2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

Boolean sums. Let XXX and Z={z1,…,zt}Z=\{z_1,\dots,z_t\}Z={z1​,…,zt​} be disjoint sets of free noncommuting variables. For e∈{0,1}te\in\{0,1\}^te∈{0,1}t, G(X,e)G(X,e)G(X,e) is the image of G∈F⟨X∪Z⟩G\in F\langle X\cup Z\rangleG∈F⟨X∪Z⟩ under the algebra map fixing every x∈Xx\in Xx∈X and sending zjz_jzj​ to the field scalar eje_jej​. The verifier GGG represents

f(X)=∑e∈{0,1}tG(X,e).(16)f(X)=\sum_{e\in\{0,1\}^t}G(X,e). \tag{16}f(X)=e∈{0,1}t∑​G(X,e).(16)

Families. A family over a fixed field FFF assigns to every n∈Nn\in\mathbb Nn∈N a number mnm_nmn​ of variables and a polynomial fn∈F⟨x1,…,xmn⟩f_n\in F\langle x_1,\dots,x_{m_n}\ranglefn​∈F⟨x1​,…,xmn​​⟩. A function u:N→Nu:\mathbb N\to\mathbb Nu:N→N is polynomially bounded when u(n)≤c nc+cu(n)\le c\,n^c+cu(n)≤cnc+c for some ccc and all nnn.

  1. (fn)∈VFnc(f_n)\in\mathrm{VF}_{nc}(fn​)∈VFnc​ (polynomial-size formulas) when some formula for fnf_nfn​ has polynomially bounded size.
  2. (fn)∈VPnc(f_n)\in\mathrm{VP}_{nc}(fn​)∈VPnc​ when mnm_nmn​ and deg⁡fn\deg f_ndegfn​ are polynomially bounded and some circuit for fnf_nfn​ has polynomially bounded size.
  3. (fn)∈VNPnc(f_n)\in\mathrm{VNP}_{nc}(fn​)∈VNPnc​ when mnm_nmn​ and a number tnt_ntn​ of Boolean variables are polynomially bounded, and fn=∑e∈{0,1}tnGn(X,e)f_n=\sum_{e\in\{0,1\}^{t_n}}G_n(X,e)fn​=∑e∈{0,1}tn​​Gn​(X,e) for verifiers GnG_nGn​ computed by circuits of polynomially bounded size and of polynomially bounded degree (the degree of the polynomial GnG_nGn​).

A class is closed under taking factors when for all families (an),(gn),(bn)(a_n),(g_n),(b_n)(an​),(gn​),(bn​) in the same variables with fn=angnbn≠0f_n=a_ng_nb_n\neq0fn​=an​gn​bn​=0 for every nnn, (fn)(f_n)(fn​) in the class implies (gn)(g_n)(gn​) in the class.

These are the objects of Theorem 1.2 and Theorem 6.1.

Formalization Note X∪ZX\cup ZX∪Z is X ⊕ Fin t; zj↦ejz_j\mapsto e_jzj​↦ej​ sends true to 111 and false to 000.

The formula-family class allows any ambient variable count, generalizing the polynomial-variable family convention of §6. Formula size already bounds polynomial degree. Restricting to polynomially bounded variable counts recovers the source class.

Definition code
import Mathlib
import Definitions.Def_NCFactorClosure607_Circuits_Polynomials
import Definitions.Def_NCFactorClosure607_Circuits_Supplement_Formula

/-!
# Boolean-sum representations and the classes VF_nc, VP_nc, VNP_nc

Arvind–Joglekar, *Factor Closure in Noncommutative Algebraic Complexity*,
STOC 2027 submission #607, Theorem 1.2, p.3; §6 opening and §6.1, p.14; §6.2, eq. (16), p.15.

* Boolean-sum representation (16): for disjoint sets `X` and `Z = {z_1, …, z_t}` of free
  noncommuting variables, a verifier `G ∈ F⟨X ∪ Z⟩` (Lean: `FreeAlgebra F (X ⊕ Fin t)`)
  represents `f(X) = Σ_{e ∈ {0,1}^t} G(X, e)`, where `G(X, e)` replaces every `z_j` by the field
  scalar `e_j ∈ {0, 1}` and keeps every `x ∈ X`.
* Families over a fixed field `F`: for every `n : ℕ` a number of variables `m n` and a
  polynomial `f n ∈ F⟨x_1, …, x_{m n}⟩` (Lean: `FreeAlgebra F (Fin (m n))`).
* A function `u : ℕ → ℕ` is polynomially bounded when `u n ≤ c nᶜ + c` for one `c` and all `n`.
* `VF_nc`: polynomial-size formulas, allowing any ambient variable count (a generalization
  of the polynomial-variable family convention of §6); `VP_nc`: polynomially many variables, polynomial degree and
  polynomial-size circuits; `VNP_nc`: polynomially many variables and Boolean inputs, and a
  verifier of polynomial circuit size and polynomial degree.
* Closure under factors (Theorem 1.2, p.3): for every specified `g_n` in `f_n = a_n g_n b_n ≠ 0`.
-/

namespace NCFactorClosure607.Circuits.Supplement

open NCFactorClosure607.Circuits

section BooleanSum

variable {F : Type*} [Field F] {X : Type*} {t : ℕ}

/-- `G ↦ G(X, e)`: the `F`-algebra map `F⟨X ∪ Z⟩ → F⟨X⟩` sending every `x ∈ X` to `x` and every
Boolean variable `z_j` to the field scalar `e_j` (`1` for `true`, `0` for `false`) (§6.2, p.15). -/
noncomputable def specialize (e : Fin t → Bool) :
    FreeAlgebra F (X ⊕ Fin t) →ₐ[F] FreeAlgebra F X :=
  FreeAlgebra.lift F (Sum.elim (FreeAlgebra.ι F) fun j => if e j then 1 else 0)

/-- The polynomial represented by the verifier `G` (eq. (16), p.15):
`Σ_{e ∈ {0,1}^t} G(X, e)`. -/
noncomputable def boolSum (G : FreeAlgebra F (X ⊕ Fin t)) : FreeAlgebra F X :=
  ∑ e : Fin t → Bool, specialize e G

end BooleanSum

/-- `u` is polynomially bounded: `u n ≤ c · nᶜ + c` for some `c` and every `n`. -/
def PolyBounded (u : ℕ → ℕ) : Prop :=
  ∃ c : ℕ, ∀ n : ℕ, u n ≤ c * n ^ c + c

variable (F : Type*) [Field F]

/-- A family `(f_n)` has **polynomial-size noncommutative formulas**: some `c` such that every
`f_n` is computed by a formula with at most `c nᶜ + c` nodes (Theorem 1.2, p.3). -/
def VFnc (m : ℕ → ℕ) (f : ∀ n, FreeAlgebra F (Fin (m n))) : Prop :=
  ∃ c : ℕ, ∀ n : ℕ, ∃ Φ : Formula F (Fin (m n)), Φ.eval = f n ∧ Φ.size ≤ c * n ^ c + c

/-- `(f_n) ∈ VP_nc` (§6, p.14): polynomially many variables, polynomial degree, and
polynomial-size noncommutative circuits. -/
def VPnc (m : ℕ → ℕ) (f : ∀ n, FreeAlgebra F (Fin (m n))) : Prop :=
  PolyBounded m ∧ PolyBounded (fun n => ncDeg (f n)) ∧
    ∃ c : ℕ, ∀ n : ℕ, ∃ C : Circuit F (Fin (m n)),
      C.WellFormed ∧ C.eval = f n ∧ C.size ≤ c * n ^ c + c

/-- `(f_n) ∈ VNP_nc` (§6.2, p.15): polynomially many variables `m n` and Boolean inputs `t n`,
and verifiers `G_n ∈ F⟨X_n ∪ Z_n⟩`, computed by circuits of polynomial size, of polynomial
degree (the degree of the polynomial `G_n`), with `f_n = Σ_{e ∈ {0,1}^{t n}} G_n(X, e)`. -/
def VNPnc (m : ℕ → ℕ) (f : ∀ n, FreeAlgebra F (Fin (m n))) : Prop :=
  PolyBounded m ∧ ∃ t : ℕ → ℕ, PolyBounded t ∧
    ∃ c : ℕ, ∀ n : ℕ, ∃ C : Circuit F (Fin (m n) ⊕ Fin (t n)),
      C.WellFormed ∧ C.size ≤ c * n ^ c + c ∧ ncDeg C.eval ≤ c * n ^ c + c ∧
        boolSum C.eval = f n

/-- A class of families is **closed under taking factors** (Theorem 1.2, p.3): for all
families `(a_n), (g_n), (b_n)` in the same variables with `f_n = a_n g_n b_n ≠ 0` for every `n`,
if `(f_n)` belongs to the class then so does `(g_n)`. -/
def ClosedUnderFactors
    (Cls : (m : ℕ → ℕ) → (∀ n, FreeAlgebra F (Fin (m n))) → Prop) : Prop :=
  ∀ (m : ℕ → ℕ) (a g b : ∀ n, FreeAlgebra F (Fin (m n))),
    (∀ n, a n * g n * b n ≠ 0) → Cls m (fun n => a n * g n * b n) → Cls m g

end NCFactorClosure607.Circuits.Supplement
Source
V. Arvind, Pushkar S Joglekar, Factor Closure in Noncommutative Algebraic Complexity, STOC 2027 submission #607 (October 2026), p.3, Theorem 1.2; p.14, §6 opening and §6.1; p.15, §6.2, eq. (16) and the definition of VNP_nc; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/607.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