domain: math info

text:
Miguel Couceiro

Erkko Lehtonen

Tam Ás Waldhauser

ADDITIVE DECOMPOSABILITY OF FUNCTIONS OVER ABELIAN GROUPS

Abelian groups are classified by

Introduction

The arity gap of a function f : A n → B is defined as the minimum decrease in the number of essential variables when essential variables of f are identified. Up to the authors' knowledge, this notion first appeared in the 1963 paper by Salomaa [START_REF] Salomaa | On essential variables of functions, especially in the algebra of logic[END_REF], where it was shown that the arity gap of every Boolean function is at most 2. Willard [START_REF] Willard | Essential arities of term operations in finite algebras[END_REF] generalized this by showing that a function f : A n → B defined on a finite set A and depending on all of its variables has arity gap at most 2 whenever n > max(|A|, 3); moreover, the arity gap of such a function equals 2 if and only if f is determined by oddsupp (see Section 2 for definitions). Several papers on the topic have appeared ever since, 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 | 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 | Essential arity gap of Boolean functions[END_REF][START_REF] Shtrakov | On finite functions with non-trivial arity gap[END_REF]. A complete classification of functions according to their arity gap was presented in [START_REF] Couceiro | Generalizations of Świerczkowski's lemma and the arity gap of finite functions[END_REF].

In a previous paper of the authors' [START_REF] Couceiro | Decompositions of functions based on arity gap[END_REF], unique additive decompositions of functions f : A n → B were presented, assuming that B has a group structure and the arity gap of f is at least 3. Similar decompositions were also proposed by Shtrakov and Koppitz [START_REF] Shtrakov | On finite functions with non-trivial arity gap[END_REF]. Further decompositions were also established in [START_REF] Couceiro | Decompositions of functions based on arity gap[END_REF] for functions whose arity gap is 2, but in this case the codomain B was required to be a Boolean group. In the current paper, we study similar additive decompositions of functions f : A n → B into sums of functions with a smaller number of essential variables, assuming that B is an abelian group. We show that such a decomposition exists for all functions f : A n → B determined by oddsupp if and only if A is finite and the exponent of B is a power of 2.

Preliminaries

2.1. Functions, essential variables, the arity gap. Throughout this paper, let A and B be arbitrary sets with at least two elements. A partial function (of several variables) from A to B is a mapping f : S → B, where S ⊆ A n for some integer n ≥ 1, called the arity of f . If S = A n , then we speak of (total ) functions (of several variables). Functions of several variables from A to A are referred to as operations on A.

For an integer n ≥ 1, let [n] := {1, . . . , n}. Let f : S → B (S ⊆ A n ) be an n-ary partial function and let i ∈ [n]. We say that the i-th variable is essential in f (or f depends on x i ), if there exist tuples (a 1 , . . . , a i-1 , a i , a i+1 , . . . , a n ), (a 1 , . . . , a i-1 , a ′ i , a i+1 , . . . , a n ) ∈ S such that f (a 1 , . . . , a i-1 , a i , a i+1 , . . . , a n ) = f (a 1 , . . . , a i-1 , a ′ i , a i+1 , . . . , a n ). Variables that are not essential are called inessential. The cardinality of the set Ess f := {i ∈ [n] : x i is essential in f } is called the essential arity of f and is denoted by ess f . Let f : A n → B, g : A m → B. We say that g is a simple minor of f , if there is a map σ : [n] → [m] such that g(x 1 , . . . , x m ) = f (x σ(1) , . . . , x σ(n) ). We say that f and g are equivalent if each one is a simple minor of the other.

For i, j ∈ [n], i = j, define the identification minor of f : A n → B obtained by identifying the i-th and the j-th variable as the simple minor f i←j : A n → B of f corresponding to the map σ : [n] → [n], i → j, ℓ → ℓ for ℓ = i, i.e., f i←j is given by the rule f i←j (x 1 , . . . , x n ) := f (x 1 , . . . , x i-1 , x j , x i+1 , . . . , x n ).

Observe that a function g is a simple minor of f , if g can be obtained from f by permutation of variables, addition and deletion of inessential variables and identification of variables. Similarly, two functions are equivalent, if one can be obtained from the other by permutation of variables and addition of inessential variables.

The arity gap of f is defined as

gap f := min i,j∈Ess f i =j (ess f -ess f i←j ).
Note that the definition of arity gap makes reference to essential variables only. Hence, in order to determine the arity gap of a function f , we may consider instead an equivalent function f ′ that is obtained from f by deleting its inessential variables. It is easy to see that in this case gap f = gap f ′ . Therefore, we may assume without loss of generality that every function the arity gap of which we may consider depends on all of its variables.

For general background and studies on the dependence of functions on their variables, see, e.g., [START_REF] Čimev | On some properties of functions[END_REF][START_REF] Čimev | Separable Sets of Arguments of Functions[END_REF][START_REF] Davies | Two theorems on essential variables[END_REF][START_REF] Denecke | Essential variables in hypersubstitutions[END_REF][START_REF] Ehrenfeucht | On the dependence of functions on their variables[END_REF][START_REF] Salomaa | On essential variables of functions, especially in the algebra of logic[END_REF][START_REF] Solovjev | On the question of the essential dependence of functions of the algebra of logic[END_REF][START_REF] Wernick | An enumeration of logical functions[END_REF][START_REF] Yablonski | Functional constructions in a k-valued logic[END_REF]. For the simple minor relation and its variants, see, e.g., [START_REF] Bouaziz | Join-irreducible Boolean functions[END_REF][START_REF] Couceiro | On a quasi-ordering on Boolean functions[END_REF][START_REF] Ekin | Equational characterizations of Boolean function classes[END_REF][START_REF] Hellerstein | On generalized constraints and certificates[END_REF][START_REF] Lehtonen | Descending chains and antichains of the unary, linear, and monotone subfunction relations[END_REF][START_REF] Lehtonen | Clones with finitely many relative R-classes[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]. The notion of arity gap was considered in [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] Salomaa | On essential variables of functions, especially in the algebra of logic[END_REF][START_REF] Shtrakov | Essential arity gap of Boolean 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], and a general classification of functions according to their arity gap was established in [START_REF] Couceiro | Generalizations of Świerczkowski's lemma and the arity gap of finite functions[END_REF], given in terms of the notions of quasi-arity and determination by oddsupp. The following explicit complete classification of Boolean functions was established in [START_REF] Couceiro | On the effect of variable identification on the essential arity of functions on finite sets[END_REF].

Theorem 2.1. Let f : {0, 1} n → {0, 1} be a Boolean function with at least two essential variables. Then gap f = 2 if and only if f is equivalent to one of the following polynomial functions over GF(2):

(1)

x 1 + x 2 + • • • + x m + c for some m ≥ 2, ( 2
) x 1 x 2 + x 1 + c, ( 3
) x 1 x 2 + x 1 x 3 + x 2 x 3 + c, ( 4
) x 1 x 2 + x 1 x 3 + x 2 x 3 + x 1 + x 2 + c, where c ∈ {0, 1}. Otherwise gap f = 1.
2.2. Functions determined by oddsupp. We will denote tuples by boldface letters and their components by the corresponding italic letters with subscripts, e.g., x = (x 1 , . . . , x n ) ∈ A n . For I ⊆ [n] and x ∈ A n , let x| I ∈ A I stand for the tuple that is obtained from x by deleting the i-th component of x for every i / ∈ I. More precisely, if

I = {i 1 , . . . , i k } and i 1 < • • • < i k , then x| I = (x i1 , . . . , x i k ).
Berman and Kisielewicz [START_REF] Berman | On the number of operations in a clone[END_REF] introduced the following notion of a function's being determined by oddsupp. Denote by P(A) the power set of A, and define the function oddsupp : n≥1 A n → P(A) by oddsupp(a 1 , . . . , a n ) := {a ∈ A : |{j ∈ [n] : a j = a}| is odd}. It was shown by Willard [28] that if the essential arity of a function f : A n → B is sufficiently large, then gap f ≤ 2, and he also classified such functions according to their arity gap.

For ϕ : P(A) → B, let ❄ ϕ : n≥1 A n → B be defined by ❄ ϕ (x) = ϕ(oddsupp(x)). A function f : S → B (S ⊆ A n ) is determined by oddsupp if f (x)
Theorem 2.5 (Willard [START_REF] Willard | Essential arities of term operations in finite algebras[END_REF]). Let A be a finite set and B be an arbitrary set, and assume that f : A n → B depends on all of its variables and n > max(|A|, 3). If f is determined by oddsupp then gap f = 2. Otherwise gap f = 1.

If B is a Boolean group (i.e., an abelian group of exponent 2), then functions f with gap f ≥ 2 can be characterized by the existence of certain additive decompositions. Here we present one of the main results of [START_REF] Couceiro | Decompositions of functions based on arity gap[END_REF] in the case n > max(|A|, 3). In this case, by Theorem 2.5, gap f ≥ 2 if and only if f is determined by oddsupp.

Theorem 2.6 ([8]

). Let (B; +) be a Boolean group, and let f : A n → B be determined by oddsupp. Then there exists a map ϕ :

P ′ n (A) → B such that (1) f (x) = ⌊ n 2 ⌋ i=1 I⊆[n] |I|=n-2i ❄ ϕ (x| I ).
Equation (1) expresses the fact that every function f : A n → B with large enough essential arity and gap f = 2 is decomposable into a sum of essentially at most (n -2)-ary functions. This fact is the starting point of the current paper. We will prove in Section 3 that such decompositions exist not only when B is a Boolean group, but also whenever B is a group whose exponent is a power of 2. In fact, we will show that in this case there is a decomposition into functions with bounded essential arity, where the bound does not depend on n. We will also see that if the exponent of B is not a power of 2, then such a decomposition does not always exist, not even a decomposition into (n -1)-ary functions. In Section 4 we focus on Boolean groups B, and we provide a concrete decomposition of a very special symmetric form, which is also unique.

Any set B can embedded into a Boolean group, e.g., into P(B) with the symmetric difference operation. Then we can regard any function f : A n → B as a function from A n to P(B), and we can apply the results of Section 4 to this function. We illustrate this for the case A = B = Z 3 in Section 5. Here we obtain decompositions involving a strange mixture of the field operations on Z 3 and the symmetric difference operation, but we will see that they can be always computed within B, without the need of working in the extension P(B).

Binomial coefficients.

We shall make use of the following combinatorial results.

Theorem 2.7 (Shattuck, Waldhauser [START_REF] Shattuck | Proofs of some binomial identities using the method of last squares[END_REF]). For all nonnegative integers m, t with 0 ≤ t ≤ m 2 -1, the following identity holds:

⌊ m 2 ⌋ i=t+1 m 2i i -1 t = 2 m-2t-1 ⌊ t 2 ⌋ k=0 m -3 -t -2k t -2k + (-1) t+1 .
Theorem 2.8. For all nonnegative integers m, t with 0 ≤ t ≤ m-1 2 the following identity holds:

⌊ m+1 2 ⌋ k=t+1 m 2k -1 2k -1 2t = m 2t 2 m-2t-1 .
Proof. Both sides of the identity count the number of pairs (A, B), where A ⊆ B ⊆ [m], |A| = 2t, and |B| is odd.

The general case

Throughout this section, unless mentioned otherwise, A is a finite set with a distinguished element 0 A and (B; +) is an arbitrary, possibly infinite abelian group with neutral element 0 B . With no risk of ambiguity, we will omit the subscripts and will denote both 0 A and 0 B by 0. Recall that the order of b ∈ B, denoted by ord(b), is the smallest positive integer

n such that nb = b + • • • + b n times = 0. If there is no such positive integer, then ord(b) = ∞.
If the orders of all elements of B have a finite common upper bound, then the exponent of B, denoted by exp(B), is the least common upper bound (equivalently, the least common multiple) of these orders. Otherwise let exp(B) = ∞. Note that a Boolean group is a group of exponent 2.

We say that a function f :

A n → B is k-decomposable if it admits an additive decomposition f = f 1 + • • • + f s , where the essential arity of each f i : A n → B is at most k. Moreover, we say that f is decomposable if it is (n -1)-decomposable.
According to Fact 2.2, every Boolean function determined by oddsupp is 1decomposable, while the functions described in Theorem 2.6 are (n -2)-decomposable. Our goal in this section is to extend these results by characterizing those abelian groups B which have the property that every function f : A n → B determined by oddsupp is decomposable. As we will see, this is the case if and only if exp(B) is a power of 2. Moreover, we will determine, for each such abelian group B, the smallest number k such that every function f : A n → B determined by oddsupp is k-decomposable.

The Taylor formula developed for finite functions by Gilezan [START_REF] Gilezan | Taylor formula of Boolean and pseudo-Boolean function[END_REF] provides a tool to test decomposability of functions. Although in [START_REF] Gilezan | Taylor formula of Boolean and pseudo-Boolean function[END_REF] the codomain B was assumed to be a ring, only multiplication by 0 and 1 was used in the Taylor formula; hence it is valid for abelian groups as well. For self-containedness, we present here the formula with a proof (see Proposition 3.2).

For a given x ∈ A n and i ∈ [n], a ∈ A, let x a i denote the n-tuple that is obtained from x by replacing its i-th component by a. More generally, for I ⊆ [n] and a ∈ A n , let x a I denote the n-tuple that is obtained from x by replacing its i-th component by a i for every i ∈ I. (Observe that the components a i of a with i / ∈ I are irrelevant in determining x a I .) For any a ∈ A and i ∈ [n] we define the partial derivative of f : A n → B with respect to its i-th variable with parameter a as the function ∆ a i f :

A n → B given by ∆ a i f (x) = f (x a i ) -f (x)
. Note that for each parameter a ∈ A we have a different partial derivative of f with respect to its i-th variable. We need the parameter a because A is just a set without any structure; hence we cannot define differences like f (x + h)f (x). It is easy to verify that the i-th variable of f is inessential if and only if ∆ a i f is identically 0 for some a ∈ A (equivalently, for all a ∈ A).

Clearly, the partial derivatives are additive, i.e., ∆ a i (f + g) = ∆ a i f + ∆ a i g. Moreover, differentiations with respect to different variables commute with each other:

(2) ∆ a i ∆ b j f (x) = ∆ b j ∆ a i f (x) = f (x ab ij ) -f (x a i ) -f (x b j ) + f (x) for all a, b ∈ A, i = j ∈ [n]. (Here x ab ij is a shorthand notation for (x a i ) b j = (x b j ) a i .
) This property allows us to define higher-order derivatives: for

I = {i 1 , . . . , i k } ⊆ [n] and a ∈ A n let ∆ a I f = ∆ a1 i1 • • • ∆ a k i k f .
(Again, the components a i (i / ∈ I) are irrelevant.) The following proposition generalizes formula (2) above. Proposition 3.1. For any function f : A n → B, I ⊆ [n] and a ∈ A n , we have

∆ a I f (x) = J⊆I (-1) |I\J| f (x a J ).
Proof. Easy induction on |I|. (For |I| = 2, the identity is just (2).)

Now we are ready to state and prove the Taylor formula for functions f : A n → B, which is essentially the same as Theorem 2 and Theorem 3 in [START_REF] Gilezan | Taylor formula of Boolean and pseudo-Boolean function[END_REF]. (Let us note that in the following considerations any fixed n-tuple a ∈ A n could be used instead of 0.) Proposition 3.2. Any function f : A n → B can be expressed as a sum of some of its partial derivatives at 0:

(3) f (x) = I⊆[n] ∆ x I f (0).
Proof. Using Proposition 3.1, we can compute the right-hand side as follows:

I⊆[n] ∆ x I f (0) = I⊆[n] J⊆I (-1) |I\J| f (0 x J ).
Observe that K := I \ J can be any subset of [n] \ J. Hence

I⊆[n] J⊆I (-1) |I\J| f (0 x J ) = J⊆[n] K⊆[n]\J (-1) |K| f (0 x J ) = J⊆[n] K⊆[n]\J (-1) |K| f (0 x J ).
Since a nonempty finite set has the same number of subsets of odd cardinality as subsets of even cardinality, the coefficient

K⊆[n]\J (-1) |K| of f (0 x J ) above is 0 unless J = [n]. Thus the sum reduces to f (0 x [n] ) = f (x)
, and this proves the theorem.

The following proposition provides a useful criterion of decomposability.

Proposition 3.3. A function f : A n → B is k-decomposable if and only if ∆ a I f (0) = 0 for all a ∈ A n and I ⊆ [n] with more than k elements.
Proof. Sufficiency follows directly from Proposition 3.2: clearly, the essential arity of the function 3) is a decomposition into a sum of essentially at most k-ary functions.

x → ∆ x I f (0) is at most |I|. Therefore, if ∆ x I f (0) vanishes whenever |I| > k, then (
For necessity, let us suppose that

f = f 1 + • • • + f s , where ess f i ≤ k for i ∈ [s]. If |I| > k, then I contains (the index of) at least one of the inessential variables of f i , hence ∆ a I f i is constant 0 for every a ∈ A n and i ∈ [s]. Since ∆ a I f = ∆ a I f 1 + • • • + ∆ a I f s , we can conclude that ∆ a I f is constant 0 as well. In particular, we have ∆ a I f (0) = 0.
The following two theorems constitute the main results of this section, and they show a strong dichotomy of abelian groups with respect to the decomposability of functions determined by oddsupp.

a i = b j }. Thus |B j | is the number of occurrences of b j in a| I ; hence |B 1 | + • • • + |B t | = |I| and t ≤ |A|. Using Proposition 3.1, we can expand ∆ a I f (0) as (4) ∆ a I f (0) = J⊆I (-1) |I\J| f (0 a J ) = J⊆I (-1) |I\J| ϕ(oddsupp(0 a J )).
Let us fix a set S ⊆ A that appears as oddsupp(0 a J ) in the above sum. Assume first that 0 ∈ {b 1 , . . . , b t }, say b t = 0. Then oddsupp(0 a J ) = S if and only if |J ∩ B j | is odd whenever b j ∈ S and |J ∩ B j | is even whenever b j / ∈ S for j = 1, . . . , t -1 (note that J ∩ B t is irrelevant in determining 0 a J ). Since the number of subsets of B t of even cardinality equals the number of subsets of B t of odd cardinality, it holds that the number of sets J satisfying oddsupp(0 a J ) = S that have an even cardinality equals the number of those that have an odd cardinality. Hence, the terms corresponding to such sets J will cancel each other in [START_REF] Čimev | Separable Sets of Arguments of Functions[END_REF].

Assume now that 0 / ∈ {b 1 , . . . , b t }. Then clearly t ≤ |A| -1. Similarly, as in the previous case, we have that oddsupp(0 a J ) = S if and only if |J ∩ B j | is odd whenever b j ∈ S and |J ∩ B j | is even whenever b j / ∈ S for j = 1, . . . , t. Therefore, the number of sets J ⊆ I satisfying oddsupp(0

a J ) = S is 2 |B1|-1 • • • 2 |Bt|-1 = 2 |B1|+•••+|Bt|-t = 2 |I|-t .
Moreover, the parity of |J| is determined by S. Therefore, all occurrences of ϕ(S) in ( 4) have the same sign.

By the argument above, ∆ a I f (0) can be written as a sum of finitely many terms of the form ±2 |I|-t ϕ(S), where t ≤ |A| -1. Since |I| ≥ |A| + e -1, the coefficient 2 |I|-t is a multiple of 2 e ; hence ±2 |I|-t ϕ(S) = 0 independently of the value of ϕ(S). We conclude that ∆ a I f (0) = 0, as claimed. As the following example shows, Theorem 3.4 cannot be improved and the number |A| + e -2 cannot be decreased. More precisely, for every finite set A with at least two elements, for every abelian group B of exponent 2 e , and for every n > |A| + e -3, there exists a function f : A n → B that is determined by oddsupp but is not (|A| + e -3)-decomposable.

Example 3.5. Let A = {0, 1, . . . , ℓ}, and let B be an arbitrary abelian group of exponent 2 e . Fix an element b ∈ B of order 2 e . Let ϕ : P(A) → B be defined by

ϕ(T ) = b, if T ⊇ A \ {0}, 0, otherwise, let n ≥ ℓ + e -1,

and let

f : A n → B be given by f (x) = ❄ ϕ (x).
To see that f is not (|A| + e -3)-decomposable, by Proposition 3. ),

and let I := {1, 2, . . . , ℓ + e -1}. Consider the expansion of ∆ a I f (0) as in [START_REF] Čimev | Separable Sets of Arguments of Functions[END_REF]. We can verify that for all J ⊆ I, f (0 a J ) = b, if J ⊇ {1, . . . , ℓ -1} and |J ∩ {ℓ, . . . , ℓ + e -1}| is odd, 0, otherwise.

From this it follows that the number of sets J ⊆ I satisfying f (0 a J ) = b is 2 e-1 . Therefore, we have ∆ a I f (0) = (-1) e-1 2 e-1 b = 0, where the inequality holds because the order of b is 2 e . Theorem 3.6. If A is a finite set with at least two elements and B is an abelian group whose exponent is not a power of 2, then for each n there exists a function f : A n → B determined by oddsupp that is not decomposable.

Proof. If the exponent of B is not a power of 2, then it has an element b whose order is not a power of 2 (possibly infinite). Let us consider first the special case A = {0, 1}. For any x ∈ A n let w(x) denote the Hamming weight of x, i.e., the number of 1's appearing in x. Let f 0 : A n → B be the function defined by

f 0 (x) = b, if w(x) is even, 0, if w(x) is odd.
Let us compute ∆ 1

[n] f 0 (0) with the help of Proposition 3.1:

∆ 1 [n] f 0 (0) = J⊆[n] (-1) |[n]\J| f 0 (0 1 J ) = (-1) n J⊆[n]
(-1) |J| f 0 (0 1 J ).

Since w(0 1 J ) = |J|, the above sum consists of 2 n-1 many b's and 2 n-1 many 0's. Thus ∆ 1

[n] f 0 (0) = (-1) n 2 n-1 b = 0, as ord(b) does not divide (-1) n 2 n-1 . Now Proposition 3.3 shows that f 0 is not (n -1)-decomposable.

Considering the general case, let 0 and 1 be two distinguished elements of A, and let f : A n → B be any function that is determined by oddsupp such that f | {0,1} n = f 0 . Then f is not decomposable, since any decomposition of f would give rise to a decomposition of f | {0,1} n . Corollary 3.7. Let A be a finite set with at least two elements, and B be an abelian group. All functions f : A n → B determined by oddsupp are decomposable if and only if the exponent of B is a power of 2.

As following example shows, decomposability is not guaranteed when A is infinite, no matter what the exponent of B is.

f (x) = b, if {x 1 , . . . , x n } = S, 0, otherwise.
It is clear that f is determined by oddsupp. Computing ∆ a

[n] f (0) for a := (s 1 , . . . , s n ) as in (4), we obtain ∆ a

[n] f (0) = b = 0. Hence f is not decomposable by Proposition 3.3. Remark 3.9. Theorem 2.6 asserts that if B is a Boolean group and n > |A|, then every function f : A n → B determined by oddsupp is (n -2)-decomposable. Theorem 3.4 gives a stronger result as it provides a decomposition into a sum of functions whose essential arity has an upper bound that depends only on A and B (and not on n). Theorem 3.6 implies that if exp(B) is not a power of 2, then even the weakest kind of decomposability (namely, (n -1)-decomposability) fails to hold for all functions f : A n → B determined by oddsupp.

The case of Boolean groups

In this section we assume that A is a finite set with a distinguished element 0 and (B; +) is a Boolean group with neutral element 0. Applying Theorem 3.4 to this case (with e = 1), we see that every function f : A n → B determined by oddsupp is (|A| -1)-decomposable. Here we will provide a canonical, highly symmetric decomposition of such functions and show that it is unique.

If

(5) f (x) = ⌊ n 2 ⌋ i=t+1 I⊆[n] |I|=n-2i i -1 t ❄ ϕ (x| I ),
for some map ϕ : P ′ n (A) → B. Moreover, ϕ is uniquely determined by f .

Proof. Let g ϕ : A n → B denote the function given by the right-hand side of ( 5). Let us note that since n > |A| and n -|A| is odd, P ′ n (A) contains all subsets of A whose complement has an odd number of elements. Observe also that in (5) I ranges over subsets of [n] of size |A|-1, |A|-3, . . .; hence (5) provides an (|A|-1)-decomposition of f . Clearly, for such sets I we have oddsupp(x| I ) ∈ P ′ n (A). To prove the theorem, it suffices to show that the following three statements hold:

(i) the number of functions f : A n → B that are determined by oddsupp is the same as the number of maps ϕ : P ′ n (A) → B; (ii) g ϕ is determined by oddsupp for every ϕ :

P ′ n (A) → B; (iii) if ϕ 1 = ϕ 2 then g ϕ1 = g ϕ2 .
The existence and uniqueness of the decomposition then follows by a simple counting argument: the functions f : A n → B determined by oddsupp are in a one-to-one correspondence with the functions g ϕ . (Alternatively, the existence could be proved by repeated applications of Theorem 2.6, as explained above.) Statement (i) is clear: the number of functions f : A n → B that are determined by oddsupp is |B| |P ′ n (A)| , the same as the number of maps ϕ : P ′ n (A) → B. To see that (ii) holds, observe that each g ϕ is a totally symmetric function. Hence, by Fact 2.3, it suffices to prove that g ϕ (x 1 , x 1 , x 3 , . . . , x n ) does not depend on x 1 . Let x = (x 1 , x 1 , x 3 , . . . , x n ) and let I be a set appearing in the summation in [START_REF] Couceiro | On the effect of variable identification on the essential arity of functions on finite sets[END_REF] and hence ❄ ϕ (x| I ) does not depend on x 1 , whereas in the second case x 1 does not appear in ❄ ϕ (x| I ) at all. Thus g ϕ (x 1 , x 1 , x 3 , . . . , x n ) does not depend on x 1 , which shows that (ii) holds.

