分野別セミナー

A lattice is a regular arrangement of infinitely many points in$ R^n$. In the 19th century, Hermite showed that in fixed dimension, the density of any lattice packing can be upper bounded: Hermite's constant determines the optimal density, and bounding this constant is a classical problem in geometry of numbers. Surprisingly, several mathematical methods to bound Hermite's constant are related to major algorithmic results on lattices. In this talk, we introduce lattices and Hermite's constant, and we survey three connections between upper bounds on Hermite's constant and lattice algorithms: Hermite's inequality and the LLL algorithm, Mordell's inequality and blockwise algorithms, Minkowski's inequality and worst-case to average-case reductions.