PARALLEL COMPUTING MINIMAL ∈cMaj{0,1}
5(PY)
ANDREAS WACHTEL
Depa amen o Acad´emico de Ma em´a icas, ITAM, M´exico
Abs ac . This da ase consis s o a (mos ly) pa allel Py hon code, i s documen a ion and i s esul s. The code is one o 3 independen implemen a ions
ha accompany he pape en i led “All minimal clones gene a ed by {0,1}- alued majo i y ope a ions on a i e-elemen se ”. Wi hin
he se o all cyclically symme ic majo i y ope a ions on he i e-elemen se A={0,1,2,3,4}wi h alues in {0,1}on injec i e iples, deno ed
cMaj{0,1}
5, he code iden i ies all ha gene a e a minimal clone. The lis o hese unc ions is educed up o an equi alence ela ion de ined by
conjugacy (isomo phisms).
Keywo ds. minimal clone, cyclic symme y, majo i y ope a ion, i e elemen se
Mos o he heo y which is implemen ed in unc ions wi hin his da a se is knowledge ha he au ho came o unde s and hanks o many
p i a e discussions abou he heo y wi h Mike Beh isch (au ho o [Beh14]) and Edi h Va gas-Ga c´ıa (au ho o [GHVG24]). The au ho is
no a seasoned expe in clones and was in i ed o de elop his independen code. Thus, implemen a ion de ails we e no discussed and he
code in his da a se is e y di e en om he codes de eloped by Mike Beh isch [Beh24] (in C++ and Py hon).
Now, in o de o simpli y he eade s unde s anding o he unc ions and he code, his documen con ains ac s he au ho came o
unde s and, as well as, some e e ences o o icial sou ces o hese. Mos o he ac s a e es ic ed o he e na y pa o a minimal clone
gene a ed by a “minimal” unc ion. Fo a smoo he in oduc ion o he opic, he in e es ed eade is e e ed o he a icle “Minimal Clones
– A minicou se”, see [Cs´a05]. A Spanish in oduc ion o clones, composi ions ha also men ions minimal clones is gi en in [GHVG24]. This
da a se compu a ionally iden i ies unc ions ( e na y cyclically symme ic {0,1}- alued majo i y ope a ions) ha on he se A={0,1,2,3,4}
gene a e a minimal clone. Fo smalle ca ie se s Awi h |A| ≤ 4 his p oblem has been sol ed wi h less es ic ions on he gene a o
unc ions. Fo ins ance, o |A|= 3 all minimal clones a e known [Cs´a83] and o |A|= 4 all minimal clones gene a ed by majo i y ope a ions
a e cha ac e ised in [Wal00].
E-mail add ess:[email p o ec ed].
The au ho g a e ully acknowledges suppo by he Asociaci´on Mexicana de Cul u a A.C.
1
2 ANDREAS WACHTEL
Con en s
De ini ions and he GOAL. 2
1. How o un he code and ead he esul s 3
1.1. Wha is needed 3
1.2. How o show and unde s and he esul s 4
1.3. How o ecompu e he esul s 5
2. The elimina ion p ocedu e 6
2.1. S ep 1 – Pa allel elimina ion o non-minimal 6
2.2. S ep 2 – Elimina ion o conjuga es 6
2.3. S ep 3 – Su icien minimali y es s 6
3. Theo y 7
3.1. Te na y pa s o clones 7
3.2. Te na y unc ions as in ege s 8
3.3. Rep esen ing he e e sed unc ion 8
3.4. A necessa y mono onici y condi ion 9
3.5. Conjuga ed unc ions 10
3.6. Clones 11
4. Lib a ies and iles 13
4.1. Func ions in hlib p og ess.py 13
4.2. Func ions in hlib TicToc.py 13
4.3. Func ions in lib in ege Bi Manipula ion.py 13
4.4. Func ions in lib uplePosi ionBij.py 13
4.5. Func ions in lib CSMO .py 13
4.6. Func ions in lib compose.py 14
4.7. Func ions in lib p ese e.py 15
4.8. Func ions in lib keepCandida es.py 16
4.9. Func ions in lib CSMO clones.py 17
4.10. Func ions in s ep2s.py 18
4.11. Func ions in s ep3p.py 19
5. Lis o iles 21
Re e ences 22
De ini ions and he GOAL.
The code is specialised in many ways o he i e-elemen se . We ha e o de ine a ew se s o unc ions be o e we can de ine he goal.
•Le A=5={0,1,2,3,4}be ou i e-elemen se .
•A iple (a, b, c)∈A3is called injec i e iple i a6=b6=c6=a.
•A e na y majo i y ope a ion :A3→Asa is ies (a, a, b) = (a, b, a) = (b, a, a) = a o all a, b ∈A.
The e o e, he majo i y p ope y o ixes i s alue o non-injec i e iples and only he alues on injec i e iples iden i y .
•A e na y majo i y ope a ion is {0,1}- alued on injec i e iples i (a, b, c)∈ {0,1} o all injec i e iples (a, b, c)∈A3.
•We de ine Maj{0,1}
5 o be he se ha con ains all {0,1}- alued e na y majo i y ope a ions on A.
PARALLEL COMPUTING MINIMAL ∈cMaj{0,1}
5(PY) 3
•A e na y unc ion ∈Maj{0,1}
5on A= 5 akes one alue in {0,1} o each injec i e iple (a, b, c)∈A3.Since |A|= 5 he e exis
5∗4∗3 = 60 di e en iples and he alues {0,1}o can be uniquely associa ed o a 60 bi in ege N .The e o e,
∈Maj{0,1}
5⇐⇒ N = 60 ∈MO :=0,1,...,260 −1.(1)
•An ∈Maj{0,1}
5is cyclically symme ic i (a, b, c) = (c, a, b) o all a, b, c ∈A.
•Le cMaj{0,1}
5:=n ∈Maj{0,1}
5: is cyclically symme ico.Applying he de ini ion a ew imes all ∈cMaj{0,1}
5sa is y
(a, b, c) = (c, a, b) = (b, c, a) and (c, b, a) = (a, c, b) = (b, a, c),(2)
whe e o e 2 independen alues o de ine all 6, i.e., he alues o ∈cMaj{0,1}
5a e uniquely de ined by a 60
3= 20 bi in ege N20
:
∈cMaj{0,1}
5⇐⇒ N20
= 20 ∈CSMO :=0,1,...,220 −1.(3)
This associa ion is no unique, as i depends on he o de o 20 injec i e iples which by eq. (2) may also di e in o de .
The goal: Find all minimal clones on Agene a ed by some ∈cMaj{0,1}
5.
1. How o un he code and ead he esul s
1.1. Wha is needed. The code is w i en (and was las un) in Py hon 3.9. The ollowing py hon lib a ies a e used:
numba, numpy, ime, mul ip ocessing, unc ools, scipy.spa se
Running he code (as desc ibed in Sec ions 1.2 and 1.3) equi es all .py iles lis ed in Sec ion 5 (Lis o iles).
4 ANDREAS WACHTEL
1.2. How o show and unde s and he esul s. O iginally we compu ed 26 minimal gene a o s ∈cMaj{0,1}
5.These may be ecom-
pu ed, see Sec ion 1.3 below. Howe e , in o de o sa e compu a ional ime (and ene gy) he 26 unc ions ha e been ha d-coded in he ile
show esul s.py in he unc ion called ge Minimals n5 AW. Running py hon show esul s.py o p in ing he ile show esul s. x , gi es
he ollowing ou pu which will be explained below he able:
show esul s. x
# OUTPUT o : py hon show_ esul s.py
Impo : In ege and bi -manipula ion (AW, 2024)
Impo : Tuple-posi ion-bijec ion (AW, 2024)
Impo : uples o CSMO (AW, 2024)
Impo : S ep 2 (conjuga es) (AW, 2024)
Resul s - Compa ibili y.
Bi and Tuple o de o Mike:
The 20 uples in he bi -o de o Mike:
[(0, 1, 2), (0, 1, 3), (0, 1, 4), (0, 2, 1),
(0, 2, 3), (0, 2, 4), (0, 3, 1), (0, 3, 2),
(0, 3, 4), (0, 4, 1), (0, 4, 2), (0, 4, 3),
(1, 2, 3), (1, 2, 4), (1, 3, 2), (1, 3, 4),
(1, 4, 2), (1, 4, 3), (2, 3, 4), (2, 4, 3)]
Hash alues o Mike, AW and alues a uples:
x 020304|030404|131414|24
y 111111|222233|222233|33
z 203040|304040|314141|42
-------------------------------------------
Mike, AW, minimal clones wi h 1 MO
0, 0 000000|000000|000000|00
20480, 65600 000000|000000|110000|00
94208, 196800 000000|000000|111100|00
94217, 197825 110000|000000|111100|00
258048, 459200 000000|000000|111111|00
258057, 460225 110000|000000|111111|00
258123, 462275 111100|000000|111111|00
258639, 466375 111111|000000|111111|00
Mike, AW, minimal clones wi h 8 MO
12289, 193 100000|000000|101000|00
28673, 65729 100000|000000|111000|00
61443, 65987 101000|000000|111010|00
61952, 70080 000001|000000|111010|00
94209, 196801 100000|000000|111100|00
126978, 197058 001000|000000|111110|00
126979, 197059 101000|000000|111110|00
126987, 198083 111000|000000|111110|00
389147, 198603 111000|100000|111110|10
258049, 459201 100000|000000|111111|00
258051, 459203 101000|000000|111111|00
258055, 459207 101010|000000|111111|00
258059, 460227 111000|000000|111111|00
258063, 460231 111010|000000|111111|00
258127, 462279 111110|000000|111111|00
Mike, AW, minimal clones wi h 16 MO
520199, 459719 101010|000000|111111|10
Mike, AW, minimal clones wi h 64 MO
520203, 460739 111000|000000|111111|10
520205, 460741 110010|000000|111111|10
how many unique minimal : 26
how many minimal : 296
The wo le mos columns o he able will be explained below (as hey depend on he code). Fo he momen , conside he igh mos pa o
he able, which is independen o he code. Each o he 20 ze os and ones in a ow shows which alue s= (x, y, z) a minimal ∈cMaj{0,1}
5
akes a he injec i e iple gi en in he column o he heade abo e s. The 26 ows o minimal a e sepa a ed by g oups, i.e., by how many
majo i y ope a ions belong o he e na y pa o he clone o . These 26 a e unique up o conjugacy, see Sec ion 3.5. The coun 296, a he
end, is he numbe o all minimal ∈cMaj{0,1}
5,including all conjuga es emo ed as discussed in Sec ion 3.5, some o which gene a e he same
clone and o he s isomo phic minimal clones.
PARALLEL COMPUTING MINIMAL ∈cMaj{0,1}
5(PY) 5
This code and he codes by Mike Beh isch [Beh24] ha e been de eloped independen ly. A he end, we ealised ha we used di e en injec i e
iples and o de s o he equi alence (3), which is possible due o eq. (2). This caused ha each o ou codes uses a di e en 20-bi in ege o
iden i y ∈cMaj{0,1}
5.In he able, he i s column shows he 20-bi in ege used in [Beh24] gi en in De ini ion 2. The second column shows
he 20-bi in ege used in his code, gi en by De ini ion 1.
De ini ion 1 (Hash- alue in his code).This code iden i ies ∈cMaj{0,1}
5and 20 =N20
∈CSMO gi en by:
N := 0
1
220+ 0
1
321+ 0
1
422+ 0
2
323+ 0
2
424+ 0
3
425+ 1
2
326+ 1
2
427+ 1
3
428+ 2
3
429
+ 2
1
0210 + 3
1
0211 + 4
1
0212 + 3
2
0213 + 4
2
0214 + 4
3
0215 + 3
2
1216 + 4
2
1217 + 4
3
1218 + 4
3
2219 .
(4)
This alue de ines all alues o a inc easing uples in he bi s 0..9 and he ones a dec easing uples in he bi s 10..19.
De ini ion 2 (Hash- alue used in [Beh24]).This associa ion iden i ies ∈cMaj{0,1}
5and N ∈CSMO gi en by:
N := 0
1
220+ 0
1
321+ 0
1
422+ 0
2
123+ 0
2
324+ 0
2
425+ 0
3
126+ 0
3
227+ 0
3
428+ 0
4
129
+ 0
4
2210 + 0
4
3211 + 1
2
3212 + 1
2
4213 + 1
3
2214 + 1
3
4215 + 1
4
2216 + 1
4
3217 + 2
3
4218 + 2
4
3219
(5)
This alue is buil upon he lexicog aphic o de o he used injec i e iples.
1.3. How o ecompu e he esul s. Running py hon compu e esul s.py ecompu es all minimal using he elimina ion p ocedu e is
summa ized in Sec ion 2. This may ake a while. Be o e unning he command one migh wan o check wha kind o ou pu o expec and
how long i ook on my compu e . These de ails a e con ained in he ile compu e esul s. x . As un- imes by hemsel es do no ell wha
o expec on ano he compu e , below I include my ha dwa e speci ica ions.
1.3.1. Ha dwa e speci ica ions. The imes we e measu ed using Linux as an ope a ing sys em (in ai plane mode) on a compu e wi h 8 GiB 1
o RAM and a CPU o ype In el Co e i5 (8 h gene a ion) wi h CPU-caches o le els {L1|L2|L3}and sizes {256 KiB |1 MiB |6 MiB}2.
1.3.2. Compu a ions a e no RAM c i ical. The la ges ec o occupied by he code in memo y, du ing some seconds, con ains 220 = 1 048 576
logical en ies which occupy app oxima ely 1 MiB – and his is only due o he pa alleliza ion. All o he ope a ions equi e a small amoun o
60 bi in ege s. In he wo s case, a pa o he clone o o less han 500 in ege s is gene a ed.
1Uni s: 1B= 1 by e = 8 bi s , 1 KiB = 210 by es , 1 MiB = 220 by es , GiB = 230 by es .
2The RAM and cache sizes a e esul s o he command “sudo lshw -class memo y”.
6 ANDREAS WACHTEL
2. The elimina ion p ocedu e
The comple e elimina ion p ocedu e is un as shown in Sec ion 1.3, bu in e nally i uns he s eps desc ibed in his sec ion.
2.1. S ep 1 – Pa allel elimina ion o non-minimal .The unc ion unS ep1 in he ile s ep1p.py goes in pa allel h ough all 220
unc ions ∈cMaj{0,1}
5and checks whe he each sa is ies some necessa y condi ions o minimali y. This s ep educes he numbe o
candida es om 220 o 540 unc ions ∈cMaj{0,1}
5,as can be seen in he esul s compu e esul s. x in line 18. The checks a e done by
pa allel ins ances o he unc ion 4.8.1 keepF20nc, which is desc ibed in Sec ion 4.8 (Func ions in lib keepCandida es.py).
Running py hon s ep1p.py also in okes he unc ion unS ep1. The esul s will be sa ed, p o ided he logical lag in line 68 is T ue.
2.2. S ep 2 – Elimina ion o conjuga es. The unc ion unS ep2 in he ile s ep2s.py elimina es conjuga es. P o ided he 540 emaining
unc ions om S ep 1 a e passed (o we e sa ed), hey a e educed o only 65 emaining ∈cMaj{0,1}
5,as can be seen in he esul s
compu e esul s. x in line 47. The heo y is desc ibed in Sec ion 3.5. This educ ion is done using he unc ions in s ep2s.py which a e
documen ed in Sec ion 4.10.
2.3. S ep 3 – Su icien minimali y es s. The unc ion unS ep3 in he ile s ep3p.py pe o ms su icien minimali y es s. P o ided he
65 emaining unc ions om S ep 2 a e passed (o we e sa ed), hey a e educed o he 26 minimal unc ions shown in Sec ion 1.2 o a he end
o he ile compu e esul s. x . The employed minimali y es 4.9.5 miniTes is desc ibed in Sec ion 4.9 (Func ions in lib CSMO clones.py).
Many o he lib a ies (see Sec ion 4) and a ew unc ions in s ep3p.py (see Sec ion 4.11) a e used o pe o m es s in he ollowing 2 le els:
L.1. A con ained unc ion named 4.11.4 indSmallClonesP calls a minimali y es (in pa allel) o he 65 emaining unc ions. The e
is a ha d-coded es ic ion on he size a clone is allowed o ha e, whe e o e his es iden i ies po en ially minimal clones ha con ain
1,8,16 o 18 majo i y ope a ions, elimina es non-minimal candida es and lea es some undecided cases. The lines 126–136 o he ile
compu e esul s. x show ha his akes less han 3 seconds, iden i ies 24 minimal unc ions and lea es 31 unclassi ied unc ions.
Be ween he lines 60 – 124 one can see ailed minimal es s o candida es whose e na y clone con ains 21 elemen s, i.e., 18 MO and 3
p ojec ions. All o hem ail because hey con ain a minimal e na y size-4 clone (1 MO and 3 p ojec ions).
L.2. A con ained unc ion named 4.11.5 indBigge ClonesP calls he minimali y es (in pa allel) o he emaining 31 unclassi ied unc ions
om Le el 1. The lines 172–186 o he ile compu e esul s. x show ha his akes abou 80 seconds, iden i ies 2 u he minimal
clones ha con ain 64 majo i y ope a ions and elimina es all emaining 29 candida es as non-minimal, 27 o hem gene a e a clone ha
con ains a smalle minimal one o size 11 (8 MO + 3 p ojec ions).
PARALLEL COMPUTING MINIMAL ∈cMaj{0,1}
5(PY) 7
3. Theo y
The ollowing sec ions con ain heo y ha jus i ies (pa ly) he comple eness o he code.
3.1. Te na y pa s o clones. The ollowing ac s abou clones al-
low he code o gi e comple e esul s and allow a signi ican educ ion
o compu a ions. In gene al, a clone is a se o unc ions ha con ains
all p ojec ions and is closed wi h espec o composi ion. Wi hin he
code we only conside he “ e na y pa ” o a clone gene a ed by a
unc ion ∈cMaj{0,1}
5and he ollowing 3 p ojec ions:
De ini ion 3. The e na y p ojec ions J(3)
Aa e he unc ions
e1, e2, e3:A3→Agi en by e1(x, y, z) = x, e2(x, y, z) = yand
e3(x, y, z) = z.
De ini ion 4. Le ∈cMaj{0,1}
5.Then, he e na y pa o a clone
gene a ed by , deno ed he ea e by h i, con ains he e na y p o-
jec ions J(3)
Aand all composi ions o wi h hese p ojec ions and
unc ions gene a ed by such composi ions.
P ope ies ela ed o he nex unc ion will educe compu a ions.
De ini ion 5. Gi en :A3→Ai s e e se ¯
is de ined as
¯
(a, b, c):= (c, b, a) o all a, b, c ∈A, ha is, ¯
e e ses he
o de o i s a gumen s be o e applying .
The nex lemma con i ms ha ¯
∈ h iand ∈¯
.
Lemma 6. Gi en an :A3→Ao i s e e se ¯
, we ha e
¯
= ◦(e3, e2, e1)and =¯
◦(e3, e2, e1).
P oo . The i s ela ion is ob ained om
¯
(a, b, c) = (c, b, a) = e3(a, b, c), e2(a, b, c), e1(a, b, c)
o all a, b, c ∈A. The second ela ion comes om
(a, b, c) = ¯
(c, b, a) = ¯
e3(a, b, c), e2(a, b, c), e1(a, b, c)
which also holds o all a, b, c ∈A.
Lemma 6 con i ms he equali y:
h i=e1, e2, e3, , ¯
, . . .=e1, e2, e3,¯
, , . . .=¯
(6)
Fo ∈cMaj{0,1}
5 he se h i=¯
may also con ain e na y
unc ions ha a e no cyclically symme ic. The nex lemma, see also
[Cs´a86, p. 54], gua an ees ha all non- i ial unc ions in h ibelong
o Maj{0,1}
5and whe e o e hese unc ion can s ill be ep esen ed by
60 bi s (and by ou code).
Lemma 7. I ∈cMaj{0,1}
5, hen h i ⊆ Maj{0,1}
5∪J (3)
A.
P oo . Since only case dis inc ions and de ini ions a e equi ed,
we only ske ch he s eps o p o e he esul . Fi s , one p o es
ha h∈Maj{0,1}
5and g1, g2, g3∈Maj{0,1}
5∪J (3)
A,always gi e
h◦(g1, g2, g3)∈Maj{0,1}
5∪J (3)
A.
Then, he only hing le o do is o cons uc an ∈cMaj{0,1}
5
ha sa is ies ◦(e1, e2, )∈Maj{0,1}
5, ha is, he cyclic symme y
ge s los due o some composi ions.
Gi en Lemma 7 and su icien ime (and RAM), he code is able
o gene a e he comple e e na y clone h i,because
h i ⊆ Maj{0,1}
5∪J (3)
A.(7)
Since minimal clones a e small hei e na y pa i s in o he RAM.
8 ANDREAS WACHTEL
3.2. Te na y unc ions as in ege s. The code sepa a es he subse cMaj{0,1}
5 om he comple e se Maj{0,1}
5.
3.2.1. Cyclically Symme ic MO. The code uses De ini ion 1 o ep esen s each ∈cMaj{0,1}
5as he ollowing 20-bi in ege 20 =N :
N := 0
1
220+ 0
1
321+ 0
1
422+ 0
2
323+ 0
2
424+ 0
3
425+ 1
2
326+ 1
2
427+ 1
3
428+ 2
3
429
+ 2
1
0210 + 3
1
0211 + 4
1
0212 + 3
2
0213 + 4
2
0214 + 4
3
0215 + 3
2
1216 + 4
2
1217 + 4
3
1218 + 4
3
2219 .
(4)
This alue de ines all alues o a inc easing uples in he bi s 0..9 and he ones a dec easing uples in he bi s 10..19.
Example: In bina y no a ion he leas bi s a e on he igh . Fo
ins ance 20 =N = 1024 + 8 = (00000 00001 00000 01000)2gi es
o each iple (gi en by he i s 3 en ies o a column) he alues:
x|4443443432 2111000000
y|3322322111 3322322111
z|2111000000 4443443432
1032|0000000001 0000001000
8193|0000001000 0000000001
3.2.2. Majo i y Ope a ions. The alues o ∈Maj{0,1}
5e al-
ua ed a he 60 injec i e iples also belong o {0,1}and
a e ep esen ed in he code using he bi s o a 60 -bi in-
ege 60 ∈MO :=0,1,...,260 −1.The associa ion o
iple and bi -posi ion is gi en by a bijec ion de ined by unc-
ions inside he lib a y lib uplePosi ionBij.py. Running
py hon lib uplePosi ionBij.py) shows bo h he iple-o de
and he bijec ion:
0 bi 2 uple(bi ) = (0, 1, 2) uple2bi ( uple) = 0
1 bi 2 uple(bi ) = (0, 1, 3) uple2bi ( uple) = 1
2 bi 2 uple(bi ) = (0, 1, 4) uple2bi ( uple) = 2
3 bi 2 uple(bi ) = (0, 2, 1) uple2bi ( uple) = 3
...
59 bi 2 uple(bi ) = (4, 3, 2) uple2bi ( uple) = 59
3.3. Rep esen ing he e e sed unc ion. By eq. (4) he code
s o es all alues o ∈cMaj{0,1}
5a inc easing iples in he bi s
0,...,9 and he ones a dec easing iples in he bi s 10,...,19.
The unc ion ¯
de ined as ¯
(x, y, z) = (z, x, y) , see De ini ion 5,
e e ses he iples. Hence, bi s can be swapped o cons uc ¯
, e.g.,
¯
0
1
2= 2
1
0=N [bi 10] and ¯
2
1
0= 0
1
2=N [bi 0].
In gene al, i we de ine wd = bi s 9,...,0 o and
bwd = bi s 19,...,10 o , hen we can w i e N =(bwd | wd)
and N¯
=( wd | bwd). Wi hin Py hon, his can be done by he
ollowing in ege -bi ope a ions:
N ba = ((N & 1023) << 10) + (N >> 10)
Fo example, i 20 = 1024 + 8, hen ¯
20 = 8 ∗1024 + 1.
3.3.1. Igno ing e e sed unc ions. One o he alues N and N¯
is smalle i 6=¯
. Since h i=¯
,see (6), he code igno es
he bigge hash- alue (i i is s ic ly bigge ), ha is, he code only
checks (necessa y) condi ions o
∈CSMO = 0,1,...,220 −1which sa is y N ≤N¯
(8)
Sa ings: Roughly 49.9% , because he numbe o N ∈CSMO ha
sa is y N > N ¯
is 29∗1023 <29∗1024 = 219.
PARALLEL COMPUTING MINIMAL ∈cMaj{0,1}
5(PY) 9
3.4. A necessa y mono onici y condi ion. The ollowing lemma
is he Lemma 17 (o ou wo k) es a ed o ease he implemen a ion.
The esul goes back o B´ela Cs´ak´any in [Cs´a86, Theo em 2, p. 56],
bu i can also be ound in [Wal07a, Rema k 1.10, p. 13], Wald-
hause ’s Ph. D. hesis.
Lemma 8. Le {0,1}(A, Ua={0,1, a}, Ub={0,1, b}whe e
a, b ∈A {0,1}and suppose ha ∈cMaj{0,1}
5gene a es a mini-
mal clone. Then (0,1, a)< (a, 1,0) and (0,1, b)> (b, 1,0) is
impossible.
Commen s on Lemma 8:
•Fo A={0,1,2,3,4}we only ha e 3 such subse s, ha is
{0,1,2},{0,1,3},{0,1,4}.
•The con aposi i e is: I (0,1, a)< (a, 1,0) and (0,1, b)>
(b, 1,0), hen is no minimal.
The nex lemma is a bi -wise e sion o Lemma 8 and e-
qui es he ollowing no a ion. Because o De ini ion 1 he al-
ues o a he inc easing iples T={(0,1,2),(0,1,3),(0,1,4)}
a e loca ed in he bi s 0,1,2 and he alues o a he de-
c easing iples {(2,1,0),(3,1,0),(4,1,0)}in he bi s 10,11,12.
In Py hon, we can ex ac hese bi s using inc = & 7
and dec = ( >> 10) & 7, ha is, we use a “bi shi ”
and a “bi wise-and &” wi h 7 = (111)2.Now, inc and
dec a e in ege s be ween 0 and 7, because each belongs o
{000,001,010,011,100,101,110,111}.
Lemma 9 (The bi wise Waldhause condi ion).We ha e
(a) min( inc, dec ) >= inc & dec and
(b) i min( inc, dec ) > inc & dec, hen is no minimal.
P oo . (a) Follows om he ac ha he bi wise-and only keeps some
o he bi s ha a e sha ed by he minimum and he o he alue.
To p o e (b), no e ha dec = inc implies ha
min( inc, dec ) = dec = inc = dec & inc. The e o e,
w.l.o.g. we suppose dec > inc and inc > inc & dec. Then,
due o inc > inc & dec, he e exis s a bi in {0,1,2}in inc
ha is one bu he same bi is ze o in dec. Thus, he e exis s
a iple (0,1, a) such ha (0,1, a) = 1 >0 = (a, 1,0).Addi-
ionally, because o dec > inc we ge ha dec has a bi se
whe e inc has no . Thus, he e exis s a iple (0,1, b) such ha
(0,1, b)=0<1 = (b, 1,0).By Lemma 8 he exis ence o hese
iples con adic s ha is minimal. An analogous a gumen wo ks
i dec < inc.
The con aposi i e o Lemma 9 gi es he ollowing condi ion:
is minimal =⇒min( inc, dec ) == inc & dec.(9)
This necessa y condi ion is checked inside lib keepCandida es.py
in a unc ion called keepCsakanyWaldhause .
16 ANDREAS WACHTEL
4.8. Func ions in lib keepCandida es.py.I is known ha a
composi ion o a unc ion ne e p ese es less subse s U⊂A
han i sel , see [PK79, Sa z 1.1.15, p. 48]. This is es ed in many
ou ines o his lib a y, as i is a necessa y condi ion o co ec ness
o he implemen a ion o composi ions. I is also known, ha i a
composi ion ho p ese es mo e subse s U⊂A han i sel ,
hen is no minimal, see [Cs´a05, Sec ion 3, p. 76] and can be
disca ded om he lis o candida es o minimal gene a o s.
This lib a y con ains unc ions ha e i y hese and o he nec-
essa y condi ions o educe he lis o candida es o minimal clone
gene a o s. The main unc ion is keepF20nc.
4.8.1. keepF20nc.This unc ion is called in pa allel ins ances.
Gi en an 20 ∈CSMO, he 20 uples o ge TuplesCS, and he
esul s o ge Us n5, his cen al unc ion uni es he esul s o all
implemen ed necessa y condi ions ( he unc ions below) ha allow
o decide whe he o keep 20 as a minimal candida e.
4.8.2. keepLE.Gi en an 20 ∈CSMO, his unc ion decides
whe he o analyse 20 o o disca d i , see Sec ion 3.3.1.
4.8.3. keepCsakanyWaldhause .Gi en an 20 ∈CSMO, his unc-
ion decides whe he 20 passes condi ion (9), see Sec ion 3.4.
4.8.4. keepF60.Gi en an 60 ∈MO and he esul s o ge Us n5,
his unc ion e u ns ue i ce ain composi ions o 60,e.g. h•, h@
gene a ed by bulle g,a oba g and he labeled con inued ix-
poin s illus a ed below, p ese e he same subse s U⊂Aas 60.
The non-labeled ixpoin s a e commen ed ou in he code, because
hey did no emo e mo e candida es.
h•
h•∗
s a g
h•@
h•@∗
s a g
a oba g
bulle g
h@
h@∗
s a g
a oba g
4.8.5. keepF60complica ed.Gi en an 60 ∈MO and he esul s o
ge Us n5, his unc ion e u ns ue i a lo o composi ions o 60
p ese e he same subse s U⊂Aas 60 i sel . In he e a small pa
o he e na y unc ions om h 60iis gene a ed, using he unc ion
called closeF cs wi h bigN = 5, see Sec ion 4.9 o de ails.
PARALLEL COMPUTING MINIMAL ∈cMaj{0,1}
5(PY) 17
4.9. Func ions in lib CSMO clones.py.This lib a y implemen s
gene al (non-specialised) composi ions, clone-closing algo i hms (de-
sc ibed in Sec ion 3.6) and he su icien minimali y es gi en by he
igh -hand-side o he ollowing equi alence:
h iOAis minimal ⇐⇒ ∀h∈ h i J(3)
Awe ha e ∈ hhi.(11)
This equi alence is aken om [Wal07b, Theo em 2.1].
4.9.1. checkP ese edU.Gi en g60 ∈MO,a logical ec o
p ese es ha s a es which o he 8 in e es ing subse s (10) a e
p ese ed by , he esul s o ge Us n5 and a name o a composi-
ion unc ion, his unc ion e i ies whe he g60 p ese es he same
subse s as . Addi ionally, he unc ion checks ha g60 p ese es
all subse s p ese ed by , which is necessa y o he co ec ness o
implemen a ion o he composi ion.
4.9.2. compose gen.Gi en ∈MO and g1, g2, g3∈MO ∪ J (3)
A
whe e J(3)
A={−3,−2,−1}and each nega i e numbe iden i ies a
p ojec ion, see Sec ion 3.6.3, his unc ion e u ns he 60-bi in e-
ge ep esen ing he composi ion ◦(g1, g2, g3)∈MO,acco ding o
Lemma 7. The esul canno be a p ojec ion, as his is no imple-
men ed, whe e o e he calle mus ensu e ha he h ee unc ions
g1, g2, g3do no con ain he same p ojec ion wice.
4.9.3. closeF cs.Gi en a lis F= [e1, e2, e3, 60] wi h a cycli-
cally symme ic 60 ∈MO, he esul s o ge Us n5 and an up-
pe bound bigN, his unc ion gene a es hFio a pa o i as a
lis Fc o 60-bi in ege s, using Algo i hm 3.1 wi h he enume a-
ion desc ibed in Sec ion 3.6.4. Fo a gi en bound bigN he lis
Fc will a mos ha e bigN + bigN*(bigN-1)*(bigN-2)/3 en ies,
which ollows because he lis F= [ 1, . . . , bigN] may gene a e up
o bigN*(bigN-1)*(bigN-2)/3 addi ional composi ions because 60
is cyclically symme ic, see Sec ion 3.6.2. The unc ion e u ns he
pai (keep,Fc), whe e Fc is he lis men ioned ea lie and keep is
T ue i all unc ions in he lis Fc p ese e he same (and no mo e)
subse s as 60.
The ollowing is used ou side (in S ep 3): I len(Fc) ≤bigN,
hen he closing was comple ed and abusing no a ion we hink o
Fc =hFi,because Fc is a disc e e ep esen a ion o hFi.
4.9.4. ind F in clone h.Gi en a lis F h = [e1, e2, e3, h60] wi h
ah60 ∈MO,and a cyclically symme ic 60-bi 2b ound ∈MO,
his unc ion decides whe he 2b ound belongs o he e na y unc-
ions in hF hiwhose size is limi ed by a gi en pa ame e bigN wi h
de aul alue 18. This is done using Algo i hm 3.1 wi h he enume -
a ion desc ibed in Sec ion 3.6.4 and he modi ica ion ha line 7 adds
6 composi ions, because h60 is no necessa ily cyclically symme ic.
The esul ound is T ue i 2b ound was ound, o he wise i may
be False i he clone hF hiwas closed wi hou con aining 2b ound
o None i he clone hF hiwas incomple e due o he size es ic ion.
4.9.5. miniTes .Gi en a e na y pa o a clone h ias a lis o
60-bi in ege s Fo g = [e1, e2, e3, 60, h1, . . . , hm] his unc ion imple-
men s he su icien minimali y es gi en by equi alence (11), ha
is, o each hi he unc ion ind F in clone h is called o e i y
whe he 60 belongs o hhii.Na u ally, his is expensi e, as hese
mclones ha e o be gene a ed o con i m ha h iis minimal. This
unc ion p in s ou ha i is “cheap” i m= 1.The e u n alue is
ei he T ue o False.
18 ANDREAS WACHTEL
4.10. Func ions in s ep2s.py.The unc ions in he e allow o cal-
cula e conjuga es and educe a lis o unc ions o a subse o unique
conjuga es as desc ibed in Sec ion 3.5.
4.10.1. bi s a e phi.Gi en a pe mu a ion φ:A→Aas an a -
ay pe m, his unc ion gene a es ano he a ay which maps a posi-
ion bi (a, b, c)∈ {0,1,...,59} o a posi ion bi φ(a), φ(b), φ(c)∈
{0,1,...,59},i.e. he posi ion a e he pe mu a ion φ. This bijec-
ion elies on he unc ions uple2bi and bi 2 uple. This a ay
will be used o es ablish he equali y gi en in De ini ion 10 bu in
he o m: φg60bi (a, b, c) = 60bi φ(a), φ(b), φ(c).The a ay
does no change o a gi en φ, so i can be eused o calcula e φ-
conjuga es o many 20 ∈CSMO.
4.10.2. calcConjuga e.Gi en an in ege 20 ∈CSMO, he esul s
o ge TuplesCS, o ge Map20in60, o bi s a e phi (which gi es
φimplici ly as an a ay) and φ(0) as an in ege , his unc ion e-
u ns g20 :=φ−1◦ 20 ◦(φ, φ, φ).Inside he unc ions ge CSMO60d
and educe60 o20 a e used.
4.10.3. keepFisoSP.Gi en a lis o unc ions candFsp, he se
A={0,1,2,3,4}and a bijec ion φ:A→Aas an a ay phi,
his unc ion calcula es he conjuga es g, ¯g o each 20 in he lis
candFsp and elimina es hem om his lis . In o de ensu e ha
20 emains in he lis , his is no done in pa allel. Inside he unc-
ions ge TuplesCS,ge Map20in60 and bi s a e phi a e used.
4.10.4. ge Pe mu a ions n5.This unc ion e u ns he non-
iden i y pe mu a ions in he se Sym{0,1}
A o A={0,1,2,3,4},see
De ini ion 11, which a e gi en by he ollowing 11 ha d-coded non-
iden i y pe mu a ions in o m o a ays [φ(0), φ(1), . . . , φ(4)] and
hei desc ip ions: (23),(24),(34),(234),(432),(01),(01)(23),
(01)(24),(01)(34),(01)(234),(01)(432) .
4.10.5. ge Conjuga es.Gi en 20 ∈CSMO and he i e-elemen
se A={0,1,2,3,4}, his unc ion gene a es he se o all in e es ing
conjuga es o 20,i.e., he se [[ 20]] om De ini ion 12. This is done
using he pe mu a ions gi en by he unc ions ge Pe mu a ions n5
and he unc ion calcConjuga e.
4.10.6. elimina eConjuga es.This in e nal unc ion de ines all
pe mu a ions φusing ge Pe mu a ions n5, and elimina es conju-
ga es g, ¯g o all 20 om he a gumen candF using he unc-
ion keepFisoSP.
4.10.7. unS ep2.This unc ion accep s 2 op ional a gumen s,
candF and a boolean sa e esul s. I candF is no p esen , hen
he esul s o S ep 1 (see Sec ion 2.1) a e loaded, o he wise candF
should con ain simila da a in he same o m. A e ha , he unc-
ion elimina eConjuga es is used.
Finally, each 20 in candF will be he smalles and only 20-bi -
in ege le om he equi alence class [[ 20]] gi en in De ini ion 12.
This is done o achie e compa able esul s.
PARALLEL COMPUTING MINIMAL ∈cMaj{0,1}
5(PY) 19
4.11. Func ions in s ep3p.py.The unc ions in he e pe o m su -
icien and necessa y es s o decide whe he each emaining can-
dida e ( om s ep 2) is minimal. Many non-minimal unc ions a e
elimina ed by selec ing o cons uc ing a special h∈ h isuch ha
6∈ hhiwhich by (11) jus i ies ha is no minimal. In hese cases
he unc ion 4.9.5 miniTes is called wi h only {e1, e2, e3, , h}and
ails, as expec ed.
4.11.1. isMinimal 3WL.This in e nal unc ion akes 20 ∈CSMO
ep esen ing ∈cMaj{0,1}
5and wo op ional a gumen s, knownMC a
se uni ing majo i y ope a ions ha belong o smalle known minimal
clones and an in ege uppe N o limi he size o he gene a ed pa
o h i.Inside, he esul (keep,Fc) gene a ed by 4.9.3 closeF cs
is decomposed as ollows.
I keep is False, hen closeF cs ound a composi ion ho ha
ails a necessa y condi ion and 20 is no minimal and his unc ion
e u ns wi h ( 20, False, 0).
In he emaining si ua ions keep is T ue and all (so a ) gene a ed
composi ions ho p ese e he same subse s as , whe e o e he
second esul is sepa a ed in o 3 cases:
•I he e exis s hwi hin he in e sec ion o Fc and knownMC, hen
he miniTes wi h {e1, e2, e3, , h}will ail, and his unc ion
e u ns ( 20, False, 0).
•I len(Fc) ≤uppe N, hen miniTes is called using Fc,
which ep esen s h i.This es may pass o ail wi h e-
sul keep ∈ {T ue, False}.Then, his unc ion e u ns
( 20, keep, len(Fc)).
•O he wise, i len(Fc) >uppe N, he unc ion e u ns
( 20, None, 0), and None signals o pos pone he decision.
4.11.2. uni eClonesWi h8MO.Gi en a lis miniGene a o s o in-
ege s ep esen ing some 20 ∈cMaj{0,1}
5, his in e nal unc ion gen-
e a es o each 20 in he lis all conjuga es (wi h ge Conjuga es)
and hei clones (wi h closeF cs) and uni es all con ained majo i y
ope a ions in o one se which is e u ned as a esul .
4.11.3. las SpecialTes .Gi en he emaining candida es as
candF and a lis o in ege s no Classi ied his in e nal unc ion
akes each 20 in no Classi ied, which ep esen s ∈cMaj{0,1}
5,
hen o ms he g een-highligh ed ix-poin h•@∗(see Sec ion 4.8.4)
and calls he ind F in clone h wi h he lis F h = [e1, e2, e3, h•@∗],
N as 2b ound and bigN = 67. I is e i ied ha his es e-
u ns False, which jus i ies ha 6∈ hh•@∗iand con i ms ha is
no minimal, see equi alence (11). The co esponding 20 a e hen
emo ed om candF and he upda ed candF is e u ned.
4.11.4. indSmallClonesP.This in e nal unc ion equi es he min-
imal candida es in o m o he a gumen candF.
Inside, in pa allel, o each candida e 20 in candF he unc-
ion isMinimal 3WL is called wi h uppe N = 21. A e all calls ha e
inished, he esul s a e in memo y in a lis con aining he iples
( 20, decision, len(Fc)) whe e each decision akes one o he
alues {T ue, False, None}.Each iple is spli , in o de o decide
wha o do wi h he 20.I decision is None, hen 20 is pu in o
a lis no Classi ied. I False, hen 20 is emo ed om candF.
I T ue, he hi d esul len(Fc) is used o classi y he ound mini-
mal clones by hei sizes 4,11,19, his coun includes 3 p ojec ions.
The upda ed candida es candF, lis s o minimal unc ions and he
no Classi ied lis a e e u ned o epo ing.
20 ANDREAS WACHTEL
4.11.5. indBigge ClonesP.This in e nal unc ion equi es he e-
sul s candF, clone11, no Classi ied o indSmallClonesP as i
con inues he decision p ocess o he no classi ied candida es.
The concep o his unc ion is he same as indSmallClonesP,
bu i calls he unc ion isMinimal 3WL wi h uppe N = 67 and wi h
knownMC = h11 whe e h11 is a se ha uni es all majo i y ope a-
ions gene a ed by uni eClonesWi h8MO ( clone11 ).
Once he pa allel ins ances o isMinimal 3WL ha e inished, he
code analyses he lis o iples ( 20, decision, len(Fc)) whe e
each decision belongs o {T ue, False, None}.The same deci-
sion p ocess is made, None means no Classi ied,False emo es
20 om candF and T ue classi ies a minimal clone (in his case only
clones o size 67), all o he sizes ail o be minimal.
A e his sepa a ion one unc ion emained no Classi ied and
was con i med o be no minimal by in oking las SpecialTes .
Finally, he upda ed candida es candF and clones67 a lis o
minimal unc ions a e e u ned o epo ing.
4.11.6. unS ep3.This unc ion has he op ional a gumen candF.
I candF is no p esen , hen he esul s o S ep 2 (see Sec ion 4.10)
a e loaded, o he wise candF should con ain simila da a in he same
o m.
This unc ion calls he unc ions men ioned in Sec ion 2.3 and does
all epo ing o he sc een.
I he esul s o S ep 2 we e sa ed p e iously, hen unning
py hon s ep3p.py in okes he unc ion unS ep3, he compu a-
ions a e un and he epo ing is pe o med.
PARALLEL COMPUTING MINIMAL ∈cMaj{0,1}
5(PY) 21
5. Lis o iles
•show_ esul s.py – Py hon sc ip ha shows ha d-coded e-
sul s (minimal unc ions), documen ed in Sec ion 1.2.
•show_ esul s. x
Ou pu log o unning he sc ip show_ esul s.py. Line-
b eaks and emp y lines we e added o show he ou pu in Sec-
ion 1.2.
•compu e_ esul s.py – Py hon sc ip ha ecompu es he
minimal unc ions. I is documen ed in Sec ion 1.3.
•compu e_ esul s. x
Ou pu log o unning he sc ip compu e_ esul s.py
•s ep1p.py – In e nal Py hon sc ip ha implemen s S ep 1 ( e-
duces candida es by checking necessa y condi ions), documen ed
in Sec ion 2.1.
•s ep2s.py – In e nal Py hon sc ip ha implemen s S ep 2
(elimina es candida es i hey a e conjuga ed), documen ed in
Sec ions 2.2, 3.5 and 4.10.
•s ep3p.py – In e nal Py hon sc ip ha implemen s S ep 3
( e i ies su icien condi ions o minimali y), summa ized in Sec-
ion 2.3 and documen ed in Sec ion 4.11.
•hlib_p og ess.py – see Sec ion 4.1.
•hlib_TicToc.py – see Sec ion 4.2.
•lib_in ege Bi Manipula ion.py – see Sec ion 4.3.
•lib_ uplePosi ionBij.py – see Sec ion 4.4.
•lib_CSMO .py – see Sec ion 4.5.
•lib_compose.py – see Sec ion 4.6.
•lib_p ese e.py – see Sec ion 4.7.
•lib_keepCandida es.py – see Sec ion 4.8.
•lib_CSMO_clones.py – see Sec ion 4.9.
•docu.pd – This documen a ion.
•docu. ex – L
A
T
EX sou ce ile o gene a e his documen a ion.
This also uses he ile show_ esul s. x .
22 ANDREAS WACHTEL
Re e ences
[Beh14] M. Beh isch. Clones wi h nulla y ope a ions. Elec onic No es in Theo e ical Compu e Science, 303:3–35, 2014. P oceedings o he Wo kshop on Algeb a,
Coalgeb a and Topology (WACT 2013). doi: 10.1016/j.en cs.2014.02.002.
[Beh24] M. Beh isch. Finding minimal ∈cMaj{0,1}
5(py, c++). Zenodo, No . 2024. doi: 10.5281/zenodo.13862887.
[Cs´a83] B. Cs´ak´any. All minimal clones on he h ee-elemen se . Ac a Cybe ne ., 6(3):227–238, 1983.
[Cs´a86] B. Cs´ak´any. On conse a i e minimal ope a ions. In Lec u es in uni e sal algeb a (Szeged, 1983), olume 43 o Colloq. Ma h. Soc. J´anos Bolyai, pages 49–60.
No h-Holland, Ams e dam, 1986. doi: 10.1016/B978-0-444-87759-8.50009-2.
[Cs´a05] B. Cs´ak´any. Minimal clones—a minicou se. Algeb a Uni e salis, 54(1):73–89, 2005. doi: 10.1007/s00012-005-1924-2.
[GHVG24] C. Galeana He n´andez and E. Va gas-Ga c´ıa. In oducci´on a los clones de unciones. Miscel´anea Ma em´a ica, 78:1–16, 2024. doi: 10.47234/MM.7801.
[PK79] R. P¨oschel and L. A. Kaluˇznin. Funk ionen- und Rela ionenalgeb en. VEB Deu sche Ve lag de Wissenscha en, Be lin, 1979. doi: 10.1007/978-3-0348-5547-1.
[Wal00] T. Waldhause . Minimal clones gene a ed by majo i y ope a ions. Algeb a Uni e salis, 44(1-2):15–26, Oc . 2000. doi: 10.1007/s000120050167.
[Wal07a] T. Waldhause . Minimal clones. PhD disse a ion, Szegedi Tudom´anyegye em (SZTE), Bolyai Ins i u e, 2007.
[Wal07b] T. Waldhause . Minimal clones wi h ew majo i y ope a ions. Ac a Sci. Ma h. (Szeged), 73(3-4):471–486, 2007.
