///////////////////////////////////////////////////////////////////////////
// "Growth of torsion groups of elliptic curves upon base changes"
// Enrique González-Jiménez & Filip Najman
///////////////////////////////////////////////////////////////////////////

// 13/10/2016 - Magma 2.21

// Magma script related to Proposition 5.4 and Lemma 5.5

load "subgroups.m";

// All proper applicable subgroups of GL_2(F_13) (up to conjugation).

ell:=13;
G:=GL(2,ell);
L:=[H`subgroup: H in Subgroups(G)];
S:={{H1: H1 in L | IsConjugate(GL(2,ell),H1,H2)}: H2 in L};
A:=[Random(s): s in S];   // list of subgroups of G up to conjugacy in GL_2(F_ell)
M:=[H: H in A | #{Determinant(h): h in H} eq ell-1 and GL(2,ell)![-1,0,0,-1] in H and H ne G];
 
AppSubGroups13:=[H: H in M |  #{h: h in H | Determinant(h) eq -1 and Trace(h) eq 0 } ne 0];

/* There are 25 proper applicable subgroups of GL_2(F_13) (up to conjugation)
> #AppSubGroups13;
25
*/

// We define the groups 13Ns, 13Nns and 13S4
// Let G be a subgroup of GL(2,F_ell) and which acts from the left: M*v (M in G) 
// then we need to transpose to work in Magma 
// (since Magma the subgroups of GL(2,F_ell) acts from the right: v*M (M in G) 

Ns:=GL2SubgroupFromLabel("13Ns");
tNs:=sub<GL(2,13)|[Transpose(g) : g in Ns]>;

Nns:=GL2SubgroupFromLabel("13Nns");
tNns:=sub<GL(2,13)|[Transpose(g) : g in Nns]>;


G7:=sub<GL(2,13)|[[2,0,0,2],[2,0,0,3],[0,-1,1,0],[1,1,-1,1]]>;
tG7:=sub<GL(2,13)|[[2,0,0,2],[2,0,0,3],[0,1,-1,0],[1,-1,1,1]]>;
/* 
> GL2SubgroupLabel(G7);                                                        
13S4
*/


function CUENTA(G)
// Given a subgroup G of GL(2,F_13) 
// the function computes all the possible applicable subgroups of G 
// with the lengths of all the orbits of the action of G of (Z/13Z)^2
  Sub:=Subgroups(G);
  GG:=[x`subgroup : x in Sub];
  S:={};Lab:=[];
  for gg in GG do 
    Pgg:=sub<GL(2,13)|Generators(gg),[-1,0,0,-1]>; 
    if &or[IsConjugate(GL(2,13),Pgg,app) : app in AppSubGroups13] then 
      orbits:={#o : o in Orbits(gg)};
      tgg:=sub<GL(2,13)|[Transpose(g) : g in gg]>;
      lab:=GL2SubgroupLabel(tgg); 
      print lab;
      print orbits;
      S:=S join orbits;
      Lab:=Append(Lab,lab); 
    end if;
  end for;
  return Sort(Lab),S;
end function;


L1,S1:=CUENTA(tNs);
/* OUTPUT from the printf function
13Cs.1.3
{ 1, 3, 4, 12 }
13Cs.1.11
{ 1, 2, 12 }
13Cs.1.4
{ 1, 6, 12 }
13Cs.1.8
{ 1, 4, 6, 12 }
13Cs.1.1
{ 1, 12 }
13Cs.1.6
{ 1, 3, 12 }
13Cs.12.3
{ 1, 4, 6, 24 }
13Cs.12.1
{ 1, 2, 12, 24 }
13Cs.12.4
{ 1, 6, 12, 24 }
13Cs.3.4
{ 1, 6, 12, 36 }
13Cs.3.1
{ 1, 3, 12, 36 }
13Cs.5.4
{ 1, 12, 48 }
13Cs.5.1
{ 1, 4, 12, 48 }
13Ns.5.2
{ 1, 24, 48 }
13Cs.4.1
{ 1, 6, 12, 72 }
13Ns.5.1.4
{ 1, 24, 48, 96 }
13Cs
{ 1, 12, 144 }
13Ns.2.1
{ 1, 24, 144 }
13Ns
{ 1, 24, 144 }
*/

L2,S2:=CUENTA(tNns);
/* OUTPUT from the printf function
13Ns.5.2
{ 1, 24, 48 }
13Nn
{ 1, 168 }
*/

L3,S3:=CUENTA(tG7);

/* OUTPUT from the printf function
13Cs.1.4
{ 1, 6, 12 }
13Cs.1.6
{ 1, 3, 12 }
13Cs.12.4
{ 1, 6, 12, 24 }
13Ns.5.2
{ 1, 24, 48 }
13Cs.5.4
{ 1, 12, 48 }
13Ns.5.1.4
{ 1, 24, 48, 96 }
13S4
{ 1, 72, 96 }
*/

/* OUTPUT: possible degrees [Q(P):Q] with ord(P)=13, corresponding to each subgroups of 13Ns, 13Nns and 13S4
// We must exclude [Q(P):Q]=1, since it is coming from the orbit of (0,0)
> S1;S2;S3;
{ 1, 2, 3, 4, 6, 12, 24, 36, 48, 72, 96, 144 }
{ 1, 24, 48, 168 }
{ 1, 3, 6, 12, 24, 48, 72, 96 }
*/


/* OUTPUT: We determine that G_E(13) is conjugate in GL(2,13) to one of the following groups:
> Sort(Setseq(Seqset(L1 cat L2 cat L3)));
[ 13Cs, 13Cs.1.1, 13Cs.1.11, 13Cs.1.3, 13Cs.1.4, 13Cs.1.6, 13Cs.1.8, 13Cs.12.1, 
13Cs.12.3, 13Cs.12.4, 13Cs.3.1, 13Cs.3.4, 13Cs.4.1, 13Cs.5.1, 13Cs.5.4, 13Nn, 
13Ns, 13Ns.2.1, 13Ns.5.1.4, 13Ns.5.2, 13S4 ]
*/

/* OUTPUT: And all the possible degrees [Q(P):Q] with ord(P)=13:
// We must exclude [Q(P):Q]=1, since it is coming from the orbit of (0,0)
> S1 join S2 join S3;
{ 1, 2, 3, 4, 6, 12, 24, 36, 48, 72, 96, 144, 168 }

*/

/* OUTPUT: The remaining cases after removing the cases 13Cs and 13Cs.a.b are

[ 13Nn, 13Ns, 13Ns.2.1, 13Ns.5.2, 13Ns.5.1.4, 13S4 ]


13Nn
{ 1, 168 }
13Ns
{ 1, 24, 144 }
13Ns.2.1
{ 1, 24, 144 }
13Ns.5.2
{ 1, 24, 48 }
13Ns.5.1.4
{ 1, 24, 48, 96 }
13S4
{ 1, 72, 96 }
*/

/* OUTPUT: With the possible degrees [Q(P):Q] with ord(P)=13:
// We must exclude [Q(P):Q]=1, since it is coming from the orbit of (0,0)

>{ 1, 168 } join { 1, 24, 144 } join { 1, 24, 144 } join { 1, 24, 48 } join { 1, 24, 48, 96 } join { 1, 72, 96 };
{ 1, 24, 48, 72, 96, 144, 168 }
*/