Miguel Couceiro

Erkko Lehtonen

Tam Ás Waldhauser

A SURVEY ON THE ARITY GAP

Keywords: functions of several variables, essential variable, arity gap, quasi-arity. gal

The arity gap of a function of several variables is defined as the minimum decrease in the number of essential variables when essential variables of the function are identified. We present a brief survey on the research done on the arity gap, from the first studies of this notion up to recent developments, and discuss some natural extensions and related problems.

Introduction

Let A and B be arbitrary nonempty sets. A function of several variables from A to B is a map f : A n → B for some integer n ≥ 1 called the arity of f . If A = B, then we speak of operations on A. Operations on the two-element set {0, 1} are called Boolean functions. 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 of f :

A n → B (1 ≤ i ≤ n) is essential, if there exist n-tuples (1)
(a 1 , . . . , a i-1 , a i , a i+1 , . . . , a n ), (a 1 , . . . , a i-1 , a ′ i , a i+1 , . . . , a n ) ∈ A n that only differ in the i-th position, 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 ).

We refer to the pair of n-tuples in (1) as a witness of essentiality of the i-th variable.

If the i-th variable of f is not essential, then we say that it is inessential. The number of essential variables of f is called the essential arity of f and it is denoted by ess f . If ess f = m, then we say that f is essentially m-ary.

For i, j ∈ {1, . . . , n}, i = j, the function f i←j : A n → B 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 a variable identification minor of f , obtained by identifying the i-th variable with the j-th variable. Note that the i-th variable of f i←j is necessarily inessential. Let f : A n → B be a function with at least two essential variables. The arity gap of f is the quantity gap f := min i =j (ess f -ess f i←j ), where i and j range over the set of indices of essential variables of f . Note that, by definition, 1 ≤ gap f ≤ ess f . We say that f and g are equivalent if each one can be obtained from the other by permutation of variables and addition or deletion of inessential variables. Whenever we consider the arity gap of a function, we can assume that all of its variables are essential. This is not a significant restriction, because every nonconstant function is equivalent to a function with no inessential variables, and equivalent functions have the same arity gap.

Example 1. Let F be an arbitrary field. Consider the polynomial function f : F 3 → F induced by x 1 x 3 -x 2 x 3 . It is clear that all variables of f are essential, i.e., ess f = 3. Let us consider the various variable identification minors of f :

f 1←2 = 0, f 2←1 = 0, f 1←3 = x 2 3 -x 2 x 3 , f 3←1 = x 2 1 -x 1 x 2 , f 2←3 = x 1 x 3 -x 2 3 , f 3←2 = x 1 x 2 -x 2 2 .
We have that ess f 1←2 = ess f 2←1 = 0, ess f 1←3 = ess f 3←1 = ess f 2←3 = ess f 3←2 = 2.

Hence gap f = 1.

Example 2. Let f : {0, 1} n → {0, 1} be the Boolean function induced by the polynomial x 1 + x 2 + • • • + x n over the two-element field. Then for each i = j we have that f i←j is induced by the polynomial ℓ∈{1,...,n}\{i,j} x ℓ .

Thus ess f = n and ess f i←j = n -2 for all i = j; hence gap f = 2.

Example 3. Let A be a finite set with k ≥ 2 elements, say, A = {0, 1, . . . , k -1}. Let f : A n → A, 2 ≤ n ≤ k, be given by the rule f (a 1 , . . . , a n ) := 1 if (a 1 , . . . , a n ) = (0, 1, . . . , n -1), 0 otherwise.

It is easy to see that all variables of f are essential, and for all i = j, the function f i←j is identically 0. Hence gap f = n.

As shown by the examples above, every positive integer is the arity gap of some function of several variables. Are all positive integers possible as the arity gaps of functions of several variables from A to B for a fixed domain A and codomain B? Does the size of the domain or the codomain have any influence on the set of possible arity gaps? Or even, could one hope to classify functions according to their arity gap? These questions have been raised and studied by several authors. In this paper, we survey the research work done on this topic over the years. In the bibliography, we indicate literature relevant to the topics of essential variables (see [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] Lupanov | On a class of schemes of functional elements[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]), variable identification minors and variants (see [START_REF] Bouaziz | Join-irreducible Boolean functions[END_REF][START_REF] Couceiro | On the lattice of equational classes of Boolean functions and its closed intervals[END_REF][START_REF] Couceiro | On a quasi-ordering on Boolean functions[END_REF][START_REF] Ekin | Equational characterizations of Boolean function classes[END_REF][START_REF] Feigelson | The forbidden projections of unate 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]) and arity gap and its variants (see [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 | On the arity gap of polynomial functions[END_REF][START_REF] Couceiro | Parametrized arity gap[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]).

This survey is organized as follows. We start in Section 2 with basic notions and classifications of special types of functions (namely, Boolean and pseudo-Boolean functions) according to their arity gap; we also give a general description of arity gap, which serves as a basis for the later sections. Section 3 reports on natural decomposition schemes which arise from arity gap and which are then used in Section 4 to enumerate functions with prescribed arity and arity gap. In Section 5, we make the description of arity gap more explicit for some special classes of functions (namely, order-preserving functions and polynomial functions over fields). Then, in Section 6, we briefly discuss the order which naturally arises from variable identification (namely, simple minor relation) and some parametrized variants of the arity gap. We conclude this survey by mentioning some open problems and proposing new directions for future research in Section 7.

From the beginnings to a complete classification

To the best of our knowledge, the first study of arity gap appeared in print in the 1963 paper by Salomaa [START_REF] Salomaa | On essential variables of functions, especially in the algebra of logic[END_REF]. In that paper, 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. Concerning identification of variables, his main result was the following.

Theorem 1 (Salomaa [START_REF] Salomaa | On essential variables of functions, especially in the algebra of logic[END_REF]). Let f : {0, 1} n → {0, 1} be a Boolean function with at least two essential variables. Then gap f ≤ 2.

As illustrated by Example 2, this upper bound is attained. On the other hand, Example 1 provides a Boolean function of arity gap 1. Since the arity gap is always at least 1, there are no other possible values for the arity gap of Boolean functions. This calls for a complete classification of Boolean functions into those with arity gap 1 and those with arity gap 2. Such a strengthening of Salomaa's result was obtained in [START_REF] Couceiro | On the effect of variable identification on the essential arity of functions on finite sets[END_REF].

Theorem 2 ([6]). 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 functions:

(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.
The number of n-ary Boolean functions f with ess f = n and gap f = 2 can be straightforwardly read off from the list of functions given in Theorem 2. Since the number of functions f :

A n → B (|A| = k, |B| = ℓ) with ess f = m (0 ≤ m ≤ n) is (2) n m m i=0 (-1) i m i ℓ k m-i
(see Wernick [START_REF] Wernick | An enumeration of logical functions[END_REF]), the number of n-ary Boolean functions with ess f = n and gap f = 1 can be easily obtained. Theorem 2 was later reproved using different techniques by Shtrakov in [START_REF] Shtrakov | Essential arity gap of Boolean functions[END_REF], where he also addressed the problem of counting the number of Boolean functions with a given arity gap.

We call functions of several variables from {0, 1} to an arbitrary nonempty set B pseudo-Boolean functions. Theorem 2 was extended for pseudo-Boolean functions in [START_REF] Couceiro | Generalizations of Świerczkowski's lemma and the arity gap of finite functions[END_REF].

Theorem 3 ([7]

). Let f : {0, 1} n → B (n ≥ 2) be a pseudo-Boolean function all of whose variables are essential. Then gap f = 2 if and only if f satisfies one of the following conditions:

(1) n = 2 and f is a nonconstant function satisfying f (0, 0) = f (1, 1), (2) f = g • h, where g : {0, 1} → B is injective and h : {0, 1} n → {0, 1} is a Boolean function with gap h = 2, as given by Theorem 2.

Otherwise gap f = 1.

A partial function of several variables from A to B is a map f : S → B where S ⊆ A n for some integer n ≥ 1, called the arity of f . If S = A n , we speak of total functions. Essential variables are defined for partial functions in the same way as for total functions, but the n-tuples of (1) forming a witness of essentiality are required to be in S. In this way, the notions of essential arity and arity gap can be naturally extended to partial functions.

The following notions were introduced by Berman and Kisielewicz [START_REF] Berman | On the number of operations in a clone[END_REF]. 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 ∈ {1, . . . , 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

f = f * • oddsupp| S .
Willard showed that if f : A n → B, where A is finite, ess f = n > max(|A|, 3) and gap f ≥ 2, then f is determined by oddsupp. It is easy to verify that if f is determined by oddsupp and ess f ≥ 2, then gap f = 2.

Theorem 4 (Willard [START_REF] Willard | Essential arities of term operations in finite algebras[END_REF]). Let A and B be finite nonempty sets, and let k := |A|. Suppose that f : A n → B depends on all of its variables. If n > k, then gap f ≤ 2. Moreover, if n > max(k, 3), then gap f = 2 if and only if f is determined by oddsupp. This theorem deals only with functions over finite domains with sufficiently large essential arities; if A and B are finite, then gap f ≤ 2 for almost all functions. The condition on essential arity was removed in [START_REF] Couceiro | Generalizations of Świerczkowski's lemma and the arity gap of finite functions[END_REF], where a full classification of finite functions according to their arity gap was given in terms of so-called quasi-arity. As pointed out in [START_REF] Couceiro | Decompositions of functions based on arity gap[END_REF], this classification theorem holds more generally -with no change needed in its proof -for functions with arbitrary domains. Thus, the study of arity gap culminated in Theorem 5, which will be presented below, after introducing some terminology.

For n ≥ 2, let

A n = := {(a 1 , . . . , a n ) ∈ A n : a i = a j for some i = j}. 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 all supports of f . If qa f = m, then we say that f is quasi-m-ary. Note that if A is finite, then A n = = A n whenever n > |A|. Hence qa f = ess f whenever n > |A|. Moreover, qa f = ess f | A n = whenever n = 2. Theorem 5 ([7, 9]). 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.

(1) For 3 ≤ p ≤ n, gap f = p if and only if qa f = n -p.

(2)

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. (3) 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 ).
(4) Otherwise gap f = 1.

Theorem 5 gives answers to the questions posed at the end of Section 1. The set of possible arity gaps of functions of several variables from A to B is {n ∈ N \ {0} : n ≤ |A|}. This does not depend on the cardinality of the codomain B, as long as |B| ≥ 2 (otherwise, all functions are constant and hence have no essential variables).

Decompositions of functions based on the arity gap

Theorem 5 provides a complete classification of functions according to their arity gap. Unfortunately, it is not as explicit as Theorems 2 and 3 that deal with Boolean and pseudo-Boolean functions. The main reason for this is the fact that no special structure was assumed on the sets A and B. By assuming that the codomain B has a group structure, more explicit descriptions can be obtained. In this direction, two cases are distinguished.

First, functions f : A n → B with arity gap p ≥ 3 are shown to be decomposable into a sum of a quasi-nullary function and an essentially (n -p)-ary function.

Theorem 6 ([9]

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

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

(2) There exist functions g, h :

A n → B such that f = h + g, h| A n = ≡ 0, h ≡ 0, and ess g = n -p.
The decomposition f = h + g given above is unique.

Similar decompositions were presented by Shtrakov and Koppitz [START_REF] Shtrakov | On finite functions with non-trivial arity gap[END_REF], without proving uniqueness.

Second, we deal with functions with arity gap 2. In this case we need to further assume that B is a Boolean group (i.e., a group satisfying x + x = 0 for all x ∈ B). We also need to introduce some notation. Let ϕ : A n-2 → B be a function that is determined by oddsupp, i.e., ϕ = ϕ * • oddsupp | A n-2 , for some function ϕ * : P(A) → B. Let ϕ be the n-ary function defined by

(3) ϕ(x 1 , . . . , x n ) := k<n 2|n-k 1≤i1<•••<i k ≤n ϕ * (oddsupp(x i1 , . . . , x i k )).
Observe that each summand is a variable identification minor of ϕ, namely

ϕ * (oddsupp(x i1 , . . . , x i k )) = ϕ(x i1 , . . . , x i k , y, . . . , y),
where the number of y's is n -2 -k, which is an even number; therefore y is indeed an inessential variable of the function on the right-hand side; moreover, the order of the variables is irrelevant. The function ϕ is obviously totally symmetric, and it can be shown that ϕ| A n = is determined by oddsupp; from these facts it follows that ϕ is determined by oddsupp as well (see [START_REF] Couceiro | Decompositions of functions based on arity gap[END_REF] for details).

Theorem 7 ([9]

). Assume that (B; +) is a Boolean group with neutral element 0. Let f : A n → B, n ≥ 4. Then the following two conditions are equivalent:

(1) ess f = n and gap f = 2.

(2) There exist functions g, h : A n → B such that f = h + g, h| A n = ≡ 0, and either (a) ess g = n -2 and h ≡ 0, or (b) g = ϕ for some nonconstant (n -2)-ary function ϕ that is determined by oddsupp.

The decomposition f = h + g given above is unique.

Theorem 2 shows that for all but finitely many Boolean functions, gap f = 2 implies that f is a sum of unary functions. The following theorem provides an analogous result for functions f : A n → B, where A is a finite set and B is a Boolean group.

Theorem 8 ([12]

). Let A be a finite set, B a Boolean group, and let f : A n → B be a function such that ess f > max(|A|, 3). Then gap f ≤ 2, and if gap f = 2, then f is a sum of functions of essential arity at most |A| -1.

Let f be a polynomial function over GF(q), the q-element finite field, with ess f = n > max(q, 3) and gap f = 2. By the above theorem, if q is even, then f is a sum of functions of arity at most q -1. Since finite fields are functionally complete, we can represent each summand by a polynomial. This implies that f is a sum of monomials, where each monomial involves at most q -1 variables. If q = 2, then we can conclude that every Boolean function f with ess f ≥ 4 and gap f = 2 is linear, in accordance with Theorem 2.

The next example shows that Theorem 7 and Theorem 8 do not hold for arbitrary groups B.

Example 4 ([11]

). Let q be an odd prime power, and let f be the following polynomial function over GF(q):

f (x 1 , . . . , x n ) = n i=1 x q-1 i - 1 2 ,
Here 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 this together with the symmetry of f shows that f is determined by oddsupp, hence gap f = 2.

If f were a sum of at most (n -1)-ary functions, then every monomial of f would involve at most n -1 variables. However, this is clearly not the case, as the expansion of f involves the monomial x q-1 1

• • • x q-1
n , which will not be cancelled by any other monomial. Thus f cannot be expressed as a sum of functions of arity smaller than the arity of f . If n > q, then the only support of f is itself, thus a support g satisfying condition 2a) or 2b) of Theorem 7 cannot exist. Theorem 8 and Example 4 ask for a characterization of those groups B for which Theorem 8 still holds. This question was partially answered in [START_REF] Couceiro | Additive decomposability of functions over abelian groups[END_REF], where abelian groups B were classified according to whether every function f : A n → B with gap f = 2 can be decomposed into a sum of functions with a smaller number of essential variables. This result followed from a study of a hierarchy of function classes based on decomposability, which we now describe.

Let (B; +) be an abelian group with neutral element 0. Recall that the order of a group element b ∈ B is the smallest positive integer n such that b

+ • • • + b n times = 0. If such a number
does not exist, the order of b is ∞. If the orders of the elements of B have a finite common upper bound, then the exponent of B is defined as the least upper bound (or, equivalently, the least common multiple) of the orders of its members; otherwise the exponent of B is ∞. For example, the exponent of a Boolean group is 2.

A function f :

A n → B is said to be k-decomposable, if it has an additive decomposition f = f 1 + • • • + f s , where each f i : A n → B (1 ≤ i ≤ s) has essential arity at most k. If f is (n -1)
-decomposable, we simply say that it is decomposable.

The following result provides a characterization of k-decomposable functions. For I ⊆ [n] and a = (a 1 , . . . , a n ) ∈ A n , let x a I denote the n-tuple which is obtained from x = (x 1 , . . . , x n ) ∈ A n by replacing its i-th component by a i , for each i ∈ I.

Proposition 1 ([12]). Let (B; +) be an abelian group, and let c ∈

A. A function f : A n → B is k-decomposable if and only if for all a ∈ A n and I ⊆ [n] with |I| > k, we have J⊆I (-1) |I\J| f (c a J ) = 0,
where c := (c, . . . , c).

Proposition 1 gave rise to the following result which reveals a dichotomy of abelian groups with respect the decomposability of functions determined by oddsupp.

Theorem 9 ([12]

). Let A be an arbitrary set with at least two elements, and let B be an abelian group. Then every function f : A n → B that is determined by oddsupp is decomposable if and only if A is finite and the exponent of B is a power of 2. Moreover, if A is finite and the exponent of B is 2 e , then every function determined by oddsupp is (|A| + e -2)-decomposable.

The following example shows that the bound (|A| + e -2) in Theorem 9 cannot be improved.

Example 5. Let A = {0, 1, . . . , k-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 ≥ k + e -2
, and let f : A n → B be given by f (x) = ϕ(oddsupp(x)). Theorem 9 asserts that f is (k +e-2)-decomposable; however, it can be shown that f is not (k +e-3)decomposable (see [START_REF] Couceiro | Additive decomposability of functions over abelian groups[END_REF]).

The number of functions with a given arity gap

The unique decompositions provided by Theorems 6 and 7 enable us to actually count the number of functions f : A n → B with ess f = n ≥ 2 and gap f = p for every 1 ≤ p ≤ n. The problem of determining these numbers for operations on finite sets was raised by Shtrakov and Koppitz in [START_REF] Shtrakov | On finite functions with non-trivial arity gap[END_REF], where upper bounds were provided. An answer to the counting problem with exact numbers was given in [START_REF] Couceiro | Decompositions of functions based on arity gap[END_REF].

Let A and B be finite sets with |A| = k, |B| = ℓ. Let us denote by G kℓ np the number of functions f : A n → B with ess f = n and gap f = p. It is well known (see Wernick [START_REF] Wernick | An enumeration of logical functions[END_REF]) that the number of functions g : A n → B that depend on exactly r variables (0 ≤ r ≤ n) is

U kℓ nr := n r r i=0 (-1) i r i ℓ k r-i . Let (m) i denote the falling factorial (m) i := m(m -1) • • • (m -(i -1)
). The number of functions h :

A n → B such that h| A n = ≡ 0, h ≡ 0 is then given by V kℓ n := ℓ (k)n -1.
Let us denote by O kℓ n the number of functions f :

A n → B such that ess f = n, qa f = n and f | A n
= is determined by oddsupp. It can be shown (see [START_REF] Couceiro | Decompositions of functions based on arity gap[END_REF]) that for k ≥ 2, ℓ ≥ 2, n ≥ 2,

O kℓ n = ℓ 2 k-1 -ℓ, if n > k, ℓ (k)n (ℓ S k n -ℓ), if n ≤ k,
where

S k n = n 2 -1 i=0 k 2i , if n is even, n-1 2 -1 i=0 k 2i+1 , if n is odd.
G kℓ n2 = O kℓ n = ℓ 2 k-1 -ℓ, G kℓ n1 = U kℓ nn -G kℓ n2 .
(

) If 3 ≤ n ≤ k and 3 ≤ p ≤ n, then G kℓ np = U kℓ n(n-p) V kℓ n . (4) If 4 ≤ n ≤ k, then G kℓ n2 = U kℓ n(n-2) V kℓ n + O kℓ n , G kℓ n1 = U kℓ n(n-1) V kℓ n + U kℓ nn ℓ (k)n -V kℓ n ℓ k n -O kℓ n (5) G kℓ 32 = (8ℓ (k)3 -3)(ℓ k -ℓ), G kℓ 31 = U kℓ 33 -G kℓ 33 -G kℓ 32 . (6) G kℓ 22 = ℓ (k)2+1 -ℓ, G kℓ 21 = U kℓ 22 -G kℓ 22 . 3

Special classes of functions

Theorems 5, 6 and 7 lack the explicitness that is enjoyed by Theorems 2 and 3 in the sense that in the former ones the arity gap of each function is described in terms of the essential arity of some related function. However, for some special classes of functions, our results become explicit. Examples include pseudo-Boolean functions (see Theorem 3), Lovász extensions (in particular, the so-called Choquet integrals), multilinear polynomial functions and lattice polynomial functions (in particular, the so-called Sugeno integrals). In this section we extend these results to other classes of functions, namely of order-preserving functions (Subsection 5.1) and of polynomial functions over fields (Subsection 5.2), and provide rather explicit descriptions of arity gap within these classes.

5.1. Order-preserving functions. Let (A; ≤ A ) and (B; ≤ B ) be partially ordered sets. A function f : A n → B is said to be order-preserving (with respect to the partial orders ≤ A and ≤ B ) if for all a, b ∈ A n , f (a) ≤ B f (b) whenever a ≤ A b, where a ≤ A b denotes the componentwise ordering of tuples, i.e., a ≤ A b if and only if a i ≤ A b i for all i ∈ {1, . . . , n}. We say that (A; ≤ A ) is bidirected if every pair of elements of A has both an upper bound and a lower bound.

Theorem 11 ([10]). Let (A; ≤ A ) be a bidirected poset, let (B; ≤ B ) be any poset, and let f : A n → B (n ≥ 2) be an order-preserving function such that ess f = n. Then gap f = 2 if and only if n = 3 and there is a nonconstant order-preserving unary function h :

A → B such that f (x 1 , x 0 , x 0 ) = f (x 0 , x 1 , x 0 ) = f (x 0 , x 0 , x 1 ) = h(x 0 ).
Otherwise, gap f = 1.

By imposing stronger assumptions on the underlying posets, we obtain more stringent descriptions of order-preserving functions with arity gap 2. For example, if (A; ≤ A ) and (B; ≤ B ) are lattices and the function h occurring in Theorem 11 is a lattice homomorphism whose image is a distributive sublattice of B, then it can be shown that

f = med h(x 1 ), h(x 2 ), h(x 3 ) ,
where med denotes the ternary median function on Im h, given by med(a, b, c

) := (a ∧ b) ∨ (a ∧ c) ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) ∧ (b ∨ c).
From this observation and Theorem 11, we obtain the following explicit classification of order-preserving functions defined on chains.

Corollary 1 ([10]

). Let (A; ≤ A ) be a chain and let (B; ≤ B ) be any lattice. Let f : A n → B be an order-preserving function. Then gap f = 2 if and only if n = 3 and f = med h(x 1 ), h(x 2 ), h(x 3 ) for some nonconstant order-preserving unary function h : A → B (here med denotes the median function on Im h). Otherwise gap f = 1.

Polynomial functions over fields.

As in the case of order-preserving functions, Theorem 5 can be refined for polynomial functions over fields. We summarize in this section the results obtained in [START_REF] Couceiro | On the arity gap of polynomial functions[END_REF] in this direction.

Polynomials over infinite fields are in one-to-one correspondence with polynomial functions. It is well known that every function over a finite field is a polynomial function, but the correspondence between polynomials and functions is not injective. This correspondence can be made bijective by assuming that, for a finite field GF(q), we only consider polynomials in which the exponent of each variable in every monomial is at most q -1; we call such polynomials canonical. Every polynomial over an infinite field is canonical.

Given a polynomial function f : F n → F , we denote by P f the unique canonical polynomial which induces f , and 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 ].

