most recent 30 from http://mathoverflow.net 2013-05-22T23:33:10Z http://mathoverflow.net/feeds/question/111320 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/111320/lattice-reduction-on-an-orthonormal-lattice zeb 2012-11-03T00:02:55Z 2012-12-29T17:34:14Z

<p>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?</p> <p>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.</p> <p>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.</p>

http://mathoverflow.net/questions/111320/lattice-reduction-on-an-orthonormal-lattice/111375#111375 unknown (google) 2012-11-03T13:51:21Z 2012-11-03T13:51:21Z

<p>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 ($=\delta_{ij}$), then $|x_i|=|| \le |v_i^*|$. If $G_{ij}=$ is the Gram matrix from the given basis, then $G^{-1}=$ 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$.</p> <p>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.</p>

http://mathoverflow.net/questions/111320/lattice-reduction-on-an-orthonormal-lattice/117541#117541 Oded Regev 2012-12-29T17:34:14Z 2012-12-29T17:34:14Z

<p>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. </p> <p>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.</p>