Ask Your Question
1

Computing maximal orders in relative extensions

asked 2012-08-04 04:33:43 -0500

Leonhard Moosbrugger gravatar image

updated 2017-01-08 05:28:25 -0500

FrédéricC gravatar image

As part of a project, I am translating some MAGMA code to SAGE. The relevant piece of code computes the maximal order of the relative extension of Qa12, a number field of degree 20, by the polynomial y^2 - kappa12:

    subOrderK:=ext<OO | y^2-kappa12>;
    subOrderK:=AbsoluteOrder(subOrderK);
    D:=Discriminant(subOrderK);
    for p in PrimeDivisors(D) do
        subOrderK:=pMaximalOrder(subOrderK,p);
    end for;
    OOK:=subOrderK;

Here OO is the ring of integers (i.e. the maximal order) of Qa12. As I did not see a way to translate this word for word (if I am missing something, please point it out), I tried a different approach. Here is my code (in SAGE):

    L.<c> = Qa12.extension(y^2-kappa12)
    L.<alpha> = L.absolute_field()
    subOrderK = L.order(alpha)
    D = subOrderK.discriminant()
    for p in factor(D):
        subOrderK = L.maximal_order(p[0])
    OOK = subOrderK

Note that y^2-kappa12 has coefficients coerced in Qa12 and we make sure that it is indeed irreducible in Qa12 (i.e. we make sure that kappa12 is not the square of an element of Qa12). You may notice immediately that my for-loop is a rather clumsy translation of the corresponding loop in the MAGMA code. I was hoping that SAGE would "remember" the previous value of subOrderK, thus having the same effect as the MAGMA-command pMaximalOrder(subOrderK,p). However, my problem arises even earlier than that: the number computed by subOrderK.discriminant() is absurdly huge - too big, in fact, for there to be any hope to factorise it in any reasonable amount of time.

The obvious alternative of simply writing

L.<c> = Qa12.extension(y^2-kappa12)
L.<alpha> = L.absolute_field()
OOK = L.maximal_order()

is also extremely time-intensive; I have not yet seen this finish.

I was hoping someone could help either with improving my code, or with a radically different approach to the problem.

NOTE: Though I have tried to make this question understandable, if some parts remain opaque, please do say so. I'll do my best to correct it.

edit retag flag offensive close merge delete

Comments

Just as a point of information, this author has also posted the question at [stackoverflow](http://stackoverflow.com/questions/11850418/computing-maximal-orders-in-large-number-fields-with-sage).

kcrisman gravatar imagekcrisman ( 2013-05-24 07:37:02 -0500 )edit

1 answer

Sort by » oldest newest most voted
0

answered 2013-05-24 09:51:32 -0500

nbruin gravatar image

updated 2013-05-24 10:25:14 -0500

Not really an answer, but hopefully some pointers that might help you.

The capabilities for Sage in this respect are bounded by what GP/PARI provides. If you can figure out how to define an order in PARI with a given basis then you can just do the transformations manually: Given an integral basis for OO and a root c of y^2-kappa12, it's pretty straightforward to write down a ZZ-basis for the order OO[c] (assuming kappa12 is integral) and then you may be able to use that as a starting point for getting the ring of integers of OO. If PARI can do that then getting that functionality exposed in Sage would be relatively straightforward. If PARI cannot do that yet, it should probably be fixed there.

Since PARI eventually computes an LLL-reduced ZZ-basis for the ring of integers (see nf.zk), it knows how to work with arbitrary bases, so it would just be a question of getting nfmaxord started with a different basis than just a power basis. The interface of the library routine nfmaxord doesn't seem to provide the possibility, but with a bit of hacking it should be possible.

Another option that exists in MAGMA is that MaximalOrder allows an optional argument (called Discriminant) that promises that the discriminant of the maximal order to be computed only contains prime factors from the specified argument. Rather than trying to factorize the discriminant completely, it will just try to remove extraneous factors with a lazy factorization approach. In your case, including 2Discriminant(OO)Norm(kappa12) would do the trick.

Reading the documentation of nfmaxord there are several ways of doing something similar in PARI: nf_PARTIALFACT and fa. These parameters do not seem to be exposed in sage. (there is an optional argument to K.maximal_order that allows the computation of p-maximal orders, but that's not what you want).

edit flag offensive delete link more

Comments

As Nils already explained in his answer, the first line of the question's Magma code creates a better starting order (OO[sqrt(kappa12)]) than the third line of the question's Sage code (ZZ[sqrt(kappa12)]). But to start out in Sage with the same order that you start out with in Magma, you shouldn't have to use pari directly. In Sage, just use something like the following: OO = Qa12.maximal_order() bas = [L.structure()\[1\](b) for b in OO.basis()] subOrderK = L.order(bas + [alpha]) \# Instead of the last line, you can also do subOrderK = L.order(bas + [b*alpha for b in bas]) Unfortunately, for the field I tried this with, it hangs (I don't know your Qa12). And even Ctrl+C does not work. I'm reporting this as a bug.

Marco Streng gravatar imageMarco Streng ( 2013-05-26 11:59:59 -0500 )edit

groups.google.com/forum/?fromgroups#!topic/sage-devel/MpPqbjAqol4

Marco Streng gravatar imageMarco Streng ( 2013-05-26 12:39:40 -0500 )edit

Thanks both of your replies. One example of the Qa12 I ended up with is: Number Field in a with defining polynomial x^20 - 50*x^18 + 1015*x^16 - 11000*x^14 + 70255*x^12 - 134825*x^10 - 1299365*x^8 + 9691600*x^6 - 25842350*x^4 + 28129275*x^2 + 147598569 I just checked, and it seems that polred doesn't reduce that polynomial any further. If I remember correctly, the MAGMA code would take about 15-30 seconds, so it might well be that the problem was the different starting order. I'll try to see if Marco's workaround also hangs for me, or if something similar works in PARI. I'll let you know if I find anything out on the problem!

Leonhard Moosbrugger gravatar imageLeonhard Moosbrugger ( 2013-06-27 06:27:46 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2012-08-04 04:33:43 -0500

Seen: 414 times

Last updated: May 24 '13