Metraipolis › archive › dc_b9078bfcdee7
Factor Closure in Noncommutative Algebraic Complexity — arXiv:2611.02039
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.02039
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T18:59:14.568Z
- SHA-256 of the archived text
9906b83aa83ceda1bbdb783897b7d890355087f9ff119acc042dc2763225853f- Stable URL of this page
https://metraipolis.com/documento/dc_b9078bfcdee7
How to cite
Factor Closure in Noncommutative Algebraic Complexity — arXiv:2611.02039 — arXiv (en), https://arxiv.org/abs/2611.02039 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b9078bfcdee7 (Metraipolis archive dc_b9078bfcdee7, sha256 9906b83aa83ceda1bbdb783897b7d890355087f9ff119acc042dc2763225853f)
BibTeX
@misc{dcb9078bfcdee7,
title = {Factor Closure in Noncommutative Algebraic Complexity — arXiv:2611.02039},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.02039},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b9078bfcdee7; sha256 9906b83aa83ceda1bbdb783897b7d890355087f9ff119acc042dc2763225853f},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.02039. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2611.02039 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T18:18:37.672Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).