//Dati d ordine del gruppo e m=(m_1,...,m_r) segnatura calcola il genere del rivestimento di P^1 con RH
GenereSegnatura:=function(d,m)
return d*(-2+#m-&+[1/m[i]: i in [1..#m]])/2+1;
end function;

//Da monodromia t restituisce la segnatura
SegnaturaMonodromia:=function(t)
return [Order(t[j]) : j in [1..#t]];
end function;

//Restituisce il genere della curva dato gruppo G e monodromia t
GenereDato:=function(G,t)
return GenereSegnatura(#G,SegnaturaMonodromia(t));
end function;


//Da un dato (G,t) di una curva C, calcola con la formula di Riemann-Hurwits il genere del quoziente C/H anche se non Galois
GenereQuozienteRH:=function(G,t,H);
Gx:=[];
A:=[{Id(G)}];
H:={G!x:x in H};
for i in [1..#t] do
	Gx[i]:={G!x: x in sub<G|t[i]>};
	A[i]:={x:x in G| #({x*y*x^-1:y in Gx[i]} meet H) gt 1};
end for;
R:=&+[#A[i]/#Gx[i]*(#(Gx[i] meet H)-1):i in [1..#t]];
return (GenereDato(G,t)-1-R/2)/#H+1;
end function;



//Massimo ordine che può avere il gruppo degli automorfismi
// solo per r>=4
MaxOrdineAut:=function(r,g)
if r eq 4 then
	return 12*(g-1);
else
	return Floor(4*(g-1)/(r-4));
end if;
end function;


//Calcola tutte le possibili segnature m=(m_1,...,m_r), ossia r-uple (non decrescenti) di divisori di d tali che diano genere g
ListaSegnature:=function(r,g,d)
L:=[];
T:=[];
X:=Remove(Divisors(d),1);
x:=#X;
b:=Binomial(r+x-1,r);
for j in [1..r] do
	T[j]:=x;
end for;
if GenereSegnatura(d,X[T]) eq g then
	Append(~L,X[T]);
end if;

for i in [2..b] do
	for j in [1..r] do
		if T[j] gt 1 then
			T[j]:=T[j]-1;
			for k in [1..j-1] do
				T[k]:=T[j];
			end for;
			if GenereSegnatura(d,X[T]) eq g then
				Append(~L,X[T]);
			end if;
			break;
		end if;
	end for;
end for;
return Sort(L);
end function;


//Genera lista di coppie (d,M) con d ordine gruppo e M lista di segnature m=(m_1,...,m_r)
GeneraSegnature:=function(r,g)
maxOrd:=MaxOrdineAut(r,g);
SegnaturaComp:=recformat< d : RngIntElt, M : SeqEnum >;
Segnature:=[];
for ord in [2..maxOrd] do
	L:=ListaSegnature(r,g,ord);
	if not IsEmpty(L) then
		Append(~Segnature,rec<SegnaturaComp|d:=ord, M:=L>);
	end if;
end for;
return Segnature;
end function;


//Restituisce una sequenza di insiemi di elementi di G divisi per gli ordini voluti
ListaElementiPerOrdine:=function(G,ordini)
Lista:=[];
Lista[1]:={Id(G)};
for n in ordini do
	Lista[n]:={};
end for;
C:=ConjugacyClasses(G);
for i in [1..#C] do
	if C[i][1] in ordini then
		Lista[C[i][1]] join:=Class(G,C[i][3]);
	end if;
end for;

return Lista;
end function;


Treccia:=function(t,i)
return Insert(Remove(t,i),i+1,t[i]^t[i+1]);
end function;

TrecciaInversa:=function(t,i)
return Insert(Remove(t,i+1),i,t[i+1]^(t[i]^-1));
end function;


//Fissato gruppo G e segnatura m restituisce un sequenza di generatori sferici modulo Aut(G) e Trecce
GeneratoriSferici:=function(G,m,ElGOrd)
r:=#m;
P:=CartesianProduct([ElGOrd[m[i]]: i in [1..r-1]]);
S:={};
Generano:={};
NonGenerano:={};
for x in P do
	y:=&*x^-1;
	if y in ElGOrd[m[r]] then
		t:=Append([g:g in x],y);
		s:=Set(t);
		if s in Generano then
			Include(~S,t);
		elif s notin NonGenerano then
			if #sub<G|s> eq #G then 
				Include(~Generano,s);
				Include(~S,t);
			else
				Include(~NonGenerano,s);
			end if;
		end if;
	end if;
end for;

if IsEmpty(S) then
	return [];
end if;

//Azione di Aut(G) e di Br su S tramite azione del sottogruppo di Aut(S) generato.
Sn:=Sym(S);	//Sn = Aut(S)
genGruppone:={};
A:=AutomorphismGroup(G);

// generatori di Aut(G)
for phi in Generators(A) do
	prod:=Sn!1;
	N:={};
	for x in S do
		y:=phi(x);
		if y notin N and y ne x then
			Include(~N,x);
			prod*:=Sn!(x,y);
		end if;
	end for;
	Include(~genGruppone,prod);
end for;

im:=[i: i in [1..r-1] | m[i] eq m[i+1]];

if IsAbelian(G) then
	/// Caso Abeliano
	//generatori delle permutazioni con m_i=m_{i+1} 
	for i in im do
		prod:=Sn!1;
		N:={};
		for x in [x: x in S | x[i] ne x[i+1]] do
			y:=Insert(Remove(x,i),i+1,x[i]);
			if y notin N and y ne x then
				Include(~N,x);
				prod*:=Sn!(x,y);
			end if;
		end for;
		Include(~genGruppone,prod);
	end for;
else
	/// Caso non Abeliano
	//generatori dei sigma_i con m_i=m_{i+1}
	for i in im do
		prod:=Sn!1;
		N:={};
		for x in S do		
			y:=Treccia(x,i);
			if y notin N and y ne x then
				Include(~N,x);
				prod*:=Sn!(x,y);
			end if;
		end for;
		Include(~genGruppone,prod);
	end for;

	// generatori trecce pure
	for i in [1..r-1] do
		for j in [i+1..r] do
			if m[i] ne m[j] then
				prod:=Sn!1;
				N:={};
				for x in S do
					y:=x;
					for k in [-(j-1) .. -(i+1)] do
						y:=TrecciaInversa(y,-k);
					end for;
					y:=Treccia(Treccia(y,i),i);
					for k in [i+1 .. j-1] do
						y:=Treccia(y,k);
					end for;

					if y notin N and y ne x then
						Include(~N,x);
						prod*:=Sn!(x,y);
					end if;
				end for;
				Include(~genGruppone,prod);
			end if;
		end for;
	end for;
end if;

//Calcolo Gruppone
H:=sub<Sn|genGruppone>;
//Orbite
Orbite:=OrbitRepresentatives(H);
L:=[rapp[2]: rapp in Orbite];

return L;
end function;


//Da i coefficienti \mu_i della decomposizione dell' H^{1,0} in rappresentazioni irriducibili di G tramite la formula di Chevalley-Weil
//T è la tabella dei caratteri di G
H10CWT:=function(G,t,T)
m:=SegnaturaMonodromia(t);
K<csi>:=CyclotomicField(#G);
S<x>:=PolynomialRing(K);
Z:=Integers();

//E[k][i][alpha] è la molteplicità dell'autovalore z^alpha di rho_chi(t[i]), dove z=exp(2%pi%i/m[i]) e chi=T[k] è il k-esimo carattere irriducibile.
E:=[];
for k:=1 to #T do
	chi:=T[k];
	n:=Z!chi[1];
	E[k]:=[];
	for i:=1 to #m do
		h:=t[i];
		z:=csi^Z!(#G/m[i]);
		c:=[];
		for l in [1..n] do
			c[l]:=chi(h^l);
			for j in [1..l-1] do
				c[l]+:=c[l-j]*chi(h^j);
			end for;
			c[l]/:=-l;
		end for;

		P:=x^n + &+[K!c[l]*x^(n-l): l in [1..n]];

		E[k][i]:=[0:alpha in [1..m[i]-1]];
		for alpha:=1 to m[i]-1 do
			for l:=1 to Degree(P) do
				if Evaluate(P,z^alpha) eq 0 then
					E[k][i][alpha]+:=1;
					P:=P/(x-z^alpha);
				else
					continue alpha;
				end if;
			end for;
		end for;//alpha
	end for;//i
end for;//k

mu:=[];
for k:=1 to #T do
	mu[k]:=-T[k][1];
	for i:=1 to #m do
		for alpha:=1 to m[i]-1 do
			mu[k]+:=alpha*E[k][i][alpha]/m[i];
		end for;
	end for;
end for;
mu[1]+:=1;
return mu;
end function;

H10CW:=function(G,t)
T:=CharacterTable(G);
return H10CWT(G,t,T);
end function;

dimS2VGT:=function(G,t,T)
mu:=H10CWT(G,t,T);
N:=1/(2*Order(G))* &+[ &+[(mu[i]*T[i](x)):i in [1..#T]]^2 + &+[mu[i]*T[i](x^2): i in [1..#T]] : x in G];
return Integers()!N;
end function;

dimS2VG:=function(G,t)
T:=CharacterTable(G);
return dimS2VGT(G,t,T);
end function;


//Dal dato della curva (G,t) e H < G restituisce il dato quoziente
//Serve H normale
DatoQuoziente:=function(G,t,H)
Q,pr:=quo<G|H>;
return Q,pr(t);
end function;


//testa la condizione (*) di FGP per il dato (G,t)
condStar:=function(G,t)
r:=#[x: x in t | Order(x) gt 1];
return dimS2VG(G,t) eq r-3;
end function;


//testa la condizione (A)
condA:=function(G,t,H)
r:=#[x: x in t | Order(x) gt 1];
Q,u:=DatoQuoziente(G,t,H);
Ntilde:=dimS2VG(G,t);
N:=dimS2VG(Q,u);
return Ntilde-N eq r-3;
end function;


//testa la condizione (B1)
// ossia voglio verificare che dim(S^2V_-)^G =  V \otimes (r-3) W con V,W rapp irriducibili di dimensione 1.
condB1:=function(G,t,H)
T:=CharacterTable(G);
H10:=H10CWT(G,t,T);
Vm1:=[];
Vmd:=[];

for i:=1 to #T do
	if T[i][1] eq 1 and &or[T[i](x) ne 1 : x in Generators(H)] then //per essere in V_- ci deve essere almeno un generatore di G che non lo fissa
		if H10[i] eq 1 then
			Append(~Vm1,i);
		end if;
		if H10[i] eq #t-3 then
			Append(~Vmd,i);
		end if;
	end if;
end for;

for i in Vm1 do
	for j in Vmd do
		if Conjugate(T[i],-1) eq T[j] then
			return true;
		end if;
	end for;
end for;

return false;
end function;



//testa la condizione (B2)
condB2:=function(G,t,H)
T:=CharacterTable(G);
H10:=H10CWT(G,t,T);
V:={i:i in [1..#T]|H10[i] gt 0};
Vp:={};
GH:=Generators(H);
for i in V do
	for x in GH do
		if T[i](x) ne T[i][1] then
			continue i;
		end if;
	end for;
	Include(~Vp,i);
end for;
Vm:=V diff Vp;

for sub in NormalSubgroups(G) do
	if sub`order eq #G then continue sub; end if;
	K:=sub`subgroup;
	for x in t do
		if x in K then
			continue sub;
		end if;
	end for;

	VK:={};
	GK:=Generators(K);
	for i in V do
		for x in GK do
			if T[i](x) ne T[i][1] then
				continue i;
			end if;
		end for;
		Include(~VK,i);
	end for;

	if VK notsubset Vm then
		continue sub;
	end if;
	
	Q,u:=DatoQuoziente(G,t,K);
	if condStar(Q,u) then
		return true;
	end if;
end for;
return false;
end function;


// Testa se è un controesempio alla congettura di Xiao
ControXiao:=function(G,t,H)
tg:=GenereDato(G,t);
g:=GenereQuozienteRH(G,t,H);
return 2*(tg-g) gt tg + 1;
end function;

//////////////////////////////

DatiRivestimentiDaListaSegnature:=function(d,ListaSegnature)
DatoCpt := recformat< Gruppo, Theta>;
ListaDatiCpt:=[];
ordini:={n: n in m, m in ListaSegnature};
r:=#ListaSegnature[1];

NumGr:=NumberOfSmallGroups(d);
for i in [1..NumGr] do
	G:=SmallGroup(d,i);
	//Numero minimo di generatori
	try
		numInv:=#AQInvariants(G);
		if numInv gt r then
			continue i;
		end if;
	catch e;
	end try;
	//Lista elementi di G per gli ordini interessanti
	ElGOrd:=ListaElementiPerOrdine(G,ordini);

	ListaMon:=[];
	for m in ListaSegnature do
		for n in Set(m) do
			if IsEmpty(ElGOrd[n]) then
				continue m;
			end if;
		end for;

		//Possibili sistemi di generatori
		L:=GeneratoriSferici(G,m,ElGOrd);
		for t in L do
			Append(~ListaMon,t);
		end for;
	end for;

	if IsEmpty(ListaMon) then
		continue i;
	end if;

	Append(~ListaDatiCpt,rec<DatoCpt| Gruppo:=G, Theta:=ListaMon>);
end for;

return ListaDatiCpt;
end function;


GeneraDatiRivestimenti:=function(r,g)
maxOrd:=MaxOrdineAut(r,g);
RF := recformat< d : Integers(), L : SeqEnum >;
ListaSegn:=[];
for d in [2..maxOrd] do
	if IsPrime(d) then
		continue d;
	end if;
	L := ListaSegnature(r,g,d);
	if not IsEmpty(L) then
		Append(~ListaSegn,rec< RF | d:= d, L:=L>);
	end if;
end for;

Dato := recformat<G,t>;
ListaDati:=[];
for dxL in ListaSegn do
	L:=DatiRivestimentiDaListaSegnature(dxL`d,dxL`L);
	for x in L do
		for t in x`Theta do
			Append(~ListaDati,rec<Dato|G:=x`Gruppo,t:=t>);
		end for;
	end for;
end for;

return ListaDati;
end function;

//////////////////////////////

SalvaListaDatiRivestimenti:=procedure(r,g,L)
schema:=recformat<r,g,S>;
Theta:=recformat<t>;
S:=[];
for dato in L do
	Append(~S,rec<Theta|t:=dato`t>);
end for;
dati:=rec<schema|r:=r,g:=g,S:=S>;
PrintFileMagma("~/riv/riv_" cat IntegerToString(r) cat "_" cat IntegerToString(g),dati);
end procedure;


LeggiListaDatiRivestimenti:=function(r,g)
schema:=recformat<r,g,S>;
Theta:=recformat<t>;
Dato := recformat<G,t>;
dati:=eval(Read("~/riv/riv_" cat IntegerToString(r) cat "_" cat IntegerToString(g)));
r:=dati`r;
g:=dati`g;
L:=[];
for dato in dati`S do
	t:=dato`t;
	G:=Universe(t);
	Append(~L,rec<Dato|G:=G,t:=t>);
end for;
return L;
end function;


////////////////////////////


// Restituisce il numero di punti di diramazione di C --> C/H
NumeroPuntiDiramazionePrym:=function(G,t,H)
Q,u:=DatoQuoziente(G,t,H);
mG:=SegnaturaMonodromia(t);
mQ:=SegnaturaMonodromia(u);
return Integers()!&+[mQ[i] lt mG[i] select #Q/mQ[i] else 0: i in [1..#t]];
end function;


// Restituisce il numero di punti di ramificazione di C --> C/H
NumeroPuntiRamificazionePrym:=function(G,t,H)
Q,u:=DatoQuoziente(G,t,H);
mG:=SegnaturaMonodromia(t);
mQ:=SegnaturaMonodromia(u);
return Integers()!&+[mQ[i] lt mG[i] select #G/mG[i] else 0: i in [1..#t]];
end function;

////////////////////////

DatiPrymDaSegnatura:=function(d,m:Gab:=true,Hcy:=true)
DatoCpt := recformat< Gruppo, Theta, Sotto>;
ListaDatiCpt:=[];
sm:=Set(m);
r:=#m;

NumGr:=NumberOfSmallGroups(d);
for i in [1..NumGr] do
	G:=SmallGroup(d,i);
	//Numero minimo di generatori
	try
		numInv:=#AQInvariants(G);
		if numInv gt r then
			continue i;
		end if;
	catch e;
	end try;
	//Lista elementi di G per gli ordini interessanti
	ElGOrd:=ListaElementiPerOrdine(G,sm);

	for n in sm do
		if IsEmpty(ElGOrd[n]) then
			continue i;
		end if;
	end for;


	//Possibili sistemi di generatori
	ListaMon:=GeneratoriSferici(G,m,ElGOrd);
	if IsEmpty(ListaMon) then
		continue i;
	end if;

	//Possibili sottogruppi di rivestimento
	N:=NormalSubgroups(G);
	ListaSub:=[];
	for H in N do
		if H`order gt 2 and H`order lt d then
			Append(~ListaSub,H`subgroup);
		end if;
	end for;
	if IsEmpty(ListaSub) then
		continue i;
	end if;

	Append(~ListaDatiCpt,rec<DatoCpt| Gruppo:=G, Theta:=ListaMon, Sotto:=ListaSub>);
end for;

return ListaDatiCpt;
end function;



DatiPrymDaListaSegnature:=function(d,ListaSegnature)
DatoCpt := recformat< Gruppo, Theta, Sotto>;
ListaDatiCpt:=[];
ordini:={n: n in m, m in ListaSegnature};
r:=#ListaSegnature[1];

NumGr:=NumberOfSmallGroups(d);
for i in [1..NumGr] do
	G:=SmallGroup(d,i);
	//Numero minimo di generatori
	try
		numInv:=#AQInvariants(G);
		if numInv gt r then
			continue i;
		end if;
	catch e;
	end try;
	//Lista elementi di G per gli ordini interessanti
	ElGOrd:=ListaElementiPerOrdine(G,ordini);

	ListaMon:=[];
	for m in ListaSegnature do
		for n in Set(m) do
			if IsEmpty(ElGOrd[n]) then
				continue m;
			end if;
		end for;

		//Possibili sistemi di generatori
		L:=GeneratoriSferici(G,m,ElGOrd);
		for t in L do
			Append(~ListaMon,t);
		end for;
	end for;

	if IsEmpty(ListaMon) then
		continue i;
	end if;

	//Possibili sottogruppi di rivestimento
	N:=NormalSubgroups(G);
	ListaSub:=[];
	for H in N do
		if H`order gt 2 and H`order lt d then
			Append(~ListaSub,H`subgroup);
		end if;
	end for;
	if IsEmpty(ListaSub) then
		continue i;
	end if;

	Append(~ListaDatiCpt,rec<DatoCpt| Gruppo:=G, Theta:=ListaMon, Sotto:=ListaSub>);
end for;

return ListaDatiCpt;
end function;

///////////////

GeneraDatiPrymZero:=function(r,g)
maxOrd:=MaxOrdineAut(r,g);
RF := recformat< d : Integers(), L : SeqEnum >;
ListaSegn:=[];
for d in [2..maxOrd] do
	if IsPrime(d) then
		continue d;
	end if;
	L := ListaSegnature(r,g,d);
	if not IsEmpty(L) then
		Append(~ListaSegn,rec< RF | d:= d, L:=L>);
	end if;
end for;

ListaDati:=[];
for dxL in ListaSegn do
	L:=DatiPrymDaListaSegnature(dxL`d,dxL`L);
	for x in L do
		Append(~ListaDati,x);
	end for;
end for;

return ListaDati;
end function;

GeneraDatiPrymDaRivestimenti:=function(r,g)
DatoCpt := recformat< Gruppo, Theta, Sotto>;
ListaDatiCpt:=[];
ListaRivestimenti:=LeggiListaDatiRivestimenti(r,g);
for dato in ListaRivestimenti do
	G:=dato`G;
	N:=NormalSubgroups(G);
	ListaSub:=[];
	for H in N do
		if H`order gt 1 and H`order lt #G then
			Append(~ListaSub,H`subgroup);
		end if;
	end for;
	if IsEmpty(ListaSub) then
		continue dato;
	end if;
	Append(~ListaDatiCpt,rec<DatoCpt| Gruppo:=G, Theta:=[dato`t], Sotto:=ListaSub>);
end for;
return ListaDatiCpt;
end function;


GeneraDatiPrym:=function(r,g)
if ReadTest("~/riv/riv_" cat IntegerToString(r) cat "_" cat IntegerToString(g)) then
	return GeneraDatiPrymDaRivestimenti(r,g);
else
	return GeneraDatiPrymZero(r,g);
end if;
end function;

//////////////////////

TrovaEsempi_fibra:=function(r,g)
Esempi:=[];
Dato := recformat<G,t,H>;
ListaDati:=GeneraDatiPrym(r,g);
for x in ListaDati do
	G:=x`Gruppo;
	Tav:=CharacterTable(G);
	for t in x`Theta do
		G:=Universe(t);
		NG:=dimS2VGT(G,t,Tav);
		for H in x`Sotto do
			Q,u:=DatoQuoziente(G,t,H);
			NQ:=dimS2VG(Q,u);
			if NG-NQ lt r-3 then
				Append(~Esempi,rec<Dato|G:=G,t:=t,H:=H>);
			end if;
		end for;
	end for;
end for;

return Esempi;
end function;


