Silvio Capobianco
email: silvio@cs.ioc.ee

Pierre Guillon
email: pguillon@math.cnrs.fr

Camille Noûs
email: camille.nous@noussommesluniversite.fr

Besicovitch pseudodistances with respect to non-Følner sequences

Keywords: Besicovitch distance, Følner sequences, submeasures, amenability, non-compact space, symbolic dynamics

The Besicovitch pseudodistance defined in [BFK99] for one-dimensional configurations is invariant by translations. We generalize the definition to arbitrary groups and study how properties of the pseudodistance, including invariance by translations, are determined by those of the sequence of finite sets used to define it. In particular, we recover that if the Besicovitch pseudodistance comes from a nondecreasing exhaustive Følner sequence, then every shift is an isometry. For non-Følner sequences, we prove that some shifts are not isometries, and the Besicovitch pseudodistance with respect to some subsequence even makes them non-continuous.

Introduction

The Besicovitch pseudodistance was proposed by Blanchard, Formenti and Kůrka in [START_REF] Blanchard | Cellular automata in the Cantor, Besicovitch and Weyl spaces[END_REF] as an "antidote" to sensitivity of the shift map in the prodiscrete (Cantor) topology of the space of 1D configurations over a finite alphabet. The idea is to take a window on the integer line, which gets larger and larger, and compute the probability that in a point under the window, chosen uniformly at random, two configurations will take different values. The upper limit of this sequence of probabilities behaves like a distance, except for taking value zero only on pairs of equal configurations: this defines an equivalence relation, and the resulting quotient space is a metric space on which the shift is an isometry, or equivalently, the distance is shift-invariant.

The original choice of windows is X n = [-n : n], the set of integers from -n to n included. This notion can be easily extended to arbitrary dimension d ≥ 1, taking a sequence of hypercubic windows. If we allow arbitrary shapes, the notion of Besicovitch space can be extended to configurations over arbitrary groups; in this case, however, the properties of the group and the choice of the windows can affect the the distance being or not being shift-invariant. An example of a Besicovitch pseudodistance which is not shift-invariant is given in [START_REF] Capobianco | Surjunctivity for cellular automata in Besicovitch spaces[END_REF], where it is also proved that, if a countable group is amenable (cf. [START_REF] Capobianco | Surjective cellular automata far from the Garden of Eden[END_REF] and [CSC10, Chapter 4]), then the Besicovitch distance with respect to any nondecreasing exhaustive Følner sequence is shift-invariant. The class of amenable groups is of great interest and importance in group theory, symbolic dynamics, and cellular automata theory.

In this paper, we explore the relation between the properties of Besicovitch pseudodistances over configuration spaces with countable base group and those of the sequence of finite sets used to define it. In Section 3, we give the main definition and prove that if a sequence of finite subsets is increasing, then the corresponding Besicovitch space is pathwise connected: this generalizes [BFK99, Proposition 1]. In Section 4, we introduce a notion of synchronous Følner equivalence between sequences, and a related order relation where one sequence comes before another sequence if it is synchronously Følner-equivalent to a subsequence of the latter. This, on the one hand, generalizes that of Følner sequences, and on the other hand, allows us to compare the Besicovitch distances and submeasures associated to different sequences. In particular, we prove that an increasing sequence of finite sets is Følner if and only if every shift is an isometry for the corresponding Besicovitch distance: this provides the converse of [START_REF] Capobianco | Surjunctivity for cellular automata in Besicovitch spaces[END_REF]Theorem 3.5]. Finally, we give conditions for absolute continuity and Lipschitz continuity of Besicovitch submeasures with respect to each other.

Background

We use the notation X Y to mean that X is a finite subset of Y . We denote the symmetric difference of two sets X and Y as X∆Y .

Given α ∈ R, its integer part α is the largest m ∈ Z such that m ≤ α.

If (α n ) and (β n ) are nonzero number sequences, we write

α n ∼ n→∞ β n if lim n→∞ α n /β n = 1, and α n = o n→∞ β n if lim n→∞ α n /β n = 0.

Submeasures

The following definition appears for instance in [START_REF] Sablik | Étude de l'action conjointe d'un automate cellulaire et du décalage: une approche topologique et ergodique[END_REF].

Definition 2.1. A submeasure over a set G is a map µ : 2 G → R {+∞} such that: 1. µ(∅) = 0; 2. µ(W ) < ∞ if W is finite; 3. µ(V ∪ W ) ≤ µ(V ) + µ(W ) for every V, W ⊂ G.
If G and A are two sets, the difference set of two functions x, y :

G → A is the set ∆(x, y) = { i ∈ G| x(i) = y(i)}.
Any submeasure over G gives rise to an associated pseudodistance over A G :

d µ (x, y) = µ(∆(x, y)) ∀x, y ∈ A G .
Remark 2.2. The topological space corresponding to such a pseudodistance is homogeneous in the following sense: the balls around every two points y and z are isometric. Indeed, identify A with the additive group Z/ |A| Z. Then for every y, z ∈ A G the map ψ y,z :

A G → A G defined by ψ y,z (x)(i) = x(i) -y(i) + z(i)
for every x ∈ A G and i ∈ G is an isometry between any ball around y and the corresponding one around z.

We say that submeasure µ is absolutely continuous (resp. α-Lipschitz, for some α > 0) with respect to submeasure ν if ν(W ) = 0 =⇒ µ(W ) = 0 (resp. µ(W ) ≤ αν(W )) for any W ⊂ G.

Remark 2.3. Let ε, δ > 0, µ, ν two submeasures on G, and z ∈ A G . The following are equivalent.

For every set

W ⊂ G, µ(W ) ≥ ε =⇒ ν(W ) ≥ δ.

For every x, y

∈ A G , d µ (x, y) ≥ ε =⇒ d ν (x, y) ≥ δ.

For every

x ∈ A G , d µ (x, z) ≥ ε =⇒ d ν (x, z) ≥ δ.
Consequently, the identity map, from space A G endowed with d µ onto space A G endowed with d ν , is continuous (resp. α-Lispchitz) if and only if µ is absolutely continuous (resp. α-Lispchitz) with respect to ν. In that case the identity is even absolutely continuous.

Shifts and translations

If A is an alphabet, G is a group, and g ∈ G, the shift by g is the function σ g : A G → A G defined by σ g (x)(i) = x(gi) for every x ∈ A G and i ∈ G. A map ψ from A G to itself is shift-invariant if ψσ g = σ g ψ for every g ∈ G. Note that ∆(σ g (x), σ g (y)) = g -1 ∆(x, y) for every x, y ∈ A G and g ∈ G, as:

∆(σ g (x), σ g (y)) = { i ∈ G| x(gi) = y(gi)} = g -1 j j ∈ G, x(j) = y(j) = g -1 { j ∈ G| x(j) = y(j)} = g -1 ∆(x, y) .
Since the maps ψ y,z from Remark 2.2 are shift-invariant, one can see that the shift is continuous, Lipschitz, etc in every x if and only if it is in one x.

The shift by g, within space A G endowed with d µ , is topologically the same as the identity map, from A G endowed with d µ onto space A G endowed with d ν , where ν(W ) = g -1 µ(W ) = µ(g -1 W ) for any set W ⊂ G. Remark 2.2 can then be rephrased into the following.

Remark 2.4. If G is a group, g ∈ G, and A G is endowed with d µ , then the shift map by g is continuous (resp. α-Lispchitz) if and only if µ is absolutely continuous (resp. α-Lispchitz) with respect to g -1 µ. In that case, the shift by g is even absolutely continuous.

Besicovitch submeasure and pseudodistance

Among classical examples of submeasures are the ones that induce the Cantor topology, or shift-invariant Besicovitch, or Weyl pseudodistance (see [START_REF] Hadeler | Cellular Automata : Analysis and Applications[END_REF]Def 4.1.1]. We will focus on the Besicovitch topology.

Definition

Let X and Y be nonempty sets and let (X n ) be a nondecreasing sequence of finite subsets of X. We may or may not require that (X n ) be exhaustive, that is, n X n = X.

Let us denote

P (W |V ) = |W ∩V | |V | (by convention, this is +∞ if V = ∅).
Remark 3.1.

1. P (W ∪ U |V ) ≤ P (W |V ) + P (U |V )
, and the equality holds if the union is disjoint.

2. If V ⊂ U , then P (V |U ) P (W |V ) = P (V ∩ W |U ) ≤ P (W |U )
The Besicovitch submeasure µ (Xn) : 2 X → [0, 1] is defined by:

µ (Xn) (W ) = lim sup n P (W |X n ) .
The Besicovitch pseudodistance is d (Xn) = d µ (Xn) . For example, if X = N, Y = {0, 1}, and

X n = [0 : n -1], x(i) = 0 for every i ∈ N and y ∈ {0, 1} N is the characteristic function of the prime numbers, then d (Xn) (x, y) = 0.
The topology of the quotient space is very different from the prodiscrete (Cantor) topology.

Remark 3.2. Remark obviously two dual cases (in general we will be in the first case, but not the second one):

1. If every U G appears finitely many times in (X n ), then µ (Xn) (W ) = 0 if W is finite.

2. If all U G appear (or, more generally, if for every n, cofinitely many U G of cardinality n appear) in (X n ), then µ (Xn) (W ) = 1 if W is infinite.

We will now concentrate on the nondecreasing case.

Connectedness

Theorem 3.3. If (X n ) is nondecreasing and has unbounded cardinality, then the Besicovitch space is pathwise-connected.

