Consistency of comparison of finite field elements

[Simon King]

Hi!

"Most" finite fields are not ordered fields, of course. Nevertheless,
cmp should return an answer on pairs of finite field elements, and it
would seem nice to have at least a small amount of consistency between
the different fields. Unfortunately,
sage: K = GF(2^10,'q')
sage: K(0)<K(1)
True
sage: K = GF(2^100,'q')
sage: K(0)<K(1)
False

Similarly, there is an inconsistency of comparison of matrices over
finite fields. Over some fields, it seems that a smaller index of a
pivot means that the matrix is smaller:
sage: K = GF(2)
sage: Matrix(K,[[0,1,0]]) < Matrix(K,[[0,0,1]])
True
Over other fields, it is different:
sage: K = GF(3)
sage: Matrix(K,[[0,1,0]]) < Matrix(K,[[0,0,1]])
False
even though comparison of elements with zero is consistent, for GF(2)
and GF(3):
sage: K = GF(2)
sage: K(0)<K(1)
True
sage: K = GF(3)
sage: K(0)<K(1)
True

Do you think it is reasonable and possible to try and introduce some
conventions that make the behaviour of comparison a bit more
predictable?

Best regards,
Simon

[Martin Albrecht]

Hi,

On Thursday 28 Jun 2012, Simon King wrote:
> Hi!
>
> "Most" finite fields are not ordered fields, of course. Nevertheless,
> cmp should return an answer on pairs of finite field elements, and it
> would seem nice to have at least a small amount of consistency between
> the different fields. Unfortunately,
> sage: K = GF(2^10,'q')
> sage: K(0)<K(1)
> True
> sage: K = GF(2^100,'q')
> sage: K(0)<K(1)
> False

I agree that this should be True ... mhh, I wrote this class so I should have
made it so then.

> Similarly, there is an inconsistency of comparison of matrices over
> finite fields. Over some fields, it seems that a smaller index of a
> pivot means that the matrix is smaller:
> sage: K = GF(2)
> sage: Matrix(K,[[0,1,0]]) < Matrix(K,[[0,0,1]])
> True
> Over other fields, it is different:
> sage: K = GF(3)
> sage: Matrix(K,[[0,1,0]]) < Matrix(K,[[0,0,1]])
> False

It's not pivots (i.e., no non-trivial computation is run) but simply
lexicographical comparision.

> Do you think it is reasonable and possible to try and introduce some
> conventions that make the behaviour of comparison a bit more
> predictable?

Yep, I vote for: take the most trivial integer representation of the finite
field and order according to this.

GF(p): order integers < p
GF(p^e): order the integers c_i*p^i where c_i are the coefficients in
polynomial representations

Cheers,
Martin

--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF
_www: http://martinralbrecht.wordpress.com/
_jab: martinr...@jabber.ccc.de

[Simon King]

Hi Martin,

On 2012-06-28, Martin Albrecht <martinr...@googlemail.com> wrote:
>> sage: K = GF(2^100,'q')
>> sage: K(0)<K(1)
>> False
>
> I agree that this should be True ... mhh, I wrote this class so I should have
> made it so then.

Oops :)

>> Similarly, there is an inconsistency of comparison of matrices over
>> finite fields. Over some fields, it seems that a smaller index of a
>> pivot means that the matrix is smaller:
>> sage: K = GF(2)
>> sage: Matrix(K,[[0,1,0]]) < Matrix(K,[[0,0,1]])
>> True
>> Over other fields, it is different:
>> sage: K = GF(3)
>> sage: Matrix(K,[[0,1,0]]) < Matrix(K,[[0,0,1]])
>> False
>
> It's not pivots (i.e., no non-trivial computation is run)

Yes, by "abuse of notion", I meant the "first nonzero coefficient".

> but simply
> lexicographical comparision.

Exactly this is what I want: Lexicographic ordering, or negative lexicographic
ordering, consistently for matrices over any field. However, ordering is
different for matrices over GF(2) and over GF(3). Anyway, I'd be happy
to review a patch...

Best regards,
Simon

[Simon King]

Hi!

Apparently we use three essentially different ways of comparing
matrices:

sage: def test(K):
....: M1 = Matrix(K,[[1,0,0]])
....: M2 = Matrix(K,[[0,1,0]])
....: M3 = Matrix(K,[[0,1,1]])
....: M4 = Matrix(K,[[0,0,1]])
....: L = [M1,M2,M3,M4]
....: L.sort()
....: return L
....:

First group: Matrices over not too big fields of characteristic 2
sage: K = GF(2)
sage: test(K)
[[1 0 0], [0 1 0], [0 0 1], [0 1 1]]
sage: K = GF(4,'z')
sage: test(K)
[[1 0 0], [0 1 0], [0 0 1], [0 1 1]]

sage: K = GF(2^10,'q')

sage: test(K)
[[1 0 0], [0 1 0], [0 0 1], [0 1 1]]

Second group: Matrices over big finite fields of characteristic 2

sage: K = GF(2^100,'q')

sage: test(K)
[[1 0 0], [0 1 0], [0 1 1], [0 0 1]]

Third group: Matrices over all other rings
sage: K = GF(3)
sage: test(K)
[[0 0 1], [0 1 0], [0 1 1], [1 0 0]]
sage: K = GF(9,'z')
sage: test(K)
[[0 0 1], [0 1 0], [0 1 1], [1 0 0]]
sage: K = GF(3^100,'q')
sage: test(K)
[[0 0 1], [0 1 0], [0 1 1], [1 0 0]]
sage: K = QQ
sage: test(K)
[[0 0 1], [0 1 0], [0 1 1], [1 0 0]]
sage: K = ZZ
sage: test(K)
[[0 0 1], [0 1 0], [0 1 1], [1 0 0]]
sage: K.<x> = GF(2)[]
sage: test(K)
[[0 0 1], [0 1 0], [0 1 1], [1 0 0]]
sage: K.<x> = GF(3)[]
sage: test(K)
[[0 0 1], [0 1 0], [0 1 1], [1 0 0]]
sage: K.<x> = GF(4,'z')[]
sage: test(K)
[[0 0 1], [0 1 0], [0 1 1], [1 0 0]]
sage: K.<x> = GF(2^100,'z')[]
sage: test(K)
[[0 0 1], [0 1 0], [0 1 1], [1 0 0]]

I have opened trac ticket #13179 for the matrix comparison, and #13180
for comparison of elements of finite fields (or more precisely:
comparison of elements of big finite fields of characteristic 2, because
all other cases seem consistent).

Cheers,
Simon