Paper 2016/847

On the smallest ratio problem of lattice bases

Jianwei Li

Abstract

Let $({\mathbf{b}}_1,\dots ,{\mathbf{b}}_n)$ be a lattice basis with Gram-Schmidt orthogonalization $({\mathbf{b}}_1^{\ast },\dots ,{\mathbf{b}}_n^{\ast })$, the quantities $\Vert {\mathbf{b}}_1\Vert /\Vert {\mathbf{b}}_i^{\ast }\Vert$ for $i=1,\dots ,n$ play important roles in analyzing lattice reduction algorithms and lattice enumeration algorithms. In this paper, we study the problem of minimizing the quantity $\Vert {\mathbf{b}}_1\Vert /\Vert {\mathbf{b}}_n^{\ast }\Vert$ over all bases $({\mathbf{b}}_1,\dots ,{\mathbf{b}}_n)$ of a given $n$-dimensional lattice. We first prove that there exists a basis $$ for any lattice $$ of dimension $$ such that $$, $$ and $$ for $$. This leads us to introduce a new NP-hard computational problem, that is, the smallest ratio problem (SRP): given an $$-dimensional lattice $$, find a basis $$ of $$ such that $$ is minimal. The problem inspires the new lattice invariant $$ and new lattice constant $$ over all $$-dimensional lattices $$: both the minimum and maximum are justified. The properties of $$ and $$ are discussed. We also present an exact algorithm and an approximation algorithm for SRP. This is the first sound study of SRP. Our work is a tiny step towards solving an open problem proposed by Dadush-Regev-Stephens-Davidowitz (CCC '14) for tackling the closest vector problem with preprocessing, that is, whether there exists a basis $$ for any $$-rank lattice such that $$.

Note: This is the full version of the work appeared in Proceedings of ISSAC ’21.