Algebraic closures of finite fields#
Let \(\Bold{F}\) be a finite field, and let \(\overline{\Bold{F}}\) be an algebraic closure of \(\Bold{F}\); this is unique up to (non-canonical) isomorphism. For every \(n\ge 1\), there is a unique subfield \(\Bold{F}_n\) of \(\overline{\Bold{F}}\) such that \(\Bold{F}\subset\Bold{F}_n\) and \([\Bold{F}_n:\Bold{F}]=n\).
In Sage, algebraic closures of finite fields are implemented using compatible systems of finite fields. The resulting Sage object keeps track of a finite lattice of the subfields \(\Bold{F}_n\) and the embeddings between them. This lattice is extended as necessary.
The Sage class corresponding to \(\overline{\Bold{F}}\) can be
constructed from the finite field \(\Bold{F}\) by using the
algebraic_closure()
method.
The Sage class for elements of \(\overline{\Bold{F}}\) is
AlgebraicClosureFiniteFieldElement
. Such an element is
represented as an element of one of the \(\Bold{F}_n\). This means that
each element \(x\in\Bold{F}\) has infinitely many different
representations, one for each \(n\) such that \(x\) is in \(\Bold{F}_n\).
Note
Only prime finite fields are currently accepted as base fields for algebraic closures. To obtain an algebraic closure of a non-prime finite field \(\Bold{F}\), take an algebraic closure of the prime field of \(\Bold{F}\) and embed \(\Bold{F}\) into this.
Algebraic closures of finite fields are currently implemented
using (pseudo-)Conway polynomials; see
AlgebraicClosureFiniteField_pseudo_conway
and the module
conway_polynomials
. Other
implementations may be added by creating appropriate subclasses of
AlgebraicClosureFiniteField_generic
.
In the current implementation, algebraic closures do not satisfy the unique parent condition. Moreover, there is no coercion map between different algebraic closures of the same finite field. There is a conceptual reason for this, namely that the definition of pseudo-Conway polynomials only determines an algebraic closure up to non-unique isomorphism. This means in particular that different algebraic closures, and their respective elements, never compare equal.
AUTHORS:
Peter Bruin (August 2013): initial version
Vincent Delecroix (November 2013): additional methods
- sage.rings.algebraic_closure_finite_field.AlgebraicClosureFiniteField(base_ring, name, category=None, implementation=None, **kwds)#
Construct an algebraic closure of a finite field.
The recommended way to use this functionality is by calling the
algebraic_closure()
method of the finite field.Note
Algebraic closures of finite fields in Sage do not have the unique representation property, because they are not determined up to unique isomorphism by their defining data.
EXAMPLES:
sage: from sage.rings.algebraic_closure_finite_field import AlgebraicClosureFiniteField sage: F = GF(2).algebraic_closure() sage: F1 = AlgebraicClosureFiniteField(GF(2), 'z') sage: F1 is F False
In the pseudo-Conway implementation, non-identical instances never compare equal:
sage: F1 == F False sage: loads(dumps(F)) == F False
This is to ensure that the result of comparing two instances cannot change with time.
- class sage.rings.algebraic_closure_finite_field.AlgebraicClosureFiniteFieldElement(parent, value)#
Bases:
FieldElement
Element of an algebraic closure of a finite field.
EXAMPLES:
sage: F = GF(3).algebraic_closure() sage: F.gen(2) z2 sage: type(F.gen(2)) <class 'sage.rings.algebraic_closure_finite_field.AlgebraicClosureFiniteField_pseudo_conway_with_category.element_class'>
- as_finite_field_element(minimal=False)#
Return
self
as a finite field element.INPUT:
minimal
– boolean (default:False
). IfTrue
, always return the smallest subfield containingself
.
OUTPUT:
a triple (
field
,element
,morphism
) wherefield
is a finite field,element
an element offield
andmorphism
a morphism fromfield
toself.parent()
.
EXAMPLES:
sage: F = GF(3).algebraic_closure('t') sage: t = F.gen(5) sage: t.as_finite_field_element() (Finite Field in t5 of size 3^5, t5, Ring morphism: From: Finite Field in t5 of size 3^5 To: Algebraic closure of Finite Field of size 3 Defn: t5 |--> t5)
By default,
field
is not necessarily minimal. We can force it to be minimal using theminimal
option:sage: s = t + 1 - t sage: s.as_finite_field_element()[0] Finite Field in t5 of size 3^5 sage: s.as_finite_field_element(minimal=True)[0] Finite Field of size 3
This also works when the element has to be converted between two non-trivial finite subfields (see github issue #16509):
sage: K = GF(5).algebraic_closure() sage: z = K.gen(5) - K.gen(5) + K.gen(2) sage: z.as_finite_field_element(minimal=True) (Finite Field in z2 of size 5^2, z2, Ring morphism: From: Finite Field in z2 of size 5^2 To: Algebraic closure of Finite Field of size 5 Defn: z2 |--> z2)
There are automatic coercions between the various subfields:
sage: a = K.gen(2) + 1 sage: _,b,_ = a.as_finite_field_element() sage: K4 = K.subfield(4)[0] sage: K4(b) z4^3 + z4^2 + z4 + 4 sage: b.minimal_polynomial() == K4(b).minimal_polynomial() True sage: K(K4(b)) == K(b) True
You can also use the inclusions that are implemented at the level of the algebraic closure:
sage: f = K.inclusion(2,4); f Ring morphism: From: Finite Field in z2 of size 5^2 To: Finite Field in z4 of size 5^4 Defn: z2 |--> z4^3 + z4^2 + z4 + 3 sage: f(b) z4^3 + z4^2 + z4 + 4
- change_level(n)#
Return a representation of
self
as an element of the subfield of degree \(n\) of the parent, if possible.EXAMPLES:
sage: F = GF(3).algebraic_closure() sage: z = F.gen(4) sage: (z^10).change_level(6) 2*z6^5 + 2*z6^3 + z6^2 + 2*z6 + 2 sage: z.change_level(6) Traceback (most recent call last): ... ValueError: z4 is not in the image of Ring morphism: From: Finite Field in z2 of size 3^2 To: Finite Field in z4 of size 3^4 Defn: z2 |--> 2*z4^3 + 2*z4^2 + 1 sage: a = F(1).change_level(3); a 1 sage: a.change_level(2) 1 sage: F.gen(3).change_level(1) Traceback (most recent call last): ... ValueError: z3 is not in the image of Ring morphism: From: Finite Field of size 3 To: Finite Field in z3 of size 3^3 Defn: 1 |--> 1
- is_square()#
Return
True
ifself
is a square.This always returns
True
.EXAMPLES:
sage: F = GF(3).algebraic_closure() sage: F.gen(2).is_square() True
- minimal_polynomial()#
Return the minimal polynomial of
self
over the prime field.EXAMPLES:
sage: F = GF(11).algebraic_closure() sage: F.gen(3).minpoly() x^3 + 2*x + 9
- minpoly()#
Return the minimal polynomial of
self
over the prime field.EXAMPLES:
sage: F = GF(11).algebraic_closure() sage: F.gen(3).minpoly() x^3 + 2*x + 9
- multiplicative_order()#
Return the multiplicative order of
self
.EXAMPLES:
sage: K = GF(7).algebraic_closure() sage: K.gen(5).multiplicative_order() 16806 sage: (K.gen(1) + K.gen(2) + K.gen(3)).multiplicative_order() 7353
- nth_root(n)#
Return an \(n\)-th root of
self
.EXAMPLES:
sage: F = GF(5).algebraic_closure() sage: t = F.gen(2) + 1 sage: s = t.nth_root(15); s 4*z6^5 + 3*z6^4 + 2*z6^3 + 2*z6^2 + 4 sage: s**15 == t True
Todo
This function could probably be made faster.
- pth_power(k=1)#
Return the \(p^k\)-th power of
self
, where \(p\) is the characteristic ofself.parent()
.EXAMPLES:
sage: K = GF(13).algebraic_closure('t') sage: t3 = K.gen(3) sage: s = 1 + t3 + t3**2 sage: s.pth_power() 10*t3^2 + 6*t3 sage: s.pth_power(2) 2*t3^2 + 6*t3 + 11 sage: s.pth_power(3) t3^2 + t3 + 1 sage: s.pth_power(3).parent() is K True
- pth_root(k=1)#
Return the unique \(p^k\)-th root of
self
, where \(p\) is the characteristic ofself.parent()
.EXAMPLES:
sage: K = GF(13).algebraic_closure('t') sage: t3 = K.gen(3) sage: s = 1 + t3 + t3**2 sage: s.pth_root() 2*t3^2 + 6*t3 + 11 sage: s.pth_root(2) 10*t3^2 + 6*t3 sage: s.pth_root(3) t3^2 + t3 + 1 sage: s.pth_root(2).parent() is K True
- sqrt(all=False)#
Return a square root of
self
.If the optional keyword argument
all
is set toTrue
, return a list of all square roots ofself
instead.EXAMPLES:
sage: F = GF(3).algebraic_closure() sage: F.gen(2).sqrt() z4^3 + z4 + 1 sage: F.gen(2).sqrt(all=True) [z4^3 + z4 + 1, 2*z4^3 + 2*z4 + 2] sage: (F.gen(2)^2).sqrt() z2 sage: (F.gen(2)^2).sqrt(all=True) [z2, 2*z2]
- class sage.rings.algebraic_closure_finite_field.AlgebraicClosureFiniteField_generic(base_ring, name, category=None)#
Bases:
Field
Algebraic closure of a finite field.
- Element#
alias of
AlgebraicClosureFiniteFieldElement
- algebraic_closure()#
Return an algebraic closure of
self
.This always returns
self
.EXAMPLES:
sage: from sage.rings.algebraic_closure_finite_field import AlgebraicClosureFiniteField sage: F = AlgebraicClosureFiniteField(GF(5), 'z') sage: F.algebraic_closure() is F True
- characteristic()#
Return the characteristic of
self
.EXAMPLES:
sage: from sage.rings.algebraic_closure_finite_field import AlgebraicClosureFiniteField sage: p = next_prime(1000) sage: F = AlgebraicClosureFiniteField(GF(p), 'z') sage: F.characteristic() == p True
- gen(n)#
Return the \(n\)-th generator of
self
.EXAMPLES:
sage: from sage.rings.algebraic_closure_finite_field import AlgebraicClosureFiniteField sage: F = AlgebraicClosureFiniteField(GF(5), 'z') sage: F.gen(2) z2
- gens()#
Return a family of generators of
self
.OUTPUT:
a
Family
, indexed by the positive integers, whose \(n\)-th element isself.gen(n)
.
EXAMPLES:
sage: from sage.rings.algebraic_closure_finite_field import AlgebraicClosureFiniteField sage: F = AlgebraicClosureFiniteField(GF(5), 'z') sage: g = F.gens(); g Lazy family (...(i))_{i in Positive integers} sage: g[3] z3
- inclusion(m, n)#
Return the canonical inclusion map from the subfield of degree \(m\) to the subfield of degree \(n\).
EXAMPLES:
sage: F = GF(3).algebraic_closure() sage: F.inclusion(1, 2) Ring morphism: From: Finite Field of size 3 To: Finite Field in z2 of size 3^2 Defn: 1 |--> 1 sage: F.inclusion(2, 4) Ring morphism: From: Finite Field in z2 of size 3^2 To: Finite Field in z4 of size 3^4 Defn: z2 |--> 2*z4^3 + 2*z4^2 + 1
- ngens()#
Return the number of generators of
self
, which is infinity.EXAMPLES:
sage: from sage.rings.algebraic_closure_finite_field import AlgebraicClosureFiniteField sage: AlgebraicClosureFiniteField(GF(5), 'z').ngens() +Infinity
- some_elements()#
Return some elements of this field.
EXAMPLES:
sage: F = GF(7).algebraic_closure() sage: F.some_elements() (1, z2, z3 + 1)
- subfield(n)#
Return the unique subfield of degree \(n\) of
self
together with its canonical embedding intoself
.EXAMPLES:
sage: F = GF(3).algebraic_closure() sage: F.subfield(1) (Finite Field of size 3, Ring morphism: From: Finite Field of size 3 To: Algebraic closure of Finite Field of size 3 Defn: 1 |--> 1) sage: F.subfield(4) (Finite Field in z4 of size 3^4, Ring morphism: From: Finite Field in z4 of size 3^4 To: Algebraic closure of Finite Field of size 3 Defn: z4 |--> z4)
- class sage.rings.algebraic_closure_finite_field.AlgebraicClosureFiniteField_pseudo_conway(base_ring, name, category=None, lattice=None, use_database=True)#
Bases:
WithEqualityById
,AlgebraicClosureFiniteField_generic
Algebraic closure of a finite field, constructed using pseudo-Conway polynomials.
EXAMPLES:
sage: F = GF(5).algebraic_closure(implementation='pseudo_conway') sage: F.cardinality() +Infinity sage: F.algebraic_closure() is F True sage: x = F(3).nth_root(12); x z4^3 + z4^2 + 4*z4 sage: x**12 3