Proof. It is enough to build, for every W ⊂ G and for every α ∈ [0, 1], a set V (α) such that:

1. if 0 ≤ α < β ≤ 1 then V (α) ⊂ V (β), 2. V (0) = ∅ and V (1) = W ∩ n X n (the submeasure does not account
for what is outside the union), and

3. µ(V (α)) = αµ(W ).
Let us assume that there is a total order on each

Y n = X n \ i<n X i (independent of our α). Now define, inductively on n ∈ N, the set U n ⊂ W ∩ Y n by taking the minimal α |W ∩ X n | - i<n |U i | elements in W ∩ Y n . Provided that this definition is valid, it maintains, for all n ∈ N, the property that i≤n |U i | = α |W ∩ X n | . It is actually valid because, by induction, α |W ∩ X n+1 | - i≤n |U i | = α |W ∩ X n+1 | -α |W ∩ X n | < α (|W ∩ X n+1 | -|W ∩ X n |) + 1 < α (|W ∩ Y n+1 |) + 1 < |W ∩ Y n+1 | + 1 .
We now define V (α) = n∈N U n . By construction, thanks to the common total order, we immediately get that α

< β =⇒ V (α) ⊂ V (β). Moreover, µ(V (α)) = lim sup n∈N P (V (α)|X n ) = lim sup n∈N i≤n U i |X n | = lim sup n∈N α |W ∩ X n | |X n | Since α |W ∩ X n | -1 < α |W ∩ X n | ≤ α |W ∩ X n | and |X n | is unbounded, we get that: µ(V (α)) = αµ(W ) .
4 Følner equivalence and Besicovitch submeasures

Følner equivalence

Let (X n ) and (Y n ) be nondecreasing sequences of finite subsets of G. We say that they are synchronously Følner-equivalent if

lim n→∞ |X n ∆Y n | |X n | = 0 . Proposition 4.1. Consider nondecreasing sequences (X n ) and (Y n ).
The following are equivalent.

1.

(X n ) and (Y n ) are synchronously Følner-equivalent. 2. |X n ∩ Y n | ∼ n→∞ |X n | ∼ n→∞ |Y | n . 3. |X n | ∼ n→∞ |Y n | and |X n \ Y n | = o n→∞ (|X n |).
Proof.

=⇒
\ Y n | = |X n | -|X n ∩ Y n |.
=⇒ 1 Note that:

|X n ∆Y n | = |X n \ Y n | + |Y n \ X n | = |X n \ Y n | + |Y n | -|X n ∩ Y n | = 2 |X n \ Y n | + |Y n | -|X n | = o n→∞ (|X n |) .
Corollary 4.2. Synchronous Følner equivalence is an equivalence relation.

Proof.

• From Proposition 4. • Transitivity follows from Proposition 4.1 and the inclusion X∆Z ⊆ (X∆Y ) ∪ (Y ∆Z), which holds for every X, Y and Z.

• Reflexivity is trivial.

Since the definition involves a lim (and not a lim inf), we immediately note the following.

Remark 4.3. (X n ) and (Y n ) are synchronously Følner-equivalent if and only if (X kn ) and (Y kn ) are synchronously Følner-equivalent, for every increasing sequence (k n ).

We also denote (

X n ) (Y n ) if (X n ) is synchronously Følner-equivalent to a subsequence (Y mn ). Equivalently, lim n→∞ min m∈N |X n ∆Y m | |X n | = 0 .
To be convinced of the equivalence, note that the minimum is reached by some m n for each n ∈ N, because (Y m ) is nondecreasing and X n is finite. Thanks to symmetry of synchronous equivalence, we also have that (X n ) (Y n ) if and only if lim n→∞ min m∈N |Xn∆Ym| |Ym| = 0. We say that they are Følner-equivalent, and write (

X n ) ∼ (Y n ), if both (X n ) (Y n ) and (Y n ) (X n ).
This is the case if they are synchronously Følner equivalent, but the converse is false. As counterexamples, one can consider twice the same sequence, but with repetitions on both sides that are longer and longer, and not synchronized. If one wants to obtain strictly increasing sequences, repetitions can be replaced by very slowly increasing sequences (point by point).

Remark 4.4.

1.

is a preorder relation.

2. Følner-equivalence is an equivalence relation.

Proof.

1. Reflexivity is obvious, and transitivity is not difficult.

2. Følner-equivalence is defined as the equivalence corresponding to a preorder, which is classical.

Proposition 4.5. Assume that

|X n | ∼ n→∞ |Y n |. Then (X n ) and (Y n ) are synchronously Følner-equivalent if and only if (X n ) (Y n ). Proof. Assume (X n ) (Y n ) (the converse implication is trivial). Let n, m ∈ N. If m ≤ n, then |X n \ Y n | ≤ |X n \ Y m | and |Y n \ X n | ≤ |Y n \ Y m | + |Y m \ X n | since (Y n ) is nondecreas- ing. Summing up, |X n ∆Y n | ≤ |X n ∆Y m | + |Y n \ Y m |. Symmetrically, if n ≤ m, |X n ∆Y n | ≤ |X n ∆Y m |+|Y m \ Y n |.

Comparing Besicovitch submeasures

A basic tool in our set constructions will be the following elementary remark.

Remark 4.6. If (X n ) is nondecreasing and exhaustive, then for every finite set W and every ε > 0, there exists n (Xn) (W, ε) such that ∀n ≥ n (Xn) (W, ε), P (W |X n ) < ε and W ⊂ X n . We deduce the following, which will be useful in our constructions.

Lemma 4.7. Let (X n ) be a nondecreasing exhaustive sequence of an infinite group G. Let W = i∈N W i where ∅ = W i G for each i ∈ N, such that, for every n ∈ N, there are at most finitely many i's such that W i ∩ X n = ∅ (this is the case, for example, if the W i 's are pairwise disjoint); in that case j n = max W j ∩Xn =∅ j is well-defined for every n. Then:

1. µ (Xn) (W ) ≥ lim sup i→∞ max m∈N P (W i |X m ) . 2. If there is a sequence (ε n ) converging to 0 such that ∀n ∈ N, n (Xn) ( i<jn W i , ε n ) ≤ n, then: µ (Xn) (W ) = lim sup i→∞ max m∈N P (W i |X m ) .
3. In general, there exists a nondecreasing integer sequence l such that, noting W l = i∈N W l i :

µ (Xn) (W l ) = lim i→∞ max m∈N P (W l i |X m ) .
Proof.

1. Let (m i ) i∈N be a sequence of integers such that P (W i |X m i ) = max m∈N P (W i |X m ). We know that this sequence goes to infinity (even though it may not be nondecreasing), because only finitely many W i 's intersect each X m , but they all intersect at least one. Hence, µ (Xn) (W ) = lim sup n→∞ P (W |X n ) ≥ lim sup i→∞ P (W |X m i ). We get the desired inequality by noting that W i ⊂ W .

2. Point 1 already gives one inequality. For the converse:

