Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose you are given an inner product on a vector space and given a set of linearly independent vectors, and that you have been promised that the lattice they span has an orthonormal basis. Can you (quickly) figure out what that basis is?

Note that this may be much easier than finding the shortest vector in a general lattice, since (for instance) you know ahead of time exactly how long the shortest vector actually is.

Motivation: Suppose you wanted to use Brauer's induction theorem to compute the character table of a big group. After computing enough induced characters, you can check (by calculating a suitable determinant) that you have a set of representations generating the Grothendieck group. You know ahead of time that the irreducible representations form an orthonormal basis - so it's natural to ask whether you can use this information to quickly figure out what the characters actually are.

share|cite|improve this question
So, more or less, given a symmetric positive definite matrix $G$ of integers with determinant $1,$ and knowing it to be possible, you want to find an integer matrix $P$ such that $P^T P = G.$ My programs find all such expressions, essentially by finding all possible first columns of $P,$ then all possible second columns, and so on. Then for each first column, I find all second columns giving the correct inner product, continue to the third column when successful. It is fast enough for me. – Will Jagy Nov 3 '12 at 0:48
That should work, but... I was kind of hoping for some kind of theoretical guarantee about worst-case performance. – zeb Nov 3 '12 at 0:55
No idea. ${}{}{}$ – Will Jagy Nov 3 '12 at 1:04

2 Answers 2

up vote 4 down vote accepted

I believe there is no known algorithm for the case of orthonormal lattices. I have seen this mentioned as an open question a couple of times. The only known algorithms are unfortunately those for general lattices, mainly LLL and its extension BKZ.

The fact that the length of the shortest vector is known is not necessarily a strong indication that the problem is easy. A similar situation occurs with other families of lattices, especially so-called ideal lattices, which are lattices obtained through the canonical embedding of ideals in number fields (see, e.g., "Lattices that Admit Logarithmic Worst-Case to Average-Case Connection Factors", Peikert and Rosen, STOC 2007). And just like in the case of orthonormal lattices, the best known algorithms are the generic ones, despite the extra structure.

share|cite|improve this answer
There is a recent paper by Lenstra and Silverberg Revisiting the Gentry-Szydlo Algorithm to appear at CRYPTO 2014 that finds the orthonormal basis in polynomial time for lattices with enough symmetries. – Daniele Micciancio Jul 12 '14 at 21:36

If there is an orthonormal basis, the lattice is $Z^n$ and one can try to find all the $n$ norm 1 vectors up to sign. If $v_j$ is your given basis and $w=\sum x_j v_j, x_j \in Z$ is of norm one and $v_i^*$ is the dual basis ($<v_i^*,v_j>=\delta_{ij}$), then $|x_i|=|<v_i^*,w>| \le |v_i^*|$. If $G_{ij}=<v_i,v_j>$ is the Gram matrix from the given basis, then $G^{-1}=<v_i^*,v_j^*>$ is the Gram for the dual lattice. So one only need to search the finitely many $x \in Z^n$ with $|x_j| \le \sqrt{(G^{-1})_{jj}}$ for all $j$ to solve $x^TGx=1$. This gives a worst-case bound but it is still exponential in $n$.

But I think one should just quickly find a few $w$ and reduce the problem by looking in the orthogonal complement. If $w_1,...w_k$ are norm 1 vectors found generating a sub-$Z^k$,then the orthogonal projection $v_j'$ of any $v_j$ on the orthogonal complement to the space spanned by the $w's$ must be a lattice vector. We now pick $v_j'$ only if the rank of the ortho-complement increased by one until we find a generating set of $n-k$ $v_j'$ and we now have a problem in lower dimension.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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