Marc Briane

Graeme W Milton

Andrejs Treibergs

Which electric fields are realizable in conducting materials?

Keywords: Conductivity, Electric field, Dynamical systems Mathematics Subject Classification : 35B27, 78A30, 37C10

In this paper we study the realizability of a given smooth periodic gradient field ∇u defined in R d , in the sense of finding when one can obtain a matrix conductivity σ such that σ∇u is a divergence free current field. The construction is shown to be always possible locally in R d provided that ∇u is non-vanishing. This condition is also necessary in dimension two but not in dimension three. In fact the realizability may fail for non-regular gradient fields, and in general the conductivity cannot be both periodic and isotropic. However, using a dynamical systems approach the isotropic realizability is proved to hold in the whole space (without periodicity) under the assumption that the gradient does not vanish anywhere. Moreover, a sharp condition is obtained to ensure the isotropic realizability in the torus. The realizability of a matrix field is also investigated both in the periodic case and in the laminate case. In this context the sign of the matrix field determinant plays an essential role according to the space dimension.

Introduction

The mathematical study of composite media has grown remarkably since the seventies through the asymptotic analysis of pde's governing their behavior (see, e.g., [START_REF] Bensoussan | Asymptotic Analysis for Periodic Structures[END_REF], [START_REF] Bakhvalov | Homogenisation: Averaging Processes in Periodic Media, Mathematical Problems in the Mechanics of Composite Materials, translated from the Russian by D. Le?tes[END_REF], [START_REF] Jikov | Homogenization of Differential Operators and Integral Functionals, translated from the Russian[END_REF], [START_REF] Milton | The Theory of Composites[END_REF]). In the periodic framework of the conductivity equation, the derivation of the effective (or homogenized) properties of a given composite conductor in R d , with a periodic matrix-valued conductivity σ, reduces to the cell problem of finding periodic gradients ∇u solving div (σ∇u) = 0 in R d , (1.1) which gives the effective conductivity σ * via the average formula

σ * ∇u = σ∇u . (1.2)
a Institut de Recherche Mathématique de Rennes, INSA de Rennes, FRANCE -mbriane@insa-rennes.fr, b Department of Mathematics, University of Utah, USA -milton@math.utah.edu, c Department of Mathematics, University of Utah, USA -treiberg@math.utah.edu.

Note that the periodicity condition is not actually a restriction, since by [START_REF] Raitums | On the local representation of G-closure[END_REF] (see also [START_REF] Allaire | Shape Optimization by the Homogenization Method[END_REF], Theorem 1.3.23) any effective matrix can be shown to be a pointwise limit of a sequence of periodic homogenized matrices. In equation (1.1) the vector-valued function ∇u represents the electric field, while σ∇u is the current field according to Ohm's law. Alternatively we can consider a vector-valued potential U with gradient DU where each component of U satisfies (1.1). In this case the components of U represent the potentials obtained for different applied fields, and DU will be referred to as the matrix-valued electric field. Going back to the original conductivity problem it is then natural to characterize mathematically among all periodic gradient fields those solving the conductivity equation (1.1) for some positive definite symmetric periodic matrix-valued function σ. In other words the question is to know which electric fields are realizable. On the other hand, this work is partly motivated by the search for sharp bounds on the effective moduli of composites. This search has led investigators to derive as much information as possible about fields in composites. A prime example is given by the positivity of the determinant of periodic matrix-valued electric fields in two dimensions obtained by Alessandrini and Nesi [START_REF] Alessandrini | Univalent σ-harmonic mappings[END_REF]. This led to sharp bounds on effective moduli for three phase conducting composites (see, e.g., [START_REF] Nesi | Bounds on the effective conductivity of two-dimensional composites made of n ≥ 3 isotropic phases in prescribed volume fraction: the weighted translation method[END_REF][START_REF] Cherkaev | Optimal anisotropic three-phase conducting composites: Plane problem[END_REF]). Therefore, a natural question to ask, which we address here, is: what are the conditions on a gradient to be realizable as an electric field?

In Section 2 we focus on vector-valued electric fields. First of all, due to the rectification theorem we prove (see Theorem 2.2) that any non-vanishing smooth gradient field ∇u is isotropically realizable locally in R d , in the sense that in the neighborhood of each point equation (1.1) holds for some isotropic conductivity σI d . Two examples show that the regularity of the gradient field is essential, and that the periodicity of σ is not satisfied in general. Conversely, in dimension two the realizability of a smooth periodic gradient field ∇u implies that ∇u does not vanish in R 2 . This is not the case in dimension three as exemplified by the periodic chain-mail of [START_REF] Briane | Change of sign of the corrector's determinant for homogenization in three-dimensional conductivity[END_REF]. Again in dimension two a necessary and sufficient condition for the (at least anisotropic) realizability is given (see Theorem 2.7). Then, the question of the global isotropic realizability is investigated through a dynamical systems approach. On the one hand, considering the trajectories along the gradient field ∇u which cross a fixed hyperplane, we build (see Proposition 2.10) an admissible isotropic conductivity σ in the whole space. The construction is illustrated with the potential u(x) := x 1 -cos(2πx 2 ) in dimension two. On the other hand, upon replacing the hyperplane by the equipotential {u = 0}, a general formula for the isotropic conductivity σ is derived (see Theorem 2.14) for any smooth gradient field in R d . Finally, a sharp condition for the isotropic realizability in the torus is obtained (see Theorem 2.16), which allows us to construct a periodic conductivity σ.

Section 3 is devoted to matrix-valued fields. The goal is to characterize those smooth potentials U = (u 1 , . . . , u d ) the gradient DU of which is a realizable periodic matrix-valued electric field. When the determinant of DU has a constant sign, it is proved to be realizable with an anisotropic matrix-valued conductivity σ. This can be achieved in an infinite number of ways using Piola's identity coming from mechanics (see Theorem 3.2 and Proposition 3.5). This yields a necessary and sufficient realizability condition in dimension two due to the determinant positivity result of [START_REF] Alessandrini | Univalent σ-harmonic mappings[END_REF]. However, the periodic chain-mail example of [START_REF] Briane | Change of sign of the corrector's determinant for homogenization in three-dimensional conductivity[END_REF] shows that this condition is not necessary in dimension three. We extend (see Theorem 3.7) the realizability result to (nonregular) laminate matrix fields having the remarkable property of a constant sign determinant in any dimension (see [START_REF] Briane | Change of sign of the corrector's determinant for homogenization in three-dimensional conductivity[END_REF], Theorem 3.3).

Notations

• (e 1 , . . . , e d ) denotes the canonical basis of R d .

• I d denotes the unit matrix of R d×d , and R ⊥ denotes the 90 • rotation matrix in R 2×2 .

• For A ∈ R d×d , A T denotes the transpose of the matrix A.

• For ξ, η ∈ R d , ξ ⊗ η denotes the matrix [ξ i η j ] 1≤i,j≤d .

• Y denotes any closed parallelepiped of R d , and

Y d := [0, 1] d . • • denotes the average over Y . • C k ♯ (Y ) denotes the space of k-continuously differentiable Y -periodic functions on R d . • L 2 ♯ (Y ) denotes the space of Y -periodic functions in L 2 (R d ), and H 1 ♯ (Y ) denotes the space of functions ϕ ∈ L 2 ♯ (Y ) such that ∇ϕ ∈ L 2 ♯ (Y ) d .
• For any open set Ω of R d , C ∞ c (Ω) denotes the space of smooth functions with compact support in Ω, and D ′ (Ω) the space of distributions on Ω.

• For u ∈ C 1 (R d ) and U = (U j ) 1≤j≤d ∈ C 1 (R d ) d , ∇u := ∂u ∂x i 1≤i≤d and DU := ∇U 1 , . . . , ∇U d = ∂U j ∂x i 1≤i,j≤d . (1.3)
The partial derivative ∂u ∂x i will be sometimes denoted ∂ i u.

• For Σ = [Σ ij ] 1≤i,j≤d ∈ C 1 (R d ) d×d , Div (Σ) := d i=1 ∂Σ ij ∂x i 1≤j≤d
and Curl (Σ) := ∂Σ ik ∂x j -∂Σ jk ∂x i 1≤i,j,k≤d .

(1.4)

• For ξ 1 1 , . . . , ξ d-1 in R d , the cross product ξ 1 × • • • × ξ d-1 is defined by ξ • ξ 1 × • • • × ξ d-1 = det ξ, ξ 1 , . . . , ξ d-1 , for any ξ ∈ R d , (1.5)
where det is the determinant with respect to the canonical basis (e 1 , . . . , e d ), or equivalently, the k th coordinate of the cross product is given by

ξ 1 × • • • × ξ d-1 • e k = (-1) k+1 ξ 1 1 ••• ξ d-1 1 . . . . . . . . . ξ 1 k-1 ••• ξ d-1 k-1 ξ 1 k+1 ••• ξ d-1 k+1 . . . . . . . . . ξ 1 d ••• ξ d-1 d . (1.6)
2 The vector field case

(x) := x 2 -x 1 + ˆx1 0 χ(t) dt, for any x = (x 1 , x 2 ) ∈ R 2 .
(2.4)

The function u is Lipschitz continuous, and

∇u = χ e 2 + (1 -χ) (e 2 -e 1 ) a.e. in ∈ R 2 .
(2.5)

The discontinuity points of ∇u lie on the lines {x

1 = 1/2 (1 + k)}, k ∈ Z. Let Q := (-r, r) 2
for some r ∈ (0, 1/2).

Assume that there exists a positive function σ ∈ L ∞ (Q) such that σ∇u is divergence free in Q. Let v be a stream function such that σ∇u = R ⊥ ∇v a.e. in Q. The function v is unique up to an additive constant, and is Lipschitz continuous. On the one hand, we have 0 = ∇u • ∇v = (e 2 -e 1 ) • ∇v a.e. in (-r, 0) × (-r, r),

(2.6) hence v(x) = f (x 1 + x 2 ) for some Lipschitz continuous function f defined in [-2r, r]. On the other hand, we have 0 = ∇u • ∇v = e 2 • ∇v a.e. in (0, r) × (-r, r),

hence v(x) = g(x 1 ) for some Lipschitz continuous function g in [0, r]. By the continuity of v on the line {x 1 = 0}, we get that f (x 2 ) = g(0), hence f is constant in [-r, r]. Therefore, we have ∇v = 0 a.e. in (-r, 0) × (0, r) and σ∇u = σ (e 2 -e 1 ) = 0 a.e. in (-r, 0) × (0, r), (2.8) which contradicts the equality σ∇u = R ⊥ ∇v a.e. in Q. Therefore, the field ∇u is non-zero a.e. in R 2 , but is not an isotropically realizable electric field in the neighborhood of any point of the lines {x

1 = 1/2 (1 + k)}, k ∈ Z.
Remark 2.5. The singularity of ∇u in Example 2.4 induces a jump of the current at the interface {x 1 = 0}. To compensate this jump we need to introduce formally an additional current concentrated on this line, which would imply an infinite conductivity there. The assumption of bounded conductivity (in L ∞ ) leads to the former contradiction. Alternatively, with a smooth approximation of ∇u around the line {x 1 = 0}, then part i) of Theorem 2.2 applies which allows us to construct a suitable conductivity. But this conductivity blows up as the smooth gradient tends to ∇u.

Example 2.6. Consider the function u defined in R by

u(x) := x 1 -cos (2πx 2 ) , for any x = (x 1 , x 2 ) ∈ R 2 .
(2.9)

