Implement algebraic closures of finite fields

[pbruin]

The goal of this ticket is a basic implementation of algebraic closures of finite fields. Most importantly, it provides the following:

• class AlgebraicClosureFiniteField_generic (abstract base class)
  • method subfield(n) returning a tuple consisting of the subfield of order pⁿ and a RingHomomorphism_im_gens giving the canonical embedding into the algebraic closure
• class AlgebraicClosureFiniteField_pseudo_conway (implements the specific defining polynomials of the finite subfields and the relations between the generators of these subfields)
• class AlgebraicClosureFiniteFieldElement (mostly a wrapper around FiniteFieldElement, so actually an element of a finite subfield, but having the algebraic closure as its parent and taking care of coercion into larger subfields)
• factory class AlgebraicClosureFiniteField (to get unique parents)
• method FiniteField.algebraic_closure() (invokes the factory class)

An example using the new functionality is the following analogue of the example from #8335:

sage: Fbar = GF(3).algebraic_closure('z')
sage: Fbar
Algebraic closure of Finite Field of size 3
sage: F2, e2 = Fbar.subfield(2)
sage: F3, e3 = Fbar.subfield(3)
sage: F2
Finite Field in z2 of size 3^2

To add, we first embed into Fbar:

sage: x2 = e2(F2.gen())
sage: x3 = e3(F3.gen())
sage: x = x2 + x3
sage: x
z6^5 + 2*z6^4 + 2*z6^3 + z6^2 + 2*z6 + 1
sage: x.parent() is Fbar
True

One can also do this without explicitly invoking the embeddings; as a shortcut, Fbar has a method gen(n) returning the fixed generator of the subfield of degree n, but as an element of Fbar:

sage: x2 == Fbar.gen(2)
True
sage: x == Fbar.gen(2) + Fbar.gen(3)
True

It is conceivable that there will be different coexisting implementations (deriving from AlgebraicClosureFiniteField_generic). The current implementation uses Conway polynomials and the pseudo-Conway polynomials from #14958, as well as the functionality for finite field homomorphisms provided by #13214.

[jpflori]

Another important question is to know what the AlgebraicClosure? structure should cache. If its possible not to store all data that was previously cmputed when some finite fields aren't used anymore, then it can make sense to discard it (imagine working with pseudo-Conway polynomials and only going up and up, at some point you won't care about polynomials used for small finite fields). This is really arguable, but we (or I at least) had several problems before (and we still have) because pieces of Sage tend to cache too much.

[pbruin]

Replying to jpflori:

Another important question is to know what the AlgebraicClosure? structure should cache. If its possible not to store all data that was previously cmputed when some finite fields aren't used anymore, then it can make sense to discard it (imagine working with pseudo-Conway polynomials and only going up and up, at some point you won't care about polynomials used for small finite fields). This is really arguable, but we (or I at least) had several problems before (and we still have) because pieces of Sage tend to cache too much.

Yes, this is something to keep in mind. As a first step, I imagine simply storing the polynomials for all fields that we encounter. This could become problematic, especially when working with fields whose degree over the prime field is highly composite. There are at least two solutions:

• convert references to fields (polynomials) that are not maximal elements in the lattice (w.r.t. divisiblity of degrees) into weak references, so the can be garbage-collected and reconstructed from the maximal elements as needed;
• generalise the algorithms for generating pseudo-Conway polynomials in such a way that in order to generate a pseudo-Conway polynomial of degree n, it doesn't need to generate pseudo-Conway polynomials for all degrees dividing n, but just uses a small set of polynomials that suffices to guarantee compatibility. For example, when you have compatible fields of degrees 30 and 200 and you want to construct a field of degree 600 containing both of them, it is of course better to use only the given polynomials of degree 30 and 200, and avoid implicitly creating subfields of degrees 300, 150, 120 etc.

[pbruin]

Here is a first implementation. The examples in the ticket description work exactly as written. It doesn't have a huge amount of functionality yet; for example, it would be nice to be able to factor polynomials over an algebraic closure of F_p. But this can probably wait until another ticket.

[pbruin]

Patch updated; now also implements is_square() and sqrt(), and makes doctests pass again.

[pbruin]

update (doctest coverage)

[defeo]

Nice work. I agree this is the way to go for Fp-bar. Here's some thoughts.

1. It'd be nice to implement a _latex_ method in the elements.

2. There's a quote problem in the first paragraph of the docstring:

'[\Bold{F}_n:\Bold{F}]=1`

3. I'm perplexed about the _cmp_ function in conway_polynomials.py:

sage: PCL3 = PseudoConwayLattice(3, use_database=False)
sage: PCL5 = PseudoConwayLattice(5, use_database=False)
sage: PCL3 == PCL5
True

Is this the intended result?

4. F.inclusion(1, a).section() is None for any a, this makes _change_level fail.

5. I wonder: wouldn't it be more efficient if _coerce_2 had a shortcut for when x and y are in the same level? (I really don't know, just wondering)

6. This patch lacks some obvious coercions, for example, F._subfield(2)(F.gen(2)). Should this wait for another ticket, or should this ticket do it?

I'd like to play around with different implementations of Fp-bar. This would help understand if the abstract class AlgebraicClosureFiniteField_generic is abstract enough, or if we need to think more carefully about its interface.

I don't know what's best: make this ticket enter 5.13, then start experimenting? Or, rather, keep experimenting and wait the different implementations to have settled before giving positive review?

If you want to go for the first, I'd be happy to give positive review as soon as the minor problems mentioned above are solved. If you prefer the second option, would you mind switching to git, so to ease collaboration?

[jpflori]

Replying to defeo:

Nice work. I agree this is the way to go for Fp-bar. Here's some thoughts.

1. It'd be nice to implement a _latex_ method in the elements.

Sure.

2. There's a quote problem in the first paragraph of the docstring:

'[\Bold{F}_n:\Bold{F}]=1`

3. I'm perplexed about the _cmp_ function in conway_polynomials.py:

sage: PCL3 = PseudoConwayLattice(3, use_database=False)
sage: PCL5 = PseudoConwayLattice(5, use_database=False)
sage: PCL3 == PCL5
True

Is this the intended result?

This looks wrong to me.

4. F.inclusion(1, a).section() is None for any a, this makes _change_level fail.

5. I wonder: wouldn't it be more efficient if _coerce_2 had a shortcut for when x and y are in the same level? (I really don't know, just wondering)

Stupid rant: I don' like the name _coerce_2, I don't think it really fits with our current naming scheme, nor that it really suggests what the function does (I first thought of coerce_to... of course it is two, not to).

About the shortcut, why not, but it does not seem that urgent. Maybe we should do some timings.

6. This patch lacks some obvious coercions, for example, F._subfield(2)(F.gen(2)). Should this wait for another ticket, or should this ticket do it?

Depends on the difficulty? :)

I'd like to play around with different implementations of Fp-bar. This would help understand if the abstract class AlgebraicClosureFiniteField_generic is abstract enough, or if we need to think more carefully about its interface.

I don't know what's best: make this ticket enter 5.13, then start experimenting? Or, rather, keep experimenting and wait the different implementations to have settled before giving positive review?

If you want to go for the first, I'd be happy to give positive review as soon as the minor problems mentioned above are solved. If you prefer the second option, would you mind switching to git, so to ease collaboration?

I don't really know. I'm usually for fast inclusion. But for this one I might be inclined to wait for 6.0 to give it a little more testing.

In particular, I'd like to make sure that this gets well with #715, #11521, #14711, #15303 and other coercion related stuff, though there should be no problems from what I currently see. We should also to check that when the user deletes an algebraic closure objects, everything gets garbage collected.

