#############################################################################
##
#W  fldabnum.gd                 GAP library                     Thomas Breuer
##
#H  @(#)$Id: fldabnum.gd,v 4.24.2.1 2005/08/10 16:38:44 gap Exp $
##
#Y  Copyright (C)  1996,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
#Y  (C) 1998 School Math and Comp. Sci., University of St.  Andrews, Scotland
#Y  Copyright (C) 2002 The GAP Group
##
##  This file declares operations for fields consisting of cyclotomics.
##
##  Note that we must distinguish abelian number fields and fields
##  that consist of cyclotomics.
##  (The image of the natural embedding of the rational number field
##  into a field of rational functions is of course an abelian number field
##  but its elements are not cyclotomics since this would be a property given
##  by their family.)
##
Revision.fldabnum_gd :=
    "@(#)$Id: fldabnum.gd,v 4.24.2.1 2005/08/10 16:38:44 gap Exp $";


#T add rings of integers in abelian number fields!
#T (NumberRing, IsIntegralBasis, NormalBasis)

#############################################################################
##
##  Abelian Number Fields
#1
##  An *abelian number field* is a field in characteristic zero
##  that is a finite dimensional normal extension of its prime field
##  such that the Galois group is abelian.
##  In {\GAP}, one implementation of abelian number fields is given by fields
##  of cyclotomic numbers (see Chapter~"Cyclotomic Numbers").
##  Note that abelian number fields can also be constructed with
##  the more general `AlgebraicExtension' (see~"AlgebraicExtension"),
##  a discussion of advantages and disadvantages can be found
##  in~"Internally Represented Cyclotomics".
##  The functions described in this chapter have been developed for fields
##  whose elements are in the filter `IsCyclotomic' (see~"IsCyclotomic"),
##  they may or may not work well for abelian number fields consisting of
##  other kinds of elements.
##
##  Throughout this chapter, $\Q_n$ will denote the cyclotomic field
##  generated by the field $\Q$ of rationals together with $n$-th roots of
##  unity.
##
##  In~"Construction of Abelian Number Fields", constructors for abelian
##  number fields are described,
##  "Operations for Abelian Number Fields" introduces operations for abelian
##  number fields,
##  "Integral Bases of Abelian Number Fields" deals with the vector space
##  structure of abelian number fields, and
##  "Galois Groups of Abelian Number Fields" describes field automorphisms
##  of abelian number fields,
##  % section about Gaussians here?
##


#############################################################################
##
#P  IsNumberField( <F> )
##
##  \index{number field}
##  returns `true' if the field <F> is a finite dimensional extension
##  of a prime field in characteristic zero, and `false' otherwise.
##
DeclareProperty( "IsNumberField", IsField );

InstallSubsetMaintenance( IsNumberField,
    IsField and IsNumberField, IsField );

InstallIsomorphismMaintenance( IsNumberField,
    IsField and IsNumberField, IsField );


#############################################################################
##
#P  IsAbelianNumberField( <F> )
##
##  \index{abelian number field}
##  returns `true' if the field <F> is a number field (see~"IsNumberField")
##  that is a Galois extension of the prime field, with abelian Galois group
##  (see~"GaloisGroup!of field").
##
DeclareProperty( "IsAbelianNumberField", IsField );

InstallTrueMethod( IsNumberField, IsAbelianNumberField );

InstallSubsetMaintenance( IsAbelianNumberField,
    IsField and IsAbelianNumberField, IsField );

InstallIsomorphismMaintenance( IsAbelianNumberField,
    IsField and IsAbelianNumberField, IsField );


#############################################################################
##
#m  Conductor( <F> )
##
##  The attribute is defined in `cyclotom.g'.
##
InstallIsomorphismMaintenance( Conductor,
    IsField and IsAbelianNumberField, IsField );


#############################################################################
##
#M  IsFieldControlledByGaloisGroup( <cycfield> )
##
##  For finite fields and abelian number fields
##  (independent of the representation of their elements),
##  we know the Galois group and have a method for `Conjugates' that does
##  not use `MinimalPolynomial'.
##
InstallTrueMethod( IsFieldControlledByGaloisGroup,
    IsField and IsAbelianNumberField );


#############################################################################
##
#P  IsCyclotomicField( <F> )
##
##  returns `true' if the field <F> is a *cyclotomic field*, i.e.,
##  an abelian number field (see~"IsAbelianNumberField")
##  that can be generated by roots of unity.
##
DeclareProperty( "IsCyclotomicField", IsField );

InstallTrueMethod( IsAbelianNumberField, IsCyclotomicField );

InstallIsomorphismMaintenance( IsCyclotomicField,
    IsField and IsCyclotomicField, IsField );


#############################################################################
##
#A  GaloisStabilizer( <F> )
##
##  Let <F> be an abelian number field (see~"IsAbelianNumberField")
##  with conductor $n$, say.
##  (This means that the $n$-th cyclotomic field is the smallest cyclotomic
##  field containing <F>, see~"Conductor".)
##  `GaloisStabilizer' returns the set of all those integers $k$ in the range
##  from $1$ to $n$ such that the field automorphism induced by raising
##  $n$-th roots of unity to the $k$-th power acts trivially on <F>.
##
DeclareAttribute( "GaloisStabilizer", IsAbelianNumberField );

InstallIsomorphismMaintenance( GaloisStabilizer,
    IsField and IsAbelianNumberField, IsField );


#############################################################################
##
#V  Rationals . . . . . . . . . . . . . . . . . . . . . .  field of rationals
#P  IsRationals( <obj> )
##
##  `Rationals' is the field $\Q$ of rational integers,
##  as a set of cyclotomic numbers,
##  see Chapter~"Cyclotomic Numbers" for basic operations,
##  Functions for the field `Rationals' can be found in the
##  chapters~"Fields and Division Rings" and~"Abelian Number Fields".
##
##  `IsRationals' returns `true' for a prime field that consists of
##  cyclotomic numbers --for example the {\GAP} object `Rationals'--
##  and `false' for all other {\GAP} objects.
##
DeclareGlobalVariable( "Rationals", "field of rationals" );

DeclareSynonym( "IsRationals",
    IsCyclotomicCollection and IsField and IsPrimeField );

InstallTrueMethod( IsCyclotomicField, IsRationals );


#############################################################################
##
#V  GaussianRationals . . . . . . . . . . . . . . field of Gaussian rationals
#C  IsGaussianRationals( <obj> )
##
##  `GaussianRationals' is the field $\Q_4 = \Q(\sqrt{-1})$
##  of Gaussian rationals, as a set of cyclotomic numbers,
##  see Chapter~"Cyclotomic Numbers" for basic operations.
##  This field can also be obtained as `CF(4)' (see~"CyclotomicField").
##
##  The filter `IsGaussianRationals' returns `true' for the {\GAP} object
##  `GaussianRationals', and `false' for all other {\GAP} objects.
##
##  (For details about the field of rationals, see Chapter~"Rationals".)
##
DeclareGlobalVariable( "GaussianRationals",
    "field of Gaussian rationals (identical with CF(4))" );

DeclareCategory( "IsGaussianRationals", IsCyclotomicCollection and IsField );
#T better?


#############################################################################
##
#V  CYCLOTOMIC_FIELDS
##
##  At position <n>, the <n>-th cyclotomic field is stored.
##
DeclareGlobalVariable( "CYCLOTOMIC_FIELDS",
    "list, CYCLOTOMIC_FIELDS[n] = CF(n) if bound" );

InstallFlushableValue( CYCLOTOMIC_FIELDS,
    [ Rationals,,, GaussianRationals ] );


#############################################################################
##
#F  CyclotomicField( <n> )  . . . . . . .  create the <n>-th cyclotomic field
#F  CyclotomicField( <gens> )
#F  CyclotomicField( <subfield>, <n> )
#F  CyclotomicField( <subfield>, <gens> )
##
##  The first version creates the <n>-th cyclotomic field $\Q_n$.
##  The second version creates the smallest cyclotomic field containing the
##  elements in the list <gens>.
##  In both cases the field can be generated as an extension of a designated
##  subfield <subfield> (cf.~"Integral Bases of Abelian Number Fields").
##
##  \indextt{CF}
##  `CyclotomicField' can be abbreviated to `CF',
##  this form is used also when {\GAP} prints cyclotomic fields.
##
##  Fields constructed with the one argument version of `CF' are stored in
##  the global list `CYCLOTOMIC_FIELDS',
##  so repeated calls of `CF' just fetch these field objects after they have
##  been created once.
#T  The cache can be flushed by ...
##
DeclareGlobalFunction( "CyclotomicField" );

DeclareSynonym( "CF", CyclotomicField );


#############################################################################
##
#V  ABELIAN_NUMBER_FIELDS
##
##  At position <n>, those fields with conductor <n> are stored that are not
##  cyclotomic fields.
##  The list for cyclotomic fields is `CYCLOTOMIC_FIELDS'.
##
DeclareGlobalVariable( "ABELIAN_NUMBER_FIELDS",
    "list of lists, at position [1][n] stabilizers, at [2][n] the fields" );
InstallFlushableValue( ABELIAN_NUMBER_FIELDS, [ [], [] ] );