The function u is smooth, and its gradient ∇u is Y 2 -periodic, independent of the variable x 1 and non-zero on R 2 . Assume that there exists a smooth positive function σ defined in R 2 , which is a-periodic with respect to x 1 for some a > 0, and such that σ∇u is divergence free in R 2 . Set Q := (0, a)×(-r, r) for some r ∈ (0, 1 2 ). By an integration by parts and taking into account the periodicity of σ∇u with respect to x 1 , we get that

0 = ˆQ div (σ∇u) dx = ˆr -r σ∇u(a, x 2 ) -σ∇u(0, x 2 ) • e 1 dx 2 =0 + ˆa 0 σ∇u(x 1 , r) -σ∇u(x 1 , -r) • e 2 dx 1 = 2π sin (2πr) ˆa 0 σ(x 1 , r) + σ(x 1 , -r) dx 1 > 0,
(2.10) which yields a contradiction. Therefore, the Y 2 -periodic field ∇u is not an isotropically realizable electric field in the torus.

Proof of Theorem 2.2.

i) Let x 0 ∈ R d . First assume that d > 2.
By the rectification theorem (see, e.g., [START_REF] Arnold | Équations Différentielles Ordinaires[END_REF]) there exist an open neighborhood V 0 of x 0 , an open set W 0 , and a C 1 -diffeomorphism Φ : V 0 → W 0 such that DΦ T ∇u = e 1 . Define v i := Φ i+1 for i ∈ {1, . . . , d -1}. Then, we get that ∇v i • ∇u = 0 in V 0 , and the rank of (∇v 1 , . . . , ∇v d-1 ) is equal to (d -1) in V 0 . Consider the continuous function

σ := |∇v 1 × • • • × ∇v d-1 | |∇u| > 0 in V 0 . (2.11)
Since by definition, the cross product ∇v 1 ו • •×∇v d-1 is orthogonal to each ∇v i as is ∇u, then due to the condition (2.3) combined with a continuity argument, there exists a fixed τ 0 ∈ {±1} such that

∇v 1 × • • • × ∇v d-1 = τ 0 σ∇u in V 0 .
(2.12)

Moreover, Theorem 3.2 of [START_REF] Dacorogna | Direct Methods in the Calculus of Variations[END_REF] implies that ∇v 1 × • • • × ∇v d-1 is divergence free, and so is σ∇u. Therefore, ∇u is an isotropically realizable electric field in V 0 . When d = 2, the equality ∇v 1 • ∇u = 0 in V 0 yields for some fixed τ 0 ∈ {±1},

τ 0 R ⊥ ∇v 1 = |∇v 1 | |∇u| σ := ∇u in V 0 , (2.13)
which also allows us to conclude the proof of (i).

ii) It is a straightforward consequence of [START_REF] Alessandrini | Univalent σ-harmonic mappings[END_REF] (Proposition 2, the smooth case).

iii) Ancona [START_REF] Ancona | Some results and examples about the behavior of harmonic functions and Green's functions with respect to second order elliptic operators[END_REF] first built an example of potential with critical points in dimension d ≥ 3. The following construction is a regularization of the simpler example of [START_REF] Briane | Change of sign of the corrector's determinant for homogenization in three-dimensional conductivity[END_REF] which allows us to derive a change of sign for the determinant of the matrix electric field. Consider the periodic chainmail

Q ♯ ⊂ R 3 of [8]
, and the associated isotropic two-phase conductivity σ κ which is equal to κ ≫ 1 in Q ♯ and to 1 elsewhere. Now, let us modify slightly the conductivity σ κ by considering a smooth Y 3 -periodic isotropic conductivity σκ ∈ [1, κ] which agrees with σ κ , except within a thin boundary layer of each interlocking ring Q ⊂ Q ♯ , of width κ -1 from the boundary of Q.

Proceeding as in [START_REF] Briane | Change of sign of the corrector's determinant for homogenization in three-dimensional conductivity[END_REF] it is easy to prove that the smooth periodic matrix-valued electric field D Ũκ solution of Div σκ

D Ũκ = 0 in R 3 , with D Ũκ = I 3 , (2.14)
converges (as κ → ∞) strongly in L 2 (Y 3 ) 3×3 to the same limit DU as the electric field DU κ associated with σ κ . Then, by virtue of [START_REF] Briane | Change of sign of the corrector's determinant for homogenization in three-dimensional conductivity[END_REF] det (DU) is negative around some point between two interlocking rings, so is det D Ũκ for κ large enough. This combined with det D Ũκ = 1 and the continuity of D Ũκ , implies that there exists some point y 0 ∈ Y 3 such that det D Ũκ (y 0 ) = 0. Therefore, there exists ξ ∈ R 3 \ {0} such that the potential u := Ũκ • ξ satisfies ∇u = ξ and ∇u(y 0 ) = D Ũκ (y 0 ) ξ = 0. Theorem 2.2 is thus proved.

Characterization of the anisotropic realizability in dimension two

In dimension two we have the following characterization of realizable electric vector fields:

Theorem 2.7. Let Y be a closed parallelogram of R 2 . Consider a function u ∈ C 1 (R 2 ) satis- fying (2.
2). Then, a necessary and sufficient condition for ∇u to be a realizable electric field associated with a symmetric positive definite matrix-valued conductivity in

C 0 ♯ (Y ) d×d , is that there exists a function v ∈ C 1 (R 2 ) satisfying (2.2) such that R ⊥ ∇u • ∇v = det (∇u, ∇v) > 0 everywhere in R 2 .
(2.15)

Remark 2.8. The result of Theorem 2.7 still holds under the less regular assumption

∇u ∈ L 2 ♯ (Y ) 2 , ∇u = 0 everywhere in R 2 and ∇u = 0. (2.16)
Then, the Y -periodic conductivity σ defined by the formula (2.17) below is only defined almost everywhere in R 2 , and is not necessarily uniformly bounded from below or above in the cell period Y . However, σ∇u remains divergence free in the sense of distributions on R 2 .

Proof of Theorem 2.7.

Sufficient condition: Let u, v ∈ C 1 (R 2 ) be two functions satisfying (2.2) and (2.15). From (2.15) we easily deduce that ∇u does not vanish in R 2 . Then, we may define in R 2 the function

σ := 1 |∇u| 4 ∂ 1 u ∂ 2 u -∂ 2 u ∂ 1 u T R ⊥ ∇u • ∇v -∇u • ∇v -∇u • ∇v |∇u•∇v| 2 +1 R ⊥ ∇u•∇v ∂ 1 u ∂ 2 u -∂ 2 u ∂ 1 u . (2.17)
Hence, σ is a symmetric positive definite matrix-valued function in C 0 ♯ (Y ) d×d with determinant |∇u| -4 . Moreover, a simple computation shows that σ∇u = -R ⊥ ∇v, so that σ∇u is divergence free in R d . Therefore, ∇u is a realizable electric field in R d associated with the anisotropic conductivity σ.

Necessary condition: Let u ∈ C 1 (R) satisfying (2.
2) such that ∇u is a realizable electric field associated with a symmetric positive definite matrix-valued conductivity σ ∈ C 0 ♯ (Y ) d×d in R d . Consider the unique (up to an additive constant) potential v which solves div (σ∇v

) = 0 in R d , with ∇v ∈ H 1 ♯ (Y ) d and ∇v = R ⊥ ∇u , and set U := (u, v). By (2.2) we have det DU = R ⊥ ∇u • ∇v = ∇u 2 > 0. (2.18)
Hence, due to [START_REF] Alessandrini | Univalent σ-harmonic mappings[END_REF] (Theorem 1) we have det (DU) > 0 a.e. in R 2 . On the other hand, assume that there exists a point y 0 ∈ R 2 such that det (DU) (y 0 ) = 0. Then, there exists ξ ∈ R 2 \ {0} such that the potential u := Uξ satisfies ∇u(y 0 ) = DU(y 0 ) ξ = 0, which contradicts Proposition 2 of [START_REF] Alessandrini | Univalent σ-harmonic mappings[END_REF] (the smooth case). Therefore, we get that R ⊥ ∇u • ∇v = det (DU) > 0 everywhere in R 2. Consider the function u defined by (2.9), and define the function v by v(x) := x 2 . Then, formula (2.17) yields the smooth conductivity

σ = 1 1 + 4π 2 sin 2 (2πx 2 ) 2 1 + 4π 2 sin 2 (2πx 2 ) 2 + 4π 2 sin 2 (2πx 2 ) -2π sin(2πx 2 ) -2π sin(2πx 2 ) 1 ,
(2.24) This implies that σ∇u = e 1 which is obviously divergence free in R 2 .

Global isotropic realizability

In the previous section we have shown that not all gradients ∇u satisfying (2.2) and (2.3) are isotropically realizable when we assume σ is periodic. In the present section we will prove that the isotropic realizability actually holds in the whole space R d when we relax the periodicity assumption on σ. To this end consider for a smooth periodic gradient field ∇u ∈ C 1 ♯ (Y ) d , the following gradient dynamical system

   dX dt (t, x) = ∇u X(t, x) X(0, x) = x, for t ∈ R, x ∈ R d , (2.25)
where t will be referred to as the time. First, we will extend the local rectification result of Theorem 2.2 to the whole space involving a hyperplane. Then, using an alternative approach we will obtain the isotropic realizability in the whole space replacing the hyperplane by an equipotential. Finally, we will give a necessary and sufficient for the isotropic realizability in the torus.

A first approach

We have the following result:

Proposition 2.10. Let u be a function in C 2 (R d ) such that ∇u satisfies (2.2) and (2.3). Also assume that there exists an hyperplane is given explicitly by (see figure 1)

H := {x ∈ R d : x • ν = h} such that each trajectory X(•, x) of (2.25), for x ∈ R d , intersects H only at one point z H (x) = X τ H (x),
     dX 1 dt (t, x) = 1, X 1 (0, x) = x 1 , dX 2 dt (t, x) = 2π sin 2πX 2 (t, x) , X 2 (0, x) = x 2 , for t ∈ R, x ∈ R 2 , ( 2
X(t, x) =    (t + x 1 ) e 1 + n + 1 π arctan e 4π 2 t tan(πx 2 ) e 2 if x 2 ∈ n -1 2 , n + 1 2 (t + x 1 ) e 1 + n + 1 2 e 2 if x 2 = n + 1 2 , (2.27)
where n is an arbitrary integer.

Consider the line {x 1 = 0} as the hyperplane H. Then, we have τ H (x) = -x 1 . Moreover, using successively the explicit formula (2.27) and the semigroup property (2.35), we get that X -X 1 (t, x), X(t, x) = X -t -x 1 , X(t, x) = X(-x 1 , x), for any t ∈ R.

(2.28)

Hence, the function v defined by v(x) := X 2 (-

x 1 , x) satisfies v X(t, x) = X 2 -X 1 (t, x), X(t, x) = X 2 (-x 1 , x) = v(x)
, for any t ∈ R.

(2.29)

The function v is thus a first integral of system (2.25). It follows that

d dt v X(t, x) = 0 = ∇v X(t, x) • dX dt (t, x) = ∇v X(t, x) • ∇u X(t, x) , (2.30)
which, taking t = 0, implies that ∇u • ∇v = 0 in R 2 . Moreover, putting t = -x 1 in (2.27), we get that for any n ∈ Z,

v(x) = n + 1 π arctan e -4π 2 x 1 tan(πx 2 ) if x 2 ∈ n -1 2 , n + 1 2 n + 1 2 if x 2 = n + 1 2 .
(2.31) Therefore, by (2.13) ∇u is an isotropically realizable electric field in the whole space R 2 , with the smooth conductivity

σ := |∇v| |∇u| =      1 + tan 2 (πx 2 ) e 4π 2 x 1 + e -4π 2 x 1 tan 2 (πx 2 ) if x 2 / ∈ 1 2 + Z e 4π 2 x 1 if x 2 ∈ 1 2 + Z.
(2.32)

It may be checked by a direct calculation that σ∇u is divergence free in R 2 .

Proof of Theorem 2.10. Let (τ 1 , . . . , τ d-1 ) be an orthonormal basis of the hyperplane H. Define for each k ∈ {1, . . . , d -1}, the function v k by

v k (x) := z H (x) • τ k = X τ H (x), x • τ k , for x ∈ R d . (2.33)
We shall prove that the functions v k satisfy the properties of the proof of Theorem 2.2. i).

