freeze;
 
/****-*-magma-* EXPORT DATE: 2004-03-08 ************************************
                                                                            
                     MODABVAR: Modular Abelian Varieties in MAGMA
 
                              William A. Stein        
                         
   FILE: torsion.m
   DESC: Torsion bounds.

   Creation: 06/16/03 -- initial creation
      
 ***************************************************************************/

/*
HANDBOOK_TITLE:  Rational Torsion Subgroups

BEGIN_HANDBOOK_INTRO

The following functions are used for computing information
about certain torsion points on modular abelian varieties. 

END_HANDBOOK_INTRO



*/


import "homology.m":
   ModSym_to_Rational;

import "modabvar.m":
   HasOnlyTrivialCharacters,
   Verbose;

import "rings.m":
   QQ, Qbar,
   IsNumberField;

forward 
   ComputeSize,
   Compute_CuspidalSubgroup;


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

  << Cuspidal Subgroup >>


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

intrinsic CuspidalSubgroup(A::ModAbVar) -> ModAbVarSubGrp
{The subgroup of A generated by all differences of cusps, where we view
A as a quotient of a modular symbols abelian variety.  }
   require Characteristic(BaseRing(A)) eq 0 : 
            "Argument 1 must be defined over a field of characteristic 0.";
   require HasOnlyTrivialCharacters(A) : "Argument 1 must be a quotient of J_0(N).";
   G := Compute_CuspidalSubgroup(A, false);  
   // I should be able to set this to some sort of Cyclotomic field. 
   // This is known -- need to look up in literature. 
   // G`field_of_definition := BaseRing(A); 
   return G;
end intrinsic;


intrinsic RationalCuspidalSubgroup(A::ModAbVar) -> ModAbVarSubGrp
{Finite subgroup of A generated by all differences of Q-rational
cusps, where we view A in some way as a quotient of a modular symbols 
abelian variety.}
   require Characteristic(BaseRing(A)) eq 0 : 
            "Argument 1 must be defined over a field of characteristic 0.";
   require HasOnlyTrivialCharacters(A) : "Argument 1 must be a quotient of J_0(N).";
   G := Compute_CuspidalSubgroup(A, true);   
   G`field_of_definition := BaseRing(A);
   return G;
end intrinsic;


function ComputeSize(A)   // this is only called in modabvar.m, since
                          // that's where it makes sense in the documentation.
   if Type(BaseRing(A)) eq RngInt then
      A := ChangeRing(A,QQ);
   end if;
   if not assigned A`num_rational_points then
      Verbose("ComputeSize", 
      Sprintf("Computing the number of points in %o.",A),"");
      if IsOnlyMotivic(A) then
         A`num_rational_points := [1, Infinity()];
         return 1, Infinity();
      end if;
   
      K := BaseRing(A);
      if Type(K) in {FldAC, FldPr} then
         A`num_rational_points := [Infinity(), Infinity()];
         return Infinity(), Infinity();
      end if;

      if Type(K) in {FldRat} then   
   // TODO:
   // This could be done for K any abelian extension!!!
         if IsZeroAt(LSeries(A),1) then
            A`num_rational_points := [Infinity(), Infinity()];
            return Infinity(), Infinity();
         end if;
         if HasOnlyTrivialCharacters(A) then
            lower := TorsionLowerBound(ChangeRing(A,QQ));
         else
            lower := 1;
         end if;
         upper := TorsionMultiple(A,30);
         if lower eq upper then
            A`num_rational_points := [lower, upper];
            return lower, upper;
         end if;
         upper := TorsionMultiple(A,100);    
         A`num_rational_points := [lower, upper];
         return lower, upper;
      end if;
      if Type(K) eq FldFin then
         f := FrobeniusPolynomial(A);
         card := Integers()!Evaluate(f, 1);
         A`num_rational_points := [card, card];
         return card, card;
      end if;
      A`num_rational_points := [1, Infinity()];
      return 1, Infinity();
   end if;
   return Explode(A`num_rational_points);
end function;

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

  << Upper and Lower Bounds >>

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

