Coercion between finite fields

[Nathann Cohen]

Hello everybody,

I am rather ignorant of Sage matters when it comes to finite fields. I have been playing with matrices for a while, working around a bug that I did not understand. It is now solved, but here is what it boils down to:

    sage: K1 = GF(4,'w')
    sage: K2 = GF(8,'x')
    sage: K2(K1(1))
    TypeError: unable to coerce from a finite field other than the prime subfield

Observe that the code works if K1 and K2 both use the same variable *name*.

While this behaviour is probably justified I, as a beginner, just needed to be told that both variable names should be the same. If somebody feels that this could be made clearer somehow, that could save time for the next person who will meet the problem (which was in my case hidden under layers of matrices).

Note also that Matrix.base_extend has no documentation.

Thanks,

Nathann

[John Cremona]

GF(4) is not a subfield of GF(8).

John

> --
> 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+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.

[Nathann Cohen]

GF(4) is not a subfield of GF(8).

Oh. Right. Actually, the problem with my code happened when both finite fields were equal, and I wrote this message without thinking.

    sage: K1 = GF(8,'a')

    sage: K2 = GF(8,'b')

    sage: K2(K1(1))

    TypeError: unable to coerce from a finite field other than the prime subfield

Perhaps it is then easier to solve.

Nathann

 

[Jean-Pierre Flori]

Hi,

I guess one of the issue is that there is no canonical map between two different representations of the same finite field (so no coercion).
In your case it is slightly more specific as it might be the case that K1 and K2 are constructed in the same exact way (expect for the string 'a' and 'b') so we could just decide to send "a" onto "b", but I'm not sure it is very helpful to define an exception in this case.

There are some way to deal with the general problem in a smart way.
See
http://trac.sagemath.org/ticket/8335 (closed)
http://trac.sagemath.org/ticket/14990 (closed)
trac.sagemath.org/ticket/8751 (needs work, dead for two years)
for some work toward this within Sage.
We also have a project with a bunch of people to compute isomorphisms between finite field faster here:
https://github.com/defeo/ffisom/
https://github.com/jpflori/sagemath/tree/ffisom

Best,
JP

[Nathann Cohen]

Hello,

> In your case it is slightly more specific as it might be the case that K1 and K2 are constructed in the same exact way (expect for the string 'a' and 'b') so we could just decide to send "a" onto "b", but I'm not sure it is very helpful to define an exception in this case.

If it is "doable", then indeed it would solve my problem and (to me)
does not seem to induce any tricky behaviour.

Nathann

[John Cremona]

In this case:

sage: [x.polynomial() for x in K1]
[0, a, a^2, a + 1, a^2 + a, a^2 + a + 1, a^2 + 1, 1]
sage: [K2(x.polynomial()) for x in K1]
[0, b, b^2, b + 1, b^2 + b, b^2 + b + 1, b^2 + 1, 1]

John

[Nathann Cohen]

>> If it is "doable", then indeed it would solve my problem and (to me)
>> does not seem to induce any tricky behaviour.
>
> In this case:
>
> sage: [x.polynomial() for x in K1]
> [0, a, a^2, a + 1, a^2 + a, a^2 + a + 1, a^2 + 1, 1]
> sage: [K2(x.polynomial()) for x in K1]
> [0, b, b^2, b + 1, b^2 + b, b^2 + b + 1, b^2 + 1, 1]

Sorry, when I said "solve my problem" I meant "the unclear error
message" (as I was not able to guess from it that I only had to change
the variable's name).

My code has been made to work by picking the same variable name in
both cases, and the result is in needs_review.

http://trac.sagemath.org/ticket/19221

Nathann

[Jeroen Demeyer]

On 2015-09-16 16:43, Jean-Pierre Flori wrote:
> Hi,
>
> I guess one of the issue is that there is no canonical map between two
> different representations of the same finite field (so no coercion).

The question is really: is the map between representations of the same
finite field, which differ only in variable name, "canonical"?

[Nathann Cohen]

> The question is really: is the map between representations of the same
> finite field, which differ only in variable name, "canonical"?

I would say that there is no big risk to do that, though I am not at
all knowledgeable on those parts of the code. If it can be dangerous
but can be detected, however, it would be cool if an error message
could hint at it, e.g. "the generators have different names".

Though really, "checking" things by comparing the strings used to
describe generators does not look very reliable either. Especially
since because of this behaviour I will now start using the same string
'a' everywhere, just to avoid it.

Nathann

[Simon King]

Hi!

I think that it is in the same way canonical as we have a
name-preserving map between polynomial rings.

The real problem here is that *conversion* gives rise to an error
that mentions *coercion*.