#############################################################################
##
#F  AbelianNumberField( <n>, <stab> ) . . . .  create an abelian number field
##
##  For a positive integer <n> and a list <stab> of prime residues modulo
##  <n>, `AbelianNumberField' returns the fixed field of the group described
##  by <stab> (cf.~"GaloisStabilizer"), in the <n>-th cyclotomic field.
##  `AbelianNumberField' is mainly thought for internal use and for printing
##  fields in a standard way;
##  `Field' (see~"Field", cf.~also~"Operations for Abelian Number Fields")
##  is probably more suitable if one knows generators of the field in
##  question.
##
##  \indextt{NF}
##  `AbelianNumberField' can be abbreviated to `NF',
##  this form is used also when {\GAP} prints abelian number fields.
##
##  Fields constructed with `NF' are stored in the global list
##  `ABELIAN_NUMBER_FIELDS',
##  so repeated calls of `NF' just fetch these field objects after they have
##  been created once.
#T  The cache can be flushed by ...
##
DeclareGlobalFunction( "AbelianNumberField" );

DeclareSynonym( "NF", AbelianNumberField );
DeclareSynonym( "NumberField", AbelianNumberField );


#############################################################################
#2
##  Each abelian number field is naturally a vector space over $\Q$.
##  Moreover, if the abelian number field $F$ contains the $n$-th cyclotomic
##  field $\Q_n$ then $F$ is a vector space over $\Q_n$.
##  In {\GAP}, each field object represents a vector space object over a
##  certain subfield $S$, which depends on the way $F$ was constructed.
##  The subfield $S$ can be accessed as the value of the attribute
##  `LeftActingDomain' (see~"LeftActingDomain").
##
##  The return values of `NF' (see~"AbelianNumberField") and of the one
##  argument versions of `CF' (see~"CyclotomicField") represent vector spaces
##  over $\Q$,
##  and the return values of the two argument version of `CF' represent
##  vector spaces over the field that is given as the first argument.
##  For an abelian number field <F> and a subfield <S> of <F>,
##  a {\GAP} object representing <F> as a vector space over <S> can be
##  constructed using `AsField' (see~"AsField").
##
##  \index{cyclotomic fields!CanonicalBasis}
##  Let <F> be the cyclotomic field $\Q_n$, represented as a vector space
##  over the subfield <S>.
##  If <S> is the cyclotomic field $\Q_m$, with $m$ a divisor of $n$,
##  then `CanonicalBasis( <F> )' returns the Zumbroich basis of <F> relative
##  to <S>, which consists of the roots of unity $`E(<n>)'^i$ where <i> is
##  an element of the list `ZumbroichBase( <n>, <m> )' (see~"ZumbroichBase").
##  If <S> is an abelian number field that is not a cyclotomic field
##  then `CanonicalBasis( <F> )' returns a normal <S>-basis of <F>, i.e.,
##  a basis that is closed under the field automorphisms of <F>.
##
##  \index{abelian number fields!CanonicalBasis}
##  Let <F> be the abelian number field `NF( <n>, <stab> )', with conductor
##  <n>, that is itself not a cyclotomic field,
##  represented as a vector space over the subfield <S>.
##  If <S> is the cyclotomic field $\Q_m$, with $m$ a divisor of $n$,
##  then `CanonicalBasis( <F> )' returns the Lenstra basis of <F> relative
##  to <S> that consists of the sums of roots of unity described by
##  `LenstraBase( <n>, <stab>, <stab>, <m> )' (see~"LenstraBase").
##  If <S> is an abelian number field that is not a cyclotomic field
##  then `CanonicalBasis( <F> )' returns a normal <S>-basis of <F>.
##


