Raphaël Lachièze-Rey

The convex class of realisable unit covariances

Keywords: Random sets, realisability problem, second order marginals, covariance, convex polytopes AMS Classification: 60D05, 52B11

The convex class of realisable unit covariances

Raphaël Lachièze-Rey

Introduction

Let X be a set, and call B X = {-1, 1} X the class of binary functions on X . Call unit field on X a random element X in B X The unit covariance of X is then defined by ρ X

x,y = EX x X y = 2P(X x = X y ) -1, x, y ∈ X .

(1.1)

The central question here is the inverse realisability problem, given a bivariate function (ρ x,y ; x, y ∈ X ) in the class F X of symmetric functions on X , to check whether it can be realised by some unit field X (i.e. ρ = ρ X ). The typical example of a non-realisable, or non-admissible, symmetric function ρ is, with X = {1, 2, 3},

ρ 1,2 = 1, ρ 1,3 = 1, ρ 2,3 = -1, ρ i,i = 1; i = 1, 2, 3,
because if ρ = ρ X for some unit field X, then X 1 = X 2 a.s., X 2 = X 3 a.s., but X 1 = -X 3 a.s.. Measurability issues don't matter in this paper, so consider that B X is endowed with the discrete topology. The affine transformation X → 2X -1 transfers unit fields to {0, 1}-valued processes, assimilable to random sets. Such marginal problems arise in many contexts, the article [START_REF] Frits | Entropic inequalities and marginal problems[END_REF], for instance, calls contextual such an admissible function, in the sense that it can be inserted in a real physical context, with applications in the fields of information theory, game theory, quantum mechanics. The authors use an entropic approach to solve some particular related questions. Our goals turn more towards materials science and geostatistics, where such a characterisation could serve many purposes in modelisation and estimation, see the companion paper [START_REF] Lachièze-Rey | Checking realisability of set covariances[END_REF] for more details. On a more theoretical level, characterising the class of second order characteristics would provide insights on a spectral theory for random sets, which apart from Koch et al. [START_REF] Koch | Spectral theory for random closed sets and estimating the covariance via frequency space[END_REF] is currently a gap in the literature. Matheron identified a combinatorially compact description of the class of realisable unit covariances if card(X ) ≤ 6, highlighting an elegant combinatorial structure.

Call U X the class of admissible unit covariances on X ×X . It is clear under the form (1.1) that to belong to U X a function ρ has to be semi-definite positive, and lie in the space F 1 X of functions taking the value 1 on the diagonal (ρ x,x = 1 for all x ∈ X ), but those conditions are not sufficient. Let F ′ X be the space of symmetric functions with finite support, and define for

α ∈ F ′ X g α (u) = x,y∈X α x,y u x u y ; u ∈ B X .
A necessary and sufficient condition for ρ ∈ F X to be a unit covariance is that for every function α ∈ F ′ X ,

x,y∈X

α x,y ρ x,y ≥ κ α := inf u∈B X g α (u), (1.2)
because then the operator that ρ induces on the vector space spanned by constant functions and functions {g α : α ∈ F ′ X } is positive, and one can apply Kantorovitch and Riesz-Markov theorems (see [START_REF] Lachièze-Rey | Regularity conditions in the realisability problem in applications to point processes and random closed sets[END_REF]) (the necessity of (1.2) is a straightforward consequence of the positivity of the mathematical expectation). In this context, ρ is sometimes loosely referred to as being positive.

The inequalities (1.2) are the linear inequalities determining the convex set U X , and we show in this article how this approach, effective in [START_REF] Shepp | On positive-definite functions associated with certain stochastic processes[END_REF] and [START_REF] Quintanilla | Necessary and sufficient conditions for the two-point probability function of two-phase random media[END_REF], can be fruitful. Even if X is finite, the positivity conditions (1.2) involve a priori an infinity of relations, and it is not even known what is the right-hand side of (1.2) for general α. In the discrete setting and in a slightly different formulation, McMillan [START_REF] Mcmillan | History of a problem[END_REF] has proved that it is enough to satisfy (1.2) for α corner positive, and κ α = 0, but the corner positivity is poorly understood; it has been numerically studied in [START_REF] Quintanilla | Necessary and sufficient conditions for the two-point probability function of two-phase random media[END_REF] if X has less than 7 elements. At the present time it is not possible to give an algorithmic procedure that determines the positivity of a given function (ρ x,y ), and it seems like a very difficult challenge with the tools available, therefore the consensus is to give necessary conditions as sharp as possible for the admissibility of ρ. This problem has been posed by MacMillan [START_REF] Mcmillan | History of a problem[END_REF] in the field of telecommunications. It is more or less implicit in many articles, and has been to the author's knowledge first addressed directly by Shepp [START_REF] Shepp | On positive-definite functions associated with certain stochastic processes[END_REF], and more recently by Quintanilla [START_REF] Quintanilla | Necessary and sufficient conditions for the two-point probability function of two-phase random media[END_REF]. A series of works by Torquato and his coauthors (see [START_REF] Jiao | Modeling heterogeneous materials via twopoint correlation functions: Basic principles[END_REF], and [START_REF] Torquato | Random Heterogeneous Materials[END_REF] Sec. 2.2 and references therein), in the field of materials science, gather known necessary conditions and illustrate them in many 2D and 3D models. This question was developed alongside in the field of geostatistics; Matheron [START_REF] Matheron | Une conjecture sur la covariance d'un ensemble aléatoire[END_REF] has found via arithmetic considerations a wide class of necessary conditions, that he has proven to be sufficient if X has cardinality less or equal to 5, and he has conjectured these conditions to be sufficient for any X . Those conditions form the widest known class of necessary conditions used in related practical problems. Some other authors do not attack frontally this question, but address the realisability problem within some particular classes of models, e.g. Gaussian, mosaic, or boolean model (see [START_REF] Chilès | Modelling spatial uncertainty[END_REF][START_REF] Emery | On the existence of mosaic and indicator random fields with spherical, circular, and triangular variograms[END_REF][START_REF] Lantuéjoul | Geostatistical simulation: models and algorithms[END_REF][START_REF] Masry | On covariance functions of unit processes[END_REF]). In the companion paper [START_REF] Lachièze-Rey | Checking realisability of set covariances[END_REF], we use the theoretical results of the present work to give a heuristic algorithm allowing to discard some inadmissible covariances, and other applications.

Our method is based on a direct study of U X , which is a convex polytope if X has finite cardinality, and can therefore be applied tools from convex geometry. In Section 1.1, we provide some structural information on U X , such as its dimension and extreme points, and from there on X is essentially assumed to have finite cardinality. As an application we give a bound for the number of different states of a random field realising an arbitrary admissible covariance. Section 2 revolves around the linear inequalities characterising U X , i.e. finding the hyperplanes supporting its facets if X has finite cardinality; we give new necessary conditions that are the support of the heuristic algorithm developed in [START_REF] Lachièze-Rey | Checking realisability of set covariances[END_REF], and disprove numerically the conjecture of Matheron on the form of the supporting hyperplanes normals. Section 3 is devoted to more theoretical facts about U X , such as the elements of its boundary and its graph structure for faces of low dimensions.

Realisability and convex geometry

It is a fairly trivial fact that U X is convex, indeed if X 1 and X 2 are two unit fields of X , then the segment [ρ

X 1 , ρ X 2 ] is comprised in U X because for every t ∈ [0, 1], tρ X 1 + (1 -t)ρ X 2 is the unit covariance of X = X 1 if B = 1 X 2 if B = 0
where B is an independent Bernoulli variable with parameter t. The convexity is exploited here to lay out some notation and basic facts about realisability. See the appendix at the end of the paper for notation and basic vocabulary in convex geometry. For a function v on

X , denote (v ⊗ v) x,y = v x v y , v ⊗ v ∈ F X . If X is a unit field, then ρ X = E[X ⊗ X],
where the expectation is taken component-wise. Furthermore the structure of vertices of U X can be made explicit.

Proposition 1.1. The extreme points of U X are the u ⊗ u, u ∈ B X .

Proof. Take u ∈ B X , and assume that u ⊗ u = tρ X 1 + (1 -t)ρ X 2 for some unit fields X 1 , X 2 and t ∈ [0, 1], t = 0, 1. Since for every x, y ∈ X we have tρ

X 1 x,y + (1 -t)ρ X 2 x,y ∈ {-1, 1}, necessarily ρ X 1 x,y = ρ X 2
x,y ∈ {-1, 1} for every pair (x, y) of X 2 . It follows that both X 1 and X 2 are deterministic with ρ X 1 = ρ X 2 , and therefore u ⊗ u is an extreme point.

Conversely, take ρ = ρ X ∈ U X , assume that for some x, y ∈ X , t = ρ X

x,y ∈ (-1, 1), meaning P(X x = X y ) / ∈ {0, 1}, and define the two unit fields X 1 and X 2 with respective laws

P(X 1 ∈ A) = P(X ∈ A | X x = X y ) P(X 2 ∈ A) = P(X ∈ A | X x = X y )
for A a subset of B X . We have, by conditioning,

ρ X = tρ X 1 + (1 -t)ρ X 2 . It follows that ρ X lies in the relative interior of the segment [ρ X 1 , ρ X 2 ] (this segment is not a singleton because 1 = ρ X 1 x,y = ρ X 2
x,y = 0). Thus ρ X is not an extreme point of U X . In the sequel we focus on the finite case X = [N] = {1, 2, . . . , N}, N ≥ 1. For the sake of clarity index [N] is replaced with N. Functions of F N are identified with N × N matrices.

Remark 1.2 (Notation for triangular arrays). Call π the projection operator that takes a matrix ρ ∈ F N to its supra-diagonal components π(ρ) = (ρ i,j ; 1 ≤ i < j ≤ N), and call F * N = π(F N ) the space of supra-diagonal triangular arrays. An element ρ of F * N is represented as the triangular array

     ρ 1,2 . . . ρ 1,N . . . . . . ρ N -1,N      .
Since any ρ ∈ U N automatically has the diagonal filled with 1's, it is somehow intuitive that mapping U N to U * N = π(U N ) does not lose any relevant information. The dimension of

F * N is d N := N (N -1)

2

, and we prove below that U * N is a full-dimensional convex subset of F * N . The elements said to be under the product form are those that can be written, for some

v ∈ R N , v v := π(v ⊗ v) = (v i v j ) 1≤i<j≤N .
Proposition 1.3. U * N has a non-empty interior in F * N . Its extreme points are the 2 N -1 vertices of the form u u for u ∈ B N .

Proof. It suffices to prove that F * N contains at least d N linearly independent vectors. Take i 0 < j 0 in [N]. Let X k , k = j 0 be independent Rademacher variables (P(X i = 1) = P(X i = -1) = 1/2) and define the unit field X = (X 1 , . . . , X j 0 -1 , X i 0 , X j 0 +1 , . . . , X N ). Its unit covariance is the canonical vector e i 0 ,j 0 = (1 { i=i 0 ,j=j 0 } ) 1≤i<j≤N . Therefore U * N contains 0 and the d N such canonical vectors, and has nonempty interior in F * N . In virtue of Proposition 1.1 the extreme points of U N are the u⊗u for u ∈ B N , whence the extreme points of U * N = π(U N ) are of the form u u, u ∈ B N . Conversely we can prove that each u u is an extreme point by mimicking the arguments from the proof of Proposition 1.1, simply by assuming x < y. All the u u are hence extreme points, and we have u u = v v if and only if u = v or u = -v. It follows that the number of extreme points is the number of binary vectors, under the identification u ≡ -u; we arrive at 2 N -1 .

A consequence of these remarks is that the number of different values taken by a random set realising a given unit covariance can be chosen to be no larger than d N + 1.

Proposition 1.4. Any unit covariance ρ ∈ U N can be realised by a random field X that takes at most d N + 1 distinct values.

Proof. Applying the Minkowski-Carathéodory theorem to U * N in F * N , π(ρ) can be expressed as the convex combination of

d N + 1 extreme points u k u k , u k ∈ B N , 1 ≤ k ≤ d N + 1 π(ρ) = d N +1 k=1 p k u k u k , with p k ≥ 0, k p k = 1,
meaning ρ is the unit covariance of the unit field X which law is defined by

P (X = u k ) = p k ∈ [0, 1] for every 1 ≤ k ≤ d N + 1.
Remark 1.5. Another consequence is that U * N contains a non-empty open ball. Using Gaussian unit covariances, it is proved in [START_REF] Lachièze-Rey | Checking realisability of set covariances[END_REF] that the euclidean ball of F * N centred in 0 with radius √ 2/π is comprised in U * N .

Checking realisability numerically and Matheron's conjecture

This section focuses on the practical problem of checking, when X = [N], N ≥ 1, is finite, the validity of a given function ρ. We saw in Proposition 1.3 that the problem is properly posed in F * N , and since U * N is a polytope, it can be written as a finite intersection of half spaces,

U * N = h N k=1 W o k µ k
where h N is the number of facets, the µ k ∈ F * N are the outer normals of U * N , the o k ∈ R are the corresponding offset values, and

W o k µ k = {ρ ∈ F * N : ρ, µ k ≤ o k }.
For a finite-dimensional vector space V , call •, • V the canonical scalar product on V . All it takes to find o k knowing µ k is to compute the infimum of µ k , • F * N on the 2 N -1 extreme points of U * N (prop. 1.3). The computational problem consists in finding the normals µ k , the complexity of computing the corresponding offsets is much smaller, see Table 1. In [START_REF] Matheron | Une conjecture sur la covariance d'un ensemble aléatoire[END_REF], Matheron studied the structure of the convex set constituted by realisable covariograms, similar to that of U N . For N ≤ 5, he computed by hand the normal vectors and detected a recurring pattern; he then conjectured that this form should be valid for every N ≥ 1. We transposed and extended his results with numeric computations here to unit covariances.

Introduce the class

E N = {e ∈ Z N : N i=1
u i e i = 1 for some binary vector u ∈ B N = {-1, 1} N }.

The following theorem gives a neat characterisation of unit covariances for N ≤ 6.

Theorem ρ ij e i e j ≥ 1.

(2.1)

(ii) Let N ≥ 1, and ρ ∈ U N .
For every e ∈ Z N with odd sum, ρ satisfies (2.1).

Proof. (i) The outer normals µ k of U * N can be listed by a linear programming algorithm which input is the 2 N -1 extreme points of U * N and output is the outer normals and corresponding offset values of the polytope spanned by these extreme points. We used the cdd+ algorithm [START_REF] Fukuda | cdd/cdd+ Reference Manual[END_REF], the list of these normals can be found at http://www.math-info.univ-paris5.fr/ rlachiez/realisability. We then checked that each normal µ k could indeed be put under the form e k e k for some e k ∈ E N . Thus ρ ∈ F 1 N is realisable if and only if for every 1

≤ k ≤ h N π(ρ), e k e k F * N ≥ inf U * N •, e k e k F * N . (2.2)
Since the minimum of a linear form on a convex polytope is necessarily reached in an extreme point, Prop. 1.3 yields that (2.2) is equivalent to

π(ρ), e k e k F * N ≥ inf u∈B N u u, e k e k F * N , 1 ≤ k ≤ h N . Using the fact that ρ ∈ F 1 N , N i=1 ρ ii (e k i ) 2 = N i=1 u i u i (e k i ) 2 for every u ∈ B N , 1 ≤ k ≤ h N , the prior condition is therefore equivalent to ρ, e k ⊗ e k F N ≥ inf u∈B N u ⊗ u, e k ⊗ e k F N = inf u∈B N N i=1 u i e k i 2 = 1 6
because N i=1 u i e k i is an odd number, and the value 1 is reached for the particular u ∈ B N such that N i=1 e k i u i = 1. Finally, a matrix ρ ∈ F 1 N indeed belongs to U N if and only if

N i,j=1
ρ ij e k i e k j ≥ 1 for every 1 ≤ k ≤ h N .

The necessity is contained in point (ii).

(ii) If ρ = ρ X for some unit field X, and e ∈ Z N is such that i e i is an odd number,

ρ X , e ⊗ e F N = E i e k X i 2 ≥ 1
because i e i X i is a.s. an odd integer.

Remark 2.2.

1.

Even though E N is infinite, point (i) provides a finite time procedure to check the realisability of a given matrix ρ, see the details in the companion paper [START_REF] Lachièze-Rey | Checking realisability of set covariances[END_REF].

2. Any vector of E N has odd sum, thus point (ii) indeed applies to E N .

3. Matheron only made computations up to N = 5, for which he found that we can furthermore state that e i ∈ {-1, 0, 1}, but numerical computations showed that this is no longer true for N = 6.

4. The point (ii) also originates in [START_REF] Matheron | Une conjecture sur la covariance d'un ensemble aléatoire[END_REF].

5.

The point (i) concerns the normal vectors to all the facets of the polytope U * N . Matheron originally formulated his result only for the normal vectors of the facets touching the vertex (1, . . . , 1). In the meantime he mentioned the idea that this could be used for other vertices by exploiting the combinatorial symmetry of unit covariances.

We give in table 1 increases. For N = 8, the algorithm was stopped in dimension d 8 = 28 after that 2 216 100 outer normals were found, no more memory space being available. To go further in the computations, one has to go deeper in understanding the structure of U * N . Section 3 gathers some metric and topological facts about U * N that can help optimise the processing time and understand the structure of U * N . Theorem 2.1 provides necessary conditions that are used in the companion paper [START_REF] Lachièze-Rey | Checking realisability of set covariances[END_REF] to design an algorithm able to discard some spherical variograms as admissible covariograms, a recurrent problem in geostatistics (see [START_REF] Lantuéjoul | Geostatistical simulation: models and algorithms[END_REF], Sec. 3.2.2).

Matheron's conjecture is not true

Matheron's conjecture is appealing, as if it were true it would provide a procedure to efficiently check the realisability of a matrix for any N ≥ 1. We show in this section via theoretic and numeric arguments that the conjecture fails at N = 7. Recall that convexity-related notation and vocabulary are introduced in the appendix.

The conjecture was originally stated for the covariogram of a random set

Y ⊆ [N] γ Y i,j = 1 2 P(1 Y (x) = 1 Y (y)), i, j ∈ [N],
where 1 Y is the indicator function of Y . Calling V N the class of admissible covariograms (convex for the same reasons than U N ), and V * N = π(V N ), Matheron conjectured that the outer normals of cone(0; V * N ) are of the form e e for e in Z N with N i=1 e i = 1. Now Φ(γ Y ) := 1 -4γ Y is the unit covariance of the unit field X = 2Y -1, therefore easy computations show that the outer normals of cone(1; U * N ) (where 1 = (1, . . . , 1) = Φ(0)) are those same e e. We prove below that the conjecture, even under a slightlier general form, is equivalent to Th. 2.1.