Maybe it needs some more thinking on the category framework integration with more general algebraic closures (not even sure it would make sense though)? I see the Factory currently sets it to Fields(). Additional question: how does it interact with the AlgebraicClosureFunctor? from sage.categories.pushout? Not sure how harmful it would be to modify that after the current ticket is merged.

[vdelecroix]

Hi,

Thanks for the nice patch! I played a little bit with the patch and here are few comments (from a user point of vue).

For the FiniteFieldAlgebraicClosure

• the method .cardinality() fails
• .some_elements() returns a very stupid list
• .gens() is not happy. I guess we can return a Family. The problem is that in the specification it is written that the method should return a tuple.

For elements

• many methods can be implemented in two lines as

     def my_method(self):
         return self._value.my_method()
  

  this concerns minimal_polynomial, trace, norm, multiplicative_order, ...
• in a similar way (calling apropriate method of _value and applying a morphism) it is straightforward to implement frobenius, pth_power, pth_root, ...
• to mimic AA or QQbar I would like a method as_finite_field_element(self, minimal=False) which return a triple (finite_field, value, homomorphism)

Vincent

[pbruin]

Thanks to you all for the comments. I haven't got a lot of time at the moment, but hope to get back to this ticket soon. In the meantime, feel free to continue suggesting improvements or implementing them yourselves. 8-)

[vdelecroix]

Replying to pbruin:

Thanks to you all for the comments. I haven't got a lot of time at the moment, but hope to get back to this ticket soon. In the meantime, feel free to continue suggesting improvements or implementing them yourselves. 8-)

Thanks. I am happy to work on this (I already implements the remarks I made). Is that ok if I switch to the git workflow ?

[defeo]

Replying to vdelecroix:

Thanks. I am happy to work on this (I already implements the remarks I made). Is that ok if I switch to the git workflow ?

Even if this ticket doesn't switch to the git workflow, I'd be happy to pull from your branch and start experimenting. Do you mind sharing it in a comment?

[vdelecroix]

Replying to defeo:

Replying to vdelecroix:

Thanks. I am happy to work on this (I already implements the remarks I made). Is that ok if I switch to the git workflow ?

Even if this ticket doesn't switch to the git workflow, I'd be happy to pull from your branch and start experimenting. Do you mind sharing it in a comment?

This is: u/vdelecroix/14990

[pbruin]

Replying to vdelecroix:

Replying to pbruin:

Thanks to you all for the comments. I haven't got a lot of time at the moment, but hope to get back to this ticket soon. In the meantime, feel free to continue suggesting improvements or implementing them yourselves. 8-)

Thanks. I am happy to work on this (I already implements the remarks I made). Is that ok if I switch to the git workflow ?

I haven't done any development with Sage+Git before (only uploaded an SSH key and installed Sage using Git), but I'll start trying it out. Once I get some facility in using it, I won't mind if this will become a Git ticket.

[vdelecroix]

Replying to pbruin:

Replying to vdelecroix:

Replying to pbruin:

Thanks to you all for the comments. I haven't got a lot of time at the moment, but hope to get back to this ticket soon. In the meantime, feel free to continue suggesting improvements or implementing them yourselves. 8-)

Thanks. I am happy to work on this (I already implements the remarks I made). Is that ok if I switch to the git workflow ?

I haven't done any development with Sage+Git before (only uploaded an SSH key and installed Sage using Git), but I'll start trying it out. Once I get some facility in using it, I won't mind if this will become a Git ticket.

Hi Peter,

I switch to git only recently and it is not easy to go from git to patches (the other way around is quite easy using the sage dev scripts). I modified several things from your patch, in particular: algebraic_closure now works without argument (the name is 'z' by default). I think that I will modify the following two problems

• .is_finite() fails on GF(3).algebraic_closure() (raise a NotImplementedError?). On the other hand it will be fixed with the new category schemes which allows Field().infinite())
• Zmod(3) does not support algebraic_closure()

From the last version #15390 (roots of polynomial and eigenvalues) works nicely !

Your work is really nice!

Cheers, Vincent

[pbruin]

Now experimenting with Git. I made some changes to Vincent's branch and will now try to create my own branch on Trac. You can ignore this for the moment...

[vdelecroix]

Hi,

In order to speed up a bit, you could add the following lines at the very begining of the method _to_common_subfield(self, x, y) (lines 561-580)

if x._level == y._level:
    return x._value, y._value

(when the level is the same I go from 3ms to 0.8ms)

What do you think about what I suggest in comment:15 namely, implementing .is_finite() (returning False) and do something for Zmod(3) ?

---

Last 10 new commits:

​dbc331b	rename _coerce_2 to _to_common_subfield; cosmetic changes
​ac93a01	remove the optional name from algebraic_closure examples
​2432102	allow no argument for .algebraic_closure()
​a197d0d	Merge branch 'u/vdelecroix/14990' of ​ssh://trac.sagemath.org:2222/sage into 14990
​f232993	fix the parent in pth_root and pth_power
​0f4b895	add examples to .cardinality()
​d95f57f	more methods to algebraic elements
​081c096	Trac 14990: implement algebraic closures of finite fields
​31045f7	fix the parent in pth_root and pth_power
​3d88af6	add examples to .cardinality()

[pbruin]

Replying to vdelecroix:

In order to speed up a bit, you could add the following lines at the very begining of the method _to_common_subfield(self, x, y) (lines 561-580)

I guess I could, but would you mind doing this yourself? (First because it's your change, but also so that I can get an idea about what this causes Git to do. If this kind of thing works smoothly, I'd be happy to definitively make this a Git ticket.) Or do I have to somehow change permissions on my branch for that?

[vdelecroix]

Replying to pbruin:

Replying to vdelecroix:

In order to speed up a bit, you could add the following lines at the very begining of the method _to_common_subfield(self, x, y) (lines 561-580)

I guess I could, but would you mind doing this yourself? (First because it's your change, but also so that I can get an idea about what this causes Git to do. If this kind of thing works smoothly, I'd be happy to definitively make this a Git ticket.) Or do I have to somehow change permissions on my branch for that?

I can not have write access to your branch on trac. But nevertheless it is still possible to synchronize our works. I will do the modification inside my branch u/vdelecroix/14990 and then you can update the changes to your local branch with

$ git checkout THE_NAME_OF_MY_LOCAL_BRANCH_FOR_14990
$ git pull u/vdelecroix/14990
$ git reset --merge

Once it is done you can just push the changes to your branch u/pruin/14990 on trac. The second command above pull the changes but do not reset the HEAD. The third one is precisely here for that purpose: it reset the head to the current FETCH_HEAD obtained from pull.

I will tell you when I am done.

[jpflori]

Hey, I'm not sure using pull/reset is the safer and best way to share your work together. What I would do, but I might be wrong, is to track the other one branch as a remote. Then go to my local branch and merge the other one latest changes.

