Explicit Bounds for Linear Forms in the Exponentials of Algebraic Numbers
Pages 371 - 379
Abstract
In this paper, we study linear forms λ=β1eα1+...βmeαm, where α_i and β_i are algebraic numbers. An explicit lower bound for the absolute value of λ is proved, which is derived from "theoreme me de Lindemann--Weierstrass effectif'' via constructive methods in algebraic computation. Besides, the existence of λ with an explicit upper bound is established on the result of counting algebraic numbers.
References
[1]
REFERENCES [1] Mohammed Ably. 1994. Une version quantitative du théorème de LindemannWeierstrass. Acta Arithmetica 67 (1994), 29--45.
[2]
Shaull Almagor, Dmitry Chistikov, Joël Ouaknine, and James Worrell. 2018. Ominimal invariants for linear loops. In 45th International Colloquium on Automata, Languages, and Programming. Schloss Dagstuhl, 1--14.
[3]
Hirokazu Anai and Volker Weispfenning. 2000. Deciding linear-trigonometric problems. In 25th international symposium on Symbolic and algebraic computation. 14--22.
[4]
James Ax. 1971. On Schanuel's conjectures. Annals of mathematics 93, 2 (1971), 252--268.
[5]
Adnan Aziz, Kumud Sanwal, Vigyan Singhal, and Robert K. Brayton. 1996. Verifying Continuous Time Markov Chains. In Computer Aided Verification, 8th International Conference, Vol. 1102. 269--276.
[6]
Alan Baker. 1990. Transcendental number theory. Cambridge university press.
[7]
Saugata Basu, Richard Pollack, and Marie-Françoise Roy. 2003. Algorithms in Real Algebraic Geometry. Springer.
[8]
Paul C Bell, Jean-Charles Delvenne, Raphaël M Jungers, and Vincent D Blondel. 2010. The continuous skolem-pisot problem. Theoretical Computer Science 411, 40--42 (2010), 3625--3634.
[9]
John Canny. 1988. The complexity of robot motion planning. MIT press.
[10]
Georg Cantor. 1874. Ueber eine Eigenschaft des Inbegriffs aller reellen algebraischen Zahlen. Journal für die reine und angewandte Mathematik 77 (1874), 258--262.
[11]
Taolue Chen, Nengkun Yu, and Tingting Han. 2015. Continuous-time orbit problems are decidable in polynomial-time. Inform. Process. Lett. 115, 1 (2015), 11--14.
[12]
Dmitry Chistikov, Stefan Kiefer, Andrzej S Murawski, and David Purser. 2020. The Big-O Problem for Labelled Markov Chains and Weighted Automata. In 31st International Conference on Concurrency Theory.
[13]
Ventsislav Chonev, Joël Ouaknine, and James Worrell. 2016. On the Skolem Problem for Continuous Linear Dynamical Systems. In 43rd International Colloquium on Automata, Languages, and Programming, Vol. 55. 100:1--100:13.
[14]
Henri Cohen, Henry Cohen, and Henri Cohen. 1993. A course in computational algebraic number theory. Vol. 8. Springer-Verlag Berlin.
[15]
George E Collins and Ellis Horowitz. 1974. The minimum root separation of a polynomial. mathematics of computation 28, 126 (1974), 589--597.
[16]
Yuan Feng and Lijun Zhang. 2017. Precisely deciding CSL formulas through approximate model checking for CTMCs. J. Comput. System Sci. 89 (2017), 361-- 371.
[17]
Ignacio García-Marco, Pascal Koiran, and Timothée Pecatte. 2018. Polynomial equivalence problems for sum of affine powers. In Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation. 303--310.
[18]
Charles Hermite. 1874. Sur la fonction exponentielle. Gauthier-Villars.
[19]
Cheng-Chao Huang, Jing-Cao Li, Ming Xu, and Zhi-Bin Li. 2018. Positive root isolation for poly-powers by exclusion and differentiation. Journal of Symbolic Computation 85 (2018), 148--169.
[20]
Arjen K Lenstra. 1983. Factoring polynomials over algebraic number fields. In European Conference on Computer Algebra. Springer, 245--254.
[21]
Arjen K Lenstra, Hendrik Willem Lenstra, and László Lovász. 1982. Factoring polynomials with rational coefficients. Mathematische annalen 261, ARTICLE (1982), 515--534.
[22]
Ferdinand Lindemann. 1882. Ueber die Zahl ??.*. Math. Ann. 20, 2 (1882), 213--225.
[23]
Joseph Liouville. 1844. Sur des classes très-étendues de quantités dont la valeur n'est ni algébrique ni même réductible à des irrationnelles algébriques. CR Acad. Sci. Paris 18 (1844), 883--885.
[24]
Rüdiger Loos. 1982. Computing in algebraic extensions. In Computer algebra. Springer, 173--187.
[25]
Kurt Mahler. 1932. Zur Approximation der Exponentialfunktion und des Logarithmus. Teil I. (1932), 118--136. (1932).
[26]
Kurt Mahler. 1960. An application of Jensen's formula to polynomials. Mathematika 7, 2 (1960), 98--100.
[27]
Kurt Mahler et al. 1964. An inequality for the discriminant of a polynomial. Michigan Mathematical Journal 11, 3 (1964), 257--262.
[28]
Rupak Majumdar, Mahmoud Salamati, and Sadegh Soudjani. 2020. On Decidability of Time-Bounded Reachability in CTMDPs. In 47th International Colloquium on Automata, Languages, and Programming.
[29]
Rupak Majumdar and Sadegh Soudjani. 2021. The computability of LQR and LQG control. In 24th International Conference on Hybrid Systems: Computation and Control. 1--7.
[30]
Scott McCallum and Volker Weispfenning. 2012. Deciding polynomialtranscendental problems. Journal of Symbolic Computation 47, 1 (2012), 16--31.
[31]
Douglas G Northcott. 1949. An inequality in the theory of arithmetic on algebraic varieties. In Mathematical Proceedings of the Cambridge Philosophical Society, Vol. 45. Cambridge University Press, 502--509.
[32]
Patrice Philippon. 1986. Critères pour l'indépendance algébrique. Publications Mathématiques de l'IHÉS 64 (1986), 5--52.
[33]
Wolfgang M Schmidt. 1993. Northcott's theorem on heights I. A general estimate. Monatshefte für Mathematik 115, 1 (1993), 169--181.
[34]
Alain Sert. 1999. Une version effective du théorème de Lindemann--Weierstrass par les déterminants d'interpolation. Journal of Number Theory 76, 1 (1999), 94--119.
[35]
Carl L Siegel. 2014. Über einige anwendungen diophantischer approximationen. In On Some Applications of Diophantine Approximations. Springer, 81--138.
[36]
Adam Strzebonski. 2009. Real root isolation for tame elementary functions. In 34th international symposium on Symbolic and algebraic computation. 341--350.
[37]
Michel Waldschmidt. 2013. Diophantine approximation on linear algebraic groups: transcendence properties of the exponential function in several variables. Vol. 326. Springer Science & Business Media.
[38]
Karl Weierstrass. 1885. Zu Lindemann's Abhandlung:Über die Ludolph'sche Zahl". Sitzungber. Königl. Preuss. Akad. Wissensch 2 (1885), 1067--1086.
[39]
Ming Xu, Jingyi Mei, Ji Guan, and Nengkun Yu. 2021. Model Checking Quantum Continuous-Time Markov Chains. In 32nd International Conference on Concurrency Theory, Vol. 203. 13:1--13:17.
[40]
Ming Xu, Lijun Zhang, David N Jansen, Huibiao Zhu, and Zongyuan Yang. 2016. Multiphase until formulas over Markov reward models: An algebraic approach. Theoretical Computer Science 611 (2016), 116--135.
[41]
Kazuhiro Yokoyama, Masayuki Noro, and Taku Takeshima. 1989. Computing primitive elements of extension fields. Journal of symbolic computation 8, 6 (1989), 553--580.
Recommendations
Algebras with Polynomial Identities and Computing the Determinant
In 1991, Nisan proved an exponential lower bound on the size of an algebraic branching program (ABP) that computes the determinant of a matrix in the noncommutative “free algebra” setting, in which there are no nontrivial relationships between the ...
Nonnegative Quadratic Forms and Bounds on Orthogonal Polynomials
We show that some nonnegative quadratic forms containing orthogonal polynomials, such as e.g. the Christoffel-Darboux kernel for x=y in the classical case, provide a lot of information about behavior of the polynomials on the real axis. We illustrate ...
Exact polynomial factorization by approximate high degree algebraic numbers
SNC '09: Proceedings of the 2009 conference on Symbolic numeric computationFor factoring polynomials in two variables with rational coefficients, an algorithm using transcendental evaluation was presented by Hulst and Lenstra. In their algorithm, transcendence measure was computed. However, a constant c is necessary to compute ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2022
547 pages
Copyright © 2022 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 05 July 2022
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
ISSAC '22
Sponsor:
ISSAC '22: International Symposium on Symbolic and Algebraic Computation
July 4 - 7, 2022
Villeneuve-d'Ascq, France
Acceptance Rates
Overall Acceptance Rate 395 of 838 submissions, 47%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 119Total Downloads
- Downloads (Last 12 months)54
- Downloads (Last 6 weeks)6
Reflects downloads up to 13 Feb 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in