/////////////////////////////////////////////////////////////////////
// "On the torsion of rational elliptic curves over sextic fields" //
//        Harris B. Daniels and Enrique González-Jiménez           //
/////////////////////////////////////////////////////////////////////

// 2/8/2018 - Magma 2.23

// Magma script related to Proposition 8 (r) 


// Split Cartan -- diagonal matrices in GL(2,Z/nZ) -- E admits two distinct rational n-isogenies if and only if \im\rho_{E,n} is conjugate ot a subgroup of the split Cartan
function GL2SplitCartan(R)
    if Type(R) eq RngIntElt then R:=Integers(R); end if;
    M,pi:=MultiplicativeGroup(R);
    return sub<GL(2,R) | [[pi(g),0,0,1] : g in Generators(M)], [[1,0,0,pi(g)] : g in Generators(M)]>;
end function;

// Borel group -- upper triangular matrices in GL(2,Z/nZ) -- E admits a rational n-isogeny if and only if \im\rho_{E,n} is conjugate to a subgroup of  the Borel
function GL2Borel(R)
    if Type(R) eq RngIntElt then R:=Integers(R); end if;
    return sub<GL(2,R) | [1,1,0,1],GL2SplitCartan(R)>;
end function;

// Subgroup of Borel that fixes a point of order n
function GL2Borel1(R)
    if Type(R) eq RngIntElt then R:=Integers(R); end if;
    M,pi:=MultiplicativeGroup(R);    
    return sub<GL(2,R) | [1,1,0,1], [[1,0,0,pi(g)] : g in Generators(M)]>;
end function;