µ (Xn) (W ) = lim sup n→∞ P   i<jn W i ∪ W jn ∪ i>jn W i |X n   ≤ lim sup n→∞   P   i<jn W i |X n   + P (W jn |X n ) + P   i>jn W i |X n     ≤ lim sup n→∞ ε n + max m∈N P (W jn |X m ) + 0 ≤ lim sup n→∞ ε n + lim sup n→∞ max m∈N P (W jn |X m ) ≤ 0 + lim sup i→∞ max m∈N P (W i |X m ) .
The last inequality comes from the fact that the sequence (j n ) is nondecreasing (because (X n ) is nondecreasing), and not upper-bounded (because the W i 's are nonempty), so it goes to infinity.

3. Let us define some sequence l by recurrence, from any seed l 0 ∈ N. Assume that l n is defined, and write k n = n (Xn) ( j≤n W l j ). Choose any l n+1 such that for every m ≥ l n+1 , W m does not intersect X kn-1 (this is possible by assumption). If j n = max W l j ∩Xn =∅ j, then n (Xn) ( j<jn W l j ) = k jn-1 . By definition, W l jn does not intersect X k jn-1 -1 . Since W l jn intersects X n , we can deduce that n > k jn-1 -1. This means that (W l i ) satisfies the hypothesis of Point 2.

Replacing the lim sup by a lim can be achieved by taking, again, a subsequence.

Lemma 4.8. Let ε, δ > 0, and (X n ), (Y n ) be nondecreasing and exhaustive. The following are equivalent.

For every

W ⊂ G, if µ (Yn) (W ) ≥ ε, then µ (Xn) (W ) ≥ δ. 2. lim inf n∈N max m∈N ε |Y n | -|Y n \ X m | |X m | ≥ δ.
If m n realizes the maximum for each n ∈ N, and if ε < 1, then these properties imply that

δ ε ≤ lim inf n∈N |Y n | |X mn | ≤ lim sup n∈N |Y n | |X mn | ≤ 1 -δ 1 -ε .
In particular, the properties imply that δ ≤ ε.

Proof.

•

|Xm n | ≤ 1-δ 1-ε , provided that ε < 1. 2⇒1 µ (Xn) (W ) = lim sup m→∞ P (W |X m ) ≥ lim sup n→∞ P (W |X mn ) ≥ lim sup n→∞ |W ∩ Y n ∩ X mn | |X mn | = lim sup n→∞ |W ∩ Y n | -|W ∩ Y n \ X mn | |X mn | ≥ lim sup n→∞ |W ∩ Y n | -|Y n \ X mn | |X mn | = lim sup n→∞ ε |Y n | -|Y n \ X mn | |X mn | + |W ∩ Y n | -ε |Y n | |Y n | |Y n | |X mn | ≥ lim inf n→∞ ε |Y n | -|Y n \ X mn | |X mn | + lim sup n→∞ |W ∩ Y n | |Y n | -ε lim inf n∈N |Y n | |X mn | ≥ δ + 0 δ ε
by the two premises and the first inequalities.

1⇒2 Assume that lim inf i→∞

ε|Y i |-|Y i \X k i | |Xk i | < δ.
Let us build a set W that contradicts Point 1.

For each n ∈ N, there exists

k n = min { k| |Y n \ X k | ≤ ε |Y n |}, because for large k, Y n \X k = ∅ (because (X k ) is exhaustive and Y n is finite). By noting that (Y n ∩ X kn ) \ X kn-1 = (Y n \ X kn-1 )\(Y n \X kn ) (by convention X -1 is empty), we can write that |(Y n ∩ X kn ) \ X kn-1 | = |Y n \ X kn-1 | -|Y n \ X kn |, which is bigger than ε |Y n | -|Y n \ X kn |, by minimality of k n . Hence (Y n ∩ X kn ) \ X kn-1 admits a subset Z n of cardinality |Z n | = ε |Y n | -|Y n \ X kn |. Define W n = (Y n \ X kn ) Z n . Note that W n ⊂ Y n , and that ε -1 |Yn| < P (W n |Y n ) ≤ ε.
The W i satisfy the hypotheses of Lemma 4.7, so that Point 3 gives an integer sequence l, with µ (Xn) (W l ) = lim i→∞ max m∈N P (W l i |X m ). By construction, we have:

P (W i |X m ) = P (Y i \ X k i |X m ) + P (Z i |X m ) = |Y i ∩ X m \ X k i | + |Z i ∩ X m | |X m | . If m < k i , then X m ⊆ X k i , and Z i ∩ X m ⊆ Z i ∩ X k i -1 = ∅, so that this quantity is 0. On the contrary, if m ≥ k i , then Z i ⊆ X k i ⊆ X m , and Y i ∩ X m \ X k i = (Y i \ X k i ) \ (Y i \ X m ),
so that:

P (W i |X m ) = |Y i ∩ X m \ X k i | + |Z i ∩ X m | |X m | = |Y i ∩ X m \ X k i | + |Z i | |X m | = |Y i \ X k i | -|Y i \ X m | + ε |Y i | -|Y i \ X k i | |X m | ≤ max m∈N | ε |Y i | | -|Y i \ X m | |X m | < δ by hypothesis.
Taking the limit, we get that µ (Xn) (W l ) < δ. On the other hand, applying now Point 1 of Lemma 4.7 to sequence (Y n ):

µ (Yn) (W l ) ≥ lim i∈N max m∈N P (W l i |Y m ) ≥ P (W l i |Y l i ) = ε .
The previous lemma now allows to characterize the main properties of interest for comparing two Besicovitch submeasures. Proposition 4.9. Let (X n ) and (Y n ) be nondecreasing and exhaustive.

1. µ (Yn) is λ-Lipschitz with respect to µ (Xn) , where λ > 0, if and only if

∀ε > 0, lim inf n→∞ max m∈N |Y n | -1 ε |Y n \ X m | |X m | ≥ 1 λ .
2. µ (Yn) is absolutely continuous with respect to µ (Xn) if and only if it is Lipschitz.

3. µ (Yn) ≤ µ (Xn) if and only if (Y n ) (X n ). 4. µ (Yn) = µ (Xn) if and only if (Y n ) ∼ (X n ).
One can even see from the proof that (Y n ) (X n ) if and only if there exists

ε ∈]0, 1[ such that ∀W ⊂ G, µ (Xn) (W ) < ε =⇒ µ (Yn) (W ) < ε.
Proof.

1. Just note that the λ-Lipschitz property of µ (Yn) is equivalent to the properties in Lemma 4.8, for every δ and ε = λδ, and hence to:

lim inf n∈N max m∈N |Y n | -1 ε |Y n \ X m | |X m | ≥ 1 λ .
2. From Lemma 4.8, µ (Yn) is absolutely continuous with respect to µ (Xn) if and only if

∀ε > 0, lim inf n→∞ max m∈N |Y n | -1 ε |Y n \ X m | |X m | > 0 .
From Point 1, this is equivalent to the existence of some λ such that µ (Yn) is λ-Lipschitz with respect to µ (Xn) .

Consider a sequence (m

n ) which witnesses that (Y n ) (X n ): lim n→∞ |Yn∆Xm n | |Yn| = 0. Then lim n∈N |Y n | -1 ε |Y n \ X mn | |X mn | = lim n∈N |Y n | |X mn | 1 - 1 ε lim n∈N |Y n \ X mn | |Y n | = 1 .
We can conclude by Point 1. Conversely, suppose that

lim inf n∈N |Y n | -1 ε |Y n \ X mn | |X mn | ≥ 1 .
By the last inequalities in Lemma 4.8, we know that lim n∈N

|Yn| |Xm n | = 1. Moreover, lim n→∞ |Y n \ X mn | |X mn | ≤ lim n→∞ ε |Y n | |X mn | -ε lim inf n∈N |Y n | -1 ε |Y n \ X mn | |X mn | = ε -ε = 0 . By Point 3 of Proposition 4.1, we obtain that (Y n ) (X n ).
4. This is direct from the definitions and the Point 3.

The following is direct from Proposition 4.9 and Remark 2.3.

Corollary 4.10. Let (X n ) and (Y n ) be nondecreasing and exhaustive. Then

(Y n ) (X n ) (resp. (Y n ) ∼ (X n ))
if and only if the identity map from space A G endowed with d (Xn) onto space A G endowed with d (Yn) is 1-Lipschitz (resp. an isometry).

Here are particular classes of sequences, where the proposition can be applied.

Corollary 4.11. Let (X n ) and (Y n ) be nondecreasing and exhaustive.

1. If there exist a real number λ > 0 and a sequence (m n ) such that lim inf n→∞ P (X n |Y mn ) ≥ 1 λ and X n ⊂ Y mn , then µ (Xn) is λ-Lipschitz with respect to µ (Yn) .

2. If for cofinitely many n ∈ N, Y n ⊂ X n+1 and lim inf n→∞ P (X n |X n+1 ) ≥ λ, then µ (Xn) is λ-Lipschitz with respect to µ (Yn) .

3. On the other hand, if

|X n | ∼ n→∞ |Y n | but (X n
) and (Y n ) are not (synchronously) Følnerequivalent , and n (Ym) (X n , ε n ) = n + 1 for some real sequence (ε n ) converging to 0, then µ (Xn) is not absolutely continuous with respect to µ (Yn) .

Proof.

1. For every ε > 0, lim inf

n→∞ max m∈N |X n | -1 ε |X n \ Y m | |Y m | ≥ lim inf n→∞ |X n | -1 ε |X n \ Y mn | |Y mn | = lim inf n→∞ |X n | |Y mn | ≥ 1 λ .

Apply

|X n | -1 ε |X n \ Y m | |Y m | ≤ max |X n | -1 ε |X n \ Y n | |Y n | , ε n .
Putting things together, lim inf n→∞ max m∈N |Xn|-1 ε |Xn\Ym| |Ym| is 0. We conclude by Point 2 of Proposition 4.9. 2. µ (Y ln ) = µ (X ln ) , for every increasing sequence (l n ) ∈ N N .

3. µ (Y ln ) is absolutely continuous with respect to µ (X ln ) , for every increasing sequence (l n ).

Proof.

=⇒ 2 By Remark 4.3, synchronous Følner equivalence is transmitted to all subsequences (provided that one takes the same subsequence for (X n ) and for (Y n )). We conclude thanks to Proposition 4.9.

=⇒ 3 This is obvious.

=⇒ 3 If (X n ) and (Y n ) are not synchronously Følner-equivalent, then there exists an infinite set I ⊂ N and a real number α > 0 such that ∀n ∈ I, |Xn∆Yn| |Xn| ≥ α. This implies that for every increasing sequence (l n ) ∈ I N , (X ln ) and (Y ln ) are not synchronously Følner-equivalent. We can take an increasing sequence (l n ) ∈ I N such that n (Ym) (X ln , ε ln ) = l n+1 , for some real sequence (ε n ) converging to 0. Then (X ln ) and (Y ln ) satisfy the assumptions for Point 3 of Corollary 4.11.

Shift

If G is a group and (X n ) ∼ (gX n ), then we say that (X n ) is (left) g-Følner. Since |X n | = |gX n |, Proposition 4.5 says that it is enough to require (X n ) (gX n ), and that in this case, (X n ) and (gX n ) are synchronously Følner-equivalent.

A (left) Følner sequence for a countable group G is a g-Følner sequence for every g ∈ G. A countable group is amenable if and only if it admits a Følner sequence: cf. [CSC10, Chapter 4], in particular for many alternative definitions.

A group G is finitely generated (briefly, f.g.) if E G exists such that for every g ∈ G there exists e 1 , . . . , e n ∈ E ∪ E -1 such that e 2. This comes from Corollary 4.12.

3. This comes from Point 2 and the characterization of amenability through Følner sequences.

There are nondecreasing non-Følner sequences for which the shift is Lipschitz (but not an isometry) in Z d . Here's an example: X n = ( -n, n ∪ 2 -n, n ) d . Indeed, for every n, 1 + X n ⊂ X 2n and |X

Propagations and right Følner sequences

Let G be a group and let g ∈ G. A sequence (X n ) of finite subsets of G is right g-Følner if (X n ) ∼ (X n g); equivalently, if (X -1 n ) is left g -1 -Følner. A right Følner sequence is then a sequence which is right g-Følner for every g ∈ G.

Let now A be an alphabet. The propagation in direction g ∈ G is the function π g : A G → A G defined by π g (x)(i) = x(ig -1 ) for every x ∈ A G and i ∈ G. With this definition, the value of π g (x) at point ig equals the value of x at point i: that is, the information moves in direction g. Points 1, 2 and 3 of Corollary 4.13 can then be dualized to right Følner sequences and propagations:

1. A nondecreasing exhaustive sequence of finite subsets of a group G is right Følner if and only if all of its subsequences yield a Besicovitch pseudodistance for which every block map is continuous.

2. A finitely generated group is amenable if and only if it admits a nondecreasing exhaustive sequence (X n ) of finite subsets such that, for every k ≥ 1 and every increasing (l n ) ∈ N N , every block map with neighborhood size k is k-Lipschitz with respect to d (X ln ) .

Conclusions

We have presented a way to compare Besicovitch submeasures (in terms of absolute continuity, Lipschitz continuity, equality) thanks to the sequences of finite sets which describe them. In a shift space (with respect to a countable group) endowed with the Besicovitch topology, we have derived conditions on the defining sequence for the shift maps to be continuous, Lipschitz or isometric. As part of this, we gave another characterization of amenable groups.

Possible future work could involve extension to configuration spaces on possibly uncountable groups. This would require the use of the more general notions of directed set and of net, and although the definition of Besicovitch pseudodistance and submeasure would be immediate to extend, the techniques used to prove the main lemmas could need a major revision.

  Overall for every m ∈ N, we get |X n ∆Y n | ≤ |X n ∆Y m |+||Y m | -|Y n ||. If we apply this with (m n ) the subsequence from the definition of , which is such that (X n ) ∼ (Y mn ), we have |X n ∆Y mn | = o n→∞ (|X n |), and by Proposition 4.1 (applied to (X n ) and (Y mn )), |Y mn | ∼ n→∞ |X n | ∼ n→∞ |Y n |. Summing up, we deduce that |X n ∆Y n | = o n→∞ (|X n |).

  Corollary 4.12. Let (X n ) and (Y n ) be nondecreasing and exhaustive. Assume that |X n | ∼ n→∞ |Y n |. Then the following are equivalent. 1. (X n ) and (Y n ) are synchronously Følner-equivalent.

  2n | |Xn| = (8n-1) d (4n-1) d , which converges to 2 d when n goes to infinity. We conclude by Point 1 of Corollary 4.11, with m n = 2n and α = 2 d . But the shift is not an isometry because the sequence is not Følner: µ((2Z) d ) = 2 d /3 d > µ((2Z + 1) d ) = 1/3 d .

  Let us start by proving the final inequalities. Suppose lim inf n∈N Then on the one hand, it is clear that lim inf n∈N ε|Yn| |Xm n | is even bigger, which gives the first inequality. On the other hand, since |Y n \ X mn | ≥ |Y n | -|X mn |, we can see that lim inf n∈N (ε-1) Yn

				ε|Yn|-|Yn\Xm n | |Xm n |	≥ δ.
	Xm n	+1 ≥ lim inf n∈N	ε|Yn|-|Yn\Xm n | |Xm n |	≥ δ, which gives that lim sup n∈N	|Yn|

  Point 1 with m n = min { m ∈ N| X n ⊂ Y m }; the hypothesis is that m n is ultimately n + 1. 3. Suppose |X n | ∼ n→∞ |Y n | and (X n ) and (Y n ) are not synchronously Følner-equivalent. By Proposition 4.5, (X n ) (Y n ), that is, ε = lim sup n→∞By the second assumption, for every m > n, X n \ Y m = ∅ and |Xn| |Ym| ≤ ε n . We get:

			|Xn\Yn| |Yn|	> 0. We can write
	lim inf n→∞	|Xn|-1 ε |Xn\Yn| |Yn|	= 0.
		max m∈N

  • • • e n = g. Remarkably (cf. [Pet, Lemma 5.3]) if a f.g. group is amenable, then it has a nondecreasing exhaustive Følner sequence. In addition, if the size of the balls grows polynomially with the radius, then they form a Følner sequence, so Point 3 of Corollary 4.13 generalizes [HM17, Cor 4.1.4]. The following is a rephrasing of Corollary 4.10. The first point generalizes [HM17, Prop 4.1.3]. Note that it still applies in nonamenable groups, but the shifts are no longer isometries, and there is a subsequence of balls with respect to which the Besicovitch pseudodistance makes them non-continuous. We remark (cf. [dlH00, VII.34]) that the sequence of balls is Følner if and only if the group has polynomial growth, and has a Følner subsequence if and only if it has subexponential growth. If E is the generating set and E n the corresponding radius-n ball, then E 0 = {e} where e is the identity of G and E

	Proof.
	1.

Corollary 4.13. Let G be a countable group and let (X n ) be a nondecreasing exhaustive sequence. n+1 = (E ∪ E -1 ) • E n , so |E n | ≤ (2 |E| + 1) n . We can apply Point 2 of Corollary 4.11.

† This research was supported by the Estonian Ministry of Education and Research institutional research grant no. IUT33-13.

Corollary 4.15. Let G be a group. 1. A nondecreasing exhaustive sequence (X n ) is right g-Følner if and only if µ (Xn) = µ (Xng -1 )

if and only if the propagation in direction g is an isometry.

2. A nondecreasing exhaustive sequence is right Følner if and only if every propagation is an isometry.

3.

A finitely generated group is amenable if and only if there exists a nondecreasing exhaustive sequence (X n ) of finite subsets of G such that every propagation is an isometry.

Proof. The first equivalence of Point 1 is immediate. For the other one, given x ∈ A G , let x(i) =

x(i -1 ) for every x ∈ A G and i ∈ G: then for every x, y ∈ A G and g ∈ G it is x = x, ∆(x, y) = (∆(x, y)) -1 and π g (x) = σ g (x), thus also

), so that the propagation in direction g is an isometry for d (Xn) if and only if the shift by g is an isometry for d X -1 n . Points 2 and 3 follow easily.

