Some corrections to paper HMM

  1. Due to a programming slip on my part, the example in Remarks 2 on page 130 of our paper HMM is not a counter-example after all!
    Experiments suggest that Theorem 5.1 is true for all α >1/4, but we are unable to prove this.
    We remark that the example (s1, s2, s3) = (13, 101, 187) with α = 101/400 is typical, as here
    B = 40 -7 1 μ21 = 819/1650, μ31 = 382/1650, μ21 = 13842/45339, 
        19 -8 3
         9 -3 1 
    
    while ||b2*||2 = 45339/1650 and ||b1*||2 = 1650. The proof of Theorem 5.1 breaks down for these numbers, but nevertheless, b3 = [9, -3, 1] is a (unique) shortest multiplier.
  2. Theorem 5.1 on page 129 of HMM is stated somewhat ambiguously. Strictly speaking, what we proved is that either b3 is a smallest multiplier or else any smaller multiplier is one of the 6 vectors b3 + e1b1 + e2b2, where ei = -1,0,1 and (e1,e2) ≠ (±1,0). The possibilities ||b3 ± b1|| = ||b3|| are not ruled out.
    For example: (with α = 1) and (s1, s2, s3) = (2, 2, 3). Here
    B = -1 1  0
         1 2 -2
        -1 0  1 
    
    Then b3 = [-1, 0, 1] and b3 - b1 = [0, -1, 1] are the shortest multipliers.
  3. Each of the last 4 lines of the table on page 130 contains one error:
    the sign should be changed in each second alternative.
    The table is to be interpreted as stating that at least one shortest multiplier will be of the type listed. There can be shortest multipliers not of these types.
    For example: (with α = 1) (41,43,49).
    B =  3 -4  1   μ21 = -7/26, μ31 = 1/2,
       -10 -3 11   μ32 = -2899/5931. 
         6  0 -5 
    
    Then b3 = [6, 0, -5], b3 - b1 = [3, 4, -6] and b3 + b2 = [-4, -3, 6] are the shortest multipliers.
    I give a complete classification of all possibilities for shortest vectors when α = 1, as well as a proof that there are at most 3 shortest multipliers in this case, in a manuscript.
  4. On page 131, Section 6 of our paper, we omitted to state that our matrix G(γ) is similar to one mentioned on page 156 of the book of Grötschel, Lovász and Schrijver. Although we quoted another result earlier in the chapter of that book, the one on page 156 had escaped our attention!
  5. The following correction was supplied by Wilberd van der Kallen in February 15, 2017 in response to a question communicated to me by Benjamin Hilprecht in Jan 31, 2017.

    In Reduce2(k,i) replace

    If there is a j such that ak,j0 then
        col2least j such that ak,j ≠ 0;
    else col2 ← n+1;

    with

    If there is j such that ak,j ≠ 0 then
        col2 ← least j such that ak,j ≠ 0;
        if ak,col2 < 0 then minus(k); ak ← -ak; bk ← -bk;
    else col ← n+1;

    This correction is not mentioned in the book An Introduction to the LLL Algorithm and Its Applications of Murray R. Bremner.

Last modified 1st November 2022