Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR22-022 | 27th February 2022 20:16

On Efficient Noncommutative Polynomial Factorization via Higman Linearization

RSS-Feed




Revision #3
Authors: Vikraman Arvind, Pushkar Joglekar
Accepted on: 27th February 2022 20:16
Downloads: 51
Keywords: 


Abstract:

In this paper we study the problem of efficiently factorizing polynomials in the free noncommutative ring F of polynomials in noncommuting variables x_1,x_2,…,x_n over the field F. We obtain the following result:

Given a noncommutative arithmetic formula of size s computing a noncommutative polynomial f in F as input, where F=F_q is a finite field, we give a randomized algorithm that runs in time polynomial in s, n and log q that computes a factorization of the polynomial f as a product f=f_1f_2… f_r, where each f_i is an irreducible polynomial that is output as a noncommutative algebraic branching program.

The algorithm works by first transforming f into a linear matrix L using Higman's linearization of polynomials. We then factorize the linear matrix L and recover the factorization of the polynomial f. We use basic elements from Cohn's theory of free ideals rings combined with Ronyai's randomized polynomial-time algorithm for computing invariant subspaces of a collection of matrices over finite fields.



Changes to previous version:

Added a discussion on factorization of polynomials over small finite fields.


Revision #2 to TR22-022 | 20th February 2022 21:38

On Efficient Noncommutative Polynomial Factorization via Higman Linearization





Revision #2
Authors: Vikraman Arvind, Pushkar Joglekar
Accepted on: 20th February 2022 21:38
Downloads: 41
Keywords: 


Abstract:

In this paper we study the problem of efficiently factorizing polynomials in the free noncommutative ring $\mathbb{F}\langle x_1,x_2,\ldots, x_n\rangle $ of polynomials in noncommuting variables $x_1,x_2,\ldots,x_n$ over the field $\mathbb{F}$. We obtain the following result:

Given a noncommutative arithmetic formula of size $s$ computing a noncommutative polynomial
$f\in\mathbb{F}\langle x_1,x_2,\ldots,x_n \rangle$ as input, where $\mathbb{F}=\mathbb{F}_q$ is a finite field, we give a randomized algorithm that runs in time polynomial in $s$, $n$ and $\log_2q$ that computes a factorization of $f$ as a
product $f=f_1f_2\cdots f_r$, where each $f_i$ is an irreducible polynomial that is output as a noncommutative algebraic branching program.

The algorithm works by first transforming $f$ into a linear matrix $L$ using Higman's linearization of polynomials. We then factorize the linear matrix $L$ and recover the factorization of $f$. We use basic elements from Cohn's theory of free ideals rings combined with Ronyai's randomized polynomial-time algorithm for computing invariant subspaces of a collection of matrices over
finite fields.



Changes to previous version:

Corrected a typographical error in Lemma 4.8, where the relation $Cv=0$ was missing.


Revision #1 to TR22-022 | 19th February 2022 12:53

On Efficient Noncommutative Polynomial Factorization via Higman Linearization





Revision #1
Authors: Vikraman Arvind, Pushkar Joglekar
Accepted on: 19th February 2022 12:53
Downloads: 57
Keywords: 


Abstract:

In this paper we study the problem of efficiently factorizing polynomials in the free noncommutative ring $\mathbb{F}\angle{x_1,x_2,\ldots,x_n}$ of polynomials in noncommuting variables $x_1,x_2,\ldots,x_n$ over the field $\mathbb{F}$. We obtain the following result:

Given a noncommutative arithmetic formula of size $s$ computing a noncommutative polynomial $f\in\mathbb{F}\angle{x_1,x_2,\ldots,x_n}$ as input, where $\mathbb{F}=\mathbb{F}_q$ is a finite field, we give a randomized algorithm that runs in time polynomial in $s, n$ and $\log_2q$ that computes a factorization of $f$ as a product $f=f_1f_2\cdots f_r$, where each $f_i$ is an irreducible polynomial that is output as a noncommutative algebraic branching program.

The algorithm works by first transforming $f$ into a linear matrix $L$ using Higman's linearization of polynomials. We then factorize the linear matrix $L$ and recover the factorization of $f$. We use basic elements from Cohn's theory of free ideals rings combined with Ronyai's randomized polynomial-time algorithm for computing invariant subspaces of a collection of matrices over finite fields.



Changes to previous version:

used Tex formatting in the abstract.


Paper:

TR22-022 | 18th February 2022 13:39

On Efficient Noncommutative Polynomial Factorization via Higman Linearization


Abstract:

In this paper we study the problem of efficiently factorizing polynomials in the free noncommutative ring F of polynomials in noncommuting variables x_1,x_2,…,x_n over the field F. We obtain the following result:

Given a noncommutative arithmetic formula of size s computing a noncommutative polynomial f in F as input, where F=F_q is a finite field, we give a randomized algorithm that runs in time polynomial in s, n and log q that computes a factorization of the polynomial f as a product f=f_1f_2… f_r, where each f_i is an irreducible polynomial that is output as a noncommutative algebraic branching program.

The algorithm works by first transforming f into a linear matrix L using Higman's linearization of polynomials. We then factorize the linear matrix L and recover the factorization of the polynomial f. We use basic elements from Cohn's theory of free ideals rings combined with Ronyai's randomized polynomial-time algorithm for computing invariant subspaces of a collection of matrices over finite fields.



ISSN 1433-8092 | Imprint