An $n$-dimensional lattice in $\mathbb R^n$ is said to be of Voronoi’s first kind if it there exists $n+1$ vectors $b_1,\cdots b_{n+1}$ (called the superbase) such that

  1. $\{b_1,\ldots,b_n \}$ is a basis,
  2. $b_1+\cdots +b_{n+1}=0$,
  3. $q_{ij}=b_i^Tb_j\le 0$ for all $i\ne j$. The $q_{ij}$ are called selling parameters.

Condition (2) is called the superbase condition and condition (3) the obtuse condition.

Given a lattice which is known to be Voronoi's first kind, are any methods known to find a superbase for it?


In the paper Finding a closest point in a lattice of Voronoi's first kind, the authors state in section 7 that:

Given a lattice, is it possible to efficiently decide whether it is of Voronoi’s first kind? Is it possible to efficiently find an obtuse superbasis if it exists? It is suspected that the answer to this second question is no because an efficient solution would yield a solution to a known problem, that of determining whether a lattice is rectangular (has a basis consisting of pairwise orthogonal vectors) given an arbitrary basis [30].

The reference is to Lenstra and Silverberg's paper Revisiting the Gentry-Szydlo Algorithm.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.