First, due the transversality of each trajectory across H, we have for any

x ∈ R d , ∂ ∂t X(t, x) • ν t=τ H (x) = ∇u z H (x) • ν = 0. (2.34)
Hence, the implicit functions theorem combined with the C 1 -regularity of (t, x) → X(t, x) (see, e.g., [START_REF] Arnold | Équations Différentielles Ordinaires[END_REF], Theorem T ′ r p. 222) implies that x → τ H (x) defines a function in C 1 (R d ). Therefore, the functions v k defined by (2.33) belong to C 1 (R).

Second, since the trajectories satisfy the identity

X s, X(t, x) = X(s + t, x) ∀ s, t ∈ R, ∀ x ∈ R d , (2.35)
we get that X τ H (x) -t, X(t, x) = X τ H (x), x , and thus

τ H X(t, x) = τ H (x) -t. (2.36) It follows that for any k ∈ {1, . . . , d -1}, v k X(t, x) = X τ H (x) -t, X(t, x) • τ k = X τ H (x), x) • τ k , for any t ∈ R.
(2.37) Therefore, each function v k is a first integral of the dynamical system (2.25). Third, consider for some

x 0 ∈ Ω, a vector (λ 1 , . . . , λ d-1 ∈ R d-1 such that d-1 k=1 λ k ∇v k (x 0 ) = 0, (2.38)
and define the function

v 0 := d-1 k=1 λ k v k = z H • τ 0 , where τ 0 := d-1 k=1 λ k τ k . ( 2

.39)

By the chain rule we have

Dz H (x) = ∇τ H (x) ⊗ ∂X ∂t τ H (x), x + D x X τ H (x), x = ∇τ H (x) ⊗ ∇u z H (x) + D x X τ H (x), x .
(2.40)

This combined with the equality (recall that z H (x) ∈ H)

0 = ∇ z H (x) • ν x=x 0 = Dz H (x 0 ) ν, (2.41) implies that ∇τ H (x 0 ) = -1 ∇u z H (x 0 ) • ν D x X τ H (x 0 ), x 0 ν. (2.42)
Hence, by the equalities (2.38), (2.39) and again using (2.40) together with (2.42), we get that

0 = ∇v 0 (x 0 ) = Dz H (x 0 ) τ 0 = D x X τ H (x 0 ), x 0 τ 0 - ∇u z H (x 0 ) • τ 0 ∇u z H (x 0 ) • ν ν . (2.43)
However, by Lemma 2.12 below, the matrix D x X τ H (x 0 ), x 0 is invertible. This combined with (2.43) yields that τ 0 is proportional to ν. Hence, τ 0 = 0 and (∇v 1 , . . . , ∇v d-1 ) has rank (d -1) everywhere in R d . Therefore, the continuous positive conductivity defined by (2.11) shows that ∇u is isotropically realizable in the whole space R d .

Lemma 2.12. The derivative D x X of the dynamical system (2.25) is invertible in R × R d .

Proof. By the chain rule the matrix field D x X satisfies the variational equation

   d dt D x X(t, x) = D x X(t, x) ∇ 2 u X(t, x) D x X(0, x) = I d , for t ∈ R, x ∈ R d , (2.44)
where ∇ 2 u denotes the Hessian matrix of u and I d is the unit matrix of R d×d . Moreover, due to the multi-linearity of the determinant det (D x X) satisfies Liouville's formula

   d dt det (D x X) (t, x) = tr ∇ 2 u X(t, x) det (D x X) (t, x) det (D x X) (0, x) = 1, for t ∈ R, x ∈ R d , (2.45)
where tr denotes the trace. It follows that

det (D x X) (t, x) = exp ˆt 0 tr ∇ 2 u X(s, x) ds > 0 for any (t, x) ∈ R × R d , (2.46) which shows that D x X(t, x) is invertible.
Remark 2.13. The hyperplane assumption of Theorem 2.10 does not hold in general. Indeed, we have the following heuristic argument: Let H be a line of R 2 , and let Σ be a smooth curve of R 2 having an S-shape across H. Consider a smooth periodic isotropic conductivity σ which is very small in the neighborhood of Σ. Let u be a smooth potential solution of div (σ∇u) = 0 in R 2 satisfying (2.2), (2.3), and let v be the associated stream function satisfying σ∇u = R ⊥ ∇v in R 2 . The potential v is solution of div (σ -1 ∇v) = 0 in R 2 . Then, since σ -1 is very large in the neighborhood of Σ, the curve Σ is close to an equipotential of v and thus close to a current line of u. Therefore, some trajectory of (2.25) has an S-shape across H. This makes impossible the regularity of the time τ H which is actually a multi-valued function.

Isotropic realizability in the whole space

Replacing a hyperplane by an equipotential (see figure 1 above) we have the more general result: Theorem 2.14. Let u be a function in C 3 (R d ) such that ∇u satisfies (2.2) and (2.3). Then, the gradient field ∇u is an isotropically realizable electric field in R d .

Proof. On the one hand, for a fixed x ∈ R d , define the function f : R → R by f (t) := u X(t, x) , for t ∈ R. The function f is in C 3 (R), and

f ′ (t) = dX dt (t, x) • ∇u X(t, x) = ∇u X(t, x) 2 , ∀ t ∈ R. (2.47)
Since ∇u is periodic, continuous and does not vanish in R d , there exists a constant m > 0 such that f ′ ≥ m in R. It follows that

f (t) -f (0) t ≥ m, ∀ t ∈ R \ {0}, (2.48) which implies that lim t→∞ f (t) = ∞ and lim t→-∞ f (t) = -∞. (2.49)
This combined with the monotonicity and continuity of f thus shows that there exists a unique τ (x) ∈ R such that u X(τ (x), x) = 0.

(2.50)

On the other hand, similar to the hyperplane case, we have that for any

x ∈ R d , ∂ ∂t u X(t, x) t=τ (x)
= ∇u X(τ (x), x) 2 > 0.

(2.51)

Hence, from the implicit functions theorem combined with the C 2 -regularity of (t, x) → u X(t, x)

we deduce that x → τ (x) is a function in C 2 (R d ). Now define the function w in R d by w(x) := ˆτ(x) 0 ∆u X(s, x) ds, for x ∈ R d , (2.52) which belongs to C 1 (R d ) since u ∈ C 3 (R d ).
Then, using (2.35), (2.36) and the change of variable r := s + t, we have for any (t, which belongs to C 1 (R d ). Applying (2.54) with t = 0, we obtain that div (σ∇u) = e w (∇w

x) ∈ R × R d , w X(t, x) = ˆτ(x)-t 0 ∆u X(s + t, x) ds = ˆτ(x) t ∆u X(r, x) dr, (2.53) which implies that ∂ ∂t w X(t, x) = ∇w X(t, x) • ∇u X(t, x) = -∆u X(t, x) . ( 2
• ∇u + ∆u) = 0 in R d , (2.56)
which concludes the proof.

Remark 2.15. In the proof of Theorem 2.14 the condition that ∇u is non-zero everywhere is essential to obtain both: -the uniqueness of the time τ (x) for each trajectory to reach the equipotential {u = 0}, -the regularity of the function x → τ (x).

Isotropic realizability in the torus

We have the following characterization of the isotropic realizability in the torus:

Theorem 2.16. Let u be a function in C 3 (R d ) such that ∇u satisfies (2.2) and (2.3). Then, the gradient field ∇u is isotropically realizable with a positive conductivity

σ ∈ L ∞ ♯ (Y ), with σ -1 ∈ L ∞ ♯ (Y ), if there exists a constant C > 0 such that ∀ x ∈ R d , ˆτ(x) 0 ∆u X(t, x) dt ≤ C, (2.57)
where X(t, x) is defined by (2.25) and τ (x) by (2.50).

Conversely, if ∇u is isotropically realizable with a positive conductivity σ ∈ C 1 ♯ (Y ), then the boundedness (2.57) holds.

Example 2.17. For the function u of Example 2.11 and for x = (x 1 , 0), we have by (2.57) and (2.27),

σ 0 (x) = exp 4π 2 ˆτ(x) 0 cos 2πX 2 (s, x) ds = exp 4π 2 τ (x) ,
and by (2.50),

X 1 τ (x), x = τ (x) + x 1 = cos 2πX 2 (τ (x), x) = 1.
Therefore, we get that σ 0 (x 1 , 0) = exp 4π 2 (1-x 1 ) , which contradicts the boundedness (2.57). This is consistent with the negative conclusion of Example 2.6.

Proof of Theorem 2.16. Sufficient condition: Without loss of generality we may assume that the period is Y = [0, 1] d . Define the function σ 0 by

σ 0 (x) := exp ˆτ(x) 0 ∆u X(t, x) dt , for x ∈ R d , (2.58)
and consider for any integer n ≥ 1, the conductivity σ n defined by the average over the (2n+1) d integer vectors of [-n, n] d :

σ n (x) := 1 (2n + 1) d k∈Z d ∩[-n,n] d σ 0 (x + k), for x ∈ R d .
(2.59)

On the one hand, by (2.57) σ n is bounded in L ∞ (R d ). Hence, there is a subsequence of n, still denoted by n, such that σ n converges weakly- * to some function σ in L ∞ (R d ). Moreover, we have for any x ∈ R d and any k ∈ Z d (denoting |k| ∞ := max

1≤i≤d |k i |), (2n + 1) d σ n (x + k) -(2n + 1) d σ n (x) = |j-k|∞≤n σ 0 (x + j) - |j|∞≤n σ 0 (x + j) ≤ |j-k|∞≤n |j|∞>n σ 0 (x + j) + |j-k|∞>n |j|∞≤n σ 0 (x + j) ≤ C n d-1 , (2.60)
where C is a constant independent of n and x. This implies that σ(• + k) = σ(•) a.e. in R d , for any k ∈ Z d . The function σ is thus Y -periodic and belongs to L ∞ ♯ (Y ). Moreover, since by virtue of (2.57) and (2.58) σ 0 is bounded from below by e -C , so is σ n and its limit σ. Therefore, σ -1 also belongs to L ∞ ♯ (Y ).

On the other hand, by virtue of Theorem 2.14 the gradient field ∇u is realizable in R d with the conductivity σ 0 . This combined with the Y -periodicity of ∇u yields div (σ n ∇u) = 0 in R d . Hence, using the weak- * convergence of σ n in L ∞ (R d ) we get that for any ϕ

∈ C ∞ c (R d ), ∇u • ∇ϕ ∈ L 1 (R d ) and 0 = lim n→∞ ˆRd σ n ∇u • ∇ϕ dx = ˆRd σ∇u • ∇ϕ dx. (2.61)
Therefore, we obtain that div (σ∇u) = 0 in D ′ (R d ), so that ∇u is isotropically realizable with the Y -periodic bounded conductivity σ.

Necessary condition: Let σ be a positive function in C 1 ♯ (Y ) such that div (σ∇u) = 0 in R d . Then, the function w := ln σ also belongs to C 1 ♯ (Y ), and solves the equation ∇w • ∇u + ∆u = 0 in R d . Therefore, using (2.25) we obtain that for any

x ∈ R d , ˆτ(x) 0 ∆u X(t, x) dt = - ˆτ(x) 0 ∇w X(t, x) • ∇u X(t, x) dt = - ˆτ(x) 0 ∇w X(t, x) • dX dt (t, x) dt = w X(0, x) -w X(τ (x), x) = w(x) -w X(τ (x), x) , (2.62)
which implies (2.57) due to the boundedness of w in R d .

Remark 2.18. If we also assume that σ 0 of (2.57) is uniformly continuous in R d , then the previous proof combined with Ascoli's theorem implies that the conductivity σ is continuous. Indeed, the sequence σ n defined by (2.59) is then equi-continuous.

3 The matrix field case Then, the Y -periodic conductivity σ defined by the formula (3.5) below is only defined a.e. in R d , and is not necessarily uniformly bounded from below or above in the cell period Y . However, σDU remains divergence free in the sense of distributions on R d .

Proof of Theorem 3. Hence, σDU is Divergence free in R d . Therefore, DU is a realizable electric matrix field associated with the continuous conductivity σ.

ii) Let DU be an electric matrix field satisfying condition (3.2) and associated with a smooth conductivity in R 2 . By the regularity results for second-order elliptic pde's the function U is smooth in R 2 . Moreover, due to [START_REF] Alessandrini | Univalent σ-harmonic mappings[END_REF] (Theorem 1) we have det DU DU > 0 a.e. in R 2 . Therefore, as in the proof of Theorem 2.7 we conclude that (3.3) holds.

iii) This is an immediate consequence of the counter-example of [START_REF] Briane | Change of sign of the corrector's determinant for homogenization in three-dimensional conductivity[END_REF] combined with the regularization argument used in the proof of Theorem 2.2 iii).

Remark 3.4. The conductivity σ defined by (3.5) can be derived by applying the coordinate change x ′ = U -1 (x) to the homogeneous conductivity det DU I d .

In fact there are many ways to derive a conductivity σ associated with a matrix field DU the determinant of which has a constant sign. Following [START_REF] Milton | The Theory of Composites[END_REF] (Remark p. 155) such a conductivity can be expressed by σ = JDU -1 , where J is a Divergence free matrix-valued function. From this perspective we have the following extension of part i) of Theorem 3. (3.7)

Proof. On the one hand, the matrix-valued function J of (3.7) is clearly Divergence free due to Piola's identity. On the other hand, we have

Cof D(∇ϕ • U) = Cof DU ∇ 2 ϕ • U = Cof (DU) Cof ∇ 2 ϕ • U , (3.8)
so that the matrix-valued σ defined by (3.7) satisfies

σ = det DU DU (DU -1 ) T Cof ∇ 2 ϕ • U DU -1 . (3.9)
Since ∇ 2 ϕ is symmetric positive definite, so is its Cofactors matrix. Therefore, σ is an admissible continuous conductivity such that σDU is Divergence free in R d . • At the smallest scale ε n , there is a set of m n rank-one laminates, the i th one of which is composed, for i = 1, . . . , m n , of an ε n -periodic repetition in the direction ξ i,n of homogeneous layers with constant positive definite conductivity matrices σ h i,n , h ∈ I i,n . • At the scale ε k , there is a set of m k laminates, the i th one of which is composed, for i = 1, . . . , m k , of an ε k -periodic repetition in the direction ξ i,k ∈ R d \ {0} of homogeneous layers and/or a selection of the m k+1 laminates which are obtained at stage (k + 1) with conductivity matrices σ h i,j , for j = k + 1, . . . , n, h ∈ I i,j . • At the scale ε 1 , there is a single laminate (m 1 = 1) which is composed of an ε 1 -periodic repetition in the direction ξ 1 ∈ R d \ {0} of homogeneous layers and/or a selection of the m 2 laminates which are obtained at the scale ε 2 with conductivity matrices σ h i,j , for j = 2, . . . , n, h ∈ I i,j .

The laminate case

σ 1 1,2 σ 1 1,2 σ 2 1,2 σ 2 1,2 σ 1 1,1 σ 2 1,1 σ 1 1,2 σ 1 1,1 σ 2 1,1 σ 1 1,2 σ 2 1,2 σ 2 1,2 σ 1 1,2 σ 1 1,2
The laminate conductivity at stage k = 1, . . . , n, is denoted by L ε k (σ), where σ is the whole set of the constant laminate conductivities.

Due to the results of [START_REF] Milton | Modelling the properties of composites by laminates[END_REF][START_REF] Briane | Correctors for the homogenization of a laminate[END_REF] there exists a set P of constant matrices in R d×d , such that the laminate P ε := L ε n ( P ) is a corrector (or a matrix electric field) associated with the conductivity

σ ε := L ε n (σ) in the sense of Murat-Tartar [15], i.e.        P ε ⇀ I d weakly in L 2 loc (R d ) d×d , Curl (P ε ) → 0 strongly in H -1 loc (R d ) d×d×d , Div (σ ε P ε ) is compact in H -1 loc (R d ) d .
(3.10)

The weak limit of σ ε P ε in L 2 loc (R d ) d×d is then the homogenized limit of the laminate. The three conditions of (3. satisfied by any electric matrix field DU in the periodic case. The equivalent of Theorem 3.2 for a laminate is the following: Theorem 3.7. Let n, d be two positive integers. Consider a rank-n laminate L ε n ( P ) built from a finite set P of R d×d (according to Definition 3.6) which satisfies the two first conditions of (3.10). Then, a necessary and sufficient condition for L ε n ( P ) to be a realizable laminate electric field, i.e. to satisfy the third condition of (3.10) for some rank-n laminate conductivity L ε n (σ), is that det L ε n ( P ) > 0 a.e. in R d , or equivalently that the determinant of each matrix in P is positive.

Proof of Theorem 3.7. The fact that the determinant positivity condition is necessary was established in [START_REF] Briane | Change of sign of the corrector's determinant for homogenization in three-dimensional conductivity[END_REF], Theorem 3.3 (see also [START_REF] Briane | Is it wise to keep laminating?[END_REF], Theorem 2.13, for an alternative approach).

Conversely, consider a rank-n laminate field P ε = L ε n ( P ) satisfying the two first convergence of (3.10) and det (P ε ) > 0 a.e. in R d , or equivalently det (P ) > 0 for any P ∈ P . Similarly to (3.5) consider the rank-n laminate conductivity defined by σ ε := det P ε (P -1 ε ) T (P ε ) -1 = L ε n (σ), where σ := det P (P -1 ) T P -1 : P ∈ P . (3.12)

Then, the third condition of (3.10) is equivalent to the condition Div Cof (P ε ) is compact in

H -1 loc (R d ) d . (3.13)
Contrary to the periodic case Cof (P ε ) is not divergence free in the sense of distributions. However, following the homogenization procedure for laminates of [START_REF] Briane | Correctors for the homogenization of a laminate[END_REF], and using the quasiaffinity of the Cofactors for gradients (see, e.g., [START_REF] Dacorogna | Direct Methods in the Calculus of Variations[END_REF]), condition (3.13) holds if any matrices P, Q of two neighboring layers in a direction ξ of the laminate satisfy the jump condition for the divergence Cof (P ) -Cof (Q) T ξ = 0. (

More precisely, at a given scale ε k of the laminate the matrix P , or Q, is:

• either a matrix in P ,

• or the average of rank-one laminates obtained at the smallest scales ε k+1 , . . . , ε n .

In the first case the matrix P is the constant value of the field in a homogeneous layer of the rank-n laminate. In the second case the average of the Cofactors of the matrices involving in these rank-one laminations is equal to the Cofactors matrix of the average, that is Cof (P ), by virtue of the quasi-affinity of the Cofactors applied iteratively to the rank-one connected matrices in each rank-one laminate. Therefore, it remains to prove equality (3.14) for any matrices P, Q with positive determinant satisfying the condition which controls the jumps in the second convergence of (3.

Example 2 . 4 .

 24 Let χ : R → R be the 1-periodic characteristic function which agrees with the characteristic function of [0, 1/2] on [0, 1]. Consider the function u defined in R 2 by u

Figure 1 :

 1 Figure 1: The trajectories crossing the line {x 1 = 0} and the equipotential {u = 0}

  .54) Finally, define the conductivity σ by σ(x) := e w(x) = exp ˆτ(x) 0 ∆u X(s, x) ds , for x ∈ R 2 , (2.55)

  2.i) Let U ∈ C 1 (R d ) d be a vector-valued function satisfying(3.2). Then, we can define the matrix-valued function σ byσ := det DU DU (DU -1 ) T DU -1 = det DU Cof (DU) DU -1 ,(3.5)where Cof denotes the Cofactors matrix. It is clear that σ is a Y -periodic continuous symmetric positive definite matrix-valued function. Moreover, Piola's identity (see, e.g.,[START_REF] Dacorogna | Direct Methods in the Calculus of Variations[END_REF], Theorem 3.2) implies that Div Cof (DU) = 0 in D ′ (R d ).(3.6)

2 :

 2 Proposition 3.5. Let U be a function in C 1 (R d ) d satisfying (3.2) and (3.3). Consider a convex function ϕ in C 2 (R d ) whose Hessian matrix ∇ 2 ϕ is positive definite everywhere in R d . Then, Du is a realizable electric matrix field with the conductivity σ := JDU -1 where J := det DU Cof D(∇ϕ • U) .

Figure 2 : 2 Definition 3 . 6 .

 2236 Figure 2: A rank-two laminate with directions ξ 1 = e 1 and ξ 1,2 = e 2

  10) satisfied by P ε extend to the laminate case the three respective conditions        DU = I d , Curl (DU) = 0, Div (σDU) = 0, (3.11)

  10), namely P -Q = ξ ⊗ η for some η ∈ R d . (3.15)By(3.15) and by the multiplicativity of the Cofactors matrix we haveCof (P ) -Cof (Q) T = Cof (Q) T Cof (I d + (ξ ⊗ η) Q -1 ) T -I d = Cof (Q) T Cof (I d + ξ ⊗ λ) T -I d , with λ := (Q -1 ) T η. (3.16) Moreover, if ξ • λ = -1, a simple computation yields Cof (I d + ξ ⊗ λ) T = det (I d + ξ ⊗ λ) (I d + ξ ⊗ λ) -1 = (1 + ξ • λ) I d -ξ ⊗ λ,(3.17)which extends to the case ξ • λ = -1 by a continuity argument. Therefore, it follows thatCof (P ) -Cof (Q) T = Cof (Q) T (ξ • λ) I d -ξ ⊗ λ ,(3.18)which implies the desired equality(3.14), since (ξ ⊗ λ) ξ = (ξ • λ) ξ.

theorem which needs at least C 1 -regularity and is local.

  Definition 2.1. Let Ω be an (bounded or not) open set of R d , d ≥ 2, and let u ∈ H 1 (Ω). The vector-valued field ∇u is said to be a realizable electric field in Ω if there exist a symmetric positive definite matrix-valued σ ∈ L ∞

	loc (Ω) d×d such that
	div (σ∇u) = 0 in D ′ (Ω).	(2.1)
	If σ can be chosen isotropic (σ → σI d ), the field ∇u is said to be isotropically realizable in Ω.
	2.1 Isotropic and anisotropic realizability
	2.1.1 Characterization of an isotropically realizable electric field
	Theorem 2.2. Let Y be a closed parallelepiped of R d . Consider u ∈ C 1 (R d ), d ≥ 2, such that
	∇u is Y -periodic and ∇u = 0.	(2.2)
	i) Assume that
	∇u = 0 everywhere in R d .	(2.3)
	Then, ∇u is an isotropically realizable electric field locally in R d associated with a con-
	tinuous conductivity.
	ii) Assume that ∇u satisfies condition (2.2), and is a realizable electric field in R 2 associated
	with a smooth Y -periodic conductivity. Then, condition (2.3) holds true.
	iii) There exists a gradient field ∇u satisfying (2.2), which is a realizable electric field in R 3
	associated with a smooth Y 3 -periodic conductivity, and which admits a critical point y 0 ,
	i.e. ∇u(y 0 ) = 0.
	Remark 2.3. Part i) of Theorem 2.2 provides a local result in the smooth case, and still holds
	without the periodicity assumption on ∇u. It is then natural to ask if the local result remains
	valid when the potential u is only Lipschitz continuous. The answer is negative as shown in
	Example 2.4 below. We may also ask if a global realization of a periodic gradient can always
	be obtained with a periodic isotropic conductivity σ. The answer is still negative as shown in
	Example 2.6.
	The underlying reason for these negative results is that the proof of Theorem 2.2 is based
	on the rectification

  (e 1 + e 2 ) + (1 -χ) e 1 a.e. in R 2 , (2.23) which is divergence free in D ′ (R 2 ) since (e 1 + e 2 -e 1 ) ⊥ e 1 .

	This combined with (2.5) yields
	σ∇u = χ
							(2.20)
	which combined with (2.5) implies that
	∇u • ∇v = R ⊥ ∇u • ∇v = 1 a.e. in R 2 .	(2.21)
	Hence, after a simple computation formula (2.17) yields the rank-one laminate (see Sec-
	tion 3.2) conductivity
	σ = χ	2 1 1 1	+ (1 -χ)	1 4	1 1 1 5	a.e. in R 2 .	(2.22)

2

, that is

(2.15)

.

Example 2.9. Go back to the Examples 2.4 and 2.6 which provide examples of gradients which are not isotropically realizable electric fields. However, in the context of Theorem 2.7 we can show that the two gradient fields are realizable electric fields associated with anisotropic conductivities:

1. Consider the function u defined by (2.4), and define the function v by

v(x) := -x 1 + ˆx2 0 χ(t) dt, for any x = (x 1 , x 2 ) ∈ R 2 .

(2.19)

We have ∇v = χ (e 2 -e 1 ) + (1 -χ) (-e 1 ) a.e. in R 2 ,

  x and at a unique time τ H (x) ∈ R, in such a way that ∇u is not tangential to H at z H (x). Then, the gradient ∇u is an isotropically realizable electric field in R d .Example 2.11. Go back to Example 2.6 with the function u defined in R 2 by (2.9). The gradient field ∇u is smooth and Y 2 -periodic. The solution of the dynamical system (2.25) which reads as

  Definition 3.1. Let Ω be an (bounded or not) open set of R d , d ≥ 2, and let U = (u 1 , . . . , u d ) be a function in H 1 (Ω) d . The matrix-valued field DU is said to be a realizable matrix-valued electric field in Ω if there exists a symmetric positive definite matrix-valued σ ∈ L ∞ Let Y be a closed parallelepiped of R d , d ≥ 2. Consider a function U ∈ C 1 (R d ) d Assume that d = 2,and that DU is a realizable electric matrix field in R 2 , satisfying (3.2) and associated with a smooth conductivity in R 2 . Then, condition (3.3) holds true. iii) In dimension d = 3, there exists a smooth matrix field DU satisfying (3.2) and associated with a smooth periodic conductivity, such that det (DU) takes positive and negative values in R 3 . Remark 3.3. Similarly to Remark 2.8 the assertions i) and ii) of Theorem 3.2 still hold under the less regular assumptions that DU ∈ L 2 ♯ (Y ) d×d and det DU DU > 0 a.e. in R d .

	loc (Ω) d×d (3.1) (3.2) (3.3) Then, DU is a realizable electric matrix field in R d associated with a continuous conduc-such that Div (σDU) = 0 in D ′ (Ω). 3.1 The periodic framework Theorem 3.2. such that DU is Y -periodic and det DU = 0. i) Assume that det DU DU > 0 everywhere in R d . tivity. ii) (3.4)

Acknowledgement. The starting point of this work was the matrix field case. The authors wish to thank G. Allaire who suggested we study the vector field case. GWM is grateful to the INSA de Rennes for hosting his visits there, and to the National Science Foundation for support through grant DMS-1211359.


Mehdi Bennis

Samir Medina Perlaza

Game Theory and Femtocell Communications: Making Network Deployment Feasible

Introduction

Femtocell base stations (FBSs), also known as Home eNodeBs (HeNBs), are short-range low-power and low-cost base stations with third party backhaul (e.g., DSL or cable modem). They are usually deployed and controlled by end-users who desire better indoor signal transmission and reception. With the help of such FBSs, the network operator is able to extend the high quality coverage inside peoples' homes without the need of additional expensive cellular towers. At the same time, FBSs offload traffic from the overlay macrocell network and subsequently improve the overall network capacity. Nevertheless, despite FBSs promise, many concerns still remain, especially cross-tier interference. Two particular aspects of FBSs give rise to serious interference issues: (a) the co-channel spectrum sharing between femtocells and macrocells as well as among femtocells, (b) the "random" location of user-installed FBSs (they can be deployed anywhere inside the macrocell area with noprior warning). First, unlike Wi-Fi access points, FBSs serve users in licensed spectrum, to guarantee Quality-of-Service (QoS). Moreover, instead of allocating dedicated licensed channels to FBSs, sharing the spectrum is preferable from an operator's perspective (higher spectral efficiency). Secondly, FBSs are installed by end-users in a "plug-and-play" manner, which translates into "randomness" in their locations. For these two reasons, interference in two-tier networks is quite different than in conventional cellular networks, which endangers their successful co-existence. A typical scenario is the "Dead Zone" or "Loud Neighbor" problem, where mobile users transmit and receive signals at positions near FBSs but far from the macrocell BSs, causing significant macro-to-femto interference in the uplink. In the downlink, these users likewise suffer from low signal to interference ratios (SIRs) because of the strong interference from the FBSs. These affects are akin to the well known near-far problem, but exacerbated by the de-centralization and lack of coordinated power control inherent in two-tier networks. In addition, because of the non-existent coordination between FBSs and macrocell BSs, centralized cooperation to mitigate cross-tier interference is deemed infeasible, hence two-tier networks need to adopt decentralized strategies for interference management.

Game Theory (GT) is a mathematical tool that analyzes interactions among decision makers. GT is seen as a natural paradigm to study and analyze wireless networks where players compete for the same resources. The importance of studying the coexistence between macro-and femtocells from a game theoretical perspective is multi-fold: First, by modeling the dynamic spectrum sharing among network players (MBSs, FBSs, MUEs, FUEs) as games, the behaviours and actions of players can be analyzed in a formalized structure, by which the theoretical achievements in GT can be fully utilized. Second, GT equips us with various optimality criteria for the spectrum sharing problem, which are of key importance when it comes to analyzing the equilibria of the game. Third, the application of GT enables us to derive efficient distributed algorithms for self-organized networks relying only on partial information. In order to achieve this, the theory of learning in games is of high importance allowing players to choose the right strategies and gradually learn from their environment through trials and errors until convergence. The expected contribution is this chapter is as follows:

In the first section of the chapter, we show that the deployment of femtocell networks is cast into a dynamic spectrum sharing problem with different interference scenarios such as femtocell-to-femtocell and femtocell-to-macrocell interference. Femto base stations and their associated femtocell user equipments (FUEs) need to to autonomously determine their transmission strategies in order to maximize their own performance metrics. Often, this configuration is described by the power allocation scheme, channel/carrier selection, modulation scheme, etc. However, the transmission configuration of one femto-base station affects the performance of other FBS and all their associated FUEs. Hence, this scenario is clearly a competition of selfish autonomous devices for radio resources. Under these conditions, GT appears as one of the paradigms to study these types of networks. Finally, in this section, we provide the fundamental concepts of game theory required to understand the results presented in the rest of this chapter.

The second section tackles one of the most important issues in self organized networks, namely learning. Due to their non-coordinated nature, femtocells opportunistically share the spectrum with the macrocell network while mitigating their interference towards among others. In order to do so, femtocells need to self-organize and optimize their strategies/actions (power level, carrier allocation etc) taking into account their side information. Learning 4CHAPTER 1. GAME THEORY AND FEMTOCELL COMMUNICATIONS: MAKING NETWORK is an inherent part of self-organization paradigms and is crucial for developing and adapting multi-agent strategies based on their perceived reward. The problem boils down as to how femtocells gradually learn from their environment (through trials-and-errors) while at the same time not interfering with the overlay macrocell network. Furthermore, learning is adamantly driven by the type of information available at every agent where the possibility of exchanging their local information drives the learning efficiency (and convergence) and thereby their respective payoffs. For this purpose, we will investigate both private and public information exchange among femtocells.

The third section looks into the QoS provisioning of femtocell networks, in which femtocells mitigate their interference towards the overlay macrocell network. Tools from game theory and Stochastic geometry are used to come up with decentralized algorithms to achieve the equilibrium of the game.

The fourth section investigates the spectral efficiency of femtocell networks using the framework of potential games. Here, typical problems such as power allocation and channel selection are tackled in detail. We put in evidence the existence of the following paradoxes (observable only in decentralized networks): In a multi-carrier system, increasing the number of channels each device can use highly reduces the global performance of the system. Hence, it is more beneficial for a given network to constraint the devices to use a single channel rather than allowing them to simultaneously use several channels. Finally, we discuss several decentralized algorithms which allow self-configuring femtocell networks to achieve the equilibrium.

System Model

Consider a set of M = {1, . . . , M} macrocell base stations (MBS) each one operating over an exclusive fixed frequency band and serving their respective macrocell user equipments (MUEs) following a time division multiple access (TDMA) policy. At each time interval, each MBS serves one of its corresponding MUE aiming to guaranteing a minimum timeaverage signal to interference plus noise ratio (SINR) over their communication duration.

We assume that there exists a set N = {1, . . . , N} of N frequency bands over which MBS can operate. Let Γ (m) 0 , m ∈ M, denote the minimum time-average SINR offered by MBS m over its corresponding fixed frequency band. Consider now a set K = {1, . . . , K} of K femtocells underlaying the M-cell N-frequency band macrocell system. Each femtocell can use any of the available frequency bands to serve its corresponding femto end-users (FUE) as long as it does not induce a lower time-average SINR than the minimum required by the MUE, i.e., Γ

(1) 0 , . . . , Γ (M ) 0 . At each time interval each FBS serves one FUE over one of the available channels following a TDMA policy.

Let t ∈ {1, . . . , ∞} be a discrete time index. For all (j, k, m) ∈ M 2 × N , h (n) 1,j,k represents the channel realization between MBS k and MUE j over channel m at time t. For all

(j, k, m) ∈ K × M × N , h (n)
2,j,k represents the channel realization between MBS k and FUE j over channel n at time t. For all (j, k, m) ∈ M × K × N , h (n) 3,j,k represents the channel realization between FBS k and MUE j over channel n at time t. Finally, for all (j, k, m) ∈ K 2 × N , h (n) 4,j,k represents the channel realization between FBS k and FUE j over channel n at time t. Denote by h(t) the vector of all channel realizations at time t. All channel realizations, i.e., each component of h(t), are independent and identically distributed following a probability distribution which is a parameter of the network. Let the finite set denoted by H be the set of all possible vectors h(t), for all t > 0. Finally, channel realizations at time t are independent of those at time t -1, for all t > 0.

Let p k,max and p 0,m , with k ∈ K and m ∈ M, be the maximum transmit power of FBS k and MBS m, respectively. For all k ∈ K, let the N-dimensional vector p k (t) = p k (t) is the transmit power of femtocell k over frequency band n at time t. In the channel selection problem, all FBSs are assumed to transmit only over one frequency band at each time t at a given power level not exceeding p k,max . Let L k be the number of power levels of FBS k, i.e., p k,max L k , . . . , p k,max . For all (k, ℓ, s) ∈ K × {1, . . . , L K } × N , denote by the N-dimensional vector

q (ℓ,n) k = ℓ L p k,max e (N ) n , (1.1)
the power allocation (PA) vector when FBS transmits over channel n at power level ℓ. Denote 6CHAPTER 1. GAME THEORY AND FEMTOCELL COMMUNICATIONS: MAKING NETWORK also by q (0,0) k , with k ∈ K, the N-dimensional null vector, i.e., q (0,0) = (0, . . . , 0). Thus, FBS

k has N k = L k • S + 1 possible PA vectors, q (0,0) , q (1,1) k , . . . , q (L k ,N ) k . For all (k, n) ∈ K × N , let γ (n) k
be the SINR of FUE k at time t and for all m ∈ M, let γ (nm) 0,m be the SINR of the MUE in the macrocell m at time t. Let also the set M n ⊂ K, with n ∈ N , be the set of MBS using channel n. Then, we can write that

γ (n) k (t)= p (n) k (t) h (n) 4,k,k (t) 2 σ (n) 2 k + m∈Mn p 0,m| h (n) 2,k,m (t) | 2 + j∈K\{k} p (n) j (t) | h (n) 4,k,j (t) | 2 (1.2)
and for all m ∈ M,

γ (nm) 0,m (t)= p 0,m h (nm) 1,m,m (t) 2 σ 2 0,m + j∈Mn m \{m} p 0,j | h (nm ) 1,m,j (t) | 2 + i∈K\{k} p i,max| h (nm) 3,m,i (t) | 2 , (1.3)
where for all m ∈ M, n m is the channel used by MBS m and σ

(nm) 0,m 2 and σ (nm) k
2 is the noise power over MUE m and the noise power over FUE k on the frequency band n.

All FBSs are interested in optimizing a given interference mitigation metric denoted by u : R N •K+M → R, which determines at each instant t the impact of the interference on the macro system based on the observation of all the SINR levels γ

(n) k and γ (nm) 0,m , with (k, n) ∈ K × N and m ∈ M.
In the case of multiple access channels (MACs), femtocell base stations communicate with a single receiver using a common channel. This case can happen when femto user equipments compete for the same resources in the uplink, or when FBSs compete for backhaul resources. We assume that there exists a set N = {1, ..., N} of N frequency bands over which transmitters operate. If N > 1 channels are available, then there exists N independent or parallel MACs, where transmitters in different MACs do not interfere each other. Moreover, the channel gain from transmitter k ∈ K to the receiver over channel n ∈ N is denoted by

h (n)
k . We assume a block flat-fading channel model such that channel realizations remain constant during the transmission of M consecutive symbols. All the channel realizations, ∀k ∈ K and ∀n ∈ N are drawn from a Gaussian distribution with zero mean and unit variance. The power allocated by transmitter k to channel n is denoted by p (n) k . Each transmitter is power-limited wherein for the i th transmitter, its transmit power cannot exceed

p k,max , i.e., ∀k ∈ K, N n=1 p (n) k ≤ p k,max .
The received SINR on channel n for transmitter k, denoted by γ

(n) k for all ∀(k, n) ∈ K × N is: γ (n) k = p (n) k |h (n) k | 2 K j =k p (n) j |h (n) j | 2 + σ 2 (1.4)

Game Theory and Self-Organized Femtocell Networks

In the following, we introduce basic concepts and definitions of game theory which will be used throughout the chapter.

Strategic-Form Games

The spectrum sharing between the macro and femtocells can be respectively modeled by the following two non-cooperative static games in strategic form (with i ∈ {a, b}):

G (i) = K, P (i) k k∈K , (u k ) k∈K . (1.5)
Let K be the set of players (i.e., FBSs). An action of a given FBS k ∈ K is a particular power allocation (PA) scheme, i.e., an N-dimensional PA vector

p k = p (1) k , . . . , p (N ) k ∈ P (i) k , where P (i)
k is the set of all possible PA vectors which FBS k can use either in the game G (a) (i = a) or in the game G (b) (i = b). An action profile of the game i ∈ {a, b} is a super vector p = (p 1 , . . . , p K ) ∈ P (i) , where P (i) is a set obtained from the Cartesian product of the action sets

P (i) k , for all k ∈ K, 8CHAPTER 1.

GAME THEORY AND FEMTOCELL COMMUNICATIONS: MAKING NETWORK

i.e., P (i) = P In this chapter, we respectively refer to the games G (a) and G (b) as the PA game and CS game. Let us denote by p -k any vector in the set

(i) 1 × . . . × P (i) K , where, P (a) k = p (1) k , . . . p (N ) k ∈ R N : ∀n ∈ N , p (n) k 0, (1.6
P (i) -k △ = P (i) 1 × . . . × P (i) k-1 × P (i) k+1 × . . . × P (i) K (1.8)
with (i, k) ∈ {a, b} × K. For a given k ∈ K, the vector denoted by p -k represents the strategies adopted by all the players other than player k. With a slight abuse of notation, we write any vector p ∈ P (i) , with i ∈ {a, b}, as p k , p -k , in order to emphasize the k-th vector component of the super vector p. The utility for player k in the game G (i) is its spectral efficiency u k : P (i) → R + , with i ∈ {a, b} and

u k (p k , p -k ) = n∈N B n B log 2 1 + γ (n) k [bps/Hz] (1.9)
where γ

(n) k
is the SINR of Femto base station k over channel n.

Potential Games

Potential games (PG) [START_REF] Monderer | Potential games[END_REF] are a class of games for which existence of pure NE is guaranteed.

Definition 1 (Exact Potential Game) Any game in strategic form defined by the 3-tuple K, (P k ) k∈K , (u k ) k∈K is an exact potential game if there exists a function φ (p) for all p ∈ P such that for all players k ∈ K and for all p ′ k ∈ P k , it holds that

u k (p k , p -k ) -u k (p ′ k , p -k ) = φ(p k , p -k ) -φ(p ′ k , p -k ).
Definition 2 (Exact Constrained Potential Game) Any game in normal form defined by the 4-tuple

K, {P k } k∈K , {c k } k∈K , {f k } k∈K is an exact constrained potential game (PG)
if there exists a function φ (s) for all p ∈ P SE such that for all players k ∈ K and for any

pair of actions (p k , p ′ k ) ∈ f k p -k 2 , it holds that c k (p k , p -k ) -c k (p ′ k , p -k ) = φ(p k , p -k ) -φ(p ′ k , p -k ).
Using the spectral efficiency utility function (1.9), the following proposition holds:

Proposition 1 The strategic games G (i) , with i ∈ {a, b}, are exact potential games with potential function

φ(p) = n∈N B n B log 2 σ 2 n + K k=1 p (n) k g (n) k
.

(1.10)

In fact, the games G (i) , i ∈ {a, b} are not only potential games but also best-response potential games [START_REF] Voorneveld | Best-response potential games[END_REF]. A BRPG is a PG which verifies: arg max

q k ∈P (i) k u k q k , p -k = arg max q k ∈P (i) k φ q k , p -k . (1.11)
Indeed, the utility function (1.9) can be written in terms of the potential function (1.10) as

follows ∀k ∈ K, u k p k , p -k = φ p k , p -k -υ k p -k ,
where

υ k p -k = n∈N B n B log 2   σ 2 n + j∈K\{k} p (n) j g (n) j   ,
and by inspection, it becomes clear that both G (a) and G (b) satisfy the condition (1.11).

In other words, condition (1.11) shows that the individual utility maximization problem is 10CHAPTER 1. GAME THEORY AND FEMTOCELL COMMUNICATIONS: MAKING NETWORK equivalent to maximizing a common function.

The Concept of Equilibrium

Our interest is to find a strategy profile p such that no player is interested in changing its own strategy. Once the network configuration p * is reached, any unilateral deviation of a given player decreases its own utility. A network configuration p * is known as a Nash equilibrium [START_REF] Nash | Equilibrium points in n-person games[END_REF].

The Nash equilibrium (NE) is an important concept in the field of game theory wherein an N.E corresponds to a profile of strategies p * = (p * 1 , ..., p * K ) for which each player's strategy p * 1 ∈ P is an N.E if it satisfies:

∀k ∈ K and ∀p k ∈ P K , u k (p * k , p * -k ) ≥ u k (p k , p * -k ) (1.12)
That is, at the NE, any unilateral deviation from the strategy profile p k of player k, ∀k ∈ K will not increase its utility function. Hence, at the NE there does not exist any motivation for a player to deviate from the NE strategy profile. As players are selfish and decide by themselves their strategy, one question arises: does an NE lead to an efficient game outcome? The NE is generally inefficient and non-optimal, however it is a lower bound in the case of non-cooperation between players.

Definition 3 (Satisfaction Equilibrium) An action profile p + is a satisfaction equilibrium for the game

G ′ = K, {P k } k∈K , {f k } k∈K if ∀k ∈ K, p + k ∈ f -k p + k . ( 1
) ∈ △ (A 1 ) , × . . . , ×△ (A K ) is a logit equilibrium, if ∀k ∈ K, π * k = β k ûk π * -k , (1.15)
where the N k dimensional vector ûk (π -k ) = ûk,q (0,0)

k (π -k ) , ûk,q (1,1) k (π -k ) , . . . , ûk,q (L k ,N) k (π -k )
is the expected interference minimization metric, i.e., for all k ∈ K and for all (

ℓ k , n k ) ∈ {1, . . . , L k } × N ∪ {(0, 0)}), u k,q (ℓ k ,n k ) k (π -k )=E p -k ∈P -k j∈K\{k} π * j,p j u(h,q (ℓ k ,n k ) k ,p -k )h.
and:

β k (û k ) = exp 1 κ k ûk (i,j)∈N ×L exp 1 κ k ûk (1.16)
Where ∀k ∈ K and ∀(s, l) ∈ N × L, β k (û k ) > 0 regardless of the estimation vector ûk .

Definition 6 (Best-Response Correspondence) In a non-cooperative game described by the 3-tuple K, (P k ) ∀k∈K , (u k ) ∀k∈K , the relation BR k :

P -k → P k such that BR k (p -k )=arg max q k ∈P k u k (q k ,p -k ), (1.17)
is defined as the best-response correspondence of player k ∈ K, given the actions p -k adopted by all the other players.

Definition 7 (Best Response Dynamics) Let the action profile p(t) = (p 1 (t), . . . , p K (t))

be the result of a best-response dynamics at time t. Then, for all k ∈ K, and for all t ∈ N and t > 0, the vector p k (t) can be obtained as follows: (1) In the sequential best-response 12CHAPTER 1. GAME THEORY AND FEMTOCELL COMMUNICATIONS: MAKING NETWORK dynamics (round-Robin order):

