102Notes on Self‐Commuting Functions
on a Finite Set
Hajime Machida*Ivo G.Rosenberg

Tokyo, JapanMontréal, CanadaAbstract

A multi‐variable function is said to be sclf‐commuting if it commutes with itself.
As the first step toward the characterization of self‐commuting functions defined ona finite set this article studies very basic facts on them. We restrict our attention toself‐commuting and conservative binary functions. Such functions on a three‐element
set are characterized and some examples of such functions on arbitrary finite set arepresented.

Keywords: commutation; self‐commuting function, conservative function

1Introduction

Ever since the concept of commutation was introduced on the set of finitary functions oversome set, commutation and its related topics have been studied by many authors. (See, e.g.,[BW87], [Da79], [Her08], [MR04], [MRII], [Sza85].)
When two functions f and g commute we write f\perp g . (The definition of commutation
will appear in the next section.) The binary relation induced by \perp is symmetric, but it is
not reflexive, that is, there exists a function which does not commute with itself. We call afunction self‐commuting if it commutes with itself.

Our goal is the characterization of self‐commuting functions defined on arbitrary finiteset. As the first step toward this goal, we take up in this note conservative binary functions
and present some preparatory results on self‐commuting and conservative binary functions.
In Section 4 such functions on a three‐element set are characterized and in Section 5 an

attempt is made to generalize thc result on a three‐element set to that on any finite set.12Definitions and Notations

Let E_{k}=\{0,1, , k-1\} for finite k>1 . We denote by \mathcal{O}_{k}^{(n)} for n\geq 1 the set of n ‐variable
functions defined on E_{k} , that is, the set of maps from E_{k}^{n} into E_{k} , and by \mathcal{O}_{k} the set offunctions defined over E_{k} , i.e., \mathcal{O}_{k}=\bigcup_{n=1}^{\infty}\mathcal{O}_{k}^{(n)}. A projection e_{i}^{n} , for n>0 and 1\leq i\leq n,is the function in \mathcal{O}_{k}^{()} which always takes the value of the i‐th variable. The set of all*machida. zauber@gmail com

lAfter finishing this articıe. the compıete characterization of self‐commuting and conservative binary

functions on arbitrary finite set was obtained (P. P. Pálfy and H. Machida).

103
projections is denoted by \mathcal{J}_{k}. A clone over E_{k} is a subset

C of \mathcal{O}_{k} which is closed under(functional) composition and includes \mathcal{J}_{k}.
Commutation for two multi‐variable functions are defined in the following way.
Definition 2.1 For

f\in \mathcal{O}_{k}^{(n)} and g\in \mathcal{O}_{k}^{(m)},f and g commute lf

g(f(a_{11}, \ldots, a_{1n}), \ldots, f(a_{m1}, \ldots, a_{mn}))= f(g(a_{11}, \ldots, a_{m1}), \ldots, g(a_{1n}, \ldots, a_{mn}))holdg for all a i_{f}\in E_{k}(i=1, \ldots, m;j=1, \ldots, n) .

Let us introduce thc operation \Diamond : \mathcal{O}_{k}^{(m)}\cros \mathcal{O}_{k}^{(n)}ar ow E_{k}^{\mathcal{M}_{m.n} (E_{k})} in the following way:f\in \mathcal{O}_{k}^{(n)}, g\in \mathcal{O}_{k}^{(m)} and M\in \mathcal{M}_{7n,n}(E_{k}) defineFor(g\Diamond f)(M) = g(f(r_{1}), \ldots, f(r_{m}))where r_{i} is the i‐th row of M ({\imath} \leq i\leq m) . Thcn, f and g commute if(g\Diamond f)(M) = (f\Diamond g)(tM)
holds for all

M\in \mathcal{M}_{7nn}(E_{k}) .

When f and g commute, we write f\perp g . Obviously, the binary relation \perp is symmetric.
However, the relation \perp is not reflexive, that is, f_{7}Lf holds for some f in \mathcal{O}_{k}.
Definition 2.2 For f\in \mathcal{O}_{k} , we say f is self‐commuting if f\perp f holds.

There are plenty of functions which are not self‐commuting. We draw some such examples
from \mathcal{O}_{2}^{(2)} , i.e., binary functions on E_{2} . The binary function f will be denoted by f_{i}(0\leq i\leq 15) when i=f(0,0) 2^{3}+f ( 0 , ı) . 2^{2}+f(1,0) . 2+f(1,1) . Thus, for example, f_{0}is the constant function taking 0, f_{1} is AND and f_{3} is the projection e_{1}^{2}.
In Table 1, the last column shows whether a function f is self‐commuting or not. The
symbol 0 in the i‐th row indicates the function f_{i} is self‐commuting and x indicates it is not
self‐commuting. Among 16 functions, 10 are self‐commuting and 6 are not self‐commuting.
In order to verify the results in the table, we pick up just one case: f_{14}(= NAND) . Consider
the following (2, 2)‐matrix Al.

M=(\begin{ar ay}{l } 0 0 1 1 \end{ar ay})
It is immediate to see that fı4 7Lf_{14} is verified by this M.

3

Some Simple Properties(1) For f\in \mathcal{O}_{k}^{(n)}, g\in \mathcal{O}_{k}^{(m)} and M\in \mathcal{M}_{m,n}(E_{k}) , we shall write
f\perp gon

Mif (g\Diamond f)(M)=(f\Diamond g)(tM) holds. Thus, f\perp 9 if and only if “ f\perp g on M ” holds for all
M in \mathcal{M}_{m,n}(E_{k}) .

104

Table 1: Binary Functions on E_{2}Lemma 3.1 For

f\in \mathcal{O}_{k}^{(n)} and M\in \mathcal{M}_{n}(E_{k}) we have.‘(1) If M is symmetric then f\perp f on M

(2)

f\perp f onM

if and only if f\perp f on tM (Here,tM is the transposed matrix ofM.)(2) Lct us define\# M=| \{a ij|1\leq i\leq m, 1\leq 2\leq n\}|

for

M=

(a i_{j})\in M_{rn,n}(E_{k}) .

For example, let

j14_{1}=(\begin{ar ay}{l } 0 0 0 0 \end{ar ay}), M_{2}=(\begin{ar ay}{l } 0 1 0 0 \end{ar ay}), M_{3}=(\begin{ar ay}{l } 0 l 2 0 \end{ar ay})
Then we have

Next,a_{1},\# M_{1}=1, \# M_{2}=2, \# M_{3}=3.

f\in \mathcal{O}_{k}^{(n)} is said to be conservative if f(a_{1}, \ldots, a_{n})\in\{a_{1}, a_{n}\} holds for alla_{n}\in E_{k}.

Lemma 3.2 For f\in \mathcal{O}_{k}^{(2)} and M\in \mathcal{M}_{2}(E_{k}), if f is conservative andf\perp f on\# M\leq 2

thenM.

Proof When \# M=1 the assertion is trivial. Suppose \# M=2 . Then, due to Lemma

3.1, among the following matrices where a\neq b we need to consider only two matrices (thesecond and the fifth).

(\begin{ar ay}{l } a a a b \end{ar ay})(\begin{ar ay}{l } a a b a \end{ar ay})(\begin{ar ay}{l } a b a a \end{ar ay})(\begin{ar ay}{l } b a a a \end{ar ay})(\begin{ar ay}{l } a a b b \end{ar ay})(\begin{ar ay}{l } a b a b \end{ar ay})(\begin{ar ay}{l } a b b a \end{ar ay})M_{1}=(\begin{ar ay}{l } a a b a \end{ar ay})

Case 1:Let*=f(f(a, a), f(b, a))=f(a, f(b, a))and\wp=f(f(a, b), f(a, a))=f(f(a, b)_{)}a) .

If

105
f(a, b)=a then it is clear that \bullet=\wp=a . Next, suppose f(a, b)=b . Then, f(b, a)=a
implies \bullet=\wp=a and f(b, a)=b implies \bullet=\wp=b . Hence f\perp f on M_{1}.
Case 2:M_{2}=(\begin{ar ay}{l } a a b b \end{ar ay})

Clearly we have f(f(a, a), f(b, b))=f(a, b)=f(f(a, b), f(a, b)) , showing f\perp f on M_{2}.

\squareCorollary 3.3 For a binary function f on E_{2} , i. e., f\in \mathcal{O}_{2}^{(2)}, if f is conservative then f isself‐commuting.

4

Binary Functions on E_{3}In this section we consider 2‐variable functions on

