Finding minimal \(f\in \mathrm{cMaj}_5^{\{0,1\}}\) (py, c++)

Finding minimal f∈cMaj{0,1} 5(py, c++) Mike Behrisch∗† 30th September 2024 1 Overview This data set provides supplementary material supporting the computational search for all minimal clones generated by such cyclically symmetric majority operations on the set A = {0,1,2,3,4} that only have values in {0,1} on the triples of the form (a, b, c)with a=b=c=a. (Concrete) clones are sets F of operations of the form f:An→A on a set A , where n∈N = {0,1,2. . .} , that are closed under composition (substitution of functions into each other) and contain for all 0 ≤i < n ∈N any projection operation e(n) i:An→A mapping any tuple ( x0, . . . , xn−1 ) ∈An to e(n) i ( x0, . . . , xn−1 ) : = xi , see [ 6 , 5 , 1 ] for more information. For a fixed carrier set A all clones on A can be ordered by set inclusion, and this ordered set forms a complete algebraic lattice [ 6 , Satz 3.1.2, p. 77], which for finite A is atomic and dually atomic, see [ 6 , Hauptsatz 3.1.5, p. 80]. The atoms of this lattice are called minimal clones and they can be characterised by the fact that they are generated by each of its member operations not being a projection, cf. [ 6 , Section 4.4, p. 113]. A function f:An→A is a minimal operation if f generates a minimal clone Fand nis the minimum arity of possible generators of F. There is a well-known theorem by Rosenberg, which classifies minimal operations into four 1 categories [ 7 ]; one of these categories are majority operations f:A3→A . These are ternary functions on A satisfying the equations f ( x, x, y ) = f ( x, y, x ) = f ( y, x, x ) = x for every x, y ∈A . Clearly, a majority operation f is completely specified by giving the values f ( a, b, c )where a, b, c ∈A are pairwise distinct: a = b = c = a . If on those triples f only attains values in {0,1} ⊆ A , then we call f a {0,1} -valued majority operation; we collect all such functions in the set Maj{0,1} A . A function f:An→A is cyclically symmetric if a cyclic shift of its arguments does not change the function value, that is, if f ( x0, . . . , xn−1 ) = f ( x1, . . . , xn−1, x0 )holds for all x0, . . . , xn−1∈A . We denote the set of all cyclically symmetric {0,1} -valued majority operations on A by cMaj{0,1} A. Rosenberg’s classification theorem only provides necessary conditions for minimal functions and is not a characterisation. That is, for |A| ≥ 3many ∗Institute of Discrete Mathematics and Geometry, TU Wien, Wien, Austria †https://orcid.org/0000-0003-0050-8085 1 Traditionally, these are listed as five types but the binary idempotent type is just a special case of the semiprojection type. 1 majority operations fail to be minimal, and it is a difficult problem to isolate and describe those that are. This problem has been answered completely when |A| ≤ 4(for |A| ≤ 2it trivial as then there is a unique majority function and this one indeed generates a minimal clone for A = {0,1} , and is a projection for |A| ≤ 1; for |A|= 3 the description can be found in [2]; for |A|= 4 in [9]). For A = {0,...,4} no complete characterisation is currently known. Since for A with five elements the search space of all possible majority operations is huge, we restrict the question of determining minimality to the set of all cyclically symmetric {0,1} -valued majority operations, which turns out to be much more feasible. This data set contains software to determine all minimal {0,1} -valued cyclically symmetric majority operations on 2A = {0,1,2,3,4} = 5—that is, the minimal f∈cMaj{0,1} 5 ; moreover, the data set includes the computed output. There is a second such data set [ 8 ] solving the same problem but deliberately developed independently of the code presented here. Our algorithm is in essence a brute force search through all potential candidate functions, sorting those out that are definitely not minimal and then testing the remaining ones for minimality. We provide here two separate implementations, one in python 3 (see Section 6) and one in c++11 (see Section 5). 2 List of files Here we give a brief overview of the files in the data set, before focusing on more background theory, encoding choices and the implementations in minimal01MajOn5.cpp and 01_valued_majorityfuncs.py in a little more detail. minimal01MajOn5.cpp c++11 code filtering out all non-minimal functions f∈cMaj{0,1} 5 and testing the remaining ones for minimality; produces the output all_minimals_cpp.txt all_minimals_cpp.txt the output of minimal01MajOn5.cpp (specifically of the routine compute_minimals discussed in Subsection 5.4.36) produced by redirecting stdout to a file 01_valued_majorityfuncs.py python 3 script filtering out all non-minimal functions f∈cMaj{0,1} 5 and testing the remaining ones for minimality; produces the output py-result_ filtering2to20_to_656quasiminimals_ reduced_to_78_conjugacy_ representatives_to_44minimals_to_26_ eqv_representatives.txt py-result_filtering2to20_to_ 656quasiminimals_reduced_to_ 78_conjugacy_representatives_ to_44minimals_to_26_eqv_ representatives.txt the output of running python3 01_valued_ majorityfuncs.py and redirecting stdout to a file 2 We here use the set theoretic convention that every n∈N as a set equals its set of predecessors n={0,...,n−1}, i.e., the von Neumann model of (finite) ordinals. 2 44_minimal_clones.txt the output of calling print_out_gen_clones(minimal44) in main() of 01_valued_majorityfuncs.py with some manual rearrangement 26_minimal_equivalence_ representatives.txt the 26 minimal functions up to equivalence ≡ , extracted from py-result_filtering2to20_ to_656quasiminimals_reduced_to_ 78_conjugacy_representatives_to_ 44minimals_to_26_eqv_representatives. txt 296_minimals_non_conjugacy_ reduced.txt the complete list of 296 minimal functions among cMaj{0,1} 5 , extracted from all_minimals_cpp. txt f*.alg input files for the universal algebra calculator UACalc [ 4 ], describing minimal {0,1} -valued majority operations on {0,...,4} ; these can be produced by calling write_uacalc_files(minimal44) and the functions understand_clone_5202xy() where xy ∈ {03,05,66} in main() of 01_valued_majorityfuncs.py , or by running the separate script write_uacalcfiles.py that contains only a small portion of the code in 01_valued_majorityfuncs.py write_uacalcfiles.py a separate python script that just contains the routines to output the f*.alg -files for UACalc [ 4 ]; running it should produce all files of the form f*.alg in the data set. minimal_clones_with_cyclic_01_ majority_witnesses.pdf this documentation minimal_clones_with_cyclic_01_ majority_witnesses.tex L A T E X source file to produce this documentation 3 More theoretical background Let us write OA: = {f:An→A|n∈N} for the set of all finitary operations on A and JA = ne(n) i  0≤i<n∈No for the set of all projection operations, also called trivial operations. The smallest clone under inclusion containing some set F⊆ OA will be denoted by ⟨F⟩OA . The set of ternary functions generated from F in this clone is symbolised by ⟨F⟩(3) OA . When F = {f} , we simply write ⟨f⟩OAand ⟨f⟩(3) OAfor brevity. The definition of minimality of a clone JA⊊F⊆ OA immediately translates into the condition that F = ⟨f⟩OA must hold for each non-trivial f∈F . Supposing that F = ⟨f⟩OA with some f∈ OA\ JA , we have that F is minimal if and only if f∈ ⟨h⟩OA for all h∈F\ JA = ⟨f⟩OA\ JA , see, e.g., [ 9 , p. 16]. The check of this condition involves infinitely many functions h to be tested 3 since the number of arguments of h∈F\ JA may be arbitrarily large. However, if fis a majority operation on A⊇ {0,1}, then this check may be simplified: Lemma 1 (cf. [ 11 , Theorem 2.1, p. 3]).For a majority operation f:A3→A on a set A of size at least two, we have that ⟨f⟩OA is minimal if and only if f∈ ⟨h⟩(3) OAholds for each h∈ ⟨f⟩(3) OA\ JA=⟨f⟩(3) OA\ne(3) 0, e(3) 1, e(3) 2o. Since for a finite set A the set of ternary operations AA3 is again finite, it is a finite task to test the validity of the characterisation of minimality of a majority function f given in the previous lemma. It is our goal to check this condition for every cyclically symmetric majority operation f∈cMaj{0,1} 5. When |A| = K , then the number of triples from A3 with pairwise distinct entries, the values of which determine any majority function f:A3→A , is K ( K− 1)( K− 2). A {0,1} -valued majority function may take values in {0,1} on each of these arguments independently, whence there are 2 K(K−1)(K−2) {0,1} - valued majority functions on A ; for |A| = K = 5, this number amounts to 2 60 . If we additionally assume that the majority function be cyclically symmetric, then the elements of each of the K 3 = K ( K− 1)( K− 2) / 6three-element subsets of A can be put in forward or backward order, which then may each take values in {0,1} independently. This means there are 2 K(K−1)(K−2)/3{0,1} -valued cyclically symmetric majority operations on A of size |A| = K ; for K = 5 this yields 2 20 functions. As a consequence of this discussion, we can represent each {0,1} -valued majority function f on A = 5 = {0,...,4} by the bits of an integer 0 ≤ˆ Nf< 2 60 , and if f is cyclically symmetric, we can represent its values on the 20 relevant triples as bits of an integer 0 ≤Nf< 2 20 , see the discussion under encoding below. Moreover, besides the three projections, {0,1} -valued majority functions are the only ones that appear in the computation of ⟨f⟩(3) OA (and thus of ⟨h⟩(3) OA ) in the minimality test described in Lemma 1. This is due to the following fact, which follows from the proof of Theorem 2.1 in [11, p. 3], see also [9, p. 17]. Lemma 2 ([ 3 , 9 , 11 ]).If f:A3→A is a majority operation, then every nontrivial h∈ ⟨f⟩(3) OA\ JA is a majority operation, as well; if f is {0,1} -valued, then so is h. This means, computation of the non-trivial ternary functions in a clone generated by a single majority function f preserves the majority property and {0,1} -valuedness. It does, however, in general not preserve the cyclic symmetry of f . That is, even if f∈cMaj{0,1} A , then h∈ ⟨f⟩(3) OA may have lost its cyclic symmetry (and therefore need more than 20 bits for its representation). While Lemma 1 makes testing of majority functions on finite sets for minimality possible, it is still an expensive test with respect to runtime. In view of the many potential candidate functions (even in the set cMaj{0,1} A ), it is necessary to use simpler necessary conditions that are implied by minimality and can be used to discard many functions more quickly. A basic necessary condition is based on preservation of relations, see, e.g., [ 6 , Chapter 1] or [ 1 , Definition 2.3, p. 10]. We say that a function f:An→A preserves a relation ρ⊆Am , m, n ∈N , if for every tuple r = ( r0, . . . , rn−1 ) ∈ρn of columns from ρthe column m-tuple s:=f◦(r0, . . . , rn−1)∈Am 4 given by s(i):=f(rj(i))0≤j<n=f(r0(i), . . . , rn−1(i)) for each 0≤i<m necessarily belongs to ρ . In such a case we shall also call the relation ρ invariant under f . The case m = 1 is particularly easy to understand. A relation ρ⊆A1 is simply a subset, and it is invariant under f , if f ( x0, . . . , xn−1 ) ∈ρ holds for every choice of x0, . . . , xn−1∈ρ . In our context, n = 3 and f:A3→A being a majority operation will be particularly important; in such a case f preserves ρ if and only if f◦ ( r0, r1, r2 ) ∈ρ holds for all choices of tuples r0, r1, r2∈ρ such that |{r0, r1, r2}| = 3 since in the case that two of the argument tuples coincide the preservation condition is trivially fulfilled by the majority property of f . Since the case m = 2 will also appear, we formulate the preservation condition for ρ⊆A2 and a majority operation f:A3→A again more explicitly: f preserves ρ⊆A2 if and only if for every x, y, z, u, v, w ∈A the following implication holds (x u),(y v),(z w)∈ρ∧ |{(x u),(y v),(z w)}| = 3 =⇒f(x,y,z) f(u,v,w)∈ρ. The following lemma gives a necessary condition for minimality of a function f∈ OA\ JA. Lemma 3. If f∈ OA\ JA generates a minimal clone and h∈ ⟨f⟩OA\ JA , then fand hmust have the same3set of invariant relations. Formulated differently, if f∈Maj{0,1} A and h∈ ⟨f⟩OA (or in ⟨f⟩(3) OA ) is a non-projection and h preserves some relation, e.g., some subset U⊆A or binary relation ρ⊆A2 , that is not preserved by f , then f fails to be minimal and thus can be discarded from the search. We remark that, as a consequence of the Baker-Pixley-Theorem, for majority operations, it is sufficient to consider at most binary relations for such a test. Concentrating on f∈Maj{0,1} A and preservation of subsets U⊆A⊇ {0,1} , one can observe that every subset of size at most two and the full set will always be preserved (by f and any h∈ ⟨f⟩(3) OA\JA ). Likewise any subset U⊋{0,1} will always be preserved since f and h are both {0,1} -valued majority operations; moreover, at least three-element subsets U⊆A\ {0,1} will not be preserved by either of the two functions as f ( u, v, w ) ∈ {0,1} for three distinct u, v, w ∈U and {0,1} ∩ U = ∅ . Therefore, the interesting subsets U⊊A to be tested with respect to the condition from Lemma 3 are those of size at least three that contain exactly one of 0or 1. For A = {0,...,4} these are of the form U = {x, a, b} with x∈ {0,1} and distinct a, b ∈ {2,3,4} or U = {x, 2,3,4} with x∈ {0,1} . A majority function f∈Maj{0,1} A preserves a set of the form U = {x, a, b} with x∈ {0,1} and a = b∈ {2,3,4} if and only if for each triple x formed as one of the six permutations of x, a, b , we have f ( x ) = x . Likewise, f preserves U = {x, 2,3,4} with x∈ {0,1} if for all 24 triples x = ( u, v, w ) ∈U3 with |{u, v, w}| = 3, we have f ( x ) = x . Under the additional assumption of cyclic symmetric, i.e., for 3 Under the stated assumptions it follows automatically from the background theory, cf. [ 6 , Satz 1.1.15, p. 48] or [ 1 , Lemma 2.6, p. 11], that every invariant relation of f also remains invariant for h. If fgenerates a minimal clone, however, the considered function hcan never have more invariants than the original f. 5 f∈cMaj{0,1} 5 , only 2 out of 6 triples for U = {x, a, b} and 8 out of 24 triples for U={x, 2,3,4}need to be considered in a test for preservation. Two further necessary conditions that follow from minimality are explained in Subsections 5.4.9 and 5.4.10. 4 Encoding of {0,1} -valued majority functions on A={0,...,4} Every {0,1} -valued majority function f∈Maj{0,1} A is uniquely specified by its values in {0,1} on the 60 triples in A3 with three distinct entries, that is by the bits of a non-negative integer ˆ Nf< 2 60 . For the implementations contained in this data set, the bijection between function arguments and bit indices has been chosen based on the lexicographic order of the triples. That is, every { 0 , 1 } -valued majority operation f:A3→A is internally represented by the (unsigned) integer ˆ Nfgiven 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,0,2)212 +f(1,0,3)213 +f(1,0,4)214 +f(1,2,0)215 +f(1,2,3)216 +f(1,2,4)217 +f(1,3,0)218 +f(1,3,2)219 +f(1,3,4)220 +f(1,4,0)221 +f(1,4,2)222 +f(1,4,3)223 +f(2,0,1)224 +f(2,0,3)225 +f(2,0,4)226 +f(2,1,0)227 +f(2,1,3)228 +f(2,1,4)229 +f(2,3,0)230 +f(2,3,1)231 +f(2,3,4)232 +f(2,4,0)233 +f(2,4,1)234 +f(2,4,3)235 +f(3,0,1)236 +f(3,0,2)237 +f(3,0,4)238 +f(3,1,0)239 +f(3,1,2)240 +f(3,1,4)241 +f(3,2,0)242 +f(3,2,1)243 +f(3,2,4)244 +f(3,4,0)245 +f(3,4,1)246 +f(3,4,2)247 +f(4,0,1)248 +f(4,0,2)249 +f(4,0,3)250 +f(4,1,0)251 +f(4,1,2)252 +f(4,1,3)253 +f(4,2,0)254 +f(4,2,1)255 +f(4,2,3)256 +f(4,3,0)257 +f(4,3,1)258 +f(4,3,2)259 For a cyclically symmetric majority function f∈cMaj{0,1} A only 20 values in {0,1} need to be stored, leading to a representation by the following nonnegative integer Nf<220: 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 In [ 8 ] different design choices have been made with respect to the bijection between the argument triples and the bit positions in the encoding integers; this has led to some code simplifications and notably shorter runtimes. According to Lemma 2, besides {0,1} -valued majority operations, which can be encoded as integers ˆ Nf< 2 60 or Nf< 2 20 , respectively, we only need the three projections e(3) 0, e(3) 1, e(3) 2 in the minimality test described in Lemma 1. 6 These have been encoded in the c++ implementation (see Section 5) by hardcoded integer constants ( j + 1) · 2 60 ≥ 2 60 for e(3) j and 0 ≤j < 3, while in the python implementation (see Section 6) we just represented e(3) 0, e(3) 1, e(3) 2 by the characters X , Y , Z , respectively. This may have been a sub-optimal choice with regard to execution speed, but the python implementation was never intended to be optimised for runtime. 5 Details on the implementation of the search in minimal01MajOn5.cpp 5.1 C++ dialect and used libraries The code is written in c++11 and should therefore be compiled with a suitable language flag, for example, for the gnu compiler 4 one would use the options g++ -std=c++11 -Wall -O3 -ofindminimals minimal01MajOn5.cpp. The following libraries are used: ctime , cstdio , iostream , set , and vector . 5.2 Types Two type aliases are declared, namely majtype for unsigned long , and cyclicmaj for unsigned int. 5.3 Global constants The following global constants are defined: K=5 , the size of the base set A , npos = K*(K-1)*(K-2)/3 , the number of relevant triples for a cyclically symmetric {0,1} -valued majority operation, and numb_subsets = 21 , the number of all at least two-element subsets U⊊{0,...,4} that contain 0,1or both; moreover, p1 = 1UL<<60 , p2 = 2UL<<60 and p3 = 3UL<<60 to represent the projections e(3) 0,e(3) 1and e(3) 2. The code also defines and initialises four global arrays of non-modifiable values const int evaldic60[K*K*K] , const int evaldic20[K*K*K] , as well as const unsigned hashtrpl[npos] , const unsigned subsets01[numb_subsets] . For a triple 0 ≤x,y,z<K with three distinct values, we may compute its hash value as h = xK2 + yK + z , and evaldic60[h] stores the unique index 0 ≤i < 60 such that for any {0,1} -valued majority function f the bit i of ˆ Nf represents f(x,y,z). In other words, one may compute ˆ Nfas ˆ Nf=X (x,y,z)∈{0,...,4}3 x=y=z=x f(x, y, z)2evaldic60[25x+5y+z]. Likewise, i = evaldic20[h] is the index 0 ≤i < 20 such that the bit i of Nf of a function f∈cMaj{0,1} 5 represents f ( x,y,z ). The hash value h of that triple ( x,y,z ) ∈A3 with three distinct entries for which f ( x,y,z )appears as coefficient in front of 2 i in the definition of Nf (as the i -th bit of Nf ) for f∈cMaj{0,1} 5 4 The code in minimal01MajOn5.cpp has been compiled with g++(Debian10.2.1-6)20210110 but we do not presume that the precise compiler version is a restriction. We expect more recent versions of the compiler to work, too, but we have not tested compilation or performance with other compilers. 7 is stored as hashtrpl[ 19 −i] . For example, the triple (2 , 4 , 3), whose function value is stored in the 19-th bit of Nf , is hashed to 2 · 25 + 4 · 5 + 3 = 73, and therefore hashtrpl[0]is initialised to the value 73. The array subsets01[numb_subsets] contains the hash values of all at least two-element subsets U⊊{0,...,4} that contain 0,1or both, where the hash value is computed as hU = P j∈U 2 j< 2 5 = 32. Conversely, for each 0 ≤j < 5we have j∈Uif and only if (hU>>j)&1U == 1U holds for its hash value hU. 5.4 Functions 5.4.1 hasht Computes 25x+ 5y+zfor three unsigned integer arguments x, y, z. 5.4.2 ppprint Prints the values of a function f∈cMaj{0,1} 5 (given by its Nf< 2 20 ) on the 20 relevant triples with three distinct entries to the screen (both the arguments and the values are printed in 20 lines); uses eval20, see 5.4.4 below. The order of the arguments for the printed function values of f is (the left to right reading order corresponds to the 20 printed lines from top to bottom): (0,1,2), (2,1,0), (0,1,3), (3,1,0), (0,1,4), (4,1,0), (0,2,3), (3,2,0), (0,2,4), (4,2,0), (0,3,4), (4,3,0), (1,2,3), (3,2,1), (1,2,4), (4,2,1), (1,3,4), (4,3,1), (2,3,4), (4,3,2) 5.4.3 pprint Prints the values of a function f∈cMaj{0,1} 5 (given by its Nf< 2 20 ) on the 20 relevant triples with three distinct entries to the screen (only the bit values are printed in one line; the order of the arguments from left to right is the same as the one for ppprint from top to bottom); uses eval20, see 5.4.4 below. 5.4.4 eval20 Evaluates a function f∈cMaj{0,1} 5 given through its Nf< 2 20 at any triple ( x, y, z ) ∈ {0,...,4}3 by using the majority law or by extracting the i -th bit of Nfwhere i=evaldic20[hasht(x,y,z)] if x=y=z=x. 5.4.5 eval60 Evaluates some function f∈Maj{0,1} 5∪ne(3) 0, e(3) 1, e(3) 2o at an arbitrary triple (x, y, z)∈ {0,...,4}3 . If f∈Maj{0,1} 5 , then it is assumed to be given through its ˆ Nf< 2 60 and will be evaluated by using the majority law or by extracting the i-th bit of ˆ Nfwhere i=evaldic60[hasht(x,y,z)] if x=y=z=x. If fis a projection e(3) j−1 with 1 ≤j≤ 3, given through the global constant pj≥ 2 60 , the correct entry x,yor zwill be returned. 8 5.4.6 compose20 This function takes four arguments interpreted as functions f∈cMaj{0,1} 5 and g1, g2, g3∈Maj{0,1} 5∪ne(3) 0, e(3) 1, e(3) 2o , where f is given by its Nf< 2 20 and gj by their ˆ Ngj< 2 60 if they are majority functions, or, if they are projections, by the fixed constants p1,p2,p3 ≥ 2 60 for 1 ≤j≤ 3. The function computes h: = f◦ ( g1, g2, g3 )and returns ˆ Nh . It is assumed (and needs to be ensured by the caller of the function, i.e., this assumption is not tested by compose20 to optimise for speed) that |{g1, g2, g3}| = 3, as otherwise the resulting composite h would be one of g1, g2, g3 and would not have to be computed. In accordance with Lemma 2, the composite function h belongs to Maj{0,1} 5 , wherefore, it can be represented by an integer ˆ Nh< 2 60 that will be computed and returned by compose20. The function iterates over all 60 triples ( x, y, z ) ∈ {0,...,4}3 with three distinct entries, uses eval60 to compute tj = gj ( x, y, z )for 1 ≤j≤ 3, then uses eval20 to compute v = f ( t1, t2, t3 ), and finally sets the correct bit of ˆ Nh to v (by summing up v times a power of 2corresponding to the correct bit position). 5.4.7 not_faster_compose20 A variant implementation of compose20 , which empirically seems to be running slower. It is therefore not used. 5.4.8 compose60 This function takes four arguments interpreted as functions f∈Maj{0,1} 5 (not a projection) and g1, g2, g3∈Maj{0,1} 5∪ne(3) 0, e(3) 1, e(3) 2o , where f is given by its ˆ Nf< 2 60 and gj by their ˆ Ngj< 2 60 if they are majority functions, or, if they are projections, by the fixed constants p1,p2,p3 ≥ 2 60 for 1 ≤j≤ 3. The function computes h: = f◦ ( g1, g2, g3 )and returns ˆ Nh . It is assumed (and needs to be ensured by the caller of the function, i.e., this assumption is not tested by compose60 to optimise for speed) that |{g1, g2, g3}| = 3, as otherwise the resulting composite h would be one of g1, g2, g3 and would not have to be computed. In accordance with Lemma 2, the composite function h belongs to Maj{0,1} 5 , wherefore, it can be represented by an integer ˆ Nh< 2 60 that will be computed and returned by compose60 . The function compose60 performs the same task as compose20 with the only difference that the first argument is not assumed to be a cyclically symmetric {0,1} -valued majority function, wherefore the internal representation of the first argument is different and the implementation slightly changes (namely, by using eval60 instead of eval20 when computing v=f(t1, t2, t3)). 5.4.9 composite_of_nonconstant_is_constant Takes two arguments f∈cMaj{0,1} 5 and h∈Maj{0,1} 5 , represented by Nf< 2 20 and ˆ Nh< 2 60 , and tests whether h is a majority function that is constant (either zero or one) on all 60 relevant triples, that is, ˆ Nh∈0,260 −1 , and at the same time f is non-constant on its 20 relevant triples, that is, Nf/∈0,220 −1 . 9 to compose60 . If f∈Fn is detected for some n∈N , then false is returned immediately. If ⟨h⟩(3) OA has been computed completely and f∈ ⟨h⟩(3) OA has not been found in it (in none of the steps leading to the completion of ⟨h⟩(3) OA ), then true is returned. In the same way as compute_ternary_part_of_gen_clone , this function is computationally expensive and has to be used with care. 5.4.27 is_minimal This function takes as input a function f∈cMaj{0,1} 5 , represented by its integer Nf< 2 20 , and it tests via the condition presented in Lemma 1 whether ⟨f⟩OA is minimal. First, we compute ⟨f⟩(3) OA via compute_ternary_part_of_gen_clone . Second, we iterate over each h∈ ⟨f⟩(3) OA\ne(3) 0, e(3) 1, e(3) 2o and test with the help of original_f_not_generated_back_by_h if f /∈ ⟨h⟩(3) OA . If so, we can immediately return false as the condition from Lemma 1 is violated for this h . If, after this iteration over ⟨f⟩(3) OA , we have never returned false , the characterising condition from Lemma 1 is satisfied, and we consequently return true. This function calls two computationally expensive functions (potentially in a medium sized loop) and therefore should be used sparingly (e.g., not in the loop in filter_out_nonminimals). 5.4.28 compute_ternary_part_of_gen_clone_trying_to_refute_f This is an auxiliary analysis function taking as arguments some f∈cMaj{0,1} 5 , given by its Nf< 2 20 , and a reference to a set compositions to store a subset of ⟨f⟩(3) OA in it. The function returns an int status flag α∈ {0,1,2,3,4} and is not needed to find all the minimal clones generated by functions f∈cMaj{0,1} 5 . First compositions is emptied. Then, in an iterative process as in the function compute_ternary_part_of_gen_clone , for n∈N increasing approximations Fn⊆ ⟨f⟩(3) OA are stored in compositions . If during that process a reason for non-minimality of f is encountered, the process is aborted and an explanatory flag 1 , 2 or 3 is returned (in this case compositions contains a subset of ⟨f⟩(3) OA that may be proper). The meaning of the flag α is that there is some h∈ ⟨f⟩(3) OA\ne(3) 0, e(3) 1, e(3) 2osuch that 1:hpreserves more subsets than f; 2:hpreserves more equivalence relations that f; 3:h has constant value 0(or 1) on all 60 triples with distinct entries, but f does not have this property. If no reason for non-minimality of f is found, the return flag α is 0 or 4 . The meaning of the flag is 0: the computation of ⟨f⟩(3) OA finished and all the computed composite functions are represented as majtype integers in compositions. 16 4: the computation of ⟨f⟩(3) OA was aborted before the closing finished because   ⟨f⟩(3) OA  ≥enormous with the heuristic constant enormous = 1253 . In this case compositions will usually represent a proper subset of ⟨f⟩(3) OA. 5.4.29 compute_clone_sizes This is an auxiliary analysis function that is not needed to find all minimal functions f∈cMaj{0,1} 5 . It takes as its single argument a reference to a set of unsigned integers Nf representing cyclically symmetric functions in cMaj{0,1} 5 , such as, for example, the set of quasiminimal functions resulting from a call to filter_out_nonminimals, or some subset thereof. The function iterates over each f from the set and attempts to compute ⟨f⟩(3) OA by calling compute_ternary_part_of_gen_clone_trying_to_refute_f , which produces some subset F⊆ ⟨f⟩(3) OA and a return flag α∈ {0,1,2,3,4} . Then Nf , |F| − 3and a single character interpretation of α is printed to the screen. For α = 0 (interpretation c losed), the integer |F| − 3 =   ⟨f⟩(3) OA\ne(3) 0, e(3) 1, e(3) 2o   is the number of majority operations in the clone generated by f , and it is meaningless in the other cases. For the cases α∈ {1,2,3} (interpretations S ubsets, con G ruences, C onstants), |F| − 3is uninteresting, as ⟨f⟩OA is not a minimal clone. For the case α = 4 (interpretation u nknown), the minimality status of ⟨f⟩OAand the full size of ⟨f⟩(3) OAare both unknown. 5.4.30 reverse20 This function takes as input Nf< 2 20 of some f∈cMaj{0,1} 5 and computes and returns N¯ f< 2 20 where ¯ f∈cMaj{0,1} 5 is given by ¯ f ( x, y, z ) : = f ( z, y, x )for x, y, z ∈ {0,...,4} . In the computation the global array hashtrpl (to recover the argument triple from the bit index in the representation N¯ f of ¯ f ) and the function eval20 (to evaluate f at the reversed argument triple recovered from the bit index) is used. 5.4.31 conjugate It takes as arguments an f∈cMaj{0,1} 5 , represented by its Nf< 2 20 , and an unsigned array pi[K] containing 5values [ π (0) , π (1) , . . . , π (4)] of a permutation π∈Sym (5) with {π(0), π(1)} = {0,1} and it computes the conjugate (cyclically symmetric) majority function fπ: = π−1◦f◦ ( π×π×π ), which is again {0,1} - valued since π preserves the set {0,1} . As π↾{0,1} is an involution and the range of f is a subset of {0,1} , we may express fπ = π◦f◦ ( π×π×π ), which simplifies the computation. The return value of conjugate is then Nfπ. In the computation the global array hashtrpl (to recover the argument triple from the bit index in the representation Nfπ of fπ ) and the function eval20 (to evaluate π◦f at the π -translated argument triple recovered from the bit index) is used. 17 5.4.32 reduce_up_to_conjugacy This function takes as its argument a reference to a set repr of unsigned integers Nf representing cyclically symmetric majority operations f∈cMaj{0,1} 5 , such as, for example, the set of quasiminimal functions resulting from a call to filter_out_nonminimals . The purpose of the function is to compute a conjugacy transversal of the set, that is, to keep of each conjugacy equivalence class of members of repr only a single representative in the set. This is done by modifying the contents of the input set repr accordingly. The function iterates over every Nf from repr , then over all 11 non-identical permutations π∈Sym (5) that preserve {0,1} to compute fπ and to erase Nfπ from repr if fπ = f . The latter condition ensures that one representative from each conjugacy class is actually kept in the set. The computation of Nfπ is achieved by calling conjugate. 5.4.33 reduce_up_to_equivalence This function takes as its argument a reference to a set repr of unsigned integers Nf representing cyclically symmetric majority operations f∈cMaj{0,1} 5 , such as, for example, the set of quasiminimal functions resulting from a call to filter_out_nonminimals . We say for functions f, g ∈cMaj{0,1} 5 that f≡g holds if g is a conjugate of f or of ¯ f with ¯ f ( x, y, z ) : = f ( z, y, x )for all values x, y, z ∈ {0,...,4} . The purpose of the function is to compute a ≡ -transversal of the set repr , that is, to keep of each equivalence class of members of repr only a single representative in the set. The implementation is analogous to reduce_up_to_conjugacy with the only modification that for each Nf from repr the integer N¯ f is computed using reverse20 , and then, for each of the permutations π∈Sym (5) preserving {0,1} , conjugates of f and of ¯ f that are distinct from fare erased from the set repr. 5.4.34 test_single_function This is an auxiliary analysis function that is not needed to find all minimal functions from cMaj{0,1} 5 . The function takes as its single argument the integer Nf< 2 20 of some f∈cMaj{0,1} 5 and tries to refute the minimality of f by applying compute_ternary_part_of_gen_clone_trying_to_refute_f to it. The result of this attempted refutation (and possibly the number of majority operations generated by f) is printed to stdout. 5.4.35 test_80_remaining_funcs This is an auxiliary analysis function that is not needed to find all minimal functions from cMaj{0,1} 5 . The function has no arguments and investigates a hard coded set of cyclicmaj integers Nf< 2 20 representing 80 quasiminimal functions f∈cMaj{0,1} 5 that were previously computed by the python 3 implementation (cf. Section 6). First, the functions that fail the homogeneity test implemented in is_not_prec_succ_hom_f20 are removed from the set, and it is reported to stdout how many and which functions pass the test and which ones fail. For the ones that pass the test, they are printed to stdout including their value table, and it is attempted to mark more of them as non-minimal functions via 18 the routine compute_clone_sizes. 5.4.36 compute_minimals This is the central routine to compute all cyclically symmetric {0,1} -valued majority functions f∈cMaj{0,1} 5 that generate a minimal clone. It has no arguments nor return values. It starts by filtering out all non-minimal functions f∈cMaj{0,1} 5 by iterating over all 0 ≤Nf< 2 20 with the help of filter_out_nonminimals . A set of (416) quasiminimal (potentially minimal functions) remains, which is reported to stdout by the filtering routine. Since conjugate functions generate conjugate (concretely isomorphic) clones, for each conjugacy class either all the clones generated by any of the functions in the class are minimal or none of them is. In the second step we therefore compute a set of conjugacy representatives of the quasiminimal functions by a call to reduce_up_to_conjugacy . The representatives and their number (55) are reported to stdout. The third step consists in calling is_minimal for each conjugacy representative, in collecting the minimal functions in a set and in computing the number of majority operations generated by them with the help of the function compute_ternary_part_of_gen_clone . The Nf for minimal representative f∈cMaj{0,1} 5 , their total number (44), and the number of generated majority operations for each one is printed to stdout . After that the minimal representatives are further reduced up to the equivalence ≡ defined in Subsection 5.4.33 by calling reduce_up_to_equivalence on the set of minimal conjugacy representatives. A set of 26 minimal equivalence representatives remains, the size and the members of which are reported to stdout. Finally, as a bonus all minimal functions out of the set of 416 quasiminimal functions from the first step are determined by calling is_minimal for each quasiminimal one. Among the 416 functions 296 are reported as being minimal, and for each of these the corresponding Nf and the number of majority operations generated by fis printed to stdout. The resulting data from running this routine, which answers the problem this data set is concerned with, can be found in the file all_minimals_cpp.txt . 5.4.37 reduce_and_check_416_quasiminimal_funcs This is an auxiliary analysis function that is not needed to find all minimal functions from cMaj{0,1} 5 . The function takes no arguments and investigates a hard coded set of 416 pre-computed quasiminimal functions (those Nf that result from calling the time-consuming function filter_out_nonminimals(20U,...) in the first step of compute_minimals ). A set of conjugacy representatives is computed from the 416 functions using reduce_up_to_conjugacy and the representatives are printed to stdout . After that all the 416 functions are tested for minimality using is_minimal and the minimal ones are printed to stdout. 5.4.38 test_not_faster_compose_compose This is an auxiliary function testing the runtime performance of different implementations of function composition ( compose20 vs. not_faster_compose20 ) 19 and of the way how the ternary part of the clone of some f∈cMaj{0,1} 5 is computed ( compute_ternary_part_of_gen_clone vs. some variant of it). This part of the code is never used. 5.4.39 main The function main currently does nothing besides calling compute_minimals and then returning 0 . It contains some code lines that were commented out and investigate special topics like •performance testing test_not_faster_compose_compose; •testing specific functions using test_single_function; •test_80_remaining_funcs; •reduce_and_check_416_quasiminimal_funcs. 6 Details on the implementation of the search in 01_valued_majorityfuncs.py 6.1 Python version and used libraries The script is written in python3 and can be invoked with the command line call python3 01_valued_majorityfuncs.py . We ran this script under Python 3.9.2 with the option -u for unbuffered output and a redirection of the output to a file: python3 -u 01_valued_majorityfuncs.py > out.txt. The following libraries are used: timeit and sys. 6.2 Global variables The following global variables are defined: •evaldic60 : a dictionary that for each of the 60 triples ( a, b, c ) ∈ {0,...,4}3 with |{a, b, c}| = 3 maps the hash value 25 a + 5 b + c to the bit index j∈ {0,...,59} where the corresponding function value h ( a, b, c )of a {0,1} - valued majority operation h∈Maj{0,1} 5 is stored in its integer representation. That is, we have ˆ Nh=P(a,b,c)∈{0,...,4}3 a=b=c=a h(a, b, c)2evaldic60[25a+5b+c]. •evaldic20 : a dictionary that for each of the 60 triples ( a, b, c ) ∈ {0,...,4}3 with |{a, b, c}| = 3 maps the hash value 25 a + 5 b + c to the bit index j∈ {0,...,19} where the corresponding function value f ( a, b, c )of a {0,1} -valued majority operation f∈Maj{0,1} 5 is stored in its integer representation Nf. •subs012 : a list with 6 entries corresponding to the 6 permutations of (0 , 1 , 2), i.e., (0 , 1 , 2) , (0 , 2 , 1) , (1 , 0 , 2) , (1 , 2 , 0) , (2 , 0 , 1) , (2 , 1 , 0). For each ( a, b, c )in this list, subs012 contains the value evaldic60 [25 a + 5 b + c ] (in the order of the triples given here). The indices in subs012 are the positions of the function values coded in ˆ Nh that have to be checked to 20 see whether a function h∈Maj{0,1} 5 preserves {0,1,2} . Note that in the case of the subset {0,1,2} no check has to be applied since h will always return a value in {0,1}⊆{0,1,2}for the six relevant triples. •subs013 : the analogous description as for subs012 but for the set {0,1,3} . •subs014 : the analogous description as for subs012 but for the set {0,1,4} . •subs023 : the analogous description as for subs012 but for the set {0,2,3} ; here h∈Maj{0,1} 5 preserves {0,2,3} if its values at all the bit positions specified in subs023 are all equal to 0. •subs024 : the analogous description as for subs012 but for the set {0,2,4} ; here h∈Maj{0,1} 5 preserves {0,2,4} if its values at all the bit positions specified in subs024 are all equal to 0. •subs034 : the analogous description as for subs012 but for the set {0,3,4} ; here h∈Maj{0,1} 5 preserves {0,3,4} if its values at all the bit positions specified in subs034 are all equal to 0. •subs123 : the analogous description as for subs012 but for the set {1,2,3} ; here h∈Maj{0,1} 5 preserves {1,2,3} if its values at all the bit positions specified in subs123 are all equal to 1. •subs124 : the analogous description as for subs012 but for the set {1,2,4} ; here h∈Maj{0,1} 5 preserves {1,2,4} if its values at all the bit positions specified in subs124 are all equal to 1. •subs134 : the analogous description as for subs012 but for the set {1,3,4} ; here h∈Maj{0,1} 5 preserves {1,3,4} if its values at all the bit positions specified in subs134 are all equal to 1. •subs234 : the analogous description as for subs012 but for the set {2,3,4} ; here h∈Maj{0,1} 5never preserves {2,3,4}. •subs02320 : a list containing the 2indices evaldic20 [25 a + 5 b + c ]for ( a, b, c ) = (0 , 2 , 3) and ( a, b, c ) = (3 , 2 , 0), that is, those bit positions where the values f (0 , 2 , 3) and f (3 , 2 , 0) of a function f∈cMaj{0,1} 5 are stored in Nf . Such a function preserves {0,2,3} if it is constant with value 0in these two positions. •subs02420 : the analogous description as for subs02320 but for the set {0,2,4}. •subs03420 : the analogous description as for subs02320 but for the set {0,3,4}. •subs12320 : the analogous description as for subs02320 but for the set {1,2,3} ; on the positions in the list a function f∈cMaj{0,1} 5 needs to have value 1to preserve {1,2,3}. •subs12420 : the analogous description as for subs12320 but for the set {1,2,4}. 21 •subs13420 : the analogous description as for subs12320 but for the set {1,3,4}. •subs23420 : the analogous description as for subs12320 but for the set {2,3,4}, which is never preserved by a function f∈cMaj{0,1} 5. •e1 = ’X’: a character constant for the first projection e(3) 0 •e2 = ’Y’: a character constant for the second projection e(3) 1 •e3 = ’Z’: a character constant for the third projection e(3) 2 6.3 Functions 6.3.1 write Writes its argument to stdout without a line break at the end. 6.3.2 fprint Writes its second argument to the first argument f with a line break at the end. 6.3.3 hasht Takes four arguments x, y, z, k and computes the hash value xk2+yk +z. 6.3.4 eval20 See 5.4.4. 6.3.5 eval60 See 5.4.5; for the test whether the first argument is a projection, it is compared against the three global constants e1,e2 and e3. 6.3.6 output_uacalc_f60_fname Outputs a function f∈Maj{0,1} 5 , given by its representation ˆ Nf< 2 60 , or f∈ne(3) 0, e(3) 1, e(3) 2o to the file fname in the format required for the universal algebra calculator [ 4 ]. The resulting .alg -file then allows investigations of the algebra ({0,...,4};f). For a format description of .alg-files, see Section 6.4. 6.3.7 output_uacalc_f60 See 6.3.6, but this routine automatically determines the file name of the resulting .alg-file from the function representation ˆ Nf. 6.3.8 output_uacalc_f20_fname See 6.3.6, but this routine takes a function argument f∈cMaj{0,1} 5 given by its representation Nf<220. 22 6.3.9 output_uacalc_f20 See 6.3.8, but this routine automatically determines the file name of the resulting .alg-file from the function representation Nf. 6.3.10 ppprintf20 See 5.4.2, but the argument may also be a projection in this implementation. 6.3.11 pprintf20 See 5.4.3, but the argument may also be a projection in this implementation. 6.3.12 pprintf20_Wachtel_style As 6.3.11, but the order of printed function values corresponds to the bit order used in [8] for the representation of f∈cMaj{0,1} 5as integers. 6.3.13 convertf20_to_Wachtel_encoding Takes Nf of some f∈cMaj{0,1} 5 and converts it to the hash value ˜ Nf< 2 20 used in [8]. 6.3.14 compose20 As 5.4.6, but the difference in this implementation is that an additional conditional ensures that the result of the composition is also correct if the three inner functions g1, g2, g3∈Maj{0,1} 5∪ne(3) 0, e(3) 1, e(3) 2o that are composed with f∈cMaj{0,1} 5 are not pairwise distinct. However, in the rest of the code this additional functionality is never relied upon. 6.3.15 compose As 5.4.8, but the difference in this implementation is that an additional conditional ensures that the result of the composition is also correct if the three inner functions g1, g2, g3∈Maj{0,1} 5∪ne(3) 0, e(3) 1, e(3) 2o that are composed with f∈cMaj{0,1} 5 are not pairwise distinct. However, in the rest of the code this additional functionality is never relied upon. 6.3.16 reverse20 This function takes as input Nf< 2 20 of some f∈cMaj{0,1} 5 and computes and returns N¯ f< 2 20 where ¯ f∈cMaj{0,1} 5 is given by ¯ f ( x, y, z ) : = f ( z, y, x )for x, y, z ∈ {0,...,4} . In the computation the global dictionary evaldic20 is used. 6.3.17 rev This function takes as input ˆ Nf< 2 60 of some f∈Maj{0,1} 5 and computes and returns ˆ N¯ f< 2 60 where ¯ f∈Maj{0,1} 5 is given by ¯ f ( x, y, z ) : = f ( z, y, x ) for x, y, z ∈ {0,...,4} . The implementation is a simple application of compose using the projections in the reverse order; clearly ¯ f∈ ⟨f⟩(3) OA. 23 6.3.18 cycl This function takes as input ˆ Nf< 2 60 of some f∈Maj{0,1} 5 and computes and returns ˆ Nζ(f)< 2 60 where ζ ( f ) ∈Maj{0,1} 5 is given by ζ ( f )( x, y, z ) : = f ( y, z, x ) for x, y, z ∈ {0,...,4} . The implementation is a simple application of compose shifting the projections cyclically; clearly ζ(f)∈ ⟨f⟩(3) OA. 6.3.19 iteratex This function takes as input ˆ Nf< 2 60 of some f∈Maj{0,1} 5 and computes and returns ˆ Nι1(f)< 2 60 where ι1 ( f ) ∈Maj{0,1} 5 is given for x, y, z ∈ {0,...,4} by the rule ι1 ( f )( x, y, z ) : = f ( f ( x, y, z ) , y, z ). The implementation is a simple application of compose; clearly ι1(f)∈ ⟨f⟩(3) OA. 6.3.20 iteratey This function takes as input ˆ Nf< 2 60 of some f∈Maj{0,1} 5 and computes and returns ˆ Nι2(f)< 2 60 where ι2 ( f ) ∈Maj{0,1} 5 is given for x, y, z ∈ {0,...,4} by the rule ι2 ( f )( x, y, z ) : = f ( x, f ( x, y, z ) , z ). The implementation is a simple application of compose; clearly ι2(f)∈ ⟨f⟩(3) OA. 6.3.21 iteratez This function takes as input ˆ Nf< 2 60 of some f∈Maj{0,1} 5 and computes and returns ˆ Nι3(f)< 2 60 where ι3 ( f ) ∈Maj{0,1} 5 is given for x, y, z ∈ {0,...,4} by the rule ι3 ( f )( x, y, z ) : = f ( x, y, f ( x, y, z )). The implementation is a simple application of compose; clearly ι3(f)∈ ⟨f⟩(3) OA. 6.3.22 starprod As 5.4.17, but raises an exception if one of the arguments is a projection. 6.3.23 bulletprod As 5.4.19, but raises an exception if one of the arguments is a projection. 6.3.24 bulletrevprod Takes as input f, g ∈Maj{0,1} 5 , represented by their ˆ Nf,ˆ Ng< 2 60 and computes ˆ Nh< 2 60 where h ( x, y, z ) : = f ( g ( z, y, x ) , y, z )for x, y, z ∈ {0,...,4} . Clearly, h = f•¯g =: f¯ •g∈ ⟨{f, g}⟩(3) OA∩Maj{0,1} 5 . The implementation translates the defining term for h into an application of compose and raises an exception of one of the arguments is a projection. 6.3.25 bulletpseudoprod Takes as input f, g ∈Maj{0,1} 5 , represented by their ˆ Nf,ˆ Ng< 2 60 and computes ˆ Nh< 2 60 where h ( x, y, z ) : = f ( x, g ( z, y, x ) , y )for x, y, z ∈ {0,...,4} . Clearly, h =: f˜ •g∈ ⟨{f, g}⟩(3) OA∩Maj{0,1} 5 . The implementation translates the defining term for h into an application of compose and raises an exception of 24 one of the arguments is a projection. exception of one of the arguments is a projection. 6.3.26 dcircprod As 5.4.21, but raises an exception if one of the arguments is a projection. 6.3.27 starsquare Computes starprod(f,f) for an integer frepresenting a function in Maj{0,1} 5. 6.3.28 starpower See 5.4.18. 6.3.29 bulletsquare Computes bulletprod(f,f) for an integer f representing a function in Maj{0,1} 5 . 6.3.30 bulletpower See 5.4.20. 6.3.31 dcircsquare Computes dcircprod(f,f) for an integer f representing a function in Maj{0,1} 5 . 6.3.32 dcircpower See 5.4.22. 6.3.33 majfunc01valued_preserves_3el_subset This function takes three arguments, an integer ˆ Nf< 2 60 representing some f∈Maj{0,1} 5 , a list S of six indices representing a subset U = {b, u, v} where b∈ {0,1} and u, v ∈ {2,3,4} are distinct, and as its last argument the integer b . Clearly, f preserves U if and only if the value of f on all six permutations of ( b, u, v )equals b . The bit positions of these six argument permutations in the encoding ˆ Nf are assumed to be listed in S , for example, for U = {1,3,4} one would use the arguments b = 1 and S = subs134 from Subsection 6.2. The function tests if f preserves U (represented by S ) by checking whether for all six positions in S the function value equals b . If not, False is returned immediately; otherwise, the function concludes by returning True. 6.3.34 majfunc01valued20_fails_preservation_3el_subset This function takes three arguments, an integer Nf< 2 20 representing some f∈cMaj{0,1} 5 , a list S of two indices representing a subset U = {b, u, v} where b∈ {0,1} and u, v ∈ {2,3,4} are distinct, and as its last argument the integer b . By cyclic symmetry, f preserves U if and only if the value of f on the two triples ( b, u, v )and ( b, v, u )equals b . The bit positions of these two argument 25 If Fn = Fn+1 = ⟨h⟩(3) OA has been computed without finding f∈Fn in the process, False is returned; the computed set Fn = ⟨h⟩(3) OA is discarded. None of the checks for non-minimality of hfrom 6.3.48 are performed. In the same way as compute_ternary_part_of_gen_clone , the execution of this function is computationally expensive in terms of the number of applications of compose and should thus be applied with care. 6.3.52 is_minimal This function takes as its single argument an integer Nf< 2 20 representing some f∈cMaj{0,1} 5 and tests whether ⟨f⟩OA is minimal by computing ⟨f⟩(3) OA and applying Lemma 1. If ⟨f⟩OA is minimal, the return value is False , otherwise True. At first, similar to the process explained in 6.3.48, the function uses compose20 to iteratively compute increasing approximations ne(3) 0, e(3) 1, e(3) 2o=F0⊆F1⊆F2⊆. . . ⊆Fn=Fn+1 =⟨f⟩(3) OA of ⟨f⟩(3) OA until Fn = Fn+1 = ⟨f⟩(3) OA has been reached. Then it loops over every h∈ ⟨f⟩(3) OA in the computed set, and tests, provided that h /∈ne(3) 0, e(2) 1, e(3) 2o , whether f∈ ⟨h⟩(3) OA by calling find_f_in_ternary_part_of_gen_clone on the representations ˆ Nf and ˆ Nh . If this returns False , then f is not minimal by Lemma 1, and False is returned by is_minimal . If this situation did not happen for any h∈ ⟨f⟩(3) OA , then the function concludes by returning True since minimality of ⟨f⟩OAhas been verified with the help of Lemma 1. This test is highly computationally expensive as it uses the involved function find_f_in_ternary_part_of_gen_clone inside a loop, and thus it should be used with much care. 6.3.53 is_minimal_slower This is a variant implementation of is_minimal , where already during the computation of ⟨f⟩(3) OA the test find_f_in_ternary_part_of_gen_clone is applied for each newly computed non-trivial h∈ ⟨f⟩(3) OA∩Maj{0,1} 5 . The idea behind this is to detect cases where ⟨f⟩OA is not minimal early and to return False before completing the computation of ⟨f⟩(3) OA , which would be unnecessary in such a case. The downside to this approach is that the computationally expensive test is used on the inside of the nested triple loop to compute the closure ⟨f⟩(3) OA . This has the consequence that overall this implementation gives significantly longer runtimes than is_minimal . Therefore, this function is not used in other parts of the code. 6.3.54 check_for_minimality The function takes as its argument an iterable containing Nf< 2 20 of cyclically symmetric majority functions f∈cMaj{0,1} 5 and checks each of them for minimality by calling is_minimal . The result of the test is reported to stdout . 32 Those Nf where f has been confirmed as minimal are appended to an initially empty list which is returned upon completion of the function. Note that is_minimal is a time consuming test, wherefore the function should not be used on large random containers of functions, where many nonminimal functions may generate large sets ⟨f⟩(3) OA that can be hard to refute as non-minimal. The function is intended to be used on pre-processed collections of functions that contain many functions that are likely to be minimal and perhaps only a few exceptions. 6.3.55 conjugatef20 This function takes two arguments, Nf< 2 20 for some f∈cMaj{0,1} 5 and a list of five integers representing the values [ π (0) , π (1) , . . . , π (4)] of a permutation π∈Sym (5) with {π(0), π(1)} = {0,1} (that is, π preserves the set {0,1} ). The function computes Nh< 2 20 for the conjugated function h: = π−1◦f◦ ( π×π×π ) as described in 5.4.31. 6.3.56 simple_remove_conjugates This function takes as its input a list of integers Nf< 2 20 representing majority functions f∈cMaj{0,1} 5 and computes a transversal of the list up to conjugacy. That is, it returns a list that contains exactly one representative from each conjugacy class occurring in the given list. The conjugacy class of f is the set of all functions that are conjugate to f , that is, those h: 5 3→ 5for which there is a permutation π∈Sym (5) such that h = π−1◦f◦ ( π×π×π ). Every conjugate function h also belongs to cMaj5 , and if π preserves {0,1} , then h = π◦f◦ ( π×π×π ) ∈cMaj{0,1} 5 . Since the given list only contains representations of {0,1} -valued cyclically symmetric majority operations, only the conjugates under the set-wise stabiliser of {0,1} in Sym (5) need to be considered in the computation of the equivalence class (as only those need to be removed from the list). The given list is copied to a new list transversal . Then the function iterates over each f∈Maj{0,1} 5 where Nf belongs to transversal , and in an inner loop over all 11 non-identical permutations π∈Sym (5) with {π(0), π(1)} = {0,1} . For each of these, h: = π−1◦f◦ ( π×π×π ) ∈cMaj{0,1} 5 is computed via conjugatef20 and if Nh = Nf , then all occurrences of Nh in transversal are replaced by -1 and thus marked as unnecessary. Multiple occurrences of Nf in the list are not handled (not removed) but can be treated afterwards by sorting or by conversion to a set. Finally, a list of the non-negative elements from transversal is returned. 6.3.57 simple_remove_equivalents This function takes as its input a list of integers Nf< 2 20 representing majority functions f∈cMaj{0,1} 5 and computes a transversal of the list up to the following equivalence relation: h: 5 3→ 5is equivalent to f , denoted by h≡f , iff h is conjugate to f or conjugate to ¯ f . That is, there is some permutation π∈Sym (5) such that h = π−1◦f◦ ( π×π×π )or h = π−1◦¯ f◦ ( π×π×π ). The latter case is equivalent to ¯ h = π−1◦f◦ ( π×π×π ), hence an alternative formulation 33 is that h≡f iff there is π∈Sym (5) with π−1◦f◦ ( π×π×π ) ∈h, ¯ h . This means that the computation of a transversal modulo ≡ removes from the given list all conjugates of a given function and all the reversed functions of every conjugate. Since the given list only contains integers representing {0,1} - valued majority operations, in the computation of the conjugates only those permutations π∈Sym(5) need to be considered where {π(0), π(1)}={0,1}. The implementation is similar to simple_remove_conjugates . The given list is copied to a new list transversal . Then the algorithm iterates over each f∈Maj{0,1} 5 where Nf belongs to transversal , and in an inner loop over all 11 non-identical permutations π∈Sym (5) with {π(0), π(1)} = {0,1} . For each of these, h: = π−1◦f◦ ( π×π×π ) ∈cMaj{0,1} 5 is computed via conjugatef20 and if Nh = Nf , then all occurrences of Nh in transversal are replaced by -1 and thus marked as unnecessary. Afterwards, for each of the 12 permutations π∈Sym (5) with {π(0), π(1)} = {0,1} , the conjugate h: = π−1◦¯ f◦ ( π×π×π ) ∈cMaj{0,1} 5 is computed via conjugatef20 and if Nh = Nf , then all occurrences of Nh in transversal are replaced by -1 . Multiple occurrences of Nf in the list are not handled (not removed) but can be treated afterwards by sorting or by conversion to a set. Finally, a list of the non-negative elements from transversal is returned. 6.3.58 write_conjugates This is an auxiliary function to compare conjugacy classes of cyclically symmetric {0,1} -valued majority functions in a given iterable container to function representations resulting from computations reported in [8]. The input of this function is an iterable flist of Nf< 2 20 representing functions f∈cMaj{0,1} 5 . The code iterates over each function f represented in flist and computes all conjugates of f under the stabiliser group of permutations from Sym (5) that preserve the set {0,1} . This conjugacy class is computed as a set [ f ] \ {f} , and then Nf is written to stdout , followed by ˜ Nh for each h∈ [ f ] \ {f} , where ˜ Nh< 2 20 is the hash value for cyclically symmetric {0,1} -valued majority operations used in [ 8 ]. For this the routine convertf20_to_Wachtel_encoding is called. There is no return value. 6.3.59 reduce_list_and_check_for_minimality This function takes as its first argument a list of integers Nf< 2 20 representing functions f∈cMaj{0,1} 5 and calls simple_remove_conjugates on it, to compute a list of conjugacy representatives. The representatives are reported to stdout and if the second optional argument is set to True (the default being False ) also the value tables of the representatives are printed using pprintf20 and the number of majority functions generated by each representative is computed by compute_clone_sizes and reported to the screen. For this reason, the flag True should be used with care and the default value is False. After that all the representatives are checked for minimality by calling check_for_minimality and the resulting list of minimal representatives is returned by the function. The minimality check may be very time consuming thus this function should be used with care (e.g., the original list should not contain too many non-minimal functions f∈cMaj{0,1} 5 where ⟨f⟩(3) OA is large 34 and it takes long to refute minimality; such functions f should be removed with faster tests before). 6.3.60 find_minimal_functions_from_scratch This function without arguments is the central routine of the script. It simply calls reduce_list_and_check_for_minimality (with the default second argument switching off the reporting of clone sizes of the conjugacy representatives) on the result of filter_out_nonminimals(20) and returns the computed list of representations Nf< 2 20 of minimal cyclically symmetric majority operations f∈cMaj{0,1} 5. This means, in the first step filter_out_nonminimals(20), all potentially minimal f∈cMaj{0,1} 5 are investigated in a large loop and all those are discarded that can be easily shown to be non-minimal by violating certain necessary conditions. The computation of the first step took about 19 hours 6 with the hardware specified at the beginning of the file 01_valued_majorityfuncs.py . The resulting list of 656 quasiminimal functions is reduced up to conjugacy in the second step (the first part of reduce_list_and_check_for_minimality ). In the third step (the second part of reduce_list_and_check_for_minimality ) the 78 representative quasiminimal functions are tested for actual minimality, only the (by Lemma 1) provably minimal ones are kept, and the computed list of 44 minimal conjugacy representatives is returned. These are the same as those computed by check_416_cpp_candidates_for_minimality (cf. 6.3.61) 6.3.61 check_416_cpp_candidates_for_minimality Without arguments this function calls reduce_list_and_check_for_minimality (with the default second argument switching off the additional analysis of the conjugacy representatives) on a hard coded list of 416 Nf< 2 20 of quasiminimal functions f∈cMaj{0,1} 5 as computed by the c++ -implementation (see 5.4.36 and 5.4.24) and returns the list of minimal functions among the conjugacy representatives of the given 416 majority operations. This results in the same 44 minimal functions as those computed by find_minimal_functions_from_scratch . The runtime for this computation was measured to around 22 minutes with the hardware specified at the beginning of the file 01_valued_majorityfuncs.py. 6.3.62 write_416_cpp_in_Wachtel_encoding This routine has no arguments nor return values. It iterates over a hard coded list of 416 Nf< 2 20 of quasiminimal functions f∈cMaj{0,1} 5 as computed by the c++ -implementation (see 5.4.36 and 5.4.24) and, for comparison with the results of [ 8 ], prints the value table of each f according to pprintf20_Wachtel_style . Then the 416 functions are reduced modulo conjugacy by a call to the function simple_remove_conjugates , and the number of conjugacy representatives as well as a value table for each representative function is reported to stdout by pprintf20_Wachtel_style (for comparison with [8]). 6All the remaining computations took less than one hour. 35 6.3.63 convert_44minimals_to_Wachtel_encoding This routine has no arguments and iterates over a hard coded list of 44 integers Nf< 2 20 corresponding to the 44 minimal functions f∈cMaj{0,1} 5 computed by check_416_cpp_candidates_for_minimality . In order to compare results with [ 8 ], for each of these operations f , the encodings Nf,˜ Nf< 2 20 are printed to stdout , where ˜ Nf is the encoding used in [ 8 ] as computed by convertf20_to_Wachtel_encoding. There is no return value. 6.3.64 print_out_gen_clones This is an auxiliary function to analyse in some detail all functions from some iterable container provided as the first argument. There is an additional second optional argument with default value None , which if given is expected to be a list of four values [ a, b, c, d ]where a, b, c ∈ {0,...,4} are three distinct argument values and d∈ {0,1}is a function value. The first input of this function is an iterable flist of integers Nf< 2 20 representing functions f∈cMaj{0,1} 5 . The code iterates over each function f represented in flist and first prints Nf and ˆ Nf for each of them. Then ⟨f⟩(3) OA is computed by calling compute_ternary_part_of_gen_clone . It is either reported that f is not minimal (if this is detected), or all the ˆ Nh for h∈ ⟨f⟩(3) OA are printed to stdout . If the second optional argument is given, some more specific information on the functions in ⟨f⟩(3) OAis reported. 6.3.65 write_uacalc_files This is an auxiliary analysis function taking as its first argument an iterable containing either only integers Nf< 2 20 , representing operations f∈cMaj{0,1} 5 , or only integers ˆ Nf< 2 60 , representing operations f∈Maj{0,1} 5 . The second argument is Boolean with default value True and decides if the integers in the iterable container represent functions from cMaj{0,1} 5 (the default case) or if they should be interpreted as hash values of functions from Maj{0,1} 5. The function iterates over each hash value of the operations f represented in the first argument and calls output_uacalc_f20 or output_uacalc_f60 as appropriate according to the value of the second argument of the function. This writes .alg -files for the universal algebra calculator [ 4 ] representing the algebra ({0,...,4};f) for further analysis of the operation f . For a description of the output files, see Section 6.4. There is no return value. 6.3.66 compare_to_original_f This is an internal function taking two integers (that are supposed to represent majority operations), and as a third optional argument a string label. The two first arguments are compared for equality; then the first argument, the label and the result of the comparison are reported to stdout. 6.3.67 understand_clone_520203 This is an auxiliary function to analyse the ternary part ⟨f⟩(3) OA for the generator function f∈cMaj{0,1} 5 that satisfies Nf = 520203. In this case ⟨f⟩(3) OA consists of 36 exactly 64 majority operations and the three projections. Functions with certain value patterns are isolated in ⟨f⟩(3) OA and for them it is computationally verified that specific hard coded terms evaluate as term functions to the original generator function f . This will be helpful in a ‘pencil and paper proof’ that ⟨f⟩OA is a minimal clone. The functions compare_to_original_f , print_out_gen_clones , as well as compute_ternary_part_of_gen_clone_with_terms are used for this. Also a few .alg-files are written by this routine. 6.3.68 understand_clone_520205 This function is analogous to understand_clone_520203 but for the operation f∈cMaj{0,1} 5 where Nf = 520205. Note that f is a conjugate of ¯g where Ng= 520265. 6.3.69 understand_clone_520266 This function is analogous to understand_clone_520203 but for the operation f∈cMaj{0,1} 5 where Nf = 520266. Note that f is a conjugate of ¯g where Ng= 520203. 6.3.70 main The top level code calls find_minimal_functions_from_scratch to compute a list of 44 minimal functions found among the conjugacy representatives of the quasiminimal functions isolated via filter_out_nonminimals(20) . These 44 functions are compared to a hard coded list of the 44 functions produced by the c++ -implementation via compute_minimals (see 5.4.36) and the result is reported to stdout. It is possible to uncomment two lines in the code in order to produce .alg - files for each of the 44 minimal representatives or to print out the ternary part of each representative to stdout. Currently these two functionalities are disabled by turning the respective function calls into comments. The reason for this is that computation of the ternary part is time-consuming (and that the output would clutter the log file); likewise the output of the alg. -files would clutter the current directory with 44 files (around 250 bytes each, as only 2 + 125 integer values need to be saved per file) every time the script is run. Subsequently, representatives of the 44 functions up to ≡ (as defined in Section 6.3.57) are computed with simple_remove_equivalents , resulting in a list of 26 functions. The hash values of these functions are reported to stdout. At this point the main function terminates; it contains some further (selfexplanatory) calls to analysis or auxiliary functions beyond the return statement. These can be added to the execution at the discretion of the caller of the script. Currently, they are not executed and thus their results are not present in the output log files listed in Section 2. 6.4 Format description of .alg-files This section contains a short explanation of the format used in .alg -input files for the universal algebra calculator [ 4 ]. A finite algebra Awith n≥ 1elements 37 is represented in UACalc by the standard carrier set n = {0,1, . . . , n −1} . An .alg-file contains, line by line, the following integer numbers. •The first line contains the value n, the cardinality of the algebra. • For each fundamental operation f of A, say with k≥ 0arguments, the following lines are included: –a line with the value k –nklines with the values of fin the following order: f(0,0,0,...,0) f(1,0,0,...,0) . . . f(n−1,0,0,...,0) f(0,1,0,...,0) f(1,1,0,...,0) . . . f(n−1,1,0,...,0) f(0,2,0,...,0) . . . f(0, n −1,0,...,0) . . . f(n−1, n −1,0. . . , 0) f(0,0,1,...,0) ... f(n−1, n −1,...,n−1), that is to say, the first argument changes fastest, the last argument changes slowest. Example. The left-zero semigroup on {0,1,2} , that is, ({0,1,2};f) where f is the binary operation f:{0,1,2}2→ {0,1,2} given as f ( x, y ) : = x for each x, y ∈ {0,1,2}, having the operation table x\y012 0 0 0 0 1 1 1 1 2 2 2 2 , would be stored in .alg -format as follows: 3 2 0 1 2 38 0 1 2 0 1 2 Acknowledgement The author wishes to express his gratitude to Andreas Wachtel for reading and giving some feedback on this code documentation, which hopefully has served to make the description of the routines more readable. References [1] Mike Behrisch. Clones with nullary operations. In John Power and Cai Wingfield, editors, Proceedings of the Workshop on Algebra, Coalgebra and Topology (WACT 2013), volume 303 of Electron. Notes Theor. Comput. Sci., pages 3–35, Amsterdam, March 2014. Elsevier Sci. B. V. doi: https: //doi.org/10.1016/j.entcs.2014.02.002. [2] Béla Csákány. All minimal clones on the three-element set. Acta Cybernet., 6(3):227–238, 1983. [3] Béla Csákány. On conservative minimal operations. In Lectures in universal algebra (Szeged, 1983), volume 43 of Colloq. Math. Soc. János Bolyai, pages 49–60. North-Holland, Amsterdam, 1986. doi: https://doi.org/10.1016/ B978-0-444-87759-8.50009-2. [4] Ralph Freese, Emil Kiss, and Matthew Valeriote Universal Algebra Calculator, 2024. Available on-line from https://www.uacalc.org. [5] Dietlinde Lau. Function algebras on finite sets. Springer Monographs in Mathematics. Springer, Berlin, 2006. A basic course on many-valued logic and clone theory. doi: https://doi.org/10.1007/3-540-36023-9. [6] Reinhard Pöschel and Lev Arkaďevič Kalužnin. Funktionenund Relationenalgebren. VEB Deutscher Verlag der Wissenschaften, Berlin, 1979. doi: https://doi.org/10.1007/978-3-0348-5547-1. [7] Ivo G. Rosenberg. Minimal clones. I. The five types. In Lectures in universal algebra (Szeged, 1983), volume 43 of Colloq. Math. Soc. János Bolyai, pages 405–427. North-Holland, Amsterdam, 1986. doi: https://doi.org/10.1016/ B978-0-444-87759-8.50029-8. [8] Andreas Wachtel. Parallel computing minimal f∈cMaj{0,1} 5 (py). Zenodo, September 2024. doi: https://doi.org/10.5281/zenodo.13786499. [9] Tamás Waldhauser. Minimal clones generated by majority operations. Algebra Universalis, 44(1-2):15–26, October 2000. doi: https://doi.org/10.1007/ s000120050167. 39 [10] Tamás Waldhauser. Minimal clones. PhD dissertation, Szegedi Tudományegyetem (SZTE), Bolyai Institute, 2007. [11] Tamás Waldhauser. Minimal clones with few majority operations. Acta Sci. Math. (Szeged), 73(3-4):471–486, 2007. 40