// Checks whether H1 is conjugate to a subgroup of H2 in G
function IsConjugateToSubgroup(G,H1,H2)
    if not IsDivisibleBy(#H2,#H1) then return false; end if;
    n:=#H2 div #H1;
    return #[H:H in Subgroups(H2:IndexEqual:=n)|IsConjugate(G,H`subgroup,H1)] ne 0;
end function;

// Compute the invariant factors of a finite Z/nZ-module of rank at most 2  (Magma apparently can't coerce Z/nZ-modules to abelian groups)
function ModuleInvariants(V)
    if Dimension(V) eq 0 then return []; end if;
    if Dimension(V) eq 1 then return [#V]; end if;
    assert Dimension(V) le 2;
    r1:=#sub<V|V.1>;  r2:=#sub<V|V.2>;
    return [GCD(r1,r2),LCM(r1,r2)];
end function;
   
// Given a subgroup of GL(2,Z/nZ), computes the invariants of the sub-module of Z/nZ x Z/nZ fixed by G (returns a list [], [a], or [a,b] with a|b|n)
function FixModule(H)
	V := Eigenspace(Identity(H),1);
	for h in Generators(H) do V:= V meet Eigenspace(Transpose(h),1); end for;	// take transpose to work with right eigenspaces
	return ModuleInvariants(V);
end function;

// Returns if the Z/nZ-module A contains a submodule isomorphic to B (where A and B are specified by invariants). 
function ModuleContains(A,B)
    i:=#A-#B;
    if i lt 0 then return false; end if;
    for j in [1..#B] do if not IsDivisibleBy(A[i+j],B[j]) then return false; end if; end for;
    return true;
end function;

// Returns true of a matrix group over a ring R contains elements of every possible determinant
function FullDeterminantMap(H)
    M,pi:=MultiplicativeGroup(BaseRing(H));
    return sub<M|[Inverse(pi)(Determinant(h)):h in Generators(H)]> eq M;
end function;

// Returns true if a give subgroup of GL(2,Z/nZ) contains an element corresponding to complex conjugation
// Here we use the stronger criterion from Remark 3.5 of  Sutherland's "Computing images of Galois representations attached to elliptic curves".
function ContainsComplexConjugation(H)
    return #[h:h in H|Determinant(h) eq -1 and Trace(h) eq 0 and ModuleContains(FixModule(sub<H|h>),[#BaseRing(H)])] gt 0;
end function;

// Given a subgroup G of GL2(Z/nZ), returns the least divisor m for which G is the full inverse image of its reduction mod m
function GL2Level(G)
    if G eq GL(2,BaseRing(G)) then return 1; end if;
    return GCD([m:m in Divisors(#BaseRing(G)) | m gt 1 and Index(GL(2,Integers(m)),ChangeRing(G,Integers(m))) eq Index(GL(2,BaseRing(G)),G)]);
end function;


G27 := GL(2,Integers(27));
G9,mp9 := ChangeRing(G27,Integers(9));
G3,mp3 := ChangeRing(G27,Integers(3));
B3 := GL2Borel(3);

//Lift 3B to be a subgroup of GL(2,Integers(27))
Im27 := sub<G27 | Inverse(mp3)(B3),Kernel(mp3) >;
Im9 := mp9(Im27);


//Compute the subgroups of Im27 with full determinant and Complex conjugation that are not subgroups of 27B as these would correspond to CM curves.

AdmisIms := [g`subgroup : g in Subgroups(Im27) | FullDeterminantMap(g`subgroup) and ContainsComplexConjugation(g`subgroup) and not IsConjugateToSubgroup(G27,g`subgroup,GL2Borel(27))];

assert #AdmisIms eq 687;

//Compute which of the groups in AdmisIms would have a point of order 27 defined over a sextic extension of Q and put those into S.
G_27:={};
S := [];
for GG in AdmisIms do
     V27:={ v : v in RSpace(GG) | not IsZero(v) and not  
&and[IsDivisibleBy(Eltseq(v)[1],3),IsDivisibleBy(Eltseq(v)[2],3)] };
     names:={GroupName(quo<GG | Core(GG,Stabiliser(GG,v))>) : v in V27  
| Integers()!(Order(GG)/Order(Stabiliser(GG,v))) eq 6};
     G_27:=G_27 join names;
    if #names ne 0 then
    Append(~S,GG);
    end if;
end for;

assert #S eq 42;

//Take the groups in S and find Maximal representatives. 

I:=Sort([<Index(G27,S[i]),i>:i in [1..#S]]);
indexes:={i[1]:i in I};
U:=[<S[I[1][2]],I[1][1],AssociativeArray(indexes)>];
 for n in indexes do if IsDivisibleBy(n,U[1][2]) then U[1][3][n] := [K`subgroup: K in Subgroups(U[1][1]:IndexEqual:=n div U[1][2])]; end if; end for;
for i:=2 to #I do
        H:=S[I[i][2]];
        Hn :=I[i][1];
        keep := true;
        for j:=1 to #U do
            if IsDivisibleBy(Hn,U[j][2]) then
                for K in U[j][3][Hn] do assert #H eq #K; if IsConjugate(G27,H,K) then keep:= false; break; end if; end for;
                if not keep then break; end if;
            end if;
        end for;
        if keep then
            r:=<H,Hn,AssociativeArray(indexes)>;
            for n in indexes do if IsDivisibleBy(n,Hn) then r[3][n] := [K`subgroup:K in Subgroups(H:IndexEqual:=n div Hn)]; end if; end for;
            U:=Append(U,r);
        end if;
    end for;
    S:=[r[1]:r in U];
    for i:= 1 to #S do m:=GL2Level(S[i]); if m gt 1 and m lt #BaseRing(S[i]) then S[i]:=ChangeRing(S[i],Integers(m)); end if; end for;

//Show that mod 9 every group in S is conjugate to a subgroup of 9B. 
for G in S do
assert IsConjugateToSubgroup(G9,mp9(G), GL2Borel(9));
end for;



//Let S1 be those subgroups of S that are not conjugate to a subgroup of 3Cs as this 
//would mean they have independent 9- and 3- isogenies and this only happens for CM curves.
S1 := [G : G in S | not (IsConjugateToSubgroup(G9,mp9(G), GL2Borel(9)) and IsConjugateToSubgroup(G3,mp3(G), GL2SplitCartan(3)))];

//There are exactly 2 groups that satisfy all of these conditions and
//they have the same image mod 9.

assert #S1 eq 2;
assert mp9(S1[2]) eq mp9(S1[1]); 

G271 := S1[1];
G272 := S1[2];

assert G271 eq sub<G27 | [1,0,0,-1],[2,0,0,1],[10,22,18,10] >;
assert G272 eq sub<G27 | [1,0,0,-1],[2,0,0,1],[19,4,9,19] >;

S27:=SL(2,Integers(27));

S271 := (G271 meet S27);
S272 := (G272 meet S27);

//A2 and B4 are the groups with Chen Pauli label 27A2 and 27B4 respectively. 
A2 := sub<G27 | [1,0,18,1], [10,0,0,19], [10,0,24,19] , [13,9,1,7] , [22,0,0,16] , [26,0,0,26]>;
B4 := sub<G27 | [1,0,15,1] , [1,0,18,1] , [1,18,2,10] , [10,0,0,19] , [10,0,15,19] , [17,0,0,8]>; 



IsConjugateToSubgroup(S27,S271,A2); 
IsConjugateToSubgroup(S27,S272,B4); 

//Prop 5.18 of Daniels, Lozano-Robledo, Najman, and Sutherland, Torsion subgroups
//of rational elliptic curves over the compositum of all cubic fields, shows that
//neither of these groups can occur.