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$.
We are withdrawing this paper.
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.
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$.