To prove (iii), suppose on the contrary that there exist maps ϕ 1 , ϕ 2 : P ′ n (A) → B such that ϕ 1 = ϕ 2 but g ϕ1 = g ϕ2 . Then for ϕ = ϕ 1 + ϕ 2 we have g ϕ = g ϕ1 + g ϕ2 ≡ 0 by Fact 2.4, that is, (6)

⌊ n 2 ⌋ i=t+1 I⊆[n] |I|=n-2i i -1 t ❄ ϕ (x| I ) = 0
for all x ∈ A n . Moreover, since ϕ 1 = ϕ 2 , there exists an S ∈ P ′ n (A) with ϕ(S) = 0. Let us choose S to be minimal with respect to this property, i.e., ϕ(S) = 0, but ϕ vanishes on all proper subsets of S.

Suppose first that S is nonempty, S = {s 1 , . . . , s n-2r }. Since n-|A| = 2t+1, we have that t ≤ r -1. Let us examine the left-hand side of ( 6 i -1 t ϕ(S).

Since r ≥ t + 1, the coefficient r i=t+1

2r+1 2i i-1 t
of ϕ(S) is odd according to Theorem 2.7 (for m = 2r + 1). Therefore, taking into account that B is a Boolean group, we can conclude that the left-hand side of ( 6) is ϕ(S) = 0, which is a contradiction.

Suppose then that S is empty. Choose x := (s 1 , . . . , s 1 ) for an arbitrary s 1 ∈ A. Since S ∈ P ′ n (A), n is even and hence each I occurring in ( 6) is of even cardinality.

Whenever |I| is even, oddsupp(x| I ) = ∅ = S and ❄ ϕ (x| I ) = ϕ(S). Therefore, the left-hand side of (6) becomes

⌊ n 2 ⌋ i=t+1 n 2i i -1 t ϕ(S),
which equals ϕ(S) by Theorem 2.7 (for m = n). This yields the desired contradiction, and the proof of (iii) is now complete.

Theorem 4.2. Let f : A n → B, where B is a finite Boolean group, A is a finite set, and n -|A| = 2t > 0. Then f is determined by oddsupp if and only if f is of the form

(7) f (x) = ⌊ n 2 ⌋ i=t+1 I⊆[n] |I|=n-2i i -1 t ❄ ϕ (x| I ) + ⌊ n+1 2 ⌋ k=t+1 K⊆[n] |K|=n-2k+1 2k -1 2t ❄ ϕ (x| K ).
for some map ϕ : P(A) → B satisfying ϕ(S) = ϕ(S △ {0}) for every S ∈ P(A). Moreover, ϕ is uniquely determined by f .

Proof. Let us note first that since n > |A| and n -|A| is even, P ′ n (A) contains all subsets of A whose complement has an even number of elements. The number of maps ϕ : P(A) → B satisfying ϕ(S) = ϕ(S △ {0}) for every S ∈ P(A) is |B| |P ′ n (A)| , since ϕ| P ′ n (A) can be chosen arbitrarily, and this uniquely determines ϕ| P(A)\P ′ n (A) . The number of functions f :

A n → B that are determined by oddsupp is |B| |P ′ n (A)|
as well, and we can use the same counting argument as in the proof of Theorem 4.1. The fact that the right-hand side of ( 7) is determined by oddsupp can be proven in a similar way, and for the uniqueness it suffices to prove that if (8)

⌊ n 2 ⌋ i=t+1 I⊆[n] |I|=n-2i i -1 t ❄ ϕ (x| I ) + ⌊ n+1 2 ⌋ k=t+1 K⊆[n] |K|=n-2k+1 2k -1 2t ❄ ϕ (x| K ) = 0
for all x ∈ A n , then ϕ| P ′ n (A) is identically 0. Suppose, for the sake of contradiction, that there exists an S ∈ P ′ n (A) such that ϕ(S) = 0, and let n -2r be the cardinality of the smallest such S. If r = t, then ϕ(A) = ϕ(A \ {0}) = 0, and ϕ is zero on all other subsets of A. Let A = {0, a 1 , . . . , a ℓ }, where ℓ = n -2t -1, and let x = (0, . . . , 0, a 1 , . . . , a ℓ ) ∈ A n , where the number of 0's is 2t + 1. Then, for any set I appearing in the first summation of (8), we have A \ {0} oddsupp(x| I ); hence ❄ ϕ (x| I ) = 0. Similarly, ❄ ϕ (x| K ) = 0 for all sets K appearing in [START_REF] Couceiro | Decompositions of functions based on arity gap[END_REF], except for K = {2t + 2, . . . , n}, where ❄ ϕ (x| K ) = ϕ(A \ {0}). Thus the left-hand side of (8) equals ϕ(A \ {0}) = 0, contrary to our assumption.

Let us now consider the case r > t, and let us suppose first that there exists a set S ∈ P ′ n (A) of cardinality n -2r such that ϕ(S) = 0 and 0 ∈ S, say S = {s 1 , . . . , s n-2r } with s 1 = 0. Let T be a subset of S. By Theorem 2.8, the coefficient of ϕ(S) here is 2r+1 2t 2 2r-2t , which is even since r > t. Thus the left-hand side of (8) reduces to ϕ(S), contradicting our assumption.

In the remaining case we have r > t and for all S ∈ P ′ n (A) of cardinality n -2r we have 0 / ∈ S whenever ϕ(S) = 0. Let S = {s 1 , . . . , s n-2r } be such a set, and Let us choose x := (s 1 , . . . , s 1 , s 2 , . . . , s n-2r ) ∈ A n as before, and examine the summands in [START_REF] Couceiro | Decompositions of functions based on arity gap[END_REF]. For each K appearing in the second sum, oddsupp(x| K ) ⊆ S and oddsupp(x| K ) / ∈ P ′ n (A), thus ❄ ϕ (x| K ) = 0. For each I appearing in the first sum, we have ❄ ϕ (x| I ) = ϕ(S) = 0 if I is a proper superset of {2r + 2, . . . , n}; otherwise oddsupp(x| I ) ⊂ S, and so ❄ ϕ (x| I ) = 0. Therefore, using Theorem 2.7 as before, we can conclude that the left-hand side of (8) equals ϕ(S), and this contradiction finishes the proof of the theorem.

Remark 4.3. Theorems 4.1 and 4.2 still hold for infinite Boolean groups B. To see this, let f : A n → B be a function that is determined by oddsupp, where A is a finite set and B is a possibly infinite Boolean group, and let R ⊆ B be the range of f . Since R is finite, the subgroup [R] ≤ B generated by R is also finite. (The free Boolean group on r generators has cardinality 2 r .) Applying Theorems 4.1 and 4.2 to f : A n → [R], we obtain the desired decomposition of f . To show the uniqueness, suppose that ϕ 1 , ϕ 2 : P(A) → B both yield the function f . Then we can replace B by its subgroup generated by the union of the ranges of ϕ 1 and ϕ 2 , and apply the uniqueness parts of Theorems 4.1 and 4.2.

Illustration: operations over the three-element set

We saw in Theorem 2.1 that a Boolean function of essential arity at least 4 has arity gap 2 if and only if it is a sum of essentially at most unary functions. Alternatively, this fact follows from the results of the previous section together with Willard's Theorem 2.5. More generally, Theorems 4.1 and 4.2 can be applied to describe polynomial functions over finite fields of characteristic 2 with arity gap 2. In [START_REF] Couceiro | On the arity gap of polynomial functions[END_REF] we provided a simpler and more explicit description of such polynomial functions. In this section we show how Theorems 4.1 and 4.2 can be used to describe functions f : Z n 3 → Z 3 of arity at least 4 with gap f = 2. Since Z 3 is not a Boolean group, we cannot apply these theorems directly. First we need to embed Z 3 into a Boolean group. To this extent, let A := Z 3 = {0, 1, 2} with the usual field operations + and •, and B := P(A) with the symmetric difference operation ⊕. We use the notation ⊕ instead of the more common △ in order to emphasize that this is a Boolean group operation on B (which was denoted by + before). The neutral element of (A; +) is 0, and the neutral element of (B; ⊕) is the empty set ∅. We identify the elements of A with the corresponding one-element sets, i.e., we simply write a instead of {a} for a ∈ A. In this way, A becomes a subset (but, of course, not a subgroup) of B.

Let f : A n → B, where n ≥ 4 is even. Then we have n = 2t + 4 in Theorem 4.1, and the summation in (5) runs over the subsets of [n] of size 2 (for i = t + 1) and of size 0 (for i = t + 2). The corresponding coefficients i-

f 1 (x 1 , x 1 , x 3 , . . . , x n ) = p(x 1 ) + d ⊕ p(x 1 ) + d ⊕ n i=3 p(x i ) + d = n i=3 p(x i ) + d .
Therefore, f 1 is determined by oddsupp by Fact 2.3. Hence f 1 (x) = ϕ 1 (oddsupp(x)) for some map ϕ 1 : P ′ n (A) → B. Observe that P ′ n (A) = {{0}, {1}, {2}, {0, 1, 2}}. Thus, in order to determine ϕ 1 , it suffices to compute the following four values of f 1 :

ϕ 1 ({0}) = f 1 (0, . . . , 0) = n i=1 p(0) + d = p(0) + d = c + d, ϕ 1 ({1}) = f 1 (1, . . . , 1) = n i=1 p(1) + d = p(1) + d = a + b + c + d, ϕ 1 ({2}) = f 1 (2, . . . , 2) = n i=1 p(2) + d = p(2) + d = a + 2b + c + d, ϕ 1 ({0, 1, 2}) = f 1 (0, . . . , 0, 1, 2) = n-2 i=1 p(0) + d ⊕ p(1) + d ⊕ p(2) + d = p(0) + d ⊕ p(1) + d ⊕ p(2) + d = (c + d) ⊕ (a + b + c + d) ⊕ (a + 2b + c + d).
We now analyze the function f 2 (x) = i<j (x ix j ) 2 p(x i + x j ) + d in a similar manner. Examining f 2 (x 1 , x 1 , x 3 , . . . , x n ) we can see that the summands corresponding to i = 1, j ≥ 3 cancel the summands corresponding to i = 2, j ≥ 3, while the summand corresponding to i = 1, j = 2 is (x 1x 1 ) 2 p(x 1 + x 1 ) + d = d. Hence f 2 (x 1 , x 1 , x 3 , . . . , x n ) = d ⊕ 3≤i<j (x ix j ) 2 p(x i + x j ) + d , which clearly does not depend on x 1 . Since f 2 is totally symmetric, we can conclude that f 2 is determined by oddsupp. Therefore, there is a map ϕ 2 : P ′ n (A) → B such that f 2 (x) = ϕ 2 (oddsupp(x)). For any a ∈ A we have where the last equality holds, because n 2 is an odd number by the assumption that n ≡ 3 (mod 4). To find ϕ 2 ({0, 1, 2}), we can proceed as follows: (Here we made use of the fact that n-2 2 is even and n -2 is odd.) The expression given for f in the theorem is f 1 (x) ⊕ f 2 (x) ⊕ d, and from the above calculations it follows that this function is determined by oddsupp, namely, d). The determinant of L is 1; hence L is a bijection. This means that the maps ϕ : P ′ n (A) → B that are of the above form are in a one-to-one correspondence with the 4-tuples over A, i.e., there are 3 4 = 81 such maps. The number of functions f : A n → A that are determined by oddsupp is also 81. Hence we can conclude by a simple counting argument that for any such f there exists a unique tuple (a, b, c, d) ∈ A 4 such that f (x) = f 1 (x) ⊕ f 2 (x) ⊕ d.

Let us observe that when computing the value of a function of the form given in Theorem 5.1, we do not have to "leave" Z 3 : using the fact that ⊕ is commutative and associative and it satisfies u ⊕ u ⊕ v = v for any u, v ∈ Z 3 , we can always perform the calculations in such a way that we work only with singleton elements of B. It is not even necessary to know that B is the power set of Z 3 , it could be any Boolean group that contains Z 3 as a subset. To illustrate this point, let us compute f (0, 0, 1, 2) for the function

f (0, 0, 1, 2) = 2 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 2 = (0 ⊕ 0) ⊕ (1 ⊕ 1) ⊕ (2 ⊕ 2) ⊕ 1 = 1.

  depends only on oddsupp(x), i.e., if there exists ϕ : P(A) → B such that ❄ ϕ | S = f . When there is no risk of ambiguity, we will simply write ❄ ϕ instead of ❄ ϕ | S . Clearly, if S = A n , then the restriction of ϕ to P ′ n (A) = S ∈ P(A) : |S| ∈ {n, n -2, . . .} uniquely determines f and vice versa. Thus, for finite sets A and B, the number of functions f : A n → B that are determined by oddsupp is |B| |P ′ n (A)| . The following facts are straightforward to verify.

Fact 2 . 2 .

 22 The Boolean functions determined by oddsupp are exactly the affine functions (also known as linear functions in the theory of Boolean functions).

Fact 2 . 3 .

 23 A function f : A n → B is determined by oddsupp if and only if f is totally symmetric and f 2←1 does not depend on x 1 .

Fact 2 . 4 .

 24 If (B; +) is an abelian group, then ❄ ϕ1+ϕ2 = ❄ ϕ1 + ❄ ϕ2 holds for all maps ϕ 1 , ϕ 2 : P(A) → B.