Remark 2.3. Matheron conjectured that conditions (2.1) characterise matrices contained in cone(0; V * N ), more precisely that for γ ∈ F N , γ ∈ cone(0; V N ) if and only if

1≤i<j≤N γ ij e i e j ≤ 0 (2.3)
for every e ∈ E N , but not that they characterise the whole convex V * N as can be seen in the literature.

Theorem 2.4. For any N ≥ 1, Matheron's conjecture is equivalent to the conjecture that a matrix ρ ∈ F 1 N is a unit covariance if and only if it satisfies (2.1).

Proof. Let γ ∈ F 0 N = {γ ∈ F N : γ i,i = 0 for all i ∈ [N]
} and ρ ∈ F 1 N be linked up by ρ = 1 -4γ, hence ρ is realisable as a unit covariance iff γ is realisable as an indicator covariogram.

Let us assume that Matheron's conjecture is true, and that ρ satisfies (2.1); we must prove that ρ is realisable. In particular, for e ∈ E N with unit sum (i.e. i e i = 1) 1≤i,j≤N

e i e j γ ij = 1 4 1≤i,j≤N e i e j (1 -ρ ij ) ≤ 0,
whence by Matheron's conjecture π(γ) lies in cone(0; V * N ). Applying Φ yields that π(ρ) is in cone(1; U * N ). Let us call, for u ∈ {-1, 1} N , θ u the transformation of F N defined by

θ u µ = (u i u j µ ij ) 1≤i,j≤N , µ ∈ F N .
The rotated matrix θ u ρ also verifies ij e i e j (θ u ρ) ij ≥ 1 for e ∈ Z N with unit sum because ρ satisfies (2.1). It follows that π(θ u ρ) also belongs to cone(1; U * N ), and therefore π(ρ

) ∈ cone(u u; U * N ). Thus in each extreme point u u of U * N , u ∈ {-1, 1} N (see Prop. 1.1), π(ρ) is contained in cone(u ⊗ u; U * N ). Thus π(ρ) is in U * N , meaning it is realisable.
In the other direction, if (2.1) characterises the realisability of unit covariances, then cone(1; U * N ) is characterised by inequalities in (2.1) that become equalities if ρ ij = 1, i.e. inequalities such that i e i = 1. It follows by applying Φ -1 that cone(0; V * N ) is characterised by (2.3), which is exactly Matheron's conjecture.

In the light of the previous proposition, Matheron hence conjectured that every normal vector of U * N is under a product form v v. We give in the file rho7.ine the normals of U * 7 computed with cdd+. The following array τ ∈ F * N is one of these normals.

τ =           -2 1 0 1 1 1 -2 1 -2 -2 -3 -1 1 1 2 -1 -1 -2 1 2 2          
It is clear that τ is not under the product form v v for some v ∈ R N because τ 14 = 0, but neither its first line nor its 4-th column are filled with 0's. In conclusion Matheron's conjecture is not true for N = 7. We proved in a similar way that it was not true for N = 8.

3 The structure of U *

N

The task of giving a tractable characterisation of realisable covariances, or unit covariances, seems a very hard one, not to say impossible. This problem, combinatorial in nature, relies heavily on arguments from convex geometry to analyse U * N . We give in this section topological facts about U * N , in order to better apprehend its structure both for a geometric and a graph-theoretic description. The convex body U * N bears some peculiar properties, which might lead to think that the combinatorial problem of characterising U * N is better apprehended with this geometric approach, and stands on its own as an interesting theoretical problem.

With the current knowledge of U * N one should more rely on numeric considerations to test the validity of a given model. Unfortunately, as is apparent in Table 1, the complexity of such a task explodes as the cardinality N of X increases. Understanding better the structure of U * N can enable programmers to design a more adapted linear programming algorithm to find the outer normals of U * N , which amounts to find the necessary and sufficient conditions of realisability.

Let us start by recalling that U *

N is a polytope of F * N which all 2 N -1 extreme points are vertices of the hypercube (Prop. 1.3 ). For algorithms based on ray-shooting queries it is interesting to have an interior point of U * N , or of its dual. Here 0 plays perfectly this role, and this can be quantified. (ii) Singular unit covariances lie on the boundary of U * N . Proof. (i) Let X be a unit field and ρ its unit covariance. As a semi-definite positive matrix, the singularity of ρ is equivalent to the existence of a non-trivial family of scalar numbers

{λ k : 1 ≤ k ≤ N} such that 1≤k,j≤N λ k λ j ρ kj = 0, which exactly means that E( N k=1 λ k X k ) 2 = 0. (ii)
Let ρ be a singular unit covariance, and λ k , k = 1, . . . , N, non-trivial coefficients such that 1≤k,j≤N λ k λ j ρ kj = 0, 1 ≤ j ≤ N.

Acknowledgements

I am grateful to Ilya Molchanov, who through many discussions about Matheron's conjecture, contributed to this research. Vincent Delos helped me find my way around linear programming for the numerical issues.

Appendix: Convex geometry

Let C be a convex set of a vector space V . The extreme points of C are the x ∈ V such that, for every y, z ∈ C, if x lies in the segment [y, z] spanned by y and z, then either x = y or x = z. Denote them by ext(C). All the subsequent statements are only made for finite dimensional space V = R d . If X is a subset of V , the convex hull of X is the smallest closed convex set of V containing X. The relative affine space span(C) of a convex C is the vector space spanned by C. In the topology of span(C), C has a non-empty interior and the relative dimension of C is defined as the dimension of span(C). Say that C is fully dimensional if span(C) = R d , equivalent to the fact that C has a non-empty interior in R d . Given a point x ∈ C, denote by cone(x; C) the smallest affine convex convex cone with vertex x containing C.

Polytopes

A polytope P of R d is the convex hull of a finite number of points x 1 , . . . , x q of R d , denoted P = conv(x 1 , . . . , x q ). For 0 ≤ k < d, a k-dimensional face of P is any set S ⊆ ∂P such that S is the convex intersection of P with a affine hyperplane and the relative dimension of S is exactly k. For any 0 ≤ k ≤ d -1, the data of all its k-dimensional facets characterise P . Its 0-facets are its extreme points, also called vertices, and the corresponding description of the form ext(P ) = {x 1 , . . . , x q } is called V -description. At the opposite, its (d -1)-dimensional facets are sometimes just called facets, and yield the so-called H-description. The latter can be understood via a finite family of affine half-spaces H 1 , . . . , H q where H i = {y ∈ R d : y, µ i ≤ o i } for some µ i ∈ R d called outer normal and corresponding offset value o i , 1 ≤ i ≤ q. Given any x ∈ ext(P ), the convex cone of C generated by x is obtained by retaining only half spaces with x in their boundary cone(x; V ) = i: x,µ i =o i H i .

For k < d, call k-th order hypergraph of C the class of k-tuples of extreme points of C {x 1 , . . . , x k } such that the simplex formed by x 1 , . . . , x k lies on the boundary of C.

Proposition 3 . 1 .Theorem 3 . 2 .

 3132 Calling B 0 (r) the euclidean ball of F * N with radius r centred in 0, we haveB 0 ( √ 2/π) ⊆ U * N ⊆ B 0 ( d N ).Proof. The first inclusion translates Remark 1.5, itself relying on classical results about Gaussian covariances and exploited in[START_REF] Lachièze-Rey | Checking realisability of set covariances[END_REF]. The second traduces the fact that the extreme points of U * N are vertices of the hypercube. The next statement locates the singular admissible covariances on the boundary of U * N . (i)The unit covariance ρ of a unit field X is singular if and only if for some non-trivial real deterministic coefficients λ 1 , . . . , λ N the components of X satisfy k λ k X k = 0 a.s..

Table 1 :

 1 the number of facets for N ≤ 7. It explodes as the dimension number of facets of U *

	N dimension d N	h N
	3	3	4
	4	6	16
	5	10	56
	6	15	368
	7	21	116 764
			N

