More about subgroups

[Attention, this code is not included in the code site!]

My first try to compute the set of subgroups of a group was to compute the set of subsets and test which subsets that was groups. But Sym(4), the group of all permutations of 1234, has 16777216 subsets. My next thought was to divide the set of subsets P(S) into subsets of equal cardinality P(S,k). This works for small k but

|P(Sym(4),12)|=24!/((24-12)!*12!)=2704156.

Not very efficient thinking nor code so far! But even a blind dog can follow a track and I think that following algorithm is correct and "efficient":

1. set Subs={{123..}}, the set of the set of the identity
2. for each x in S include x in all sets in a copy of Subs and compute the set of subgroups generated by the sets in the copy
3. set Subs=Subs+copy (union)

Repetition of some set words and group words.

• fence ( x -- {x} ) and x could be an integer or a set
• nfence ( s -- s') any object in s' is a fenced object of s
• incl ( s x -- su{x}) the object x is included to s
• nincl ( s x -- s') the elements in s' is the sets that are elements of s where x is included
• generate ( s -- s') s' is the group generated by the permutations in s

A set on the stack is represented by a negative-counted bundle on the stack and the count specifies the number of integers in the bundle. A semiotic word foreach prepares for processing of the elements in a do-loop:

: foreach ( s -- x1...xn n 0 )

  ndup               \ s s  duplicates the bundle

  card               \ s n  computes n=|s|

  nip 0 ;            \ drop the bundle count and prepare for do loop

  

: ngenerate ( s -- s')

  0 >>yst            \ empty set on yst stack

  foreach            \ for each element in the set s

  do generate        \ the sets in s generates cyclic groups

     fence           \ fence the group

     yst>> union >>yst

  loop yst>> ;

Here s' is the set of groups generated by the sets of permutations that are elements of s.

And now finally the set of all subgroups

: psubs ( s -- s')
  over numb identity fence fence >>yst  \ {{123...}} pushed to yst
  foreach
  do >r yst>> ndup r> nincl ngenerate union >>yst
  loop yst>> ;

4 sym psubs cr set. 

{{1234},{2134,1234},{3412,1234},{4123,3412,2341,1234},{1423,1342,1234},{4213,3241,1234},{4321,1234},{3142,2413,4321,1234},{4231,1234},{1243,1234},{1324,1234},{4321,4231,1324,1234},{1432,1234},{1423,1342,1243,1324,1432,1234},{3214,1234},{4213,3241,4231,1243,3214,1234},{3412,1432,3214,1234},{2314,3124,1234},{2134,2314,1324,3214,3124,1234},{2431,4132,1234},{2134,2431,4231,1432,4132,1234},{2143,1234},{3421,4312,2143,1234},{3412,4321,2143,1234},{2134,1243,2143,1234},{2134,3412,3421,4312,4321,1243,2143,1234},{3412,3142,2413,4321,4231,1324,2143,1234},{4123,3412,2341,4321,1432,3214,2143,1234},{3412,4213,1423,1342,2314,2431,3241,4321,3124,4132,2143,1234},{4123,2134,3412,4213,1423,2341,3421,3142,4312,2413,1342,2314,2431,3241,4321,4231,1243,1324,1432,3214,3124,4132,2143,1234}}

The normal subgroups:

: pnsubs ( s -- s')
  ndup >>xst
  0 >>yst
  psubs foreach
  do ndup nxst@ pnormal
     if fence yst>> union >>yst else ndrop then
  loop nxstdrop yst>> ;

4 sym pnsubs cr set.
{{1234},{3412,4321,2143,1234},{3412,4213,1423,1342,2314,2431,3241,4321,3124,4132,2143,1234},{4123,2134,3412,4213,1423,2341,3421,3142,4312,2413,1342,2314,2431,3241,4321,4231,1243,1324,1432,3214,3124,4132,2143,1234}} ok

Some reflections and facts:

Any finite group is isomorphic to a subgroup of Sym(n) for some n. For all n>2, Sym(n) can be generated by two permutations. A consequence of the Structure Theorem for Abelian Groups, (a group where ab=ba for all a and b in the group) is that for any positive number m there is an Abelian group that can be generated by m but not by m-1 elements. So for n big enough, Sym(n) can be generated by 2 elements, but has subgroups needing m>2 generators.