1 Introduction and preliminaries

Throughout the paper we assume that A is a finite set and \(|A|\geqslant 3.\) Let \(O_A^{(n)}\) denote the set of all n-ary operations on A (so that \(O_A^{(1)}=A^A\)) and let \(O_A:=\bigcup _{n\geqslant 1} O_A^{(n)}\) denote the set of all finitary operations on A. For \(F\subseteq O_A\) let \(F^{(n)}:=F\cap O_A^{(n)}\) be the set of all n-ary operations in F. A set \(C\subseteq O_A\) of finitary operations is a clone of operations on A if it contains all projection maps \({\pi }^n_i:A^n\rightarrow A: (x_1,\ldots ,x_n)\mapsto x_i\) and is closed with respect to composition of functions in the following sense: whenever \(g\in C^{(n)}\) and \(f_1,\ldots ,f_n\in C^{(m)}\) for some positive integers m and n then \(g(f_1,\ldots ,f_n)\in C^{(m)},\) where the composition \(h:=g(f_1,\ldots ,f_n)\) is defined by \(h(x_1,\ldots ,x_m):= g(f_1(x_1,\ldots ,x_m),\ldots ,f_n(x_1,\ldots ,x_m)).\)

Clearly, for any family \((C_i)_{i\in I}\) of clones on A we have that \(\bigcap _{i\in I} C_i\) is a clone, too. Therefore, for any \(F\subseteq O_A\) it makes sense to define \({\text {Clo}}(F)\) to be the smallest clone that contains F.

We say that an n-ary operation f preserves an h-ary relation \(\varrho \) if the following holds:

$$\begin{aligned} \begin{bmatrix} a_{11}\\ a_{21}\\ \vdots \\ a_{h1} \end{bmatrix}, \begin{bmatrix} a_{12}\\ a_{22}\\ \vdots \\ a_{h2} \end{bmatrix}, \ldots , \begin{bmatrix} a_{1n}\\ a_{2n}\\ \vdots \\ a_{hn} \end{bmatrix}\in \varrho {\text { implies }} \begin{bmatrix} \textit{f}(\textit{a}_{11},\textit{a}_{12},\ldots ,\textit{a}_{1\textit{n}})\\ \textit{f}(\textit{a}_{21},\textit{a}_{22},\ldots ,\textit{a}_{2\textit{n}}) \\ \vdots \\ \textit{f}(\textit{a}_{\textit{h}1},\textit{a}_{\textit{h}2},\ldots ,\textit{a}_{\textit{hn}}) \end{bmatrix}\in \varrho . \end{aligned}$$

For a set Q of relations let

$$\begin{aligned} {\text {Pol}}Q :=\{ f\in O_A \mid f\text { preserves every } \varrho \in \textit{Q}\}. \end{aligned}$$

Let \({\text {Pol}}_n Q =({\text {Pol}}Q)\cap O_A^{(n)}.\) For an h-ary relation \(\theta \subseteq A^h\) and a unary operation \(f\in A^A\) it is convenient to write

$$\begin{aligned} f(\theta ):= \{ (f(x_1),\ldots , f(x_h)) \mid (x_1,\ldots ,x_h) \in \theta \}. \end{aligned}$$

Then clearly f preserves \(\theta \) if and only if \(f(\theta )\subseteq \theta .\) It follows that \({\text {Pol}}_1 Q\) is the endomorphism monoid of the relational structure (A, Q). Therefore instead of \({\text {Pol}}_1 Q\) we simply write \({\text {End}}Q.\)

If the underlying set is finite and has at least three elements, then the lattice of clones has cardinality \(2^{{\aleph }_0}.\) However, one can show that the lattice of clones on a finite set has a finite number of coatoms, called maximal clones, and that every clone distinct from \(O_A\) is contained in one of the maximal clones. One of the most influential results in clone theory is the explicit characterization of the maximal clones, obtained by I. G. Rosenberg as the culmination of the work of many mathematicians. It is usually stated in terms of the following six classes of finitary relations on A (the so-called Rosenberg relations).

  1. (R1)

    Bounded partial orders. These are partial orders on A with a least and a greatest element.

  2. (R2)

    Nontrivial equivalence relations. These are equivalence relations on A distinct from \({\Delta }_A:=\{ (x,x) \mid x\in A\}\) and \(A^2.\)

  3. (R3)

    Permutational relations. These are relations of the form \(\{ (x,\pi (x)) \mid x\in A\}\) where \(\pi \) is a fixpoint-free permutation of A with all cycles of the same length p,  where p is a prime.

  4. (R4)

    Affine relations. For a binary operation \(\oplus \) on A let

    $$\begin{aligned} {\lambda }_{\oplus }:=\{ (x,y,u,v) \in A^4 \mid x\oplus y=u\oplus v\}. \end{aligned}$$

    A relation \(\varrho \) is called affine if there is an elementary abelian p-group \((A,\oplus ,\ominus ,0)\) on A such that \(\varrho ={\lambda }_{\oplus }.\) Suppose now that A is an elementary abelian p-group. Then it is well-known that \(f\in {\text {Pol}}\{ {\lambda }_{\oplus }\}\) if and only if

    $$\begin{aligned} f(x_1\oplus y_1,\ldots ,x_n\oplus y_n)=f(x_1,\ldots ,x_n)\oplus f(y_1,\ldots , y_n)\ominus f(0,\ldots ,0) \end{aligned}$$

    for all \(x_i,y_i\in A.\) In case f is unary, this condition becomes

    $$\begin{aligned} f(x\oplus y)=f(x)\oplus f(y)\ominus f(0). \end{aligned}$$
  5. (R5)

    Central relations. All unary relations are central relations. For central relations \(\varrho \) of arity \(h\geqslant 2\) the definition is as follows: \(\varrho \) is said to be totally symmetric if \((x_1,\ldots ,x_h)\in \varrho \) implies \((x_{\pi (1)},\ldots ,x_{\pi (h)})\in \varrho \) for all permutations \(\pi ,\) and it is said to be totally reflexive if \((x_1,\ldots ,x_h)\in \varrho \) whenever there are \(i \ne j\) such that \(x_i=x_j.\) An element \(c\in A\) is central if \((c,x_2,\ldots ,x_h) \in \varrho \) for all \(x_2,\ldots ,x_h\in A.\) Finally, \(\varrho \not = A^h\) is called central if it is totally reflexive, totally symmetric and has a central element. According to this, every central relation \(\varrho \) can be written as \(C_{\varrho }\cup R_{\varrho }\cup T_{\varrho },\) where \(C_{\varrho }\) consists of all the tuples of distinct elements containing at least one central element (the central part), \(R_{\varrho }\) consists of all the tuples \((x_1,\ldots ,x_h)\) such that there are \(i\not = j\) with \(x_i=x_j\) (the reflexive part) and \(T_{\varrho }\) consists of all the tuples \((x_1,\ldots ,x_h)\) such that \(x_1,\ldots ,x_h\) are distinct non-central elements. Let \(Z_\varrho \) denote the set of all central elements of \(\varrho .\)

  6. (R6)

    h-regular relations. Let \(\Theta =\{ {\theta }_1,\ldots ,{\theta }_m\}\) be a family of equivalence relations on the same set A. We say that \(\Theta \) is an h-regular family if every \({\theta }_i\) has precisely h blocks, and additionally, if \(B_i\) is an arbitrary block of \({\theta }_i\) for \(i\in \{ 1,\ldots ,m\},\) then \(\bigcap _{i=1}^m B_i\not =\emptyset .\) An h-ary relation \(\varrho \not = A^h\) is h-regular if \(h\geqslant 3\) and there is an h-regular family \(\Theta \) such that \((x_1,\ldots ,x_h)\in \varrho \) if and only if for all \(\theta \in \Theta \) there are distinct i,  j with \(x_i \theta x_j.\) Clearly, \(\varrho \) is completely determined by its h-regular family \(\Theta .\) Therefore, we will also denote it by \(R_{\Theta }.\) Note that regular relations are totally reflexive and totally symmetric.

Theorem 1.1

(Rosenberg [7]). A clone M of operations on a finite set is maximal if and only if there is a relation \(\varrho \) from one of the classes (R1)–(R6) such that \(M={\text {Pol}}\{\varrho \}.\)

Table 1 A summary of the results
Full size table

Table 1 summarizes all known results about the mutual containment of unary parts of maximal clones over a finite set A with \(|A|\geqslant 3.\) The entries in this table are to be interpreted in the following way:

  • we write − if \({\text {End}}\varrho \not \subseteq {\text {End}}\sigma \) for every pair \((\varrho ,\sigma )\) of distinct relations of the indicated type;

  • we write \(+\) whenever there is a complete characterization of the situation \({\text {End}}\varrho \subseteq {\text {End}}\sigma ;\)

  • we write \(+ ?\) if there is a partial characterization of the situation \({\text {End}}\varrho \subseteq {\text {End}}\sigma .\)

2 Binary operations in maximal clones

The partially ordered set of unary parts of maximal clones ordered by inclusion has a very rich structure [1, 2, 5]. Moreover, the main result of [4] shows that every finite Boolean algebra is order-embeddable into the partially ordered set of unary parts of maximal clones on a sufficiently large finite set. In this section we would like to consider a similar problem and embark on the investigation of the partially ordered set \(\{{\text {Pol}}_2 \varrho \mid \varrho \text { is a Rosenberg relation}\}.\)

This problem is closely related to the notion of the order of a clone. For a finitely generated clone C,  let \({\text {ord}}(C)\) denote the order of C, that is, the least positive integer k such that \({\text {Clo}}(C^{(k)}) = C.\) If C is not finitely generated we set \({\text {ord}}(C) = \infty .\) It is easy to see that if C is a maximal clone with \({\text {ord}}(C) = 2\) and D is another maximal clone then \(C^{(2)} \not \subseteq D^{(2)},\) for otherwise we would have \(C = {\text {Clo}}(C^{(2)}) \subseteq {\text {Clo}}(D^{(2)}) \subseteq D,\) which contradicts the maximality of C.

Proposition 2.1

If \(\varrho \) and \(\sigma \) are distinct Rosenberg relations such that \({\text {Pol}}_2 \varrho \subseteq {\text {Pol}}_2 \sigma \) then both \(\varrho \) and \(\sigma \) have to be central relations of arity at least 2.

Proof

It is a well-known fact (see [6]) that if \(|A| \geqslant 3\) then \({\text {ord}}(C) = 2\) for all maximal clones \(C = {\text {Pol}}\varrho \) where \(\varrho \) belongs to one of the classes (R2),(R3), (R4) and (R6). Therefore, if \({\text {Pol}}_2 \varrho \subseteq {\text {Pol}}_2 \sigma \) for some Rosenberg relations \(\varrho \) and \(\sigma ,\) then \(\varrho \) is a bounded partial order or a central relation.

Step 1. Let \(\varrho \) be a bounded partial order with the least element 0 and the greatest element 1. If \(\sigma \) belongs to one of the classes (R1), (R2),(R3), (R4) or if \(\sigma \) is a unary central relation, then \({\text {End}}\varrho \not \subseteq {\text {End}}\sigma \) (see Table 1), and hence \({\text {Pol}}_2 \varrho \not \subseteq {\text {Pol}}_2 \sigma .\)

Let \(\sigma \) be a central relation of arity \(k \geqslant 2\) and consider the following three binary operations on A:

$$\begin{aligned}{} & {} f(x, y) = {\left\{ \begin{array}{ll} x, &{} \text {if }{} \textit{y} = 1,\\ y, &{} \text {if }{} \textit{x} = 1,\\ 0, &{} \text {otherwise}, \end{array}\right. } \quad g(x, y) = {\left\{ \begin{array}{ll} x, &{} \text {if }{} \textit{y} = 0,\\ y, &{} \text {if }{} \textit{x} = 0,\\ 1, &{} \text {otherwise}, \end{array}\right. }\\{} & {} \quad \text {and}\quad \textit{t}_{\textit{a,b}}(\textit{x, y}) = {\left\{ \begin{array}{ll} 0, &{} \text {if }(\textit{x, y}) \leqslant (\textit{a, b}),\\ \textit{x}, &{} \text {otherwise}. \end{array}\right. } \end{aligned}$$

All three operations are monotonous with respect to \(\varrho \) and \(f(1, x) = f(x, 1) = g(0, x) = g(x, 0) = x.\) If \(1 \in Z_\sigma ,\) take any \((x_1, x_2, \ldots , x_k) \notin \sigma \) and note that

Thus, f does not preserve \(\sigma ,\) and \({\text {Pol}}_2 \varrho \not \subseteq {\text {Pol}}_2 \sigma .\)

If \(0 \in Z_\sigma ,\) take any \((x_1, x_2, \dots , x_k) \notin \sigma \) and note that

Thus, g does not preserve \(\sigma ,\) and \({\text {Pol}}_2 \varrho \not \subseteq {\text {Pol}}_2 \sigma .\)

Finally, assume that \(0 \notin Z_\sigma \) and \(1 \notin Z_\sigma .\) Since \(0 \notin Z_\sigma \) there exist \(x_2,\ldots , x_k \in A\) such that \((0, x_2, \ldots , x_k) \notin \sigma .\) Take any \(c \in Z_\sigma \) and note that \(t_{c,c}(c, c) = 0\) and \(t_{c,c}(x_i, 1) = x_i\) since \(c < 1.\) Therefore,

Thus, \(t_{c,c}\) does not preserve \(\sigma ,\) and \({\text {Pol}}_2 \varrho \not \subseteq {\text {Pol}}_2 \sigma .\)

This completes the proof that if \(\varrho \) is a bounded partial order and \(\sigma \) is a central relation then \({\text {Pol}}_2 \varrho \not \subseteq {\text {Pol}}_2 \sigma .\)

Now, let \(\sigma =R_{\Theta }\) be a regular relation. From [1, Proposition 4.25] we know that if \({\text {End}}\varrho \subseteq {\text {End}}R_\Theta \) where \(\varrho \) is a bounded partial order, then \(\Theta \) has to be a singleton \(\Theta = \{\theta \}.\) Let \(B_1,\) ..., \(B_h\) be the blocks of \(\theta .\) One of the \(B_i\)’s contains 0,  so without loss of generality we can assume that \(0 \in B_1.\) If 1 is not the only element in its block, we can choose \(x_2 \in B_2, \ldots , x_h \in B_h\) such that \(1 \notin \{x_2, \dots , x_h\}.\) But then

so, \({\text {Pol}}_2 \varrho \not \subseteq {\text {Pol}}_2 R_\Theta .\) If 1 is the only element in its block, without loss of generality we can assume \(B_2 = \{1\}.\) Take arbitrary \(x_3 \in B_3, \ldots , x_h \in B_h\) and note that

Therefore, \({\text {Pol}}_2 \varrho \not \subseteq {\text {Pol}}_2 R_\Theta .\) This completes the proof that \(\varrho \) cannot be a bounded partial order if \({\text {Pol}}_2 \varrho \subseteq {\text {Pol}}_2 \sigma .\)

Step 2. Let \(\varrho \) be a central relation. If \(\sigma \) belongs to one of the classes (R1), (R3), (R4) or if \(\sigma \) is a unary central relation, then \({\text {End}}\varrho \not \subseteq {\text {End}}\sigma \) (see Table 1), and hence \({\text {Pol}}_2 \varrho \not \subseteq {\text {Pol}}_2 \sigma .\)

Suppose \(\sigma \) is an equivalence relation. According to [5, Proposition 4.3], from \({\text {End}}\varrho \subseteq {\text {End}}\sigma \) it follows that \({\text {ar}}(\varrho ) \in \{1, 2\},\) \(T_{\varrho }=\emptyset \) and \(A / \sigma = \{Z_\varrho , \{a_2\}, \ldots , \{a_t\}\},\) i.e. \(Z_\varrho \) is the only nontrivial block of \(\sigma .\) Since \(\sigma \) is a nontrivial equivalence relation we have that \(|Z_\varrho | \geqslant 2\) and \(t \geqslant 2.\) Take \(c_1, c_2 \in Z_\varrho \) so that \(c_1 \ne c_2\) and define \(* :A^2 \rightarrow A\) by \(c_1 * y = c_1\) and \(x * y = y\) for \(x \ne c_1.\) Clearly, \(* \in {\text {Pol}}_2 \varrho .\) To see that \(* \notin {\text {Pol}}_2 \sigma ,\) note that \((c_1,c_2) \in \sigma \) and \((a_2,a_2) \in \sigma \) but \((c_1 * a_2,c_2 * a_2) = (c_1,a_2) \notin \sigma .\) Therefore, \({\text {Pol}}_2 \varrho \not \subseteq {\text {Pol}}_2 \sigma .\)

Suppose \(\sigma \) is a regular relation defined by an h-regular family \(\Theta .\) According to [5, Propositions 4.6 and 4.7] from \({\text {End}}\varrho \subseteq {\text {End}}\sigma \) it follows that \(\Theta = \{\theta \},\) \(A / \theta = \{B, \{b_2\}, \dots , \{b_h\}\},\) \(|B| \geqslant 2\) and \(Z_\varrho \subseteq B.\) Define \(* :A^2 \rightarrow A\) by \(x * y = y\) if \(y \in Z_\varrho \) and \(x * y = x\) otherwise. Then clearly \(* \in {\text {Pol}}_2 \varrho .\) To see that \(* \notin {\text {Pol}}_2 \sigma \) take arbitrary \(c \in Z_\varrho \) and note that

If \(\varrho \) is a unary central relation and \(\sigma \) is an at least binary central relation, say of arity k,  then according to [5, Proposition 4.1], \(Z_\sigma = \varrho \) and \(T_{\sigma }=\emptyset .\) Define \(* :A^2 \rightarrow A\) by \(x * y = y\) if \(x \in \varrho \) and \(x * y = x\) otherwise. Clearly, \(* \in {\text {Pol}}_2 \varrho .\) To see that \(* \notin {\text {Pol}}_2 \sigma \) take any \(c \in \varrho = Z_\sigma \) and any \((x_1, x_2, \ldots , x_k) \notin \sigma .\) Then

Therefore, if \({\text {Pol}}_2 \varrho \subseteq {\text {Pol}}_2 \sigma \) then both \(\varrho \) and \(\sigma \) have to be at least binary central relations. \(\square \)

At this point it is clear that the only nontrivial containments among k-ary parts of maximal clones with \(k\geqslant 2\) can occur for central relations of arity at least 2. This case is studied in detail in the next section.

3 Rosenberg clones defined by central relations

To untangle the situation concerning the k-ary parts of Rosenberg clones of central relations we introduce another set of strategies. Let \(\varrho \) be an n-ary relation on A and let \({\bar{a}} = (a_1,\ldots ,a_m) \in A^m.\) Let us define the type of \({\bar{a}}\) with respect to \(\varrho \) as follows:

$$\begin{aligned} {{\text {type}}}_{\varrho } (\bar{a}) = {{\text {type}}}_{\varrho }(a_1,\ldots ,a_m)=({\tau }_1(\bar{a}),{\tau }_2(\bar{a})) \end{aligned}$$

where

$$\begin{aligned} {\tau }_1(\bar{a})&= \{ (i_1,\ldots ,i_n)\mid i_1<\dots<i_n\in \{1,\ldots ,m\}\text { and } (\textit{a}_{\textit{i}_1},\ldots ,\textit{a}_{\textit{i}_\textit{n}})\in \varrho \}, \text { and}\\ {\tau }_2(\bar{a})&= \{ (i,j)\mid i<j\in \{1,\ldots ,m\}, \; \text { and } \textit{a}_\textit{i}=\textit{a}_\textit{j}\}. \end{aligned}$$

For \(\bar{a}_1,\bar{a}_2\in A^m\) define

$$\begin{aligned} {{\text {type}}}_{\varrho } (\bar{a}_1)\cap {{\text {type}}}_{\varrho } (\bar{a}_2):= ({\tau }_1(\bar{a}_1)\cap {\tau }_1(\bar{a}_2) ,{\tau }_2(\bar{a}_1)\cap {\tau }_2(\bar{a}_2)), \end{aligned}$$

and \({{\text {type}}}_{\varrho } (\bar{a})\subseteq {{\text {type}}}_{\varrho } (\bar{b})\) if \({\tau }_i (\bar{a})\subseteq \tau _i(\bar{b})\) for \(i=1,2.\)

Proposition 3.1

Let \(\varrho \) be an n-ary central relation on A and let \(\sigma \) be any m-ary relation on the same set A. Then \({\text {Pol}}_k \varrho \subseteq {\text {Pol}}_k \sigma \) if and only if the following holds for every \(\bar{a}_1,\ldots ,\bar{a}_k\in \sigma \) and every \(\bar{b}\in A^m{:}\)

$$\begin{aligned} {{\text {type}}}_{\varrho } (\bar{a}_1)\cap {{\text {type}}}_{\varrho } (\bar{a}_2)\cap \dots \cap {{\text {type}}}_{\varrho } (\bar{a}_k)\subseteq {{\text {type}}}_{\varrho } (\bar{b})\Rightarrow \bar{b}\in \sigma . \end{aligned}$$

Proof

\((\Leftarrow )\) Assume that for every \({{\bar{a}}}_1,\ldots ,{{\bar{a}}}_k\in \sigma \) and every \(\bar{b}\in A^m\) we have that \( {{\text {type}}}_{\varrho } ({{\bar{a}}}_1)\cap {{\text {type}}}_{\varrho } ({{\bar{a}}}_2)\cap \dots \cap {{\text {type}}}_{\varrho } ({{\bar{a}}}_k)\subseteq {{\text {type}}}_{\varrho } (\bar{b})\Rightarrow \bar{b}\in \sigma .\)

Take \(f\in {\text {Pol}}_k \varrho \) and \({{\bar{a}}}_1,\ldots ,{{\bar{a}}}_k\in \sigma ,\) say,

figure a

We define \(\bar{b}\) in the following way: \(\bar{b}=f({{\bar{a}}}_1,\ldots ,{{\bar{a}}}_k),\) i.e. \(b_i=f(a_i^1,\ldots , a_i^k),\) \(i\in \{ 1,\ldots ,m\}.\) We will show that \(\bar{b}\in \sigma .\) According to the assumption, it suffices to show that

$$\begin{aligned} {{\text {type}}}_{\varrho } ({{\bar{a}}}_1)\cap {{\text {type}}}_{\varrho } ({{\bar{a}}}_2)\cap \dots \cap {{\text {type}}}_{\varrho } ({{\bar{a}}}_k)\subseteq {{\text {type}}}_{\varrho } (\bar{b}) \end{aligned}$$

or, equivalently,

$$\begin{aligned}{} & {} {\tau }_{1} ({{\bar{a}}}_1)\cap {\tau }_{1} ({{\bar{a}}}_2)\cap \dots \cap {\tau }_{1} ({{\bar{a}}}_k)\subseteq {\tau }_{1} (\bar{b})\\{} & {} \text { and } {\tau }_{2} ({{\bar{\textit{a}}}}_1)\cap {\tau }_{2} ({{\bar{\textit{a}}}}_2)\cap \dots \cap {\tau }_{ 2} ({{\bar{\textit{a}}}}_\textit{k})\subseteq {\tau }_{2} (\bar{\textit{b}}). \end{aligned}$$

For the first inclusion take any \((i_1,\ldots ,i_n)\in {\tau }_{1} ({{\bar{a}}}_1)\cap {\tau }_{1} ({{\bar{a}}}_2)\cap \dots \cap {\tau }_{1} ({{\bar{a}}}_k).\) Then \((a_{i_1}^1,\ldots ,a_{i_n}^1),\ldots ,(a_{i_1}^k,\ldots ,a_{i_n}^k)\in \varrho .\) Since \(f\in {\text {Pol}}_k \varrho \) it follows that

$$\begin{aligned} \begin{bmatrix} f(a_{i_1}^1,a_{i_1}^2,\ldots ,a_{i_1}^k)\\ f(a_{i_2}^1,a_{i_2}^2,\ldots ,a_{i_2}^k) \\ \vdots \\ f(a_{i_n}^1,a_{i_n}^2,\ldots ,a_{i_n}^k) \end{bmatrix}\in \varrho , \end{aligned}$$

i.e., \((b_{i_1},b_{i_2},\ldots ,b_{i_n})\in \varrho ,\) so \((i_1,i_2,\ldots ,i_n)\in {\tau }_{1} (\bar{b}).\)

For the second inclusion let \((i,j)\in {\tau }_{2} ({{\bar{a}}}_1)\cap {\tau }_{2} ({{\bar{a}}}_2)\cap \cdots \cap {\tau }_{ 2} ({{\bar{a}}}_k).\) Then \(a_i^l=a_j^l,\) \(l=1,\ldots ,k.\) It follows that \((i,j)\in {\tau }_{2} (\bar{b})\) since

$$\begin{aligned} b_i=f(a_i^1,\ldots ,a_i^k)=f(a_j^1,\ldots ,a_j^k)=b_j. \end{aligned}$$

Putting it all together, \(\bar{b}\in \sigma \) and, therefore, \(f\in {\text {Pol}}_k \sigma .\)

\((\Rightarrow )\) Assume \({\text {Pol}}_k \varrho \subseteq {\text {Pol}}_k \sigma .\) Take \({{\bar{a}}}_1,\ldots ,{{\bar{a}}}_k\in \sigma \) and \(\bar{b}\in A^m,\) say,

figure b

such that

$$\begin{aligned} {{\text {type}}}_{\varrho } ({{\bar{a}}}_1)\cap {{\text {type}}}_{\varrho } ({{\bar{a}}}_2)\cap \dots \cap {{\text {type}}}_{\varrho } ({{\bar{a}}}_k)\subseteq {{\text {type}}}_{\varrho } (\bar{b}). \end{aligned}$$

We shall now construct an \(f\in {\text {Pol}}_k \sigma \) such that \(f({{\bar{a}}}_1,\ldots ,{{\bar{a}}}_k)=\bar{b},\) in the following way:

$$\begin{aligned} f(x_1,\ldots ,x_k )= {\left\{ \begin{array}{ll} b_i, &{}\text {if } (\textit{x}_1,\ldots ,\textit{x}_\textit{k})=(\textit{a}_\textit{i}^1,\ldots ,\textit{a}_\textit{i}^\textit{k}), \textit{i}=1,\ldots ,\textit{m}\\ c, &{} \text {otherwise}, \end{array}\right. } \end{aligned}$$

where \(c\in Z_{\varrho }.\) Clearly, \(f({{\bar{a}}}_1,\ldots ,{{\bar{a}}}_k)=\bar{b},\) so it is left to show that f is well defined and that \(f\in {\text {Pol}}_k \varrho \) (and, therefore, \(f\in {\text {Pol}}_k \sigma \)).

To see that f is well defined, suppose that \((a_i^1,\ldots ,a_i^k)=(a_j^1,\ldots ,a_j^k)\) for some \(i\not =j,\) then \((i,j)\in {\tau }_{2} ({{\bar{a}}}_1)\cap {\tau }_{2} ({{\bar{a}}}_2)\cap \dots \cap {\tau }_{ 2} ({{\bar{a}}}_k)\subseteq {\tau }_{2} (\bar{b}),\) so \(b_i=b_j,\) and f is indeed well defined.

To see that \(f\in {\text {Pol}}_k \varrho \) let \({{\bar{x}}}_1,\ldots ,{{\bar{x}}}_k\in \varrho ,\) where \(\bar{x}_i=(x_1^i,\ldots ,x_n^i),\) \(i=1,\ldots ,k.\) Then

$$\begin{aligned} f({{\bar{x}}}_1,\ldots ,{{\bar{x}}}_k)=\begin{bmatrix} f(x_{1}^1,x_{1}^2,\ldots ,x_{1}^k)\\ f(x_{2}^1,x_{2}^2,\ldots ,x_{2}^k) \\ \vdots \\ f(x_{n}^1,x_{n}^2,\ldots ,x_{n}^k) \end{bmatrix}. \end{aligned}$$

If there is \((x_i^1,\ldots ,x_i^k)\not =(a_j^1,\ldots ,a_j^k),\) for some \(j\in \{1,\ldots ,m\},\) then we have that \(f(x_i^1,\ldots ,x_i^k)=c,\) so \(f({{\bar{x}}}_1,\ldots ,{{\bar{x}}}_k)\) is a tuple that contains a central element, and, therefore, it is in \(\varrho .\)

Otherwise, for each \(i\in \{1,\ldots ,n\}\) \((x_i^1,\ldots ,x_i^k)=(a_{j_i}^1,\ldots ,a_{j_i}^k),\) for some \(j_i\in \{1,\ldots ,m\}.\)

If \((x_{i_1}^1,\ldots ,x_{i_1}^k)=(x_{i_2}^1,\ldots ,x_{i_2}^k)=(a_j^1,\ldots ,a_j^n),\) where \(i_1,i_2\in \{1,\ldots ,n\}\) and \(i_1\not =i_2,\) then \(f({{\bar{x}}}_1,\ldots ,{{\bar{x}}}_k)\) is a reflexive tuple, so it belongs to \(\varrho .\)

If that fails to be true then

$$\begin{aligned} f({{\bar{x}}}_1,\ldots ,{{\bar{x}}}_k)= \begin{bmatrix} f(a_{j_1}^1,a_{j_1}^2,\ldots ,a_{j_1}^k)\\ f(a_{j_2}^1,a_{j_2}^2,\ldots ,a_{j_2}^k) \\ \vdots \\ f(a_{j_n}^1,a_{j_n}^2,\ldots ,a_{j_n}^k) \end{bmatrix} = \begin{bmatrix} b_{j_1}\\ b_{j_2}\\ \vdots \\ b_{j_n}\end{bmatrix}. \end{aligned}$$

Since \(\bar{x}_i=(a_{j_1}^i,\ldots ,a_{j_n}^i)\) and \(\bar{x}_i\in \varrho ,\) for \(1\leqslant i \leqslant n,\) it follows that

$$\begin{aligned} (j_1,\ldots ,j_n)\in {\tau }_{1} ({{\bar{a}}}_1)\cap {\tau }_{1} ({{\bar{a}}}_2)\cap \cdots \cap {\tau }_{1} ({{\bar{a}}}_k), \end{aligned}$$

so \((j_1,\ldots ,j_n)\in {\tau }_{1} (\bar{b}),\) so \((b_{j_1},\ldots ,b_{j_n})\in \varrho .\)

Therefore, \(f\in {\text {Pol}}_k \varrho \subseteq {\text {Pol}}_k \sigma ,\) so \(\bar{b}\in \sigma .\)    \(\square \)

Lemma 3.2

Let \(\varrho \) and \(\sigma \) be two distinct central relations. If \({\text {Pol}}_k \varrho \subseteq {\text {Pol}}_k \sigma \) and \(T_\varrho =\emptyset ,\) then \({\text {ar}}(\varrho ) <{\text {ar}}(\sigma ),\) \(Z_{\varrho }=Z_{\sigma }\) and \(T_{\sigma }=\emptyset .\)

Proof

If \({\text {Pol}}_k \varrho \subseteq {\text {Pol}}_k \sigma ,\) then, clearly, \({{\text {End}}} \varrho \subseteq {{\text {End}}} \sigma \) and the claim follows from the corresponding lemma for endomorphisms, see [5, Proposition 4.1].\(\square \)

Theorem 3.3

Let \(\varrho \) and \(\sigma \) be two distinct central relations on A such that \(T_\varrho =\emptyset .\) Then \({\text {Pol}}_k \varrho \subseteq {\text {Pol}}_k \sigma \) for \(k\geqslant 2\) if and only if \(2k\leqslant {\text {ar}}(\varrho )<{\text {ar}}(\sigma )\leqslant |A|-1,\) \(Z_\varrho =Z_\sigma ,\) and \(T_\sigma =\emptyset .\)

Proof

Let \(\varrho \subseteq A^n\) and \(\sigma \subseteq A^m\) be distinct central relations.

\((\Leftarrow )\) Assume that \(Z_\varrho = Z_\sigma ,\) and \(T_\varrho =T_\sigma = \emptyset ,\) \(2k\leqslant n<m.\) We will show that \({\text {Pol}}_k \varrho \subseteq {\text {Pol}}_k \sigma \) using the criterion from Proposition 3.1.

Let \(\bar{a}_1,\bar{a}_2,\ldots , \bar{a}_k\in \sigma ,\) say,

figure c

Let \(\bar{b}\in A^m\) such that \({{\text {type}}}_{\varrho } (\bar{a}_1)\cap {{\text {type}}}_{\varrho } (\bar{a}_2)\cap \cdots \cap {{\text {type}}}_{\varrho } (\bar{a}_k)\subseteq {{\text {type}}}_{\varrho } (\bar{b}).\) According to Proposition 3.1 we have to show that \(\bar{b}\in \sigma .\) Note that if \(\tau _2(\bar{b})\ne \emptyset ,\) then \(\bar{b}\in \sigma ,\) and we are done. So suppose that \(\tau _2(\bar{b})=\emptyset .\) Let \(J:=\{j\in \{1,\ldots ,k\}\mid \bar{a}_j\in C_\sigma \},\) \(L:=\{l\in \{1,\ldots ,k\}\mid \bar{a}_l\in R_\sigma \}.\) For each \(j\in J,\) choose some index \(r_j\in \{1,\ldots ,m\},\) such that \(a_{r_j}^j\in Z_\sigma .\) Furthermore, for each \(l\in L\) choose indices \(t_l<s_l\in \{1,\ldots ,m\},\) such that \(a_{t_l}^l=a_{s_l}^l.\) Let \(P:=\{r_j\mid j\in J\}\cup \{t_l\mid l\in L\}\cup \{s_l\mid l\in L\}.\) Note that \(|P|\leqslant 2k.\) Hence, we can find indices \(1\leqslant i_1<i_2<\cdots <i_n\leqslant m\) such that \(P\subseteq \{i_1,\ldots ,i_n\}.\) It follows that \((i_1,\ldots ,i_n)\in {\tau }_{1} (\bar{a}_1)\cap {\tau }_{1} (\bar{a}_2)\cap \cdots \cap {\tau }_{1} (\bar{a}_k)\subseteq {\tau }_{1} (\bar{b}),\) so \((b_{i_1},\ldots ,b_{i_n})\in \varrho .\) Since \(T_{\varrho }=\emptyset ,\) it follows that \((b_{i_1},\ldots ,b_{i_n})\in C_\varrho .\) So for some \(j\in \{1,\ldots ,n\}\) we have \(b_{i_j}\in Z_\varrho =Z_\sigma .\) But this implies \(\bar{b}\in C_\sigma \subseteq \sigma .\)

\((\Rightarrow )\) By Lemma 3.2, we obtain immediately that \(T_\sigma =\emptyset ,\) \(Z_{\varrho }=Z_{\sigma }\) and \(n<m\leqslant |A|-1,\) so it is left to show that \(2k\leqslant n.\) Suppose that \(n<2k.\) We will show that then there exist \(\bar{a}_1,\ldots ,\bar{a}_k\in \sigma \) such that \({{\text {type}}}_{\varrho } (\bar{a}_1)\cap {{\text {type}}}_{\varrho } (\bar{a}_2)\cap \cdots \cap {{\text {type}}}_{\varrho } (\bar{a}_k)=(\emptyset ,\emptyset ).\) If we succeed in this endeavor, then Proposition 3.1 implies \(\sigma =A^m,\) a contradiction.

It remains to construct \(\bar{a}_1,\ldots ,\bar{a}_k.\) Let \(\bar{b}\in A^m\) be such that \({\text {type}}_{\varrho } (\bar{b})=(\emptyset ,\emptyset ).\) As \(T_\varrho =\emptyset \) and \(Z_\varrho =Z_\sigma ,\) any element from \(A^m\setminus \sigma \) will do.

The m-tuples \(\bar{a}_1,\bar{a}_2,\ldots ,\bar{a}_{\lfloor \frac{n}{2}\rfloor },\bar{a}_{\lfloor \frac{n}{2}\rfloor +1}\) are constructed using elements from \(\{b_1,\ldots ,b_m\}\) as entries. In case that n is odd or \(m> n+1,\) we define

figure d

where all other entries are distinct and from the set \(\{b_1,\ldots ,b_m\}\setminus \{b_i\}.\) Otherwise, if n is even and \(m=n+1,\) then, for all \(i\in \{1,\ldots ,\frac{n}{2}\}\) we define \(\bar{a}_i\) as above in (\(*\)). Moreover, we define

$$\begin{aligned} \bar{a}_{\frac{n}{2}+1}:=(b_1,\ldots ,b_{m-1},c), \end{aligned}$$

where \(c\in Z_{\sigma }(=Z_{\varrho }).\) Note that since \(n<2k,\) it follows that \(\lfloor \frac{n}{2}\rfloor +1\leqslant k.\) If \(\lfloor \frac{n}{2}\rfloor +1<k\) the remaining tuples \(\bar{a}_i,\) for \(\lfloor \frac{n}{2}\rfloor +2\leqslant i\leqslant k\) we choose arbitrarily.

Observe that then

$$\begin{aligned} \bigcap _{i=1}^{\lfloor \frac{n}{2}\rfloor +1} {{\text {type}}}_{\varrho } (\bar{a}_i)\supseteq \bigcap _{i=1}^k {{\text {type}}}_{\varrho } (\bar{a}_i). \end{aligned}$$

Let us compute \(\bigcap _{i=1}^{\lfloor \frac{n}{2}\rfloor +1} {{\text {type}}}_{\varrho } (\bar{a}_i).\)

It is clear that

$$\begin{aligned} \bigcap _{i=1}^{\lfloor \frac{n}{2}\rfloor +1} {\tau }_{2} (\bar{a}_i)=\emptyset . \end{aligned}$$

We will show that the same holds for \(\bigcap _{i=1}^{\lfloor \frac{n}{2}\rfloor +1} {\tau }_{1} (\bar{a}_i).\)

Let us first treat the case when n is odd or \(m> n+1.\) Suppose \((j_1,\ldots ,j_n)\in \bigcap _{i=1}^{\lfloor \frac{n}{2}\rfloor +1} {\tau }_{1} (\bar{a}_i).\) Then since \((j_1,\ldots ,j_n)\in \tau _1(\bar{a}_i),\) for each \(i\in \{1,\ldots ,\lfloor \frac{n}{2}\rfloor +1\}\) we have that \(\{2i-1,2i\}\subseteq \{j_1,\ldots ,j_n\}.\) It follows that \(|\{j_1,\ldots ,j_n\}|\geqslant 2\cdot (\lfloor \frac{n}{2}\rfloor +1)>n,\) a contradiction.

Hence,

figure e

In case that n is even and \(m=n+1,\) we argue as follows:

Note that every tuple from \(\tau _1(\bar{a}_{\frac{n}{2}+1})\) contains m as an entry. Suppose that \(\bigcap _{i=1}^{\frac{n}{2} +1} {\tau }_{1} (\bar{a}_i)\ne \emptyset .\) Then it contains a tuple \((i_1,\ldots ,i_{n-1},m),\) where \(i_1<\cdots<i_{n-1}<m.\) Since every tuple from \(\tau _1(\bar{a}_i),\) \(i=1,\ldots ,\frac{n}{2}\) has to contain entries \(2i-1\) and 2i,  it follows that \(\{1,\ldots ,n\}=\bigcup _{i=1}^{\frac{n}{2}}\{2i-1,2i\}\subseteq \{i_1,\ldots ,i_{n-1}\}\)—a contradiction. Hence, (\(**\)) holds in this case, too.

Altogether we proved

$$\begin{aligned} \bigcap _{i=1}^{k} {{\text {type}}}_{\varrho } (\bar{a}_i)=(\emptyset ,\emptyset ). \end{aligned}$$

It follows that \(\sigma =A^m,\) which is a contradiction. \(\square \)

Corollary 3.4

For each \(k\geqslant 2\) the height of the poset of k-ary parts of maximal clones on a set A with \(|A| \geqslant 2k+1\) is at least \(|A| - 2k.\)

Proof

Fix a \(c \in A\) and consider a sequence of central relations \(\varrho _i,\) \(i \in \{0, \ldots , |A| - 2k - 1\}\) such that \({\text {ar}}(\varrho _i) = 2k + i,\) \(Z_{\varrho _i} = \{c\}\) and \(T_{\varrho _i}=\emptyset .\) Then, by Theorem 3.3 we have that

$$\begin{aligned} {\text {Pol}}_k \varrho _0 \subseteq {\text {Pol}}_k \varrho _1 \subset \cdots \subset {\text {Pol}}_k \varrho _{|A|-2k-1}. \end{aligned}$$

This concludes the proof. \(\square \)