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.
Type de document :
Pré-publication, Document de travail
2017
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal-ens-lyon.archives-ouvertes.fr/ensl-01585049
Contributeur : Pascal Koiran <>
Soumis le : mercredi 13 décembre 2017 - 11:21:03
Dernière modification le : mardi 24 avril 2018 - 13:52:53

Fichiers

trinomial2.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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

Collections

Citation

Pascal Koiran. Root Separation for Trinomials. 2017. 〈ensl-01585049v2〉

Partager

Métriques

Consultations de la notice

201

Téléchargements de fichiers

35