CyclotomicField's is_isomorphic is mathematically incorrect

[rharron]

If K is a CyclotomicField, then K.is_isomorphic(L) returns true as long as L is a number field and K has an embedding in to L!

sage: K = CyclotomicField(4)
sage: N = K.extension(x^2-5, 'z')
sage: K.is_isomorphic(N)
True

Is there a reason that CyclotomicField overrides the generic version of this? I guess one could first do the quick check: if L is a CyclotomicField, then checking they are isomorphic just means checking they are both the nth cyclotomic field (I assume the n is stored somewhere easily accessible).

Component: number fields

Keywords: CyclotomicField

Author: Robert Harron

Reviewer: Francis Clarke

Merged: sage-5.10.beta1

Issue created by migration from https://trac.sagemath.org/ticket/14300

[rharron]

Author: Robert Harron

[fchapoton]

comment:2

please use the python3 syntax for raise

raise ValueError("message here")

[rharron]

comment:3

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)?

Replying to @fchapoton:

please use the python3 syntax for raise

raise ValueError("message here")

[rharron]

comment:4

Attachment: trac_14300_fix_CyclotomicField_is_isomorphic.2.patch.gz

I think that is the correct syntax, so I uploaded a new version of the patch.

[rharron]

comment:5

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

Replying to @fchapoton:

please use the python3 syntax for raise

raise ValueError("message here")

[rharron]

comment:6

Apply trac_14300_fix_CyclotomicField_is_isomorphic.2.patch

[sagetrac-fwclarke]

comment:7

I was responsible, in #3533, for the faulty code for NumberField_cyclotomic.is_isomorphic. There should have been first a check that the absolute degrees were equal. I apologise for my stupid mistake.

However the reason for having a separate method for cyclotomic fields was that it can be much faster than the generic code. Thus with

sage: C = CyclotomicField(39)
sage: K = NumberField(cyclotomic_polynomial(39), 'a')

I find that in Sage-5.8

C.is_isomorphic(K)

takes 0.684 seconds, while

C.pari_polynomial().nfisisom(K.pari_polynomial())

(which is the essential part of the generic is_isomorphic) takes 5.007 seconds. The difference is even more marked for higher degrees.

Thus I think that the only change to the existing code that is needed is to add the two extra lines:

        if self.degree() != other.absolute_degree():
            return False

Plus, of course, the new doctests.

[rharron]

comment:8

(And, also of course, the lines:

if is_CyclotomicField(other):
            return self.zeta_order() == other.zeta_order()

which are really fast.)

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:

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

Here: .is_isomorphic is my code and .is_isomorphic2 is the code you propose.

Aside from timing:

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.

So, the code I posted turns out to be more robust (though this just illustrates an issue with pari_nf).

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?

[sagetrac-fwclarke]

Reviewer: Francis Clarke

[sagetrac-fwclarke]

comment:9

Replying to @rharron:

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?

After spending some time looking at why the existing code is sometimes slow, I agree with this suggestion, so a positive review.

---

Using the fact that PARI's nfisom runs much faster when one of its arguments is a number field, rather than a polynomial, it is possible to make the generic is_isomorphic much quicker. It gets a bit complicated though, because

1. a field's pari_nf shouldn't be computed unnecessarily;
2. doing so is much quicker for a cyclotomic field than a general field of the same degree;
3. for (monic) polynomials with non-integer coefficients PARI's nfinit fails, but nfisom works.
   I have a draft patch in preparation and will post it soon.

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 K.is_isomorphic(K) can be slow). This is hardly more time-consuming than comparing the values of zero_order when both fields are cyclotomic.

[jdemeyer]

Merged: sage-5.10.beta1