Miguel Couceiro
email: miguel.couceiro@uni.lu

Erkko Lehtonen
email: erkko.lehtonen@uni.lu

Tamás Waldhauser
email: tamas.waldhauser@uni.lu

GAP vs. PAG

We propose a parametrized version of arity gap. The parametrized arity gap gap(f, ) of a function f : A n → B measures the minimum decrease in the number of essential variables of f when consecutive identifications of pairs of essential variables are performed. We determine gap(f, ) for an arbitrary function f and a positive integer . We also propose other variants of arity gap and discuss further problems pertaining to the effect of identification of variables on the number of essential variables of functions.

I. INTRODUCTION

Let A and B be arbitrary nonempty sets. We investigate a variant of the so-called arity gap of functions f : A n → B. The study of arity gap goes back to the 1963 paper by Salomaa [START_REF] Salomaa | On essential variables of functions, especially in the algebra of logic[END_REF], where he addressed the question how the number of essential variables of a function is affected by substitution of constants for variables or by identification of variables.

The arity gap of a function f : A n → B is defined as the minimum decrease in the number of essential variables when any two essential variables of f are identified, and it is denoted by gap f . Concerning the effect of identifying variables on the number of essential variables, Salomaa's main result asserts that in the case when A = B = {0, 1}, it holds that gap f ≤ 2 for every function f : {0, 1} n → {0, 1} with at least two essential variables. (In fact, it is implicit in Salomaa's work that if |A| = k and |B| ≥ 2, then the arity gap of any function f : A n → B, all variables of which are essential, is at most k, and that there exist functions of arity k for which this upper bound is met.) For background and developments on this topic 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 | The arity gap of order-preserving functions and extensions of pseudo-Boolean functions[END_REF], [START_REF] Couceiro | Decompositions of functions based on arity gap[END_REF], [START_REF] Couceiro | On the arity gap of polynomial functions[END_REF], [START_REF] Shtrakov | On finite functions with non-trivial arity gap[END_REF], [START_REF] Willard | Essential arities of term operations in finite algebras[END_REF].

In this paper we introduce a parametrized version of arity gap which measures the minimum decrease in the number of essential variables when we make ≥ 1 successive identifications of pairs of essential variables. For a function f : A n → B, let gap(f, ) denote this minimum decrease. This parametrized notion extends that of arity gap as gap f = gap(f, 1). Also, it is tightly related to yet another problem which appears naturally when studying the effect of identification of variables on the number of essential variables of functions: Given a function f : A n → B and an integer p ≥ 1, what is the smallest number m such that any m successive identifications of essential variables result in the loss of at least p essential variables? Denoting this smallest number by pag(f, p), it will become clear that pag(f, p) is the smallest such that gap(f, ) ≥ p. This paper is organized as follows. In Section II, we recall basic notions and establish preliminary results concerning the simple minor relation and the arity gap, which will be needed in the later sections. Section III is devoted to the study of the parametrized arity gap. In particular, given sets A and B and positive integers n, p, we explicitly determine the possible sequences gap(f, 1), gap(f, 2), . . . , gap(f, ), . . . , for functions f : A n → B depending on all of their variables such that gap f = p. In Section IV, we briefly discuss some further problems related to the effect of several identifications of essential variables on the number of essential variables of a function, as that mentioned above.

The current study was motivated by the questions and remarks made by Dan A. Simovici at the IEEE 41st International Symposium on Multiple-Valued Logic (ISMVL 2011).

II. PRELIMINARIES A. Functions of several variables and simple minors

For a positive integer n, we will denote [n] := {1, . . . , n}, and we will assume throughout this paper that A and B are arbitrary sets with at least two elements. A function of several variables (or arguments) from A to B is a map f : A n → B for some positive integer n called the arity of f . We denote the set of all finitary functions from A to B by

F AB := n≥1 B A n .
We say that the i-th variable is essential in f : A n → B, or f depends on the i-th variable, if there exist tuples a := (a 1 , . . . , a n ) and b := (b 1 , . . . , b n ) such that a j = b j for all j = i and f (a) = f (b). A variable that is not essential is called inessential. The essential arity of f is defined to be the cardinality of the set

Ess f := {i ∈ [n] : the i-th variable is essential in f }
and is denoted by ess f . If ess f = n, then we say that f is essentially n-ary.

Let f : A n → B and g : A m → B. We say that g is a simple minor of f , and we write g ≤ f , if there exists a map α :

[n] → [m] such that g(a 1 , . . . , a m ) = f (a α(1) , . . . , a α(n) )
for all a 1 , . . . , a m ∈ A. (Informally, g is a simple minor of f , if g can be obtained from f by permutation of variables, addition of inessential variables, deletion of inessential variables, or identification of variables.) Let f : A n → B. For i, j ∈ [n], i = j, the simple minor f i←j : A n → B of f given by the rule f i←j (a 1 , . . . , a n ) = f (a 1 , . . . , a i-1 , a j , a i+1 , . . . , a n ), for all a 1 , . . . , a n ∈ A, is called an identification minor of f , obtained by substituting x j for x i . Note that a j occurs twice on the right-hand side of the above equality while a i does not appear at all. Thus, the i-th variable is necessarily inessential in f i←j .

The simple minor relation ≤ is a quasiorder on F AB . As for quasiorders, ≤ induces an equivalence relation ≡ on F AB . If f ≡ g, then we say that f and g are equivalent. (Informally, f and g are equivalent, if each of f and g can be obtained from the other by permutation of variables, addition of inessential variables, and deletion of inessential variables.) Remark 1. If f ≡ g, then ess f = ess g. Every nonconstant function is equivalent to a function that depends on all of its variables.

If g ≤ f but f ≡ g, then we write g < f and say that g is a strict minor of f . If g < f but there is no h such that g < h < f , then we say that g is a lower cover of f and denote this fact by g ≺ f or, equivalently, by f g. Remark 2. It was shown in [START_REF] Bouaziz | Join-irreducible Boolean functions[END_REF] that the lower covers of any function f : A n → B have the same essential arity when A = B = {0, 1}. The proof of this fact given in [START_REF] Bouaziz | Join-irreducible Boolean functions[END_REF] actually shows that this claim is true whenever |A| = 2 and |B| ≥ 2. However, this is not the case when |A| > 2.

To this extent, let A be a set with at least three elements, let B be a set with at least two elements, and assume that 0 and 1 are distinct elements of B. Let ν : A 2 → B be the inequality predicate

ν(x, y) = 1, if x = y, 0, if x = y,
and let ∧ : B 2 → B and ∨ : B 2 → B be arbitrary extensions of the Boolean conjunction and disjunction to B (i.e., arbitrary binary operations on B satisfying 0

∧ 0 = 0 ∧ 1 = 1 ∧ 0 = 0, 1 ∧ 1 = 1, 0 ∨ 0 = 0, 1 ∨ 0 = 0 ∨ 1 = 1 ∨ 1 = 1). Consider the function f : A 4 → B defined by f (a 1 , a 2 , a 3 , a 4 ) := ν(a 1 , a 2 ) ∨ 1≤i<j≤4 (i,j) =(1,2) ν(a i , a j ), for all (a 1 , a 2 , a 3 , a 4 ) ∈ A 4 . It is easy to see that f i←j (a 1 , a 2 , a 3 , a 4 ) = ν(a 1 , a 2 ) for 1 ≤ i < j ≤ 4, (i, j) = (1, 2), and
f 1←2 (a 1 , a 2 , a 3 , a 4 ) = 2≤i<j≤4 ν(a i , a j ).
Furthermore, ess f = 4, ess f 1←2 = 3, ess f i←j = 2, and

f 1←2 ≤ f i←j ≤ f 1←2 , for every 1 ≤ i < j ≤ 4, (i, j) =
(1, 2). Hence, f has two lower covers of different essential arities.

For background on the simple minor relation and its variants, see [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] Lehtonen | Descending chains and antichains of the unary, linear, and monotone subfunction relations[END_REF], [START_REF] Lehtonen | Equivalence of operations with respect to discriminator clones[END_REF], [START_REF] Pippenger | Galois theory for minors of finite functions[END_REF], [START_REF] Wang | Boolean minors[END_REF], [START_REF] Zverovich | Characterizations of closed classes of Boolean functions in terms of forbidden subfunctions and Post classes[END_REF].

We say that f is totally symmetric, if for all permutations π of [n] the identity f (a 1 , . . . , a n ) = f (a π(1) , . . . , a π(n) ) holds for all a 1 , . . . , a n ∈ A. Observe that a totally symmetric function depends on either all or none of its variables.

Fact 1. If f : A n → B is totally symmetric, then for all i, j, i , j ∈ [n] (i = j, i = j ), f i←j ≡ f i ←j . Therefore, if f is nonconstant, then for all distinct i, j ∈ [n],
f i←j is, up to equivalence, the unique lower cover of f .

B. Functions determined by supp and oddsupp

Following Berman and Kisielewicz [START_REF] Berman | On the number of operations in a clone[END_REF], we define supp : n≥1 A n → P(A) and oddsupp :

n≥1 A n → P(A) as supp(a 1 , . . . , a n ) := {a 1 , . . . , a n }, oddsupp(a 1 , . . . , a n ) := {a ∈ A : |{i ∈ [n] : a i = a}| is odd}.
We say that f : A n → B is determined by supp (respectively, determined by oddsupp), if there exists a function ϕ :

P(A) → B such that f = ϕ • supp | A n (respectively, f = ϕ•oddsupp | A n ).
Note that every function determined by supp or oddsupp is totally symmetric; hence such a function either depends on all of its variables or on none of them. However, not every totally symmetric function is determined by supp or oddsupp.

Remark 3. For any positive integer n, let us define the following subsets of P(A):

P ≤n (A) := {S ⊆ A : 1 ≤ |S| ≤ n}, P ≤n (A) := {S ⊆ A : |S| ∈ {n, n -2, . . .}}.
Clearly, {supp(x) : x ∈ A n } = P ≤n (A), therefore the restriction of ϕ : P(A) → B to P ≤n (A) uniquely determines the function ϕ • supp | A n , and vice versa. Similarly, we have {oddsupp(x) : x ∈ A n } = P ≤n (A), and consequently there is a one-to-one correspondence between functions f : A n → B determined by oddsupp and maps ϕ :

P ≤n (A) → B. In particular, ϕ • supp | A n (resp. ϕ • oddsupp | A n ) is constant if and only if ϕ| P ≤n (A) (resp. ϕ| P ≤n (A)
) is constant, and has essential arity n otherwise.

Example 2. Every constant function and every unary function is determined by both supp and oddsupp. Furthermore, for each 2 ≤ n ≤ |A|, there are nonconstant functions f : A n → B that are determined by both supp and oddsupp. For instance, let a and b be distinct elements of B and define

f : A n → B by the rule f (a 1 , . . . , a n ) := a if a i = a j for all i = j, b otherwise. It is easy to see that f = φ • supp | A n = φ • oddsupp | A n , where φ : P(A) → B is the map φ(S) := a if |S| = n, b otherwise.
Our next result shows that, in fact, such nontrivial examples of functions determined by both supp and oddsupp can only be found among functions with small arities. Proposition 3. If n > |A|, then f : A n → B is determined by both supp and oddsupp if and only if f is a constant function.

As it will become clear from Propositions 4 and 7 below, if a nonconstant function f is determined by oddsupp (supp, respectively) then every simple minor of f is equivalent to a function that is determined by oddsupp (supp, respectively).

f = f n f n-2 • • • f n-2t-2 f n-2t
of length t such that ess f n-2i = n-2i for all i < t. Moreover, we either have ess f n-2t = 1 and t = n-1

2 or ess f n-2t = 0 and n-k 2 < t ≤ n 2 .
In the following two examples we construct for all possible values of k, n and t a function determined by oddsupp whose simple minors form a chain as stated in Proposition 4, thereby showing that this result cannot be sharpened.

ϕ(S) := 1 if |S| ≥ s, 0 if |S| < s,
where 0 and 1 denote two distinct elements of B. For every 0 ≤ i ≤ t, let f n-2i : A n-2i → B be the function determined by oddsupp via ϕ, i.e., let

f n-2i = ϕ • oddsupp | A n-2i
. It is straightforward to verify with the help of Remark 3 that

f n-2t = f s-2 is constant, and that ess f n-2i = n -2i if i < t. Moreover, for i < t, the unique lower cover of f n-2i is f n-2i-2 .
Thus the simple minors of f n form a chain exactly as in (the second case of) Proposition 4.

Example 6. Let k, n, t be positive integers such that k ≥ 2 and t = n-1 2 . Let A be a set with k elements, let B be a set with at least two elements, and let ϕ : P(A) → B be any function that is not constant on singletons, i.e., there exist a 1 , a 2 ∈ A such that ϕ({a 1 }) = ϕ({a 2 }). For every odd number r, let f r : A r → B be the function determined by oddsupp via ϕ, i.e., let f r = ϕ • oddsupp | A r . Then f r is not constant, hence ess f r = r, and the unique lower cover of f r is f r-2 . Thus the simple minors of f n form a chain exactly as in (the first case of) Proposition 4.