p k (t)∈BR k (p 1 (t),...,p k-1 (t),p k+1 (t-1),...,p K (t-1)), (

(2) in the simultaneous best-response dynamics:

p k (t) ∈ BR k p -k (t -1) , (1.19)
where p(0) can be any vector p ∈ P.

Learning mechanisms for femtocell networks

Two mechanisms for interference mitigation, inspired by evolutionary game theory and reinforcement-based learning [START_REF] Hofbauer | Evolutionary Games and Population Dynamics[END_REF] to support the coexistence of a macrocell network and underlaid self-organized femtocells are herein compared in terms of achievable performances as well as needed signalling. In both approaches, femto base stations rely on the measurements fed back by their user equipments in order to update their strategy until an eventual convergence.

Evolutionary-based approach

The first interference mitigation mechanism is based on the concept of evolutionary game theory, where each FBS chooses its strategy against other FBSs located within the same network. FBSs observe the behavior of other competitors, learn from the observations, and make the best decision based on their instantaneous payoff, as well as the average payoff of all other femtocells. The game theoretic model G (ev) = K, (A k ) k∈K , (u k ) k∈K is formulated as follows:

• K = {1, ..., K} is the set of players (i.e., femtocell base stations),

• A t k = {a k,s t } k∈K where a k,n t is the action of FBS k at time t is to transmit over a carrier

LEARNING MECHANISMS FOR FEMTOCELL NETWORKS

n.

• R t k = n log 2 1 + SINR is the reward of FBS k transmitting in sub-carrier n at time t. Moreover, the average payoff of the entire population is defined as: Rt

k = k R t k K .
In the aforementioned mechanism, an entity which is referred to as HNB-Gateway [START_REF] Gpp | TR:3GPP-TR25.820, 3G Home Node B Study Item[END_REF] collects the payoffs for all femtocells and calculates the average rate of the entire femtocell network. The payoff R t k of FBS k is then compared with the average payoffs Rt k and in the case when it is less that the average rate of the femtocell network, a random strategy is chosen and the whole process is repeated again.

Q-learning based approach

The Q-learning model consists of a set of states n ∈ N and actions a ∈ A aiming at finding a policy that maximizes the observed rewards over the interaction time of the agents/players (i.e., femtocells). Every FBS k ∈ K explores its environment, observes its current state s, and takes a subsequent action a, according to a decision policy π : s → a. With their ability to learn, the knowledge about other players' strategies is not explicitly needed by FBS k.

Instead, a Q-function maintains the knowledge about other players in the network locally, based on which decisions are made. Several authors have shown that Q-learning converges to optimal values in Markov decision process environment. Thus, the goal of the agent is to find an optimal policy π * (s) for each state s, which maximizes a cumulative measure of the rewards over time.

The expected discounted reward over an infinite horizon is given by:

V π (s) = E γ t × r(s t , π * (s t ))|s 0 = s , (1.20)
where 0 ≤ γ ≤ 1 is a discount factor and r is the agent's reward at time t. Furthermore, 14CHAPTER

GAME THEORY AND FEMTOCELL COMMUNICATIONS: MAKING NETWORK

Equation (1.20) can be rewritten as:

V π (s) = R(s, π * (s)) + γ v∈S P s,v (π(s))V π (v), (1.21)
where R(s, π * (s)) = E{r(s, π(s))} is the mean value of reward r(s, π(s)), and P s,v is the transition probability from state s to v. Moreover, the optimal policy π * satisfies the optimality criterion:

V * (s) = V π * (s) = max a∈A R(s, a) + γ v∈N P s,v (a)V * (v) , (1.22)
It is generally difficult to explicitly calculate the reward R(s, a) and transition probability P s,v (a). However, through Q-learning, the knowledge of these values can be gradually learnt and reinforced with time. For a given policy π, define a Q-value as:

Q * (s, a) = R(s, a) + γ v∈S P s,v (a)V π (v), (1.23)
which is the expected discounted reward when executing action a at state s and then following policy π thereafter.

We make use of the Q-learning algorithm to iteratively approximate the state-action value function Q(s, a). Here, the FBS keeps trying all actions in all states with non-zero probability and must sometimes explore by choosing at each step a random action with probability β ∈ (0, 1). Alternatively, FBSs can make use of the Boltzmann exploration strategy with the temperature parameter κ, where the action a in state s is taken with a probability P (a|s), and the femtocell receives a reinforcement r. The actions are chosen according to their Q-values as:

p(a|s) = e Q(s i ,a)/κ a ′ =a e Q(s i ,a ′ )/κ . (1.24)
The game is defined as follows: G (rl) = K, (P k ) k∈K , (u k ) k∈K where

• K = {1, ...,
• R t k = 1 {Γ 0 -C 0 } n∈C log(1 + SINR) is the reward of FBS k transmitting in the set C at time t.
In the Q-learning process, in which FBS k performs the exploration step with probability

β. A new Q-value, i.e., Q(S t+1 k , A t+1 k )
, which is the expected payoff for the future iterations, is obtained based on previous value, i.e., Q(S t k , A t k ), along with the new observed payoff R k t+1 (S k t+1 ). Moreover, the Q-learning is updated as follows:

Q(S t k , A t k ) = (1 -α)Q(S t k , A t k ) + α R k t+1 (S k t+1 ) + γ max B t+1 k Q(S t+1 k , B t+1 k ) (1.25)
where α is the players' willingness to learn from its environment and γ is the discount factor.

QoS provisioning for femtocell network

The focus is on a fully decentralized approach for solving interference mitigation from the FBS to the macrocell user equipments (MUEs). The underlying assumption is that MUEs feed back messages to their corresponding macrocell BS containing their instantaneous SINR (decoded by all FBSs). The repetitive observation of the SINR is used by the FBS to dynamically configure their frequency band and power levels such that a minimum timeaverage SINR can be guaranteed at the macrocells. We make use of recent results in game theory and stochastic approximation applied to the problem of femto-to-macrocell cross-tier interference.

The At each time t > 0 and for all k ∈ K, FBS k chooses its action from the finite set A k following a probability distribution π k (t) = π k,q (1,1) .26) where (l k , n k ) ∈ {1, ..., L K } × S ∪ {(0, 0)} In the following, we describe the long-term game G, and we introduce the method which each FBS uses to choose the probability distribution π k (t), at each time t.

k (t), ..., π k,q (L k ,N k ) k (t) where π k,q (l k ,n k ) k is the probability that femtocell k plays action q (l k ,n k ) k at time t, i.e., π k,q (l k ,n k ) k = Pr p k (t) = q (l k ,n k ) k . ( 1

Long-Term Formulation

The long-term behaviour of the network is modeled by the succession of static strategic games

G = {G (h(t))} t 0 .
This succession produces a Markov game G = {G(h(t))} t 0 , where at each stage t the game G(h(t)) is played assuming that the network is described by the vector h(t). According to the system model, the actual state of the network h(t) follows a Markov chain with transitions following the rule,

∀ (h ′ , h ′′ ) ∈ H 2 , Pr (h(t) = h ′ |h(t -1) = h ′′ ) = Pr (h(t) = h ′ ) = π h ′ .
Here, π h ′ , for all h ′ ∈ H, are parameters obtained from previous channel modeling studies. Note that transitions between states are independent of the actions of the transmitters. The game G = {G(h(t))} t 0 proceeds in infinitely many stages. At each stage t ∈ {0, . . . , ∞}, FBSs choose their corresponding actions p 1 (t), . . . , p K (t). When doing so, each FBS k observes a noisy sample ũk (t) of the corresponding instantaneous interference minimization metric u(h(t), p k (t), p -k (t)), i.e.,

ũk (t) = u(h(t), p k (t), p -k (t)) + ε k,p k (t) (t), (1.27)
where,

∀(ℓ k , n k ) ∈ {1, . . . , L k } × S ∪ {(0, 0)}, and ∀k ∈ K, ε k,q (ℓ k ,n k ) k (t) is the realization at time t of a random variable ε k,q (ℓ k ,n k ) k
which represents the additive noise on the observation of the instantaneous performance u(t) when FBS k plays action q

(ℓ k ,n k ) k
. Here, we assume

that Eε k,q (ℓ k ,n k ) k = 0.
Our behavioral assumption is that all FBS are interested on choosing the probability distribution π k (t) ∈ △ (A k ) to optimize the time-average interference minimization metric at each time t > 0, i.e., ūk (t), which is calculated empirically based on the observations ũk (t) as follows,

ūk (t) = 1 t t n=1 u k (n). (1.28)
To choose the optimal probability distribution π k (t), the FBS relies on estimations of the time-average interference minimization metric obtained with each of its actions. For all (ℓ k , n k ) ∈ {1, . . . , L k } × S ∪ {(0, 0)}, let ûk,q (ℓ k ,n k ) k (t), be the estimation of time-average interference minimization metric obtained by playing action q

(ℓ k ,n k ) k
. This estimation is calculated as follows, ûk,q (ℓ k ,n k )

k (n) = 1 T k,q (ℓ k ,n k ) k (t) t n=1 ũk (n)1 p k (n)=q (ℓ k ,n k ) k , (1.29)
where,

T k,q (ℓ k ,n k ) k (t) = t n=1 1 p k (n)=q (ℓ k ,n k ) k . Once the N k -dimensional vector of estimations of FBS k is obtained, i.e., ûk = ûk,q (0,0) k , ûk,q (1,1) k , . . . , ûk,q (L k ,S) k for all k ∈ K, it is used to determine the optimal probability distribution π k (t) = π k,q (0,0) k , π k,q (1,1) k , . . . , π k,q (L k ,S)
k at each time t. For doing so, we define the function β k : R N k → △ (A). Note that the probability distribution β k (û k (t)) must take into consideration that, FBSs must experiment between different actions such that the estimation vector ûk (t) is improved at each time t, but also FBSs must optimize their respective interference minimization metric.

18CHAPTER 1. GAME THEORY AND FEMTOCELL COMMUNICATIONS: MAKING NETWORK

Exploration vs. Performance Optimization

Femtocells face a trade-off between optimizing their time-average utility by taking the action that does it at each time t, and trying out different actions so as to improve the estimation of the time-average interference mitigation metric obtained with each action. This implies that a reasonable behavioral rule would be to choose the actions which yield high payoffs more likely than actions yielding low payoffs, but in any case, always letting a non-null probability of playing any of the actions. Following the results in [START_REF] Perlaza | Radio resource sharing in decentralized wireless networks: a dynamical system approach[END_REF], the behavioral rule described above can be modeled by the probability distribution β k (û k (t)) satisfying:

β k (û k (t)) ∈ arg max π k ∈△(A k ) p k ∈A k π k,p k ûk,p k (t) + κ k H(π k ) (1.30)
where H represents the Shannon entropy function. For all k ∈ K, the parameter κ k > 0 represents the interest of FBS k to choose other actions rather than the optimal one in order to improve the time-average interference minimization metric. The unique solution to the right hand side of the optimization problem in (1.30) is written as (1.16):

β k (û k (t))= β k,q (0,0) k (û k (t)),β k,q (1,1) k (û k (t)),...,β k,q (L k ,S) k (û k (t)) , (1.31)
In order to achieve the LE of game G = {G(h(t))} t 0 . Assume that the estimation of the time-average interference minimization metric and the mixed strategy of FBS k are calculated as follows, ∀k ∈ K and

∀(ℓ k , n k ) ∈ {1, . . . , L k } × N ∪ {(0, 0)},                    ûk,q (ℓ k ,n k ) k (t) = ûk,q (ℓ k ,n k ) k (t-1)+ α(t) 1 p k (t)=q (ℓ k ,n k ) k π k,q (ℓ k ,s k ) k (t) ũ(t)-û k,q (ℓ k ,n k ) k (t-1) , π k,q (ℓ k ,n k ) k (t) = π k,q (ℓ k ,n k ) k (t-1)+ λ(t) β k,q (ℓ k ,s k ) k (û k (t))-π k,q (ℓ k ,n k ) k (t-1) , (1.32)
where, ûk (0) ∈ R N k and π k (0) ∈ △ (A k ) are arbitrary initializations and λ and α are learning rates chosen such that lim

lim t→∞ ûk,q (ℓ k ,s k ) k (t) = u k (π * -k ), (1.37)
where π * = (π * 1 , . . . , π * K ) is a LE of the game G = {G(h(t))} t 0 .

Spectral Efficiency in Femtocell Networks

Power Allocation Problems

The PA game G (a) models the scenario where FBSs allocate any power level to any of their own channels subject to the power constraints given in (1.6)

20CHAPTER 1. GAME THEORY AND FEMTOCELL COMMUNICATIONS: MAKING NETWORK

It is proved in [START_REF] Perlaza | Spectral Efficiency of Decentralized Parallel Multiple Access Channels[END_REF] that the game G (a) is an exact potential game, and hence at least one NE in pure strategies exists. Similarly, at least one NE in mixed strategies exist because the action spaces, P

k for all k ∈ K are convex and compact in their respective finite dimensional spaces, and the utility is jointly continuous [START_REF] Fan | Fixed-point and Minimax Theorems in Locally Convex Topological Linear Spaces[END_REF]. Furthermore, the game G (a) is shown to have a unique NE strategy profile in pure strategies, p † ∈ P (a) with probability one, solution of the following optimization problem:

p † ∈ arg max p∈P (a)
φ (p) .

(1.38)

The components of the vector p † in (1.38) are for all (k, s) ∈ K × N , (p

(n) k ) † =      B n B 1 β k - σ 2 n + j∈K\{k} (p (n) j ) † g (n) j g (n) k      + , (1.39)
where, β k is a Lagrangian multiplier chosen to saturate the power constraints (1.16).

Assuming that each transmitter knows its actual channel gains g k = g

k , . . . , g an NE [START_REF] Young | Strategic Learning and Its Limits (Arne Ryde Memorial Lectures Sereis)[END_REF].

It is worth noting that the sequential BRD in the game G (a) lead to the same result as the iterative water-filling algorithm (IWFA) presented in [START_REF] Yu | Iterative water-filling for Gaussian vector multiple-access channels[END_REF] but under a different setting. One of the main drawbacks of the iterative BRD (and IWFA) is its large time for convergence as well as its required signaling (message κ(t)). To overcome this problem, other algorithms such as the simultaneous water-filling algorithm (SWFA), which follows the simultaneous best-response dynamics (Def. 7) was proposed [START_REF] Scutari | Simultaneous Iterative Water-Filling for Gaussian Frequency-Selective Interference Channels[END_REF].

Different information drive different convergence behaviors. In terms of convergence, the IWFA (iterative BRD) always converges. The SWFA (simultaneous BRD), at least on the interference channel, converges to an NE depending on the channel realizations and the number of active transmitters [START_REF] Scutari | Simultaneous Iterative Water-Filling for Gaussian Frequency-Selective Interference Channels[END_REF]. In the interference channel PA game in [START_REF] Scutari | Simultaneous Iterative Water-Filling for Gaussian Frequency-Selective Interference Channels[END_REF], when the SWFA converges, hence it converges faster than the IWFA. Finally, the IWFA requires a (broadcast) signaling message (the multiple access interference over each channel) every time that a given transmitter updates its PA vector. Conversely, SWFA requires one message after all transmitters have updated their PA vector.

Channel Selection Problems

Here, a constraint is imposed onto the femtocells, in which they can only transmit over one channel at a time. It is ready to check that every femto BS has to saturate its transmit power to maximize its utility. Indeed, ∀k ∈ K and ∀p -k ∈ P The game G (b) is an exact potential game (Prop. 1) and thus, following Lemma 2.3 in [START_REF] Monderer | Potential games[END_REF], the game G (b) has always at least one NE in pure as well as mixed strategies. To identify an upper-bound of the number of NE, basic tools from graph theory in which L ∈ N multiple pure NE strategy profiles exist, and 1 L S K-1 .

Assuming that the game is played repeatedly, one can exploit Prop. ?? to state that BRD converges to an NE. The best response of transmitter

k ∈ K in the game G (b) is BR k p -k = {p k ∈ P k : p k = p k,max e n * k and n * k = (1.40) arg max n∈N B N B log 2 1+ p k,max g k,n σ 2 n + j∈K\{k} p j,max g j,n },
and can be determined locally by each transmitter using the feedback message, the knowledge of its own channel realizations and the bandwidth of each channel.

22CHAPTER 1. GAME THEORY AND FEMTOCELL COMMUNICATIONS: MAKING NETWORK

Besides the BRD (iterative and sequential, Def. 7), when the set of actions is discrete, other dynamics such as fictitious play [START_REF] Brown | Iterative Solution of Games by Fictitious Play[END_REF], reinforcement learning (RL) [START_REF] Young | Strategic Learning and Its Limits (Arne Ryde Memorial Lectures Sereis)[END_REF], among some others, converge to equilibrium in the game G (b) , and more importantly, the information assumptions can be significantly relaxed [START_REF] Perlaza | How can Ignorant but Patient Cognitive Terminals Learn Their Strategy and Utility?[END_REF].

Let us denote by p k (t) ∈ P For the ease of notation, we use the equality u k (t) = u k h(t), p k (t), p -k (t) . At each time t, each player k ∈ K chooses its action p k (t) following a probability distribution π k (t) = π k,p k at time t, i.e., π k,p k (t) = Pr (p k (t) = p k ). In the fictitious play (FP) [START_REF] Brown | Iterative Solution of Games by Fictitious Play[END_REF], player k ∈ K must observe the actions of all the other players at each time t and be able to calculate the empirical probability distributions π j (t), for all j ∈ K \ {k}. At each time t, the action of player k is:

p k (t) ∈ arg max p k ∈P (b) k E π -k u k (p k , p -k ).
(1.41)

In the reinforcement learning (RL), e.g. replicator dynamics [START_REF] Hofbauer | Evolutionary Games and Population Dynamics[END_REF], transmitters k ∈ K observes a numerical sample ũk (t) of its obtained utility at each time t and its set of actions P

k are supposed to be known. At each time t, transmitter k chooses its PA vector following the probability distribution π k (t), which is updated based on ũk (t), as follows,

π k,p (n) k (t) = π k,p (n) k (t-1)
(1.42)

+λ k (t)ũ k (t) {p k (t)=p (n) k } -π k,p (n) k (t-1) ,
where λ k (t) is such that 0 λ k (t)ũ k (t) 1, for all k ∈ K and t > 0.

The FP converges (at least in probability) to NE in potential games [START_REF] Monderer | Fictitious Play Property for Games with Identical Interests[END_REF]. On the contrary, the convergence of the RL is conditioned on the initial strategies of the dynamics π k (0), for all k ∈ K [START_REF] Hofbauer | Evolutionary Games and Population Dynamics[END_REF]. Moreover, in the FP, players must be able to solve at each time t, the optimization problem (1.41). Hence, the computational capabilities depend on the complexity of the utility function. Conversely, in RL only arithmetic operations are required, since the utility is assumed to be observed at each time t. Besides, In the FP players are supposed to know the structure of the game and observe the actions of all the other players. In RL, players know only their own actions and are able to observe a numerical value of the obtained utility.

Finally, in the FP players are assumed to be myopically rational, i.e., players take the action which maximizes their instant utility. In contrast, the rationality assumption is not required in the RL case. Here, players take randomly (subject to a probability distribution) an action which might or not maximize its own utility. Note that unlike RL, FP is too demanding in terms of information assumptions.

Conclusions and open issues

In this chapter, we have looked at the strategic interaction between the macrocell and underlaid femtocells from a game theoretic perspective. Different game theoretic formulations were investigated along with different information assumption. It turns out that game theory along with learning theory are two key enabling frameworks for the analysis and design of femtocell networks. Yet, more work is needed for addressing the strategic interaction of femtocells such as in the case of hierarchy and cooperation among femtocells.

( 1 )

 1 k (t), ..., p (N ) k (t) denote the power allocation vector of FBS k ∈ K at time t. Here p

=( 1 . 7 )

 17 p k,max e n : ∀n ∈ N , e n = e (1) n , . . . , e (N ) n and ∀r ∈ N \ n, e n (r) = 0, and e (n) n = 1 .

  Spectral efficiency in femtocell networks is instrumental for the successful deployment of femtocells. Here, Femtocells access the spectrum in a parallel multiple access mode. Two particular deployment scenarios are hereafter studied: (a) FBSs strategically split their transmit power between the available channels, and (b) FBSs use only one channel at a time. In both cases, FBSs maximize their individual spectral efficiency. Problems (a) and (b), which respectively correspond to a decentralized power allocation and channel selection problem, are modeled by strategic form games.

  N ) k, the bandwidth of all channels b = (B 1 , . . . , B N ), and its own actual PA vector p k , each transmitter can determine its best response(1.19) based on a common message from the receiver, and hence obtain the unique outcome of the game using the best response dynamics (BRD) in which the sequential best response dynamics of any potential game converges to

  φ p k e n , p -k < φ p k,max e s , p -k where e n = e (1) n , . . . , e (N ) n ∈ R N , ∀r ∈ N \ n, e problem under investigation is therefore a channel selection problem. Technically, the main difference between G (a) and G (b) is that the latter is a finite game (|K × N | < +∞). As a consequence, the number of pure NE is generally more than 1.

  t) ∈ H the action taken by player k and the vector of channel realizations at time t. Hence, for all k ∈ K, u k : H × P (b) → R, and u k h(t), p k (t), p -k (t) represents the instantaneous utility obtained by player k at time t.

  , . . . , π k,p (N) k (t) , where ∀k ∈ K and ∀p k ∈ P (b) k , π k,p k (t) represents the probability that player k plays action p k ∈ P (b)

  is one of the efficient SE (ESE) of the game G ′ . Definition 5 (Logit Equilibrium): Consider the Markov game G = {G(h(t))} t 0 . The mixed strategy profile π * = (π * 1 , ..., π * L

	only if:
	∀k ∈ K, p * k ∈ arg min p k ∈f k (p * -k )	c k (p k ) .	(1.14)
	Then, p

.13) Definition 4 (Efficient Satisfaction Equilibrium) Define a function c k : P k → [0, 1] for all k ∈ K and consider the game G ′ . For all (k, p * k , p ′ k ) ∈ K × P 2 k , the action p ′ k is said to be more costly that action p * k if c k (p ′ k ) > c k (p k ). An action profile p * ∈ P is an ESE if and *

  1}. The state of every FBS k at time t in sub-carrier n indicates whether FBS k generates interference towards MUE and the QoS of MUE is violated, (i.e., C 0 < Γ 0 ).

	• S t k = {s k,n t } k∈K where s k,n t ∈ {0, • A t k = {a k,n t } k∈K where a k,n t is the action of FBS k at time t is to transmit over a set of
	sub-carrier C ∈ {1, ..., N sub }.

K} is the set of players (i.e., femtocell base stations),

  {A k } k∈K , {φ} k∈K ) the static strategic game and let us denote by G = {G(h(t))} t>0 the stochastic game where at each time t, the game G(h(t)) is played, with t ∈ {1, . . . , ∞}. In order to define the stochastic game, a short and long-term formulation is given:Let us describe the network during the interval from t -1 to t by the game G(h(t)) = (K, {A k } k∈K , {u} k∈K ). Here, K represents the set of FBS in the network. For all k ∈ K, the set of actions of FBS k is the set of PA vectors, i.e., A k = {q Finally, u : H × A 1 × A K → R + is the payoff or interference minimization metric of all femtocells.

	(ℓ,n) k	: ℓ ∈ {0, . . . , L k }, and n ∈
	N }.

interference minimization problem is modeled by a stochastic game made of a sequence of strategic games played at different states, e.g., channel realizations. Let us de-16CHAPTER 1. GAME THEORY AND FEMTOCELL COMMUNICATIONS: MAKING NETWORK note by G(h(t)) = (K,

Contents