# Root Separation for Trinomials

2 MC2 - Modèles de calcul, Complexité, Combinatoire
LIP - Laboratoire de l'Informatique du Parallélisme
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.
Keywords :
Document type :
Journal articles
Domain :

Cited literature [18 references]

https://hal-ens-lyon.archives-ouvertes.fr/ensl-01585049
Contributor : Pascal Koiran <>
Submitted on : Wednesday, October 24, 2018 - 3:09:30 PM
Last modification on : Thursday, November 21, 2019 - 1:54:38 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

### Citation

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

Record views