More Web Proxy on the site http://driver.im/

research-article

Root separation for trinomials

Author:

Pascal KoiranAuthors Info & Claims

Volume 95, Issue C

Pages 151 - 161

https://doi.org/10.1016/j.jsc.2019.02.004

Published: 01 November 2019 Publication History

Abstract

We give a separation bound for the complex roots of a trinomial f ∈ 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.

References

[1]

Alan Baker, Gisbert Wüstholz, Logarithmic forms and group varieties, J. Reine Angew. Math. 442 (19–62) (1993) 34–57.

[2]

Osbert Bastani, Christopher J. Hillar, Dimitar Popov, Maurice Rojas, Randomization, sums of squares, near-circuits, and faster real root counting, Contemp. Math. 556 (2011) 145–166.

[3]

Bugeaud, Yann; Dujella, Andrej; Pejkovic, Tomislav; Salvy, Bruno (2016): Absolute real root separation. arXiv preprint arXiv:1606.01131.

[4]

Yann Bugeaud, Maurice Mignotte, Polynomial root separation, Int. J. Number Theory 6 (03) (2010) 587–602.

[5]

Augustin Cauchy, Mémoire sur la résolution des équations numériques et sur la théorie de l'élimination, 1829.

[6]

Felipe Cucker, Pascal Koiran, Steve Smale, A polynomial time algorithm for Diophantine equations in one variable, J. Symb. Comput. 27 (1) (1999) 21–29.

Digital Library

[7]

Kousha Etessami, Alistair Stewart, Mihalis Yannakakis, A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing, ACM Trans. Comput. Theory 6 (2) (2014) 9.

[8]

Israel M. Gelfand, Mikhail Kapranov, Andrei Zelevinsky, Discriminants, Resultants, and Multidimensional Determinants, Birkhäuser, 1994.

[9]

Hendrik W. Lenstra Jr., Finding small degree factors of lacunary polynomials, in: Number Theory in Progress, 1999, pp. 267–276.

[10]

Jindal, Gorav, Sagraloff, Michael. A polynomial time algorithm for computing real roots of sparse real polynomials. Expanded version of Jindal and Sagraloff (2017), in preparation.

[11]

Gorav Jindal, Michael Sagraloff, A polynomial time algorithm for computing real roots of sparse real polynomials, in: Proc. ISSAC 2017 (42nd International Symposium on Symbolic and Algebraic Computation), ACM Press, 2017.

[12]

Kurt Mahler, An inequality for the discriminant of a polynomial, Mich. Math. J. 11 (3) (1964) 257–262.

[13]

Morris Marden, Geometry of Polynomials, Mathematical Surveys and Monographs, vol. 3, American Mathematical Society, 1966.

[14]

Morris Marden, The search for a Rolle's theorem in the complex domain, Am. Math. Mon. 92 (9) (1985) 643–650.

[15]

Maurice Mignotte, Some useful bounds, in: Computer Algebra, Springer, 1982, pp. 259–263.

[16]

Qazi Ibadur Rahman, Gerhard Schmeisser, Analytic Theory of Polynomials, London Mathematical Society Monographs (New Series), vol. 26, Oxford University Press, 2002.

[17]

Maurice Rojas, Yinyu Ye, On solving univariate sparse polynomials in logarithmic time, J. Complex. 21 (1) (2005) 87–110.

[18]

Michael Sagraloff, A near-optimal algorithm for computing real roots of sparse polynomials, in: Proc. ISSAC 2014 (39th International Symposium on Symbolic and Algebraic Computation), ACM Press, 2014, pp. 359–366.

Cited By

Jindal GGaillard L(2023)On the Order of Power Series and the Sum of Square Roots ProblemProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597079(354-362)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597079
Rojas JZhu YChyzak FLabahn G(2021)A Complexity Chasm for Solving Univariate Sparse Polynomial Equations Over p-adic FieldsProceedings of the 2021 International Symposium on Symbolic and Algebraic Computation10.1145/3452143.3465554(337-344)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3452143.3465554

Index Terms

Root separation for trinomials
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Algebraic algorithms
2. Mathematics of computing
  1. Discrete mathematics
  2. Mathematical analysis
    1. Numerical analysis
      1. Computations on polynomials

Index terms have been assigned to the content through auto-classification.

Recommendations

Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields
ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computation

We present algorithms that compute all irreducible factors of degree ≤ d of supersparse (lacunary) multivariate polynomials in n variables over an algebraic number field in deterministic polynomial-time in (l+d)ⁿ, where l is the size of the input ...
Short Communication: On multiple roots in Descartes' Rule and their distance to roots of higher derivatives

If an open interval I contains a k-fold root @a of a real polynomial f, then, after transforming I to (0,~), Descartes' Rule of Signs counts exactly k roots of f in I, provided I is such that Descartes' Rule counts no roots of the kth derivative of f. ...
On the complexity of factoring bivariate supersparse (Lacunary) polynomials
ISSAC '05: Proceedings of the 2005 international symposium on Symbolic and algebraic computation

We present algorithms that compute the linear and quadratic factors of supersparse (lacunary) bivariate polynomials over the rational numbers in polynomial-time in the input size. In supersparse polynomials, the term degrees can have hundreds of digits ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Symbolic Computation

Journal of Symbolic Computation Volume 95, Issue C

Nov 2019

238 pages

ISSN:0747-7171

Issue’s Table of Contents

Elsevier Ltd.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 November 2019

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jindal GGaillard L(2023)On the Order of Power Series and the Sum of Square Roots ProblemProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597079(354-362)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597079
Rojas JZhu YChyzak FLabahn G(2021)A Complexity Chasm for Solving Univariate Sparse Polynomial Equations Over p-adic FieldsProceedings of the 2021 International Symposium on Symbolic and Algebraic Computation10.1145/3452143.3465554(337-344)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3452143.3465554

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents