Sage: Ticket #14990: Implement algebraic closures of finite fields
https://trac.sagemath.org/ticket/14990
<p>
The goal of this ticket is a basic implementation of algebraic closures of finite fields. Most importantly, it provides the following:
</p>
<ul><li>class <code>AlgebraicClosureFiniteField_generic</code> (abstract base class)
<ul><li>method <code>subfield(n)</code> returning a tuple consisting of the subfield of order <em>p<sup>n</sup></em> and a <code>RingHomomorphism_im_gens</code> giving the canonical embedding into the algebraic closure
</li></ul></li><li>class <code>AlgebraicClosureFiniteField_pseudo_conway</code> (implements the specific defining polynomials of the finite subfields and the relations between the generators of these subfields)
</li><li>class <code>AlgebraicClosureFiniteFieldElement</code>
(mostly a wrapper around <code>FiniteFieldElement</code>, so actually an element of a finite subfield, but having the algebraic closure as its parent and taking care of coercion into larger subfields)
</li><li>factory class <code>AlgebraicClosureFiniteField</code> (to get unique parents)
</li><li>method <code>FiniteField.algebraic_closure()</code> (invokes the factory class)
</li></ul><p>
An example using the new functionality is the following analogue of the example from <a class="closed ticket" href="https://trac.sagemath.org/ticket/8335" title="enhancement: Finite field lattices via Conway polynomials (closed: fixed)">#8335</a>:
</p>
<pre class="wiki">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
</pre><p>
To add, we first embed into <code>Fbar</code>:
</p>
<pre class="wiki">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
</pre><p>
One can also do this without explicitly invoking the embeddings; as a shortcut, <code>Fbar</code> has a method <code>gen(n)</code> returning the fixed generator of the subfield of degree <em>n</em>, but as an element of <code>Fbar</code>:
</p>
<pre class="wiki">sage: x2 == Fbar.gen(2)
True
sage: x == Fbar.gen(2) + Fbar.gen(3)
True
</pre><p>
It is conceivable that there will be different coexisting implementations (deriving from <code>AlgebraicClosureFiniteField_generic</code>). The current implementation uses Conway polynomials and the pseudo-Conway polynomials from <a class="closed ticket" href="https://trac.sagemath.org/ticket/14958" title="enhancement: Implement pseudo-Conway polynomials (closed: fixed)">#14958</a>, as well as the functionality for finite field homomorphisms provided by <a class="closed ticket" href="https://trac.sagemath.org/ticket/13214" title="enhancement: Finite field homomorphisms and Frobenius endomorphisms (closed: fixed)">#13214</a>.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/14990
Trac 1.1.6jpfloriWed, 31 Jul 2013 17:13:30 GMT
https://trac.sagemath.org/ticket/14990#comment:1
https://trac.sagemath.org/ticket/14990#comment:1
<p>
Another important question is to know what the <a class="missing wiki">AlgebraicClosure?</a> 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.
</p>
TicketpbruinThu, 01 Aug 2013 14:36:40 GMT
https://trac.sagemath.org/ticket/14990#comment:2
https://trac.sagemath.org/ticket/14990#comment:2
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:1" title="Comment 1">jpflori</a>:
</p>
<blockquote class="citation">
<p>
Another important question is to know what the <a class="missing wiki">AlgebraicClosure?</a> 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.
</p>
</blockquote>
<p>
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:
</p>
<ul><li>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;
</li><li>generalise the algorithms for generating pseudo-Conway polynomials in such a way that in order to generate a pseudo-Conway polynomial of degree <em>n</em>, it doesn't need to generate pseudo-Conway polynomials for all degrees dividing <em>n</em>, 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.
</li></ul>
TicketpbruinThu, 15 Aug 2013 14:38:57 GMTstatus, dependencies, description changed; author set
https://trac.sagemath.org/ticket/14990#comment:3
https://trac.sagemath.org/ticket/14990#comment:3
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>dependencies</strong>
changed from <em>#14958</em> to <em>#14958, #13214</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/14990?action=diff&version=3">diff</a>)
</li>
<li><strong>author</strong>
set to <em>Peter Bruin</em>
</li>
</ul>
<p>
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 <strong>F</strong><sub><em>p</em></sub>. But this can probably wait until another ticket.
</p>
TicketpbruinThu, 15 Aug 2013 15:17:41 GMTdescription changed
https://trac.sagemath.org/ticket/14990#comment:4
https://trac.sagemath.org/ticket/14990#comment:4
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/14990?action=diff&version=4">diff</a>)
</li>
</ul>
TicketpbruinFri, 06 Sep 2013 09:12:10 GMTmilestone changed
https://trac.sagemath.org/ticket/14990#comment:5
https://trac.sagemath.org/ticket/14990#comment:5
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.12</em> to <em>sage-5.13</em>
</li>
</ul>
TicketpbruinSun, 03 Nov 2013 00:14:34 GMT
https://trac.sagemath.org/ticket/14990#comment:6
https://trac.sagemath.org/ticket/14990#comment:6
<p>
Patch updated; now also implements <code>is_square()</code> and <code>sqrt()</code>, and makes doctests pass again.
</p>
TicketpbruinSun, 03 Nov 2013 16:50:05 GMTattachment set
https://trac.sagemath.org/ticket/14990
https://trac.sagemath.org/ticket/14990
<ul>
<li><strong>attachment</strong>
set to <em>trac_14990-algebraic_closure_finite_field.patch</em>
</li>
</ul>
<p>
update (doctest coverage)
</p>
TicketdefeoThu, 07 Nov 2013 23:07:15 GMTcc changed
https://trac.sagemath.org/ticket/14990#comment:7
https://trac.sagemath.org/ticket/14990#comment:7
<ul>
<li><strong>cc</strong>
<em>defeo</em> added
</li>
</ul>
<p>
Nice work. I agree this is the way to go for Fp-bar. Here's some thoughts.
</p>
<ol><li>It'd be nice to implement a <code>_latex_</code> method in the elements.
</li></ol><ol start="2"><li>There's a quote problem in the first paragraph of the docstring:
</li></ol><pre class="wiki">'[\Bold{F}_n:\Bold{F}]=1`
</pre><ol start="3"><li>I'm perplexed about the <code>_cmp_</code> function in <code>conway_polynomials.py</code>:
</li></ol><pre class="wiki">sage: PCL3 = PseudoConwayLattice(3, use_database=False)
sage: PCL5 = PseudoConwayLattice(5, use_database=False)
sage: PCL3 == PCL5
True
</pre><blockquote>
<p>
Is this the intended result?
</p>
</blockquote>
<ol start="4"><li><code>F.inclusion(1, a).section()</code> is <code>None</code> for any <code>a</code>, this makes <code>_change_level</code> fail.
</li></ol><ol start="5"><li>I wonder: wouldn't it be more efficient if <code>_coerce_2</code> had a shortcut for when <code>x</code> and <code>y</code> are in the same level? (I really don't know, just wondering)
</li></ol><ol start="6"><li>This patch lacks some obvious coercions, for example, <code>F._subfield(2)(F.gen(2))</code>. Should this wait for another ticket, or should this ticket do it?
</li></ol><p>
I'd like to play around with different implementations of Fp-bar. This would help understand if the abstract class <code>AlgebraicClosureFiniteField_generic</code> is abstract enough, or if we need to think more carefully about its interface.
</p>
<p>
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?
</p>
<p>
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?
</p>
TicketjpfloriFri, 08 Nov 2013 09:37:30 GMT
https://trac.sagemath.org/ticket/14990#comment:8
https://trac.sagemath.org/ticket/14990#comment:8
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:7" title="Comment 7">defeo</a>:
</p>
<blockquote class="citation">
<p>
Nice work. I agree this is the way to go for Fp-bar. Here's some thoughts.
</p>
<ol><li>It'd be nice to implement a <code>_latex_</code> method in the elements.
</li></ol></blockquote>
<p>
Sure.
</p>
<blockquote class="citation">
<ol start="2"><li>There's a quote problem in the first paragraph of the docstring:
</li></ol><pre class="wiki">'[\Bold{F}_n:\Bold{F}]=1`
</pre><ol start="3"><li>I'm perplexed about the <code>_cmp_</code> function in <code>conway_polynomials.py</code>:
</li></ol><pre class="wiki">sage: PCL3 = PseudoConwayLattice(3, use_database=False)
sage: PCL5 = PseudoConwayLattice(5, use_database=False)
sage: PCL3 == PCL5
True
</pre><blockquote>
<p>
Is this the intended result?
</p>
</blockquote>
</blockquote>
<p>
This looks wrong to me.
</p>
<blockquote class="citation">
<ol start="4"><li><code>F.inclusion(1, a).section()</code> is <code>None</code> for any <code>a</code>, this makes <code>_change_level</code> fail.
</li></ol><ol start="5"><li>I wonder: wouldn't it be more efficient if <code>_coerce_2</code> had a shortcut for when <code>x</code> and <code>y</code> are in the same level? (I really don't know, just wondering)
</li></ol></blockquote>
<p>
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).
</p>
<p>
About the shortcut, why not, but it does not seem that urgent.
Maybe we should do some timings.
</p>
<blockquote class="citation">
<ol start="6"><li>This patch lacks some obvious coercions, for example, <code>F._subfield(2)(F.gen(2))</code>. Should this wait for another ticket, or should this ticket do it?
</li></ol></blockquote>
<p>
Depends on the difficulty? :)
</p>
<blockquote class="citation">
<p>
I'd like to play around with different implementations of Fp-bar. This would help understand if the abstract class <code>AlgebraicClosureFiniteField_generic</code> is abstract enough, or if we need to think more carefully about its interface.
</p>
<p>
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?
</p>
<p>
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?
</p>
</blockquote>
<p>
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.
</p>
<p>
In particular, I'd like to make sure that this gets well with <a class="closed ticket" href="https://trac.sagemath.org/ticket/715" title="defect: Parents probably not reclaimed due to too much caching (closed: fixed)">#715</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/11521" title="defect: Use weak references to cache homsets (closed: fixed)">#11521</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/14711" title="defect: Weak references in the coercion graph (closed: fixed)">#14711</a>, <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/15303" title="defect: Coercion discovery fails to be transitive (needs_work)">#15303</a> 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.
</p>
<p>
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 <a class="missing wiki">AlgebraicClosureFunctor?</a> from sage.categories.pushout?
Not sure how harmful it would be to modify that after the current ticket is merged.
</p>
TicketvdelecroixFri, 08 Nov 2013 13:35:42 GMT
https://trac.sagemath.org/ticket/14990#comment:9
https://trac.sagemath.org/ticket/14990#comment:9
<p>
Hi,
</p>
<p>
Thanks for the nice patch! I played a little bit with the patch and here are few comments (from a user point of vue).
</p>
<p>
For the <code>FiniteFieldAlgebraicClosure</code>
</p>
<ul><li>the method .cardinality() fails
</li><li>.some_elements() returns a very stupid list
</li><li>.gens() is not happy. I guess we can return a <code>Family</code>. The problem is that in the specification it is written that the method should return a tuple.
</li></ul><p>
For elements
</p>
<ul><li>many methods can be implemented in two lines as
<pre class="wiki"> def my_method(self):
return self._value.my_method()
</pre>this concerns <code>minimal_polynomial</code>, <code>trace</code>, <code>norm</code>, <code>multiplicative_order</code>, ...
</li><li>in a similar way (calling apropriate method of _value and applying a morphism) it is straightforward to implement <code>frobenius</code>, <code>pth_power</code>, <code>pth_root</code>, ...
</li><li>to mimic AA or QQbar I would like a method <code></code>as_finite_field_element(self, minimal=False)<code></code> which return a triple (finite_field, value, homomorphism)
</li></ul><p>
Vincent
</p>
TicketvdelecroixFri, 08 Nov 2013 13:36:14 GMTcc changed
https://trac.sagemath.org/ticket/14990#comment:10
https://trac.sagemath.org/ticket/14990#comment:10
<ul>
<li><strong>cc</strong>
<em>vdelecroix</em> added
</li>
</ul>
TicketpbruinFri, 08 Nov 2013 13:43:27 GMT
https://trac.sagemath.org/ticket/14990#comment:11
https://trac.sagemath.org/ticket/14990#comment:11
<p>
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-)
</p>
TicketvdelecroixFri, 08 Nov 2013 19:53:13 GMT
https://trac.sagemath.org/ticket/14990#comment:12
https://trac.sagemath.org/ticket/14990#comment:12
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:11" title="Comment 11">pbruin</a>:
</p>
<blockquote class="citation">
<p>
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-)
</p>
</blockquote>
<p>
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 ?
</p>
TicketdefeoSat, 09 Nov 2013 09:59:50 GMT
https://trac.sagemath.org/ticket/14990#comment:13
https://trac.sagemath.org/ticket/14990#comment:13
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:12" title="Comment 12">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
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 ?
</p>
</blockquote>
<p>
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?
</p>
TicketvdelecroixSat, 09 Nov 2013 16:17:03 GMT
https://trac.sagemath.org/ticket/14990#comment:14
https://trac.sagemath.org/ticket/14990#comment:14
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:13" title="Comment 13">defeo</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:12" title="Comment 12">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
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 ?
</p>
</blockquote>
<p>
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?
</p>
</blockquote>
<p>
This is: u/vdelecroix/14990
</p>
TicketpbruinSat, 09 Nov 2013 18:57:30 GMT
https://trac.sagemath.org/ticket/14990#comment:15
https://trac.sagemath.org/ticket/14990#comment:15
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:12" title="Comment 12">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:11" title="Comment 11">pbruin</a>:
</p>
<blockquote class="citation">
<p>
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-)
</p>
</blockquote>
<p>
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 ?
</p>
</blockquote>
<p>
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.
</p>
TicketvdelecroixSat, 09 Nov 2013 23:47:07 GMT
https://trac.sagemath.org/ticket/14990#comment:16
https://trac.sagemath.org/ticket/14990#comment:16
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:15" title="Comment 15">pbruin</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:12" title="Comment 12">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:11" title="Comment 11">pbruin</a>:
</p>
<blockquote class="citation">
<p>
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-)
</p>
</blockquote>
<p>
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 ?
</p>
</blockquote>
<p>
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.
</p>
</blockquote>
<p>
Hi Peter,
</p>
<p>
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
</p>
<ul><li>.is_finite() fails on GF(3).algebraic_closure() (raise a <a class="missing wiki">NotImplementedError?</a>). On the other hand it will be fixed with the new category schemes which allows Field().infinite())
</li><li>Zmod(3) does not support algebraic_closure()
</li></ul><p>
From the last version <a class="closed ticket" href="https://trac.sagemath.org/ticket/15390" title="enhancement: roots of polynomials and eigenvalues of matrices over finite fields (closed: fixed)">#15390</a> (roots of polynomial and eigenvalues) works nicely !
</p>
<p>
Your work is really nice!
</p>
<p>
Cheers,
Vincent
</p>
TicketpbruinWed, 13 Nov 2013 14:10:38 GMTchangetime, time changed
https://trac.sagemath.org/ticket/14990#comment:17
https://trac.sagemath.org/ticket/14990#comment:17
<ul>
<li><strong>changetime</strong>
changed from <em>11/09/13 23:47:07</em> to <em>11/09/13 23:47:07</em>
</li>
<li><strong>time</strong>
changed from <em>07/31/13 16:22:09</em> to <em>07/31/13 16:22:09</em>
</li>
</ul>
<p>
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...
</p>
TicketpbruinWed, 13 Nov 2013 14:37:33 GMTbranch set
https://trac.sagemath.org/ticket/14990#comment:18
https://trac.sagemath.org/ticket/14990#comment:18
<ul>
<li><strong>branch</strong>
set to <em>u/pbruin/14990</em>
</li>
</ul>
TicketvdelecroixWed, 13 Nov 2013 15:19:12 GMTcommit set
https://trac.sagemath.org/ticket/14990#comment:19
https://trac.sagemath.org/ticket/14990#comment:19
<ul>
<li><strong>commit</strong>
set to <em>dbc331bb85d634cb9cb6c75ad8dd82764c066f39</em>
</li>
</ul>
<p>
Hi,
</p>
<p>
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)
</p>
<pre class="wiki">if x._level == y._level:
return x._value, y._value
</pre><p>
(when the level is the same I go from 3ms to 0.8ms)
</p>
<p>
What do you think about what I suggest in <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:15" title="Comment 15">comment:15</a> namely, implementing .is_finite() (returning False) and do something for Zmod(3) ?
</p>
<hr />
<p>
Last 10 new commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=dbc331b"><span class="icon"></span>dbc331b</a></td><td>rename _coerce_2 to _to_common_subfield; cosmetic changes
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=ac93a01"><span class="icon"></span>ac93a01</a></td><td>remove the optional name from algebraic_closure examples
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=2432102"><span class="icon"></span>2432102</a></td><td>allow no argument for .algebraic_closure()
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=a197d0d"><span class="icon"></span>a197d0d</a></td><td>Merge branch 'u/vdelecroix/14990' of <a class="ext-link" href="ssh://trac.sagemath.org:2222/sage"><span class="icon"></span>ssh://trac.sagemath.org:2222/sage</a> into 14990
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=f232993"><span class="icon"></span>f232993</a></td><td>fix the parent in pth_root and pth_power
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=0f4b895"><span class="icon"></span>0f4b895</a></td><td>add examples to .cardinality()
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=d95f57f"><span class="icon"></span>d95f57f</a></td><td>more methods to algebraic elements
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=081c096"><span class="icon"></span>081c096</a></td><td>Trac 14990: implement algebraic closures of finite fields
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=31045f7"><span class="icon"></span>31045f7</a></td><td>fix the parent in pth_root and pth_power
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=3d88af6"><span class="icon"></span>3d88af6</a></td><td>add examples to .cardinality()
</td></tr></table>
TicketpbruinWed, 13 Nov 2013 15:38:27 GMT
https://trac.sagemath.org/ticket/14990#comment:20
https://trac.sagemath.org/ticket/14990#comment:20
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:19" title="Comment 19">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
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)
</p>
</blockquote>
<p>
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?
</p>
TicketvdelecroixWed, 13 Nov 2013 15:51:42 GMT
https://trac.sagemath.org/ticket/14990#comment:21
https://trac.sagemath.org/ticket/14990#comment:21
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:20" title="Comment 20">pbruin</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:19" title="Comment 19">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
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)
</p>
</blockquote>
<p>
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?
</p>
</blockquote>
<p>
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
</p>
<pre class="wiki">$ git checkout THE_NAME_OF_MY_LOCAL_BRANCH_FOR_14990
$ git pull trac u/vdelecroix/14990
$ git reset --merge
</pre><p>
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.
</p>
<p>
I will tell you when I am done.
</p>
TicketjpfloriWed, 13 Nov 2013 15:56:48 GMT
https://trac.sagemath.org/ticket/14990#comment:22
https://trac.sagemath.org/ticket/14990#comment:22
<p>
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.
</p>
<ul><li>"git fetch --all" (or just the remote name if you don't want --all) to update the remote branch.
</li><li>"git checkout my_local_branch" to go to my branch.
</li><li>"git merge remote_name" to merge the remote change locally.
</li></ul><p>
Best,
JP
</p>
TicketvdelecroixWed, 13 Nov 2013 16:09:41 GMT
https://trac.sagemath.org/ticket/14990#comment:23
https://trac.sagemath.org/ticket/14990#comment:23
<p>
Hey,
</p>
<p>
Thanks Jean-Pierre for the suggestion. My method is what is described in the <a class="ext-link" href="http://sagemath.github.io/git-developer-guide/manual_git.html#getting_changes"><span class="icon"></span>developer guide</a>. Anyway, how should I do to declare u/pbruin/14990 on trac has a remote ?
</p>
<p>
Best,
Vincent
</p>
TicketvdelecroixWed, 13 Nov 2013 16:18:06 GMT
https://trac.sagemath.org/ticket/14990#comment:24
https://trac.sagemath.org/ticket/14990#comment:24
<p>
Hi,
</p>
<p>
I push my changes to u/vdelecroix/14990. For the Zmod(p) suggestion it is actually possible to obtain the algebraic closure with
</p>
<pre class="wiki">sage: Zmod(3).field().algebraic_closure()
Algebraic closure of Finite Field of size 3
</pre><p>
So I think there is nothing to change here.
</p>
<p>
V.
</p>
TicketgitWed, 13 Nov 2013 17:25:49 GMTcommit changed
https://trac.sagemath.org/ticket/14990#comment:25
https://trac.sagemath.org/ticket/14990#comment:25
<ul>
<li><strong>commit</strong>
changed from <em>dbc331bb85d634cb9cb6c75ad8dd82764c066f39</em> to <em>f8540ae3547c28c717c41a44b7791f86d596427e</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=f8540ae"><span class="icon"></span>f8540ae</a></td><td>fix comparison of pseudo-Conway polynomial trees
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=d6cf8d6"><span class="icon"></span>d6cf8d6</a></td><td>tiny optimization for _to_common_subfield and implementation of is_finite.
</td></tr></table>
TicketjpfloriWed, 13 Nov 2013 17:27:29 GMT
https://trac.sagemath.org/ticket/14990#comment:26
https://trac.sagemath.org/ticket/14990#comment:26
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:23" title="Comment 23">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
Hey,
</p>
<p>
Thanks Jean-Pierre for the suggestion. My method is what is described in the <a class="ext-link" href="http://sagemath.github.io/git-developer-guide/manual_git.html#getting_changes"><span class="icon"></span>developer guide</a>. Anyway, how should I do to declare u/pbruin/14990 on trac has a remote ?
</p>
</blockquote>
<p>
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!).
</p>
<p>
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:
</p>
<ul><li>git remote set-branches trac --add u/pbruin/14990
</li></ul>
TicketpbruinWed, 13 Nov 2013 17:49:22 GMT
https://trac.sagemath.org/ticket/14990#comment:27
https://trac.sagemath.org/ticket/14990#comment:27
<p>
Hi Vincent,
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:16" title="Comment 16">vdelecroix</a>:
</p>
<blockquote class="citation">
<ul><li>.is_finite() fails on GF(3).algebraic_closure() (raise a <a class="missing wiki">NotImplementedError?</a>). On the other hand it will be fixed with the new category schemes which allows Field().infinite())
</li></ul></blockquote>
<p>
Are you sure we should remove <code>is_finite()</code> and <code>cardinality()</code> after <a class="closed ticket" href="https://trac.sagemath.org/ticket/10963" title="enhancement: Axioms and more functorial constructions (closed: fixed)">#10963</a> is done? Maybe a user wants to pass a custom category to <code>__init__()</code> (say <code>Ring()</code> or <code>Fields()</code>); then the magic wouldn't work anymore, it seems.
</p>
TicketpbruinWed, 13 Nov 2013 17:53:45 GMTdescription changed
https://trac.sagemath.org/ticket/14990#comment:28
https://trac.sagemath.org/ticket/14990#comment:28
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/14990?action=diff&version=28">diff</a>)
</li>
</ul>
<p>
For me Git seems to work fine now; I propose we continue with this.
</p>
<p>
After a combination of Git commands and editing <code>.git/config</code> by hand, it looks as follows:
</p>
<pre class="wiki">[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
</pre><p>
Does this look correct to the more experienced Git users?
</p>
TicketpbruinWed, 13 Nov 2013 18:13:34 GMTstatus changed; work_issues set
https://trac.sagemath.org/ticket/14990#comment:29
https://trac.sagemath.org/ticket/14990#comment:29
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
set to <em>see comment 29</em>
</li>
</ul>
<p>
The following problems observed by Luca in <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:7" title="Comment 7">comment:7</a> still need to be fixed:
</p>
<ol><li>It'd be nice to implement a _latex_ method in the elements.
</li></ol><ol start="4"><li>F.inclusion(1, a).section() is None for any a, this makes _change_level fail.
</li></ol><ol start="6"><li>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?
</li></ol>
TicketvdelecroixFri, 15 Nov 2013 15:41:41 GMT
https://trac.sagemath.org/ticket/14990#comment:30
https://trac.sagemath.org/ticket/14990#comment:30
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:29" title="Comment 29">pbruin</a>:
</p>
<blockquote class="citation">
<p>
The following problems observed by Luca in <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:7" title="Comment 7">comment:7</a> still need to be fixed:
</p>
<ol><li>It'd be nice to implement a _latex_ method in the elements.
</li></ol><ol start="4"><li>F.inclusion(1, a).section() is None for any a, this makes _change_level fail.
</li></ol><ol start="6"><li>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?
</li></ol></blockquote>
<p>
I implemented 1 using self._value._latex_().
</p>
<p>
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.
</p>
<p>
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.
</p>
TicketpbruinFri, 15 Nov 2013 18:21:21 GMT
https://trac.sagemath.org/ticket/14990#comment:31
https://trac.sagemath.org/ticket/14990#comment:31
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:30" title="Comment 30">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:29" title="Comment 29">pbruin</a>:
</p>
<blockquote class="citation">
<p>
The following problems observed by Luca in <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:7" title="Comment 7">comment:7</a> still need to be fixed:
</p>
<ol><li>It'd be nice to implement a _latex_ method in the elements.
</li></ol><ol start="4"><li>F.inclusion(1, a).section() is None for any a, this makes _change_level fail.
</li></ol><ol start="6"><li>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?
</li></ol></blockquote>
<p>
I implemented 1 using self._value._latex_().
</p>
</blockquote>
<p>
That seems like the right solution. The last doctest was wrong, at least on my system; this will be fixed in my next commit.
</p>
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
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 <code>ValueError</code> otherwise.
</p>
<p>
The reason for <code>_change_level()</code> 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.
</p>
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
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 <code>section()</code> method, or we could (less elegantly) teach the element constructors of the various finite field classes to accept elements of an algebraic closure.
</p>
TicketgitFri, 15 Nov 2013 18:28:49 GMTcommit changed
https://trac.sagemath.org/ticket/14990#comment:32
https://trac.sagemath.org/ticket/14990#comment:32
<ul>
<li><strong>commit</strong>
changed from <em>f8540ae3547c28c717c41a44b7791f86d596427e</em> to <em>6325b20ee46837e1d700a9df41a4582966406068</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=6325b20"><span class="icon"></span>6325b20</a></td><td>rename/fix change_level(); new doctests
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=27cc628"><span class="icon"></span>27cc628</a></td><td>add a _latex_ method to the elements
</td></tr></table>
TicketpbruinFri, 15 Nov 2013 18:45:01 GMT
https://trac.sagemath.org/ticket/14990#comment:33
https://trac.sagemath.org/ticket/14990#comment:33
<p>
One issue I have some doubts about is whether the <code>name</code> argument of <code>FiniteField.algebraic_closure(self, name='z')</code> 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.
</p>
<p>
An exception is <code>CyclotomicField()</code>, which generates names starting with <code>zeta</code>; but in this case one could argue that this naming convention is practically universal. In the case of <code>AA</code> and <code>QQbar</code>, the name <code>a</code> is used for the generator in <code>as_number_field_element()</code>, and here one cannot even specify a name; this seems to go against the convention as well.
</p>
TicketvdelecroixFri, 15 Nov 2013 20:09:06 GMT
https://trac.sagemath.org/ticket/14990#comment:34
https://trac.sagemath.org/ticket/14990#comment:34
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:33" title="Comment 33">pbruin</a>:
</p>
<blockquote class="citation">
<p>
One issue I have some doubts about is whether the <code>name</code> argument of <code>FiniteField.algebraic_closure(self, name='z')</code> 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.
</p>
</blockquote>
<p>
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 <a class="closed ticket" href="https://trac.sagemath.org/ticket/15390" title="enhancement: roots of polynomials and eigenvalues of matrices over finite fields (closed: fixed)">#15390</a>) then you do not want to guess about what kind of argument the algebraic closure needs. More precisely, you do
</p>
<pre class="wiki">P.change_ring(P.base_ring().algebraic_closure()).roots()
</pre><p>
I would not be in trouble if we have a default for the generator of finite field, polynomial ring, etc. Actually, <code>GF(9)</code> looks more natural to me than <code>GF(9, 'a')</code> as there is only one field of cardinality 9.
</p>
<blockquote class="citation">
<p>
An exception is <code>CyclotomicField()</code>, which generates names starting with <code>zeta</code>; but in this case one could argue that this naming convention is practically universal. In the case of <code>AA</code> and <code>QQbar</code>, the name <code>a</code> is used for the generator in <code>as_number_field_element()</code>, and here one cannot even specify a name; this seems to go against the convention as well.
</p>
</blockquote>
TicketvdelecroixFri, 15 Nov 2013 20:18:41 GMT
https://trac.sagemath.org/ticket/14990#comment:35
https://trac.sagemath.org/ticket/14990#comment:35
<blockquote class="citation">
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
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 <code>ValueError</code> otherwise.
</p>
<p>
The reason for <code>_change_level()</code> 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.
</p>
</blockquote>
<p>
I see. But then, as a user, you do not want to guess what should be the level. If you have a look at <code>.as_finite_field_element()</code> there is a <code>minimal</code> option if set to True make the method returns the "optimal" level. If you compare with AA and QQbar the methods is called <code>exactify</code> or <code>simplify</code> (I do not understand the subtle difference between those two methods). The two latter do not accept arguments.
</p>
TicketpbruinTue, 19 Nov 2013 14:00:05 GMT
https://trac.sagemath.org/ticket/14990#comment:36
https://trac.sagemath.org/ticket/14990#comment:36
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:34" title="Comment 34">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
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 <a class="closed ticket" href="https://trac.sagemath.org/ticket/15390" title="enhancement: roots of polynomials and eigenvalues of matrices over finite fields (closed: fixed)">#15390</a>) then you do not want to guess about what kind of argument the algebraic closure needs.
</p>
</blockquote>
<p>
Fair point; as far as I am concerned, this is the main argument for allowing a default argument in <code>FiniteField.algebraic_closure()</code>.
</p>
<blockquote class="citation">
<p>
I would not be in trouble if we have a default for the generator of finite field, polynomial ring, etc. Actually, <code>GF(9)</code> looks more natural to me than <code>GF(9, 'a')</code> as there is only one field of cardinality 9.
</p>
</blockquote>
<p>
That is true, but it is only unique up to non-canonical isomorphism, unlike <strong>Z</strong>/9<strong>Z</strong>, for example. To me the notation <code>GF(9)</code> 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.
</p>
<p>
For algebraic closures, I am inclined to say that the current status is not bad: keep <code>'z'</code> as the default name for <code>FiniteField.algebraic_closure()</code>, but don't extend this to a default name for the <code>AlgebraicClosureFiniteField</code> constructor.
</p>
TicketgitThu, 21 Nov 2013 20:38:11 GMTcommit changed
https://trac.sagemath.org/ticket/14990#comment:37
https://trac.sagemath.org/ticket/14990#comment:37
<ul>
<li><strong>commit</strong>
changed from <em>6325b20ee46837e1d700a9df41a4582966406068</em> to <em>5fe4189d600b3bd56a663f6155831ce949e846f5</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=5fe4189"><span class="icon"></span>5fe4189</a></td><td>matrix2.pyx: no special case for finite fields in F.algebraic_closure()
</td></tr></table>
TicketpbruinThu, 21 Nov 2013 20:40:00 GMTchangetime, description changed; work_issues deleted
https://trac.sagemath.org/ticket/14990#comment:38
https://trac.sagemath.org/ticket/14990#comment:38
<ul>
<li><strong>changetime</strong>
changed from <em>11/21/13 20:38:11</em> to <em>11/21/13 20:38:11</em>
</li>
<li><strong>work_issues</strong>
<em>see comment 29</em> deleted
</li>
<li><strong>description</strong>
modified (<a href="/ticket/14990?action=diff&version=38">diff</a>)
</li>
</ul>
TicketdefeoThu, 05 Dec 2013 23:11:26 GMT
https://trac.sagemath.org/ticket/14990#comment:39
https://trac.sagemath.org/ticket/14990#comment:39
<p>
Hi,
</p>
<p>
I'm still baking my own experimental version of Fp-bar on top of this ticket. I have a question: shouldn't <code>_subfield()</code> use <code>check_irreducible=False</code> in the <code>FiniteField</code> constructor? It looks like a waste to check twice for irreducibility.
</p>
TicketpbruinWed, 11 Dec 2013 16:07:02 GMT
https://trac.sagemath.org/ticket/14990#comment:40
https://trac.sagemath.org/ticket/14990#comment:40
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:39" title="Comment 39">defeo</a>:
</p>
<blockquote class="citation">
<p>
I'm still baking my own experimental version of Fp-bar on top of this ticket. I have a question: shouldn't <code>_subfield()</code> use <code>check_irreducible=False</code> in the <code>FiniteField</code> constructor? It looks like a waste to check twice for irreducibility.
</p>
</blockquote>
<p>
Good idea, I'll rebase this ticket and then disable the check.
</p>
TicketdefeoWed, 11 Dec 2013 16:19:33 GMT
https://trac.sagemath.org/ticket/14990#comment:41
https://trac.sagemath.org/ticket/14990#comment:41
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:40" title="Comment 40">pbruin</a>:
</p>
<blockquote class="citation">
<p>
Good idea, I'll rebase this ticket and then disable the check.
</p>
</blockquote>
<p>
Why "rebase"? Maybe you meant "merge master"?
</p>
TicketgitWed, 11 Dec 2013 16:22:48 GMTcommit changed
https://trac.sagemath.org/ticket/14990#comment:42
https://trac.sagemath.org/ticket/14990#comment:42
<ul>
<li><strong>commit</strong>
changed from <em>5fe4189d600b3bd56a663f6155831ce949e846f5</em> to <em>4265b4fe176d32b3bc7cbc616f8f0964e273ecdb</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. Recent commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=4265b4f"><span class="icon"></span>4265b4f</a></td><td>do not check twice for irreducibility
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=555055b"><span class="icon"></span>555055b</a></td><td>matrix2.pyx: no special case for finite fields in F.algebraic_closure()
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=7f7ed5b"><span class="icon"></span>7f7ed5b</a></td><td>rename/fix change_level(); new doctests
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=2de16f2"><span class="icon"></span>2de16f2</a></td><td>add a _latex_ method to the elements
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=4455c84"><span class="icon"></span>4455c84</a></td><td>fix comparison of pseudo-Conway polynomial trees
</td></tr></table>
TicketpbruinWed, 11 Dec 2013 16:29:24 GMT
https://trac.sagemath.org/ticket/14990#comment:43
https://trac.sagemath.org/ticket/14990#comment:43
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:41" title="Comment 41">defeo</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:40" title="Comment 40">pbruin</a>:
</p>
<blockquote class="citation">
<p>
Good idea, I'll rebase this ticket and then disable the check.
</p>
</blockquote>
<p>
Why "rebase"? Maybe you meant "merge master"?
</p>
</blockquote>
<p>
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).
</p>
TicketpbruinWed, 11 Dec 2013 16:40:16 GMT
https://trac.sagemath.org/ticket/14990#comment:44
https://trac.sagemath.org/ticket/14990#comment:44
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:43" title="Comment 43">pbruin</a>:
</p>
<blockquote class="citation">
<p>
it turned out to remove some duplicate commits which were in the previous version of the branch (I noticed this before).
</p>
</blockquote>
<p>
Although if I read the <code>git-rebase</code> man page correctly, merging our branches will now create even more duplicates because of my <code>rebase</code>. What is the best solution for this?
</p>
TicketdefeoWed, 11 Dec 2013 17:21:54 GMT
https://trac.sagemath.org/ticket/14990#comment:45
https://trac.sagemath.org/ticket/14990#comment:45
<blockquote class="citation">
<p>
Although if I read the <code>git-rebase</code> man page correctly, merging our branches will now create even more duplicates because of my <code>rebase</code>. What is the best solution for this?
</p>
</blockquote>
<p>
What do you mean by "duplicate commits"?
</p>
<p>
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.
</p>
<p>
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)
</p>
<pre class="wiki">git reset --hard 5fe4189
git cherry-pick 4265b4f
git merge master
git push -f
</pre><p>
assuming the only commit that really did something was the last one, 4265b4f.
</p>
<p>
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.
</p>
TicketpbruinWed, 11 Dec 2013 22:06:37 GMT
https://trac.sagemath.org/ticket/14990#comment:46
https://trac.sagemath.org/ticket/14990#comment:46
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:45" title="Comment 45">defeo</a>:
</p>
<blockquote class="citation">
<p>
What do you mean by "duplicate commits"?
</p>
</blockquote>
<p>
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.
</p>
<blockquote class="citation">
<p>
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.
</p>
<p>
But it might be a problem for Vincent, if you still want to share work.
</p>
</blockquote>
<p>
OK, let's leave it as is unless it creates trouble for Vincent (or someone else who might have been using this branch).
</p>
TicketdefeoWed, 11 Dec 2013 23:19:08 GMT
https://trac.sagemath.org/ticket/14990#comment:47
https://trac.sagemath.org/ticket/14990#comment:47
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:46" title="Comment 46">pbruin</a>:
</p>
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
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).
</p>
TicketpbruinWed, 11 Dec 2013 23:37:06 GMT
https://trac.sagemath.org/ticket/14990#comment:48
https://trac.sagemath.org/ticket/14990#comment:48
<p>
Actually, there is <a class="closed ticket" href="https://trac.sagemath.org/ticket/15390" title="enhancement: roots of polynomials and eigenvalues of matrices over finite fields (closed: fixed)">#15390</a> 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 <a class="closed ticket" href="https://trac.sagemath.org/ticket/15390" title="enhancement: roots of polynomials and eigenvalues of matrices over finite fields (closed: fixed)">#15390</a> onto this one.
</p>
TicketpbruinSat, 14 Dec 2013 22:54:22 GMT
https://trac.sagemath.org/ticket/14990#comment:49
https://trac.sagemath.org/ticket/14990#comment:49
<p>
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 (<a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:9" title="Comment 9">comment:9</a>):
</p>
<blockquote class="citation">
<ul><li>.some_elements() returns a very stupid list
</li></ul></blockquote>
<p>
This can be made less stupid by implementing <code>_an_element_()</code> to return <code>self.gen(2)</code>.
</p>
<blockquote class="citation">
<ul><li>.gens() is not happy. I guess we can return a <code>Family</code>. The problem is that in the specification it is written that the method should return a tuple.
</li></ul></blockquote>
<p>
I think returning a <code>Family</code> is acceptable given that there is no finite set of generators.
</p>
<blockquote class="citation">
<ul><li>many methods can be implemented in two lines as
<pre class="wiki"> def my_method(self):
return self._value.my_method()
</pre>this concerns <code>minimal_polynomial</code>, <code>trace</code>, <code>norm</code>, <code>multiplicative_order</code>, ...
</li></ul></blockquote>
<p>
I agree for <code>minimal_polynomial</code> and <code>multiplicative_order</code>; the latter was implemented by Vincent.
</p>
<p>
The trace and norm, on the other hand, are not well-defined since the definition requires a <em>finite</em> extension, for which there is no canical choice.
</p>
<p>
It remains to implement <code>minimal_polynomial</code>, which can of course be done in two lines as above.
</p>
<blockquote class="citation">
<ul><li>in a similar way (calling apropriate method of _value and applying a morphism) it is straightforward to implement <code>frobenius</code>, <code>pth_power</code>, <code>pth_root</code>, ...
</li></ul></blockquote>
<p>
We now have <code>pth_power</code> and <code>pth_root</code>, again thanks to Vincent, and the field itself has <code>frobenius</code>. I don't think an additional <code>frobenius</code> on elements would be useful.
</p>
TicketpbruinSat, 14 Dec 2013 23:24:04 GMT
https://trac.sagemath.org/ticket/14990#comment:50
https://trac.sagemath.org/ticket/14990#comment:50
<p>
Something else: I would prefer if the implementation of <code>nth_root()</code> 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 <em>n</em> (is it true/clear that the degree has to divide <em>n</em>?), I think we should either factor <em>x<sup>n</sup></em> - <em>a</em> (where <em>a</em> is the element whose <em>n</em>-th root we want) and look at the smallest degree of a factor, or we should compute the multiplicative order of <em>a</em>. Also, before doing anything else, we should take all factors <em>p</em> out of <em>n</em> and use <code>pth_root()</code>.
</p>
<p>
I hope to have an update soon, at least for the remaining things mentioned in the previous comment.
</p>
TicketgitSun, 15 Dec 2013 00:14:12 GMTcommit changed
https://trac.sagemath.org/ticket/14990#comment:51
https://trac.sagemath.org/ticket/14990#comment:51
<ul>
<li><strong>commit</strong>
changed from <em>4265b4fe176d32b3bc7cbc616f8f0964e273ecdb</em> to <em>70f07cafc62f0fdf6d3f3897973fd33400168d40</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=70f07ca"><span class="icon"></span>70f07ca</a></td><td>implement three more methods
</td></tr></table>
TicketgitSat, 21 Dec 2013 23:38:45 GMTcommit changed
https://trac.sagemath.org/ticket/14990#comment:52
https://trac.sagemath.org/ticket/14990#comment:52
<ul>
<li><strong>commit</strong>
changed from <em>70f07cafc62f0fdf6d3f3897973fd33400168d40</em> to <em>7b3d68a49b460e336f98c46c7f219fc2f2fbd78f</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=7b3d68a"><span class="icon"></span>7b3d68a</a></td><td><code>cosmetic improvement to nth_root()</code>
</td></tr></table>
TicketpbruinSat, 21 Dec 2013 23:45:51 GMTstatus changed
https://trac.sagemath.org/ticket/14990#comment:53
https://trac.sagemath.org/ticket/14990#comment:53
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
I thought a bit about <code>nth_root()</code> but couldn't easily make it faster. Hence I just made two very minor fixes: raise an <code>AssertionError</code> instead of a <code>ValueError</code> if we don't find the root (since this should never happen) and move the TODO to the docstring.
</p>
<p>
Since the basic functionality of the ticket is usable, I'm setting it to <code>needs_review</code>.
</p>
TicketgitSat, 04 Jan 2014 21:07:15 GMTcommit changed
https://trac.sagemath.org/ticket/14990#comment:54
https://trac.sagemath.org/ticket/14990#comment:54
<ul>
<li><strong>commit</strong>
changed from <em>7b3d68a49b460e336f98c46c7f219fc2f2fbd78f</em> to <em>ff35daa8828581bb74f929131dd352204a6f8cb1</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=ff35daa"><span class="icon"></span>ff35daa</a></td><td><code>Merge branch 'develop' into ticket/14990</code>
</td></tr></table>
Ticketvbraun_spamThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/14990#comment:55
https://trac.sagemath.org/ticket/14990#comment:55
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.1</em> to <em>sage-6.2</em>
</li>
</ul>
TicketgitTue, 15 Apr 2014 08:18:08 GMTcommit changed
https://trac.sagemath.org/ticket/14990#comment:56
https://trac.sagemath.org/ticket/14990#comment:56
<ul>
<li><strong>commit</strong>
changed from <em>ff35daa8828581bb74f929131dd352204a6f8cb1</em> to <em>785c7b90031db8fc32b5a271e5bca538027bcfc1</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=d45b9b65527a5a4f299db060b3a642ff10da33f7"><span class="icon"></span>d45b9b6</a></td><td><code>Merge branch 'develop' into ticket/14990</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=785c7b90031db8fc32b5a271e5bca538027bcfc1"><span class="icon"></span>785c7b9</a></td><td><code>fix doctest: finite field homset now has unique representation</code>
</td></tr></table>
TicketvdelecroixWed, 23 Apr 2014 21:42:27 GMTstatus changed
https://trac.sagemath.org/ticket/14990#comment:57
https://trac.sagemath.org/ticket/14990#comment:57
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
<p>
Hello,
</p>
<p>
Sorry, the story started already long time ago. I would be happy to finish the review of this ticket and work again on <a class="closed ticket" href="https://trac.sagemath.org/ticket/15390" title="enhancement: roots of polynomials and eigenvalues of matrices over finite fields (closed: fixed)">#15390</a> (no trouble about the possible rebase, I will try the cherry-pick proposed by Luca).
</p>
<p>
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).
</p>
<p>
I am in trouble because of the <code>UniqueFactory</code>. Firstly, in some doctests there is a direct call to <code>AlgebraicClosureFiniteField_pseudo_conway</code> but in practice this should be avoided as we have
</p>
<pre class="wiki">sage: F = AlgebraicClosureFiniteField_pseudo_conway(GF(5),'z')
sage: z = F.an_element()
sage: z == loads(dumps(z))
False
</pre><p>
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 <code>__reduce__</code> when there will be several implementations and I am pretty sure that many others trouble will show up.
</p>
<p>
Minor issues that I solved in a commit on my branch:
</p>
<ul><li>the doctest must be in an <code>EXAMPLES</code> bloc and not an <code>EXAMPLE</code> bloc.
</li></ul><ul><li>I was wondering what was the point of <code>__getstate__</code> (line 473) and <code>__setstate__</code> (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 <code>__getstate__</code> and <code>__setstate__</code> 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).
</li></ul><ul><li>Add optional keywords to <code>FiniteField.algebraic_closure</code> that are sent to the factory in order to be able to do
<pre class="wiki">sage: GF(5).algebraic_closure(implementation='pseudo_conway')
</pre></li></ul><ul><li>for <code>_get_polynomial</code> and <code>_get_im_gen</code> we could use the decorator <code>@abstract_method</code> (from <code>sage.misc.abstract_method</code>). That way, their existence become part of the <code>TestSuite</code> and there is no need for the <code>NotImplementedError</code>. There are many example of its usage in <code>sage/categories</code>.
</li></ul><ul><li>It would be better to move the test lines 41-44 inside the constructor of <code>AlgebraicClosure</code> and rather use <code>AlgebraicClosureFiniteField_pseudo_conway</code> directly. That way we are sure that the good class is tested.
</li></ul><ul><li>Implement <code>some_elements</code>: this is important for having better automatic tests
</li></ul><p>
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.
</p>
<p>
Thanks
Vincent
</p>
TicketpbruinWed, 23 Apr 2014 23:12:00 GMT
https://trac.sagemath.org/ticket/14990#comment:58
https://trac.sagemath.org/ticket/14990#comment:58
<p>
Hello Vincent,
</p>
<blockquote class="citation">
<p>
Sorry, the story started already long time ago. I would be happy to finish the review of this ticket and work again on <a class="closed ticket" href="https://trac.sagemath.org/ticket/15390" title="enhancement: roots of polynomials and eigenvalues of matrices over finite fields (closed: fixed)">#15390</a> (no trouble about the possible rebase, I will try the cherry-pick proposed by Luca).
</p>
</blockquote>
<p>
Great!
</p>
<blockquote class="citation">
<p>
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).
</p>
</blockquote>
<p>
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).
</p>
<blockquote class="citation">
<p>
I am in trouble because of the <code>UniqueFactory</code>. Firstly, in some doctests there is a direct call to <code>AlgebraicClosureFiniteField_pseudo_conway</code> but in practice this should be avoided as we have
</p>
<pre class="wiki">sage: F = AlgebraicClosureFiniteField_pseudo_conway(GF(5),'z')
sage: z = F.an_element()
sage: z == loads(dumps(z))
False
</pre><p>
I had no idea how to make it clear.
</p>
</blockquote>
<p>
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...
</p>
<blockquote class="citation">
<p>
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 <code>__reduce__</code> when there will be several implementations and I am pretty sure that many others trouble will show up.
</p>
</blockquote>
<p>
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.
</p>
<p>
From my perspective, the guiding philosophy should be that you can use <code>UniqueRepresentation</code> or <code>UniqueFactory</code> for objects that are defined <em>up to unique isomorphism</em> by a certain amount of "defining data", which corresponds to the arguments of the <code>__init__()</code> method of an object derived from <code>UniqueRepresentation</code>, resp. to the <code>key</code> used by a <code>UniqueFactory</code>.
</p>
<p>
The problem with of algebraic closures of finite fields is that in principle they are <em>not</em> 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 <em>pseudo</em>-Conway polynomials, which do not have the same uniqueness property.
</p>
<p>
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.
</p>
TicketgitThu, 24 Apr 2014 17:12:54 GMTcommit changed
https://trac.sagemath.org/ticket/14990#comment:59
https://trac.sagemath.org/ticket/14990#comment:59
<ul>
<li><strong>commit</strong>
changed from <em>785c7b90031db8fc32b5a271e5bca538027bcfc1</em> to <em>48e0ffed9690ba9614f7a1655bc2f02465cff4b0</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=02d152003815d6711582b7bcd11054e8069043bb"><span class="icon"></span>02d1520</a></td><td><code>Merge branch 'develop' into 14990-closure_finite_field</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c14a9034fb23279406c2e373bc9dc343eff1f072"><span class="icon"></span>c14a903</a></td><td><code>Minor improvements to algebraic closure of finite fields</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=96bf62ddaf624edceaf4a597437757e363593dee"><span class="icon"></span>96bf62d</a></td><td><code>Trac 14990: do not try to get unique representation</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=14e18af76afe6092dd2002f2359856daaf9087d4"><span class="icon"></span>14e18af</a></td><td><code>Trac 14990: remove pickling code</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=48e0ffed9690ba9614f7a1655bc2f02465cff4b0"><span class="icon"></span>48e0ffe</a></td><td><code>Trac 14990: fix comparison of elements</code>
</td></tr></table>
TicketpbruinThu, 24 Apr 2014 17:17:28 GMTstatus changed
https://trac.sagemath.org/ticket/14990#comment:60
https://trac.sagemath.org/ticket/14990#comment:60
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
<p>
I decided to remove both the <code>UniqueRepresentation code</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.
</p>
<p>
(The branch is based on <code>u/vdelecroix/14990</code>.)
</p>
TicketgitThu, 24 Apr 2014 17:47:59 GMTcommit changed
https://trac.sagemath.org/ticket/14990#comment:61
https://trac.sagemath.org/ticket/14990#comment:61
<ul>
<li><strong>commit</strong>
changed from <em>48e0ffed9690ba9614f7a1655bc2f02465cff4b0</em> to <em>33f982f1acbf61cf08897e6a46ee23bb14e78e1e</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=33f982f1acbf61cf08897e6a46ee23bb14e78e1e"><span class="icon"></span>33f982f</a></td><td><code>Trac 14990: small documentation improvements</code>
</td></tr></table>
TicketvdelecroixThu, 24 Apr 2014 19:43:43 GMT
https://trac.sagemath.org/ticket/14990#comment:62
https://trac.sagemath.org/ticket/14990#comment:62
<p>
Hello Peter,
</p>
<p>
I do not like
</p>
<pre class="wiki">sage: GF(5).algebraic_closure() is GF(5).algebraic_closure()
False
</pre><p>
As far as I understand, a pseudo Conway polynomial is not uniquely defined. But nevertheless, the implementation of <code>PseudoConwayLattice.polynomial</code> is, no? The only thing that today prevents the uniqueness is the use of the database as shown in the following example:
</p>
<pre class="wiki">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
</pre><p>
Maybe I am wrong and there is more than that.
</p>
<p>
So, I propose to restore some kind of unique representation based on the lattice. More precisely (if you agree)
</p>
<ul><li>Make <code>AlgebraicClosureFiniteField_pseudo_conway</code> inherit from <code>UniqueRepresentation</code>
</li><li>add a non optional argument <code>lattice</code> in the constructor of <code>AlgebraicClosureFiniteField_pseudo_conway</code> that can also be used from something like
<pre class="wiki">GF(5).algebraic_closure(implementation='pseudo_conway',lattice=MyFunnyLattice())
</pre>(that way we would have two <strong>different</strong> implementations of the algebraic closure depending if we use or not the database)
</li><li>possibly restore a <code>__reduce__</code> in <code>AlgebraicClosureFiniteField_pseudo_conway</code> that avoid the factory (but I guess that it should be taken care by the <code>UniqueRepresentation</code>)
</li></ul><p>
And then, it remains to find a nice way to avoid rebuilding new lattices each time a user asks for
</p>
<pre class="wiki">sage: GF(5).algebraic_closure()
</pre><p>
What do you think?
</p>
<p>
Vincent
</p>
TicketpbruinThu, 24 Apr 2014 20:00:15 GMT
https://trac.sagemath.org/ticket/14990#comment:63
https://trac.sagemath.org/ticket/14990#comment:63
<p>
Hello Vincent,
</p>
<blockquote class="citation">
<p>
I do not like
</p>
<pre class="wiki">sage: GF(5).algebraic_closure() is GF(5).algebraic_closure()
False
</pre></blockquote>
<p>
Would you be happier if <code>FiniteField.algebraic_closure()</code> were a <code>cached_method</code>?
</p>
<p>
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.)
</p>
TicketdefeoThu, 24 Apr 2014 20:45:14 GMT
https://trac.sagemath.org/ticket/14990#comment:64
https://trac.sagemath.org/ticket/14990#comment:64
<p>
Hi,
</p>
<blockquote class="citation">
<p>
As far as I understand, a pseudo Conway polynomial is not uniquely defined. But nevertheless, the implementation of <code>PseudoConwayLattice.polynomial</code> is, no? The only thing that today prevents the uniqueness is the use of the database
</p>
</blockquote>
<p>
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.
</p>
<p>
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.
</p>
TicketvdelecroixFri, 25 Apr 2014 08:19:34 GMTstatus changed
https://trac.sagemath.org/ticket/14990#comment:65
https://trac.sagemath.org/ticket/14990#comment:65
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Hello,
</p>
<p>
Thanks Peter and Luca for the lights.
</p>
<p>
1) For the comparison of <code>AlgebraicClosureFiniteField</code> you rely on the equality in <code>PseudoConwayLattice</code>... which is not exactly what you want. It compares the nodes which is something dynamical by definition. We have for example
</p>
<pre class="wiki">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
</pre><p>
It is fine for the lattices but not for the fields. The simplest fix would be
</p>
<pre class="wiki">class AlgebraicClosureFiniteField_pseudo_conway:
...
def __cmp___(self, other):
...
return self._pseudo_conway_lattice is other._pseudo_conway_lattice
</pre><p>
2) It makes sense to have something more flexible like
</p>
<pre class="wiki">sage: AC = AlgebraicClosureFiniteField_pseudo_conway
sage: AC(GF(3), lattice=my_pc_lattice)
</pre><p>
where "my_pc_lattice" is an instance of a subclass or <code>PseudoConwayLattice</code> or something with the same specifications (i.e. at least a method <code>polynomial</code>). That way we can already have two implementations of the algebraic closure (calling <code>PseudoConwayLattice</code> with the option <code>use_database=True</code> or <code>use_database=False</code>).
</p>
<p>
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 <code>base_ring</code> that returns the finite field it is based on.
</p>
<p>
4) It would also make sense in <code>PseudoConwayLattice</code> to have a method <code>associated_finite_field_algebraic_closure</code> (with a better name if possible).
</p>
<p>
Vincent
</p>
<p>
PS: will see later for the unique representation problems.
</p>
TicketjpfloriFri, 25 Apr 2014 08:57:04 GMT
https://trac.sagemath.org/ticket/14990#comment:66
https://trac.sagemath.org/ticket/14990#comment:66
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:65" title="Comment 65">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
Hello,
</p>
<p>
Thanks Peter and Luca for the lights.
</p>
<p>
1) For the comparison of <code>AlgebraicClosureFiniteField</code> you rely on the equality in <code>PseudoConwayLattice</code>... which is not exactly what you want. It compares the nodes which is something dynamical by definition. We have for example
</p>
<pre class="wiki">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
</pre><p>
It is fine for the lattices but not for the fields. The simplest fix would be
</p>
</blockquote>
<p>
Is it really fine for lattices?
I would say lattices with different polynomials shouldn't evaluate equal.
</p>
<blockquote class="citation">
<pre class="wiki">class AlgebraicClosureFiniteField_pseudo_conway:
...
def __cmp___(self, other):
...
return self._pseudo_conway_lattice is other._pseudo_conway_lattice
</pre><p>
2) It makes sense to have something more flexible like
</p>
<pre class="wiki">sage: AC = AlgebraicClosureFiniteField_pseudo_conway
sage: AC(GF(3), lattice=my_pc_lattice)
</pre><p>
where "my_pc_lattice" is an instance of a subclass or <code>PseudoConwayLattice</code> or something with the same specifications (i.e. at least a method <code>polynomial</code>). That way we can already have two implementations of the algebraic closure (calling <code>PseudoConwayLattice</code> with the option <code>use_database=True</code> or <code>use_database=False</code>).
</p>
</blockquote>
<p>
That sounds like a good idea.
</p>
<blockquote class="citation">
<p>
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 <code>base_ring</code> that returns the finite field it is based on.
</p>
</blockquote>
<p>
+1
</p>
<blockquote class="citation">
<p>
4) It would also make sense in <code>PseudoConwayLattice</code> to have a method <code>associated_finite_field_algebraic_closure</code> (with a better name if possible).
</p>
</blockquote>
<p>
Would that be really useful?
That does not really make sense, but one might want to create a lattice without the corresponding algebraic closure :)
</p>
TicketjpfloriFri, 25 Apr 2014 12:05:37 GMT
https://trac.sagemath.org/ticket/14990#comment:67
https://trac.sagemath.org/ticket/14990#comment:67
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:66" title="Comment 66">jpflori</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:65" title="Comment 65">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
Hello,
</p>
<p>
Thanks Peter and Luca for the lights.
</p>
<p>
1) For the comparison of <code>AlgebraicClosureFiniteField</code> you rely on the equality in <code>PseudoConwayLattice</code>... which is not exactly what you want. It compares the nodes which is something dynamical by definition. We have for example
</p>
<pre class="wiki">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
</pre><p>
It is fine for the lattices but not for the fields. The simplest fix would be
</p>
</blockquote>
<p>
Is it really fine for lattices?
I would say lattices with different polynomials shouldn't evaluate equal.
</p>
</blockquote>
<p>
Ok, I answered too quickly here.
The problem is that polynomials are added to the lattices but not at the same time.
</p>
<p>
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.
</p>
<p>
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 <code>database=True</code> 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 <code>database=True</code> 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).
</p>
TicketpbruinFri, 25 Apr 2014 23:42:42 GMT
https://trac.sagemath.org/ticket/14990#comment:68
https://trac.sagemath.org/ticket/14990#comment:68
<p>
I agree with Jean-Pierre's analysis. Let me just add that one shouldn't read too much mathematical meaning into equality (<code>==</code>) of parents. The main use for it is in deciding whether to allow coercion from one <code>AlgebraicClosureFiniteField</code> 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 <em>x</em> in the subfield of degree <em>n</em> in one of the two, then we would have no guarantee that the subfield of degree <em>n</em> that would have to be constructed in the other instance (where we want to coerce <em>x</em>) would be the same.
</p>
TicketvdelecroixSat, 26 Apr 2014 06:55:50 GMT
https://trac.sagemath.org/ticket/14990#comment:69
https://trac.sagemath.org/ticket/14990#comment:69
<p>
Hi Peter,
</p>
<p>
Either I badly explained something or there is something contradictory in your argument. First of all you said
</p>
<blockquote class="citation">
<p>
The main use for it [the equality] is in deciding whether
to allow coercion from one <code>AlgebraicClosureFiniteField</code>
to another.
</p>
</blockquote>
<p>
Fine. But that was my point, equality is broken as we currently have with your branch applied
</p>
<pre class="wiki">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
</pre><p>
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?
</p>
<blockquote class="citation">
<p>
we do definitely want to check "only" equality, not identity [of PCL].
</p>
</blockquote>
<p>
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.
</p>
<p>
Vincent
</p>
TicketgitSat, 26 Apr 2014 10:43:20 GMTcommit changed
https://trac.sagemath.org/ticket/14990#comment:70
https://trac.sagemath.org/ticket/14990#comment:70
<ul>
<li><strong>commit</strong>
changed from <em>33f982f1acbf61cf08897e6a46ee23bb14e78e1e</em> to <em>f9162dbae92551a67aea7a489d96591141fdebc8</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=a585d4a99ac7e2a3bad1bb32ef2229eccea1f0ff"><span class="icon"></span>a585d4a</a></td><td><code>Trac 14990: make AlgebraicClosureFiniteField_pseudo_conway accept more arguments</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=f9162dbae92551a67aea7a489d96591141fdebc8"><span class="icon"></span>f9162db</a></td><td><code>Trac 14990: make FiniteField.algebraic_closure() a cached method</code>
</td></tr></table>
TicketpbruinSat, 26 Apr 2014 10:49:26 GMT
https://trac.sagemath.org/ticket/14990#comment:71
https://trac.sagemath.org/ticket/14990#comment:71
<p>
Hi Vincent,
</p>
<blockquote class="citation">
<p>
2) It makes sense to have something more flexible like
</p>
<pre class="wiki">sage: AC = AlgebraicClosureFiniteField_pseudo_conway
sage: AC(GF(3), lattice=my_pc_lattice)
</pre><p>
where "my_pc_lattice" is an instance of a subclass or <code>PseudoConwayLattice</code> or something with the same specifications (i.e. at least a method <code>polynomial</code>). That way we can already have two implementations of the algebraic closure (calling <code>PseudoConwayLattice</code> with the option <code>use_database=True</code> or <code>use_database=False</code>).
</p>
</blockquote>
<p>
This is implemented in one of the two new commits; one can now pass a <code>lattice</code> argument, and the <code>use_database</code> flag is now accepted here as well.
</p>
<blockquote class="citation">
<p>
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 <code>base_ring</code> that returns the finite field it is based on.
</p>
</blockquote>
<p>
It already has a public attribute <code>p</code> for the characteristic; since the PCL is not really meant to be used directly anyway, I think it is redundant to also add a <code>base_ring()</code> method.
</p>
<blockquote class="citation">
<p>
4) It would also make sense in <code>PseudoConwayLattice</code> to have a method <code>associated_finite_field_algebraic_closure</code> (with a better name if possible).
</p>
</blockquote>
<p>
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 <code>associated_finite_field()</code> for polynomials over <strong>F</strong><sub><em>p</em></sub> either.
</p>
TicketpbruinSat, 26 Apr 2014 11:19:01 GMT
https://trac.sagemath.org/ticket/14990#comment:72
https://trac.sagemath.org/ticket/14990#comment:72
<p>
Hi Vincent,
</p>
<blockquote class="citation">
<p>
Either I badly explained something or there is something contradictory in your argument.
</p>
</blockquote>
<p>
Or I badly explained something...
</p>
<blockquote class="citation">
<p>
First of all you said
</p>
<blockquote class="citation">
<p>
The main use for it [the equality] is in deciding whether
to allow coercion from one <code>AlgebraicClosureFiniteField</code>
to another.
</p>
</blockquote>
<p>
Fine. But that was my point, equality is broken
</p>
</blockquote>
<p>
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.)
</p>
<blockquote class="citation">
<p>
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?
</p>
</blockquote>
<p>
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 <em>same</em> field; making <code>algebraic_closure()</code> 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" <code>loads(dumps(x)) == x</code> 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.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
we do definitely want to check "only" equality, not identity [of PCL].
</p>
</blockquote>
<p>
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.
</p>
</blockquote>
<p>
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 <code>AlgebraicClosureFiniteField_pseudo_conway</code> 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.
</p>
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
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.
</p>
TicketvdelecroixSat, 26 Apr 2014 13:12:07 GMT
https://trac.sagemath.org/ticket/14990#comment:73
https://trac.sagemath.org/ticket/14990#comment:73
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:71" title="Comment 71">pbruin</a>:
</p>
<blockquote class="citation">
<p>
Hi Vincent,
</p>
<blockquote class="citation">
<p>
2) It makes sense to have something more flexible like
</p>
<pre class="wiki">sage: AC = AlgebraicClosureFiniteField_pseudo_conway
sage: AC(GF(3), lattice=my_pc_lattice)
</pre><p>
where "my_pc_lattice" is an instance of a subclass or <code>PseudoConwayLattice</code> or something with the same specifications (i.e. at least a method <code>polynomial</code>). That way we can already have two implementations of the algebraic closure (calling <code>PseudoConwayLattice</code> with the option <code>use_database=True</code> or <code>use_database=False</code>).
</p>
</blockquote>
<p>
This is implemented in one of the two new commits; one can now pass a <code>lattice</code> argument, and the <code>use_database</code> flag is now accepted here as well.
</p>
</blockquote>
<p>
Great. Thanks.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
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 <code>base_ring</code> that returns the finite field it is based on.
</p>
</blockquote>
<p>
It already has a public attribute <code>p</code> for the characteristic; since the PCL is not really meant to be used directly anyway, I think it is redundant to also add a <code>base_ring()</code> method.
</p>
</blockquote>
<p>
Here I am not sure I agree. But anyway it would be better not to touch <code>PseudoConwayLattice</code> anyway.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
4) It would also make sense in <code>PseudoConwayLattice</code> to have a method <code>associated_finite_field_algebraic_closure</code> (with a better name if possible).
</p>
</blockquote>
<p>
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 <code>associated_finite_field()</code> for polynomials over <strong>F</strong><sub><em>p</em></sub> either.
</p>
</blockquote>
<p>
Agreed.
</p>
TicketvdelecroixSat, 26 Apr 2014 14:10:59 GMT
https://trac.sagemath.org/ticket/14990#comment:74
https://trac.sagemath.org/ticket/14990#comment:74
<p>
Hi Peter,
</p>
<p>
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
</p>
<ul><li>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)
</li><li>comparisons with == and != may never raise an error.
</li></ul><p>
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 <strong>more</strong> 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.
</p>
<p>
Within your branch
</p>
<pre class="wiki">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 ...
</pre><p>
In principle we could hope for a False above but the coercion system has a cache. This is the reason for the <code>RuntimeError</code>.
</p>
TicketpbruinSat, 26 Apr 2014 18:51:43 GMT
https://trac.sagemath.org/ticket/14990#comment:75
https://trac.sagemath.org/ticket/14990#comment:75
<p>
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.
</p>
<p>
It seems to me that in the case of <code>AlgebraicClosureFiniteField_pseudo_conway</code>, 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.
</p>
<p>
If this reasoning is correct, <em>and</em> 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.
</p>
<p>
It is a bit annoying, and I do not see how to easily avoid breaking the sanity check <code>loads(dumps(x)) == x</code> if we take this approach. Maybe we should just capitulate on this point and disable this check in the <code>TestSuite</code>, or explicitly give the error as the expected result of the <code>TestSuite</code>.
</p>
TicketvdelecroixSat, 26 Apr 2014 22:29:21 GMT
https://trac.sagemath.org/ticket/14990#comment:76
https://trac.sagemath.org/ticket/14990#comment:76
<p>
Hi,
</p>
<p>
Given that <code>PseudoConwayLattice</code> is what it is, I agree to (1) and (2) in your <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:75" title="Comment 75">comment:75</a>.
</p>
<p>
Coercion are cached and I guess it forbids to have a mutable <code>Parent</code> (unless they coerce with nothing).
</p>
<p>
And you are right, we have a big trouble as we can not loads/dumps <code>PseudoConwayLattice</code> in the way we would like them to be. It seems reasonable to me to keep the error on <code>x == loads(dumps(x))</code> and document it.
</p>
<p>
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
</p>
<pre class="wiki">@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)
...
</pre><p>
And then the pickling must be adapted by calling <code>AlgebraicClosureFiniteField</code>. I am sure that it can work but I am not sure at all it is reasonable.
</p>
TicketvdelecroixFri, 02 May 2014 10:16:16 GMT
https://trac.sagemath.org/ticket/14990#comment:77
https://trac.sagemath.org/ticket/14990#comment:77
<p>
<strong>ping</strong>
</p>
<p>
Do you want that I give it a try?
</p>
<p>
Vincent
</p>
TicketpbruinFri, 02 May 2014 10:28:26 GMT
https://trac.sagemath.org/ticket/14990#comment:78
https://trac.sagemath.org/ticket/14990#comment:78
<p>
Hi Vincent,
</p>
<blockquote class="citation">
<p>
And you are right, we have a big trouble as we can not loads/dumps <code>PseudoConwayLattice</code> in the way we would like them to be. It seems reasonable to me to keep the error on <code>x == loads(dumps(x))</code> and document it.
</p>
</blockquote>
<p>
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.
</p>
<p>
If you want to implement this approach, go ahead. You can try to simply do <code>git revert 48e0ffed</code> and fix the ensuing doctest failures.
</p>
Ticketvbraun_spamTue, 06 May 2014 15:20:58 GMTmilestone changed
https://trac.sagemath.org/ticket/14990#comment:79
https://trac.sagemath.org/ticket/14990#comment:79
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.2</em> to <em>sage-6.3</em>
</li>
</ul>
TicketgitMon, 12 May 2014 13:56:02 GMTcommit changed
https://trac.sagemath.org/ticket/14990#comment:80
https://trac.sagemath.org/ticket/14990#comment:80
<ul>
<li><strong>commit</strong>
changed from <em>f9162dbae92551a67aea7a489d96591141fdebc8</em> to <em>fdd883792076e8cdb2b1ae7a15cfe28b36d653ca</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=ffd377f31b43ecb094863eef44a2936c9d28722d"><span class="icon"></span>ffd377f</a></td><td><code>Revert "Trac 14990: fix comparison of elements"</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=fdd883792076e8cdb2b1ae7a15cfe28b36d653ca"><span class="icon"></span>fdd8837</a></td><td><code>Trac 14990: do not check pickling of elements in TestSuite, with explanation</code>
</td></tr></table>
TicketpbruinMon, 12 May 2014 14:01:17 GMTstatus changed
https://trac.sagemath.org/ticket/14990#comment:81
https://trac.sagemath.org/ticket/14990#comment:81
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Someone asked me about this today, so I tried my suggestion from <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:78" title="Comment 78">comment:78</a>. 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.
</p>
TicketvdelecroixMon, 12 May 2014 15:40:40 GMT
https://trac.sagemath.org/ticket/14990#comment:82
https://trac.sagemath.org/ticket/14990#comment:82
<p>
Hi Peter,
</p>
<p>
Thank you.
</p>
<p>
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.
</p>
<p>
2) It must absolutely be clear in the documentation of <code>.algebraic_closure</code> that the pickling is broken! This is the main entry point for users.
</p>
<p>
3) Do you agree to add to the documentation the different weirdnesses I described in my comments ? (possibly in a TODO section)
</p>
<p>
Best
Vincent
</p>
TicketpbruinMon, 12 May 2014 16:21:50 GMT
https://trac.sagemath.org/ticket/14990#comment:83
https://trac.sagemath.org/ticket/14990#comment:83
<p>
Hi Vincent,
</p>
<blockquote class="citation">
<p>
1) I found that your explanation is rather vague: it is not clear if you speak about mathematics or the Sage implementation.
</p>
</blockquote>
<p>
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.
</p>
<blockquote class="citation">
<p>
Moreover, this weirdness only concerns pseudo-Conway implementation (which is right now the only one).
</p>
</blockquote>
<p>
Certainly, that is why the new paragraph starts with "In the current implementation".
</p>
<blockquote class="citation">
<p>
In a future, we might implement Jean-Pierre idea: deal with Conway polynomial or have a certified- non-random version of pseudo-Conway.
</p>
</blockquote>
<p>
Of course, but we are still in the present... 8-)
</p>
<p>
(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!)
</p>
<blockquote class="citation">
<p>
2) It must absolutely be clear in the documentation of <code>.algebraic_closure</code> that the pickling is broken! This is the main entry point for users.
</p>
</blockquote>
<p>
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.
</p>
<blockquote class="citation">
<p>
3) Do you agree to add to the documentation the different weirdnesses I described in my comments ? (possibly in a TODO section)
</p>
</blockquote>
<p>
I don't see quickly which "weirdnesses" are still remaining, could you give me a list?
</p>
TicketgitMon, 12 May 2014 17:06:40 GMTcommit changed
https://trac.sagemath.org/ticket/14990#comment:84
https://trac.sagemath.org/ticket/14990#comment:84
<ul>
<li><strong>commit</strong>
changed from <em>fdd883792076e8cdb2b1ae7a15cfe28b36d653ca</em> to <em>b1d4424ec179f4975a54a14993e4c842b3fb39f5</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=b1d4424ec179f4975a54a14993e4c842b3fb39f5"><span class="icon"></span>b1d4424</a></td><td><code>Trac 14990: expand documentation of FiniteField_base.algebraic_closure()</code>
</td></tr></table>
TicketvdelecroixTue, 13 May 2014 11:50:30 GMT
https://trac.sagemath.org/ticket/14990#comment:85
https://trac.sagemath.org/ticket/14990#comment:85
<p>
Dear Peter,
</p>
<p>
I like very much the documentation in <code>algebraic_closure</code>. Thank you.
</p>
<p>
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.
</p>
<p>
1) Equality among algebraic closures is not constant over time:
</p>
<pre class="wiki">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
</pre><p>
It becomes really weird when we play with pickling
</p>
<pre class="wiki">sage: p = 100003
sage: K = GF(p).algebraic_closure()
sage: K2 = loads(dumps(K))
sage: K.gen(3)
z3
sage: K == K2
False
</pre><p>
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 <code>K == loads(dumps(K))</code> will be <code>False</code>. I think it would be safer that way.
</p>
<p>
2) Get a very strange error from conversions between different algebraic closures that can be fixed introducing more type checking in the methods.
</p>
<pre class="wiki">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
</pre><p>
3) (minor) The cache in <code>algebraic_closure</code> does not take into account the default arguments.
</p>
<pre class="wiki">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
</pre><p>
One fix is to move the cache at the level of <code>AlgebraicClosureFiniteField</code>, but on the other hand it is good to have the cache at a Cython level.
</p>
<p>
That's all
Vincent
</p>
TicketgitTue, 13 May 2014 13:43:25 GMTcommit changed
https://trac.sagemath.org/ticket/14990#comment:86
https://trac.sagemath.org/ticket/14990#comment:86
<ul>
<li><strong>commit</strong>
changed from <em>b1d4424ec179f4975a54a14993e4c842b3fb39f5</em> to <em>63bc7aa3b23e6d7dc4db54de76c60b24134e7895</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=4ac10fb0702a315e64755fd9df0e929e1d26ac1a"><span class="icon"></span>4ac10fb</a></td><td><code>Trac 14990: compare pseudo-Conway algebraic closures by ID</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=63bc7aa3b23e6d7dc4db54de76c60b24134e7895"><span class="icon"></span>63bc7aa</a></td><td><code>Trac 14990: more informative error message in _element_constructor_()</code>
</td></tr></table>
TicketpbruinTue, 13 May 2014 13:49:39 GMT
https://trac.sagemath.org/ticket/14990#comment:87
https://trac.sagemath.org/ticket/14990#comment:87
<p>
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 <code>AlgebraicClosureFiniteField</code>, 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:
</p>
<pre class="wiki">sage: GF(5).algebraic_closure('z') is GF(5).algebraic_closure()
True
</pre><p>
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.
</p>
TicketvdelecroixWed, 14 May 2014 05:14:45 GMT
https://trac.sagemath.org/ticket/14990#comment:88
https://trac.sagemath.org/ticket/14990#comment:88
<p>
Hi Peter,
</p>
<p>
I agree with your analysis of (3).
</p>
<p>
All test pass and the documentation builds.
</p>
<p>
There is a typo which becomes ugly in the compiled documentation. At line 960 of <code>algebraic_closure_finite_field.py</code> you wrote <code>`:meth:~sage.rings.finite_rings.finite_field_base.FiniteField.algebraic_closure`</code> instead of <code>:meth:`~sage.rings.finite_rings.finite_field_base.FiniteField.algebraic_closure`</code>.
</p>
<p>
Once the change done, you can set to positive review.
</p>
<p>
Vincent
</p>
TicketgitWed, 14 May 2014 07:58:28 GMTcommit changed
https://trac.sagemath.org/ticket/14990#comment:89
https://trac.sagemath.org/ticket/14990#comment:89
<ul>
<li><strong>commit</strong>
changed from <em>63bc7aa3b23e6d7dc4db54de76c60b24134e7895</em> to <em>b0e1539b899af271fb16dcc6dadfaa7e567620b9</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=b0e1539b899af271fb16dcc6dadfaa7e567620b9"><span class="icon"></span>b0e1539</a></td><td><code>Trac 14990: fix typo in documentation</code>
</td></tr></table>
TicketpbruinWed, 14 May 2014 08:01:03 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/14990#comment:90
https://trac.sagemath.org/ticket/14990#comment:90
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Vincent Delecroix</em>
</li>
</ul>
<p>
Done. Thanks a lot for your thorough review!
</p>
TicketvbraunThu, 15 May 2014 17:18:32 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/14990#comment:91
https://trac.sagemath.org/ticket/14990#comment:91
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>u/pbruin/14990</em> to <em>b0e1539b899af271fb16dcc6dadfaa7e567620b9</em>
</li>
</ul>
TicketslelievreTue, 16 Sep 2014 17:23:21 GMTcommit deleted
https://trac.sagemath.org/ticket/14990#comment:92
https://trac.sagemath.org/ticket/14990#comment:92
<ul>
<li><strong>commit</strong>
<em>b0e1539b899af271fb16dcc6dadfaa7e567620b9</em> deleted
</li>
</ul>
<p>
Some change introduced by this ticket is being discussed in <a class="ext-link" href="https://groups.google.com/d/topic/sage-devel/JgB6p9eu970/discussion"><span class="icon"></span>this sage-devel thread</a>.
</p>
TicketzimmermaMon, 15 Jan 2018 09:57:25 GMT
https://trac.sagemath.org/ticket/14990#comment:93
https://trac.sagemath.org/ticket/14990#comment:93
<p>
for information, Pari/GP 2.10 implements finite field embeddings.
See <a class="ext-link" href="http://pari.math.u-bordeaux.fr/Events/PARI2018/talks/features.pdf"><span class="icon"></span>http://pari.math.u-bordeaux.fr/Events/PARI2018/talks/features.pdf</a>
</p>
TicketdefeoMon, 15 Jan 2018 10:15:53 GMT
https://trac.sagemath.org/ticket/14990#comment:94
https://trac.sagemath.org/ticket/14990#comment:94
<p>
Flint will soon have them too. See <a class="ext-link" href="https://github.com/wbhart/flint2/pull/351"><span class="icon"></span>https://github.com/wbhart/flint2/pull/351</a>.
</p>
<p>
Are the embeddings in PARI/GP compatible?
</p>
TicketvdelecroixMon, 15 Jan 2018 16:08:04 GMT
https://trac.sagemath.org/ticket/14990#comment:95
https://trac.sagemath.org/ticket/14990#comment:95
<p>
Would be nice to have both of them interfaced in Sage together with the version that is already there!
</p>
TicketdefeoMon, 15 Jan 2018 16:15:55 GMTcc changed
https://trac.sagemath.org/ticket/14990#comment:96
https://trac.sagemath.org/ticket/14990#comment:96
<ul>
<li><strong>cc</strong>
<em>erousseau</em> added
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14990#comment:95" title="Comment 95">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
Would be nice to have both of them interfaced in Sage together with the version that is already there!
</p>
</blockquote>
<p>
That's part of our plans. Not immediately, though.
</p>
Ticket