Lemma 1 ([11]

). If f is a polynomial function over a field F , then the functions g and h in the decomposition f = h + g given in Theorem 6 are also polynomial functions.

Lemma 2 ([11]). If h is an n-ary polynomial function over a field 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 ].
With an application of the two lemmas above, Theorem 6 about functions with arity gap at least 3 particularizes for polynomial functions as follows.

Theorem 12 ([11]). Let F be a field and let f : F n → F be a polynomial function of arity at least 4. 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 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 multiple of ∆ n such that Q ′ is not identically 0, then P ′ = P and Q ′ = Q.

Theorem 12 only deals with polynomial functions with arity gap at least 3, which thus asks for the study of the polynomial functions with arity gap at most 2. In particular, we consider polynomial functions determined by oddsupp, and we will see that the characteristic of the underlying field plays a crucial role here. We first introduce some notation that will be needed to state the subsequent results. Let F be an arbitrary field.

• If F is infinite, then N F denotes the set of nonnegative 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}, 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).

Proposition 2 ([11]

). Let F be a 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 exists 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. In order to obtain more explicit descriptions of polynomial functions determined by oddsupp, we need to take into account the characteristic of the underlying field. We start with finite fields and fields of characteristic 2.

Proposition 3 ([11]

). 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 . Theorem 13 ([11]). 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

(1) exactly n -p variables occur in P and Q = 0, or (2) P is not a constant polynomial and P satisfies conditions (A) and (B 2 ) of Proposition 2. Otherwise gap f = 1.

Corollary 2 ([11]

). 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 functions of essential arity at most q -1.

We now consider the case of fields of characteristic 0.

Lemma 3 ([11]

). Let F be a field of characteristic 0, let n ≥ 2, and let f :

