# PSLQ: An Algorithm to Discover Integer Relations

### Description

Let x = (x{sub 1}, x{sub 2} {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{sub 1}x{sub 1} + a{sub 2}x{sub 2} + {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 ... continued below

5

### Creation Information

Bailey, David H. & Borwein, J. M. April 3, 2009.

### Context

This report is part of the collection entitled: Office of Scientific & Technical Information Technical Reports and was provided by UNT Libraries Government Documents Department to Digital Library, a digital repository hosted by the UNT Libraries. More information about this report can be viewed below.

## Who

People and organizations associated with either the creation of this report or its content.

### Provided By

#### UNT Libraries Government Documents Department

Serving as both a federal and a state depository library, the UNT Libraries Government Documents Department maintains millions of items in a variety of formats. The department is a member of the FDLP Content Partnerships Program and an Affiliated Archive of the National Archives.

## What

Descriptive information to help identify this report. Follow the links below to find similar items on the Digital Library.

### Description

Let x = (x{sub 1}, x{sub 2} {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{sub 1}x{sub 1} + a{sub 2}x{sub 2} + {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.

5

### Identifier

Unique identifying numbers for this report in the Digital Library or other systems.

• Report No.: LBNL-2144E
• Grant Number: DE-AC02-05CH11231
• DOI: 10.2172/963658 | External Link
• Office of Scientific & Technical Information Report Number: 963658

### Collections

This report is part of the following collection of related materials.

#### Office of Scientific & Technical Information Technical Reports

Reports, articles and other documents harvested from the Office of Scientific and Technical Information.

Office of Scientific and Technical Information (OSTI) is the Department of Energy (DOE) office that collects, preserves, and disseminates DOE-sponsored research and development (R&D) results that are the outcomes of R&D projects or other funded activities at DOE labs and facilities nationwide and grantees at universities and other institutions.

What responsibilities do I have when using this report?

## When

Dates and time periods associated with this report.

### Creation Date

• April 3, 2009

### Added to The UNT Digital Library

• Nov. 13, 2016, 7:26 p.m.

### Description Last Updated

• Nov. 18, 2016, 4:13 p.m.

Yesterday: 0
Past 30 days: 2
Total Uses: 5

## Interact With This Report

Here are some suggestions for what to do next.