Reasoning as above, by making use of Remark 3, we have the following analogue of Proposition 4. Proposition 7. Let A and B be finite nonempty sets, and let k := |A|. If f : A n → B is a nonconstant function determined by supp, then the simple minors of f form a chain

f = f n f n-1 • • • f n-t+1 f n-t
of length t such that ess f n-i = n -i for all i < t. Moreover, we either have ess f n-t = 1 and t = n -1, or ess f n-t = 0 and n -k < t < n.

As for functions determined by oddsupp, we can find functions which fall into each of the two possible cases provided in Proposition 7.

C. Arity gap

Let f : A n → B be a function that depends on at least two variables, i.e., ess f ≥ 2. The arity gap of f , denoted gap f , is defined as

gap f := min i,j∈Ess f i =j (ess f -ess f i←j ).
While f i←j is not necessarily a lower cover of f in the simple minor quasiorder, every lower cover of f is of the form f i←j . Therefore, we could define the arity gap of f in an equivalent way as gap f := min g≺f (ess f -ess g).

Whenever we consider the arity gap of a function f : A n → B, we may assume, without loss of generality, that f depends on all of its variables (see Remark 1). As made apparent by Willard [START_REF] Willard | Essential arities of term operations in finite algebras[END_REF], the notion of arity gap is tightly related to determinability by supp and oddsupp. The following statements are immediate consequences of Propositions 4 and 7.

Corollary 8. Let

f : A n → B, n > |A|, be nonconstant. (1) If f is determined by oddsupp, then gap f = 2. (2) If f is determined by supp, then gap f = 1.
We now recall a noteworthy result about the arity gap.

Theorem 9 (Willard [START_REF] Willard | Essential arities of term operations in finite algebras[END_REF]). Let A and B be finite nonempty sets, and let k := |A|. Suppose that f : A n → B depends on all of its variables. If n > k, then gap f ≤ 2. Moreover, if n > max(k, 3), then gap f = 2 if and only if f is determined by oddsupp.

III. PARAMETRIZED ARITY GAP

In this section we are interested in a parametrized version of arity gap which measures the minimum decrease in the essential arity when we take ≥ 0 steps downwards in the simple minor quasiorder. Let f : A n → B, and let ↓ 0 f := {f }, and for ≥ 1, let

↓ f := {g ∈ F AB | ∃f 1 , . . . , f -1 : f f 1 • • • f -1 g}.
If ↓ f = ∅, then we define gap(f, ) := min g∈↓ f (ess f -ess g).

(1)

Note that gap(f, ) is defined only if there exists a chain of length below f , and in this case ≤ gap(f, ) ≤ ess f . The arity gap (as defined in Section II-C) corresponds to the case = 1, that is, gap(f, 1) = gap f for every function f . Observe also that gap(f, 0) = 0 for every function f .

We saw in Section II-A that taking a strict minor of a function f requires the identification of at least one pair of essential variables of f ; otherwise, the minors we obtain are equivalent to f . This means that gap(f, ) can be computed by sequentially identifying a pair of essential variables times in all possible ways, starting from f , and then determining the sequence of identifications which results in the minimum loss of essential variables.

Remark 4. It is worth stressing the fact that the identification of variables is performed sequentially, and at each step only one pair of essential variables is identified; otherwise, ambiguities could occur since a priori we do not know which essential variables become inessential after a pair is identified.

We mentioned in Section II-C that not every identification minor f i←j is a lower cover of f , and if f i←j is not a lower cover of f , then gap f < ess f -ess f i←j . Moreover, it can be the case that f has two lower covers f 1 and f 2 such that ess f 1 < ess f 2 , and again we would conclude that gap f < ess f -ess f 1 . Hence, one might be led to thinking that in order to compute gap(f, ) it suffices to choose at each recursion step an identification which results in the minimum loss of essential variables. However, as the following example illustrates, this is not true.

Example 10. Let A be the 5-element field and consider the function f : A 6 → A represented by the polynomial

(x 1 -x 2 )(x 5 -x 6 ) + 1≤i<j≤6 (i,j) =(5,6) (x i -x j ).
It is easy to verify that ess f = 6, f 1←2 ≡ 0, and that f has, up to equivalence, two lower covers, namely,

f 1←3 = (x 1 -x 2 ) • (x 5 -x 6 ), f 5←6 = 1≤i<j≤4 (x i -x j ) • 1≤i≤4 (x i -x 5 ) 2 .
Figure 1 presents the Hasse diagram of the principal ideal generated by the equivalence class of f in the simple minor poset. The label of each edge g ≺ h is the number ess h-ess g. We use the following notation for simple minors of f :

q 1 = 1≤i<j≤4 (x i -x j ) • 1≤i≤4 (x i -x 5 ) 2 , q 2 = (x 1 -x 2 ) • (x 3 -x 4 ), q 3 = (x 1 -x 2 ) • (x 1 -x 3 ), q 4 = (x 1 -x 2 ) • (x 2 -x 3 ), q 5 = (x 1 -x 2 ) 2 , q 6 = -(x 1 -x 2 ) 2 .
Now if we would choose as our first identification the pair {5, 6}, then any other identification of essential variables results in the loss of all the remaining essential variables. In other words, any downward path in Figure 1 which starts from f and passes through q 1 has length 2, and along it we first lose 1 and then 5 essential variables. However, the downward paths that start from f and pass through q 2 have length 4, and along them we lose 2, 1, 1, and then 2 essential variables. This shows that, in order to compute gap(f, 1) as in (1), the minimum value is attained at the lower cover q 1 , whereas, for 2 ≤ ≤ 4, we need to pass through q 2 for computing gap(f, ). Hence, gap(f, 0) = 0, gap(f, 1) = 1, gap(f, 2) = 3, gap(f, 3) = 4, and gap(f, 4) = 6.

The following recursion formula is an immediate consequence of the definition: gap(f, ) = min g≺f (ess f -ess g + gap(g, -1)).

( Informally speaking, Theorem 11 means that if gap f = 1, then we can walk down from f in the simple minor quasiorder in such a way that in each step we lose only one essential variable, provided that the walk is not too long. The next result asserts that if we consider arbitrarily long walks, then we can lose any number of essential variables. More precisely, for each 2 ≤ ≤ q ≤ n we can find a function f with gap f = 1 and gap(f, ) = q. Theorem 12. For every 2 ≤ ≤ q ≤ n, there exist sets A and B and a function f : A n → B such that ess f = n, gap f = 1, gap(f, ) = q, |A| < n.

Next we consider the analogue of Theorem 11 for the case gap f = 2. Theorem 13. Let A and B be finite nonempty sets, and let k := |A|. Let f :

A n → B, ess f = n and gap f = 2. If 1 ≤ ≤ n-k 2 , then gap(f, ) = 2 .
The following result makes explicit the fact that, for almost every integer sequence 0

= n 0 < n 1 < n 2 < • • • < n r ≤ n,
we can find a function f : A n → B whose parametrized arity gap meets every member of the sequence. Theorem 14. Let A be a finite set with k elements and let B be a set with at least two elements. Let

2 ≤ n ≤ k, 1 ≤ r ≤ n-1, 0 = n 0 < n 1 < n 2 < • • • < n r ≤ n such that n -1 ≤ n r ≤ n and n r-1 = n -1.
Then there exists a function f : A n → B such that gap(f, ) = n for every 0 ≤ ≤ r.

Note that the condition n r-1 = n -1 is necessary, because no function has both an essentially unary function and a constant function as its simple minors.

IV. CONCLUDING REMARKS

As mentioned in Section I, the parametrized arity gap constitutes a tool for tackling yet another natural problem pertaining to the effect of variable identification on the number of essential variables of a function. Given a function f : A n → B and an integer p ≥ 1, what is the smallest number m such that any m successive identifications of essential variables result in the loss of at least p essential variables? Let us denote this smallest number by pag(f, p). As already mentioned in the introduction, pag(f, p) is indeed the smallest such that gap(f, ) ≥ p. We may also consider similar problems when we perform several simultaneous identifications of variables. Following the formalism of Willard [START_REF] Willard | Essential arities of term operations in finite algebras[END_REF], we view functions of several variables as maps f : A V → B, where V ⊆ {x i : i ∈ N}. The cardinality of V is called the arity of f . In this framework, a function g :

A W → B is a simple minor of f : A V → B, if there exists a map α : V → W such that g(a) = f (a • α) for all a ∈ A W .
We denote the set of all equivalence relations on a set V by Eq(V ). Given an equivalence relation θ ∈ Eq(V ), denote the canonical surjection by v θ : V → V /θ. For a function f : A V → B, we define the function f θ : A V /θ → B by f θ (a) = f (a • v θ ), and we say that f θ is obtained from f by block identification of variables through θ. We informally identify V /θ with any one of its distinct representatives; in this way f θ is a simple minor of f , and every simple minor of f is equivalent to f ψ for some ψ ∈ Eq(V ). The number of variables identified through θ is

Proposition 4 .

 4 Let A and B be finite nonempty sets, and let k := |A|. If f : A n → B is a nonconstant function determined by oddsupp, then the simple minors of f form a chain

Example 5 . 2 < t ≤ n 2 .

 522 Let k, n, t be positive integers such that k ≥ 2 and n-k Then s := n -2t + 2 satisfies the inequalities 2 ≤ s ≤ k. Let A be a set with k elements, let B be a set with at least two elements, and let us define ϕ : P(A) → B by

Fig. 1 .

 1 Fig. 1. The simple minors of the function f given in Example 10.

) Theorem 11 .

 11 Let A and B be finite nonempty sets, and let k := |A|. Let f : A n → B, ess f = n and gap f = 1. If 1 ≤ ≤ n -max(k, 3), then gap(f, ) = .

Example 15 .

 15 Consider the 6-ary function f of Example 10. We can read off of Figure 1 that pag(f, 1)

Example 17 .

 17 e(θ) := X∈V /θ (|X| -1) = |V | -|V /θ|. Assuming that f depends on all of its variables, i.e., ess f = |V |, we have that ess f θ ≤ |V /θ| = |V | -e(θ) = ess f -e(θ). Now we can define the analogue of the parametrized arity gap for block identification of variables. For a function f : A V → B with ess f = |V | = n and for an integer such that 0 ≤ ≤ n -1, we define b-gap(f, ) := min θ∈Eq(V ) e(θ)=(ess f -ess f θ ).Note that if e(θ) = 0, then θ is the trivial equivalence relation {(x, x) : x ∈ V }; hence b-gap(f, 0) = 0. Note also that b-gap(f, 1) = gap f for every function f . It is also clear that ≤ b-gap(f, ) ≤ n for every 0 ≤ ≤ n -1, and b-gap(f, ) ≤ gap(f, ) for every for which gap(f, ) is defined.Let H(f) := {ess f -ess g : g ≤ f }. It is clear that {b-gap(f, ) : 0 ≤ ≤ n -1} ⊆ H(f ). Moreover, if f : A V → B is a function such that ess f = |V | = n, then b-gap(f, ) = min{m ∈ H(f ) : m ≥ }, for every 0 ≤ ≤ n -1.Example 16. Consider the 6-ary function f of Example 10. We can read off of Figure 1 that H(f ) = {1, 2, 3, 4, 6} and b-gap(f, 1) = 1, b-gap(f, 2) = 2, b-gap(f, 3) = 3, b-gap(f, 4) = 4, b-gap(f, 5) = 6. We can still consider an analogue of the problem stated in the first paragraph of this section. Given a function f : A V → B that depends on all of its variables and an integer p ≥ 1, what is the smallest number m such that block identification of variables of f through every equivalence relation θ on V with e(θ) = m results in the loss of at least p essential variables? Let us denote this smallest number by b-pag(f, p). It is again clear that b-pag(f, p) is the smallest such that b-gap(f, ) ≥ p. Consider the 6-ary function f of Example 10. We can determine from the values of b-gap(f, ) listed in Example 16, or we can easily read off of Figure 1 that b-pag(f, 1) = 1, b-pag(f, 2) = 2, b-pag(f, 3) = 3, b-pag(f, 4) = 4, b-pag(f, 5) = 5, b-pag(f, 6) = 5.

ACKNOWLEDGMENTS

The first named author is supported by the internal research project F1R-MTH-PUL-12RDO2 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 the 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).


Miguel Couceiro
email: miguel.couceiro@uni.lu

Jean-Luc Marichal
email: jean-luc.marichal@uni.lu

Tam Ás Waldhauser
email: tamas.waldhauser@uni.lu

Hierarchies of local monotonicities and lattice derivatives for Boolean and pseudo-Boolean functions

>IJH=?JIn this paper we report recent results in [1] concerning local versions of monotonicity for Boolean and pseudo-Boolean functions: say that a pseudo-Boolean (Boolean) function is p-locally monotone if each of its partial derivatives keeps the same sign on tuples which differ on less than p positions. As it turns out, this parameterized notion provides a hierarchy of monotonicities for pseudo-Boolean (Boolean) functions.

Local monotonicities are tightly related to lattice counterparts of classical partial derivatives via the notion of permutable derivatives. More precisely, p-locally monotone functions have p-permutable lattice derivatives and, in the case of symmetric functions, these two notions coincide. We provide further results relating these two notions, and present a classication of plocally monotone functions, as well as of functions having ppermutable derivatives, in terms of certain forbidden sections, i.e., functions which can be obtained by substituting variables for constants. This description is made explicit in the special case when p = 2.

I. INTRODUCTION Throughout this paper, let

[n] = {1, . . . , n} and B = {0, 1}. We are interested in the so-called Boolean functions f : B n → B and pseudo-Boolean functions f : B n → R, where n denotes the arity of f . The pointwise ordering of functions is denoted by ≤, i.e., f ≤ g means that f (x) ≤ g(x) for all x ∈ B n . The negation of x ∈ B is dened by x = x ⊕ 1, where ⊕ stands for addition modulo 2. For x, y ∈ B, we set x ∧ y = min(x, y) and x ∨ y = max(x, y).

For k ∈ [n], x ∈ B n , and a ∈ B, let x a k be the tuple in B n whose i-th component is a, if i = k, and x i , otherwise. We use the shorthand notation x ab jk for (x a j ) b k = (x b k ) a j . More generally, for S ⊆ [n], a ∈ B n , and x ∈ B S , let a x S be the tuple in B n whose i-th component is x i , if i ∈ S, and a i , otherwise.

Let i ∈ [n] and f : B n → R. A variable x i is said to be essential in f , or that f depends on x i , if there exists a ∈ B n such that f (a 0 i ) = f (a 1 i ). Otherwise, x i is said to be inessential in f . Let S ⊆ [n] and f : B n → R. We say that g : B S → R is an S-section of f if there exists a ∈ B n such that g(x) = f (a x S ) for all x ∈ B S (observe that the components a i are irrelevant for i ∈ S). By a section of f we mean an S-section of f for some S ⊆ [n], i.e., any function which can be obtained from f by replacing some of its variables by constants.

The (discrete) partial derivative of f : B n → R with respect to its k-th variable is the function Δ k f : B n → R dened by

Δ k f (x) = f (x 1 k ) -f (x 0
k ); see [START_REF] Foldes | Submodularity, supermodularity, and higherorder monotonicities of pseudo-Boolean functions[END_REF], [START_REF] Grabisch | Equivalent representations of set functions[END_REF]. Note that Δ k f does not depend on its k-th variable, hence it could be regarded as a function of arity n -1, but for notational convenience we dene it as an n-ary function.

A pseudo-Boolean function f : B n → R can always be represented by a multilinear polynomial of degree at most n (see [START_REF] Hammer | Boolean methods in operations research and related areas[END_REF]), that is,

f (x) = S⊆[n]
a S i∈S x i , [START_REF] Couceiro | Locally monotone Boolean and pseudo-Boolean functions[END_REF] where a S ∈ R. For instance the multilinear expression for a binary pseudo-Boolean function is given by

a 0 + a 1 x 1 + a 2 x 2 + a 12 x 1 x 2 . ( 2
)
This representation is very convenient for computing the partial derivatives of f . Indeed, Δ k f can be obtained by applying the corresponding formal derivative to the multilinear representation of f . Thus, from (1), we obtain immediately

Δ k f (x) = S k a S i∈S\{k} x i . (3) We say that f is isotone (resp. antitone) in its k-th variable if Δ k f (x) ≥ 0 (resp. Δ k f (x) ≤ 0) for all x ∈ B n . If f
is either isotone or antitone in its k-th variable, then we say that f is monotone in its k-th variable. If f is isotone (resp. antitone, monotone) in all of its variables, then f is an isotone (resp. antitone, monotone) function. It is clear that any section of an isotone (resp. antitone, monotone) function is also isotone (resp. antitone, monotone).

Thus dened, a function f : B n → R is monotone if and only if each of its partial derivatives has the same sign on B n . In this paper we are interested in some parameterized relaxations of monotonicity: a function f : B n → R is plocally monotone if each of its partial derivatives has the same sign on tuples which differ on less than p positions. As we will see, these relaxations are tightly related to the following lattice versions of partial derivatives. For f :

B n → R and k ∈ [n], let ∧ k f : B n → R and ∨ k f : B n → R be the partial lattice derivatives dened by ∧ k f (x) = f (x 0 k ) ∧ f (x 1 k ) and ∨ k f (x) = f (x 0 k ) ∨ f (x 1 k ).
The latter, known as the k-th join derivative of f , was proposed by Fadini [START_REF] Fadini | Operatori che estendono alle algebre di Boole la nozione di derivata. (Italian)[END_REF] while the former, known as the k-th meet derivative of f , was introduced by Thayse [START_REF] Thayse | Disjunctive and conjunctive operators for Boolean functions[END_REF]. In [START_REF] Thayse | Meet and join derivatives and their use in switching theory[END_REF] these lattice derivatives were shown to be related to so-called prime implicants and implicates of Boolean functions which play an important role in the consensus method for Boolean and pseudo-Boolean functions. For further background and applications see, e.g., [START_REF] Crama | Boolean Functions: Theory, Algorithms, and Applications (Encyclopedia of Mathematics and its Applications)[END_REF], [START_REF] Davio | Discrete and switching functions[END_REF], [START_REF] Foldes | Disjunctive and conjunctive normal forms of pseudo-Boolean functions[END_REF], [START_REF] Posthoff | Logic functions and equations: binary models for computer science[END_REF], [START_REF] Thayse | Boolean Calculus of Differences[END_REF].

Observe that, just like in the case of the partial derivative Δ k f , the k-th variable of each of the lattice derivatives ∧ k f and ∨ k f is inessential.

The following proposition assembles some basic properties of lattice derivatives. Proposition 1. For any pseudo-Boolean functions f, g :

B n → R and j, k ∈ [n], j = k, the following hold: (i) ∧ k ∧ k f = ∧ k f and ∨ k ∨ k f = ∨ k f ; (ii) if f ≤ g, then ∧ k f ≤ ∧ k g and ∨ k f ≤ ∨ k g; (iii) ∧ j ∧ k f = ∧ k ∧ j f and ∨ j ∨ k f = ∨ k ∨ j f ; (iv) ∨ k ∧ j f ≤ ∧ j ∨ k f .
From equations (1) and (3) it follows that every function is (up to an additive constant) uniquely determined by its partial derivatives. As it turns out, this does not hold when the lattice derivatives are considered. However, as we shall see, there are only two types of such exceptions (see Theorem 22). Now, if an n-ary pseudo-Boolean function is 2-locally monotone, then for every j, k ∈ [n], j = k, we have Lemma 10 below). This motivates the notion of permutable lattice derivatives. As it turns out, plocal monotonicity of f implies permutability of p of its lattice derivatives (see Theorem 21). However the converse does not hold; see Example 24.

∨ k ∧ j f = ∧ j ∨ k f (see
The structure of this paper goes as follows. In Section II we formalize the notion of p-local monotonicity. As it turns out, this notion gives rise to a hierarchy of monotonicities whose largest member is the class of all n-ary pseudo-Boolean functions (this is the case when p = 1) and whose smallest member is the class of n-ary monotone functions (this is the case when p = n). We also provide a characterization of plocally monotone functions in terms of forbidden sections; this characterization is made explicit in the special case when p = 2. In Section III we introduce the notion of permutable lattice derivatives. Similarly to local monotonicity, the notion of permutable lattice derivatives gives rise to nested classes, each of which is also described in terms of its sections. In the Boolean case and for p = 2, these two parameterized notions coincide; this does not hold for pseudo-Boolean functions even when p = 2 (see Example 12). However, in the case of symmetric functions, the notion of being p-locally monotone is equivalent to that of having p-permutable lattice derivatives; see Section IV. In the last section we discuss directions for future research.

II. LOCAL MONOTONICITIES

The following denition formulates a local version of monotonicity, where Δ k f (x) and Δ k f (y) are required to have the same sign only for tuples x, y which are close to each other with respect to the Hamming distance. In what follows we assume that p ∈ [n].

Denition 2. We say that f :

B n → R is p-locally monotone if, for every k ∈ [n] and every x, y ∈ B n , we have i∈[n]\{k} |x i -y i | < p ⇒ Δ k f (x) Δ k f (y) ≥ 0.
Any p-locally monotone pseudo-Boolean function is also plocally monotone for every p ≤ p. Every function f : B n → R is 1-locally monotone, and f is n-locally monotone if and only if it is monotone. Thus p-local monotonicity is a relaxation of monotonicity, and the nested classes of p-locally monotone functions for p = 1, . . . , n provide a hierarchy of monotonicities for n-ary pseudo-Boolean functions. The weakest nontrivial condition is 2-local monotonicity, therefore we will simply say that f is locally monotone whenever f is 2-locally monotone. If f is p-locally monotone for some p < n but not (p + 1)-locally monotone, then we say that f is exactly p-locally monotone, or that the degree of local monotonicity of f is p.

If f : B n → B is a Boolean function, then Δ k f (x) ∈ {-1, 0, 1} for all x ∈ B n , hence the condition Δ k f (x) Δ k f (y) ≥ 0 in the denition of p-local monotonicity is equivalent to |Δ k f (x) -Δ k f (y)| ≤ 1. (4)
From this it follows that a Boolean function f : B n → B is locally monotone if and only if

Δ k f (x) -Δ k f (y) ≤ i∈[n]\{k} |x i -y i |.
(5) (see [START_REF] Marichal | Aggregation on nite ordinal scales by scale independent functions[END_REF]Lemma 5.1] for a proof of (5) in a slightly more general framework). In a sense, the latter identity means that

Δ k f is 1-Lipschitz continuous.
The following proposition is just a reformulation of the denition of p-local monotonicity.

Proposition 3. A function f : B n → R is p-locally monotone if and only if, for every k ∈ [n], S ⊆ [n]\{k}, with |S| = p-1,
and every a ∈ B n , x, y ∈ B S , we have

Δ k f (a x S ) Δ k f (a y S ) ≥ 0. (6)
In [START_REF] Gotsman | Spectral properties of threshold functions[END_REF], local monotonicity is used to refer to Boolean functions which are monotone (i.e., isotone or antitone in each variable).

As a special case, we have that f : B n → R is locally monotone if and only if, for every j, k ∈ [n], j = k, and every

x ∈ B n Δ k f (x 0 j ) Δ k f (x 1 j ) ≥ 0. (7)
By using (4), we see that, for Boolean functions f : B n → B, the inequality ( 7) can be replaced with

|Δ jk f (x)| ≤ 1,
where

Δ jk f (x) = Δ j Δ k f (x) = Δ k Δ j f (x).
Example 4. The binary Boolean sum

f 1 (x 1 , x 2 ) = x 1 ⊕ x 2 = x 1 + x 2 -2x 1 x 2
and the binary Boolean equivalence

f 2 (x 1 , x 2 ) = f 1 (x 1 , x 2 ) = x 1 ⊕ x 2 ⊕ 1 = 1 -x 1 -x 2 + 2x 1 x 2
are not locally monotone. Indeed, we have

|Δ 12 f 1 (x 1 , x 2 )| = |Δ 12 f 2 (x 1 , x 2 )| = 2.
Example 5. Consider the ternary Boolean function f : B 3 → B given by

f (x 1 , x 2 , x 3 ) = x 1 -x 1 x 2 + x 2 x 3 . Since Δ 2 f may change in sign (Δ 2 f (x) = x 3 -x 1 ), the function f is not monotone. However, f is locally monotone since |Δ 12 f (x)| = 1, |Δ 13 f (x)| = 0, and |Δ 23 f (x)| = 1.
Thus f is exactly The next theorem gives a characterization of p-locally monotone functions in terms of their sections. Theorem 7. A function f : B n → R is p-locally monotone if and only if every p-ary section of f is monotone.

By combining [START_REF] Gotsman | Spectral properties of threshold functions[END_REF] with Theorem 7, we can easily verify the following corollary. Corollary 8. A function f : B n → R is locally monotone if and only if every binary section (2) of f satises a 1 (a 1 + a 12 ) ≥ 0 and a 2 (a 2 + a 12 ) ≥ 0.

Since every binary Boolean function is monotone except for x ⊕ y and x ⊕ y ⊕ 1, we also obtain the following corollary. Corollary 9. A Boolean function f : B n → B is locally monotone if and only if neither x ⊕ y nor x ⊕ y ⊕ 1 is a section of f .

III. PERMUTABLE LATTICE DERIVATIVES

The aim of this section is to relate commutation of lattice derivatives to p-local monotonicity. The starting point is the following result.

Lemma 10. If f : B n → R is locally monotone, then ∨ k ∧ j f = ∧ j ∨ k f for all j, k ∈ [n], j = k.
As we will see in Example 12, Lemma 10 cannot be strengthened to an equivalence. However, the converse of Lemma 10 also holds in the case of Boolean functions.

