A new bound on cofactors of sparse polynomials
Forum of Mathematics, Sigma · 2026 · 14
DOI: 10.1017/fms.2026.10202 ↗Kurz gefasst
Fachartikel in der Zeitschrift Forum of Mathematics, Sigma, online erschienen am 31.03.2026. Verfasst von Ido Nahshon und 1 weiteren Autor:innen. Die Arbeit nennt 32 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: European Research Council, Israel Science Foundation.
Abstract (Originalsprache)
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}$ .
Förderung
- European Research Council
- Israel Science Foundation
Zitieren
APA
Nahshon, I., & Shpilka, A. (2026). A new bound on cofactors of sparse polynomials. Forum of Mathematics, Sigma, 14. https://doi.org/10.1017/fms.2026.10202
Vancouver
Nahshon I, Shpilka A. A new bound on cofactors of sparse polynomials. Forum of Mathematics, Sigma. 2026;14. doi:10.1017/fms.2026.10202
BibTeX
@article{Nahshon2026,
author = {Nahshon, Ido and Shpilka, Amir},
title = {A new bound on cofactors of sparse polynomials},
journal = {Forum of Mathematics, Sigma},
year = {2026},
volume = {14},
doi = {10.1017/fms.2026.10202}
}
EUVIMED