Two at least of the λ k are non zero (because ρ has 1's on the diagonal), say λ i 1 and λ i 2 , and put σ = sign(λ i 1 λ i 2 ) ∈ {-1, 1}. Let us take ε > 0 and

Then if ρ ε was realisable by some unit field X ε , we would have

which is impossible. Thus there are unrealisable covariances arbitrarily close from ρ, it follows that ρ is on the boundary of U * N . Remark 3.3. It is conversely not true that every ρ on the boundary is singular (otherwise finding the outer normals of U * N , and thus characterising realisable unit covariances, would be easy). According to Th. 3.2 it would mean that i λ i X i = 0 a.s. for some non-trivial family (λ i ), but if for instance X takes the values (-1, 1, 1), (-1, -1, 1), (1, -1, 1) each with probability 1/3 yields the non-singular unit covariance

On the other hand π(ρ X ) lies on the border of U * 4 because it is a convex combination of three out of the 4 vertices of the tetrahedron U * 4 (see Prop. 1.3 or [START_REF] Matheron | Une conjecture sur la covariance d'un ensemble aléatoire[END_REF] p.110). A manner of describing exhaustively the topological structure of U * N is to explicit the hypergraph structure of its vertices. The following theorem states that for k < N, the k-th order hypergraph structure of U * N is complete, in the sense that the simplex formed by any k-tuple of extreme points is contained in U * N 's boundary.

Theorem 3.4. For every k < N, and k-tuple u 1 , . . . , u k of {-1, 1} N , the k-dimensional simplex formed by their respective unit covariances ρ u 1 , . . . , ρ u k only contains singular matrices and thus lies on the boundary of U * N . Proof. A covariance of the form ρ = k i=1 p i ρ u i is the covariance of the unit field X with law P(X = u i ) = p i , allowed to take values among the k vectors u i . Since k < N, there exists a non-trivial family λ 1 , . . . , λ N such that N j=1 λ j u i j = 0 for all i, whence a.s. j λ j X j = 0. It follows by Th. 3.2(i) that ρ is singular. The conclusion comes by applying Th. 3.2.

In some sense U * N has the topological structure of the d N -dimensional simplex as long as one only looks at dimensions strictly smaller than N. Higher dimensional facets are harder to explicit.


Bartlomiej Blaszczyszyn

Holger Mohamed Kadhem Karray

Paul Keeler

Using Poisson processes to model lattice cellular networks

Using Poisson processes to model lattice cellular networks Bartłomiej Błaszczyszyn * , Mohamed Kadhem Karray † and Holger Paul Keeler * * INRIA-ENS, 23 Avenue d'Italie, 75214 Paris, France Email: Bartek.Blaszczyszyn@ens.fr, Holger-Paul.Keeler@inria.fr † Orange Labs; 38/40 rue Général Leclerc, 92794 Issy-les-Moulineaux, France Email: mohamed.karray@orange.com Abstract-An almost ubiquitous assumption made in the stochastic-analytic approach to study of the quality of user-service in cellular networks is Poisson distribution of base stations, often completed by some specific assumption regarding the distribution of the fading (e.g. Rayleigh). The former (Poisson) assumption is usually (vaguely) justified in the context of cellular networks, by various irregularities in the real placement of base stations, which ideally should form a lattice (e.g. hexagonal) pattern. In the first part of this paper we provide a different and rigorous argument justifying the Poisson assumption under sufficiently strong lognormal shadowing observed in the network, in the evaluation of a natural class of the typical-user service-characteristics (including path-loss, interference, signal-to-interference ratio, spectral efficiency). Namely, we present a Poisson-convergence result for a broad range of stationary (including lattice) networks subject to log-normal shadowing of increasing variance. We show also for the Poisson model that the distribution of all these typical-user service characteristics does not depend on the particular form of the additional fading distribution. Our approach involves a mapping of 2D network model to 1D image of it "perceived" by the typical user. For this image we prove our Poisson convergence result and the invariance of the Poisson limit with respect to the distribution of the additional shadowing or fading. Moreover, in the second part of the paper we present some new results for Poisson model allowing one to calculate the distribution function of the SINR in its whole domain. We use them to study and optimize the mean energy efficiency in cellular networks.

Index Terms-Wireless cellular networks, Poisson, Hexagonal, convergence, shadowing, fading, spectral/energy efficiency, optimization

I. INTRODUCTION

Cellular networks are being extensively deployed and upgraded in order to cope with the steady rise of user-traffic. This has created the need for new and robust analytic techniques to study the quality of user-service. The ability to tractably model and calculate the quality of user-service related to the signal-to-interference-and-noise ratio (SINR, or SIR when the noise is neglected) will serve as the motivating force behind the work presented here.

In order to derive analytic techniques, various mathematical models have been proposed. A common and simplifying model assumption is that the base stations are located according to a Poisson process in the plane. In the first section of this paper we recall such a model with shadowing and/or fading, and present a simple yet very useful result, upon which the bulk of the remaining work here hinges. This result involves mapping the point process on R 2 (that models the locations of base stations) through the distance-loss function and the shadowing and/or fading variables (that model the propagation losses between these stations and a typical user), to a point process of propagation losses on R + , which are experienced by this user. It allows one to study all typical-user characteristics, which can be expressed in terms of its propagation losses (or received powers, e.g. SINR, etc). We observe that this new process also forms a Poisson process, regardless of the shadowing and/or fading distribution, and is characterized only by the moment of this distribution of order 2/β, where β is the distance-loss exponent.

In the context of an actual deployment of cellular networks, lattice (e.g. hexagonal) models for the base station placement are usually thought of as more pertinent. However, perfect lattice models do not seem to allow analytic techniques for the study of the SINR-based characteristics. Hence, the Poisson model is used and justified by positioning "irregularities" of the network. It is also considered as a "worst-case" scenario due to its complete randomness property. Although the validity of these arguments alone may be questioned, we seek to support the Poisson assumption with a powerfully new convergence result when there is sufficiently strong log-normal shadowing in the network. Namely, provided a network is represented by a sufficiently large homogeneous point pattern (whose definition will later be made precise, and includes general lattices and various "perturbed lattice" models), we show that as the variance of log-normal shadowing increases, the resulting propagation losses between the stations and the typical user form a stochastic process that converges to the aforementioned non-homogeneous Poisson process on R, due to the Poisson model. In other words, the actual (large but not necessarily Poisson) network is perceived by a typical user as an equivalent (infinite) Poisson network, provided shadowing is strong enough, of logarithmic standard deviation greater than approximately 10dB, as shown by numerical evidence. This is a realistic assumption for outdoor and indoor wireless communications in many urban scenarios.

This result rigorously justifies using a Poisson point process to model typical-user characteristics in a wide range of network models, which includes the hexagonal model and a large class of perturbed lattice models, thus adding theoretical weight to the work being done under the Poisson assumption.

After stating this convergence result, we derive important complementary analytic tools for the study of the distribution of the SINR in the Poisson model, which remain valid for any distribution of the shadowing and/or fading random variables.

We use them to investigate the spectral and energy efficiency in cellular networks. In particular, we evaluate the mean energy efficiency as a function of the base station transmit power, which allows one to optimally tune this latter power. Poisson and hexagonal networks with and without shadowing are compared in this context.

Related work: It is beyond the scope of this short introduction to review all works with Poisson model of wireless networks. Some results and further references may be found in [START_REF] Baccelli | Stochastic Geometry and Wireless Networks[END_REF][START_REF] Haenggi | Stochastic geometry and random graphs for the analysis and design of wireless networks[END_REF]. More specifically, our results presented in this paper allow to extend to a general fading distribution the explicit expressions for the distribution function of the SINR derived in [START_REF] Dhillon | Modeling and analysis of K-tier downlink heterogeneous cellular networks[END_REF], where Rayleigh fading is assumed. Our representation of the network via the process of propagation losses is similar tho this considered in [START_REF] Haenggi | A Geometric Interpretation of Fading in Wireless Networks: Theory and Applications[END_REF] for other purposes, mostly to study the effect of shadowing/fading on connectivity. Moreover, using the Laplace/Fourier analysis, we manage to characterize (no longer explicitly) the SINR over its entire range, whereas the aforementioned explicit expressions are valid only for SINR ≥ 1. The result of Lemma 1 appeared in [START_REF] Błaszczyszyn | Impact of the geometry, path-loss exponent and random shadowing on the mean interference factor in wireless cellular networks[END_REF]. The infinite Poisson model was statistically fitted in [START_REF] Błaszczyszyn | Linear-regression estimation of the propagation-loss parameters using mobiles' measurements in wireless cellular network[END_REF] to some real data provided by an operator regarding propagation losses in order to estimate the parameters of the propagation loss using a simple linear regression model. The spectral and energy efficiency in hexagonal networks without shadowing was studied in [START_REF] Karray | Spectral and energy efficiencies of OFDMA wireless cellular networks[END_REF]. Finally, the convergence result presented here is in the spirit of classical limit theorems of point processes, which are detailed in [START_REF] Daley | An introduction to the theory of point processes[END_REF]Chapter 11]. In particular, these theorems show that under specific conditions, the repeated superposition, thinning or translation of points of a point process will result in the point process converging in the limit to a Poisson process.

The remaining part of this paper is organized as follows. In section II we present the basic result on the network mapping to the process of propagation losses. The main convergence result is presented in Section III and its proof is given Appendix A. We revisit the Poisson model in order to study the SINR distribution in Section IV.

II. INFINITE POISSON MODEL

For motivation purposes, we first recall the usual cellular network model based on the Poisson process. In particular, we model the geographic locations of the base stations with an homogeneous Poisson point process Φ = {X i } i∈N of intensity λ on R 2 , which we refer to as the infinite Poisson model.

We assume that the (typical) user is located at the origin without loss of generality due to the stationarity of {X i } i∈N . Let l (X i ) be the distance loss between a base station at X i and the user, where l (•) is given by

l (x) = (K |x|) β (1)
for two given positive constants K and β. When we incorporate shadowing (and/or fading), the propagation loss is

L Xi = l (X i ) S Xi where {S x } x∈R 2 is
a collection of independent and identically distributed (iid) positive random variables. We will sometimes write also S Xi = S i to simplify the notation. Let S be a random variable having the same distribution as any S x .

Note that the power received at the origin from the station X i , transmitting with power P Xi , is equal to

p Xi = P Xi L Xi = P Xi S Xi l (X i ) .
In this paper we do not assume any power control, i.e., P Xi = P for some given positive constant P > 0. In this case (as well in a more general case of iid emitted powers), including P Xi in the associated shadowing random variable, we retrieve an equivalent model in which the shadowing is SXi := P Xi S Xi and the transmitted powers PXi = 1.

Henceforth we assume, without loss of generality, that the transmitted powers are all equal to one, while keeping in mind that the shadowing random variables now include the effective transmitted powers. This transformation will slightly simplify our notation. However, when studying the energy efficiency in Section IV-B4 we will reintroduce emitted powers to our model.

A. Mapping of the propagation losses of the typical user from R 2 to R + Denote by N = {L Xi } i∈N the process of propagation losses experienced by the typical user with respect to the stations in Φ. We consider N a point process on R + . Note that all characteristics of the typical user, which can be expressed in terms of its propagation losses (or received powers, under the aforementioned assumption on emitted powers, e.g. SIR, SINR, spectral and energy efficiency, etc) are determined by the distribution of N . This motivates the following simple result that appeared, to the best of our knowledge for the first time, in [START_REF] Błaszczyszyn | Impact of the geometry, path-loss exponent and random shadowing on the mean interference factor in wireless cellular networks[END_REF]. In order to make this presentation more selfcontained we present it with a proof.

Lemma 1: Assume infinite Poisson model with distanceloss (1) and generic shadowing (and/or fading) variable satisfying

E[S 2 β ] < ∞ . ( 2
)
Then the process of propagation losses N experienced by the typical user is a non-homogeneous Poisson point process on R + with intensity measure

Λ ([0, t)) := E [N ([0, t))] = at 2 β ( 3
)
where

a := λπE[S 2 β ] K 2 (4)
Proof: The point process N may be viewed as a transformation of the point process Φ by the probability kernel

p(x, A) = P l (x) S ∈ A , x ∈ R 2 , A ∈ B R +
By the displacement theorem [1, Theorem 1.10], the point process N is Poisson on R + with intensity measure

Λ ([0, t)) = λ R 2 P l (x) S ∈ [0, t) dx = λ R 2 ×R + 1 l (x) s < t dxP S (ds) = λ R + π (st) 2 β K 2 P S (ds) = λπE S 2 β K 2 t 2 β
which completes the proof. Remark 2: Note that the distribution of N is invariant with respect to the distribution of the shadowing/fading S having same given value of the moment E[S 2/β ]. This means that the infinite Poisson network with an arbitrary shadowing S is perceived at a given location statistically in the same manner as an "equivalent" infinite Poisson with "constant shadowing" equal to s const = (E[S 2/β ]) β/2 (to have the same moment of order 2/β). The model with such a "constant shadowing" boils down to the model without shadowing (S ≡ 1) and the constant K replaced by

K = K/ E[S 2/β ].
The above result requires condition (2), which is satisfied by the usual models, as e.g. the log-normal shadowing or Rayleigh fading, and we tacitly assume it throughout the paper.

III. CONVERGENCE RESULTS UNDER LOG-NORMAL

SHADOWING

In this section we derive a powerful convergence result rigorously showing that the infinite Poisson model can be used to analyse the characteristics of the typical user in the context of any fixed (deterministic!) placement of base stations, meeting some empirical homogeneity condition, provided there is sufficiently strong log-normal shadowing.

A. Model description

Let φ = {X i } i∈N be a locally finite deterministic point pattern on R 2 and B 0 (r) the ball of radius r, centered at the origin. For 0 < λ < ∞, as r → ∞ we require the empirical homogeneity condition

φ(B 0 (r)) πr 2 → λ. (5)
Note that the above condition is satisfied by any lattice (e.g. hexagonal) pattern φ, as well as by almost any realization of an arbitrary ergodic point process.

Let the shadowing S (σ) i between the station X i and the origin be iid (across i) log-normal random variables

S (σ) i = exp(-σ 2 /2 + σZ i ), (6)
where Z i are standard normal random variables. Note that for such S

(σ) i = S (σ) , we have E[S] = 1 and E (S (σ) ) 2/β = exp[σ 2 (2 -β)/β 2 ]. 1
Consider the distance-loss model [START_REF] Baccelli | Stochastic Geometry and Wireless Networks[END_REF] with the constant K replaced by the function of σ

K(σ) = K exp - σ 2 (β -2) 2β 2 , (7)
where K > 0 and β > 2.

As in Section II, we consider the point process on R + of propagation losses experienced by the typical user with respect to the stations in φ

N (σ) := K(σ) β |X i | β S (σ) i : X i ∈ φ . (8)
We consider also the analogous process of propagation losses

N (σ) := K(σ) β |X i | β S (σ) i : a σ < |X i | < b σ , X i ∈ φ , (9)
where the stations in φ that are closer than a σ and farther than b σ are ignored, for all sequences

0 ≤ a σ < b σ ≤ ∞ satisfying log(a σ ) σ 2 → 0, (10)
log(b σ ) σ 2 → ∞. (11)

B. Main result

We present now our main convergence result. Theorem 3: Given homogeneity condition (5), then N (σ) converges weakly as σ → ∞ to the Poisson point process on R + with the intensity measure Λ given by ( 3) with a = λπ/K 2 . Moreover, N (σ) also converges weakly (σ → ∞) to the Poisson point process with the same intensity measure, provided conditions [START_REF] Richter | Energy efficiency aspects of base station deployment strategies for cellular networks[END_REF] and [START_REF] Abate | Numerical inversion of Laplace transforms of probability distributions[END_REF] are satisfied.

The proof of Theorem 3 is deferred to Appendix A. Remark 4: The above result, in conjunction with Lemma 1, says that infinite Poisson model can be used to approximate the characteristics of the typical user for a very general class of homogeneous pattens of base stations, including the standard hexagonal one. The second statement of this result says that this approximation remains valid for sufficiently large but finite patterns.

Remark 5: The distance-loss model (1) suffers from having a singularity at the origin. This issue is often circumvented by some appropriate modification of the distance-loss function within a certain distance from the origin. The second statement of Theorem 3 with a σ = const > 0 shows that such a modification is not significant in the Poisson approximation.

To illustrate Theorem 3 and obtain some insight into the speed of convergence we used Kolmogorov-Smirnov (K-S) test, cf [START_REF] Williams | Weighing The Odds: A Course In Probability And Statistics[END_REF], to compare the cumulative distribution functions (CDF) of the SIR of the typical user (see Section IV-A2) in the infinite Poisson model versus hexagonal one consisting of 30 × 30 = 900 stations on a torus. We found that for 9/10 realizations of the network shadowing the K-S test does not allow to distinguish the empirical (obtained from simulations) CDF of the SIR from the CDF of SIR evaluated in the infinite Poisson model with the critical p-value fixed to α = 10% provided σ dB 10dB. On Figure 1 we present a few examples of these CDF's. Similar numerical study was done for the CDF of the path-loss with respect to the serving station in [START_REF] Błaszczyszyn | Linear-regression estimation of the propagation-loss parameters using mobiles' measurements in wireless cellular network[END_REF].

IV. POISSON MODEL REVISITED

We now return to the model outlined in Section II and investigate it further. We show that Lemma 1 is very useful in studying random quantities of the network, independently of the shadowing/fading distribution. We do not pretend to develop a complete theory, which is well beyond the scope of this paper. As a general remark let us emphasize only that many, already known, results (cf Related work in the Introduction), were originally derived under specific assumptions on the distribution of shadowing and/or fading. By Lemma 1 they necessarily remain valid for a general distribution, with the appropriate specification of the value of the moment E[S 2/β ].

Our specific goal in this section is to present a new representation of distribution function of the SINR, which in consequence will allow us to study the spectral and energy efficiency -two important engineering characteristics of the network. To the best of our knowledge, they have not yet been studied in the Poisson model. Moreover, as another illustration of our convergence result, we will compare these characteristics in Poisson and hexagonal network, with this latter studied by simulations.

Unless otherwise specified all results of this section regard Poisson model of Section II.

A. Path-loss and SIR

The novelty of our approach consists in representing the SINR in terms of the path-loss to the serving station and the respective SIR, rather than, as usual, the interference.

1) Path loss: The weakest propagation loss denoted by

L = inf i∈N L Xi (12)
is often called path-loss factor. It may be interpreted as the propagation loss with the serving base station (that is, the one with strongest received power). Note by (3) that the number of points of the process N = {L Xi } i∈N is almost surely finite in any finite interval. Hence, the above infimum is almost surely achieved for some base station; that is L = min i∈N L Xi . Moreover, Lemma 1 allows us to conclude the following characterisation of the distribution of L, which follows immediately from the well known expression for void

probabilities of Poisson process P{L ≥ t} = P{N ([0, t)) = 0} = exp[-Λ([0, t))]. Corollary 6: The CDF of L is equal to P{ L ≤ t } = 1 -exp[-at 2/β ]
where a is given by (4). Consequently, the probability density of L is given by

P L (ds) = 2a β t 2 β -1 e -at 2 β dt . (13)
This corresponds to a Fréchet distribution with shape parameter 2 β and scale parameter a β 2 . 2) Interference factor and SIR: The interference factor is defined by

