Closest Vector not in Lattice

96 views
Skip to first unread message

Taylor Huang

unread,
Jun 8, 2020, 5:45:34 AM6/8/20
to sage-devel
It seems to be a bug.
As shown in the figure, the computed closest vector is not in the lattice.

For copy-paste convenience, see the following.
from sage.modules.free_module_integer import IntegerLattice
L = Matrix(ZZ,[[20957228, -4966110],[ 9411844, 19625639]])
L = IntegerLattice(L)
targ = Matrix([-10663326362211/114509810943883, -453593624348888995904502033/114509810943883])
v0 = Matrix([-423434678248195, -18882583298608161305227077482])
cv = L.closest_vector(targ-v0)
print(cv in L)

bug_report.png

Taylor Huang

unread,
Jun 15, 2020, 3:28:55 AM6/15/20
to sage-devel
anyone here?

Dima Pasechnik

unread,
Jun 15, 2020, 4:05:30 AM6/15/20
to sage-devel
Yes, it looks like a bug.
I've opened https://trac.sagemath.org/ticket/29866
(a slightly simplified example, without a vector with non-integer
coefficients, is there)

On Mon, Jun 15, 2020 at 8:28 AM Taylor Huang <asd00012...@gmail.com> wrote:
>
> anyone here?
>
> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/1897d159-171a-4e26-821d-1750a224a918o%40googlegroups.com.

Taylor Huang

unread,
Jun 16, 2020, 3:52:06 AM6/16/20
to sage-devel
Hi, thanks for your reply.
I also note found that the membership check is broken as well.

from sage.modules.free_module_integer import IntegerLattice
coef = Matrix([-44429982080874270968379672793605458, 98931650854481334735580708522902113])
bMat = Matrix([[20957228, -4966110],[ 9411844, 19625639]])
L = IntegerLattice(bMat)
print(coef*bMat in L)

dim...@gmail.com 在 2020年6月15日 星期一下午4:05:30 [UTC+8] 的信中寫道:

Dima Pasechnik

unread,
Jun 16, 2020, 4:53:21 AM6/16/20
to sage-devel
On Tue, Jun 16, 2020 at 8:52 AM Taylor Huang <asd00012...@gmail.com> wrote:
>
> Hi, thanks for your reply.
> I also note found that the membership check is broken as well.
>
> from sage.modules.free_module_integer import IntegerLattice
> coef = Matrix([-44429982080874270968379672793605458, 98931650854481334735580708522902113])
> bMat = Matrix([[20957228, -4966110],[ 9411844, 19625639]])
> L = IntegerLattice(bMat)
> print(coef*bMat in L)

here is a bit of sanity check, also showing how to take a different
codepath in Sage for the membership check

from sage.modules.free_module_integer import IntegerLattice
coef = Matrix([-44429982080874270968379672793605458,
98931650854481334735580708522902113])
bMat = Matrix([[20957228, -4966110],[ 9411844, 19625639]])
L = IntegerLattice(bMat)
coef*bMat in L # prints false
bMatGAP=libgap(bMat)
v=libgap(coef*bMat)[0]
sol=libgap.SolutionIntMat(bMatGAP,v); sol # prints
# [ -423434671769860, -18882583298608161305225815339 ]
vector(sol.sage())*bMat==vector(coef*bMat) # sanity check - prints True

I've updated the ticket, and made it blocker.
>
> dim...@gmail.com 在 2020年6月15日 星期一下午4:05:30 [UTC+8] 的信中寫道:
>>
>> Yes, it looks like a bug.
>> I've opened https://trac.sagemath.org/ticket/29866
>> (a slightly simplified example, without a vector with non-integer
>> coefficients, is there)
>>
>> On Mon, Jun 15, 2020 at 8:28 AM Taylor Huang <asd00012...@gmail.com> wrote:
>> >
>> > anyone here?
>> >
>> > --
>> > You received this message because you are subscribed to the Google Groups "sage-devel" group.
>> > To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
>> > To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/1897d159-171a-4e26-821d-1750a224a918o%40googlegroups.com.
>
> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
Reply all
Reply to author
Forward
0 new messages