Block maps

A block map on a group G with source alphabet A, target alphabet B, neighborhood N = {j 1 , . . . , j k } and local rule φ :

defined as the synchronous application of φ at the "N -shaped neighborhood" of each point of the group: that is, for every

. By the Curtis-Lyndon-Hedlund theorem [START_REF] Hedlund | Endomorphisms and automorphisms of the shift dynamical system[END_REF] (see also [CSC10, Chapter 1]), block maps are all and only those functions from A G to B G which are continuous in the prodiscrete topology and commute with all the shifts. Every propagation is a block map, but the shift by g ∈ G is a block map if and only if g is central in G, that is, gh = hg for every h ∈ G; in this case, σ g = π g -1 . Note that the local rule φ itself can be identified with a block map Φ with source alphabet A k , target alphabet B, and neighborhood N = {e}, where e is the identity element of G. Such a function is surely 1-Lipschitz, but not necessarily an isometry: for example, φ could be constant. Block maps can be defined equivalently as follows. For f 1 , . . . , f k :

Then a block map F with source alphabet A, target alphabet B, neighborhood N = {j 1 , . . . , j k } and local rule φ has the form

), where Φ is as in the previous paragraph.

Lipschitz with respect to d (Xn) . In particular, if α q = α for every q ∈ [1 : k], then f is kα-Lipschitz, and if each f q is an isometry, then f is k-Lipschitz.

