Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Given linearly independent vectors x_1,...,x_n in a Euclidean space, how short can a nonzero integer combination of the vectors be? Such problems arise in many applications in number theory and elsewhere, usually as variations of the problem of simultaneous rational approximation. The integer combinations a_1 x_1 + ... + a_n x_n constitute a _lattice_ L in Euclidean space. We report on classical and modern approaches to the problem of _lattice reduction_: finding new generators of L that yield efficient solutions to finding the shortest vector and related lattice problems. We then explain how rational approximation reduces to continued fractions, and thus how lattice reduction may be viewed as a higher-dimensional generalization of the venerable Euclidean algorithm. We conclude with some recent applications of lattice reduction such as efficiently searching for "Fermat near-misses" such as 386692^7 + 411413^7 != 441849^7.