f = L i∈N 1 L Xi -1
where L is the path-loss factor. It may be interpreted as the interference to signal ratio; that is the inverse of the SIR.

Introducing I = i∈N 1 L X i
(can be interpreted as the total received power) we can write f = LI -1. Also, f = LI where

I := I - 1 L = i∈N 1 L Xi - 1 L
may be viewed as the interference. Define

ϕ β (z) := e -z + z 2 β γ 1 - 2 β , z (14)
where γ(α, z) = z 0 t α-1 e -t dt is the lower incomplete gamma function. Another representation of the function ϕ β (z), used in evaluation of the Laplace transform of the f (cf proof of Corollary 8) is given in Appendix B.

Here is a key technical result for our approach. Proposition 7: The Laplace transform of the interference factor conditional to the path-loss factor is equal to

E e -zf |L = s = e -a[ϕ β (z)-1]s 2 β . ( 15
)
Proof:

We have

E e -zf |L = s = E[e -zsI |L = s] . (16)
Observe that I is a shot-noise associated to the point process obtained from the Poisson point process N of the propagation losses by suppressing its smallest (nearest to the origin) point, which is located precisely at L. By the well-known property of the Poisson process, given L = s, this new process is also Poisson on (s, ∞) with intensity measure

M ((s, t)) = Λ ([0, t)) -Λ ([0, s]) , t ∈ (s, +∞) . Thus M (dt) = Λ (dt) = 2a β t 2 β -1 dt, on (s, +∞) (17)
and by [START_REF] Baccelli | Stochastic Geometry and Wireless Networks[END_REF]Proposition 1.5]

