Parallel computing minimal $ f\in \mathrm{cMaj}_5^{\{0,1\}} $ (py)

PARALLEL COMPUTING MINIMAL f∈cMaj{0,1} 5(PY) ANDREAS WACHTEL  Departamento Acad´emico de Matem´aticas, ITAM, M´exico Abstract. This dataset consists of a (mostly) parallel Python code, its documentation and its results. The code is one of 3 independent implementations that accompany the paper entitled “All minimal clones generated by {0,1}-valued majority operations on a five-element set”. Within the set of all cyclically symmetric majority operations on the five-element set A={0,1,2,3,4}with values in {0,1}on injective triples, denoted cMaj{0,1} 5,the code identifies all fthat generate a minimal clone. The list of these functions is reduced up to an equivalence relation defined by conjugacy (isomorphisms). Keywords. minimal clone, cyclic symmetry, majority operation, five element set. Most of the theory which is implemented in functions within this data set, cf. [Wac24], is knowledge that the author came to understand thanks to many private discussions about the theory with Mike Behrisch (author of [Beh14]) and Edith Vargas-Garc´ıa (author of [GHVG24]). The author is not a seasoned expert in clones and was invited to develop this independent code. Thus, implementation details were not discussed and the code in this data set is very different from the codes developed by Mike Behrisch [Beh24] (in C++ and Python). Now, in order to simplify the readers understanding of the functions and the code, this document contains facts the author came to understand, as well as, some references to official sources of these. Most of the facts are restricted to the ternary part of a minimal clone generated by a “minimal” function. For a smoother introduction to the topic, the interested reader is referred to the article “Minimal Clones – A minicourse”, see [Cs´a05]. A Spanish introduction to clones, compositions that also mentions minimal clones is given in [GHVG24]. This data set computationally identifies functions (ternary cyclically symmetric {0,1}-valued majority operations) that on the set A={0,1,2,3,4} generate a minimal clone. For smaller carrier sets Awith |A| ≤ 4 this problem has been solved with less restrictions on the generator functions. For instance, for |A|= 3 all minimal clones are known [Cs´a83] and for |A|= 4 all minimal clones generated by majority operations are characterised in [Wal00]. E-mail address:[email protected]. The author gratefully acknowledges support by the Asociaci´on Mexicana de Cultura A.C. 1 2 ANDREAS WACHTEL Contents Definitions and the GOAL. 2 1. How to run the code and read the results 3 1.1. What is needed 3 1.2. How to show and understand the results 4 1.3. How to recompute the results 5 2. The elimination procedure 6 2.1. Step 1 – Parallel elimination of non-minimal f6 2.2. Step 2 – Elimination of conjugates 6 2.3. Step 3 – Sufficient minimality tests 6 3. Theory 7 3.1. Ternary parts of clones 7 3.2. Ternary majority operations as integers 8 3.3. Representing the reversed function 8 3.4. A necessary monotonicity condition 9 3.5. Conjugated functions 10 3.6. Clones 11 4. Libraries and files 13 4.1. Functions in hlib progress.py 13 4.2. Functions in hlib TicToc.py 13 4.3. Functions in lib integerBitManipulation.py 13 4.4. Functions in lib tuplePositionBij.py 13 4.5. Functions in lib CSMOt.py 13 4.6. Functions in lib compose.py 14 4.7. Functions in lib preserve.py 15 4.8. Functions in lib keepCandidates.py 16 4.9. Functions in lib CSMO clones.py 17 4.10. Functions in step2s.py 18 4.11. Functions in step3p.py 19 5. List of files 21 References 22 Definitions and the GOAL. The code is specialised in many ways to the five-element set. We have to define a few sets of functions before we can define the goal. •Let A=5={0,1,2,3,4}be our five-element set. •A triple (a, b, c)∈A3is called injective triple iff a6=b6=c6=a. •Aternary majority operation f:A3→Asatisfies f(a, a, b) = f(a, b, a) = f(b, a, a) = afor all a, b ∈A. Therefore, the majority property of ffixes its value for non-injective triples and only the values on injective triples identify f. •A ternary majority operation fis {0,1}-valued on injective triples if f(a, b, c)∈ {0,1}for all injective triples (a, b, c)∈A3. •We define Maj{0,1} 5to be the set that contains all {0,1}-valued ternary majority operations on A. PARALLEL COMPUTING MINIMAL f∈cMaj{0,1} 5(PY) 3 •A ternary function f∈Maj{0,1} 5on A= 5 takes one value in {0,1}for each injective triple (a, b, c)∈A3.Since |A|= 5 there exist 5∗4∗3 = 60 different triples and the values {0,1}of fcan be uniquely associated to a 60 bit integer Nf.Therefore, f∈Maj{0,1} 5⇐⇒ Nf=f60 ∈MO :=0,1,...,260 −1.(1) •An f∈Maj{0,1} 5is cyclically symmetric iff f(a, b, c) = f(c, a, b) for all a, b, c ∈A. •Let cMaj{0,1} 5:=nf∈Maj{0,1} 5:fis cyclically symmetrico.Applying the definition a few times all f∈cMaj{0,1} 5satisfy f(a, b, c) = f(c, a, b) = f(b, c, a) and f(c, b, a) = f(a, c, b) = f(b, a, c),(2) wherefore 2 independent values of fdefine all 6, i.e., the values of f∈cMaj{0,1} 5are uniquely defined by a 60 3= 20 bit integer N20 f: f∈cMaj{0,1} 5⇐⇒ N20 f=f20 ∈CSMO :=0,1,...,220 −1.(3) This association is not unique, as it depends on the order of 20 injective triples which by eq. (2) may also differ in order. The goal: Find all minimal clones on Agenerated by some f∈cMaj{0,1} 5. 1. How to run the code and read the results 1.1. What is needed. The code is written (and was last run) in Python 3.9. The following python libraries are used: numba, numpy, time, multiprocessing, functools, scipy.sparse Running the code (as described in Sections 1.2 and 1.3) requires all .py files listed in Section 5 (List of files). 4 ANDREAS WACHTEL 1.2. How to show and understand the results. Originally we computed 26 minimal generators f∈cMaj{0,1} 5.These may be recomputed, see Section 1.3 below. However, in order to save computational time (and energy) the 26 functions have been hard-coded in the file show results.py in the function called getMinimals n5 AW. Running python show results.py or printing the file show results.txt, gives the following output which will be explained below the table: show results.txt # OUTPUT of: python show_results.py Import: Integer and bit-manipulation (AW, 2024) Import: Tuple-position-bijection (AW, 2024) Import: tuples for CSMO (AW, 2024) Import: Step 2 (conjugates) (AW, 2024) Results - Compatibility. Bit and Tuple order of Mike: The 20 tuples in the bit-order of 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 values of Mike, AW and values at tuples: x 020304|030404|131414|24 y 111111|222233|222233|33 z 203040|304040|314141|42 ------------------------------------------- Mike, AW, minimal clones with 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 with 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 with 16 MO 520199, 459719 101010|000000|111111|10 Mike, AW, minimal clones with 64 MO 520203, 460739 111000|000000|111111|10 520205, 460741 110010|000000|111111|10 how many unique minimal f : 26 how many minimal f : 296 The two leftmost columns of the table will be explained below (as they depend on the code). For the moment, consider the rightmost part of the table, which is independent of the code. Each of the 20 zeros and ones in a row shows which value s=f(x, y, z) a minimal f∈cMaj{0,1} 5 takes at the injective triple given in the column of the header above s. The 26 rows or minimal fare separated by groups, i.e., by how many majority operations belong to the ternary part of the clone of f. These 26 are unique up to conjugacy, see Section 3.5. The count 296, at the end, is the number of all minimal f∈cMaj{0,1} 5,including all conjugates removed as discussed in Section 3.5, some of which generate the same clone and others isomorphic minimal clones. PARALLEL COMPUTING MINIMAL f∈cMaj{0,1} 5(PY) 5 This code and the codes by Mike Behrisch [Beh24] have been developed independently. At the end, we realised that we used different injective triples and orders for the equivalence (3), which is possible due to eq. (2). This caused that each of our codes uses a different 20-bit integer to identify f∈cMaj{0,1} 5.In the table, the first column shows the 20-bit integer used in [Beh24] given in Definition 2. The second column shows the 20-bit integer used in this code, given by Definition 1. Definition 1 (Hash-value in this code).This code identifies f∈cMaj{0,1} 5and f20 =N20 f∈CSMO given by: Nf:=f0 1 220+f0 1 321+f0 1 422+f0 2 323+f0 2 424+f0 3 425+f1 2 326+f1 2 427+f1 3 428+f2 3 429 +f2 1 0210 +f3 1 0211 +f4 1 0212 +f3 2 0213 +f4 2 0214 +f4 3 0215 +f3 2 1216 +f4 2 1217 +f4 3 1218 +f4 3 2219 . (4) This value defines all values of fat increasing triples in the bits 0..9 and the ones at decreasing tuples in the bits 10..19. Definition 2 (Hash-value used in [Beh24]).This association identifies f∈cMaj{0,1} 5and Nf∈CSMO given by: Nf:=f0 1 220+f0 1 321+f0 1 422+f0 2 123+f0 2 324+f0 2 425+f0 3 126+f0 3 227+f0 3 428+f0 4 129 +f0 4 2210 +f0 4 3211 +f1 2 3212 +f1 2 4213 +f1 3 2214 +f1 3 4215 +f1 4 2216 +f1 4 3217 +f2 3 4218 +f2 4 3219 (5) This value is built upon the lexicographic order of the used injective triples. 1.3. How to recompute the results. Running python compute results.py recomputes all minimal fusing the elimination procedure is summarized in Section 2. This may take a while. Before running the command one might want to check what kind of output to expect and how long it took on my computer. These details are contained in the file compute results.txt. As run-times by themselves do not tell what to expect on another computer, below I include my hardware specifications. 1.3.1. Hardware specifications. The times were measured using Linux as an operating system (in airplane mode) on a computer with 8 GiB 1 of RAM and a CPU of type Intel Core i5 (8th generation) with CPU-caches of levels {L1|L2|L3}and sizes {256 KiB |1 MiB |6 MiB}2. 1.3.2. Computations are not RAM critical. The largest vector occupied by the code in memory, during some seconds, contains 220 = 1 048 576 logical entries which occupy approximately 1 MiB – and this is only due to the parallelization. All other operations require a small amount of 60 bit integers. In the worst case, a part of the clone of fof less than 500 integers is generated. 1Units: 1B= 1 byte = 8 bits , 1 KiB = 210 bytes , 1 MiB = 220 bytes , GiB = 230 bytes . 2The RAM and cache sizes are results of the command “sudo lshw -class memory”. 6 ANDREAS WACHTEL 2. The elimination procedure The complete elimination procedure is run as shown in Section 1.3, but internally it runs the steps described in this section. 2.1. Step 1 – Parallel elimination of non-minimal f.The function runStep1 in the file step1p.py goes in parallel through all 220 functions f∈cMaj{0,1} 5and checks whether each fsatisfies some necessary conditions for minimality. This step reduces the number of candidates from 220 to 540 functions f∈cMaj{0,1} 5,as can be seen in the results compute results.txt in line 18. The checks are done by parallel instances of the function 4.8.1 keepF20nc, which is described in Section 4.8 (Functions in lib keepCandidates.py). Running python step1p.py also invokes the function runStep1. The results will be saved, provided the logical flag in line 68 is True. 2.2. Step 2 – Elimination of conjugates. The function runStep2 in the file step2s.py eliminates conjugates. Provided the 540 remaining functions from Step 1 are passed (or were saved), they are reduced to only 65 remaining f∈cMaj{0,1} 5,as can be seen in the file compute results.txt in line 47. The theory is described in Section 3.5. This reduction is done using the functions in step2s.py which are documented in Section 4.10. 2.3. Step 3 – Sufficient minimality tests. The function runStep3 in the file step3p.py performs sufficient minimality tests. Provided the 65 remaining functions from Step 2 are passed (or were saved), they are reduced to the 26 minimal functions shown in Section 1.2 or at the end of the file compute results.txt. The employed minimality test 4.9.5 miniTest is described in Section 4.9 (Functions in lib CSMO clones.py). Many other libraries (see Section 4) and a few functions in step3p.py (see Section 4.11) are used to perform tests in the following 2 levels: L.1. A contained function named 4.11.4 findSmallClonesP calls a minimality test (in parallel) for the 65 remaining functions. There is a hard-coded restriction on the size a clone is allowed to have, wherefore this test identifies potentially minimal clones that contain 1,8,16 or 18 majority operations, eliminates non-minimal candidates and leaves some undecided cases. The lines 126–136 of the file compute results.txt show that this takes less than 3 seconds, identifies 24 minimal functions and leaves 31 unclassified functions. Between the lines 60 – 124 one can see failed minimal tests for candidates whose ternary clone contains 21 elements, i.e., 18 MO and 3 projections. All of them fail because they contain a minimal ternary size-4 clone (1 MO and 3 projections). L.2. A contained function named 4.11.5 findBiggerClonesP calls the minimality test (in parallel) for the remaining 31 unclassified functions from Level 1. The lines 172–186 of the file compute results.txt show that this takes about 80 seconds, identifies 2 further minimal clones that contain 64 majority operations and eliminates all remaining 29 candidates as non-minimal, 27 of them generate a clone that contains a smaller minimal one of size 11 (8 MO + 3 projections). PARALLEL COMPUTING MINIMAL f∈cMaj{0,1} 5(PY) 7 3. Theory The following sections contain theory that justifies (partly) the completeness of the code. 3.1. Ternary parts of clones. The following facts about clones allow the code to give complete results and allow a significant reduction of computations. In general, a clone is a set of functions that contains all projections and is closed with respect to composition. Within the code we only consider the “ternary part” of a clone generated by a function f∈cMaj{0,1} 5and the following 3 projections: Definition 3. The ternary projections J(3) Aare the functions e1, e2, e3:A3→Agiven by e1(x, y, z) = x, e2(x, y, z) = yand e3(x, y, z) = z. Definition 4. Let f∈cMaj{0,1} 5.Then, the ternary part of a clone generated by f, denoted hereafter by hfi, contains the ternary projections J(3) Aand all compositions of fwith these projections and functions generated by such compositions. Properties related to the next function will reduce computations. Definition 5. Given f:A3→Aits reverse ¯ fis defined as ¯ f(a, b, c):=f(c, b, a)for all a, b, c ∈A, that is, ¯ freverses the order of its arguments before applying f. The next lemma confirms that ¯ f∈ hfiand f∈¯ f. Lemma 6. Given an f:A3→Aor its reverse ¯ f, we have ¯ f=f◦(e3, e2, e1)and f=¯ f◦(e3, e2, e1). Proof. The first relation is obtained from ¯ f(a, b, c) = f(c, b, a) = fe3(a, b, c), e2(a, b, c), e1(a, b, c) for all a, b, c ∈A. The second relation comes from f(a, b, c) = ¯ f(c, b, a) = ¯ fe3(a, b, c), e2(a, b, c), e1(a, b, c) which also holds for all a, b, c ∈A.  Lemma 6 confirms the equality: hfi=e1, e2, e3, f, ¯ f, . . .=e1, e2, e3,¯ f, f, . . .=¯ f(6) For f∈cMaj{0,1} 5the set hfi=¯ fmay also contain ternary functions that are not cyclically symmetric. The next lemma, see also [Cs´a86, p. 54], guarantees that all non-trivial functions in hfibelong to Maj{0,1} 5and wherefore these function can still be represented by 60 bits (and by our code). Lemma 7. If f∈cMaj{0,1} 5,then hfi ⊆ Maj{0,1} 5∪J (3) A. Proof. Since only case distinctions and definitions are required, we only sketch the steps to prove the result. First, one proves that h∈Maj{0,1} 5and g1, g2, g3∈Maj{0,1} 5∪J (3) A,always give h◦(g1, g2, g3)∈Maj{0,1} 5∪J (3) A. Then, the only thing left to do is to construct an f∈cMaj{0,1} 5 that satisfies f◦(e1, e2, f)∈Maj{0,1} 5,that is, the cyclic symmetry gets lost due to some compositions.  Given Lemma 7 and sufficient time (and RAM), the code is able to generate the complete ternary clone hfi,because hfi ⊆ Maj{0,1} 5∪J (3) A.(7) Since minimal clones are small their ternary part fits into the RAM. 8 ANDREAS WACHTEL 3.2. Ternary majority operations as integers. The code separates the subset cMaj{0,1} 5from the complete set Maj{0,1} 5. 3.2.1. Cyclically Symmetric MO. The code uses Definition 1 to represent each f∈cMaj{0,1} 5as the following 20-bit integer f20 =Nf: Nf:=f0 1 220+f0 1 321+f0 1 422+f0 2 323+f0 2 424+f0 3 425+f1 2 326+f1 2 427+f1 3 428+f2 3 429 +f2 1 0210 +f3 1 0211 +f4 1 0212 +f3 2 0213 +f4 2 0214 +f4 3 0215 +f3 2 1216 +f4 2 1217 +f4 3 1218 +f4 3 2219 . (4) This value defines all values of fat increasing tuples in the bits 0..9 and the ones at decreasing tuples in the bits 10..19. Example: In binary notation the least bits are on the right. For instance f20 =Nf= 1024 + 8 = (00000 00001 00000 01000)2gives for each triple (given by the first 3 entries of a column) the values: x|4443443432 2111000000 y|3322322111 3322322111 z|2111000000 4443443432 1032|0000000001 0000001000 8193|0000001000 0000000001 3.2.2. Majority Operations. The values of f∈Maj{0,1} 5evaluated at the 60 injective triples also belong to {0,1}and are represented in the code using the bits of a 60 -bit integer f60 ∈MO :=0,1,...,260 −1.The association of triple and bit-position is given by a bijection defined by functions inside the library lib tuplePositionBij.py. Running python lib tuplePositionBij.py) shows both the triple-order and the bijection: 0 bit2tuple(bit) = (0, 1, 2) tuple2bit(tuple) = 0 1 bit2tuple(bit) = (0, 1, 3) tuple2bit(tuple) = 1 2 bit2tuple(bit) = (0, 1, 4) tuple2bit(tuple) = 2 3 bit2tuple(bit) = (0, 2, 1) tuple2bit(tuple) = 3 ... 59 bit2tuple(bit) = (4, 3, 2) tuple2bit(tuple) = 59 3.3. Representing the reversed function. By eq. (4) the code stores all values of f∈cMaj{0,1} 5at increasing triples in the bits 0,...,9 and the ones at decreasing triples in the bits 10,...,19. The function ¯ fdefined as ¯ f(x, y, z) = f(z, x, y) , see Definition 5, reverses the triples. Hence, bits can be swapped to construct ¯ f, e.g., ¯ f0 1 2=f2 1 0=Nf[bit 10] and ¯ f2 1 0=f0 1 2=Nf[bit 0]. In general, if we define fwd = bits 9,...,0 of f and bwd = bits 19,...,10 of f, then we can write Nf=(bwd | fwd) and N¯ f=(fwd | bwd). Within Python, this can be done by the following integer-bit operations: Nfbar = ((Nf & 1023) << 10) + (Nf >> 10) For example, if f20 = 1024 + 8,then ¯ f20 = 8 ∗1024 + 1. 3.3.1. Ignoring reversed functions. One of the values Nfand N¯ f is smaller iff f6=¯ f. Since hfi=¯ f,see (6), the code ignores the bigger hash-value (if it is strictly bigger), that is, the code only checks (necessary) conditions for f∈CSMO = 0,1,...,220 −1which satisfy Nf≤N¯ f(8) Savings: Roughly 49.9% , because the number of Nf∈CSMO that satisfy Nf> N ¯ fis 29∗1023 <29∗1024 = 219. PARALLEL COMPUTING MINIMAL f∈cMaj{0,1} 5(PY) 9 3.4. A necessary monotonicity condition. The following lemma is the Lemma 17 (of our work) restated to ease the implementation. The result goes back to B´ela Cs´ak´any in [Cs´a86, Theorem 2, p. 56], but it can also be found in [Wal07a, Remark 1.10, p. 13], Waldhauser’s Ph. D. thesis. Lemma 8. Let {0,1}(A, Ua={0,1, a}, Ub={0,1, b}where a, b ∈A\ {0,1}and suppose that f∈cMaj{0,1} 5generates a minimal clone. Then f(0,1, a)< f(a, 1,0) and f(0,1, b)> f(b, 1,0) is impossible. Comments on Lemma 8: •For A={0,1,2,3,4}we only have 3 such subsets, that is {0,1,2},{0,1,3},{0,1,4}. •The contrapositive is: If f(0,1, a)< f(a, 1,0) and f(0,1, b)> f(b, 1,0),then fis not minimal. The next lemma is a bit-wise version of Lemma 8 and requires the following notation. Because of Definition 1 the values of fat the increasing triples T={(0,1,2),(0,1,3),(0,1,4)} are located in the bits 0,1,2 and the values of fat the decreasing triples {(2,1,0),(3,1,0),(4,1,0)}in the bits 10,11,12. In Python, we can extract these bits using finc = f & 7 and fdec = (f >> 10) & 7, that is, we use a “bitshift” and a “bitwise-and &” with 7 = (111)2.Now, finc and fdec are integers between 0 and 7, because each belongs to {000,001,010,011,100,101,110,111}. Lemma 9 (The bitwise Waldhauser condition).We have (a) min( finc, fdec ) >= finc & fdec and (b) if min( finc, fdec ) > finc & fdec, then fis not minimal. Proof. (a) Follows from the fact that the bitwise-and only keeps some of the bits that are shared by the minimum and the other value. To prove (b), note that fdec = finc implies that min( finc, fdec ) = fdec = finc = fdec & finc. Therefore, w.l.o.g. we suppose fdec > finc and finc > finc & fdec. Then, due to finc > finc & fdec, there exists a bit in {0,1,2}in finc that is one but the same bit is zero in fdec. Thus, there exists a triple (0,1, a) such that f(0,1, a) = 1 >0 = f(a, 1,0).Additionally, because of fdec > finc we get that fdec has a bit set where finc has not. Thus, there exists a triple (0,1, b) such that f(0,1, b)=0<1 = f(b, 1,0).By Lemma 8 the existence of these triples contradicts that fis minimal. An analogous argument works if fdec < finc. The contrapositive of Lemma 9 gives the following condition: fis minimal =⇒min( finc, fdec ) == finc & fdec.(9) This necessary condition is checked inside lib keepCandidates.py in a function called keepCsakanyWaldhauser. 16 ANDREAS WACHTEL 4.8. Functions in lib keepCandidates.py.It is known that a composition of a function fnever preserves less subsets U⊂A than fitself, see [PK79, Satz 1.1.15, p. 48]. This is tested in many routines of this library, as it is a necessary condition for correctness of the implementation of compositions. It is also known, that if a composition hof fpreserves more subsets U⊂Athan fitself, then fis not minimal, see [Cs´a05, Section 3, p. 76] and fcan be discarded from the list of candidates of minimal generators. This library contains functions that verify these and other necessary conditions to reduce the list of candidates of minimal clone generators. The main function is keepF20nc. 4.8.1. keepF20nc.This function is called in parallel instances. Given an f20 ∈CSMO,the 20 tuples of getTuplesCS, and the results of get fUs n5, this central function unites the results of all implemented necessary conditions (the functions below) that allow to decide whether to keep f20 as a minimal candidate. 4.8.2. keepLE.Given an f20 ∈CSMO,this function decides whether to analyse f20 or to discard it, see Section 3.3.1. 4.8.3. keepCsakanyWaldhauser.Given an f20 ∈CSMO,this function decides whether f20 passes condition (9), see Section 3.4. 4.8.4. keepF60.Given an f60 ∈MO and the results of get fUs n5, this function returns true iff certain compositions of f60,e.g. h•, h@ generated by bullet g,arroba g and the labeled continued fixpoints illustrated below, preserve the same subsets U⊂Aas f60. The non-labeled fixpoints are commented out in the code, because they did not remove more candidates. f h• h•∗ star g h•@ h•@∗ star g arroba g bullet g h@ h@∗ star g arroba g 4.8.5. keepF60complicated.Given an f60 ∈MO and the results of get fUs n5, this function returns true iff a lot of compositions of f60 preserve the same subsets U⊂Aas f60 itself. In here a small part of the ternary functions from hf60iis generated, using the function called closeF cs with bigN = 5, see Section 4.9 for details. PARALLEL COMPUTING MINIMAL f∈cMaj{0,1} 5(PY) 17 4.9. Functions in lib CSMO clones.py.This library implements general (non-specialised) compositions, clone-closing algorithms (described in Section 3.6) and the sufficient minimality test given by the right-hand-side of the following equivalence: hfiOAis minimal ⇐⇒ ∀h∈ hfi\J(3) Awe have f∈ hhi.(11) This equivalence is taken from [Wal07b, Theorem 2.1]. 4.9.1. checkPreservedU.Given g60 ∈MO,a logical vector fpreserves that states which of the 8 interesting subsets (10) are preserved by f, the results of get fUs n5 and a name of a composition function, this function verifies whether g60 preserves the same subsets as f. Additionally, the function checks that g60 preserves all subsets preserved by f, which is necessary for the correctness of implementation of the composition. 4.9.2. compose gen.Given f∈MO and g1, g2, g3∈MO ∪ J (3) A where J(3) A={−3,−2,−1}and each negative number identifies a projection, see Section 3.6.3, this function returns the 60-bit integer representing the composition f◦(g1, g2, g3)∈MO,according to Lemma 7. The result cannot be a projection, as this is not implemented, wherefore the caller must ensure that the three functions g1, g2, g3do not contain the same projection twice. 4.9.3. closeF cs.Given a list F= [e1, e2, e3, f60] with a cyclically symmetric f60 ∈MO,the results of get fUs n5 and an upper bound bigN, this function generates hFior a part of it as a list Fc of 60-bit integers, using Algorithm 3.1 with the enumeration described in Section 3.6.4. For a given bound bigN the list Fc will at most have bigN + bigN*(bigN-1)*(bigN-2)/3 entries, which follows because the list F= [f1, . . . , fbigN] may generate up to bigN*(bigN-1)*(bigN-2)/3 additional compositions because f60 is cyclically symmetric, see Section 3.6.2. The function returns the pair (keep,Fc), where Fc is the list mentioned earlier and keep is True iff all functions in the list Fc preserve the same (and not more) subsets as f60. The following is used outside (in Step 3): If len(Fc) ≤bigN, then the closing was completed and abusing notation we think of Fc =hFi,because Fc is a discrete representation of hFi. 4.9.4. find F in clone h.Given a list F h = [e1, e2, e3, h60] with ah60 ∈MO,and a cyclically symmetric 60-bit f2bfound ∈MO, this function decides whether f2bfound belongs to the ternary functions in hF hiwhose size is limited by a given parameter bigN with default value 18. This is done using Algorithm 3.1 with the enumeration described in Section 3.6.4 and the modification that line 7 adds 6 compositions, because h60 is not necessarily cyclically symmetric. The result found is True if f2bfound was found, otherwise it may be False if the clone hF hiwas closed without containing f2bfound or None if the clone hF hiwas incomplete due to the size restriction. 4.9.5. miniTest.Given a ternary part of a clone hfias a list of 60-bit integers Forg = [e1, e2, e3, f60, h1, . . . , hm] this function implements the sufficient minimality test given by equivalence (11), that is, for each hithe function find F in clone h is called to verify whether f60 belongs to hhii.Naturally, this is expensive, as these mclones have to be generated to confirm that hfiis minimal. This function prints out that it is “cheap” if m= 1.The return value is either True or False. 18 ANDREAS WACHTEL 4.10. Functions in step2s.py.The functions in here allow to calculate conjugates and reduce a list of functions to a subset of unique conjugates as described in Section 3.5. 4.10.1. bits after phi.Given a permutation φ:A→Aas an array perm, this function generates another array which maps a position bit(a, b, c)∈ {0,1,...,59}to a position bitφ(a), φ(b), φ(c)∈ {0,1,...,59},i.e. the position after the permutation φ. This bijection relies on the functions tuple2bit and bit2tuple. This array will be used to establish the equality given in Definition 10 but in the form: φg60bit(a, b, c) =f60bitφ(a), φ(b), φ(c).The array does not change for a given φ, so it can be reused to calculate φconjugates of many f20 ∈CSMO. 4.10.2. calcConjugate.Given an integer f20 ∈CSMO,the results of getTuplesCS, of getMap20in60, of bits after phi (which gives φimplicitly as an array) and φ(0) as an integer, this function returns g20 :=φ−1◦f20 ◦(φ, φ, φ).Inside the functions getCSMO60d and reduce60to20 are used. 4.10.3. keepFisoSP.Given a list of functions candFsp, the set A={0,1,2,3,4}and a bijection φ:A→Aas an array phi, this function calculates the conjugates g, ¯gfor each f20 in the list candFsp and eliminates them from this list. In order ensure that f20 remains in the list, this is not done in parallel. Inside the functions getTuplesCS,getMap20in60 and bits after phi are used. 4.10.4. getPermutations n5.This function returns the nonidentity permutations in the set Sym{0,1} Afor A={0,1,2,3,4},see Definition 11, which are given by the following 11 hard-coded nonidentity permutations in form of arrays [φ(0), φ(1), . . . , φ(4)] and their descriptions: (23),(24),(34),(234),(432),(01),(01)(23), (01)(24),(01)(34),(01)(234),(01)(432) . 4.10.5. getConjugates.Given f20 ∈CSMO and the five-element set A={0,1,2,3,4},this function generates the set of all interesting conjugates of f20,i.e., the set [[f20]] from Definition 12. This is done using the permutations given by the functions getPermutations n5 and the function calcConjugate. 4.10.6. eliminateConjugates.This internal function defines all permutations φusing getPermutations n5, and eliminates conjugates g, ¯gfor all f20 from the argument candF using the function keepFisoSP. 4.10.7. runStep2.This function accepts 2 optional arguments, candF and a boolean save results. If candF is not present, then the results of Step 1 (see Section 2.1) are loaded, otherwise candF should contain similar data in the same form. After that, the function eliminateConjugates is used. Finally, each f20 in candF will be the smallest and only 20-bitinteger left from the equivalence class [[f20]] given in Definition 12. This is done to achieve comparable results. PARALLEL COMPUTING MINIMAL f∈cMaj{0,1} 5(PY) 19 4.11. Functions in step3p.py.The functions in here perform sufficient and necessary tests to decide whether each remaining candidate (from step 2) is minimal. Many non-minimal functions are eliminated by selecting or constructing a special h∈ hfisuch that f6∈ hhiwhich by (11) justifies that fis not minimal. In these cases the function 4.9.5 miniTest is called with only {e1, e2, e3, f, h}and fails, as expected. 4.11.1. isMinimal 3WL.This internal function takes f20 ∈CSMO representing f∈cMaj{0,1} 5and two optional arguments, knownMC a set uniting majority operations that belong to smaller known minimal clones and an integer upperN to limit the size of the generated part of hfi.Inside, the result (keep,Fc) generated by 4.9.3 closeF cs is decomposed as follows. If keep is False, then closeF cs found a composition hof fthat fails a necessary condition and f20 is not minimal and this function returns with (f20, False, 0). In the remaining situations keep is True and all (so far) generated compositions hof fpreserve the same subsets as f, wherefore the second result is separated into 3 cases: •If there exists hwithin the intersection of Fc and knownMC, then the miniTest with {e1, e2, e3, f, h}will fail, and this function returns (f20, False, 0). •If len(Fc) ≤upperN,then miniTest is called using Fc, which represents hfi.This test may pass or fail with result keep ∈ {True, False}.Then, this function returns (f20, keep, len(Fc)). •Otherwise, if len(Fc) >upperN,the function returns (f20, None, 0), and None signals to postpone the decision. 4.11.2. uniteClonesWith8MO.Given a list miniGenerators of integers representing some f20 ∈cMaj{0,1} 5,this internal function generates for each f20 in the list all conjugates (with getConjugates) and their clones (with closeF cs) and unites all contained majority operations into one set which is returned as a result. 4.11.3. lastSpecialTest.Given the remaining candidates as candF and a list of integers notClassified this internal function takes each f20 in notClassified, which represents f∈cMaj{0,1} 5, then forms the green-highlighted fix-point h•@∗(see Section 4.8.4) and calls the find F in clone h with the list F h = [e1, e2, e3, h•@∗], Nfas f2bfound and bigN = 67. It is verified that this test returns False, which justifies that f6∈ hh•@∗iand confirms that fis not minimal, see equivalence (11). The corresponding f20 are then removed from candF and the updated candF is returned. 4.11.4. findSmallClonesP.This internal function requires the minimal candidates in form of the argument candF. Inside, in parallel, for each candidate f20 in candF the function isMinimal 3WL is called with upperN = 21. After all calls have finished, the results are in memory in a list containing the triples (f20, decision, len(Fc)) where each decision takes one of the values {True, False, None}.Each triple is split, in order to decide what to do with the f20.If decision is None, then f20 is put into a list notClassified. If False, then f20 is removed from candF. If True, the third result len(Fc) is used to classify the found minimal clones by their sizes 4,11,19,this count includes 3 projections. The updated candidates candF, lists of minimal functions and the notClassified list are returned for reporting. 20 ANDREAS WACHTEL 4.11.5. findBiggerClonesP.This internal function requires the results candF, clone11, notClassified of findSmallClonesP as it continues the decision process for the not classified candidates. The concept of this function is the same as findSmallClonesP, but it calls the function isMinimal 3WL with upperN = 67 and with knownMC = h11 where h11 is a set that unites all majority operations generated by uniteClonesWith8MO ( clone11 ). Once the parallel instances of isMinimal 3WL have finished, the code analyses the list of triples (f20, decision, len(Fc)) where each decision belongs to {True, False, None}.The same decision process is made, None means notClassified,False removes f20 from candF and True classifies a minimal clone (in this case only clones of size 67), all other sizes fail to be minimal. After this separation one function remained notClassified and was confirmed to be not minimal by invoking lastSpecialTest. Finally, the updated candidates candF and clones67 a list of minimal functions are returned for reporting. 4.11.6. runStep3.This function has the optional argument candF. If candF is not present, then the results of Step 2 (see Section 4.10) are loaded, otherwise candF should contain similar data in the same form. This function calls the functions mentioned in Section 2.3 and does all reporting to the screen. If the results of Step 2 were saved previously, then running python step3p.py invokes the function runStep3, the computations are run and the reporting is performed. PARALLEL COMPUTING MINIMAL f∈cMaj{0,1} 5(PY) 21 5. List of files •show_results.py – Python script that shows hard-coded results (minimal functions), documented in Section 1.2. •show_results.txt Output log of running the script show_results.py. Linebreaks and empty lines were added to show the output in Section 1.2. •compute_results.py – Python script that recomputes the minimal functions. It is documented in Section 1.3. •compute_results.txt Output log of running the script compute_results.py •step1p.py – Internal Python script that implements Step 1 (reduces candidates by checking necessary conditions), documented in Section 2.1. •step2s.py – Internal Python script that implements Step 2 (eliminates candidates if they are conjugated), documented in Sections 2.2, 3.5 and 4.10. •step3p.py – Internal Python script that implements Step 3 (verifies sufficient conditions for minimality), summarized in Section 2.3 and documented in Section 4.11. •hlib_progress.py – see Section 4.1. •hlib_TicToc.py – see Section 4.2. •lib_integerBitManipulation.py – see Section 4.3. •lib_tuplePositionBij.py – see Section 4.4. •lib_CSMOt.py – see Section 4.5. •lib_compose.py – see Section 4.6. •lib_preserve.py – see Section 4.7. •lib_keepCandidates.py – see Section 4.8. •lib_CSMO_clones.py – see Section 4.9. •docu.pdf – This documentation. •docu.tex – L A T EX source file to generate this documentation. This also uses the file show_results.txt. 22 ANDREAS WACHTEL References [Beh14] M. Behrisch. Clones with nullary operations. Electronic Notes in Theoretical Computer Science, 303:3–35, 2014. doi: 10.1016/j.entcs.2014.02.002. Proceedings of the Workshop on Algebra, Coalgebra and Topology (WACT 2013). [Beh24] M. Behrisch. Finding minimal f∈cMaj{0,1} 5(py, c++), Nov. 2024. doi: 10.5281/zenodo.13862887. [Cs´a83] B. Cs´ak´any. All minimal clones on the three-element set. Acta Cybernet., 6(3):227–238, 1983. [Cs´a86] B. Cs´ak´any. On conservative minimal operations. In Lectures in universal algebra (Szeged, 1983), volume 43 of Colloq. Math. Soc. J´anos Bolyai, pages 49–60. North-Holland, Amsterdam, 1986. doi: 10.1016/B978-0-444-87759-8.50009-2. [Cs´a05] B. Cs´ak´any. Minimal clones—a minicourse. Algebra Universalis, 54(1):73–89, 2005. doi: 10.1007/s00012-005-1924-2. [GHVG24] C. Galeana Hern´andez and E. Vargas-Garc´ıa. Introducci´on a los clones de funciones. Miscel´anea Matem´atica, 78:1–16, 2024. doi: 10.47234/MM.7801. [PK79] R. P¨oschel and L. A. Kaluˇznin. Funktionenund Relationenalgebren. VEB Deutscher Verlag der Wissenschaften, Berlin, 1979. doi: 10.1007/978-3-0348-5547-1. [Wac24] A. Wachtel. Parallel computing minimal f∈cMaj{0,1} 5(py), Dec. 2024. doi: 10.5281/zenodo.13786499. [Wal00] T. Waldhauser. Minimal clones generated by majority operations. Algebra Universalis, 44(1-2):15–26, Oct. 2000. doi: 10.1007/s000120050167. [Wal07a] T. Waldhauser. Minimal clones. PhD dissertation, Szegedi Tudom´anyegyetem (SZTE), Bolyai Institute, 2007. [Wal07b] T. Waldhauser. Minimal clones with few majority operations. Acta Sci. Math. (Szeged), 73(3-4):471–486, 2007.