sage: K.<x> = GF(25)
sage: L.<y> = GF(25)
sage: K(y)
Traceback (most recent call last):
...

TypeError: unable to coerce from a finite field other than the prime subfield

That's clearly a bug. Conversion should work, even if it isn't canonical
and thus doesn't qualify as coercion!

Is there no ticket for it already? I think I have seen that issue
before.

Cheers,
Simon

[Volker Braun]

Two comments: 

A) There is no such thing as "different finite fields of the same size with the same generator name"

sage: GF(4, 'a') is GF(4, 'a')

True

sage: GF(4, 'a') is GF(4, 'b')

False

There is no way to cast finite field elements to other finite field elements apart from the prime subfield case.

B) The ambiguity in mapping GF(p^n) to itself is of course super-important and gives rise to lots of interesting mathematics.

[Vincent Delecroix]

+1

The behavior should be similar to

sage: Rx.<x> = ZZ[]
sage: Ry.<y> = ZZ[]
sage: Rx(3*y**2 + 1)
3*x^2 + 1
sage: x+y

Traceback (most recent call last):
...

TypeError: unsupported operand parent(s) for '+': 'Univariate Polynomial
Ring in x over Integer Ring' and 'Univariate Polynomial Ring in y over
Integer Ring'

Vincent

[Nathann Cohen]

Here is another discovery after 15 minutes of debugging:

sage: K1 = GF(8,'x')
sage: K2 = GF(8,'y')
sage: K1(1) == K2(1)
False

Nathann

On 17 September 2015 at 12:15, Vincent Delecroix

> --
> You received this message because you are subscribed to a topic in the
> Google Groups "sage-devel" group.
> To unsubscribe from this topic, visit
> https://groups.google.com/d/topic/sage-devel/1rIMPfChUM4/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to

[Jeroen Demeyer]

On 2015-09-17 11:56, Volker Braun wrote:
> Two comments:
>
> A) There is no such thing as "different finite fields of the same size
> with the same generator name"

Of course there is:

sage: GF(8, 'a') is GF(8, 'a', modulus="adleman-lenstra")
False

[Jean-Pierre Flori]

Don't we have a random keyword as well?

[Jeroen Demeyer]

On 2015-09-17 12:32, Jean-Pierre Flori wrote:
> Don't we have a random keyword as well?

Not a random keyword, but a modulus="random" argument (there are several
more algorithms to choose a modulus)

[Vincent Delecroix]

Another instance of our non-transitive equality

sage: K1 = GF(8,'x')
sage: K2 = GF(8,'y')

sage: K1.one() == 1 == K2.one()
True

[Jeroen Demeyer]

This one is also fun:

sage: K = GF(8, 'a')
sage: K(1) == ZZ(1) == QQ(1)
True
sage: K(1) == QQ(1)
False

[William Stein]

That may be because K(y) used to actually be called "coercion" in
Sage, and it didn't get changed in this one place when Robert Bradshaw
(?) introduced the name "conversion" for non-canonical coercions.
When I wrote the first coercion model I had two notions:

- coercions -- like K(y)
- canonical coercion -- like x + 5, which converts the integer 5 to GF(25)

I think Robert renamed these to:

- coercion --> conversion
- canonical coercion --> coercion

which would lead to confusion like you're seeing.

>
> Is there no ticket for it already? I think I have seen that issue
> before.
>
> Cheers,
> Simon
>

> --
> 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+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.

