REVIEW
Factor Closure in Noncommutative Algebraic Complexity
Computational Complexity · Submitted 1 Nov 2026 · 14 references
Pith's verdict: Noncommutative factor closure over every field is settled, with explicit polynomial bounds, and the one delicate cancellation argument the proof hangs on is correct.
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
Any factor of a polynomial computed by a noncommutative circuit of size s and degree D has a circuit of size O(sD^3), and the closure extends to formulas, VP^nc, and VNP^nc over every field.
The reading
What carries the argument
The load-bearing object is a small weighted nondeterministic finite automaton with replacement labels: one copying state * and b+1 erasing states, where b is the degree of the right cofactor h. Its transitions read a chosen maximum-degree word v = v_1...v_b of h with coefficient c; from state i the machine either advances on v_{i+1}, replacing it by 1, or resets to state 0, replacing it by -alpha_{i+1}, where the reset coefficient alpha_{i+1} = [t_{i+1}]h / c is the normalized coefficient of the proper suffix t_{i+1} of v. The proof that the induced linear map satisfies T(gh) = g is an exact pairing of accepting runs: every accepting run on rv that uses a reset is paired with exactly one run on the shorter word r t_l, obtained by deleting its last reset block, and the two runs contribute opposite values and cancel, leaving as the sole unpaired run the one that copies r and erases v. Replacing each variable by the transition matrix M_x = (x, e_0^T A_x; 0, A_x) evaluates T on any circuit without expanding it into monomials, giving the O($sD^{3}$) and O($sD^{6}$) circuit bounds; the triangular block form — the polynomial in the upper-left corner and field scalars in the lower-right block — is the feature the formula construction exploits to avoid duplicating polynomial subformulas, yielding O($s^{2}$) and O($s^{4}$).
Extended reading notes
Core claim
The central claim, Theorem 1.1, is that factor complexity is polynomially bounded in product complexity: from a size-s circuit for f of degree at most D, every factor g in any identity f = gh has a circuit of size O($sD^{3}$), and every central factor g in f = agb has one of size O($sD^{6}$), with the circuits constructible deterministically once a maximum-degree word of the cofactor, its coefficient, and the coefficients of all its proper suffixes are supplied. The proof defines a single linear map T that removes a specified right cofactor: built from the cofactor h, the map satisfies T(gh) = g for every left factor g. T is implemented by substituting block matrices M_x for the variables, which turns any circuit for f into a circuit for g; reversing words handles left factors, and two substitutions handle central factors. Theorem 1.2 extends the statement to formulas (O($s^{2}$) one-sided, O($s^{4}$) central), to VP^nc, and to VNP^nc, because the fixed linear map T commutes with the Boolean sum that defines VNP verifiers. The same map gives ABP closure, and over finite fields the size theorems feed algorithms that output complete irreducible factorizations as formulas, as succinct ABPs with polynomial-time edge queries, or as circuits via an $FP^{{\Sigma_2^P}}$ search or a zero-error randomized search with an NP oracle.
Load-bearing premise
The entire chain of theorems rests on the bijective cancellation pairing in Theorem 3.1: for every word r, every accepting run of the automaton on rv that uses a reset must pair with exactly one run on the shorter word r t_l with opposite contribution, and the only unpaired run must be the one that copies r and erases v; if that exact one-to-one pairing failed for a single word, T(gh) = g would collapse, and with it the circuit, formula, ABP, and VNP closure theorems.
Editorial extensions
If this is right
- Lower-bound transfer: if a polynomial-degree family (g_n) requires superpolynomial noncommutative circuit size, then every nonzero family (f_n) with f_n = a_n g_n b_n also requires superpolynomial circuit size — and the same holds for formulas and ABPs.
- A common circuit bound B(s,D) = K s D^6 with K absolute applies to every factor of the original circuit, so repeatedly splitting a polynomial does not force the size bound to grow.
- Over finite fields, complete factorizations of formula inputs can be output as formulas of size O(s^4) in randomized polynomial time, by combining the formula closure with the known ABP factorization.
- For polynomial-degree circuit inputs, every factor admits a succinct ABP of length D+1 whose affine edge labels are computable in polynomial time, even though the ABP width may be exponential.
- Complete ordered irreducible factorizations of circuit inputs can be computed deterministically in FP^{\Sigma_2^P}, or with zero error and expected polynomial time using an NP oracle; a deterministic polynomial-time identity test would turn the latter into an unconditional FP^{NP} algorithm.
Reading between the lines
- The extraction map is a linear identity that deletes a factor from the right without knowing what stands on the left; the same pattern — pick a top-degree word, use reset labels to cancel shorter-suffix contributions — is a transferable template for symbolic division identities in other settings, such as extracting common factors from noncommutative power series.
- Read quantitatively, the paper locates the open algorithmic problem precisely: the only missing piece for polynomial-time factor finding from a general circuit is obtaining a maximum-degree word and its suffix coefficients; everything after that point is settled by the size theorems.
- The lower-bound corollary makes hardness hereditary under multiplication: to prove a noncommutative circuit lower bound it suffices to exhibit one hard family, since every polynomial-degree multiple of it is then hard regardless of how the multiple is constructed.
- The formula bound depends on the automaton being triangular (one polynomial block, one scalar block); the paper itself notes the argument does not extend to arbitrary NFAs, and an extraction method for a stronger model would probably need to replicate that triangular structure.
Original abstract
We prove that $\VPnc$ is closed under taking factors over every field. If a noncommutative circuit of size $s$ computes a nonconstant polynomial of degree at most $D$, then each left or right factor has a circuit of size $O(sD^3)$. A central factor $g$ in a decomposition $f=agb$, with nonconstant outer factors $a,b$, has a circuit of size $O(sD^6)$. The proof uses a small weighted nondeterministic finite automaton (NFA) with replacement labels. Given $f=gh$, its labels depend on a word of maximum degree in $h$ and the coefficients of its suffixes. A pairing of accepting paths proves that the induced linear map $T$ satisfies $T(gh)=g$. Matrix substitution implements $T$ in a circuit. Applying the same substitution to a Boolean-sum verifier proves $\VNPnc$ closure. The construction also proves formula closure. The automaton has one copying state and, after leaving it, uses only scalar replacements. This structure gives formulas of size $O(s^2)$ for one-sided factors and $O(s^4)$ for central factors of a size-$s$ formula. The same map proves that polynomial-size noncommutative algebraic branching programs are closed under taking factors. Polynomial-size ABP factorizations over finite fields are already known from~\cite{AJ25}. These are arithmetic size bounds, with arbitrary field constants at unit cost, including over $\Q$. Over finite fields, combining the formula construction with~\cite{AJ22} gives randomized polynomial-time complete factorization of formula inputs, with factors output as formulas. For polynomial-degree circuit inputs, we obtain polynomial-length succinct ABP descriptions with polynomial-time edge queries. We also give two algorithms that output complete ordered irreducible factorizations as polynomial-size circuits: a deterministic $\FP^{\SigTwo}$ algorithm and a zero-error randomized algorithm with an NP oracle and expected polynomial running time.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
We prove that $\VPnc$ is closed under taking factors over every field. If a noncommutative circuit of size $s$ computes a nonconstant polynomial of degree at most $D$, then each left or right factor has a circuit of size $O(sD^3)$. A central factor $g$ in a decomposition $f=agb$, with nonconstant outer factors $a,b$, has a circuit of size $O(sD^6)$. The proof uses a small weighted nondeterministic finite automaton (NFA) with replacement labels. Given $f=gh$, its labels depend on a word of maximum degree in $h$ and the coefficients of its suffixes. A pairing of accepting paths proves that the induced linear map $T$ satisfies $T(gh)=g$. Matrix substitution implements $T$ in a circuit. Applying the same substitution to a Boolean-sum verifier proves $\VNPnc$ closure. The construction also proves formula closure. The automaton has one copying state and, after leaving it, uses only scalar replacements. This structure gives formulas of size $O(s^2)$ for one-sided factors and $O(s^4)$ for central factors of a size-$s$ formula. The same map proves that polynomial-size noncommutative algebraic branching programs are closed under taking factors. Polynomial-size ABP factorizations over finite fields are already known from~\cite{AJ25}. These are arithmetic size bounds, with arbitrary field constants at unit cost, including over $\Q$. Over finite fields, combining the formula construction with~\cite{AJ22} gives randomized polynomial-time complete factorization of formula inputs, with factors output as formulas. For polynomial-degree circuit inputs, we obtain polynomial-length succinct ABP descriptions with polynomial-time edge queries. We also give two algorithms that output complete ordered irreducible factorizations as polynomial-size circuits: a deterministic $\FP^{\SigTwo}$ algorithm and a zero-error randomized algorithm with an NP oracle and expected polynomial running time.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We prove that $\VPnc$ is closed under taking factors over every field. | result 0.83 | 0.95 | 0.93 | asserted 1.00 |
| s1 | If a noncommutative circuit of size $s$ computes a nonconstant polynomial of degree at most $D$, then each left or right factor has a circuit of size $O(sD^3)$. | result 0.98 | 0.93 | 0.23 | asserted 1.00 |
| s2 | A central factor $g$ in a decomposition $f=agb$, with nonconstant outer factors $a,b$, has a circuit of size $O(sD^6)$. | result 0.99 | 0.94 | 0.09 | asserted 1.00 |
| s3 | The proof uses a small weighted nondeterministic finite automaton (NFA) with replacement labels. | method 1.00 | 0.86 | 0.02 | asserted 1.00 |
| s4 | Given $f=gh$, its labels depend on a word of maximum degree in $h$ and the coefficients of its suffixes. | method 0.99 | 0.85 | 0.02 | asserted 1.00 |
| s5 | A pairing of accepting paths proves that the induced linear map $T$ satisfies $T(gh)=g$. | method 0.98 | 0.90 | 0.03 | asserted 1.00 |
| s6 | Matrix substitution implements $T$ in a circuit. | method 1.00 | 0.84 | 0.02 | asserted 1.00 |
| s7 | Applying the same substitution to a Boolean-sum verifier proves $\VNPnc$ closure. | result 0.53 | 0.91 | 0.07 | asserted 1.00 |
| s8 | The construction also proves formula closure. | result 0.93 | 0.92 | 0.05 | asserted 1.00 |
| s9 | The automaton has one copying state and, after leaving it, uses only scalar replacements. | method 0.97 | 0.88 | 0.02 | asserted 1.00 |
| s10 | This structure gives formulas of size $O(s^2)$ for one-sided factors and $O(s^4)$ for central factors of a size-$s$ formula. | result 0.97 | 0.93 | 0.06 | asserted 1.00 |
| s11 | The same map proves that polynomial-size noncommutative algebraic branching programs are closed under taking factors. | result 0.93 | 0.88 | 0.11 | asserted 1.00 |
| s12 | Polynomial-size ABP factorizations over finite fields are already known from~\cite{AJ25}. | background 0.99 | 0.04 | 0.02 | asserted 1.00 |
| s13 | These are arithmetic size bounds, with arbitrary field constants at unit cost, including over $\Q$. | interpretation 0.65 | 0.59 | 0.03 | asserted 1.00 |
| s14 | Over finite fields, combining the formula construction with~\cite{AJ22} gives randomized polynomial-time complete factorization of formula inputs, with factors output as formulas. | result 0.74 | 0.76 | 0.04 | asserted 1.00 |
| s15 | For polynomial-degree circuit inputs, we obtain polynomial-length succinct ABP descriptions with polynomial-time edge queries. | result 0.93 | 0.91 | 0.04 | asserted 1.00 |
| s16 | We also give two algorithms that output complete ordered irreducible factorizations as polynomial-size circuits: a deterministic $\FP^{\SigTwo}$ algorithm and a zero-error randomized algorithm with an NP oracle and expected polynomial running time. | contribution 0.64 | 0.95 | 0.10 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.