EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A new bound on cofactors of sparse polynomials

Ido Nahshon, Amir Shpilka

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →