domain: math info

text:
Miguel Couceiro

AND Erkko Lehtonen
email: erkko.lehtonen@uni.lu

Karsten Sch Ölzel
email: karsten.schoelzel@uni.lu

A COMPLETE CLASSIFICATION OF EQUATIONAL CLASSES OF THRESHOLD FUNCTIONS INCLUDED IN CLONES

The class of threshold functions is known to be characterizable by functional equations or, equivalently, by pairs of relations, which are called relational constraints. It was shown by Hellerstein that this class cannot be characterized by a finite number of such objects. In this paper, we investigate classes of threshold functions which arise as intersections of the class of all threshold functions with clones of Boolean functions, and provide a complete classification of such intersections in respect to whether they have finite characterizations. Moreover, we provide a characterizing set of relational constraints for each class of threshold functions arising in this way.

Introduction and preliminaries

1.1. Introduction. Two approaches to characterize properties of Boolean functions have been considered recently: one in terms of functional equations [START_REF] Ekin | Equational characterizations of Boolean function classes[END_REF], another in terms of relational constraints [START_REF] Pippenger | Galois theory for minors of finite functions[END_REF]. As it turns out, these two approaches have the same expressive power in the sense that they characterize the same properties (classes) of Boolean functions, which can be described as initial segments of the so-called "minor" relation between functions: for two functions f and g of several variables, f is said to be a minor of g if f can be obtained from g by identifying variables, permuting variables, or adding inessential variables (see Subsection 1.3). Furthermore, a class is characterizable by a finite number of functional equations if and only if it is characterizable by a finite number of relational constraints (see, e.g., [START_REF] Couceiro | On closed sets of relational constraints and classes of functions closed under variable substitution[END_REF][START_REF] Pippenger | Galois theory for minors of finite functions[END_REF]). For the sake of simplifying the presentation of constructions and proofs, we will focus on the approach by relational constraints.

Several properties of functions can be charaterized by relational constraints (or, equivalently, by functional equations. In fact, uncountably many properties are expressible by such objects, even in the simplest interesting case of functions of several variables, i.e., the Boolean functions (see [START_REF] Couceiro | On a quasi-ordering on Boolean functions[END_REF][START_REF] Pippenger | Galois theory for minors of finite functions[END_REF]). Classical examples of such properties include idempotency, monotonicity and linearity. More contemporary examples include submodularity, supermodularity and the combination of the two, i.e., modularity (see, e.g., [START_REF] Couceiro | Discrete integrals based on comonotonic modularity[END_REF][START_REF] Lovász | Submodular functions and convexity[END_REF][START_REF] Singer | Extensions of functions of 0-1 variables and applications to combinatorial optimization[END_REF][START_REF] Topkis | Minimizing a submodular function on a lattice[END_REF]).

Another noteworthy example is thresholdness that is the property of those Boolean functions whose true points can be separated from the false points by a hyperplane when considered as elements of the n-dimensional real space R n . Threshold functions have been widely studied in the literature on Boolean functions, switching theory, system reliability theory, game theory, etc.; for background see, e.g., [START_REF] Isbell | A class of majority games[END_REF][START_REF] Muroga | Threshold Logic and Its Applications[END_REF][START_REF] Peleg | A theory of coalition formation in committees[END_REF][START_REF] Peleg | Coalition formation in simple games with dominant players[END_REF][START_REF] Taylor | Simple games and magic squares[END_REF][START_REF] Winder | Threshold Logic[END_REF].

Despite being a property expressible by relational constraints, thresholdness cannot be captured by a finite set of relational constraints (see Hellerstein [START_REF] Hellerstein | On generalized constraints and certificates[END_REF]). However, by imposing additional conditions such as linearity or preservation of componentwise conjunctions or disjunctions of tuples, the resulting classes of threshold functions may become characterizable by a finite number of relational constraints. In fact, these examples can be obtained from the class of threshold functions by intersecting it with certain clones, namely, those of linear functions, conjunctions and disjunctions, respectively. (Recall that a clone is a class of functions that contains all projections and is closed under functional composition.) Another noteworthy and well-known example of such an intersection is the class of "majority games", which results as the intersection with the clone of self-dual monotone functions. The natural question is then: Is the class of majority games characterizable by a finite number of relational constraints?

In this paper we answer negatively to this question. In fact, we will determine, for each clone of Boolean functions, whether its intersection with the class of threshold functions is finitely characterizable by relational constraints. Moreover, we provide finite or infinite characterizing sets of relational constraints accordingly.

The paper is organized as follows. In the remainder of this section, we recall basic notions and results that will be needed throughout the paper. The main results are presented in Section 2, in particular, the classification of all intersections C ∩ T , where C is a clone and T is the class of all threshold functions, as well as the corresponding characterizing set of relational constraints. For the reader's convenience, the constructions needed for the main results will be left for Section 3. One of the main tools in our proof is Taylor and Zwicker's [START_REF] Taylor | Simple games and magic squares[END_REF] theorem on the existence of a k-asummable function that is not (k + 1)-asummable. In Section 4, we slightly refine Taylor and Zwicker's result and show how the classes of functions characterizable by the relational constraints that arise in our current work are related to each other. Appendix A provides a list of the clones of Boolean functions and relations characterizing them.

(i ∈ [n]) e (n) i : B n → B, (a 1 , . . . , a n ) → a i ; • negation • : B → B, 0 = 1, 1 = 0; • conjunction ∧ : B 2 → B, x ∧ y = 1 if and only if x = y = 1; • disjunction ∨ : B 2 → B, x ∨ y = 0 if and only if x = y = 0; • modulo-2 addition ⊕ : B 2 → B, x ⊕ y = (x + y) mod 2.
The set of all Boolean functions is denoted by Ω and the set of all projections is denoted by I c .

The preimage f -1 (1) of 1 under f is referred to as the set of true points, while f -1 (0) is referred to as the set of false points.

The i-th variable of a Boolean function f : B n → B is said to be essential in f , or that f depends on x i , if there are a 1 , . . . , a i-1 , a i+1 , . . . , a n ∈ B such that

f (a 1 , . . . , a i-1 , 0, a i+1 , . . . , a n ) = f (a 1 , . . . , a i-1 , 1, a i+1 , . . . , a n ).
The dual of a Boolean function f :

B n → B is the function f d : B n → B given by f d (x 1 , . . . , x n ) = f (x 1 , . . . , x n ). A function f is self-dual if f = f d . If f : B n → B and g 1 , . . . , g n : B m → B, then the composition of f with g 1 , . . . , g n is the function f (g 1 , . . . , g n ) : B m → B given by f (g 1 , . . . , g n )(a) = f (g 1 (a), . . . , g n (a))
for all a ∈ B m . A clone of Boolean functions is a subset C of the set Ω of all Boolean functions that satisfies the following two conditions:

• I c ⊆ C, i.e., C contains all projections,

• if f : B n → B, g 1 , . . . , g n : B m → B and f, g 1 , . . . , g n ∈ C, then f (g 1 , . . . , g n ) ∈ C, i.e., C is closed under composition.
The clones of Boolean functions were completely described by Post [START_REF] Post | The Two-Valued Iterative Systems of Mathematical Logic[END_REF], and they are often referred to as Post's classes. We provide a list of all clones of Boolean functions in Appendix A.

1.3. Minors and relational constraints. We will denote tuples in B m by boldface letters and their entries with corresponding italic letters, e.g., a = (a 1 , . . . , a m ). Tuples a ∈ B m may be viewed as mappings a : [m] → B, i → a i . With this convention, given a map σ : [n] → [m], we can write the tuple (a σ(1) , . . . , a σ(n) ) as a • σ, or simply aσ.

A function f :

B m → B is a minor of another function g : B n → B if there exists a map σ : [n] → [m] such that f (a) = g(aσ)
for all a ∈ B m ; in this case we write f ≤ g. Functions f and g are equivalent, denoted f ≡ g, if f ≤ g and g ≤ f . In other words, f is a minor of g if f can be obtained from g by permutation of arguments, addition and deletion of inessential arguments and identification of arguments. Functions f and g are equivalent if each one can be obtained from the other by permutation of arguments and addition and deletion of inessential arguments.

The minor relation ≤ is a quasi-order (i.e., a reflexive and transitive relation) on the set of all Boolean functions, and the relation ≡ is indeed an equivalence relation. For further background see, e.g., [START_REF] Couceiro | On the effect of variable identification on the essential arity of functions on finite sets[END_REF][START_REF] Couceiro | Generalizations of Świerczkowski's lemma and the arity gap of finite functions[END_REF][START_REF] Couceiro | On a quasi-ordering on Boolean functions[END_REF][START_REF] Ekin | Equational characterizations of Boolean function classes[END_REF][START_REF] Pippenger | Galois theory for minors of finite functions[END_REF] In what follows, we shall consider minors of the following special form. Let n ≥ 2, and let f : B n → B. For any two-element subset I of [n], we define the function

f I : B n-1 → B by the rule f I (a) = f (aδ I ) for all a ∈ B n-1 , where δ I : [n] → [n -1]
is given by the rule [START_REF] Bioch | Generating and approximating nondominated coteries[END_REF] δ

I (i) =      i, if i < max I, min I, if i = max I, i -1, if i > max I.
In other words, if I = {i, j} with i < j, then f I (a 1 , . . . , a n-1 ) = f (a 1 , . . . , a j-1 , a i , a j , . . . , a n-1 ).

Note that a i occurs twice on the right side of the above equality: both at the i-th and at the j-th position. The function f I will be referred to as an identification minor of f . It was shown by Pippenger [25] that the classes of functions closed under taking minors are characterizable by so-called relational constraints. We will briefly survey some results which we will use hereinafter. An m-ary relational constraint is a couple (R, S) of m-ary relations R (the antecedent ) and S (the consequent ) on B (i.e., R, S ⊆ B m ). We denote the antecedent and the consequent of a relational constraint Q by R(Q) and S(Q), respectively. If both R(Q) and S(Q) equal the binary equality relation, then Q is called the binary equality constraint. Furthermore, we refer to constraints with empty antecedent and empty consequent as empty constraints, and to constraints where the antecedent and consequent are the full relation B m , for some m ≥ 1, as full constraints. The set of all relational constraints is denoted by Θ.

A function f : B n → B preserves an m-ary relational constraint (R, S), denoted f ⊲ (R, S), if for every a 1 , . . . , a n ∈ R, we have f (a 1 , . . . , a n ) ∈ S. (Regarding tuples a i as unary maps, f (a 1 , . . . , a n ) denotes the m-tuple whose i-th entry is f (a 1 , . . . , a n )(i) = f (a 1 i , . . . , a n i ).) The preservation relation gives rise to a Galois connection between functions and relational constraints that we now briefly describe; for further background, see [START_REF] Couceiro | On Galois connections between external functions and relational constraints: arity restrictions and operator decompositions[END_REF][START_REF] Couceiro | On a quasi-ordering on Boolean functions[END_REF][START_REF] Pippenger | Galois theory for minors of finite functions[END_REF]. Define cPol: P(Θ) → P(Ω), cInv : P(Ω) → P(Θ) by

cPol(Q) = {f ∈ Ω : f ⊲ Q for every Q ∈ Q}, cInv(F ) = {Q ∈ Θ : f ⊲ Q for every f ∈ F }.
We say that a set F of functions is characterized by a set Q of relational constraints if F = cPol(Q). Dually, Q is characterized by F if Q = cInv(F ). In other words, sets of functions characterizable by relational constraints are exactly the fixed points of cPol • cInv, and, dually, sets of relational constraints characterizable by functions are exactly the fixed points of cInv • cPol.

Remark 1.1. Preservation of a relational constraint generalizes the notion of preservation of a relation, as in the classical Pol-Inv theory of clones and relations, which establishes that the clones on finite sets are exactly the classes of functions that are characterized by relations (see [START_REF] Bodnarčuk | Galois theory for Post algebras, I, II[END_REF][START_REF] Geiger | Closed systems of functions and predicates[END_REF]). In this framework, a function f preserves a relation R if and only if f preserves the relational constraint (R, R). Hence, clones are exactly the classes that are characterized by relational constraints of the form (R, R) for some relation R.

The following result reassembles various descriptions of the Galois closed sets of functions, which can be found in [START_REF] Couceiro | On a quasi-ordering on Boolean functions[END_REF][START_REF] Ekin | Equational characterizations of Boolean function classes[END_REF][START_REF] Pippenger | Galois theory for minors of finite functions[END_REF].

Theorem 1.2. Let F be a set of functions. The following are equivalent.

(i) F is closed under taking minors. (ii) F is characterizable by relational constraints. (iii) F is of the form forbid(A) := {f ∈ Ω : g f for all g ∈ A} for some antichain A with respect to the minor relation ≤.

Remark 1.3. It follows from the equivalence of (i) and (ii) in Theorem 1.2 that the union and the intersection of classes that are characterizable by relational constraints are characterizable by relational constraints.

Remark 1.4. Note that the antichain A in item (iii) of Theorem 1.2 is unique up to equivalence. In fact, A can be chosen among the minimal elements of Ω \ F ; the elements of A are called minimal forbidden minors for F . As we will see, there are classes of functions that, even though characterizable by relational constraints, are not characterized by any finite set of relational constraints. A set of functions is finitely characterizable if it is characterized by a finite set of relational constraints.

The following theorem is a refinement of Theorem 1.2 and provides a description for finitely characterizable classes. Theorem 1.5 ([9, 11]). Let F be a set of functions. The following are equivalent.

(i) F is finitely characterizable. (ii) F is of the form forbid(A) for some finite antichain A with respect to the minor relation ≤.

The Galois closed sets of relational constraints were likewise described by Pippenger [START_REF] Pippenger | Galois theory for minors of finite functions[END_REF]; this description was extended to arbitrary, possibly infinite, underlying sets in [START_REF] Couceiro | On closed sets of relational constraints and classes of functions closed under variable substitution[END_REF]. We shall briefly survey Pippenger's description of the Galois closed sets of constraints.

An m-ary relational constraint (R, S) is a simple minor of an (m + p)-ary relational constraint (R ′ , S ′ ) if there is h : {1, . . . , n} → {1, . . . , m + p} such that

R    x 1 . . . x m    ⇐⇒ ∃x m+1 . . . ∃x m+p R ′    x h(1)
. . .

x h(n)    and S    x 1 . . . x m    ⇐⇒ ∃x m+1 . . . ∃x m+p S ′    x h(1)
. . .

x h(n)    .
Note that simple minors subsume the notions of permutation, diagonalization and projection of arguments; for background see [START_REF] Couceiro | On closed sets of relational constraints and classes of functions closed under variable substitution[END_REF][START_REF] Pippenger | Galois theory for minors of finite functions[END_REF].

A constraint (R, S) is obtained from a constraint (R ′ , S) by restricting the antecedent if R ⊆ R ′ . Likewise, (R, S) is obtained from a constraint (R, S ′ ) by extending the consequent if S ⊇ S ′ . A constraint (R, S ∩ S ′ ) is said to be obtained from (R, S) and (R, S ′ ) by intersecting consequents.

A set Q of relational constraints is said to be minor-closed if it contains the binary equality constraint, the unary empty constraint, and it is closed under taking simple minors, restricting antecedents, and extending and intersecting consequents.

We can now state Pippenger's [START_REF] Pippenger | Galois theory for minors of finite functions[END_REF] description of the Galois closed sets of relational constraints.

Theorem 1.6. Let Q be a set of relational constraints. The following are equivalent.

(i) Q is characterizable by some set of functions.

(ii) Q is minor-closed.

The following lemma provides a noteworthy tool for showing that certain classes of threshold functions are not finitely characterizable.

Lemma 1.7. Let C and C i for all i ≥ 1 be classes of functions that are closed under taking minors, such that C = i≥1 C i , and

C i+1 ⊆ C i for all i ≥ 1. If C is finitely characterizable by constraints, then there exists ℓ ∈ N such that C j = C ℓ for all j ≥ ℓ. Proof. By Theorem 1.2, each minor-closed class C i is characterized by some set Q i of relational constraints, i.e., C i = cPol Q i for all i ≥ 1.
Assume that C is finitely characterizable. Then there is some finite set P of constraints with C = cPol P, and thus cInv C = cInv cPol P. Since

C = i≥1 cPol Q i = cPol i≥1 Q i
we can construct each P ∈ P from the constraints in i≥1 Q i . Since the constraints are finite, all such constructions are finite. In particular, only a finite number of constraints from i≥1 Q i are used for each P ∈ P. Since P is finite, this implies that only a finite number of constraints are needed to construct all P ∈ P. Therefore

C = cPol P ⊇ cPol l i=1 Q i = l i=1 cPol Q i = cPol Q l = C l
holds for some l ∈ N. Now this implies that for any j ≥ l,

C ⊆ C j ⊆ C l ⊆ C
and consequently C = C j = C l for all j ≥ l.

Main results: classification and characterizations of Galois

closed sets of threshold functions 2.1. Motivation. A threshold function is a Boolean function f : B n → B such that there exist weights w 1 , . . . , w n ∈ R and a threshold t ∈ R fulfilling

f (x 1 , . . . , x n ) = 1 ⇐⇒ n i=1 w i x i ≥ t.
Another, equivalent, definition is the following. An n-ary Boolean function f is called a threshold function if there is a hyperplane in R n strictly separating the true points of f from the false points of f , considered as elements of R n . The set of all threshold functions is denoted by T . The class of threshold functions has remarkable invariance properties. For instance, it is closed under taking negations and duals (see Lemma 3.15). Moreover, the class of threshold functions is also closed under taking minors of its members; hence it is characterizable by relational constraints by Theorem 1.2. However, no finite set of relational constraints suffices.

Theorem 2.1 (Hellerstein [START_REF] Hellerstein | On generalized constraints and certificates[END_REF]). The class of threshold functions is not finitely characterizable.

Imposing some additional conditions on threshold functions, we may obtain proper subclasses of T that are finitely characterizable. Easy examples arise from the intersections of T with the clones L, Λ, V (see Appendix A). However, as we have seen, other intersections C ∩ T may fail to be finitely characterizable, e.g., for

C = Ω.
This fact gives rise to the following problem.

Problem. Which clones C of Boolean functions have the property that C ∩ T is finitely characterizable?

In the following subsection we present a solution to this problem.

2.2.

Classification and characterizations of intersections of the class of threshold functions with clones. We start by observing that

L ∩ T = Ω(1), Λ ⊆ T, V ⊆ T,
from which it follows that the intersection C ∩T is a clone for any clone C contained in one of L, V and Λ. Hence, the characterization of C ∩ T for any such clone C is given by the relational constraint (R, R), where R is the relation characterizing

C ∩ T given in Appendix A.
We proceed to characterizing the intersections C ∩ T for the remaining clones C; as we will see, none of these is finitely characterizable. A characterization of the class T of all threshold functions (i.e., for C = Ω) is easily obtained with the help of the notion of asummability.

For k ≥ 2, a Boolean function f : B n → B is k-asummable if for any m ∈ {2, . . . , k} and for all a 1 , . . . ,

a m ∈ f -1 (0) and b 1 , . . . , b m ∈ f -1 (1), it holds that a 1 + • • • + a m = b 1 + • • • + b m .
(Addition here is standard vector addition in R n .) A function is asummable if it is k-asummable for all k ≥ 2. It is well known that asummability characterizes threshold functions; see [START_REF] Chow | Boolean functions realizable with single threshold devices[END_REF][START_REF] Elgot | Truth functions realizable by single threshold organs[END_REF][START_REF] Muroga | Threshold Logic and Its Applications[END_REF].

Theorem 2.2. A Boolean function is threshold if and only if it is asummable.

Define for n ≥ 1, the 2n-ary relational constraint B n as

R(B n ) := {(x 1 , . . . , x 2n ) ∈ B 2n : n i=1 x i = 2n i=n+1 x i } S(B n ) := B 2n \ {(0, . . . , 0 n , 1, . . . , 1 n ), (1, . . . , 1 n , 0, . . . , 0 n )}.
Note that in the definition of R(B n ) we employ the usual addition of real numbers. Denoting by w(a) the Hamming weight of a tuple a ∈ B n (i.e., the number of nonzero entries in a), we can equivalently define

R(B n ) as {(x 1 , . . . , x 2n ) ∈ B 2n : w(x 1 , . . . , x n ) = w(x n+1 , . . . , x 2n )}. Lemma 2.3. Let f : B n → B and ℓ ≥ 2. Then a 1 + • • • + a ℓ = b 1 + • • • + b ℓ for all a 1 , . . . , a ℓ ∈ f -1 (0) and b 1 , . . . , b ℓ ∈ f -1 (1) if and only if f preserves B ℓ .
Proof. Assume first that f does not preserve B ℓ . Then there exists a matrix

M =      m 1 1 m 1 2 . . . m 1 n m 2 1 m 2 2 . . . m 2 n . . . . . . . . . m 2ℓ 1 m 2ℓ 2 . . . m 2ℓ n      =      M 1 M 2 . . . M 2ℓ      = (M 1 , M 2 , . . . , M n ),
i.e., M 1 , . . . , M 2ℓ ∈ B n are the rows of M , and M 1 , . . . , M n ∈ B 2ℓ are the columns of M , such that

• M 1 , . . . , M n ∈ R(B ℓ )
, and ).

• z := g(M 1 , . . . , M n ) :=    g(M 1 ) . . . g(M 2ℓ )    / ∈ S(B ℓ ).
Then M 1 , . . . , M ℓ ∈ f -1 (0) and M ℓ+1 , . . . , M 2ℓ ∈ f -1 (1), and

M 1 + • • • + M ℓ = M ℓ+1 + • • • + M 2ℓ by the definition of B ℓ .
Assume then that there exist a 1 , . . . ,

a ℓ ∈ f -1 (0) and b 1 , . . . , b ℓ ∈ f -1 (1) such that a 1 + • • • + a ℓ = b 1 + • • • + b ℓ . Let M be the 2ℓ × n matrix whose rows are a 1 , . . . , a ℓ , b 1 , . . . , b ℓ . The columns of M are tuples in R(B ℓ ), but f (M ) = (0, . . . , 0 ℓ , 1, . . . , 1 ℓ ) / ∈ S(B ℓ ). We conclude that f does not preserve B ℓ . Now it is easy to define a set of relational constraints that characterizes k- asummable functions. For k ≥ 2, let A k := {B n : 2 ≤ n ≤ k}. Lemma 2.4. Let k ≥ 2. A Boolean function f is k-asummable if and only if f ∈ cPol(A k ).
Proof. Follows immediately from the definition of k-asummability and Lemma 2.3. (i) f is a threshold function.

(ii) f ∈ k≥2 cPol(A k ). (iii) f ∈ cPol({B n : n ≥ 2}).
Proof. The equivalence of (i) and (ii) follows immediately from Theorem 2.2 and Lemma 2.4. Conditions (ii) and (iii) are equivalent, because

k≥2 cPol(A k ) = cPol k≥2 A k = cPol k≥2 {B n : 2 ≤ n ≤ k} = cPol({B n : n ≥ 2}). Since A k ⊆ A k ∪ {B k+1 } = A k+1 , it is clear that cPol(A k+1 ) ⊆ cPol(A k ) for all k ≥ 2.
Taylor and Zwicker have shown in [START_REF] Taylor | Simple games and magic squares[END_REF] that for every k ≥ 2, there exist k-asummable functions that are not (k + 1)-asummable. Hence these inclusions are strict for every k.

Theorem 2.6. For all k ≥ 2, cPol(A k+1 ) ⊂ cPol(A k ).
Theorem 2.7. The set cPol({B n : n ≥ 2}) is the class of all threshold functions. Moreover, for every clone C, the subclass C ∩ T of threshold functions is characterized by the set

{B n : n ≥ 2} ∪ Q C ,
T = k≥2 cPol(A k ) ⊂ • • • ⊂ cPol(A ℓ+1 ) ⊂ cPol(A ℓ ) ⊂ • • • ⊂ cPol(A 2 )
holds for all ℓ ≥ 3, i.e., the sets cPol(A k ) with k ≥ 2 form an infinite descending chain, whose intersection is the set T of all threshold functions. Theorem 2.7 provides an infinite set of relational constraints characterizing the set C ∩ T for each clone C. As Theorem 2.11 will reveal, the characterization provided is optimal for the clones not contained in L, V or Λ in the sense that for such clones C, the set C ∩ T is not finitely characterizable by relational constraints.

In order to proceed, we need the following lemma. Its proof is somewhat technical and is deferred to Section 3. Lemma 2.9. Let f be a Boolean function, and let

C ∈ {SM, M c U ∞ , M c W ∞ }.
There exists a Boolean function G C (f ) that satisfies the following conditions:

(i) G C (f ) ∈ C, (ii) for all n ≥ 2, f ∈ cPol B n if and only if G C (f ) ∈ cPol B n .
Proof. This brings together Corollaries 3.9, 3.14 and 3.16, which will be proved in Section 3.

Remark 2.10. Lemma 2.9 gives rise to a noteworthy refinement of Theorem 2.6. Indeed, by Theorem 2.6, there is some f ∈ cPol(A k )\cPol(A k+1 ) and, by Lemma 2.9, there exists a function This theorem is illustrated by Figure 1.

G E (f ) ∈ E ⊆ C satisfying G E (f ) ∈ cPol(A k ) \ cPol(A k+1 ). This implies that G E (f ) ∈ (C ∩ cPol(A k )) \ (C ∩ cPol(A k+1 )) and thus C ∩ cPol(A k+1 ) ⊂ C ∩ cPol(A k ) for all k ≥ 2. This shows that if C is a clone of Boolean functions satisfying E ⊆ C for some E ∈ {SM, M c U ∞ , M c W ∞ }, then C ∩ cPol(A k+1 ) ⊂ C ∩ cPol(A k ) for all k ≥ 2.
Proof. We have already observed that C ∩ T is finitely characterizable for every subclone C of L, V or Λ.

Now we consider all the other clones. Let C be a clone such that C ⊆ D for all D ∈ {L, V, Λ}. We can read off of Post's lattice (see Figure 1) that there is

Ω T 0 T 1 M L Ω(1) S SM U 2 U 3 U ∞ M c U ∞ Λ W 2 W 3 W ∞ M c W ∞ V Figure 1. Post's lattice. Illustration of Theorem 2.11: for a clone C, the set C ∩ T of threshold functions in C is finitely characteri- zable if and only if C is below the dashed line. some E ∈ {SM, M c U ∞ , M c W ∞ } such that E ⊆ C. It follows from Theorem 2.6
and Lemma 2.9 that for every k ≥ 2, there exists a function

f k ∈ E such that f k ∈ cPol B ℓ whenever 2 ≤ ℓ ≤ k and f k / ∈ cPol B k+1 . Note that f k / ∈ C ∩ T .
Suppose, on the contrary that C ∩ T is finitely characterizable. By Theorem 1.5, C ∩ T is of the form forbid(A) for some finite antichain A of minimal forbidden minors. Each one of the functions f k has a minor in A. Since A is finite, there is an element g ∈ A and an infinite set S ⊆ N such that g ≤ f k for all k ∈ S. The function g is not threshold, so there exists p ∈ N such that p ≥ 2 and g / ∈ cPol B p . Being infinite, the set S contains an element q with p ≤ q. Then we have g ≤ f q and f q ∈ cPol B p . We also have g ∈ cPol B p , because cPol B p is closed under taking minors. This yields the desired contradiction.

Remark 2.12. Alternatively, Theorem 2.11 can be proved using Lemma 1.7 and Remark 2.10.

As before if C is a subclone of L, V or Λ, then C ∩ T is finitely characterizable. As for any other clone C, we know (once again reading off of Post's lattice) that there is some

E ∈ {SM, M c U ∞ , M c W ∞ } such that E ⊆ C. By Remark 2.10, we have C ∩ cPol(A k+1 ) ⊂ C ∩ cPol(A k ) for all k ≥ 2. Furthermore, C ∩ T = C ∩ n≥2 cPol(A k ) = n≥2 (C ∩ cPol(A k )),
i.e., we have an infinite descending chain the intersection of which equals C ∩ T . By Lemma 1.7 we thus conclude that C ∩ T is not finitely characterizable.

Constructions

In order to prove Lemma 2.9, we will construct from a given Boolean function

f , for each C ∈ {S, M c , SM, U ∞ , M c U ∞ , M c W ∞ }, a Boolean function G C (f ) that satisfies the following conditions: (i) G C (f ) ∈ C, (ii) for all ℓ ≥ 2, f ∈ cPol B ℓ if and only if G C (f ) ∈ cPol B ℓ .
We do this step by step. We first construct functions G S (f ) and G Mc (f ) with the desired properties. Using these two constructions as building blocks, we can construct G SM as G Mc (G S (f )). Then we construct G U∞ (f ), and, building upon this, we finally get

G McU∞ (f ) := G U∞ (G Mc (f )) and G McW∞ (f ) := (G McU∞ (f )) d . 3.1. Construction of G S (f ). Let f : B n → B. Then we define G S (f ) : B n+1 → B by G S (f )(x 1 , . . . , x n+1 ) = (x n+1 ∧ f (x 1 , . . . , x n )) ∨ (x n+1 ∧ f d (x 1 , . . . , x n )).
Lemma 3.1. For any f :

B n → B, the function G S (f ) is self-dual.
Proof. Let g := G S (f ). Then

g d (x, x n+1 ) = (x n+1 ∧ f (x)) ∨ (x n+1 ∧ f d (x)) = (x n+1 ∨ f d (x)) ∧ (x n+1 ∨ f (x)) = (x n+1 ∧ x n+1 ) ∨ (x n+1 ∧ f (x)) ∨ (f d (x) ∧ x n+1 ) ∨ (f d (x) ∧ f (x)) = (x n+1 ∧ f (x)) ∨ (f d (x) ∧ x n+1 ) = g(x, x n+1 ),
where the second last equality holds since

f d (x) ∧ f (x) ≤ (x n+1 ∧ f (x)) ∨ (f d (x) ∧ x n+1 ) for every x n+1 . Lemma 3.2. Let f : B n → B. If f / ∈ cPol B ℓ for some ℓ ≥ 2, then G S (f ) / ∈ cPol B ℓ .
Proof. Assume that f / ∈ cPol B ℓ , and let g := G S (f ). Then there are y 1 , . . . , y n ∈ R(B ℓ ) with f (y 1 , . . . , y n ) / ∈ S(B ℓ ). Since g(x 1 , . . . , x n , 1) = f (x 1 , . . . , x n ), we have g(y 1 , . . . , y n , 1) = f (y 1 , . . . , y n ) / ∈ S(B ℓ ).

Since also 1 ∈ R(B ℓ ), we conclude that g / ∈ cPol B ℓ .

Lemma 3.3. Let f : B n → B. If f ∈ cPol B ℓ for some ℓ ≥ 2, then G S (f ) ∈ cPol B ℓ .
Proof. Let g := G S (f ). Suppose, on the contrary, that g / ∈ cPol B ℓ . Then there is some matrix M given by

M =      m 1 1 m 1 2 . . . m 1 n+1 m 2 1 m 2 2 . . . m 2 n+1 . . . . . . . . . m 2ℓ 1 m 2ℓ 2 . . . m 2ℓ n+1      =      M 1 M 2 . . . M 2ℓ      = (M 1 , M 2 , . . . , M n+1 ),
i.e., M 1 , . . . , M 2ℓ ∈ B n+1 are the rows of M , and M 1 , . . . , M n+1 ∈ B 2ℓ are the columns of M , such that

• M 1 , . . . , M n+1 ∈ R(B ℓ ), and ).

• z := g(M 1 , . . . , M n+1 ) :=    g(M 1 ) . . . g(M 2ℓ )    / ∈ S(B ℓ ).
We now look at the last column M n+1 of M . Since ) holds for some α, β ≥ 0 with α + β = ℓ.

We will now construct a matrix K with

K =      k 1 1 k 1 2 . . . k 1 n k 2 1 k 2 2 . . . k 2 n . . . . . . . . . k 2ℓ 1 k 2ℓ 2 . . . k 2ℓ n      =      K 1 K 2 . . . K 2ℓ      = (K 1 , K 2 , . . . , K n ), that satisfies K 1 , . . . , K n ∈ R(B ℓ ) and f (K 1 , . . . , K n ) / ∈ S(B ℓ
). This will yield the desired contradiction since we started with the assumption that f ∈ cPol B ℓ .

We define k i j for 1 ≤ i ≤ 2ℓ and 1 ≤ j ≤ n by

k i j =          m i+ℓ j if 1 ≤ i ≤ α m i j if α + 1 ≤ i ≤ ℓ m i-ℓ j if ℓ + 1 ≤ i ≤ ℓ + α m i j if ℓ + α + 1 ≤ i ≤ 2ℓ
In other words, matrix K is obtained from M by omitting the last column, negating rows 1, . . . , α and ℓ + 1, . . . , ℓ + α, and then swapping rows 1, . . . , α with rows ℓ + 1, . . . , ℓ + α.

We need to show that K j ∈ R(B ℓ ) for all j ∈ [n]. Let j ∈ [n] be arbitrary, and let

a := α i=1 m i j , b := ℓ i=α+1 m i j , c := ℓ+α i=ℓ+1 m i j , d := 2ℓ i=ℓ+α+1 m i j . Since M j ∈ R(B ℓ ) we have (2) a + b = ℓ i=1 m i j = 2ℓ i=ℓ+1 m i j = c + d.
For K j we find the following:

α i=1 k i j = α i=1 m i+ℓ j = α i=1 (1 -m i+ℓ j ) = α - ℓ+α i=ℓ+1 m i j = α -c, ℓ i=α+1 k i j = ℓ i=α+1 m i j = b, ℓ+α i=ℓ+1 k i j = ℓ+α i=ℓ+1 m i-ℓ j = ℓ+α i=ℓ+1 (1 -m i-ℓ j ) = α - α i=1 m i j = α -a, 2ℓ i=ℓ+α+1 k i j = 2ℓ i=ℓ+α+1 m i j = d.
From this it follows that

ℓ i=1 k i j = α -c + b (2) = α -a + d = 2ℓ i=ℓ+1 k i j ,
and thus K j ∈ R(B ℓ ) for all j ∈ [n].

We now show that f

(K i ) = 0 if 1 ≤ i ≤ ℓ, and f (K i ) = 1 if ℓ + 1 ≤ i ≤ 2ℓ.
We need to consider four different cases for i:

• 1 ≤ i ≤ α. Then (K i , 0) = M i+ℓ , and
f (K i ) = f d (K i ) = g(K i , 0) = g(M i+ℓ ) = 1. Hence f (K i ) = 0. • α + 1 ≤ i ≤ ℓ. Then (K i , 1) = M i , and f (K i ) = g(K i , 1) = g(M i ) = 0. • ℓ + 1 ≤ i ≤ ℓ + α. Then (K i , 0) = M i-ℓ , and
f (K i ) = f d (K i ) = g(K i , 0) = g(M i-ℓ ) = 0. Hence f (K i ) = 1. • ℓ + α + 1 ≤ i ≤ 2ℓ. Then (K i , 1) = M i , and f (K i ) = g(K i , 1) = g(M i ) = 1.
Thus we have

f (K 1 , . . . , K n ) =           f (K 1 )
. . .

f (K ℓ ) f (K ℓ+1 ) . . . f (K 2ℓ )           =           0 . . . 0 1 . . . 1           / ∈ S(B ℓ ),
in contradiction to f ∈ cPol B ℓ . We conclude that g ∈ cPol B ℓ .

• If w(x) < n, then G Mc (f )(x) := 0. • If w(x) > n, then G Mc (f )(x) := 1. • If x = (a, a) for some a ∈ B n , then G Mc (f )(x) := f (a). • If w(x) = n and there exists i ∈ [n] such that x i = x n+i and x j = x n+j for all j < i, then G Mc (f )(x) := x i .
It is easy to verify that the function G Mc (f ) is defined on every tuple x ∈ B 2n .

Lemma 3.5. Let f : B n → B. (i) G Mc (f ) ∈ M c , i.e., G Mc (f ) is monotone and constant-preserving. (ii) If f is self-dual, then G Mc (f ) is self-dual. Proof. Let g := G Mc (f ).
(i) Let x, y ∈ B 2n with x < y. Then w(x) < w(y) and one of the following cases applies: w(x) < n or w(y) > n. In the former case, we have g(x) = 0 ≤ g(y); in the latter case, we have g(x) ≤ 1 = g(y). We conclude that g is monotone.

Since w(0) = 0 < n and w(1) = 1 > n, it holds that f (0) = 0 and f (1) = 1, i.e., f preserves both constants.

(ii) Assume that f is self-dual. Let x ∈ B 2n . If w(x) > n then w(x) < n, and thus (g(x), g(x)) = (1, 0). Similarly, if w(x) < n then w(x) > n, and thus (g(x), g(x)) = (0, 1).

If x = (a, a) for some a ∈ B n , then (g(x), g(x)) = (f (a), f (a)) ∈ {(0, 1), (1, 0)} since f is self-dual.

Otherwise, there is some i ∈ [m] with x i = x m+i and x j = x m+j for all j < i. This holds also for the negation of x, and thus (g(x), g(x)) ∈ {(0, 1), (1, 0)}.

We conclude that g is self-dual.

Lemma 3.6. Let f : B n → B. If f / ∈ cPol B ℓ for some ℓ ≥ 2, then G Mc (f ) / ∈ cPol B ℓ . Proof. Let f / ∈ cPol B ℓ and g := G Mc (f ).
Then there are y 1 , . . . , y n ∈ R(B ℓ ) with f (y 1 , . . . , y n ) / ∈ S(B ℓ ). Also y 1 , . . . , y n ∈ R(B ℓ ) and thus g(y 1 , . . . , y n , y 1 , . . . ,

y n ) = f (y 1 , . . . , y n ) / ∈ S(B ℓ ). Therefore g / ∈ cPol B ℓ . Lemma 3.7. Let f : B n → B with f ∈ cPol B ℓ for some ℓ ≥ 2. Then G Mc (f ) ∈ cPol B ℓ .
Proof. Let g := G Mc (f ). Suppose, on the contrary, that g / ∈ cPol B ℓ . Then there is some matrix M given by

M =      m 1 1 m 1 2 . . . m 1 2n m 2 1 m 2 2 . . . m 2 2n . . . . . . . . . m 2ℓ 1 m 2ℓ 2 . . . m 2ℓ 2n      =      M 1 M 2 . . . M 2ℓ      = (M 1 , M 2 , . . . , M 2n ),
i.e., M 1 , . . . , M 2ℓ ∈ B 2n are the rows of M , and M 1 , . . . , M 2n ∈ B 2ℓ are the columns of M , such that

• M 1 , . . . , M 2n ∈ R(B ℓ ), and ).

• z := g(M 1 , . . . , M 2n ) :=    g(M 1 ) . . . g(M 2ℓ )    / ∈ S(B ℓ ).
We have the following possibilities for M i with 1 ≤ i ≤ 2ℓ:

(i) w(M i ) = n; (ii) w(M i ) = n and there is some b ∈ [n] with m i b = m i n+b ; (iii) w(M i ) = n and m i b = m i n+b for all b ∈ [n],
i.e., there is some a i ∈ B n with M i = (a i , a i ). We show that case (i) cannot happen, since the weight of each row

M i of M is exactly n. Since g(M i ) = 0 for 1 ≤ i ≤ ℓ, we have w(M i ) ≤ n for 1 ≤ i ≤ ℓ. Similarly, we have w(M i ) ≥ n for ℓ + 1 ≤ i ≤ 2ℓ. Thus ℓ i=1 w(M i ) ≤ nℓ and 2ℓ i=ℓ+1 w(M i ) ≥ nℓ. Because M j ∈ R(B ℓ ) for 1 ≤ j ≤ 2n, we get ℓ i=1 w(M i ) = ℓ i=1 2n j=1 m i j = 2n j=1 ℓ i=1 m i j = 2n j=1 2ℓ i=ℓ+1 m i j = 2ℓ i=ℓ+1 2n j=1 m i j = 2ℓ i=ℓ+1 w(M i ) Therefore ℓ i=1 w(M i ) = 2ℓ
i=ℓ+1 w(M i ) = nℓ, and w(M i ) = n for 1 ≤ i ≤ 2ℓ. Thus the case (i) cannot happen for M i .

We will show that case (ii) is also not possible. Suppose, on the contrary, that there is some i ∈ [2ℓ] and some b ∈ [n] such that m i b = m i n+b , and m i a = m i n+a for all a < b. We can assume that b is the smallest number with this property. Now we consider the weights of M b and M n+b . Because b is minimal, we have that m i ′ a = m i ′ n+a for all a < b. Thus we have (m i ′ b , m i ′ n+b ) ∈ {(0, 0), (0, 1), (1, 0)} for 1 ≤ i ′ ≤ ℓ, and (m i ′ b , m i ′ n+b ) ∈ {(0, 1), (1, 0), (1, 1)} for ℓ + 1 ≤ i ′ ≤ 2ℓ. Then

ℓ i ′ =1 (m i ′ b + m i ′ n+b ) ≤ n, 2ℓ i ′ =ℓ+1 (m i ′ b + m i ′ n+b ) ≥ n,
and at least one of these inequalities holds strictly. This implies that one of the following holds:

ℓ i ′ =1 m i ′ b < 2ℓ i ′ =ℓ+1 m i ′ b or ℓ i ′ =1 m i ′ n+b < 2ℓ i ′ =ℓ+1 m i ′ n+b .
This means that

M b / ∈ R(B ℓ ) or M n+b / ∈ R(B ℓ )
, in contradiction to the assumption. Thus no such b exists, and case (ii) cannot happen.

Thus case (iii) applies for all M i , i.e., M i = (a i , a i ) for some a i ∈ B n holds for all i ∈ [2ℓ]. By the definition of g and since f ∈ cPol B ℓ , we obtain

z = g    M 1 . . . M 2ℓ    = f    a 1 . . . a 2ℓ    = f (M 1 , . . . , M n ) ∈ S(B ℓ ).
But this is a contradiction to z / ∈ S(B ℓ ). Thus the matrix M cannot exist, and we have g ∈ cPol B ℓ .

Corollary 3.8. For any Boolean function

f : B n → B, G Mc (f ) ∈ M c and for all ℓ ≥ 2, f ∈ cPol B ℓ if and only if G Mc (f ) ∈ cPol B ℓ .
Proof. This brings together Lemmas 3.5(i), 3.6 and 3.7.

Let G SM (f ) := G Mc (G S (f )).
Then we can conclude the following corollary from the preceding lemmas. Corollary 3.9. For any Boolean function f :

B n → B, G SM (f ) ∈ SM and for all ℓ ≥ 2, f ∈ cPol B ℓ if and only if G SM (f ) ∈ cPol B ℓ .
Proof. By Corollary 3.4, we have G S (f ) ∈ S, and by Lemma 3.5, we get

G SM (f ) = G Mc (G S (f )) ∈ SM . By Corollary 3.4, the condition f ∈ cPol B ℓ is equivalent to G S (f ) ∈ cPol B ℓ , which is in turn equivalent to G SM (f ) = G Mc (G S (f )) ∈ cPol B ℓ by Corollary 3.8. 3.3. Construction of G U∞ (f ), G McU∞ (f ) and G McW∞ (f ). Let f : B n → B. De- fine G U∞ (f ) : B n+1 → B by G U∞ (f )(x 1 , . . . , x n+1 ) = x n+1 ∧ f (x 1 , . . . , x n ). Lemma 3.10. Let f : B n → B. (i) G U∞ (f ) ∈ U ∞ . (ii) If f is monotone, then G U∞ (f ) is monotone. (iii) If f (1) = 1, then G U∞ (f ) preserves both constants. (iv) If f ∈ M c , then G U∞ (f ) ∈ M c U ∞ .
Proof. Let g := G U∞ (f ).

(i) By the definition of g we have that if g(x 1 , . . . , x n+1 ) = 1 then x n+1 = 1. Thus g ∈ U ∞ .

(ii) Let x, y ∈ B n+1 , and assume that x < y. If x n+1 = 0, then g(x) = 0 ≤ g(y). If x n+1 = 1, then also y n+1 = 1, and since f is monotone, we have

g(x) = f (x 1 , . . . , x n ) ≤ f (y 1 , . . . , y n ) = g(y).
We conclude that g is monotone.

(iii) By the definition of g, we have g(0) = 0. Furthermore, if f (1) = 1, then we have g(1) = f (1) = 1.

(iv) Follows immediately from the previous items.

Lemma 3.11. Let f : B n → B. If f / ∈ cPol B ℓ for some ℓ ≥ 2, then G U∞ (f ) / ∈ cPol B ℓ .
Proof. The proof is exactly the same as the proof of Lemma 3.2.

Lemma 3.12. Let f : B n → B. If f ∈ cPol B ℓ for some ℓ ≥ 2, then G U∞ (f ) ∈ cPol B ℓ . Proof. Let g := G U∞ (f ).
Suppose, on the contrary, that g / ∈ cPol B ℓ . Then there is some matrix M given by

M =      m 1 1 m 1 2 . . . m 1 n+1 m 2 1 m 2 2 . . . m 2 n+1 . . . . . . . . . m 2ℓ 1 m 2ℓ 2 . . . m 2ℓ n+1      =      M 1 M 2 . . . M 2ℓ      = (M 1 , M 2 , . . . , M n+1 ),
i.e., M 1 , . . . , M 2ℓ ∈ B n+1 are the rows of M , and M 1 , . . . , M n+1 ∈ B 2ℓ are the columns of M , such that • M 1 , . . . , M n+1 ∈ R(B ℓ ), and

• z := g(M 1 , . . . , M n+1 ) :=    g(M 1 ) . . . g(M 2ℓ )    / ∈ S(B ℓ ). Thus z ∈ {(0, . . . , 0 ℓ , 1, . . . , 1 ℓ ), (1, . . . , 1 ℓ , 0, . . . , 0 ℓ )}. As B ℓ is invariant under swap-
ping the first ℓ coordinates with the last ℓ coordinates, we can assume that z = (0, . . . ,

0 ℓ , 1, . . . , 1 ℓ
).

We now look at the last column M n+1 of M . Since

ℓ i=1 m i n+1 = 2ℓ i=ℓ+1 m i n+1
, and since B ℓ is totally symmetric on the first ℓ rows and on the last ℓ rows, we can assume that

M n+1 = (0, . . . , 0 α , 1, . . . , 1 β , 0, . . . , 0 α , 1, . . . , 1 β ) holds for some α, β ≥ 0 with α + β = ℓ. If α > 0 then g(M ℓ+1 ) = g(m ℓ+1 1 , . . . , m ℓ+1 n , 0) = 0 ∧ f (m ℓ+1 1 , . . . , m ℓ+1 n ) = 0, in contradiction to g(M ℓ+1 ) = 1. Thus α = 0, and M n+1 = 1. But then f (M 1 , . . . , M n ) = g(M 1 , . . . , M n , 1) = z /
∈ S(B ℓ ), which implies that f / ∈ cPol B ℓ . This contradicts the assumption f ∈ cPol B ℓ , and we conclude that g ∈ cPol B ℓ . Corollary 3.13. For any Boolean function f :

B n → B, G U∞ (f ) ∈ U ∞ and for all ℓ ≥ 2, f ∈ cPol B ℓ if and only if G U∞ (f ) ∈ cPol B ℓ .
Proof. This brings together Lemmas 3.10(i), 3.11 and 3.12.

Let G McU∞ (f ) := G U∞ (G Mc (f )) and G McW∞ (f ) := G McU∞ (f ) d .
Corollary 3.14. For any Boolean function f :

B n → B, G McU∞ (f ) ∈ M c U ∞ and for all ℓ ≥ 2, f ∈ cPol B ℓ if
G McU∞ (f ) = G U∞ (G Mc (f )) ∈ M c U ∞ . By Corollary 3.8, the condition f ∈ cPol B ℓ is equivalent to G Mc (f ) ∈ cPol B ℓ , which in turn is equivalent to G McU∞ (f ) = G U∞ (G Mc (f )) ∈ cPol B ℓ by Corol- lary 3.13. Let f : B n → B. We define the functions f : B n → B and f : B n → B, for u ∈ B n , as f (a) = f (a), f u (a) = f (a ⊕ u).
Note that f d = f 1 , where 1 := (1, . . . , 1) ∈ B n . Lemma 3.15. Let f : B n → B, and let ℓ ≥ 2. The following are equivalent:

(i) f ∈ cPol B ℓ , (ii) f u ∈ cPol B ℓ for any u ∈ B n , (iii) f ∈ cPol B ℓ , (iv) f d ∈ cPol B ℓ .
Proof. (i) ⇐⇒ (ii): Let a 1 , . . . a n ∈ R(B ℓ ). Since R(B ℓ ) is invariant under taking negations of its members, we also have a 1 , . . . a n ∈ R(B ℓ ). Let u ∈ B n , and let b i := a i if u i = 0 and b

i := a i if u i = 1, for i ∈ [n]. If f ∈ cPol B ℓ , then f u (a 1 , . . . , a n ) = f (b 1 , . . . , b n ) ∈ S(B ℓ ); hence f u ∈ cPol B ℓ .
The converse implication holds, since (f u ) u = f . (i) ⇐⇒ (iii): Assume that f ∈ cPol B ℓ , and let a 1 , . . . a n ∈ R(B ℓ ). Then f (a 1 , . . . , a n ) ∈ S(B ℓ ). Since S(B ℓ ) is invariant under taking negations of its members, we have

f (a 1 , . . . , a n ) = f (a 1 , . . . , a n ) ∈ S(B ℓ ); hence f ∈ cPol B ℓ .
The converse implication holds, since f = f . (i) ⇐⇒ (iv): This follows immediately from the equivalence of (i), (ii) and (iii), because f d = f 1 . Corollary 3.16. For any Boolean function f :

B n → B, G McW∞ (f ) ∈ M c W ∞ and for all ℓ ≥ 2, f ∈ cPol B ℓ if and only if G McW∞ (f ) ∈ cPol B ℓ . Proof. Since M c W ∞ = {f d : f ∈ M c U ∞ },

Simple games and magic squares revisited

In their proof of the existence of k-asummable functions that are not (k + 1)asummable (see Theorem 2.6), Taylor and Zwicker constructed a certain family of functions [START_REF] Taylor | Simple games and magic squares[END_REF]. We recall their construction here, and then we will refine Theorem 2.6 and determine how the sets cPol B n are related to each other. We will also show that Taylor and Zwicker's functions actually constitute an antichain of minimally non-threshold functions.

Fix an integer k ≥ 3. For p, q ∈ [k], define the k × k matrix A p,q = (a i,j ) as follows:

a i,j =      k -1, if (i, j) = (p, q), 1
, if i = p and j = q, 0, otherwise.

For example, if k = 4, then

A 2,3 =     1 1 0 1 0 0 3 0 1 1 0 1 1 1 0 1     . Let B be the k × k matrix all
of whose entries are equal to k -1.

Let S be a subset of [k]×[k]. We refer to S as the i-th row if S = {(i, j) : j ∈ [k]}, and we refer to S as the j-th column if S = {(i, j)

: i ∈ [k]}. Lemma 4.1. Let S ⊆ [k] × [k].
Then (p,q)∈S A p,q = B if and only if S is a row or a column.

Proof. It is clear that if S is a row or a column, then (p,q)∈S A p,q = B.

Assume then that (p,q)∈S A p,q = B. Clearly S is nonempty, so choose an element (p, q) of S; clearly S contains another element (p ′ , q ′ ). If p = p ′ and q = q ′ , then the entry on row p column q in the sum (p,q)∈S A p,q is at least k; hence the sum cannot be equal to B. Thus either p = p ′ or q = q ′ . It is easy to see that in the former case, all remaining entries of S must be on the p-th row, and all elements of the p-th row must be in S; in the latter case, all remaining entries of S must be on the q-th column, and all elements of the q-th column must be in S. We conclude that S is either a row or a column.

We define a function φ : [R] k×k → N that maps each k × k matrix with entries in [R] to an integer, where R is a sufficiently large integer that will be specified below. The function φ is defined as follows: for a matrix M , read the entries of M from left to right and from top to bottom; the resulting string is the representation of φ(M ) in base R. For p, q ∈ [k], denote w p,q := φ(A p,q ) and t := φ(B). For example if k = 4, then w 2,3 = 1101003011011101 R and t = 3333333333333333 R . We must choose R in such a way that when we add these numbers to form the sum (p,q)∈S w p,q for any S ⊆ [k] × [k], no carry will occur. Thus, the number (k -1) 2 + (k -1) + 1 = k 2 -k + 1, or anything larger, would be fine.

It is easy to see that the function φ has the following preservation property: for any S ⊆ [k] × [k], φ( (p,q)∈S A p,q ) = (p,q)∈S φ(A p,q ). It thus follows from Lemma 4.1 that for all S ⊆ [k] × [k], it holds that (p,q)∈S w p,q = t if and only if S is a row or a column.

Fix a bijection β :

[k] × [k] → [k 2 ]. The characteristic tuple of a subset S of [k] × [k]
is the tuple e S ∈ B k 2 , whose i-th entry is 1 if i = β(p, q) for some (p, q) ∈ S and 0 otherwise. With no risk of confusion, we will refer to the characteristic tuples of rows and columns also as rows and columns, respectively.

Let w = (w β -1 (1) , . . . , w β -1 (k 2 ) ).

For any n-tuples a, b ∈ R n , the dot product is defined as

a • b = n i=1 a i b i .
Taylor and Zwicker's function f k : B k 2 → B is defined by the following rule: f k (x) = 1 if and only if x • w > t or x is a row.

Note that for all x ∈ B k Proof. If ℓ = mk for some integer m, then let a 1 , . . . , a ℓ comprise m occurrences of each column, and let b 1 , . . . , b ℓ comprise m occurrences of each row. Then, the a i are false points of f k and the b i are true points, and

a 1 + • • • + a ℓ = (m, . . . , m) = b 1 + • • • + b ℓ . Thus f k is not ℓ-asummable. Lemma 2.3 implies that f k does not preserve B ℓ .
Assume then that k is not a divisor of ℓ. Suppose, on the contrary, that f k does not preserve B ℓ By Lemma 2.3, there exist a 1 , . . . , On the other hand, since

