A New Bound on Cofactors of Sparse Polynomials
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914434591490048 |
|---|---|
| author | Nahshon, Ido Shpilka, Amir |
| author_facet | Nahshon, Ido Shpilka, Amir |
| contents | 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 $\|h\|_2 \leq \|f\|_1 \cdot\left( \widetilde{O}\left(\|g\|_0^3 \frac{\text{deg }{(f)}^2}{\sqrt{\text{deg }{(g)}}}\right)\right)^{\|g\|_0 - 1}$, where $\|g\|_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)}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_03885 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A New Bound on Cofactors of Sparse Polynomials Nahshon, Ido Shpilka, Amir Symbolic Computation Computational Complexity Number Theory 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 $\|h\|_2 \leq \|f\|_1 \cdot\left( \widetilde{O}\left(\|g\|_0^3 \frac{\text{deg }{(f)}^2}{\sqrt{\text{deg }{(g)}}}\right)\right)^{\|g\|_0 - 1}$, where $\|g\|_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)}$. |
| title | A New Bound on Cofactors of Sparse Polynomials |
| topic | Symbolic Computation Computational Complexity Number Theory |
| url | https://arxiv.org/abs/2308.03885 |