Lattice Reduction

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

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])]]

REFERENCES:

Borwein, J. M. and Corless, R. M. "Emerging Tools for Experimental Mathematics." Amer. Math. Monthly 106, 899-909, 1999.

Borwein, J. M. and Lisonek, P. "Applications of Integer Relation Algorithms." Disc. Math. 217, 65-82, 2000.

Cohen, H. A Course in Computational Algebraic Number Theory. New York: Springer-Verlag, 1993.

Coster, M. J.; Joux, A.; LaMacchia, B. A.; Odlyzko, A. M.; Schnorr, C. P.; and Stern, J. "Improved Low-Density Subset Sum Algorithms." Comput. Complex. 2, 111-128, 1992.

Hastad, J.; Just, B.; Lagarias, J. C.; and Schnorr, C. P. "Polynomial Time Algorithms for Finding Integer Relations Among Real Numbers." SIAM J. Comput. 18, 859-881, 1988.

Lagarias, J. C.; Lenstra, H. W. Jr.; and Schnorr, C. P. "Korkin-Zolotarev Bases and Successive Minima of a Lattice and Its Reciprocal Lattice." Combinatorica 10, 333-348, 1990.

Schnorr, C. P. "A More Efficient Algorithm for Lattice Basis Reduction." J. Algorithms 9, 47-62, 1988.

Schnorr, C. P. and Euchner, M. "Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems." In Fundamentals of Computation Theory: Proceedings of the 8th International Conference, Fct '91 Gosen, Germany, September 9-13, 1991. Berlin: Springer-Verlag, pp. 68-85, 1991.