GF(16,'x') when we do not care about the 'x'

[Nathann Cohen]

Hello everybody,

I write a lot of code that requires me to build finite fields, and the
finite fields F_q, when q is not a prime number, cannot be
instanciated without specifying a variable name:

sage: GF(16)
ValueError: parameter 'conway' is required if no name given

Thus, I always use GF(16,'x') to avoid this exception.

Is there any reason to not make GF(16) behave as GF(16,'x') does,
unless specified otherwise? I do not see the point of requesting the
user to provide a character if (s)he does not care.

Nathann

[John Cremona]

+1 for having a default, though I would choose 'a'.

> Nathann
>
> --
> 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 https://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.

[Nils Bruin]

On Wednesday, January 20, 2016 at 1:04:49 PM UTC-8, John Cremona wrote:

> Is there any reason to not make GF(16) behave as GF(16,'x') does,
> unless specified otherwise? I do not see the point of requesting the
> user to provide a character if (s)he does not care.
>

+1 for having a default, though I would choose 'a'.

There is a potential confusion there:

sage: ZX.<x>=ZZ[]
sage: ZY.<y>=ZZ[]
sage: F=GF(16,'x')
sage: R=F['x,u,v']
sage: S=F['y,u,v']
sage: S(x).degree()
0
sage: R(x).degree()
1
sage: S(y).degree()
1
sage: R(y).degree()
0

This is actually a bit of a mess: generator names are supposed to be used in figuring out coercion maps, but currently this doesn't seem to happen too much with GF(p^r) . [Really, F(y) should be an error, because it's totally not clear where y should go]. So currently, having a default name in GF doesn't seem to be too much of an issue because GF violates normal coercion rules. However, if this were fixed then a default generator name (especially when it's something usual such as x) would lead to odd interactions with coercions from various structures.

[Dima Pasechnik]

how about making GF(16) default to GF(16,'conway')

no symbols injected, no conflicts...

[Nathann Cohen]

> how about making GF(16) default to GF(16,'conway')
> no symbols injected, no conflicts...

If conflicts can come from the choice of a variable name, I'd say that
the problem is not the variable's name but the code that relies on it.

As far as I am concerned the name can be absolutely anything you agree on.

Nathann

[Nils Bruin]

On Wednesday, January 20, 2016 at 1:49:12 PM UTC-8, Nathann Cohen wrote:

If conflicts can come from the choice of a variable name, I'd say that
the problem is not the variable's name but the code that relies on it.

Conflicts do not arise from variable names (or at least not the conflicts we need to be worried about). It's that the names of generators are part of the identity of a parent in sage: It is expected that for some structure generator S, the result of S(name='a') and of S(name='b') interact differently with other structures in sage.

Thus, if we decide the default name is "conway" then GF(p^r) and GF(p^r,'conway') will behave the same (they should be identical objects in fact!), but GF(p^r) and GF(p^r,'x') will behave differently. If we choose dthe default name 'a' then GF(p^r) and GF(p^r,'a') will behave the same but GF(p^r) and GF(p^r,'conway') will behave differently.

More insidious is the interaction with names on the other side: if GF were to follow coercion rules properly and 'conway' is a special name, then

ZZ['conway'] and GF(p^r) would have a special relation, but ZZ['x'] and GF(p^r) would not. So choosing something like "conway" would indeed be safer.

A little further down the line, one would probably want that GF(p^2) coerces into GF(p^4). If we use the same name 'conway' for both generators, then ZZ['conway'] would have a good reason for coercing into both, but obviously in a way that is incompatible with the embedding of GF(p^2) into GF(p^4).

So I'd actually suggest to make the order (or at least the degree) part of the default generator name. That'll be more "future proof" wrt coercion improvements.

[Dima Pasechnik]

On Wednesday, 20 January 2016 22:18:04 UTC, Nils Bruin wrote:

On Wednesday, January 20, 2016 at 1:49:12 PM UTC-8, Nathann Cohen wrote:

If conflicts can come from the choice of a variable name, I'd say that
the problem is not the variable's name but the code that relies on it.

Conflicts do not arise from variable names (or at least not the conflicts we need to be worried about). It's that the names of generators are part of the identity of a parent in sage: It is expected that for some structure generator S, the result of S(name='a') and of S(name='b') interact differently with other structures in sage.

Thus, if we decide the default name is "conway" then GF(p^r) and GF(p^r,'conway') will behave the same (they should be identical objects in fact!), but GF(p^r) and GF(p^r,'x') will behave differently. If we choose dthe default name 'a' then GF(p^r) and GF(p^r,'a') will behave the same but GF(p^r) and GF(p^r,'conway') will behave differently.

to me,  two fields that are specified by the same irreducible polynomial over the same prime subfield ought to be identical.

it'd be much better design, not wedding them to named generators at all.

In GAP, the "standard" GF(p^r) has generator named Z(p^r); this would use Conway polynomials to specify the field, no ambiguity arises.

[Nils Bruin]

On Wednesday, January 20, 2016 at 3:22:54 PM UTC-8, Dima Pasechnik wrote:

to me,  two fields that are specified by the same irreducible polynomial over the same prime subfield ought to be identical.

it'd be much better design, not wedding them to named generators at all.

That's not compatible with the coercion model in sage where

Z['x'] coerces into QQ['x'] and QQ['u','x','v'], but not into QQ['y']

Names of generators are part of the identity of a structure in sage. With respect to polynomial rings this allows for various automatic behaviours that are out of reach for other computer algebra systems, so we are getting a benefit from it. It also has unfortunate and/or counterintuitive consequences in other cases; for you this may be one of them. It'll be way too invasive to change sage's concepts at this stage, so I think we'll have to live with it. Currently the generator name is important for finite fields:

sage: GF(64,'x').0+GF(64,'y').0
TypeError: unsupported operand parent(s) for '+'

[William Stein]

Nils -- many thanks for your post explaining the longterm perspective
and underlying reasons why things are the way they are.

I mentioned this thread in my class today, which happened to be on
constructing finite fields in Sage:

https://cloud.sagemath.com/projects/b85dd1b3-3f5f-4c2d-b503-242612561b9e/files/lectures/2016-01-20/2016-01-20-part2-finite-fields.sagews

Also -- pdf attached to this email....

The immediate surprises I hit when looking again at finite fields from
a high level after all this time (and we did a *lot* with finite
fields before there was a coercion model -- e.g., crazy Givaro
wrapping in Cython before there was Cython C++ support) is that the
following things don't exist:

(1) GF(3^2,'a').embeddings(GF(3^6,'b')) # like we do have for number fields

(2) GF(3^2,'a').gen() + GF(3^3,'b').gen()

However, the new Fpbar stuff by Vincent looks awesome (especially if
we had embeddings)...

(3) GF(f(x), names='a') # this doesn't work, but it should like for
number fields

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 https://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.

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

[David Roe]

I agree that it would be quite intrusive to remove the concept of variable names from finite fields.  What if GF(p^n) were equivalent to GF(p).algebraic_closure().subfield(n)[0] ?  Here's a quick timing comparison (a bit noisy since I ran only once in order to eliminate caching effects)

sage: for p in prime_range(2,20):
....:     print p, timeit("L=GF(p).algebraic_closure().subfield(12)[0]",number=1,repeat=1)
2 1 loops, best of 1: 256 ms per loop
3 1 loops, best of 1: 33.1 ms per loop
5 1 loops, best of 1: 9.18 ms per loop
7 1 loops, best of 1: 8.25 ms per loop
11 1 loops, best of 1: 6.36 ms per loop
13 1 loops, best of 1: 6.23 ms per loop
17 1 loops, best of 1: 9.78 ms per loop
19 1 loops, best of 1: 6.56 ms per loop

