Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.