Theorem 3 . 4 .

 34 If A is a finite set and B is an abelian group of exponent 2 e , then every function f : A n → B determined by oddsupp is (|A| + e -2)-decomposable. Proof. Suppose that f = ❄ ϕ for some ϕ : P ′ n (A) → B. By Proposition 3.3, it suffices to verify that ∆ a I f (0) = 0 whenever |I| ≥ |A|+ e -1. Let {a i : i ∈ I} =: {b 1 , . . . , b t } (b i = b j whenever i = j), and let B j := {i ∈ I :

  3, it suffices to find I ⊆ [n] and a ∈ A n such that |I| = |A| + e -2 = ℓ + e -1 and ∆ a I f (0) = 0. To this end, let a := (1, 2, . . . , ℓ -1, ℓ, . . . , ℓ e , 0, . . . , 0 n-ℓ-e+1

Example 3 . 8 .

 38 Let A be an infinite set, let B be an abelian group and let 0 = b ∈ B. Fix n ≥ 2, and let S := {s 1 , . . . , s n } ⊆ A \ {0} with |S| = n. Define f : A n → B by the rule

such that 1 ∈

 1 I and 2 / ∈ I. Then I ′ := I △ {1, 2} = (I \ {1}) ∪ {2} (△ denotes the symmetric difference) appears as well, since it has the same cardinality as I. As oddsupp(x| I ) = oddsupp(x| I ′ ), we have ❄ ϕ (x| I ) = ❄ ϕ (x| I ′ ), thus these two summands will cancel each other. The remaining sets I either contain both 1 and 2 or neither of them. In the first case, oddsupp(x| I ) = oddsupp(x| I\{1,2} ),

  ) for x := (s 1 , . . . , s 1 2r+1 , s 2 , . . . , s n-2r ) ∈ A n . Observe that oddsupp(x| I ) ⊆ S. If oddsupp(x| I ) ⊂ S, then ❄ ϕ (x| I ) = 0 by the minimality of S. If oddsupp(x| I ) = S, then ❄ ϕ (x| I ) = ϕ(S) = 0. The latter is the case if and only if I is a proper superset of {2r + 2, . . . , n} of cardinality n -2i for some i. The number of sets I ⊆ [n] with |I| = n -2i and I ⊃ {2r + 2, . . . , n} is 2r+1 2i . Hence the left-hand side of (6

  By the minimality of |S|, if T ∈ P ′ n (A) then we have ϕ(T ) = 0 if and only if T = S. Similarly, if T / ∈ P ′ n (A) then we have ϕ(T ) = 0 if and only if T = S \ {0}. (Indeed, if T = S \ {0}, then T △ {0} ∈ P ′ n (A) is a proper subset of S. Hence ϕ(T ) = ϕ(T △ {0}) = 0.) Let us examine the left-hand side of (8) for x := (s 1 , . . . , s 1 2r+1 , s 2 , . . . , s n-2r ) ∈ A n .The same argument as in the proof of Theorem 4.1 shows that the first sum of (8which is ϕ(S) by Theorem 2.7, since r ≥ t+1. If K is a set of size n-2k+1 appearing in the second sum of (8), then ❄ ϕ (x| K ) = ϕ(S \ {0}) = ϕ(S) if K ⊇ {2r + 2, . . . , n}, and ❄ ϕ (x| K ) = 0 otherwise. The number of such sets K is 2r+1 2k-1 , thus the second sum on the left-hand side of (8

  let T ⊆ S. If T ∈ P ′ n (A), then we have ϕ(T ) = 0 if and only if T = S by the minimality of |S|. Similarly, if T / ∈ P ′ n (A), then we have ϕ(T ) = 0. (Indeed, if T / ∈ P ′ n (A) then T ∪ {0} = T △ {0} ∈ P ′ n (A) and |T △ {0}| ≤ |S|. On the other hand, if ϕ(T △ {0}) = ϕ(T ) = 0 then |T △ {0}| ≥ |S| by the minimality of |S|. Thus we have |T △ {0}| = |S| = n -2r, hence T △ {0} is a set in P ′ n (A) with cardinality n -2r such that ϕ(T △ {0}) = 0 and 0 ∈ T △ {0}, and then replacing S by T △ {0} we come back to the previous case.)

ϕ 2 (

 2 {a}) = f 2 (a, . . . , a) = i<j (aa) 2 p(a + a) + d = n 2 d = d,

ϕ 2 (

 2 {0, 1, 2}) = f 2 (0, . . . , 0, 12) 2 p(0 + 2) + d ⊕ (1 -2) 2 p(1 + 2) + d = (a + b + c + d) ⊕ (a + 2b + c + d) ⊕ (c + d).

  f 1 (x) ⊕ f 2 (x) ⊕ d = ϕ(oddsupp(x)), where ϕ({0}) = ϕ 1 ({0}) ⊕ ϕ 2 ({0}) ⊕ d = (c + d) ⊕ d ⊕ d = c + d, ϕ({1}) = ϕ 1 ({1}) ⊕ ϕ 2 ({1}) ⊕ d = (a + b + c + d) ⊕ d ⊕ d = a + b + c + d, ϕ({2}) = ϕ 1 ({2}) ⊕ ϕ 2 ({2}) ⊕ d = (a + 2b + c + d) ⊕ d ⊕ d = a + 2b + c + d, ϕ({0, 1, 2}) = ϕ 1 ({0, 1, 2}) ⊕ ϕ 2 ({0, 1, 2}) ⊕ d = (c + d) ⊕ (a + b + c + d) ⊕ (a + 2b + c + d) ⊕ (a + b + c + d) ⊕ (a + 2b + c + d) ⊕ (c + d) ⊕ d = d.Observe that the range of ϕ is a subset of A. Hencef 1 (x) ⊕ f 2 (x) ⊕ d is a function from A n to A.Let us consider the linear transformationL : Z 4 3 → Z 4 3 ,(a, b, c, d) → (c + d, a + b + c + d, a + 2b + c + d,

f (x 1

 1 , x 2 , x 3 , x 4 ) = i<j (x ix j ) 2 p(x i + x j ) + d⊕ d that corresponds to the case n = 4 with a = 1, b = c = d = 2 in Theorem 5.1:

  n > |A|, then Theorem 2.6 provides a decomposition of f into a sum of functions of essential arity at most n -2. Each summand ❄ ϕ (x| I ) is a function determined by oddsupp, and if |I| > |A|, then we can apply Theorem 2.6 to decom-(x| I ) appears, we arrive at decomposition[START_REF] Couceiro | On the effect of variable identification on the essential arity of functions on finite sets[END_REF] given below in Theorem 4.1. If the parities of |A| and n are equal, then we have to further decompose the summands of essential arity |A|. We then get the more refined decomposition[START_REF] Couceiro | The arity gap of order-preserving functions and extensions of pseudo-Boolean functions[END_REF] given below in Theorem 4.2. Note that in these theorems we assume that B is finite. However, as we will see in Remark 4.3, the general case can be easily reduced to the case finite groups. Theorem 4.1. Let f : A n → B, where B is a finite Boolean group, A is a finite set, and n -|A| = 2t + 1 > 0. Then f is determined by oddsupp if and only if f is of the form

pose ❄ ϕ (x| I ) into a sum of functions of essential arity at most |I| -2. Repeating this process as long as we have summands of essential arity greater than |A|, we end up with an |A|-decomposition of f . If the parities of |A| and n are different, then this is already an (|A| -1)-decomposition. By counting how many times a given summand ❄ ϕ

  It is clear that this function is totally symmetric, and f 1 (x 1 , x 1 , x 3 , . . . , x n ) does not depend on x 1 , since

	t+1	t	1	are t t = 1 and
	t

= t + 1, respectively. Thus i-1 t ❄ ϕ (x| I ) = ❄ ϕ (x| I ) whenever |I| = 2 or I = ∅ and t is even (i.e., n is divisible by 4); on the other hand, if I = ∅ and t is odd, then

Acknowledgments

The third named author acknowledges that the present project is supported by the T ÁMOP-4.2.1/B-09/1/KONV-2010-0005 program of National Development Agency of Hungary, by the Hungarian National Foundation for Scientific Research under grants no. K77409 and K83219, by the National Research Fund of Luxembourg, and cofunded under the Marie Curie Actions of the European Commission (FP7-COFUND).

i-1 t ❄ ϕ (x| I ) = 0. Therefore, [START_REF] Couceiro | On the effect of variable identification on the essential arity of functions on finite sets[END_REF] takes one of the following two forms, depending on the residue of n modulo 4 (the summation indices i and j always run from 1 to n, unless otherwise indicated):

(Note that ϕ(oddsupp(x i , x j )) = ϕ({x i , x j }) if x i = x j , and ϕ(oddsupp

If n is odd, then we can apply Theorem 4.2. In this case we have n = 2t + 3, and in the first summation of ( 7) I is a one-element set (i = t+1) and the corresponding coefficient is i-1 t = t t = 1. In the second summation, K is either a two-element set (k = t + 1) or the empty set (k = t + 2). The corresponding coefficients 2k-1 2t are 2t+1 2t = 2t + 1 and 2t+3 2t = (2t+3)(2t+1)(t+1) 3 ≡ t + 1 (mod 2). Thus, [START_REF] Couceiro | The arity gap of order-preserving functions and extensions of pseudo-Boolean functions[END_REF] takes one of the following two forms:

(Note that ϕ(oddsupp(x i )) = ϕ({x i }).)

The above formulas are valid for any function f : A n → B, but we are interested only in functions whose range lies within A, i.e., whose values are one-element sets in B. In this case, we can give more concrete expressions for the above decompositions.

Otherwise we have gap f = 1.

Proof. Let A := Z 3 and B := P(Z 3 ) as explained above. We work out the details only for the case n ≡ 3 (mod 4), the other cases are similar. First let us consider the function


text:
Miguel Couceiro

Erkko Lehtonen
email: erkko.lehtonen@uni.lu

Tam Ás Waldhauser

PARAMETRIZED ARITY GAP

Keywords: 2010 Mathematics Subject Classification. 06A06, 08A40 arity gap, parametrized arity gap, essential variable, simple minor, variable identification minor

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 nonnegative 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.

Introduction

Let A and B be arbitrary nonempty sets. In this paper 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 |A| = 2, examples of functions meeting each of the two possible values of the arity gap can be easily constructed. For instance, it is clear that the Boolean multiplication has arity gap 1, whereas the Boolean addition has arity gap 2. This observation asks for a complete classification of Boolean functions into ones with arity gap 1 and ones with arity gap 2.

Such a classification was attained in [START_REF] Couceiro | On the effect of variable identification on the essential arity of functions on finite sets[END_REF], where explicit descriptions of functions with arity gap 2 were provided; interestingly, this result led to a similar classification of pseudo-Boolean functions (i.e., A = {0, 1} and |B| ≥ 2) into ones with arity gap 1 and ones with arity gap 2 (see [START_REF] Couceiro | Generalizations of Świerczkowski's lemma and the arity gap of finite functions[END_REF]).

Willard [START_REF] Willard | Essential arities of term operations in finite algebras[END_REF] extended Salomaa's result to functions defined on arbitrary finite domains and showed that the same upper bound 2 holds for the arity gap of any function f : A n → B depending on all of its variables, provided that n > max (3, |A|). Moreover, he proved that the arity gap of such a function f is 2 if and only if f is determined by oddsupp (see Section 2.2).

Further classifications for wider classes of functions (e.g., where A and B are arbitrary nonempty sets) were obtained and made explicit under certain conditions in, e.g., [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].

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). This paper is organized as follows. In Section 2, 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 3 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 4, 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.

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).

Preliminaries

2.1. 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 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 x i is essential in f : A n → B, or f depends on x i , 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] : x i 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, x i 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 2.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 . Remark 2.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, as the following example illustrates.

Example 2.3. 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 (x 1 , x 2 , x 3 , x 4 ) := ν(x 1 , x 2 ) ∨ 1≤i<j≤4 (i,j) =(1,2) ν(x i , x j ).
It is easy to see that f i←j = ν(x 1 , x 2 ) for 1 ≤ i < j ≤ 4, (i, j) = (1, 2), and

f 1←2 = 2≤i<j≤4 ν(x i , x 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 2.4. 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 . 2.2. 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 2.5. 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.6. 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 2.7. If n > |A|, then f : A n → B is determined by both supp and oddsupp if and only if f is a constant function.
Proof. The condition is clearly sufficient: as noted in Example 2.6, every constant function is determined by both supp and oddsupp.

For necessity, assume that f is determined by both supp and oddsupp. Then there exist maps ϕ, ψ :

P(A) → B such that f = ϕ • supp | A n = ψ • oddsupp | A n .
We will prove that for every S ⊆ A (|S| ≥ 2), t ∈ S, it holds that ϕ(S) = ϕ(S \ {t}). A simple inductive argument then shows that the restriction of ϕ to P(A)\{∅} is constant, which implies that f is constant, as claimed.

Thus, let S ⊆ A, |S| = s ≥ 2, say S = {a 1 , . . . , a s }, a s = t. Since |S| ≤ |A| < n, there exists an injective map h : S → [n]. We will define tuples b, c ∈ A n ; the definition depends on the parity of n -|S|:

• If n -|S| is odd, then for each j ∈ [n], let b j := a i if h(a i ) = j, a s otherwise, c j := a i if h(a i ) = j, i = s, a s-1 otherwise.
Since n -|S| is odd, b has an even number of occurrences of a s , and c has an odd number of occurrences of a s-1 . Therefore supp

(b) = S, supp(c) = oddsupp(b) = oddsupp(c) = S \ {a s }. • If n -|S| is even, then for each j ∈ [n], let b j :=      a i if h(a i ) = j, i = s, a s-1 if h(a s ) = j, a s otherwise, c j := a i if h(a i ) = j, i = s, a s-1 otherwise.
Since n -|S| is even, b has two occurrences of a s-1 and an even number of occurrences of a s , and c has an even number of occurrences of a s-1 . Therefore supp(b) = S,

supp(c) = S \ {a s }, oddsupp(b) = oddsupp(c) = S \ {a s-1 , a s }.
Our choice of b and c yields

ϕ • supp(b) = f (b) = ψ • oddsupp(b) = ψ • oddsupp(c) = f (c) = ϕ • supp(c), that is, ϕ(S) = ϕ(S \ {a s }).
This completes the proof of the proposition.

As it will become clear from Propositions 2.8 and 2.11 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 .
Proof. Let us assume that f = ϕ • oddsupp | A n for some ϕ : P(A) → B. Since f is totally symmetric, it has a unique lower cover, namely the (n -2)-ary function f n-2 given by f n-2 = ϕ • oddsupp | A n-2 . We see that f n-2 is also determined by oddsupp, hence we can repeat this argument, and we conclude that the simple minors of f form a chain as stated in the theorem. It is obvious that the length of this chain is t ≤ n 2 . As every function in this chain is totally symmetric, the essential arity of f n-2i is either n -2i or 0 for all i ≤ t. Clearly, only the last element of the chain can be constant, i.e., ess f n-2i = n -2i for i < t. Moreover, f n-2t has no proper simple minor, therefore it is essentially at most unary. If ess f n-2t = 1, then n -2t = 1, thus t = n-1 2 , as claimed. Now let us assume that ess f n-2t = 0. By Remark 2.5, f n-2i is not constant if and only if the restriction of ϕ to P ′ ≤n-2i (A) is not constant. Since f is not constant, and

P ′ ≤n (A) = P ′ ≤n-2i (A) whenever n -2i + 2 > k, we have that f n-2i is not constant for all i ≤ n-k 2 . As f n-2t is constant by our assumption, it follows that t > n-k 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 2.8, thereby showing that this result cannot be sharpened.

Example 2.9. Let k, n, t be positive integers such that k ≥ 2 and n-k 2 < t ≤ n 2 . 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 ϕ(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 2.5 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 2.8.

Example 2.10. 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 2.8.

Reasoning as above, by making use of Remark 2.5, we have the following analogue of Proposition 2.8.

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 nk < t < n.

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

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 fess 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 2.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 corollaries are immediate consequences of Propositions 2.8 and 2.11. We now recall a few noteworthy results about the arity gap. These appear as Lemma 1.2, Lemma 2.2, Corollary 2.3, and Corollary 2.7 in Willard's paper [START_REF] Willard | Essential arities of term operations in finite algebras[END_REF].

Theorem 2.14 (Willard [16]). 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.

Lemma 2.15 (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.

(1) If n > 2, gap f = 1, f is totally symmetric, and for any distinct i, j ∈ [n], f i←j is equivalent to a totally symmetric function, then f is determined by supp. (2) If f is determined by supp, then f i←j is equivalent to a function determined by supp for any distinct i, j ∈

[n]. Moreover, if n > k, then f i←j is nonconstant. (3) If n ≥ max(k, 3
) + 2 and f is not totally symmetric, then there exist distinct i, j ∈ [n] such that f i←j depends on n -1 variables and is not equivalent to a totally symmetric function.

The following theorem will play an important role in the next section.

Theorem 2.16. Let A and B be finite nonempty sets, and let k := |A|. Suppose that f : A n → B depends on all of its variables.

(1) If n ≥ max(k, 3) + 1 and gap f = 2, then for all g < f with ess g > k, it holds that gap g = 2.

(2) If n ≥ max(k, 3)+2 and gap f = 1, then there exists a g ≺ f such that gap g = 1 and ess g = n -1.

Proof. For (1), observe that Theorem 2.14 and the assumption gap f = 2 imply that f is determined by oddsupp. Hence, by Proposition 2.8, g is also determined by oddsupp. By Corollary 2.12, gap g = 2.

For (2), observe that Theorem 2.14 and the assumption gap f = 1 imply that f is not determined by oddsupp. If f is not totally symmetric, then the claim holds by Lemma 2.15 (3) and Theorem 2.14. Therefore we may assume that f is totally symmetric. By Fact 2.4, f has a unique lower cover g, and ess g = ess f -1. If g is not totally symmetric, then it is not determined by oddsupp, and by Theorem 2.14, gap g = 1. If g is totally symmetric, then Lemma 2.15 (1) implies that f is determined by supp. By Lemma 2.15 (2), g is determined by supp. By Proposition 2.7, g is not determined by oddsupp, from which it follows that gap g = 1 by Theorem 2.14.

Parametrized arity gap

In this section we are interested in the following parametrized version of arity gap which measures the minimum decrease in the essential arity when we take ℓ ≥ 0 steps downwards in the simple minor partial order:

(3.1) gap(f, ℓ) := min g∈↓ ℓ f (ess f -ess g),
where ↓ 0 f := {g ∈ F AB : g ≡ f } and, for ℓ > 0,

↓ ℓ f := {g ∈ F AB | ∃f 1 , . . . , f ℓ-1 : f ≻ f 1 ≻ • • • ≻ f ℓ-1 ≻ g}.
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 2.3) corresponds to the case ℓ = 1: we have gap(f, 1) = gap f for every function f . Observe also that gap(f, 0) = 0 for every function f . We saw in Section 2.1 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 3.1. 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 2.3 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 fess 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 fess 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 3.2. Let A be the 5-element field and consider the polynomial function f : A 6 → A defined by:

f (x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ) := (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 3←1 = (x 1 -x 2 ) • (x 5 -x 6 ), f 6←5 = 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 hess g. We use the following notation for the 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 (3.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.

q 1 f 1 5 2 q 2 1 1 1 1 2 2 q 3 q 4 q 5 q 6 0 Figure 1.
The simple minors of the function f given in Example 3.2.

The following recursion formula is an immediate consequence of the definition:

(3.2) gap(f, ℓ) = min g≺f (ess f -ess g + gap(g, ℓ -1)).
Theorem 3.3. 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, ℓ) = ℓ.
Proof. We prove the theorem by induction on ℓ.

If ℓ = 1, then gap(f, ℓ) = gap f = 1. If ℓ ≥ 2 then n ≥ max(k, 3) + 2
, hence by Theorem 2.16, f has a lower cover g with ess g = n -1 and gap g = 1. Since 1 ≤ ℓ -1 ≤ ess gmax(k, 3), we can apply the induction hypothesis to obtain gap(g, ℓ -

1) = ℓ -1. From (3.2) it follows that gap(f, ℓ) ≤ ess f -ess g + gap(g, ℓ -1) = n -(n -1) + (ℓ -1) = ℓ.
On the other hand we have the trivial inequality gap(f, ℓ) ≥ ℓ, and therefore gap(f, ℓ) = ℓ.

Informally, the above theorem 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 ess f = n, gap f = 1 and gap(f, ℓ) = q. Theorem 3.4. 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. Proof. Let p := n -q, k := n + 1 -ℓ, A := [k], B := [3], and for k ≤ m ≤ n, define f m : A m → B as f m (x 1 , . . . , x m ) =      1, if x k = x k+1 = • • • = x m and supp(x) = A, 2, if x 1 = • • • = x p = 2 and supp(x) ⊂ A, 3, otherwise.
We are going to prove that gap(f n , ℓ) = q. Claim 3.4.1. For k ≤ m ≤ n, the function f m depends on all of its variables.

Proof of Claim 3.4.1 Let x = (1, 2, . . . , k, k, . . . , k) ∈ A m . Then f m (x) = 1, and it is easy to verify that if any coordinate of x is changed, the value of f will change. Proof of Claim 3.4.3 Let g = (f k ) i←j ; we may assume without loss of generality that j < i. Then g(x 1 , . . . , x k ) = f k (x 1 , . . . , x i-1 , x j , x i+1 , . . . , x k ).

⋄ Claim 3.4.2. If m > k, then f m-1 ≺ f m . Proof of Claim 3.4.2 Clearly f m-1 (x 1 , . . . , x m-1 ) = f m (x 1 , . . . , x m-1 , x m-1 ), so f m-1 ≤ f m . Since ess f m-1 = m -
Since supp(x 1 , . . . , x i-1 , x j , x i+1 , . . . , x k ) ⊂ A, we have that, if i > p,

g(x 1 , . . . , x k ) = 2, if x 1 = • • • = x p = 2, 3, otherwise,
and if i ≤ p, g(x 1 , . . . , x k ) = 2, if x 1 = • • • = x i-1 = x i+1 = • • • = x p = 2, 3, otherwise.
In the former case, g is equivalent to the function u :

A p → B, u(x 1 , . . . , x p ) = 2, if x 1 = • • • = x p = 2, 3, otherwise,
and in the latter case g is equivalent to the function u

′ : A p-1 → B, u ′ (x 1 , . . . , x p-1 ) = 2, if x 1 = • • • = x p-1 = 2, 3, otherwise.
It clearly holds that u ′ < u, and we conclude that u is the unique lower cover of

f k . ⋄ Claim 3.4.4. If v < f and ess v = t ≤ k -1, then v ≤ u.
Proof of Claim 3.4.4 There exists σ :

[n] → [t] such that v(x 1 , . . . , x t ) = f (x σ(1) , . . . , x σ(n) ).
Since supp(x σ(1) , . . . , x σ(n) ) ⊂ A, we have f (x σ(1) , . . . , x σ(n) ) = u(x σ(1) , . . . , x σ(p) ).

Hence v ≤ u. ⋄ By Claims 3.4.2 and 3.4.3, we have

f n ≻ f n-1 ≻ • • • ≻ f k+1 ≻ f k ≻ u.
Since nk + 1 = ℓ and ess f ness u = np = q, it holds that gap(f n , ℓ) ≤ q. Suppose, on the contrary, that gap(f n , ℓ) < q. Then there exists a chain f n ≻ g 1 ≻ g 2 ≻ • • • ≻ g ℓ such that ess f n -ess g ℓ < q. Clearly ess f n -ess g ℓ ≥ ℓ, that is ess g ℓ ≤ ess f n -ℓ = n-ℓ = k -1. By Claim 3.4.4, g ℓ ≤ u, whence ess g ℓ ≤ ess u = p = nq = ess f nq < ess g ℓ . We have reached a contradiction that completes the proof of the theorem.

Next we consider the analogue of Theorem 3.3 for the case gap f = 2. Theorem 3.5. 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ℓ. Proof. If ℓ = 1, then gap(f, ℓ) = gap f = 2 = 2ℓ. If ℓ ≥ 2 then n ≥ k + 3 ≥ max(k, 3) + 2.
Hence by Theorem 2.14 f is determined by oddsupp. The theorem then follows immediately from Proposition 2.8.

Our last result shows that for almost every integer sequence 0 = n 0 < n 1 < n 2 < • • • < n r ≤ n, we can construct a function f : A n → B whose parametrized arity gap meets every member of the sequence. We only need to assume that n r-1 = n -1, because no function has both an essentially unary function and a constant function as its simple minors. Theorem 3.6. 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.

Proof. We can assume that the codomain B has a group structure, and 0 is the neutral element of the group operation + on B. We will define recursively functions

f i : A n-ni → B, 0 ≤ i ≤ r, such that f 0 ≻ f 1 ≻ • • • ≻ f r and ess f i = n -n i for all 0 ≤ i ≤ r.
If n r = n -1, then let f r : A → B be an arbitrary nonconstant function. If n r = n, then let f r : A → B be an arbitrary constant function. Assume that f i+1 : A n-ni+1 → B has been defined (0 ≤ i < r). Define f i : A n-ni → B as follows. Let g i : A n-ni → B be a function equivalent to f i+1 , i.e., g i is obtained from f i+1 by adding n i+1n i inessential variables. Let h i : A n-ni → B be an arbitrary nonconstant function such that h i (a 1 , . . . , a n-ni ) = 0 whenever a j = a j ′ for some j = j ′ . Set f i := g i + h i . It is easy to verify that f i depends on all of its variables. Moreover, the strict simple minors of f i are precisely the simple minors of f i+1 (including f i+1 itself). Therefore f i+1 is the unique lower cover of f i .

Setting f := f 0 , we have that the simple minors of f are precisely the functions f, f 1 , . . . , f r , and they comprise a covering sequence

f ≻ f 1 ≻ f 2 ≻ • • • ≻ f r . Since ess f ℓ = n -n ℓ ,
we conclude that gap(f, ℓ) = n ℓ for every 0 ≤ ℓ ≤ r, as desired.

Concluding remarks

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 the reader may now realise, pag(f, p) is the smallest ℓ for which 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 the rule 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 2 . 8 .

 28 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

Proposition 2 . 11 .

 211 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

Corollary 2 . 12 .

 212 If f : A n → B is determined by oddsupp, n > |A|, and f is nonconstant, then gap f = 2. Corollary 2.13. If f : A n → B is determined by supp, n > |A|, and f is nonconstant, then gap f = 1.

  1 and ess f m = m by Claim 3.4.1, f m-1 is necessarily a lower cover of f m . ⋄ Claim 3.4.3. f k has a unique lower cover u : A p → B, and ess u = p.

Example 4 . 1 . 1

 411 Consider the 6-ary function f of Example 3.2. We can read off of Figure

(

  |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 fe(θ). 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 fess f θ ). Note that b-gap(f, 0) = 0 and 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 fess g : g ≤ f }. It is clear that {b-gap(f, ℓ) : 0 ≤ ℓ ≤ n -1} ⊆ H(f ).

Proposition 4 . 2 .

 42 Let f : A V → B be a function such that ess f = |V | = n. Then b-gap(f, ℓ) = min{m ∈ H(f ) : m ≥ ℓ}, for all 0 ≤ ℓ ≤ n -1.Proof. Let ℓ ∈ {0, . . . , n -1}. Assume first that ℓ ∈ H(f ). Then there exists an equivalence relation θ ∈ Eq(V ) such that ess f θ = nℓ. It clearly holds that e(θ) ≤ ℓ. We can construct an equivalence relation ζ ∈ Eq(V ) such that e(ζ) = ℓ and f ζ ≡ f θ . Namely, we merge the blocks of θ that are indexing the inessential variables of f θ , if any, and we merge the resulting block with another block of θ. We leave it for the reader to verify that ζ indeed satisfies e(ζ) = ℓ and f ζ ≡ f θ . This construction shows that b-gap(f, ℓ) ≤ ℓ. On the other hand, b-gap(f, ℓ) ≥ ℓ, so we conclude that b-gap(f,ℓ) = ℓ = min{m ∈ H(f ) : m ≥ ℓ}. Assume then that ℓ / ∈ H(f ). Since ℓ ≤ b-gap(f, ℓ) ∈ H(f ),we have in fact that ℓ < b-gap(f, ℓ); moreover, b-gap(f, ℓ) ≥ t for t := min{m ∈ H(f ) : m ≥ ℓ}. Since b-gap(f, •) is a monotone increasing function in its second argument, and b-gap(f, t) = t by the first part of this proof, we have t ≤ b-gap(f, ℓ) ≤ b-gap(f, t) = t, that is, b-gap(f, ℓ) = t = min{m ∈ H(f ) : m ≥ ℓ}.

Example 4 . 3 .Example 4 . 4 .

 4344 Consider the 6-ary function f of Example 3.2. We can read off of Figure1thatH(f ) = {0, 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 thatdepends 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 ℓ for which b-gap(f, ℓ) ≥ p. In other words, b-pag(f, 0) = 0 and b-pag(f, p) = max{m ∈ H(f ) : m < p} + 1 for 1 ≤ p ≤ n. Consider the 6-ary function f of Example 3.2. We can determine from the values of b-gap(f, ℓ) listed in Example 4.3, 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.

The first named author is supported by the internal research project F1R-MTH-PUL-09MRDO of the University of Luxembourg. The third named author acknowledges that the present project is supported by the T ÁMOP-4.2.1/B-09/1/KONV-2010-0005 program of 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)..