Root separation for trinomials

DOI10.1016/J.JSC.2019.02.004MaRDI QIDQ2000267zbMATH OpenOpenAlexFDO

Authors Pascal Koiran

Publication date 28 June 2019

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

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)

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.

Recommendations

• Trinomials with given roots
• Absolute root separation
• Counting real connected components of trinomial curve intersections and m-nomial hypersurfaces
• Absolute real root separation
• Improving root separation bounds

Cites work

• scientific article; zbMATH DE number 3785018 (Why is no real title available?)
• scientific article; zbMATH DE number 1305293 (Why is no real title available?)
• scientific article; zbMATH DE number 575960 (Why is no real title available?)
• scientific article; zbMATH DE number 3260031 (Why is no real title available?)
• A near-optimal algorithm for computing real roots of sparse polynomials
• A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing
• A polynomial time algorithm for diophantine equations in one variable
• Absolute real root separation
• An inequality for the discriminant of a polynomial
• Characterization of entire functions via quadrature
• Efficiently Computing Real Roots of Sparse Polynomials
• Logarithmic forms and group varieties.
• On solving univariate sparse polynomials in logarithmic time
• Polynomial root separation
• Randomization, sums of squares, near-circuits, and faster real root counting
• The Search for a Rolle's Theorem in the Complex Domain

Cited in

(8)

• Counting real connected components of trinomial curve intersections and \(m\)-nomial hypersurfaces
• Root separation for polynomials with reducible derivative
• The number of roots of a lacunary bivariate polynomial on a line
• Trinomials with given roots
• Absolute root separation
• On the Order of Power Series and the Sum of Square Roots Problem
• A complexity chasm for solving univariate sparse polynomial equations over \(p\)-adic fields
• Root repulsion and faster solving for very sparse polynomials 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)