Proof. For every x, y ∈ A G and i ∈ G, we have f (x Corollary 4.17.


Marie Masson
email: marie.masson@orange.com

Zwi Altman
email: zwi.altman@orange.com

Eitan Altman
email: eitan.altman@sophia.inria.fr

Multi-User collaborative scheduling in 5G massive MIMO heterogeneous networks

Keywords: Collaborative scheduling, Small Cells, densification, Massive MIMO, Multi-User MIMO, 5G

Macro cell densification with Small Cells (SCs) is an effective solution to cope with traffic increase. To fully benefit from the additional SCs capacity, interference mitigation techniques are needed. Densification in 5G networks with Massive Multiple Input Multiple Output (M-MIMO) deployment needs to rethink interference mitigation to account for highly focused beams and Multi-User (MU) scheduling. This paper presents a low complexity collaborative Proportional Fair (PF) based scheduling that maximizes the throughput and improves fairness of the heterogeneous network. The solution is based on the calculation of a loss factor indicator that each SC provides to the macro cell at each scheduling period. These indicators allow the macro cell MU scheduler to efficiently select the set of users for scheduling, leading to a significant improvement in performance. Numerical results illustrate the interest of the collaborative solution.

I. INTRODUCTION

5G targets a significant leap forward in user experience in terms of data rates, latency, support of very high speed and massive connectivity [START_REF] Elayoubi | 5G innovations for new business opportunities[END_REF]. Enhanced user throughput and network capacity can be achieved thanks to 5G technologies such as M-MIMO and SC densification [START_REF] Jungnickel | The role of small cells, coordinated multipoint, and massive MIMO in 5G[END_REF] [START_REF] Bhushan | Network densification: the dominant theme for wireless evolution into 5G[END_REF].

M-MIMO enhances Signal to Interference plus Noise Ratio (SINR) using beamforming. It allows better focusing of the radiated power on the user, reduced interference generated on neighboring cells, and spacial multiplexing of users known as Multi-User MIMO (MU-MIMO). However, significant interference can occur at cell edge in macro cells with M-MIMO deployment, or when SCs are deployed within the macro cell coverage. In this case, interference mitigation techniques are necessary, some of which are briefly summarized presently.

In 4G, the enhanced Inter Cell Interference Coordination (eICIC) feature was introduced to enhance capacity and mitigate interference in heterogeneous networks with SCs deployment [START_REF] Wang | Performance analysis of enhanced intercell interference coordination in LTE-Advanced heterogeneous networks[END_REF] [START_REF] Tall | Self organizing strategies for enhanced ICIC (eICIC)[END_REF]. The interference reduction is obtained by means of the Almost Blank Subframe (ABS) feature that mutes almost all macro Base Station (BS) transmissions on a certain portion of the subframes, thus letting SCs serve their users with reduced interference. However with M-MIMO, only part of the users are served simultaneously by the focused beams, thus making ABS of limited use.

Interference mitigation can be fully performed in the physical layer via more complex transceivers with advanced precod-ing. The BS can then precode the Down Link (DL) signals for its users while being orthogonal to the dominating subspace of the interfering signals from SCs [START_REF] Hosseini | Massive MIMO and small cells: How to densify heterogeneous networks[END_REF].

Interference between a macro cell and SCs can be minimized using Joint Processing (JP) Coordinated Multipoint transmission (CoMP) [START_REF] Irmer | Coordinated multipoint: Concepts, performance, and field trial results[END_REF]. This scheme has been studied in the framework of heterogeneous networks with M-MIMO deployment [START_REF] Jungnickel | The role of small cells, coordinated multipoint, and massive MIMO in 5G[END_REF]. The CoMP approach imposes strict requirements on the network such as synchronization between cooperating cells, high backhaul capacity and low latency transmissions which impact network cost.

The purpose of this paper is to propose a low complexity collaborative scheduling for a M-MIMO cell with SCs in its coverage area. It is assumed that the macro cell utilizes Grid of Beams (GoB) [START_REF] Vook | MIMO and beamforming solutions for 5G technology[END_REF] for the control channels. At each Transmission Time Interval (TTI), each SC sends a signal comprising a single number to the macro cell. The received signals are used by the macro cell MU scheduler to maximize a global PF utility of the heterogeneous cell and to mitigate the interference that the macro cell produces. It is noted that the virtualization of the 5G Radio Access Network (RAN) motivates this approach. The Media Access Control (MAC) layer is expected to be virtualized within a centralized data center or a Mobile Edge Computing (MEC), thus simplifying the exchange of information between network nodes and alleviating requirements on the backhaul and associated costs.

The paper is organized as follows. Section II presents the system model. Section III describes the scheduling algorithms including the macro cell MU scheduling under beam-skipping constraints, and the collaborative PF scheduling. Numerical results are presented in Section IV followed by concluding remarks in Section V. Throughout the paper, the terms pico cell and SC have the same meaning and are used interchangeably.

Notation: Scalars are denoted by lowercase italic letters a, vector columns are presented in bold lowercase letters a and matrices are denoted by bold uppercase letters A. a denotes a time average and H the hermitian transpose. card() denotes the cardinality.

II. SYSTEM MODEL

Consider a network with tri-sectorial sites with M-MIMO system in the DL. GoB is used for control, including initial access and synchronization and defines the macro cell area. BS data is served using Time Division Duplex (TDD) with Maximum Ratio Transmission (MRT) beamforming [START_REF] Tse | Fundamentals of wireless communication[END_REF]. It is noted that the collaborative scheduling is independent of the beamforming implementation, and can be directly applied also to Frequency Division Duplex (FDD).

Each sector m is equipped with a Large Scale Antenna System (LSAS) with N = N x × N z radiating elements and is serving mobiles, each with one receiving antenna [START_REF] Tall | Multilevel beamforming for high data rate communication in 5G networks[END_REF]. Pico cells with omnidirectional antennas are deployed at hotspot zones in order to offload the macro cell traffic and thus increase the cell capacity, as shown in Fig. 1. Neighboring interfering cells are omitted. Fig. 1b presents the coverage area, namely the best server map. The color code is used for visualization purpose only.

c m u = h m u Γ, (1)
where Γ is a normalizing factor such that ||c m u || 2 = 1 k . We denote by σ the thermal noise.

Users with elastic traffic arrive in every cell according to a Poisson process. Each user downloads a file and leaves the cell afterwards. The size of the file varies according to a Gaussian distribution.

The interference created by a pico cell p on the user u is written as:

I p u = p p |g p u | 2 (2)
The interference generated by a macro cell m on u reads:

I m u = p m u ∈m ,u =u |(h m u ) H c m u | 2 (3)
We can express the SINR of a user u from a macro cell m [11] [START_REF] Hosseini | Massive MIMO and small cells: How to densify heterogeneous networks[END_REF]:

S m u = p m |(h m u ) H c u )| 2 p∈P I p u + m I m u + σ 2 (4)
The SINR S p u of user u attached to the pico cell p can be written as:

S p u = p p |g p u | 2 p =p I p u + m I m u + σ 2 (5)

III. MU SCHEDULING

In this section, we consider the PF scheduling framework for both pico cells and macro cells. At each time slot t M the macro cell serves simultaneously up to k users. At most one user attached to a control beam b, denoted as active user, can be selected by the MU-scheduler. Denote by B k the set of control beams having active users with |B k | ≤ k. We first describe the concept of beam skipping. We then assume that B k is given and derive the PF based scheduling utility function for the macro cell and the SCs [START_REF] Combes | Scheduling gain for frequency-selective Rayleighfading channels with application to self-organizing packet scheduling[END_REF]. Then we present the MU collaborative scheduling for the heterogeneous cell which relies on a selection algorithm for B k .

A. Beam skipping

Beam skipping is a beam selection technique used by the scheduler to optimize a Quality of Service (QoS) or a performance utility by reducing inter-beam interference. It is noted that beam skipping technique can be applied to both duplexing modes, TDD and FDD. Each User Equipment (UE) is attached to the control beam of the GoB providing it with the best SINR. The user attachment provides additional spatial information that is exploited by the scheduler to mitigate interbeam interference: (i) by avoiding scheduling of two users attached to the same control beam, and (ii) by avoiding the scheduling of two users attached to adjacent beams of the GoB.

Given a performance utility, we can select a set of candidate UEs from a list while complying with a beam skipping constraint as follows. We select the top-ranked candidate UE, and remove the UEs attached to the same control beam and the adjacent ones from the candidate list. We repeat these two operations until we have selected k candidates or until the set of candidates is empty.

B. Macro cell utility

Denote by R b u,t M the rate of user u attached to the beam b at time t M , and by R b u,t M the average rate of user u attached to beam b. The average rate at t M +1 is calculated using exponential moving average (or Abel average) with a small parameter [START_REF] Combes | Scheduling gain for frequency-selective Rayleighfading channels with application to self-organizing packet scheduling[END_REF].

R u,t M +1 = (1 -)R u,t M + R u,t M +1 (6)
Let B be the set containing all the beams b of the GoB of the macro cell m. We assume fading of different users is independent and for a given user, fading is independent at different allocation time t M . While fading is assumed fixed during the transmission period, the coherence time is supposed not greater than t M +1 -t M . Denote by U m (t M ) the part of the utility function that depends on the past scheduling steps up to time t M , and by ω m the part that depends on the scheduling at time t M +1 and on the selected subset B k . We assume for the moment that B k is given. The resulting utility is given by ( 7)-( 9) [START_REF] Combes | Scheduling gain for frequency-selective Rayleighfading channels with application to self-organizing packet scheduling[END_REF]:

U m (t M +1 ) = U m (t M ) + ω m (t M +1 ) (7)
where

U m (t M ) = b∈B u∈b (log(R b u,t M + d) - R b u,t M R b u,t M + d ) (8) ω m (t M +1 ) = b∈B k max u∈b ( R b u,t M +1 R b u,t M + d ) (9)

C. Pico cell utility

Similarly to the macro cell, we define the pico cell utility using the terms U p and ω p :

U p (t M +1 ) = U p (t M ) + ω p (t M +1 ) (10)
where

U p (t M ) = u∈p (log(R p u,t M + d) - R p u,t M R p u,t M + d ) (11)
ω p (t M +1 ) = max u∈p ( R p u,t M +1 R p u,t M ) (12)

D. Collaborative scheduling

We define the global utility of the heterogeneous cell, U global as the sum of utilities of the macro-and pico cells in its coverage area as defined in the previous two subsections. The collaborative scheduling aims at optimizing U global under the beam skipping constraint at each time step. The optimization problem reads: maximize

B k ∈B U global (t M +1 ) = U m (t M ) + p∈P U p (t M ) + ω m (t M +1 ) + p∈P ω p (t M +1 ) (13) subject to ∀(b i , b j ) ∈ B k , |i -j| ≥ 2
The problem (13) is a complex combinatorial optimization problem. The solution aims at maximizing the global throughput in a fair manner. A heuristic solution is proposed to allow real-time solution compatible with operational systems.

