# Computing the length of a finite group

Can someone suggest a GAP or MAGMA command (or code) to obtain the length $l(G)$ of a finite group $G$, i.e. the maximum length of a strictly descending chain of subgroups in $G$?

-
Does the length depend on more than the composition factors? If so you just need a table for simple groups, but I don't think the length is known exactly (even for alternating groups if I recall correctly). – Jack Schmidt Jun 6 '12 at 17:58
I don't think so either, but it is precisely for simple groups that I want it. In my mind this is equivalent to asking for a path of maximal length in a directed graph (by looking at the subgroup lattice), but this problem is known to be generally hard. For relatively small cases brute force should work though. I'm just not sure how to ask either GAP or MAGMA to do this. – the_fox Jun 6 '12 at 18:24
Thanks to both Jack and Derek for their answers. Quick question: once you have defined a function in MAGMA, can you save it somehow so that there's no need to define it all over again whenever you start a new session? – the_fox Jun 7 '12 at 10:07
I use the "load" command for simple scripts, and "Attach" for things I spent more time on. I made an Attach-able version on my website. Download ms.uky.edu/~jack/2012-06-07-SubgroupLength.m and in magma Attach("SubgroupLength.m"). – Jack Schmidt Jun 7 '12 at 14:34
I'd like to raise an issue at this point: could it be that the length of a finite group $G$ is a good "recognizability" criterion for testing simplicity? For example it's not difficult to see that $l(PSL_2(2^n))=n+\Omega(2^n-1)+1$, so unless $2^n+1$ is a Fermat prime, you can always tell it apart from the soluble groups of the same order at least. – the_fox Jun 7 '12 at 16:58

I believe the length of the simple groups are not known in general, so this will require the groups involved to be small enough to do some brute force calculations.

Assuming the length is an invariant of the composition factors, we try an inductive approach for simple groups: l(G) = max( l(M) : M a maximal subgroup of G ) + 1. For composite groups, we just add up the lengths on the composition factors.

Since magma has large precomputed tables of maximal subgroups of groups (that have had errors), I recommend it for speed.

subgroupLength := function( grp )
len := $$; if #grp eq 1 then return 0; elif IsSolvable( grp ) then return &+[ pn[2] : pn in FactoredOrder( grp ) ]; elif IsSimple(grp) then return 1 + Max( { len( maxsubgroup ) : max in MaximalSubgroups( grp) } ); // else return &+[ len( groupForm( cf ) ) : cf in CompositionFactors( grp ) ]; else // use the series 1 < O_oo(O^oo(G)) < O^oo(G) < G top := SolvableQuotient( grp ); if #top gt 1 then bot := SolvableResidual( grp ); else top, _, bot := RadicalQuotient( grp ); end if; if #top gt 1 and #bot gt 1 then return &+[ len( part ) : part in [* top, bot *] ]; else // oh no! resort to Len return 1 + Max( { len( maxsubgroup ) : max in MaximalSubgroups( grp ) } ); end if; end if; end function;  This is much faster than Len above for Alt(8) but still slow on A5 wr A5 which has a large composite insoluble section. This would be fixed if one could convert the output of CompositionFactors to a form suitable as input for MaximalSubgroups. - I wrote a version using composition factors and a simple group cache. It is more complicated, but works on any group I've succeeded at calling CompositionFactors on. Download: ms.uky.edu/~jack/2012-06-07-SubgroupLength.m and then in magma use Attach("SubgroupLength.m") – Jack Schmidt Jun 7 '12 at 12:26 Just to get you started, here is a very short recursive Magma function to compute this. You could do something similar in GAP. Of course, it will only work in reasonable time for small groups. On my computer it took about 10 seconds to do A_8. To do better you would need to do something more complicated like working up through the subgroup lattice. It is not an easy function to compute exactly.  Len := function(G) if #G eq 1 then return 0; end if; return 1 + Max([$$(msubgroup) : m in MaximalSubgroups(G)]);
end function;

-
Do you have a function that converts the output of CompositionFactors back into something that one could use MaximalSubgroups on? That would allow handling some nastier composite maximal subgroups. – Jack Schmidt Jun 6 '12 at 20:33
You could call CompositionSeries and find some permutation representation of the quotients, which would probably work in this situation, because the simple groups involved will not be very big. – Derek Holt Jun 7 '12 at 19:34

Here is yet another version. It includes all of Jack's ideas, but it also uses a lazy way of adding up the lengths of the nonabelian composition factors. It performs much faster on example lie $A_5 \wr A_5$. I am sure it could be further improved!

subgroupLengthNew := function( grp )
len := ;
if #grp eq 1 then return 0;
elif IsSolvable( grp ) then return
&+[ pn[2] : pn in FactoredOrder( grp ) ];
elif IsSimple(grp) then return
1 + Max( { len( maxsubgroup ) : max in MaximalSubgroups( grp) } );
else
top := SolvableQuotient( grp );
if #top gt 1 then bot := SolvableResidual( grp );
else top, _, bot := RadicalQuotient( grp );
end if;
if #top gt 1 and #bot gt 1 then
return &+[ len( part ) : part in [* top, bot *] ];
else //add up over composition factors
tot := 0;
cs := CompositionSeries( grp ); //goes from top down
for i in [1..#cs-1] do
ind := Index( cs[i], cs[i+1] );
fac := Factorisation( ind );
if IsPrime( ind ) then tot +:= 1;
else
//nonabelian simple factor - get perm rep on Sylow normaliser
if i eq #cs-1 then I :=  cs[i];
else
_,pos := Max( [ f[1]^f[2] : f in fac ] );
S := sub< cs[i] | cs[i+1], Sylow(cs[i], fac[pos][1]) >;
I := CosetImage( cs[i], Normalizer( cs[i], S ) );
end if;
tot +:= len(I);
end if;
end for;
end if;
end if;
end function;

-