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

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm working on the Shortest Lattice Vector Problem (SVP) for a paper that I'm currently writing. I wish to verify whether a particular structural, namely the building block property ( refer to the paper by Prof. Manindra Agrawal titled "Universal Relation"), is satisfied by the SVP.

Basically what this needs me to do is the following:

  1. Come up with a lattice basis $\mathcal{B} \in \mathcal{Z}^{n\times n}$, which is of full rank and of dimension: $n > 3$
  2. From the coefficient matrix $\mathcal{X} \in \mathcal{Z}^{n}$, of the vector $\mathcal{BX}$ in the lattice, choose any $3$ coefficients, which remain the same for all $\mathcal{BX}$.
  3. These $3$ coefficients can take a total of $8$ possible values, i.e. if the coefficients $(x_i,x_j,x_k)= (1,0,1)$ implies that $x_i$ and $x_k$ take a non-zero value and $x_j$ is zero.
  4. Now for all of the 8 possible values there should exist atleast one solution of the SVP (that is there should be a shortest lattice vector whose coefficients satisfy the required constraints) except for the case where all the three coefficients take the value 0.

The problem that I'm facing is that I'm finding it hard to come up with such a construction.

  • Could you suggest a way I could proceed in constructing such a lattice?
  • Or is it even possible to construct such a lattice basis, a possible heuristic argument would also help?
  • Would it be possible if we change the fact that $\mathcal{B} \in \mathcal{R}^{n \times n}$? If yes then how would I proceed?

PS: I had initially tried an approach (Minimum number of points required to determine lattice basis), to move in the reverse direction, that I first decided upon 7 shortest vectors and then tried to deduce the a possible satisfying lattice basis. But based on the comments on the question it seems that it is a dead end.

share|cite|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.