The scheduling decision for the time slot t M +1 impacts U global via the terms ω m (t M +1 ) and ω p (t M +1 ). For sake of clarity, we denote by δ b the utility gain term obtained by scheduling the macro cell user attached to the control beam b having the best PF criterion. The contribution of the beam b to the term ω m (t M +1 ) is written as follows:

δ b = max u∈b R b u,t M +1 R b u,t M + d (14)
Due to the small pico cells' size, we assume that a pico cell is located within the coverage area of one control beam of the GoB, and is interfered by the beam (denoted hereafter as interfering beam) scheduled to serve a macro cell UE attached to that control beam. The interfering beam comprizes the dominant contribution of the interference of a pico cell UE.

The interference experienced by pico cells' UEs from neighboring macro cells are taken into account while inter-pico cell interference is very low and is therefore neglected. When activated, the interfering beam reduces the rate of pico cell p and hence its utility given by [START_REF] Combes | Scheduling gain for frequency-selective Rayleighfading channels with application to self-organizing packet scheduling[END_REF]. The idea of the collaborative scheduling is to take into account this utility reduction by the macro cell PF scheduler in order to optimize the global utility U global .

The pico cell's UE u estimates the two following values: R p,I u,t M +1 , the rates received if its interfering beam is active and R p,N I u,t M +1 , the rate received otherwise (the superscripts I and N I stand for Interfered and Not Interfered, respectively). One of the two rates is calculated using actual received signals (which depend on the status of the interfering beam). The other one (denoted as the complement rate) is estimated as follows: samples of the interference signals in the presence and in the absence of the interfering beam are measured and stored once, and their average value is computed. Given the interference signal, the UE performs a simple test (e.g. comparison to a threshold or a Likelihood ratio test) and infers the status (active or inactive) of the interfering beam. The UE can then provide an estimate for the complement rate using the corresponding stored averaged interference value. These values are sent to the pico cell.

We define the quantity δ p as the loss factor of pico cell p associated with the activation of its interfering beam. It is calculated as the difference between the PF criteria with and without the activation of the interfering beam:

δ p = max u∈p ( R p,I u,t M +1 -R p,N I u,t M +1 R p u,t M ) (15)
This loss factor is transmitted to the macro cell scheduler by the different pico cells. We define the quantity ∆ b in (16) that the BS calculates to assess the contribution of b to the global utility taking into account the corresponding loss factor δ p :

∆ b = δ b + δ p (16)
We calculate ∆ b for all the beams. We proceed and derive the set B k using the ∆ b -s and the beam skipping constraint (Section III-A), as described in Algorithm 1. The algorithm modifies the macro cell PF selection criterion to account for the pico cell loss factors. Once the set B k is known, the user selection for the macro cell becomes straightforward. The pico cells' scheduler remain unchanged and is performed independently. It is recalled that each beam b serves at most one user at a time which is selected using a standard PF criterion applied to the users covered by that beam. Finally, the complexity of the algorithm is O(N users ), where N users is the total number of users in the heterogeneous cell.

IV. NUMERICAL RESULTS

A. Simulation scenario

Consider the network model of Section II, comprising a central sector with 10 pico cells (see Fig. 1), surrounded by 18 interfering sectors placed over a hexagonal grid. The performance results are extracted from the central sector. We compare the collaborative MU scheduling presented in Section III-D to a baseline without collaboration, namely the macroand pico cells schedule their users independently according to the PF criterion δ b given by ( 14). The simulation parameters are summarized in Table I.

B. Performance evaluation

We first compare the Mean User Throughput (MUT) in the macro cell and the pico cells for a fixed λ m and for different λ p (see Fig. 2). The load of the pico cells varies between 75 and 85 percent for λ p equals 3 and 4 users/sec/cell respectively. The MUT gain achieved by the collaborative scheduler with respect to the baseline varies from 4 to 20 percent, with bigger gain for higher pico cell traffic. As the pico cell traffic increases, so does the number of users in the pico cell. Therefore, the more users benefit from the muting of a beam. Furthermore, unlike in 4G network, the spatial granularity of the muting is smaller: in a 4G network, either the whole macro cell is muted or it is not. Here, muting a beam means that other users in the macro cell, attached to different control beams, can still be served, allowing higher gains.

Fig. 2: MUT in the macro cell and its attached pico cells Fig. 3 presents the CETs in cell 5 (see Fig. 1) as a function of the users' arrival rate in this cell. Here as well, the CET gain increases with the users' arrival rate. A throughput gain of around 17 percent with respect to the baseline is achieved, from 3.4 users/sec/cell and above.

The time variations of the filtered MUT and the CET are depicted in Figures 4 and5 respectively. Performance gain is achieved for both MUT and CET using the collaborative scheduling, while the latter is particularly important: around 2 Mbps for the baseline and 2.4 Mbps and above for the collaborative scheduling.

V. CONCLUSION

This paper has presented a collaborative scheduling technique to manage 5G heterogeneous network with M-MIMO macro cells and pico cells deployment. The solution is based on exchanging a loss factor that each pico cell provides to the macro cell, that estimates the performance utility loss due to the macro cell scheduling. While the optimization of MU scheduling is a combinatorial problem, it is shown that the the exchange of the loss factor allows to design a very low complexity scheduling algorithm.

The collaborative scheduling provides throughput gain that grows with the increase of traffic demand. In the simulations, the MUT gain of up to 20 percent is obtained for the heterogeneous cell comprising the macro-and pico cell. The proposed solution has been developed for TDD system. The solution is simpler for FDD system since the same beams are used for the transmission of both control and data signals.

  Fig. 1: Network model

Algorithm 1

 1 MU Beam Selection Init: B k = {}, B candidates = {b ∈ B|∃u ∈ b} for all p ∈ P do Compute loss factor δ p using (15) Send δ p to macro cell m end for for all b ∈ B candidates do Compute gain factor δ b using (14) if ∃p ∈ P interfered by user attached to b then ∆ b ← δ b + δ p else ∆ b ← δ b end if end for while card(B k ) < k or B candidate = ∅ do b select ← argmax b∈B candidates ∆ b B k ← B k ∪ b select Define N (b select ) the set containing b select and its adjacent beams B candidates ← B candidates \N (b select ) end while

Fig. 3 :Fig. 4 :

 34 Fig. 3: Cell-Edge Throughput (CET) in pico cell 5

TABLE I :

 I Network and Traffic characteristics

	Network parameters
	Number of macro BSs m	1
	Number of beams b in the GoB	16
	Number of pico BSs p	10
	Number of interfering macros	3x6 sectors
	Intersite distance	500 m
	Bandwidth	20 MHz
	Channel characteristics
	Thermal noise	-174 dBm/Hz
	Macro Path Loss (d in km)	128.1 + 37.6log 10 (d) dB
	Pico Path Loss (d in km)	140.7 + 36.7log 10 (d) dB
	Traffic characteristics
	Macro users' arrival rate λm	3.5 users/sec/cell
	Pico users' arrival rate λp	[3, 3.4, 3.8, 4] users/sec/cell
	Macro/pico traffic spatial distribution	Uniform
	Service Type	FTP
	Average file size	5 Mbits


Alexis Ferrand

RECIPROCAL APPROBATION AND THE FORMING OF PUBLIC OPINION

Based on P.Blau approach of social exchange, we define the approbation an actor can give to the judgments and opinions of another actor as a resource exchangeable among other resources in a multiplex relation. That communication is an essay to introduce the production of shared opinions in sociology of exchan

PUBLIC POLICY AND OPINIONS ON THE HEALTH SYSTEM

The regulation of health systems is a major issue in all European countries. It implies controls on the quality and accessibility of care, on the efficiency of organizations, and on the amount of financial resources used 1 . Three major types of regulation exist: 1) Formal controls exerted by the public health administration and/or by health insurance (public or private) which are a top down regulation.

2) Formal controls exerted by professional associations which are horizontal control. E. Friedson (1963) has shown that the "processes of control in a company of equals" can be weak. 3) Control is also exerted by the public in two ways: first, as patients or clients when they choice a practitioner; second when individuals are invited by the state, as consumers or citizens, to take part in health organisation boards, or in regional consultations to sit priorities for public health policy. It is a down top regulation.

Regulation by individuals implies that they can have opinions and judge their local or regional health system. This is an integral part of their behavior as clients -in an open system -when they decide to consult such or such practitioner or not to go to the local hospital and of their behavior as citizen when they participate in public consultations. The forming of opinions on health system implies that peoples evaluate and judge various dimensions of the quality of care. This is not simple task: 1) due to the asymmetry of knowledge about the technical content of medical practice and to the fundamental uncertainty of medical "art"; 2) due to the difficulty of testing and comparing quality of several practitioners.

Personal evaluation of the local health system is undermined by uncertainty. E. Freidson (1960) has suggested that, to minimize that uncertainty, people should exchange information and form their opinion about practitioners and medical care through "lay referral systems", meaning a subset of their personal network.

If one is interested by the role played by the public in the regulation of health systems, it is of the utmost importance to understand how people form their opinions on it. Based on Freidson 's ideas, a recent research has shown the importance of discussion networks about health issues to help people to form an opinion: the proportion of dubious or uncertain people decreases dramatically when they have at least two presons with who they are able to discuss these issues (A.Ferrand, 2000(A.Ferrand, , 2001)).

The next question, addressed in this paper, is how actors reach the point where they share common opinions, and we propose a model which links social exchanges and reciprocity with processes of cognitive and evaluative exchange involved in the formation opinions.

THEORIES EXPLAINING HOW ACTORS DEVELOP COMMON OPINIONS

