58 Fields and Division Rings
  
  A  division  ring is a ring (see Chapter 56) 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 59) and abelian number fields (see
  Chapter 60), in particular the field of rationals (see Chapter 17).
  
  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 61). 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  (58.1-2)),  thus  each field is in fact a field extension in a
  natural  way,  which  is  used  by functions such as Norm (58.3-4) and Trace
  (58.3-5) (see 58.3).
  
  
  58.1 Generating Fields
  
  58.1-1 IsDivisionRing
  
  IsDivisionRing( D )  Category
  
  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  the  value  of  the  attribute
  LeftActingDomain (57.1-11) of D.
  
  58.1-2 IsField
  
  IsField( D )  filter
  
  A   field  is  a  commutative  division  ring  (see IsDivisionRing  (58.1-1)
  and IsCommutative (35.4-9)).
  
    Example  
    gap> IsField( GaloisField(16) );           # the field with 16 elements
    true
    gap> IsField( Rationals );                 # the field of rationals
    true
    gap> q:= QuaternionAlgebra( Rationals );;  # noncommutative division ring
    gap> IsField( q );  IsDivisionRing( q );
    false
    true
    gap> mat:= [ [ 1 ] ];;  a:= Algebra( Rationals, [ mat ] );;
    gap> IsDivisionRing( a );   # algebra not constructed as a division ring
    false
  
  
  58.1-3 Field
  
  Field( z, ... )  function
  Field( [F, ]list )  function
  
  Field returns the smallest field K that contains all the elements z, ..., 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.  Called  with a field F and a list list, Field
  constructs  the  field  generated by F and the elements in list, as a vector
  space over F.
  
  58.1-4 DefaultField
  
  DefaultField( z, ... )  function
  DefaultField( list )  function
  
  DefaultField  returns  a field K that contains all the elements z, ..., 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  (58.1-3).  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.
  
    Example  
    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
  
  
  58.1-5 DefaultFieldByGenerators
  
  DefaultFieldByGenerators( [z, ...] )  operation
  
  returns  the default field containing the elements z, .... This field may be
  bigger than the smallest field containing these elements.
  
  58.1-6 GeneratorsOfDivisionRing
  
  GeneratorsOfDivisionRing( D )  attribute
  
  generators  with  respect  to  addition, multiplication, and taking inverses
  (the identity cannot be omitted ...)
  
  58.1-7 GeneratorsOfField
  
  GeneratorsOfField( F )  attribute
  
  generators  with  respect  to addition, multiplication, and taking inverses.
  This attribute is the same as GeneratorsOfDivisionRing (58.1-6).
  
  58.1-8 DivisionRingByGenerators
  
  DivisionRingByGenerators( [F, ]gens )  operation
  FieldByGenerators( [F, ]gens )  operation
  
  Called  with  a field F and a list gens of scalars, DivisionRingByGenerators
  returns  the  division  ring  over  F  generated  by gens. The unary version
  returns  the division ring as vector space over FieldOverItselfByGenerators(
  gens ).
  
  FieldByGenerators is just a synonym for DivisionRingByGenerators.
  
  58.1-9 AsDivisionRing
  
  AsDivisionRing( [F, ]C )  operation
  AsField( [F, ]C )  operation
  
  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.
  
  
  58.2 Subfields of Fields
  
  58.2-1 Subfield
  
  Subfield( F, gens )  function
  SubfieldNC( F, gens )  function
  
  Constructs the subfield of F generated by gens.
  
  58.2-2 FieldOverItselfByGenerators
  
  FieldOverItselfByGenerators( [z, ...] )  operation
  
  This operation is needed for the call of Field (58.1-3) or FieldByGenerators
  (58.1-8)  without  explicitly  given  subfield, in order to construct a left
  acting domain for such a field.
  
  58.2-3 PrimitiveElement
  
  PrimitiveElement( D )  attribute
  
  is  an  element  of  D that generates D as a division ring together with the
  left acting domain.
  
  58.2-4 PrimeField
  
  PrimeField( D )  attribute
  
  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.
  
  58.2-5 IsPrimeField
  
  IsPrimeField( D )  property
  
  A  division  ring  is  a  prime  field  if  it  is  equal to its prime field
  (see PrimeField (58.2-4)).
  
  58.2-6 DegreeOverPrimeField
  
  DegreeOverPrimeField( F )  attribute
  
  is the degree of the field F over its prime field (see PrimeField (58.2-4)).
  
  58.2-7 DefiningPolynomial
  
  DefiningPolynomial( F )  attribute
  
  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 (58.2-8).
  
  58.2-8 RootOfDefiningPolynomial
  
  RootOfDefiningPolynomial( F )  attribute
  
  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 (58.2-7).
  
  58.2-9 FieldExtension
  
  FieldExtension( F, poly )  operation
  
  is the field obtained on adjoining a root of the irreducible polynomial poly
  to the field F.
  
  58.2-10 Subfields
  
  Subfields( F )  attribute
  
  is the set of all subfields of the field F.
  
  
  58.3 Galois Action
  
  Let L > K be a field extension of finite degree. Then to each element α ∈ L,
  we  can associate a K-linear mapping φ_α on L, and for a fixed K-basis of L,
  we can associate to α the matrix M_α (over K) of this mapping.
  
  The  norm  of  α  is  defined  as  the determinant of M_α, the trace of α is
  defined  as  the  trace  of  M_α,  the  minimal polynomial μ_α and the trace
  polynomial  χ_α  of α are defined as the minimal polynomial (see 66.8-1) and
  the  characteristic  polynomial  (see CharacteristicPolynomial (24.13-1) and
  TracePolynomial  (58.3-3))  of M_α. (Note that μ_α depends only on K whereas
  χ_α depends on both L and K.)
  
  Thus  norm and trace of α are elements of K, and μ_α and χ_α are polynomials
  over K, χ_α being a power of μ_α, and the degree of χ_α equals the degree of
  the field extension L > K.
  
  The conjugates of α in L are those roots of χ_α (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 α are all roots of χ_α
  (with multiplicity), the set of conjugates equals the roots of μ_α, the norm
  of  α equals the product and the trace of α equals the sum of the conjugates
  of  α,  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 ).
  
  The  default  methods  for  field elements are as follows. MinimalPolynomial
  (66.8-1)  solves  a  system  of  linear  equations, TracePolynomial (58.3-3)
  computes  the appropriate power of the minimal polynomial, Norm (58.3-4) and
  Trace  (58.3-5)  values  are  obtained as coefficients of the characteristic
  polynomial,   and   Conjugates   (58.3-6)  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 (58.3-6) returns the
  sorted  list  of  images (with multiplicity) of the element under the Galois
  group,  Norm (58.3-4) computes the product of the conjugates, Trace (58.3-5)
  computes   the   sum   of   the  conjugates,  TracePolynomial  (58.3-3)  and
  MinimalPolynomial  (66.8-1) compute the product of linear factors x - c with
  c ranging over the conjugates and the set of conjugates, respectively.
  
  58.3-1 GaloisGroup
  
  GaloisGroup( F )  attribute
  
  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.
  
    Example  
    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
  
  
  58.3-2 MinimalPolynomial
  
  MinimalPolynomial( F, z[, ind] )  operation
  
  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 (66.8-1) for
  rings.)
  
    Example  
    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))
  
  
  58.3-3 TracePolynomial
  
  TracePolynomial( L, K, z[, inum] )  operation
  
  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  (24.13-1) that call TracePolynomial in the case of
  field extensions.
  
    Example  
    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
  
  
  58.3-4 Norm
  
  Norm( [L, [K, ]]z )  attribute
  
  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.
  
  
  58.3-5 Traces of field elements and matrices
  
  Trace( [L, [K, ]]z )  attribute
  Trace( mat )  attribute
  
  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.
  
  58.3-6 Conjugates
  
  Conjugates( [L, [K, ]]z )  attribute
  
  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,
  or  of  the  default  field  of z, respectively. The result list need not be
  sorted.
  
    Example  
    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 ]
  
  
  58.3-7 NormalBase
  
  NormalBase( F[, elm] )  attribute
  
  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 (58.3-1)) 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 [Art73].
  
    Example  
    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 ]