domain: info math

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

Tam Ás Waldhauser

PSEUDO-POLYNOMIAL FUNCTIONS OVER FINITE DISTRIBUTIVE LATTICES

Keywords: Sugeno integral, distributive lattice, lattice polynomial function, pseudopolynomial function, axiomatization, factorization, multicriteria decision making

In this paper we extend the authors previous works by considering a multi-attribute aggregation model based on a composition of a polynomial function over a finite distributive lattice with local utility functions; these are referred to as pseudo-polynomial functions. We present an axiomatization for this class of pseudo-polynomial functions which differs from the previous ones both in flavour and nature, and develop general tools which are then used to obtain all possible such factorizations of a given pseudo-polynomial function.

Introduction and motivation

The Sugeno integral (introduced by Sugeno [START_REF] Sugeno | Theory of fuzzy integrals and its applications[END_REF][START_REF] Sugeno | Fuzzy measures and fuzzy integrals-a survey[END_REF]) remains as one of the most noteworthy aggregation functions, and this is partially due to the fact that it provides a meaningful way to fuse or merge values within universes where essentially no structure, other than an order, is assumed. Even though primarily defined over real intervals, the concept of Sugeno integral can be extended to wider domains, namely, distributive lattices, via the notion of lattice polynomial function (i.e., a combination of variables and constants using the lattice operations ∧ and ∨). As it turned out, idempotent lattice polynomial functions coincide with (discrete) Sugeno integrals (see e.g. [START_REF] Couceiro | Characterizations of discrete Sugeno integrals as polynomial functions over distributive lattices[END_REF][START_REF] Marichal | Weighted lattice polynomials[END_REF]).

Recently, the Sugeno integral has been generalized via the notion of quasi-polynomial function (see [START_REF] Couceiro | Axiomatizations of quasi-polynomial functions on bounded chains[END_REF]) originally defined as a mapping f : X n → X on a bounded chain X and which can be factorized as [START_REF] Birkhoff | On the combination of subalgebras[END_REF] f (x 1 , . . . , x n ) = p(ϕ(x 1 ), . . . , ϕ(x n )),

where p : X n → X is a polynomial function and ϕ : X → X is an order-preserving map. This notion was later extended in two ways.

In [START_REF] Couceiro | Axiomatizations of quasi-polynomial functions over bounded distributive lattices[END_REF], the input and output universes were allowed to be arbitrary, possibly different, bounded distributive lattices X and Y so that f : X n → Y is factorizable as in [START_REF] Birkhoff | On the combination of subalgebras[END_REF], where now p : Y n → Y and ϕ : X → Y . These functions appear naturally within the scope of decision making under uncertainty since they subsume overall preference functionals associated with Sugeno integrals whose variables are transformed by the utility function ϕ. Several axiomatizations for this function class were proposed, as well as all possible factorizations described.

In [START_REF] Couceiro | Sugeno utility functions I: Axiomatizations[END_REF] and [START_REF] Couceiro | Sugeno utility functions II: Factorizations[END_REF] a different extension was considered, now appearing within the realm of multicriteria decision making. Essentially, the aggregation model was based on functions f : X 1 × • • • × X n → Y for bounded chains X 1 , . . . , X n and Y , which can be factorized as compositions [START_REF]Decision-Making Process -Concepts and Methods[END_REF] f (x 1 , . . . , x n ) = p(ϕ 1 (x 1 ), . . . , ϕ n (x n )),

where p : Y n → Y is a Sugeno integral, and each ϕ k : X k → Y is an order-preserving map. Such functions were referred to as Sugeno utility functions in [START_REF] Couceiro | Sugeno utility functions I: Axiomatizations[END_REF]. Pseudo-polynomial functions were defined as functions of the form [START_REF]Decision-Making Process -Concepts and Methods[END_REF], where p is an arbitrary (possibly non-idempotent) lattice polynomial function, and each ϕ k satisfies a certain boundary condition (which is weaker than order-preservation). Note that every quasi-polynomial function [START_REF] Birkhoff | On the combination of subalgebras[END_REF] can be regarded as a pseudo-polynomial function, where

X 1 = • • • = X n = X and ϕ 1 = • • • ϕ n = ϕ.
Moreover, pseudo-polynomial functions naturally subsume Sugeno utility functions, and several axiomatizations were established for this function class in [START_REF] Couceiro | Sugeno utility functions I: Axiomatizations[END_REF]. The question of factorizing a given Sugeno utility function into a composition [START_REF]Decision-Making Process -Concepts and Methods[END_REF] was addressed in [START_REF] Couceiro | Sugeno utility functions II: Factorizations[END_REF], where a method for producing such a factorization was presented.

In the current paper we extend the previous results by letting X 1 , . . . , X n to be arbitrary sets and Y to be an arbitrary finite distributive lattice, thus subsuming the frameworks in [START_REF] Couceiro | Axiomatizations of quasi-polynomial functions over bounded distributive lattices[END_REF][START_REF] Couceiro | Sugeno utility functions I: Axiomatizations[END_REF][START_REF] Couceiro | Sugeno utility functions II: Factorizations[END_REF]. Moreover, we develop general tools which allow us to produce all possible factorizations of a given pseudo-polynomial function into compositions (2) of a lattice polynomial function p :

Y n → Y with maps ϕ k : X k → Y .
The structure of the paper is as follows. In Section 2 we introduce the basic notions and terminology needed throughout the paper, and recall some preliminary results. For further background on aggregation functions and their use in decision making, we refer the reader to [START_REF]Decision-Making Process -Concepts and Methods[END_REF][START_REF] Grabisch | Aggregation Functions. Encyclopedia of Mathematics and its Applications[END_REF]; for basics in the theory of lattices, see [START_REF] Davey | Introduction to Lattices and Order[END_REF][START_REF] Grätzer | General Lattice Theory[END_REF]. In Section 3 we develop a general framework used to derive an axiomatization of pseudo-polynomial functions of somewhat different nature than those proposed in [START_REF] Couceiro | Axiomatizations of quasi-polynomial functions over bounded distributive lattices[END_REF][START_REF] Couceiro | Sugeno utility functions I: Axiomatizations[END_REF][START_REF] Couceiro | Sugeno utility functions II: Factorizations[END_REF], and which will provide tools for determining all possible factorizations of given pseudo-polynomial functions in Section 4. These results are then illustrated in Section 5 by means of a concrete example, and in Section 6 we show how this new procedure can be applied to derive the algorithm provided in [START_REF] Couceiro | Sugeno utility functions II: Factorizations[END_REF][START_REF] Couceiro | Axiomatizations and factorizations of Sugeno utility functions[END_REF].

Preliminaries

Throughout this paper, Y is assumed to be a finite distributive lattice with meet and join operations denoted by ∧ and ∨, respectively. Being finite, Y has a least element and a greatest element, denoted by 0 and 1, respectively. By Birkhoff's Representation Theorem [START_REF] Birkhoff | On the combination of subalgebras[END_REF], Y can be embedded into P (U ), the power set of a finite set U . Identifying Y with its image under this embedding, we will consider Y as being a sublattice of P (U ) with 0 = ∅ and 1 = U . The complement of a set S ∈ P (U ) will be denoted by S. Since Y is closed under intersections, it induces a closure operator cl on U , and since Y is closed under unions, it also induces a dual closure operator int (also known as "interior operator"): It is easy to verify that these two operators satisfy the following identities for any S 1 , S 2 ∈ P (U ):

cl (S 1 ∨ S 2 ) = cl (S 1 ) ∨ cl (S 2 ) , int (S 1 ∧ S 2 ) = int (S 1 ) ∧ int (S 2 ) .
A function p : Y n → Y is a polynomial function if it can be obtained as a composition of the lattice operations ∧ and ∨ with variables and constants. Note that polynomial functions are thus order-preserving. As observed in [START_REF] Marichal | Weighted lattice polynomials[END_REF], (discrete) Sugeno integrals coincide exactly with those lattice polynomial functions p which are idempotent, i.e., satisfy the identity p (y, . . . , y) = y. An important lattice polynomial function (in fact, a Sugeno integral) is the median function med :

Y 3 → Y defined by med (y 1 , y 2 , y 3 ) = (y 1 ∧ y 2 ) ∨ (y 2 ∧ y 3 ) ∨ (y 3 ∧ y 1 ) = (y 1 ∨ y 2 ) ∧ (y 2 ∨ y 3 ) ∧ (y 3 ∨ y 1 ) .
It is useful to observe that the above expressions for the median can be simplified when two of the arguments are comparable:

(3) med (s, y, t) = s ∨ (t ∧ y) whenever s ≤ t.

Polynomial functions over bounded distributive lattices have very neat representations, for instance, in disjunctive normal form [START_REF] Goodstein | The solution of equations in a lattice[END_REF], i.e., representations by expressions of the form

I⊆[n] a I ∧ i∈I y i ,
where i∈I y i = 1 when I = ∅. To provide the "canonical" expression in this disjunctive normal form, let us define 1 I to be the characteristic vector of I ⊆ [n] := {1, . . . , n}, i.e., the n-tuple in Y n whose i-th component is 1 if i ∈ I, and 0 otherwise. Theorem 1 (Goodstein [START_REF] Goodstein | The solution of equations in a lattice[END_REF]). A function p : Y n → Y is a polynomial function if and only if [START_REF] Couceiro | Axiomatizations of quasi-polynomial functions over bounded distributive lattices[END_REF] p(y 1 , . . . , y n ) =

I⊆[n] p(1 I ) ∧ i∈I y i .
Remark 2. Equation ( 4) is referred to as the canonical disjunctive normal form representation of p.

Remark 3. The function given by ( 4) is a Sugeno integral if and only if p(0) = 0 and p(1) = 1.

Remark 4. Let us note that in the case n = 1, Goodstein's theorem shows that unary polynomial functions p are exactly the functions of the form p (y) = s ∨ (t ∧ y) with s = p (0) ≤ p (1) = t, and these can be written as p (y) = med (s, y, t) according to (3).

Let X 1 , . . . , X n be arbitrary sets with at least two elements, and for each k ∈ [n] let us fix two distinct elements 0 X k , 1 X k of X k . We shall say that a mapping ϕ k : X k → Y satisfies the boundary condition (for 0 X k and 1

X k ) if for every x k ∈ X k , (5) ϕ k (0 X k ) ≤ ϕ k (x k ) ≤ ϕ k (1 X k ).
Observe that if X k is a partially ordered set with least element 0 X k and greatest element 1 X k , and if ϕ k is order-preserving, then it satisfies the boundary condition (cf. also Remark 22). With no danger of ambiguity, we simply write 0 and 1 instead of 0 X k and 1 X k in the sequel.

A function f : i∈[n] X i → Y is said to be a pseudo-polynomial function, if there is a polynomial function p : Y n → Y and there are unary functions

ϕ k : X k → Y (k ∈ [n]), satisfying the boundary condition, such that (6) f (x) = p (ϕ (x)) = p(ϕ 1 (x 1 ), . . . , ϕ n (x n )) holds for all x = (x 1 , . . . , x n ) ∈ i∈[n] X i .
If p is a Sugeno integral, then we say that f is a pseudo-Sugeno integral. As it turns out, the notions of pseudo-polynomial function and pseudo-Sugeno integral are equivalent. This result was proved in [START_REF] Couceiro | Sugeno utility functions I: Axiomatizations[END_REF][START_REF] Couceiro | Axiomatizations and factorizations of Sugeno utility functions[END_REF] for chains Y , but the proof given there actually just uses the fact that Y is a distributive lattice and that polynomial functions are "range homogeneous", hence it applies verbatim to our setting.

Proposition 5. A function f : i∈[n] X i → Y is a pseudo-polynomial function if and only if it is a pseudo-Sugeno integral.
Clearly, if f is a pseudo-polynomial function, then it satisfies the following n-variable analogue of the boundary condition (5):

(7) f x 0 k ≤ f (x) ≤ f x 1 k for all k ∈ [n] , x ∈ i∈[n] X i ,
where x a k ∈ i∈[n] X i denotes the n-tuple which coincides with x in all but the k-th component, whose value is a. Remark 6. Note that the particular orderings ϕ k (0 5) and ( 7) could be reversed as the choice of 0 X k and 1 X k is arbitrary. Hence, the current notion of boundary condition is not more restrictive than the one used in [START_REF] Couceiro | Axiomatizations and factorizations of Sugeno utility functions[END_REF].

X k ) ≤ ϕ k (1 X k ) and f x 0 k ≤ f x 1 k in (
Next we define a property that can be used to characterize pseudo-polynomial functions. We say that f : [START_REF] Couceiro | Characterizations of discrete Sugeno integrals as polynomial functions over distributive lattices[END_REF], then [START_REF] Couceiro | Sugeno utility functions II: Factorizations[END_REF] holds.

i∈[n] X i → Y is pseudo-median decomposable if for each k ∈ [n] there is a unary function ϕ k : X k → Y satisfying (5), such that (8) f (x) = med f (x 0 k ), ϕ k (x k ), f (x 1 k ) for every x ∈ i∈[n] X i . Note that if f is pseudo-median decomposable w.r.t. unary functions ϕ k : X k → Y (k ∈ [n]) satisfying
The following theorem shows that every pseudo-median decomposable function is a pseudo-polynomial function, and provides a disjunctive normal form of a polynomial function p f which can be used to factorize f . This theorem appears in [START_REF] Couceiro | Sugeno utility functions II: Factorizations[END_REF][START_REF] Couceiro | Axiomatizations and factorizations of Sugeno utility functions[END_REF] for the special case of chains. We use the notation 1 I for the characteristic vector of

I ⊆ [n] in i∈[n] X i , i.e., 1 I ∈ i∈[n] X i is the n-tuple whose i-th component is 1 Xi if i ∈ I, and 0 Xi otherwise. Theorem 7. If f : i∈[n] X i → Y is pseudo-median decomposable w.r.t. unary func- tions ϕ k : X k → Y (k ∈ [n]), then f (x) = p f (ϕ (x))
, where the polynomial function p f is given by

(9) p f (y 1 , . . . , y n ) = I⊆[n] f 1 I ∧ i∈I y i .
Proof. We need to prove that the following identity holds:

(10) f (x 1 , . . . , x n ) = I⊆[n] f 1 I ∧ i∈I ϕ i (x i ) .
We proceed by induction on n. If n = 1, then the right hand side of ( 10) takes the form

f (0) ∨ (f (1) ∧ ϕ 1 (x 1 )
). From ( 7) it follows that f (0) ≤ f (1), and then, using (3), we can rewrite

f (0) ∨ (f (1) ∧ ϕ 1 (x 1 )) as med (f (0) , ϕ 1 (x 1 ) , f (1)
), which equals f (x 1 ) by ( 8). Now suppose that the statement of the theorem is true for all pseudo-median decomposable functions in n -1 variables. Let f 0 and f 1 be the (n -1)-ary functions defined by

f 0 (x 1 , . . . , x n-1 ) = f (x 1 , . . . , x n-1 , 0) , f 1 (x 1 , . . . , x n-1 ) = f (x 1 , . . . , x n-1 , 1) .
Observe that (7) implies f 0 ≤ f 1 . Applying the pseudo-median decomposition to f with k = n and rewriting the median using (3), we obtain

f (x 1 , . . . , x n ) = med (f 0 (x 1 , . . . , x n-1 ) , ϕ n (x n ) , f 1 (x 1 , . . . , x n-1 )) (11) = f 0 (x 1 , . . . , x n-1 ) ∨ (f 1 (x 1 , . . . , x n-1 ) ∧ ϕ n (x n )) .
It is easy to verify that f 0 and f 1 are pseudo-median decomposable w.r.t. ϕ 1 , . . . , ϕ n-1 , therefore we can apply the induction hypothesis to these functions:

f 0 (x 1 , . . . , x n-1 ) = I⊆[n-1] f 0 1 I ∧ i∈I ϕ i (x i ) = I⊆[n-1] f 1 I ∧ i∈I ϕ i (x i ) , f 1 (x 1 , . . . , x n-1 ) = I⊆[n-1] f 1 1 I ∧ i∈I ϕ i (x i ) = I⊆[n-1] f 1 I∪{n} ∧ i∈I ϕ i (x i ) .
Substituting back into [START_REF] Dubois | Qualitative decision theory with Sugeno integrals, Fuzzy measures and integrals[END_REF] and using distributivity we obtain the desired equality [START_REF] Davey | Introduction to Lattices and Order[END_REF]. Now we can prove that pseudo-median decomposability actually characterizes pseudopolynomial functions (see [START_REF] Couceiro | Sugeno utility functions I: Axiomatizations[END_REF][START_REF] Couceiro | Axiomatizations and factorizations of Sugeno utility functions[END_REF] for the case of chains, where the proof is slightly simpler).

Theorem 8. Let f : i∈[n] X i → Y be a function. Then f is a pseudo-polynomial function if and only if f is pseudo-median decomposable.
Proof. Sufficiency follows from Theorem 7, so we only need to show that if f is a pseudopolynomial function, then it is pseudo-median decomposable. Suppose that f (x) = p (ϕ (x)) as in [START_REF] Couceiro | Sugeno utility functions I: Axiomatizations[END_REF], and let k ∈ [n]. We have to prove that (8) holds for all x ∈ i∈[n] X i . Regarding x i as a fixed element of X i for each i = k, we can define a unary polynomial function

u : Y → Y by u (y) = p(ϕ 1 (x 1 ), . . . , ϕ k-1 (x k-1 ), y, ϕ k+1 (x k+1 ), . . . , ϕ n (x n )).
To simplify notation, let us write a := ϕ k (0) , z := ϕ k (x k ) , b := ϕ k (1), and let us note that the boundary condition (5) yields a ≤ z ≤ b. With this notation (8) reads as u (z) = med (u (a) , z, u (b)). In order to verify this equality, we write u in disjunctive normal form as in Remark 4: u (y) = s ∨ (t ∧ y), where s ≤ t. Now the proof is a straightforward computation, making heavy use of distributivity:

med (u (a) , z, u (b)) = u (a) ∨ (u (b) ∧ z) = (s ∨ (t ∧ a)) ∨ ((s ∨ (t ∧ b)) ∧ z) = s ∨ (t ∧ a) ∨ (s ∧ z) ∨ (t ∧ b ∧ z) = s ∨ (t ∧ a) ∨ (s ∧ z) ∨ (t ∧ z) = s ∨ (t ∧ a) ∨ (t ∧ z) = s ∨ (t ∧ (a ∨ z)) = s ∨ (t ∧ z) = u (z)

Characterization of pseudo-polynomial functions

Let f : i∈[n] X i → Y be a function satisfying [START_REF] Couceiro | Sugeno utility functions II: Factorizations[END_REF], and for each k ∈ [n] let us define two auxiliary functions Φ - k , Φ + k : X k → Y as follows:

(12) Φ - k (a k ) := x:x k =a k cl f (x) ∧ f (x 0 k ) , Φ + k (a k ) := x:x k =a k int f (x) ∨ f (x 1 k ) .
Here the join and the meet range over all x ∈ i∈[n] X i whose k-th component is a k . Note that from [START_REF] Couceiro | Sugeno utility functions II: Factorizations[END_REF] it follows that Φ - k and Φ + k satisfy the boundary condition [START_REF] Couceiro | Characterizations of discrete Sugeno integrals as polynomial functions over distributive lattices[END_REF]. With the help of these functions, we will give a necessary and sufficient condition for f to be a pseudo-polynomial function. The following lemma formulates a simple observation that allows us to solve equation ( 8) for ϕ k (x k ). Lemma 9. For any u ≤ m ≤ w, v ∈ Y the following two conditions are equivalent:

(i) med (u, v, w) = m; (ii) m ∧ u ≤ v ≤ m ∨ w.
Proof. Assuming that med (u, v, w) = m, we can estimate m ∧ u using (3) as follows:

m ∧ u = u ∨ (v ∧ w) ∧ u = (u ∧ u) ∨ (v ∧ w ∧ u) = 0 ∨ (v ∧ w ∧ u) ≤ v.
An analogous argument shows that v ≤ m ∨ w, and this establishes (i) =⇒ (ii).

In order to prove (ii) =⇒ (i), let us first compute med (u, m ∧ u, w), again with the help of (3):

med (u, m ∧ u, w) = u ∨ (m ∧ u ∧ w) = (u ∨ m) ∧ (u ∨ u) ∧ (u ∨ w) = m ∧ 1 ∧ w = m.
Similarly, we have med (u, m ∨ w, w) = m, and then, using (ii) and the monotonicity of the median function, we conclude

m = med (u, m ∧ u, w) ≤ med (u, v, w) ≤ med (u, m ∨ w, w) = m, hence med (u, v, w) = m.
With the help of the above lemma we derive from Theorem 8 a necessary condition for f to be a pseudo-polynomial function.

Proposition 10. If f : i∈[n] X i → Y is a pseudo-polynomial function, then it satisfies (7) and (13) Φ - k ≤ Φ + k , for all k ∈ [n] . Proof. Let us suppose that f (x) = p (ϕ (x)
) is a pseudo-polynomial function. Then [START_REF] Couceiro | Axiomatizations and factorizations of Sugeno utility functions[END_REF] holds by Theorem 8, and applying Lemma 9 with

u = f x 0 k , m = f (x) , w = f x 1 k and v = ϕ k (x k ), we see that f (x) ∧ f (x 0 k ) ≤ ϕ k (x k ) ≤ f (x) ∨ f (x 1 k ). Moreover, since ϕ k (x k ) ∈ Y , we have cl f (x) ∧ f (x 0 k ) ≤ ϕ k (x k ) ≤ int f (x) ∨ f (x 1 k ) . Considering these inequalities for all x ∈ i∈[n] X i with a fixed k-th component x k = a k , it follows that (14) Φ - k (a k ) ≤ ϕ k (a k ) ≤ Φ + k (a k ) for all k ∈ [n] , a k ∈ X k .
Remark 11. Let us note that (13) holds if and only if each joinand in the definition of Φ - k (a k ) is less than or equal to each meetand in the definition of Φ + k (a k ). In other words, [START_REF] Grabisch | Aggregation Functions. Encyclopedia of Mathematics and its Applications[END_REF]

is equivalent to cl f (y) ∧ f (y 0 k ) ≤ int f (x) ∨ f (x 1 k ) for all x, y ∈ i∈[n]
X with x k = y k .

In order to prove that the necessary condition presented in the above proposition is also sufficient, we verify that ( 7) and ( 13) imply that f is pseudo-median decomposable with respect to Φ - 1 , . . . , Φ - n and also with respect to Φ + 1 , . . . , Φ + n . Proposition 12. Suppose that f : i∈[n] X i → Y satisfies [START_REF] Couceiro | Sugeno utility functions II: Factorizations[END_REF] and [START_REF] Grabisch | Aggregation Functions. Encyclopedia of Mathematics and its Applications[END_REF]. Then, for all x ∈ i∈[n] X i and k ∈ [n], we have

f (x) = med f (x 0 k ), Φ - k (x k ), f (x 1 k ) = med f (x 0 k ), Φ + k (x k ), f (x 1 k ) . Proof.
We prove that f is pseudo-median decomposable with respect to Φ - 1 , . . . , Φ - n , and leave to the reader the analogous argument for Φ + 1 , . . . ,

Φ + n . Let us fix k ∈ [n] , a k ∈ X k and x ∈ i∈[n] X i with x k = a k . By the definition of Φ - k , we have med f (x 0 k ), Φ - k (a k ), f (x 1 k ) = med f (x 0 k ), y:y k =a k cl f (y) ∧ f (y 0 k ) , f (x 1 k ) .
From the distributivity of Y it follows that joins distribute over medians, and thus:

(15) med f (x 0 k ), Φ - k (a k ), f (x 1 k ) = y:y k =a k med f (x 0 k ), cl f (y) ∧ f (y 0 k ) , f (x 1 k ) .
We can estimate this join from below by keeping only the joinand corresponding to y = x (this indeed appears in the join, since x k = a k ):

(16) med f (x 0 k ), Φ - k (a k ), f (x 1 k ) ≥ med f (x 0 k ), cl f (x) ∧ f (x 0 k ) , f (x 1 k ) . Applying Lemma 9 with u = f (x 0 k ), v = cl f (x) ∧ f (x 0 k ) , w = f (x 1 k
) and m = f (x) and taking into account that f x 0 k ≤ f (x) ≤ f x 1 k holds by [START_REF] Couceiro | Sugeno utility functions II: Factorizations[END_REF], we see that the right hand side of (16) equals f (x). This yields the inequality [START_REF] Sugeno | Theory of fuzzy integrals and its applications[END_REF] med

f (x 0 k ), Φ - k (a k ), f (x 1 k ) ≥ f (x)
. In order to prove the converse inequality, let us note that property [START_REF] Grabisch | Aggregation Functions. Encyclopedia of Mathematics and its Applications[END_REF]

implies cl f (y) ∧ f (y 0 k ) ≤ int f (x) ∨ f (x 1 k ) , whenever y k = a k (see Remark 11). Thus, replacing cl f (y) ∧ f (y 0 k ) by int f (x) ∨ f (x 1
k ) in each joinand on the right hand side of (15), we get the upper estimate [START_REF] Sugeno | Fuzzy measures and fuzzy integrals-a survey[END_REF] med Lemma 9 shows that the right hand side of (18) equals f (x), hence we have [START_REF] Sugeno | Theory of fuzzy integrals and its applications[END_REF] and (19), we get the desired equality

f (x 0 k ), Φ - k (a k ), f (x 1 k ) ≤ med f (x 0 k ), int f (x) ∨ f (x 1 k ) , f (x 1 k ) . Again,
(19) med f (x 0 k ), Φ - k (a k ), f (x 1 k ) ≤ f (x) . Combining inequalities
med f (x 0 k ), Φ - k (a k ), f (x 1 k ) = f (x) .
Propositions 10 and 12 together with Theorem 8 yield the following characterization of pseudo-polynomial functions.

Theorem 13. A function f : i∈[n] X i → Y is a pseudo-polynomial function if and only if it satisfies conditions [START_REF] Couceiro | Sugeno utility functions II: Factorizations[END_REF] and [START_REF] Grabisch | Aggregation Functions. Encyclopedia of Mathematics and its Applications[END_REF].

Remark 14. Theorem 13 is of different nature than Theorem 8 and the various characterizations obtained in [START_REF] Couceiro | Axiomatizations and factorizations of Sugeno utility functions[END_REF]: here the necessary and sufficient condition for f being a pseudo-polynomial function is given solely in terms of f itself, without referring to the existence of certain functions ϕ k .

Factorizations of pseudo-polynomial functions

Let us suppose that f : i∈[n] X i → Y satisfies ( 7) and [START_REF] Grabisch | Aggregation Functions. Encyclopedia of Mathematics and its Applications[END_REF]. According to Theorem 13, f is a pseudo-polynomial function, i.e., it has a factorization of the form f (x) = p (ϕ (x)), where p : Y n → Y is a polynomial function and each ϕ k :

X k → Y (k ∈ [n]
) is a unary map satisfying [START_REF] Couceiro | Characterizations of discrete Sugeno integrals as polynomial functions over distributive lattices[END_REF]. We now show how to construct such a factorization; in fact, we will find all possible factorizations. First we describe the set of possible functions ϕ k .

Theorem 15. For any function f : i∈[n] X i → Y satisfying [START_REF] Couceiro | Sugeno utility functions II: Factorizations[END_REF] and unary maps

ϕ k : X k → Y (k ∈ [n]
) satisfying (5), the following three conditions are equivalent:

(i) Φ - k ≤ ϕ k ≤ Φ + k holds for all k ∈ [n]; (ii) f (x) = p f (ϕ (x))
(where p f is given by (9) in Theorem 7); (iii) there exists a polynomial function p :

Y n → Y such that f (x) = p (ϕ (x)).
Proof. The implication (ii) =⇒ (iii) is trivial, and (iii) =⇒ (i) has been established in the course of the proof of Proposition 10 (see equation ( 14)).

So suppose that (i) holds. Then obviously (13) holds, and Proposition 12 shows that f is pseudo-median decomposable with respect to Φ - 1 , . . . , Φ - n and also with respect to Φ + 1 , . . . ,

Φ + n . Since Φ - k ≤ ϕ k ≤ Φ + k holds for all k ∈ [n] by (i), we have f (x) = med f (x 0 k ), Φ - k (x k ), f (x 1 k ) ≤ med f (x 0 k ), ϕ k (x k ), f (x 1 k ) ≤ med f (x 0 k ), Φ + k (x k ), f (x 1 k ) = f (x)
, therefore f is pseudo-median decomposable with respect to ϕ 1 , . . . , ϕ n . Now (ii) follows immediately from Theorem 7.

Theorem 15 describes all those unary maps ϕ 1 , . . . , ϕ n that can occur in a factorization of f , but it does not provide all possible polynomial functions p. (We know that p f can be used in any factorization, but there may be others as well.) To find all factorizations (6) of f , let us fix unary functions ϕ k : since e I = ϕ 1 I . We show that (20) is not only necessary but also sufficient to establish the factorization f (x) = p (ϕ (x)).

X k → Y (k ∈ [n]) satisfying (5), such that Φ - k ≤ ϕ k ≤ Φ + k for each k ∈ [n]. To simplify notation, let a k = ϕ k (0 X k ) , b k = ϕ k (1 X k ),
Lemma 16. Let f : i∈[n] X i → Y be a function satisfying [START_REF] Couceiro | Sugeno utility functions II: Factorizations[END_REF] and [START_REF] Grabisch | Aggregation Functions. Encyclopedia of Mathematics and its Applications[END_REF], and let

ϕ k : X k → Y (k ∈ [n]) be maps satisfying (5), such that Φ - k ≤ ϕ k ≤ Φ + k for all k ∈ [n]. Then a polynomial function p : Y n → Y yields a factorization f (x) = p (ϕ (x)) if and only if (20) holds.
Proof. As noted above, necessity is trivial. To prove the sufficiency, let us assume that p satisfies (20), and let us define a function

f ′ : i∈[n] X i → Y by f ′ (x) = p (ϕ (x))
. Then f ′ is a pseudo-polynomial function, and by Theorem 8 it is pseudo-median decomposable with respect to ϕ 1 , . . . , ϕ n . From Theorem 7 we get the following expression for f ′ :

(21) f ′ (x) = I⊆[n] f ′ 1 I ∧ i∈I ϕ i (x i ) .
The assumptions on f and ϕ k guarantee that f (x) = p f (ϕ (x)) by Theorem 15, and hence f can be written as

(22) f (x) = I⊆[n] f 1 I ∧ i∈I ϕ i (x i ) .
Since f ′ 1 I = p ϕ 1 I = p (e I ) and p (e I ) = f 1 I by (20), it follows from (21) and ( 22) that f ′ (x) = f (x).

Table 1. The airline example (a) The function f

x 1 x 2 f (x 1 , x 2 ) A 1 E B A 1 F B A 2 E B A 2 F D A 3 E N A 3 F G A 4 E N A 4 F V (b) The functions Φ - k , Φ + k x 1 Φ - 1 (x 1 ) Φ + 1 (x 1 ) A 1 B B A 2 D D A 3 G G A 4 V V x 2 Φ - 2 (x 2 ) Φ + 2 (x 2 ) E B N F V V
For a given f and given a k , b k ∈ Y , (20) gives rise to a polynomial interpolation problem over Y : the values of the unknown polynomial function p are prescribed at certain (2 n many) points in Y n . It has been shown in [START_REF] Couceiro | Interpolation by polynomial functions of distributive lattices: a generalization of a theorem of[END_REF] that the least solution of this interpolation problem is

p -(y) = I⊆[n] c - I ∧ i∈I y i , where c - I = cl f 1 I ∧ i / ∈I a i ,
whereas the greatest solution is

p + (y) = I⊆[n] c + I ∧ i∈I y i , where c + I = int f 1 I ∨ i∈I b i .
In other words, a polynomial function p is a solution of (20) if and only if p -≤ p ≤ p + . Since, by Theorem 1, p is uniquely determined by its values on the tuples 1

I (I ⊆ [n]),
this is equivalent to

c - I = p -(1 I ) ≤ p (1 I ) ≤ p + (1 I ) = c + I for all I ⊆ [n] .
Thus we obtain the following description of all possible factorizations of a given pseudopolynomial function f . Theorem 17. Let f : i∈[n] X i → Y be a function satisfying [START_REF] Couceiro | Sugeno utility functions II: Factorizations[END_REF], for each k ∈ [n] let ϕ k : X k → Y be a given function satisfying [START_REF] Couceiro | Characterizations of discrete Sugeno integrals as polynomial functions over distributive lattices[END_REF], and let p :

Y n → Y be a polynomial function. Then f (x) = p (ϕ (x)) if and only if Φ - k ≤ ϕ k ≤ Φ + k for each k ∈ [n]
, and we have p -≤ p ≤ p + . Remark 18. Note that the polynomial functions p -and p + are defined in terms of the maps ϕ k , hence we have to choose these maps first, and only then we can determine p - and p + (cf. the example in Section 5). Remark 20. If X k is a partially ordered set for each k ∈ [n] and f is order-preserving, then Φ - k and Φ + k are also order-preserving. This shows that every order-preserving pseudo-polynomial function has a factorization where each ϕ k is order-preserving. Consequently, order-preserving pseudo-Sugeno integrals coincide with Sugeno utility functions (cf. Corollary 2 in [START_REF] Couceiro | Axiomatizations and factorizations of Sugeno utility functions[END_REF]).

An example

We illustrate the results of the previous section with a simple example, where preferences about travelling with four airlines A 1 , A 2 , A 3 , A 4 in economy class (E) and first class (F) are modelled by pseudo-polynomial functions. Table 1(a) shows a fictitious customer's evaluation of these eight options, where B,N, G, V stand for "bad", "neutral",

B N D G V B N D G V D N G Figure 1.
The lattice Y and its embedding into a power set "good" and "very good", respectively, and D means "don't know". This table defines an overall preference function f :

X 1 × X 2 → Y ,
where

X 1 := {A 1 , A 2 , A 3 , A 4 } , X 2 := {E, F} , Y := {B, N, G, V, D} .
It is plausible that D is better than B, worse than G, and incomparable with N, hence the ordering of Y is the one given in Figure 1. This is a distributive lattice that can be embedded into the power set of a three-element set U as shown in Figure 1. The figure does not indicate the representation of each element of Y as a subset of U , only the complements of the elements, since this is all we need in order to perform the computations that follow. (Note that B and V are the complements of each other.)

For y ∈ Y we have obviously cl (y) = int (y) = y, and for the three "extra" elements the closures and interiors can be read easily from Figure 1:

cl D = V, cl N = V, cl G = V, int D = N, int N = D, int G = B.
It is obvious that 0 X2 = E and 1 X2 = F, but 0 X1 and 1 X1 are not clear. However, from Table 1(a) we can infer that 0 X1 = A 1 and 1 X1 = A 4 if f satisfies (7) at all. (If not, then f is not a pseudo-polynomial function.) Table 1(b) shows the auxiliary functions Φ - k , Φ + k corresponding to the function f . We give the details of the computation of Φ + 2 (E), the other values can be calculated similarly:

Φ + 2 (E) = x1∈X1 int f (x 1 , E) ∨ f (x 1 , F) = int(B ∨ B) ∧ int(B ∨ D) ∧ int(N ∨ G) ∧ int(N ∨ V) = int(V) ∧ int(D) ∧ int(D) ∧ int(N) = V ∧ N ∧ N ∧ N = N.
We can see that Φ - k ≤ Φ + k for k = 1, 2, therefore f is a pseudo-polynomial function by Theorem 13. Theorem 15 implies that in any factorization

f (x 1 , x 2 ) = p (ϕ 1 (x 1 ) , ϕ 2 (x 2 )) of f , we must have ϕ 1 = Φ - 1 = Φ + 1
, while we have two possibilities for ϕ 2 (as ϕ 2 (E) can be chosen to be B or N, and ϕ 2 (F) must be V). Thus there are two pairs of functions

(ϕ 1 , ϕ 2 ), namely Φ - 1 , Φ - 2 and Φ + 1 , Φ + 2
that allow us to factorize f . Theorem 15 also shows that in both cases one can use the polynomial function

p f (y 1 , y 2 ) = B∨(y 1 ∧ N)∨(y 2 ∧ B)∨(V ∧ y 1 ∧ y 2 ) = (y 1 ∧ N)∨(y 1 ∧ y 2 ) = y 1 ∧(y 2 ∨ N) .

Computing the coefficients c

- I , c + I for Φ - 1 , Φ - 2 , one can see that in this case p -= p f = p + , i.e., p = p f is the only polynomial function such that f (x 1 , x 2 ) = p Φ - 1 (x 1 ) , Φ - 2 (x 2
) . On the other hand, choosing (ϕ 1 , ϕ 2 ) = Φ + 1 , Φ + 2 , we obtain p -= y 1 ∧ y 2 and p + = p f , and these are the only possibilities, since there is no polynomial function strictly between p -and p + . Thus f has altogether three factorizations:

f (x 1 , x 2 ) = Φ - 1 (x 1 ) ∧ Φ - 2 (x 2 ) ∨ N = Φ + 1 (x 1 ) ∧ Φ + 2 (x 2 ) ∨ N = Φ + 1 (x 1 ) ∧ Φ + 2 (x 2
) . Note that these factorizations are essentially the same, since Φ - 2 ∨ N = Φ + 2 ∨ N = Φ + 2 . The meaning of Φ + 2 is pretty obvious, and Φ + 1 shows the customer's opinion about the The fact that Φ + 1 (x 1 ) and Φ + 2 (x 2 ) are aggregated in a conjunctive manner indicates a pessimistic attitude: the customer expects an enjoyable flight only if both the airline and the travel class are good enough.

Pseudo-polynomial functions over chains

In this section we consider the case when Y is a finite chain. As we will see, in this case the results of Section 4 lead to a generalization of Algorithm SUFF presented in [START_REF] Couceiro | Axiomatizations and factorizations of Sugeno utility functions[END_REF]. As before, we will suppose that Y is a sublattice of P (U ) for some finite set U , with least element ∅ and greatest element U . We may assume without loss of generality that Let us assume that f : i∈[n] X i → Y satisfies [START_REF] Couceiro | Sugeno utility functions II: Factorizations[END_REF]. Then

f x 0 k = [u] , f (x) = [v] , f x 1 k = [w] with u ≤ v ≤ w, hence we have f (x) ∧ f (x 0 k ) = {u + 1, . . . , v} , f (x) ∨ f (x 1 k ) = {1, .
. . , v, w + 1, . . . , m} . Therefore the terms in the definition of Φ - k and Φ + k can be determined as follows:

cl f (x) ∧ f (x 0 k ) = f (x) , if f x 0 k < f (x) ; ∅, if f x 0 k = f (x) ; (23) int f (x) ∨ f (x 1 k ) = f (x) , if f x 1 k > f (x) ; U, if f x 1 k = f (x) . (24)
Thus we obtain from Theorem 13 and Remark 11 the following characterization of pseudo-polynomial functions valued in a chain.

Theorem 21. If Y is a finite chain, then a function f : i∈[n] X i → Y is a pseudopolynomial function if and only if it satisfies condition [START_REF] Couceiro | Sugeno utility functions II: Factorizations[END_REF] and

f x 0 k < f (x a k k ) and f (y a k k ) < f y 1 k =⇒ f (x a k k ) ≤ f (y a k k ) holds for all x, y ∈ i∈[n] X i and k ∈ [n], a k ∈ X k .
Let us now define the following three sets for any k ∈ [n] , a k ∈ X k , as in [START_REF] Couceiro | Axiomatizations and factorizations of Sugeno utility functions[END_REF]:

W f a k = f (x) : x k = a k and f x 0 k < f (x) < f x 1 k , L f a k = f (x) : x k = a k and f x 0 k < f (x) = f x 1 k , U f a k = f (x) : x k = a k and f x 0 k = f (x) < f x 1 k .
From ( 23) and ( 24) it follows that Φ

- k (a k ) = L f a k ∨ W f a k and Φ + k (a k ) = U f a k ∧ W f a k , hence the condition Φ - k ≤ ϕ k ≤ Φ +
k in Theorem 15 can be reformulated as follows:

(a) either

W f a k = {ϕ k (a k )} or W f a k = ∅; (b) ϕ k (a k ) ≥ L f a k ; (c) ϕ k (a k ) ≤ U f a k .
Thus by Theorem 15, f is a pseudo-polynomial function if and only if there are functions ϕ k satisfying the above three conditions. If each X k is a bounded chain and f is an order-preserving function depending on all of its variables, then (a),(b),(c) are equivalent to equation [START_REF] Sugeno | Fuzzy measures and fuzzy integrals-a survey[END_REF] in [START_REF] Couceiro | Axiomatizations and factorizations of Sugeno utility functions[END_REF], and Algorithm SUFF does not return the value false if and only if (13) holds. Thus, in the finite case, Theorem 7 of [START_REF] Couceiro | Axiomatizations and factorizations of Sugeno utility functions[END_REF] follows as a special case of Theorem 15. Moreover, the results of Section 4 not only generalize Algorithm SUFF to arbitrary finite distributive lattices (instead of finite chains) and to pseudo-polynomial functions (instead of Sugeno utility functions), but they provide all possible factorizations of a given pseudo-polynomial function f (whereas Algorithm SUFF constructs only one factorization).

Algorithm 1 Sugeno Utility Function Factorization (SUFF) [START_REF] Couceiro | Axiomatizations and factorizations of Sugeno utility functions[END_REF] Require: f depends on all of its variables and satisfies [START_REF] Couceiro | Sugeno utility functions II: Factorizations[END_REF] 1: if f is not order-preserving then

2: return false // f is not a SUF 3: end if 4: for k ∈ [n] do 5: for a k ∈ X k do 6: compute W f a k 7: if W f a k ≥ 2 then 8: return false // f is not a SUF 9: end if 10: compute L f a k , U f a k and w a k := w if W f a k = {w} l a k := L f a k u a k := U f a k 11: if l a k > u a k or l a k > w a k or w a k > u a k then 12: return false // f is not a SUF 13: end if 14: if W f a k = ∅ then 15: ϕ f k (a k ) := w a k // (W) 16: else if L f a k = ∅ then 17: ϕ f k (a k ) := l a k // (L),(LU) 18: else if U f a k = ∅ then 19: ϕ f k (a k ) := u a k // (U
p f , ϕ f 1 , . . . , ϕ f n // f is a SUF Remark 22.
If the lattice Y is a finite chain, as it is the case in many applications, then any map ϕ k : X k → Y attains its minimum and its maximum at some points in X k , hence there exist elements 0 X k and 1 X k such that (5) holds. Thus, the boundary condition does not impose any restriction on ϕ k ; the point is that we must know the elements 0 X k and 1 X k , even if we do not know the function ϕ k . However, even this mild assumption can be released, by suitably modifying the definition of the functions Φ - k and Φ + k , so that they do not refer to 0 and 1 anymore:

Φ - k (a k ) := x:x k =a k ♥∈X k cl f (x) ∧ f (x ♥ k ) , Φ + k (a k ) := x:x k =a k ♥∈X k int f (x) ∨ f (x ♥ k ) .
To see that these new definitions yield the same functions as [START_REF] Goodstein | The solution of equations in a lattice[END_REF], we only need to observe that we have just added some new joinands to the join defining Φ - k , but each of these new joinands is dominated by some of the original joinands of [START_REF] Goodstein | The solution of equations in a lattice[END_REF]. Indeed, from [START_REF] Couceiro | Sugeno utility functions II: Factorizations[END_REF]

it follows that f (x ♥ k ) ≤ f (x 0 k ) for all ♥ ∈ X k , hence cl f (x) ∧ f (x ♥ k ) ≤ cl f (x) ∧ f (x 0 k ) .
Similarly, each of the new meetands that we have added to the meet defining Φ + k is absorbed by some of the original meetands.

With these new definitions, we can apply Theorem 13 to decide whether a given function f is a pseudo-polynomial function, and we can find all maps ϕ k that can appear in a factorization of f with the help of Theorem 15. Once we have the maps ϕ k , we can define 0 X k and 1 X k as 0 X k := argmin

x k ∈X k ϕ k (x k ) and 1 X k := argmax x k ∈X k ϕ k (x k ) ,
and then we can use Theorem 17 to find the possible polynomial functions p. (Here argmin and argmax denote the elements of X k where ϕ k attains its minimum and its maximum, respectively.) The price that we have to pay for this generality is that the computation of Φ - k and Φ + k is longer. Alternatively, we can apply "reverse engineering" to [START_REF] Couceiro | Sugeno utility functions II: Factorizations[END_REF], as in Section 5, in order to find 0 X k and 1 X k .

Concluding remarks

We have extended the study of Sugeno utility functions over chains developed in [START_REF] Couceiro | Sugeno utility functions I: Axiomatizations[END_REF][START_REF] Couceiro | Sugeno utility functions II: Factorizations[END_REF][START_REF] Couceiro | Axiomatizations and factorizations of Sugeno utility functions[END_REF] to the case of finite distributive lattices. We refined the axiomatization given in [START_REF] Couceiro | Sugeno utility functions I: Axiomatizations[END_REF][START_REF] Couceiro | Axiomatizations and factorizations of Sugeno utility functions[END_REF] by providing necessary and sufficient conditions for a function defined on a Cartesian product of arbitrary underlying sets and valued in a finite distributive lattice, to be factorizable as a pseudo-polynomial function [START_REF] Couceiro | Sugeno utility functions I: Axiomatizations[END_REF]. Moreover, in doing so, we were able to furnish all possible factorizations, if such a factorization exists, and we proposed a new procedure for constructing them, which subsumes that of [START_REF] Couceiro | Sugeno utility functions II: Factorizations[END_REF][START_REF] Couceiro | Axiomatizations and factorizations of Sugeno utility functions[END_REF] in the case when the codomain is a finite chain.

Looking at directions for further research, we are inevitably drawn to the two following topics. As mentioned, pseudo-polynomial functions play an important role in multicriteria decision making since they subsume the so-called Sugeno utility functions, which in turn are used to model preference relations: Say that a preference relation on X 1 × • • • × X n is Sugeno representable if there is a Sugeno utility function U : X 1 × • • • × X n → Y such that x y if and only if U (x) ≤ U (y). Given the results of the current paper, and following the line of research developed in [START_REF]Decision-Making Process -Concepts and Methods[END_REF][START_REF] Dubois | Qualitative decision theory with Sugeno integrals, Fuzzy measures and integrals[END_REF][START_REF] Rico | Preference modeling on totally ordered sets by the Sugeno integral[END_REF], it is natural to consider the following problem.

Problem 23. Axiomatize those preference relations that are Sugeno representable. This problem was solved in the realm of decision making under uncertainty in [START_REF] Dubois | Qualitative decision theory with Sugeno integrals, Fuzzy measures and integrals[END_REF]. The second emerging topic is of somewhat different nature. So far, we have played within the setting where no information is missing. However, in real-life situations this is rarely the case. Translating it into mathematical terms, it is often the case that information about the functions we deal with is incomplete. In other words, we are given partial functions in the sense that they are not everywhere defined. Taking the simplest case where the only aggregation functions considered are Sugeno integrals, we are faced with the following interpolation problem.

Problem 24. Given a partial function f : D → X, where X is a distributive lattice and D ⊆ X n , give necessary and sufficient conditions for the existence of a Sugeno integral p : X n → X which interpolates f on all of its domain D, i.e., p| D = f . If such a Sugeno integral exists, provide a procedure to compute it.

Again, this problem has been solved for the case of finite chains X in [START_REF] Rico | Preference modeling on totally ordered sets by the Sugeno integral[END_REF]. These two problems constitute topics of current research being carried out by the authors.

  all S ∈ P (U ).

  and for each I ⊆ [n] let e I ∈ Y n be the n-tuple whose i-th component is a i if i / ∈ I and b i if i ∈ I. If p : Y n → Y is a polynomial function such that f (x) = p (ϕ (x)), then (20) p (e I ) = f 1 I for all I ⊆ [n] ,

Remark 19 .

 19 Clearly, c - I ≤ f 1 I ≤ c + I holds independently of a k , b k , hence the polynomial function p f can be used in any factorization of f , as it was already shown in Theorem 7.

Figure 2 .

 2 Figure 2. The closure and interior of a subset of a chain

  U = [m] = {1, 2, . . . , m}, and Y = {[0] , [1] , . . . , [m]}, where [0] = ∅. The closure of a set S ⊆ U is the smallest set of the form [k] that contains S, while the interior of S is the largest set of the form [k] that is contained in S (see Figure 2). Formally, we have cl (S) = [max S] , int (S) = min S -1 .

  )

	20:	else
	21:	return false	// a k is inessential
	22:	end if
	23:	end for
	24: end for
	25: compute p f
	26: return

Acknowledgments. The first named author is supported by the internal research project F1R-MTH-PUL-09MRDO of the University of Luxembourg. The second 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).


Miguel Couceiro

Erkko Lehtonen

Tam Ás Waldhauser

ADDITIVE DECOMPOSITION SCHEMES FOR POLYNOMIAL FUNCTIONS OVER FIELDS

Keywords: 2010 Mathematics Subject Classification. 08A40, 12E05 function of several variables, arity gap, polynomial function, partial derivative

The authors' previous results on the arity gap of functions of several variables are refined by considering polynomial functions over arbitrary fields. We explicitly describe the polynomial functions with arity gap at least 3, as well as the polynomial functions with arity gap equal to 2 for fields of characteristic 0 or 2. These descriptions are given in the form of decomposition schemes of polynomial functions. Similar descriptions are given for arbitrary finite fields. However, we show that these descriptions do not extend to infinite fields of odd characteristic.

Introduction

The arity gap of a function f : A n → B is a quantity that indicates the minimum number of variables that become inessential when a pair of essential variables is identified in f . This notion was first studied by Salomaa [START_REF] Salomaa | On essential variables of functions, especially in the algebra of logic[END_REF], who showed that the arity gap of any Boolean function is at most 2. Willard [START_REF] Willard | Essential arities of term operations in finite algebras[END_REF] showed that the same upper bound holds for any function f : A n → B with a finite domain, provided that f depends on at least max(|A|, 3) + 1 variables. A complete classification of functions in regard to the arity gap was presented in [START_REF] Couceiro | Generalizations of Świerczkowski's lemma and the arity gap of finite functions[END_REF] and [START_REF] Couceiro | Decompositions of functions based on arity gap[END_REF]; see Theorem 2.6.

