freeze;
 
/****-*-magma-* EXPORT DATE: 2004-03-08 ************************************
                                                                            
                   HECKE:  Modular Symbols in Magma                          
                                                                            
   Author: First version by David Kohel;
           Greatly re-written and extended by William A. Stein

   FILE: dirichlet.m (Dirichlet characters)                

   This is a change log.  For further details see the bottom of this file.
                 
   2004-10-05: Fixed intrinsic 'eq' (G::GrpDrch,H::GrpDrch) -> BoolElt
   by comparing actual base rings instead of just their types, which makes
   more sense.

   08/15/03: (WAS) Fixed bad error messages when coercing (stack traces when
             there should be stack traces -- see end of this file.)

   08/14/03: (WAS) Add FullDirichletGroup intrinsic, as requested by Kevin Buzzard.

   02/23/03: (WAS) Added proper error checking to coercision of sequence 
             into Dirichlet Group element

   02/15/03: (WAS) Fixed some bugs with BaseExtend when the root of unity
             suddenly gets smaller.  Hopefully this makes sense.

   02/06/03: (WAS) Fixed some bugs (i.e., spurious require statement, missing coercision) 
             that appeared when user tries to create Dirichlet characters over number fields.

   11/17/02: (WAS) Fixed two bugs that Allan Steel found.  Bug 1 involved confusing a character
             and the character modulo its conductor which induces it.  The second was a special
             case in which the universe of the empty sequence wasn't defined. 
             

   10/31/02: (WAS) **MASSIVE CHANGES**  Totally changed the internal representation, which
             meant rewriting almost every command.

   10/31/02: I'm sick of RCS.  I'm not using it anymore.

   $Header: /home/was/magma/packages/ModSym/code/RCS/dirichlet.m,v 1.17 2002/09/27 19:36:16 was Exp was $ 
   $Log: dirichlet.m,v $
   Revision 1.17  2002/09/27 19:36:16  was
   finished fixing my fix.

   Revision 1.16  2002/09/27 19:35:12  was
   Replaced David's "elementary bug fix" by
         when FldCyc :
            return R!(CyclotomicField(LCM(2,r)).1), LCM(2,r);

   Revision 1.15  2002/09/26 19:35:27  was
   Improved comment in BaseExtend and fixed bug in equality test (before it didn't
   test that roots of unity are equal.)

   Revision 1.14  2002/05/06 05:10:57  was
   Fixed a problem with equality testing that appeared because, I guess,
   of a change in how abelian groups are handled by Magma V2.9.

   Revision 1.13  2001/11/20 18:02:54  was
   Speed up GaloisConjugacyRepresentatives

   Revision 1.12  2001/11/20 17:48:37  was
   nothing!

   Revision 1.11  2001/09/03 23:24:35  was
   nothing.

   Revision 1.10  2001/08/07 03:13:29  was
   Changed a require statement in DirichletGroup.

   Revision 1.9  2001/05/22 07:49:09  was
   Added AssociatedPrimitiveCharacter.

   Revision 1.8  2001/05/22 05:48:45  was
   Added IsPrimitive.

   Revision 1.7  2001/05/21 10:30:43  was
   *** empty log message ***

   Revision 1.6  2001/05/21 10:01:12  was
   Added intrinsic MinimalBaseRingCharacter(eps::GrpDrchElt) -> GrpDrchElt

   Revision 1.5  2001/05/18 04:40:52  was
   Made ValueList an intrinsic.

   Revision 1.4  2001/05/17 22:21:55  was
   Added
     GaloisConjugacyRepresentatives(S::[GrpDrchElt]) -> SeqEnum
   and
     AbelianGroup(G::GrpDrch) -> GrpAb, Map
   -- William

   Revision 1.3  2001/05/16 03:16:09  was
   Slight change to comment of '*'.

   Revision 1.2  2001/04/29 02:47:27  was
   Default Kronecker character is over the integers now.

   Revision 1.1  2001/04/20 04:46:56  was
   Initial revision

   Revision 1.15  2001/03/27 07:27:40  was
   Added a "KroneckerCharacter" intrinsic, which gives the popular Kronecker character as a
   DirichletGroup element.

   Revision 1.14  2001/02/24 04:35:32  was
   Strengthened error checking.

   Revision 1.13  2001/02/05 14:50:42  was
   Removed a require "Type(R) in " statement, so that my cusp forms with dirichlet
   character over Zp code would work.

   Revision 1.12  2001/02/05 13:58:12  was
   Fixed typo in a comment.

   Revision 1.11  2001/02/04 16:42:15  was
   Removed the Type(R) requirement from BaseExtend.

   Revision 1.10  2001/02/04 15:42:57  was
   Added uses of "ReductionMap".

   Revision 1.9  2001/02/04 15:18:33  was
   Added

      intrinsic DistinguishedRoot(G::GrpDrch) -> RngElt, RngIntElt

   Revision 1.8  2001/02/03 19:49:46  was
   Deleted a commented-out require statement.

   Revision 1.7  2000/09/01 17:08:43  was
   William,

   Here are corrections to a couple of elementary bugs in
   dirichlet.m.  First the universe needs to be defined in
   this line to avoid empty sequence bugs.

      G`Orders   := [ Integers() | GCD(r,Order(A.i)) : i in [1..Ngens(A)]];

   and the even-odd orders have to be differentiated for
   cyclotomic fields.

         when FldCyc :
            r := CyclotomicOrder(R);
            if r mod 2 eq 0 then
               return R.1, r;
            else
               return -R.1, 2*r;
            end if;

   --David

   Revision 1.6  2000/06/22 00:43:44  was
   Added BaseExtend for maps.

   Revision 1.5  2000/06/14 19:43:51  was
   Allow general DirichletGroup in general constructor; also, fixed a bug in the error message for
   DirichletGroup(m,R).

   Revision 1.4  2000/06/03 04:57:31  was
   commented out IsOdd

   Revision 1.3  2000/05/25 21:54:31  was
   fixed "IsEven" "IsOdd" comments

   Revision 1.2  2000/05/25 21:49:15  was
   added comment.

   Revision 1.1  2000/05/02 08:00:37  was
   Initial revision

                                                                            
 ***************************************************************************/


