5
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.