From: nikl@mathematik.tu-muenchen.de (Gerhard Niklasch) Newsgroups: sci.math Subject: Re: Looking for failures of the LLL algorithm Date: 17 Sep 1996 15:06:59 GMT In article <51bqa0$71u@newsroom.gsfc.nasa.gov>, nsinger@eos.hitc.com (Nick Singer) writes: [...] |> |> I am seeking examples of bases which LLL cannot improve upon, but which do |> not contain the shortest nonzero vector(s) in the lattice. Obviously, the |> lower the dimension of your basis, the better your example is. It would |> also be nice if your basis vectors were actually in Z^n (rather than R^n), |> but that's not necessary. |> |> Can anyone supply an example? See M. Pohst and H. Zassenhaus, Algorithmic Algebraic Number Theory, Cambridge Univ. Press 1989, section 3.3, p.202, where a rather extreme family of examples is constructed. It uses rational coordinates and the standard inner product. I'll try to transcribe it in plain text. To get something interesting, let n > 2. Let b_ij be the i-th coordinate of the j-th lattice basis vector. Give them the following values: b_ij = 0 for j < i, \ = (sqrt(3)/2)^(i-1) for j = i, } 1 <= i <= n . = (1/2)(sqrt(3)/2)^(i-1) for j > i / Then for 2 <= k <= n , the first k basis vectors form a LLL-reduced basis of the rank k sublattice spanned by them, and the shortest nonzero vectors of these sublattices have length (sqrt(3)/2)^(k-2) . In particular, the shortest length for the whole lattice is (sqrt(3)/2)^(n-2), whereas the shortest basis vector -- the first one -- has length (sqrt(3)/2) . Note that the 3/4 in the Lovasz condition can be replaced by anything strictly larger than 1/4 and strictly less than 1; if you pick a value close to 1, you'll get better reduced bases (and a sharper estimate for the minimal length) but the computation will take longer. (More about this in H. Cohen, A Course in Computational Algebraic Number Theory, Springer Grad. Texts in Math. 138, section 2.6.1.) On the next few pages, P&Z also give an explicit example of a sublattice of Z^n in dimension 20 where a basis of short vectors is made worse by applying LLL. The original references are an institute report from the Univ. of Cologne and a diploma thesis from U Duesseldorf (under Pohst), so it probably won't help you much if I repeat them here. Enjoy, Gerhard -- * Gerhard Niklasch *** Some or all of the con- * http://hasse.mathematik.tu-muenchen.de/~nikl/ ******* tents of the above mes- * sage may, in certain countries, be legally considered unsuitable for consump- * tion by children under the age of 18. Me transmitte sursum, Caledoni... :^/ ============================================================================== From: nsinger@eos.hitc.com (Nick Singer) Newsgroups: sci.math Subject: Re: Looking for failures of the LLL algorithm Date: 18 Sep 1996 12:01:21 GMT In article <51meqj$kip@sparcserver.lrz-muenchen.de>, nikl@mathematik.tu-muenchen.de says... [previous article reprinted, deleted by djr] If I interpret your matrix correctly, for n=3 it looks like [1 1/2 1/2 ] [0 sqrt(3)/2 sqrt(3)/4] [0 0 3/4 ]. Each column has length 1. The orthogonal basis of b^*'s is [1 0 0 ] [0 sqrt(3)/2 0 ] [0 0 3/4], with obvious lengths. Then mu_{2,1}=1/2, mu_{3,1}=1/2, and mu_{3,2}=(3/8)/(3/4)=1/2. And the Lovasz conditions are met. So this basis *is* LLL-reduced. But we would take column_2 - column_3 = [ 0 ] [sqrt(3)/4] [ -3/4 ], which has length sqrt(3)/2, as our shortest vector. What this example shows me is that it's possible to have an LLL-reduced basis which could be further reduced by using a Z-linear combination of just 2 basis vectors. That's a sad state of affairs. So now I pose the question I should have asked the first time: can anyone come up with an LLL-reduced basis which cannot be further reduced by using a Z-linear combination of 2 vectors but which *can* be reduced by a more complicated Z-linear combination? Suppose we forget LLL entirely and just ask it this way: can anyone come up with a basis which cannot be further reduced by using a Z-linear combination of 2 vectors but which *can* be reduced by a more complicated Z-linear combination? TIA, Nick ============================================================================== Date: Tue, 24 Sep 1996 14:21:58 -0400 (EDT) From: nsinger@eos.hitc.com (Nick Singer) Subject: Looking for failures of the LLL algorithm To: rusin@math.niu.edu, nikl@pchelwig1.mathematik.tu-muenchen.de Thank you for helping. The questions were: (1) Can you come up with an LLL-reduced basis which cannot be further reduced by using a Z-linear combination of 2 vectors but which *can* be reduced by a more complicated Z-linear combination? (2) Suppose we forget LLL entirely and just ask it this way: can you come up with *any* basis which cannot be further reduced by using a Z-linear combination of 2 vectors but which *can* be reduced by a more complicated Z-linear combination? (3) Is a basis which cannot be further reduced by using a Z-linear combination of 2 vectors necessarily LLL-reduced (if appropriately ordered)? I can now answer questions 2 & 3, but not the first. Thanks to Peter L. Montgomery for the suggestion. Let the matrix of basis (column) vectors be b_1 = (1,1,-3)^T, b_2 = (1,-3,1)^T, b_3 = (-3,1,1)^T. Then we have b_i dot b_j = -5 for i<>j = 11 for i=j. Hence no 2 vectors can be combined to produce a shorter vector, since |-5/11| < 1/2. But b_1 + b_2 + b_3 = (-1,-1,-1)^T, which *is* shorter. This completes the answer to question 2 ("yes"). Unfortunately, the b_i's are not LLL-reduced. The Gram-Schmidt orthogonalized vectors are b_1^* = b_1 = (1, 1, -3)^T, b_2^* = b_2 + (5/11) b_1^* = (16/11, -28/11, -4/11)^T, b_3^* = b_3 + (5/11) b_1^* + (5/6)b_2^* = (-4/3, -2/3, -2/3)^T. So mu_{2,1} = -5/11, mu_{3,1} = -5/11, but mu_{3,2} = -5/6. This completes the answer to question 3 ("no"). Nick