# Given a basis set of a lattice and the normalized shortest vector of this lattice, can we solve SVP efficiently (i.e. in poly time)?

Given a basis set B (say $$m \times n$$), denote the lattice by L(B), also given a unit vector $$\vec{d} = \frac{1}{\lambda_1}\vec{u}$$, say $$\vec{u}$$ is the unique shortest vector of L(B). In other words, we know the direction of the shortest vector.

The question is: can we solve exact/approx SVP using any of the existing algorithms?

A natural idea of using binary search doesn't seem to work, because say currently, the step is testing some value $$\lambda$$, then

• if $$\lambda \cdot \vec{d} \in L(B)$$, we can be sure that $$\lambda_1 \leq \lambda$$;
• however, if $$\lambda \cdot \vec{d} \notin L(B)$$, then either $$\lambda_1 < \lambda$$ or $$\lambda_1 > \lambda$$ is possible.

Any helpful thoughts or pointers will be greatly appreciated.

Express $$\vec{d}$$ as a linear combination of the basis $$B$$, this can be done efficiently by taking projections of $$\vec{d}$$ along each of the basis vectors. Thus we will have $$\vec{d} = B \vec{x}$$ for some $$\vec{x} \in \mathbb{R}^n$$. Now find the smallest $$\lambda \in \mathbb{R}$$ such that $$\lambda \vec{x} \in \mathbb{Z}^n$$. Also it is guaranteed that there exists such a $$\lambda$$.

Suppose $$\lambda\vec{x}=(z_1,\ldots,z_n)\in\mathbb{Z}^n$$, then $$\lambda z_1^{-1}\vec{x}=(1,z_2z_1^{-1},\ldots, z_nz_1^{-1})\in\mathbb{Q}^n$$. Thus if $$\vec{x} = (x_1, \ldots, x_n)$$, then $$x_1^{-1}\vec{x}=(1,r_2,\ldots, r_n)$$ where $$r_i=z_iz_1^{-1}$$. Now if the rational $$r_i$$ is written as $$p_i/q_i$$ such that $$\mathrm{gcd}(p_i,q_i)=1$$, then we get our required $$\lambda$$ to be $$\mathrm{lcm}(q_2,\ldots, q_n)\cdot x_1^{-1}$$.

Thus given the direction of the shortest vector, SVP can be solved efficiently.

• Yes, you are right. So my question is basically about how to find such value efficiently. Jan 8, 2023 at 14:39
• I just edited my answer.
– QED
Jan 8, 2023 at 15:53
• Yeah, I can see that if the coefficients are rational numbers, this works. But in general, can we assume that? or the poly-size input (which includes the set of basis) already implies that? Jan 9, 2023 at 16:04
• The coefficients has to be rational after multiplying by $x_1^{-1}$. Can you see that?
– QED
Jan 9, 2023 at 16:29
• This is because if the first coordinate of $c_1\vec{x}$ is same as the first coordinate of $c_2\vec{x}$, then $c_1=c_2$, and in particular, $c_1 x_i = c_2 x_i$ for all $i$, i.e., every coordinate is same. Hence $r_i = x_1^{-1} x_i = \lambda z_1^{-1} x_i = z_i z_1^{-1}$, which has to be rational, even if $x_i$ is not.
– QED
Jan 10, 2023 at 3:32