Theorem 11. A Boolean function

f : B n → B is locally monotone if and only if ∨ k ∧ j f = ∧ j ∨ k f holds for all j, k ∈ [n], j = k.
Example 12. Let f be the binary pseudo-Boolean function dened by f (0, 0) = 1, f (0, 1) = 4, f (1, 0) = 2 and f (1, 1) = 3. Then we have

∨ 2 ∧ 1 f = ∧ 1 ∨ 2 f = 3 and ∨ 1 ∧ 2 f = ∧ 2 ∨ 1 f = 2. However, f is not locally monotone since Δ 1 f (x 0 2 )Δ 1 f (x 1 2 ) = -1.
The above results motivate the following notion of permutability of lattice derivatives, and its relation to local monotonicities. Denition 13. We say that a pseudo-Boolean function f : B n → R has p-permutable lattice derivatives if, for every p-subset {k 1 , . . . , k p } ⊆ [n], every choice of the operators O ki ∈ {∧ ki , ∨ ki } (i = 1, . . . , p), and every permutation π ∈ S p , the following identity holds:

O k1 • • • O kp f = O k π(1) • • • O k π(p) f.
If f : B n → R has n-permutable lattice derivatives, then we simply say that f has permutable lattice derivatives.

Every function f : B n → R has 1-permutable lattice derivatives. We will see in Theorem 23 that if a function f : B n → R has p-permutable lattice derivatives, then it also has p -permutable lattice derivatives for every p ≤ p. Fact 14. A function f : B n → R has p-permutable lattice derivatives if and only if so has αf + β for every α, β ∈ R, with α = 0. The same holds for any function obtained from f by negating some of its variables. Fact 15. A function f : B n → R has p-permutable lattice derivatives if and only if every p-ary section of f has permutable lattice derivatives.

In the particular case when p = 2, we have the following description of functions having

Corollary 20. Let 0 ≤ ℓ < p ≤ n. If f : B n → R is p-locally monotone, then, for any ℓ-subset {k 1 , . . . , k ℓ } ⊆ [n] and every choice of the operators O ki ∈ {∨ ki , ∧ ki } (i = 1, . . . , ℓ), the function O k1 • • • O k ℓ f is (p -ℓ)-locally monotone. In particular, if ℓ ≤ p-2, then O k1 • • • O k ℓ f is locally monotone.
Remark 1. We will see in Example 26 of Section IV that Theorem 19 cannot be sharpened, i.e., the lattice derivatives of a p-locally monotone function are not necessarily p-locally monotone, not even in the case of Boolean functions.

We can now present the relation between p-local monotonicity and p-permutability of lattice derivatives, which generalizes Lemma 10.

Theorem 21. If f : B n → R is p-locally monotone, then it has p-permutable lattice derivatives.

A natural question regarding the lattice derivatives is whether a function can be reconstructed from its derivatives. The answer is positive for almost all functions.

Theorem 22. Let f, g :

B n → R be pseudo-Boolean functions such that for all k ∈ [n] we have ∨ k f = ∨ k g and ∧ k f = ∧ k g. Then either f = g or there exists a one-to-one function α : B → R such that f (x) = α(x 1 ⊕ • • • ⊕ x n ) and g(x) = α(x 1 ⊕ • • • ⊕ x n ⊕ 1) for all x ∈ B n .
As in the case of local monotonicity, the classes of functions having permutable lattice derivatives form a chain under inclusion.

Theorem 23. If f : B n → R has (p + 1)-permutable lattice derivatives then f has p-permutable lattice derivatives.

If f : B n → B is a Boolean function with p-permutable lattice derivatives for some p ≥ 2, then f has 2-permutable lattice derivatives by the above theorem, and then Theorem 11 implies that f is 2-locally monotone. Unfortunately, nothing more can be said about the degree of local monotonicity of a Boolean function with p-permutable lattice derivatives. Indeed, the next example shows that there exist n-ary Boolean functions with n-permutable lattice derivatives that are exactly 2-locally monotone. Example 24. Let f n : B n → B be the function that takes the value 1 on all tuples of the form

x = ( m 1, . . . , 1, 0, . . . , 0) with 0 ≤ m ≤ n,
and takes the value 0 everywhere else. Using Corollary 9, it is not difcult to verify that f n is 2-locally monotone. However, if n ≥ 3, then f n is not 3-locally monotone, since

Δ 2 f (0, 0, 0, 0, . . . , 0) = -1, Δ 2 f (1, 0, 1, 0, . . . , 0) = 1.
Thus f n is exactly 2-locally monotone.

We will show by induction on n that f n has n-permutable lattice derivatives. First we compute the meet derivatives:

∧ k f n (x) =    1, if x 1 = • • • = x k-1 = 1 and x k+1 = • • • = x n = 0; 0, otherwise.
Since ∧ k f takes the value 1 only at one tuple, it is monotone. The join derivative ∨ k f n is essentially the same as the function

f n-1 (up to the inessential k-th variable of ∨ k f n ): ∨ k f n (x) = f n-1 (x 1 , . . . , x k-1 , x k+1 , . . . , x n ). (8)
Now it follows that if {k 1 , . . . , k n } = [n] and O ki ∈ {∧ ki , ∨ ki } (i = 1, . . . , n), then

O k1 • • • O kn-1 O kn f = O k π(1) • • • O k π(n-1) O kn f (9)
holds for every permutation π ∈ S n-1 . (If O kn = ∧ kn , then we use Theorem 21 and the fact that ∧ kn f is monotone, and if O kn = ∨ kn , then we use [START_REF] Grabisch | Equivalent representations of set functions[END_REF] and the induction hypothesis.) On the other hand, from the 2-local monotonicity of f we can conclude [START_REF] Marichal | Aggregation on nite ordinal scales by scale independent functions[END_REF] with the help of Theorem 11. Since S n is generated by S n-1 and the transposition (n -1 n), we see from ( 9) and ( 10) that f has n-permutable lattice derivatives.

O k1 • • • O kn-2 O kn-1 O kn f = O k1 • • • O kn-2 O kn O kn-1 f

IV. SYMMETRIC FUNCTIONS

In the previous sections we saw that both notions of local monotonicity and of permutable lattice derivatives lead to two hierarchies of pseudo-Boolean functions which are related by the fact that each p-local monotone class is contained in the corresponding class of functions having p-permutable lattice derivatives. Now, in general this containment is strict. However, under certain assumptions (see Theorem 11), plocal monotonicity is equivalent to p-permutability of lattice derivatives. Hence it is natural to ask for conditions under which these two conditions coincide.

In this section we present a partial answer to this problem by focusing on symmetric pseudo-Boolean functions, i.e., functions f : B n → R that are invariant under all permutations of their variables. Quite surprisingly, in this case the notions of p-local monotonicity and p-permutablity of lattice derivatives become equivalent.

Symmetric functions of arity n are in a one-to-one correspondence with sequences of real numbers of length n + 1, where the function corresponding to the sequence α = α 0 , . . . , α n is given by f (x) = α |x| (x ∈ B n ); here |x| denotes the Hamming weight of x. Clearly, f is isotone if and only if the corresponding sequence is nondecreasing, i.e.,

α 0 ≤ α 1 ≤ • • • ≤ α n . Similarly, f is antitone if and only if α 0 ≥ α 1 ≥ • • • ≥ α n ,
and f is monotone if and only if f is either isotone or antitone. ! It is easy to see that if f is symmetric, then every section of f is also symmetric; moreover, if f corresponds to the sequence α = α 0 , . . . , α n , then the p-ary sections of f are exactly the symmetric functions corresponding to the subsequences " α i , α i+1 , . . . , α i+p of α of length p + 1. This observation and Theorem 7 lead to the following description of p-locally monotone pseudo-Boolean functions.

Proposition 25. Let f : B n → R be a symmetric function corresponding to the sequence α = α 0 , . . . , α n . Then f is plocally monotone if and only if each subsequence of length p + 1 of α is either nondecreasing or nonincreasing.

Unlike in the previous sections, here it will be more convenient to discard the inessential k-th variable of the lattice derivatives ∧ k f and ∨ k f , and regard the latter as (n -1)-ary functions. Clearly, if f is symmetric, then so are its lattice derivatives. Moreover, if f corresponds to the sequence α = α 0 , . . . , α n , then ∧ k f and ∨ k f correspond to the sequences

α 0 ∧ α 1 , α 1 ∧ α 2 , . . . , α n-1 ∧ α n and α 0 ∨ α 1 , α 1 ∨ α 2 , . . . , α n-1 ∨ α n ,
respectively, for all k ∈ [n]. Since these sequences do not depend on k, we will write ∧f and ∨f instead of ∧ k f and ∨ k f , respectively.

The next example shows that Theorem 19 cannot be sharpened.

Example 26. Let f : B n → B be the symmetric function corresponding to the sequence α = 0, 0, where n = 2p + 4 and p ≥ 2. It follows from Proposition 25 that f is exactly p-locally monotone. To compute ∧f , it is handy to construct a table whose rst row contains the ! Since if f is isotone (resp. antitone) in one variable, then it is isotone (resp. antitone) in all variables. " Here by a subsequence we mean a sequence of consecutive entries of the original sequence.

sequence α, and in the second row we write α i ∧α i+1 between α i and α i+1 :

f : 0 0 1 1 • • • 1 1 0 0 • • • 0 0 1 1 ∧f : 0 0 1 1 • • • 1 1 0 0 0 • • • 0 0 0 1
Thus ∧f corresponds to the sequence We conclude this section by making explicit the equivalence between the notions of p-local monotonicity and ppermutability of lattice derivatives in the case of symmetric functions.

Theorem 27. If f : B n → R is a symmetric function, then f is p-locally monotone if and only if f has p-permutable lattice derivatives.

Remark 3. As a consequence of the above theorem, we can observe that any exactly p-locally monotone symmetric function (for instance, the functions considered in Example 26) has p-permutable but not (p+1)-permutable lattice derivatives.

V. OPEN PROBLEMS AND CONCLUDING REMARKS

We proposed relaxations of monotonicity, namely p-local monotonicity, and we presented characterizations of each in terms of forbidden sections. Also, for each p, we observe that p-locally monotone functions have the property that any p of its lattice derivatives permute, and showed that the converse also holds in the special case of symmetric functions. The classes of 2-locally monotone functions, and of functions having 2-permutable lattice derivatives were explicitly described; as a by-product their symmetric difference was obtained. However, similar descriptions elude us for p ≥ 3. Hence we are left with the following problems. Problem 1. For p ≥ 3, describe the class of p-locally monotone functions and that of functions having p-permutable lattice derivatives. Problem 2. For p ≥ 3, determine necessary and sufcient conditions on functions for the equivalence between p-local monotonicity and permutability of p lattice derivatives.

p 1 ,

 1 . . . , 1, p 0, . . . , 0, 1, 1

  2-permutable lattice derivatives. Proposition 16. A function f : B n → R has 2-permutable lattice derivatives if and only if every binary section (2) of f satises a 1 a 12 ≥ 0 or a 2 a 12 ≥ 0 or |a 12| ≤ |a 1 | ∨ |a 2 |. Equivalently, (i) a 1 a 12 < 0 or a 2 a 12 < 0, (ii) |a 12 | > |a 1 | ∧ |a 2 |, (iii) if a 1 a 2 > 0, then |a 12 | ≤ |a 1 | ∨ |a 2 |, (iv) if a 1 a 12 ≥ 0, then |a 12 | > |a 2 |,and (v) if a 2 a 12 ≥ 0, then |a 12 | > |a 1 |. Now, according to Theorem 11, a Boolean function is 2locally monotone if and only if it has 2-permutable lattice derivatives. Example 24 below shows that the analogous equivalence does not hold for p > 2. However, p-local monotonicity implies p-permutability of lattice derivatives of any pseudo-Boolean function (see Theorem 21 below). To this extent, let us rst study how the degree of local monotonicity is affected by taking lattice derivatives. Lemma 18. If f : B n → R is a monotone function, then ∧ j f and ∨ j f are also monotone for all j ∈ [n]. Theorem 19. If f : B n → R is a p-locally monotone function, then ∧ j f and ∨ j f are (p-1)-locally monotone for all j ∈ [n].

	Example 12 showed that the class of 2-locally monotone
	pseudo-Boolean functions is a proper subclass of that of
	pseudo-Boolean functions which have 2-permutable lattice
	derivatives. From Corollary 8 and Proposition 16, we obtain
	the following description of pseudo-Boolean functions which
	have 2-permutable lattice derivatives but are not 2-locally
	monotone.
	Corollary 17.

