Root Separation for Trinomials - ENS de Lyon - École normale supérieure de Lyon Accéder directement au contenu
Article Dans Une Revue Journal of Symbolic Computation Année : 2019

Root Separation for Trinomials

Résumé

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.
Fichier principal
Vignette du fichier
revised.pdf (223.39 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

ensl-01585049 , version 1 (11-09-2017)
ensl-01585049 , version 2 (13-12-2017)
ensl-01585049 , version 3 (24-10-2018)

Identifiants

Citer

Pascal Koiran. Root Separation for Trinomials. Journal of Symbolic Computation, In press. ⟨ensl-01585049v3⟩
304 Consultations
182 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More