F n → F be a polynomial function. If f | F n = is determined by oddsupp, then f | F n = is constant, i.e., qa f = 0.
Theorem 14 ([11]). Let F be a field of characteristic 0, let n ≥ 2, 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, when it exists, is unique.

As the following example illustrates, Proposition 3 and Lemma 3 do not extend to (infinite) fields of odd characteristic. Example 6. Let F be an arbitrary field of characteristic 3, and let f : F 3 → F be the polynomial function induced by ( 4)

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 3 does not hold if F has characteristic 3.
Next we show that Proposition 3 does not hold for infinite fields of characteristic 3. Assume now that F is infinite, and let f be induced by [START_REF] Čimev | Separable Sets of Arguments of Functions[END_REF]. that g : F 3 → F is a polynomial function determined by oddsupp induced by the canonical polynomial

(k1,k2,k3)∈N 3 c (k1,k2,k3) x k1 1 x k2 2 x k3 3 .
Condition (B) of Proposition 2 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.
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 = .

Further directions

In this section, we briefly discuss two further research directions: the study of an order which naturally arises from variable identification (Subsection 6.1) and the consideration of extensions to the notion of arity gap (Subsection 6.2).

6.1. The simple minor order and its respective covering relation. Let f : A m → B and g : A n → B. We say that f is a simple minor of g and we write f ≤ g, if there exists a function σ : {1, . . . , n} → {1, . . . , m} such that f (a 1 , . . . , a m ) = g(a σ(1) , . . . , a σ(n) ), for all a 1 , . . . , a m ∈ A. Loosely speaking, f is a simple minor of g, if f can be obtained from g by permutation of variables, identification of variables, and addition and deletion of inessential variables.

The simple minor relation ≤ on F AB is both reflexive and transitive, and thus it constitutes a quasiordering of F AB . As for quasiorders, ≤ induces an equivalence relation ≡ on F AB : for f, g ∈ F AB , we set f ≡ g if f ≤ g and g ≤ f , and in this case we say that f and g are equivalent. As observed in the introduction, 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. Note that ess f = ess g whenever f ≡ g, and that every nonconstant function is equivalent to a function that depends on all of its variables.

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

Remark 1. These and other observations were made for the case A = B = {0, 1} in the paper [START_REF] Couceiro | On a quasi-ordering on Boolean functions[END_REF], in which it was shown that the poset of equivalence classes of functions induced by simple minor order is equimorphic (i.e., equivalent w.r.t. embeddings) to the poset made of finite subsets of positive integers ordered by inclusion. This result was later extended in various ways in [START_REF] Lehtonen | Partial orders induced by quasilinear clones, Contributions to General Algebra[END_REF], in particular to arbitrary sets A and B.

We say that g is a strict minor of f , denoted by g < f , if g ≤ f but f ≡ g. 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 we denote this fact by g ≺ f . Remark 2. It was shown in [START_REF] Bouaziz | Join-irreducible Boolean functions[END_REF] that the lower covers of any function f : A n → B have the same essential arity when A = B = {0, 1}. The proof of this fact given in [START_REF] Bouaziz | Join-irreducible Boolean functions[END_REF] actually shows that this claim is true whenever |A| = 2 and |B| ≥ 2. However, as the following example shows, this is not the case when |A| > 2.

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

q 1 = 1≤i<j≤4 (x i -x j ) • 1≤i≤4 (x i -x 5 ) 2 , q 2 = (x 1 -x 2 ) • (x 3 -x 4 ), q 3 = (x 1 -x 2 ) • (x 1 -x 3 ), q 4 = (x 1 -x 2 ) • (x 2 -x 3 ), q 5 = (x 1 -x 2 ) 2 , q 6 = -(x 1 -x 2 ) 2 .
Remark 3. Even though not every identification minor f i←j is a lower cover of f , every lower cover of f is of the form f i←j . Therefore, we can alternatively define the arity gap of f as gap f := min g≺f (ess f -ess g).

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 either on all of its variables or on none of them.

Fact 1. If f : A n → B is totally symmetric, then for all i, j, i ′ , j ′ ∈ [n] (i = j, i ′ = j ′ ), f i←j ≡ f i ′ ←j ′ . Therefore, if f is nonconstant, then for all distinct i, j ∈ [n],
f i←j is, up to equivalence, the unique lower cover of f . Berman and Kisielewicz [START_REF] Berman | On the number of operations in a clone[END_REF] also introduced the following analogue of oddsupp. Let supp : n≥1 A n → P(A) be the mapping defined by supp(a 1 , . . . , a n ) := {a 1 , . . . , a n }.

A function f : A n → B is determined by supp, if there exists a function ϕ :

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

In [START_REF] Couceiro | Parametrized arity gap[END_REF] it was observed that there exist functions that are determined both by supp and oddsupp. For instance, every constant function and every unary function is determined by both supp and oddsupp. In fact, for each 2 ≤ n ≤ |A| we can construct functions f : A n → B determined by both supp and oddsupp; see [START_REF] Couceiro | Parametrized arity gap[END_REF]. However, such nontrivial examples cannot be found when n > |A|.

Proposition 4 ([13]

). If n > |A|, then f : A n → B is determined by both supp and oddsupp if and only if f is a constant function. Now it is natural to ask how the properties of being determined by supp and oddsupp are affected when taking strict minors. The answer is given by the following result.

Proposition 5 ([13]). Let A and B be finite nonempty sets, let k := |A|, and let f : A n → B be a nonconstant function.

(1) If f is determined by oddsupp, then the simple minors of f form a chain

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; in this case, 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 .
(2) If f is determined by supp, then the simple minors of f form a chain

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

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 corollary is an immediate consequence of Proposition 5.

Corollary 3.

Let A and B be finite nonempty sets, let k := |A|, and let f : A n → B be a nonconstant function.

(1) If f is determined by oddsupp with n > k, then gap f = 2.

(2) If f is determined by supp with n > k, then gap f = 1.

We now recall a noteworthy result about the arity gap.

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

( From Proposition 5, Theorem 4 and Lemma 4, we can obtain the following theorem whose importance is made apparent in the next subsection.

) 1
Theorem 15 ([13]). 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.

6.2. Parametrized variants of arity gap. So far we have considered the effect that the identification of two essential variables has on the essential arity of functions. Indeed, the arity gap of a function measures the minimum decrease in the essential arity when two essential variables are identified. We shall now discuss the minimum decrease in the essential arity when we identify an arbitrarily large number of essential variables. There are two ways of formalizing such a measure: by sequentially identifying pairs of variables or by simultaneously identifying "blocks" of variables. Despite being related, as we will see these two approaches are rather different.

6.2.1. Sequential identification. One approach to formalizing the minimum decrease in the essential arity when several essential variables are identified is to consider 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 quasiorder:

(5) gap(f, ℓ) := min

g∈↓ ℓ f (ess f -ess g),
where

↓ ℓ 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 . In fact, it is not difficult to verify that: [START_REF] Couceiro | On the effect of variable identification on the essential arity of functions on finite sets[END_REF] gap(f, ℓ) = min g≺f (ess f -ess g + gap(g, ℓ -1)).

Thus for every function f , we have gap(f, 1) = gap f and gap(f, 0) = 0.

Remark 4. We saw in the previous subsection 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. 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 have also observed in Remark 3 that not every identification minor f i←j is a lower cover of f and, by the alternative definition of arity gap, if f i←j is not a lower cover of f , then gap f < ess f -ess f i←j . Moreover, as observed in Remark 2 it can be the case that f has two lower covers f 1 and f 2 such that ess f 1 < ess f 2 , and again we would conclude that gap f < ess f -ess f 1 . Hence, one might be led to thinking that in order to compute gap(f, ℓ) it suffices to choose at each recursion step an identification which results in the minimum loss of essential variables. However, this is not true.

Example 8. Consider function f in Example 7. If we 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 [START_REF] Couceiro | On the lattice of equational classes of Boolean functions and its closed intervals[END_REF], the minimum value is attained at the lower cover q 1 , whereas, for 2 ≤ ℓ ≤ 4, we need to pass through q 2 for computing gap(f, ℓ). Hence, gap(f, 0) = 0, gap(f, 1) = 1, gap(f, 2) = 3, gap(f, 3) = 4, and gap(f, 4) = 6.

The following result can be obtained inductively by making use of equation ( 6) and Theorem 15. Essentially, it asserts that, if ℓ is not too large, then we can walk from f down ℓ steps in the simple minor quasiorder in such a way that in each step we lose only one essential variable (resp. only two essential variables) if gap f = 1 (resp. gap f = 2).

