Integer relations among algebraic numbers
HTML articles powered by AMS MathViewer
- by Bettina Just PDF
- Math. Comp. 54 (1990), 467-477 Request permission
Abstract:
A vector $m = ({m_1}, \ldots ,{m_n}) \in {{\mathbf {Z}}^n}\backslash \{ 0\}$ is called an integer relation for the real numbers ${\alpha _1}, \ldots ,{\alpha _n}$, if $\sum {\alpha _i}{m_i} = 0$ holds. We present an algorithm that, when given algebraic numbers ${\alpha _1}, \ldots ,{\alpha _n}$ and a parameter $\varepsilon$, either finds an integer relation for ${\alpha _1}, \ldots ,{\alpha _n}$ or proves that no relation of Euclidean length shorter than $1/\varepsilon$ exists. Each algebraic number is assumed to be given by its minimal polynomial and by a sufficiently precise rational approximation. Our algorithm uses the Lenstra-Lenstra-Lovász lattice basis reduction technique. It performs \[ {\operatorname {poly}}\left ( {\log 1/\varepsilon ,n,\log \max \limits _i {\text {height}}({\alpha _i}),[{\mathbf {Q}}({\alpha _1}, \ldots ,{\alpha _n}):{\mathbf {Q}}]} \right )\] bit operations. The straightforward algorithm that works with a primitive element of the field extension ${\mathbf {Q}}({\alpha _1}, \ldots ,{\alpha _n})$ of Q would take \[ {\operatorname {poly}}\left ( {n,\log \max \limits _i {\text {height}}({\alpha _i}),\prod \limits _{i = 1}^n {{\text {degree}}({\alpha _i})} } \right )\] bit operations. In order to prove the correctness of the algorithm, we show a lower bound for $\left | {\sum {\alpha _1}{m_i}} \right |$ if m is not an integer relation for ${\alpha _1}, \ldots ,{\alpha _n}$, which may be interesting in its own right.References
- László Babai, Bettina Just, and Friedhelm Meyer auf der Heide, On the limits of computations with the floor function, Inform. and Comput. 78 (1988), no. 2, 99–107. MR 955578, DOI 10.1016/0890-5401(88)90031-4 G. Bergman, Notes on Ferguson and Forcade’s generalized Euclidean algorithm, preprint, Dept. of Math., Univ. of California, Berkeley, 1980.
- Garrett Birkhoff and Saunders Mac Lane, A survey of modern algebra, 3rd ed., The Macmillan Company, New York; Collier Macmillan Ltd., London, 1965. MR 0177992
- B. Buchberger, G. E. Collins, R. Loos, and R. Albrecht (eds.), Computer algebra, 2nd ed., Springer-Verlag, Vienna, 1983. Symbolic and algebraic computation. MR 728960, DOI 10.1007/978-3-7091-7551-4 V. Brun, En generalisation av kjedebroken. I; II, Skr. Vid. Selsk. Kristiana, Mat. Nat. Kl. 6 (1919), 1-29; 6 (1920), 1-24.
- H. R. P. Ferguson and R. W. Forcade, Generalization of the Euclidean algorithm for real numbers to all dimensions higher than two, Bull. Amer. Math. Soc. (N.S.) 1 (1979), no. 6, 912–914. MR 546316, DOI 10.1090/S0273-0979-1979-14691-3
- H. R. P. Ferguson and R. W. Forcade, Multidimensional Euclidean algorithms, J. Reine Angew. Math. 334 (1982), 171–181. MR 667456
- Gerd Fischer and Reinhard Sacher, Einführung in die Algebra, Teubner Studienbücher Mathematik, B. G. Teubner, Stuttgart, 1978 (German). Zweite überarbeitete Auflage. MR 492996
- J. Håstad, B. Just, J. C. Lagarias, and C.-P. Schnorr, Polynomial time algorithms for finding integer relations among real numbers, SIAM J. Comput. 18 (1989), no. 5, 859–881. MR 1015261, DOI 10.1137/0218059 C. G. J. Jacobi, Allgemeine Theorie der kettenbruchähnlichen Algorithmen, J. Reine Angew. Math. 69 (1868), 29-64. R. Kannan, Improved algorithms for integer programming and related problems, 15th ACM Sympos. on Theory of Computing, Association for Computing Machinery, New York, 1983, pp. 193-206.
- R. Kannan, A. K. Lenstra, and L. Lovász, Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers, Math. Comp. 50 (1988), no. 181, 235–250. MR 917831, DOI 10.1090/S0025-5718-1988-0917831-4
- J. C. Lagarias, The computational complexity of simultaneous Diophantine approximation problems, 23rd annual symposium on foundations of computer science (Chicago, Ill., 1982) IEEE, New York, 1982, pp. 32–39. MR 780377
- A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515–534. MR 682664, DOI 10.1007/BF01457454
- Oskar Perron, Grundlagen für eine Theorie des Jacobischen Kettenbruchalgorithmus, Math. Ann. 64 (1907), no. 1, 1–76 (German). MR 1511422, DOI 10.1007/BF01449880
- C.-P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms, Theoret. Comput. Sci. 53 (1987), no. 2-3, 201–224. MR 918090, DOI 10.1016/0304-3975(87)90064-8
- C.-P. Schnorr, A more efficient algorithm for lattice basis reduction, J. Algorithms 9 (1988), no. 1, 47–62. MR 925597, DOI 10.1016/0196-6774(88)90004-1
- Arnold Schönhage, Factorization of univariate integer polynomials by Diophantine approximation and an improved basis reduction algorithm, Automata, languages and programming (Antwerp, 1984) Lecture Notes in Comput. Sci., vol. 172, Springer, Berlin, 1984, pp. 436–447. MR 784270, DOI 10.1007/3-540-13345-3_{4}0
- G. Szekeres, Multidimensional continued fractions, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 13 (1970), 113–140 (1971). MR 313198
Additional Information
- © Copyright 1990 American Mathematical Society
- Journal: Math. Comp. 54 (1990), 467-477
- MSC: Primary 11R04; Secondary 11Y40, 68Q25, 68Q40
- DOI: https://doi.org/10.1090/S0025-5718-1990-0993930-5
- MathSciNet review: 993930