I'm currently working on the SVP (Shortest Lattice Vector Problem) as a part of a paper that I'm writing. I've been trying to prove ( or disprove) the following without too much success :
Question : Does there exist a lattice such that when we project the first $k$ co-ordinates of the shortest vectors we obtain the set of all binary strings of length $k$ except all $0$'s, i.e. $2^k - 1$ strings.
A trivial solution is the following lattice (for k=2, where we project the first 2 co-ordinates):
$\left( \begin{array}{ccc} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ N & 0 & 0 \\ 0 & N & 0 \\ 0 & 0 & N \end{array} \right)$
For large enough values of N these lattice basis vectors are the shortest vectors of the lattice. But the dimension in which such lattice vectors are embedded becomes exponential (in $k$, $O(2^k)$).
We want to find out whether there exists a lattice of sub-exponential dimension within which such shortest vectors can co-exist?
A simpler case, would be to assume that all the co-ordinates in the shortest vectors only take the value $0$ or $1$. And then try to prove whether such a lattice can exist with the above constraints?
If we could establish some sort of a lower bound on the minimum dimension of the lattice required, it would be a step forward. Also any suggestions as to which Theorems I can read that comment about the type of shortest vectors that can co-exist in a lattice?