/* eigenvalues.m -- Compute Hecke eigenvalues
   Author: William Stein
   Description: I'm going to implement the algorithm suggested
   in an email from Cremona on 8 July 2001. 
*/

intrinsic DualHeckeOperatorSparse(M::ModSym, 
                                  p::RngIntElt, 
                                  i::RngIntElt) -> ModTupFldElt
{The image of the ith basis vector of DualVectorSpace(M) under T_p.}
   /* The algorithm below is for testing purposes only.  Of course
      it could be made vastly more efficient. */
   requirege i,1;
   require i le Dimension(M) : 
       "Argument 3 must be at most the dimension of argument 1.";
//   require p ge 0 and IsPrime(p) :  
//       "Argument 2 must be prime.";
   return DualHeckeOperator(M,p)[i];
end intrinsic;

intrinsic W_Matrix(M::ModSym, 
                   p::RngIntElt,
                   i::RngIntElt) -> AlgMatElt
{p must be a prime such that T_p has irreducible charpoly on M.
 v is the ith basis vector for DualVectorSpace(M).}

   A := DualHeckeOperator(M,p);
   n := Dimension(M);
   W :=  MatrixAlgebra(BaseField(M),n)!0;
   W[1,i] := 1;
   for j in [2..n] do
      W[j] := W[j-1]*A;
   end for;
   return W^(-1);
end intrinsic;

intrinsic Eigenvalue(M::ModSym,
  		     W::AlgMatElt,
		     i::RngIntElt,
   		     R::Rng,
   		     p::RngIntElt) -> RngElt
{Compute the eigenvalue a_p in R.}
   require p gt 0 and IsPrime(p) : "Argument 5 must be prime.";
   requirege i,1;
   require i le Dimension(M) : 
       "Argument 3 must be at most the dimension of argument 1.";
   // The eigenvalue is defined by 
   //       b = v*B*W, since b*W^{-1} = v*B,
   // where v is the ith standard basis vector and B is
   // a matrix that represents T_p on the dual.
   
   vB := DualHeckeOperatorSparse(M,p,i);
   b  := vB*W;
   if Dimension(M) eq 1 then
      return b[1];
   else
      return &+[b[i]*R.1^(i-1) : i in [1..Dimension(M)]];
   end if;
end intrinsic;

intrinsic aplist(M::ModSym, b::RngIntElt) -> SeqEnum
{}
   p := 2;
   // this will fail, e.g., for level 512 -- but this is fun test code only!
   while Level(M) mod p eq 0 or 
             not IsIrreducible(CharacteristicPolynomial(
                                          DualHeckeOperator(M,p))) do
      p := NextPrime(p);
   end while;
   i := 1;  // why not?
   W := W_Matrix(M,p,i);
   if Dimension(M) eq 1 then
      R := RationalField();
   else
      S := PolynomialRing(RationalField());
      f := CharacteristicPolynomial(DualHeckeOperator(M,p));
      R<a> := quo<S | f>;
   end if;

   ans := [Eigenvalue(M,W,i,R,p) : p in [2..b] | IsPrime(p)];
   f := qEigenform(M,b+1);
   ans2 := [Coefficient(f,p) : p in [2..b] | IsPrime(p)];
   return ans, ans2;
end intrinsic;
                 
