Abstract
Based on a theorem of Bergman [Cohn, 2006] we show that multivariate noncommutative polynomial factorization is deterministic polynomialtime reducible to the factorization of bivariate noncommutative polynomials. More precisely, we show the following:
1) In the whitebox setting, given an nvariate noncommutative polynomial f ∈ ?⟨X⟩ over a field ? (either a finite field or the rationals) as an arithmetic circuit (or algebraic branching program), computing a complete factorization of f into irreducible factors is deterministic polynomialtime reducible to whitebox factorization of a noncommutative bivariate polynomial g ∈ ?⟨x,y⟩; the reduction transforms f into a circuit for g (resp. ABP for g), and given a complete factorization of g (namely, arithmetic circuits (resp. ABPs) for irreducible factors of g) the reduction recovers a complete factorization of f in polynomial time.
We also obtain a similar deterministic polynomialtime reduction in the blackbox setting.
2) Additionally, we show over the field of rationals that bivariate linear matrix factorization of 4× 4 matrices is at least as hard as factoring squarefree integers. This indicates that reducing noncommutative polynomial factorization to linear matrix factorization (as done in [Vikraman Arvind and Pushkar S. Joglekar, 2022]) is unlikely to succeed over the field of rationals even in the bivariate case. In contrast, multivariate linear matrix factorization for 3×3 matrices over rationals is in polynomial time.
BibTeX  Entry
@InProceedings{arvind_et_al:LIPIcs.MFCS.2023.14,
author = {Arvind, Vikraman and Joglekar, Pushkar S.},
title = {{Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization}},
booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
pages = {14:114:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772921},
ISSN = {18688969},
year = {2023},
volume = {272},
editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18548},
URN = {urn:nbn:de:0030drops185480},
doi = {10.4230/LIPIcs.MFCS.2023.14},
annote = {Keywords: Arithmetic circuits, algebraic branching programs, polynomial factorization, automata, noncommutative polynomial ring}
}
Keywords: 

Arithmetic circuits, algebraic branching programs, polynomial factorization, automata, noncommutative polynomial ring 
Collection: 

48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) 
Issue Date: 

2023 
Date of publication: 

21.08.2023 