E e -zsI |L = s = exp ∞ s (e -zs t -1)M (dt) = exp - 2a β ∞ s (1 -e -zs t )t 2 β -1 dt . ( 18
)
Now we calculate the integral on the right-hand side of the above equation by making the change of variable u := zs t , that is

∞ s (1 -e -zs t )t 2 β -1 dt = 0 z (1 -e -u ) zs u 2 β -1 -zs u 2 du = (zs) 2 β z 0 (1 -e -u )u -2 β -1 du = s 2 β β 2 [-1 + ϕ β (z)]
where the third equality is obtained by integration by parts.

Combining the above equation with Equations ( 16), ( 18) gives the final result.

The following results can be derived from Proposition 7, although we will not use them in the remaining part of the paper.

Corollary 8: The joint distribution of L and f is characterized by

E 1 {L ≥ u} e -zf = 1 ϕ β (z) e -au 2 β ϕ β (z) , z ∈ R + .
The unconditional Laplace transform of the interference factor is

E e -zf = 1 ϕ β (z) , z ∈ R + . ( 19
)
Proof: For the first statement we have

E 1 {L ≥ u} e -zf = ∞ u E e -zf |L = s P L (ds) = ∞ u e -a[ϕ β (z)-1]s 2 β 2a β s 2 β -1 e -as 2 β ds = 1 ϕ β (z) e -au 2 β ϕ β (z)
where for the second equality we use ( 13) and (15). This completes the proof of the first statement. For the second statement, conditioning on the value of the path-loss factor yields

E e -zf = R + E e -zf |L = s P L (ds)
where P L (•) is the distribution of L given by ( 13). Using the above equation and (15), we ascertain

E[e -zf ] = ∞ 0 e -a[ϕ β (z)-1]s 2 β 2a β s 2 β -1 e -as 2 β ds = 2a β ∞ 0 s 2 β -1 e -aϕ β (z)s 2 β ds = 1 ϕ β (z) ∞ 0 aϕ β (z) 2 β s 2 β -1 e -aϕ β (z)s 2 β ds = 1 ϕ β (z)
where the third equality stems from ϕ β (z) = 0 which follows from (40) in Appendix B and the assumption β > 2.

Remark 9: For t ≥ 1 the (complementary) CDF of the SIR admits the following explicit expression

P{ SIR ≥ t } = P{f ≤ 1/t} = t -2/β C (β) (20)
where

C (β) = 2π β sin(2π/β) = 2Γ(2/β)Γ(1 -2/β) β and Γ(z) =
∞ 0 e -z z t-1 dt it the complete Gamma function. It was proved in [START_REF] Dhillon | Modeling and analysis of K-tier downlink heterogeneous cellular networks[END_REF] assuming exponential distribution of S. But in the infinite Poisson model, SIR is invariant with respect to λ, and K and consequently by Lemma 1 it is also invariant with respect to the value of E[S 2/β ]. Hence the result remains valid for arbitrary distribution of S, provided E[S 2/β ] < ∞. Other results of [START_REF] Dhillon | Modeling and analysis of K-tier downlink heterogeneous cellular networks[END_REF], including these involving the superposition of independent Poisson models (called K-tier cellular network model) can also be appropriately generalized using Lemma 1.

B. Distribution of SINR, spectral and energetic efficiency 1) SINR: In this section we are primarily interested in the signal to interference and noise ratio

SINR = 1 L N + i∈N 1 L X i -1 L = 1 N L + f , (21)
where N is the noise power. We will show how CDF of the SINR can be evaluated, which opens a way for the study of functionals of SINR.

2) Spectral efficiency: An important characteristic of a wireless cellular network is its spectral efficiency, defined in the simplest case of additive white Gaussian noise (AWGN) and the optimal theoretical link performance as

S := log (1 + SINR) .
It tells us how many bits per second and per Hertz can be sent to the typical user of the network.

3) Energy efficiency: Up to now we have considered a unit transmitted power. Assume now that base stations transmit some power P ≥ 0. In fact, in order for a base station to be able to transmit this power to the mobile, it needs to be powered (i.e., consumes energy per second) at the level P > P . Following [START_REF] Richter | Energy efficiency aspects of base station deployment strategies for cellular networks[END_REF], assume that these two quantities are related through a simple linear relation P = cP +d for some positive constants c and d. The energy efficiency is defined by

E := E(P ) = W log 1 + 1 N L/P +f cP + d .
where W is the bandwidth expressed in Hz. Thus E is equal to W log(1 + SINR(P ))/P , where SINR(P ) takes into account the transmitted power, and P is the consumed power. It tells us how many bits per second per Watt of consumed power can be sent by a base station to the typical user. Note that E(0) = E(∞) = 0 and thus E(P ) admits a non-trivial optimization in P .

4) Evaluation of the CDF of the SINR: Proposition 7 in conjunction with Corollary 6 completely characterizes the joint distribution of L and f . It does not, however, allow for an explicit expression for the CDF of the SINR in the whole domain (cf Remark 9). In this section we describe a practical way for numerical computation of this CDF. We will use it to study the spectral and energy efficiency. In fact, we will compute the CDF of the random variable Y := N L + f , which is sufficient, in view of (21).

Proposition 10: The cumulative distribution function of Y is given by

P (Y < x) = ∞ 0 F s (x -N s)P L (ds) (22)
where P L (ds) is given by ( 13), and F s (y) := P (f < y|L = s) may be expressed by

F s (y) = 1 - 2e γt π ∞ 0 R L Fs (γ + iu) cos ut du , ( 23
)
where γ > 0 is an arbitrary constant, R is the real part if it complex argument and

L Fs (z) = 1 z - 1 z e -a[ϕ β (z)-1]s 2 β ( 24
)
with ϕ β (•) is given by ( 14). Proof: The expression ( 22) is trivial. The expression (23) of the (conditional) CDF F s is based on the Bromwich contour inversion integral of the Laplace transform L Fs of 1 -F s . The expression (24) for this latter follows from (15).

Remark 11: As shown in [START_REF] Abate | Numerical inversion of Laplace transforms of probability distributions[END_REF], the integral in (23) can be numerically evaluated using the trapezoidal rule, with the parameter γ allowing control of the approximation error. The function F s may be also retrieved from (15) using other inversion techniques.

Remark 12: For t ≥ 1 the (complementary) CDF of the SINR admits the following expression

P{SINR ≥ t} = 2t -2/β Γ(1 + 2 β ) ∞ 0 re -r 2 Γ(1-2/β)-N a -β/2 r β dr
(25) with a given by (4). It follows from [START_REF] Dhillon | Modeling and analysis of K-tier downlink heterogeneous cellular networks[END_REF]Theorem 1] (where the exponential distribution is assumed for S) and our Lemma 1. Note on Figure 2 that the expression is not valid for t < 1.

5) Numerical examples:

In what follows we assume the following parameter values. If not otherwise specified we take log-normal shadowing with logarithmic standard deviation σ dB = 12dB (cf the footnote on page 3). The parameters of the distance-loss model are K = 4250Km -1 , β = 3.52 (which corresponds to the COST-Hata model for urban environment with the BS height 30m, mobile height 1.5m, carrier frequency 805MHz and penetration loss 19dB). For the hexagonal network model simulations, we consider 900 base stations (30x30) on a torus, with the cell radius R = 0.26Km (i.e., the surface of the hexagonal cell is equal to this of the disk of radius R). System bandwidth is W = 10MHz, noise power N = -93dBm.

Figure 2 shows the CDF of the SINR assuming the base station power P = 58.5dBm. We obtain results by simulations for finite hexagonal network on the torus with and without shadowing as well as the finite Poisson network on the same torus. For the infinite Poisson model we use our method based on the inversion of the Laplace transform. For comparison, we plot also the curve corresponding the explicit expression (20), which is valid only for SINR > 1.