A function f : B n → R has 2-permutable lattice derivatives but is not 2-locally monotone if and only if every binary section (2) of f satises the following two conditions: (i) a 1 a 12 ≥ 0 or a 2 a 12 ≥ 0 or |a 12 | ≤ |a 1 | ∨ |a 2 |, and (ii) a 1 (a 1 + a 12 ) < 0 or a 2 (a 2 + a 12 ) < 0.

  Now Proposition 25 shows that ∧f and ∨f are exactly (p-1)locally monotone.Remark 2. The above example shows that the degree of local monotonicity can decrease, when taking lattice derivatives, and Theorem 19 states that it can decrease by at most one. Other examples can be found to illustrate the cases when this degree stays the same, or even increases. For instance, consider the function f (x) = x 1 ⊕ • • • ⊕ x n , which is not even 2-locally monotone, but its lattice derivatives are constant.

			p-1	p+1
	0, 0,	1, . . . , 1,	0, . . . , 0, 1,
	and a similar calculation yields that ∨f corresponds to the
	sequence
			p+1	p-1
	0,	1, . . . , 1,	0, . . . , 0, 1, 1.

Note that the terms positive and nondecreasing (resp. negative and nonincreasing) are often used instead of isotone (resp. antitone), and it is also customary to use the word monotone only for isotone functions.

ACKNOWLEDGMENTS

Miguel Couceiro and Jean-Luc Marichal are supported by the internal research project F1R-MTH-PUL-09MRDO of the University of Luxembourg. Tamás Waldhauser 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 Scientic Research under grants no. K77409 and K83219, by the National Research Fund of Luxembourg, and by the Marie Curie Actions of the European Commission (FP7-COFUND).


Miguel Couceiro
email: miguel.couceiro@uni.lu

Lucien Haddad
email: haddad-l@rmc.ca

A survey on intersections of maximal partial clones of Boolean partial functions

We survey known results and present some new ones about intersections of maximal partial clones on a 2-element set.

I. PRELIMINARIES

Let A be a finite non-singleton set. Without loss of generality we assume that A = k := {0, . . . , k-1}. For a positive integer n, an n-ary partial function on k is a map f : dom (f ) → k where dom (f ) is a subset of k n called the domain of f . Let Par (n) (k) denote the set of all n-ary partial functions on k and let Par(k) := n≥1 Par (n) (k). An n-ary partial function g is said to be a total function if dom (g) = k n . Let Op(k) be the set of all total functions on k.

For n, m ≥ 1, f ∈ Par (n) (k) and g 1 , . . . , g n ∈ Par (m) (k), the composition of f and g 1 , . . . , g n , denoted by f [g 1 , . . . , g n ] ∈ Par (m) (k), is defined by

dom (f [g 1 , . . . , g n ]) := { a ∈ k m | a ∈ m i=1
dom (g i ), (g 1 ( a), . . . , g m ( a)) ∈ dom (f )}, and f [g 1 , . . . , g n ]( a) := f (g 1 ( a), . . . , g n ( a)), for all a ∈ dom (f [g 1 , . . . , g n ]).

For every positive integer n and each 1 ≤ i ≤ n, let e n i denote the n-ary i-th projection function defined by e n i (a 1 , . . . , a n ) = a i for all (a 1 , . . . , a n ) ∈ k n . Furthermore, let J k := {e n i : 1 ≤ i ≤ n} be the set of all (total) projections. Definition 1. A partial clone on k is a composition closed subset of Par(k) containing J k . If a partial clone is contained in the set of all total functions Op(k), then it is called a clone on k.

Remark 1. There are two other equivalent definitions for partial clones. One definition uses Mal'tsev's formalism and the other uses the concept of one point extension. These definitions can be found in chapter 20 of [START_REF] Lau | Function Algebras on Finite Sets, a basic course on Multiple-Valued Logic and Clone Theory[END_REF].

The partial clones on k (clones on k), ordered by inclusion, form a lattice L P k (L O k , respectively) in which the infinimum is the set-theoretical intersection. That means that the intersection of an arbitrary family of partial clones (clones) on k is also a partial clone on k (clone on k, respectively). A maximal partial clone on k is a coatom of the lattice

L P k . Therefore a partial clone M is maximal if there is no partial clone C over k such that M ⊂ C ⊂ Par(k). Similarly a clone M is called a maximal clone if there is no clone C on k such that M ⊂ C ⊂ Op(k). We say that a partial clone C 0 on A is covered by a partial clone C 1 on A if there is no partial clone C such that C 0 ⊂ C ⊂ C 1 . Therefore a maximal partial clone is a partial clone covered by Par(k). Example 2. Let Ω k := n≥1 {f ∈ Par (n) (k) | dom (f ) = ∅ =⇒ dom (f ) = k n } = n≥1 {f ∈ Par (n) (k) | dom (f ) = ∅ =⇒ f ∈ Op(k)}.
Then Ω k is a maximal partial clone on k.

An interesting and somehow difficult problem in clone theory is to study intersections of maximal clones and maximal partial clones. The lattice L O2 is known and was completely described by E. Post in [START_REF] Post | The two-valued iterative systems of mathematical logic[END_REF]. In chapter 14 of [START_REF] Lau | Function Algebras on Finite Sets, a basic course on Multiple-Valued Logic and Clone Theory[END_REF] are listed all submaximal elements of L O3 , i.e., all clones on 3 covered by the maximal elements of L O3 . Several results dealing with intersection of maximal clones can be found in the literature, we refer the reader to the list of reference in [START_REF] Lau | Function Algebras on Finite Sets, a basic course on Multiple-Valued Logic and Clone Theory[END_REF] for details.

In this paper we focus on L P2 , the lattice of partial clones of Boolean functions. We survey the known results and present some new results concerning the intersections of the maximal elements of L P2 .

With one exception, every maximal partial clone is the polymorphism of a relation. We have: Definition 3. For h ≥ 1, let ρ be an h-ary relation on k and f be an n-ary partial function on k. We say that f preserves ρ if for every h × n matrix M = [M ij ] whose columns M * j ∈ ρ, (j = 1, . . . n) and whose rows

M i * ∈ dom (f ) (i = 1, . . . , h), the h-tuple (f (M 1 * ), . . . , f (M h * )) ∈ ρ. Define pPol ρ := {f ∈ Par(k) | f preserves ρ}.
It is well known that pPol ρ is a partial clone called the partial clone determined by the relation ρ.

Note that if there is no h × n matrix M = [M ij ] whose columns M * j ∈ ρ and whose rows M i * ∈ dom (f ), then f ∈ pPol ρ.

Example 4. Let 2 := {0, 1}, let {(0, 0), (0, 1), (1, 1)} be the natural order on 2 and consider the binary relation {(0, 1), (1, 0)} on 2.

Then pPol {(0, 0), (0, 1), (1, 1)} is the set of all monotone partial functions and pPol {(0, 1), (1, 0)} is the set of all selfdual partial functions on 2. For simplicity we will write pPol (≤) and pPol ( =) for pPol ({(0, 0), (0, 1), (1, 1)}) and pPol ({(0, 1), (1, 0)}), respectively.

It is easy to see that if ρ is an h-ary relation on 2, then pPol ρ = pPol (ρ ⊗ 2). This fact motivates the concept of irredundant relation.

Let h ≥ 1 and let ρ be an h-ary relation on k. We say that ρ is repetition-free if for all 1 ≤ i < j ≤ h, there exists (a 1 , . . . , a h ) ∈ ρ with a i = a j . Moreover, ρ is said to be irredundant if it is repetition-free and has no fictitious components, i.e., there is no i ∈ {1, . . . , h} such that

(a 1 , . . . , a h ) ∈ ρ implies (a 1 , . . . , a i-1 , x, a i+1 , . . . , a h ) ∈ ρ for all x ∈ k.
can be shown that if µ is a nonempty relation, then we can find an irredundant relation ρ such that pPol µ = pPol ρ (see, e. g. [START_REF] Haddad | Completeness theory for finite partial algebras[END_REF]) for details).

The following result, known as the Definability Lemma, was first established by B. Romov in [START_REF] Romov | The algebras of partial functions and their invariants[END_REF] (see Lemma 20.3.4 in [START_REF] Lau | Function Algebras on Finite Sets, a basic course on Multiple-Valued Logic and Clone Theory[END_REF]) and has been widely used to handle maximal partial clones via the relational approach.

Lemma 5. (The Definability Lemma) Let h 1 , . . . , h n , t ≥ 1 be integers, ρ i be an h i -ary relation on k, i = 1, . . . , n, and β be a t-ary irredundant relation on k. Then 1≤i≤n pPol ρ i ⊆ pPol β if and only if there exists a family of h i -ary auxiliary relations { 1 , . . . , n } whose vertex sets is {1, . . . , t}, and such that

β = {(x 1 , . . . , x t ) ∈ k t | (i j 1 , . . . , i j hj ) ∈ j ⇒ (x i j 1 , . . . , x i j h j ) ∈ ρ j , for j = 1, . . . , n}.
Example 6. Let ρ 1 be a binary and ρ 2 be a ternary relation on k. Let β be the 4-ary relation defined by

β := {(x 1 , . . . , x 4 ) ∈ k 4 | (x 1 , x 2 ) ∈ ρ 1 , (x 3 , x 2 ) ∈ ρ 1 , and (x 1 , x 4 , x 3 ) ∈ ρ 2 }. Then pPol ρ 1 ∩ pPol ρ 2 ⊆ pPol β. (Here n = 2, 1 = {(1, 2), (3, 2)} and 2 = {(1, 4, 3)}.)
As mentioned earlier, Freivald showed that there are exactly eight maximal partial clones on 2. The following two relations determine maximal partial clones. Set

R 1 := {(x, x, y, y) | x, y ∈ 2} ∪ {(x, y, y, x) | x, y ∈ 2} and R 2 := R 1 ∪ {(x, y, x, y) | x, y ∈ 2}.
Theorem 7. ( [START_REF] Freivald | Completness criteria for functions of the algebra of logic and many-valued logics[END_REF]) There are exactly 8 maximal partial clones on 2, namely: pPol {0}, pPol {1}, pPol {(0, 1)}), pPol (≤), pPol ( =), pPol (R 1 ), pPol (R 2 ) and Ω 2 .

The three maximal partial clones pPol R 1 , pPol R 2 and Ω 2 contain the unary functions Op (1) (2) (i.e., maps) on 2. Such partial clones are called Słupecki type partial clones in [START_REF] Haddad | Pairwise intersections of Słupecki type maximal partial clones[END_REF], [START_REF] Romov | Maximal subalgebras of algebras of partial multivalued logic functions[END_REF]. They are the only three maximal partial clones of Słupecki type on 2.

It is known that pPol R 2 ∩ Op(2) is the maximal clone of all (total) linear functions over 2 (see, e.g., section 5.2.4 of [START_REF] Lau | Function Algebras on Finite Sets, a basic course on Multiple-Valued Logic and Clone Theory[END_REF]). Alekzeev and Voronenko studied the classes of partial clones of Boolean functions that contain pPol R 2 ∩ Op(2) on 2. From the main result of [START_REF] Alekzeev | Some closed classes in the partial two-valued logic (Russian)[END_REF] we have:

Theorem 8. The interval of partial clones [pPol R 2 ∩ Op(2), Par(2)] is of continuum cardinality on 2.
The proof of this result is quite complicated and is given in ( [START_REF] Alekzeev | Some closed classes in the partial two-valued logic (Russian)[END_REF]) (see also Theorem 20.8.1 of [START_REF] Lau | Function Algebras on Finite Sets, a basic course on Multiple-Valued Logic and Clone Theory[END_REF]). We refer the reader to Theorem 19 of [START_REF] Haddad | Pairwise intersections of Słupecki type maximal partial clones[END_REF] and Theorem 20.7.13 of [START_REF] Lau | Function Algebras on Finite Sets, a basic course on Multiple-Valued Logic and Clone Theory[END_REF] for the generalization of Theorem 8 to partial clones on k with k ≥ 3. A consequence of Theorem 8 is that the interval of partial clones

[pPol (R 2 ) ∩ Ω 2 , Par(2)] is of continuum cardinality on 2.
On the other hand it is shown in [START_REF] Haddad | On the depth of the intersection of two maximal partial clones[END_REF] that pPol R 1 ∩ Op(k) is the clone over k generated by Op (1) (k) for every k ≥ 2. We present a result similar to Theorem 8 that is established for pPol R 1 in [START_REF] Haddad | On the depth of the intersection of two maximal partial clones[END_REF].

For n ≥ 3 define the 2n-ary relation τ 2n on 2 by setting: (x 1 , . . . , x 2n ) ∈ τ n if and only if either x 1 = • • • = x 2n , or each of 0 and 1 appears exactly n times in (x 1 , . . . , x 2n ).

It is shown in [START_REF] Haddad | On the depth of the intersection of two maximal partial clones[END_REF] that Op (1) (2) ⊆ pPol τ 2n for all n ≥ 3. Since

R 1 = {(x 1 , x 2 , x 3 , x 4 ) ∈ 2 4 | (x 1 , . . . , x 1 , x 2 , x 3 , . . . , x 3 , x 4 ) ∈ τ 2n }
holds for all n ≥ 3, it follows from Lemma 5 that pPol τ 2n ⊆ pPol R 1 for all n ≥ 3.

