/*******************************************************************
 * different.m -- code to compute the different of a number field. *
 * Author: William A. Stein                                        *
 * Date:   10/24/00                                                *
 *******************************************************************/

/* BASIC DEFINITIONS
   Let L/K be an extension of number fields, and let O_L, O_K be
   the ring of integers of L, K, respectively.   The different of
   L/K is the inverse of the following fractional ideal:
     { x in L : tr_{L/K}(x*O_L) in O } 
   Specializing to the case K=Q and L a general number field, the
   different is the inverse of the fractional ideal

     I = { x in L : tr_{L/Q}(x*O_L) in Z }.

   ALGORITHM TO COMPUTE INVERSE DIFFERENT
      (1) Choose any basis for L.
      (2) Compute a basis for O_L.
      (3) Compute a matrix representing the map L --> Q^r that 
          sends an element to the traces of its product with 
          each element of O_L. 
      (4) Now we must find the Z-module of elements in L that
          map to Z^r.  This is equivalent to finding a collection
          of elements e_1,...,e_r in L that map to each of the
          standard basis vectors of Z^r.  Then e_1,...,e_r together
          generate a lattice Lambda in L that maps to Z^r.  If a 
          lattice in L that is bigger than Lambda also maps to Z^r
          then the map L--->Q^r is not an injective linear map of 
          Q-vector spaces, which would be a contradiction. 
          Here's how to compute e_1,...,e_r:
            (a) Invert the matrix representing the map L-->Q^r.
            (b) Then the e_i are the images of the standard basis vector.
      (5) The ideal I is then generated by e_1,...,e_r.  
   
   The different is now the inverse of the ideal I.
 
   COMPLEXITY
      The difficulty of computing a basis for O_L probably overshadows
      all other steps, as they involve linear algebra over a Q-vector
      space of very small discriminant.  Inverting I might also be
      difficult.  Other than these standard steps, the other steps are
      slightly tedious to code but should be very efficient. 
*/

intrinsic Different(L::FldNum) -> RngOrdIdl
{The different of the number field L.}
  
   n := Degree(L);
   O := MaximalOrder(L);
   Lbase := Basis(L);
   Obase := Basis(O);
   T := MatrixAlgebra(Rationals(),n)!(&cat [
           [Trace(x*a) : a in Obase] : x in Lbase
        ]);
   Tinv := T^(-1);
   ei := [L!Eltseq(Tinv[i]) : i in [1..n]];
   I := 1*O;
   for e in ei do
     I := I + e*O;
   end for;
   return (1*O)/I;
end intrinsic;


          
 