Figure 3 shows the expected energy efficiency E(E) of the finite hexagonal model with and without shadowing as well as the infinite Poisson, assuming the affine relation between consumed and emitted power with constants c = 21, 45 and d = 354.44W.

On both figures we see that the infinite Poisson model gives a reasonable approximation of the (finite) hexagonal network provided the shadowing is high enough. In particular, the value of the transmitted power at which the hexagonal network with the shadowing attains the maximal expected energy efficiency is very well predicted by the Poisson model.

CONCLUSIONS

We present a powerful mathematical convergence result rigorously justifying the fact that any actual (including regular hexagonal) network is perceived by a typical user as an equivalent (infinite) Poisson network, provided log-normal shadowing variance is sufficiently high. Good approximations are obtained for logarithmic standard deviation of the shadowing greater than approximately 10dB, which is a realistic assumption in many urban scenarios. Moreover, the equivalent infinite Poisson representation is invariant with respect to an additional fading distribution. Using this representation we study the distribution of the SINR of the typical user. In particular, we evaluate and optimize the mean energy efficiency as a function of the base station transmit power.

APPENDIX

A. Proof of Theorem 3

In order to simplify the notation we set n := σ 2 . Moreover, without loss of generality we assume that n takes positive integer values. Also, it is more convenient to study the point process of propagation losses on the logarithmic scale, which we do in what follows. In this regard denote by Λ log the image of the measure Λ given by ( 3) with a = λπ/K 2 through the logarithmic mapping

Λ log ((-∞, s]) := R + 1(log(t) ≤ s) Λ(dt) = π K 2 e 2s β
for s ∈ R.

For a given i, we first observe by ( 6) that

ν n (s, |X i |) := P log K(n) β |X i | β S (n) i ≤ s = P Z i ≤ s -β log(K|X i |) -n/β √ n = G s -β log(K|X i |) -n/β √ n , (26)
where G is the CDF of the standard Gaussian random variable. Let B 0 (r) = {x ∈ R 2 : |x| < r}. We now need to derive two results. provided that a n and b n satisfy [START_REF] Richter | Energy efficiency aspects of base station deployment strategies for cellular networks[END_REF] and [START_REF] Abate | Numerical inversion of Laplace transforms of probability distributions[END_REF]. Proof: We start with the integral over R 2 in polar form We proceed similarly with the other integral in Lemma 13

= β 2 √ n ∞ -∞ exp - t 2 2 + 2t √ n β dt √ 2π = β 2 √ n exp 2n β 2 ∞ -∞ exp - 1 2 t - 2 √ n β 2 dt √ 2π (28)

Fig. 1 :

 1 Fig. 1: Empirical CDF of SIR simulated in hexagonal network with shadowing and their Poisson approximations.

Fig. 2 :

 2 Fig. 2: CDF of the SINR for (finite) hexagonal network with and without (σ dB = 0dB) shadowing, finite Poisson as well as for the infinite Poisson model. The last in the legend curve corresponds to (20).

Fig. 3 :

 3 Fig. 3: Mean energy efficiency of finite hexagonal model with and without (σ dB = 0dB) shadowing as well as the infinite Poisson in function of the transmitted power.

Lemma 13 : 2 ν

 132 lim n→∞ B0(bn)\B0(an) ν n (s, |x|)dx = lim n→∞ R n (s, |x|)dx = Λ log ((-∞, s])

R 2 ν

 2 n (s, |x|)dx = 2π ∞ 0 rG s -β log(Kr) -n/β √ n drIntroduce a change of variables t = s -β log(Kr) -

  B0(bn)\B0(an) ν n (s, |x|)dx = 2π bn an rG s -β log(Kr) -n/β √ n dr.The change of variablest = s-β log(Kr)-n/β √ s -β log(Ka n ) -n/β √ n , v n = s -β log(Kb n ) -n/β √ n .

  Noting that G(-t) = 1 -G(t) := Ḡ(t), apply integration by parts on the above integral

									∞ -∞	exp	-2t β √	n	G(t)dt = = + β 2 √	∞ -∞ β 2 √ n n ∞ exp exp -∞ exp 2t √ β 2t √ n n β 2t √ β	n	Ḡ(t)dt ∞ Ḡ(t) -∞ g(t)dt,
									where g(t) is the normal probability density, and, via the
									inequality
									y	∞	e -x 2	dx <	e -y 2 (1 + y)	, y ≥ 0 ,	(27)
									(cf [12, Section 7.8]) the final integrated term on the left
									vanishes. Hence
									∞ -∞	exp	-2t √ β	n	G(t)dt
		∞ -∞	1 K 2 exp	2 β	s -t √	n -n/β G(t)	√ β n	dt
	= 2π	√ β n	exp 2 β (s -n/β) K 2	∞ -∞	exp	-2t √ β	n	G(t)dt

This also means that the path-loss from a given station X expressed in dB, i.e., dB(L X (y)), where dB (x) := 10×log 10 (x) dB, is a Gaussian random variable with standard deviation σ dB = σ10/ log 10, called logarithmic standard deviation of the shadowing.

We now derive the conditions of a n and b n which ensure that the above integral converges and the integrated term disappears. The latter can be achieved, given inequality (27), in the limit as -u n and -v n both approach infinity, or equiv-

which agrees with conditions [START_REF] Richter | Energy efficiency aspects of base station deployment strategies for cellular networks[END_REF] and [START_REF] Abate | Numerical inversion of Laplace transforms of probability distributions[END_REF]. Further conditions are revealed after the change of variable

whose limits of integration imply, in light of the earlier integral (28), that as n → ∞ the following β log(Kbn) n > 1/β and β log(Kan) n < 1/β are required, of which both conditions (10) and (11) satisfy.

Lemma 14: Assume (5), [START_REF] Richter | Energy efficiency aspects of base station deployment strategies for cellular networks[END_REF] and [START_REF] Abate | Numerical inversion of Laplace transforms of probability distributions[END_REF], then lim n→∞ Xi∈φ∩(B0(bn)\B0(an))

Proof: For k ≥ 0 and a fixed > 0, let r k = e k and A k = B 0 (r k+1 ) \ B 0 (r k ), and write the summation in (30) as

for some k 0 ≥ 0, whose value will be fixed later on. In the limit of n → ∞, the first summation in (31) disappears

where X * gives the maximum of G s-β log(K|X|)-n/β √ n over X ∈ φ∩B 0 (r k0 ) which exists since φ is (by our assumption) a locally finite point measure. For the second summation in (31) we write ν n (s,

Then the bounds

and form of ν n , which implies ν n (s, |x|e ) = ν n (s -β , |x|), lead to the lower bound

and the upper bound

(33) Moreover, we write

and requirement (5) yields lim k→∞ φ(A k )

|A k | = λ. Hence, for any fixed δ > 0, there exists a k 0 (δ) such that for all k ≥ k 0 , the bounds

Finally, Lemma 13 allows us to set a n = r k0 and b n = ∞, hence

and similarly the upper bound (33) becomes

, and indeed → 0 and δ → 0 completes the proof of (30). The other result, (29), can be proved by a straightforward modification of the above arguments.

Proof of Theorem 3: We use a classical convergence result [START_REF] Daley | An introduction to the theory of point processes[END_REF]Theorem 11.22V] which in our setting requires verification of the following two conditions (cf [8, (11.4.2) and (11.4.3)])

and

for all bounded Borel sets A ⊂ R, where ν i n (•) is the (probability) measure on R defined by setting ν i n ((-∞, s]) := ν n (s, |X i |). The first condition, (34), clearly holds by (26) for any locally finite φ. The second condition, (35) follows from Lemma 13 and 14, which establish the required convergence for A = (-∞, s] and any s ∈ R. This is enough to conclude the convergence for all bounded Borel sets.

B. Representation of the function ϕ β (z) given by (14)

Lemma 15: The function ϕ β (z) given by ( 14) can be written as

where

is an analytic function on C × C. Moreover ϕ β (z) > 0, ∀β > 2, ∀z ∈ R + (40)

Proof: Using (14) and recurrence formula [13, 6.5.22] we obtain (36). Introducing the modified incomplete gamma function γ * defined by (38) (which is holomorphic on C × C; see [13, 6.5.4]) we obtain (37). The expansion (39) is given in [13, 6.5.29]. This expansion shows that if α > -1 then for any z ∈ R + , γ * (α, z) > 0, and therefore by (37) ϕ β (z) > 0 for any β > 2, z ∈ R + .


F Gilbert

G Stora

G Desrosiers

J-P Gagne

B Deflandre

J-C Bertrand

CHANGES IN ALIPHATIC HYDROCARBON TRACER COMPOSITION DURING THE DIGESTIVE PROCESS OF THE MARINE WORM NEREIS VIRENS. PRELIMINARY RESULTS

In the laboratory, marine worms were fed with a mixture of algae and several aliphatic hydrocarbons for 15 days. By comparing hydrocarbons in food and in faeces, it appeared that the worm's digestive process led to changes in the distribution of the n-alkanes mixture. These changes were different from those only due to physical processes in the experimental conditions, indicating that marine worm feeding could substantially affect the fate of hydrocarbons in the sedimentary marine ecosystem.

 and extend it throughout the whole depth of bioturbated sediment depth 9 . However, if hydrocarbon redistribution is principally the result of particle transport induced by macrofauna during various activities (e.g. tube and burrow construction), it may also be realized through the

