satisfies an integer polynomial of degree 50 or less, then the Euclidean
norm of the coefficients must exceed 
.
The following text about
the PSLQ algorithm was pulled out from a paper by Jonathan M. Borwein and Petr Lisonek:
Applications
of Integer Relation Algorithms,
Discrete Mathematics (Special issue for FPSAC 1997)
The first integer relation algorithm working reliably on vectors of non-trivial length was discovered by Ferguson and Forcade [26]. After a number of improvements, in 1991 a new algorithm, known as the PSLQ algorithm, was developed by Ferguson [24]. More recently a much simpler formulation of this algorithm was introduced [25]. The papers [24] and [25] are available on David Bailey's WWW page. Because this algorithm employs a numerically stable matrix reduction procedure, it is free from the numerical difficulties that plague other integer relation algorithms. Furthermore, its stability allows for an efficient implementation with lower run times on average than other algorithms currently in use.
A distinguishing feature of the PSLQ algorithm is that, besides
recovering an integer relation (if one exists), it can also produce a negative
(non-existence) result of the form ``if a relation exists, then its Euclidean
norm is greater than M (an explicit numerical bound)''. One can
show, on using a working precision that is only slightly higher than that
of the input data, that these bound results obtained from computer runs
are reliable. Results of this type, supporting conjectures about transcendence
of certain constants, are to be found in [2,4].
(See also Section 2.3 on minimal
polynomials.) For example, Bailey and Ferguson [4]
used PSLQ to establish, that if Euler's constant
satisfies an integer polynomial of degree 50 or less, then the Euclidean
norm of the coefficients must exceed .
In the context of these exclusion bounds it is important to realize
that, even for very ``similar'' numbers, the Euclidean norms of their relations
can differ greatly. For example, if x satisfies an integer polynomial
of degree d, norm sand k is an integer, then kx
satisfies an integer polynomial whose norm may become as high as roughly
|k|ds. The lesson here is that, if we can, we
should ``normalize'' our input so that the resulting integer relation is
of low Euclidean norm.
Jazzing Up Euclid's Algorithm (Feb 12 issue of Science News) is an article about the PSLQ algorithm, with mention of the various people involved. At the end of the article you can find references.
Back to IntegerRelations.