## Monday, March 14, 2016

### Some groups

First, I have improved the word psubgroups. Stupidly enough it calculated the whole (known) group. Now it works 5-10 times faster and calculate the set of subgroups of Sym(4) in a second. To calculate the set of subgroups to Sym(5) takes about 30 minutes, though, so enhancements must still be made.

Now handling groups with order around 100 and subgroups of groups with order around 30 is okay. A little more with a fast system...

Some finite groups

\ cyclic group of permutations of 1...n
: cyc \ n -- | -- s
pcirc pgen ;

6 cyc zet. {(6,1,2,3,4,5),(5,6,1,2,3,4),(4,5,6,1,2,3),(3,4,5,6,1,2),(2,3,4,5,6,1),(1,2,3,4,5,6)} ok

\ symetric group of permutations of 1...n, n<6
: sym \ n -- | -- s
dup 2 >
if dup pcirc zfence proll zfence zmerge generate
else 2 = if ( 2 1 ) pgen else ( 1 ) pgen then
then ;

The n-th symmetry group is the set of all bijections of {1,...,n}.

4 sym cr zet.
{(4,2,3,1),(1,2,3,4),(1,3,4,2),(2,3,4,1),(2,4,3,1),(1,4,3,2),(2,1,3,4),(4,1,3,2),(3,4,1,2),(2,4,1,3),(3,4,2,1),(1,4,2,3),(3,1,4,2),(2,1,4,3),(3,2,4,1),(1,2,4,3),(4,3,1,2),(2,3,1,4),(4,2,1,3),(3,2,1,4),(4,3,2,1),(1,3,2,4),(4,1,2,3),(3,1,2,4)} ok

\ dihedral group of permutations of 1...n
: dih \ n -- | -- s
dup >r pcirc zfence
( 1 r> ?do i -1 +loop ) zfence
zetmerge generate ;

6 dih cr zet.
{(6,5,4,3,2,1),(6,1,2,3,4,5),(2,1,6,5,4,3),(2,3,4,5,6,1),(4,5,6,1,2,3),(4,3,2,1,6,5),(3,2,1,6,5,4),(3,4,5,6,1,2),(5,4,3,2,1,6),(5,6,1,2,3,4),(1,2,3,4,5,6),(1,6,5,4,3,2)} ok

There is also an other tradition where the dihedral group is denoted after the order of the group, but I think it's more consequent to denote it after the number of permutation elements.

Any permutation can be factorized in simple so called 2-cycles: (n m) where n maps to m and m maps to n. Example: (2,3,1)=(1 2)(1 3). 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.

\ alternating group of permutations of 1...n, n<6
: alt \ n -- | -- s   n>2
dup 3 = if drop ( 2 3 1 ) pgen exit then
dup 1 and
if >r
{ r@ pcirc
( r@ 2 - 1 do i loop r@ 1- r@ r> 2 - )
} generate
else >r
{ ( r@ 2 do i loop 1 r@ )
( r@ 2 - 1 do i loop r@ 1- r@ r> 2 - )
} generate
then ;

4 alt cr zet.
{(3,4,1,2),(3,1,2,4),(3,2,4,1),(4,1,3,2),(2,1,4,3),(1,3,4,2),(2,4,3,1),(1,4,2,3),(2,3,1,4),(4,3,2,1),(1,2,3,4),(4,2,1,3)} ok

\ quaternion group Q8={±1,±i,±j,±k} as group of permutations of 1..8
\ q8 \ -- s
: { ( 2 4 6 7 3 8 1 5 ) ( 3 5 4 8 7 2 6 1 ) } generate ;

### The product of two permutation groups given as a permutation group

\ extend, to the right, bijection v to permute n elements
: rext \ n -- | v -- v'
>r ( r> zst@ cs do i 1+ loop )
1 zst+! zswap 1 zst+! zswap zmerge -1 zst+! ;

\ extend to the left
: lext \ n -- | v -- v'
dup >r ( r> zst@ cs - 1+ 1 do i loop ) 1 zst+!
zswap zst@ tuck cs - loc{ x y }
1 zst+! foreach
do zst> y + loop x 1+ >>zst
zmerge -1 zst+! ;

\ extend all functions in a set to the right
: multirext \ n -- | s -- s'
0 >xst foreach
do dup rext zfence xzmerge
loop drop xst zst setmove ;

3 sym 4 multirext cr zet.
{(3,2,1,4),(1,2,3,4),(2,3,1,4),(1,3,2,4),(3,1,2,4),(2,1,3,4)} ok

\ extend all to the left
: multilext \ n -- | s -- s'
0 >xst foreach
do dup lext zfence xzmerge
loop drop xst zst setmove ;

