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:  sage6.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 
Description (last modified by )
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,a^{2},...], 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
comment:2 Changed 8 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:3 Changed 8 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:4 Changed 8 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:5 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:6 Changed 6 years ago by
 Stopgaps set to todo
comment:7 Changed 4 years ago by
While the original diagnosis is not wrong, there is a more basic problem as this smaller example shows:
sage: K.<a> = NumberField(x^310) 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 Zbasis, 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 11421143):
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
After doing the above "simplest solution", which did fix the x^310
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
 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
 Commit changed from 6bee3fca54bf50cfbd7a82e71d899b7ddafacb89 to 5d51b3260b6bec7eacc24aca4f469ee1ba8b4572
comment:11 Changed 4 years ago by
Quick comments (more might come):
 Replace
See (:trac:`10017`)::
byCheck that :trac:`10017` is fixed::
or something along those lines.
 Replace
sage: assert R.discriminant()==k.discriminant()
by
sage: R.discriminant() == k.discriminant() True
comment:12 Changed 4 years ago by
 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
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
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.
comment:15 Changed 4 years ago by
 Description modified (diff)
(fixing exponentiation in ticket description)
Looks like the definition of
O
was omitted. The following slightly simplified code works ok for me: