Noam Elkies on Some Novel Uses of Lattice Reduction

The talk's main topic was the power and applications of an algorithm that performs lattice basis reduction. Prof. Elkies began with a warning that the talk contained explicit material. And indeed within the first five minutes he had given a gigantic explicit solution to the diophantine equation x^3 + y^3 + z^3 = 2 and two lists of common aphorisms--ten on one list and eleven on the other--that were anagrams, i.e. each list contained exactly the same number of a's, b's, c's, etc. To find either of these shockingly explicit things, a brute-force search would have taken far too long, and it was only through lattice basis reduction that finding them became feasible.

The idea of basis reduction is to try to transform any basis of a given lattice into another basis that is "reduced" in the sense that its vectors are close to orthogonal. This problem is closely related to the shortest vector problem (SVP) which, unsurprisingly, asks what the shortest vector is in a given lattice. This problem can be converted to the problem of simultaneous rational approximation: given an integer N and real numbers r and c_i, find a < N such that a*c_i is within r of an integer for each i. It was the search for a good algorithmic to solve this problem that led to the development of good algorithms to perform lattice basis reduction.

--- Rafe Jones, Brown University (AAAS-AMS Media Fellow, 2001)

[Noam D. Elkies (Harvard University) gave this AMS-MAA Invited Address on January 17.]

More highlights of the 2003 Joint Mathematics Meetings