# PSLQ [electronic resource] : An Algorithm to Discover Integer Relations

- Published:
- Berkeley, Calif. : Lawrence Berkeley National Laboratory, 2009. and Oak Ridge, Tenn. : Distributed by the Office of Scientific and Technical Information, U.S. Dept. of Energy.
- Physical Description:
- 5 : digital, PDF file
- Additional Creators:
- Lawrence Berkeley National Laboratory and United States. Department of Energy. Office of Scientific and Technical Information
- Access Online:
- www.osti.gov

- Restrictions on Access:
- Free-to-read Unrestricted online access
- Summary:
- Let x = (x₁, x₂ {hor_ellipsis}, x{sub n}) be a vector of real or complex numbers. x is said to possess an integer relation if there exist integers a{sub i}, not all zero, such that a₁x₁ + a₂x₂ + {hor_ellipsis} + a{sub n}x{sub n} = 0. By an integer relation algorithm, we mean a practical computational scheme that can recover the vector of integers ai, if it exists, or can produce bounds within which no integer relation exists. As we will see in the examples below, an integer relation algorithm can be used to recognize a computed constant in terms of a formula involving known constants, or to discover an underlying relation between quantities that can be computed to high precision. At the present time, the most effective algorithm for integer relation detection is the 'PSLQ' algorithm of mathematician-sculptor Helaman Ferguson [10, 4]. Some efficient 'multi-level' implementations of PSLQ, as well as a variant of PSLQ that is well-suited for highly parallel computer systems, are given in [4]. PSLQ constructs a sequence of integer-valued matrices B{sub n} that reduces the vector y = xB{sub n}, until either the relation is found (as one of the columns of B{sub n}), or else precision is exhausted. At the same time, PSLQ generates a steadily growing bound on the size of any possible relation. When a relation is found, the size of smallest entry of the vector y abruptly drops to roughly 'epsilon' (i.e. 10{sup -p}, where p is the number of digits of precision). The size of this drop can be viewed as a 'confidence level' that the relation is real and not merely a numerical artifact - a drop of 20 or more orders of magnitude almost always indicates a real relation. Very high precision arithmetic must be used in PSLQ. If one wishes to recover a relation of length n, with coefficients of maximum size d digits, then the input vector x must be specified to at least nd digits, and one must employ nd-digit floating-point arithmetic. Maple and Mathematica include multiple precision arithmetic facilities and Maple ships with a full implementation of PSLQ. One may also use any of several freeware multiprecision software packages, for example the ARPREC package by the first author and colleagues at LBNL [7]. In the remaining sections we describe various representative applications of PSLQ. More detail about these examples is given in [8] and the references therein.
- Note:
- Published through SciTech Connect., 04/03/2009., "lbnl-2144e", Borwein, J. M.; Bailey, David H., and Computational Research Division
- Funding Information:
- DE-AC02-05CH11231

View MARC record | catkey: 14654105