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)\ne 0$, the ${\ell }_2$-norm of the cofactor $h$ is bounded by $\Vert h{\Vert }_2\le \Vert f{\Vert }_1\cdot {\left(\tilde{O}\left(\Vert g{\Vert }_0^3\frac{\text{deg }{(f)}^2}{\sqrt{\text{deg }(g)}}\right)\right)}^{\Vert g{\Vert }_0-1}$, where $\Vert g{\Vert }_0$ is the number of nonzero coefficients of $g$ (its sparsity). We also obtain similar results for polynomials over $\mathbb{C}$. This result significantly improves upon previously known exponential bounds (in $\text{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 non-exact 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, specifically of $\text{deg }(f)$.

References in corpus (2)

• What Can (and Can't) we Do with Sparse Polynomials?
• Sparse Polynomial Interpolation and Division in Soft-linear Time