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:
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.
Bases: sage.structure.element.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'>
Return self as a finite field element.
INPUT:
OUTPUT:
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 the minimal 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 trac ticket #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 is currently no automatic conversion 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)
Traceback (most recent call last):
...
TypeError: unable to coerce from a finite field other than the prime
subfield
Nevertheless it is possible to 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
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
Return True if self is a square.
This always returns True.
EXAMPLES:
sage: F = GF(3).algebraic_closure()
sage: F.gen(2).is_square()
True
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
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
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
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.
Return the \(p^k\)-th power of self, where \(p\) is the characteristic of self.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
Return the unique \(p^k\)-th root of self, where \(p\) is the characteristic of self.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
Return a square root of self.
EXAMPLES:
sage: F = GF(3).algebraic_closure()
sage: F.gen(2).sqrt()
z4^3 + z4 + 1
Bases: sage.rings.ring.Field
Algebraic closure of a finite field.
alias of AlgebraicClosureFiniteFieldElement
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
Return the cardinality of self.
This always returns +Infinity.
Todo
When trac ticket #10963 is merged we should remove that method and set the category to infinite fields (i.e. Fields().Infinite()).
EXAMPLES:
sage: F = GF(3).algebraic_closure()
sage: F.cardinality()
+Infinity
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
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
Return a family of generators of self.
OUTPUT:
EXAMPLES:
sage: from sage.rings.algebraic_closure_finite_field import AlgebraicClosureFiniteField
sage: F = AlgebraicClosureFiniteField(GF(5), 'z')
sage: g = F.gens()
sage: g
Lazy family (<lambda>(i))_{i in Positive integers}
sage: g[3]
z3
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
Returns False as an algebraically closed field is always infinite.
Todo
When trac ticket #10963 is merged we should remove that method and set the category to infinite fields (i.e. Fields().Infinite()).
EXAMPLES:
sage: GF(3).algebraic_closure().is_finite()
False
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
Return some elements of this field.
EXAMPLES:
sage: F = GF(7).algebraic_closure()
sage: F.some_elements()
(1, z2, z3 + 1)
Return the unique subfield of degree \(n\) of self together with its canonical embedding into self.
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)
Bases: sage.rings.algebraic_closure_finite_field.AlgebraicClosureFiniteField_generic, sage.misc.fast_methods.WithEqualityById
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
TESTS:
sage: F3 = GF(3).algebraic_closure()
sage: F3 == F3
True
sage: F5 = GF(5).algebraic_closure()
sage: F3 == F5
False