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
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 +
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:
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
>>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 ;
{ 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 ;
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 ;
: pquotient ( s s' -- s/s' )
>>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:
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/ ( m n -- k r q )
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 * + ;
These partial shifts are used to create some standard groups:
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 ;
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 ;
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