Corollary 5.2 — one-sided factors of a size- formula have formulas of size , central factors
OpenNCFactorClosure607.Circuits.Supplement.formula_factor_closurearithmetic-formulasfactorizationnoncommutative-algebrap2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be a field and a set of noncommuting variables. There is an absolute constant such that, whenever a formula of size computes a nonzero polynomial :
- if , then both and have formulas of size at most ;
- if , then has a formula of size at most .
where is the least formula size. This is the quantitative formula clause of Theorem 1.2.
Differences from the source:
- generalization: X = {x_1, …, x_m} with m ≥ 1 → an arbitrary type X of noncommuting variables; reason: the statement for every type specializes to every finite nonempty variable set
- encoding: O(s²) and O(s⁴) → one absolute natural constant K quantified before the field, the variable type, the input and the factors; reason: the O(·) of the source is a uniform absolute constant
- encoding: each one-sided factor → both g and h in every presentation f = g h; reason: a left factor is g in f = gh and a right factor is h in f = gh (p.5)
Preamble
import Mathlib import Definitions.Def_NCFactorClosure607_Circuits_Supplement_Formula universe u v
Formal statement
namespace NCFactorClosure607.Circuits.Supplement
/-- Corollary 5.2 (Formula factor closure), p.12. There is one absolute constant `K` such that
for every field `F`, every type `X` of noncommuting variables and every formula `Φ` of size `s`
computing a nonzero `f`: if `f = g h` then `g` and `h` have formulas of size at most `K s²`, and
if `f = a g b` then `g` has a formula of size at most `K s⁴`. -/
theorem formula_factor_closure :
∃ K : ℕ, ∀ (F : Type u) [Field F] (X : Type v) (Φ : Formula F X), Φ.eval ≠ 0 →
(∀ g h : FreeAlgebra F X, Φ.eval = g * h →
(∃ Ψ : Formula F X, Ψ.eval = g ∧ Ψ.size ≤ K * Φ.size ^ 2) ∧
(∃ Ψ : Formula F X, Ψ.eval = h ∧ Ψ.size ≤ K * Φ.size ^ 2)) ∧
(∀ a g b : FreeAlgebra F X, Φ.eval = a * g * b →
∃ Ψ : Formula F X, Ψ.eval = g ∧ Ψ.size ≤ K * Φ.size ^ 4) := by sorry
end NCFactorClosure607.Circuits.Supplement
Source
V. Arvind, Pushkar S Joglekar, Factor Closure in Noncommutative Algebraic Complexity, STOC 2027 submission #607 (October 2026), p.12, Corollary 5.2; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/607.pdf