Implement pseudo-Conway polynomials

[pjbruin]

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.

Apply: attachment: trac_14958-pseudo_conway_simplified.patch

Depends on #14833
Depends on #14957

CC: @roed314 @jpflori @sagetrac-mraum @fredstro @sagetrac-JCooley @loefflerd @sagetrac-dfesti

Component: finite rings

Keywords: Conway polynomial sd51

Author: David Roe, Jean-Pierre Flori, Peter Bruin

Reviewer: Jean-Pierre Flori, Peter Bruin

Merged: sage-5.13.beta0

Issue created by migration from https://trac.sagemath.org/ticket/14958

[pjbruin]

Changed dependencies from #14957 to #14833, #14957

[pjbruin]

comment:2

CC-ing the authors of #8335 and Sage Days 51 participants on this split-off ticket.

[pjbruin]

comment:6

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!

[pjbruin]

comment:7

The last patch still needed some cleaning up; here is a new one.

[pjbruin]

implement pseudo-Conway polynomials

[pjbruin]

comment:8

Attachment: trac_14958-pseudo_conway.patch.gz

Reasons for status change to needs_info:

• the 'tree' terminology (see #14958 comment:6); I think that PseudoConwayPolyTree should be changed to PseudoConwayLattice 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

[pjbruin]

Work Issues: terminology; possible bug

[jpflori]

comment:9

Replying to @pjbruin:

Reasons for status change to needs_info:

• the 'tree' terminology (see #14958 comment:6); I think that PseudoConwayPolyTree should be changed to PseudoConwayLattice 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 #8335 comment:55 because I thought the addition David made were not needed, and then i realized they were: #8335 comment:57.

[jpflori]

comment:10

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 Finite field lattices via Conway polynomials #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 #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).

[jpflori]

comment:11

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

[jpflori]

Changed work issues from terminology; possible bug to none

[jpflori]

Reviewer: Jean-Pierre Flori, Peter Bruin

[pjbruin]

comment:12

Attachment: trac_14958-rename-doctests.patch.gz

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.

[pjbruin]

comment:13

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.

[pjbruin]

Attachment: trac_14958-pseudo_conway_simplified.patch.gz

implement pseudo-Conway polynomials (replaces both previous patches)

[pjbruin]

comment:14

apply trac_14958-pseudo_conway_simplified.patch

[pjbruin]

Changed author from David Roe, Jean-Pierre Flori to David Roe, Jean-Pierre Flori, Peter Bruin

[jpflori]

comment:15

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.

[jdemeyer]

Merged: sage-5.13.beta0