sage: for p in prime_range(2,20):
....:     print p, timeit("L=GF(p^12,'x')",number=1,repeat=1)
2 1 loops, best of 1: 230 ms per loop
3 1 loops, best of 1: 34.6 ms per loop
5 1 loops, best of 1: 2.69 ms per loop
7 1 loops, best of 1: 2.4 ms per loop
11 1 loops, best of 1: 3.34 ms per loop
13 1 loops, best of 1: 2.19 ms per loop
17 1 loops, best of 1: 2.07 ms per loop
19 1 loops, best of 1: 11.9 ms per loop

There seems to be some speed penalty to my suggestion, but it's not too bad.  And if you care you can always use a variable name....

David

[William Stein]

On Wed, Jan 20, 2016 at 6:20 PM, William Stein <wst...@gmail.com> wrote:
> Nils -- many thanks for your post explaining the longterm perspective
> and underlying reasons why things are the way they are.
>
> I mentioned this thread in my class today, which happened to be on
> constructing finite fields in Sage:
>
> https://cloud.sagemath.com/projects/b85dd1b3-3f5f-4c2d-b503-242612561b9e/files/lectures/2016-01-20/2016-01-20-part2-finite-fields.sagews
>
> Also -- pdf attached to this email....
>
> The immediate surprises I hit when looking again at finite fields from
> a high level after all this time (and we did a *lot* with finite
> fields before there was a coercion model -- e.g., crazy Givaro
> wrapping in Cython before there was Cython C++ support) is that the
> following things don't exist:
>
> (1) GF(3^2,'a').embeddings(GF(3^6,'b')) # like we do have for number fields
>
> (2) GF(3^2,'a').gen() + GF(3^3,'b').gen()

The surrounding discussion about variables names provide a good reason
why (2) shouldn't work. However (1) should exist (and would be about
3 lines of code to add).

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

[Jean-Pierre Flori]

On Thursday, January 21, 2016 at 3:26:55 AM UTC+1, William wrote:

On Wed, Jan 20, 2016 at 6:20 PM, William Stein <wst...@gmail.com> wrote:
> Nils -- many thanks for your post explaining the longterm perspective
> and underlying reasons why things are the way they are.
>
> I mentioned this thread in my class today, which happened to be on
> constructing finite fields in Sage:
>
>    https://cloud.sagemath.com/projects/b85dd1b3-3f5f-4c2d-b503-242612561b9e/files/lectures/2016-01-20/2016-01-20-part2-finite-fields.sagews
>
> Also -- pdf attached to this email....
>
> The immediate surprises I hit when looking again at finite fields from
> a high level after all this time (and we did a *lot* with finite
> fields before there was a coercion model -- e.g., crazy Givaro
> wrapping in Cython before there was Cython C++ support) is that the
> following things don't exist:
>
>  (1) GF(3^2,'a').embeddings(GF(3^6,'b'))  # like we do have for number fields
>
>  (2) GF(3^2,'a').gen() + GF(3^3,'b').gen()

The surrounding discussion about variables names provide a good reason
why (2) shouldn't work.  However (1) should exist (and would be about
3 lines of code to add).

>
> However, the new Fpbar stuff by Vincent looks awesome (especially if
> we had embeddings)...
>

IIRC algebraic closure were mostly Peter's work :)
* http://trac.sagemath.org/ticket/14990
@William: were you thinking of something else?

Embeddings should be coming one of these days.
Old tickets:
* http://trac.sagemath.org/ticket/8751
* http://trac.sagemath.org/ticket/16354
We're working on faster algorithms there:
* https://github.com/defeo/ffisom/
It should make it into Sage somehow.

For the original variable name question:
* http://trac.sagemath.org/ticket/17569
Were the proposed solution is the algebraic closure one.

This one would be nice as well:
* http://trac.sagemath.org/ticket/17568
You could do GF(p, n[, 'x']) as Magma.

[Nathann Cohen]

A ticket has been created (needs_review)

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

Nathann