A new bound on cofactors of sparse polynomials

Abstract We prove that for polynomials $ f, g, h \in \mathbb {Z}[x] $ satisfying $ f = gh $ and $ f(0) \neq 0 $ , the $\ell _2$ -norm of the cofactor $ h $ is bounded by $$ \begin{align*} \left\Vert {h} \right\Vert{}_2\leq \sqrt{\frac{\left\Vert {g} \right\Vert{}_0}{\deg g}}\cdot \left\Vert {f} \right\Vert{}_1\cdot \left(\widetilde{O}\left( \frac{\left\Vert {g} \right\Vert{}_0^{2.5} \cdot \deg^2{f}}{\sqrt{\deg{g}}} \right) \right)^{\left\Vert {g} \right\Vert{}_0-1} \ , \end{align*} $$ where $\left \Vert {g} \right \Vert {}_0$ is the number of nonzero coefficients of g (its sparsity). We also obtain similar results for polynomials over $\mathbb {C}$ . These bounds are an improvement over the bounds presented in an earlier conference version of this paper [NS24]. This result significantly improves upon previously known exponential bounds (in $\deg {f}$ ) for general polynomials. It further implies that, under exact division, the polynomial division algorithm runs in quasi-linear time with respect to the input size and the number of terms in the quotient $ h $ . This resolves a long-standing open problem concerning the exact divisibility of sparse polynomials. In particular, our result demonstrates a quadratic separation between the runtime (and representation size) of exact and nonexact divisibility by sparse polynomials. Notably, prior to our work, it was not even known whether the representation size of the quotient polynomial could be bounded by a sub-quadratic function of its number of terms, or even by a subquadratic function of $\deg {f}$ .