Opened 7 years ago

Closed 7 years ago

#14300 closed defect (fixed)

CyclotomicField's is_isomorphic is mathematically incorrect

Reported by: robharron Owned by: davidloeffler
Priority: critical Milestone: sage-5.10
Component: number fields Keywords: CyclotomicField
Cc: Merged in: sage-5.10.beta1
Authors: Robert Harron Reviewers: Francis Clarke
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

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

Attachments (1)

trac_14300_fix_CyclotomicField_is_isomorphic.2.patch (2.3 KB) - added by robharron 7 years ago.

Download all attachments as: .zip

Change History (11)

comment:1 Changed 7 years ago by robharron

  • Authors set to Robert Harron
  • Status changed from new to needs_review

comment:2 follow-ups: Changed 7 years ago by chapoton

please use the python3 syntax for raise

raise ValueError("message here")

comment:3 in reply to: ↑ 2 Changed 7 years ago by robharron

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 chapoton:

please use the python3 syntax for raise

raise ValueError("message here")

comment:4 Changed 7 years ago by robharron

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

comment:5 in reply to: ↑ 2 Changed 7 years ago by robharron

(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 chapoton:

please use the python3 syntax for raise

raise ValueError("message here")

comment:6 Changed 7 years ago by robharron

Apply trac_14300_fix_CyclotomicField_is_isomorphic.2.patch

comment:7 Changed 7 years ago by fwclarke

  • Status changed from needs_review to needs_work

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.

comment:8 follow-up: Changed 7 years ago by robharron

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

comment:9 in reply to: ↑ 8 Changed 7 years ago by fwclarke

  • Reviewers set to Francis Clarke
  • Status changed from needs_work to positive_review

Replying to robharron:

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.

comment:10 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.10.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.