# Find an example of a lattice such that LLL algorithm can't find the shortest vector of the lattice, satisfying

I want to find an example of a basis of a lattice of dimension $n$ such that LLL algorithm can't find the shortest vector of the lattice, and such that the shortest vector of this lattice, say $b=c_1b_1+\cdots+c_nb_n$, has small $c_i$, i.e., $c_i \in \{-r,\ldots,r\}$ with small $r$.

Note that $b_i \in \mathbb{Z}^n$ and $c_i \in \mathbb{Z}$.

Such example must satisfy $\log_2(2(r+1)) \cdot n \leq 15$, say $n=5$ and $r=4$.

The idea here is to have a treatable value for $2^{\log_2(2(r+1)) \cdot n}$.

I can't find any lattice satisfying this.

• Given that LLL guarantees a vector within $2^{(n-1)/2}$ from optimal, and it tends to behave better than that in practice, $15$ is probably too short of a target. Increasing this limit to $25$ makes it easier to find examples. Jun 22 '16 at 1:42
• Thanks for commenting, I agree, $2^{25}$ is "treatable", but instead of 5 minutes of testing all possibilities, with 25 we have to wait 3.5 days... I will try to increase $n$ or $r$ Jun 22 '16 at 22:04

Bruteforce appears to work well enough. The following Sage script finds an instance quickly:

from sage.libs.fplll.fplll import FP_LLL
from sage.libs.fplll.fplll import gen_uniform

n = 5 # dimension
q = 16 # size of matrix entries

while True:
M = gen_uniform(n, n, q)
L = M.LLL(delta=0.999)
S = FP_LLL(L).shortest_vector(algorithm='proved')
if min([ row.norm() for row in L]) != S.norm():
break

print M
print L
print min([ row.norm() for row in L])
print S
print S.norm()


As a concrete example, the lattice (column vectors) $$L = \begin{pmatrix} 16252& 5541& 48769& 2593& 22395\\ 2404& 46418& 5335& 59631& 29390\\ 41816& 27475& 56363& 50417& 62371\\ 27419& 53783& 1412& 42344& 55983\\ 62503& 52719& 22160& 3940& 64256\\ \end{pmatrix}$$ can be reduced with LLL ($\delta = 0.999$) to $$B= \begin{pmatrix} 1855& 31849 & -6182& -5480& 16007\\ 23160& -24484 & 2259& -11807& 10586\\ 29450& -465 & 8167& 2997& -19059\\ 10069& -8429 & 24671& -21117& -18320\\ 4328& -17879 & 30280& 29190& 24708\\ \end{pmatrix}$$ Yet, none of those vectors is the shortest. The shortest vector is $$(-19381, -7964, 16504, -24114, 739),$$ which can be written as $2L_0 - L_1 - L_2 + 2L_3 - L_4$, where $L_i$ is the $i$th row of $L$. So we have $n = 5$ and $r = 2$.

• Thanks for answering, seems nice, I wanted $\delta=3/4$ but $\delta=0.999$ will surely do. Obrigado (?) Jun 23 '16 at 5:38
• I think, if L[0].norm() != S.norm(): , is enough, instead of, if min([ row.norm() for row in L]) != S.norm():
– 111
Jun 24 '16 at 8:44
• L[0] is likely, but not guaranteed, to be the shortest vector in the basis. Jun 24 '16 at 19:33