Let P := {3, 5, 7, . . . } be the set of all odd prime numbers and P(P) be its power set. It is shown in [START_REF] Haddad | On the depth of the intersection of two maximal partial clones[END_REF] that the map

χ : P(P) → [pPol R 1 ∩ Ω 2 , pPol R 1 ]
defined by X -→ χ(X) := t∈P\X pPol τ 2t is one-to-one. Hence we have the following result:

Theorem 9. The interval of partial clones [pPol (R 1 ) ∩ Ω 2 , Par(2)] is of continuum cardinality on 2.
Together with D. Lau, the second author studied several intersections of Słupecki type partial clones on a non-singleton finite set. The following result comes from [START_REF] Haddad | Pairwise intersections of Słupecki type maximal partial clones[END_REF]:

Theorem 10. The partial clone pPol R 1 ∩ pPol R 2 is covered by the maximal partial clone pPol R 2 .
The dual of the above result does not hold for pPol R 1 . It is shown in [START_REF] Haddad | Pairwise intersections of Słupecki type maximal partial clones[END_REF] that there is at least one partial clone that strictly lies between pPol R 1 ∩ pPol R 2 and pPol R 1 . Indeed, let

λ := {(x 1 , . . . , x 7 ) ∈ 2 7 | (x 1 , x 2 , x 5 , x 6 ) ∈ R 1 , (x 2 , x 4 , x 6 , x 7 ) ∈ R 1 , and (x 1 , x 2 , x 3 , x 4 ) ∈ R 2 }.
Then it is shown in [START_REF] Haddad | Pairwise intersections of Słupecki type maximal partial clones[END_REF] that pPol R 1 ∩ pPol R 2 pPol λ pPol R 1 . Therefore the partial clone pPol R 1 ∩ pPol R 2 is not covered by the maximal partial clone pPol R 1 . To our knowledge, little seems to be known about the interval of partial clones

[pPol R 1 ∩ pPol R 2 , pPol R 1 ].
Intersections of maximal partial clones that are not of Słupecki type have been studied as well. Intersections of the form pPol ρ ∩ pPol θ where ρ, θ ∈ {{0}, {1}, {(0, 1)}, =, ≤}, with the exception of {ρ, θ} = {≤, =}, have been studied in [START_REF] Haddad | Intersections of Maximal partial clones I[END_REF], [START_REF] Haddad | Intersections of Maximal partial clones II[END_REF]. Almost all proofs given in [START_REF] Haddad | Intersections of Maximal partial clones I[END_REF], [START_REF] Haddad | Intersections of Maximal partial clones II[END_REF] are based on the composition of partial functions. In the same direction, deeper results were established in [START_REF] Haddad | Intervals of Boolean Partial Clones[END_REF] and [START_REF] Haddad | On Intervals of Partial Clones of Boolean Partial Functions[END_REF] where partial clones are handled via relations, and all proofs are based on the Lemma 5. Let

C M := pPol {0} ∩ pPol {1} ∩ pPol {(0, 1)} ∩ pPol (≤) and C D := pPol {0} ∩ pPol {1} ∩ pPol {(0, 1)} ∩ pPol ( =).
Then C M (respectively C D ) is the set of all idempotent monotonic partial functions on 2 (idempotent self-dual partial functions on 2). We have: 2)] are completely described in [START_REF] Haddad | Intervals of Boolean Partial Clones[END_REF] (see also [START_REF] Haddad | On Intervals of Partial Clones of Boolean Partial Functions[END_REF]). D. Lau informed the second author that some of the results in [START_REF] Haddad | Intervals of Boolean Partial Clones[END_REF] exist in the unpublished manuscript [START_REF] Strauch | On partial classes containing all monotone and zeropreserving total Boolean functions[END_REF] by B. Strauch. In view of results from [START_REF] Alekzeev | Some closed classes in the partial two-valued logic (Russian)[END_REF], [START_REF] Haddad | On the depth of the intersection of two maximal partial clones[END_REF], [START_REF] Haddad | Intervals of Boolean Partial Clones[END_REF], [START_REF] Strauch | On partial classes containing all monotone and zeropreserving total Boolean functions[END_REF], [START_REF] Strauch | The classes which contain all monotone and idempotent total Boolean functions[END_REF], it was thought that if 2 ≤ i ≤ 5 and M 1 , . . . , M i are non-Słupecki maximal partial clones on 2, then the interval

[M 1 ∩ • • • ∩ M i , Par (2)
] is either finite or countably infinite. It is shown in [START_REF] Haddad | Partial clones containing all self-dual monotonic Boolean partial functions[END_REF] that the interval of partial clones [pPol (≤) ∩ pPol ( =), Par(2)] is infinite. This result is mentioned in Theorem 20.8 of [START_REF] Lau | Function Algebras on Finite Sets, a basic course on Multiple-Valued Logic and Clone Theory[END_REF] (with an independent proof given in [START_REF] Lau | A Classification of Partial Boolean Clones[END_REF]) and in chapter 8 of the PhD thesis [START_REF] Schölzel | Clones of Partial Functions on Finite Sets[END_REF]. However, it remained an open problem to determine whether [pPol (≤) ∩ pPol ( =), Par(2)] is countably or uncountably infinite.

The following relations, introduced in [START_REF] Couceiro | Partial clones containing all Boolean monotone self-dual partial functions[END_REF], are needed to settle this question. For n ≥ 5 and n > k ≥ 1 we denote by σ n k ⊆ 2 2n the (2n)-ary relation defined by

σ n k := {(x 1 , . . . , x n , y 1 , . . . , y n ) ∈ 2 2n | ∀ i = 1, . . . , n, x i = y i , and ∀ k = 1, . . . , n, y i+k ≤ x i },
where the subscripts i + j in the above definition are taken modulo n. Now for n ≥ 5 and n > k ≥ 1, we denote by ρ n k ⊆ 2 4n the (4n)-ary relation defined by ρ n k := {(x 1 , . . . , x 2n , y 1 , . . . , y 2n ) ∈ 2 4n | (x 1 , . . . , x n , y 1 , . . . , y n ) ∈ σ n 1 , and (x n+1 , . . . , x 2n , y n+1 , . . . , y 2n ) ∈ σ n k }. By Lemma 5 we have that for all n ≥ 5 and n

> k ≥ 1 pPol (≤) ∩ pPol ( =) ⊆ pPol σ n k ∩ pPol σ n 1 ⊆ pPol ρ n k .
Denote by E ≥4 := {4, 6, 8, . . . } the set of all even integers greater or equal to 4 and denote by P(E ≥4 ) the power set of E ≥4 . Furthermore, for every even integer k ≥ 4, let n(k) := k(k +1)+1. Since pPol (≤)∩pPol ( =) ⊆ pPol (ρ n k ) for every n ≥ 5 and every n > k ≥ 1, we have that

pPol (≤) ∩ pPol ( =) ⊆ t∈E ≥4 \X pPol ρ n(t)
for every subset X of E ≥4 . It was shown in [START_REF] Couceiro | Partial clones containing all Boolean monotone self-dual partial functions[END_REF] that the map We need the following notation. For v ∼ = (v 1 , . . . , v t ) ∈ 2 t , we define ker(v ∼ ) := {(i, j) ∈ {1, . . . , t} 2 | v i = v j }. Note that ker(v ∼ ) is a binary equivalence relation on the set {1, . . . , t} with at most two blocks.

χ : P(E ≥4 ) → [pPol (≤) ∩ pPol ( =), Par(2)] defined by X -→ χ(X) := t∈E ≥4 \X pPol ρ n(t)
Proof of Theorem 13. Let θ ∈ {R 1 , R 2 }. We consider three cases: a) pPol {(0, 1)} ∩ pPol θ is covered by pPol θ. Let t ≥ 1 and λ be a t-ary irredundant relation such that pPol {(0, 1)} ∩ pPol θ ⊆ pPol λ. By Lemma 5, there is a binary relation 1 and a 4-ary relation 2 , with { 1 , 2 } covering the set {1, . . . , t} and such that λ = {(x 1 , . . . , x t ) ∈ 2 t | ∀ (j 1 , j 2 ) ∈ 1 , (x j1 , x j2 ) ∈ {(0, 1)}, and ∀ (i 1 , . . . , i 4 ) ∈ 2 , (x i1 , . . . , x i4 ) ∈ θ}.

Note that if 1 = ∅, then λ can be defined from θ and by Lemma 5 pPol θ ⊆ pPol λ, thus pPol θ = pPol λ by the maximality of pPol θ. So assume 1 = ∅. Without loss of generality, let (1, 2) ∈ 1 , i.e., (x 1 , x 2 ) = (0, 1) for every tuple

(x 1 , . . . , x t ) ∈ λ. Fix v ∼ = (0, 1, v 3 , . . . , v t ) ∈ λ and set µ := {(x 1 , x 2 ) ∈ 2 2 | (x 1 , x 2 , x i3 , . . . , x it ) ∈ λ}
where, for j = 3, . . . , t, i j = 1 if (1, i j ) ∈ ker (v ∼ ) and i j = 2 if (2, i j ) ∈ ker (v ∼ ). Then we have that pPol λ ⊆ pPol µ by Lemma 5. As v ∼ = (0, 1, v 3 , . . . , v t ) ∈ λ we have (0, 1) ∈ µ and since every (x 1 , . . . , x t ) ∈ λ satisfies x 1 = 0, x 2 = 1, we have that µ = {(0, 1)}. By Fact 14, pPol {(0, 1)} ∩ pPol θ is covered by pPol θ. The proof of the claim that pPol {0} ∩ pPol θ and pPol {1} ∩ pPol θ are covered by pPol θ follows similarly. b) pPol { =} ∩ pPol θ is covered by pPol θ. We proceed as in case a), and choose v ∼ = (v 1 , v 2 , . . . , v t ) ∈ λ. Then either (v 1 , v 2 ) = (0, 1) or (v 1 , v 2 ) = (1, 0). Suppose that (v 1 , v 2 ) = (0, 1) and consider the map ¬(0) = 1, ¬(1) = 0. Since ¬ ∈ pPol ( =) ∩ pPol θ, we have ¬ ∈ pPol λ and so ¬(v ∼ ) := (¬(v 1 ), . . . , ¬(v t )) ∈ λ. Again consider the relation µ defined in a). It is easy to see that µ is the binary relation = and the rest of the proof is as above. The case (v 1 , v 2 ) = (1, 0) follows similarly. c) pPol ≤ ∩ pPol θ is covered by pPol θ. Again proceed as in case a) with the assumption that (1, 2) ∈ 1 . Note that in this case we have (0, . . . , 0), (1, . . . , 1) ∈ λ. Moreover since λ is irredundant, there is v ∼ = (v 1 , v 2 , . . . , v t ) ∈ λ such that v 1 = v 2 . As v 1 ≤ v 2 we get (v 1 , v 2 ) = (0, 1). Again consider the relation µ as defined in case a). From v ∼ ∈ λ we obtain (0, 1) ∈ µ and as (i, . . . , i) ∈ λ we have (i, i) ∈ µ, for i = 0, 1. Note that (1, 0) ∈ µ since for every (x 1 , x 2 , . . . , x t ) ∈ λ, x 1 ≤ x 2 . So µ is the binary relation ≤. The rest of the proof is as in case a).

