Computing the length of a finite group

Question

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$?

Thanks in advance.

Answer 1

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( max`subgroup ) : 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( max`subgroup ) : 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.

Answer 2

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([$$(m`subgroup) : m in MaximalSubgroups(G)]);
 end function;

Answer 3

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( max`subgroup ) : 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;
      return tot;
    end if;
  end if;
end function;