/* Here is a collection of Magma programs used in implementing Graham Higmans PORC paper on enumerating p-class two groups In particular, we have here a function implementing Theorem 3.1 from my paper "On Graham Higman's famous PORC paper", Int. J. Group Theory 1 (2012), 65--79. We have an action of GL(m,p)xGL(n,p) on W, where W is the space of mxn matrices over GF(p). If M \in W and (A,B) \in GL(m,p)xGL(n,p) then M acted on by (A,B) is A^-1MB. Theorem 3.1 states that \Sum_A fix(A,B) (with the sum taken over all A \in GL(m,p)) is a polynomial in p which depends only on the type of B. If B has type t then the command gettotals(m,t); will return this polynomial. */ R

:=RationalFunctionField(Integers()); gettypes:=function(n) /* This program lists all possible "types" of matrices in GL(n,F). The rational canonical form of a square matrix will have primary invariant factors of the form p(x)^e, where p(x) is an irreducible polynomial. We need to take account of the fact that different invariant factors can involve the same irreducible polynomial. So we assume that the distinct irreducibles are p_1,p_2,...,p_r, and that the primary invariant factors are p_1^(e_1), p_1^(e_2), ..., p_1^(e_n1), p_2^(f_1), p_2^(f_2),...,p_2^(f_n2), p_3^(g_1), ..., p_r^(h_nr). The type is then [[deg p_1,e_1,e_2,...,e_n1], [deg p_2,f_1,f_2,...,f_n2], ..., [deg p_r,h_1,h_2,...,h_nr]] (We sort the sequences [e_1,e_2,...,e_n1], [f_1,f_2,...,f_n2] etc, and sort the entries [deg p_1,e_1,e_2,...,e_n1], [deg p_2,f_1,f_2,...,f_n2], ..., [deg p_r,h_1,h_2,...,h_nr].) */ //First get the possible sequences [e_1,e_2,...,e_n1] with the entries summing //to at most n. (The n in GL(n,F).) seqpowers:=[]; done:=false; wt:=0; nextg:=1; powers:=[]; while not done do while wt+nextg le n do Append(~powers,nextg); wt:=wt+nextg; Append(~seqpowers,powers); end while; //Backtrack if #powers eq 0 then done:=true; else; len:=#powers; nextg:=powers[len]; wt:=wt-nextg; nextg:=nextg+1; Prune(~powers); end if; end while; //get the weights of these sequences wtpowers:=[]; for i in [1..#seqpowers] do pow:=seqpowers[i]; w:=0; for j in [1..#pow] do w:=w+pow[j]; end for; wtpowers[i]:=w; end for; //build up primaries and their weights primaries:=[]; wtprims:=[]; for w in [1..n] do for i in [1..#seqpowers] do for degp in [1..n] do if wtpowers[i]*degp ne w then continue; end if; s:=Insert(seqpowers[i],1,degp); Append(~primaries,s); Append(~wtprims,w); end for; end for; end for; Append(~wtprims,n+1); //And finally generate the types of weight n types:=[]; done:=false; wt:=0; nextg:=1; guide:=[]; powers:=[]; while not done do while wt+wtprims[nextg] le n do Append(~guide,nextg); Append(~powers,primaries[nextg]); wt:=wt+wtprims[nextg]; if wt eq n then Append(~types,Sort(powers)); end if; end while; //Backtrack if #powers eq 0 then done:=true; else; len:=#powers; nextg:=guide[len]; wt:=wt-wtprims[nextg]; nextg:=nextg+1; Prune(~guide); Prune(~powers); end if; end while; return Sort(types); end function; sizeclass:=function(t) //This uses the formula from Brett Witty's thesis //for the size of a conjugacy class of a given type t //First get the size n of a matrix of type t n:=0; for i in [1..#t] do u:=t[i]; s:=0; for j in [2..#u] do s:=s+u[j]; end for; n:=n+u[1]*s; end for; //Get order of GL(n,p) ogl:=1; for i in [0..n-1] do ogl:=ogl*(p^n-p^i); end for; //now get size of conjugacy class size:=ogl; for i in [1..#t] do u:=t[i]; d:=u[1]; //get lamda lambda:=[u[j]:j in [2..#u]]; Sort(~lambda); Reverse(~lambda); modl:=0; for j in [1..#lambda] do modl:=modl+lambda[j]; end for; //Get conjugate of lambda lprime:=[]; while #lambda gt 0 do Append(~lprime,#lambda); for j in [1..#lambda] do lambda[j]:=lambda[j]-1; end for; while #lambda gt 0 and lambda[#lambda] eq 0 do Prune(~lambda); end while; end while; tee:=#lprime; Append(~lprime,0); nl:=0; for j in [1..tee] do nl:=nl+((lprime[j]*(lprime[j]-1)) div 2); end for; exp:=d*(modl+2*nl); al:=p^exp; for j in [1..tee] do k:=lprime[j]-lprime[j+1]; for m in [1..k] do al:=al*(1-p^(-d*m)); end for; end for; size:=size/al; end for; return size; end function; findtype:=function(g); //Find the type of a matrix f:=PrimaryInvariantFactors(g); pfs:={}; for i in [1..#f] do Include(~pfs,f[i][1]); end for; type:=[]; for pf in pfs do party:=[]; for i in [1..#f] do if f[i][1] ne pf then continue; end if; Append(~party,f[i][2]); end for; Sort(~party); Insert(~party,1,Degree(pf)); Append(~type,party); end for; Sort(~type); return type; end function; numirred:=function(n) //Count the irreducible polys of degree n over GF(p) //(Don't count x) if n eq 1 then return p-1; end if; D:=Divisors(n); nums:=[p]; for i in [2..#D] do k:=D[i]; deg:=p^k; for j in [1..i-1] do if k mod D[j] ne 0 then continue; end if; deg:=deg-nums[j]; end for; nums[i]:=deg; end for; return nums[#D]/n; end function; numtype:=function(t) //Get number of conjugacy classes of a given type t u:=Sort(t); num:=1; spot:=0; while spot lt #u do spot1:=spot+1; spot:=spot1; while spot lt #u and u[spot1][1] eq u[spot+1][1] do spot:=spot+1; end while; k:=spot+1-spot1; m:=numirred(u[spot1][1]); for i in [1..k] do num:=num*(m-i+1); end for; bin:=1; for i in [spot1..spot-1] do if u[i] eq u[i+1] then bin:=bin+1; num:=num/bin; else; bin:=1; end if; end for; end while; return num; end function; getsubts:=function(t,s) //We are looking at the action of (h,g) on W, //where h \in GL(s,p) and g \in GL(n,p) has type t. //The different entries in t correspond to distinct //irreducible polynomials which occur in the invariant //factors of g. We want to pick out the entries in //t which also correspond to irreducible polynomials //which occur in the invariant factors of h. //The various possibilities give us a sequence of //subtypes of t. //Note that since t can have repeated entries the same //subtype can appear more than once. We take this into //account. subts:=[[]]; numsubts:=[1]; m:=#t; subsec:=[]; subt:=[]; weight:=0; nextg:=1; len:=0; while len ge 0 do while nextg le m and weight+t[nextg][1] le s do Append(~subsec,nextg); Append(~subt,t[nextg]); weight:=weight+t[nextg][1]; nextg:=nextg+1; len:=len+1; //Look for subt found:=0; for i in [1..#subts] do if subts[i] eq subt then found:=i; break; end if; end for; if found eq 0 then Append(~subts,subt); Append(~numsubts,1); else; numsubts[found]:=numsubts[found]+1; end if; end while; //backtrack len:=#subsec; if len gt 0 then nextg:=subsec[len]; Prune(~subsec); Prune(~subt); weight:=weight-t[nextg][1]; len:=len-1; nextg:=nextg+1; else; len:=-1; end if; end while; return subts,numsubts; end function; getsubhts:=function(htype,subt) //We are looking at the action of (h,g) on W, //where h in GL(s,p) has type htype and g in GL(n,p) has type t. //The elements of t correspond to distinct irreducible polynomials //occuring in the primary invariant factors of g. //subt lists the elements of t corresponding to the irreducible //polynomials which also appear in the primary invariant factors of h. //Get the subtypes of htype which can match the degrees //of the irreducibles in subt. Also get what is left //over from htype when these subtypes are removed n:=#subt; //We want to pick out subsets of size n from //the entries in htype, so that the degrees match up //with the degrees of subt. subhts:=[]; resthts:=[]; m:=#htype; subsec:=[]; nextg:=1; len:=0; while len ge 0 do while nextg le m and len lt n do Append(~subsec,nextg); nextg:=nextg+1; len:=len+1; end while; //check it out if len eq n then ok:=true; for i in [1..n] do if htype[subsec[i]][1] ne subt[i][1] then ok:=false; break; end if; end for; if ok then subht:=[]; restht:=[]; for i in [1..m] do if i in subsec then Append(~subht,htype[i]); else; Append(~restht,htype[i]); end if; end for; if subht notin subhts then m1:=#subht; new:=true; while new do Append(~subhts,subht); Append(~resthts,restht); new:=false; spot:=m1; while spot gt 1 and not new do if subht[spot-1][1] lt subht[spot][1] or subht[spot-1] ge subht[spot] then spot:=spot-1; else; new:=true; temp:=subht[spot-1]; //Look for the smallest bigger than temp min:=subht[spot]; minspot:=spot; for xx in [spot+1..m1] do ttt:=subht[xx]; if ttt gt temp and ttt lt min then min:=ttt; minspot:=xx; end if; end for; subht[spot-1]:=min; subht[minspot]:=temp; head:=[subht[r]:r in [1..spot-1]]; tail:=[subht[r]:r in [spot..m1]]; Sort(~tail); subht:=head cat tail; end if; end while; end while; end if; end if; end if; //backtrack len:=#subsec; if len gt 0 then nextg:=subsec[len]; Prune(~subsec); len:=len-1; nextg:=nextg+1; else; len:=-1; end if; end while; return subhts,resthts; end function; numtypeleft:=function(t,numleft) //Get number of conjugacy classes of a given type t //with a reduced choice of irreducible polys. //The numbers of irreducible polys available are given in numleft. if t eq [] then return R!1; end if; u:=Sort(t); num:=1; spot:=0; while spot lt #u do spot1:=spot+1; spot:=spot1; while spot lt #u and u[spot1][1] eq u[spot+1][1] do spot:=spot+1; end while; k:=spot+1-spot1; m:=numleft[u[spot1][1]]; for i in [1..k] do num:=num*(m-i+1); end for; bin:=1; for i in [spot1..spot-1] do if u[i] eq u[i+1] then bin:=bin+1; num:=num/bin; else; bin:=1; end if; end for; end while; return num; end function; gettotals:=function(s,t) //Get \Sum_A fix(A,B) in the action of (A,B) on sxn matrices where //B in GL(n,p) has type t and the sum is taken over all A in GL(s,p). //The matrix M acted on by (A,B) gives A^-1MB. //First get size of matrices of type t n:=0; for a in t do count:=0; for i in [2..#a] do count:=count+a[i]; end for; n:=n+a[1]*count; end for; totals:=[R!0:i in [1..n*s+1]]; stypes:=gettypes(s); numleft:=[numirred(i):i in [1..s]]; for j in [1..#t] do k:=t[j][1]; if k gt s then continue; end if; numleft[k]:=numleft[k]-1; end for; subts,numsubts:=getsubts(t,s); for j in [1..#subts] do subt:=subts[j]; num:=numsubts[j]; for ht in stypes do if subt eq [] then totals[1]:=totals[1]+numtypeleft(ht,numleft)*sizeclass(ht); continue; end if; subhts,resthts:=getsubhts(ht,subt); for k in [1..#subhts] do subht:=subhts[k]; restht:=resthts[k]; dimn:=0; for m in [1..#subt] do t1:=subht[m]; t2:=subt[m]; deg:=t1[1]; if deg ne t2[1] then print "arghhh!!!"; readi z; end if; for n in [2..#t1] do for o in [2..#t2] do dimn:=dimn+deg*Minimum(t1[n],t2[o]); end for; end for; end for; //print ht,subht,subt,dimn; readi z; totals[dimn+1]:=totals[dimn+1]+num*numtypeleft(restht,numleft)*sizeclass(ht); end for; end for; end for; gtotal:=0; for i in [1..#totals] do gtotal:=gtotal+totals[i]*p^(i-1); end for; return gtotal; end function; testall:=function(s,n); //Test it all!!!!! //This should give the answer 1+min(s,n) //If we have sxn matrices and we consider the action of //GL(s,p)xGL(n,p) then we are dealing with equivalence of matrices. //The rank of the matrix defines the equivalence class. //This is just a way of testing the function gettotals!!! tts:=gettypes(n); gtotal:=0; for t in tts do gtotal:=gtotal+gettotals(s,t)*numtype(t)*sizeclass(t); end for; for i in [1..s] do gtotal:=gtotal/(p^s-p^(i-1)); end for; for i in [1..n] do gtotal:=gtotal/(p^n-p^(i-1)); end for; return gtotal; end function;