A decomposition scheme of functions based on the arity gap was proposed by Shtrakov and Koppitz [START_REF] Shtrakov | On finite functions with non-trivial arity gap[END_REF], and it was later refined in [START_REF] Couceiro | Decompositions of functions based on arity gap[END_REF] as follows (here ess f denotes the number of essential variables of f , and gap f denotes the arity gap of f ).

Theorem 1.1. Assume that (B; +) is a group with neutral element 0. Let f : A n → B, n ≥ 3, and 3 ≤ p ≤ n. Then the following two conditions are equivalent:

(i) ess f = n and gap f = p.

(ii) There exist functions g, h : A n → B such that f = g + h, h| A n = ≡ 0, h ≡ 0, and ess g = n -p. The decomposition f = g + h given above is unique.

Theorem 1.1 does not extend as such into the case when p = 2. Namely, there exist functions f : A n → B with gap f = 2 that do not admit a decomposition of the form given in item (ii). These exceptional functions are determined by oddsupp (see Section 2). However, as shown in [START_REF] Couceiro | Decompositions of functions based on arity gap[END_REF], if f is determined by oddsupp, then it can be decomposed as f = g + h with h| A n = ≡ 0, h ≡ 0, and g is a sum of functions of essential arity at most n -2. With these results as our starting point, we study in this paper polynomial functions over arbitrary fields. Our goal is to obtain further, more explicit and simpler decomposition schemes, especially for the case when gap f = 2 and f is determined by oddsupp.

