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)
Change History (11)
comment:1 Changed 7 years ago by
- Status changed from new to needs_review
comment:2 follow-ups: ↓ 3 ↓ 5 Changed 7 years ago by
comment:3 in reply to: ↑ 2 Changed 7 years ago by
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")
Changed 7 years ago by
comment:4 Changed 7 years ago by
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
(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
Apply trac_14300_fix_CyclotomicField_is_isomorphic.2.patch
comment:7 Changed 7 years ago by
- 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
(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
- 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
- a field's
pari_nf
shouldn't be computed unnecessarily; - doing so is much quicker for a cyclotomic field than a general field of the same degree;
- for (monic) polynomials with non-integer coefficients PARI's
nfinit
fails, butnfisom
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
- Merged in set to sage-5.10.beta1
- Resolution set to fixed
- Status changed from positive_review to closed
please use the python3 syntax for raise