ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 27 Jun 2013 13:27:46 +0200Computing maximal orders in relative extensionshttps://ask.sagemath.org/question/9203/computing-maximal-orders-in-relative-extensions/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. Sat, 04 Aug 2012 11:33:43 +0200https://ask.sagemath.org/question/9203/computing-maximal-orders-in-relative-extensions/Comment by kcrisman for <p>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 <code>Qa12</code>, a number field of degree 20, by the polynomial <code>y^2 - kappa12</code>:</p>
<pre><code> 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;
</code></pre>
<p>Here <code>OO</code> is the ring of integers (i.e. the maximal order) of <code>Qa12</code>.
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):</p>
<pre><code> 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
</code></pre>
<p>Note that <code>y^2-kappa12</code> has coefficients coerced in <code>Qa12</code> and we make sure that it is indeed irreducible in <code>Qa12</code> (i.e. we make sure that <code>kappa12</code> is not the square of an element of <code>Qa12</code>).
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 <code>subOrderK</code>, thus having the same effect as the MAGMA-command <code>pMaximalOrder(subOrderK,p)</code>. However, my problem arises even earlier than that:
the number computed by <code>subOrderK.discriminant()</code> is absurdly huge - too big, in fact, for there to be any hope to factorise it in any reasonable amount of time. </p>
<p>The obvious alternative of simply writing</p>
<pre><code>L.<c> = Qa12.extension(y^2-kappa12)
L.<alpha> = L.absolute_field()
OOK = L.maximal_order()
</code></pre>
<p>is also extremely time-intensive; I have not yet seen this finish. </p>
<p>I was hoping someone could help either with improving my code, or with a radically different approach to the problem. </p>
<p>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. </p>
https://ask.sagemath.org/question/9203/computing-maximal-orders-in-relative-extensions/?comment=17645#post-id-17645Just 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).Fri, 24 May 2013 14:37:02 +0200https://ask.sagemath.org/question/9203/computing-maximal-orders-in-relative-extensions/?comment=17645#post-id-17645Answer by nbruin for <p>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 <code>Qa12</code>, a number field of degree 20, by the polynomial <code>y^2 - kappa12</code>:</p>
<pre><code> 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;
</code></pre>
<p>Here <code>OO</code> is the ring of integers (i.e. the maximal order) of <code>Qa12</code>.
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):</p>
<pre><code> 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
</code></pre>
<p>Note that <code>y^2-kappa12</code> has coefficients coerced in <code>Qa12</code> and we make sure that it is indeed irreducible in <code>Qa12</code> (i.e. we make sure that <code>kappa12</code> is not the square of an element of <code>Qa12</code>).
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 <code>subOrderK</code>, thus having the same effect as the MAGMA-command <code>pMaximalOrder(subOrderK,p)</code>. However, my problem arises even earlier than that:
the number computed by <code>subOrderK.discriminant()</code> is absurdly huge - too big, in fact, for there to be any hope to factorise it in any reasonable amount of time. </p>
<p>The obvious alternative of simply writing</p>
<pre><code>L.<c> = Qa12.extension(y^2-kappa12)
L.<alpha> = L.absolute_field()
OOK = L.maximal_order()
</code></pre>
<p>is also extremely time-intensive; I have not yet seen this finish. </p>
<p>I was hoping someone could help either with improving my code, or with a radically different approach to the problem. </p>
<p>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. </p>
https://ask.sagemath.org/question/9203/computing-maximal-orders-in-relative-extensions/?answer=14968#post-id-14968Not 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 2*Discriminant(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).Fri, 24 May 2013 16:51:32 +0200https://ask.sagemath.org/question/9203/computing-maximal-orders-in-relative-extensions/?answer=14968#post-id-14968Comment by Marco Streng for <p>Not really an answer, but hopefully some pointers that might help you.</p>
<p>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.</p>
<p>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 <code>nfmaxord</code> started with a different basis than just a power basis. The interface of the library routine <code>nfmaxord</code> doesn't seem to provide the possibility, but with a bit of hacking it should be possible.</p>
<p>Another option that exists in MAGMA is that <code>MaximalOrder</code> allows an optional argument (called <code>Discriminant</code>) 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 2<em>Discriminant(OO)</em>Norm(kappa12) would do the trick.</p>
<p>Reading the documentation of <code>nfmaxord</code> there are several ways of doing something similar in PARI: <code>nf_PARTIALFACT</code> and <code>fa</code>. These parameters do not seem to be exposed in sage. (there is an optional argument to <code>K.maximal_order</code> that allows the computation of p-maximal orders, but that's not what you want).</p>
https://ask.sagemath.org/question/9203/computing-maximal-orders-in-relative-extensions/?comment=17642#post-id-17642groups.google.com/forum/?fromgroups#!topic/sage-devel/MpPqbjAqol4Sun, 26 May 2013 19:39:40 +0200https://ask.sagemath.org/question/9203/computing-maximal-orders-in-relative-extensions/?comment=17642#post-id-17642Comment by Marco Streng for <p>Not really an answer, but hopefully some pointers that might help you.</p>
<p>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.</p>
<p>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 <code>nfmaxord</code> started with a different basis than just a power basis. The interface of the library routine <code>nfmaxord</code> doesn't seem to provide the possibility, but with a bit of hacking it should be possible.</p>
<p>Another option that exists in MAGMA is that <code>MaximalOrder</code> allows an optional argument (called <code>Discriminant</code>) 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 2<em>Discriminant(OO)</em>Norm(kappa12) would do the trick.</p>
<p>Reading the documentation of <code>nfmaxord</code> there are several ways of doing something similar in PARI: <code>nf_PARTIALFACT</code> and <code>fa</code>. These parameters do not seem to be exposed in sage. (there is an optional argument to <code>K.maximal_order</code> that allows the computation of p-maximal orders, but that's not what you want).</p>
https://ask.sagemath.org/question/9203/computing-maximal-orders-in-relative-extensions/?comment=17643#post-id-17643As 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.
Sun, 26 May 2013 18:59:59 +0200https://ask.sagemath.org/question/9203/computing-maximal-orders-in-relative-extensions/?comment=17643#post-id-17643Comment by Leonhard Moosbrugger for <p>Not really an answer, but hopefully some pointers that might help you.</p>
<p>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.</p>
<p>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 <code>nfmaxord</code> started with a different basis than just a power basis. The interface of the library routine <code>nfmaxord</code> doesn't seem to provide the possibility, but with a bit of hacking it should be possible.</p>
<p>Another option that exists in MAGMA is that <code>MaximalOrder</code> allows an optional argument (called <code>Discriminant</code>) 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 2<em>Discriminant(OO)</em>Norm(kappa12) would do the trick.</p>
<p>Reading the documentation of <code>nfmaxord</code> there are several ways of doing something similar in PARI: <code>nf_PARTIALFACT</code> and <code>fa</code>. These parameters do not seem to be exposed in sage. (there is an optional argument to <code>K.maximal_order</code> that allows the computation of p-maximal orders, but that's not what you want).</p>
https://ask.sagemath.org/question/9203/computing-maximal-orders-in-relative-extensions/?comment=17442#post-id-17442Thanks 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!Thu, 27 Jun 2013 13:27:46 +0200https://ask.sagemath.org/question/9203/computing-maximal-orders-in-relative-extensions/?comment=17442#post-id-17442