Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

3 Answers 3

up vote 4 down vote accepted

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.

share|improve this answer
1  
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
add comment

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;
share|improve this answer
    
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
add comment

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;
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.