HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Root Separation for Trinomials

Abstract : We give a separation bound for the complex roots of a trinomial $f \in \mathbb{Z}[X]$. The logarithm of the inverse of our separation bound is polynomial in the size of the sparse encoding of $f$; in particular, it is polynomial in $\log (\deg f)$. It is known that no such bound is possible for 4-nomials (polynomials with 4 monomials). For trinomials, the classical results (which are based on the degree of $f$ rather than the number of monomials) give separation bounds that are exponentially worse. As an algorithmic application, we show that the number of real roots of a trinomial $f$ can be computed in time polynomial in the size of the sparse encoding of~$f$. The same problem is open for 4-nomials.
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download

https://hal-ens-lyon.archives-ouvertes.fr/ensl-01585049
Contributor : Pascal Koiran Connect in order to contact the contributor
Submitted on : Wednesday, October 24, 2018 - 3:09:30 PM
Last modification on : Saturday, September 11, 2021 - 3:18:59 AM
Long-term archiving on: : Friday, January 25, 2019 - 2:11:13 PM

Files

revised.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : ensl-01585049, version 3
  • ARXIV : 1709.03294

Collections

Citation

Pascal Koiran. Root Separation for Trinomials. Journal of Symbolic Computation, Elsevier, In press. ⟨ensl-01585049v3⟩

Share

Metrics

Record views

284

Files downloads

145