//This file contains two functions to compute the number of //orbits of irreducible binary forms of degree n over GF(p) //under the action of GL(2,p) //OrbitsIrredPols(p,n) computes the number over GF(p) //OrbitsIrredPolsPORC(n) gives the number as PORC polynomials in p //Vishnevetskii's function A(n,e) when e|(n,p-1) //Counting number of irreducible polynomials of //degree n fixed by GL(2,p)![1,0,0,a] where a has order e. VisA:=function(p,n,e) k:=n div e; while GCD(k,e) ne 1 do k:=k div GCD(k,e); end while; r:=n div (e*k); A:=0; for i in [1..k] do if k mod i ne 0 then continue; end if; A:=A+MoebiusMu(k div i)*(p^(r*i)-1); end for; A:=A*EulerPhi(e)/n; return A; end function; //Vishnevetskii's function B(n,p) when p divides n //This counts the number of irreducible polynomials //of degree n fixed by GL(2,p)![1,1,0,1]. //When p does not divide n, B(n,p)=0 VisB:=function(p,n) if n mod p ne 0 then return 0; end if; B:=0; k:=n div p; for d in [1..k] do if d mod p eq 0 then continue; end if; if k mod d ne 0 then continue; end if; B:=B+MoebiusMu(d)*p^(k div d); end for; B:=B*(p-1)/n; return B; end function; MikeC:=function(p,n,e) //Michaels's function C(p,n,e) when e divides p+1 //This counts the number of irreducible polynomials //of degree n fixed by g:=GL(2,p)![0,r,1,s] //with x^2-sx-r irreducible over GF(p), and //where g^e is diagonal, and no lower power of g //is diagonal k:=n div e; while GCD(k,e) ne 1 do k:=k div GCD(k,e); end while; r:=n div (e*k); C:=0; for i in [1..k] do if k mod i ne 0 then continue; end if; C:=C+MoebiusMu(k div i)*(p^(r*i)-1+2*((r*i) mod 2)); end for; C:=C*EulerPhi(e)/n; return C; end function; OrbitsIrredPols:=function(p,n) if n le 2 then return 1; end if; //Get divisors of n divs:=[]; for i in [1..n] do if n mod i eq 0 then Append(~divs,i); end if; end for; //Get the number of irreducible polys of degree n numirred:=0; for d in divs do numirred:=numirred+MoebiusMu(d)*(p^(n div d)-1); end for; numirred:=numirred/n; if p eq 2 then numorbs:=numirred; //fix(I) if n mod 2 eq 0 then numorbs:=numorbs+3*VisB(p,n); end if; //fix([1,1,0,1]) if n mod 3 eq 0 then numorbs:=numorbs+2*MikeC(p,n,3); end if; //fix([0,1,1,1]) return numorbs/6; end if; fix:=numirred; //Identity matrix for d in divs do if d eq 1 then continue; end if; if (p-1) mod d ne 0 then continue; end if; fix:=fix+EulerPhi(d)*(p^2+p)/2*VisA(p,n,d); end for; //Conjugacy classes of GL(2,p)![1,0,0,a] fix:=fix+(p^2-1)*VisB(p,n); //Conjugacy class of GL(2,p)![1,1,0,1] for d in divs do if d le 1 then continue; end if; if (p+1) mod d ne 0 then continue; end if; fix:=fix+EulerPhi(d)*(p^2-p)/2*MikeC(p,n,d); end for; //Conjugacy classes of GL(2,p)![0,s,1,t] return fix/(p^3-p); end function; OrbitsIrredPolsPORC:=function(n) if n le 2 then return [<"All p",1>]; end if; //Get divisors of n divs:=[]; for i in [1..n] do if n mod i eq 0 then Append(~divs,i); end if; end for; P

:=PolynomialRing(Rationals()); //Get the number of irreducible polys of degree n numirred:=0; for d in divs do numirred:=numirred+MoebiusMu(d)*(p^(n div d)-1); end for; numirred:=numirred/n; PORC:=[<"p = 2",P!OrbitsIrredPols(2,n)>]; for d in divs do if d le 2 or not IsPrime(d) then continue; end if; Append(~PORC,<"p = "*IntegerToString(d),P!OrbitsIrredPols(d,n)>); end for; for pmodn in [1..n-1] do if not GCD(pmodn,n) eq 1 then continue; end if; pm1:=(pmodn-1) mod n; pp1:=(pmodn+1) mod n; fix:=numirred; //Identity matrix for d in divs do if d eq 1 then continue; end if; if pm1 mod d ne 0 then continue; end if; fix:=fix+EulerPhi(d)*(p^2+p)/2*VisA(p,n,d); end for; //Conjugacy classes of GL(2,p)![1,0,0,a] for d in divs do if d le 1 then continue; end if; if pp1 mod d ne 0 then continue; end if; fix:=fix+EulerPhi(d)*(p^2-p)/2*MikeC(p,n,d); end for; //Conjugacy classes of GL(2,p)![0,s,1,t] fixa:=fix/(p^3-p); Append(~PORC,<"p mod "*IntegerToString(n)*" = "*IntegerToString(pmodn),fixa>); end for; return PORC; end function;