The paper is organised as follows. In Section 2, we recall the basic notions and introduce preliminary results which will be needed throughout the paper. In Section 3, we provide a general decomposition scheme for polynomial functions over arbitrary fields with arity gap at least 3. In subsequent sections we focus on functions with arity gap 2. More precisely, in Section 4, we describe the polynomial functions determined by oddsupp, and we obtain decomposition schemes for functions with arity gap 2 over finite fields and fields of characteristic 2. In Section 5, we consider the case of fields of characteristic 0. In this case, we show that if f is a polynomial function such that f | A n = is determined by oddsupp, then f | A n = is constant. Hence, simpler decomposition schemes are available for polynomial functions with arity gap 2. The question whether similar decomposition schemes exist over infinite fields of odd characteristic is addressed in Section 6. We answer negatively to this question by means of an illustrative example.

Preliminaries

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.

Let Ess f := {i ∈ [n] : x i is essential in f }.
The cardinality of Ess f is called the essential arity of f and denoted by ess f . Let f :

A n → B, g : A m → B. We say that g is a 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 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 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 ).
Remark 2.1. Note that for all f : A n → B and for all i, j ∈ [n] with i = j, it holds that f i←j is equivalent to f j←i . Remark 2.2. Loosely speaking, a function g is a minor of f , if g can be obtained from f by permutation of variables, addition of inessential variables and identification of variables. Similarly, two functions are equivalent, if each one can be obtained from the other by permutation of variables and addition or deletion 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 ).
Remark 2.3. Note that the definition of arity gap refers only to essential variables. Hence, in order to determine the arity gap of a function f , we may consider, instead of f , an equivalent function f that is obtained from f by removing its inessential variables. It is easy to see that in this case gap f = gap f . Therefore, whenever we consider the arity gap of a function f , we may assume without loss of generality that f depends on all of its variables.