intrinsic TorsionLowerBound(A::ModAbVar) -> RngIntElt
{A divisor of the cardinality of the K-rational torsion 
subgroup of A over K.}
   K := BaseRing(A);
   if Type(K) in {FldAC, FldPr} then
      return Infinity();
   end if;
   require IsNumberField(K) : "Argument 1 must be defined over a number field.";   
   /* TODO: this is a really crappy bound, compared to what one could do ... 
        - using Stevens's better information about galois action on cusps.
        - using cyclotomic nature of K.
   */
   return #RationalCuspidalSubgroup(A);
end intrinsic;

intrinsic TorsionMultiple(A::ModAbVar) -> RngIntElt
{Same as TorsionMultiple(A,50).}
   return TorsionMultiple(A,50);
end intrinsic;

intrinsic TorsionMultiple(A::ModAbVar, n::RngIntElt) -> RngIntElt
{A multiple of the cardinality of the K-rational torsion subgroup of A 
over K obtained by counting points on A mod p, where p
varies over the odd primes p<=n such that p does
not divide the level of A.}
   Verbose("TorsionMultiple", 
      Sprintf("Computing multiple of order of torsion subgroup of A=%o using primes up to %o", 
         A, n),"");
   K := BaseRing(A);
   if Type(K) in {FldAC, FldPr} then
      return Infinity();
   end if;

   require IsNumberField(K) : "Argument 1 must be defined over a number field.";   

   // Worry about e < p-1:   Our torsion point is defined over K,
   // so e is at most [K:Q], so we assume [K:Q]+1 < p.

   d := Degree(K);
   ans := 0;
   for p in [q : q in [d+2..n] | IsPrime(q) and Level(A) mod q ne 0] do
      Verbose("TorsionMultiple", "", Sprintf("Using p = %o", p));
      F := FrobeniusPolynomial(A,p);
      if Type(F) ne SeqEnum then
         F := [F];
      end if;
      for f in F do 
         Np := Integers()!Evaluate(f,1);
         ans := GCD(Np,ans);
       end for;
   end for;
   return ans;
end intrinsic;



/************************************************************************/
/* Cuspidal subgroup */
/************************************************************************/

function Compute_CuspidalSubgroup(A, rational_only)
   Verbose("Compute_CuspidalSubgroup", 
       Sprintf("Computing %ocuspidal subgroup of A=%o.", 
         rational_only select "rational " else "", A), "");
   assert Type(A) eq ModAbVar;
   assert Type(rational_only) eq BoolElt;
   assert HasOnlyTrivialCharacters(A);
   if Dimension(A) eq 0 then
      return ZeroSubgroup(A);
   end if;
     
   if not IsAttachedToModularSymbols(A) then
      pi := ModularParameterization(A);
      G := Compute_CuspidalSubgroup(Domain(pi), rational_only);
      return pi(G);
   end if;

   if Weights(A) eq {2} then
      return Subgroup(
         [ A ! < 1,  [Cusps()|alpha,Infinity()]  > : 
             alpha in (rational_only select RationalCusps(M) else Cusps(M)),
                 M in ModularSymbols(A)
         ]);
   end if;

   assert not rational_only;

   // Use a general algorithm:
   H := Homology(A);
   modsym := H`modsym;
   to_H := ModSym_to_Rational(H);
   gens := [];
   zero := [M!0 : M in modsym];
   for i in [1..#modsym] do
      for x in IntegralBasis(AmbientSpace(modsym[i])) do
         v := zero;
         v[i] := x;
         Append(~gens, A!to_H(v));
      end for;
   end for;
   return Subgroup(gens);
end function;

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

  << Torsion Subgroup >>

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

intrinsic TorsionSubgroup(A::ModAbVar) -> BoolElt, ModAbVarSubGrp
{Either false and a subgroup of the torsion subgroup, or true
and the exact torsion subgroup of A over the base field.}
   K := BaseRing(A);
   if not (IsField(K) and Characteristic(K) eq 0) then
      return false, ZeroSubgroup(A);
   end if;
   mult := TorsionMultiple(A,100);
   C := RationalCuspidalSubgroup(A);
   if #C eq mult then
      return true, C;
   end if;
   return false, C;
end intrinsic;