to find all conservative f\in \mathcal{O}_{3}^{(2)} satisfying f\perp f.

E_{3}=\{0,1,2\} . Our aim in this section isIn order to find all such functions, we need to consider

M onıy of the following type,because of Lemma 3.1 again.

(A)(\begin{ar ay}{l} a_{l} O 1 a_{2} \end{ar ay})(B)(\begin{ar ay}{l} b_{l} 0 2 b_{2} \end{ar ay})(C)(\begin{ar ay}{l} c_{l} 1 2 c_{2} \end{ar ay})First, take, for example, a matrix M_{0} of type (A):M_{0}=(\begin{ar ay}{l} 0 0 1 2 \end{ar ay})In this case, in order to have the condition “‘ f\perp f on M_{0}f must satisfyf(0_{1}f(1,2)) = f(f(0,1), f(0,2)).

It follows that\bulletf(0,1)=0, f(0,2)=2\Rightarrow f(1,2)=2\bulletf(0,1)=1, f(0,2)=0, f(1,2)=1\Rightarrow f(1,0)=1f(0,1)-1, f(0,2)-0, f(1,2)=2\Rightarrow f(1,0)=0

In other words, each row in the following table gives a forbidden combindtion for AT_{0} :By applying the similar consideration to other matrices of type (A) we get the following
table of forbidden combinations.

(A)

106
The forbidden combinations for types (B) and (C) are the following:

(B)

(C)

Now, the list of the binary functions on E_{3} which are self‐commuting and conservative is:

To rephrase, we conclude as follows.

Proposition 4.1 If f\in \mathcal{O}_{3}^{(2)} is self‐commuting and conservative, then f is a projection
or one of the following shape. (Here the symbol * indicates arbitrary element provided thatconservat?vene6S is preserved.)

107
5

Binary Functions on E_{k}In this section we consider more general case: E_{k} for any k>1 . We present some examplesof self‐commuting and conservative binary functions on E_{k}.
Notice that if f\in \mathcal{O}_{k}^{(2)} is self‐commuting and conservative then the following property,
which we may call the 3‐element property, must be satisfied for f.

“The3‐element property” : For every 3‐element subset \{a, b, c\} of E_{k} , the \zeta sub ‐tables’of Cayley table of f consisting of the rows and the columns corresponding to a, b and c are oneof the following forms. (Here the symbol*

is arbitrary up to preserving conservativeness.)

Now, the following Cayley tables are three examples of self‐commuting and conservative

binary functions f(\in \mathcal{O}_{k}^{(2)}) on E_{k} . (Again,*is arbitrary up to preserving conservativeness.)

(1)

(2)

(3)

We remark that the 3‐element property can be effectively used to obtain these examples.

108
References[BWS7] Burris, S. and Willard, R., Finitely many primitive positive clones, Proceedings of theAmer. Math. Soc. , 1987, 427‐430.

[Da77] Danil’tchenko, A. F., Parametric expressibility of functions of three‐valued logic (in Rus‐sian), Algebra i Logika, 16, 1977, 397‐416, English transıation: Algebra and Logic, 16, 1977,266‐280.

[Da79] Danil’c‐enko, A. \Gamma. , On parametrical expressibility of the functions of k ‐valued logic, Colloquia Mathematica Societatis János Bolyai, 28, Finite Algebra and Multiple‐Valued Logic,
1979, 147‐159.

[Her08] Hermarln, M., On Boolean primitive positive clones, Disc. Math., 308200S, 3151‐3162.
[MR04] Machida, H. and Rosenberg, I. G., On centralizers of monoids, Novi Sad Journal of Math‐ematics, Vol. 34, No. 2, 2004,

153-\perp 66.

[MRIO] Machida, H. and Rosenberg, I. G., Endoprimal monoids and witness lemma in clone theory,
Proceedings 40th Inlernational Symposium on Mulliple‐ Valued Logic, IEEE, 2010, 195‐200.

[MRII] Machida, H. and Rosenberg, I. G., Maximal centralizing monoids and their relation tominimal clones, Proceedings 41st International Symposium on Multiple‐ Valued Logic, IEEE,
2011, 153‐159.

[Sza85] Szabó, L., Characterization of clones acting bicentrally and containing a primitive group,Acta. Cybernet., 7, 1985, 137‐ı42.