Opinions are judgments which imply evaluations. The domain where opinions are pertinent is the human and social world. Having an opinion about the physical world has little meaning. Opinions define the relation of individuals to the social world. Linked to underlying representations, they are a basis of potential and actual actions (S. Moscovici,1986). They are the first level of engagement of individuals as willing actors in the social world, even if an actor is constrained to act against his opinion, or if an actor's engagement is weak. As an expression of values and norms opinions are a basis of human interaction and collective action.

The process of formation of common opinions was explained by various theory.

Holist theory: Socialization processes constraint actors to interiorise collective norms and values of the social group to which they belong. Common opinions are formed at the level of the group, and are "sui generis" 2 and precede the individual process of opinion formation. But in this framework the individual changes of opinions are difficult to define and explain.

Others theories explain how actors form an opinion, and eventually change their opinions.

Methodological individualism: R.Boudon (1997) explains collective beliefs3 by a trans-subjective process. Separate actor thinks about an issue in the same way because they use the same logic. Actors who share the same material and social condition have many chances to develop # the same conclusion about the social world. R.Boudon states that " pour rendre compte des croyances collectives, il est bien souvent inopportun de faire appel à des hypothèses supposant un effet mécanique de forces sociales mal définies sur l'esprit de l'individu. Il suffit de comprendre les raisons que chaque sujet ou chaque individu idéal typique a d'endosser de telles croyances » (1997: 33) Psycho sociological influence theory is built on a process of communication: in one-way communication, one or several "senders" inform "receivers" of their opinions or judgments on an issue. Either by laboratory experiments or by surveys of the "real world", researchers show how asymmetry in number (majority / minority), in power, status, and competence drives the receivers to change their opinion.

An interactionist theory: the convergence communication model

One version of this model was presented by E.M.Rogers and D.L. Kincaid (1981). It is built on ideas of G.H.Mead 's interactionist theory and of G.Bateson 's systemic theory. The basic idea is that "information is inherently imprecise and uncertain, and that communication is a dynamic process of development over time" (p.44). Communication is a process of reciprocal exchange of information through which actors can reach both mutual understandings as divergent opinions (p.65). Communication is linked to social action and is purposeful. It "cannot be adequately studied without reference to the purpose of a social system" (p.62) because "information is a difference in matter-energy which affects uncertainty in a situation where a choice exists among a set of alternatives" (p.48). This type of theory is interesting because: a) it links action and cognition; b) it defines an exchange in which both actors contribute; c) it can lead to mutual approbation or to disagreement. I suggest a social exchange theory of the formation of common opinions elles des synthèses de toutes sortes, qui sont déterminés par leurs affinités naturelles et non par l'état du milieu au sein duquel elles évoluent. Par conséquent les représentations nouvelles, qui sont le produit de ces synthèses, sont de même nature: elles ont pour cause prochaine d'autres représentations collectives, non tel ou tel caractère de la structure sociale." Durkheim E. (1898, p.43) 3 Beliefs are not exacly the same cognitive contents as opinions, they tend to explain the world, where opinions tend to evaluate it. But we suppose that a similar paradigm can be used to explain opinions.

A SOCIAL EXCHANGE THEORY OF THE FORMATION OF COMMON OPINIONS

In his theory of social exchange, P. Blau (1964) begins by posing psychological postulates. One states that human beings act to receive gratifications from others and that they are anxious to receiving approbation of their decisions, actions, opinions, or suggestions, particularly when the question under discussion is uncertain and ambiguous (1964: 62). Approbation is a more-or-less explicit statement by which Alter expresses his agreement with Ego's opinions or behaviours.

Let us begin by a situation where Ego and Alter have not the same opinion. In many cases this dissensus has no consequences for the interaction, in others cases the situation is such that actors have to reach a minimum level of agreement. One or both have to change his / their mind(s). The dissensus about opinions on uncertain issues cannot be solved by a rational debate because, by definition, opinions involve arbitrary values and references. We suggest here that the dissensus can be solved through a process based on social exchange.

Indeed, in this circumstance, if Ego appreciates receiving Alter's approbation and wants that approbation, then: a) Approbation is a valued good and can be seen as a resource controlled by Alter; b) By definition, Ego is unable to obtain that resource by himself. He is obliged to obtain approbation from another person, from Alter. That resource exists only in a process of interaction, as the content of a relationship between two (or more) actors: it can only be developed in an exchange. c) When Ego receives approbation as a resource, he contracts a debt.

If one agree with these ideas, then arises the question of the possibility for an actor to reimburse that debt, and the theory of social exchanges provides answers to that question. d) Approbation can be introduced in a process of exchange. e) Ego can reimburse approbation received by approbation given, but also by another kind of resource.

f) The appropriateness of the resource used to reimbursment, the quantity of the returned resource used to reach a balance in exchanges are a matter of specific conventions between actors, since, in social exchanges, a general equivalent doesn't exist. P.Blau states "In contrast to economic commodities, the benefits involved in social exchange do not have an exact price in term of a single quantitative medium of exchange, which is another reason why social obligations are unspecific. It is essential to realize that this is a substantive fact, not simply a methodological problem. It is not just the social scientist who cannot exactly measure how much approval a given helpful action is worth; the actors themselves cannot precisely specify the worth of approval or of help in the absence of a money price. The obligations individuals incur in social exchange, therefore, are defined only in general somewhat diffuse terms. " (1964: 10) Thus, it should be difficult for the observer to describe equivalences established by actors between various resources to mach the reciprocity of their exchanges.

But an exchange is not only a flux of resources, it also a relationship between partners. The analysis of that other dimension of social exchanges can also be examined.

g) P. Blau introduces the distinction between intrinsic and extrinsic rewards. In a relationship, an intrinsic reward is totally dependant to the identity and particularity of the Alter who provides it. An extrinsic reward can be moreor-less detached from the individual idiosyncratic particularities of Alter. P. Blau classifies approbation as an extrinsic reward. "Extrinsic benefits are, in principle, detachable from the source that supplies them, but their detachability is a matter of degree. At one extreme are economic commodities, the significance of which is quite independent of the firm that supplies them. The value of a share in a corporation is not affected by the broker from whom we buy it. At the other extreme is the diffuse social support we derive in a love relationship, the significance of which depends entirely on the individual who supplies it. The typical extrinsic benefits socially exchanged, such as advice, invitations, assistance, or compliance, have a distinctive significance of their own that is independent of their supplier, yet an individuals preferences for them are also affected by his interpersonal relations with the supplier. " (1964: 95) h) That distinction is important because if approbation is an extrinsic reward, Ego can obtain it from various relationships. He has the possibility of choosing between alternative relations, and we can postulate that he choices to maintain those which are the more satisfying for him, those in which a better level of reciprocity is guaranteed. "In the long run, however, the explicit efforts the associates in a peer relation make in one another's behalf tend to be in balance, if only because a persistent imbalance in these manifestations of good win raise questions about the reciprocity in the underlying orientations of support and congeniality".

If the flux of resources exchanged for approbation is difficult to analyze, it is nevertheless possible to emphasize the kind of relationship in which reciprocity is possible, and which, for that reason are maintained. Now we shall present few results of an empirical study on the forming of opinions about local health system as an illustration of this approach.

THE KINDS OF RELATIONS IN WHICH PEOPLE SHARE COMMON OPINION

A survey was conducted in two cities in the North of France: Lens (37.000 inhabitants) and Tourcoing (100.000 inhabitants); 250 persons interviewed in both. In each city, two sub-samples were interviewed: a) bluecollar workers (men) and low-wages clerks (women); b) professionals and managerial staff (G. Cresson, A.Ferrand, P.Lardé, 2001) First, to capture the "lay referral system" of actors, we asked people to cite persons with whom they speak about three types of issues: 1) Personal health: "It can happen that you talk about your own health with personal acquaintances, family members, colleagues, friends… For example you discuss a disease you recently caught, drugs you take, a diet you go on, with someone who is not one of your physicians… During the last six months, did you discuss about your health with someone…" 2) A physician: "It can happen that you talk about a physician, remedies he prescribes, or care he takes of you… During the last six months, did you talk about a physician…" 3) Three diseases: " Finally, I am going to ask you if you talk about specific diseases… During the last six months, did you discuss one of theses diseases: a) cancer; b) heart troubles; c) nervous breakdowns…" We have asked for social characteristics of each person cited by respondents.

Secondly, we asked for the opinions of interviewees about the quality of treatment in the locality for the three illness: cancer, heart troubles, nervous breakdowns.

Third we have asked how interviewees perceive the opinions about the treatment of these illness of each person with who they have discussed these topics.

For each relation, we know if Ego perceives Alter as having the same opinion as him on the quality of local treatment of the three illness. Of course, these type of data don't allow us to disentangle who gives approbation to whom, to capture the orientation of the tie. Let us assume that when opinions of Ego and Alter are the same, some process of approbation has occurred. Some relations allow repeated approbation -noted as "A" -on each issue, and present the pattern "AAA" . Others avoid any kind of approbation and present repeated disagreement "DDD". Others mix the two patterns ( "AAD", "ADD").

Knowing some social characteristic of the person cited, it is possible to determine in what kind of relations approbation is more frequent. We have selected two basic properties: sex matching and role relationship.

