#14300: CyclotomicField's is_isomorphic is mathematically incorrect
-----------------------------------+----------------------------------------
Reporter: robharron | Owner: davidloeffler
Type: defect | Status: needs_work
Priority: critical | Milestone: sage-5.10
Component: number fields | Resolution:
Keywords: CyclotomicField | Work issues:
Report Upstream: N/A | Reviewers:
Authors: Robert Harron | Merged in:
Dependencies: | Stopgaps:
-----------------------------------+----------------------------------------
Comment (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?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14300#comment:8>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