Theorem 16 ([13]). Let A and B be finite nonempty sets, and let k := |A|. Let f : A n → B, ess f = n.

(

) If gap f = 1 and 1 ≤ ℓ ≤ n -max(k, 3), then gap(f, ℓ) = ℓ. (2) If gap f = 2 and 1 ≤ ℓ ≤ n-k 2 , then gap(f, ℓ) = 2ℓ. 1
Surprisingly, it turns out 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. This statement is made precise in the following theorem.

Theorem 17 ([13]). 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.
This parametrized version of 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? Denoting this smallest number by pag(f, p), we can easily see that pag(f, p) is the smallest ℓ for which gap(f, ℓ) ≥ p. 6.2.2. Block identification. Instead of taking successive identifications of pairs of variables, another approach to measuring the minimum decrease in the essential arity when several essential variables are identified is to consider simultaneous identifications of "blocks" of variables. To formalize this measure we follow Willard's [START_REF] Willard | Essential arities of term operations in finite algebras[END_REF] framework and 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 . Let Eq(V ) denote the set of all equivalence relations on V . Given an equivalence relation θ ∈ Eq(V ), denote the canonical surjection by v θ : V → V /θ. For a function f : A V → B, we define the function f θ : A V /θ → B by f θ (a) = f (a • v θ ), and we say that f θ is obtained from f by block identification of variables through θ. We informally identify V /θ with any one of its distinct representatives so that f θ becomes a simple minor of f , and every simple minor of f is then equivalent to f ψ for some ψ ∈ Eq(V ). The number of variables identified through θ is

Open problems and future work

Looking ahead to possible future research topics related to arity gap, we are naturally drawn to two rather distinct problems. On the one hand, the work mentioned in Section 3 and Subsection 5.2 inevitably brings up the question on whether a general classification of algebras can be attained in terms of decomposability as in the case of abelian groups or fields of prescribed characterictic. On the other hand, the work surveyed in Section 4 naturally asks for similar enumeration results for the parametrized versions of arity gap discussed in Subsection 6.2.

