Opened 7 years ago

Closed 7 years ago

# CyclotomicField's is_isomorphic is mathematically incorrect

Reported by: Owned by: robharron davidloeffler critical sage-5.10 number fields CyclotomicField sage-5.10.beta1 Robert Harron Francis Clarke N/A

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

### comment:1 Changed 7 years ago by robharron

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

### comment:2 follow-ups: ↓ 3 ↓ 5 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)?

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

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: ↓ 9 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

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.