a ℓ ∈ f -1 (0) and b 1 , . . . , b ℓ ∈ f -1 (1) such that a 1 + • • • + a ℓ = b 1 + • • • + b ℓ . Since x • w ≤ t for
a 1 + • • • + a ℓ = b 1 + • • • + b ℓ , we have ℓ i=1 a i • w = (a 1 + • • • + a ℓ ) • w = (b 1 + • • • + b ℓ ) • w = ℓ i=1 b i • w.
Consequently, a i • w = t and b i • w = t for all i ∈ [ℓ], and we conclude that each a i is a column and each b i is a row. Since k is not a divisor of ℓ, there necessarily exist two columns that have a different number of occurrences among a 1 , . . . , a ℓ . Then φ -1 (a 1 + • • • + a n ) is a matrix that is constant along each column, but there are two columns with distinct values. This contradicts the fact that the matrix φ If ℓ is even, say ℓ = 2k, then ). ).

-1 (b 1 + • • • + b n ) is constant
(0, 0) + • • • + (0, 0) k + (1, 1) + • • • + (1, 1) k = (0, 1) + • • • + (0, 1) k + (1, 0) + • • • + (1,

It is clear that

b i ∈ R(B ℓ ). Let z := f (b 1 , . . . , b n ), that is, z = (f (a
Since f ∈ cPol B ℓ , we have z ∈ S(R ℓ ). Then

z ∈ B ℓ \ {(0, . . . , 0 ℓ , 1, . . . , 1 ℓ ), (1, . . . , 1 ℓ , 0, . . . , 0 ℓ ))}.
This implies that Proof. Let m = n, and consider the comparability of f m and f n . Since all variables are essential in f m and in f n , and the number of essential variables cannot increase when taking minors, we have that f m ≤ f n whenever m > n. If m < n, then n is not a divisor of m but n is a divisor of itself. By Lemma 4.2, f n preserves B m and f m does not preserve B m . Since every minor of f n preserves all relational constraints f n does, we must have that f m ≤ f n also in this case.

f (a 1 , . . . , a n ) ∈ B m \ {(0, . . . , 0 m , 1, . . . , 1
Proposition 4.6. For every k ≥ 3, the function f k is monotone.

Proof. Let x, y ∈ B k 2 . If x < y, then, since each w p,q is positive, x • w < y • w. Therefore one of the following conditions holds: x • w < t or y • w > t. In the former case, f (x) = 0 ≤ f (y). In the latter case, f (x) ≤ 1 = f (y).

Proposition 4.7. For every k ≥ 3, the function f k is minimally non-threshold.

Proof. We need to show that every identification minor of f k is threshold. Let (p, q) and (p ′ , q ′ ) be distinct elements of [k] × [k], let I = {β(p, q), β(p ′ , q ′ )}, and assume without loss of generality that β(p, q) < β(p ′ , q ′ ). We will show that (f k ) I is ℓ-asummable for every ℓ ≥ 2 and hence threshold by Theorem 2.2. Let ℓ ≥ 2, and let a 1 , . . . , a ℓ ∈ ((f k ) I ) -1 (0), b 1 , . . . , b ℓ ∈ ((f k ) I ) -1 (1). Suppose, on the contrary, that

a 1 + • • • + a ℓ = b 1 + • • • + b ℓ . Let v ∈ B k 2 -1
be the tuple obtained from w by replacing its β(p, q)-th entry by w β(p,q) + w β(p ′ ,q ′ ) and deleting the β(p ′ , q ′ )-th entry. (Before proceeding, we ask the reader to recall the definition of δ I from (1) in Section 1.

a i • v = (a 1 + • • • + a ℓ ) • v = (b 1 + • • • + b ℓ ) • v = ℓ i=1 b i • v ≥ ℓt.
Hence a i • v = t and b i • v = t for all i ∈ [ℓ], that is, a i δ I is a column and b i δ I is a row for all i ∈ [ℓ]. Since (p, q) = (p ′ , q ′ ), we have p = p ′ or q = q ′ . If p = p ′ , then none of the rows b i δ I is the p-th row; hence φ -1 (b 1 δ I + • • • + b ℓ δ I ) is a matrix with a row full of 0's, while φ -1 (a 1 δ I + • • • + a ℓ δ I ) has no row full of 0's. If q = q ′ , then none of the columns a i δ I is the q-th column; hence φ -1 (a 1 δ I + • • • + a ℓ δ I ) is a matrix with a column full of 0's, while φ -1 (b 1 δ I + • • • + b ℓ δ I ) has no column full of 0's. On the other hand,

a 1 δ I + • • • + a ℓ δ I = (a 1 + • • • + a ℓ )δ I = (b 1 + • • • + b ℓ )δ I = b 1 δ I + • • • + b ℓ δ I .
Let a ∈ {0, 1}. A set A ⊆ {0, 1} n is said to be a-separating if there is some i ∈ [n] such that for every (a 1 , . . . , a n ) ∈ A we have a i = a. A function f is said to be a-separating if f -1 (a) is a-separating. The function f is said to be a-separating of rank k ≥ 2 if every subset A ⊆ f -1 (a) of size at most k is a-separating.

• For m ≥ 2, U m and W m denote the clones of all 1-and 0-separating functions of rank m, respectively. They are characterized by the m-ary relations B m \{(0, . . . , 0)} and B m \ {(1, . . . , 1)}, respectively.

• U ∞ and W ∞ denote the clones of all 1-and 0-separating functions, respectively, i.e., U ∞ = k≥2 U k and W ∞ = k≥2 W k .

• • V denotes the clone of all disjunctions and constants, i.e.,

V = {f ∈ Ω : f = x i1 ∨ • • • ∨ x in } ∪ {0 (n) : n ≥ 1} ∪ {1 (n) : n ≥ 1}.
It is characterized by the ternary relation {(a, b, c) : a ∨ b = c}.

• V 0 = V ∩ T 0 , V 1 = V ∩ T 1 , V c = V ∩ T c .
• Ω(1) denotes the clone of all projections, negations, and constants. It

1. 2 .

 2 Boolean functions. Throughout the paper, we denote the set {1, . . . , n} by [n] and the set {0, 1} by B. A Boolean function is a map f : B n → B for some positive integer n called the arity of f . Typical examples of Boolean functions include • the n-ary i-th projection

  Thus z ∈ {(0, . . . , 0 l , 1, . . . , 1 l ), (1, . . . , 1 l , 0, . . . , 0 l )}. As B ℓ is invariant under swapping the first ℓ rows with the last ℓ rows, we can assume that z = (0, . . . , 0 ℓ , 1, . . . , 1 ℓ

Corollary 2 . 5 .

 25 Let f : B n → B. The following are equivalent.

Theorem 2 . 11 .

 211 Let C be a clone of Boolean functions. The subclass C ∩ T of threshold functions is finitely characterizable if and only if C is contained in one of the clones L, V , Λ.

  As B ℓ is invariant under swapping the first ℓ coordinates with the last ℓ coordinates, we can assume that z = (0, . . . , 0 ℓ , 1, . . . , 1 ℓ

α, 1 ,

 1 since B ℓ is totally symmetric on the first ℓ rows and on the last ℓ rows, we can assume that M n+1 = (0, . . . , 0

Corollary 3 . 4 . 3 . 2 .

 3432 For any Boolean function f : B n → B, G S (f ) ∈ S and for all ℓ ≥ 2, f ∈ cPol B ℓ if and only if G S (f ) ∈ cPol B ℓ . Proof. This brings together Lemmas 3.1, 3.2 and 3.3. Construction of G Mc (f ) and G SM (f ). Let f : B n → B. We define the Boolean function G Mc (f ) : B 2n → B by the following rules

, 1 ,ℓ, 1 ,

 11 Thus z ∈ {(0, . . . , 0 ℓ . . . , 1 ℓ ), (1, . . . , 1 ℓ , 0, . . . , 0 ℓ )}. As B ℓ is invariant under swapping the first ℓ coordinates with the last ℓ coordinates, we can assume that z = (0, . . . , 0 . . . , 1 ℓ

  the claim follows from Lemma 3.15 and Corollary 3.14.

  any false point x of f k , and x • w ≥ t for any true point x, we have ℓ i=1 a i • w ≤ ℓt and ℓ i=1 b i • w ≥ ℓt.

Lemma 4 . 3 .

 43 along each row. This completes the proof, and we conclude that f k preserves B ℓ . The modulo-2 addition operation ⊕ preserves B ℓ if and only if ℓ is odd.Proof. The false points of ⊕ are (0, 0) and (1, 1), while the true points are (0, 1) and (1, 0). Hence the sum of any ℓ false points is of the form (m, m) for some m with 0 ≤ m ≤ ℓ. The sum of any ℓ true points is of the form (m, ℓ -m) for somem with 0 ≤ m ≤ ℓ. If ℓ is odd, then m = ℓ -m for any m. It follows that a 1 + • • • + a ℓ = b 1 + • • • + b ℓ forany false points a 1 , . . . , a ℓ and any true points b 1 , . . . , b ℓ . By Lemma 2.3, ⊕ preserves B ℓ .

Proposition 4 . 5 .

 45 f ∈ cPol B m , and we conclude that cPol B ℓ ⊆ cPol B m . The functions f k (k ≥ 3) are pairwise incomparable by the minor relation.

  3.) It clearly holds thatx • v = xδ I • w for all x ∈ B k 2 -1 . Therefore ((f k ) I )(x) = f k (xδ I ) = 1 if and only if x • v = xδ I • w > t or xδ I is a row. Note that if xδ I is a row or a column, then x • v = xδ I • w = t.In a similar way as we argued in the proof of Lemma 4.2, we have ℓt ≥ ℓ i=1

  T c U m = T c ∩ U m and T c W m = T c ∩ W m , for m = 2, . . . , ∞. • M U m = M ∩ U m and M W m = M ∩ W m , for m = 2, . . . , ∞. • M c U m = M c ∩ U m and M c W m = M c ∩ W m , for m = 2, . . . , ∞.• Λ denotes the clone of all conjunctions and constants, i.e.,Λ = {f ∈ Ω : f = x i1 ∧ • • • ∧ x in } ∪ {0 (n) : n ≥ 1} ∪ {1 (n) : n ≥ 1}. It is characterized by the ternary relation {(a, b, c) : a ∧ b = c}. • Λ 0 = Λ ∩ T 0 , Λ 1 = Λ ∩ T 1 , Λ c = Λ ∩ T c .

  is characterized by the ternary relation {(a, b, c) : a = b or b = c}.•I * = Ω(1) ∩ S, I = Ω(1) ∩ M . • I 0 = I ∩ T 0 , I 1 = I ∩ T 1 .• I c denotes the smallest clone containing only projections, i.e., I c = I ∩ T c .

  where Q C is the set of relational constraints characterizing the clone C, as given in Appendix A.

	Remark 2.8. From Theorems 2.6 and 2.7 it follows that

  and only if G McU∞ (f ) ∈ cPol B ℓ . Proof. By Corollary 3.8, we have G Mc (f ) ∈ M c , and by Lemma 3.10, we get

  2 , x • w = t if and only if x is a row or a column. Lemma 4.2. Let k ≥ 3 and ℓ ≥ 2. Then f k preserves B ℓ if and only if k is not a divisor of ℓ.

  Proposition 4.4. Let ℓ, m ≥ 2. Then cPol B ℓ ⊆ cPol B m if and only if m divides ℓ. Proof. Assume first that m does not divide ℓ. If m = 2, then by Lemma 4.2,f m ∈ cPol B ℓ but f m / ∈ cPol B m . If m = 2, then by Lemma 4.3, ⊕ ∈ cPol B ℓ but ⊕ / ∈ cPol B m .In either case, we conclude that cPol B ℓ ⊆ cPol B m . Assume then that ℓ = km for some integer k. Let f ∈ cPol B ℓ . Let a 1 , . . . , a n ∈ R(B m ). For each i ∈ {1, . . . , n}, define the tuple b i ∈ B ℓ as

	b i = (a i 1 , . . . , a i 1	, . . . , a i m , . . . , a i m	, a i m+1 , . . . , a i m+1	, . . . , a i 2m , . . . , a i 2m
	k	k	k	k

0) k . By Lemma 2.3, ⊕ does not preserve B ℓ .

We have reached a contradiction.

We conclude that (f k ) I is ℓ-asummable for every ℓ ≥ 2 and hence threshold.

Taylor and Zwicker's functions f k constitute an infinite antichain of monotone, minimally non-threshold functions (Propositions 4.5, 4.6, 4.7). It should be noted here that this antichain does not, however, characterize the set of monotone threshold functions in terms of forbidden minors, i.e., M ∩ T = forbid({f k : k ≥ 3}). For example, there exist self-dual monotone non-threshold functions of arity 6 (see, e.g., [1]), which clearly fail to have any of the f n as a minor.

Appendix A. Post classes

We provide a concise description of all clones of Boolean functions as well as characterizing sets of relations R -or, equivalently, relational constraints (R, R) -for some clones; the characterizion of the remaining clones is easily derived by noting that if

We make use of notations and terminology appearing in [START_REF] Foldes | Post classes characterized by functional terms[END_REF] and [START_REF] Jablonski | Boolesche Funktionen und Postsche Klassen[END_REF].

• Ω denotes the clone of all Boolean functions. It is characterized by the empty relation.

• T 0 and T 1 denote the clones of 0-and 1-preserving functions, respectively, i.e.,

They are characterized by the unary relations {0} and {1}, respectively.

• T c denotes the clone of constant-preserving functions, i.e., T c = T 0 ∩ T 1 .

• M denotes the clone of all monotone functions, i.e.,

It is characterized by the binary relation ≤ := {(0, 0), (0, 1), (1, 1)}.

• S denotes the clone of all self-dual functions, i.e., S = {f ∈ Ω :

It is characterized by the binary relation {(0, 1), (1, 0)}.

• S c = S ∩ T c , SM = S ∩ M .

• L denotes the clone of all linear functions, i.e.,


Miguel Couceiro

Erkko Lehtonen

Tam Ás Waldhauser

ON EQUATIONAL DEFINABILITY OF FUNCTION CLASSES

We propose a notion of functional equation for functions of a fixed arity, which is based on a pair of clones. We present necessary conditions for a class of functions to be definable by such equations, and show that for certain choices of clones these conditions are also sufficient.

Introduction and motivations

This paper is a study of definability of properties of functions by functional equations. We propose an equational framework which differs from those presented in [START_REF] Couceiro | Definability of Boolean function classes by linear equations over GF(2)[END_REF][START_REF] Couceiro | Functional equations, constraints, definability of function classes, and functions of Boolean variables[END_REF][START_REF] Ekin | Equational characterizations of Boolean function classes[END_REF][START_REF] Foldes | Equational classes of Boolean functions via the HSP theorem[END_REF][START_REF] Foldes | Post classes characterized by functional terms[END_REF][START_REF] Pippenger | Galois theory for minors of finite functions[END_REF] in that here the properties to be defined concern functions of a given fixed arity rather than functions of different arities. (This distinction is made clear in Subsection 1.2.) The current approach is thus rooted in the classical theory of functional equations, and it provides a means to express natural properties of functions that are not definable in those other equational frameworks. A classical example of such a property is symmetry. A preliminary version of the current paper was presented at the 41st International Symposium on Multiple-Valued Logic (ISMVL 2011), see [START_REF] Couceiro | On equational definability of function classes[END_REF].

1.1. Basic notions. Throughout the paper let A, B and C be finite sets, and for each integer n ≥ 1 let [n] := {1, . . . , n}. We denote tuples by bold letters and their components by corresponding indexed italic letters, e.g., a = (a 1 , . . . , a n ) ∈ A n . By a function of several variables from A to B (or simply function, when the sets A and B are clear from the context) we mean a map f : A n → B, where n ≥ 0 is called the arity of f . The set of all n-ary functions from A to B is denoted by B A n . For a class K ⊆ n≥0 B A n , we set K (m) = K ∩ B A m . Functions of several variables from the two-element set {0, 1} to {0, 1} are usually called Boolean functions. The set of all functions of several variables from A to A is denoted by O A . The kernel of a function f ∈ B A n is the equivalence relation ker f ⊆ A n × A n defined by (a, a ) ∈ ker f ⇐⇒ f (a) = f (a ).

The composition of f : B n → C by g 1 , . . . , g n : A m → B, denoted by f (g 1 , . . . , g n ), is defined as the m-ary function from A to C given by f (g 1 , . . . , g n )(a) = f (g 1 (a), . . . , g n (a)), for every a ∈ A m .

We say that f is the outer function of the composition, and g 1 , . . . , g n are the inner functions.

A clone on A is a class C ⊆ O A of finitary functions on A that is closed under composition and contains the projections

x (n) i : A n → A, (x 1 , . . . , x n ) → x i (n ∈ N, 1 ≤ i ≤ n) .
We will omit the upper index, when there is no risk of ambiguity. It is noteworthy that the class I A of all projections is the smallest clone on A, whereas O A is the largest clone on A. Also, it is well known that the intersection of any family of clones is itself a clone. Hence, for F ⊆ O A , there is a smallest clone on A which contains F , namely, F A := C∈F C, where F is the set of all clones on A which contain F ; we may write simply F whenever the underlying set A is clear from the context. We will denote the clone of all constant functions and projections on A by C A . For further background in clone theory see, e.g., [START_REF] Lau | Function Algebras on Finite Sets[END_REF][START_REF] Pöschel | Funktionen-und Relationenalgebren, Mathematische Monographien[END_REF]. 1 1.2. Functional equations. In [START_REF] Couceiro | Functional equations, constraints, definability of function classes, and functions of Boolean variables[END_REF], the authors worked on an equational framework for defining properties of functions f : A n → B, n ≥ 1, rooted in universal algebra and originally proposed in [START_REF] Ekin | Equational characterizations of Boolean function classes[END_REF] for the study of Boolean functions. Essentially, a functional equation (for functions f : A n → B) was defined as a formal expression

(1) u(f (g 1 (x 1 , . . . , x m )), . . . , f (g r (x 1 , . . . , x m ))) = v(f (h 1 (x 1 , . . . , x m )), . . . , f (h s (x 1 , . . . , x m ))),
where r, s, m ≥ 1, u : B r → C, v : B s → C, each g i and h j is a map A m → A, the symbols x 1 , . . . , x m are m distinct vector variable symbols, and f is a distinct function symbol. A function f :

A n → B is said to satisfy (1) if, for all a 1 , . . . , a m ∈ A n , u(f (g 1 (a 1 , . . . , a m )), . . . , f (g r (a 1 , . . . , a m ))) = v(f (h 1 (a 1 , . . . , a m )), . . . , f (h s (a 1 , . . . , a m ))).
In this way, a class of functions is defined by a set of such functional equations if it comprises exactly those functions which satisfy every equation in the set. This framework has been advantageously used to specify noteworthy properties of functions in terms of functional equations. Classical examples include

• linearity of functions f : F n → F, n ≥ 1, on a field F, which is defined by f (x + y) = f (x) + f (y),
• nondecreasing and nonincreasing monotonicity of functions f : L n → L, n ≥ 1, on a lattice L, which are defined by

f (x) = f (x) ∨ f (x ∧ y) and f (x) = f (x) ∨ f (x ∨ y),
respectively.

More contemporary examples, which have strong consequences in combinatorial optimization, include

• submodularity of functions f : I n → R, where I is a chain, usually expressed by the functional inequality

f (x) + f (y) ≥ f (x ∧ y) + f (x ∨ y)
or, equivalently, by the functional equation

f (x) + f (y) = max f (x ∧ y) + f (x ∨ y), f (x) + f (y) ,
• supermodularity of functions f : I n → R, where I is a chain, usually expressed by the functional inequality

f (x) + f (y) ≤ f (x ∧ y) + f (x ∨ y)
or, equivalently, by the functional equation

f (x) + f (y) = min f (x ∧ y) + f (x ∨ y), f (x) + f (y) ,
• modularity of functions f : I n → R, where I is a chain, which is defined by the functional equation

f (x) + f (y) = f (x ∧ y) + f (x ∨ y).
Using this functional equation, it can be shown [START_REF] Topkis | Minimizing a submodular function on a lattice[END_REF] that modular functions are exactly those which are separable, i.e., of the form f i (x i ) + c, where f i : I → R for each i ∈ [n] and c ∈ R. For background on sub-and supermodularity and their applications in combinatorial optimization, see, e.g., [START_REF] Lovász | Submodular functions and convexity[END_REF][START_REF] Welsh | Matroid Theory[END_REF].

Pippenger [START_REF] Pippenger | Galois theory for minors of finite functions[END_REF] considered somewhat different defining objects, so-called relational constraints. An m-ary relational constraint from A to B is a pair (R, S), where R is an m-ary relation on A and S is an m-ary relation on B. A function f : A n → B preserves a relational constraint (R, S), if for all m-by-n matrices A = [a ij ] m×n with entries from A, it holds that f (a 11 , . . . , a 1n ), f (a 21 , . . . , a 2n ), . . . , f (a m1 , . . . , a mn ) ∈ S whenever (a 1j , . . . , a mj ) ∈ R for all j ∈ [n] (in other words, if all columns of A are tuples in the relation R, then application of f to the rows of A results in a tuple in S). A class C of functions is defined by a set K of relational constraints if C is the set of all functions that preserve all relational constraints in K.

As it turned out, relational constraints have the same expressive power as functional equations in the sense that they define exactly the same function classes. For example, let I be a chain and let

R = {(a, b, c, d) ∈ I 4 : c = a ∧ b, d = a ∨ b}, S ≥ = {(p, q, r, s) ∈ R 4 : p + q ≥ r + s}, S ≤ = {(p, q, r, s) ∈ R 4 : p + q ≤ r + s}, S = = {(p, q, r, s) ∈ R 4 : p + q = r + s}.
It is not difficult to see that (R, S ≥ ), (R, S ≤ ), and (R, S = ) define the classes of submodular, supermodular, and modular functions, respectively.

Observe that a function f : A n → A preserves a relation R if and only if f preserves the relational constraint (R, R). Since clones (on a finite set) are exactly those classes which are defined by relations [START_REF] Bodnarčuk | Galois theory for Post algebras[END_REF][START_REF] Geiger | Closed systems of functions and predicates[END_REF][START_REF] Lau | Function Algebras on Finite Sets[END_REF][START_REF] Pöschel | Funktionen-und Relationenalgebren, Mathematische Monographien[END_REF], every clone is definable by relational constraints or, equivalently, by functional equations. For variants and extensions see, e.g., [START_REF] Couceiro | Definability of Boolean function classes by linear equations over GF(2)[END_REF][START_REF] Couceiro | Function classes and relational constraints stable under compositions with clones[END_REF][START_REF] Foldes | Equational classes of Boolean functions via the HSP theorem[END_REF][START_REF] Foldes | Post classes characterized by functional terms[END_REF][START_REF] Marchenkov | Solutions of systems of functional equations of manyvalued logic[END_REF][START_REF] Pippenger | Galois theory for minors of finite functions[END_REF].

Classes definable by functional equations of the form (1), or, equivalently, by relational constraints, were completely characterized in terms of a quasi-ordering of functions, the so-called simple minor relation. For a finite set A, the equational classes of B-valued functions on A were shown to coincide with the initial segments of this quasi-ordering [START_REF] Couceiro | On the lattice of equational classes of Boolean functions and its closed intervals[END_REF][START_REF] Couceiro | On a quasi-ordering on Boolean functions[END_REF][START_REF] Ekin | Equational characterizations of Boolean function classes[END_REF][START_REF] Pippenger | Galois theory for minors of finite functions[END_REF]. In the case when A is arbitrary, possibly infinite, one additional "local closure" condition is also required [START_REF] Couceiro | On closed sets of relational constraints and classes of functions closed under variable substitutions[END_REF][START_REF] Couceiro | Functional equations, constraints, definability of function classes, and functions of Boolean variables[END_REF].

Despite the fact that a wide variety of function classes can be defined within this framework, it cannot express certain classical properties of functions f : A n → B such as symmetry:

f (a 1 , . . . , a n ) = f (a σ(1) , . . . , a σ(n) ) for all a 1 , . . . , a n ∈ A and any permutation σ on [n]. This limitation may be due to the fact that functional equations of the form (1) do not refer to the arity of functions. This fact leads to the following notion of functional equation, that is rooted in classical theory of functional equations.

Let A and B be clones on A and B, respectively. A (B, A)-equation is a functional equation of the form (2) u (f (g 11 , . . . , g 1n ) , . . . , f (g r1 , . . . , g rn ))

= v (f (h 11 , . . . , h 1n ) , . . . , f (h s1 , . . . , h sn )) , where r, s, n ≥ 0, u ∈ B (r) , v ∈ B (s) , each g ij and h ij is a function in A (m) , m ≥ 0, and f is an n-ary function symbol. Observe that if we interpret the function symbol f by a function f : A n → B, then each side of (2) becomes an m-ary function from A to B. For this reason we will sometimes refer to (2) as an m-ary (B, A)-equation.

We say that f : A n → B satisfies (2) if for every a ∈ A m u (f (g 11 , . . . , g 1n ) , . . . , f (g r1 , . . . , g rn )) (a)

= v (f (h 11 , . . . , h 1n ) , . . . , f (h s1 , . . . , h sn )) (a) .

A set E of (B, A)-equations defines a class K of n-ary functions from A to B if f ∈ K if and only if f satisfies all members of E. A class K of n-ary functions from A to B is (finitely) definable by (B, A)-equations if there is a (finite) set E of (B, A)-equations that defines K. In the sequel, unless otherwise specified, B and A always denote arbitrary clones on B and A.

Example 1. The class of n-ary symmetric functions is definable by (I

A , I A )- equations. Indeed, f ∈ O (n) A is symmetric if and only if it satisfies the (I A , I A )- equation f (x 1 , . . . , x n ) = f x σ(1) , . . . , x σ(n)
, for every permutation σ on [n]. In fact, two of these n! equations suffice, since the symmetric group S n can be generated by two permutations (e.g., an n-cycle and a transposition).

Example 2. Let (A; ∧ A , ∨ A ) and (B; ∧ B , ∨ B ) be lattices. The class of n-ary orderpreserving functions from A to B is defined by the ( ∧ B , ∧ A )-equation

f (x 1 ∧ A y 1 , . . . , x n ∧ A y n ) ∧ B f (x 1 , . . . , x n ) = f (x 1 ∧ A y 1 , . . . , x n ∧ A y n ) ,
while the class of n-ary order-reversing functions from A to B is defined by the

( ∧ B , ∧ A )-equation f (x 1 ∧ A y 1 , . . . , x n ∧ A y n ) ∧ B f (x 1 , . . . , x n ) = f (x 1 , . . . , x n ) .
Similarly, these classes are definable by (B, A)-equations for any choice of clones

B ∈ { ∧ B , ∨ B } and A ∈ { ∧ A , ∨ A }.
Clearly, all of these equations are (M B , M A )equations, where M A and M B denote the clones of monotone (order-preserving) functions on A and B, respectively. In general, the larger the clones B and A are, the larger the expressive power of (B, A)-equations is: if B ⊆ B and A ⊆ A , then every class definable by (B, A)-equations is definable by (B , A )-equations.

Example 3. If (A; •) and (B; * ) are groupoids, with clones of term functions A and B, respectively, then the set of homomorphisms from A n to B is defined by the (B, A)-equation

(3) f (x 1 • y 1 , . . . , x n • y n ) = f (x 1 , . . . , x n ) * f (y 1 , . . . , y n ) .
This is a generalization of the classical Cauchy equation f (x + y) = f (x) + f (y) (see, e.g., [START_REF] Aczél | Functional Equations in Several Variables[END_REF]) whose solutions f : I → R, for I ⊆ R containing the origin 0, are of the form f (x) = cx, for some c ∈ R, or the graph of f is everywhere dense in I × R (for a recent reference, see also [START_REF] Couceiro | Axiomatizations of Lovász extensions of pseudo-Boolean functions[END_REF]). Another particular instance of ( 3) is the so-called Jensen's equation f

( x+y 2 ) = f (x)+f (y) 2
whose most general solutions are of the form f (x) = f 0 (x) + a for an arbitrary a ∈ R and an arbitrary function f 0 satisfying Cauchy's equation (see, e.g., [START_REF] Aczél | Lectures on Functional Equations and Their Applications[END_REF]).

Example 4.

Several other examples of functional equations, involving not only unary functions, can be found in classical theory of functional equations. A noteworthy example is the so-called Sincov's functional equation f (x 1 , x 2 ) + f (x 2 , x 3 ) = f (x 1 , x 3 ). The general solutions for this (L 0 , I R )-equation are known to be of the form f (x 1 , x 2 ) = g(x 2 ) -g(x 1 ). (Here L 0 denotes the clone of 0-preserving linear functions over the field R.) For general background and further examples in classical theory of functional equations see, e.g., [START_REF] Aczél | Lectures on Functional Equations and Their Applications[END_REF][START_REF] Aczél | Functional Equations in Several Variables[END_REF][START_REF] Kuczma | An Introduction to the Theory of Functional Equations and Inequalities[END_REF].

Example 5. For any f ∈ B A n , the singleton {f } can be defined by (C B , C A )equations as follows. Let a be an arbitrary element of A n , and let b = f (a). The functional equation f (a 1 , . . . , a n ) = b is a (C B , C A )-equation: on the left side the outer function is the identity function, and the inner functions are the constants a 1 , . . . , a n , while on the right side we have only the constant function b as outer function. These equations, for all a ∈ A n , constitute a system of equations that is satisfied only by f , since these equations specify the value of the function at every a ∈ A n . Example 6. Let A be a finite field, and let L 0 be the clone of 0-preserving linear functions on A, i.e., functions of the form u (x 1 , . . . , x r ) = a

1 x 1 +• • •+a r x r (a i ∈ A). Let us examine which classes K ⊆ O (n) A are definable by (L 0 , C A )-equations. Let N = |A|
n , and let {a 1 , . . . , a N } = A n . We will regard a function f ∈ O (n)

A as a vector -→ f in the N -dimensional vector space A N whose i-th coordinate is f (a i ). Any (L 0 , C A )-equation (for f = f ) translates into a system of homogeneous linear equations involving the components of -→ f (namely, one equation corresponding to each assignment of values to the variables). Conversely, every homogeneous linear equation involving the components of -→ f is equivalent to an (L 0 , C A )-equation. Therefore, a function class K is definable by (L 0 , C A )-equations if and only if the corresponding set

- → K = - → f : f ∈ K of vectors
is the solution set of a system of homogeneous linear equations. It is a well-known fact from linear algebra that such sets can be characterized as subspaces of the vector space A N . Thus, a class K of functions is definable by (L 0 , C A )-equations if and only if it is closed under linear combinations.

In the next section we make some general observations about equational definability, and in the last two sections we consider the problem of characterizing function classes definable by (B, A)-equations by means of closure conditions, much in the spirit of Example 6. We present a necessary condition in Section 3, and we prove in Section 4 that this necessary condition is also sufficient in the four cases when B and A contain either only projections or all functions.

Preliminary results

From the fact that A and B are finite it follows that definability by (B, A)equations can be always achieved by means of finite sets of (B, A)-equations.

Proposition 1. A class K ⊆ B A n is definable by (B, A)-equations if and only if it is finitely definable by (B, A)-equations.
Proof. Clearly, the condition is sufficient. To show that it is also necessary, suppose that K is defined by a (possibly infinite) set E of (B, A)-equations. For every f ∈ B A n \ K we can find an equation in E that is not satisfied by f . Choosing one such equation for each f ∈ B A n \ K, we get a finite subset of E that defines K, since Proof. The sufficiency is obvious; for the necessity let us suppose that K is definable by (B, A)-equations. By Proposition 1, we may assume that K is defined by a finite set {E 1 , . . . , E t } of (B, A)-equations, say, each E i being of the form T i1 = T i2 . Consider the (B, A)-equation

B A n \ K is finite.
i∈[t] (T i1 ↔ T i2 ) = 1.
(Note that since clone B contains ↔, it also contains the operation 1 = x 1 ↔ x 1 occurring on the right side of the above equation.) Obviously, this equation alone defines K.

The next proposition shows that the set of classes K ⊆ B A n definable by (B, A)equations constitutes a lattice under union and intersection, provided that the clone B is sufficiently large. Proposition 3. If clone B contains the operations ∧ and ↔, and K, K ⊆ B A n are definable by (B, A)-equations, then so are K ∩ K and K ∪ K .

Proof. Clearly, K ∩ K is definable by (B, A)-equations, whenever both K and K are definable by (B, A)-equations.

For the second claim, observe that by Proposition 2 there are two (B, A)-equations T 1 = T 2 and T 1 = T 2 defining K and K , respectively. Let us define a binary operation ∨ on B by the formula x ∨ y = (x ∧ y) ↔ (x ↔ y). It is easy to see that the restriction of this operation to {0, 1} coincides with the Boolean disjunction operation, moreover ∨ ∈ B by our assumption on B. Consider the (B, A)-equation

(T 1 ↔ T 2 ) ∨ (T 1 ↔ T 2 ) = 1.
(Note that since clone B contains ↔, it also contains the operation 1 = x 1 ↔ x 1 occurring on the right side of the above equation.) It is straightforward to verify that a function f satisfies this equation if and only if f ∈ K ∪ K .

Remark 1. Let us note that in Propositions 2 and 3, the operation ∧ can be replaced by any binary operation whose restriction to {0, 1} coincides with the Boolean conjunction.

Proposition 4. A class K ⊆ B A n is definable by (B, O A )-equations if and only if it is definable by (B, C A )-equations.
Proof. Sufficiency is obvious. To show necessity, let us assume that K is defined by a set E of (B, O A )-equations. For any m-ary equation E ∈ E, let us evaluate E at every tuple a ∈ A m . This way we get |A| m equalities, each of which can be regarded as a (B, C A )-equation (the inner functions are the constants obtained by evaluating the inner functions of E at a). A function f satisfies these equations if and only if it satisfies the original equation E. Unfolding each equation of E in this manner, we end up with a (large) set of (B, C A )-equations that defines K. Remark 2. In equation [START_REF] Aczél | Functional Equations in Several Variables[END_REF], only the arity of f is fixed; the arities of the inner and outer functions are arbitrary. However, by making use of the fact that the underlying set A is finite, we can actually restrict these arities. To see this, let us consider a functional equation E of the form (2). Let us choose a map ρ : [m] → A, and let us replace the variables x i in E by new variables y ρ(i) for all i ∈ [m]. We denote the resulting |A|-ary equation by E ρ . If a function f satisfies E, then it also satisfies E ρ , since every evaluation of E ρ is also an evaluation of E. Conversely, if f satisfies E ρ for all ρ ∈ A [m] , then it also satisfies E, since every evaluation of E is an evaluation of some E ρ . Thus every equation E can be translated to a set of |A|-ary equations, i.e., we can always assume m = |A| in (2). As an illustration, let E be the ternary equation

u (f (g 1 (x 1 , x 2 , x 3 )) , f (g 2 (x 1 , x 2 , x 3 ))) = v (f (h (x 1 , x 2 , x 3 )))
with A = {0, 1}. The above procedure would translate E to a set of 8 equations, but actually the three equations u (f (g 1 (y 0 , y 0 , y 1 )) , f (g 2 (y 0 , y 0 , y 1 ))) = v (f (h (y 0 , y 0 , y 1 ))) , u (f (g 1 (y 1 , y 0 , y 0 )) , f (g 2 (y 1 , y 0 , y 0 ))) = v (f (h (y 1 , y 0 , y 0 ))) , u (f (g 1 (y 0 , y 1 , y 0 )) , f (g 2 (y 0 , y 1 , y 0 ))) = v (f (h (y 0 , y 1 , y 0 ))) are sufficient, since for any a ∈ A 3 at least one of a 1 = a 2 , a 2 = a 3 or a 1 = a 3 holds.

In a similar manner, we can also restrict the arities of the outer functions. Indeed, once we have fixed the arities of the inner functions to be m = |A| as above, we have only |A| |A| m n possibilities for the n-tuples of inner functions (g i1 , . . . , g in )

appearing in E, and we can identify those variables of u that carry the same n-tuple of inner functions. . Observe that clones are closed under forming substitution instances of its members where variables are substituted for variables; hence the equations we obtain by performing the replacements of inner and outer functions as described above are still (B, A)equations. Thus, a class is definable by arbitrary (B, A)-equations if and only if it is definable by (B, A)-equations of the form (2) with m = |A| and r = s = |A| n|A| |A| .

A necessary condition for equational definability

In this section we address the question: Which classes of functions are definable by (B, A)-equations? In other words, we consider the following problem: Problem 1. Given two clones A and B, determine necessary and sufficient closure conditions on a class K which guarantee the existence of a defining set of (B, A)equations.

The general solution to this problem eludes us. However, we provide partial results towards a general solution of this problem. To this extent we need to recall some notions concerning certain special clones.

Two functions f :

A n → A and g : A m → A are said to commute, denoted by f ⊥ g, if for all a ij ∈ A (i ∈ [n], j ∈ [m]
), we have f g(a 11 , a 12 , . . . , a 1m ), . . . , g(a n1 , a n2 , . . . , a nm ) = g f (a 11 , a 21 , . . . , a n1 ), . . . , f (a 1m , a 2m , . . . , a nm ) .

The above definition of commutation is illustrated as follows: given any n × m matrix

M =    a 11 • • • a 1m . . . . . . a n1 • • • a nm   
over A, first applying g to the rows of M and then applying f to the resulting column vector yields the same result as first applying f to the columns of M and then applying g to the resulting row vector. Let A ⊆ O A be a class of functions on A. The centralizer of A, denoted by A * , is defined as the set of all functions which commute with every member of A, i.e.,

A * = {g ∈ O A : g ⊥ f for every f ∈ A}.
It is not difficult to verify that A * is a clone for any class A (see, e.g., [START_REF] Hermann | On Boolean primitive positive clones[END_REF][START_REF] Kuznecov | On detecting non-deducibility and non-expressibility, Logical deduction[END_REF][START_REF] Szabó | On the lattice of clones acting bicentrally[END_REF]). A * ) (1) we have f (ϕ (x 1 ) , . . . , ϕ (x n )) ∈ K, and

(B) for every ≥ 0, f 1 , . . . , f ∈ K and Φ ∈ (B * ) ( ) we have Φ (f 1 , . . . , f ) ∈ K.
Proof. Assume that K is definable by (B, A)-equations, and let E be one of the defining equations of K, given in the form [START_REF] Aczél | Functional Equations in Several Variables[END_REF]. For any function f : A n → B and any tuple a ∈ A m , let LHS(f, a) and RHS(f, a) denote the left-hand side and the right-hand side of E, respectively, when evaluated for f = f at a. For the first claim, let f ∈ K, ϕ ∈ (A * ) (1) , and let f : A n → B be defined by

f (x 1 , . . . , x n ) = f (ϕ(x 1 ), . . . , ϕ(x n )).
For a ∈ A m let ϕ(a) := (ϕ(a 1 ), . . . , ϕ(a m )). Since ϕ ⊥ g ij , it holds that

g ij (ϕ(a)) = ϕ(g ij (a)) (i ∈ [r], j ∈ [n]
). Therefore, LHS(f, ϕ(a)) = LHS(f , a). A similar argument shows that RHS(f, ϕ(a)) = RHS(f , a). Since f ∈ K, the equality LHS(f, ϕ(a)) = RHS(f, ϕ(a)) holds for all a ∈ A m . From this it follows that LHS(f , a) = RHS(f , a) for all a ∈ A m . This means that f satisfies E, and we conclude that f ∈ K.

For the second claim, let Φ ∈ (B * ) ( ) , f 1 , . . . , f ∈ K. We need to prove that f := Φ (f 1 , . . . , f ) satisfies E, i.e., that LHS(f , a) = RHS(f , a) for all a ∈ A m . Since f 1 , . . . , f ∈ K, we have LHS(f i , a) = RHS(f i , a) for i = 1, . . . , ; therefore for all a ∈ A m . Let us consider the following × r matrix over B:

   f 1 (g 11 , . . . , g 1n )(a) • • • f 1 (g r1 , . . . , g rn )(a) . . . . . . f (g 11 , . . . , g 1n )(a) • • • f (g r1 , . . . , g rn )(a)    .
Applying Φ to the columns and u to the resulting row vector, we obtain LHS(f , a), whereas applying u to the rows and Φ to the resulting column vector, we obtain Φ(LHS(f 1 , a), . . . , LHS(f , a)). Since Φ ⊥ u, we have

(5) LHS(f , a) = Φ(LHS(f 1 , a), . . . , LHS(f , a)).
A similar argument shows that

(6) RHS(f , a) = Φ(RHS(f 1 , a), . . . , RHS(f , a)).
From ( 4), ( 5), ( 6) it follows that LHS(f , a) = RHS(f , a) for all a ∈ A m . Thus f satisfies E.

Let us note that Example 6 illustrates that the above conditions are also sufficient when B = A is a finite field, and B = L 0 , A = C A . Indeed, in this case A * is the clone of idempotent functions on A, thus (A * ) (1) contains only the identity function, hence f (ϕ(x 1 ), . . . , ϕ(x n )) = f in condition (A) of Proposition 5; this condition holds trivially for any class K. The -ary elements of B * are just the linear functionals on the vector space A , and these are all of the form a 1 x 1 + • • • + a x (a i ∈ A), hence B * = B = L 0 . Therefore, condition (B) of the above proposition expresses the fact that K is closed under linear combinations. As we have seen in Example 6, this condition is necessary and sufficient for definability by (L 0 , C A )-equations.

The next example shows that the two necessary conditions given in Proposition 5 are not always sufficient.

Example 7. Let B = A = {0, 1, 2, 3}, and let υ be the unary function on A defined by υ (0) = υ (1) = υ (2) = 0, υ (3) = 1. Let B be the clone generated by υ, let A be any clone on A, and let K ⊆ O (0)

A consist of the constants 0 and 1. We claim that K satisfies the two conditions of Proposition 5. Indeed, Condition (A) is trivial, as K contains only constants. Condition (B) states that every function Φ ∈ B * preserves the set {0, 1} ⊆ B. This is clear, since {0, 1} is exactly the range of υ. Now let us suppose that K is defined by a set E of (B, A)-equations. Since υ (υ (x)) is constant 0, every function u ∈ B is of the form u (x) = x i , u (x) = υ (x i ) or u (x) = 0. As K contains only nullary functions, inner functions do not appear at all in our (B, A)-equations, therefore, E consists of some of the equations υ (f ) = f , f = 0 and υ (f ) = 0. However, the equations υ (f ) = f and f = 0 both define the set {0}, while υ (f ) = 0 defines the set {0, 1, 2}, hence no combination of these equations can define K = {0, 1}. This shows that K is not definable by (B, A)-equations.

In order to construct an example where the inner functions play a crucial role, let us consider classes K ⊆ B A of unary functions definable by (I B , A)-equations, where A is the clone generated by a given permutation group G ≤ S A . Such an equation is of the form f (g (x)) = f (h (x)) or f (g (x)) = f (h (y)), where g, h ∈ G. Clearly, the latter equation is satisfied only by constant functions. The solutions of f (g (x)) = f (h (x)) are described in the next lemma, for which we need to introduce the following notation. For any permutation g ∈ S A , let π g be the equivalence relation on A whose blocks are the cycles of g (in other words: the orbits of the group generated by g). Lemma 1. A function f : A → B satisfies the equation f (g (x)) = f (h (x)) for given g, h ∈ S A if and only if π hg -1 ⊆ ker f.

Proof. Let us assume that f satisfies f (g (x)) = f (h (x)), and let q = hg -1 . Evaluating the equation at x = g -1 (a) for an arbitrary a ∈ A, we obtain f (a) = f (q (a)).

By iteration, we get f (a) = f q k (a) for any a ∈ A and k ∈ N. If (a, a ) ∈ π hg -1 = π q , then there exists k ∈ N such that a = q k (a), hence we have f (a) = f (a ), i.e., (a, a ) ∈ ker f . Assume now that π q ⊆ ker f , and let a ∈ A. Since q (g (a)) = h (a) , we have (g (a) , h (a)) ∈ π q , hence (g (a) , h (a)) ∈ ker f , and this means that f (g (a)) = f (h (a)) holds for all a ∈ A. Therefore f satisfies the equation f (g (x)) = f (h (x)).

If a class K ⊆ B A is defined by a system of equations f (g i (x)) = f (h i (x)) (i ∈ [t]), then, according to the above lemma, the members of K are exactly those functions f that satisfy each of the conditions π hig -1 i ⊆ ker f (i ∈ [t]). These can be translated into a single condition i∈[t] π hig -1 i ⊆ ker f , where ∨ denotes the join operation in the lattice of equivalence relations (transitive closure of the union). Also, taking into account equations of the form f (g (x)) = f (h (y)), we obtain the following description of classes of unary functions definable by (I B , A)-equations. Proposition 6. Let A be the clone generated by a given permutation group G ≤ S A . Then a class K ⊆ B A is definable by (I B , A)-equations if and only if either K is the class of all constant functions or there exists a subset Q ⊆ G such that

K = f ∈ B A : q∈Q π q ⊆ ker f .
With the help of Proposition 6, we can give another example showing that the conditions of Proposition 5 do not always guarantee definability by (B, A)equations. In contrast to Example 7, here the key role is played by the inner functions.

Example 8. Let A be the clone generated by the alternating group on A = {0, 1, 2, 3}, and let B = I B , where B is an arbitrary set with at least two elements. Then the class K = f ∈ B A : f (0) = f (1) satisfies the two conditions of Proposition 5, but it is not definable by (B, A)-equations. To see this, let us observe that K = f ∈ B A : ϑ ⊆ ker f , where ϑ denotes the equivalence relation on A whose blocks are {0, 1} , {2} , {3}. From Proposition 6 it follows that K is definable by (B, A)-equations if and only if ϑ is the join of some equivalences π q with each q being an even permutation. However, ϑ is an atom in the lattice of equivalence relations on A, hence it is join irreducible. Therefore, if K was definable by (B, A)-equations, then ϑ would be equal to π q for some even permutation q. This is clearly not the case, as the only permutation q with π q = ϑ is the transposition (01), which is an odd permutation. This shows that K is not definable by (B, A)-equations.

To verify that K satisfies the conditions of Proposition 5, let us observe that (A * ) (1) contains only the identity function 1 , hence condition (A) is trivially satisfied.

1 It is straightforward to check that the only unary function commuting with all even permutations is the identity, whenever the underlying set has at least 4 elements. Alternatively, one can use the description of the centralizers of alternating groups given by Machida and Rosenberg [START_REF] Machida | On the centralizers of monoids in clone theory[END_REF].

As I * B = O B , condition (B) is equivalent to condition (7) below, and we will see in Remark 4 that it is satisfied if and only if K is of the form K = f ∈ B A : ϑ ⊆ ker f for some equivalence relation ϑ, which is indeed the case in our example.

A : f (ϕ (x 1 ) , . . . , ϕ (x n )) ∈ K. Lemma 2. A class K ⊆ B A n is definable by (B, I A )-equations if and only if it is definable by (B, O A )-equations and satisfies condition [START_REF] Couceiro | Function classes and relational constraints stable under compositions with clones[END_REF].

Proof. The necessity of the conditions follows from Proposition 5. To prove the sufficiency, let us suppose that K ⊆ B A n is definable by (B, O A )-equations and satisfies [START_REF] Couceiro | Function classes and relational constraints stable under compositions with clones[END_REF]. By Proposition 4, there exists a system E of (B, C A )-equations that defines K, moreover, we may assume that only constant functions appear as inner functions in every equation of E. To simplify notation, in the following we will assume that A = {1, 2, . . . , k}. Let us replace every occurrence of every constant i ∈ A by the i-th k-ary projection x (k) i in every equation of E. This way we obtain a system E of k-ary (B, I A )-equations. We will prove that E defines K.

Assume first that a function f satisfies E . Then the two sides of each equation of E evaluate to the same value for f = f at every a ∈ A k . Choosing a = (1, 2, . . . , k), we get exactly the original equations in E. Therefore f satisfies E, and this implies that f ∈ K. Now let us assume that f ∈ K, and let us evaluate the two sides of an equation in E for f = f at an arbitrary tuple a ∈ A k . Then we obtain the same values as if we evaluated the two sides of the corresponding equation of E for the function f = f (ϕ (x 1 ) , . . . , ϕ (x n )), where ϕ is the unary map defined by ϕ (i) = a i for every i ∈ A. Since K has property (8), f (ϕ (x 1 ) , . . . , ϕ (x n )) ∈ K, hence it satisfies every equation of E. This shows that f satisfies every equation of E . Proof. The necessity of the condition follows from Proposition 5. For the sufficiency, let us assume that K ⊆ B A n satisfies [START_REF] Couceiro | Functional equations, constraints, definability of function classes, and functions of Boolean variables[END_REF], and let f ∈ B A n be an arbitrary function that satisfies every (I B , O A )-equation that is satisfied by all members of K. We will prove that f ∈ K.

Let us choose = |K|, let K = {f 1 , . . . , f }, and for any a ∈ A n let us write F (a) for the -tuple (f 1 (a) , . We claim that this formula gives rise to a well-defined function Φ ∈ O ( ) B . Suppose that b =F (a) = F (a ) for some tuples a, a ∈ A n . Let us consider the functional equation [START_REF] Couceiro | On equational definability of function classes[END_REF] f (a 1 , . . . , a n ) = f (a 1 , . . . , a n ) .

This is an (I B , O A )-equation, since the outer function on both sides is the identity function (i.e., the first unary projection), and the inner functions are constants.

The equality F (a) = F (a ) implies that every element of K satisfies [START_REF] Couceiro | On equational definability of function classes[END_REF]. Therefore, according to our assumption, f satisfies (9) as well. This means that f (a) = f (a ), hence Φ (b) = f (a) = f (a ) is well defined. Since K satisfies condition [START_REF] Couceiro | Functional equations, constraints, definability of function classes, and functions of Boolean variables[END_REF], in order to prove that f ∈ K, it suffices to verify that f = Φ (f 1 , . . . , f ). Indeed, for all a ∈ A n we have Φ (f 1 , . . . , f ) (a) = Φ (F (a)) = f (a) by the definition of Φ. Remark 4. As the proof of Theorem 3 shows, a class K ⊆ B A n satisfies condition [START_REF] Couceiro | Functional equations, constraints, definability of function classes, and functions of Boolean variables[END_REF] if and only if it can be defined by equations of the form (9), i.e., by equations that involve only constants as inner functions (cf. also Proposition 4). A function f satisfies equation ( 9) if and only if f (a) = f (a ), which is equivalent to (a, a ) ∈ ker f . Therefore, the assertion that a given set E of equations of this form is satisfied by a function f is equivalent to the condition R ⊆ ker f , where R is a binary relation on A n (consisting of all pairs (a, a ) that appear in E). If ϑ is the least equivalence relation containing R, then clearly R ⊆ ker f if and only if ϑ ⊆ ker f . Thus a class K ⊆ B A n satisfies (7) if and only if there exists an equivalence relation ϑ on A n such that K = f ∈ B A n : ϑ ⊆ ker f . Theorem 4. A class K ⊆ B A n is definable by (I B , I A )-equations if and only if conditions (7) and (8) hold.

Proof. Follows from Lemma 2 and Theorem 3.

Proposition 2 .

 2 This result can be strengthened for sufficiently large clones B. Indeed, as our next result indicates, if the clone B contains certain functions, then a single (B, A)equation suffices. To this extent, let 0 and 1 be two arbitrary distinct elements of B, and consider analogues of the Boolean conjunction ∧ and equivalence ↔, defined as follows: for a, b ∈ A leta ∧ b = 1, if a = 1 and b = 1; 0, otherwise; a ↔ b = 1, if a = b; 0, otherwise.If clone B contains the operations ∧ and ↔, then a class K ⊆ B A n is definable by (B, A)-equations if and only if it can be defined by a single (B, A)equation.

Proposition 5 .

 5 The clones O A and I A are centralizers of each other: O * A = I A and I * A = O A . The following proposition establishes necessary conditions for a class K to be definable by (B, A)-equations. If a class K ⊆ B A n is definable by (B, A)-equations, then (A) for every f ∈ K and ϕ ∈ (

  (f 1 , a), . . . , LHS(f , a)) = Φ(RHS(f 1 , a), . . . , RHS(f , a))

Remark 3 . 4 .

 34 In light of Remark 2, the conditions of Proposition 5 can be slightly strengthened. Namely, condition (A) must hold for every unary function ϕ that commutes with all |A|-ary members of A, and similarly, in condition (B) it suffices to require that Φ commutes with the |A| n|A| |A| -ary part of B. However, as Examples 7 and 8 show, these stronger necessary conditions are still not sufficient for definability by (B, A)-equations. Characterizations of classes definable by equations induced by the smallest and largest clones In the rest of the paper we show that the necessary conditions presented in Proposition 5 are sufficient when B ∈ {I B , O B } and A ∈ {I A , O A }. As O * B = I B , in the case B = O B condition (B) is satisfied by every class, while for B = I B it takes the form (7) ∀ f 1 , . . . , f ∈ K ∀ Φ ∈ O ( ) B : Φ (f 1 , . . . , f ) ∈ K, since I * B = O B . Similarly, condition (A) is trivial for A = O A , and for A = I A it reads as (8) ∀f ∈ K ∀ϕ ∈ O

Theorem 1 .

 1 Every class K ⊆ B A n is definable by (O B , O A )-equations.Proof. We have seen in Example 5 that {f } is definable for any given f ∈ B A n . Since A and B are finite sets, any class K ⊆ B A n is a finite union of singletons, hence the theorem follows by Proposition 3.

Theorem 2 .

 2 A class K ⊆ B A n is definable by (O B , I A )-equations if and only if it satisfies condition (8).Proof. Follows from Lemma 2 and Theorem 1.

Theorem 3 .

 3 A class K ⊆ B A n is definable by (I B , O A )-equations if and only if it satisfies condition[START_REF] Couceiro | Functional equations, constraints, definability of function classes, and functions of Boolean variables[END_REF].

  . . , f (a)). Let 0 be an arbitrary element of A, and for any b ∈ B let Φ (b) = f (a) , if b = F (a) ; 0, if a ∈ A n : b = F (a) .

  This way we can replace u (and similarly v) by a function of arity at most |A| |A| m n = |A| n|A| |A| , and by adding fictitious variables if necessary, we can actually assume that the arity of u and v is exactly |A|

	n|A| |A|

Acknowledgment

The authors would like to thank Eszter K. Horváth for helpful discussions. The first named author is supported by the internal research project F1R-MTH-PUL-09MRDO of the University of Luxembourg. The third named author acknowledges that the present project is supported by the T ÁMOP-4.2.1/B-09/1/KONV-2010-0005 program of National Development Agency of Hungary, by the Hungarian National Foundation for Scientific Research under grants no. K77409 and K83219, by the National Research Fund of Luxembourg, and cofunded under the Marie Curie Actions of the European Commission (FP7-COFUND).