( 1 ) 2 )

 12 With the notation and facts given above, we can now provide the number G kℓ np of functions f : A n → B with ess f = n and gap f = p. Theorem 10 ([9]). Let k ≥ 2, ℓ ≥ 2, n ≥ 2. If n > k and 3 ≤ p ≤ n, then G kℓ np = 0. (If n > k and n ≥ 4, then

Example 9 . 1

 91 Consider the 6-ary function f of Example 7. We can read off of Figure

( 1 . 10 .

 110 |X| -1) = |V | -|V /θ|. Assuming that f depends on all of its variables, i.e., ess f = |V |, we have that ess f θ ≤ |V /θ| = |V | -e(θ) = ess f -e(θ). Now we can define the analogue of the parametrized arity gap for block identification of variables. For a function f : A V → B with ess f = |V | = n and for an integer ℓ such that 0 ≤ ℓ ≤ n -1, we define b-gap(f, ℓ) := min θ∈Eq(V ) e(θ)=ℓ(ess f -ess f θ ).Note that b-gap(f, 0) = 0 and b-gap(f, 1) = gap f for every function f . It is also clearthat ℓ ≤ b-gap(f, ℓ) ≤ n for every 0 ≤ ℓ ≤ n -1, and b-gap(f, ℓ) ≤ gap(f, ℓ) for every ℓ for which gap(f, ℓ) is defined. Let H(f ) := {ess f -ess g : g ≤ f }. It is clear that {b-gap(f, ℓ) : 0 ≤ ℓ ≤ n -1} ⊆ H(f ).Proposition 6 ([13]). 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 -Example Consider the 6-ary function f of Example 7. We can read off of Figure 1 that H(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. Following the same steps as in the sequential approach, we ended up considering the following problem: Given a function f : A V → B that depends on all of its variables and an integer p ≥ 1, what is the smallest number m such that block identification of variables of f through every equivalence relation θ on V with e(θ) = m results in the loss of at least p essential variables? Let us denote this smallest number by b-pag(f, p). It is again clear that b-pag(f, p) is the smallest ℓ 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. Example 11. Consider the 6-ary function f of Example 7. We can determine from the values of b-gap(f, ℓ) listed in Example 10, 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.

  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) + 2and 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.

Acknowledgment

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


Ye Liu
email: ye.liu1@alcatel-lucent.com

Chung Shue Chen
email: cs.chen@alcatel-lucent.com

Chi Wan Sung

Joint Optimization on Inter-cell Interference Management and User Attachment in LTE-A HetNets

Keywords: LTE/LTE-A, heterogeneous networks, enhanced inter-cell interference coordination, almost blank subframe, cell selection bias, distributed optimization, potential game

To optimize the network utility in 3GPP Long Term Evolution-Advanced (LTE-A) heterogeneous networks (HetNets), it is necessary to jointly consider inter-cell interference mitigation and user attachment. Based on potential game formulation, we optimize almost blank subframe (ABS) and/or cell selection bias (CSB) settings for both macrocells and picocells in a distributed manner. We demonstrate the need of joint ABS and CSB optimization via simulation case studies. Extensive simulations confirm that joint ABS and CSB optimizations can lead to a 20% improvement in spectral efficiency and a 46% improvement in energy efficiency while increasing the fairness of the achieved rates of users.

I. INTRODUCTION

To meet the predicted fast growth of mobile data traffic [START_REF] Cisco | Cisco visual networking index: Forecast and methodology[END_REF], it has been envisioned that cell densification is one of the key technologies. Due to the high cost and shortage of available sites of deploying more macrocells, adding low-power small cells into the current cellular networks becomes a feasible way to increase the network capacity [START_REF] Andrews | Seven ways that HetNets are a cellular paradigm shift[END_REF]. The resultant networks that operators have to deal with after deploying small cells will be heterogeneous networks (HetNets). Some non-trivial optimization work, however, must be done in order to get the maximum capacity increase from HetNets. Mobile users, even located near a small cell, may be associated to an overloaded macrocell because the macrocell provides higher reference signal received power (RSRP). On the other hand, a user associated to a small cell may suffer large interference from nearby macrocells and can therefore enjoy very low downlink (DL) throughput. 3GPP has proposed enhanced inter-cell interference coordination (eICIC), where the cellselection bias (CSB) and almost blank subframe (ABS) are the mechanisms to solve the user off-loading and inter-cell interference problems, respectively.

User off-loading and inter-cell interference management are not decoupled problems. The toy example in Fig. 1 illustrates the point that joint ABS and CSB optimization is needed to obtain good DL throughput performance, where the network consists of one macrocell, one picocell, and two users. Fig. 1a shows the situation where eICIC is not applied, and both user equipment 1 (UEs) will be attached to the macrocell even if UE 2 is located near the picocell. In Fig. 1b, the picocell modifies its CSB value so that UE 2 is now attached to the picocell even if the macrocell offers higher RSRP. In this case, UE 1 can enjoy higher throughput because UE 2 has been offloaded to the picocell. However, UE 2 will suffer from low throughput due to the strong interference from the macrocell. In Fig. 1c, the macrocell offers one of the two subframes (time slots) as an ABS and mutes its transmission on that subframe. Although UE 1 enjoys less throughput in this case, the throughput of UE 2 can be greatly increased because it is served by an interference-free subframe. Also, the total power consumption of the cells are greatly reduced while the users can achieve reasonably high data rate. By comparing the three cases in Fig. 1, we can see that joint ABS and CSB optimization can lead to a resource allocation pattern that strikes a good balance among fairness, high data rate, and energy efficiency.

Several algorithms of eICIC optimization exist in the literature. Tall et al.'s algorithm in [START_REF] Tall | Self organizing strategies for enhanced ICIC (eICIC)[END_REF] performs optimization of ABS and CSB separately, where the ABS patterns are represented as fractional numbers. Deb et al. proposes a centralized algorithm that jointly optimizes ABS and CSB patterns in [START_REF] Deb | Algorithms for enhanced inter-cell interference coordination (eICIC) in LTE HetNets[END_REF], where the interfering macrocells of a picocell are constrained to offer ABSs on the same subframes. In [START_REF] Pang | Optimized time-domain resource partitioning for enhanced inter-cell interference coordination in heterogeneous networks[END_REF], Pang et al. propose a distributed algorithm that determines the number of ABSs without the optimization of CSB. Thakur et al. considered CSB optimization together with femtocell power control in [START_REF] Thakur | Improving capacity and energy efficiency of femtocell based cellular network through cell biasing[END_REF]. In [START_REF] Bedekar | Optimal muting and load balancing for eICIC[END_REF], Bedekar and Agrawal show that under certain simplifications, the joint optimization problem can be decoupled into optimizing ABS ratios and optimizing user attachment problems.

This paper aims at optimizing the proportional fair (PF) global utility of a LTE-A HetNet by using a distributed algorithm that jointly optimizes ABS and CSB patterns. Specifically, we formulate an exact potential game, and we show that by randomly choosing a player and letting the player plays (c) CSB applied to the picocell and ABS applied to the macrocell.

Fig. 1: Toy example of a LTE HetNet which consists of a macrocell, a picocell, and two users. its best response will lead to a Nash equilibrium. Through simulation studies, we find out that our distributed joint ABS and CSB optimizer can improve the spectral efficiency by 20% and improve the energy efficiency by 46% while enhancing the fairness of the achieved user data rates. Also, we use different DL schedulers and compare their impact on various system performance indicators, and we find out that the scheduler based on convex relaxation can lead to 14% increase in spectral efficiency and 16% in energy efficiency compared to a conventional PF DL scheduler.

The rest of the paper is organized as follows. Section II gives the system model of the LTE-A HetNets. Section III formulates the joint ABS, CSB, and resource allocation optimization problem. Section IV proposes the distributed optimization algorithm based on exact potential game and describes three different DL schedulers. Section V presents the numerical studies, and Section VI concludes the paper.

II. SYSTEM MODEL

Consider a heterogeneous cellular network where picocells are deployed together with macrocells. Denote M and P as the set of macrocells and picocells, respectively. Denote U i as the set of users associated with station 2 i, where i ∈ M ∪ P. Let the vector γ denote the CSB values of all stations and let γ i denote the CSB value of station i, where each γ i takes a value in a pre-defined set of real numbers C. Let P i Rx,u be the RSRP of user u from station i, user u will be attached to the following station

g(u, γ) arg max i (P i Rx,u + γ i ). (1)
Clearly, P i Rx,u depends on the transmission power of the serving station, the distance between the serving station and user u, the shadowing loss, and fast fading. These relevant parameters will be described later in the numerical studies section.

Suppose each station has the following resources, i.e., T equal-length subframes in the time domain and F equal-width resource blocks (RBs) in the frequency domain, where each subframe and RB pair forms a physical resource block (PRB). Denote B := T • F as the total number of PRBs available at each station. It is assumed that when a station is transmitting on a certain subframe, the transmission power allocated on all the PRBs is the same. Also, it is assumed that all PRBs are synchronized in both time and frequency domains.

Let α m be the ABS pattern vector of macrocell m, where the vector consists of T binary entries, and the values 0 and 1 indicate that the corresponding subframe is an ABS and a non-ABS, respectively. Let gives the interference power from macrocells in M \ {m} at PRB b, P P Int,b gives the interference power from picocells in P at PRB b, and N 0 denotes the additive white Gaussian noise (AWGN). When user u is served by picocell p, its SINR at PRB b is given by:

SINR p u,b = h p u,b • P p Rx,u P M Int,u,b + P P\{p} Int,u,b + N 0 ,
where h p u,b is the fast fading link gain from picocell p to user u at PRB b, P M Int,u,b gives the interference power from macrocells in M and P P\{p} Int,u gives the interference power from picocells 2 A station may be referred to as a macrocell or a picocell. The index of subframe of PRB (b) g(u, γ)

The station user u is associated with Set of all users in the system U i

h i u,b
Users associated with station i in P \ p. It is assumed that the serving station knows the throughput of user u at PRB b, and the throughput can be calculated using Shannon's capacity formula, i.e.,

r u,b = W • log 2 (1 + SINR m u,b ), g(u, γ) = m, W • log 2 (1 + SINR p u,b ), g(u, γ) = p,
where W is the bandwidth of a PRB. Note that the interference power from the interfering macrocells depends on their ABS patterns. Table I summaries the notations used throughout the paper.

III. PROBLEM FORMULATION

We now present the resource allocation problem, where the ABS and CSB patterns of the stations are the main parameters to be optimized.

Let x u,b be the binary variable which tells if PRB b is allocated to user u by its serving station, where x u,b = 1 indicates that user u occupies the b-th PRB and x u,b = 0 indicates otherwise. Assume a nonnegative weighting factor w u is applied to user u. To achieve a good trade-off between maximizing total throughput and user fairness, we aim to solve the following MAXPFUTILITY optimization problem:

maximize i∈M∪P u∈Ui w u • ln B b=1 x u,b • r u,b , (2) subject to u∈Um x u,b = α m,τ (b) , ∀m ∈ M, b ∈ [1, B], α m ∈ A, (3)
u∈Up x u,b = 1, ∀p ∈ P, b ∈ [1, B], (4)
x u,b ∈ {0, 1}, ∀u ∈ U , b ∈ [1, B], (5)
γ(i) ∈ C, ∀i ∈ M ∪ P, (6)
where the objective function is chosen to be the sum of log of users' throughput so that proportional fairness among the users is the goal [START_REF] Hou | Self-organized resource allocation in LTE systems with weighted proportional fairness[END_REF]. In the constraint (3), A denotes the set of ABS patterns that a macrocell can adopt.

We will discuss in more detail that MAXPFUTILITY is hard to solve in the next section. Also, a distributed algorithm based on exact potential game will be provided.

IV. DISTRIBUTED ALGORITHM USING GAME THEORY

In this section, we describe the distributed algorithm based on exact potential game and various downlink schedulers. A similar approach for distributed optimization on power control and user association has been discussed in [START_REF] Singh | Distributed downlink resource allocation in cellular networks through spatial adaptive play[END_REF].

A. Exact Potential Game Formulation

In an exact potential game, there exists a potential function such that the change of the potential function due to the change of a player's strategy is equal to the change of the payoff function of that player due to the change of its strategy. If players take turns randomly to update their strategies so that their payoff functions are maximized (i.e., best response), the strategies of players will converge to a Nash equilibrium within finite steps of game plays [START_REF] Neel | Analysis and Design of Cognitive Radio Networks and Distributed Radio Resource Management Algorithms[END_REF], where the underlying assumption is that the game is finite.

Recall that our objective is to maximize the PF objective function in a LTE-A HetNet as stated in MAXPFUTILITY. When a station changes its CSB value or ABS pattern (in case of a macrocell only), the neighboring stations' user attachment and DL throughput can be affected. Let the stations be the players. If each player's payoff function takes the neighboring stations' utilities into account, then the change of the global utility due to the change of a player's strategy will be equal to the change of the payoff function of that player. This gives the intuition of how we can formulate the exact potential game.

Besides ABS and CSB patterns, the selection of DL schedulers also impacts the DL throughput of a station. In this paper, instead of including various schedulers in the strategy set of each station, we fix the selection of DL schedulers during game plays and compare system performance when different schedulers are used. We will describe the DL schedulers after formulating the exact potential game.

Let M ∪ P be the set of players. For joint ABS and CSB optimization, define the set of strategies that player i can adopt as

S i := A × C, i ∈ M, C, i ∈ P,
so that macrocells offer ABSs and can adjust CSB values while picocells only adjust CSB values and offer no ABS. In the sequel we use player and station interchangeably. Denote s and s i as the strategies played by all players and the strategy played by player i, respectively. Let

s -i (s 1 , ..., s i-1 , s i+1 , ..., s |M|+|P| ),
be the strategies adopted by every player other than player i. Denote (s ′ i , s -i ) (s 1 , ..., s i-1 , s ′ i , s i+1 , ..., s |M|+|P| ) as the strategies of all players so that player i chooses strategy s ′ i and all other players' strategies are given as s -i .

Define the neighboring set of player i as N i {i} ∪ N Int i ∪ N Att i , where i ∈ M ∪ P, N Int i denotes the set of stations whose downlink transmissions can be interfered by station i, N Att i is the set of stations whose user attachment patterns can be changed by modifying the CSB value of station i. Let the utility of station i ∈ M ∪ P be

U i (s) u∈Ui w u • ln B b=1 x u,b • r u,b , (7)
where x u,b is given by the underlying scheduling scheme and satisfies the constraints (3), ( 4) and [START_REF] Pang | Optimized time-domain resource partitioning for enhanced inter-cell interference coordination in heterogeneous networks[END_REF]. The total utility of all players is

U (s) = i∈M∪P U i (s). (8)
Let the payoff function of player i be

V i (s) j∈Ni U j (s).
We show that the function U (•) is a potential function in the following theorem.

Theorem 1. The function U (•) is a potential function of the game (M ∪ P, (S i , i ∈ M ∪ P), (V i , i ∈ M ∪ P)).
Proof. Suppose we change the strategies of players from s to (s ′ i , s -i ), then the change on U (•) is given as follows:

U (s ′ i , s -i ) -U (s) = j∈M∪P U j (s ′ i , s -i ) -U j (s) = j∈Ni (U j (s ′ i , s -i ) -U j (s)) + j∈M∪P\Ni (U j (s ′ i , s -i ) -U j (s)) = j∈Ni (U j (s ′ i , s -i ) -U j (s)) (9) = V i ((s ′ i , s -i )) -V i (s), (10)
where [START_REF] Singh | Distributed downlink resource allocation in cellular networks through spatial adaptive play[END_REF] follows since the change of player i's strategy only affects the utilities of players in N i , and [START_REF] Neel | Analysis and Design of Cognitive Radio Networks and Distributed Radio Resource Management Algorithms[END_REF] follows from the definition of the payoff function of a player. Eqn. [START_REF] Neel | Analysis and Design of Cognitive Radio Networks and Distributed Radio Resource Management Algorithms[END_REF] indicates that the change of U (•) due to the change of the strategy of a player is equal to the change of the payoff function of that player. Therefore, U (•) is a potential function of the game (M ∪ P, (S i , i ∈ M ∪ P), (V i , i ∈ M ∪ P)).

Since randomly updating players' strategies will lead to a Nash equilibrium if each player plays its best response, the procedure of the distributed optimization can be carried out as follows:

1) Initialize the ABS and CSB patterns of all macrocells.

