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:
- Come up with a lattice basis $\mathcal{B} \in \mathcal{Z}^{n\times n}$, which is of full rank and of dimension: $n > 3$
- 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}$.
- 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.
- 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 (https://mathoverflow.net/questions/139734/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.