If everybody can be more or less anxious about his own health, in French society women are practically the most involved in providing "profane" care and they play a major role in decisions about visiting a doctor or consulting a specialist in a clinic (G.Cresson, 1991(G.Cresson, , 1995)). We can say that they are more specialized than men in this domain, and that they have clearer ideas and opinions (although often necessarily built on gossip) about the local health system. We can then hypothesize that the process of reciprocal approbation in relations where a woman discuss with another woman, should not be the same as when she discusses with a man, or when two men discuss.

If approbation between Ego and Alter concerning opinions is a resource exchanged between actors, that kind of exchange can take a more-or-less important part in their relationship. At one extreme discussions about opinions can be the sole component of the relationship and actors get in touch only to discuss about these particular issues. It is a specialized relation. At the other extreme, discussions about opinions are a component of a multiplex or "multistrand" relation. Social support researches have shown that different kinds of resources are exchanged in different kinds of relations (B. Wellman, P.J.Carrington, A.Hall, 1988;C.S.Fischer, 1982;L.Freeman, 1997). Even the particular resource of approbation is exchanged through relations which are of different kind according to the issue discussed (A.Ferrand, L.Mounier, 1990). Thus we have to consider that relations are more or less specialized or multiplex at two level: a) relations mainly formed by discussions can allow cognitive and emotional exchanges on particular or various issues; b) relations can allow exchanges of a single kind of resource or of several kinds of resources (practical or financial help, emotional support, information and advice…).

In Peter Blau's theory, the possibility of offering approbation, and more fundamentally, compliance to Alters'willings, in exchange for practical resources received is the basis of emergent status differentiation and power. Regarding the balance of exchanges, multiplexity makes possible that more complex and sophisticated form of interaction were actors bargain at the same time in different domains, engaging several kind of resources, and being able to balance, for example, approbation given for practical help received. Then we can hypothesis that that the more multiplex a relation, the more global approbation it can offer.

Another important condition of exchange is the expectation of reciprocity. Peter Blau has proposed two (classic) conditions which allow an actor to anticipate reciprocation: interpersonal trust built on the history of a dyadic relation, and social control produced by the embededness of the relation in -at least -the elementary structure of a triad where a third party guarantees the fairness of return. Then we can hypothesis that relations which are embedded in a denser set of relations can sustain more complex exchanges, and offer more approbation.

The data do not provide a direct measure of multiplexity of exchanges or of the structural embededness of relations. We used as a proxy indicator the roles relationship crudely divided in three categories: "members of the family", "close friends", and "others" which bring together various questionnaire categories (colleagues, neighbor, co member, and other).

We performed a factorial analysis on the sample of relations cited by respondents to estimate how the degrees of approbation linked to various types of relations, defined by sex matching and role relationship. In a three dimensions analysis, the first two dimensions capture 32% of the "variance", which is not unusual for sociological data.

The global structure exhibited by the results is quite clear: Family relations occupies the left side, Friends and Others the right side.

Relations between different sexes are in the upper-left quadrant, same sex in the upper-right quadrant. Heterosexual relations are close to family ; same sex relations are in the quadrant of friendship for women, and of others for men. If we understand family and friends as strong multiplex relations , and others as weak specialized one, we identify a diagonal with weakness and specialization on the upper-right corner, and multiplexity in the opposite corner. Italic: main significations of the dimensions of the space (not variables introduced in the factorial analysis)

The higher degree of approbation ("AAA") is very close to family relations, and heterosexual ties ("ManWoman" and "WomanMan" . These two properties contribute also to the third dimension, each in opposite direction). In the kind of relations where exchanges are more multiplex (in family relations, various kinds of resources circulate: practical, emotional, informational, and so on) we found, as expected, the higher degree of reciprocal approbation.

A lower degree of approbation ("AAD") is in the quadrant of "Friends", and very close to "Woman-Woman" relations.

The first degree of disagreement ("DDA") is in the upper-right quadrant of "Others" relations, in the same direction as "ManMan" relations.

The highest degree of disagreement ("DDD") is close and exactly in same direction as "Others" relations.

As expected, relations in which various kind of exchanges are possiblemultiplex family relations -are more often those in which exchange of approbation are the more developed. On the contrary, more specialized ties (colleague, neighbour, co-member, others) are those in which approbation is the more rare, disagreement more frequent.

Same-sex discussion relations are also more often extra family relations, and present a lower degree of approbation: "AAD" for "WomanWoman", "ADD" for "ManMan" relations. In extra family relations, women are more "approbative" than men. More involved in health problems, women's discussion relations are more oriented toward concrete problem solving, and are also better able to reach a consensus.

On the contrary, more weak, specialized and public relations, are very often characterized by extensive disagreement between discussion partners. These results suggest an opposition between a private domain, realm of consensus, and a public sphere agitated by dispute and opposition.

These results are coherent with the global hypothesis presented. We do not interpret them as "verification" of this hypothesis, but as a credible illustration of the kind of approach proposed. The important point is that a model incorporating reciprocal approbation as an exchange process, dependant on the diversity of other exchanges involved in the same relation and allowing exchange of approbation against other kinds of resources and a global reciprocity, seems reasonable and pertinent for further exploration.

CONCLUSION

Approbation is most often seen as an expression of affective and emotional support or as an expression of status recognition. First, we have emphasized the cognitive contents of approbation. When the initial situation involves a dissensus, approval needs that one actor modifies his/her opinion, changes his/her mind.

Second, we have emphasized the fact that approbation is a resource which can be part of exchanges of others kind of resources.

In doing so we are encouraged to understand the changing of opinion not as a cognitive process externally constrained or influenced by the relationship Ego-Alter, but as a constituent of social exchanges, a component of the global process of exchanges which constitutes the relation itself.

Then, agreement between actors is not a normative pre-condition of others kinds of "fair exchanges", it is a part and an effect of the process of exchange Two limitations must be clearly set a) The exchange of approbation for another kind of resource is not presented here as an universal relational and cognitive process. It seems reasonable to think that deep representations and values cannot be "bargained" nor opinions about unambiguous issues.

b) The triadic (sociometric or structural) level of analysis -where the interdependencies between several relations in a same network are taken into account -is absent of the discussion of results presented.

Regarding the role of the public in the regulation of the health system, different conclusions can be proposed for the two main processes. When people acts as clients, consumers, in private life, the multiplex exchanges in family relations seem to produce reciprocal approbation and wide consensus, which prevent hesitation and reduce uncertainty. But more specialized and public relations of discussion about health generate systematic disagreement. If we generalize this result, we have to recognize that these latter relations, which are more susceptible to be involved in public discussions and official consultations of citizen, are less able to produce common opinions on the health system. Paradoxically, perhaps the mobilization of family relations will allow, in that domain, the emergence of common opinions as basis for public opinion and action in the political domain.

This is the theoretical line of Durkheim's continuators : "Une fois qu'un premier fonds de représentations s'est ainsi constitué, elles deviennent.. des réalité partiellement autonomes qui vivent d'une vie propre. Elles ont le pouvoir de s'appeler de se repousser, de former entre "Reciprocity as a Human Resource" Barcelona 09/2001 A.Ferrand Reciprocal approbation and the forming of public opinion

"Reciprocity as a Human Resource" Barcelona 09/2001

Bibliography

Blau P.M. (1964). Exchange and power in social life. New York, J. Wiley, 1964. Boudon R. (1997). « L'explication cognitiviste des croyances collectives », in Cognitions et sciences sociales, Boudon R., Bouvier A., Chazel F., Paris, Puf Burt R.S. (1989). "Kinds of relations in American discussion networks", in Calhoun and alii, (Eds), Structure of power and constraint, Cambridge, Cambridge University Press Cresson G., Pitrou A. (1991). "The role of the family in creating and maintening healthy lifestyles", in Badura B. and Kickbusch I., (eds), Health promotion research towards a new social epidemiology, Copenhagen, WHO Regional Publications, European series N° 37 Cresson G. (1995). Le travail domestique de santé, analyse sociologique, Paris, L'Harmattan Cresson G., Ferrand A., Lardé P., (2001). Les systèmes locaux de santé ; Modèles médicaux des généralistes; relations de confiance et production des réputations dans la population. Etude de deux localités. Lille, CNRS CLERSE Durkheim E. (1898). Représentations individuelles et représentations collectives. In Revue de Métaphysique et de Morale, T.VI, Mai 1898. (reprint in Sociologie et philosophie. Paris, PUF, 1963) Ferrand A. Mounier L. (1990). Relations sexuelles et relations de confidence -Analyse de réseaux. Paris, ANRS -CNRS LASMAS Ferrand A. (2000). « Effets des structures des réseaux de discussion sur la production des réputations », in Cresson G. et Schweyer F.X.,(éds) Les usagers du système de soins, Rennes ,Editions de l'ENSP Ferrand A. (2001) « La production profane des réputations dans les réseaux de discussion » in G.Cresson, A.Ferrand, P.Lardé, Les systèmes locaux de santé.. Lille, CNRS CLERSE Fischer C.S. (1982). To dwell among friends: personal network in town and city. Chicago, University Press Freeman L.C. Ruan D. (1997). "An International Comparative Study of interpersonal Behavior and Role Relationships", L'année sociologiques, v.47, 1 Freidson E. (1960). "Client control and medical practice", American Journal of Sociology,

1 I want to thank Lise Mounier (CNRS LASMAS) for her comments and Karl Van Metter (CNRS LASMAS) for his comments and a reviewing of the first version of this presentaton. Results presented here are part of a research conducted in CNRS CLERSE by G.Cresson, in collaboration with A.Ferrand and P.Lardé, and granted by the CNRS program "Santé et Société".