Mathematics of Computation

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

 

 

Analysis of PSLQ,
an integer relation finding algorithm


Authors: Helaman R. P. Ferguson, David H. Bailey and Steve Arno
Journal: Math. Comp. 68 (1999), 351-369
MSC (1991): Primary 11A05, 11Y16, 68--04
MathSciNet review: 1489971
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let ${\mathbb{K}}$ be either the real, complex, or quaternion number system and let ${\mathbb{O}}({\mathbb{K}})$ be the corresponding integers. Let $ x = (x_{1}, \hdots , x_{n})$ be a vector in ${\mathbb{K}}^{n}$. The vector $x$ has an integer relation if there exists a vector $m = (m_{1}, \hdots , m_{n}) \in {\mathbb{O}}({\mathbb{K}})^{n}$, $m \ne 0$, such that $m_{1} x_{1} + m_{2} x_{2} + \ldots + m_{n} x_{n} = 0$. In this paper we define the parameterized integer relation construction algorithm PSLQ$(\tau )$, where the parameter $\tau $ can be freely chosen in a certain interval. Beginning with an arbitrary vector $x = (x_{1}, \hdots , x_{n}) \in {\mathbb{K}}^{n}$, iterations of PSLQ$(\tau )$ will produce lower bounds on the norm of any possible relation for $x$. Thus PSLQ$(\tau )$ can be used to prove that there are no relations for $x$ of norm less than a given size. Let $M_{x}$ be the smallest norm of any relation for $x$. For the real and complex case and each fixed parameter $\tau $ in a certain interval, we prove that PSLQ$(\tau )$ constructs a relation in less than $O(n^{3} + n^{2} \log M_{x})$ iterations.


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

  • 1. Steve Arno and Helaman Ferguson, A new polynomial time algorithm for finding relations among real numbers, Supercomputing Research Center Tech Report SRC-93-093 (March 1993), 1-13.
  • 2. D. H. Bailey and H. R. P. Ferguson, A polynomial time, numerically stable integer relation algorithm, SRC Technical Report SRC-TR-92-066; RNR Technical Report RNR-91-032 (16 December 1991; 14 July 1992), 1-14.
  • 3. David H. Bailey, Jonathan M. Borwein, and Roland Girgensohn, Experimental evaluation of Euler sums, Experiment. Math. 3 (1994), no. 1, 17–30. MR 1302815
  • 4. D. H. Bailey, P. Borwein, and S. Plouffe, On the rapid computation of various polylogarithmic constants, Mathematics of Computation 66 (218) (April 1997), 903 - 913. CMP 97:06
  • 5. David H. Bailey, Numerical results on the transcendence of constants involving 𝜋,𝑒, and Euler’s constant, Math. Comp. 50 (1988), no. 181, 275–281. MR 917835, 10.1090/S0025-5718-1988-0917835-1
  • 6. D. H. Bailey, Multiprecision translation and execution of Fortran programs, ACM Transactions on Mathematical Software 19 (3) (1993), 288 - 319.
  • 7. D. H. Bailey, A Fortran-90 based multiprecision system, ACM Transactions on Mathematical Software 21 (4) (1995), 379 - 387..
  • 8. G. Bergman, Notes on Ferguson and Forcade's generalized Euclidean algorithm, University of California at Berkeley, unpublished notes, Nov. 1980.
  • 9. V. Brun, En generalisatiken av kjedebroøken, I, II, Norske Videnskapsselskapets Skrifter I. Matematisk Naturvidenskapelig Klasse 6 (1919, 1920), 1-29, 1-24.
  • 10. Viggo Brun, Algorithmes euclidiens pour trois et quatre nombres, Treizième congrès des mathèmaticiens scandinaves, tenu à Helsinki 18-23 août 1957, Mercators Tryckeri, Helsinki, 1958, pp. 45–64 (French). MR 0111735
  • 11. Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206
  • 12. Matthijs J. Coster, Antoine Joux, Brian A. LaMacchia, Andrew M. Odlyzko, Claus-Peter Schnorr, and Jacques Stern, Improved low-density subset sum algorithms, Comput. Complexity 2 (1992), no. 2, 111–128. MR 1190825, 10.1007/BF01201999
  • 13. Euclid, The thirteen books of Euclid’s Elements translated from the text of Heiberg. Vol. I: Introduction and Books I, II. Vol. II: Books III–IX. Vol. III: Books X–XIII and Appendix, Dover Publications, Inc., New York, 1956. Translated with introduction and commentary by Thomas L. Heath; 2nd ed. MR 0075873
  • 14. H. R. P. Ferguson and R. W. Forcade, Generalization of the Euclidean algorithm for real numbers to all dimensions higher than two, Bulletin (New Series) of the American Mathematical Society 1 (1979), 912 - 914. MR 80i:11039
  • 15. H. R. P. Ferguson and R. W. Forcade, Multidimensional Euclidean algorithms, J. Reine Angew. Math. 334 (1982), 171–181. MR 667456
  • 16. W. D. Brownawell and D. W. Masser, Vanishing sums in function fields, Math. Proc. Cambridge Philos. Soc. 100 (1986), no. 3, 427–434. MR 857720, 10.1017/S0305004100066184
  • 17. Helaman R. P. Ferguson, A noninductive 𝐺𝐿(𝑛,𝑍) algorithm that constructs integral linear relations for 𝑛𝑍-linearly dependent real numbers, J. Algorithms 8 (1987), no. 1, 131–145. MR 875331, 10.1016/0196-6774(87)90033-2
  • 18. Helaman Ferguson, PSOS: A new integral relation finding algorithm involving partial sums of squares and no square roots, Abstracts of papers presented to the American Mathematical Society 9 (56; 88T-11-75) (March 1988), 214.
  • 19. Rodney W. Forcade, Brun's algorithm, unpublished manuscript (November 1981), 1 - 27.
  • 20. D. H. Fowler, Ratio in early Greek mathematics, Bull. Amer. Math. Soc. (N.S.) 1 (1979), no. 6, 807–846. MR 546311, 10.1090/S0273-0979-1979-14684-6
  • 21. Gene H. Golub and Charles F. Van Loan, Matrix computations, 2nd ed., Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1989. MR 1002570
  • 22. C. Hermite, Extraits de lettres de M. Ch. Hermite à M. Jacobi sur differénts objets de la théorie de nombres, (Crelle's) Journal für die Reine und Angewandte Mathematik (3, 4) (1850), 261 - 315.
  • 23. 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, 10.1137/0218059
  • 24. C. G. J. Jacobi, Allgemeine Theorie der Kettenbruchahnlichen Algorithmen, in welchen jede Zahl aus drei vorhergehenden gebildet wird (Aus den hinterlassenen Papieren von C. G. J. Jacobi mitgetheilt durch Herrn E. Heine.), Journal für die Reine und Angewandte Mathematik 69 (1) (1868), 29 - 64.
  • 25. R. Kannan, Lattices, basis reduction and the shortest vector problem, Theory of algorithms (Pécs, 1984) Colloq. Math. Soc. János Bolyai, vol. 44, North-Holland, Amsterdam, 1985, pp. 283–311. MR 872314
  • 26. Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 633878
  • 27. J. C. Lagarias, H. W. Lenstra Jr., and C.-P. Schnorr, Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice, Combinatorica 10 (1990), no. 4, 333–348. MR 1099248, 10.1007/BF02128669
  • 28. 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, 10.1007/BF01457454
  • 29. László Lovász and Herbert E. Scarf, The generalized basis reduction algorithm, Math. Oper. Res. 17 (1992), no. 3, 751–764. MR 1177735, 10.1287/moor.17.3.751
  • 30. O. Perron, Grundlagen für eine Theorie des Jacobischen Kettenbruchalgorithmus, Math. Ann. (64) (1907), 1 - 76.
  • 31. M. Pohst and H. Zassenhaus, Algorithmic algebraic number theory, Encyclopedia of Mathematics and its Applications, vol. 30, Cambridge University Press, Cambridge, 1989. MR 1033013
  • 32. H. Poincaré, Sur une généralisation des fractions continues, Comptes Rendus Acad. Sci. Paris 99 (1884), 1014 - 1016.
  • 33. Asmus L. Schmidt, Diophantine approximation of complex numbers, Acta Math. 134 (1975), 1–85. MR 0422168
  • 34. L. Budach (ed.), Fundamentals of computation theory, Lecture Notes in Computer Science, vol. 529, Springer-Verlag, Berlin, 1991. MR 1136064
    C.-P. Schnorr and M. Euchner, Lattice basis reduction: improved practical algorithms and solving subset sum problems, Math. Programming 66 (1994), no. 2, Ser. A, 181–199. MR 1297061, 10.1007/BF01581144
  • 35. C. Rössner and C. P. Schnorr, A stable integer relation algorithm, FB Mathematik/ Informatik Universität Frankfurt TR-94-016 (1994), 1 - 11.
  • 36. C.-P. Schnorr, A more efficient algorithm for lattice basis reduction, J. Algorithms 9 (1988), no. 1, 47–62. MR 925597, 10.1016/0196-6774(88)90004-1
  • 37. Goro Shimura, Fractional and trigonometric expressions for matrices, Amer. Math. Monthly 101 (1994), no. 8, 744–758. MR 1299160, 10.2307/2974529
  • 38. I. E. Jurut′, An asymptotic formula for the number of representations of integers that are bounded by a number of random summands, Vescī Akad. Navuk BSSR Ser. Fīz.-Mat. Navuk 2 (1972), 5–14 (Russian). MR 0313208

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11A05, 11Y16, 68--04

Retrieve articles in all journals with MSC (1991): 11A05, 11Y16, 68--04


Additional Information

Helaman R. P. Ferguson
Affiliation: Center for Computing Sciences, 17100 Science Drive, Bowie, MD 20715-4300
Email: helamanf@super.org

David H. Bailey
Affiliation: Lawrence Berkeley Lab, Mail Stop 50B-2239, Berkeley, CA 94720
Email: dhb@nersc.gov

Steve Arno
Email: arno@super.org

DOI: http://dx.doi.org/10.1090/S0025-5718-99-00995-3
Keywords: Euclidean algorithm, integer relation finding algorithm, Gaussian integer, Hamiltonian integer, polynomial time
Received by editor(s): April 12, 1996
Received by editor(s) in revised form: June 9, 1997