% This file was created automatically from fields.msk. % DO NOT EDIT! %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %A fields.msk GAP documentation Thomas Breuer %% %A @(#)$Id: fields.msk,v 1.17.2.2 2006/09/16 19:02:49 jjm Exp $ %% %Y (C) 1998 School Math and Comp. Sci., University of St. Andrews, Scotland %Y Copyright (C) 2002 The GAP Group %% \Chapter{Fields and Division Rings} \index{fields} \index{division rings} A *division ring* is a ring (see Chapter~"Rings") in which every non-zero element has an inverse. The most important class of division rings are the commutative ones, which are called *fields*. {\GAP} supports finite fields (see Chapter~"Finite Fields") and abelian number fields (see Chapter~"Abelian Number Fields"), in particular the field of rationals (see Chapter~"Rational Numbers"). This chapter describes the general {\GAP} functions for fields and division rings. If a field <F> is a subfield of a commutative ring <C>, <C> can be considered as a vector space over the (left) acting domain <F> (see Chapter~"Vector Spaces"). In this situation, we call <F> the *field of definition* of <C>. Each field in {\GAP} is represented as a vector space over a subfield (see~"IsField"), thus each field is in fact a field extension in a natural way, which is used by functions such as `Norm' and `Trace' (see~"Galois Action"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Generating Fields} \>IsDivisionRing( <D> ) C A *division ring* in {\GAP} is a nontrivial associative algebra <D> with a multiplicative inverse for each nonzero element. In {\GAP} every division ring is a vector space over a division ring (possibly over itself). Note that being a division ring is thus not a property that a ring can get, because a ring is usually not represented as a vector space. The field of coefficients is stored as `LeftActingDomain( <D> )'. \>IsField( <D> ) P A *field* is a commutative division ring (see~"IsDivisionRing" and~"IsCommutative"). \beginexample gap> IsField( GaloisField(16) ); # the field with 16 elements true gap> IsField( Rationals ); # the field of rationals true gap> q:= QuaternionAlgebra( Rationals );; # a noncommutative division ring gap> IsField( q ); IsDivisionRing( q ); false true gap> mat:= [ [ 1 ] ];; a:= Algebra( Rationals, [ mat ] );; gap> IsDivisionRing( a ); # an algebra not constructed as a division ring false \endexample \>Field( <z>, ... ) F \>Field( <list> ) F \>Field( <F>, <list> ) F `Field' returns the smallest field $K$ that contains all the elements $<z>, \ldots$, or the smallest field $K$ that contains all elements in the list <list>. If no subfield <F> is given, $K$ is constructed as a field over itself, i.e. the left acting domain of $K$ is $K$. In the third form, `Field' constructs the field generated by the field <F> and the elements in the list <list>, as a vector space over <F>. \>DefaultField( <z>, ... ) F \>DefaultField( <list> ) F `DefaultField' returns a field $K$ that contains all the elements $<z>, \ldots$, or a field $K$ that contains all elements in the list <list>. This field need not be the smallest field in which the elements lie, cf.~`Field' (see~"Field"). For example, for elements from cyclotomic fields `DefaultField' returns the smallest cyclotomic field in which the elements lie, but the elements may lie in a smaller number field which is not a cyclotomic field. \beginexample gap> Field( Z(4) ); Field( [ Z(4), Z(8) ] ); # finite fields GF(2^2) GF(2^6) gap> Field( E(9) ); Field( CF(4), [ E(9) ] ); # abelian number fields CF(9) AsField( GaussianRationals, CF(36) ) gap> f1:= Field( EB(5) ); f2:= DefaultField( EB(5) ); NF(5,[ 1, 4 ]) CF(5) gap> f1 = f2; IsSubset( f2, f1 ); false true \endexample \>DefaultFieldByGenerators( [ <z>, ... ] ) O returns the default field containing the elements <z>,$\ldots$. This field may be bigger than the smallest field containing these elements. \>GeneratorsOfDivisionRing( <D> ) A generators with respect to addition, multiplication, and taking inverses (the identity cannot be omitted ...) \>GeneratorsOfField( <F> ) A generators with respect to addition, multiplication, and taking inverses. This attribute is the same as `GeneratorsOfDivisionRing' (see~"GeneratorsOfDivisionRing"). \>DivisionRingByGenerators( [ <z>, ... ] ) O \>DivisionRingByGenerators( <F>, [ <z>, ... ] ) O The first version returns a division ring as vector space over `FieldOverItselfByGenerators( <gens> )'. \>AsDivisionRing( <C> ) O \>AsDivisionRing( <F>, <C> ) O \>AsField( <C> ) O \>AsField( <F>, <C> ) O If the collection <C> can be regarded as a division ring then `AsDivisionRing( <C> )' is the division ring that consists of the elements of <C>, viewed as a vector space over its prime field; otherwise `fail' is returned. In the second form, if <F> is a division ring contained in <C> then the returned division ring is viewed as a vector space over <F>. `AsField' is just a synonym for `AsDivisionRing'. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Subfields of Fields} \>Subfield( <F>, <gens> ) F \>SubfieldNC( <F>, <gens> ) F Constructs the subfield of <F> generated by <gens>. \>FieldOverItselfByGenerators( [ <z>, ... ] ) O This operation is needed for the call of `Field' or `FieldByGenerators' without explicitly given subfield, in order to construct a left acting domain for such a field. \>PrimitiveElement( <D> ) A is an element of <D> that generates <D> as a division ring together with the left acting domain. \>PrimeField( <D> ) A The *prime field* of a division ring <D> is the smallest field which is contained in <D>. For example, the prime field of any field in characteristic zero is isomorphic to the field of rational numbers. \>IsPrimeField( <D> ) P A division ring is a prime field if it is equal to its prime field (see~"PrimeField"). \>DegreeOverPrimeField( <F> ) A is the degree of the field <F> over its prime field (see~"PrimeField"). \>DefiningPolynomial( <F> ) A is the defining polynomial of the field <F> as a field extension over the left acting domain of <F>. A root of the defining polynomial can be computed with `RootOfDefiningPolynomial' (see~"RootOfDefiningPolynomial"). \>RootOfDefiningPolynomial( <F> ) A is a root in the field <F> of its defining polynomial as a field extension over the left acting domain of <F>. The defining polynomial can be computed with `DefiningPolynomial' (see~"DefiningPolynomial"). \>FieldExtension( <F>, <poly> ) O is the field obtained on adjoining a root of the irreducible polynomial <poly> to the field <F>. \>Subfields( <F> ) A is the set of all subfields of the field <F>. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Galois Action} Let $L > K$ be a field extension of finite degree. Then to each element $\alpha \in L$, we can associate a $K$-linear mapping $\varphi_{\alpha}$ on $L$, and for a fixed $K$-basis of $L$, we can associate to $\alpha$ the matrix $M_{\alpha}$ (over $K$) of this mapping. The *norm* of $\alpha$ is defined as the determinant of $M_{\alpha}$, the *trace* of $\alpha$ is defined as the trace of $M_{\alpha}$, the *minimal polynomial* $\mu_{\alpha}$ and the *trace polynomial* $\chi_{\alpha}$ of $\alpha$ are defined as the minimal polynomial (see~"MinimalPolynomial!over a field") and the characteristic polynomial (see~"CharacteristicPolynomial" and "TracePolynomial") of $M_{\alpha}$. (Note that $\mu_{\alpha}$ depends only on $K$ whereas $\chi_{\alpha}$ depends on both $L$ and $K$.) Thus norm and trace of $\alpha$ are elements of $K$, and $\mu_{\alpha}$ and $\chi_{\alpha}$ are polynomials over $K$, $\chi_{\alpha}$ being a power of $\mu_{\alpha}$, and the degree of $\chi_{\alpha}$ equals the degree of the field extension $L > K$. The *conjugates* of $\alpha$ in $L$ are those roots of $\chi_{\alpha}$ (with multiplicity) that lie in $L$; note that if only $L$ is given, there is in general no way to access the roots outside $L$. Analogously, the *Galois group* of the extension $L > K$ is defined as the group of all those field automorphisms of $L$ that fix $K$ pointwise. If $L > K$ is a Galois extension then the conjugates of $\alpha$ are all roots of $\chi_{\alpha}$ (with multiplicity), the set of conjugates equals the roots of $\mu_{\alpha}$, the norm of $\alpha$ equals the product and the trace of $\alpha$ equals the sum of the conjugates of $\alpha$, and the Galois group in the sense of the above definition equals the usual Galois group, Note that `MinimalPolynomial( <F>, <z> )' is a polynomial *over* <F>, whereas `Norm( <F>, <z> )' is the norm of the element <z> *in* <F> w.r.t.~the field extension $<F> > `LeftActingDomain( <F> )'$. \indextt{IsFieldControlledByGaloisGroup} \>GaloisGroup( <F> )!{of field} A The *Galois group* of a field <F> is the group of all field automorphisms of <F> that fix the subfield $K = `LeftActingDomain( <F> )'$ pointwise. Note that the field extension $<F> > K$ need *not* be a Galois extension. \beginexample gap> g:= GaloisGroup( AsField( GF(2^2), GF(2^12) ) );; gap> Size( g ); IsCyclic( g ); 6 true gap> h:= GaloisGroup( CF(60) );; gap> Size( h ); IsAbelian( h ); 16 true \endexample \>MinimalPolynomial( <F>, <z>[, <ind>] )!{over a field} O returns the minimal polynomial of <z> over the field <F>. This is a generator of the ideal in $<F>[x]$ of all polynomials which vanish on <z>. (This definition is consistent with the general definition of `MinimalPolynomial' for rings, see~"MinimalPolynomial".) \beginexample gap> MinimalPolynomial( Rationals, E(8) ); x_1^4+1 gap> MinimalPolynomial( CF(4), E(8) ); x_1^2+(-E(4)) gap> MinimalPolynomial( CF(8), E(8) ); x_1+(-E(8)) \endexample \>TracePolynomial( <L>, <K>, <z>[, <inum>] ) O returns the polynomial that is the product of $(X - c)$ where $c$ runs over the conjugates of <z> in the field extension <L> over <K>. The polynomial is returned as a univariate polynomial over <K> in the indeterminate number <inum> (defaulting to 1). This polynomial is sometimes also called the *characteristic polynomial* of <z> w.r.t.~the field extension $<L> > <K>$. Therefore methods are installed for `CharacteristicPolynomial' (see~"CharacteristicPolynomial") that call `TracePolynomial' in the case of field extensions. \index{characteristic polynomial!for field elements} \beginexample gap> TracePolynomial( CF(8), Rationals, E(8) ); x_1^4+1 gap> TracePolynomial( CF(16), Rationals, E(8) ); x_1^8+2*x_1^4+1 \endexample \>Norm( <z> ) A \>Norm( <L>, <z> ) O \>Norm( <L>, <K>, <z> ) O `Norm' returns the norm of the field element <z>. If two fields <L> and <K> are given then the norm is computed w.r.t.~the field extension $<L> > <K>$, if only one field <L> is given then `LeftActingDomain( <L> )' is taken as default for the subfield <K>, and if no field is given then `DefaultField( <z> )' is taken as default for <L>. \>Trace( <z> )!{for field elements} A \>Trace( <mat> )!{for field elements} A \>Trace( <L>, <z> )!{for field elements} O \>Trace( <L>, <K>, <z> )!{for field elements} O `Trace' returns the trace of the field element <z>. If two fields <L> and <K> are given then the trace is computed w.r.t.~the field extension $<L> > <K>$, if only one field <L> is given then `LeftActingDomain( <L> )' is taken as default for the subfield <K>, and if no field is given then `DefaultField( <z> )' is taken as default for <L>. The *trace of a matrix* is the sum of its diagonal entries. Note that this is *not* compatible with the definition of `Trace' for field elements, so the one-argument version is not suitable when matrices shall be regarded as field elements. \>Conjugates( <z> ) A \>Conjugates( <L>, <z> ) O \>Conjugates( <L>, <K>, <z> ) O `Conjugates' returns the list of *conjugates* of the field element <z>. If two fields <L> and <K> are given then the conjugates are computed w.r.t.~the field extension $<L> > <K>$, if only one field <L> is given then `LeftActingDomain( <L> )' is taken as default for the subfield <K>, and if no field is given then `DefaultField( <z> )' is taken as default for <L>. The result list will contain duplicates if <z> lies in a proper subfield of <L>, respectively of the default field of <z>. The result list need not be sorted. \beginexample gap> Norm( E(8) ); Norm( CF(8), E(8) ); 1 1 gap> Norm( CF(8), CF(4), E(8) ); -E(4) gap> Norm( AsField( CF(4), CF(8) ), E(8) ); -E(4) gap> Trace( E(8) ); Trace( CF(8), CF(8), E(8) ); 0 E(8) gap> Conjugates( CF(8), E(8) ); [ E(8), E(8)^3, -E(8), -E(8)^3 ] gap> Conjugates( CF(8), CF(4), E(8) ); [ E(8), -E(8) ] gap> Conjugates( CF(16), E(8) ); [ E(8), E(8)^3, -E(8), -E(8)^3, E(8), E(8)^3, -E(8), -E(8)^3 ] \endexample The default methods for field elements are as follows. `MinimalPolynomial' solves a system of linear equations, `TracePolynomial' computes the appropriate power of the minimal polynomial, `Norm' and `Trace' values are obtained as coefficients of the characteristic polynomial, and `Conjugates' uses the factorization of the characteristic polynomial. For elements in finite fields and cyclotomic fields, one wants to do the computations in a different way since the field extensions in question are Galois extensions, and the Galois groups are well-known in these cases. More general, if a field is in the category `IsFieldControlledByGaloisGroup' then the default methods are the following. `Conjugates' returns the sorted list of images (with multiplicity) of the element under the Galois group, `Norm' computes the product of the conjugates, `Trace' computes the sum of the conjugates, `TracePolynomial' and `MinimalPolynomial' compute the product of linear factors $x - c$ with $c$ ranging over the conjugates and the set of conjugates, respectively. \>NormalBase( <F> ) A \>NormalBase( <F>, <elm> ) O Let <F> be a field that is a Galois extension of its subfield `LeftActingDomain( <F> )'. Then `NormalBase' returns a list of elements in <F> that form a normal basis of <F>, that is, a vector space basis that is closed under the action of the Galois group (see~"GaloisGroup!of field") of <F>. If a second argument <elm> is given, it is used as a hint for the algorithm to find a normal basis with the algorithm described in~\cite{Art68}. \beginexample gap> NormalBase( CF(5) ); [ -E(5), -E(5)^2, -E(5)^3, -E(5)^4 ] gap> NormalBase( CF(4) ); [ 1/2-1/2*E(4), 1/2+1/2*E(4) ] gap> NormalBase( GF(3^6) ); [ Z(3^6)^2, Z(3^6)^6, Z(3^6)^18, Z(3^6)^54, Z(3^6)^162, Z(3^6)^486 ] gap> NormalBase( GF( GF(8), 2 ) ); [ Z(2^6), Z(2^6)^8 ] \endexample %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\Section{Field Homomorphisms} % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %E