Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Integer relations among algebraic numbers

Author: Bettina Just
Journal: Math. Comp. 54 (1990), 467-477
MSC: Primary 11R04; Secondary 11Y40, 68Q25, 68Q40
MathSciNet review: 993930
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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

$\displaystyle {\operatorname{poly}}\left( {\log 1/\varepsilon ,n,\log \mathop {... ...pha _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

$\displaystyle {\operatorname{poly}}\left( {n,\log \mathop {\max }\limits_i {\te... ...}}({\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\vert {\sum {\alpha _1}{m_i}} \right\vert$ if m is not an integer relation for $ {\alpha _1}, \ldots ,{\alpha _n}$, which may be interesting in its own right.

References [Enhancements On Off] (What's this?)

  • [1] L. Babai, B. Just, and F. Meyer auf der Heide, On the limits of computations with the floor function, Inf. Comput. 78 (1988), 99-107. MR 955578 (89h:68053)
  • [2] G. Bergman, Notes on Ferguson and Forcade's generalized Euclidean algorithm, preprint, Dept. of Math., Univ. of California, Berkeley, 1980.
  • [3] G. Birkhoff and S. Mac Lane, A survey of modern algebra, Macmillan, New York, 1965. MR 0177992 (31:2250)
  • [4] B. Buchberger, G. Collins, and R. Loos (eds.), Computer algebra. Symbolic and algebraic computation, Springer, Wien and New York, 1982. MR 728960 (87a:68024)
  • [5] V. Brun, En generalisation av kjedebroken. I; II, Skr. Vid. Selsk. Kristiana, Mat. Nat. Kl. 6 (1919), 1-29; 6 (1920), 1-24.
  • [6] H. Ferguson and R. Forcade, Generalization of the Euclidean algorithm for real numbers to all dimensions higher than two, Bull. Amer. Math. Soc. (N. S.) 1 (1979), 912-914. MR 546316 (80i:10039)
  • [7] -, Multidimensional Euclidean algorithms, J. Reine Angew. Math. 334 (1982), 171-181. MR 667456 (84d:10015)
  • [8] G. Fischer and R. Sacher, Einführung in die Algebra, Teubner, Stuttgart, 1983. MR 492996 (80c:00002)
  • [9] J. Hastad, B. Just, J. C. Lagarias, and C. P. Schnorr, Polynomial time algorithms for finding integer relations among real numbers, SIAM J. Comput. 18 (1989), 859-881. MR 1015261 (90g:11171)
  • [10] C. G. J. Jacobi, Allgemeine Theorie der kettenbruchähnlichen Algorithmen, J. Reine Angew. Math. 69 (1868), 29-64.
  • [11] 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.
  • [12] R. Kannan, A. K. Lenstra, and L. Lovász, Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers, Math. Comp. 182 (1988), 235-250. MR 917831 (89j:68061)
  • [13] J. C. Lagarias, The computational complexity of simultaneous Diophantine approximation problems, 23rd Annual Sympos. on the Foundations of Computer Science, IEEE Computer Society Press, Los Angeles, Calif., 1982, pp. 32-39. MR 780377
  • [14] A. K. Lenstra, H. W. Lenstra, and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 513-534. MR 682664 (84a:12002)
  • [15] O. Perron, Grundlagen für eine Theorie des Jacobischen Kettenbruchalgorithmus, Math. Ann. 64 (1907), 1-76. MR 1511422
  • [16] C. P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms, Theor. Comput. Sci. 53 (1987), 201-224. MR 918090 (89h:11085)
  • [17] -, A more efficient algorithm for lattice basis reduction, J. Algorithms 9 (1988), 47-62. MR 925597 (89h:11086)
  • [18] A. Schönhage, Factorization of univariate integer polynomials by Diophantine approximation and by an improved basis reduction algorithm, Proc. of 11th ICALP Antwerpen, Lecture Notes in Comput. Sci., vol. 172, Springer, 1984. MR 784270 (86i:68057)
  • [19] G. Szekeres, Multidimensional continued fractions, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 13 (1970), 113-140. MR 0313198 (47:1753)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11R04, 11Y40, 68Q25, 68Q40

Retrieve articles in all journals with MSC: 11R04, 11Y40, 68Q25, 68Q40

Additional Information

Keywords: Integer relation, algebraic number, lattice basis reduction
Article copyright: © Copyright 1990 American Mathematical Society

American Mathematical Society