Opened 11 years ago

Last modified 4 years ago

#10017 closed defect

reduced_basis for number field multiples wrong — at Version 15

Reported by: schilly Owned by: davidloeffler
Priority: major Milestone: sage-6.4
Component: number fields Keywords:
Cc: Merged in:
Authors: John Cremona Reviewers:
Report Upstream: N/A Work issues:
Branch: u/cremona/10017 Commit: 8b3eb02ede88e3de6bf03cc54f8565b2a0ef3bcf
Dependencies: Stopgaps: todo

Status badges

Description (last modified by vdelecroix)

This was reported by the "report a problem" link:

The reduced_basis for number fields applies LLL to basis of the maximal order in order to get a reduced basis. The problem is that after applying LLL, it multiples the transformation matrix by the vector [1,a,a2,...], where 'a' is generator of the field - instead of using the vector it actually used for the maximal order.

How to reproduce:

x = QQ['x'].0
k = NumberField(x^6 + 2218926655879913714112*x^4 - \
32507675650290949030789018433536*x^3 + \
4923635504174417014460581055002374467948544*x^2 - \
36066074010564497464129951249279114076897746988630016*x + \
264187244046129768986806800244258952598300346857154900812365824,'a')
new_basis = k.reduced_basis()
print new_basis[0].minpoly()

This prints a crazy big polynomial. Looking a bit at what is returned it is clear that reduced_basis is multiplying the transformation matrix by the wrong vector.

To solve you just need to multiply by the vector of generators of the maximal order:

mp = pari( k.Minkowski_embedding(k.maximal_order().gens(), prec=120) )
ml = sage.libs.pari.gen.gen.qflll(mp)
T = matrix([[ZZ(y) for y in list(x)] for x in list(ml)]).transpose()
r = Matrix(O.gens())* T
for rr in r[0]:
print rr.minpoly()

This works fine.

Change History (15)

comment:1 Changed 11 years ago by fwclarke

Looks like the definition of O was omitted. The following slightly simplified code works ok for me:

sage: O = k.ring_of_integers()
sage: mp = pari( k.Minkowski_embedding(O.gens(), prec=120) )
sage: ml = sage.libs.pari.gen.gen.qflll(mp)
sage: T = ml.sage()
sage: r = vector(O.gens())*T
sage: for rr in r:
....:     rr.minpoly()

comment:2 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:3 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:4 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:5 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:6 Changed 6 years ago by jakobkroeker

  • Stopgaps set to todo

comment:7 Changed 4 years ago by cremona

While the original diagnosis is not wrong, there is a more basic problem as this smaller example shows:

sage: K.<a> = NumberField(x^3-10)
sage: ZK = K.ring_of_integers()
sage: ZK.basis()
[1/3*a^2 + 1/3*a + 1/3, a, a^2]
sage: ZK([1,2,3])
3*a^2 + 2*a + 1

Although the ring of integers is an order which knows its own Z-basis, when you construct an element of the order from an integer vector it ignores that and uses the power_basis of the field and not its integral basis.

I think the problem is in these lines of _element_constructor() (order.py lines 1142-1143):

       if not is_Element(x) or x.parent() is not self._K:
            x = self._K(x)

There appears to be a related problem in the constructor of OrderElementAbsolute? in number_field_element:

       K = order.number_field()
        NumberFieldElement_absolute.__init__(self, K, f)
        self._number_field = K

where the parameter f is not documented and there are no relevant tests, but this seems to be saying "take the data in f and construct a field element from it".

Perhaps the simplest solution is to go to those lines in order.py and insert code to handle the case where the input data is an integer vector of the right length.

comment:8 Changed 4 years ago by cremona

After doing the above "simplest solution", which did fix the x^3-10 example above, I saw that it's not the fix needed for the original which is to take the vectors output by the LLL reduction and push them into the ring of integers rather than the field. Now I get

sage: [c.minpoly() for c in new_basis]

[x - 1,
 x^6 + 3*x^5 + 258*x^4 + 511*x^3 + 3564*x^2 + 3309*x + 2347,
 x^6 - 24*x^5 + 6126*x^4 - 312664*x^3 + 5407566*x^2 - 33643572*x + 95921443,
 x^6 + 18*x^5 + 3366*x^4 + 82008*x^3 + 886962*x^2 - 840726*x + 5521647,
 x^6 + 27*x^5 + 9579*x^4 + 623358*x^3 + 5060091*x^2 - 139224285*x + 880944177,
 x^6 - 72*x^5 + 65286*x^4 - 10762768*x^3 + 473072922*x^2 - 2502686322*x + 54227921641]

which is a lot better.

Patch up when I have added doctests...

comment:9 Changed 4 years ago by cremona

  • Authors set to John Cremona
  • Branch set to u/cremona/10017
  • Commit set to 6bee3fca54bf50cfbd7a82e71d899b7ddafacb89
  • Status changed from new to needs_review

The doctest based on the original post works fine for me when run manually, but when run as a doctest something weird happens -- it takes ages and then gives an enormous python crash. I have no idea what this is but hope that a human can help before this breaks all the patchbots out there...


New commits:

6bee3fc#10017: fix construction of order elements from list, and number field reduced basis

comment:10 Changed 4 years ago by git

  • Commit changed from 6bee3fca54bf50cfbd7a82e71d899b7ddafacb89 to 5d51b3260b6bec7eacc24aca4f469ee1ba8b4572

Branch pushed to git repo; I updated commit sha1. New commits:

0000be4Merge branch 'develop' into 10017
5d51b32#10017 added 2 lines to new doctest

comment:11 Changed 4 years ago by jdemeyer

Quick comments (more might come):

  1. Replace See (:trac:`10017`):: by Check that :trac:`10017` is fixed:: or something along those lines.
  1. Replace
    sage: assert R.discriminant()==k.discriminant()
    

by

sage: R.discriminant() == k.discriminant()
True

comment:12 Changed 4 years ago by git

  • Commit changed from 5d51b3260b6bec7eacc24aca4f469ee1ba8b4572 to 8b3eb02ede88e3de6bf03cc54f8565b2a0ef3bcf

Branch pushed to git repo; I updated commit sha1. New commits:

8b3eb02#10017 minor changes to docstring

comment:13 Changed 4 years ago by jdemeyer

In this block of code:

            M = self.Minkowski_embedding(self.integral_basis(), prec=prec)
            T = pari(M).qflll().sage()
            ZK = self.ring_of_integers()
            self.__reduced_basis = [ ZK(v.list()) for v in T.columns() ]

you are assuming that self.integral_basis() corresponds to the basis chosen in ZK(v.list()). After all, that's the bug on this ticket, right? To me, this looks way too implicit. I would prefer to see the code written in such a way that you are actually using self.integral_basis() in this computation, instead of the ZK() call. I.e. something like

ZK = self.integral_basis()
reduced_basis = [sum(x * g for x, g in zip(v.list(), ZK)) for v in T.columns()]

comment:14 Changed 4 years ago by cremona

Yes, you are right, and perhaps being explicit like this is safest. I still think (do you agree?) that being able to do ZK(list) is useful and must give the linear combination of ZK's basis with coefficients from the list.

A related different point is that after computing the reduced basis, it is stored as self.__reduced_basis, but not actually used anywhere. Perhaps we should implement the ability to change the integral basis itself; but that might be too dangerous since various functions using pari directly will assume that the integral basis does not change.

Last edited 4 years ago by cremona (previous) (diff)

comment:15 Changed 4 years ago by vdelecroix

  • Description modified (diff)

(fixing exponentiation in ticket description)

Note: See TracTickets for help on using tickets.