Initialize the CSB values of all picocells. 2) Select a player i randomly from M ∪ P. The player then tests all strategies in S i and selects the one that maximizes V i . 3) Repeat step 2 until some stopping criterion is met. Note that the same potential game framework can be used to optimize other objective functions. For example one may aim at maximizing the weighted sum of DL throughput of all users [START_REF] Chen | Round-robin power control for the weighted sum rate maximisation of wireless networks over multiple interfering links[END_REF], in this case it will be more reasonable to define the payoff function of a player in [START_REF] Bedekar | Optimal muting and load balancing for eICIC[END_REF]

as u∈Ui w u • B b=1 x u,b • r u,b .
Moreover, the potential game framework can be used to perform optimizations when only ABS patterns of the macrocells or only CSB values of the stations are allowed to be changed. For solely ABS optimization of macrocells, the strategy sets of all macrocells becomes A and the only strategy that a picocell has is to use all subframes and set its CSB value to 0 dB. For solely CSB optimization, the strategy set of each station is C.

B. DL Schedulers

In this paper, we compare the performance of the distributed optimization algorithm using three DL schedulers.

1) Round-Robin (RR) Scheduler: A station simply allocates its PRBs to the attached users in turns. For example, suppose a station has five PRBs labeled as PRB 1 , PRB 2 , ..., and PRB 5 , and there are two users attached to the station, then PRB 1 , PRB 3 , and PRB 5 will be allocated to user 1 while PRB 2 and PRB 4 will be allocated to user 2.

2) PF Scheduler [START_REF] Sesia | LTE -The UMTS Long Term Evolution: From Theory to Practice[END_REF]: For station i, the b-th PRB at subframe t, given that the subframe is not an ABS, will be allocated to the following user

u b arg max u∈Ui r u,b r u (τ (b))
,

where b ∈ [1, B], r u (t)
is the long-term average throughput of user u in subframe τ (b) and it is calculated as

r u (τ (b)) = (1 -1 tc )r u (τ (b) -1) + 1 tc Σ {b ′ |τ (b ′ )=τ (b)} r u,b ′ • I{ u ′ b = u}.
In the above equation, t c is the time window to be chosen and I{•} is the indicator function. The performance of this scheduler has been studied in several scenarios, see [START_REF] Caire | Hard fairness versus proportional fairness in wireless communications: The single-cell case[END_REF].

3) Convex PF Scheduler: Given a strategy, we wish to maximize the payoff function of a player as defined in [START_REF] Bedekar | Optimal muting and load balancing for eICIC[END_REF] subject to the constraints (3), ( 4) and ( 5). This problem, however, has been proved to be an NP-hard problem in [14, Theorem 2].

On the other hand, if we take a picocell as an example, relax the integer constraint in [START_REF] Pang | Optimized time-domain resource partitioning for enhanced inter-cell interference coordination in heterogeneous networks[END_REF] and formulate the following RELAXEDSCHEDULER problem

maximize u∈Up w u • ln B b=1 x u,b • r u,b , (cf. 7) subject to u∈Up x u,b = 1, ∀p ∈ P, b ∈ [1, B], 0 ≤ x u,b ≤ 1, ∀u ∈ U p , p ∈ P, b ∈ [1, B], (11)
we have the following observations: (a) The objective function is concave. To see this, note that ln