The notion of arity gap has been studied by several authors [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 polynomial functions over bounded distributive lattices[END_REF][START_REF] Couceiro | Decompositions of functions based on arity gap[END_REF][START_REF] Couceiro | The arity gap of order-preserving functions and extensions of pseudo-Boolean functions[END_REF][START_REF] Couceiro | Additive decomposability of functions over abelian groups[END_REF][START_REF] Salomaa | On essential variables of functions, especially in the algebra of logic[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 [START_REF] Couceiro | Generalizations of Świerczkowski's lemma and the arity gap of finite functions[END_REF], a general classification of functions according to their arity gap was established. In order to state this result, we need to recall a few notions.

For n ≥ 2, define

A n = := {(a 1 , . . . , a n ) ∈ A n : a i = a j for some i = j}. Furthermore, define A 1 = := A. Let f : A n → B. Any function g : A n → B satisfying f | A n = = g| A n = is called a support of f .
The quasi-arity of f , denoted qa f , is defined as the minimum of the essential arities of all supports of f , i.e., qa f := min g ess g where g ranges over the set of all supports of f . If qa f = m, then we say that f is quasi-m-ary. Note that if A is finite and n > |A|, then A n = = A n ; hence in this case qa f = ess f . Moreover, for an arbitrary A and n = 2, we have qa

f = ess f | A n = (see Lemma 4 in [3]). The case n = 2 is excluded, because if f : A 2 → B is a function such that f (a, a) = f (b, b) for some a, b ∈ A, then qa f = 1 yet ess f | A n = = 0.
Example 2.4. Consider the polynomial function f : R 3 → R induced by the polynomial

x 2 1 x 2 2 x 3 -x 2 1 x 2 x 2 3 -x 1 x 3 2 x 3 + x 1 x 2 x 3 3 + x 3 1 x 2 2 -x 2 2 x 3 3 + x 3 2 x 2 3 .
Writing the above polynomial as

(x 1 -x 2 )(x 1 -x 3 )(x 2 -x 3 )x 2 x 3 + x 3 1 x 2 2 , we see easily that f 1←2 (x 1 , x 2 , x 3 ) = x 5 2 , f 2←1 (x 1 , x 2 , x 3 ) = x 5 1 , f 1←3 (x 1 , x 2 , x 3 ) = x 2 2 x 3 3 , f 3←1 (x 1 , x 2 , x 3 ) = x 3 1 x 2 2 , f 2←3 (x 1 , x 2 , x 3 ) = x 3 1 x 2 3 , f 3←2 (x 1 , x 2 , x 3 ) = x 3 1 x 2 2 .
Note that f i←j is equivalent to f j←i for all i, j ∈ {1, 2, 3} with i = j, as pointed out in Remark 2.1. The function f clearly depends on all of its variables, and the essential arities of its identification minors are

ess f 1←2 = ess f 2←1 = 1, ess f 1←3 = ess f 3←1 = ess f 2←3 = ess f 3←2 = 2.
We conclude that gap f = 1.

Let g : R 3 → R be the function induced by the polynomial x 3 1 x 2 2 . It is clear that g is a support of f of the smallest possible essential arity. Thus qa f = ess g = 2.

Denote by P(A) the power set of A. Following Berman and Kisielewicz [START_REF] Berman | On the number of operations in a clone[END_REF], we 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}.
We say that a partial function f : S → B (S ⊆ A n ) is determined by oddsupp if there exists a function f * : P(A) → B such that

(1) f = f * • oddsupp| S .
Observe that only the restriction of f * to the set = is totally symmetric and f 2←1 does not depend on x 1 . We can now state the general classification of functions according to the arity gap. This result was first obtained in [START_REF] Couceiro | Generalizations of Świerczkowski's lemma and the arity gap of finite functions[END_REF] for functions with finite domains, and in [START_REF] Couceiro | Decompositions of functions based on arity gap[END_REF] it was shown to still hold for functions with arbitrary, possibly infinite domains.

P n (A) := T ∈ P(A) : |T | ∈
Theorem 2.6. Let A and B be arbitrary sets with at least two elements. Suppose that f : A n → B, n ≥ 2, depends on all of its variables.

(i)

For 3 ≤ p ≤ n, gap f = p if and only if qa f = n -p. (ii) For n = 3, gap f = 2 if and only if • qa f = n -2 or • qa f = n and f | A n = is determined by oddsupp. (iii) For n = 3, gap f = 2 if and only if there is a nonconstant unary function h : A → B and i 1 , i 2 , i 3 ∈ {0, 1} such that f (x 1 , x 0 , x 0 ) = h(x i1 ), f (x 0 , x 1 , x 0 ) = h(x i2 ), f (x 0 , x 0 , x 1 ) = h(x i3 ).
(iv) Otherwise gap f = 1.

Theorem 2.6 can be refined to obtain more explicit classifications by assuming certain structures on the domain A or the codomain B of f . Examples of such refinements include the complete classification of Boolean functions [START_REF] Couceiro | On the effect of variable identification on the essential arity of functions on finite sets[END_REF], pseudo-Boolean functions [START_REF] Couceiro | Generalizations of Świerczkowski's lemma and the arity gap of finite functions[END_REF], lattice polynomial functions [START_REF] Couceiro | The arity gap of polynomial functions over bounded distributive lattices[END_REF], or more generally, order-preserving functions [START_REF] Couceiro | The arity gap of order-preserving functions and extensions of pseudo-Boolean functions[END_REF]. Moreover, in [START_REF] Couceiro | Decompositions of functions based on arity gap[END_REF], B was assumed to be a group, and the following decomposition scheme based on the quasiarity was obtained.

Theorem 2.7. Assume that (B; +) is a group with neutral element 0. Let f : A n → B, n ≥ 3, and 1 ≤ p ≤ n. Then the following two conditions are equivalent:

(i) ess f = n and qa f = n -p.

(ii) There exist functions g, h : A n → B such that f = g + h, h| A n = ≡ 0, h ≡ 0, and ess g = n -p. The decomposition f = g + h given above is unique.

In the case when p ≥ 3, condition (i) of Theorem 2.7 can be transformed into condition (i) of Theorem 1.1 by a straightforward application of Theorem 2.6(i). Thus, Theorem 1.1 is a special case of Theorem 2.7.

Remark 2.8. Note that if h : A n → B satisfies h| A n = ≡ 0 and h ≡ 0, then h depends on all of its variables. For, since h is not the constant 0 function, there exists a tuple a ∈ A n \ A n = such that h(a) = 0. For each i ∈ [n], we may change the i-th component of a to obtain a tuple b belonging to A n = , and we have g(b) = 0 = g(a), showing that g depends on the i-th variable. Therefore, ess h = n for the function h of Theorem 2.7.

Polynomial functions over fields

In what follows, we will assume that the reader is familiar with the basic notions of algebra, such as rings, unique factorization domains, fields, vector spaces, polynomials and polynomial functions. However, we find it useful to recall the following well-known result. Polynomials over infinite fields are in one-to-one correspondence with polynomial functions. Fact 3.1 establishes a correspondence between polynomials and functions over finite fields, which is not bijective. This correspondence can be made bijective by assuming that we only consider polynomials over a given finite field, say F = GF(q), in which the exponent of every variable in every monomial is at most q -1; we shall call such polynomials over finite fields canonical. In the case of infinite fields, every polynomial is canonical.

Given a polynomial function f : F n → F , we denote by P f the unique canonical polynomial which induces f . Given a polynomial p ∈ F [x 1 , . . . , x n ], we denote by p the function f : F n → F induced by p. Note that p + q = p + q for all p, q ∈ F [x 1 , . . . ,

x n ]. Fact 3.2. A variable x i is essential in a polynomial function f : F n → F if and only if x i occurs in P f .
Let F be a field, and let us apply the results of Section 2 in the case A = B = F for polynomial functions f : F n → F . Lemma 3.3. If f is a polynomial function over F , then the functions g and h in the decomposition f = g +h given in Theorem 1.1 and Theorem 2.7 are also polynomial functions.

Proof. Since ess g = n -p ≤ n -1, the function g has an inessential variable, say the i-th variable is inessential in g. Let j = i. We clearly have g i←j = g, and since h| A n = ≡ 0, we have f i←j = g i←j + h i←j = g + 0 = g. Thus, g is a minor of f and hence a polynomial function. Then h = f -g is a polynomial function as well.

Lemma 3.4. If h is an n-ary polynomial function over F , then h| F n = ≡ 0 if and only if h is induced by a multiple of the polynomial

∆ n = 1≤i<j≤n (x i -x j ) ∈ F [x 1 , . . . , x n ].
Proof. It is clear that if h is induced by a multiple of ∆ n , then h| F n = ≡ 0. For the converse implication, we need to distinguish between the cases of finite and infinite F . Assume first that F is infinite, and let us suppose that h| F n = ≡ 0. Let us consider P h as an element of R[x n ], where R denotes the ring F [x 1 , . . . , x n-1 ]. Since h| F n = ≡ 0, each one of the elements x 1 , . . . , x n-1 ∈ R is a root of the unary polynomial P h (x n ) ∈ R[x n ]. Therefore P h is divisible by x i -x n for all i = 1, . . . , n -1. Repeating this argument with x j in place of x n , we can see that x i -x j divides P h for all 1 ≤ i < j ≤ n. Since these divisors of P h are relatively prime (and R[x n ] = F [x 1 , . . . , x n ] is a unique factorization domain), we can conclude that P h is divisible by their product ∆ n .

Assume then that F is finite. Define the function h : F n → F by the rule

h (a) = h(a) • (∆ n (a)) -1 , if a ∈ F n \ F n = , 0, if a ∈ F n = .
Observe that ∆ n (a) = 0 for every a ∈ F n \ F n = ; hence h is well defined. (In fact, h could be defined in an arbitrary way on

F n = .) Clearly h = h • ∆ n . By Fact 3.1, h is a polynomial function. Thus h is induced by the polynomial P h • ∆ n .
Combining the previous two lemmas with Theorem 1.1 we obtain the following description of polynomial functions over F with arity gap at least 3. Theorem 3.5. Let F be a field and let f : F n → F be a polynomial function of arity at least 3 that depends on all of its variables. Then gap f = p ≥ 3 if and only if there exist polynomials P, Q ∈ F [x 1 , . . . , x n ] such that f = P +Q, P is canonical, exactly n-p variables occur in P , and Q is a nonzero multiple of the polynomial ∆ n such that Q is not identically 0. Moreover, if f = P + Q , where P is canonical, n -p variables occur in P and Q is a nonzero multiple of ∆ n such that Q is not identically 0, then P = P and Q = Q.

Polynomial functions determined by oddsupp over fields of characteristic 2

We refine Fact 2.5 for polynomial functions over an arbitrary field F . For this purpose, we need some formalism. We use the following notation:

• If F is infinite, then N F denotes the set N of nonnegative integers, M F denotes the set of all nonnegative even integers, and ⊕ F denotes the usual addition of nonnegative integers. • If F has finite order q, then N F denotes the set {0, 1, . . . , q -1}, M F := N F , and ⊕ F is the operation on N F given by the following rules:

-0 ⊕ F 0 = 0.

-If a = 0 or b = 0, then a⊕ F b = c, where c is the unique number in {1, . . . , q -1} such that c ≡ a + b (mod q -1). Define the map τ F : N F → M F by the rule m → m ⊕ F m. Remark 4.1. If F is infinite or of even order, then τ F is a bijection that has 0 as a fixed point.

Lemma 4.2. Let F be an arbitrary field, and let f : F n → F be a polynomial function with

P f = k=(k1,...,kn)∈N n F c k x k1 1 x k2 2 • • • x kn n .
Then f 2←1 does not depend on x 1 if and only if for all (k, k

3 , . . . , k n ) ∈ N n-1 F with k = 0, (a1,a2)∈N 2 F a1⊕ F a2=k
c (a1,a2,k3,...,kn) = 0.

Proof. The canonical polynomial for f 2←1 is Proposition 4.3. Let F be an arbitrary field, and let f : F n → F be a polynomial function with

P f = k=(k1,...,kn)∈N n F c k x k1 1 x k2 2 • • • x kn n .
Then f is determined by oddsupp if and only if (A) f is symmetric, i.e., c (k1,...,kn) = c (l1,...,ln) whenever there is a permutation π ∈ S n such that k i = l π(i) for all i ∈ [n], and

(B) for all (k, k 3 , . . . , k n ) ∈ N n-1 F with k = 0, (a1,a2)∈N 2 F a1⊕ F a2=k c (a1,a2,k3,...,kn) = 0.
In particular, if the characteristic of F is 2, then f is determined by oddsupp if and only if condition (A) above holds together with

(B 2 ) c (k,k,k3,...,kn) = 0 for all (k, k, k 3 , . . . , k n ) ∈ N n
F with k = 0. Proof. By Fact 2.5, f is determined by oddsupp if and only if f is totally symmetric (i.e., (A) holds) and f 2←1 does not depend on x 1 (i.e., (B) holds, by Lemma 4.2).

Assume then that the characteristic of F is 2. We need to prove that condition (B) is equivalent to (B 2 ) under the assumption that f is totally symmetric. Let us analyse more carefully the coefficient .

Assuming that f is totally symmetric, we have c (a1,a2,b3,...,bn) = c (a2,a1,b3,...,bn) . Hence summand (II) above equals 2•C for some C ∈ F , which is equal to 0 since F has characteristic 2.

As for summand (I), observe first that if F is infinite and b 1 is odd, then there is no a 1 ∈ N F such that a 1 ⊕ F a 1 = b 1 ; hence the sum in (I) is empty and equals 0. Thus, in this case, we have d (b1,b3,...,bn) = 0. Otherwise, i.e., if F is finite or if F is infinite and b 1 is even, the sum in (I) has just one summand, namely the one indexed by a 1 = τ -1 F (b 1 ) (τ F is a bijection by Remark 4.1), and we have d (b1,b3,...,bn) = c (τ -1 F (b1),τ -1 F (b1),b3,...,bn) . By the above observations, we conclude that under the assumption that F has characteristic 2 and f is totally symmetric, condition (B) is equivalent to the condition that c (k,k,k3,...,kn) = 0 for all (k, k, k 3 , . . . , k n ) ∈ N n F with k = 0.

We reassemble in the following remark some facts that have been established in [START_REF] Couceiro | Decompositions of functions based on arity gap[END_REF] (more specifically, in the second paragraph of Section 5 and in Theorem 5.2 of [START_REF] Couceiro | Decompositions of functions based on arity gap[END_REF]). Remark 4.4. Assume that B is a set with a Boolean group structure (i.e., an abelian group such that x + x = 0 holds identically). Let n ≥ 3, and assume that f :

A n → B is a function such that f | A n
= is determined by oddsupp. Fix an element a ∈ A, and let ϕ : A n-2 → B be the function given by ϕ(a 1 , . . . , a n-2 ) := f (a 1 , . . . , a n-2 , a, a) for all a 1 , . . . , a n-2 ∈ A.

(Since f | A n

= is determined by oddsupp, the definition of ϕ is independent of the choice of a.) Then ϕ is determined by oddsupp, i.e., ϕ = ϕ * • oddsupp| A n-2 for some function ϕ * : P(A) → B. Let ϕ : A n → B be the function given by

ϕ(a 1 , . . . , a n ) = k<n 2|n-k 1≤i1<•••<i k ≤n ϕ * (oddsupp(a i1 , . . . , a i k )),
for all a 1 , . . . , a n ∈ A. Each summand ϕ * (oddsupp(a i1 , . . . , a i k )) on the right side is an identification minor of ϕ. The function ϕ is determined by oddsupp and ϕ|

A n = = f | A n = . Proposition 4.5.
Let F be a field, and let f :

F n → F be a polynomial function. If F is finite or the characteristic of F is 2, then f | F n
= is determined by oddsupp if and only if there exist polynomials P, Q ∈ F [x 1 , . . . , x n ] such that f = P + Q, P is determined by oddsupp, and Q is a multiple of the polynomial ∆ n .

Proof. For sufficiency, let us assume that f = P + Q, where P and Q are as in the statement of the proposition. Since P is determined by oddsupp, the restriction P | F n = is obviously determined by oddsupp as well. Moreover, Q| F n = ≡ 0 by Lemma 3.4. Thus,

f | F n = = P | F n = + Q| F n = = P | F n = is determined by oddsupp. For necessity, assume first that F is finite. If f | F n
= is determined by oddsupp, then there is a (not necessarily unique) function g such that g is determined by oddsupp and f | F n = = g| F n = . By Fact 3.1, g is a polynomial function; hence so is h = f -g. By Lemma 3.4, P h is a multiple of the polynomial ∆ n .

Assume then that F is a field of characteristic 2. Since the additive group of any field of characteristic 2 is a Boolean group, Remark 4.4 applies to operations on F . Assume that f :

F n → F is a polynomial function such that f | F n
= is determined by oddsupp, and let ϕ, ϕ * , and ϕ be as defined in Remark 4.4. Then ϕ is also a polynomial function. The functions ϕ * (oddsupp(a i1 , . . . , a i k )), being identification minors of ϕ, are polynomial functions. Therefore, Remark 4.4 implies that ϕ is a polynomial function and ϕ|

F n = = f | F n = .
Letting g := ϕ and h := f -g, and arguing as in the previous paragraph, we conclude that P h is a multiple of the polynomial ∆ n . Theorem 4.6. Let F be a field of characteristic 2, possibly infinite, and let f : F n → F be a polynomial function of arity at least 4 which depends on all of its variables. Then gap f = p ≥ 2 if and only if there exist polynomials P, Q ∈ F [x 1 , . . . , x n ] such that f = P +Q, P is canonical, Q is a multiple of the polynomial ∆ n , and either (a) exactly n -p variables occur in P and Q = 0, or (b) P is not a constant polynomial and P satisfies conditions (A) and (B 2 ) of Proposition 4.3.

Otherwise gap f = 1.

Proof. Combine Theorem 2.6, Theorem 2.7, Lemma 3. = is not constant. Corollary 4.7. Let F = GF(q), where q is a power of 2, and let f : F n → F be a polynomial function of essential arity n > max(q, 3). If gap f = 2, then f can be decomposed into a sum of polynomial functions of essential arity at most q -1.

Proof. If n > q, then F n = = F n ; hence case (a) in Theorem 4.6 cannot occur, while in case (b) we have Q ≡ 0; thus f = P . Moreover, in case (b), every monomial of P involves at most q -1 variables, by conditions (A) and (B 2 ) of Proposition 4.3. This implies that f can be written as a sum of polynomial functions of essential arity at most q -1, namely the polynomial functions corresponding to the monomials of f . Remark 4.8. Applying Corollary 4.7 in the case q = 2, we see that any function f : {0, 1} n → {0, 1} with essential arity n ≥ 4 and gap f = 2 can be written as a sum of at most unary functions, i.e., that f is a linear function.

Remark 4.9. From the results of [START_REF] Couceiro | Decompositions of functions based on arity gap[END_REF] it follows that if A is a finite set and B is a Boolean group, then every function f : A n → B with essential arity n > max(|A|, 3) and gap f = 2 can be decomposed into a sum of functions of essential arity at most n -2 (cf. Remark 4.4). Corollary 4.7 shows that the bound n -2 on the essential arity of the summands can be improved to q -1 (which is independent of n) if A = B = GF(q), where q is a power of 2 (for further results in this direction see also [START_REF] Couceiro | Additive decomposability of functions over abelian groups[END_REF]). In the example below, we will construct a polynomial function f : F n → F over F = GF(q) for any odd prime power q and any n ≥ 2, such that gap f = 2 but f cannot be written as a sum of (n -1)-ary functions. This shows that Corollary 4.7 does not hold for finite fields with odd characteristic and that the condition of B's being a Boolean group cannot be dropped in the aforementioned result of [START_REF] Couceiro | Decompositions of functions based on arity gap[END_REF].

Example 4.10. Let q be an odd prime power, and let f be the polynomial function

(2) f (x 1 , . . . , x n ) = n i=1 x q-1 i - 1 2
over GF(q), where 1 2 stands for the multiplicative inverse of 2 = 1 + 1 (it exists, since GF(q) is of odd characteristic). Let us identify the first two variables of f :

f (x 1 , x 1 , x 3 , . . . , x n ) = x q-1 1 - 1 2 2 • n i=3 x q-1 i - 1 2 = x 2q-2 1 -x q-1 1 + 1 4 • n i=3 x q-1 i - 1 2 = 1 4 • n i=3 x q-1 i - 1 2 ,
since x q 1 = x 1 holds identically in GF(q). We see that x 1 becomes an inessential variable, and ess f 2←1 = n -2. This together with the total symmetry of f shows that gap f = 2.

Suppose that f is a sum of functions of arity at most n -1. By Fact 3.1, these functions are polynomial. This implies that every monomial of P f involves at most n -1 variables. However, this is clearly not possible, as the expansion of the right side of ( 2) is a canonical polynomial that involves the monomial x q-1 1

• • • x q-1
n , which will not be cancelled by any other monomial. This contradiction shows that f cannot be expressed as a sum of functions of arity at most n -1.

Polynomial functions over fields of characteristic 0

We now consider the case of polynomial functions over fields of characteristic 0. Unlike polynomial functions over fields of characteristic 2 (see Proposition 4.5), it turns out that in the current case there is no polynomial function f :

F n → F whose restriction f | F n
= is nonconstant and determined by oddsupp.

We first recall the notion of partial derivative in the case of polynomial functions. We denote the partial derivative of a polynomial p ∈ F [x 1 , . . . , x n ] with respect to its i-th variable by ∂ i p, and we define it by the following rules. The i-th partial derivative of a monomial is defined by the rule

(3) ∂ i cx a1 1 • • • x an n = ca i x a1 1 • • • x ai-1 i-1 x ai-1 i x ai+1 i+1 • • • x an n , if a i = 0, 0, otherwise.
Moreover, partial derivatives are additive, i.e.,

∂ i j∈J f j = j∈J ∂ i f j . (4)
The partial derivatives of arbitrary polynomials can then be determined by application of (3) and ( 4). The partial derivative of a polynomial function f : F n → F with respect to its i-th variable is denoted by ∂ i f , and it is given by ∂ i f := ∂ i P f . Observe that for fields of characteristic 0, ∂ i f = 0 if and only if the i-th variable is inessential in f . Also, let us note the difference between

∂ 1 f (x 1 , x 1 , x 2 ) = ∂ 1 (f (x 1 , x 1 , x 2 )) and (∂ 1 f )(x 1 , x 1 , x 2 ),
where f : F 3 → F is a polynomial function. The first one is a partial derivative of an identification minor of f , while the second one is an identification minor of a partial derivative of f . The chain rule gives the following relationship between these polynomials functions:

∂ 1 f (x 1 , x 1 , x 2 ) = (∂ 1 f )(x 1 , x 1 , x 2 ) + (∂ 2 f )(x 1 , x 1 , x 2 ).
Since we will often consider derivatives of minors, it is worth formulating a generalization of the above formula.

Fact 5.1. Let F be a field of characteristic 0, let f : F n → F be a polynomial function, let σ : [n] → [m], and let g ∈ F m → F be the minor of f defined by g(x 1 , . . . , x m ) = f (x σ(1) , . . . , x σ(n) ). Then the j-th partial derivative of g is

∂ j g = σ(i)=j (∂ i f )(x σ(1) , . . . , x σ(n) ).
Lemma 5.2. Let F be a field of characteristic 0 and let f :

F n → F be a polynomial function of arity at least 2. Then f | F n = is determined by oddsupp if and only if f | F n = is constant, i.e., qa f = 0.
Proof. Sufficiency is obvious. We will prove necessity. For n = 2, the claim is trivial, so we will assume that n ≥ 3. Let us suppose that f | F n = is determined by oddsupp. Then f (x 1 , x 1 , x 3 , . . . , x n ) does not depend on x 1 by Fact 2.5; hence we have (∂ 1 f )(x 1 , x 1 , x 3 , . . . , x n ) + (∂ 2 f )(x 1 , x 1 , x 3 , . . . , x n ) = 0 by Fact 5.1. Let u = (x 1 , x 1 , x 1 , x 4 , . . . , x n ) ∈ F n . From the above equality it follows that

(∂ 1 f )(u) + (∂ 2 f )(u) = 0,
and a similar argument shows that

(∂ 1 f )(u) + (∂ 3 f )(u) = 0 and (∂ 2 f )(u) + (∂ 3 f )(u) = 0.
Since the characteristic of F is different from 2, by adding these three equalities we can conclude that

(∂ 1 f )(u) + (∂ 2 f )(u) + (∂ 3 f )(u) = 0.
However, according to Fact 5.1, (∂

1 f )(u)+(∂ 2 f )(u)+(∂ 3 f )(u)
is nothing else but the derivative of f (x 1 , x 1 , x 1 , x 4 , . . . , x n ) with respect to x 1 . This implies that f (x 1 , x 1 , x 1 , x 4 , . . . , x n ) does not depend on x 1 , i.e., [START_REF] Couceiro | Decompositions of functions based on arity gap[END_REF] f (a, a, a, x 4 , . . . ,

x n ) = f (b, b, b, x 4 , . . . , x n )
for any a, b, x 4 , . . . , x n ∈ F . Informally, equality (5) expresses the fact that whenever the first three entries of an ntuple are the same, then replacing these three entries with another element of F , the value of f does not change. (By symmetry, this is certainly true for any three entries, not only the first three.) From the definition of being determined by oddsupp it follows immediately that we can also change any two identical entries: [START_REF] Couceiro | The arity gap of order-preserving functions and extensions of pseudo-Boolean functions[END_REF] f

(• • • a • • • a • • • ) = f (• • • b • • • b • • • ).
Let x = (x 1 , . . . , x n ) be any vector in F n = . We may suppose without loss of generality that x 1 = x 2 . With the help of ( 5) and ( 6) we can replace the entries of x in triples and pairs, until all of them are the same: f (x) = f (x 1 , x 1 , x 3 , x 4 , x 5 , x 6 , . . . , x n ) = f (x 3 , x 3 , x 3 , x 4 , x 5 , x 6 , . . . , x n ) = f (x 4 , x 4 , x 4 , x 4 , x 5 , x 6 , . . . , x n ) = f (x 5 , x 5 , x 5 , x 5 , x 5 , x 6 , . . . , x n ) = f (x 6 , x 6 , x 6 , x 6 , x 6 , x 6 , . . . ,

x n ) = • • • = f (x n , x n , x n , x n , x n , x n , . . . , x n ).
If n is even, then [START_REF] Couceiro | The arity gap of order-preserving functions and extensions of pseudo-Boolean functions[END_REF] shows that f (x) = f (0):

f (x) = f (x n ,
x n , x n , x n , . . . , x n , x n ) = f (0, 0, 0, 0, . . . , 0, 0); while if n is odd, then we use both ( 5) and ( 6): Proof. By case (iii) of Theorem 2.6, there exist a nonconstant map h :

f (x) = f (x n , x n , x n , x n , x n , . . . , x n , x n ) = f (0, 0, 0, 0, 0, . . . , 0, 0). We have shown that f (x) = f (0) for all x ∈ F n = ; hence f | F n = is indeed constant. Remark 5.
A → B and i 1 , i 2 , i 3 ∈ {0, 1} such that f (x 1 , x 0 , x 0 ) = h(x i1 ), f (x 0 , x 1 , x 0 ) = h(x i2 ), f (x 0 , x 0 , x 1 ) = h(x i3 ).
Up to permutation of variables there are four possibilities for (i 1 , i 2 , i 3 ), namely (1, 1, 1), (0, 0, 0), (1, 1, 0) and (1, 0, 0). We will show that the first three cases cannot occur.

If (i 1 , i 2 , i 3 ) = (1, 1, 1) then f | F 3 = is determined by oddsupp, and Lemma 5.2 shows that h is constant, a contradiction.

If (i 1 , i 2 , i 3 ) = (0, 0, 0) then f (x 2 , x 1 , x 1 ) = f (x 1 , x 2 , x 1 ) = f (x 1 , x 1 , x 2 ) = h(x 1 ); hence f (x 2 , x 1 , x 1 ) does not depend on x 2 . By Fact 5.1 this means that (∂ 1 f )(x 2 , x 1 , x 1 ) = 0, in particular, (∂ 1 f )(x 1 , x 1 , x 1 ) = 0 for all x 1 ∈ F . Similarly, we have (∂ 2 f )(x 1 , x 1 , x 1 ) = (∂ 3 f )(x 1 , x 1 , x 1 ) = 0. Another application of Fact 5.1 yields ∂ 1 h(x 1 ) = ∂ 1 f (x 1 , x 1 , x 1 ) = (∂ 1 f )(x 1 , x 1 , x 1 ) + (∂ 2 f )(x 1 , x 1 , x 1 ) + (∂ 3 f )(x 1 , x 1 , x 1 ) = 0,
and this means that h is constant, a contradiction.

If (i 1 , i 2 , i 3 ) = (1, 1, 0), then f (x 1 , x 2 , x 2 ) = f (x 2 , x 1 , x 2 ) = f (x 1 , x 1 , x 2 ) = h(x 1 )
, which does not depend on x 2 . Again, by Fact 5.1 we see that

(∂ 2 f )(x 1 , x 2 , x 2 ) + (∂ 3 f )(x 1 , x 2 , x 2 ) = 0, (∂ 1 f )(x 2 , x 1 , x 2 ) + (∂ 3 f )(x 2 , x 1 , x 2 ) = 0, (∂ 3 f )(x 1 , x 1 , x 2 ) = 0.
From these equalities it follows that

(∂ 1 f )(x 1 , x 1 , x 1 ) = (∂ 2 f )(x 1 , x 1 , x 1 ) = (∂ 3 f )(x 1 , x 1 , x 1 ) = 0,
which is again a contradiction.

We are left with the case that (i 1 , i 2 , i 3 ) = (1, 0, 0) (up to permutation). This implies that f | F 3 = = h(x 1 )| F 3 = , i.e., qa f = 1.

Theorem 5.5. Let F be a field of characteristic 0, let n ≥ 3, and let P ∈ F [x 1 , . . . , x n ] be a polynomial such that all n variables occur in P . Then gap P = p ≥ 2 if and only if there exist polynomials Q, R ∈ F [x 1 , . . . , x n ] such that P = Q + R, exactly n -p variables occur in Q, and R is a nonzero multiple of the polynomial ∆ n . Otherwise gap P = 1. Moreover, the decomposition P = Q + R is unique.

Proof. For necessity, assume that gap P = p ≥ 2. By Lemma 5.2, if P | F n = is determined by oddsupp, then qa P = 0. Theorem 2.6 and Lemma 5.4 then imply that if gap P = p ≥ 2, then qa P = n -p. By Theorem 2.7, there exist unique functions g, h : F n → F such that P = g + h, h| F n = ≡ 0, h ≡ 0 and ess g = n -p. By Lemma 3.3, g and h are polynomial functions. Since F is infinite, each one of g and h is induced by a unique polynomial over F , namely P g and P h , respectively. Thus, P = P g + P h . By Fact 3.2, exactly n -p variables occur in P g , and by Lemma 3.4, P h is a nonzero multiple of ∆(x 1 , . . . , x n ).

For sufficiency, assume that P = Q + R, where Q and R are as in the statement of the theorem. Then ess Q = n -p by Fact 3.2, and R ≡ 0 and R| F n = ≡ 0 by Lemma 3.4. From Theorem 2.7 it follows that qa P = n -p, and then Theorem 2.6 implies that gap P = p.

The uniqueness of the decomposition P = Q + R follows from Theorem 2.7 and from the fact that polynomials and polynomial functions over infinite fields are in one-to-one correspondence.

Let us note that in the proof of the above theorem we did not really make use of the fact that the function P is polynomial; we only used the basic properties of the derivative. Therefore the theorem remains valid for differentiable real functions.

Theorem 5.6. Let f : R n → R be a differentiable function of arity at least 2. Then gap f = p ≥ 2 if and only if there exist differentiable functions g, h : R n → R such that f = g + h, h| R n = ≡ 0, h ≡ 0, and ess g = n -p. Otherwise gap f = 1. Moreover, the decomposition f = g + h is unique.

Some remarks on polynomial functions over infinite fields of odd characteristic

As the following example illustrates, Proposition 4.5 and Lemma 5.2 do not extend to infinite fields of odd characteristic. Example 6.1. Let F be an arbitrary field of characteristic 3, and let f : F 3 → F be the polynomial function induced by [START_REF] Couceiro | Additive decomposability of functions over abelian groups[END_REF] 2x 3 + 2y 3 + 2z 3 + yz 2 -xy 2 -xz 2 + y 2 z + 2xyz.

It is straightforward to verify that f (x, x, y) = f (x, y, x) = f (y, x, x) = 2y 3 .

Hence f | F 3 = is determined by oddsupp but f | F 3 = is not constant. This shows that Lemma 5.2 does not hold if F has characteristic 3.

Next we show that Proposition 4.5 does not hold for infinite fields of characteristic 3. Assume now that F is infinite, and let f be induced by [START_REF] Couceiro | Additive decomposability of functions over abelian groups[END_REF]. Suppose that g : F 3 → F is a polynomial function determined by oddsupp induced by the canonical polynomial Taking into account the total symmetry of g (condition (A)) and the fact that the characteristic of F is not 2, the only solution to this system of equations is c (k1,k2,k3) = 0 for all (k 1 , k 2 , k 3 ) ∈ N 3 such that k 1 + k 2 + k 3 = 3. Thus, the canonical polynomial of g(x, x, x) does not contain any cubic term; therefore it cannot coincide with f (x, x, x) = 2x 3 , and we conclude that f | F 3 = = g| F 3 = .

Fact 3 . 1 .

 31 Every function f : F n → F on a finite field F is a polynomial function over F .

( 1 Fd 2 Fc 1 F

 121 b1,b3,...,bn)∈N n-(b1,b3,...,bn) x b1 1 x b3 3 • • • x bn n , where d (b1,b3,...,bn) = (a1,a2)∈N a1⊕a2=b1 (a1,a2,b3,...,bn) . By Fact 3.2, the condition that f 2←1 does not depend on x 1 is equivalent to the condition that d (b1,b3,...,bn) = 0 for all (b 1 , b 3 , . . . , b n ) ∈ N n-such that b 1 = 0.

d 2 F 2 F

 22 (b1,b3,...,bn) = (a1,a2)∈N a1⊕ F a2=b1 c (a1,a2,b3,...,bn) = a1∈N F a1⊕ F a1=b1 c (a1,a1,b3,...,bn) (I) + (a1,a2)∈N a1<a2, a1⊕ F a2=b1 (c (a1,a2,b3,...,bn) + c (a2,a1,b3,...,bn) ) (II)

3 .

 3 It follows from Lemma 3.4 that a function f : A n → B satisfies the condition of Lemma 5.2, i.e., f | F n = is constant, if and only if f is induced by a polynomial of the form P • ∆ n + c, where P ∈ F [x 1 , . . . , x n ] and c ∈ F . Lemma 5.4. Let F be a field of characteristic 0 and let f : F 3 → F be a polynomial function. If gap f = 2, then qa f = 1.

(x k2 2 x k3 3 .

 3 k1,k2,k3)∈N 3 c (k1,k2,k3) x k11Condition (B) of Proposition 4.3 yields the following equalities:c (3,0,0) + c (2,1,0) + c (1,2,0) + c (0,3,0) = 0, c (2,0,1) + c (1,1,1) + c (0,2,1) = 0, c(1,0,2) + c (0,1,2) = 0.

then f is determined by oddsupp. The following fact is easy to verify. Fact 2.5. 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 . Similarly, f | A n = is determined by oddsupp if and only if f | A n

	{n, n -2, n -4, . . . } ,
	is relevant in determining the values of f in (1). Moreover, the functions f : A n → B
	determined by oddsupp are in one-to-one correspondence with the functions f * : P n (A) →
	B.
	Willard showed in [10] that if f : A n → B, where A is finite, ess f = n > max(|A|, 3) and
	gap f ≥ 2,

  3, Lemma 3.4, Proposition 4.3, and Proposition 4.5, and observe that if f | F n = is determined by oddsupp then qa f = n if and only if f | F n

Acknowledgments

The authors are grateful to Ágnes Szendrei for her valuable comments on an early version of this manuscript.

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

The present project is supported by the European Union and co-funded by the European Social Fund under the project "Telemedicine-focused research activities on the field of Mathematics, Informatics and Medical sciences" of project number "T ÁMOP-4.2.2.A-11/1/KONV-2012-0073". This work was developed within the FCT Project PEst-OE/MAT/UI0143/2014 of CAUL, FCUL.