#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:
-------------------------------------------------+-------------------------
Changes (by {'newvalue': u'Peter Bruin', 'oldvalue': ''}):
* status: new => needs_review
* dependencies: #14958 => #14958, #13214
* author: => Peter Bruin
Old description:
> Algebraic closures of finite fields should be implemented. Most
> importantly, we will need 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`
> (should mostly be 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 would be 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
> }}}
> It would be nice to do this without explicitly invoking the embeddings;
> as a shortcut, `Fbar` should have 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 assumes that an `AlgebraicClosureFiniteFieldElement`
> is printed in the same way as the underlying `FiniteFieldElement`; we do
> not necessarily have to do this.)
>
> It is conceivable that there will be different coexisting implementations
> (classes deriving from an abstract `AlgebraicClosureFiniteField`). The
> first (and easiest) to implement should use Conway polynomials and the
> pseudo-Conway polynomials from #14958, probably using some of the code
> from #8335.
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`
- 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.
--
Comment:
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 '''F''',,''p'',,. But this can probably wait
until another ticket.
--
Ticket URL: <http://trac.sagemath.org/ticket/14990#comment:3>
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.