B b=1 x u,b • r u,b
is a composition of a concave function and a linear function so that it is concave, and the objective function is therefore concave since it is a nonnegative summation of concave functions [START_REF] Boyd | Convex Optimization[END_REF]. (b) The constraints are linear. As a result, we can solve RELAXEDSCHEDULER by changing the objective to minimizing the negative of ( 7 so that the constraints in (3), (4), and (5) are satisfied. The quantization can be done as

x u,b :=    1, u = arg max u ′ {x Relaxed u ′ ,b }, 0, ∀u = arg max u ′ {x Relaxed u ′ ,b },
where a tie is broken randomly in case arg max u ′ {x Relaxed u ′ ,b } returns multiple answers for a given b.

The case when the station is a macrocell is similar except no user is assigned to the PRBs that are offered as ABSs. The details are omitted for simplicity.

V. SIMULATION RESULTS

A randomly generated hexagonal HetNet layout is shown in Fig. 2, where the whole network consists of seven clusters of macrocells and the borders of each cluster are marked with bolded lines. Macrocells are located at the center of their respective hexagons. One picocell is placed within each hexagon in the center cluster, where the angle of the vector which starts from the hexagon center and ends at the picocell is randomly chosen and the distance from the picocell to the center of the hexagon follows triangular distribution. This will create an effect that the picocells are more likely to be located near the edge of each hexagon, an area where all neighboring macrocells impose strong interference. Also, for each hexagon in the center cluster, six users are placed within 120 meters from each picocell and another four users are placed within the hexagon. The distribution of the distances from the six Fig. 3: ABS patterns that can be chosen by a macrocell. users who are intentionally placed within 120 meters of a picocell follows triangular distribution, and the directions from the picocell to the six users are random. The other four users are similarly generated except the reference point becomes the respective macrocell. The six clusters surrounding the center cluster are exact copies of the center cluster. Other parameters are given in Table II. The setup of the potential game is given as follows. The elements in M and P are the macrocells and the picocells in the center cluster, respectively. The weighting factors of all users are the same, i.e., w u = 1 for all u. T and F are set to be 10 and 3, respectively. All possible ABS patterns are shown in Fig. 3, and all possible CSB values are given in Table II.

It is assumed that the users are static and the buffers of the stations are always fully loaded. Also, each PRB experiences independent Rayleigh fading with variance 1. The shadowing from a station to a user is calculated by adding a common shadowing value and a randomly generated shadowing value and then dividing the sum by √ 2, so that the shadowing values are correlated [START_REF] Greentouch | Mobile communications WG architecture doc2: Reference scenarios[END_REF]. The following results are obtained by averaging 200 randomly generated HetNet topologies.

Fig. 4 plots the global utility functions as the potential games are being played, where the global utility function is defined in [START_REF] Hou | Self-organized resource allocation in LTE systems with weighted proportional fairness[END_REF]. The maximum number of iteration is set to be 300. We can see that all global utility functions increase as more iterations are played. Also, the global utility functions when the convex PF schedulers as described in Section IV-B3 are used are always larger than the global utility functions when the PF schedulers as described in Section IV-B2 are used, and the global utility functions when the PF schedulers are used are always larger than the global utility functions when the RR schedulers are used. On average, a global utility function when the convex PF scheduler is used is about 5% larger than a global utility function when the PF scheduler is used, and a global utility function when the PF scheduler is used is about 15% larger than a global utility function when the RR scheduler is used. Three different values of the time window t c of the PF scheduler are tested, and the variation of the global utility function due to different t c settings is not large.

Fig. 5, Fig. 6, and Fig. 7 show the cumulative distribution functions (CDFs) of the achieved user rates when ABS together with CSB optimization, ABS optimization, and CSB optimization are performed, respectively. The achieved rate of a user is defined as the sum of the per-bandwidth Shannon capacity of each PRB that is assigned to that user. We can observe from Fig. 5 that the user rates when joint ABS and CSB optimizations are performed are improved compared to the counterparts when no optimization is done. The user rates improvements due to ABS optimization and CSB optimization, as depicted in Fig. 6 and Fig. 7, respectively, are unfortunately not very obvious.

Fig. 8 gives the CDFs of the achieved rates of the worst 5% users of all randomly generated HetNets, where the convex PF scheduler is used in each of the four scenarios. We can see that the joint ABS and CSB optimization can help the worst users to increase their achieved rates.

Table III summaries several performance indicators of different game plays, where Jain's Index stands for the Jain's fairness index of the achieved user rates, CoV stands for the coefficient of variation on the achieved user rates, SE stands for the spectral efficiency defined as the average per-bandwidth capacity of all allocated PRB from cells in M and P, and EE stands for energy efficiency defined as the number of bits transmitted in all allocated PRBs from cells in M and P divided by the transmission energy used by all cells in M are jointly optimized against the cases when no optimization is performed. For example, "RR" represent the CDF of user rates when no optimization is done and the scheduler is RR, "RR, ABS+CSB" represent the CDF of user rates when ABS and CSB joint optimization is performed and the scheduler is RR. Comparison of CDFs of user rates when ABS is optimized against the cases when no optimization is performed. For example, "RR" represent the CDF of user rates when no optimization is done and the scheduler is RR, "RR, ABS" represent the CDF of user rates when ABS optimization is performed and the scheduler is RR. Comparison of CDFs of user rates when CSB is optimized against the cases when no optimization is performed. For example, "RR" represent the CDF of user rates when no optimization is done and the scheduler is RR, "RR, CSB" represent the CDF of user rates when CSB optimization is performed and the scheduler is RR. Fig. 8: The CDF of the worst 5% users' rates. and P. In general, we can observe that ABS and CSB joint optimization can lead to better user fairness, less deviation of user rates, higher spectral efficiency and higher energy efficiency. Specifically, if we compare the case when joint ABS and CSB optimization is performed and the case when no optimization is carried out while the underlying schedulers in both cases are the convex PF schedulers, then we can observe a 20% increase in spectral efficiency, a 46% increase in energy efficiency, and a larger fairness index achieved by joint ABS and CSB optimization. Also, if we compare the convex PF scheduler and the PF scheduler with t c = 40 when joint ABS and CSB optimization is performed, we can observe 14% increase in spectral efficiency, a 16% increase in energy efficiency, and a larger fairness index achieved by the convex PF scheduler.

VI. CONCLUSION

We have proposed a distributed game-theoretic-based algorithm for jointly optimizing the ABS and CSB patterns in LTE-A HetNets. Based on the potential game framework, we have demonstrated the necessity of jointly optimizing the ABS and CSB patterns, as simulation results suggest that large improvements on spectral efficiency, energy efficiency, and user fairness can be achieved by doing so. Moreover, we have compared two DL PF schedulers and showed that the scheduler obtained from relaxing an NP-hard resource allocation problem outperforms the other more conventional scheduler in terms of user fairness, spectral efficiency, and energy efficiency.

  (a) No eICIC optimization. (b) CSB applied to the picocell.

  r u,b be the throughput of user u at PRB b, where b ∈ [1, B]. The actual value of r u,b is affected by α m when macrocell m is either interfering or serving user u. When user u is associated with macrocell m, its signal-to-noise-plus-interference ratio (SINR) on PRB b is then calculated as: SINR m u,b = h m u,b • P m Rx,u • α m,τ (b) P M\{m} Int,u,b + P P Int,u,b + N 0 , where h m u,b is the fast fading link gain on PRB b from macrocell m to user u, τ (b) returns the subframe index with respect to PRB b, P M\{m} Int,b

Fading

  gain from station i to user u at PRB b r u,b Throughput of user u at PRB b, where the serving station of the user is implicitly given wu Weighting factor of UE u x u,b Indicator of whether user u occupies PRB b of the serving cell B Number of PRBs F Number of RBs N 0 Noise power of a frequency subcarrier at a user T Number of subframes W Bandwidth per RB A Set of vectors from which macrocells can choose ABS pattern C Set of CSB values any station can choose from M Set of all macrocells P Set of all picocells U

  Fig.2:A randomly generated hexagonal HetNet layout. The triangles, dots, and crosses represent macrocells, picocells and users, respectively.

  ) and use standard convex optimization solvers. Let x Relaxed u,b be the solution to RELAXEDSCHEDULER. To get a feasible solution of MAXPFUTILITY, we need to quantize x Relaxed u,b

Fig. 4 :

 4 Fig. 4: Average global utility as a function of number of game plays.

Fig. 5 :

 5 Fig.5: Comparison of CDFs of user rates when ABS and CSB are jointly optimized against the cases when no optimization is performed. For example, "RR" represent the CDF of user rates when no optimization is done and the scheduler is RR, "RR, ABS+CSB" represent the CDF of user rates when ABS and CSB joint optimization is performed and the scheduler is RR.

  Fig.6: Comparison of CDFs of user rates when ABS is optimized against the cases when no optimization is performed. For example, "RR" represent the CDF of user rates when no optimization is done and the scheduler is RR, "RR, ABS" represent the CDF of user rates when ABS optimization is performed and the scheduler is RR.

  Fig.7: Comparison of CDFs of user rates when CSB is optimized against the cases when no optimization is performed. For example, "RR" represent the CDF of user rates when no optimization is done and the scheduler is RR, "RR, CSB" represent the CDF of user rates when CSB optimization is performed and the scheduler is RR.

  PF Convex, CSB PF Convex, ABS PF Convex, no opti.

TABLE I :

 I Descriptions of notations

	Notation	Description
	αm	ABS pattern of macrocell m
	γ	Vector specifying CSB patterns of all stations
	τ (b)

TABLE II :

 II Parameters for Generating HetNet Topologies

	Parameter	Value
	Inter-macrocell distance	1000 m
	Minimum distance from macro to user	35 m
	Minimum distance from pico to user	10 m
	Minimum distance from macro to pico	75 m
	Antenna per site	Omnidirectional × 1
	Macrocell power	40 W
	Picocell Power	1 W
	Noise density	-174 dBm/Hz
	Noise figure	9 dB
	Duration per subframe	1 ms
	Bandwidth per RB	180 kHz
	CSB values

{0, 3, 6, 9, 12, 15} dB Log-normal shadowing 10 dB standard deviation Path loss from macrocell to user 128.1 + 37.6 log 10 d, d in km Path loss from picocell to user 140.7 + 36.7 log 10 d, d in km

TABLE III :

 III Performance Indicators

	Optimizer	Scheduler	Jain's	CoV	SE	EE
			Index		(bps/Hz)	(10 5 bits/J)
		PF convex	0.62	0.78	3.77	1.028
		PF tc = 40	0.56	0.88	3.31	0.886
	ABS+CSB	PF tc = 20	0.57	0.88	3.30	0.885
		PF tc = 5	0.57	0.87	3.23	0.874
		RR	0.52	0.95	2.76	0.763
		PF convex	0.49	1.03	3.34	0.772
		PF tc = 40	0.46	1.09	3.05	0.698
	ABS	PF tc = 20	0.46	1.08	3.04	0.698
		PF tc = 5	0.46	1.09	2.98	0.695
		RR	0.39	1.25	2.54	0.601
		PF convex	0.58	0.86	3.06	0.703
		PF tc = 40	0.56	0.88	2.83	0.649
	CSB	PF tc = 20	0.56	0.88	2.82	0.649
		PF tc = 5	0.56	0.89	2.77	0.643
		RR	0.50	1.01	2.33	0.530
		PF convex	0.50	0.99	3.14	0.703
		PF tc = 40	0.48	1.05	2.89	0.639
	None	PF tc = 20	0.47	1.05	2.88	0.639
		PF tc = 5	0.47	1.06	2.83	0.634
		RR	0.41	1.21	2.35	0.523

We use UE and user interchangeably.

ACKNOWLEDGEMENT

This work was supported by ANR project IDEFIX under grant number ANR-13-INFR-0006 and in part by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China, under Project CityU 121713. A part of the work was carried out at LINCS (www.lincs.fr).