5 cyc 6 multilext cr zet.
{(1,2,3,4,5,6),(1,3,4,5,6,2),(1,4,5,6,2,3),(1,5,6,2,3,4),(1,6,2,3,4,5)} ok

\ the product of two groups s and s'
: gprod \ s s' -- sxs'
ord zswap ord +
dup multirext zswap
multilext union generate ;

2 cyc zdup gprod zet. {(2,1,3,4),(1,2,3,4),(1,2,4,3),(2,1,4,3)} ok

3 cyc 4 alt gprod cr zet.
{(2,3,1,4,5,6,7,8,9,10,11,15,12,14,13),(2,3,1,4,5,6,7,8,9,10,11,15,14,13,12),(2,3,1,4,5,6,7,8,9,10,11,12,14,15,13),(2,3,1,4,5,6,7,8,9,10,11,13,14,12,15),(2,3,1,4,5,6,7,8,9,10,11,14,15,12,13),(2,3,1,4,5,6,7,8,9,10,11,13,12,15,14),(2,3,1,4,5,6,7,8,9,10,11,14,12,13,15),(2,3,1,4,5,6,7,8,9,10,11,13,15,14,12),(2,3,1,4,5,6,7,8,9,10,11,12,15,13,14),(2,3,1,4,5,6,7,8,9,10,11,14,13,15,12),(2,3,1,4,5,6,7,8,9,10,11,12,13,14,15),(1,2,3,4,5,6,7,8,9,10,11,12,14,15,13),(1,2,3,4,5,6,7,8,9,10,11,12,15,13,14),(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15),(1,2,3,4,5,6,7,8,9,10,11,14,15,12,13),(1,2,3,4,5,6,7,8,9,10,11,13,15,14,12),(1,2,3,4,5,6,7,8,9,10,11,15,12,14,13),(1,2,3,4,5,6,7,8,9,10,11,13,14,12,15),(1,2,3,4,5,6,7,8,9,10,11,15,14,13,12),(1,2,3,4,5,6,7,8,9,10,11,13,12,15,14),(1,2,3,4,5,6,7,8,9,10,11,14,12,13,15),(1,2,3,4,5,6,7,8,9,10,11,14,13,15,12),(3,1,2,4,5,6,7,8,9,10,11,12,14,15,13),(3,1,2,4,5,6,7,8,9,10,11,12,15,13,14),(3,1,2,4,5,6,7,8,9,10,11,12,13,14,15),(3,1,2,4,5,6,7,8,9,10,11,14,15,12,13),(3,1,2,4,5,6,7,8,9,10,11,13,15,14,12),(3,1,2,4,5,6,7,8,9,10,11,15,12,14,13),(3,1,2,4,5,6,7,8,9,10,11,13,14,12,15),(3,1,2,4,5,6,7,8,9,10,11,15,14,13,12),(3,1,2,4,5,6,7,8,9,10,11,13,12,15,14),(3,1,2,4,5,6,7,8,9,10,11,14,12,13,15),(3,1,2,4,5,6,7,8,9,10,11,15,13,12,14),(3,1,2,4,5,6,7,8,9,10,11,14,13,15,12),(2,3,1,4,5,6,7,8,9,10,11,15,13,12,14),(1,2,3,4,5,6,7,8,9,10,11,15,13,12,14)} ok

### Pseudo isomorphism test

\ the set of cyclic subgroups of the group s
: pcsubs \ s -- s'
0 >xst
foreach
do pgen zfence xzmerge
loop xst zst setmove reduce ;

\ flag true if not equal cardinality
: card<> \ -- flag | s s' -- s s'

zover cardinality zdup cardinality = 0= ;

\ sort a list of non-negative integers
: vect-sort \ v -- v'
set-sort zst> 1- > zst ;

\ compute vector of orders of all cyclic subgroups in s
: pscan \ s -- v
0 foreach do cardinality swap 1+ loop
sort 2* 1+ negate >zet ;

: pseudoiso \ -- flag | s s' --
card<>
if zdrop zdrop false exit then
pcsubs zswap pcsubs card<>
if zdrop zdrop false exit then
pscan zswap pscan vector= ;

4 dih pcsubs pscan zet. (1,2,2,2,2,2,4) ok
4 dih 8 cyc pseudoiso . 0  ok
3 sym 3 dih pseudoiso . -1  ok

Due to Mathematics Stack Exchange the psudoiso test holds for all subgroups of Sym(7) but already in Sym(8) there are counterexamples. A counterexample in Sym(16) is also:

4 cyc zdup gprod 2 cyc q8 gprod pseudoiso . -1  ok

#### 1 comment:

1. This comment has been removed by a blog administrator.