#############################################################################
##
#F  ZumbroichBase( <n>, <m> )
##
##  Let <n> and <m> be positive integers, such that <m> divides <n>.
##  `ZumbroichBase' returns the set of exponents <i> for which `E(<n>)^<i>'
##  belongs to the (generalized) Zumbroich basis of the cyclotomic field
##  $\Q_n$, viewed as a vector space over $\Q_m$.
##
##  This basis is defined as follows.
##  Let $P$ denote the set of prime divisors of <n>,
##  $<n> = \prod_{p\in P} p^{\nu_p}$, and
##  $<m> = \prod_{p\in P} p^{\mu_p}$ with $\mu_p \leq \nu_p$.
##  Let $e_n = `E(<n>)'$,
##  and $\{ e_{n_1}^j\}_{j\in J} \otimes \{ e_{n_2}^k\}_{k\in K} =
##  \{ e_{n_1}^j \cdot e_{n_2}^k\}_{j\in J, k\in K}$.
##
##  Then the basis is
##  $$
##  B_{n,m} = \bigotimes_{p\in P}
##    \bigotimes_{k=\mu_p}^{\nu_p-1} \{ e_{p^{k+1}}^j\}_{j\in J_{k,p}}
##    {\rm\ \ where\ \ }
##  J_{k,p} = \left\{
##     \matrix{ \{ 0 \} & ; & k=0, p=2 \cr
##              \{ 0, 1 \} & ; & k > 0, p=2 \cr
##              \{ 1, \ldots, p-1 \} & ; & k = 0, p\not= 2 \cr
##              \{ -\frac{p-1}{2}, \ldots, \frac{p-1}{2} \} & ; &
##                               k > 0, p\not= 2 \cr
##  }
##  \right.
##  $$
##
##  $B_{n,1}$ is equal to the basis of $\Q_n$ over the rationals which is
##  introduced in~\cite{Zum89}.
##  Also the conversion of arbitrary sums of roots of unity into its
##  basis representation, and the reduction to the minimal cyclotomic field
##  are described in this thesis.
##  (Note that the notation here is slightly different from that there.)
##
##  $B_{n,m}$ consists of roots of unity, it is an integral basis
##  (that is, exactly the integral elements in $\Q_n$ have integral
##  coefficients w.r.t.~$B_{n,m}$, cf.~"IsIntegralCyclotomic"),
##  it is a normal basis for squarefree $n$
##  and closed under complex conjugation for odd $n$.
##
##  *Note:*
##  For $<n> \equiv 2 \pmod 4$, we have
##  `ZumbroichBase(<n>, 1) = 2 * ZumbroichBase(<n>/2, 1)' and
##  `List( ZumbroichBase(<n>, 1), x -> E(<n>)^x ) =
##   List( ZumbroichBase(<n>/2, 1), x -> E(<n>/2)^x )'.
##
DeclareGlobalFunction( "ZumbroichBase" );


#############################################################################
##
#F  LenstraBase( <n>, <stabilizer>, <super>, <m> )
##
##  Let <n> and <m> be positive integers, such that <m> divides <n>,
##  <stabilizer> be a list of prime residues modulo <n>, which describes
##  a subfield of the <n>-th cyclotomic field (see~"GaloisStabilizer"),
##  and <super> be a list representing a supergroup of the group given by
##  <stabilizer>.
##
##  `LenstraBase' returns a list $[ b_1, b_2, \ldots, b_k ]$ of lists,
##  each $b_i$ consisting of integers such that the elements
##  $\sum_{j\in b_i} `E(n)'^j$ form a basis of the abelian number field
##  `NF( <n>, <stabilizer> )', as a vector space over the <m>-th
##  cyclotomic field (see~"AbelianNumberField").
##
##  This basis is an integral basis,
##  that is, exactly the integral elements in `NF( <n>, <stabilizer> )'
##  have integral coefficients.
##  (For details about this basis, see~\cite{Bre97}.)
##
##  If possible then the result is chosen such that the group described by
##  <super> acts on it, consistently with the action of <stabilizer>,
##  i.e., each orbit of <super> is a union of orbits of <stabilizer>.
##  (A usual case is `<super> = <stabilizer>', so there is no additional
##  condition.
##
##  *Note:*
##  The $b_i$ are in general not sets, since for `<stabilizer> = <super>',
##  the first entry is always an element of `ZumbroichBase( <n>, <m> )';
##  this property is used by `NF' (see~"AbelianNumberField")
##  and `Coefficients' (see~"Integral Bases of Abelian Number Fields").
##
##  <stabilizer> must not contain the stabilizer of a proper
##  cyclotomic subfield of the <n>-th cyclotomic field,
##  i.e., the result must describe a basis for a field with conductor <n>.
##
DeclareGlobalFunction( "LenstraBase" );


#############################################################################
##
#V  Cyclotomics . . . . . . . . . . . . . . . . . . domain of all cyclotomics
##
##  is the domain of all cyclotomics.
##
DeclareGlobalVariable( "Cyclotomics", "domain of all cyclotomics" );


#############################################################################
##
#F  ANFAutomorphism( <F>, <k> )  . .  automorphism of an abelian number field
##
##  Let <F> be an abelian number field and <k> an integer that is coprime to
##  the conductor (see~"Conductor") of <F>.
##  Then `ANFAutomorphism' returns the automorphism of <F> that is defined as
##  the linear extension of the map that raises each root of unity in <F>
##  to its <k>-th power.
##
DeclareGlobalFunction( "ANFAutomorphism" );


#############################################################################
##
#A  ExponentOfPowering( <map> )
##
##  For a mapping <map> that raises each element of its preimage to the same
##  positive power, `ExponentOfPowering' returns the smallest positive number
##  $n$ with this property.
##
##  Examples of such mappings are Frobenius automorphisms
##  (see~"FrobeniusAutomorphism").
##
##  The action of a Galois automorphism of an abelian number field is given
##  by the $\Q$-linear extension of raising each root of unity to the same
##  power $n$, see~"ANFAutomorphism".
##  For such a field automorphism, `ExponentOfPowering' returns $n$.
##
DeclareAttribute( "ExponentOfPowering", IsMapping );


#############################################################################
##
#E