Parallel finding of minimal $ f\in \mathrm{cMaj}_6^{\{0,1\}} $ (py)

PARALLEL FINDING OF MINIMAL f∈cMaj{0,1} 6(PY) MIKE BEHRISCH 1AND ANDREAS WACHTEL 23 Abstract. This dataset consists of a deterministic (mostly) parallel Python code, its documentation and its results. The code accompanies the paper entitled “All minimal clones generated by {0, 1}-valued majority operations on a six-element set”. Within this document, the set of all cyclic {0,1}-valued majority operations on a set Ais denoted by cMaj{0,1} A.The code is capable of identifying all f∈cMaj{0,1} Athat generate a minimal clone, for |A| ∈ {4,5,6}.The list of these functions is reduced up to an equivalence relation defined by conjugacy (isomorphisms). On A={0,1,2,3,4,5}the set cMaj{0,1} 6contains 240 = 1 099 511 627 776 functions, but only 258 non-equivalent minimal functions remain. Keywords. minimal clone, {0,1}-valued majority operation, cyclic majority operation, six-element set. The code described here, and available in the dataset [BW25], computationally identifies minimal functions (ternary cyclic {0,1}- valued majority operations), i.e., functions in cMaj{0,1} 6that generate a minimal clone. It reduces the 240 = 1 099 511 627 776 functions in cMaj{0,1} 6down to only 258 minimal functions. This is a substantial extension of previous results, which reduced 220 majority operations in cMaj{0,1} 5down to 26 minimal functions, see [BVW25, Wac24, Beh24]. These numbers are small, because each minimal function is one unique representative of a class of equivalent minimal functions. In order to simplify the interested reader’s understanding of the code, this documentation contains facts, 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]. Happy clone finding. https://openclipart.org/artist/lemmling E-mail address:[email protected]. 1Institute of Discrete Mathematics and Geometry, TU Wien, Wien, Austria. 2Departamento Acad´emico de Matem´aticas, ITAM, M´exico. 3This author gratefully acknowledges support by the Asociaci´on Mexicana de Cultura A.C. 1 2 MIKE BEHRISCH AND ANDREAS WACHTEL Contents Definitions and the GOAL. 3 1. How to run the code and read the results 4 1.1. What is needed 4 1.2. How to show and understand the results 5 1.3. How to recompute the results 6 2. The elimination procedure 7 2.1. Step 0 7 2.2. Step 1 – Parallel elimination 7 2.3. Step 2 – Elimination of conjugates 7 2.4. Step 3 – Sufficient minimality tests 7 3. Theory 8 3.1. Clones and their ternary parts 8 3.2. Representing majority operations 9 3.3. Reduced Conjugates, part 1 10 3.4. An additional explicit reduction 11 3.5. Possible searches 12 3.6. Unique Conjugates, part 2 13 3.7. Clones 14 4. Unique minimal functions and isomorphic restrictions 15 5. Libraries and files 24 5.1. lib constants.py 24 5.2. Functions in hlib progress.py 24 5.3. Functions in hlib TicToc.py 24 5.4. Functions in lib integerBitManipulation.py 24 5.5. Functions in lib tuplePositionBij.py 24 5.6. Functions in lib integer120.py 25 5.7. Functions in lib CSMO.py 25 5.8. Functions in lib minimals A4.py 26 5.9. Functions in lib restrict to k4.py 26 5.10. Functions in lib quick compose.py 27 5.11. Functions in lib preserve.py 28 5.12. Functions in lib keepCandidates.py 29 5.13. Functions in step1y.py 30 5.14. Functions in lib permutations.py 32 5.15. Functions in lib conjugates.py 32 5.16. Functions in step2s.py 33 5.17. Functions in lib CSMO clones.py 34 5.18. Functions in step3p.py 35 5.19. Functions in show results.py 36 5.20. Functions in lib minimals A5.py 36 5.21. Functions in lib restrict to k5.py 37 5.22. Functions in step4 iso.py 37 6. List of files 38 References 39 Appendix A. 40 A.1. Cyclic {0,1}-valued MO on {0,1,2,3}40 A.2. A necessary monotonicity condition 42 PARALLEL FINDING OF MINIMAL f∈cMaj{0,1} 6(PY) 3 Definitions and the GOAL. We have to define a few sets of functions before we can define the goal. •Let A=k={0,1,2, . . . , k −1}with k∈ {4,5,6}be our k-element carrier set. •A triple (a, b, c)∈A3is called injective triple iff a6=b6=c6=a. •Amajority operation is a ternary operation f:A3→Athat satisfies f(a, a, b) = f(a, b, a) = f(b, a, a) = afor all a, b ∈A. Hence, the majority property of ffixes its value for non-injective triples and only the values on injective triples identify f. •Let Maj{0,1} Abe the set that contains all {0,1}-valued majority operations on A. A function f∈Maj{0,1} Atakes one value in {0,1}for each injective triple (a, b, c)∈A3. Since |A|=kthere exist M:=k(k−1)(k−2) different injective triples and 2M{0,1}-valued majority operations. For k= 6 we have M= 120 and the value {0,1}of f∈Maj{0,1} Aon each of the 120 triples can be stored in a 120 bit integer: f∈Maj{0,1} A⇐⇒ fMO ∈0,1,...,2120 −1.(1) •A function f∈Maj{0,1} Ais cyclic iff f(a, b, c) = f(c, a, b) for all a, b, c ∈A. By transitivity f∈Maj{0,1} Ais cyclic iff 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) for all a, b, c ∈A . (2) •Let cMaj{0,1} A:=nf∈Maj{0,1} A:fis cyclico. By (2) only 2 out of 6 values per injective triple identify f∈cMaj{0,1} A. In other words, fis uniquely defined by its values on m:=1 6k(k−1)(k−2) = M/6increasing and mdecreasing triples. For k= 6 we have m= 20 increasing and m= 20 decreasing injective triples, and the {0,1}values of f∈cMaj{0,1} Aon these 40 triples can be uniquely associated to a 40 bit integer: f∈cMaj{0,1} A⇐⇒ Nf∈0,1,...,240 −1.(3) This bijection between f∈cMaj{0,1} Aand Nfis defined in Section 3.2.1, it is closely related to the order of the injective triples. The goal: Find all minimal clones on Agenerated by some f∈cMaj{0,1} A. 4 MIKE BEHRISCH AND ANDREAS WACHTEL 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. Running the code (as described in Sections 1.2 and 1.3) requires all .py files listed in Section 6(List of files) and the libraries above. Strictly speaking the code could be changed to not require the packages numba,multiprocessing,but the execution time would increase significantly, by an estimated factor of about 25. This factor is really only important for the case |A|= 6.For smaller carrier sets Athe parallel speedup can barely be noticed or measured. To the contributors of the numba package, see [Ana18, A+20]: THANK YOU. Using numba reduced our computing time by a factor of roughly 7. To the contributors of the multiprocessing, functools packages: THANK YOU. Using parallelism reduced our computing time by a factor of roughly 3.67. PARALLEL FINDING OF MINIMAL f∈cMaj{0,1} 6(PY) 5 1.2. How to show and understand the results. The code computes 258 minimal generators f∈cMaj{0,1} Awhen |A|= 6.These may be recomputed, see Section 1.3 below. However, in order to save computational time (and energy) the 258 functions have been hard-coded in the file show results.py in the function called get minimals A6 AW. The complete output of running python show results.py is in the file show results A6.txt. The following incomplete output illustrates the structure and some numbers that will be explained below: show_results_A6.txt (only selected lines) # Incomplete OUTPUT of: python show_results.py Import: Integer and bit-manipulation (2024) Import: Integer-120-bag (2025) Import: Tuple-position-bijection v2 (2025) Import: tuples for CSMO (2025) Import: Automatic Permutations (2025) Import: lib_conjugates (2025) Results ... Bit and Tuple order: The 40 tuples in the bit-order: [(0, 1, 2), (0, 1, 3), (0, 1, 4), (0, 1, 5), (0, 2, 3), (0, 2, 4), (0, 2, 5), (0, 3, 4), (0, 3, 5), (0, 4, 5), (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), (2, 3, 4), (2, 3, 5), (2, 4, 5), (3, 4, 5), (2, 1, 0), (3, 1, 0), (4, 1, 0), (5, 1, 0), (3, 2, 0), (4, 2, 0), (5, 2, 0), (4, 3, 0), (5, 3, 0), (5, 4, 0), (3, 2, 1), (4, 2, 1), (5, 2, 1), (4, 3, 1), (5, 3, 1), (5, 4, 1), (4, 3, 2), (5, 3, 2), (5, 4, 2), (5, 4, 3)] how many unique minimal f : 258 all minimal f : 13752 656 minimal f that generate 1 MO. 7624 minimal f that generate 8 MO. 1056 minimal f that generate 16 MO. 4416 minimal f that generate 64 MO. Hash values and values at tuples: x 02030405|030405040505|131415141515|24252535 y 11111111|222222333344|222222333344|33334444 z 20304050|304050405050|314151415151|42525253 ----------------------------------------------------------- AW, 43 unique minimal f that generate 1 MO 0 00000000|000000000000|000000000000|00000000 1073742848 00000000|000000000000|110000000000|00000000 ... 273817009164 00001111|000000000000|111111111111|11110000 AW, 139 unique minimal f that generate 8 MO 7169 10000000|000000000000|101010000000|00000000 ... 273808620557 10001110|000000000000|111111111111|11110000 AW, 20 unique minimal f that generate 16 MO 11811290119 10101000|000000000000|111110111010|10000000 ... 411243838479 10101010|000000000000|111111111111|01100110 AW, 56 unique minimal f that generate 64 MO 16107273219 11100000|000000000000|111111111000|10000000 ... 136375303181 11001011|000000000000|111111111111|11000010 6 MIKE BEHRISCH AND ANDREAS WACHTEL On the bottom left, some numbers are shown. The code found 258 minimal f∈cMaj{0,1} 6that are unique up to conjugacy, see Section 3.6. The count 13752 is the number of all minimal f∈cMaj{0,1} 6, including all conjugates, that were removed during the search, some of which generate the same clone and others isomorphic minimal clones. This number is divided into groups of fthat generate minimal clones containing a certain number of majority operations. On the right, the left column of the table contains the hash-value defined in Section 3.2.1. In the right column, each of the 40 zeros and ones in a row shows which value s=f(x, y, z) a minimal f∈cMaj{0,1} 6takes at the injective triple given in the column of the header above s. The 258 rows or minimal fare separated into groups, i.e., by how many majority operations belong to the ternary part of the clone generated by f. The complete list of the unique 258 minimal f∈cMaj{0,1} 6with more information can be found in Section 4. If the flag show all in line 175 of show results.py is True, then the output additionally shows similar tables for all equivalent minimal functions of each unique hash-value, see Section 3.6. For k= 6,these tables are included in the log-files all minimals A6 01mo.txt,all minimals A6 08mo.txt, all minimals A6 16mo.txt and all minimals A6 64mo.txt. Additionally, for k= 5,the tables are included in the log-files all minimals A5 01mo.txt,all minimals A5 08mo.txt, all minimals A5 16mo.txt and all minimals A5 64mo.txt. 1.3. How to recompute the results. Running python compute results.py recomputes all minimal fusing the elimination procedure summarized in Section 2. Recomputing is quick for |A|= 5 and takes some hours for |A|= 6.The code is a generalization of a previous code, cf. [Wac24], and, for verification purposes, it is able to also find the minimal f∈cMaj{0,1} Afor |A|=k∈ {4,5,6}.The desired value of parameter kcan be adjusted in the file lib constants.py. Before running the command one might want to check what kind of output to expect and how long the computations took. These details are contained in the files compute results Ak.txt with k∈ {4,5,6}.As run-times by themselves do not tell what to expect on any computer, below we also show the hardware specifications of the computer that computed the results. 1.3.1. Hardware specifications. The times were measured using Linux as an operating system (in airplane mode) on a computer with 16 GiB 1of RAM and a CPU of type Intel Core i7−6700 with CPUcaches of levels {L1|L2|L3}and sizes {256 KiB |1 MiB |8 MiB}2. 1.3.2. Computations are not RAM critical. The longest list, of empty and non-empty lists, occupied by the code in memory, during some seconds, contains less than 16 000 integers which occupy less than 1 MiB.All other operations require a small amount of 120 bit integers. In the worst case, a ternary part of a clone of fof less than 916 compositions h∈Maj{0,1} Ais 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”. PARALLEL FINDING OF MINIMAL f∈cMaj{0,1} 6(PY) 7 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. The numbers of functions presented in this summary are valid for |A|=k= 6. 2.1. Step 0. This theoretical step justifies reductions to roughly 50 %,or even 37.5 % when |A| ≥ 5,of interesting functions in cMaj{0,1} A.These reductions are based on a bijection between the functions in cMaj{0,1} Aand a set of non-negative integers, presented in Section 3.2, and moreover on some facts about clones and conjugates in Sections 3.1 and 3.3, respectively. Section 3.4 summarizes how 240 functions in (3) can be reduced to at most 239. 2.2. Step 1 – Parallel elimination. The function runStep1 in the file step1y.py, see Section 5.13, goes in parallel through the functions f∈cMaj{0,1} Aidentified in Step 0 and checks whether each fsatisfies some conditions necessary for minimality. On |A|= 6,this step reduces the number of candidates from 239 to 9954 functions f∈cMaj{0,1} A,as can be seen in line 56 of the file compute results A6.txt. The checks are done by parallel instances of the function passesNC, which is described in Section 5.12. Running python step1y.py also invokes the function runStep1 and saves the results, provided the passed logical flag is True. 2.3. Step 2 – Elimination of conjugates. The function runStep2 in the file step2s.py eliminates conjugates. Provided the 9954 remaining functions from Step 1 are passed (or were saved), they are reduced to only 454 remaining f∈cMaj{0,1} A,as can be seen in the file compute results A6.txt in line 159. The theory is documented in Section 3.6 and the functions in Sections 5.14,5.15 and 5.16. To be on the safe side, the code verifies that the conjugates of the least kept fcontain all candidates supplied by step 1. 2.4. Step 3 – Sufficient minimality tests. The function runStep3 in the file step3p.py performs sufficient minimality tests. Provided the 454 remaining functions from Step 2 are passed (or were saved), they are reduced to the 258 minimal functions, see show results A6.txt or at the end of the output compute results A6.txt. The theory of clone-closing and the employed minimality test is described in Section 3.7, but the implementation of the minimality test miniTest is documented in Section 5.17 (Functions in lib CSMO clones.py). Many other libraries, documented in Section 5, and a few functions in step3p.py, see Section 5.18, are used to perform the final tests. The contained function find small clones calls a minimality test (in parallel) for the 454 remaining functions, but for reasons of run time efficiency, it uses a hard-coded bound on the size of a computed ternary part of a clone. In case this bound is exceeded, the implementation of the minimality test may give no definite answer. The test identifies minimal clones (which turn out to contain 1,8,16 or 64 majority operations), eliminates non-minimal candidates and may leave some undecided cases. The last lines (after 630) of the file compute results A6.txt show that this takes less than 135 seconds, identifies 258 minimal functions and leaves 0 unclassified functions. Between the lines 174 – 628 one can see successful and failed minimality tests for varios candidates. The failed tests are due to an h∈ hfi(3) whose hhi(3) could be closed without exceeding the specified bound and is smaller than hfi(3). 8 MIKE BEHRISCH AND ANDREAS WACHTEL 3. Theory The following sections contain theory that justifies the completeness of the code. 3.1. Clones and their ternary parts. 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 cyclic function f∈cMaj{0,1} Aand 3 projections. This restriction is allowed, due to Machida’s lemma, which implies that every clone generated by an f∈Maj{0,1} Aalso contains a cyclic h∈cMaj{0,1} A. Lemma 1 ([Mac24]).Each f∈Maj{0,1} Apossesses a composition h∈cMaj{0,1} A. Proof. Define h(a, b, c):=ff(a, b, c), f(c, a, b), f(b, c, a).By [BVW25, Corollary 11] we get h∈Maj{0,1} A∪J (3) A.Moreover, since f∈Maj{0,1} Awe obtain h(2,3,4) ∈ {0,1},wherefore his not a projection and h∈Maj{0,1} A.To obtain that his cyclic on injective triples, we evaluate h(c, a, b) = ff(c, a, b), f(b, c, a), f(a, b, c) and realise that the triples are equal to those in the definition of h. Since fis {0,1}-valued on these, and the exterior fis a majority operation, it follows that h(a, b, c) = h(c, a, b) and his cyclic.  Definition 2. 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 3. Let f∈cMaj{0,1} A.Then, the clone generated by f, denoted hereafter by hfi, contains all projections JAand all compositions of fwith these projections and functions generated by such compositions. Properties related to the next function will reduce computations. Definition 4. 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 5. 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 5confirms the equality: hfi=e1, e2, e3, f, ¯ f, . . .=e1, e2, e3,¯ f, f, . . .=¯ f.(4) Given this equality we only have to check one of the functions f, ¯ f for minimality. However, to decide whether one of the two functions was already analysed, we need a convenient identification of f. The hash-value presented next turns out to be very convenient. { PARALLEL FINDING OF MINIMAL f∈cMaj{0,1} 6(PY) 9 3.2. Representing majority operations. The code separates the subset cMaj{0,1} Afrom the complete set Maj{0,1} A. 3.2.1. Cyclic majority operations. By (2) each f∈cMaj{0,1} Ais identified by its values on the increasing and decreasing triples. The code uses this idea to identify each f∈cMaj{0,1} Awith a hash-value Nf∈N.The values of fon increasing triples are associated to the first m=1 6k(k−1)(k−2) bits of an integer, and the values on decreasing triples to bits on the second mbits. For instance, on |A|=k= 5 we have m=1 6k(k−1)(k−2) = 10 and the bits {0,1,...,9}represent the values of fon increasing triples, whereas the bits {10,11,...,19} contain the values of fon decreasing triples, so the hash-value is: Nf:=x+y·210 with x:=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 y:=f2 1 020+f3 1 021+f4 1 022+f3 2 023+f4 2 024+f4 3 025+f3 2 126+f4 2 127+f4 3 128+f4 3 229. (5) The general hash-value: Nf:=x+y·2m with x:=f0 1 220+f0 1 321+. . . +fk−3 k−2 k−12m−1 y:=f2 1 020+f3 1 021+. . . +fk−1 k−2 k−32m−1. (6) The count: By (6) the number of 2 -valued cyclic majority operations f∈cMaj{0,1} Aon |A|=kis given by 22msince we have to consider values on mincreasing and mdecreasing triples. The largest hash-value is Nf≡1=P2m−1 i=0 2i= 22m−1,wherefore the code analyses functions with Nfin the set 0,1, . . . , 22m−1.(7) 3.2.2. Majority Operations. The code stores f∈Maj{0,1} Aas a pair of integers. This will be explained in Sections 5.5 and 5.7. 3.2.3. Hash-value of the reversed function. By Definition 4, the function ¯ freverses the triples ¯ f(x, y, z) = f(z, x, y),that is, each increasing triple becomes a decreasing triple and vice-versa. Now, taking Nf=x+y·2mand N¯ f= ¯x+ ¯y·2m,the 0 -th bit of ¯xencodes ¯ f(0,1,2),but ¯ f(0,1,2) = f(2,1,0) is also the 0 -th bit of y. Similarly, the 0 -th bit of ¯yencodes ¯ f(2,1,0) = f(0,1,2) which is also the 0 -th bit of x. This is valid on each triple and yields N¯ f=y+x·2m.(8) In Python, the following integer-bit operations give the value: x = Nf & (2**m -1) y=Nf>>m Nfrev = (x << m) + y { 16 MIKE BEHRISCH AND ANDREAS WACHTEL 67648945155 11110000|000000000000|111111111111|00000000 1 MO, fR5 = 462275 67653139463 11111100|000000000000|111111111111|00000000 1 MO, fR5 = 466375 67661528079 11111111|000000000000|111111111111|00000000 1 MO, fR5 = 466375 80530713600 00000000|000000000000|111100110000|11000000 1 MO, fR4 = 65600 84825684992 00000000|000000000000|111111110000|11000000 1 MO, fR4 = 196800 84826733569 11000000|000000000000|111111110000|11000000 1 MO, fR4 = 197825 102005570560 00000000|000000000000|111111111100|11000000 1 MO, fR4 = 459200 102006619137 11000000|000000000000|111111111100|11000000 1 MO, fR4 = 460225 102008716291 11110000|000000000000|111111111100|11000000 1 MO, fR4 = 462275 136365341696 00000000|000000000000|111111111111|11000000 1 MO, fR4 = 459200 136366390273 11000000|000000000000|111111111111|11000000 1 MO, fR4 = 460225 136368487427 11110000|000000000000|111111111111|11000000 1 MO, fR4 = 462275 136372681735 11111100|000000000000|111111111111|11000000 1 MO, fR4 = 462275 136373730312 00000011|000000000000|111111111111|11000000 1 MO, fR5 ~ 466375 136374778889 11000011|000000000000|111111111111|11000000 1 MO, fR5 ~ 462275 136376876043 11110011|000000000000|111111111111|11000000 1 MO, fR4 = 466375 136381070351 11111111|000000000000|111111111111|11000000 1 MO, fR4 = 466375 239444655104 00000000|000000000000|111111111100|11110000 1 MO, fR3 = 196800 239445703681 11000000|000000000000|111111111100|11110000 1 MO, fR3 = 197825 239447800835 11110000|000000000000|111111111100|11110000 1 MO, fR3 = 197825 239464578067 11110000|110000000000|111111111100|11110000 1 MO, fR3 = 197825 273804426240 00000000|000000000000|111111111111|11110000 1 MO, fR3 = 459200 273805474817 11000000|000000000000|111111111111|11110000 1 MO, fR3 = 460225 273807571971 11110000|000000000000|111111111111|11110000 1 MO, fR3 = 460225 273808620548 00001100|000000000000|111111111111|11110000 1 MO, fR5 ~ 462275 273809669125 11001100|000000000000|111111111111|11110000 1 MO, fR3 = 462275 273817009164 00001111|000000000000|111111111111|11110000 1 MO, fR5 ~ 462275 ----------------------------------------------------------- 7169 10000000|000000000000|101010000000|00000000 8 MO, fR5 = 193 1073748993 10000000|000000000000|111010000000|00000000 8 MO, fR5 = 65729 1073773571 10100000|000000000000|111010101000|00000000 8 MO, fR5 = 65987 1082184704 00000001|000000000000|110010001010|00000000 8 MO, fR4 = 70080 PARALLEL FINDING OF MINIMAL f∈cMaj{0,1} 6(PY) 17 3221232641 10000000|000000000000|111110000000|00000000 8 MO, fR5 = 196801 3221253122 00100000|000000000000|111100101000|00000000 8 MO, fR5 = 197058 3221257219 10100000|000000000000|111110101000|00000000 8 MO, fR5 = 197059 3229670400 00000001|000000000000|111110001010|00000000 8 MO, fR4 = 70080 7516199937 10000000|000000000000|111111000000|00000000 8 MO, fR5 = 196801 7516224514 00100000|000000000000|111111101000|00000000 8 MO, fR5 = 197058 7516224515 10100000|000000000000|111111101000|00000000 8 MO, fR5 = 197059 7517273091 11100000|000000000000|111111101000|00000000 8 MO, fR5 = 198083 7517469715 11100000|100000000000|111111101000|10100000 8 MO, fR5 = 198603 11811175425 10000000|000000000000|111110110000|00000000 8 MO, fR5 = 459201 11811191811 10100000|000000000000|111110111000|00000000 8 MO, fR5 = 459203 11811224583 10101000|000000000000|111110111010|00000000 8 MO, fR5 = 459207 11819613184 00000001|000000000000|111110111010|00000000 8 MO, fR4 = 70080 12884917249 10000000|000000000000|101011110000|00000000 8 MO, fR4 ~ 65729 13958659073 10000000|000000000000|111011110000|00000000 8 MO, fR4 = 196801 13958675459 10100000|000000000000|111011111000|00000000 8 MO, fR4 = 197059 13967094784 00000001|000000000000|110011111010|00000000 8 MO, fR2 = 70080 16106142721 10000000|000000000000|111111110000|00000000 8 MO, fR5 = 459201 16106159106 00100000|000000000000|111111111000|00000000 8 MO, fR4 = 197058 16106159107 10100000|000000000000|111111111000|00000000 8 MO, fR5 = 459203 16106188806 00101000|000000000000|010111111010|00000000 8 MO, fR2 = 65987 16106189830 00101000|000000000000|110111111010|00000000 8 MO, fR4 = 197058 16106191878 00101000|000000000000|111111111010|00000000 8 MO, fR4 = 197058 16106191879 10101000|000000000000|111111111010|00000000 8 MO, fR5 = 459207 16107207683 11100000|000000000000|111111111000|00000000 8 MO, fR5 = 460227 16107240455 11101000|000000000000|111111111010|00000000 8 MO, fR5 = 460231 16114580480 00000001|000000000000|111111111010|00000000 8 MO, fR2 = 70080 16115629056 01000001|000000000000|111111111010|00000000 8 MO, fR2 = 70080 16115629057 11000001|000000000000|111111111010|00000000 8 MO, fR2 = 70080 16183131137 11000001|000001000000|111111111010|00101000 8 MO, fR2 = 70080 32212286465 10000000|000000000000|101111111100|00000000 8 MO, fR3 = 196801 32212319237 10001000|000000000000|101111111110|00000000 8 MO, fR3 = 197059 18 MIKE BEHRISCH AND ANDREAS WACHTEL 33286028289 10000000|000000000000|111111111100|00000000 8 MO, fR5 = 459201 33286028291 10100000|000000000000|111111111100|00000000 8 MO, fR5 = 459203 33286061060 00001000|000000000000|111111111110|00000000 8 MO, fR3 = 197058 33286061061 10001000|000000000000|111111111110|00000000 8 MO, fR4 = 459201 33286061063 10101000|000000000000|111111111110|00000000 8 MO, fR5 = 459207 33287076867 11100000|000000000000|111111111100|00000000 8 MO, fR5 = 460227 33287109637 11001000|000000000000|111111111110|00000000 8 MO, fR3 = 198083 33287109639 11101000|000000000000|111111111110|00000000 8 MO, fR5 = 460231 33289206791 11111000|000000000000|111111111110|00000000 8 MO, fR5 = 462279 67645799425 10000000|000000000000|111111111111|00000000 8 MO, fR5 = 459201 67645799427 10100000|000000000000|111111111111|00000000 8 MO, fR5 = 459203 67645799431 10101000|000000000000|111111111111|00000000 8 MO, fR5 = 459207 67645799439 10101010|000000000000|111111111111|00000000 8 MO, fR5 = 459207 67646848003 11100000|000000000000|111111111111|00000000 8 MO, fR5 = 460227 67646848007 11101000|000000000000|111111111111|00000000 8 MO, fR5 = 460231 67646848015 11101010|000000000000|111111111111|00000000 8 MO, fR5 = 460231 67648945159 11111000|000000000000|111111111111|00000000 8 MO, fR5 = 462279 67648945167 11111010|000000000000|111111111111|00000000 8 MO, fR5 = 462279 67653139471 11111110|000000000000|111111111111|00000000 8 MO, fR4 = 462279 80530717697 10000000|000000000000|111110110000|11000000 8 MO, fR4 = 65729 80530734083 10100000|000000000000|111110111000|11000000 8 MO, fR4 = 65987 80530766855 10101000|000000000000|111110111010|11000000 8 MO, fR4 = 65987 80539155456 00000001|000000000000|111110111010|11000000 8 MO, fR4 = 70080 84825684993 10000000|000000000000|111111110000|11000000 8 MO, fR4 = 196801 84825701378 00100000|000000000000|111111111000|11000000 8 MO, fR4 = 197058 84825701379 10100000|000000000000|111111111000|11000000 8 MO, fR4 = 197059 84825734150 00101000|000000000000|111111111010|11000000 8 MO, fR4 = 197058 84825734151 10101000|000000000000|111111111010|11000000 8 MO, fR4 = 197059 84826749955 11100000|000000000000|111111111000|11000000 8 MO, fR4 = 198083 84826782727 11101000|000000000000|111111111010|11000000 8 MO, fR4 = 198083 84826881043 11100000|100000000000|111111111000|11100000 8 MO, fR4 = 198603 84826913815 11101000|100000000000|111111111010|11100000 8 MO, fR4 = 198603 PARALLEL FINDING OF MINIMAL f∈cMaj{0,1} 6(PY) 19 84827175991 11101000|101000000000|111111111010|11101000 8 MO, fR4 = 198603 84834122752 00000001|000000000000|111111111010|11000000 8 MO, fR2 = 70080 84835171328 01000001|000000000000|111111111010|11000000 8 MO, fR2 = 70080 84835171329 11000001|000000000000|111111111010|11000000 8 MO, fR2 = 70080 84902673409 11000001|000001000000|111111111010|11101000 8 MO, fR2 = 70080 102005570561 10000000|000000000000|111111111100|11000000 8 MO, fR4 = 459201 102005570563 10100000|000000000000|111111111100|11000000 8 MO, fR4 = 459203 102005603332 00001000|000000000000|111111111110|11000000 8 MO, fR3 = 197058 102005603333 10001000|000000000000|111111111110|11000000 8 MO, fR4 = 459201 102005603335 10101000|000000000000|111111111110|11000000 8 MO, fR4 = 459203 102006619139 11100000|000000000000|111111111100|11000000 8 MO, fR4 = 460227 102006651909 11001000|000000000000|111111111110|11000000 8 MO, fR3 = 198083 102006651911 11101000|000000000000|111111111110|11000000 8 MO, fR4 = 460227 102006914085 11001000|001000000000|111111111110|11001000 8 MO, fR3 = 198603 102006914087 11101000|001000000000|111111111110|11001000 8 MO, fR4 = 460227 102008749063 11111000|000000000000|111111111110|11000000 8 MO, fR3 = 198083 102009011239 11111000|001000000000|111111111110|11001000 8 MO, fR3 = 198603 102013991936 00000001|000000000000|111111111110|11000000 8 MO, fR4 ~~ 459201 102015040512 01000001|000000000000|111111111110|11000000 8 MO, fR5 ~~ 462279 102015040513 11000001|000000000000|111111111110|11000000 8 MO, fR4 ~~ 460227 102017137664 01010001|000000000000|111111111110|11000000 8 MO, fR5 ~~ 460231 102017137665 11010001|000000000000|111111111110|11000000 8 MO, fR5 ~~ 460227 102017137667 11110001|000000000000|111111111110|11000000 8 MO, fR4 ~~ 462279 136365341697 10000000|000000000000|111111111111|11000000 8 MO, fR4 = 459201 136365341699 10100000|000000000000|111111111111|11000000 8 MO, fR4 = 459203 136365341703 10101000|000000000000|111111111111|11000000 8 MO, fR4 = 459203 136365341704 00000010|000000000000|111111111111|11000000 8 MO, fR4 ~ 459201 136365341705 10000010|000000000000|111111111111|11000000 8 MO, fR5 ~ 462279 136365341707 10100010|000000000000|111111111111|11000000 8 MO, fR4 = 459207 136365341711 10101010|000000000000|111111111111|11000000 8 MO, fR4 = 459207 136366390275 11100000|000000000000|111111111111|11000000 8 MO, fR4 = 460227 136366390279 11101000|000000000000|111111111111|11000000 8 MO, fR4 = 460227 20 MIKE BEHRISCH AND ANDREAS WACHTEL 136366390281 11000010|000000000000|111111111111|11000000 8 MO, fR4 ~ 460227 136366390283 11100010|000000000000|111111111111|11000000 8 MO, fR4 = 460231 136366390287 11101010|000000000000|111111111111|11000000 8 MO, fR4 = 460231 136368487431 11111000|000000000000|111111111111|11000000 8 MO, fR3 = 460227 136368487435 11110010|000000000000|111111111111|11000000 8 MO, fR4 = 462279 136368487439 11111010|000000000000|111111111111|11000000 8 MO, fR4 = 462279 136372681743 11111110|000000000000|111111111111|11000000 8 MO, fR4 = 462279 136373730313 10000011|000000000000|111111111111|11000000 8 MO, fR5 ~ 462279 136373730315 10100011|000000000000|111111111111|11000000 8 MO, fR5 ~ 460231 136373730319 10101011|000000000000|111111111111|11000000 8 MO, fR5 ~ 459207 136374778891 11100011|000000000000|111111111111|11000000 8 MO, fR5 ~ 460227 136374778895 11101011|000000000000|111111111111|11000000 8 MO, fR5 ~ 459203 136376876047 11111011|000000000000|111111111111|11000000 8 MO, fR5 ~ 459201 239444655105 10000000|000000000000|111111111100|11110000 8 MO, fR3 = 196801 239444655107 10100000|000000000000|111111111100|11110000 8 MO, fR3 = 196801 239444687876 00001000|000000000000|111111111110|11110000 8 MO, fR3 = 197058 239444687877 10001000|000000000000|111111111110|11110000 8 MO, fR3 = 197059 239444687879 10101000|000000000000|111111111110|11110000 8 MO, fR3 = 197059 239445703683 11100000|000000000000|111111111100|11110000 8 MO, fR2 = 196801 239445703699 11100000|100000000000|111111111100|11110000 8 MO, fR2 = 196801 239445736453 11001000|000000000000|111111111110|11110000 8 MO, fR3 = 198083 239445736455 11101000|000000000000|111111111110|11110000 8 MO, fR3 = 198083 239445736471 11101000|100000000000|111111111110|11110000 8 MO, fR3 = 198083 239447833607 11111000|000000000000|111111111110|11110000 8 MO, fR3 = 198083 273804426241 10000000|000000000000|111111111111|11110000 8 MO, fR3 = 459201 273804426243 10100000|000000000000|111111111111|11110000 8 MO, fR3 = 459201 273804426244 00001000|000000000000|111111111111|11110000 8 MO, fR5 ~ 462279 273804426245 10001000|000000000000|111111111111|11110000 8 MO, fR3 = 459203 273804426247 10101000|000000000000|111111111111|11110000 8 MO, fR3 = 459203 273804426252 00001010|000000000000|111111111111|11110000 8 MO, fR5 ~ 462279 273804426253 10001010|000000000000|111111111111|11110000 8 MO, fR3 = 459207 273804426255 10101010|000000000000|111111111111|11110000 8 MO, fR3 = 459207 PARALLEL FINDING OF MINIMAL f∈cMaj{0,1} 6(PY) 21 273805474819 11100000|000000000000|111111111111|11110000 8 MO, fR2 = 459201 273805474821 11001000|000000000000|111111111111|11110000 8 MO, fR3 = 460227 273805474823 11101000|000000000000|111111111111|11110000 8 MO, fR3 = 460227 273805474829 11001010|000000000000|111111111111|11110000 8 MO, fR3 = 460231 273808620549 10001100|000000000000|111111111111|11110000 8 MO, fR5 ~ 460227 273808620556 00001110|000000000000|111111111111|11110000 8 MO, fR4 ~ 462279 273808620557 10001110|000000000000|111111111111|11110000 8 MO, fR5 ~ 460227 ----------------------------------------------------------- 11811290119 10101000|000000000000|111110111010|10000000 16 MO, fR5 = 459719 16106257415 10101000|000000000000|111111111010|10000000 16 MO, fR5 = 459719 33286126599 10101000|000000000000|111111111110|10000000 16 MO, fR5 = 459719 67645864967 10101000|000000000000|111111111111|10000000 16 MO, fR5 = 459719 67645864975 10101010|000000000000|111111111111|10000000 16 MO, fR5 = 459719 67645996047 10101010|000000000000|111111111111|10100000 16 MO, fR5 = 459719 67646127119 10101010|000000000000|111111111111|10001000 16 MO, fR5 = 459719 67646258191 10101010|000000000000|111111111111|10101000 16 MO, fR5 = 459719 67646782479 10101010|000000000000|111111111111|10101010 16 MO, fR5 = 459719 67647372303 11101010|000000000000|111111111111|00000010 16 MO, fR2 = 459719 102017268736 01010001|000000000000|111111111110|11100000 16 MO, fR4 ~~ 459719 136365472779 10100010|000000000000|111111111111|11100000 16 MO, fR4 = 459719 136365472783 10101010|000000000000|111111111111|11100000 16 MO, fR4 = 459719 136365734927 10101010|000000000000|111111111111|11101000 16 MO, fR4 = 459719 136365931535 10101010|000000000000|111111111111|01100010 16 MO, fR4 = 459719 136365997071 10101010|000000000000|111111111111|11100010 16 MO, fR4 = 459719 136366128143 10101010|000000000000|111111111111|11001010 16 MO, fR3 = 459719 136366193679 10101010|000000000000|111111111111|01101010 16 MO, fR4 = 459719 136366914575 11101010|000000000000|111111111111|11000010 16 MO, fR2 = 459719 411243838479 10101010|000000000000|111111111111|01100110 16 MO, fR4 = 459719 ----------------------------------------------------------- 16107273219 11100000|000000000000|111111111000|10000000 64 MO, fR5 = 460739 16107289605 11001000|000000000000|111111110010|10000000 64 MO, fR5 = 460741 33287142403 11100000|000000000000|111111111100|10000000 64 MO, fR5 = 460739 22 MIKE BEHRISCH AND ANDREAS WACHTEL 33287175173 11001000|000000000000|111111111110|10000000 64 MO, fR5 = 460741 33287240711 11101000|000000000000|111111111110|00100000 64 MO, fR4 = 460739 33287273475 11100000|000000000000|111111111100|10100000 64 MO, fR5 = 460739 33288190979 10110000|000000000000|111111111100|10000000 64 MO, fR5 ~ 460741 33288223750 00111000|000000000000|111111111110|10000000 64 MO, fR5 ~ 460739 33288289287 10111000|000000000000|111111111110|00100000 64 MO, fR4 ~ 460741 33288322051 10110000|000000000000|111111111100|10100000 64 MO, fR5 ~ 460741 67646913539 11100000|000000000000|111111111111|10000000 64 MO, fR5 = 460739 67646913541 11001000|000000000000|111111111111|10000000 64 MO, fR5 = 460741 67646913547 11100010|000000000000|111111111111|10000000 64 MO, fR5 = 460739 67646913549 11001010|000000000000|111111111111|10000000 64 MO, fR5 = 460741 67647044611 11100000|000000000000|111111111111|10100000 64 MO, fR5 = 460739 67647044621 11001010|000000000000|111111111111|10100000 64 MO, fR5 = 460741 67647241223 11101000|000000000000|111111111111|00101000 64 MO, fR4 = 460739 67647241225 11000010|000000000000|111111111111|00101000 64 MO, fR4 = 460741 67649207303 11111000|000000000000|111111111111|00001000 64 MO, fR3 = 460739 67649207307 11110010|000000000000|111111111111|00001000 64 MO, fR3 = 460741 67649731591 11111000|000000000000|111111111111|00001010 64 MO, fR3 = 460739 67649731595 11110010|000000000000|111111111111|00001010 64 MO, fR3 = 460741 102006750211 11100000|000000000000|111111111100|11100000 64 MO, fR4 = 460739 102006782983 11101000|000000000000|111111111110|11100000 64 MO, fR4 = 460739 102007045159 11101000|001000000000|111111111110|11101000 64 MO, fR4 = 460739 102007798787 10110000|000000000000|111111111100|11100000 64 MO, fR4 ~ 460741 102007831559 10111000|000000000000|111111111110|11100000 64 MO, fR4 ~ 460741 102008355975 10111000|000000100000|111111111110|11100010 64 MO, fR4 ~ 460741 102015171585 11000001|000000000000|111111111110|11100000 64 MO, fR4 ~~ 460739 102016220162 00110001|000000000000|111111111110|11100000 64 MO, fR4 ~~ 460741 136366521347 11100000|000000000000|111111111111|11100000 64 MO, fR4 = 460739 136366521351 11101000|000000000000|111111111111|11100000 64 MO, fR4 = 460739 136366521353 11000010|000000000000|111111111111|11100000 64 MO, fR4 = 460741 136366521357 11001010|000000000000|111111111111|11100000 64 MO, fR4 = 460741 136366783495 11101000|000000000000|111111111111|11101000 64 MO, fR4 = 460739 PARALLEL FINDING OF MINIMAL f∈cMaj{0,1} 6(PY) 23 136366783497 11000010|000000000000|111111111111|11101000 64 MO, fR4 = 460741 136367569923 10110000|000000000000|111111111111|11100000 64 MO, fR4 ~ 460741 136367569927 10111000|000000000000|111111111111|11100000 64 MO, fR4 ~ 460741 136367569930 00110010|000000000000|111111111111|11100000 64 MO, fR4 ~ 460739 136367569934 00111010|000000000000|111111111111|11100000 64 MO, fR4 ~ 460739 136368749575 11111000|000000000000|111111111111|11001000 64 MO, fR3 = 460739 136368749579 11110010|000000000000|111111111111|11001000 64 MO, fR3 = 460741 136369273863 11111000|000000000000|111111111111|11001010 64 MO, fR3 = 460739 136369273867 11110010|000000000000|111111111111|11001010 64 MO, fR3 = 460741 136370322439 10101100|000000000000|111111111111|11001010 64 MO, fR3 ~ 460741 136371108871 11101100|000000000000|111111111111|11000010 64 MO, fR2 ~ 460741 136371108877 11001110|000000000000|111111111111|11000010 64 MO, fR2 ~ 460739 136372026382 00111110|000000000000|111111111111|11101000 64 MO, fR4 ~ 460739 136373861385 10000011|000000000000|111111111111|11100000 64 MO, fR4 ~ 460739 136373861386 00100011|000000000000|111111111111|11100000 64 MO, fR4 ~ 460741 136373861389 10001011|000000000000|111111111111|11100000 64 MO, fR4 ~ 460739 136373861390 00101011|000000000000|111111111111|11100000 64 MO, fR4 ~ 460741 136374123534 00101011|000000000000|111111111111|11101000 64 MO, fR4 ~ 460741 136374516747 10100011|000000000000|111111111111|11001010 64 MO, fR3 ~ 460739 136375303179 11100011|000000000000|111111111111|11000010 64 MO, fR2 ~ 460739 136375303181 11001011|000000000000|111111111111|11000010 64 MO, fR2 ~ 460741 24 MIKE BEHRISCH AND ANDREAS WACHTEL 5. Libraries and files 5.1. lib constants.py.This is THE central place where the constant |A|=k∈ {4,5,6}is set. All routines use this constant. 5.2. Functions in hlib progress.py.This auxiliary library only contains functions to save and load partial results. They are expected to be self-explanatory. The idea is to save candidates of minimal functions as integers using the representation given in equation (6). 5.3. Functions in hlib TicToc.py.This auxiliary library only contains functions to measure and print time. They are expected to be self-explanatory. 5.4. Functions in lib integerBitManipulation.py.Some bitmagic functions. They are expected to be self-explanatory. 5.5. Functions in lib tuplePositionBij.py.The number of injective triples on Ais M:=k(k−1)(k−2) where kis defined in lib constants.py. This library establishes a bijection between the set {0,1, . . . , M −1}and the Minjective triples respecting their lexicographic order, which is illustrated in Section 5.5.4. 5.5.1. triple 2 MObit.Given one of Minjective triples as three integers t0, t1, t2, this function returns the unique position in {0,1, . . . , M −1}that is associated to this triple. 5.5.2. MObit 2 triple.Given a position i∈ {0,1, . . . , M −1},this function returns the associated triple t0, t1, t2 of the Minjective triples. 5.5.3. get A.This function returns the tuple A= (0,1,2, . . . , k−1). 5.5.4. Storing majority Operations. The values of f∈Maj{0,1} A evaluated at the Minjective triples will be stored in a new datatype that contains two integers to save up to 120 bits. The association of each injective triple and value-position is given by the bijection implemented in the functions MObit 2 triple and triple 2 MObit. The order is the lexicographic order. Running python lib tuplePositionBij.py shows both the triple-order and the bijection. The output for |A|= 6 starts and ends as follows: 0 MObit_2_triple(bit) = (0, 1, 2) triple_2_MObit(tuple) = 0 1 MObit_2_triple(bit) = (0, 1, 3) triple_2_MObit(tuple) = 1 2 MObit_2_triple(bit) = (0, 1, 4) triple_2_MObit(tuple) = 2 3 MObit_2_triple(bit) = (0, 1, 5) triple_2_MObit(tuple) = 3 4 MObit_2_triple(bit) = (0, 2, 1) triple_2_MObit(tuple) = 4 ... 119 MObit_2_triple(bit) = (5, 4, 3) triple_2_MObit(tuple) = 119 Since these are 120 triples, a majority operation f∈Maj{0,1} 6requires 120 bits to be stored. We use a new data-type to do that, see Section 5.6. The reasons are as follows: •Pure software integers produced a slower code. •Unfortunately, the software integers of python and the numpy 64bit integers are not compatible if the used bits exceed 63. Moreover, integer bit-shifting using the software and hardware types gives undesired results due to implicit type-conversion. For instance, 1 << np.int64( 64 ) == 0 (in python 3.9). In order to avoid implicit conversions and unexpected wrong results, we use the new object-type. PARALLEL FINDING OF MINIMAL f∈cMaj{0,1} 6(PY) 25 5.6. Functions in lib integer120.py.Section 5.5.4 shows 120 injective triples, wherefore we need 120 bits to store the values of f∈Maj{0,1} Awhen |A|= 6.Aside from a few conversion routines, which are expected to be self-explanatory, this library defines: 5.6.1. Bag.A data-type that pairs two integers (hi, lo) where lo is used to store the values of f∈Maj{0,1} Aat the first 60 triples, and hi to store the values at the triples 61–120. The Bag data-type was modified from an example given in the numba-documentation, [A+20]. Using it avoids passing the two integers as two separate arguments to every composition or clone-closing function while still maintaining an efficient pre-compiled data access. { 5.7. Functions in lib CSMO.py.Running python lib CSMO.py illustrates a few functionalities. Constants, like the number of injective triples M=k(k−1)(k−2) and the number of increasing triples m=M/6,set in lib constants.py, are heavily used. 5.7.1. triplesCS.This constant array is generated by an internal function called getTriplesCS and contains increasing followed by decreasing injective triples in the order illustrated in equation (6) as rows of a 2m×3 matrix. 5.7.2. getCSMO.This function converts a given hash-value Nf∈N, see (6), into a {0,1}-valued majority operation represented by a Bag containing a pair of integers to store up to 120 values of f∈cMaj{0,1} A,that is, the code allows |A| ∈ {4,5,6}. For each monotone triple, given by a row r∈ {0,...,2m−1} of triplesCS, the bit rof Nfis copied to 3 positions in {0, . . . , M −1}calculated by triple 2 MObit applied to the 3 cyclically shifted versions of the monotone triple, see (2). Hence, the value at 3 positions came from one bit rof Nf.The information where bits came from is also saved in an array generated by get mob 2 csb. 5.7.3. get mob 2 csb.Generates an array mob 2 csb that represents the following map {0, . . . , M −1}→{0,...,2m−1}.For each 0≤i < M let (x, y, z) the be the result of MObit 2 triple. Exactly, one of the three cyclically shifted versions (x, y, z),(z, x, y) and (y, z, x) appears among the 2mrows of triplesCS, and moreover, if appears in a unique row 0 ≤r < 2mas triplesCS [r]. This unique ris the function value at i, that is, mob 2 csb[i]=r. The abbreviation mob 2 csb stands for “MObit” to “CSbit”. 5.7.4. splitNf.Given a hash-value Nf∈N,this function returns the two associated integers x, y ∈ {0, . . . , 2m−1},see (6). 5.7.5. fbar.Given a hash-value Nf∈N,see (6), this function returns the value N¯ fof the reversed function ¯ fdefined in (8). This function is only used to reconstruct functions with hash-values outside the green or turquoise area shown in Section 3.4. { 32 MIKE BEHRISCH AND ANDREAS WACHTEL 5.14. Functions in lib permutations.py.The functions in here implement general permutations φ:A→Athat preserve the set {0,1}and therefore also A\ {0,1}.They will be used to remove conjugates. Running python lib permutations.py shows all permutations for Awhose size is defined by lib constants.py. The idea is to show that all necessary permutations are contained. 5.14.1. get permutations.This function uses python’s itertool.permutations to return all bijections from Definition 9, i.e.,φ:A→Athat preserve {0,1},as rows of a returned matrix. 5.14.2. permutation txt2tuple.This internal function converts a permutation given by a string into an array. 5.14.3. permutation txt2tuple.This internal function converts a permutation given by an array into a string containing its decomposition into disjoint cycles. { 5.15. Functions in lib conjugates.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.6. Running python lib conjugates.py calculates the 96 conjugates and reversed conjugates of Nf= 7465 and shows that 48 of them belong to (9) and only 24 belong to the turquoise set, see Algorithm 3.1. 5.15.1. triple 2 CSbit.Uses triple 2 MObit to convert an injective triple to a MObit ∈ {0, . . . , M −1}and the map from get mob 2 csb to convert this bit into the CSbit ∈ {0,...,2m−1}. Idea: Using the map mob 2 csb avoids determining if a permuted triple (φ(a), φ(b), φ(c)) is increasing or decreasing, then ordering it and finally searching for the ordered monotone triple in triplesCS to retrieve the bit-position after φ. 5.15.2. csbit o phi.Given a permutation φ:A→Aas an array phi, this function generates a vector that maps the position of each cyclic injective triple pos(a, b, c)∈ {0,1,...,2m−1}to the position triple 2 CSbitφ(a), φ(b), φ(c)∈ {0,1,...,2m−1},i.e. the bitposition after the permutation φ. This vector is used to establish the equality φNgpos(a, b, c) =Nfposφ(a), φ(b), φ(c),representing Definition 6. Also, the vector is constant for a given φ, so it can be reused to calculate φ-conjugates of many f∈cMaj{0,1} A. 5.15.3. calc conjugate CS.Given an f∈cMaj{0,1} Aby its hashvalue Nf,the result of csbit o phi applied to φas an array and the value φ(0),this function constructs and returns Ngassociated to g:=φ−1◦f◦φ(3). 5.15.4. get conjugates.Given f∈cMaj{0,1} Aby its hash-value Nf given by (6), this function generates and returns the set of all hashvalues Ngthat represent conjugates and reversed conjugates of f. This is done using all permutations given by get permutations, the function calc conjugate CS and fbar. { PARALLEL FINDING OF MINIMAL f∈cMaj{0,1} 6(PY) 33 5.16. Functions in step2s.py.The functions in here perform the reduction of minimal candidates left from step 1 down to a list of unique representatives up to conjugacy or “reversed” conjugacy. Running python step2s.py invokes the function runStep2 and saves its results. 5.16.1. remove phi conjugates.Given a few f∈cMaj{0,1} Arepresented by integers in a given increasingly ordered list candF and one permutation φ:A→Aas an array phi, this function generates a reduced new list of “smaller” conjugates. The function will go through all Nfin the list (starting with the smallest), and calculate for each Nfthe hash-values of f, ¯ f, g, ¯gwhere g=φ−1◦f◦φ(3) is generated by calc conjugate CS. The smallest of these values is added to a new list which is returned. Note: Step 1 only leaves Nfwith Nf≤N¯ f,wherefore this function directly ignores the value N¯ f. 5.16.2. eliminate conjugates.Given a few f∈cMaj{0,1} Arepresented by integers in a given list candF, this function uses all permutations φ:A→Apreserving {0,1}defined by get permutations, and eliminates conjugates g∈cMaj{0,1} Afor all f∈cMaj{0,1} Afrom the argument candF using the function remove phi conjugates. The result is that each remaining Nfin candF will be the smallest and only hash-value left from its equivalence class [[Nf]],see Definition 10, (the set of all conjugates or “reversed” conjugates). 5.16.3. assert least conjugates.This function receives a few f∈cMaj{0,1} Auniquely represented by their hash-value in a unique sorted list of numbers candF and verifies that each entry Nfis the smallest in its equivalence class [[Nf]],see Definition 10. 5.16.4. runStep2.This function accepts 2 optional arguments. If the first, candF, is not present, then previously saved results of runStep1 are expected to exist and loaded, otherwise candF should contain a list of hash-values. After that, the function eliminate conjugates is called to reduce candF, which is later returned as the result and saved to a file if the second optional parameter save results is True. The result contains the least (possibly reversed) conjugates, which is verified by assert least conjugates, and it is also verified that all (possibly reversed) conjugates of the remaining least representatives contain the initial set of functions. Reductions. On |A|= 5,kept fof runStep2 after runStep1: ylim f of step 1 Function kept f ------------ ------------ ---------- -------- 2^9 117 runStep2 29 2^10 196 runStep2 29 Reductions. On |A|= 6,kept fof runStep2 after runStep1: yLim f of step 1 Function kept f ------------ ------------ ---------- -------- 2^19 9954 runStep2 454 2^20 15488 runStep2 454 The most important observation from these numbers is that the number of kept functions after step 2 is the same. I.e., all functions left after step 1 with the bigger limit for yare conjugates or “reversed” conjugates of the functions with the smaller ylimit. { 34 MIKE BEHRISCH AND ANDREAS WACHTEL 5.17. Functions in lib CSMO clones.py.This library implements clone-closing algorithms (described in Section 3.7) and the sufficient minimality given by (10). The minimality test also relies on the following general fact. Lemma 13. If h∈ hfi(3),then hhi(3) ⊆ hfi(3). Proof. Let h∈ hfi(3).Since hfiis a clone containing h, we have hhi ⊆ hfi,hence hhi(3) ⊆ hfi(3). 5.17.1. closeF cs.Given an f∈cMaj{0,1} Aas a Bag, an upper bound bigN and an optional logical quiet with default value False, this function generates hfi(3),or a part of it, as a list Fc using Algorithm 3.3 with the enumeration described in [Wac24, Section 3.6.4]. The list Fc contains projections and compositions generated by get projections and compose gen as integer pairs (high, low) each of which represents a Bag. This allows to have the core part of this function look exactly as the one in [Wac24]. For a given bound bigN the list Fc will at most have bigN + bigN*(bigN-1)*(bigN-2)/3 entries, which follows because a list F= [f1, . . . , fbigN] may generate up to bigN*(bigN-1)*(bigN-2)/3 additional compositions because fis cyclic, see [Wac24, Section 3.6.2]. closeF cs returns the pair (keep,Fc), where Fc is the generated list and keep ∈ {True,False}is set to True iff no function represented in the list Fc preserves more subsets than f. Attention: The following is used in Step 3: If the closing was completed, then len(Fc) ≤bigN and abusing notation we think of Fc =hfi(3) because Fc is a discrete representation of hfi(3). 5.17.2. find f in clone h.Given a list Fh= [e1, e2, e3, h] with h∈Maj{0,1} Aand an f∈cMaj{0,1} Aas a pair of integers f2bfound = (high, low), this function attempts to decide whether fbelongs to H⊆ hhi(3),where His computed from Fhup to a limited size bigN with default value 18. This is done using Algorithm 3.3, with the enumeration described in [Wac24, Section 3.6.4] and the modification that line 7adds 6 compositions, and stops when the size limit triggers abortion of the closure process. The return value is: •True, if f2bfound was found in H. •False, if |H| ≤ bigN and f2bfound was not found in H. •None,|H|>bigN and f2bfound was not found in H. 5.17.3. miniTest.Given a ternary part of a clone hfias a list Fc = [e1, e2, e3, f, h1, . . . , h`],that was possibly partially computed by closeF cs with a size limit bigN, this function verifies the sufficient minimality condition (10), that is, for each hiit calls find f in clone h to verify whether fbelongs to hhii.Naturally, this is expensive, as these `clones have to be generated to confirm that hfiis minimal. There are 3 cases. The first one is that there is some 1 ≤i≤` where find f in clone h applied to fand hireturns False. Then provably f6∈ hhii(3) (hfi(3) and miniTest (correctly) returns False. The opposite situation is that find f in clone h (f, hi) returns True or None for each i∈ {1, . . . , `}.As a (second) subcase we consider then that |Fc| ≤ bigN.Under the condition |Fc| ≤ bigN, we also have |hhii(3)| ≤ bigN by Lemma 13. Thus, in this case all results of find f in clone h will belong to {True,False}; hence all must be True.miniTest identifies this second case by testing PARALLEL FINDING OF MINIMAL f∈cMaj{0,1} 6(PY) 35 whether all results are True and |Fc| ≤ bigN,and then correctly returns True because (10) yields that hfiis indeed minimal in this case. The third and final situation is the opposite subcase, i.e., where the first case fails and |Forg|>bigN.Here miniTest cannot achieve a definite decision and returns None. In our calls to miniTest the parameter bigN was chosen in such a way that fortunately this third case never occurred, cf. Section 5.18.3. { 5.18. Functions in step3p.py.The functions in here verify if the remaining candidates f∈cMaj{0,1} Aof runStep2 satisfy sufficient conditions for minimality, as mentioned in Section 3.7. 5.18.1. isMinimal 3WL.This function receives f∈cMaj{0,1} Aas its hash-value Nf and uses closeF cs with bigN = 67, to generate the tuple (keep,Fc), where Fc is a (possibly incomplete) subset of hfi(3) and keep is a logical. The function returns the triple (Nf, decision, len(Fc)) where the decision takes one of the values {True, False, None}.The value is chosen as follows: If keep is False, then a composition hof fthat preserved more subsets was found and fis not minimal and decision = False. In the remaining situations keep is True, and the decision is based on the size of Fc and the result of an executed miniTest as follows: •If |Fc| ≤bigN , then the miniTest gives a logical decision passed ∈ {True, False},as described in miniTest. So decision = passed is used. •Otherwise, when |Fc| > bigN,then miniTest will give passed ∈ {False, None},because Fc was not closed in the first place. Again, decision = passed will be used. 5.18.2. find small clones.This function requires the minimal candidates in form of list candF. Inside, for each candidate hashvalue Nfin candF the function isMinimal 3WL is called. After all calls have finished, the results are in memory in a list containing the triples (Nf, decision, len(Fc)). Each triple is split, in order to decide what to do with Nf.If decision is None, then Nfis put into a list notClassified. If False, then Nfis removed from candF. If True, the third result len(Fc) is used to classify the found minimal Nfby their ternary clone sizes 1,8,16,64 (this count does not include the 3 projections) into four lists. The updated candidates candF, the four lists of minimal Nfand the notClassified list are returned for reporting. 5.18.3. runStep3.This function receives the result of runStep2 or loads a previously saved list of candidates as candF. Then, this list is passed on to find small clones and its results are evaluated and printed. The remaining candidates are saved to a file if the optional parameter save results is True. Reductions. On |A|∈{5,6},kept fof runStep3 after runStep2: On |A| f of step 2 Function kept f ------------- ------------ ---------- -------- {0,1,2,3,4} 29 runStep3 26 {0,1,2,3,4,5} 454 runStep3 258 Most importantly, the output, in the included log-file compute results A6.txt, shows that the notClassified list is empty. In order words, all eliminated functions were not minimal and all remaining functions generate minimal clones with pmajority operations where p∈ {1,8,16,64}. { 36 MIKE BEHRISCH AND ANDREAS WACHTEL Attention : Functions in the following files are only used for post-processing and were not used to identify the minimal functions for |A|>4. 5.19. Functions in show results.py.Running python show results.py will print the complete table sketched in Section 1.2. The printed hash-values are hard-coded in get minimals A6 AW. All other data is prepared and printed by other functions. The presentation is designed for |A| ∈ {4,5,6}. 5.19.1. get minimals A6 AW.Returns four hard-coded lists of hashvalues of the unique minimal f∈cMaj{0,1} 6separated by the number of majority operations that belong to the minimal clones in each list. Other functions, that are considered self-explanatory: •getTriplesCS Table – returns triples in (6) in table order. •get decimal len – gives bound on decimals of hash-values. •get bar positions – gives positions of “|” in tables. •print table head – prints triples at top of tables. •print one hashvalue – prints bits in table order. •print hashvalues – similar, but for many hash-values. •count minimals – given a list of unique (non-equivalent) minimals, it generates all equivalent minimals (by get conjugates) and counts them. •count all – takes the minimals of get minimals A6 AW or get minimals A5 AW in the four lists, and uses count minimals to count all minimal cyclic f∈cMaj{0,1} Afor |A|=k. { 5.20. Functions in lib minimals A5.py.This file contains everything needed to construct conjugates of minimal fon |A|= 5 and also the functionality to get the least conjugate of a given f∈cMaj{0,1} 5.All the functionality is based on code in [Wac24]. The file also provides the hash-values of the 26 minimals on {0,1,2,3,4}, see also [BVW25, Table 1] or the log file show results A5.txt. 5.20.1. get minimals A5 AW.Returns four hard-coded lists of hashvalues of the unique minimal f∈cMaj{0,1} 5separated by the number of majority operations that belong to the minimal clone. 5.20.2. reverse Nf k5.A specialized fbar. 5.20.3. get least conjugate k5.Calculates the smallest hashvalue of a conjugate of f∈cMaj{0,1} 5given by a hash-value f20 without the reversed conjugates. To implement this functionality, the library also contains the following functions specialized to |A|=5: •triple 2 MObit k5 a specialized triple 2 MObit. •get mob 2 csb k5 a specialized get mob 2 csb. •triple 2 CSbit k5 a specialized triple 2 CSbit. •csbit o phi k5 a specialized csbit o phi. •get conjugate k5 a specialized calc conjugate CS. •get equiclass k5 a specialized get conjugates. { PARALLEL FINDING OF MINIMAL f∈cMaj{0,1} 6(PY) 37 5.21. Functions in lib restrict to k5.py.This file provides functions that allow to detect whether a restriction of a minimal f∈cMaj{0,1} 6to a 5-element set Ue:={0,1, a, b, c}=A\ {e} is isomorphic to a minimal function in cMaj{0,1} 5.Similar to Section 5.9 we identify f|Uewith a function in cMaj{0,1} 5via a bijection ρe:Ue→ {0,1,2,3,4}which is always given as follows: ρe(x) = x for x<e and ρe(x) = x−1 for x > e. The restriction to a five-element set Ueafter identification lives on {0,1,2,3,4}and is denoted by fRe,to also show which element e∈Awas removed. 5.21.1. f40 U01234.Given f∈cMaj{0,1} 6as a hash-value f40 this function returns the 20-bit hash-value fR5 of the restriction fR5, that is, frestricted to U5={0,1,2,3,4}as the name suggests. The next internal functions are similar but use identification, i.e., fRe(x, y, z) = ρef|Ue(ρ−1 e(x), ρ−1 e(y), ρ−1 e(z))where the outer ρe is not required, due to f∈cMaj{0,1} Aand ρe(0) = 0 and ρe(1) = 1. •f40 U01235 returns the 20-bit hash-value fR4 of fR4, •f40 U01245 returns the 20-bit hash-value fR3 of fR3, •f40 U01345 returns the 20-bit hash-value fR2 of fR2. 5.21.2. iso restrict k5.This function receives a hash-value f40 identifying an f∈cMaj{0,1} 6and a list samesize k5 of hash-values of minimal functions from cMaj{0,1} 5that generate a clone with the same number of majority operations as f. The function returns True and the string of the first of the following occurring cases: •“ fRe=fRe ” if fRe belongs to the list samesize k5. •“ fRe∼get least conjugate k5(fRe) ” if the least conjugate of fRe belongs to the list samesize k5. •“ fRe∼∼ get least conjugate k5(reverse Nf k5(fRe)) ” if the least reversed conjugate of fRe belongs to samesize k5. Each condition is checked for e∈ {5,4,3,2}before continuing with the next point. If none of the conditions applies, then False and an empty string are returned. { 5.22. Functions in step4 iso.py.This is a structure-analysis step. It takes the minimal functions f∈cMaj{0,1} 6on |A|= 6 identified and saved by Step 3 or gets the hard-coded results from show results.py as a list. This list is passed to an internal function find isomorphisms which classifies the minimals by their “ternary clone sizes”, i.e., by their numbers of generated majority operations, and uses the function iso restrict k5 to verify whether a restriction to a preserved 5-element-set {0,1, a, b, c}=A\ {e}is isomorphic to a minimal hash-value on A= 5 that additionally identifies a minimal clone of the same “ternary size”. The idea of using “ = ”, “ ∼” and “ ∼∼ ” is to denote when a restriction fRe is equal “ = ”, or a conjugate “ ∼”, or conjugate to a reversed function “ ∼∼ ” to one of the 26 minimal hash-values of the same ternary clone size. Running python step4 iso.py recalculates and prints the table shown in Section 4. { 38 MIKE BEHRISCH AND ANDREAS WACHTEL 6. List of files •compute_results.py – Python script that recomputes the minimal functions. It is documented in Section 1.3. Included log files: compute_results_Ak.txt for k∈ {4,5,6}. •lib_constants.py – see Section 5.1. •hlib_progress.py – see Section 5.2. •hlib_TicToc.py – see Section 5.3. •lib_integerBitManipulation.py – see Section 5.4. •lib_tuplePositionBij.py – see Section 5.5. •lib_integer120.py – see Section 5.6. •lib_CSMO.py – see Section 5.7. •lib_minimals_A4.py – see Section 5.8. •lib_restrict_to_k4.py – see Section 5.9. •lib_quick_compose.py – see Section 5.10. •lib_preserve.py – see Section 5.11. •lib_keepCandidates.py – see Section 5.12. Some speed tests were generated with the included file xst_keep.py. •step1y.py – Internal script that reduces candidates by checking necessary conditions, see Sections 2.2 and 5.13. •lib_permutations.py – see Section 5.14. •lib_conjugates.py – see Section 5.15. •step2s.py – Internal script that eliminates (potentially reversed) conjugates within candidates, see Sections 3.6 and 5.16. •lib_CSMO_clones.py – see Section 5.17. •step3p.py – Internal script that checks sufficient minimality conditions, see Section 5.18. Post-processing •show_results.py – Python script that shows hard-coded results (minimal functions), documented in Sections 1.2 and 5.19. Short log files: show_results_Ak.txt for k∈ {4,5,6}.Document external tables for all minimals on |A|=k∈ {5,6}: all_minimals_A6_01mo.txt,all_minimals_A6_08mo.txt, all_minimals_A6_16mo.txt and all_minimals_A6_64mo.txt. all_minimals_A5_01mo.txt,all_minimals_A5_08mo.txt, all_minimals_A5_16mo.txt and all_minimals_A5_64mo.txt. •lib_minimals_A5.py – see Section 5.20. •lib_restrict_to_k5.py – see Section 5.21. •step4_iso.py – Documented in Section 5.22, results shown in Section 4. Included log file: step4_iso.txt •parallel_finding_minimal_cs01mo_6.pdf – This pdf. •parallel_finding_minimal_cs01mo_6.tex – L A T EX source file to generate this pdf. This also uses the file step4_iso.txt, see Section 4, and the picture lemmling-cartoon-sheep.pdf. PARALLEL FINDING OF MINIMAL f∈cMaj{0,1} 6(PY) 39 References [A +20] I. Anaconda et al. Numba documentation, 2020. URL https://numba.readthedocs.io/en/stable/user/jitclass.html. [Ana18] Anaconda. Numba: A high performance python compiler, 2018. URL https://numba.pydata.org/. [Beh24] M. Behrisch. Finding minimal f∈cMaj{0,1} 5(py, c++), Nov. 2024. doi: 10.5281/zenodo.13862887. [BVW25] M. Behrisch, E. Vargas-Garc´ıa, and A. Wachtel. All minimal clones generated by {0,1}-valued majority operations on a five-element set. In 2025 IEEE 55th International Symposium on Multiple-Valued Logic—ISMVL 2025, Montreal, Quebec, Canada, 5–6 June 2025, pages 184–189, Los Alamitos, CA, June 2025. IEEE Computer Soc. doi: 10.1109/ISMVL64713.2025.00042. [BW25] M. Behrisch and A. Wachtel. Parallel finding of minimal f∈cMaj{0,1} 6(py), Nov. 2025. doi: 10.5281/zenodo.17460590. [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. [Mac24] H. Machida. Orderly majority functions with their relation to minimal clones. In 2024 IEEE 54th International Symposium on Multiple-Valued Logic (ISMVL), pages 1–6, 2024. doi: 10.1109/ISMVL60454.2024.00011. [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. 40 MIKE BEHRISCH AND ANDREAS WACHTEL Appendix A. A.1. Cyclic {0,1}-valued MO on {0,1,2,3}.The summary in this section was kindly provided in private communication by M. Behrisch. The following describes all minimal cyclic {0,1}-valued majority operations on {0,1,2,3}.The description is based on [Wal00, Theorem 1.1, p. 16], the table in [Wal00, p. 26] and the description of the conservative minimal majority operations in [Wal07a, Theorem 1.9, p. 12] (see also [Wal00, p. 18]). Let f∈cMaj{0,1} 4be minimal and set F:=hfi. Case 1. We first consider the case that the minimal clone contains a non-conservative majority generator function. By [Wal00, Theorem 1.1, p. 16] the clone contains one of three functions M1, M2, M3up to isomorphism. This means there is 1 ≤i≤3 and an isomorphic copy ˆ Miof Misuch that ˆ Mi∈F, hences hfi=F=ˆ Miby the minimality of F. Since f∈ˆ Mi(3) ∩cMaj{0,1} 4,we need to identify the cyclically symmetric at most two-valued majority functions in ˆ Mi(3) and consider all suitable conjugates that produce {0,1}- valued functions to obtain all possibilities for f. Although Waldhauser’s functions M1, M2, M3live on {1,2,3,4},we here already present them as a {0,1}-valued isomorphic copy on {0,1,2,3}. The function M1is as constant as a majority operation can be, that is, it is single valued and totally symmetric. Therefore, hM1i(3) ={e1, e2, e3, M1}and thus {M1}=F(3) \ J (3) A={f}. Since fis {0,1}-valued, we have f=M1for the following M1or fis its (01) -conjugate with the opposite value: M1 M1(01) x:0203|0313 y:1111|2222 z:2030|3031 -+----+---- :0000 0000 :1111 1111 Since the clone generated by M2contains no 2-valued majority operations, f6∈ ˆ M2,that is, the case i= 2 does not appear in our classification. The clone generated by M3contains only 2-valued majority operations, and two of these are cyclic, namely M3and ¯ M3.Each of these has 4 {0,1}-valued conjugates, giving altogether 8 possibilities for f: M3 M3(23) M3(01) M3(01)(23) ¯ M3 ¯ M3(23) ¯ M3(01) ¯ M3(01)(23) x:0203|0313 y:1111|2222 z:2030|3031 -+----+---- :1101 0111 :0111 1011 :0001 0010 :0100 0001 :1110 1011 :1011 0111 :0010 0001 :1000 0010 PARALLEL FINDING OF MINIMAL f∈cMaj{0,1} 6(PY) 41 Case 2. The second case is that every ternary generator function of the minimal clone Fis a conservative ( {0,1}-valued cyclically symmetric) majority function. Here, the restriction to each three-element subset Umust yield a minimal {0,1}-valued cyclic majority operation on the three-element subset U. Having a look at the table in [Wal00, p. 18], the restriction may be (up to isomorphism) m1, or m3or ¯m3by the cyclic symmetry of f. We show here suitable conjugates for U={0,1,2}: m1m3¯m3 012 : 0 0 1 210 : 0 1 0 [Wal07a, Theorem 1.9, p. 12] states that if m3appears as the restriction of one three-element subset and ¯m3appears as the restriction of another one, then the majority function cannot be minimal. Moreover, all the other combinations of restricted behaviour are indeed possible. Therefore, if one restriction is m3,all others are m1or m3; alternatively, if one restriction is ¯m3,then all others are m1or ¯m3.A conservative {0,1}-valued cyclic minimal majority function thus must have the form: x:0203|0313 y:1111|2222 z:2030|3031 -+----+---- f:abcd 0011 subject to the restrictions a, b, c, d ∈ {0,1}and a<b =⇒c≤d, a>b =⇒c≥d, c<d =⇒a≤b, c>d =⇒a≥b, cf. Lemma 14. Consequently, we obtain the following conservative minimal functions: f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 x:0203|0313 y:1111|2222 z:2030|3031 -+----+---- :0000 0011 :0001 0011 :0010 0011 :0011 0011 :1100 0011 :1101 0011 :1110 0011 :1111 0011 :0100 0011 :1000 0011 :0111 0011 :1011 0011 :0101 0011 :1010 0011 Altogether we have 2 + 2 ×4 + 14 = 24 minimal cyclic {0,1}-valued minimal majority operations on {0,1,2,3}.The 24 functions in this appendix coincide with those used computed by get all minimals A4 and shown in the log-files compute results Ak.txt for k∈ {5,6}. {