Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

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

#### On Efficient Noncommutative Polynomial Factorization via Higman Linearization

Revision #3
Authors: Vikraman Arvind, Pushkar Joglekar
Accepted on: 27th February 2022 20:16
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
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
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

TR22-022
Authors: Vikraman Arvind, Pushkar Joglekar
Publication: 19th February 2022 07:28
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.

ISSN 1433-8092 | Imprint