First, the code in the previous post about sets had to be enhanced. The bundle stack manipulation words have been replaced with more efficient coding and the xst/yst stacks has got 8 times more memory allocated. Still only very small sets (and groups) can be handled.

Also an other set operation is included:

**: nunion ( s -- s' )**

**ndup card nip 0 tuck ?do union loop ;**

that compute the union on all sets in the set s (which is supposed to have only sets as elements).

The permutations of a list of distinct symbols can be thought of as bijective functions: 52314 then represent the bijection where

1 maps to 5, 2 maps to 2, 3 maps to 3, 4 maps to 1 and 5 maps to 4.

The combination of two permutations, i.e. f=52314 and g=23451 is the composition of the corresponding bijections:

g◦f=23451◦52314=13425

1. composition of bijections are bijections

2. composition of functions is associative

3. the non permutation (i.e. 12345) is an identity to right and left

4. every permutation has a backward permutation (inverse)

To find the inverse of 52314, take the position of 1 to be the first figure 4, the position of 2 to be the next figure 42 etc: 42351.

Permutations was the kind of groups known to Évariste Galois when he developed his theory that showed that there was no general solution to solve fifth degree (or higher) equations by radicals, and thereby solved a problem standing for 350 years. Later on the concept of abstract groups was defined by the axioms:

It can be proved that any finite abstract group is virtually the same as (isomorphic to) some subset of permutations (Cayley's Theorem). Therefore, by using the figures 1 to 9 for permutations, positive numbers on the stack represent group elements in a concrete and simple way. Also in 32 bit systems 987654321 is a positive single integer.

The symmetric group Sym(S) is the group of all permutations (all bijections) of the elements in S. Here Sym(n) is the group of all permutations of n figures. Sym(9) has 9!=362880 elements and is far too big for the implementation in this blog. But several subgroups of Sym(9) can be studied.

The word

**numb**gives the number of figures in the permutation f

**: numb ( f -- n ) 0 <# #s #> nip ;**

and

**maps**is the action of f on i

**: maps ( i f -- j ) 0 <# #s #> drop + 1- c@ 48 - ;**

The composition of two permutations is given by

**: pcomp loc{ g f -- g◦f }**

**0 \ the start value**

**f numb 1+ 1**

do 10 * i f maps g maps +

do 10 * i f maps g maps +

**loop ;**

Given a permutation f, repeated compositions results in the serie

f, f◦f, f◦f◦f, ...

which because of the group axioms must repeat itself. If then

f◦...◦f = f (n times)

then composition with the inverse f' gives

f◦...◦f = e (n-1 times)

Each permutation f generates a cyclic group (f) and n-1 above is the order of that group - the number of permutations in the group. The word

**gen**generates the set of the elements of the cyclic group (g):

**: gen loc{ g -- f1...fn -n }**

**g dup numb ufaculty 1+ 1**

**do dup g pcomp dup g =**

**if drop i negate leave then**

**loop ;**

Now groups can be generated:

2345671 gen cr set.

{2345671,3456712,4567123,5671234,6712345,7123456,1234567} ok

The order of the cyclic group (2345671) is 7, a prime. It can be proved that the order of a subgroup must divide the order of it's main group. So the only subgroups of (2345671) are (1234567) and (2345671) itself. Also, this is why the do-loop in

**gen**is from 1 to m! where m is the number of figures: (g) is a subgroup of Sym(m). Though, the loop is left when

g◦...◦g = g (n times).

Some words to generate non cyclic groups:

**: prco ( s n -- s' )**

loc{ n } >>xst xst> abs 0 tuck

?do xst> n pcomp fence cup

loop ;

loc{ n } >>xst xst> abs 0 tuck

?do xst> n pcomp fence cup

loop ;

To generate right co-sets of a set of permutations

**prco**is used. A right co-set of a set s of permutations is the set of all permutations in s composed to the right with the permutation n. Given a set of permutations A={p1,...,pn} and a permutation p, then A◦r={p1◦p,...,pn◦p} is the right co-set:

{ 4231 2341 } 3412 prco cr set.

{3142,4123} ok

**: plco ( n s -- s' )**

>>xst { n } xst> abs 0 tuck

?do n xst> pcomp fence cup

loop ;

>>xst { n } xst> abs 0 tuck

?do n xst> pcomp fence cup

loop ;

Similar for the left co-set

**plco**. The word

**pset***computes the set of all combinations of all elements in two sets:

{f1,...fn}◦{g1,...,gm}={f1◦g1,...,fi◦gj,...,fn◦gm}

**: pset* ( s1 s2 -- s3 )**

>>xst >>yst yst> abs 0 tuck

?do nxst@ yst> prco cup

loop nxstdrop ;

>>xst >>yst yst> abs 0 tuck

?do nxst@ yst> prco cup

loop nxstdrop ;

{ 4312 2341 2314 } { 1234 3124 } pset* cr set.

{4312,4231,2341,1243,2314,1234} ok

The word

**pgr**checks if a set of permutations is a group:

**: pgr ( s -- flag )**

**ndup ndup pset* set= ;**

{ 4312 2341 2314 } { 1234 3124 } pset* pgr . 0 ok

The only thing that needs to be checked is that the composition of any two permutations in the set is a permutation in the set.

**s" 123456789" create id$ here swap dup allot move align**

**: identity ( n -- m )**

**>r 0. id$ r> >number drop 2drop ;**

The word

**identity**gives the identity permutation with n figures:

5 identity . 12345 ok

**: generate ( s -- s' )**

over numb identity incl

begin >>yst nyst@ nyst@ pset*

yst>> nover set=

until ;

over numb identity incl

begin >>yst nyst@ nyst@ pset*

yst>> nover set=

until ;

And now how to

**generate**non cyclic permutation groups:

{ 234561 321654 } generate cr ndup pgr . cr set.

-1

{654321,561234,456123,165432,543216,612345,345612,216543,432165,234561,321654,123456} ok

Given a subgroup H of G. Define G/H to be the set of all right co-sets H◦g where g is an element of G. Any right co-set in G/H has the same number of elements as H and the co-sets are an equivalence class division of G with o(G)=o(H)o(G/H).

Let G be the group generated by {234561,321654}, that is, G={654321,561234,456123,165432,543216,612345,345612,216543,432165,234561,321654,123456} and let H be the subgroup generated by 561234, that is H={561234,345612,123456}. Then G/H={{654321,216543,432165},{612345,456123,234561},{543216,165432,321654},{561234,345612,123456}}.

Now, if for all g in G it holds that H◦g=g◦H, then H is said to be a normal subgroup of G and then it holds for all co-sets that

(H◦a)◦(H◦b)=H◦(a◦b) and the co-sets forms a group G/H, a quotient group.

**: pnormal ( s s' -- flag )**

**true loc{ flag } nswap dup -1 =**

if ndrop ndrop true exit then

>>yst abs 0

do dup >r nyst@ plco nyst@ r> prco set= 0=

if false to flag then

loop nystdrop flag ;

if ndrop ndrop true exit then

>>yst abs 0

do dup >r nyst@ plco nyst@ r> prco set= 0=

if false to flag then

loop nystdrop flag ;

**: pquotient ( s s' -- s/s' )**

>>yst abs 0 dup >xst

do nyst@ plco fence xst>> union >>xst

loop nystdrop xst>> ;

>>yst abs 0 dup >xst

do nyst@ plco fence xst>> union >>xst

loop nystdrop xst>> ;

Now testing:

561234 gen n{ 234561 321654 }n generate pnormal . -1 ok

So G/H should be a group:

{ 234561 321654 } generate ndup cr set.

{654321,561234,456123,165432,543216,612345,345612,216543,432165,234561,321654,123456} ok

561234 gen ndup cr set.

{561234,345612,123456} ok

pquotient set. {{654321,216543,432165},{612345,456123,234561},{543216,165432,321654},{561234,345612,123456}} ok

{ 654321 216543 432165 } { 612345 456123 234561 } pset* cr set.

{321654,165432,543216} ok

Obviously the composition of the two co-sets is a co-set itself (the third set in G/H but with an other order. And the same should be true for any combination of co-sets.

Next some words to permute permutations:

**: circ$ { ad n -- }**

**ad n + 1- c@ ad dup 1+ n 1- move ad c! ;**

The permutation number at

*ad*is circular shifted one step rightward.

**: circ ( f -- g )**

**0 0 rot 0 <# #s #> 2dup circ$ >number drop 2drop ;**

1234567 circ . 7123456 ok

**circ/**prepare for partial shifts.

**: circ/ ( m n -- k r q )**

over swap

10 rot numb rot - **

tuck /mod ;

over swap

10 rot numb rot - **

tuck /mod ;

Partial shift of the n first numbers in the permutation m. The rightmost figures are left unchanged:

: lcirc ( m n -- m' )

circ/ circ

rot * + ;

Partial shift of the most rightward numbers in the permutation m, Where the n leftmost figures are left unchanged:

**: rcirc ( m n -- m' )**

circ/ swap circ swap

rot * + ;

circ/ swap circ swap

rot * + ;

These partial shifts are used to create some standard groups:

**: sym ( n -- s )**

dup 2 < if -1 exit then

identity dup 2 lcirc swap circ -2 generate ;

dup 2 < if -1 exit then

identity dup 2 lcirc swap circ -2 generate ;

5 sym set. {12453,21453,54321,43215,21543,54312,24531,14532,34215,23514,32514,25413,24153,32154,15432,14253,43125,13524,12543,42531,15423,52413,45312,45321,42153,35142,25143,54132,41532,34125,31524,35214,31254,35241,25431,25314,54231,24135,53124,53214,23154,53142,21534,51423,51432,41325,15324,41253,15243,52143,45132,45231,42135,35124,42315,41352,31245,32145,31542,31425,15342,14235,14325,13254,53241,12534,52431,21435,51324,52314,21354,51243,51342,41235,53421,42351,43251,32541,32415,25341,24315,14352,13245,23145,13542,12435,13425,12354,52341,24513,53412,43152,43521,32451,31452,35421,24351,34251,23541,23415,13452,14523,54213,43512,42513,35412,34152,34521,23451,25134,54123,41523,45213,34512,15234,52134,45123,21345,51234,12345} ok

This take some time, from 5 seconds on SP-Forth and more on the others.

Any permutation can be factorized in simple so called 2-cycles: (nm) where n maps to m and m maps to n. Example: 231=(12)(13). Certain permutations can be factorized in an even number of 2-cycles and some can not. The product of even permutations is of course an even permutation and those permutation forms a subgroup Alt(S) of Sym(S). Both Sym(S) and Alt(S) can be generated by two elements, while their subgroups might not.

**: alt ( n -- s )**

dup 3 < if drop 1 -1 exit then

dup 3 = if drop 231 gen exit then

dup 1 and

if identity dup 3 lcirc swap circ

else identity dup 3 lcirc swap 1 rcirc

then -2 generate ;

dup 3 < if drop 1 -1 exit then

dup 3 = if drop 231 gen exit then

dup 1 and

if identity dup 3 lcirc swap circ

else identity dup 3 lcirc swap 1 rcirc

then -2 generate ;

5 alt cr set.

{32154,52143,42135,43215,21543,13254,21435,21354,53241,15432,54321,41325,32541,15243,14235,24315,14352,13542,32415,51342,23514,25413,54132,52431,42351,43152,35142,43521,35421,25341,34125,24153,13425,12453,31524,51423,35214,54213,53412,41253,41532,31452,45231,34251,24531,23451,12534,15324,14523,52314,42513,45312,34512,23145,25134,53124,45123,31245,51234,12345} ok

**For some reason the system crash for 6 sym and 6 alt.**

**: psubs ( s -- s' )**

ndup card >r

powerset 0 excl drop

2 r> ** 1- 0 tuck

do >>yst generate fence yst>> union

loop ;

ndup card >r

powerset 0 excl drop

2 r> ** 1- 0 tuck

do >>yst generate fence yst>> union

loop ;

3 sym psubs cr set.

{{123},{132,123},{321,123},{213,123},{231,312,123},{132,321,231,213,312,123}} ok

A better way to do this is to use that all subgroups has orders that divide the order of the group and only create and test those subsets. I hope I can manage to do that later on.

A nice text book on elementary theory of finite groups

## No comments:

## Post a Comment