#7160: comparison with quadratic number field elements needs work
-----------------------------+----------------------------------------------
Reporter: mhansen | Owner: davidloeffler
Type: defect | Status: needs_review
Priority: major | Milestone: sage-5.0
Component: number fields | Keywords: sd35
Work_issues: | Upstream: N/A
Reviewer: | Author: Mike Hansen, Burcin Erocal
Merged: | Dependencies:
-----------------------------+----------------------------------------------
Changes (by newvalueoldvalue):
* milestone: sage-4.8 => sage-5.0
* author: Mike Hansen => Mike Hansen, Burcin Erocal
Comment:
Replying to [comment:7 was]:
> 4. I feel like this is too much code that gets around a fundamental
problem or bug in number field elements in the case of the reported
problem, but leaves the underlying bug unfixed. Note that *before*
applying your patch:
{{{
sage: bool(I^2 < 0)
True
sage: (I^2).pyobject() < 0
False
}}}
>
> It seems to me that the output of both lines above should be the same,
right, but I bet pynac is evaluating the first comparison and not even
going to the pyobject level.
The first comparison is done in the `test_relation()` method of
`sage.symbolic.expression.Expression`. This converts both sides of the
relation to `CIF` and performs the comparison there.
> Similarly:
>
> {{{
> sage: bool(I^2 < SR(0))
> True
> sage: (I^2).pyobject() < SR(0).pyobject()
> False
> }}}
>
> This is because in Sage we currently have:
> {{{
> sage: K.<I> = QuadraticField(-1)
> sage: I^2 < 0
> False
> sage: I^2
> -1
> }}}
> This is, as Cremona pointed out, due to the arbitrary lexicographic
ordering rather than using the one we get on the intersection of K and R
inside embedding(K).
>
> So... it seems to me that the real problem is that the arbitrary
ordering is lame. What you've done is implemented a natural fix in one
very, very special case. Maybe that's the intention, and maybe you had
something more general before? I don't know, since you changed the patch.
Note that this lame ordering is causing problems all over symbolics since
`is_positive()` checks fail. See #10849, #10062, #10064 for examples.
> I'm guessing your more general patch changed comparison for all elements
to:
> (1) check if there is an embedding of the parent(s), and (2) if so,
use that to induce an embedding on *the* real subfield of the field(s).
That would be natural.
I attached a new patch at
attachment:trac_7160-quadratic_number_field_element_comparison.patch,
based on Mike's last patch attachment:trac_7160.patch. This changes the
comparison function of quadratic number field elements to always use the
embedding into `CC`.
Timings with the patch:
{{{
sage: K.<sqrt2> = QuadraticField(2)
sage: t = K.random_element(); t
-2*sqrt2 - 35
sage: u = K.random_element(); u
-1
sage: %timeit res = cmp(t,u)
625 loops, best of 3: 659 µs per loop
sage: u = K.random_element(); u
-2*sqrt2 - 1
sage: %timeit res = cmp(t,u)
625 loops, best of 3: 807 µs per loop
}}}
Without the patch:
{{{
sage: K.<sqrt2> = QuadraticField(2)
sage: t = -2*sqrt2 - 35
sage: u = K(-1)
sage: %timeit res = cmp(t,u)
625 loops, best of 3: 419 ns per loop
sage: u = -2*sqrt2 - 1
sage: %timeit res = cmp(t,u)
625 loops, best of 3: 419 ns per loop
}}}
So there is a significant slow down.
There are two failing doctests I need help with:
{{{
sage -t devel/sage/sage/schemes/elliptic_curves/ell_curve_isogeny.py
**********************************************************************
File "/home/burcin/sage/sage-5.0.prealpha0/devel/sage-
main/sage/schemes/elliptic_curves/ell_curve_isogeny.py", line 4361:
sage: _[0].rational_maps()
Expected:
(((-4/25*i - 3/25)*x^5 + (-4/5*i + 2/5)*x^3 + x)/(x^4 + (-4/5*i +
2/5)*x^2 + (-4/25*i - 3/25)),
((2/125*i - 11/125)*x^6*y + (64/125*i + 23/125)*x^4*y + (162/125*i -
141/125)*x^2*y + (-4/25*i - 3/25)*y)/(x^6 + (-6/5*i + 3/5)*x^4 + (-12/25*i
- 9/25)*x^2 + (2/125*i - 11/125)))
Got:
(((4/25*i + 3/25)*x^5 + (4/5*i - 2/5)*x^3 - x)/(x^4 + (-4/5*i +
2/5)*x^2 + (-4/25*i - 3/25)), ((11/125*i + 2/125)*x^6*y + (-23/125*i +
64/125)*x^4*y + (141/125*i + 162/125)*x^2*y + (3/25*i - 4/25)*y)/(x^6 +
(-6/5*i + 3/5)*x^4 + (-12/25*i - 9/25)*x^2 + (2/125*i - 11/125)))
**********************************************************************
File "/home/burcin/sage/sage-5.0.prealpha0/devel/sage-
main/sage/schemes/elliptic_curves/ell_curve_isogeny.py", line 4622:
sage: isogenies_13_0(E)[0].rational_maps()
Expected:
(((-4/169*r - 11/169)*x^13 + (-128/13*r - 456/13)*x^10 + (-1224/13*r -
2664/13)*x^7 + (-2208/13*r + 5472/13)*x^4 + (1152/13*r - 8064/13)*x)/(x^12
+ (4*r - 36)*x^9 + (-1080/13*r + 3816/13)*x^6 + (2112/13*r + 5184/13)*x^3
+ (17280/169*r - 1152/169)), ((18/2197*r - 35/2197)*x^18*y +
(-23142/2197*r + 35478/2197)*x^15*y + (-1127520/2197*r +
1559664/2197)*x^12*y + (87744/2197*r + 5992704/2197)*x^9*y +
(-6625152/2197*r + 9085824/2197)*x^6*y + (28919808/2197*r -
2239488/2197)*x^3*y + (-1990656/2197*r + 3870720/2197)*y)/(x^18 + (6*r -
54)*x^15 + (-3024/13*r + 11808/13)*x^12 + (31296/13*r - 51840/13)*x^9 +
(-487296/169*r - 2070144/169)*x^6 + (-940032/169*r - 248832/169)*x^3 +
(-1990656/2197*r + 3870720/2197)))
Got:
(((7/338*r + 23/338)*x^13 + (-164/13*r - 420/13)*x^10 + (720/13*r +
3168/13)*x^7 + (3840/13*r - 576/13)*x^4 + (4608/13*r + 2304/13)*x)/(x^12 +
(4*r + 36)*x^9 + (1080/13*r + 3816/13)*x^6 + (2112/13*r - 5184/13)*x^3 +
(-17280/169*r - 1152/169)), ((18/2197*r + 35/2197)*x^18*y + (23142/2197*r
+ 35478/2197)*x^15*y + (-1127520/2197*r - 1559664/2197)*x^12*y +
(-87744/2197*r + 5992704/2197)*x^9*y + (-6625152/2197*r -
9085824/2197)*x^6*y + (-28919808/2197*r - 2239488/2197)*x^3*y +
(-1990656/2197*r - 3870720/2197)*y)/(x^18 + (6*r + 54)*x^15 + (3024/13*r +
11808/13)*x^12 + (31296/13*r + 51840/13)*x^9 + (487296/169*r -
2070144/169)*x^6 + (-940032/169*r + 248832/169)*x^3 + (1990656/2197*r +
3870720/2197)))
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7160#comment:12>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
