Opened 11 years ago

Last modified 4 years ago

#10017 closed defect

reduced_basis for number field multiples wrong — at Initial Version

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

Status badges

Description

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 (0)

Note: See TracTickets for help on using tickets.