Theorem 11 .

 11 The interval [C M , Par(2)] contains exactly 25 partial clones and the interval [C D , Par(2)] contains exactly 33 partial clones on 2. The intervals of partial clones [C M , Par(2)] and [C D , Par(

Theorem 13 .Fact 14 .

 1314 is one-to-one.Hence we have the following result:Theorem 12. The interval of partial clones [pPol (≤) ∩ pPol ( =), Par(2)] is of continuum cardinality on 2.We conclude this survey with the following new result, which provides several examples of finite intervals of the form above. Let ρ ∈ {{0}, {1}, {(0, 1)}, =, ≤} and θ ∈ {R 1 , R 2 }. Then the partial clone pPol ρ∩pPol θ is covered by the maximal partial clone pPol θ over 2. In particular, each interval of partial clones of the form [pPol ρ ∩ pPol θ, Par(2)] has size 2.The proof is based on the following fact established after Lemma 3 in[START_REF] Haddad | Pairwise intersections of Słupecki type maximal partial clones[END_REF]. Let pPol ρ and pPol θ be two distinct maximal partial clones on k. Suppose that[pPol ρ ∩ pPol θ ⊆ pPol λ] =⇒ [pPol λ ⊆ pPol ρ or pPol λ = pPol θ]holds for every irredundant relation λ. Then the partial clone pPol ρ∩pPol θ is covered by the maximal partial clone pPol θ on k.

ACKNOWLEDGMENTS

Miguel Couceiro is supported by the internal research project F1R-MTH-PUL-09MRDO of the University of Luxembourg.


domain: math info

text:
Miguel Couceiro
email: miguel.couceiro@uni.lu

Jean-Luc Marichal
email: jean-luc.marichal@uni.lu

Quasi-Lovász extensions and their symmetric counterparts

Keywords: Aggregation function, discrete Choquet integral, Lovász extension, comonotonic modularity, invariance under horizontal differences. MSC classes: 39B22, 39B72 (Primary) 26B35 (Secondary)

We introduce the concept of quasi-Lovász extension as being a mapping f : I n → IR defined over a nonempty real interval I containing the origin, and which can be factorized as f (x1, . . . , xn) = L(ϕ(x1), . . . , ϕ(xn)), where L is the Lovász extension of a pseudo-Boolean function ψ : {0, 1} n → IR (i.e., the function L : IR n → IR whose restriction to each simplex of the standard triangulation of [0, 1] n is the unique affine function which agrees with ψ at the vertices of this simplex) and ϕ : I → IR is a nondecreasing function vanishing at the origin. These functions appear naturally within the scope of decision making under uncertainty since they subsume overall preference functionals associated with discrete Choquet integrals whose variables are transformed by a given utility function.

To axiomatize the class of quasi-Lovász extensions, we propose generalizations of properties used to characterize the Lovász extensions, including a comonotonic version of modularity and a natural relaxation of homogeneity. A variant of the latter property enables us to axiomatize also the class of symmetric quasi-Lovász extensions, which are compositions of symmetric Lovász extensions with 1-place nondecreasing odd functions.

Introduction

Aggregation functions arise wherever merging information is needed: applied and pure mathematics (probability, statistics, decision theory, functional equations), operations research, computer science, and many applied fields (economics and finance, pattern recognition and image processing, data fusion, etc.). For recent references, see Beliakov et al. [START_REF] Beliakov | Aggregation Functions: A Guide for Practitioners[END_REF] and Grabisch et al. [START_REF] Grabisch | Aggregation functions[END_REF].

The discrete Choquet integral has been widely investigated in aggregation theory due to its many applications, for instance, in decision making (see the edited book [START_REF] Grabisch | Fuzzy measures and integrals -Theory and applications[END_REF]). A convenient way to introduce the discrete Choquet integral is via the concept of Lovász extension. An n-place Lovász extension is a continuous function L : IR n → IR whose restriction to each of the n! subdomains

IR n σ = {x = (x 1 , . . . , x n ) ∈ IR n : x σ(1) • • • x σ(n) }, σ ∈ S n ,
is an affine function, where S n denotes the set of permutations on [n] = {1, . . . , n}.

An n-place Choquet integral is simply a nondecreasing (in each variable) n-place Lovász extension which vanishes at the origin. For general background, see [7, §5.4].

The class of n-place Lovász extensions has been axiomatized by the authors [START_REF] Couceiro | Axiomatizations of Lovász extensions and symmetric Lovász extensions of pseudo-Boolean functions[END_REF] by means of two noteworthy aggregation properties, namely comonotonic additivity and horizontal min-additivity (for earlier axiomatizations of the nplace Choquet integrals, see, e.g., [START_REF] Benvenuti | Monotone set functions-based integrals[END_REF][START_REF] De Campos | Characterization and comparison of Sugeno and Choquet integrals[END_REF]). Recall that a function f : IR n → IR is said to be comonotonically additive if, for every σ ∈ S n , we have

f (x + x ) = f (x) + f (x ),
x, x ∈ IR n σ .

The function f is said to be horizontally min-additive if

f (x) = f (x ∧ c) + f (x -(x ∧ c)), x ∈ IR n , c ∈ IR,
where x ∧ c denotes the n-tuple whose ith component is

x i ∧ c = min(x i , c).
In this paper we consider a generalization of Lovász extensions, which we call quasi-Lovász extensions, and which are best described by the following equation

f (x 1 , . . . , x n ) = L(ϕ(x 1 ), . . . , ϕ(x n ))
where L is a Lovász extension and ϕ a nondecreasing function such that ϕ(0) = 0. Such an aggregation function is used in decision under uncertainty, where ϕ is a utility function and f an overall preference functional. It is also used in multicriteria decision making where the criteria are commensurate (i.e., expressed in a common scale). For a recent reference, see Bouyssou et al. [START_REF]Decision-Making Process -Concepts and Methods[END_REF].

To axiomatize the class of quasi-Lovász extensions, we propose the following generalizations of comonotonic additivity and horizontal min-additivity, namely comonotonic modularity and invariance under horizontal min-differences (as well as its dual counterpart), which we now briefly describe. We say that a function f : IR n → IR is comonotonically modular if, for every σ ∈ S n , we have

f (x) + f (x ) = f (x ∧ x ) + f (x ∨ x ), x, x ∈ IR n σ , where x ∧ x (resp. x ∨ x ) denotes the n-tuple whose ith component is x i ∧ x i = min(x i , x i ) (resp. x i ∨ x i = max(x i , x i )). We say that f is invariant under horizontal min-differences if f (x) -f (x ∧ c) = f ([x] c ) -f ([x] c ∧ c), x ∈ IR n , c ∈ IR,
where [x] c denotes the n-tuple whose ith component is 0, if x i c, and x i , otherwise.

The outline of this paper is as follows. In Section 2 we recall the definitions of Lovász extensions, discrete Choquet integrals, as well as their symmetric versions, and present representations for these functions. In Section 3 we define the concept of quasi-Lovász extension and its symmetric version, introduce natural relaxations of homogeneity, namely weak homogeneity and odd homogeneity, and present characterizations of those quasi-Lovász extensions (resp. symmetric quasi-Lovász extensions) that are weakly homogeneous (resp. oddly homogeneous). In Section 4 we define the concepts of comonotonic modularity, invariance under horizontal min-differences and invariance under horizontal max-differences, and present a complete description of those function classes axiomatized by each of these properties. In Section 5 we give axiomatizations of the class of quasi-Lovász extensions by means of the properties above, and give all possible factorizations of quasi-Lovász extensions into compositions of Lovász extensions with 1-place functions. Finally, in Section 6 we present analogous results for the symmetric quasi-Lovász extensions.

We employ the following notation throughout the paper. Let B = {0, 1}, IR + = [0, +∞[, and IR -= ]-∞, 0]. The symbol I denotes a nonempty real interval, possibly unbounded, containing 0. We also introduce the notation I + = I ∩ IR + , I -= I ∩ IR -, and

I n σ = I n ∩ IR n σ . A function f : I n → IR,
where I is centered at 0, is said to be odd if f (-x) = -f (x). For any function f : I n → IR, we define f 0 = f -f (0). For every A ⊆ [n], the symbol 1 A denotes the n-tuple whose ith component is 1, if i ∈ A, and 0, otherwise. Let also 1 = 1 [n] and 0 = 1 ∅ . The symbols ∧ and ∨ denote the minimum and maximum functions, respectively. For every x ∈ IR n , let x + = x ∨ 0 and x -= (-x) + . For every x ∈ IR n and every c

∈ IR + (resp. c ∈ IR -) we denote by [x] c (resp. [x] c ) the n-tuple whose ith component is 0, if x i c (resp. x i c), and x i , otherwise.
In order not to restrict our framework to functions defined on IR, we consider functions defined on intervals I containing 0, in particular of the forms I + , I -, and those centered at 0.

A full version of the current paper appeared as [START_REF] Couceiro | Axiomatizations of quasi-Lovász extensions of pseudo-Boolean functions[END_REF].

Lovász extensions and symmetric Lovász extensions

We now recall the concepts of Lovász extension and symmetric Lovász extension. Consider an n-place pseudo-Boolean function, i.e. a function ψ : B n → IR, and define the set function v ψ : 2

[n] → IR by v ψ (A) = ψ(1 A ) for every A ⊆ [n].
Hammer and Rudeanu [START_REF] Hammer | Boolean methods in operations research and related areas[END_REF] showed that such a function has a unique representation as a multilinear polynomial of n variables

ψ(x) = ∑ A⊆[n] a ψ (A) ∏ i∈A x i ,
where the set function a ψ : 2

[n] → IR, called the Möbius transform of v ψ , is defined by a ψ (A) = ∑ B⊆A (-1) |A|-|B| v ψ (B).
The Lovász extension of a pseudo-Boolean function ψ : B n → IR is the function L ψ : IR n → IR whose restriction to each subdomain IR n σ (σ ∈ S n ) is the unique affine function which agrees with ψ at the n + 1 vertices of the n-simplex [0, 1] n ∩ IR n σ (see [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]). We then have L ψ | B n = ψ. It can be shown (see [7, §5.4.2]) that the Lovász extension of a pseudo-Boolean function ψ : B n → IR is the continuous function

L ψ (x) = ∑ A⊆[n] a ψ (A) ∧ i∈A x i , x ∈ IR n .
Its restriction to IR n σ is the affine function

L ψ (x) = ψ(0) + ∑ i∈[n] x σ(i) ( v ψ (A ↑ σ (i)) -v ψ (A ↑ σ (i + 1)) ) , x ∈ IR n σ , (1)
or equivalently,

L ψ (x) = ψ(0) + ∑ i∈[n] x σ(i) ( L ψ (1 A ↑ σ (i) ) -L ψ (1 A ↑ σ (i+1) ) ) , x ∈ IR n σ , ( 2
)
where

A ↑ σ (i) = {σ(i), . . . , σ(n)}, with the convention that A ↑ σ (n+1) = ∅. Indeed, for any k ∈ [n + 1],
both sides of each of the equations ( 1) and (2) agree at

x = 1 A ↑ σ (k) .
It is noteworthy that L ψ can also be represented by

L ψ (x) = ψ(0) + ∑ i∈[n] x σ(i) ( L ψ (-1 A ↓ σ (i-1) ) -L ψ (-1 A ↓ σ (i) ) ) , x ∈ IR n σ ,
where A ↓ σ (i) = {σ(1), . . . , σ(i)}, with the convention that A ↓ σ (0) = ∅. Indeed, for any k ∈ [n+1], by [START_REF] Benvenuti | Monotone set functions-based integrals[END_REF] we have

L ψ (-1 A ↓ σ (k-1) ) = ψ(0)+L ψ (1 A ↑ σ (k) )-L ψ (1 A ↑ σ (1)
). Let ψ d denote the dual of ψ, that is the function

ψ d : B n → IR defined by ψ d (x) = ψ(0)+ψ(1)-ψ(1-x).
The next result provides further representations for L ψ .

Proposition 1. The Lovász extension of a pseudo-Boolean function

ψ : B n → IR is given by L ψ (x) = ψ(0) + ∑ A⊆[n] a ψ d (A) ∨ i∈A x i , and L ψ (x) = ψ(0) + L ψ (x + ) -L ψ d (x -). A function f : IR n → IR is said to be a Lovász extension if there is a pseudo- Boolean function ψ : B n → IR such that f = L ψ .
An n-place Choquet integral is a nondecreasing Lovász extension L ψ : IR n → IR such that L ψ (0) = 0. It is easy to see that a Lovász extension L : IR n → IR is an n-place Choquet integral if and only if its underlying pseudo-Boolean function ψ = L| B n is nondecreasing and vanishes at the origin (see [7, §5.4]).

The symmetric Lovász extension of a pseudo-Boolean function ψ : B n → IR is the function Ľ : IR n → IR defined by Ľψ (x) = ψ(0) + L ψ (x + ) -L ψ (x -) (see [START_REF] Couceiro | Axiomatizations of Lovász extensions and symmetric Lovász extensions of pseudo-Boolean functions[END_REF]). In particular, we see that Ľψ -Ľψ (0) = Ľψ -ψ(0) is an odd function.

It is easy to see that the restriction of Ľψ to IR n σ is the function

Ľψ (x) = ψ(0) + ∑ 1 i p x σ(i) ( L ψ (1 A ↓ σ (i) ) -L ψ (1 A ↓ σ (i-1) ) ) + ∑ p+1 i n x σ(i) ( L ψ (1 A ↑ σ (i) ) -L ψ (1 A ↑ σ (i+1) ) ) , x ∈ IR n σ ,
where the integer p ∈ {0, . . . , n} is such that x σ(p) < 0 x σ(p+1) .

A function f : IR n → IR is said to be a symmetric Lovász extension if there is a pseudo-Boolean function ψ : B n → IR such that f = Ľψ . Nondecreasing symmetric Lovász extensions vanishing at the origin, also called discrete symmetric Choquet integrals, were introduced by Šipoš [START_REF] Šipoš | Integral with respect to a pre-measure[END_REF] (see also [7, §5.4]).

Quasi-Lovász extensions and symmetric quasi-Lovász extensions

In this section we introduce the concepts of quasi-Lovász extension and symmetric quasi-Lovász extension. We also introduce natural relaxations of homogeneity, namely weak homogeneity and odd homogeneity, and present a characterization of those quasi-Lovász extensions (resp. symmetric quasi-Lovász extensions) that are weakly homogeneous (resp. oddly homogeneous). Recall that I is a real interval containing 0.

f 0 = L 0 • ϕ, where f 0 = f -f (0) and L 0 = L -L(0).
Lemma 2. Assume I ⊆ IR + . For every quasi-Lovász extension f :

I n → IR, f = L • ϕ, we have f 0 (x1 A ) = ϕ(x)L 0 (1 A ), x ∈ I, A ⊆ [n]. (3)
Observe that if [0, 1] ⊆ I ⊆ IR + and ϕ(1) = 1, then the equation in (3) becomes f 0 (x1 A ) = ϕ(x)f 0 (1 A ). This motivates the following definition. We say that a function f : I n → IR, where I ⊆ IR + , is weakly homogeneous if there exists a nondecreasing function ϕ : I → IR satisfying ϕ(0) = 0 such that f (x1 A ) = ϕ(x)f (1 A ) for every x ∈ I and every A ⊆ [n]. Clearly, every weakly homogeneous function f satisfies f (0) = 0 (take x = 0 in the definition).

I n → IR defined by f (x) = ∧ i∈[n] ϕ(x i )
, where ϕ(x) = 0 ∨ (x -1), is not weakly homogeneous. (b) When I = [0, 1], the assumption that f is nonconstant implies immediately that ϕ(1) = 0. We then see by Proposition 3 that f 0 is weakly homogeneous. Note also that, if f is constant, then f 0 ≡ 0 is clearly weakly homogeneous. Thus, for any quasi-Lovász extension f : [0, 1] n → IR, the function f 0 is weakly homogeneous.

Assume now that -x ∈ I whenever x ∈ I, that is, I is centered at 0. A symmetric quasi-Lovász extension is a function f : I n → IR defined by f = Ľ • ϕ, where Ľ : IR n → IR is a symmetric Lovász extension and ϕ : I → IR is a nondecreasing odd function.

We say that a function f : I n → IR, where I centered at 0, is oddly homogeneous if there exists a nondecreasing odd function ϕ :

I → IR such that f (x1 A ) = ϕ(x)f (1 A )

Comonotonic modularity

Recall that a function f : I n → IR is said to be modular (or a valuation) if

f (x) + f (x ) = f (x ∧ x ) + f (x ∨ x ) ( 4
)
for every x, x ∈ I n . It was proved (see Topkis [START_REF] Topkis | Minimizing a submodular function on a lattice[END_REF]Thm 3.3]) that a function f : I n → IR is modular if and only if it is separable, that is, there exist n functions

f i : I → IR, i ∈ [n], such that f = ∑ i∈[n] f i .
In particular, any 1-place function f : I → IR is modular.

Two n-tuples x, x ∈ I n are said to be comonotonic if there exists σ ∈ S n such that x, x ∈ I n σ . A function f : I n → IR is said to be comonotonically modular (or a comonotonic valuation) if ( 4) holds for every comonotonic n-tuples x, x ∈ I n . This notion was considered in the special case when I = [0, 1] in [START_REF] Mesiar | The ordered modular averages[END_REF]. We observe that, for any function f : I n → IR, condition (4) holds for every x, x ∈ I n of the forms x = x1 A and x = x 1 A , where x, x ∈ I and A ⊆ [n]. Observe also that, for every x ∈ IR n + and every c ∈ IR + , we have x -

x ∧ c = [x] c -c ∧ c
. This motivates the following definition. We say that a function f : I n → IR, where I ⊆ IR + , is invariant under horizontal min-differences if, for every x ∈ I n and every c ∈ I, we have

f (x) -f (x ∧ c) = f ([x] c ) -f ([x] c ∧ c).
(

Dually, we say that a function f : I n → IR, where I ⊆ IR -, is invariant under horizontal max-differences if, for every x ∈ I n and every c ∈ I, we have

f (x) -f (x ∨ c) = f ([x] c ) -f ([x] c ∨ c). ( 6
)
We observe that, for any function f : I n → IR, where I ⊆ IR + , condition (5) holds for every x ∈ I n of the form x = x1 A , where x ∈ I and A ⊆ [n]. Dually, for any function f : I n → IR, where I ⊆ IR -, condition (6) holds for every tuple x ∈ I n of the form x = x1 A , where x ∈ I and A ⊆ [n]. We also observe that a function f is comonotonically modular (resp. invariant under horizontal mindifferences, invariant under horizontal max-differences) if and only if so is the function f 0 . Theorem 7. Assume I ⊆ IR + and let f : I n → IR be a function. Then the following are equivalent.

(i) f is comonotonically modular. (ii) f is invariant under horizontal min-differences. (iii) There exists a function g : I n → IR such that, for every σ ∈ S n and every

x ∈ I n σ , we have

f (x) = g(0) + ∑ i∈[n] ( g(x σ(i) 1 A ↑ σ (i) ) -g(x σ(i) 1 A ↑ σ (i+1) )
) .

In this case, we can choose g = f .

Remark 8. The equivalence between (i) and (iii) in Theorem 7 generalizes Theorem 1 in [START_REF] Mesiar | The ordered modular averages[END_REF], which describes the class of comonotonically modular functions f : [0, 1] n → [0, 1] under the additional conditions of symmetry and idempotence.

We observe that if f : I n → IR is comonotonically modular then necessarily

f 0 (x) = f 0 (x + ) + f 0 (-x -) (take x = 0 in (4)).
We may now present a characterization of the class of comonotonically modular functions on an arbitrary interval I containing 0. Theorem 9. For any function f : I n → IR, the following are equivalent.

(i) f is comonotonically modular. (ii) There exist g : I n + → IR comonotonically modular (or invariant under horizontal min-differences) and h : I n -→ IR comonotonically modular (or invariant under horizontal max-differences) such that f 0 (x) = g 0 (x + ) + h 0 (-x -) for every x ∈ I n . In this case, we can choose g = f | I n + and h = f | I n -. (iii) There exist g : I n + → IR and h : I n -→ IR such that, for every σ ∈ S n and every x ∈ I n σ ,

f 0 (x) = ∑ 1 i p ( h(x σ(i) 1 A ↓ σ (i) ) -h(x σ(i) 1 A ↓ σ (i-1) ) ) + ∑ p+1 i n ( g(x σ(i) 1 A ↑ σ (i) ) -g(x σ(i) 1 A ↑ σ (i+1) )
) ,

where p ∈ {0, . . . , n} is such that x σ(p) < 0 x σ(p+1) . In this case, we can choose g = f | I n + and h = f | I n -. Remark 10. Observe that using condition (iii) in Theorems 7 and 9, we can easily derive characterizations of Choquet integrals and of symmetric Choquet integrals given in terms of comonotonic modularity. Indeed, we simply need to suppose that f : I n → IR is nondecreasing and satisfies

f (x1 A ) = xf (1 A ), for every x ∈ I and every A ⊆ [n],
and assume that [0, 1] ⊆ I ⊆ IR + (in Theorem 7) and that I is centered at 0 with [-1, 1] ⊆ I ⊆ IR (in Theorem 9).

From Theorem 9 we obtain the "comonotonic" analogue of Topkis' characterization [START_REF] Topkis | Minimizing a submodular function on a lattice[END_REF] of modular functions as separable functions, and which provides an alternative description of comonotonically modular functions.

Corollary 11. Let J be any nonempty real interval, possibly unbounded. A function f : J n → IR is comonotonically modular if and only if it is comonotonically separable, that is, for every σ ∈ S n , there exist functions

f σ i : J → IR, i ∈ [n], such that f (x) = n ∑ i=1 f σ i (x σ(i) ) = n ∑ i=1 f σ σ -1 (i) (x i ), x ∈ J n ∩ IR n σ .

Axiomatization and representation of quasi-Lovász extensions and their symmetric counterparts

We now present axiomatizations of the class of quasi-Lovász extensions and describe all possible factorizations of quasi-Lovász extensions into compositions of Lovász extensions with 1-place nondecreasing functions. Similarly, we provide analogous results concerning the class of symmetric quasi-Lovász extensions.

Theorem 12. Assume [0, 1] ⊆ I ⊆ IR + and let f : I n → IR be a nonconstant function. Then the following are equivalent.

(i) f is a quasi-Lovász extension and there exists A ⊆ [n] such that f 0 (1 A ) = 0.

(ii) f is comonotonically modular (or invariant under horizontal min-differences) and f 0 is weakly homogeneous. (iii) There is a nondecreasing function ϕ f :

I → IR satisfying ϕ f (0) = 0 and ϕ f (1) = 1 such that f = L f | B n • ϕ f .
Let f : I n → IR be a quasi-Lovász extension, where [0, 1] ⊆ I ⊆ IR + , for which there exists A * ⊆ [n] such that f 0 (1 A * ) = 0. Then the inner function ϕ f introduced in Theorem 12 is unique. Indeed, by Proposition 3, we have f 0 Remark 16. If I = [-1, 1], then the "nonconstant" assumption and the second condition in assertion (i) of Theorem 14 can be dropped off.

(x1 A ) = ϕ f (x)f 0 (1 A ) for every x ∈ I and every A ⊆ [n]. The function ϕ f is then defined by ϕ f (x) = f0(x1 A * ) f0(1 A * ) , x ∈ I.

  A quasi-Lovász extension is a function f : I n → IR defined by f = L • (ϕ, . . . , ϕ), also written f = L•ϕ, where L : IR n → IR is a Lovász extension and ϕ : I → IR is a nondecreasing function satisfying ϕ(0) = 0. Observe that a function f : I n → IR is a quasi-Lovász extension if and only if

Proposition 3 .

 3 Assume [0, 1] ⊆ I ⊆ IR + . Let f : I n → IR be a nonconstant quasi-Lovász extension, f = L • ϕ. Then the following are equivalent. (i) f 0 is weakly homogeneous. (ii) There exists A ⊆ [n] such that f 0 (1 A ) = 0. (iii) ϕ(1) = 0. In this case we have f 0 (x1 A ) = ϕ(x) ϕ(1) f 0 (1 A ) for every x ∈ I and every A ⊆ [n]. Remark 4. (a) If [0, 1] I ⊆ IR + , then the quasi-Lovász extension f :

5 .Remark 6 .

 56 for every x ∈ I and every A ⊆ [n]. Clearly, for every oddly homogeneous function f , the functions f | I n + and f | I n -are weakly homogeneous. Proposition Assume that I is centered at 0 with [-1, 1] ⊆ I. Let f : I n → IR be a symmetric quasi-Lovász extension, f = Ľ • ϕ, such that f | I n + or f | I n -is nonconstant. Then the following are equivalent. (i) f 0 is oddly homogeneous. (ii) There exists A ⊆ [n] such that f 0 (1 A ) = 0. (iii) ϕ(1) = 0. In this case we have f 0 (x1 A ) = ϕ(x) ϕ(1) f 0 (1 A ) for every x ∈ I and every A ⊆ [n]. Similarly to Remark 4(b), we see that, for any symmetric quasi-Lovász extension f : [-1, 1] n → IR, the function f 0 is oddly homogeneous.

Theorem 13 .Theorem 14 .

 1314 Assume [0, 1] ⊆ I ⊆ IR + and let f : I n → IR be a quasi-Lovász extension, f = L • ϕ. Then there exists A * ⊆ [n] such that f 0 (1 A * ) = 0 if and only if there exists a > 0 such that ϕ = a ϕ f andL 0 = 1 a (L f | B n ) 0 .We now present an axiomatization of the class of symmetric quasi-Lovász extensions and describe all possible factorizations of symmetric quasi-Lovász extensions into compositions of symmetric Lovász extensions with 1-place nondecreasing odd functions. Assume that I is centered at 0 with [-1, 1] ⊆ I and let f :I n → IR be a function such that f | I n + or f | I n -is nonconstant.Then the following are equivalent.(i) f is a symmetric quasi-Lovász extension and there exists A ⊆ [n] such that f 0 (1 A ) = 0. (ii) f is comonotonically modular and f 0 is oddly homogeneous. (iii) There is a nondecreasing odd function ϕ f :I → IR satisfying ϕ f (1) = 1 such that f = Ľf| B n • ϕ f .Assume again that I is centered at 0 with [-1, 1] ⊆ I and let f : I n → IR be a symmetric quasi-Lovász extension for which there exists A * ⊆ [n] such that f 0 (1 A * ) = 0. Then the inner function ϕ f introduced in Theorem 14 is unique. Indeed, by Proposition 5, we havef 0 (x1 A ) = ϕ f (x)f 0 (1 A ) for every x ∈ I and every A ⊆ [n]. The function ϕ f is then defined by ϕ f (x) = f0(x1 A * ) f0(1 A * ) , x ∈ I.Theorem 15. Assume that I is centered at 0 with [-1, 1] ⊆ I and let f :I n → IR be a symmetric quasi-Lovász extension, f = Ľ • ϕ. Then there exists A * ⊆ [n]such that f 0 (1 A * ) = 0 if and only if there exists a > 0 such that ϕ = a ϕ f and Ľ0 = 1 a ( Ľf| B n ) 0 .

Acknowledgments

This research is supported by the internal research project F1R-MTH-PUL-09MRDO of the University of Luxembourg.