\\ ---------------  GP code  ---------------------------------------
\\
\\ Time-stamp: <Fri, Dec 20, 2002 - 12:33:40 - apacetti>
\\
\\ Description: This are some routines for lifting matrices with
\\ determinant +1 or -1, from Slg(Z/NZ) to Slg(Z)
\\
\\
\\ Original Authors:    Fernando Rodriguez-Villegas 
\\                      villegas@math.utexas.edu
\\                      University of Texas at Austin
\\
\\			Ariel Martin Pacetti
\\			apacetti@math.utexas.edu
\\                      University of Texas at Austin
\\
\\ Created:             May  14  2001
\\
\\----------------------------------------------------------------------

\\ This is a routine for lifting a matrix in Sl_n(Z/NZ). The algorithm
\\ is based in the proof that the sequence 
\\ 1 -> \Gamma(N) -> Sl2(Z) -> Sl_n(Z/NZ) ->1  is exact given un the
\\book "Introduction to the Arithmetic Theory of Automorphic Forms, by
\\Goro Shimura", with a slight modification, so as to work if the given
\\matrix has determinant -1

liftslg(M,N)=
	{local(signo,eigen,A,U,V,W,X,C,dim);
	dim=matsize(M)[1];
	if(dim==1,if(M[1,1]%N==1,return(Mat([1])),return(Mat([-1]))));
	A=matsnf(M,1);
	if(matdet(A[3])%N==1,signo=1,signo=-1);
	U=A[1];
	V=A[2];
	eigen=diag(A[3]);
	W=matid(dim);
	W[1,1]=prod(k=2,dim,eigen[k]);
	W[1,2]=1; W[2,1]=W[1,1]-1;
	X=matid(dim); X[1,2]=-eigen[2]*signo;
	C=matdiagonal(vector(dim-1,k,eigen[k+1]));
	C[1,1]=signo*eigen[1]*eigen[2];
	C=liftslg(C,N);
	M=matrix(dim,dim,x,y,if(x==1&&y==1,signo,
		if(x==2&&y==1,signo-eigen[1],if(x>1&&y>1,C[x-1,y-1]))));
	U^(-1)*W^(-1)*M*X^(-1)*V^(-1)}

\\======================================================================
\\ This is another routine for lifting 2X2 matrices with determinant
\\ 1, but using the gcd, which in general gives smaller lifts.


liftsl2(M,N)=
	{local(k,aux);
	if(M[2,1]%N==0,M[2,1]=N);
	while(gcd(M[1,1],M[2,1])>1,M[1,1]=M[1,1]+N);
	aux=bezout(M[1,1],M[2,1]);
	if(M[1,1]%N!=0,
		k=lift(Mod(M[1,2]+aux[2],N)*Mod(M[1,1],N)^(-1)),
		k=lift(Mod(-aux[1]+M[2,2],N)*Mod(M[2,1],N)^(-1)));
	M[2,2]=aux[1]+M[2,1]*k;
	M[1,2]=k*M[1,1]-aux[2];
	M}

\\======================================================================
\\ Routine for lifting 2X2 matrices with determinant +1 or -1, as in
\\ the previous routine, in general gives smaller coefficients than the
\\ general case.


liftgl2(M,N)=
	{local(k,aux);
	if(M[2,1]%N==0,M[2,1]=N);
	if(matdet(M)%N==1,return(liftsl2(M,N)));     
	while(gcd(M[1,1],M[2,1])>1,M[1,1]=M[1,1]+N);
	aux=-bezout(M[1,1],M[2,1]);
	if(M[1,1]%N!=0,
		k=lift(Mod(M[1,2]+aux[2],N)*Mod(M[1,1],N)^(-1)),
		k=lift(Mod(-aux[1]+M[2,2],N)*Mod(M[2,1],N)^(-1)));
	M[2,2]=aux[1]+M[2,1]*k;
	M[1,2]=k*M[1,1]-aux[2];
	M}



addhelp(liftslg,"liftslg(M,N): This is a routine for lifting a matrix in Sl_n(Z/NZ). The algorithm is based in the proof that the sequence 1 -> \Gamma(N) -> Sl2(Z) -> Sl_n(Z/NZ) ->1  is exact given un the book "Introduction to the Arithmetic Theory of Automorphic Forms, by Goro Shimura", with a slight modification, so as to work if the given matrix has determinant -1")

addhelp(liftsl2,"liftsl2(M,N): This is a routine for lifting 2X2 matrices with determinant 1 using the gcd, which in general gives smaller lifts than liftslg")

addhelp(liftgl2,"liftsl2(M,N): This is a routine for lifting 2X2 matrices with determinant +1 or -1 using the gcd, which in general gives smaller lifts than liftslg")