The process of finding a reduced set of basis vectors for a given lattice having certain special properties. Lattice reduction algorithms are used in a number of modern number theoretical applications, including in the discovery of a spigot algorithm for pi. Although determining the shortest basis is possibly an NP-complete problem, algorithms such as the LLL algorithm can find a short basis in polynomial time with guaranteed worst-case performance.
The LLL algorithm of lattice reduction is implemented in the Wolfram Language using the
function LatticeReduce.
RootApproximant[x,
n] also calls this routine in order to find a algebraic
number of degree at most 
such that 
is an approximate zero of the number.
When used to find integer relations, a typical input to the algorithm consists of an augmented 
identity matrix with the entries in the last column
consisting of the 
elements (multiplied by a large positive constant 
to penalize vectors that do not sum to zero) between which
the relation is sought. For example, if an equality of
the form
 |
is known to exist, then doing a lattice reduction on the matrix
![m=[1 0 0 wx; 0 1 0 wy; 0 0 1 wz]](/images/equations/LatticeReduction/NumberedEquation2.svg) |
will produce a new matrix in which one or more entries in the last column being close to zero. This row then gives the coefficients 
of the identity. An example lattice reduction
calculation is illustrated in both Borwein and Corless (1999) and Borwein and Lisonek
(2000).
An example implementation of integer relation finding in the Wolfram Language is given by the following, which can be called as, for example, TranscendentalRecognize[N[Pi
+ E], 
Pi,
E, EulerGamma
].
TranscendentalRecognize[n_, basis_] := Module[
{c, d, digs, e, id, lat, powerten, r, s, vals},
{d, e} = RealDigits[n];
s = Sign[n];
c = FromDigits[d];
powerten = 10^(Length[d] - e);
digs = (RealDigits[N[#1, -e + Length[d] + 5]]&) /@ basis;
r = (FromDigits[Take[First[#1], -e + Last[#1] + Length[d]]]&) /@
digs;
lat = Transpose[
Append[IdentityMatrix[Length[basis] + 2],
Flatten[{powerten, r, c}]]];
vals = Take[First[LatticeReduce[lat]], Length[basis] + 2];
Expand[-((s (Take[vals, {2, -2}].basis + First[vals]))/Last[vals])]]
