Root separation for trinomials

DOI10.1016/J.JSC.2019.02.004zbMATH Open1429.30009arXiv1709.03294OpenAlexW2963165744MaRDI QIDQ2000267FDOQ2000267

Pascal Koiran

Publication date: 28 June 2019

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Abstract: We give a separation bound for the complex roots of a trinomial $finmathbbZ[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(degf)$. 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.

Full work available at URL: https://arxiv.org/abs/1709.03294

zbMATH Keywords

trinomialsroot separation

Mathematics Subject Classification ID

Polynomials and rational functions of one complex variable (30C10) Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• An inequality for the discriminant of a polynomial
• POLYNOMIAL ROOT SEPARATION
• Logarithmic forms and group varieties.
• Randomization, Sums of Squares, and Faster Real Root Counting for Tetranomials and Beyond
• Characterization of entire functions via quadrature
• A polynomial time algorithm for diophantine equations in one variable
• A near-optimal algorithm for computing real roots of sparse polynomials
• On solving univariate sparse polynomials in logarithmic time
• The Search for a Rolle's Theorem in the Complex Domain
• Absolute Real Root Separation
• A Note on the Complexity of Comparing Succinctly Represented Integers, with an Application to Maximum Probability Parsing
• Efficiently Computing Real Roots of Sparse Polynomials

Cited In (7)

• Trinomials with given roots
• Root separation for polynomials with reducible derivative
• Absolute Root Separation
• On the Order of Power Series and the Sum of Square Roots Problem
• Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields
• The number of roots of a lacunary bivariate polynomial on a line
• A complexity chasm for solving univariate sparse polynomial equations over \(p\)-adic fields

This page was built for publication: Root separation for trinomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2000267)