--
William (http://wstein.org)

[Nils Bruin]

On Thursday, September 17, 2015 at 2:54:15 AM UTC-7, Simon King wrote:

The real problem here is that *conversion* gives rise to an error
that mentions *coercion*.

  sage: K.<x> = GF(25)
  sage: L.<y> = GF(25)
  sage: K(y)
  Traceback (most recent call last):
  ...
  TypeError: unable to coerce from a finite field other than the prime subfield

That's clearly a bug. Conversion should work, even if it isn't canonical
and thus doesn't qualify as coercion!

 
I don't think it's "clearly a bug". Conversions are *allowed* to work when there is a non-canonical map (i.e., a section map back that's not a morphism, as for ZZ -> ZZ/p ) but I don't think conversions are *required* to work when such a map exists.

What would the condition be? That the minimal polynomials of x,y over GF(5) are identical? That the minimal poly of y has a root over K and then just choose a root (and let the conversion system try to keep things sane)?

Do we expect for
N.<a> = NumberField(x^5-x+1)
M.<b> = NumberField(x^5 + 5*x^4 + 8*x^3 + 4*x^2 - 1)

that

N(b)

should work? (there is actually less ambiguity there!)

[William Stein]

Equals is not transitive in Sage. Addition (of floating point
numbers) is not commutative either. And many, many other things that
are different from our perfect abstractions when you try to model
infinite objects in a finite machine. I definitely do not consider
this a bug:

sage: K1 = GF(8,'x')
sage: K2 = GF(8,'y')
sage: K1(1) == K2(1)
False

It is because there is no "canonical coercion" (renamed now-a-days to
"coercion") between K1 and K2, so there's no way to compare elements
automatically. == always says false when it can't decide right now.
The other option is to throw an exception, which is very painful in
code.

On Thu, Sep 17, 2015 at 5:38 AM, Jeroen Demeyer <jdem...@cage.ugent.be> wrote:
> This one is also fun:
>
> sage: K = GF(8, 'a')
> sage: K(1) == ZZ(1) == QQ(1)
> True

This follows exactly the same rule above: in each case above there is
a canonical codomain that 1 gets mapped to that can be used to
compare.

> sage: K(1) == QQ(1)
> False

There is no canonical map from K and QQ into something, so no
comparison is possible.

William

>
>
> --
> 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+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.

--
William (http://wstein.org)

[William Stein]

On Thu, Sep 17, 2015 at 8:00 AM, Nils Bruin <nbr...@sfu.ca> wrote:
> On Thursday, September 17, 2015 at 2:54:15 AM UTC-7, Simon King wrote:
>>
>> The real problem here is that *conversion* gives rise to an error
>> that mentions *coercion*.
>>
>> sage: K.<x> = GF(25)
>> sage: L.<y> = GF(25)
>> sage: K(y)
>> Traceback (most recent call last):
>> ...
>> TypeError: unable to coerce from a finite field other than the prime
>> subfield
>>
>> That's clearly a bug. Conversion should work, even if it isn't canonical
>> and thus doesn't qualify as coercion!
>
>
> I don't think it's "clearly a bug". Conversions are *allowed* to work when
> there is a non-canonical map (i.e., a section map back that's not a
> morphism, as for ZZ -> ZZ/p ) but I don't think conversions are *required*
> to work when such a map exists.

That's right. Conversions are almost always dangerous and *not*
something you want to use. It's much, much better to define an
explicit morphism and use that. We have implemented conversions in
many cases, but if you use them, you're increasing the chances of a
very subtle bug by an order of magnitude.

Here's what you should do:

K.<x> = GF(25)
L.<y> = GF(25)
phi = K.hom([y])
phi(x + 3)

And this lets you do anything that makes sense, but protects you from
doing wrong stuff like this:

psi = K.hom([y^2])
[boom]

https://cloud.sagemath.com/projects/4a5f0542-5873-4eed-a85c-a18c706e8bcd/files/support/2015-09-17-080944-conversions.sagews

> What would the condition be? That the minimal polynomials of x,y over GF(5)
> are identical? That the minimal poly of y has a root over K and then just
> choose a root (and let the conversion system try to keep things sane)?
>
> Do we expect for
> N.<a> = NumberField(x^5-x+1)
> M.<b> = NumberField(x^5 + 5*x^4 + 8*x^3 + 4*x^2 - 1)
>
> that
>
> N(b)
>
> should work? (there is actually less ambiguity there!)

Explicit is better than implicit. Use hom. If I were doing it all
over, I would very likely remove coercion entirely and make hom even
better than it already is. Coercion is a bad idea and source of very
subtle bugs.

William

>
> --
> 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+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.

--
William (http://wstein.org)

[Simon King]

Hi Nathann,

On 2015-09-17, Nathann Cohen <nathan...@gmail.com> wrote:
> Here is another discovery after 15 minutes of debugging:
>
> sage: K1 = GF(8,'x')
> sage: K2 = GF(8,'y')
> sage: K1(1) == K2(1)
> False

Not a bug, because cross-parent comparison would only make sense if
there is some kind of a canonical map of one parent (and not just of a
single element!) into the other or of both parents into a third one.

Cheers,
Simon

[Nathann Cohen]

Simon,

>> sage: K1 = GF(8,'x')
>> sage: K2 = GF(8,'y')
>> sage: K1(1) == K2(1)
>> False
>
> Not a bug, because cross-parent comparison would only make sense if
> there is some kind of a canonical map of one parent (and not just of a
> single element!) into the other or of both parents into a third one.

What I think is unreliable is that "deep down" you decide that two finite fields are equal (or not) based on a string comparison.

If two functions create independently two GF(8,'x') then you decide that they mean the same, and if two functions create a GF(8,'y') and GF(8,'x') then you decide that they mean something different.

The only consequence I see to that is that we should *always* use the same variable name for a finite field in Sage's source code, which is a very odd rule. At least it gets the code to work.

If would feel better if two GF(8,'x') were always different, or if all GF(8,<whatever>) were equal.

Nathann

[Simon King]

Hi Nathann,

On 2015-09-18, Nathann Cohen <nathan...@gmail.com> wrote:
>>> sage: K1 = GF(8,'x')
>>> sage: K2 = GF(8,'y')
>>> sage: K1(1) == K2(1)
>>> False
>>
>> Not a bug, because cross-parent comparison would only make sense if
>> there is some kind of a canonical map of one parent (and not just of a
>> single element!) into the other or of both parents into a third one.
>
> What I think is unreliable is that "deep down" you decide that two finite
> fields are equal (or not) based on a string comparison.
>
> If two functions create independently two GF(8,'x') then you decide that
> they mean the same, and if two functions create a GF(8,'y') and GF(8,'x')
> then you decide that they mean something different.

What do you mean by "mean"?

Certainly the two fields are isomorphic. But that's not the point here.
So, let me explain what I mean by "mean".

The question is how we can find a system C ("canonical" resp. "coercion")
of homomorphisms between parents in Sage that contains identity morphisms
and is closed under composition and such that for each pair of parents
there is at most one homomorphism in C having the given pair of parents
as domain and codomain.

If there is an isomorphism in C between parents P1 and P2 then there is
a canonical way to identify elements of P1 with elements of P2. But if
there is not, then Sage developers found it difficult to admit that
elements of P1 have *anything* to do with elements of P2.

Thus, if there is no canonical morphism between the parents P1, P2, then
their elements should always evaluate unequal --- because they live in
separate worlds.

The automorphism group of GF(p^n) for n>1 is non-trivial. Thus, it is
not straight forward to single out a "canonical" isomorphism between two
non-identic copies of GF(p^n). In that sense, they do not mean the same.

So, that's what *I* mean by "mean". If we build a system C of canonical
morphisms (aka "coercions") and there is no isomorphism in C with domain
GF(8,'y') and codomain GF(8,'x') then GF(8,'y') and GF(8,'x') mean
something different. Otherwise, they do *not* mean "the same", but at
least one can make them "the same" in a canonical way.

> If would feel better if two GF(8,'x') were always different, or if all
> GF(8,<whatever>) were equal.

There are good reasons to say that if you construct GF(8,'x') twice then
the results are not only the same but *identical*. Even better reasons
are imply that GF(8,'x') and GF(8,'y') can not be identical.

One can of course try the following rule for constructing C: If the
minimal polynomial used in the construction of GF(8,'x') is obtained
from the minimal polynomial used in the construction of GF(8,'y') by
substitution y->x, then the map extends to an isomorphism that shall
belong to C. If the minimal polynomials are not mapped in that way, then
*no* isomorphism between the two fields should belong to C.

I simply don't know if such a rule gives rise to an inconsistency in the
"global picture" (i.e., in the system of *all* coercions in Sage). But
the rule does seem reasonable to me.

Best regards,
Simon

[John Cremona]

Wow, this is getting quite heavy (and I thought this language belonged
more in sage-algebra but never mind).

By keeping track of the generator x's minimal polynomial and not just
the abstract field structure of F=GF(p^n) means that we are
considering not just F, but also the ring homomorphism GF(p)[X] ->
GF(p^n) mapping X to x. In other words, F is considered not just as a
field but as a GF(p)-algebra. Once you have adorned each instance of
a finite field with this additional algebra structure, one can allow a
map F1 -> F2 only in a more restricted situation: not just that #F1
divides #F2 (which is iff there is a field morphism) but that there is
a GF(p)-algebra morphism from F1 to F2 --which is a field morphism
mapping F1's generator to F2's. Of course when F=GF(p) itself there
is only one choice of a GF(p)-algebra structure anyway.

It happens all the time in computational algebra & number theory that
structures need to be considered with such additional structure, often
given by fixing generators.

John

>
> I simply don't know if such a rule gives rise to an inconsistency in the
> "global picture" (i.e., in the system of *all* coercions in Sage). But
> the rule does seem reasonable to me.
>
> Best regards,
> Simon
>
>

> --

> 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+...@googlegroups.com.

[Nathann Cohen]

Hello Simon,

> One can of course try the following rule for constructing C: If the

> minimal polynomial used in the construction of GF(8,'x') is obtained
> from the minimal polynomial used in the construction of GF(8,'y') by
> substitution y->x, then the map extends to an isomorphism that shall
> belong to C. If the minimal polynomials are not mapped in that way, then
> *no* isomorphism between the two fields should belong to C.

This makes a lot of sense to me. It would make a "Field with a distinguished generator" independent of the string used to represent the generator.

Nathann