Lattice Size and Generalized Basis Reduction in Dimension 3

Abstract

The lattice size of a lattice polytope $P$ was defined and studied by Schicho, and Castryck and Cools. They provided an "onion skins" algorithm for computing the lattice size of a lattice polygon $P$ in ${\mathbb{R}}^2$ based on passing successively to the convex hull of the interior lattice points of $P$. We explain the connection of the lattice size to the successive minima of $K={\left(P+(-P)\right)}^{\ast }$ and to the lattice reduction with respect to the general norm that corresponds to $K$. It follows that the generalized Gauss algorithm of Kaib and Schnorr (which is faster than the "onion skins" algorithm) computes the lattice size of any convex body in ${\mathbb{R}}^2$. We extend the work of Kaib and Schnorr to dimension 3, providing a fast algorithm for lattice reduction with respect to the general norm defined by a convex origin-symmetric body $K\subset {\mathbb{R}}^3$. We also explain how to recover the successive minima of $K$ and the lattice size of $P$ from the obtained reduced basis and therefore provide a fast algorithm for computing the lattice size of any convex body $P\subset {\mathbb{R}}^3$.

References in corpus (1)

• Small polygons and toric codes

Cited by in corpus (1)

• Bounds on Area Involving Lattice Size