Trinomials and Deterministic Complexity Limits for Real Solving
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913821089595392 |
|---|---|
| author | Boniface, Emma Deng, Weixun Rojas, J. Maurice |
| author_facet | Boniface, Emma Deng, Weixun Rojas, J. Maurice |
| contents | We detail an algorithm that -- for all but a $\frac{1}{Ω(\log(dH))}$ fraction of $f\in\mathbb{Z}[x]$ with exactly $3$ monomial terms, degree $d$, and all coefficients in $\{-H,\ldots, H\}$ -- produces an approximate root (in the sense of Smale) for each real root of $f$ in deterministic time $\log^{4+o(1)}(dH)$ in the classical Turing model. (Each approximate root is a rational with logarithmic height $O(\log(dH))$.) The best previous deterministic bit complexity bounds were exponential in $\log d$. We then relate this to Koiran's Trinomial Sign Problem (2017): Decide the sign of a degree $d$ trinomial $f\in\mathbb{Z}[x]$ with coefficients in $\{-H,\ldots,H\}$, at a point $r\!\in\!\mathbb{Q}$ of logarithmic height $\log H$, in (deterministic) time $\log^{O(1)}(dH)$. We show that Koiran's Trinomial Sign Problem admits a positive solution, at least for a fraction $1-\frac{1}{Ω(\log(dH))}$ of the inputs $(f,r)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2202_06115 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Trinomials and Deterministic Complexity Limits for Real Solving Boniface, Emma Deng, Weixun Rojas, J. Maurice Algebraic Geometry Computational Complexity Numerical Analysis Symbolic Computation We detail an algorithm that -- for all but a $\frac{1}{Ω(\log(dH))}$ fraction of $f\in\mathbb{Z}[x]$ with exactly $3$ monomial terms, degree $d$, and all coefficients in $\{-H,\ldots, H\}$ -- produces an approximate root (in the sense of Smale) for each real root of $f$ in deterministic time $\log^{4+o(1)}(dH)$ in the classical Turing model. (Each approximate root is a rational with logarithmic height $O(\log(dH))$.) The best previous deterministic bit complexity bounds were exponential in $\log d$. We then relate this to Koiran's Trinomial Sign Problem (2017): Decide the sign of a degree $d$ trinomial $f\in\mathbb{Z}[x]$ with coefficients in $\{-H,\ldots,H\}$, at a point $r\!\in\!\mathbb{Q}$ of logarithmic height $\log H$, in (deterministic) time $\log^{O(1)}(dH)$. We show that Koiran's Trinomial Sign Problem admits a positive solution, at least for a fraction $1-\frac{1}{Ω(\log(dH))}$ of the inputs $(f,r)$. |
| title | Trinomials and Deterministic Complexity Limits for Real Solving |
| topic | Algebraic Geometry Computational Complexity Numerical Analysis Symbolic Computation |
| url | https://arxiv.org/abs/2202.06115 |