<p>As far as I know, the best algorithm we have currently to check if $f$ (given by an arithmetic circuit) can be factorized into linear factors is via the randomized algorithm of <a href="http://www.math.ncsu.edu/~kaltofen/bibliography/89/Ka89_slpfac.pdf">Kaltofen (PDF)</a> which actually produces blackboxes for all the irreducible factors of $f$, and works over any large enough field. In fact, this problem of polynomial factorization for general circuits was recently shown by <a href="http://www.cs.technion.ac.il/~shpilka/publications/KoppartySarafShpilka14.pdf">Kopparty, Saraf and Shpilka</a> to be equivalent to the problem of blackbox-PIT for general circuits. </p>

<p>As mentioned by Bruno, if you are interested in checking a the given circuit is divisible by a given $\ell$, then this reduces to a specific PIT problem. We don't know how to do this deterministically in general but I know of one special case where we know how to do this PIT. There is a <a href="http://eccc.hpi-web.de/report/2011/021/download">deterministic poly-time algorithm (PDF)</a> to check if a given $\ell$ divides a given sparse polynomial $f$. </p>

<p>(Another trivial special case when $f$ is given by a bounded top fan-in depth three circuit. There, $f \bmod \ell$ is also a bounded fan-in depth three circuit and we know how to do PIT in deterministic polynomial time.)</p>

CC BY-SA 3.0
2014-06-04T13:00:10.220Z
2014-06-04T13:00:10.220Z
Ramprasad
<p>Let $f\in\mathbb{Q}[x_{1},x_{2},\ldots,x_{n}]$ be a polynomial given
by an arithmetic circuit $C$ of size $s$. Given $C$ as the input,
is there a deterministic algorithm to check whether all the irreducible
factors of $f$ in $\mathbb{Q}[x_{1},x_{2},\ldots,x_{n}]$ are linear
forms? On a related note, given a linear form $l=\sum_{i=1}^{n}l_{i}\cdot x_{i}$,
can we check deterministically whether $l$ is factor of $f$. Of
course, we want running time to be polynomial in both the cases. 
By size, we mean the total bit size. Also, it can be assumed that degree of $f$ is polynomial in $n$.</p>

CC BY-SA 3.0
2014-06-03T16:16:08.180Z
When you say "size $s$" does that mean number of gates/wires, or total bit-size (taking into account the bits used to describe any constants in the circuit)?
Joshua Grochow
CC BY-SA 3.0
2014-06-03T17:31:01.767Z
@JoshuaGrochow, yeah size is the toal bit size here.
Gorav Jindal
CC BY-SA 3.0
2014-06-04T09:13:56.220Z
Three comments you probably already have in mind, but just in case: 1. Concerning polynomial time, factorization algorithms for arithmetic circuits are polynomial in the size *and the degree* of the polynomial, and I am not aware of algorithms for related tasks that run in time polynomial in the size only. 2. Concerning determinism, these algorithms are randomized and deterministic variants become exponential in the number of variables. 3. The second question can be translated into a PIT problem, so your question amounts to derandomize some specific PIT algorithm.
Bruno
CC BY-SA 3.0
2014-06-04T09:15:21.103Z
I also add that I find these problems very interesting and I'd like to know what is already known on this!
Bruno
CC BY-SA 3.0
2014-06-04T22:34:52.723Z
re [PIT, polynomial identity testing via Schwartz–Zippel](http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma) / wikipedia & there is much active research in that area. (re that pg PIT can be used to factor integers but what is a ref that outlines how to use it to factor polynomials?)
vzn
<ds.algorithms><algebraic-complexity><arithmetic-circuits>
Checking if a polynomial factors into linear factors
Gorav Jindal
# Checking if a polynomial factors into linear factors

(Asked by: username_0 on 2014-06-03)

Let $f\in\mathbb{Q}[x\_{1},x\_{2},\ldots,x\_{n}]$ be a polynomial given
by an arithmetic circuit $C$ of size $s$. Given $C$ as the input,
is there a deterministic algorithm to check whether all the irreducible
factors of $f$ in $\mathbb{Q}[x\_{1},x\_{2},\ldots,x\_{n}]$ are linear
forms? On a related note, given a linear form $l=\sum\_{i=1}^{n}l\_{i}\cdot x\_{i}$,
can we check deterministically whether $l$ is factor of $f$. Of
course, we want running time to be polynomial in both the cases.
By size, we mean the total bit size. Also, it can be assumed that degree of $f$ is polynomial in $n$.

**Tags:** ds.algorithms, algebraic-complexity, arithmetic-circuits

> **Comments:**
> **username_1**: When you say "size $s$" does that mean number of gates/wires, or total bit-size (taking into account the bits used to describe any constants in the circuit)?  
> **username_0**: @JoshuaGrochow, yeah size is the toal bit size here.  
> **username_2**: Three comments you probably already have in mind, but just in case: 1. Concerning polynomial time, factorization algorithms for arithmetic circuits are polynomial in the size *and the degree* of the polynomial, and I am not aware of algorithms for related tasks that run in time polynomial in the size only. 2. Concerning determinism, these algorithms are randomized and deterministic variants become exponential in the number of variables. 3. The second question can be translated into a PIT problem, so your question amounts to derandomize some specific PIT algorithm.  
> **username_2**: I also add that I find these problems very interesting and I'd like to know what is already known on this!  
> **username_3**: re [PIT, polynomial identity testing via Schwartz–Zippel](http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma) / wikipedia & there is much active research in that area. (re that pg PIT can be used to factor integers but what is a ref that outlines how to use it to factor polynomials?)  

---

## 1 answers

### Answer by username_4 on 2014-06-04. Score: 8 | Accepted answer

As far as I know, the best algorithm we have currently to check if $f$ (given by an arithmetic circuit) can be factorized into linear factors is via the randomized algorithm of [Kaltofen (PDF)](http://www.math.ncsu.edu/~kaltofen/bibliography/89/Ka89_slpfac.pdf) which actually produces blackboxes for all the irreducible factors of $f$, and works over any large enough field. In fact, this problem of polynomial factorization for general circuits was recently shown by [Kopparty, Saraf and Shpilka](http://www.cs.technion.ac.il/~shpilka/publications/KoppartySarafShpilka14.pdf) to be equivalent to the problem of blackbox-PIT for general circuits.

As mentioned by username_2, if you are interested in checking a the given circuit is divisible by a given $\ell$, then this reduces to a specific PIT problem. We don't know how to do this deterministically in general but I know of one special case where we know how to do this PIT. There is a [deterministic poly-time algorithm (PDF)](http://eccc.hpi-web.de/report/2011/021/download) to check if a given $\ell$ divides a given sparse polynomial $f$.

(Another trivial special case when $f$ is given by a bounded top fan-in depth three circuit. There, $f \bmod \ell$ is also a bounded fan-in depth three circuit and we know how to do PIT in deterministic polynomial time.)


---

