TOPICS
Search

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 n such that x is an approximate zero of the number.

When used to find integer relations, a typical input to the algorithm consists of an augmented n×n identity matrix with the entries in the last column consisting of the n elements (multiplied by a large positive constant w to penalize vectors that do not sum to zero) between which the relation is sought. For example, if an equality of the form

a_1x+a_2y+a_3z=0

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]

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 {a_1,a_2,a_3,0} 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])]]

See also

Gram-Schmidt Orthonormalization, Integer Relation, LLL Algorithm, PSLQ Algorithm

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Lattice Reduction

Cite this as:

Weisstein, Eric W. "Lattice Reduction." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/LatticeReduction.html

Subject classifications