Opened 9 years ago

Closed 2 years ago

#10544 closed defect (wontfix)

LLL reduced kernel bases are not always correct

Reported by: rbeezer Owned by: jason, was
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: linear algebra Keywords: days84
Cc: wjp Merged in:
Authors: Reviewers: Thierry Monteil
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

On 4.6.1.alpha 3:

sage: sage: E=matrix(ZZ, 5, 8,
....: [5, -23, 21, 77, -50, 8, -76, 16, 2,
....: -9, 8, 30, -19, 3, -29, 6, 4, -16, 13,
....: 53, -30, 4, -47, 9, 0, 5, -14, -24,
....: 33, -5, 47, -14, -2, 11, -9, -35, 23,
....: -5, 34, -7])
sage: sage: KK=E.right_kernel(LLL=True)
sage: sage: BB=KK.basis_matrix().change_ring(ZZ)
sage: sage: BB.is_LLL_reduced()
False
sage: sage: LL=BB.LLL()
sage: sage: LL-BB
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
[1 0 1 0 1 1 0 1]
[0 0 0 0 0 0 0 0]

I can't say for certain that this is a bug, but it does not look correct to me. This may happen about one time in twenty for random matrices of this size. Any smaller and it seemed to be quite rare. Larger and it was more frequent. Wish I had a better test case to offer.

Change History (9)

comment:1 Changed 9 years ago by rbeezer

  • Cc wjp added

comment:2 Changed 9 years ago by wjp

After discussion at days27, it seems this is an LLL parameter mismatch:

in gp:

? ??qflll
qflll(x,{flag = 0}):

   LLL algorithm applied to the columns of the matrix x.   The columns of x may
be linearly dependent.  The result is a unimodular transformation matrix T such
that  x  .T  is  an  LLL-reduced  basis  of the lattice generated by the column
vectors of x.  Note that if x is not of maximal rank T will not be square.  The
LLL parameters are (0.51,0.99),  meaning that the Gram-Schmidt coefficients for
the  final  basis satisfy mu_{i,j} <= |0.51|,  and the Lov\'{a}sz's constant is
0.99.
sage: BB.is_LLL_reduced(eta=.51)
True

comment:3 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:4 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:5 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:6 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:7 Changed 3 years ago by tmonteil

  • Keywords days84 added
  • Milestone changed from sage-6.4 to sage-duplicate/invalid/wontfix
  • Reviewers set to Thierry Monteil
  • Status changed from new to needs_review

I had a look to this as sage days 84, actually, the LLL option is not passed correctly, according to the doc, this should be passed as a string to the basis option, compare (on 7.6.beta5):

E=matrix(ZZ, 5, 8,
[5, -23, 21, 77, -50, 8, -76, 16, 2,
-9, 8, 30, -19, 3, -29, 6, 4, -16, 13,
53, -30, 4, -47, 9, 0, 5, -14, -24,
33, -5, 47, -14, -2, 11, -9, -35, 23,
-5, 34, -7])
KK=E.right_kernel(LLL=True)
BB=KK.basis_matrix().change_ring(ZZ)
BB.is_LLL_reduced()
False

with

E=matrix(ZZ, 5, 8,
[5, -23, 21, 77, -50, 8, -76, 16, 2,
-9, 8, 30, -19, 3, -29, 6, 4, -16, 13,
53, -30, 4, -47, 9, 0, 5, -14, -24,
33, -5, 47, -14, -2, 11, -9, -35, 23,
-5, 34, -7])
KK=E.right_kernel(basis='LLL')
BB=KK.basis_matrix().change_ring(ZZ)
BB.is_LLL_reduced()
True

Hence, i suggest to close this ticket as wontfix.

comment:8 Changed 3 years ago by tmonteil

  • Status changed from needs_review to positive_review

comment:9 Changed 2 years ago by embray

  • Resolution set to wontfix
  • Status changed from positive_review to closed

Closing tickets in the sage-duplicate/invalid/wontfix module with positive_review (i.e. someone has confirmed they should be closed).

Note: See TracTickets for help on using tickets.