On Saturday, February 6, 2016 at 8:20:29 AM UTC-8, John Cremona 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.
I think that one is out of the window. Python3 itself has recognized that pretending there's a reasonable total ordering on all python objects leads to more pain than value. > 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. > No, that is not impossible. A routine that computes roots should be returning a *set*, not a list. One may decide to return a list instead of a set because that might be more efficient, but proper usage of the "roots" routine should not depend on the order of that list. The way around that is by doctesting in a way that's not sensitive to return order: sage: f = ... sage: L = f.roots(); L # random order [...] sage: sorted(L, key=str) [...] (you may want to use something more meaningful than key=str, but for doctesting it should be sufficient) I don't think there's a compelling reason why we need a total ordering by default, if specifying a key is so easy (and much clearer!) > (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. > But it does show why we cannot put an ordering on the more general classes of NumberField: if one specifies a real embedding then "<" can really have only one meaning: the induced ordering from the real embedding. This is essentially a subclass of NumberField: ReallEmbeddedNumberField (even if we don't implement it as such). But since there may be multiple real embeddings available that give incompatible orderings, we cannot make NumberField itself ordered. Otherwise we're not free to specify an ordering on the more specific RealEmbeddedNumberField anymore. (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). > > These are excellent candidates for key functions that can be made available. In addition or as alternative to David's suggestion, we can make the key functions available straight on the field, so that K=NumberField(...) L=[K.0^i for i in [0..100]] sorted(L,key=K.coefkey) sorted(L,key=K.heightkey) would work. 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! > That means their labelling is not well-defined for number fields of larger degree: sage: K.<a>=NumberField(x^3+x+1) sage: a<a^2 False sage: a^2<a False sage: sorted([a,a^2]) [a, a^2] sage: sorted([a^2,a]) [a^2, a] so at least in deciding how to resolve this issue, you don't have a legacy compatibility requirement (unless you can reverse engineer a deterministic procedure that yields the order in which the curves were originally considered and then see what python's "timsort" does with that) I would actually consider this rather grave an unfortunate consequence for LMFDB as an example why one SHOULD leave order comparison undefined unless a clear order is available, and why we should try and get rid of orderings in Sage that aren't clearly defined ASAP. -- 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.