import "arith.m": ReductionMap;

forward DirichletCharacterFromValuesOnUnitGenerators,
        initGrpDrchElt ;

////////////////////////////////////////////////////////////////
//                                                            //
//                  Attribute declarations                    //
//                                                            // 
////////////////////////////////////////////////////////////////


declare attributes GrpDrch:  // Call this GrpDrch object G.
   BaseRing,      // The base ring R over which the characters are defined
   RootOf1,       // A root of unity z in R^*
   PowersOfRoot,  // [z,z^2,z^3,...,z^r], where z has order r.
   OrderOfRoot,   // r = Order of z, where z is RootOf1.
   Modulus,       // The modulus N
   Exponent,      // Exponent of the group (Z/N)^*
   UGroup,        // A group such that 
   UnitsMap,      //    UnitsMap:  A -> (Z/N)^* is an isomorphism
   Elements,      // Sequence of all elements of G.
   OrdersUGroup,  // The orders of the standard generators of (Z/N)^*
   OrdersGens,    // Orders of the generators of G.
   Images,        // Images of the chosen generators of G; these are powers of z.
   Labels,        // Labels of the standard generators
   AbGrp,         // An abelian group isomorphic to this Dirichlet group,
                  // so AbGrp is the r-torsion in UGroup.
   AbGrpMap;      // Invertible homomorphism AbGrp ----> G.

declare attributes GrpDrchElt: 
   Parent,
   Conductor,     // Smallest M such that (Z/N)^* --> R^* factors through (Z/M)^*.
   Element,       // Corresponding element of (Z/N)^* (see comments far below),
                  // which represents this Dirichlet group element.
   ValueList;     // [Evaluate(eps,i) : i in [1..m]];   (useful sometimes for efficiency).



////////////////////////////////////////////////////////////////
//                   Creation functions                       // 
////////////////////////////////////////////////////////////////

function CyclotomicGenerator(R)
   case Category(R) :
      when RngInt :
         return R!-1, 2;
      when FldRat :
         return R!-1, 2;
      when FldCyc :
         r := CyclotomicOrder(R);
         return R!(CyclotomicField(LCM(2,r)).1), LCM(2,r);
      when FldFin :
         r := #R - 1;
         G, f := UnitGroup(R);
         z := f(G.1);
         return z,r;
      when FldQuad :
         case Discriminant(R):
            when -4:
               r := 4;
               z := R.1;
            when -3:
               r := 6;
               z := (1+R.1)/2;
            else:
               r := 2;
               z := R!-1;
         end case;         
         return z,r;
      when FldNum :
         G, f := TorsionUnitGroup(R);
         z := R!f(G.1);
         return z,Order(G);
      else
         if Characteristic(R) ne 2 then
            return R!-1,2;
         else
            return R!1,1;
         end if;
   end case;
end function;


intrinsic ValueList(eps::GrpDrchElt) -> SeqEnum
{[The values [eps(1), eps(2), ..., eps(N)].}
   if not assigned eps`ValueList then
      eps`ValueList := [Evaluate(eps,i) : i in [1..Modulus(eps)]];
   end if;
   return eps`ValueList;
end intrinsic;


intrinsic DirichletGroup(m::RngIntElt) -> GrpDrch
   {The group of Dirichlet characters mod m with image 
    in RationalField(). This is a group of exponent at most 2.}
   requirege m,1;
   return DirichletGroup(m,RationalField());
end intrinsic;


intrinsic DirichletGroup(m::RngIntElt,R::Rng) -> GrpDrch
   {The group of Dirichlet characters mod m with image in the ring R.}
   require Type(R) in {RngInt, FldRat, FldCyc, FldFin, FldQuad, FldNum} :
       "Argument 2 must be of type RngInt, FldRat, FldCyc, FldFin, FldQuad, or FldNum.";
   requirege m,1;

   z, r := CyclotomicGenerator(R);
   return DirichletGroup(m,R,z,r);
end intrinsic


intrinsic DirichletGroup(m::RngIntElt,R::Rng,z::RngElt,r::RngIntElt) -> GrpDrch
{The group of Dirichlet characters mod m with image in the order-r cyclic
 subgroup of R generated by the root of unity z.}
   // not a thorough check, but fast enough...
   require m ge 1 : "Argument 1 must be at least 1."; 
   require R cmpeq Parent(z) and z in R : "Argument 3 must lie in argument 2.";
   if not (Type(R) in {FldPad, FldPr}) then
      require z^r eq R!1 : "Argument 3 must have order equal to argument 4.";  
   end if;

   G          := HackobjCreateRaw(GrpDrch);
   G`Modulus  := m;
   G`BaseRing := R;
   G`UGroup, G`UnitsMap := UnitGroup(quo< Integers() | m>);
   G`RootOf1  := z;
   G`OrderOfRoot := r;
   G`PowersOfRoot := [z^i : i in [1..r]];
   G`Exponent := Exponent(G`UGroup);
   G`OrdersUGroup := [ Order(G`UnitsMap(x)) : x in [G`UGroup.i : i in [1..Ngens(G`UGroup)]]];
   G`OrdersGens := [Integers()| GCD(r,m) : m in G`OrdersUGroup];
   G`Labels   := ["$." cat IntegerToString(i) : i in [1..#G`OrdersUGroup] ];
   return G;
