Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR14-056 | 20th May 2014 08:08

#### Factors of Sparse Polynomials are Sparse

Revision #1
Authors: Zeev Dvir, Rafael Mendes de Oliveira
Accepted on: 20th May 2014 08:08
Keywords:

Abstract:

This paper was removed due to an error in the proof (Claim 4.12 as stated is not true). The authors would like to thank Ilya Volkovich for pointing out a counterexample to this paper’s main result in positive characteristic: If \$F\$ is a field with prime characteristic \$p\$, then the polynomial
\$x_1^p + x_2^p + \ldots + x_n^p\$ has the following factor:
\$(x_1+x_2+ \ldots + x_n)^{p-1}\$, which has sparsity \$n^p\$.

Changes to previous version:

We are withdrawing this paper.

### Paper:

TR14-056 | 18th April 2014 18:08

#### Factors of Sparse Polynomials are Sparse

TR14-056
Authors: Zeev Dvir, Rafael Mendes de Oliveira
Publication: 18th April 2014 23:47
Keywords:

Abstract:

We show that if \$f(x_1,\ldots,x_n)\$ is a polynomial with \$s\$ monomials and \$g(x_1,\ldots,x_n)\$ divides \$f\$ then \$g\$
has at most \$\max(s^{O(\log s \log\log s)},d^{O(\log d)})\$ monomials, where \$d\$ is a bound on the individual degrees
of \$f\$. This answers a question of von zur Gathen and Kaltofen (JCSS 1985) who asked whether a quasi-polynomial
bound holds in this case. Two immediate applications are a randomized quasi-polynomial time factoring algorithm for
sparse polynomials and a deterministic quasi-polynomial time algorithm for sparse divisibility.

### Comment(s):

Comment #1 to TR14-056 | 23rd May 2014 10:17

#### Withdrawal of this paper

Authors: Rafael Mendes de Oliveira
Accepted on: 23rd May 2014 10:17
Keywords:

Comment:

This paper was removed due to an error in the proof (Claim 4.12 as stated is not true). The authors would like to thank Ilya Volkovich for pointing out a counterexample
to this paper’s main result in positive characteristic: If \$F\$ is a field with prime characteristic \$p\$, then the polynomial
\$x_1^p + x_2^p + \ldots + x^n^p\$ has the following factor:
\$(x_1+x_2+ \ldots + x_n)^{p-1}\$, which has sparsity \$n^p\$.

ISSN 1433-8092 | Imprint