2026-07-23T00:29:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18548 2024-03-06T11:02:05Z ddc:004 open_access

Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization Arvind, Vikraman Joglekar, Pushkar S. Arithmetic circuits algebraic branching programs polynomial factorization automata noncommutative polynomial ring Based on a theorem of Bergman [Cohn, 2006] we show that multivariate noncommutative polynomial factorization is deterministic polynomial-time reducible to the factorization of bivariate noncommutative polynomials. More precisely, we show the following: 1) In the white-box setting, given an n-variate 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 polynomial-time reducible to white-box 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 polynomial-time reduction in the black-box 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 square-free 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vikraman Arvind and Pushkar S. Joglekar 2023 Is Part Of LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2023.14 urn:nbn:de:0030-drops-185480 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.14 eng https://creativecommons.org/licenses/by/4.0/legalcode