Sage: Ticket #14300: CyclotomicField's is_isomorphic is mathematically incorrect
https://trac.sagemath.org/ticket/14300
<p>
If K is a <a class="missing wiki">CyclotomicField?</a>, then K.is_isomorphic(L) returns true as long as L is a number field and K has an embedding in to L!
</p>
<pre class="wiki">sage: K = CyclotomicField(4)
sage: N = K.extension(x^2-5, 'z')
sage: K.is_isomorphic(N)
True
</pre><p>
Is there a reason that <a class="missing wiki">CyclotomicField?</a> overrides the generic version of this? I guess one could first do the quick check: if L is a <a class="missing wiki">CyclotomicField?</a>, then checking they are isomorphic just means checking they are both the nth cyclotomic field (I assume the n is stored somewhere easily accessible).
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/14300
Trac 1.1.6robharronWed, 03 Apr 2013 13:36:21 GMTstatus changed; author set
https://trac.sagemath.org/ticket/14300#comment:1
https://trac.sagemath.org/ticket/14300#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>author</strong>
set to <em>Robert Harron</em>
</li>
</ul>
TicketchapotonSun, 07 Apr 2013 19:05:00 GMT
https://trac.sagemath.org/ticket/14300#comment:2
https://trac.sagemath.org/ticket/14300#comment:2
<p>
please use the python3 syntax for raise
</p>
<pre class="wiki">raise ValueError("message here")
</pre>
TicketrobharronSun, 07 Apr 2013 19:13:58 GMT
https://trac.sagemath.org/ticket/14300#comment:3
https://trac.sagemath.org/ticket/14300#comment:3
<p>
That's what I get for copying and pasting the code from NumberField_generic. It would probably be better if I just call that code. Is the proper syntax for calling a super class's method NumberField_generic.is_isomorphic(self, other)?
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14300#comment:2" title="Comment 2">chapoton</a>:
</p>
<blockquote class="citation">
<p>
please use the python3 syntax for raise
</p>
<pre class="wiki">raise ValueError("message here")
</pre></blockquote>
TicketrobharronSun, 07 Apr 2013 21:04:36 GMTattachment set
https://trac.sagemath.org/ticket/14300
https://trac.sagemath.org/ticket/14300
<ul>
<li><strong>attachment</strong>
set to <em>trac_14300_fix_CyclotomicField_is_isomorphic.2.patch</em>
</li>
</ul>
TicketrobharronSun, 07 Apr 2013 21:05:29 GMT
https://trac.sagemath.org/ticket/14300#comment:4
https://trac.sagemath.org/ticket/14300#comment:4
<p>
I think that is the correct syntax, so I uploaded a new version of the patch.
</p>
TicketrobharronSun, 07 Apr 2013 22:16:11 GMT
https://trac.sagemath.org/ticket/14300#comment:5
https://trac.sagemath.org/ticket/14300#comment:5
<p>
(Actually, I don't think it was that I copy-pasted, rather I simply didn't change that line of code, though that's not clear from the way trac shows the diff.)
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14300#comment:2" title="Comment 2">chapoton</a>:
</p>
<blockquote class="citation">
<p>
please use the python3 syntax for raise
</p>
<pre class="wiki">raise ValueError("message here")
</pre></blockquote>
TicketrobharronSun, 07 Apr 2013 22:44:24 GMT
https://trac.sagemath.org/ticket/14300#comment:6
https://trac.sagemath.org/ticket/14300#comment:6
<p>
Apply trac_14300_fix_CyclotomicField_is_isomorphic.2.patch
</p>
TicketfwclarkeWed, 24 Apr 2013 09:59:57 GMTstatus changed
https://trac.sagemath.org/ticket/14300#comment:7
https://trac.sagemath.org/ticket/14300#comment:7
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
I was responsible, in <a class="closed ticket" href="https://trac.sagemath.org/ticket/3533" title="enhancement: [with patch, with positive review] better number fields (mostly ... (closed: fixed)">#3533</a>, for the faulty code for <code>NumberField_cyclotomic.is_isomorphic</code>. There should have been first a check that the absolute degrees were equal. I apologise for my stupid mistake.
</p>
<p>
However the reason for having a separate method for cyclotomic fields was that it can be <strong>much</strong> faster than the generic code. Thus with
</p>
<pre class="wiki">sage: C = CyclotomicField(39)
sage: K = NumberField(cyclotomic_polynomial(39), 'a')
</pre><p>
I find that in Sage-5.8
</p>
<pre class="wiki">C.is_isomorphic(K)
</pre><p>
takes 0.684 seconds, while
</p>
<pre class="wiki">C.pari_polynomial().nfisisom(K.pari_polynomial())
</pre><p>
(which is the essential part of the generic <code>is_isomorphic</code>) takes 5.007 seconds. The difference is even more marked for higher degrees.
</p>
<p>
Thus I think that the only change to the existing code that is needed is to add the two extra lines:
</p>
<pre class="wiki"> if self.degree() != other.absolute_degree():
return False
</pre><p>
Plus, of course, the new doctests.
</p>
TicketrobharronWed, 24 Apr 2013 14:36:59 GMT
https://trac.sagemath.org/ticket/14300#comment:8
https://trac.sagemath.org/ticket/14300#comment:8
<p>
(And, also of course, the lines:
</p>
<pre class="wiki">if is_CyclotomicField(other):
return self.zeta_order() == other.zeta_order()
</pre><p>
which are really fast.)
</p>
<p>
I had done some testing before posting this code and for all the examples in the documentation the code I posted was quicker than the code you're suggesting. It's looks like the timing situation is pretty complex though. For instance:
</p>
<pre class="wiki">sage: f = x^60 + x^59 - x^58 - x^53 - x^50 + 2*x^49 - x^48 + x^47 + x^45 - 2*x^44 + 16*x^43 + x^42 - x^41 - x^40 - 2*x^39 + x^38 - x^37 - 7*x^36 - x^35 - x^33 + 5*x^32 - x^31 + x^30 - 2*x^29 - x^28 + 24*x^27 + x^26 - 9*x^25 - 10*x^24 - x^23 + 5*x^22 - 6*x^21 + x^20 - 9*x^19 - x^18 + x^17 - x^16 - 7*x^15 + 4*x^14 - x^13 - x^11 - 2*x^10 - x^9 + 2*x^8 - 2*x^7 + 2*x^5 - x^4 + x^3 + 4*x^2 + 3*x - 19
sage: K77b = NumberField(f, 'a')
sage: C77 = CyclotomicField(77)
sage: timeit('C77.is_isomorphic(K77b)')
125 loops, best of 3: 3.02 ms per loop
sage: timeit('C77.is_isomorphic2(K77b)')
KeyboardInterrupt because it was taking so long
</pre><p>
Here: .is_isomorphic is my code and .is_isomorphic2 is the code you propose.
</p>
<p>
Aside from timing:
</p>
<pre class="wiki">sage: f = x^60 - x^58 + 4*x^57 - 3/5*x^55 - 2*x^54 + 3*x^53 - 1/2*x^52 - 1/5*x^51 - 16/3*x^50 + 5/4*x^49 + 1/2*x^48 + 1/4*x^47 + 2/7*x^46 + 1/2*x^45 - 1/4*x^44 - 1/3*x^43 + 9*x^42 - 3/2*x^41 - 12*x^40 + 2/33*x^39 - x^38 + 1/2*x^37 - 4*x^36 - 1/2*x^35 + 1/2*x^34 - 2*x^31 - 13*x^30 + 2*x^29 - 8/189*x^28 - 1/2*x^27 + 1/5*x^26 + 1/2*x^25 + 1/3*x^24 - x^23 - 2*x^22 + 2/5*x^21 - 3/2*x^20 + 2/3*x^19 + 1/7*x^18 - 1/3*x^17 + 23/3*x^16 + 1/4*x^15 - x^13 + 1/24*x^12 - 1/4*x^11 - 1/3*x^10 - 1/2*x^8 - 1/2*x^7 + x^6 + x^5 + 18/5*x^4 + 11*x^2 + x + 2
sage: K = NumberField(f, 'a')
sage: C = CyclotomicField(77)
sage: timeit('C.is_isomorphic(K)')
25 loops, best of 3: 8.7 ms per loop
sage: C.is_isomorphic2(K)
TypeError: Unable to coerce number field defined by non-integral polynomial to PARI.
</pre><p>
So, the code I posted turns out to be more robust (though this just illustrates an issue with pari_nf).
</p>
<p>
Since this ticket is for a mathematically incorrect output of sage it would be great to get it fixed ASAP (my functioning patch has already been sitting around for three weeks). In view of the examples above, I would propose worrying about optimizing this function in a separate ticket and (if there isn't some big problem with what I've written) accepting the current patch. How does that sound?
</p>
TicketfwclarkeSat, 27 Apr 2013 13:15:46 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/14300#comment:9
https://trac.sagemath.org/ticket/14300#comment:9
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Francis Clarke</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14300#comment:8" title="Comment 8">robharron</a>:
</p>
<blockquote class="citation">
<p>
Since this ticket is for a mathematically incorrect output of sage it would be great to get it fixed ASAP (my functioning patch has already been sitting around for three weeks). In view of the examples above, I would propose worrying about optimizing this function in a separate ticket and (if there isn't some big problem with what I've written) accepting the current patch. How does that sound?
</p>
</blockquote>
<p>
After spending some time looking at why the existing code is sometimes slow, I agree with this suggestion, so a positive review.
</p>
<hr />
<p>
Using the fact that PARI's <code>nfisom</code> runs much faster when one of its arguments is a number field, rather than a polynomial, it is possible to make the generic <code>is_isomorphic</code> much quicker. It gets a bit complicated though, because
</p>
<ol><li>a field's <code>pari_nf</code> shouldn't be computed unnecessarily;
</li><li>doing so is much quicker for a cyclotomic field than a general field of the same degree;
</li><li>for (monic) polynomials with non-integer coefficients PARI's <code>nfinit</code> fails, but <code>nfisom</code> works.
</li></ol><p>
I have a draft patch in preparation and will post it soon.
</p>
<p>
When this is done, it might be sensible to eliminate the cyclotomic version as the new code will check first whether the defining polynomials are equal (at the moment <code>K.is_isomorphic(K)</code> can be slow). This is hardly more time-consuming than comparing the values of <code>zero_order</code> when both fields are cyclotomic.
</p>
TicketjdemeyerTue, 30 Apr 2013 09:39:11 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/14300#comment:10
https://trac.sagemath.org/ticket/14300#comment:10
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-5.10.beta1</em>
</li>
</ul>
Ticket