OKlibrary  0.2.1.6
Transformations.hpp File Reference

On investigations regarding transformation semigroups. More...

Go to the source code of this file.

## Detailed Description

On investigations regarding transformation semigroups.

Todo:
Hypergraph transformations I
• Consider a natural number n >= 0, N = {1,...,n}, the powerset P = powerset(P), and the set MS_n =powerset(P) of all set-systems on N.
• Let c_0: MS -> MS be direct complementation: c_0(S) = P - S.
• Let c_1: MS -> MS be elementwise complementation: c_1(S): c_1(S) = { N - T : T in S }.
• Let s: MS -> MS be the closure under subsumption: s(S) = union_{T in S} powerset(T).
• What is the closure of {c_0, c_1, s} under composition?
• ```oklib_include("OKlib/ComputerAlgebra/Algebra/Lisp/Groupoids/Closures.mac")\$
oklib_include("OKlib/ComputerAlgebra/Algebra/Lisp/Groupoids/Semigroups/TransformationMonoids.mac")\$
oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/SetSystems.mac")\$
oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/HashMaps.mac")\$

det_cl(n) := block([N : setn(n), P, MS, c0, c0l, c1,c1l, s,sl, h, MSA, C],
P : powerset(N),
MS : powerset(P),
c0 : lambda([S], setdifference(P,S)),
c1 : lambda([S], ecomp(S,N)),
s : lambda([S], subset_closure(S)),
h : osm2hm(ll2osm(listify(MS),create_list(i,i,1,2^(2^n)))),
c0l : map(lambda([S],ev_hm(h,c0(S))), listify(MS)),
c1l : map(lambda([S],ev_hm(h,c1(S))), listify(MS)),
sl : map(lambda([S],ev_hm(h,s(S))), listify(MS)),
C : closure_bydef_grd(trf_l_compo, {c0l,c1l,sl}),
length(C)
)\$
create_list(det_cl(n),n,0,3);
[2,28,28,28]
```
• So it seems as soon as the base set contains at least one element, the closure contains exactly 28 elements. One now needs to determine them.
• The above transformations c0,c1,s in list-form are
```[3,4,1,2]
[1,4,3,2]
[1,2,3,3]
```
• In Gap:
```LoadPackage("monoid");
c0a := Transformation([3,4,1,2]);
c1a := Transformation([1,4,3,2]);
sa := Transformation([1,2,3,3]);
Ca := Monoid(c0a,c1a,sa);
GeneratorsOfMonoid(Ca);
[Transformation([3,4,1,2]),Transformation([1,4,3,2]),Transformation([1,2,3,3])]
Size(Ca);
28
Centre(Ca);
[ Transformation( [ 1, 2, 3, 4 ] ) ]
Idempotents(Ca);
[Transformation([1,1,3,1]),Transformation([1,1,3,3]),Transformation([1,1,3,4]),
Transformation([1,2,3,1]),Transformation([1,2,3,3]),Transformation([1,2,3,4]),
Transformation([1,3,3,1]),Transformation([1,3,3,3]),Transformation([1,3,3,4])]
```
• Finding a presentation:
1. First by using Gap directly:
```phi_Ca := IsomorphismFpMonoid(Ca);
FCa := Range(phi_Ca);
ma := GeneratorsOfMonoid(FCa);
sa = PreImageElm(phi_Ca, ma[1])[1];
c1a = PreImageElm(phi_Ca, ma[2])[1];
c0a = PreImageElm(phi_Ca, ma[3])[1];

# So m1 = sa, m2 = c1a, m3 = c0a.

RelationsOfFpMonoid(FCa);
[ [ m1^2, m1 ],
[ m2^2, <identity ...> ],
[ m3*m2, m2*m3 ],
[ m3^2, <identity ...> ],
[ m1*m2*m1*m2, m1*m2*m1 ],
[ m1*m2*m3*m1, m1*m2*m3 ],
[ m1*m2*m3^2, m1*m2 ],
[ m1*m3*m1*m2, m1*m3*m1 ],
[ m2*m1*m2*m1, m1*m2*m1 ],
[ m2*m1*m2^2, m2*m1 ],
[ m2*m1*m3^2, m2*m1 ],
[ m3*m1*m2^2, m3*m1 ],
[ m3*m1*m3*m1, m1*m3*m1*m3 ],
[ m3*m1*m3^2, m3*m1 ],

[ m1*m2*m1*m3*m1, m1*m2*m1*m3 ],
[ m2*m3*m1*m2*m1, m3*m1*m2*m1 ] ]
```
Note the consistent use of "monoid" here; it is also possible to use "semigroup" (possibly yielding a different representation), but then also a "semigroup" needs to be constructed.
2. These relations just translated:
```s^2 = s
c1^2 = id
c1 c0 = c0 c1
c0^2 = id
c1 s c1 s = s c1 s
s c0 c1 s = c0 c1 s
superfluous
c1 s c0 s = s c0 s
s c1 s c1 = s c1 s
superfluous
superfluous
superfluous
s c0 s c0 = c0 s c0 s
s c0 s c1 s = c0 s c1 s
s c1 s c0 c1 = s c1 s c0
superfluous
```
3. Now "bottom-up", trying to guess a complete set of relations.
4. Using three generators m[1] = c0, m[2] = c1, m[3] = s together with the four basic relations, expressing that c0,c1 are involutions which commute and that s is idempotent:
```f3 := FreeMonoid(3);
g := GeneratorsOfMonoid(f3);
r1 := [g[1]^2, g[1]^0];
r2 := [g[2]^2, g[2]^0];
r3 := [g[1]*g[2], g[2]*g[1]];
r4 := [g[3]*g[3], g[3]];
C0 := f3 / [r1,r2,r3,r4];
Size(C0);
??
```
5. Using the transversal-operator Tr = c0 s c1 and closure under superset-formation s' = c1 s c1, adding the relation Tr^2 = s':
```r5 := [(g[2]*g[3]*g[1])^2, g[2]*g[3]*g[2]];
C1 := f3 / [r1,r2,r3,r4,r5];
Size(C1);
??
```
(Note that Gap composes transformations from left to right.)
6. Adding s' s = s s':
```r6 := [ g[3]*g[2]*g[3]*g[2], g[2]*g[3]*g[2]*g[3] ];
C2 := f3 / [r1,r2,r3,r4,r5,r6];
Size(C2);
44
```
7. Adding c1 s c0 s = s c0 s:
```r7 := [ g[3]*g[1]*g[3]*g[2], g[3]*g[1]*g[3] ];
C3 := f3 / [r1,r2,r3,r4,r5,r6,r7];
Size(C3);
32
```
8. Adding s c0 s c0 = c0 s c0 s:
```r8 := [ g[1]*g[3]*g[1]*g[3], g[3]*g[1]*g[3]*g[1] ];
C4 := f3 / [r1,r2,r3,r4,r5,r6,r7,r8];
Size(C4);
28
```
9. So we got a representation with 8 equations; checking independence:
```Size(f3 / [r1,r2,r3,r4,r5,r6,r8]);
36
Size(f3 / [r1,r2,r3,r4,r5,r7,r8]);
32
Size(f3 / [r1,r2,r3,r4,r6,r7,r8]);
??
Size(f3 / [r1,r2,r3,r5,r6,r7,r8]);
28
Size(f3 / [r1,r2,r5,r6,r7,r8]);
??
Size(f3 / [r1,r3,r5,r6,r7,r8]);
??
Size(f3 / [r2,r3,r5,r6,r7,r8]);
??
```
So r4 is derivable.
10. The conjecture is that [r1,r2,r3,r5,r6,r7,r8] is a minimal system of equations (relations) representing C.
11. Trying the relations computed by Gap above:
```C16 := f3 / [ [ g[1]^2, g[1] ],
[ g[2]^2, g[2]^0 ],
[ g[3]*g[2], g[2]*g[3] ],
[ g[3]^2, g[2]^0 ],
[ g[1]*g[2]*g[1]*g[2], g[1]*g[2]*g[1] ],
[ g[1]*g[2]*g[3]*g[1], g[1]*g[2]*g[3] ],
[ g[1]*g[2]*g[3]^2, g[1]*g[2] ],
[ g[1]*g[3]*g[1]*g[2], g[1]*g[3]*g[1] ],
[ g[2]*g[1]*g[2]*g[1], g[1]*g[2]*g[1] ],
[ g[2]*g[1]*g[2]^2, g[2]*g[1] ],
[ g[2]*g[1]*g[3]^2, g[2]*g[1] ],
[ g[3]*g[1]*g[2]^2, g[3]*g[1] ],
[ g[3]*g[1]*g[3]*g[1], g[1]*g[3]*g[1]*g[3] ],
[ g[3]*g[1]*g[3]^2, g[3]*g[1] ],
[ g[1]*g[2]*g[1]*g[3]*g[1], g[1]*g[2]*g[1]*g[3] ],
[ g[2]*g[3]*g[1]*g[2]*g[1], g[3]*g[1]*g[2]*g[1] ] ];
Size(C16);
28
```
12. The last four relations can be left out without changing the size, but then removing the (new) last one increases the size to 32.
• To understand the monoid Ca, Prof. Mitchell proposes to use the function "DisplayEggBoxesOfSemigroup", which displays the eggbox diagram of the D-classes (strong orbits of the semigroup on itself by left and right multiplication) of the semigroup C.
Todo:
Hypergraph transformations Ib
• Now instead of closure under subset-formation we consider elimination of subsumed subsets.
• ```det1b_cl(n) := block([N : setn(n), P, MS, c0, c0l, c1,c1l, s,sl, h, MSA, C],
P : powerset(N),
MS : powerset(P),
c0 : lambda([S], setdifference(P,S)),
c1 : lambda([S], ecomp(S,N)),
m : lambda([S], min_elements(S)),
h : osm2hm(ll2osm(listify(MS),create_list(i,i,1,2^(2^n)))),
c0l : map(lambda([S],ev_hm(h,c0(S))), listify(MS)),
c1l : map(lambda([S],ev_hm(h,c1(S))), listify(MS)),
ml : map(lambda([S],ev_hm(h,m(S))), listify(MS)),
C : closure_bydef_grd(trf_l_compo, {c0l,c1l,ml}),
length(C)
)\$

heap_size : 3/2*10^9;
:lisp (ext:set-limit 'ext:heap-size \$heap_size)
oklib_monitor : true;

for i : 0 thru 4 do print(i, det1b_cl(i));
Current size of closure is  2
0 2
Current size of closure is  3
Current size of closure is  9
Current size of closure is  23
Current size of closure is  28
1 28
Current size of closure is  3
Current size of closure is  9
Current size of closure is  25
Current size of closure is  68
Current size of closure is  74
2 74
Current size of closure is  3
Current size of closure is  9
Current size of closure is  25
Current size of closure is  68
Current size of closure is  76
3 76
Current size of closure is  3
Current size of closure is  9
Current size of closure is  25
Current size of closure is  68
Current size of closure is  76
4 76
```
(where 28=2^2*7, 74=2*37, 76=2^2*19).
• So here the conjecture is that as soon as the base-set contains at least three elements, then the closure contains exactly 76 elements, and the monoids for different such base-sets are canonically isomorphic.
• See below for a direct Gap-presentation of these 3 transformations for n=3 (named c0,c1,m):
```Cb := Monoid(c0,c1,m);
Size(Cb);
76
```
• Finding a presentation:
1. First by using Gap directly:
```phi_Cb := IsomorphismFpMonoid(Cb);
FCb := Range(phi_Cb);
mb := GeneratorsOfMonoid(FCb);
m = PreImageElm(phi_Cb, mb[1])[1];
c1 = PreImageElm(phi_Cb, mb[2])[1];
c0 = PreImageElm(phi_Cb, mb[3])[1];

# So mb1 = m, mb2 = c1, mb3 = c0.

RelationsOfFpMonoid(FCb);
[ [ m1^2, m1 ],
[ m2^2, <identity ...> ],
[ m3*m2, m2*m3 ],
[ m3^2, <identity ...> ],
[ m1*m2*m1, m1*m2 ],
[ m1*m2*m3^2, m1*m2 ],
[ m2*m1*m2^2, m2*m1 ],
[ m2*m1*m3^2, m2*m1 ],
[ m3*m1*m2^2, m3*m1 ],
[ m3*m1*m3^2, m3*m1 ],
[ m1*m3*m1*m3*m1, m3*m1*m3*m1 ],
[ m1*m2*m3*m1*m2*m3*m1, m1*m3*m1*m2*m3*m1 ],
[ m2*m1*m3*m1*m2*m3*m1, m1*m3*m1*m2*m3*m1 ],
[ m3*m1*m3*m1*m2*m3*m1, m1*m3*m1*m2*m3*m1 ] ]
```
Todo:
Hypergraph transformations II
• Additionally, let m: MS -> MS be subsumption elimination: m(S) = {T in S : there is no T' in S with T < T'}.
• ```det2_cl(n) := block([N : setn(n), P, MS, c0, c0l, c1,c1l, s,sl, m,ml, h, MSA, C],
P : powerset(N),
MS : powerset(P),
c0 : lambda([S], setdifference(P,S)),
c1 : lambda([S], ecomp(S,N)),
s : lambda([S], subset_closure(S)),
m : lambda([S], min_elements(S)),
h : osm2hm(ll2osm(listify(MS),create_list(i,i,1,2^(2^n)))),
c0l : map(lambda([S],ev_hm(h,c0(S))), listify(MS)),
c1l : map(lambda([S],ev_hm(h,c1(S))), listify(MS)),
sl : map(lambda([S],ev_hm(h,s(S))), listify(MS)),
ml : map(lambda([S],ev_hm(h,m(S))), listify(MS)),
if oklib_monitor and oklib_monitor_level >= 1 then (
print("c0l = ",c0l),
print("c1l = ",c1l),
print("sl = ", sl),
print("ml = ", ml)
),
C : closure_bydef_grd(trf_l_compo, {c0l,c1l,sl,ml}),
length(C)
)\$

heap_size : 5*10^9;
:lisp (ext:set-limit 'ext:heap-size \$heap_size)
oklib_monitor : true;

for i : 0 thru 4 do print(i, det2_cl(i));

Current size of closure is  2
0 2

Current size of closure is  4
Current size of closure is  16
Current size of closure is  80
Current size of closure is  176
1 176

Current size of closure is  4
Current size of closure is  16
Current size of closure is  83
Current size of closure is  350
Current size of closure is  404
2 404

Current size of closure is  4
Current size of closure is  16
Current size of closure is  83
Current size of closure is  421
Current size of closure is  656
3 656

Current size of closure is  4
Current size of closure is  16
Current size of closure is  83
Current size of closure is  434
Current size of closure is  966
Current size of closure is  972
4 972
```
(where 176=2^4*11, 404=2^2*101, 656=2^4*41, 972=2^2*3^5).
• In Gap:
1. n=1:
```c0 := Transformation([3,4,1,2]);
c1 := Transformation([1,4,3,2]);
s := Transformation([1,2,3,3]);
m := Transformation([1,2,2,4]);
M1 := Monoid(c0,c1,s,m);
Size(M1);
176
```
2. n=2:
```c0 := Transformation([5,12,15,16,1,14,13,10,11,8,9,2,7,6,3,4]);
c1 := Transformation([1,14,15,8,5,12,7,4,11,16,9,6,13,2,3,10]);
s := Transformation([1,2,3,5,5,6,5,5,9,3,5,5,6,5,5,9]);
m := Transformation([1,2,2,2,2,2,2,2,2,10,10,13,13,14,16,16]);
M2 := Monoid(c0,c1,s,m);
Size(M2);
404;
```
3. n=3:
```c0 := Transformation([9,136,199,230,245,252,255,256,1,254,253,250,251,248,249,242,247,246,243,244,237,240,241,226,239,
238,235,236,233,234,227,232,231,228,229,214,221,224,225,194,223,222,219,220,217,218,211,216,215,
212,213,206,209,210,195,208,207,204,205,202,203,196,201,200,197,198,167,182,189,192,193,130,191,
190,187,188,185,186,179,184,183,180,181,174,177,178,163,176,175,172,173,170,171,164,169,168,165,
166,151,158,161,162,131,160,159,156,157,154,155,148,153,152,149,150,143,146,147,132,145,144,141,
142,139,140,133,138,137,134,135,72,103,118,125,128,129,2,127,126,123,124,121,122,115,120,119,116,
117,110,113,114,99,112,111,108,109,106,107,100,105,104,101,102,87,94,97,98,67,96,95,92,93,90,91,
84,89,88,85,86,79,82,83,68,81,80,77,78,75,76,69,74,73,70,71,40,55,62,65,66,3,64,63,60,61,58,59,52,
57,56,53,54,47,50,51,36,49,48,45,46,43,44,37,42,41,38,39,24,31,34,35,4,33,32,29,30,27,28,21,26,25,
22,23,16,19,20,5,18,17,14,15,12,13,6,11,10,7,8]);
c1 := Transformation([1,226,239,240,113,110,103,40,9,72,47,16,79,106,43,12,75,50,19,82,237,230,167,136,199,174,143,206,
233,170,139,202,177,146,209,112,109,102,39,8,71,46,15,78,105,42,11,74,49,18,81,236,229,166,135,
198,173,142,205,232,169,138,201,176,145,208,241,114,111,104,41,10,73,48,17,80,107,44,13,76,51,20,
83,238,231,168,137,200,175,144,207,234,171,140,203,178,147,210,99,108,101,38,7,70,45,14,77,100,37,
6,69,36,5,68,235,228,165,134,197,172,141,204,227,164,133,196,163,132,195,254,255,128,125,118,55,
24,87,62,31,94,121,58,27,90,65,34,97,252,245,182,151,214,189,158,221,248,185,154,217,192,161,224,
127,124,117,54,23,86,61,30,93,120,57,26,89,64,33,96,251,244,181,150,213,188,157,220,247,184,153,
216,191,160,223,256,129,126,119,56,25,88,63,32,95,122,59,28,91,66,35,98,253,246,183,152,215,190,
159,222,249,186,155,218,193,162,225,2,123,116,53,22,85,60,29,92,115,52,21,84,3,4,67,250,243,180,
149,212,187,156,219,242,179,148,211,130,131,194]);
s := Transformation([1,2,3,29,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,25,25,24,24,25,24,24,25,29,31,31,32,31,31,32,9,9,9,9,9,9,
9,9,9,9,9,9,9,9,9,9,59,56,55,55,56,55,55,59,60,62,62,63,62,62,66,29,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,
9,25,25,24,24,25,24,24,25,29,31,31,32,31,31,32,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,59,56,55,55,56,55,
55,59,123,125,125,126,125,125,129,3,29,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,25,25,24,24,25,24,24,25,29,
31,31,32,31,31,32,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,59,56,55,55,56,55,55,59,60,62,62,63,62,62,66,29,
9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,25,25,24,24,25,24,24,25,29,31,31,32,31,31,32,9,9,9,9,9,9,9,9,9,9,
9,9,9,9,9,9,59,56,55,55,56,55,55,59,123,125,125,126,125,125,129]);
m := Transformation([1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,130,130,130,130,187,187,190,190,191,
193,193,187,187,190,190,191,193,193,130,187,187,190,190,191,193,193,187,187,190,190,191,193,193,
130,130,187,187,190,190,191,193,193,187,187,190,190,191,193,193,130,187,187,190,190,191,193,193,
187,187,190,190,191,193,193,194,194,211,243,243,253,253,216,225,225,250,250,253,253,223,225,225,
211,243,243,253,253,216,225,225,250,250,253,253,223,225,225,226,242,243,243,253,253,247,256,256,
250,250,253,253,254,256,256,242,243,243,253,253,247,256,256,250,250,253,253,254,256,256]);
M3 := Monoid(c0,c1,s,m);
Size(M3);
656;
```
4. n=4: Now we need to compute the four transformations directly in Gap (instead of copy-and-paste them from Maxima, as above). Of course, we have now 2^16=65536 elements in the base-set, but this should be possible.

Definition in file Transformations.hpp.