end intrinsic;

intrinsic FullDirichletGroup(N::RngIntElt) -> GrpDrch
{The group of Dirichlet characters modulo N with values in Q(zeta_m), where
m is the exponent of (Z/N)^*.}
   requirege N, 1;
   mu := Exponent(UnitGroup(quo< Integers() | N>));
   if mu gt 2 then
      return DirichletGroup(N,CyclotomicField(mu));
   else
      return DirichletGroup(N);   
   end if;
end intrinsic;




intrinsic AbelianGroup(G::GrpDrch) -> GrpAb, Map
{}
   if not assigned G`AbGrp then
      r := G`OrderOfRoot;
      I := Invariants(G`UGroup);
      J := [GCD(r,i) : i in I];
      G`AbGrp := AbelianGroup(J);
      function f(x) 
         e := Eltseq(x);
         e := [Integers()|e[i]*(I[i] / GCD(r,I[i])) : i in [1..#I]];
         g := G`UGroup!e;
         return initGrpDrchElt(G, g);
      end function;
      function g(x)
         e := Eltseq(x); 
         e := [Integers()| e[i] / (I[i] / GCD(r,I[i])) : i in [1..#I]];
         return G`AbGrp!e;
      end function;
      G`AbGrpMap := hom<G`AbGrp -> G | x :-> f(x), y :-> g(y)>;
   end if;
   return G`AbGrp, G`AbGrpMap;
end intrinsic;


intrinsic Elements(G::GrpDrch) -> SeqEnum
   {The Dirichlet characters in G.}
   if not assigned G`Elements then
      chars := [ G!1 ];
      for i in [1..Ngens(G)] do
         chrsi := [ G.i^j : j in [0..Order(G.i)-1] ];
         chars := [ x*y : x in chars, y in chrsi ];
      end for;
      G`Elements := chars;
   end if;
   return G`Elements;
end intrinsic;


intrinsic Random(G::GrpDrch) -> GrpDrchElt
   {A random element of G.}
   return Random(Elements(G));
end intrinsic;


////////////////////////////////////////////////////////////////
//                                                            //
//                     Coercions                              //
//                                                            // 
////////////////////////////////////////////////////////////////


/* Elements of GrpDrch are represented as elements of (Z/N)^*,
   since there is an isomorphism between Hom((Z/N)^*, C^*) and (Z/N)^*.
   Let r be the order of the distinguished root z of unity.   We
   are interested in the subgroup of Hom((Z/N)^*, C^*) of elements
   of order dividing r.  This corresponds to the subgroup of (Z/N)^* of
   elements of order dividing r.   Suppose x in (Z/N)^* has order 
   dividing r.   Write x = prod g_i^m_i, where the g_i are fixed (once
   and for all) generators for (Z/N)^*.  Then x corresponds to the
   homomorphism which sends g_i to (z^(r/order(g_i)))^m_i.  In particular,
   the element g_i of (Z/N)^* corresponds to the homomorphism that sends
   g_j to 1 for all i=/=j and sends g_i to z^(r/order(g_i)).
 */

function initGrpDrchElt(G,g)
  x := HackobjCreateRaw(GrpDrchElt);  
  x`Parent := G;
  x`Element := g;
  return x;
end function;


intrinsic HackobjCoerceGrpDrch(G::GrpDrch,x::.) -> BoolElt, GrpDrchElt
   {}
   if Type(x) eq GrpDrchElt then
      if x`Parent eq G then
         return true, x;
      elif Modulus(G) mod Conductor(x) eq 0 then
         s := [];
         for g in UnitGenerators(G) do // We have to do this since GCD(g,Modulus(x)) > 1 then Eval(x,g)=0.
                                       // which is wrong. remember, we are trying to evaluate the character
                                       // modulo Conductor(x) that *induces* x, not x itself.
            h := g;
            while GCD(h,Modulus(x)) ne 1 do
               h +:= Conductor(x);
            end while;
            Append(~s, Evaluate(x,h));
         end for;
         t,msg,eps := DirichletCharacterFromValuesOnUnitGenerators(G,s);
         require t : msg;
         return true, eps;
      end if;
   elif Type(x) eq RngIntElt and x eq 1 then
      return true, initGrpDrchElt(G,G`UGroup!0); 
   elif Type(x) eq SeqEnum and (#x eq 0 or Type(Universe(x)) eq RngInt) and #x eq Ngens(G) then
      for i in [1..Ngens(G)] do
         m := G`OrdersUGroup[i];
         g := GCD(G`OrderOfRoot,m);
         if g*x[i] mod m ne 0 then
            return false, "Invalid coercion: The sequence does not define a valid Dirichlet character (over the given base ring).";
         end if;
      end for;
      return true, initGrpDrchElt(G,G`UGroup!x); 
   end if;
   return false, "Invalid coercion.";
end intrinsic;


intrinsic AssignNames(~G::GrpDrch, S::[MonStgElt])
{Assign names to the generators of G.}
   require #S eq Ngens(G) : "Argument 2 must have length", Ngens(G);
   G`Labels := S;
end intrinsic;

intrinsic Name(G::GrpDrch,i::RngIntElt) -> GrpDrchElt
   {The ith generator.}
   require i ge 1 : "Argument 2 must be positive";
   require i le Ngens(G) : "Argument 2 can be at most", Ngens(G);
   return G.i;
end intrinsic;


intrinsic '.'(G::GrpDrch,i::RngIntElt) -> GrpDrchElt
   {The ith generator.}
   require i ge 1 : "Argument 2 must be positive";
   require i le Ngens(G) :  "Argument 2 can be at most", Ngens(G);
   S := [ 0 : i in [1..Ngens(G)] ]; 
   m := G`OrdersUGroup[i];
   r := G`OrderOfRoot;
   S[i] := Integers()!(m/GCD(r,m));
   return G!S;
end intrinsic;


////////////////////////////////////////////////////////////////
//                     Printing                               //
////////////////////////////////////////////////////////////////

intrinsic HackobjPrintGrpDrch(X::GrpDrch, level::MonStgElt)
   {}
   printf "Group of Dirichlet characters of modulus %o over %o", 
          X`Modulus, BaseRing(X);
end intrinsic;


intrinsic HackobjPrintGrpDrchElt(x::GrpDrchElt, level::MonStgElt)
   {}
   G := Parent(x);
   r := G`OrderOfRoot;
   S := Eltseq(x`Element);
   Star := "";
   if &and[ x eq 0 : x in S ] then
      printf IntegerToString(1);
   else 
      for i in [1..Ngens(G)] do
         a := S[i];
         m := G`OrdersUGroup[i];
         w := (GCD(r,m)*a/m);
         e := Integers()!w mod G`OrdersGens[i];
         if e eq 1 then 
	    printf Star cat G`Labels[i];
            Star := "*";
         elif e ne 0 then
            printf Star cat G`Labels[i] cat 
                   "^" cat IntegerToString(e); 
            Star := "*";
         end if; 
      end for;
   end if;
end intrinsic;



////////////////////////////////////////////////////////////////
//                                                            //
//            Membership and equality testing                 //
//                                                            //
////////////////////////////////////////////////////////////////

intrinsic HackobjInGrpDrch(x::., X::GrpDrch) -> BoolElt
   {Returns true if x is in X.}
   if Type(x) eq GrpDrchElt then
      return x`Parent eq X;
   end if;
   return false;
end intrinsic;


intrinsic HackobjParentGrpDrchElt(x::GrpDrchElt) -> GrpDrch
   {}
   return x`Parent;
end intrinsic;


intrinsic 'eq' (G::GrpDrch,H::GrpDrch) -> BoolElt
   {}
   return G`Modulus eq H`Modulus and G`BaseRing cmpeq H`BaseRing
          and G`RootOf1 cmpeq H`RootOf1;
end intrinsic;

intrinsic 'eq' (x::GrpDrchElt,y::GrpDrchElt) -> BoolElt
   {}
   return Parent(x)`Modulus eq Parent(y)`Modulus and
      ValuesOnUnitGenerators(x) cmpeq ValuesOnUnitGenerators(y);
end intrinsic;


////////////////////////////////////////////////////////////////
//                                                            //
//                Attribute Access Functions                  //
//                                                            //
////////////////////////////////////////////////////////////////

intrinsic BaseRing(G::GrpDrch) -> Rng
   {The base ring of G.}
   return G`BaseRing;
end intrinsic;


intrinsic BaseRing(x::GrpDrchElt) -> Rng
   {The base ring, i.e. the codomain, of x.}
   return x`Parent`BaseRing;
end intrinsic;


intrinsic CoefficientRing(G::GrpDrch) -> Rng
   {The base ring of G.}
   return G`BaseRing;
end intrinsic;


intrinsic Domain(x::GrpDrchElt) -> Rng
   {The integers.}
   return Integers();
end intrinsic;


intrinsic Codomain(x::GrpDrchElt) -> Rng
{The coefficient ring in which x takes values.}
   return Parent(x)`BaseRing;
end intrinsic;


intrinsic Exponent(G::GrpDrch) -> RngIntElt
{The exponent of G.}
   return G`Exponent;
end intrinsic;



intrinsic Order(G::GrpDrch) -> RngIntElt
{The order of G.}
   return &*G`OrdersGens;
end intrinsic;

intrinsic '#'(G::GrpDrch) -> RngIntElt
{The order of G.}
   return Order(G);
end intrinsic;

intrinsic Order(x::GrpDrchElt) -> RngIntElt
{The order of x.}
   return Order(x`Element);
end intrinsic;


intrinsic Generators(G::GrpDrch) -> SeqEnum
   {Generators for the character group.}
   return [ G.i : i in [1..Ngens(G)] ];
end intrinsic;


intrinsic UnitGenerators(G::GrpDrch) -> SeqEnum
{The ordered sequence of integers that reduce to 
 "canonical" generators of (Z/m)^*, where m is the modulus of G.}
   return [Integers()| G`UnitsMap(G`UGroup.i) : 
                   i in [1..Ngens(G`UGroup)]] ;
end intrinsic;


intrinsic Ngens(G::GrpDrch) -> RngIntElt
   {The number of generators of G.}
   return #G`Labels;
end intrinsic;


intrinsic NumberOfGenerators(G::GrpDrch) -> RngIntElt
   {The number of generators of G.}
   return #G`Labels;
end intrinsic;


intrinsic Modulus(G::GrpDrch) -> RngIntElt
   {The modulus of G.}
   return G`Modulus;
end intrinsic;


intrinsic Conductor(x::GrpDrchElt) -> RngIntElt
   {The conductor of x.} 
   if not assigned x`Conductor then
      if Modulus(x) eq 1 or Order(x) eq 1 then
         x`Conductor := 1;
         return 1;
      end if;
      F := Factorization(Modulus(x));
      if #F gt 1 then
         x`Conductor := 1;
         D := Decomposition(x);
         for d in D do
            x`Conductor *:= Conductor(d);
         end for;
         return x`Conductor;
      end if;
      p := F[1][1];
      // When p is odd, and x =/= 1, the conductor is the smallest p^r such that
      //   Order(x) divides EulerPhi(p^r) = p^(r-1)*(p-1).
      // For a given r, whether or not the above divisiblity holds
      // depends only on the factor of p^(r-1) on the right hand side.
      // Since p-1 is coprime to p, this smallest r such that the
      // divisibility holds equals Valuation(Order(x),p)+1. 
      x`Conductor := p^(Valuation(Order(x),p)+1);    
      if p eq 2 and F[1][2] gt 2 and Eltseq(x`Element)[2] ne 0 then
         x`Conductor *:= 2;
      end if;
   end if;
   return x`Conductor;
end intrinsic;


intrinsic Modulus(x::GrpDrchElt) -> RngIntElt
   {The modulus of the parent group of x.}
   return x`Parent`Modulus;
end intrinsic;



////////////////////////////////////////////////////////////////
//         Functionality, arithmetic operations, etc.         //
////////////////////////////////////////////////////////////////

intrinsic IsTrivial(x::GrpDrchElt) -> BoolElt
{True if and only if x has order 1.}
   return &and[ n eq 0 : n in Eltseq(x`Element) ];
end intrinsic;


intrinsic IsEven(x::GrpDrchElt) -> BoolElt
   {True if and only if Evaluate(x,-1) is equal to 1.   Note that the space of modular forms of weight k is zero if x is even and k is odd.}
   return Evaluate(x,-1) eq 1;
end intrinsic;


intrinsic IsPrimitive(x::GrpDrchElt) -> BoolElt
  {}
   return Modulus(x) eq Conductor(x);
end intrinsic;

intrinsic AssociatedPrimitiveCharacter(x::GrpDrchElt) -> GrpDrchElt
  {}
   return Restrict(x,Conductor(x));
end intrinsic;

function Evaluate_helper(x, n_rep)
   assert Type(x) eq GrpDrchElt;
   assert Type(n_rep) eq SeqEnum;
   G     := Parent(x);
   x_rep := Eltseq(x`Element); 
   assert #n_rep eq #x_rep;
   ords  := G`OrdersUGroup;
   r     := G`OrderOfRoot;
   power_of_root := &+[Integers()| n_rep[i]*x_rep[i]*r/ords[i] : i in [1..#n_rep]] mod r;
   if power_of_root eq 0 then
      power_of_root := r;
   end if;
   return G`PowersOfRoot[power_of_root];
end function;

intrinsic Evaluate(x::GrpDrchElt,n::RngIntElt) -> RngElt
{The evaluation of x at n.}
   if GCD(Modulus(x),n) ne 1 then
      return 0;
   end if;
   G     := Parent(x);
   f     := G`UnitsMap;
   ZmodN := Codomain(f);
   n_rep := Eltseq((ZmodN!n)@@f);   // discrete log 
   return Evaluate_helper(x, n_rep);
end intrinsic;


intrinsic Evaluate(x::GrpDrchElt,n::RngIntResElt) -> RngElt
{Evaluation x(n).}
   return Evaluate(x, Integers()!n);
end intrinsic;

intrinsic '@'(n::RngIntElt, x::GrpDrchElt) -> RngElt
{}
   return Evaluate(x,n);
end intrinsic;

intrinsic '@'(n::RngIntResElt, x::GrpDrchElt) -> RngElt
{}
   return Evaluate(x,n);
end intrinsic;

intrinsic '*' (x::GrpDrchElt,y::GrpDrchElt) -> GrpDrchElt
{The product of x and y.  This is a Dirichlet character
of modulus equal to the least common multiple of the moduli of x
and y.  If the parents of x and y are not equal, then the product
lies in a new Dirichlet group.  If the base rings or roots are not 
equal then the base ring has to be cyclotomic.}
   Gx := Parent(x);
   Gy := Parent(y);

   if Gx eq Gy then
      if Parent(x`Element) cmpeq Parent(y`Element) then
         return initGrpDrchElt(Gx,x`Element+y`Element);
      end if;
      xe := Eltseq(x);
      ye := Eltseq(y);
      assert #xe eq #ye;
      return Gx![xe[i] + ye[i] : i in [1..#xe]];
   end if;

   // Construct new parent. 
   N := LCM(Modulus(x), Modulus(y));
   if BaseRing(Gx) cmpeq BaseRing(Gy) and Gx`RootOf1 eq Gy`RootOf1 then
      G := DirichletGroup(N, BaseRing(Gx), Gx`RootOf1, Gx`OrderOfRoot);
   else
      require Type(BaseRing(Gx)) in {FldRat, RngInt, FldCyc} : 
         "The base ring of argument 1 must be the integers, rationals, or cyclotomics.";
      r := LCM(Gx`OrderOfRoot, Gy`OrderOfRoot);
      K := CyclotomicField(r);
      G := DirichletGroup(N, K);
   end if;
   
   vals := [Evaluate(x,g)*Evaluate(y,g) : g in UnitGenerators(G)];
   t,msg,eps := DirichletCharacterFromValuesOnUnitGenerators(G,vals);
   require t : msg;
   return eps;
end intrinsic;

intrinsic '/' (x::GrpDrchElt,y::GrpDrchElt) -> GrpDrchElt
{The quotient of x and y.  This is a Dirichlet character
of modulus equal to the least common multiple of the moduli of x
and y.  The base rings and chosen roots of unity of 
the parents of x and y must be equal.}
   return x * y^(-1);
end intrinsic;

intrinsic '^' (x::GrpDrchElt,n::RngIntElt) -> GrpDrchElt
   {}
   if n eq 1 then 
      return x;
   end if; 
   return initGrpDrchElt(Parent(x),n*x`Element);
end intrinsic;

intrinsic Extend(x::GrpDrchElt, m::RngIntElt) -> GrpDrchElt
   {Extension of x to a Dirichlet character mod m.}
   require m mod Modulus(x) eq 0 : "Argument 2 must be divisible by the modulus of argument 1.";
   G := Parent(x);
   return Extend(x,DirichletGroup(m,BaseRing(G),G`RootOf1,G`OrderOfRoot));
end intrinsic;

intrinsic Extend(x::GrpDrchElt, H::GrpDrch) -> GrpDrchElt
{Extension of x to an element of H.}
   require (Modulus(H) mod Modulus(x)) eq 0: 
          "Modulus of argument 2 must be a multiple of the modulus of argument 1.";
   vals := [Evaluate(x,g) : g in UnitGenerators(H)];
   t,msg,eps := DirichletCharacterFromValuesOnUnitGenerators(H,vals);
   require t : msg;
   return eps;
end intrinsic;


intrinsic Eltseq(x::GrpDrchElt) -> SeqEnum
{}
   return Eltseq(x`Element);
end intrinsic;


intrinsic Decomposition(x::GrpDrchElt) -> SeqEnum
{Decomposition of x as a product of Dirichlet characters 
of prime power modulus.}
   
   G := Parent(x);
   e := Eltseq(x`Element);
   R := BaseRing(G);
   m := Modulus(G);
   r := G`OrderOfRoot;
   s := [m/GCD(r,m) : m in G`OrdersUGroup];
   F := Factorization(m);
   D := [* *];
   i := 1;
   for a in F do
      Gp := DirichletGroup(a[1]^a[2], R, G`RootOf1, G`OrderOfRoot);
      if a[1] ne 2 then 
         xp := Gp.1^(Integers()!(e[i]/s[i]));
         i +:= 1;
      elif a[1] eq 2 then
         if a[2] eq 1 then
            xp := Gp!1;
         else
            pow := Integers()!(e[i]/s[i]);
            xp := Gp.1^pow;
            i +:= 1;
            if a[2] gt 2 then
               pow := Integers()!(e[i]/s[i]);
               xp := xp * Gp.2^(Integers()!pow);
               i +:= 1;
            end if;
         end if;
      end if;
      Append(~D,xp);
   end for;
   return D;
end intrinsic;


intrinsic Restrict(x::GrpDrchElt,m::RngIntElt) -> GrpDrchElt
 {The associated mod-m Dirichlet character. The conductor 
of x must divide m.}
   require (m mod Conductor(x)) eq 0: "Conductor of argument 1 does not divide argument 2.";
   require Modulus(x) mod m eq 0: "Argument 2 must divide the modulus of argument 1.";
   G := Parent(x);
   H := DirichletGroup(m,BaseRing(G),G`RootOf1,G`OrderOfRoot);
   return Restrict(x,H);
end intrinsic;

intrinsic Restrict(x::GrpDrchElt,H::GrpDrch) -> GrpDrchElt
{The associated Dirichlet character in H.}
   require (Modulus(H) mod Conductor(x)) eq 0: 
               "Conductor of first argument must divide modulus of second.";
   require Modulus(x) mod Modulus(H) eq 0: 
               "Modulus of argument 2 must divide the modulus of argument 1.";
   m := Modulus(H);
   n := Modulus(x);
   gens := UnitGenerators(H);   // These generate (Z/m)^*.  There a map (Z/n)^* --> (Z/m)^*
   // Now we lift these to elements of (Z/n)^*.
   for i in [1..#gens] do
      while GCD(n,gens[i]) ne 1 do
         gens[i] +:= m;
      end while;
   end for;
   vals := [Evaluate(x,g) : g in gens];
   t,msg,eps := DirichletCharacterFromValuesOnUnitGenerators(H,vals);
   require t : msg;
   return eps;
end intrinsic;

intrinsic BaseExtend(G::GrpDrch, R::Rng) -> GrpDrch
{Base extension of G to R.}
   require Type(R) in {RngInt, FldRat, FldCyc, FldFin, FldQuad, FldNum} :
       "Argument 1 must be of type RngInt, FldRat, FldCyc, FldFin, FldQuad, or FldNum.";

   return BaseExtend(G, R, R!G`RootOf1);
end intrinsic;

intrinsic BaseExtend(G::GrpDrch, R::Rng, z::RngElt) -> GrpDrch
{Base extension of G to R that identifies the distinguished
root of unity of the base ring of G with z.}

   require z^G`OrderOfRoot eq 1 :
           "Invalid root of unity.  The order of argument 3 must divide the order of DistinguishedRoot(argument 1).";
   // the following might be *really* stupid if the order is 
   // divisible by several primes.
   n := Min([r : r in Divisors(G`OrderOfRoot) | z^r eq 1]);   
   //return DirichletGroup(Modulus(G), R, z, G`OrderOfRoot);  
   return DirichletGroup(Modulus(G), R, z, n);  
end intrinsic;


intrinsic BaseExtend(eps::GrpDrchElt, R::Rng) -> GrpDrchElt
{Base extension of eps to R.}
   phi := ReductionMap(BaseRing(Parent(eps)),R);
   return BaseExtend(eps, R, phi(Parent(eps)`RootOf1));
end intrinsic;


intrinsic BaseExtend(eps::GrpDrchElt, R::Rng, z::RngElt) -> GrpDrchElt
{Base extension of eps to R.}
   require z^Parent(eps)`OrderOfRoot eq 1 : "Invalid root of unity.";
   H := BaseExtend(Parent(eps),R,z);
   return H!eps;
end intrinsic;


intrinsic BaseExtend(G::GrpDrch, f::Map) -> GrpDrch
{Base extension of G to Codomain(f).}
   R := Codomain(f);
   z := f(G`RootOf1);
   require z^G`OrderOfRoot eq 1 : "Invalid map f.";
   return BaseExtend(G,R,z);
end intrinsic;


intrinsic BaseExtend(eps::GrpDrchElt, f::Map) -> GrpDrchElt
{Base extension of eps to Codomain(R).}
   H := BaseExtend(Parent(eps),f);
   return H!eps;
end intrinsic;

intrinsic DistinguishedRoot(G::GrpDrch) -> RngElt, RngIntElt
{The distinguished root of unity in the base ring of G and its order.}
   return G`RootOf1, G`OrderOfRoot;
end intrinsic;


intrinsic KroneckerCharacter(D::RngIntElt) -> GrpDrchElt
   {The Kronecker character (D/n).}
   require D eq 1 or IsFundamental(D) : "Argument 1 must be either 1 or a fundamental discriminant.";
   return KroneckerCharacter(D,IntegerRing());
end intrinsic;


intrinsic KroneckerCharacter(D::RngIntElt, R::Rng) -> GrpDrchElt
   {The Kronecker character (D/n) over the ring R, where D is a fundamental discriminant or 1.}
   require D eq 1 or IsFundamental(D) : "Argument 1 must be either 1 or a fundamental discriminant.";

   eps := DirichletGroup(1,R)!1;
   for factor in Factorization(D) do
      if not (factor[1] eq 2 and factor[2] le 2) then
         G := DirichletGroup(factor[1]^factor[2],R);
         chi := G.(2-(factor[1] mod 2));
         eps := eps*(chi^(Order(chi) div 2));
	 if factor[1] mod 4 eq 3 then
            D := -D; 
         end if;
      end if;
   end for;
   if D mod 4 eq 0 and D lt 0 then
      eps := eps*DirichletGroup(4,R).1;
   end if;
   return eps;
   
end intrinsic;

intrinsic GaloisConjugacyRepresentatives(G::GrpDrch) -> SeqEnum
{Representatives for the Gal(Qbar/Q)-conjugacy classes of G.}     
   require Type(BaseRing(G)) in {FldRat, FldCyc, FldNum} : 
             "The base ring of argument 1 must be a number field.";
   return GaloisConjugacyRepresentatives(Elements(G));
end intrinsic;


intrinsic GaloisConjugacyRepresentatives(S::[GrpDrchElt]) -> SeqEnum
{Representatives for the Gal(Qbar/Q)-conjugacy classes of S.}  
   if #S eq 0 then
      return S;
   end if;
   require Type(BaseRing(S[1])) in {FldRat, FldCyc, FldNum} : 
             "The base ring of argument 1 must be a number field.";

   G := Parent(S[1]);
   r, n := DistinguishedRoot(G);      
   i := 1;
   U := [k : k in [2..n-1] | GCD(k,n) eq 1];
   while i lt #S do
      x := S[i];
      for m in U do
         y := x^m;
         R := [j : j in [i+1..#S] | S[j]`Element eq y`Element];
         for j in Reverse(R) do    // important to reverse.
            Remove(~S,j);
         end for;
      end for;
      i +:= 1;
   end while;
   return S;
end intrinsic;

intrinsic MinimalBaseRingCharacter(eps::GrpDrchElt) -> GrpDrchElt
   {}
   F := BaseRing(eps);
   N := Modulus(eps);
   case Type(F):
      when FldRat:
         return eps;
      when FldFin:
         if IsPrime(#BaseRing(eps)) then
            return eps; 
         end if;
      when FldCyc:
         n := Order(eps);
         if n eq 1 then
            return DirichletGroup(N)!1;
         end if;
         if EulerPhi(n) eq Degree(F) then
            return eps;
         elif EulerPhi(n) lt Degree(F) then
            if n eq 2 then
               K := RationalField();
            else
               K := CyclotomicField(n);
            end if;
            G := DirichletGroup(N,K);
            return G!eps;
         else
            error "There is a bug.";
         end if;
   end case;   
   require false : "The base ring of argument 1 must be the Q, F_p, or cyclotomic.";
end intrinsic;

////////////////////// NEW STUFF //////////////////////////////////

intrinsic ValuesOnUnitGenerators(x::GrpDrchElt) -> SeqEnum
{The values of x on the ordered sequence generators of (Z/m)^*, where
 m is the modulus of x.}
   U := Parent(x)`UGroup;
   gens :=  [U.i : i in [1..Ngens(U)]];
   return [Evaluate_helper(x, Eltseq(g)) : g in gens];
end intrinsic;

function DirichletCharacterFromValuesOnUnitGenerators(G, v)
// Return a boolean (success = true), an error message (success = ""), 
// and a DirichletCharacter on success or 0 on failure. 

   assert Type(G) eq GrpDrch;
   assert Type(v) eq SeqEnum;

   gens := UnitGenerators(G);
   if #gens ne #v then
      return false, 
     "Argument two must be a sequence of length equal to the number of 'canonical' generators of (Z/m)^*, where m is the modulus of G.",
      0;
   end if;
   if #v eq 0 then
      return true, "", G!1;
   end if;   
   if not IsCoercible(BaseRing(G), v[1]) then
      return false,
      "Argument 2 must be a sequence of elements in the base ring of argument 1.",
      0;
   end if;
   z, n := DistinguishedRoot(G);      
   if z eq 1 then
      assert n eq 1;
      return true, "", G!1;
   end if;
   for x in v do 
      if x^n ne 1 then 
         return false,
          "Each element of argument 2 must have order dividing the"*
         " order of the chosen distinguished root of unity in the base ring of argument 1.",
         0;
      end if;
   end for;
   
   // Now determine, for each element a of v, the minimum power m of z such
   // that z^m = a.
   rootpows := G`PowersOfRoot;
   I     := [Index(rootpows,a) : a in v]; 
   ords  := G`OrdersUGroup;
   r     := G`OrderOfRoot;
   elt   := [Integers() | I[i]*ords[i]/r : i in [1..#I]];
   if 0 in elt then
      return false, "Elements of argument 2 must lie in the group generated by the root of unity associated to argument 1.", 0;
   end if;
 
   return true, "", initGrpDrchElt(G, G`UGroup!elt);
end function;

intrinsic ApplyAutomorphism(x::GrpDrchElt, phi::.) -> GrpDrchElt
{}
   t,msg,y := DirichletCharacterFromValuesOnUnitGenerators(Parent(x), 
              [phi(z) : z in ValuesOnUnitGenerators(x)]); 
   require t : "Argument 2 must be an automorphism, and for some reason it didn't behave correctly ("*msg*")";
   return y;
end intrinsic;


function OrderOfZeta(zeta)
   C := Parent(zeta);
   for d in Sort(Divisors(CyclotomicOrder(C))) do
      if zeta^d eq 1 then
         return d;
      end if;
   end for;
   assert false;
end function;

// find a square root of eps:
function RootOf1Sqrt(zeta)   
   // Given a root of unity zeta_n, with n odd, return one of the
   // two powers of -zeta_n that has square equal to zeta.
   // Let e be the multiplicative inverse of 2 modulo n.  Then
   // ((-zeta_n)^e)^2 = zeta_n, so this function should return 
   // the value (-zeta_n)^e.
   if zeta eq 1 then
      return -1;
   end if;
   e := Integers()!((Integers(OrderOfZeta(zeta))!2)^(-1));
   return (-zeta)^e;
end function;

intrinsic Sqrt(eps::GrpDrchElt) -> GrpDrchElt
{A square root of eps, where eps is a Dirichlet character of odd order.}
   require IsOdd(Order(eps)) : "Argument 1 must have odd order.";
   G := Parent(eps);
   v := ValuesOnUnitGenerators(eps);
   v := [RootOf1Sqrt(x) : x in v];
   t, msg, sqrt_eps := DirichletCharacterFromValuesOnUnitGenerators(G, v);
   require t : msg;
   return sqrt_eps;   
end intrinsic;


////////////////////// END dirichlet.m ////////////////////////////



/******** FURTHER COMMENTS ABOUT BUG FIXES are below ********


==================================================================
This is about 08/15/03:

On Mon, 2003-08-11 at 07:16, Kevin Buzzard wrote:
> Garbage in, not a pretty error out. Isn't the philosophy to give a 
> prettier error?
> 
> [buzzard@kbuzzard buzzard]$ magma
> Magma V2.10-13    Mon Aug 11 2003 12:15:16 on kbuzzard [Seed = 2660686648]
> Type ? for help.  Type <Ctrl>-D to quit.
> > G1<a,b>:=DirichletGroup(21,CyclotomicField(6));
> > G2<aa,bb>:=DirichletGroup(21,GF(9));
> > G2!b;
> 
> HackobjCoerceGrpDrch(
>     G: Group of Dirichlet characters of modulus 21 over Finite fiel...,
>     x: b
> )
...

I wish MAGMA had "exception handling", because it's harder to code error
messages in instances like this than it should be.  I fixed the problem
so now the error is:
------------------
>> G2!b;
     ^
Runtime error in '!': Each element of argument 2 must have order
dividing the order of the chosen distingui\shed root of unity in the
base ring of argument 1.
------------------

I fixed this by demoting  DirichletCharacterFromValuesOnUnitGenerators
to a function (it was an intrinsic) and making it return whether or not
an error occurs, and if so an error message.  Then each intrinsic that
calls  DirichletCharacterFromValuesOnUnitGenerators includes a require
statement asserting that an error didn't occur.  I've attached the
newest dirichlet.m to this file.

William

==================================================================*/