• "git fetch --all" (or just the remote name if you don't want --all) to update the remote branch.
• "git checkout my_local_branch" to go to my branch.
• "git merge remote_name" to merge the remote change locally.

Best, JP

[vdelecroix]

Hey,

Thanks Jean-Pierre for the suggestion. My method is what is described in the ​developer guide. Anyway, how should I do to declare u/pbruin/14990 on trac has a remote ?

Best, Vincent

[vdelecroix]

Hi,

I push my changes to u/vdelecroix/14990. For the Zmod(p) suggestion it is actually possible to obtain the algebraic closure with

sage: Zmod(3).field().algebraic_closure()
Algebraic closure of Finite Field of size 3

So I think there is nothing to change here.

V.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​f8540ae	fix comparison of pseudo-Conway polynomial trees
​d6cf8d6	tiny optimization for _to_common_subfield and implementation of is_finite.

[jpflori]

Replying to vdelecroix:

Hey,

Thanks Jean-Pierre for the suggestion. My method is what is described in the ​developer guide. Anyway, how should I do to declare u/pbruin/14990 on trac has a remote ?

In fact, doing "pull" is the same thing as doing "fetch+merge" at once in your local branch. It's just I find it nicer to have a bunch of remotes synchronized locally to be able to have a look at them, make local branch from them for experimentation and so on, before merging them into actual working branches. Then you don't need the "reset --merge" trick (that I didn't know!).

To add a branch to an existing remote (as trac already exist and you surely want to track all branches coming from the trac server in the same remote), you can issue:

• git remote set-branches trac --add u/pbruin/14990

[pbruin]

Hi Vincent,

Replying to vdelecroix:

• .is_finite() fails on GF(3).algebraic_closure() (raise a NotImplementedError?). On the other hand it will be fixed with the new category schemes which allows Field().infinite())

Are you sure we should remove is_finite() and cardinality() after #10963 is done? Maybe a user wants to pass a custom category to __init__() (say Ring() or Fields()); then the magic wouldn't work anymore, it seems.

[pbruin]

For me Git seems to work fine now; I propose we continue with this.

After a combination of Git commands and editing .git/config by hand, it looks as follows:

[core]
        repositoryformatversion = 0
        filemode = true
        bare = false
        logallrefupdates = true
[remote "origin"]
        fetch = +refs/heads/*:refs/remotes/origin/*
        url = git://github.com/sagemath/sage.git
[branch "master"]
        remote = origin
        merge = refs/heads/master
[remote "trac"]
        url = git://trac.sagemath.org/sage.git
        fetch = +refs/heads/master:refs/remotes/trac/master
        fetch = +refs/heads/u/pbruin/14990:refs/remotes/trac/u/pbruin/14990
        fetch = +refs/heads/u/vdelecroix/14990:refs/remotes/trac/u/vdelecroix/14990
[branch "ticket/14990"]
        remote = trac
        merge = refs/heads/u/pbruin/14990

Does this look correct to the more experienced Git users?

[pbruin]

The following problems observed by Luca in comment:7 still need to be fixed:

1. It'd be nice to implement a _latex_ method in the elements.

4. F.inclusion(1, a).section() is None for any a, this makes _change_level fail.

6. This patch lacks some obvious coercions, for example, F._subfield(2)(F.gen(2)). Should this wait for another ticket, or should this ticket do it?

[vdelecroix]

Replying to pbruin:

The following problems observed by Luca in comment:7 still need to be fixed:

1. It'd be nice to implement a _latex_ method in the elements.

4. F.inclusion(1, a).section() is None for any a, this makes _change_level fail.

6. This patch lacks some obvious coercions, for example, F._subfield(2)(F.gen(2)). Should this wait for another ticket, or should this ticket do it?

I implemented 1 using self._value._latex_().

For 4, why is there a method _change_level, it is nowhere used ? Anyway, what do you expect as a section ? It needs to be compatible with embeddings of subfields.

For 6, it is definitely not a coercion but rather a conversion. It would be nice to have it but I am in favor of having it for a next ticket.

[pbruin]

Replying to vdelecroix:

Replying to pbruin:

The following problems observed by Luca in comment:7 still need to be fixed:

1. It'd be nice to implement a _latex_ method in the elements.

4. F.inclusion(1, a).section() is None for any a, this makes _change_level fail.

6. This patch lacks some obvious coercions, for example, F._subfield(2)(F.gen(2)). Should this wait for another ticket, or should this ticket do it?

I implemented 1 using self._value._latex_().

That seems like the right solution. The last doctest was wrong, at least on my system; this will be fixed in my next commit.

For 4, why is there a method _change_level, it is nowhere used ? Anyway, what do you expect as a section ? It needs to be compatible with embeddings of subfields.

The bug involving the prime subfield has been fixed. The section of the embedding between two subfields is just the map that sends an element of the larger subfield to the unique preimage in the smaller one if it exists, and raises a ValueError otherwise.

The reason for _change_level() is just that it would be nice to be able to change to a smaller internal representation of the same element, for example if one knows in advance that the result of a computation is going to be in a smaller subfield. Probably the function shouldn't have a leading underscore, though; I'm changing this.

For 6, it is definitely not a coercion but rather a conversion. It would be nice to have it but I am in favor of having it for a next ticket.

In principle we could register a conversion map from our algebraic closure to any finite subfield at the moment we construct this subfield, but this feels somewhat like a waste. Alternatively, we could create a class for embeddings of a finite field into an algebraic closure, and equip that with a section() method, or we could (less elegantly) teach the element constructors of the various finite field classes to accept elements of an algebraic closure.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​6325b20	rename/fix change_level(); new doctests
​27cc628	add a _latex_ method to the elements

[pbruin]

One issue I have some doubts about is whether the name argument of FiniteField.algebraic_closure(self, name='z') should be optional. We require the user to specify a name in most cases (finite fields, number fields, polynomial rings, Hecke eigenforms, etc.), so allowing a default here seems to go against the convention.

An exception is CyclotomicField(), which generates names starting with zeta; but in this case one could argue that this naming convention is practically universal. In the case of AA and QQbar, the name a is used for the generator in as_number_field_element(), and here one cannot even specify a name; this seems to go against the convention as well.

[vdelecroix]

Replying to pbruin:

One issue I have some doubts about is whether the name argument of FiniteField.algebraic_closure(self, name='z') should be optional. We require the user to specify a name in most cases (finite fields, number fields, polynomial rings, Hecke eigenforms, etc.), so allowing a default here seems to go against the convention.

On the other hand, QQ.algebraic_closure() works and if you want a generic method for roots of polynomials and eigenvalues of matrices (have a look at #15390) then you do not want to guess about what kind of argument the algebraic closure needs. More precisely, you do

P.change_ring(P.base_ring().algebraic_closure()).roots()

I would not be in trouble if we have a default for the generator of finite field, polynomial ring, etc. Actually, GF(9) looks more natural to me than GF(9, 'a') as there is only one field of cardinality 9.

An exception is CyclotomicField(), which generates names starting with zeta; but in this case one could argue that this naming convention is practically universal. In the case of AA and QQbar, the name a is used for the generator in as_number_field_element(), and here one cannot even specify a name; this seems to go against the convention as well.

[vdelecroix]

For 4, why is there a method _change_level, it is nowhere used ? Anyway, what do you expect as a section ? It needs to be compatible with embeddings of subfields.

The bug involving the prime subfield has been fixed. The section of the embedding between two subfields is just the map that sends an element of the larger subfield to the unique preimage in the smaller one if it exists, and raises a ValueError otherwise.

The reason for _change_level() is just that it would be nice to be able to change to a smaller internal representation of the same element, for example if one knows in advance that the result of a computation is going to be in a smaller subfield. Probably the function shouldn't have a leading underscore, though; I'm changing this.

I see. But then, as a user, you do not want to guess what should be the level. If you have a look at .as_finite_field_element() there is a minimal option if set to True make the method returns the "optimal" level. If you compare with AA and QQbar the methods is called exactify or simplify (I do not understand the subtle difference between those two methods). The two latter do not accept arguments.

[pbruin]

Replying to vdelecroix:

On the other hand, QQ.algebraic_closure() works and if you want a generic method for roots of polynomials and eigenvalues of matrices (have a look at #15390) then you do not want to guess about what kind of argument the algebraic closure needs.

Fair point; as far as I am concerned, this is the main argument for allowing a default argument in FiniteField.algebraic_closure().

I would not be in trouble if we have a default for the generator of finite field, polynomial ring, etc. Actually, GF(9) looks more natural to me than GF(9, 'a') as there is only one field of cardinality 9.

That is true, but it is only unique up to non-canonical isomorphism, unlike Z/9Z, for example. To me the notation GF(9) looks too much like it is canonical, and insisting on a variable name is a good way to remind the user that a choice of a defining polynomial is being made.

For algebraic closures, I am inclined to say that the current status is not bad: keep 'z' as the default name for FiniteField.algebraic_closure(), but don't extend this to a default name for the AlgebraicClosureFiniteField constructor.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​5fe4189

matrix2.pyx: no special case for finite fields in F.algebraic_closure()

[defeo]

Hi,

I'm still baking my own experimental version of Fp-bar on top of this ticket. I have a question: shouldn't _subfield() use check_irreducible=False in the FiniteField constructor? It looks like a waste to check twice for irreducibility.

[pbruin]

Replying to defeo:

I'm still baking my own experimental version of Fp-bar on top of this ticket. I have a question: shouldn't _subfield() use check_irreducible=False in the FiniteField constructor? It looks like a waste to check twice for irreducibility.

Good idea, I'll rebase this ticket and then disable the check.

[defeo]

Replying to pbruin:

Good idea, I'll rebase this ticket and then disable the check.

Why "rebase"? Maybe you meant "merge master"?

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Recent commits:

​4265b4f	do not check twice for irreducibility
​555055b	matrix2.pyx: no special case for finite fields in F.algebraic_closure()
​7f7ed5b	rename/fix change_level(); new doctests
​2de16f2	add a _latex_ method to the elements
​4455c84	fix comparison of pseudo-Conway polynomial trees

[pbruin]

Replying to defeo:

Replying to pbruin:

Good idea, I'll rebase this ticket and then disable the check.

Why "rebase"? Maybe you meant "merge master"?

I saw your comment only after the above Git operation; I may just have commited the sin of rewriting history and/or have messed things up for you. I'm still more used to Mercurial, which is why rebasing sounded like the obvious thing to do. Besides, it turned out to remove some duplicate commits which were in the previous version of the branch (I noticed this before).

[pbruin]

Replying to pbruin:

it turned out to remove some duplicate commits which were in the previous version of the branch (I noticed this before).

Although if I read the git-rebase man page correctly, merging our branches will now create even more duplicates because of my rebase. What is the best solution for this?

[defeo]

Although if I read the git-rebase man page correctly, merging our branches will now create even more duplicates because of my rebase. What is the best solution for this?

What do you mean by "duplicate commits"?

It's not a big deal for me, I can easily rebase my branch on yours. It's not meant to enter Sage anyway: it's just some experiments.

But it might be a problem for Vincent, if you still want to share work. If you want to go back in time, you can do something like this (make sure you have no uncommited work)

git reset --hard ​5fe4189
git cherry-pick ​4265b4f
git merge master
git push -f

assuming the only commit that really did something was the last one, ​4265b4f.

Anyway, as I said, I don't care. If this history is better for you, it's ok for me. I'll just rebase on top of your new history. Just try this if Vincent needs it.

[pbruin]

Replying to defeo:

What do you mean by "duplicate commits"?

The previous branch looked (on the Trac "commits" page) like two parallel and unconnected linear "chains" of commits, with all commits in the first also appearing in the other. When I was rebasing this, Git spit out several messages saying something to the effect that the patch had already been applied (in some cases I had to resolve a conflict first). After the rebasing, there was only one chain of commits left.

It's not a big deal for me, I can easily rebase my branch on yours. It's not meant to enter Sage anyway: it's just some experiments.

But it might be a problem for Vincent, if you still want to share work.

OK, let's leave it as is unless it creates trouble for Vincent (or someone else who might have been using this branch).

[defeo]

Replying to pbruin:

The previous branch looked (on the Trac "commits" page) like two parallel and unconnected linear "chains" of commits, with all commits in the first also appearing in the other. When I was rebasing this, Git spit out several messages saying something to the effect that the patch had already been applied (in some cases I had to resolve a conflict first). After the rebasing, there was only one chain of commits left.

Yes, you are right. There has been a little bit of a mess before the merge commit a197d0d79. Probably the mercurial patch was imported once by you and once by Vincent. No big deal, but since now you have rebased, there's no point in going back (unless someone was depending on the old commits).

[pbruin]

Actually, there is #15390 which depends on the old branch; I'm not sure whether it is better for me to go back or for Vincent to rebase his branch at #15390 onto this one.

[pbruin]

Just to get an idea of what would be good to do before setting this to "needs-review", here is the status of the items from Vincent's list (comment:9):

• .some_elements() returns a very stupid list

This can be made less stupid by implementing _an_element_() to return self.gen(2).

• .gens() is not happy. I guess we can return a Family. The problem is that in the specification it is written that the method should return a tuple.

I think returning a Family is acceptable given that there is no finite set of generators.

• many methods can be implemented in two lines as

     def my_method(self):
         return self._value.my_method()
  

  this concerns minimal_polynomial, trace, norm, multiplicative_order, ...

I agree for minimal_polynomial and multiplicative_order; the latter was implemented by Vincent.

The trace and norm, on the other hand, are not well-defined since the definition requires a finite extension, for which there is no canical choice.

It remains to implement minimal_polynomial, which can of course be done in two lines as above.

• in a similar way (calling apropriate method of _value and applying a morphism) it is straightforward to implement frobenius, pth_power, pth_root, ...

We now have pth_power and pth_root, again thanks to Vincent, and the field itself has frobenius. I don't think an additional frobenius on elements would be useful.

[pbruin]

Something else: I would prefer if the implementation of nth_root() could be improved before getting this ticket merged. The basic difficulty is figuring out in which subfield we have to look. Rather than trying extensions of degrees dividing n (is it true/clear that the degree has to divide n?), I think we should either factor xⁿ - a (where a is the element whose n-th root we want) and look at the smallest degree of a factor, or we should compute the multiplicative order of a. Also, before doing anything else, we should take all factors p out of n and use pth_root().

I hope to have an update soon, at least for the remaining things mentioned in the previous comment.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​70f07ca

implement three more methods

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​7b3d68a

cosmetic improvement to nth_root()

[pbruin]

I thought a bit about nth_root() but couldn't easily make it faster. Hence I just made two very minor fixes: raise an AssertionError instead of a ValueError if we don't find the root (since this should never happen) and move the TODO to the docstring.

Since the basic functionality of the ticket is usable, I'm setting it to needs_review.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​ff35daa

Merge branch 'develop' into ticket/14990

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​d45b9b6	Merge branch 'develop' into ticket/14990
​785c7b9	fix doctest: finite field homset now has unique representation

[vdelecroix]

Hello,

Sorry, the story started already long time ago. I would be happy to finish the review of this ticket and work again on #15390 (no trouble about the possible rebase, I will try the cherry-pick proposed by Luca).

In case you do not want to recompile your Sage over the 6.2.rc0, I put a version that merge the develop release at u/vdelecroix/14990 (with some extra, see below).

I am in trouble because of the UniqueFactory. Firstly, in some doctests there is a direct call to AlgebraicClosureFiniteField_pseudo_conway but in practice this should be avoided as we have

sage: F = AlgebraicClosureFiniteField_pseudo_conway(GF(5),'z')
sage: z = F.an_element()
sage: z == loads(dumps(z))
False

I had no idea how to make it clear. On the other hand, what it the purpose of a factory if there is only one implementation? Note that there will be a problem with the generic __reduce__ when there will be several implementations and I am pretty sure that many others trouble will show up.

Minor issues that I solved in a commit on my branch:

• the doctest must be in an EXAMPLES bloc and not an EXAMPLE bloc.

• I was wondering what was the point of __getstate__ (line 473) and __setstate__ (line 487) in the base class. It becomes clear after reading the code for the pseudo_conway class. Please, put some specification (better than "used for pickling") in __getstate__ and __setstate__ that would be useful to anybody who wants to implement their own algebraic closure (all right, there should not be a lot of them, but at least it will help people, like me, who are reading the code).

• Add optional keywords to FiniteField.algebraic_closure that are sent to the factory in order to be able to do

  sage: GF(5).algebraic_closure(implementation='pseudo_conway')
  

• for _get_polynomial and _get_im_gen we could use the decorator @abstract_method (from sage.misc.abstract_method). That way, their existence become part of the TestSuite and there is no need for the NotImplementedError. There are many example of its usage in sage/categories.

• It would be better to move the test lines 41-44 inside the constructor of AlgebraicClosure and rather use AlgebraicClosureFiniteField_pseudo_conway directly. That way we are sure that the good class is tested.

• Implement some_elements: this is important for having better automatic tests

Feel free to reuse the merge commit or the extra one from my branch. As soon as the situation of the factory is clear to me, the branch is good to go.

Thanks Vincent

[pbruin]

Hello Vincent,

Sorry, the story started already long time ago. I would be happy to finish the review of this ticket and work again on #15390 (no trouble about the possible rebase, I will try the cherry-pick proposed by Luca).

Great!

In case you do not want to recompile your Sage over the 6.2.rc0, I put a version that merge the develop release at u/vdelecroix/14990 (with some extra, see below).

OK, we should probably switch to that branch (although merging the latest development branch is only necessary in case of conflicts, and it clutters the history).

I am in trouble because of the UniqueFactory. Firstly, in some doctests there is a direct call to AlgebraicClosureFiniteField_pseudo_conway but in practice this should be avoided as we have

sage: F = AlgebraicClosureFiniteField_pseudo_conway(GF(5),'z')
sage: z = F.an_element()
sage: z == loads(dumps(z))
False

I had no idea how to make it clear.

It is hopefully clear from the general structure, and the fact that these classes are not in the global namespace, that they are not meant to be called directly. I do not find it too important, but we can add a remark if you think it is useful. The above behaviour is quite bad, though...

On the other hand, what it the purpose of a factory if there is only one implementation? Note that there will be a problem with the generic __reduce__ when there will be several implementations and I am pretty sure that many others trouble will show up.

There are indeed problems here. First, looking at the code again, I think that in the current implementation, the interaction between the factory and the pickling code is flawed. Second, I have been thinking about unique representation in other contexts (e.g. number fields and elliptic curves), and there seems to be something more fundamentally problematic.

From my perspective, the guiding philosophy should be that you can use UniqueRepresentation or UniqueFactory for objects that are defined up to unique isomorphism by a certain amount of "defining data", which corresponds to the arguments of the __init__() method of an object derived from UniqueRepresentation, resp. to the key used by a UniqueFactory.

The problem with of algebraic closures of finite fields is that in principle they are not defined up to unique isomorphism by a finite amount of defining data. This is exactly the reason why Conway polynomials were invented, and we could have unique representation if we only used Conway polynomials. However, the idea of this implementation was to use pseudo-Conway polynomials, which do not have the same uniqueness property.

It is not clear to me at the moment that trying to get unique representation at all in this case is the right thing to do. Especially with the current implementation, given that pseudo-Conway polynomials are not unique, it may be better to just (1) ensure that pickling works and (2) put some warnings in place that algebraic closures are not globally unique and that users should be careful if they want to ensure all elements live in the same algebraic closure.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​02d1520	Merge branch 'develop' into 14990-closure_finite_field
​c14a903	Minor improvements to algebraic closure of finite fields
​96bf62d	Trac 14990: do not try to get unique representation
​14e18af	Trac 14990: remove pickling code
​48e0ffe	Trac 14990: fix comparison of elements

[pbruin]

I decided to remove both the UniqueRepresentation code and the pickling methods. The code is much clearer now. It was surprisingly easy to get everything (mainly comparison of elements) to work again; one just has to be careful in the case where two parents are equal but not identical.

(The branch is based on u/vdelecroix/14990.)

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​33f982f

Trac 14990: small documentation improvements

[vdelecroix]

Hello Peter,

I do not like

sage: GF(5).algebraic_closure() is GF(5).algebraic_closure()
False

As far as I understand, a pseudo Conway polynomial is not uniquely defined. But nevertheless, the implementation of PseudoConwayLattice.polynomial is, no? The only thing that today prevents the uniqueness is the use of the database as shown in the following example:

sage: P1 = PseudoConwayLattice(5,use_database=True)
sage: P2 = PseudoConwayLattice(5,use_database=False)
sage: P1.polynomial(2)
x^2 + 4*x + 2
sage: P2.polynomial(2)
x^2 + x + 2

Maybe I am wrong and there is more than that.

So, I propose to restore some kind of unique representation based on the lattice. More precisely (if you agree)

• Make AlgebraicClosureFiniteField_pseudo_conway inherit from UniqueRepresentation
• add a non optional argument lattice in the constructor of AlgebraicClosureFiniteField_pseudo_conway that can also be used from something like

  GF(5).algebraic_closure(implementation='pseudo_conway',lattice=MyFunnyLattice())
  

  (that way we would have two different implementations of the algebraic closure depending if we use or not the database)
• possibly restore a __reduce__ in AlgebraicClosureFiniteField_pseudo_conway that avoid the factory (but I guess that it should be taken care by the UniqueRepresentation)

And then, it remains to find a nice way to avoid rebuilding new lattices each time a user asks for

sage: GF(5).algebraic_closure()

What do you think?

Vincent

[pbruin]

Hello Vincent,

I do not like

sage: GF(5).algebraic_closure() is GF(5).algebraic_closure()
False

Would you be happier if FiniteField.algebraic_closure() were a cached_method?

I see your point, but I really don't like the idea that constructing two algebraic closures of the same field can be expected to give identical objects. (Except if there are "trivial" reasons why it should, like caching the result in the above example, or if you use a mathematically well-defined construction like (non-pseudo) Conway polynomials.)

[defeo]

Hi,

As far as I understand, a pseudo Conway polynomial is not uniquely defined. But nevertheless, the implementation of PseudoConwayLattice.polynomial is, no? The only thing that today prevents the uniqueness is the use of the database

I think there are some random choices of roots in the pseudo-Conway algorithm. Am I wrong? And even then, in practice a pseudo-Conway lattice can never be computed completely, and when you are given a partial pseudo-Conway lattice, there are many different ways of completing it.

Anyway, I agree with Peter. This ticket is not only about pseudo-Conway polynomials. There's plenty of algorithmic ways of constructing the algebraic closure of GF(p), each with its pros and cons. None of them is canonical: even the famous "canonically embedded lattices" of Lenstra and De Smit, use an arbitrary lexicographic order at some point to make things canonical. So my opinion is that even for those "canonical" constructions, it is arguable whether they should be unique representations.

[vdelecroix]

Hello,

Thanks Peter and Luca for the lights.

1) For the comparison of AlgebraicClosureFiniteField you rely on the equality in PseudoConwayLattice... which is not exactly what you want. It compares the nodes which is something dynamical by definition. We have for example

sage: P1 = PseudoConwayLattice(5, use_database=False)
sage: P2 = PseudoConwayLattice(5, use_database=False)
sage: P1 == P2
True
sage: _ = P1.polynomial(1)
sage: P1 == P2     # hum!?
False
sage: _ = P2.polynomial(1)
sage: P1 == P2     # hum hum!!??
True

It is fine for the lattices but not for the fields. The simplest fix would be

class AlgebraicClosureFiniteField_pseudo_conway:
   ...
   def __cmp___(self, other):
      ...
      return self._pseudo_conway_lattice is other._pseudo_conway_lattice

2) It makes sense to have something more flexible like

sage: AC = AlgebraicClosureFiniteField_pseudo_conway
sage: AC(GF(3), lattice=my_pc_lattice)

where "my_pc_lattice" is an instance of a subclass or PseudoConwayLattice or something with the same specifications (i.e. at least a method polynomial). That way we can already have two implementations of the algebraic closure (calling PseudoConwayLattice with the option use_database=True or use_database=False).

3) In the example above, there is some redundancy as the pseudo-Conway lattice already knows the finite field... so it would be nice if the pseudo-Conway lattice implements a method base_ring that returns the finite field it is based on.

4) It would also make sense in PseudoConwayLattice to have a method associated_finite_field_algebraic_closure (with a better name if possible).

Vincent

PS: will see later for the unique representation problems.

[jpflori]

Replying to vdelecroix:

Hello,

Thanks Peter and Luca for the lights.

1) For the comparison of AlgebraicClosureFiniteField you rely on the equality in PseudoConwayLattice... which is not exactly what you want. It compares the nodes which is something dynamical by definition. We have for example

sage: P1 = PseudoConwayLattice(5, use_database=False)
sage: P2 = PseudoConwayLattice(5, use_database=False)
sage: P1 == P2
True
sage: _ = P1.polynomial(1)
sage: P1 == P2     # hum!?
False
sage: _ = P2.polynomial(1)
sage: P1 == P2     # hum hum!!??
True

It is fine for the lattices but not for the fields. The simplest fix would be

Is it really fine for lattices? I would say lattices with different polynomials shouldn't evaluate equal.

class AlgebraicClosureFiniteField_pseudo_conway:
   ...
   def __cmp___(self, other):
      ...
      return self._pseudo_conway_lattice is other._pseudo_conway_lattice

2) It makes sense to have something more flexible like

sage: AC = AlgebraicClosureFiniteField_pseudo_conway
sage: AC(GF(3), lattice=my_pc_lattice)

where "my_pc_lattice" is an instance of a subclass or PseudoConwayLattice or something with the same specifications (i.e. at least a method polynomial). That way we can already have two implementations of the algebraic closure (calling PseudoConwayLattice with the option use_database=True or use_database=False).

That sounds like a good idea.

3) In the example above, there is some redundancy as the pseudo-Conway lattice already knows the finite field... so it would be nice if the pseudo-Conway lattice implements a method base_ring that returns the finite field it is based on.

+1

4) It would also make sense in PseudoConwayLattice to have a method associated_finite_field_algebraic_closure (with a better name if possible).

Would that be really useful? That does not really make sense, but one might want to create a lattice without the corresponding algebraic closure :)

[jpflori]

Replying to jpflori:

Replying to vdelecroix:

Hello,

Thanks Peter and Luca for the lights.

1) For the comparison of AlgebraicClosureFiniteField you rely on the equality in PseudoConwayLattice... which is not exactly what you want. It compares the nodes which is something dynamical by definition. We have for example

sage: P1 = PseudoConwayLattice(5, use_database=False)
sage: P2 = PseudoConwayLattice(5, use_database=False)
sage: P1 == P2
True
sage: _ = P1.polynomial(1)
sage: P1 == P2     # hum!?
False
sage: _ = P2.polynomial(1)
sage: P1 == P2     # hum hum!!??
True

It is fine for the lattices but not for the fields. The simplest fix would be

Is it really fine for lattices? I would say lattices with different polynomials shouldn't evaluate equal.

Ok, I answered too quickly here. The problem is that polynomials are added to the lattices but not at the same time.

In this case, the fact that when the polynomials of the same degree added to the two lattices are actually the same is pure luck. As Luca remarked, there is some randomness (ok, maybe not so random if you look at what is actually happenning, but it is designed in a way it should be random), and the polynomials may be different.

Anyway, I do agree with the fact that the lattice are once equal, then different and then equal again. The only sensible thing to do to compare the lattices is to chek they have the same polynomials at every degree. Maybe in the case where database=True or conway polynomials are used we could make the lattice unique or consider two lattices with different degrees computed equal (but then we should also forbid lattices with database=True to overflow the database limits) and whatsoever that's not really the issue here. In the case of algebraic closure, I feel the same is enough. We don't really need identity of the underlying lattices. It's dynamical indeed, but there's no other way to do that (except for construction where you have something canonical or at least unique, let's say with Conway polynomials). But if we have that's even better (and would be easier to test: only a pointers comparison).

[pbruin]

I agree with Jean-Pierre's analysis. Let me just add that one shouldn't read too much mathematical meaning into equality (==) of parents. The main use for it is in deciding whether to allow coercion from one AlgebraicClosureFiniteField to another. For that, the only thing that make sense is to check if the PCPL's are the same. Here we do definitely want to check "only" equality, not identity. If we did anything less than checking equality, say only checking if one lattice is equal to a sublattice of the other, then we would be asking for trouble. For example, if we had an element x in the subfield of degree n in one of the two, then we would have no guarantee that the subfield of degree n that would have to be constructed in the other instance (where we want to coerce x) would be the same.

[vdelecroix]

Hi Peter,

Either I badly explained something or there is something contradictory in your argument. First of all you said

The main use for it [the equality] is in deciding whether to allow coercion from one AlgebraicClosureFiniteField to another.

Fine. But that was my point, equality is broken as we currently have with your branch applied

sage: p = next_prime(100000)
sage: K = GF(p)
sage: F1 = K.algebraic_closure()
sage: F2 = K.algebraic_closure()
sage: F1 == F2
True
sage: _ = F1.gen(3)   # force computation in PCL 1
sage: F1 == F2
False
sage: _ = F2.gen(3)   # same computation in PCL 2
sage: F1 == F2
True

So depending in which stage of the computation you are, there will or will not be a coercion between your fields! Do you agree that there is a problem here?

we do definitely want to check "only" equality, not identity [of PCL].

Here it depends on what you mean by "equality". If it is equality as mathematical object I do agree if it is equality as Python comparison I strongly disagree. The Python equality of PCL currently is: "two PCL are equal if they agree on their already made computations". And, as Jean-Pierre mentioned, it is not the purpose of that ticket to improve that.

Vincent

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​a585d4a	Trac 14990: make AlgebraicClosureFiniteField_pseudo_conway accept more arguments
​f9162db	Trac 14990: make FiniteField.algebraic_closure() a cached method

[pbruin]

Hi Vincent,

2) It makes sense to have something more flexible like

sage: AC = AlgebraicClosureFiniteField_pseudo_conway
sage: AC(GF(3), lattice=my_pc_lattice)

where "my_pc_lattice" is an instance of a subclass or PseudoConwayLattice or something with the same specifications (i.e. at least a method polynomial). That way we can already have two implementations of the algebraic closure (calling PseudoConwayLattice with the option use_database=True or use_database=False).

This is implemented in one of the two new commits; one can now pass a lattice argument, and the use_database flag is now accepted here as well.

3) In the example above, there is some redundancy as the pseudo-Conway lattice already knows the finite field... so it would be nice if the pseudo-Conway lattice implements a method base_ring that returns the finite field it is based on.

It already has a public attribute p for the characteristic; since the PCL is not really meant to be used directly anyway, I think it is redundant to also add a base_ring() method.

4) It would also make sense in PseudoConwayLattice to have a method associated_finite_field_algebraic_closure (with a better name if possible).

I agree with Jean-Pierre here; this doesn't seem to be useful. To compare, we don't have (and don't need) a method associated_finite_field() for polynomials over F_p either.

[pbruin]

Hi Vincent,

Either I badly explained something or there is something contradictory in your argument.

Or I badly explained something...

First of all you said

The main use for it [the equality] is in deciding whether to allow coercion from one AlgebraicClosureFiniteField to another.

Fine. But that was my point, equality is broken

I don't see in what sense you can really say that equality is broken, since it is not designed to be a mathematically meaningful property in this case. I think we should use the most restrictive notion possible that still allows non-identical fields to compare equal. (In this way we stay as close to unique representation as possible, in the sense that two non-identical objects only compare equal under very precise circumstances.)

So depending in which stage of the computation you are, there will or will not be a coercion between your fields! Do you agree that there is a problem here?

No, I don't think there is a problem. Nobody forces us to have all kinds of coercions that could possibly make sense. We should encourage the user to do all computations in the same field; making algebraic_closure() a cached method (as in one of the two new commits) is meant to help with this. As far as I'm concerned, coercion between equal but non-identical fields is only useful to make the "sanity check" loads(dumps(x)) == x work. I think it would be a mistake to make efforts to make different instances "synchronized" in some way, e.g. by keeping coercion once the underlying pseudo-Conway lattices of two instances start to diverge.

we do definitely want to check "only" equality, not identity [of PCL].

Here it depends on what you mean by "equality". If it is equality as mathematical object I do agree if it is equality as Python comparison I strongly disagree.

In this context I really think that the only sensible notion of equality is to compare the finite sublattices that have already been computed. I understand that this does not fit the idea of "equality as mathematical object", but this is out of necessity, because an AlgebraicClosureFiniteField_pseudo_conway object simply doesn't define a unique mathematical object. There is no guarantee that two partially computed PCL's will evolve in the same way. Think of a situation where the user pickles one instance, loads it in a newer Sage version where the algorithm for computing pseudo-Conway polynomials has changed, and computes another instance of "the same" field in that Sage version. Then as a consequence of the non-uniqueness of pseudo-Conway polynomials, the results may disagree even if the commands used to create them were exactly the same.

The Python equality of PCL currently is: "two PCL are equal if they agree on their already made computations". And, as Jean-Pierre mentioned, it is not the purpose of that ticket to improve that.

I think it is not even desirable in principle to improve this, because PCL's are non-unique by design. If you want a mathematically well-defined notion of equality (that is preserved under future extension of the lattices), you have to stick to (non-pseudo) Conway polynomials or use other canonical lattices of finite fields.

[vdelecroix]

Replying to pbruin:

Hi Vincent,

2) It makes sense to have something more flexible like

sage: AC = AlgebraicClosureFiniteField_pseudo_conway
sage: AC(GF(3), lattice=my_pc_lattice)

where "my_pc_lattice" is an instance of a subclass or PseudoConwayLattice or something with the same specifications (i.e. at least a method polynomial). That way we can already have two implementations of the algebraic closure (calling PseudoConwayLattice with the option use_database=True or use_database=False).

This is implemented in one of the two new commits; one can now pass a lattice argument, and the use_database flag is now accepted here as well.

Great. Thanks.

3) In the example above, there is some redundancy as the pseudo-Conway lattice already knows the finite field... so it would be nice if the pseudo-Conway lattice implements a method base_ring that returns the finite field it is based on.

It already has a public attribute p for the characteristic; since the PCL is not really meant to be used directly anyway, I think it is redundant to also add a base_ring() method.

Here I am not sure I agree. But anyway it would be better not to touch PseudoConwayLattice anyway.

4) It would also make sense in PseudoConwayLattice to have a method associated_finite_field_algebraic_closure (with a better name if possible).

I agree with Jean-Pierre here; this doesn't seem to be useful. To compare, we don't have (and don't need) a method associated_finite_field() for polynomials over F_p either.

Agreed.

[vdelecroix]

Hi Peter,

I still think that the equality of algebraic closures is broken for several reasons. I think (please correct me if you do not agree) that

• we do not want that the equality between unmutable objects changes: if two unmutable objects are equal at a given time they still should be equal a minute later (this is true for parents and elements)
• comparisons with == and != may never raise an error.

This is why the example I gave you before is a bug (see the other one below if you are not convinced). I am in favour of a more restrictive equality for fields based on identity of the pseudo conway lattice. It will allow less coercion but at least it will be consistent with the two things above.

Within your branch

sage: p = next_prime(100000)
sage: K = GF(p).algebraic_closure()
sage: x = K.gen(2)
sage: y = loads(dumps(x))
sage: x == y        # sanity check
True
sage: _ = K.gen(5)  # force computation
sage: x.parent() == y.parent()
False
sage: x == y
Traceback (most recent call last):
...
RuntimeError: BUG in map ...

In principle we could hope for a False above but the coercion system has a cache. This is the reason for the RuntimeError.

[pbruin]

This is not an easy problem. First of all, I have to say I don't understand precisely what it means for an object to be immutable. Roughly speaking it is supposed to mean that "its value cannot change", but that doesn't seem to be a completely well-defined notion either.

It seems to me that in the case of AlgebraicClosureFiniteField_pseudo_conway, the indeterminacy of pseudo-Conway lattices forces us to say that (1) the "value" of an instance has to include the set of subfields that have been computed, and (2) the only way to guarantee immutability is to define equality using identity of the lattices.

If this reasoning is correct, and we accept that parents should be immutable (which does sound like a reasonable condition, although I'm not immediately convinced that it should hold in this situation), then we have to accept Vincent's opinion that for two instances to compare equal it is a necessary condition that the lattices be identical. In that case I guess we may as well go all the way back to comparing by identity of the fields themselves.

It is a bit annoying, and I do not see how to easily avoid breaking the sanity check loads(dumps(x)) == x if we take this approach. Maybe we should just capitulate on this point and disable this check in the TestSuite, or explicitly give the error as the expected result of the TestSuite.

[vdelecroix]

Hi,

Given that PseudoConwayLattice is what it is, I agree to (1) and (2) in your comment:75.

Coercion are cached and I guess it forbids to have a mutable Parent (unless they coerce with nothing).

And you are right, we have a big trouble as we can not loads/dumps PseudoConwayLattice in the way we would like them to be. It seems reasonable to me to keep the error on x == loads(dumps(x)) and document it.

Nevertheless, we can fix it for most use cases by avoiding calling loads/dumps on the lattice. More precisely, when the user does not provide directly a lattice argument to the algebraic closure, we might cache the pseudo conway lattice used. In other words do something along the lines of

@cached_function
def cached_pseudo_conway_lattice(p, use_database):
    return PseudoConwayLattice(p, use_database)

def AlgebraicClosureFiniteField(p, implementation='pseudo_conway', **kwds):
    if implementation == 'pseudo_conway':
        lattice = kwds.get('lattice')
        use_database = kwds.get('use_database', True)
        if lattice is None:
            lattice = cached_pseudo_conway_lattice(p, use_database)
        ...

And then the pickling must be adapted by calling AlgebraicClosureFiniteField. I am sure that it can work but I am not sure at all it is reasonable.

[vdelecroix]

ping

Do you want that I give it a try?

Vincent

[pbruin]

Hi Vincent,

And you are right, we have a big trouble as we can not loads/dumps PseudoConwayLattice in the way we would like them to be. It seems reasonable to me to keep the error on x == loads(dumps(x)) and document it.

I think this is the best solution. Caching the pseudo-Conway lattice just moves the problem but does not fundamentally solve it, since PCL have the same property of not being determined up to unique isomorphism by their defining parameters.

If you want to implement this approach, go ahead. You can try to simply do git revert 48e0ffed and fix the ensuing doctest failures.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​ffd377f	Revert "Trac 14990: fix comparison of elements"
​fdd8837	Trac 14990: do not check pickling of elements in TestSuite, with explanation

[pbruin]

Someone asked me about this today, so I tried my suggestion from comment:78. At this moment the only thing that I'm not too sure about is if non-identical parents should be allowed to compare equal. At this moment they compare equal if and only if their PCLs compare equal. There is something to be said for the convention that two instances should be equal if and only if they are identical, but the current state of affairs does not seem to break anything, so we can also decide to leave it like it is.

[vdelecroix]

Hi Peter,

Thank you.

1) I found that your explanation is rather vague: it is not clear if you speak about mathematics or the Sage implementation. Moreover, this weirdness only concerns pseudo-Conway implementation (which is right now the only one). In a future, we might implement Jean-Pierre idea: deal with Conway polynomial or have a certified- non-random version of pseudo-Conway.

2) It must absolutely be clear in the documentation of .algebraic_closure that the pickling is broken! This is the main entry point for users.

3) Do you agree to add to the documentation the different weirdnesses I described in my comments ? (possibly in a TODO section)

Best Vincent

[pbruin]

Hi Vincent,

1) I found that your explanation is rather vague: it is not clear if you speak about mathematics or the Sage implementation.

Both: mathematically speaking, algebraic closures are not unique up to unique isomorphism unless you fix some standard model, and therefore we necessarily have a similar non-uniqueness in Sage reflecting this mathematical fact. I tried to make clear how the mathematical fact influences the Sage implementation, but let me know if you have a concrete idea for improving this paragraph.

Moreover, this weirdness only concerns pseudo-Conway implementation (which is right now the only one).

Certainly, that is why the new paragraph starts with "In the current implementation".

In a future, we might implement Jean-Pierre idea: deal with Conway polynomial or have a certified- non-random version of pseudo-Conway.

Of course, but we are still in the present... 8-)

(Actually, I'm sceptical about the possibility of defining "certified-non-random version of pseudo-Conway" in a way that would improve on the original Conway polynomials. Besides, I would say that the "idea" of using Conway polynomials should be attributed to Conway!)

2) It must absolutely be clear in the documentation of .algebraic_closure that the pickling is broken! This is the main entry point for users.

OK, I'll add some explanation there too. But I am against phrasing it as "pickling is broken"; we should really say that this is an inherent "feature" of the non-unicity of algebraic closures, at least until we support any standard model.

3) Do you agree to add to the documentation the different weirdnesses I described in my comments ? (possibly in a TODO section)

I don't see quickly which "weirdnesses" are still remaining, could you give me a list?

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​b1d4424

Trac 14990: expand documentation of FiniteField_base.algebraic_closure()

[vdelecroix]

Dear Peter,

I like very much the documentation in algebraic_closure. Thank you.

For each problem below, I think we need to find a solution which might be: either write specifications in the documentation or provide a fix that change the behaviour.

1) Equality among algebraic closures is not constant over time:

sage: F1 = AlgebraicClosureFiniteField(GF(3), 'z', use_database=False)
sage: F2 = AlgebraicClosureFiniteField(GF(3), 'z', use_database=False)
sage: F1 == F2
True
sage: F1.gen(3)
z3
sage: F1 == F2
False
sage: F2.gen(3)
z3
sage: F1 == F2
True

It becomes really weird when we play with pickling

sage: p = 100003
sage: K = GF(p).algebraic_closure()
sage: K2 = loads(dumps(K))
sage: K.gen(3)
z3
sage: K == K2
False

One fix is to use identity in comparisons of the parent themselves as I suggested in previous comments. The only drawback I see is that K == loads(dumps(K)) will be False. I think it would be safer that way.

2) Get a very strange error from conversions between different algebraic closures that can be fixed introducing more type checking in the methods.

sage: from sage.rings.algebraic_closure_finite_field import AlgebraicClosureFiniteField
sage: F1 = AlgebraicClosureFiniteField(GF(3), 'z')
sage: F2 = AlgebraicClosureFiniteField(GF(3), 'z')
sage: F1(F2.gen(1))
Traceback (most recent call last):
...
TypeError: no canonical coercion from Algebraic closure of Finite Field of size 3 to Finite Field of size 3

3) (minor) The cache in algebraic_closure does not take into account the default arguments.

sage: K1 = GF(5).algebraic_closure(implementation='pseudo_conway', use_database=True)
sage: K2 = GF(5).algebraic_closure(implementation='pseudo_conway')
sage: K4 = GF(5).algebraic_closure()
sage: K1 is K2 or K1 is K3 or K2 is K3
False

One fix is to move the cache at the level of AlgebraicClosureFiniteField, but on the other hand it is good to have the cache at a Cython level.

That's all Vincent

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​4ac10fb	Trac 14990: compare pseudo-Conway algebraic closures by ID
​63bc7aa	Trac 14990: more informative error message in _element_constructor_()

[pbruin]

Thanks for your feedback, Vincent! The two new commits should address your points (1) and (2), respectively. As for (3), I thought about moving the cache to AlgebraicClosureFiniteField, but then we would have to be very careful with weak references to make sure we don't store every algebraic closure forever. Another (ugly) solution would be to duplicate the same default arguments everywhere. I think it is not really worth the trouble, especially because the following does work:

sage: GF(5).algebraic_closure('z') is GF(5).algebraic_closure()
True

I expect it is much more likely that users switch between specifying the 'z' or not than that they switch between specifying keyword arguments or not.

[vdelecroix]

Hi Peter,

I agree with your analysis of (3).

All test pass and the documentation builds.

There is a typo which becomes ugly in the compiled documentation. At line 960 of algebraic_closure_finite_field.py you wrote `:meth:~sage.rings.finite_rings.finite_field_base.FiniteField.algebraic_closure` instead of :meth:`~sage.rings.finite_rings.finite_field_base.FiniteField.algebraic_closure`.

Once the change done, you can set to positive review.

Vincent

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​b0e1539

Trac 14990: fix typo in documentation

[pbruin]

Done. Thanks a lot for your thorough review!

[slelievre]

Some change introduced by this ticket is being discussed in ​this sage-devel thread.

[zimmerma]

for information, Pari/GP 2.10 implements finite field embeddings. See ​http://pari.math.u-bordeaux.fr/Events/PARI2018/talks/features.pdf

[defeo]

Flint will soon have them too. See ​https://github.com/wbhart/flint2/pull/351.

Are the embeddings in PARI/GP compatible?

[vdelecroix]

Would be nice to have both of them interfaced in Sage together with the version that is already there!

[defeo]

Replying to vdelecroix:

Would be nice to have both of them interfaced in Sage together with the version that is already there!

That's part of our plans. Not immediately, though.