#14990 closed enhancement (fixed)
Implement algebraic closures of finite fields
Reported by: | pbruin | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.3 |
Component: | algebra | Keywords: | finite field algebraic closure |
Cc: | roed, jpflori, JCooley, dfesti, defeo, vdelecroix, erousseau | Merged in: | |
Authors: | Peter Bruin | Reviewers: | Vincent Delecroix |
Report Upstream: | N/A | Work issues: | |
Branch: | b0e1539 (Commits, GitHub, GitLab) | Commit: | |
Dependencies: | #14958, #13214 | Stopgaps: |
Description (last modified by )
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 pn and aRingHomomorphism_im_gens
giving the canonical embedding into the algebraic closure
- method
- 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 aroundFiniteFieldElement
, 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.
Attachments (1)
Change History (97)
comment:1 follow-up: ↓ 2 Changed 8 years ago by
comment:2 in reply to: ↑ 1 Changed 8 years ago by
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.
comment:3 Changed 8 years ago by
- Dependencies changed from #14958 to #14958, #13214
- Description modified (diff)
- Status changed from new to needs_review
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 Fp. But this can probably wait until another ticket.
comment:4 Changed 8 years ago by
- Description modified (diff)
comment:5 Changed 8 years ago by
- Milestone changed from sage-5.12 to sage-5.13
comment:6 Changed 7 years ago by
Patch updated; now also implements is_square()
and sqrt()
, and makes doctests pass again.
comment:7 follow-up: ↓ 8 Changed 7 years ago by
- Cc defeo added
Nice work. I agree this is the way to go for Fp-bar. Here's some thoughts.
- It'd be nice to implement a
_latex_
method in the elements.
- There's a quote problem in the first paragraph of the docstring:
'[\Bold{F}_n:\Bold{F}]=1`
- I'm perplexed about the
_cmp_
function inconway_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?
F.inclusion(1, a).section()
isNone
for anya
, this makes_change_level
fail.
- I wonder: wouldn't it be more efficient if
_coerce_2
had a shortcut for whenx
andy
are in the same level? (I really don't know, just wondering)
- 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?
comment:8 in reply to: ↑ 7 Changed 7 years ago by
Replying to defeo:
Nice work. I agree this is the way to go for Fp-bar. Here's some thoughts.
- It'd be nice to implement a
_latex_
method in the elements.
Sure.
- There's a quote problem in the first paragraph of the docstring:
'[\Bold{F}_n:\Bold{F}]=1`
- I'm perplexed about the
_cmp_
function inconway_polynomials.py
:sage: PCL3 = PseudoConwayLattice(3, use_database=False) sage: PCL5 = PseudoConwayLattice(5, use_database=False) sage: PCL3 == PCL5 TrueIs this the intended result?
This looks wrong to me.
F.inclusion(1, a).section()
isNone
for anya
, this makes_change_level
fail.
- I wonder: wouldn't it be more efficient if
_coerce_2
had a shortcut for whenx
andy
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.
- 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.
comment:9 follow-up: ↓ 49 Changed 7 years ago by
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 concernsminimal_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
comment:10 Changed 7 years ago by
- Cc vdelecroix added
comment:11 follow-up: ↓ 12 Changed 7 years ago by
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-)
comment:12 in reply to: ↑ 11 ; follow-ups: ↓ 13 ↓ 15 Changed 7 years ago by
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 ?
comment:13 in reply to: ↑ 12 ; follow-up: ↓ 14 Changed 7 years ago by
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?
comment:14 in reply to: ↑ 13 Changed 7 years ago by
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
comment:15 in reply to: ↑ 12 ; follow-up: ↓ 16 Changed 7 years ago by
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.
comment:16 in reply to: ↑ 15 ; follow-up: ↓ 27 Changed 7 years ago by
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
comment:17 Changed 7 years ago by
- Created changed from 07/31/13 16:22:09 to 07/31/13 16:22:09
- Modified changed from 11/09/13 23:47:07 to 11/09/13 23:47:07
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...
comment:18 Changed 7 years ago by
- Branch set to u/pbruin/14990
comment:19 follow-up: ↓ 20 Changed 7 years ago by
- Commit set to dbc331bb85d634cb9cb6c75ad8dd82764c066f39
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() |
comment:20 in reply to: ↑ 19 ; follow-up: ↓ 21 Changed 7 years ago by
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?
comment:21 in reply to: ↑ 20 Changed 7 years ago by
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.
comment:22 Changed 7 years ago by
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
comment:23 follow-up: ↓ 26 Changed 7 years ago by
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
comment:24 Changed 7 years ago by
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.
comment:25 Changed 7 years ago by
- Commit changed from dbc331bb85d634cb9cb6c75ad8dd82764c066f39 to f8540ae3547c28c717c41a44b7791f86d596427e
comment:26 in reply to: ↑ 23 Changed 7 years ago by
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
comment:27 in reply to: ↑ 16 Changed 7 years ago by
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.
comment:28 Changed 7 years ago by
- Description modified (diff)
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?
comment:29 follow-up: ↓ 30 Changed 7 years ago by
- Status changed from needs_review to needs_work
- Work issues set to see comment 29
The following problems observed by Luca in comment:7 still need to be fixed:
- It'd be nice to implement a _latex_ method in the elements.
- F.inclusion(1, a).section() is None for any a, this makes _change_level fail.
- 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?
comment:30 in reply to: ↑ 29 ; follow-up: ↓ 31 Changed 7 years ago by
Replying to pbruin:
The following problems observed by Luca in comment:7 still need to be fixed:
- It'd be nice to implement a _latex_ method in the elements.
- F.inclusion(1, a).section() is None for any a, this makes _change_level fail.
- 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.
comment:31 in reply to: ↑ 30 ; follow-up: ↓ 35 Changed 7 years ago by
Replying to vdelecroix:
Replying to pbruin:
The following problems observed by Luca in comment:7 still need to be fixed:
- It'd be nice to implement a _latex_ method in the elements.
- F.inclusion(1, a).section() is None for any a, this makes _change_level fail.
- 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.
comment:32 Changed 7 years ago by
- Commit changed from f8540ae3547c28c717c41a44b7791f86d596427e to 6325b20ee46837e1d700a9df41a4582966406068
comment:33 follow-up: ↓ 34 Changed 7 years ago by
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.
comment:34 in reply to: ↑ 33 ; follow-up: ↓ 36 Changed 7 years ago by
Replying to pbruin:
One issue I have some doubts about is whether the
name
argument ofFiniteField.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 withzeta
; but in this case one could argue that this naming convention is practically universal. In the case ofAA
andQQbar
, the namea
is used for the generator inas_number_field_element()
, and here one cannot even specify a name; this seems to go against the convention as well.
comment:35 in reply to: ↑ 31 Changed 7 years ago by
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.
comment:36 in reply to: ↑ 34 Changed 7 years ago by
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 thanGF(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.
comment:37 Changed 7 years ago by
- Commit changed from 6325b20ee46837e1d700a9df41a4582966406068 to 5fe4189d600b3bd56a663f6155831ce949e846f5
Branch pushed to git repo; I updated commit sha1. New commits:
5fe4189 | matrix2.pyx: no special case for finite fields in F.algebraic_closure() |
comment:38 Changed 7 years ago by
- Description modified (diff)
- Modified changed from 11/21/13 20:38:11 to 11/21/13 20:38:11
- Work issues see comment 29 deleted
comment:39 follow-up: ↓ 40 Changed 7 years ago by
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.
comment:40 in reply to: ↑ 39 ; follow-up: ↓ 41 Changed 7 years ago by
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()
usecheck_irreducible=False
in theFiniteField
constructor? It looks like a waste to check twice for irreducibility.
Good idea, I'll rebase this ticket and then disable the check.
comment:41 in reply to: ↑ 40 ; follow-up: ↓ 43 Changed 7 years ago by
Replying to pbruin:
Good idea, I'll rebase this ticket and then disable the check.
Why "rebase"? Maybe you meant "merge master"?
comment:42 Changed 7 years ago by
- Commit changed from 5fe4189d600b3bd56a663f6155831ce949e846f5 to 4265b4fe176d32b3bc7cbc616f8f0964e273ecdb
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 |
comment:43 in reply to: ↑ 41 ; follow-up: ↓ 44 Changed 7 years ago by
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).
comment:44 in reply to: ↑ 43 ; follow-up: ↓ 45 Changed 7 years ago by
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?
comment:45 in reply to: ↑ 44 ; follow-up: ↓ 46 Changed 7 years ago by
Although if I read the
git-rebase
man page correctly, merging our branches will now create even more duplicates because of myrebase
. 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.
comment:46 in reply to: ↑ 45 ; follow-up: ↓ 47 Changed 7 years ago by
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).
comment:47 in reply to: ↑ 46 Changed 7 years ago by
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).
comment:48 Changed 7 years ago by
comment:49 in reply to: ↑ 9 Changed 7 years ago by
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 concernsminimal_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.
comment:50 Changed 7 years ago by
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 xn - 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.
comment:51 Changed 7 years ago by
- Commit changed from 4265b4fe176d32b3bc7cbc616f8f0964e273ecdb to 70f07cafc62f0fdf6d3f3897973fd33400168d40
Branch pushed to git repo; I updated commit sha1. New commits:
70f07ca | implement three more methods |
comment:52 Changed 7 years ago by
- Commit changed from 70f07cafc62f0fdf6d3f3897973fd33400168d40 to 7b3d68a49b460e336f98c46c7f219fc2f2fbd78f
Branch pushed to git repo; I updated commit sha1. New commits:
7b3d68a | cosmetic improvement to nth_root()
|
comment:53 Changed 7 years ago by
- Status changed from needs_work to needs_review
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
.
comment:54 Changed 7 years ago by
- Commit changed from 7b3d68a49b460e336f98c46c7f219fc2f2fbd78f to ff35daa8828581bb74f929131dd352204a6f8cb1
Branch pushed to git repo; I updated commit sha1. New commits:
ff35daa | Merge branch 'develop' into ticket/14990
|
comment:55 Changed 7 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:56 Changed 7 years ago by
- Commit changed from ff35daa8828581bb74f929131dd352204a6f8cb1 to 785c7b90031db8fc32b5a271e5bca538027bcfc1
comment:57 follow-up: ↓ 58 Changed 7 years ago by
- Status changed from needs_review to needs_info
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 anEXAMPLE
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 dosage: GF(5).algebraic_closure(implementation='pseudo_conway')
- for
_get_polynomial
and_get_im_gen
we could use the decorator@abstract_method
(fromsage.misc.abstract_method
). That way, their existence become part of theTestSuite
and there is no need for theNotImplementedError
. There are many example of its usage insage/categories
.
- It would be better to move the test lines 41-44 inside the constructor of
AlgebraicClosure
and rather useAlgebraicClosureFiniteField_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
comment:58 in reply to: ↑ 57 Changed 7 years ago by
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 toAlgebraicClosureFiniteField_pseudo_conway
but in practice this should be avoided as we havesage: F = AlgebraicClosureFiniteField_pseudo_conway(GF(5),'z') sage: z = F.an_element() sage: z == loads(dumps(z)) FalseI 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.
comment:59 Changed 7 years ago by
- Commit changed from 785c7b90031db8fc32b5a271e5bca538027bcfc1 to 48e0ffed9690ba9614f7a1655bc2f02465cff4b0
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
|
comment:60 Changed 7 years ago by
- Status changed from needs_info to needs_review
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
.)
comment:61 Changed 7 years ago by
- Commit changed from 48e0ffed9690ba9614f7a1655bc2f02465cff4b0 to 33f982f1acbf61cf08897e6a46ee23bb14e78e1e
Branch pushed to git repo; I updated commit sha1. New commits:
33f982f | Trac 14990: small documentation improvements
|
comment:62 follow-ups: ↓ 63 ↓ 64 Changed 7 years ago by
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 fromUniqueRepresentation
- add a non optional argument
lattice
in the constructor ofAlgebraicClosureFiniteField_pseudo_conway
that can also be used from something likeGF(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__
inAlgebraicClosureFiniteField_pseudo_conway
that avoid the factory (but I guess that it should be taken care by theUniqueRepresentation
)
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
comment:63 in reply to: ↑ 62 Changed 7 years ago by
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.)
comment:64 in reply to: ↑ 62 Changed 7 years ago by
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.
comment:65 follow-ups: ↓ 66 ↓ 71 Changed 7 years ago by
- Status changed from needs_review to needs_work
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.
comment:66 in reply to: ↑ 65 ; follow-up: ↓ 67 Changed 7 years ago by
Replying to vdelecroix:
Hello,
Thanks Peter and Luca for the lights.
1) For the comparison of
AlgebraicClosureFiniteField
you rely on the equality inPseudoConwayLattice
... which is not exactly what you want. It compares the nodes which is something dynamical by definition. We have for examplesage: 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!!?? TrueIt 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_lattice2) 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 methodpolynomial
). That way we can already have two implementations of the algebraic closure (callingPseudoConwayLattice
with the optionuse_database=True
oruse_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 methodassociated_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 :)
comment:67 in reply to: ↑ 66 Changed 7 years ago by
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 inPseudoConwayLattice
... which is not exactly what you want. It compares the nodes which is something dynamical by definition. We have for examplesage: 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!!?? TrueIt 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).
comment:68 Changed 7 years ago by
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.
comment:69 follow-up: ↓ 72 Changed 7 years ago by
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
comment:70 Changed 7 years ago by
- Commit changed from 33f982f1acbf61cf08897e6a46ee23bb14e78e1e to f9162dbae92551a67aea7a489d96591141fdebc8
comment:71 in reply to: ↑ 65 ; follow-up: ↓ 73 Changed 7 years ago by
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 methodpolynomial
). That way we can already have two implementations of the algebraic closure (callingPseudoConwayLattice
with the optionuse_database=True
oruse_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 methodassociated_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 Fp either.
comment:72 in reply to: ↑ 69 ; follow-up: ↓ 74 Changed 7 years ago by
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.
comment:73 in reply to: ↑ 71 Changed 7 years ago by
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 methodpolynomial
). That way we can already have two implementations of the algebraic closure (callingPseudoConwayLattice
with the optionuse_database=True
oruse_database=False
).This is implemented in one of the two new commits; one can now pass a
lattice
argument, and theuse_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 abase_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 methodassociated_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 Fp either.
Agreed.
comment:74 in reply to: ↑ 72 Changed 7 years ago by
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
.
comment:75 Changed 7 years ago by
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
.
comment:76 follow-up: ↓ 78 Changed 7 years ago by
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.
comment:77 Changed 7 years ago by
ping
Do you want that I give it a try?
Vincent
comment:78 in reply to: ↑ 76 Changed 7 years ago by
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 onx == 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.
comment:79 Changed 7 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:80 Changed 7 years ago by
- Commit changed from f9162dbae92551a67aea7a489d96591141fdebc8 to fdd883792076e8cdb2b1ae7a15cfe28b36d653ca
comment:81 Changed 7 years ago by
- Status changed from needs_work to needs_review
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.
comment:82 follow-up: ↓ 83 Changed 7 years ago by
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
comment:83 in reply to: ↑ 82 Changed 7 years ago by
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?
comment:84 Changed 7 years ago by
- Commit changed from fdd883792076e8cdb2b1ae7a15cfe28b36d653ca to b1d4424ec179f4975a54a14993e4c842b3fb39f5
Branch pushed to git repo; I updated commit sha1. New commits:
b1d4424 | Trac 14990: expand documentation of FiniteField_base.algebraic_closure()
|
comment:85 Changed 7 years ago by
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
comment:86 Changed 7 years ago by
- Commit changed from b1d4424ec179f4975a54a14993e4c842b3fb39f5 to 63bc7aa3b23e6d7dc4db54de76c60b24134e7895
comment:87 Changed 7 years ago by
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.
comment:88 Changed 7 years ago by
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
comment:89 Changed 7 years ago by
- Commit changed from 63bc7aa3b23e6d7dc4db54de76c60b24134e7895 to b0e1539b899af271fb16dcc6dadfaa7e567620b9
Branch pushed to git repo; I updated commit sha1. New commits:
b0e1539 | Trac 14990: fix typo in documentation
|
comment:90 Changed 7 years ago by
- Reviewers set to Vincent Delecroix
- Status changed from needs_review to positive_review
Done. Thanks a lot for your thorough review!
comment:91 Changed 7 years ago by
- Branch changed from u/pbruin/14990 to b0e1539b899af271fb16dcc6dadfaa7e567620b9
- Resolution set to fixed
- Status changed from positive_review to closed
comment:92 Changed 7 years ago by
- Commit b0e1539b899af271fb16dcc6dadfaa7e567620b9 deleted
Some change introduced by this ticket is being discussed in this sage-devel thread.
comment:93 Changed 3 years ago by
for information, Pari/GP 2.10 implements finite field embeddings. See http://pari.math.u-bordeaux.fr/Events/PARI2018/talks/features.pdf
comment:94 Changed 3 years ago by
Flint will soon have them too. See https://github.com/wbhart/flint2/pull/351.
Are the embeddings in PARI/GP compatible?
comment:95 follow-up: ↓ 96 Changed 3 years ago by
Would be nice to have both of them interfaced in Sage together with the version that is already there!
comment:96 in reply to: ↑ 95 Changed 3 years ago by
- Cc erousseau added
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.
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.