################################################################# ## ## This file contains a collection of programs for counting ## subgroups of the symmetric group. The table of marks library ## should be loaded since many of these programs take as argument the table of marks of G ## ## ################################################################# LoadPackage("tomlib"); ## Example with G:=SymmetricGroup(4); G:=SymmetricGroup(4); ## Number of conjugacy classes of abelian subgroups of G Size(Positions(List([1..Size(SubsTom(TableOfMarks(G)))], i-> IsAbelian(RepresentativeTom(TableOfMarks(G), i))), true)); ## Number of conjugacy classes of nilpotent subgroups of G Size(Positions(List([1..Size(SubsTom(TableOfMarks(G)))], i-> IsNilpotentGroup(RepresentativeTom(TableOfMarks(G), i))), true)); ## Number of conjugacy classes of solvable subgroups of G Size(Positions(List([1..Size(SubsTom(TableOfMarks(G)))], i-> IsSolvableGroup(RepresentativeTom(TableOfMarks(G), i))), true)); ## Number of conjugacy classes of supersolvable subgroups of G Size(Positions(List([1..Size(SubsTom(TableOfMarks(G)))], i-> IsSupersolvableGroup(RepresentativeTom(TableOfMarks(G), i))), true)); ## Number of different orders of subgroups of G Size(DuplicateFreeList(List([1..Size(SubsTom(TableOfMarks(G)))], i-> Size(RepresentativeTom(TableOfMarks(G), i))))); ## Number of missing subgroup orders of G Size(Difference(DivisorsInt(Size(G)), DuplicateFreeList(List([1..Size(SubsTom(TableOfMarks(G)))], i-> Size(RepresentativeTom(TableOfMarks(G), i)))))); ## Sum of the entries in the table of marks of G Sum(Sum(MarksTom(TableOfMarks(G)))); ## Sum of the diagonal entries in the table of marks of G Sum(WeightsTom(TableOfMarks(G))); ## Total number of subgroups of G Sum(List([1..Size(SubsTom(TableOfMarks(G)))], i-> MarksTom(TableOfMarks(G))[i][1]/WeightsTom(TableOfMarks(G))[i])); ## Number of incidences in the lattice of subgroups of G NrIncidenceTom:=function(tom) return Sum(Sum(ListN(MarksTom(tom),WeightsTom(tom), \/))); end; ## Number of incidences in the poset of conjugacy classes of subgroups of G Sum(MarksTom(TableOfMarks(G)), Size); ## Number of edges in the lattice of subgroups of G EdgesLattice:=function(tom) local edges, i, max, x; edges:=[]; for i in Reversed([1..Size(SubsTom(tom))]) do max:=MaximalSubgroupsTom(tom, i)[1]; Add(edges, MarksTom(tom)[i][1]/WeightsTom(tom)[i]*Sum(max, x->ContainedTom(tom, x, i))); od; return Sum(edges); end; ## Number of edges in the poset of conjugacy classes of subgroups of G EdgesPoset:=function(tom) local edges, i, max, x; edges:=[]; for i in Reversed([1..Size(SubsTom(tom))]) do max:=MaximalSubgroupsTom(tom, i)[1]; Add(edges, Size(max)); od; return Sum(edges); end; ## row indices in the table of marks of G of the maximal solvable subgroups of G PositionsMaxSolvableSubs:=function(tom) local subgroups, i, x, solpos, bucket, subs, allsol; subgroups:=[]; for i in [1..Size(SubsTom(tom))] do Add(subgroups, RepresentativeTom(tom, i)); od; allsol:=List(subgroups, x-> IsSolvableGroup(x)); solpos:=Positions(allsol, true); bucket:=[]; for x in solpos do subs:=ShallowCopy(SubsTom(tom)[x]); RemoveSet(subs, x); UniteSet(bucket, subs); od; return Difference(solpos, bucket); end; ## row indices in the table of marks of G of the maximal supersolvable subgroups of G PositionsMaxSupersolvableSubs:=function(tom) local subgroups, i, x, supsolpos, bucket, subs, allsupsol; subgroups:=[]; for i in [1..Size(SubsTom(tom))] do Add(subgroups, RepresentativeTom(tom, i)); od; allsupsol:=List(subgroups, x-> IsSupersolvableGroup(x)); supsolpos:=Positions(allsupsol, true); bucket:=[]; for x in supsolpos do subs:=ShallowCopy(SubsTom(tom)[x]); RemoveSet(subs, x); UniteSet(bucket, subs); od; return Difference(supsolpos, bucket); end; ## row indices in the table of marks of G of the maximal abelian subgroups of G PositionsMaxAbelianSubs:=function(tom) local subgroups, i, x, solpos, bucket, subs, allsol; subgroups:=[]; for i in [1..Size(SubsTom(tom))] do Add(subgroups, RepresentativeTom(tom, i)); od; allsol:=List(subgroups, x-> IsAbelian(x)); solpos:=Positions(allsol, true); bucket:=[]; for x in solpos do subs:=ShallowCopy(SubsTom(tom)[x]); RemoveSet(subs, x); UniteSet(bucket, subs); od; return Difference(solpos, bucket); end; ## row indices in the table of marks of G of the maximal cyclic subgroups of G PositionsMaxCyclicSubs:=function(tom) local subgroups, i, x, solpos, bucket, subs, allsol; subgroups:=[]; for i in [1..Size(SubsTom(tom))] do Add(subgroups, RepresentativeTom(tom, i)); od; allsol:=List(subgroups, x-> IsCyclic(x)); solpos:=Positions(allsol, true); bucket:=[]; for x in solpos do subs:=ShallowCopy(SubsTom(tom)[x]); RemoveSet(subs, x); UniteSet(bucket, subs); od; return Difference(solpos, bucket); end; ## row indices in the table of marks of G of the maximal nilpotent subgroups of G PositionsMaxNilpotentSubs:=function(tom) local subgroups, i, x, solpos, bucket, subs, allsol; subgroups:=[]; for i in [1..Size(SubsTom(tom))] do Add(subgroups, RepresentativeTom(tom, i)); od; allsol:=List(subgroups, x-> IsNilpotentGroup(x)); solpos:=Positions(allsol, true); bucket:=[]; for x in solpos do subs:=ShallowCopy(SubsTom(tom)[x]); RemoveSet(subs, x); UniteSet(bucket, subs); od; return Difference(solpos, bucket); end; ## Test whether or not a subgroup of the symmetric group corresponds to an atomic species IsAtomic:=function(grp, n) local ooo, ran, k, subs, par, h; ran:=[1..n]; ooo:=Orbits(grp, ran); if Length(ooo) = 1 then return true; fi; if 1 in List(ooo, Length) then return false; fi; for k in [1..Length(ooo)-1] do for subs in Combinations(ooo, k) do ##try using pairs of orbits, ie all pairs rather than all k comninations. par:=Union(subs); if Size(Action(grp, par))* Size(Action(grp, Difference(ran, par))) = Size(grp) then return false; fi; od; od; return true; end; ## Test whether or not a subgroup is connected on n points IsConnected:=function(K, n) local ooo, pairs, p, S, p1, p2, Kp, p1Kp, p2Kp, G, matrix, row, i, j, Ci, Cj; ooo:=Orbits(K, [1..n]); matrix:=IdentityMat(Size(ooo)); if Size(ooo) = 1 then return true;fi; for i in [1..Size(ooo)] do for j in [1..i-1] do S:=DirectProduct(SymmetricGroup(ooo[i]), SymmetricGroup(ooo[j])); p1:=Projection(S,1); p2:=Projection(S,2); Kp:=Action(K, Concatenation(ooo[i], ooo[j])); p1Kp:=Image(RestrictedMapping(p1, Kp)); p2Kp:=Image(RestrictedMapping(p2, Kp)); G:=DirectProduct(p1Kp, p2Kp); Ci:=Stabilizer(Kp, ooo[j], OnTuples); Cj:=Stabilizer(Kp, ooo[i], OnTuples); if not Size(Kp) = Size(G) then matrix[i][j]:=1;matrix[j][i]:=1;fi; od; od; for i in [1..Size(ooo)] do for j in [1..Size(ooo)] do if matrix[i][j] > 0 then matrix[i]:=matrix[i] + matrix[j];fi; od; od; return not 0 in matrix[1];; end;