faeces production process [START_REF] Lee | Analysis, Chemistry, Biology[END_REF] . In areas of intensive reworking, where surface sediments are ingested several times a year 10 , passage through the gut exposes sorbed hydrocarbons to a harsh chemical and active microbiological environment 11 . If the metabolization of polycyclic aromatic hydrocarbons 7,[START_REF] Lee | Marine Pollution: Functional Responses[END_REF][START_REF] Mcelroy | [END_REF][14] by worms has been demonstrated, little information is available on the uptake of aliphatic hydrocarbons 3 by worms and their fate through the digestion process. A laboratory experiment has been carried out in order to investigate the fate of a mixture of aliphatic hydrocarbons ingested by the marine worm Nereis virens which is widely distributed in estuarine ecosystems. In this paper, we present the preliminary results obtained. EXPERIMENTAL -Collection of polychaetes and experimental setup: Twenty adult Nereis virens individuals with an average weight of 3.16  0.29 g (mean  SE, n=20) were randomly collected in the tidal zone of l'Anse à l'Orignal (Bic, Québec) in November 1996. They were divided into 4 groups and placed in 4 containers (50 cm x 25 cm x 5 cm). Each container was separated into 5 sections, and in each section a worm was placed in a horizontal glass tube (length: 19 cm ; i. d.: 0.7 cm). The containers were filled with filtered seawater which was kept aerated by a small aquarium pump and maintained at constant temperature (15°C) on a 12 h light : 12 h dark cycle. Sea water was replaced each day. Worms were acclimated to the experimental conditions during 7 days (Figure 1).

For the same period, the animals were not fed in order to clear their gut.

-Polychaetes feeding: Experimental food was prepared from individual portions of fresh algae Enteromorpha spp. (13.9 ± 1.7 mg; mean ± SE, n=304) doped with hydrocarbon tracer (3.6 ± 0.2 mg; mean ± SE, n=304) containing a mixture of eight n-alkanes (n-C 14 , n-C 15 , n-C 17 , n-C 18 , n-C 22 , n-C 23 , n-C 28 and n-C 29 ), one isoprenoid alkane (pristane) and one cyclic alkane (androstane). These hydrocarbons were wrapped inside a fresh leaf of algae to form a small pellet preserved frozen to -20°C until feeding to the marine worm. This small solid pellet is stable for a few minutes in water and can therefore be used as feed for the marine worm.

At the beginning of the experiment, both experimental tubes and sections were cleaned and the sea water replaced. Then, at the start of the dark period, each worm was individually fed with a food portion, which was positioned at the end of the tube towards which the worm's head was pointing. In the following 10 seconds, the food portion was picked up by the worm. After 2, 4, 8, 12 and 24 hours 15 , the faeces of the five individual worms living in each separate container were sampled in the glass tubes and individual sections, regrouped, weighed and frozen before analysis. After collection of the 24h-faeces, the thin mucous layer with which inhabited tubes were coated was also collected, weighed and frozen. The tubes and sections were then cleaned by collecting the food residues, and the sea water was replaced. A new food portion was then given to each worm. During the experiment, worms were fed 15 times. In an additional container, in order to evidence possible non-worm related changes in tracer composition, e.g. induced by dissolution, four food portions were subjected to experimental conditions for 24 hours to serve as control. The four "24h-Controls" were then collected and separately frozen.

-Hydrocarbons analysis : The hydrocarbons were extracted from each crushed material (faeces, mucus or gut) by maceration in 10 ml of dichloromethane and sonication for 15 min. The mixture was then centrifugated at 7 000 g for 10 min and the supernantant filtered (Whatman GF/C). This extraction procedure was repeated three times for each sample. The three fractions collected were pooled and dichloromethane was removed by evaporation. The dried sample was redissolved in 1 ml hexane and loaded into a conditioned solid sorbent cartridge. The mini chromatographic column Alumina N Sep-Pak® Plus Cartridge was pre-conditioned by successive elutions of toluene (10 ml) and hexane (10 ml). The aliphatic hydrocarbons were then eluted with 10 ml of hexane and analysed by GC/MS (5970 B HP, SPB-5 Supelco capillary column, temperature program 16 ) using n-eicosane as internal standard.

-Data analysis : Differences between materials were studied using a one-way analysis of variance (ANOVA).

Bartlett's test was employed to test for homogeneity of variance. Heteroscedastic data were transformed and then evaluated using ANOVA.

RESULTS AND DISCUSSION

In this paper, we presented the results obtained after 15 days, corresponding to the end of the feeding experiment. Figure 2 illustrates recovery percentage of the different compounds (n-alkanes, pristane and androstane) from the initial tracer (food portion), in the 24h-Control and the 24h-Transit/D15 materials (faecal material sampled during 24 h after worm feeding, for the 15 th day of experiment).

Results showed first that all the compounds of the initial tracer (food portion) were present in 24h-Control and in faeces. However, it appeared that the distribution of the n-alkanes changed with the experimental conditions.

After a 24h stay in the seawater (24h-Control), the distribution of n-alkanes indicated a loss of compounds in the food portion. The loss was greater for the low molecular weight n-alkanes (LALK 17 ) than for the heavy molecular weight n-alkanes (HALK) (Table I) and could be explained by dissolution and volatilization, the food portions floating at the water surface. On the other hand, on the 15th day of experimentation, the change in the tracer composition induced by ingestion of the initial tracer by worms was different. An increased loss of the low molecular weight compounds (n-alkanes from n-C 14 to n-C 18 and pristane) was apparent in the 24hsampled faeces, whereas the differences measured for the highest molecular weight n-alkanes (from n-C 22 to n-C 29 ) were slight, resulting in greater decrease of LALK/HALK ratios (Table I). Moreover, the n-C17/Pr ratio, a diagnostic ratio used to study the biodegradation of hydrocarbons 8,9,18 , which was calculated from the 24h-Control and 24h-Transit/D15 samples was significantly different. For both materials, the increase of the n-C17/Pr ratio ran counter the evidence of the bacterial degradation of hydrocarbons 19 , though this was less marked for the 24h-Transit/D15 samples. androstane.

However, we should bear in mind that a recent work has demonstrated that the use of this n-alkane/isoprenoid ratio may be limited in certain experimental conditions 20 .

The alteration in the n-alkane tracer composition in the faece samples could then be not solely related to the dissolution and volatilization of compounds during the stay of faeces in seawater (<12h) but might be in part due to the impact of the worm's digestif process involving :

-stimulation of the dissolution process induced by the gut transit;

-preferential adsorption of compounds in the worm gut;

-chemical or/and biological attack on the compounds in the worm gut as demonstrated with aromatic hydrocarbons 7,12-14 ;

-and, though classical specificity in the possible compound microbial biodegradation 21 was not indicated by the study of the n-C17/Pr ratios, the development of a hydrocarbonoclastic microflora and the biodegradation of coumpounds in the worm gut and/or biodegradation occurring in the faeces. The first result presented in this paper demonstrates the direct role of the Nereis virens digestive process in the fate of hydrocarbons in the sediments, passage through the worm gut altering the composition of the hydrocarbon mixture tracer in a different manner than would physical processes of compounds alone. Further complementary results might make it possible to determine whether hydrocarbons are stored in worms and whether the process demonstrated after 15 days of experimentation varied with the time the worms are exposed to hydrocarbons.

FreezingFigure 1 :

 1 Figure 1: Experimental procedure. The various steps are described in detail in text.

Figure 2 :

 2 Figure 2: Recovery percentage of the various compounds from the initial tracer (food portion) in the different experimental material samples. Standard errors appear above the mean values (n=4). 24h-Control: food portion submitted to experimental conditions for 24 hours in absence of worms; 24h-Transit/D15: faeces sampled during 24 h in a container containing four Nereis virens, after the ingestion of one food portion per worm, for the 15 th day of experiment). Numbers refer to carbons in n-alkanes (n-C 14 to n-C 29 ); Pr: pristane; Andr:

Table I LALK

 I

	C 23 ,	n-C 28 , n-C 29 ); Pr: pristane.
			Initial Tracer	24h-Control	24h-Transit/D15
		LALK/HALK	0.91±0.2	0.73±0.2	0.42±0.4
		n-C17/Pr	0.67±0.1	1.12±0.3	0.90±0.4

/HALK and n-C17/Pr ratios of the hydrocarbon n-alkanes composition calculated from the different materials. ANOVA analysis (for 4 replicates) comparing the values indicates a significant difference between the three types of material for both ratios (P < 0.001). For the name of each material, see text. LALK: Low molecular weight n-alkanes (n-C 14 , n-C 15 , n-C 17 , n-C 18 ); HALK: heavy molecular weight n-alkanes (n-C 22 , n-

ACKNOWLEDGEMENTS

The authors are grateful to Diane "S.O.S. GC/MS" Bérubé for her kindness. This work was carried out as part of the G.R.E.C. (Groupe de Recherche en Environnement Côtier, UQAR, Québec, Canada) and the G.D.R. "HYCAR" (Groupement De Recherche n°1123, CNRS -Universities -Société Elf Aquitaine, France) and was supported by a grant from the Société de Secours des Amis des Sciences (to Franck Gilbert) and by grants from the Natural Sciences and Engineering Research Council of Canada (CRSNG) to Gaston Desrosiers and Jean-Pierre Gagné.