#14990: Implement algebraic closures of finite fields
-------------------------------------------------+-------------------------
Reporter: pbruin | Owner:
Type: enhancement | Status:
Priority: major | needs_review
Component: algebra | Milestone: sage-5.12
Keywords: finite field algebraic | Resolution:
closure | Merged in:
Authors: Peter Bruin | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: #14958, #13214 | Stopgaps:
-------------------------------------------------+-------------------------
Description changed by pbruin:
Old description:
> The goal of this ticket is a basic implementation of algebraic closures
> of finite fields. Most importantly, it provides the following:
>
> - class `AlgebraicClosureFiniteField`
> - method `subfield(n)` returning a tuple consisting of the subfield of
> order ''p^n^'' and a `RingHomomorphism_im_gens` giving the canonical
> embedding into the algebraic closure
> - class `AlgebraicClosureFiniteFieldElement`
> (mostly a wrapper around `FiniteFieldElement`, so actually an element
> of a finite subfield, but having the algebraic closure as its parent and
> taking care of coercion into larger subfields)
> - method `FiniteField.algebraic_closure()`
>
> (Alternative names: `FiniteFieldAlgebraicClosure`,
> `FiniteFieldAlgebraicClosureElement`, maybe with aliases `FFpbar`,
> `FFpbarElement`?)
>
> An example using the new functionality is the following analogue of the
> example from #8335:
> {{{
> sage: Fbar = GF(3).algebraic_closure('z')
> sage: Fbar
> Algebraic closure of Finite Field of size 3
> sage: F2, e2 = Fbar.subfield(2)
> sage: F3, e3 = Fbar.subfield(3)
> sage: F2
> Finite Field in z2 of size 3^2
> }}}
> To add, we first embed into `Fbar`:
> {{{
> sage: x2 = e2(F2.gen())
> sage: x3 = e3(F3.gen())
> sage: x = x2 + x3
> sage: x
> z6^5 + 2*z6^4 + 2*z6^3 + z6^2 + 2*z6 + 1
> sage: x.parent() is Fbar
> True
> }}}
> One can also do this without explicitly invoking the embeddings; as a
> shortcut, `Fbar` has a method `gen(n)` returning the fixed generator of
> the subfield of degree ''n'', but as an element of `Fbar`:
> {{{
> sage: x2 == Fbar.gen(2)
> True
> sage: x == Fbar.gen(2) + Fbar.gen(3)
> True
> }}}
>
> (The above example shows that `AlgebraicClosureFiniteFieldElement` is
> printed in the same way as the underlying `FiniteFieldElement`.)
>
> It is conceivable that there will be different coexisting implementations
> (classes deriving from an abstract `AlgebraicClosureFiniteField`). The
> current implementation uses Conway polynomials and the pseudo-Conway
> polynomials from #14958, as well as the functionality for finite field
> homomorphisms provided by #13214.
New description:
The goal of this ticket is a basic implementation of algebraic closures of
finite fields. Most importantly, it provides the following:
- class `AlgebraicClosureFiniteField_generic` (abstract base class)
- method `subfield(n)` returning a tuple consisting of the subfield of
order ''p^n^'' and a `RingHomomorphism_im_gens` giving the canonical
embedding into the algebraic closure
- class `AlgebraicClosureFiniteField_pseudo_conway` (implements the
specific defining polynomials of the finite subfields and the relations
between the generators of these subfields)
- class `AlgebraicClosureFiniteFieldElement`
(mostly a wrapper around `FiniteFieldElement`, so actually an element of
a finite subfield, but having the algebraic closure as its parent and
taking care of coercion into larger subfields)
- factory class `AlgebraicClosureFiniteField` (to get unique parents)
- method `FiniteField.algebraic_closure()` (invokes the factory class)
An example using the new functionality is the following analogue of the
example from #8335:
{{{
sage: Fbar = GF(3).algebraic_closure('z')
sage: Fbar
Algebraic closure of Finite Field of size 3
sage: F2, e2 = Fbar.subfield(2)
sage: F3, e3 = Fbar.subfield(3)
sage: F2
Finite Field in z2 of size 3^2
}}}
To add, we first embed into `Fbar`:
{{{
sage: x2 = e2(F2.gen())
sage: x3 = e3(F3.gen())
sage: x = x2 + x3
sage: x
z6^5 + 2*z6^4 + 2*z6^3 + z6^2 + 2*z6 + 1
sage: x.parent() is Fbar
True
}}}
One can also do this without explicitly invoking the embeddings; as a
shortcut, `Fbar` has a method `gen(n)` returning the fixed generator of
the subfield of degree ''n'', but as an element of `Fbar`:
{{{
sage: x2 == Fbar.gen(2)
True
sage: x == Fbar.gen(2) + Fbar.gen(3)
True
}}}
It is conceivable that there will be different coexisting implementations
(deriving from `AlgebraicClosureFiniteField_generic`). The current
implementation uses Conway polynomials and the pseudo-Conway polynomials
from #14958, as well as the functionality for finite field homomorphisms
provided by #13214.
Apply: [attachment:trac_14990-algebraic_closure_finite_field.patch]
--
--
Ticket URL: <http://trac.sagemath.org/ticket/14990#comment:4>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
