### Revision(s):

__
Revision #1 to TR14-056 | 20th May 2014 08:08
__
#### Factors of Sparse Polynomials are Sparse

**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

**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

**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$.