On Sat, Feb 6, 2016 at 11:19 AM, John Cremona <john.crem...@gmail.com>
wrote:
> Thanks for the replies and suggestions. I am not sure what is the
> best thing to do. I can see three different needs here:
>
> (1) Any deterministic total order for python sorting to be possible
> and consistent. For example, a function which returns the roots of a
> polynomial over a number field *must* return these sorted into an
> order that is not going to change if (for instance) the root-finding
> algorithm changes. Otherwise getting any doctests to work
> consistently would be impossible.
>
> (2) The mathematical total order which comes with any embedding into
> RR. This is not very well defined though since there may be more than
> one embedding, or none; and some number fields define a "natural"
> embedding by default, which can be overruled:
>
> sage: K.<a> = NumberField(x^2-2)
> sage: a>0
> True
> sage: K.<a> = NumberField(x^2-2, embedding=-1.4)
> sage: a>0
> False
>
> There has been previous discussion about this but it is *not* what I
> need, since I need something which applies to all fields, including
> totally complex ones.
>
> (3) Some natural total ordering with some other nice mathematical
> features, preferably independent of any arbitrary choices such as
> choice of field generator or embedding into RR or CC. (Without this
> requirement, the first could be achieved for absolute number fields by
> taking the coefficients with respect to the power basis with which
> every such field in Sage comes equipped.)
>
> Two ideas for this, neither of which is total without some extra
> "artificial" tie-breaking:
>
> (a) first sort by the coefficient vector of a minimal polynomial,
> scaled to be integral and primitive and with positive leading
> coefficient (to make it unique, not even depending on the parent
> number field). This is pretty good and canonical, but of course it
> does not distinguish between conjugates. Perhaps there is no
> canonical way to distinguish conjugates; if so the tie-break needs to
> be specified rather carefully.
>
> (b) first sort by height. One advantage over (a) is that number field
> elements which "look small" will probably come before those which look
> larger, but again there will need to be tie breaks, since again
> conjugates have the same height (and more? I forget).
>
> ---
>
> Here is one reason I need this. I want to sort the elliptic curves in
> an isogeny class, in order to label them for the LMFDB. My current
> way to do this involves sorting the j-invariants since it is almost
> always true that the different isomorphism classes in an isogeny class
> have distinct j-invariants (the only exception being curves with CM
> but not rational CM by some discriminant d<0, where the d-twist is not
> isomorphic but is isogenous). I like that, since it does not depend
> on the chosen (Weierstrass) model. And I have been using it (the
> LMFDB today has 318906 curves in it defined over number fields other
> than Q, and their labels - within each isogeny class -- are based on
> how Sage orders their j-invariants. For some reason I thought that
> sorting was based on some thought-out principal, hence this thread!
>
These all seem like reasonable orders; conversely, there doesn't seem to
be a single choice that works for all situations. Here's an idea.
Let's implement a sort_key class in sage.arith (for example). It could take
an algorithm argument for its constructor, allowing the user to choose
between
different comparison methods. With no argument, it would just use the
standard cmp (or richcmp) on elements. But with this in place, we could
start deprecating those default comparisons that aren't mathematically
very well defined.
Using it would look something like this:
L.sort(key=sage.arith.sort_key('minpoly'))
Thoughts?
David
> John
>
> On 5 February 2016 at 17:29, Nils Bruin <nbr...@sfu.ca> wrote:
> > On Friday, February 5, 2016 at 4:05:22 AM UTC-8, John Cremona wrote:
> >>
> >> Understood. I thought that a total order was implemented for number
> >> field elements, but looking in the code I could not even find the
> >> relevant _cmp_ function!
> >
> >
> > It's there, but indeed it doesn't implement a total order:
> >
> > sage: k.<a>=NumberField(x^3+x+1)
> > sage: a._cmp_??
> > Source:
> > cpdef int _cmp_(left, sage.structure.element.Element right) except
> -2:
> > cdef NumberFieldElement _right = right
> > return not (ZZX_equal(left.__numerator, _right.__numerator) and
> > ZZ_equal(left.__denominator, _right.__denominator))
> >
> > so it only tests if equality holds (for quadratic fields, the situation
> is
> > different. There seems to be a lex order there (wrt whatever basis is
> used).
> >
> > The real problem here is of course that we're getting inconsistent
> results
> > instead of an error. With an error you would have known immediately to
> use
> > an appropriate "key".
> >
> > "_richcmp_" does have enough information to throw an error, but it
> prefers
> > to punt to _cmp_. I think we need to move to a "_richcmp_" only
> environment
> > eventually. In order to so gradually perhaps we can do something like:
> >
> > 1) rewrite _richcmp_ to try the "<,=,>" etc. in preference to calling
> _cmp_
> > 2) devise a way to allow objects to indicate that the result from
> "<,=,>"
> > is authoritative and that _cmp_ should not be tried
> > 3) start removing _cmp_ methods
> >
> > [I'm not sure 2 is necessary or will make a real difference.
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "sage-nt" group.
> > To unsubscribe from this group and stop receiving emails from it, send an
> > email to sage-nt+unsubscr...@googlegroups.com.
> > To post to this group, send email to sage...@googlegroups.com.
> > Visit this group at https://groups.google.com/group/sage-nt.
> >
> > For more options, visit https://groups.google.com/d/optout.
>
> --
> You received this message because you are subscribed to the Google Groups
> "sage-nt" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sage-nt+unsubscr...@googlegroups.com.
> To post to this group, send an email to sage...@googlegroups.com.
> Visit this group at https://groups.google.com/group/sage-nt.
> For more options, visit https://groups.google.com/d/optout.
>
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
