ordering number field elements

[John Cremona]

Elements of number fields currently have no custom cmp() function
which means that x>y is always True and x<y is always False when x!=y.

We need to be able to sort lists of number field elements properly,
which requires implementing this.

I suggest something like

if x.parent()==y.parent(): return cmp(list(x),list(y))
else: return cmp(x.parent(),y.parent())

Would that work ok? in practice people would most often sort elements
of the same field of course.

John

[Nick Alexander]

On 22-May-09, at 4:23 AM, John Cremona wrote:

>
> Elements of number fields currently have no custom cmp() function
> which means that x>y is always True and x<y is always False when x!=y.

Really? I don't understand how we always get roots in the same order
in that case.

> We need to be able to sort lists of number field elements properly,
> which requires implementing this.
>
> I suggest something like
>
> if x.parent()==y.parent(): return cmp(list(x),list(y))
> else: return cmp(x.parent(),y.parent())

+1

Nick

[John Cremona]

2009/5/22 Nick Alexander <ncale...@gmail.com>:

>
>
> On 22-May-09, at 4:23 AM, John Cremona wrote:
>
>>
>> Elements of number fields currently have no custom cmp() function
>> which means that x>y is always True and x<y is always False when x!=y.
>
> Really? I don't understand how we always get roots in the same order
> in that case.

That is a mystery. Perhaps the order in which the roots are produced
is not so random. I was hoping that someone would confirm my claim!

[N. Bruin]

On May 22, 4:23 am, John Cremona <john.crem...@gmail.com> wrote:
> Elements of number fields currently have no custom cmp() function
> which means that x>y is always True and x<y is always False when x!=y.
>
> We need to be able to sort lists of number field elements properly,
> which requires implementing this.

Do we? Unlikely comparisons have been discussed before. Python 3.0
returns TypeErrors on many comparisons, e.g. Python complex numbers do
not allow comparison. Hence, I don't think there is any pressure from
the language environment in sage to make all objects comparable. There
is not a very good mathematical reason to do it either, unless you
are considering a special class of number fields with a fixed real
embedding.

To get the effect you are describing above (roughly), one could do

sorted(L,key=list)

which is both short and requires people to acknowledge that they are
making a (necessary) choice about how L is supposed to be sorted. I
would think explicit is better than implicit for this too.

Is the main reason to force things like roots to produce deterministic
output to facilitate doctesting? Would it be bad to put the sort
command in the doctest?

[John Cremona]

2009/5/22 N. Bruin <nbr...@sfu.ca>:

>
> On May 22, 4:23 am, John Cremona <john.crem...@gmail.com> wrote:
>> Elements of number fields currently have no custom cmp() function
>> which means that x>y is always True and x<y is always False when x!=y.
>>
>> We need to be able to sort lists of number field elements properly,
>> which requires implementing this.
>
> Do we? Unlikely comparisons have been discussed before. Python 3.0
> returns TypeErrors on many comparisons, e.g. Python complex numbers do
> not allow comparison. Hence, I don't think there is any pressure from
> the language environment in sage to make all objects comparable. There
> is not a very good mathematical reason to do it either,  unless you
> are considering a special class of number fields with a fixed real
> embedding.

I am not thinking about a mathematically sensible sorting, i.e. not a
partial order in the mathematical sense. I actually want sorted lists
for implementing modular symbols where it is important to be able to
look things up quickly.

If that can be done (deterministically and fast) some other way, I
would be happy.

>
> To get the effect you are describing above (roughly), one could do
>
> sorted(L,key=list)

That is neat; my python knowledge has just expanded a bit!

>
> which is both short and requires people to acknowledge that they are
> making a (necessary) choice about how L is supposed to be sorted. I
> would think explicit is better than implicit for this too.
>
> Is the main reason to force things like roots to produce deterministic
> output to facilitate doctesting? Would it be bad to put the sort
> command in the doctest?

That is very sneaky!

John

>
> >
>

[William Stein]

2009/5/22 John Cremona <john.c...@gmail.com>:

>
> 2009/5/22 N. Bruin <nbr...@sfu.ca>:
>>
>> On May 22, 4:23 am, John Cremona <john.crem...@gmail.com> wrote:
>>> Elements of number fields currently have no custom cmp() function
>>> which means that x>y is always True and x<y is always False when x!=y.
>>>
>>> We need to be able to sort lists of number field elements properly,
>>> which requires implementing this.
>>
>> Do we? Unlikely comparisons have been discussed before. Python 3.0
>> returns TypeErrors on many comparisons, e.g. Python complex numbers do
>> not allow comparison. Hence, I don't think there is any pressure from
>> the language environment in sage to make all objects comparable. There
>> is not a very good mathematical reason to do it either,  unless you
>> are considering a special class of number fields with a fixed real
>> embedding.
>
> I am not thinking about a mathematically sensible sorting, i.e. not a
> partial order in the mathematical sense.  I actually want sorted lists
> for implementing modular symbols where it is important to be able to
> look things up quickly.
>
> If that can be done (deterministically and fast) some other way, I
> would be happy.

Some notes: In sage-3.4.2, number field elements do not even have a
sensible hash -- it is just some default hash inherited from Element
(?), which is "hash of the string representation". If you fix this by
defining __hash__ (which I expect you did), then because of how Cython
works, the cmp code will be deactivated unless one explicitly defines
__richcmp__. Anyways, in sage-4.0.rc0, number field elements *do*
have a proper hash function (=the hash of the defining polynomial),
since I had to implement this as part of the Pynac switch.

William

>
>>
>> To get the effect you are describing above (roughly), one could do
>>
>> sorted(L,key=list)
>
> That is neat;  my python knowledge has just expanded a bit!
>
>>
>> which is both short and requires people to acknowledge that they are
>> making a (necessary) choice about how L is supposed to be sorted. I
>> would think explicit is better than implicit for this too.
>>
>> Is the main reason to force things like roots to produce deterministic
>> output to facilitate doctesting? Would it be bad to put the sort
>> command in the doctest?
>
> That is very sneaky!
>
> John
>
>>
>> >
>>
>
> >
>

--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org

[David Roe]

Another thing to note if you're using sorted lists is the python module bisect.  Try
sage: import bisect
sage: bisect.<tab>
David