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":

- set Subs={{123..}}, the set of the set of the identity
- 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
- 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>> ;

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:

{{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.

## No comments:

## Post a Comment