Opened 9 years ago
Closed 9 years ago
#14958 closed enhancement (fixed)
Implement pseudo-Conway polynomials
Reported by: | Peter Bruin | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-5.13 |
Component: | finite rings | Keywords: | Conway polynomial sd51 |
Cc: | David Roe, Jean-Pierre Flori, Martin Raum, Fredrik Strömberg, Jenny Cooley, David Loeffler, Dino Festi | Merged in: | sage-5.13.beta0 |
Authors: | David Roe, Jean-Pierre Flori, Peter Bruin | Reviewers: | Jean-Pierre Flori, Peter Bruin |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #14833, #14957 | Stopgaps: |
Description (last modified by )
This patch implements pseudo-Conway polynomials, which are used to enable coercion between finite fields. This has been split off from #8335, and is a dependency of that ticket.
Attachments (3)
Change History (21)
comment:1 Changed 9 years ago by
Dependencies: | #14957 → #14833, #14957 |
---|
comment:2 Changed 9 years ago by
Cc: | David Roe Jean-Pierre Flori Martin Raum Fredrik Strömberg Jenny Cooley David Loeffler Dino Festi added |
---|
comment:3 Changed 9 years ago by
Description: | modified (diff) |
---|---|
Status: | new → needs_review |
comment:4 Changed 9 years ago by
Status: | needs_review → needs_work |
---|
comment:5 Changed 9 years ago by
Description: | modified (diff) |
---|---|
Status: | needs_work → needs_review |
comment:6 Changed 9 years ago by
I rebased and updated the code written by David Roe and Jean-Pierre Flori.
One important question before me or someone else reviews this: why does this patch introduce objects that are called pseudo-Conway polynomial trees? This strongly suggests that the system of compatible finite fields that it represents forms a tree, which is definitely NOT the case. This is the whole reason why all of this work needs to be done to get such a system of finite fields!
Changed 9 years ago by
Attachment: | trac_14958-pseudo_conway.patch added |
---|
implement pseudo-Conway polynomials
comment:8 follow-up: 9 Changed 9 years ago by
Description: | modified (diff) |
---|---|
Status: | needs_review → needs_info |
Work issues: | → terminology; possible bug |
Reasons for status change to needs_info:
- the 'tree' terminology (see http://trac.sagemath.org/ticket/14958#comment:6); I think that
PseudoConwayPolyTree
should be changed toPseudoConwayLattice
or something similar.
- during Sage Days 51, Jenny Cooley found a paper claiming that there is a mistake in one of the algorithms in the article of Heath and Loehr cited in the code. We should check that the error is not in this patch.
- R. Gurjar, Generating Conway polynomials, http://home.iitk.ac.in/~rgurjar/projects/conwayPolynomial.pdf
comment:9 Changed 9 years ago by
Replying to pbruin:
Reasons for status change to needs_info:
- the 'tree' terminology (see http://trac.sagemath.org/ticket/14958#comment:6); I think that
PseudoConwayPolyTree
should be changed toPseudoConwayLattice
or something similar.
I agree. I also don't really feel satisfied with the way all these polynomials are stored right now, but I'm not sure I'll come up with anything quickly.
- during Sage Days 51, Jenny Cooley found a paper claiming that there is a mistake in one of the algorithms in the article of Heath and Loehr cited in the code. We should check that the error is not in this patch.
- R. Gurjar, Generating Conway polynomials, http://home.iitk.ac.in/~rgurjar/projects/conwayPolynomial.pdf
I think it's fixed in David's implementation. That's what got me confused at http://trac.sagemath.org/ticket/8335#comment:55 because I thought the addition David made were not needed, and then i realized they were: http://trac.sagemath.org/ticket/8335#comment:57.
comment:10 Changed 9 years ago by
I'd say David used the term tree because a PCPT objecgt only contains one layer of references, i.e. a pseudo-conway poly and refs to the PCPTs for n/q where q is a prime divisor of n.
Some minor remarks:
- I think we should add a warning that PCPTs are only weakrefed. I saw that you correctly took care of that in #8335, thanks for that.
- At some point the new doc says "The following demonstrate coercions", shouldn't it be "demonstrates"? (please pardon me if I'm wrong, I'm no english expert).
- The doc changes corresponding to the fix mentionned in http://trac.sagemath.org/ticket/8335#comment:59 are missing; it should not read:
If False, then `n` is prime and no references are stored (since there is no compatibility condition).
but:If ``False``, then `n == 1` and no references are stored (since there is no compatiblity condition).
comment:11 follow-up: 12 Changed 9 years ago by
Description: | modified (diff) |
---|---|
Reviewers: | → Jean-Pierre Flori, Peter Bruin |
Status: | needs_info → needs_review |
Work issues: | terminology; possible bug |
The last patch renames some classes, methods and functions.
It also fixes doctests and documentation.
Patchbot, apply: * trac_14958-pseudo_conway.patch * trac_14958-rename-doctests.patch
Changed 9 years ago by
Attachment: | trac_14958-rename-doctests.patch added |
---|
comment:12 Changed 9 years ago by
Replying to jpflori:
The last patch renames some classes, methods and functions.
It also fixes doctests and documentation.
These changes all look good to me.
Actually, I realised that we never call irreducible_element(n, algorithm='pseudo-conway')
in #8335, so it is not even necessary to allow this parameter. In fact, it may cause confusion, since creating a single pseudo-Conway polynomial really only makes sense in the context of a lattice. Without that, a pseudo-Conway polynomial is nothing more than a primitive polynomial!
I confess that I never got around to learning what exactly weakref
does, until now. I just read the relevant parts of http://www.python.org/dev/peps/pep-0205/ and see why we may have to be careful. I think this question is mostly relevant to #8335, so let's not move that discussion here; let me just say for now that I agree that weakref
does not appear to be the ideal solution to our caching problem.
comment:13 Changed 9 years ago by
While working on #14990, it occurred to me that this patch could be simplified substantially. I am attaching a new version that gives an extremely intuitive interface to pseudo-Conway lattices:
class PseudoConwayLattice(SageObject) def __init__(self, p, use_database=True) def polynomial(self, n)
This is morally equivalent to a construction of an algebraic closure of F_{p} with a method that returns the unique subfield of degree n.
The method get_pseudo_conway_polynomial()
is now simply called polynomial()
. The functions find_pseudo_conway_polynomial_tree()
and compute_pseudo_conway_polynomial()
have been dissolved into __init__()
and polynomial()
. The global variables to implement caching are gone.
Changed 9 years ago by
Attachment: | trac_14958-pseudo_conway_simplified.patch added |
---|
implement pseudo-Conway polynomials (replaces both previous patches)
comment:14 Changed 9 years ago by
Authors: | David Roe, Jean-Pierre Flori → David Roe, Jean-Pierre Flori, Peter Bruin |
---|---|
Description: | modified (diff) |
apply trac_14958-pseudo_conway_simplified.patch
comment:15 Changed 9 years ago by
Status: | needs_review → positive_review |
---|
Now we've departed from the idea of implementing what should be provided by the algebraic closure constructions, the new patch is fine for me.
comment:16 Changed 9 years ago by
Milestone: | sage-5.12 → sage-pending |
---|
comment:17 Changed 9 years ago by
Milestone: | sage-pending → sage-5.13 |
---|
comment:18 Changed 9 years ago by
Merged in: | → sage-5.13.beta0 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
CC-ing the authors of #8335 and Sage Days 51 participants on this split-off ticket.