Jonas Kahn

IMPROPER POISSON LINE PROCESS AS SIRSN IN ANY DIMENSION

Keywords: AMS 2000 subject classifications. Primary 60D05; secondary 90B15, 51F99, 60G55 Poisson line process, SIRSN, scale-invariant random spatial network, stochastic geometry, spatial network, random metric space, Π-geodesic, many directions

Aldous has introduced a notion of scale-invariant random spatial network (SIRSN) as a mathematical formalization of road networks. Intuitively, those are random processes that assign a route between each pair of points in Euclidean space, while being invariant under rotation, translation, and change of scale, and such that the routes are not too long and mainly lie on "main roads".

The only known example was somewhat artificial since invariance had to be added using randomization at the end of the construction. We prove that the network of geodesics in the random metric space generated by a Poisson line process marked by speeds according to a power law is a SIRSN, in any dimension.

Along the way, we establish bounds comparing Euclidean balls and balls for the random metric space. We also prove that in dimension more than two, the geodesics have "many directions" near each point where they are not straight.

1. Introduction. Scale-invariant random spatial networks (SIRSNs) are a class of random networks defined as a route between each pair of points, with three types of properties. First, invariance properties, second, guarantees on mean lengths of routes-in the Euclidean metric-and third guarantees on the mean length of intersection of a suitably truncated version of the network with a given compact set. It turns out that these conditions are enough to deeply constrain the network. For example, all SIRSNs have singly-infinite paths for which any subset is included in a route, but no such paths are doubly-infinite.

The only known example is the binary hierarchy model, in two dimensions. It consists of minimum-time paths on a dyadic grid where speed depends on the two-valuation. Invariance is obtained by a randomization construction. The latter feature is somewhat unsatisfying: the model itself is invariant, but realisations exhibit long-range dependence: observation of a small region gives much information on the network everywhere.

A more "natural" candidate for a SIRSN is therefore the Poisson line process model. Intuitively, lines are thrown uniformly at random in R d , and marked with random speed limits. Slower lines are dense in R d . Then the route between two points is the minimum-time path made of segments of these lines. Remarkably, even in dimension d ≥ 3, when random lines almost surely do not intersect, such paths exist. The whole construction is invariant. The aim of this paper is to show that the Poisson line process is indeed a SIRSN for all d ≥ 2.

Historically, [START_REF] Aldous | Scale-invariant random spatial networks[END_REF] introduced the notion of a SIRSN, and proved a number of their properties, including those mentioned in the first paragraphs of this Introduction. [START_REF] Aldous | True scale-invariant random spatial networks[END_REF] give a verbal description. The motivation was twofold.

First, [START_REF] Aldous | Short-length routes in low-cost networks via Poisson line patterns[END_REF] had proved that it was possible to build a road network connecting a prescribed set of points that both had routes almost as short as the segments between each pair of points, that is, the corresponding Euclidean geodesics, and total road length almost as short as the Steiner tree, that is, the shortest possible connecting network. However, the network was less efficient at small scales. Thanks to their invariance properties, SIRSNs have the same efficiency at all scales. It turns out that there is a trade-off: for a SIRSN, there is a lower bound on the expected total length of the network, which is decreasing in the expected route length between two points.

The second motivation was to give a mathematical abstraction of road networks and maps, in particular online maps as they are used today. Namely, we may change viewpoint, zoom in or out, and the appearance changes little, as smaller roads are shown and hidden. SIRSNs are then defined as statistically invariant under translation, rotation and change of scale. Moreover, we are less interested in the roads than in the routes: how do we drive from A to B? SIRSNs are thus defined by giving routes only, namely unique routes connecting pairs of points. It turns out that a notion of "main roads" at any scale can be built from the network of routes itself. To wit, the network of main roads at scale r would be the network of routes deprived of balls of radius r around their endpoints. It is finite in every compact. Similarly, [START_REF] Kalapala | Scale invariance in road networks[END_REF] have shown that a number of statistics of real road networks do not depend on scale. [START_REF] Aldous | Scale-invariant random spatial networks[END_REF]proved that the binary hierarchy model was a SIRSN, and suggested two other possible models for SIRSN, one of which is the Poisson line process model. [START_REF] Kendall | From random lines to metric spaces[END_REF] has then proved important properties of the Poisson line process with appropriate speeds: it does yield a random metric space and this space is a geodesic space. Moreover, in dimension two, the geodesics are almost everywhere unique, the geodesics are locally of finite mean-length, and the subnetwork obtained from the routes connecting points of an independent Poisson point process has finite length in a compact set. The latter properties establish a "pre-SIRSN" result, but fall short of the full definition.

As a candidate for a SIRSN, Poisson line process model then fall in a large category: networks derived from geodesic spaces. Indeed, from any geodesic space, we may build a spatial network by associating to any two points the geodesic(s) connecting them. It is not obvious how one might determine when such a network is a SIRSN.

In Section 2, we give a precise definition of a SIRSN and of Poisson line processes. We also present other notation and definitions, and recall some known results, in particular that the Poisson line process with speed limits yields a random metric on R d . We then give a few basic properties of Πpaths, that is paths in this metric space. In Section 3, we give sharp bounds on the random diameter for this metric of a Euclidean ball, with a few generalizations. These estimates will be an important tool in several subsequent proofs. In Section 4, we prove that geodesics between a given pair of points are almost surely unique, in any dimension. Lemma 4.6 will play a central role: we introduce the notion of "many directions", and the lemma states that geodesics have many directions at relevant points. A consequence is that any path using the same lines as a geodesic will contain these points. We will then conclude by noticing that geodesics between the same pair of points almost surely use the same lines (Lemma 4.7). In Section 5, we prove that geodesics have finite mean Euclidean length. Alternatively, we may see the result as supplying a stochastic control of the Euclidean diameter of balls for the metric generated by the Poisson line process. Section 6 contains the last and most important component of the proof that the Poisson line process generates a SIRSN. Intuitively, we establish a sharp control of the total length of the intersection of all infinitely many geodesics minus a ball around each endpoint, with a given ball. This corresponds to the fact that all these geodesics coalesce before hitting the ball and split after leaving it. Bounds are given using the pigeon-hole principle and the fact that relevant geodesics must use the few fast lines that hit the ball. Finally, Section 7 suggests a few potential directions of future inquiry.

2. Notation, definitions, basic properties. We follow [START_REF] Kendall | From random lines to metric spaces[END_REF] notation whenever possible.

We write B(x, r) for the ball with center x and radius r.

We first give the precise definition of a SIRSN. Suppose that Λ is an atom-free measure on a measurable space (X , B). Recall that a Poisson point process of intensity measure Λ is a random set of points such that for any B ∈ B, the number of points N (B) in B is a Poisson variable with intensity Λ(B), and the number of points N (B i ) in disjoint B i are independent. Then a SIRSN is defined as follows.

Definition 2.1. A SIRSN is a process that associates to any two points x 1 and x 2 in R d random routes such that:

1. Between two specified points x 1 and x 2 , there is almost surely a unique route R(x 1 , x 2 ) = R(x 2 , x 1 ). It is a finite-length path connecting x 1 and x 2 .

2. For a finite number of points x 1 , . . . , x k in R d , consider the subnetwork N (x 1 , . . . , x k ) formed by the random routes connecting all x i and x j . Then N (x 1 , . . . , x k ) is statistically invariant under translation, rotation and change of scale: if R is a Euclidean similarity of R d , then N (R(x 1 ), . . . , R(x k )) has the same distribution as RN (x 1 , . . . , x k ).

3. Let D 1 be the length of a route between two points at unit distance.

Then E[D 1 ] < ∞.
4. Let {Ξ n , n ∈ N * } be a collection of Poisson processes on R d with intensity n times Lebesgue, all independent from the SIRSN. Suppose they are coupled so that Ξ n ⊂ Ξ n+1 . Write Ξ = n∈N * Ξ n . Then the intensity (mean length per unit area) p(1) of the following long-distance network is finite:

x 1 ,x 2 ∈Ξ (R(x 1 , x 2 )) \ (B(x 1 , 1) ∪ B(x 2 , 1)).
Note that [START_REF] Kendall | From random lines to metric spaces[END_REF] uses more conditions in his definition, but the missing properties are implied by property 4. They were useful to define weaker variants of a SIRSN.

The use of Poisson processes in property 4 makes it look slightly complex, but this is a technical shortcut: it allows us to study the network through only countably many routes. Morally, we would like property 4 to hold true if the long-distance network was defined as the union of all routes between all pairs of points of R d , minus the balls around the endpoints. But there would be uncountably many routes, and it would be harder to work with.

We now turn to the definition of the improper Poisson line process. We first need a measure on lines. More details on this kind of process may be found in the book by Stoyan, [START_REF] Kahn Stoyan | Stochastic Geometry and Its Applications[END_REF].

Let L d be the space of all lines of R d . A line is "un-sensed", that is, it is seen as a subset of R d , without a preferred direction. For K, a compact of R d , the hitting set of K is the set of lines that intersect K, denoted as

[K] = {l ∈ L d : l hits K}.
We also denote by m d the Hausdorff measure of dimension d. With this notation, we have the following.

Definition 2.2. The invariant line measure µ d (l) is the unique measure on the space of lines of R d that is invariant under Euclidean isometries, and normalized by the following requirement: for a compact set K in R d of nonempty interior, the µ d -measure of the hitting set of K is half the Hausdorff (d -1)-dimensional measure of the boundary of K:

µ d ([K]) = 1 2 m d-1 (∂K).
The reason for the normalizing constant 1 2 is to ensure that the measure of the hitting set of a flat hypersurface A is its hyperarea m d-1 (A).

We will often need the hitting set of a ball, so write ω d-1 for the hyperarea of the unit sphere S d-1 . Thus

µ d ([B(x, r)]) = ω d-1 2 r d-1 .
Consider the following parameterization of a line l: it is given by a direction and a localization. The direction is an element of the projective space P R d-1 . It then defines a hyperplane normal to this direction, through a special point-the origin-of R d . The localization is a point on this hyperplane. The line l is then the line through this point normal to this hyperplane.

Hence, writing H = R d-1 for an hyperplane of R d , we may parameterize the set of lines by P R d-1 ⊗ H. Notice that if we want to keep track of the topology of the set of lines, the product should be twisted, but we only need measure-theoretical properties, so we stick to the simpler direct product.

Recall that the projective space P R d-1 may be seen as the sphere S d-1 with opposite-antipodal-points identified. The projective space then inherits the natural metric on the sphere, namely the distance between two pairs of antipodal points is the angle between the pair of segments joining them, in radians. Up to a null-measure set, the projective space may be more simply viewed as a hemisphere.

With this parameterization, and writing B d for the unit ball in R d , we may write µ d as a product measure on P R d-1 ⊗ H:

µ d = 1 m d-1 (B d-1 ) m d-1 ⊗ m d-1 .
To make a clearer reference to it, we write µ

(o) d-1 = 2m d-1 /m d-1 (S d-1
) for the probability measure on P R d-1 . For a set of lines L, we write µ

(o) d-1 (L)
for the measure of the set of directions of lines in L that go through the origin. In particular, for A a subset of R d and x a point of R d , the value µ

(o) d-1 ([A -x]
) will be the proportion of directions that appear in the set of directions of lines through A and x. We call it the solid angle of A from x. Notice that it is not quite the usual definition since pairs of antipodal points contribute only once, and since we have normalized to a probability measure. This is because we are concerned with orientations of undirected lines, rather than angles of directed lines.

A special case we shall need is the measure of a cone, that is, all the lines with angle less than θ 0 from a given line through the origin. This measure is proportional to the area on the hemisphere hit by the lines, hence proportional to θ 0 0 sin d-2 θ cos θ dθ = sin d-1 (θ 0 )/(d -1). The integral up to θ 0 = π/2 has value 1, so that

µ (o) d-1 (cone of aperture θ 0 ) = sin d-1 (θ 0 ). (1)
The uniform Poisson line process is the image of the Poisson point process on L d with intensity measure µ d .

We define our improper Poisson line process by adding a mark on each line, a speed limit. Namely, the improper Poisson line process is the image of a Poisson point process on P R d-1 ⊗ H ⊗ R + * with intensity measure µ d,γ , given by the density [START_REF] Kendall | From random lines to metric spaces[END_REF] does define this process for all γ > 1, but the relevant case for SIRSNs is that of γ > d.

dµ d,γ (l, v) = dµ d (l)(γ -1)v -γ dv for γ > d.
In words, we have more and more slower lines, following a power law. Since v -γ dv diverges at zero, the lines are dense in R d . However, lines faster than any given speed are not dense. In particular, the number of lines faster than v 0 hitting a convex set K is a Poisson variable with parameter

µ d,γ ((l, v) : l ∈ [K] and v ≥ v 0 ) = µ d ([K]) ∞ v 0 (γ -1)v -γ dv = 1 2 m d-1 (∂K)v -(γ-1) 0
.

We call Π = Π(d, γ) the corresponding random process of marked lines (l, v). Since the dimension d and parameter γ will always be clear from context, we drop them in the notation. Notice that the total number of lines is almost surely countable. If (l, v) ∈ Π, we say that the speed of line l is v and denote it v(l).

For a subset L of lines, we write Π L for the restriction of Π to these lines, that is, Π L = {(l, v) : l ∈ L}. In particular, the line process restricted to lines hitting

A but not B is Π [A]\[B] .
We denote S the silhouette of Π, that is the random set in R d made of all the lines of Π, that is S = {x ∈ R d : ∃(l, v) ∈ Π : x ∈ l}. We also write S v 0 for the random closed set in R d made of all the lines (l, v) in Π such that v ≥ v 0 .

We may then define Π-paths.

Definition 2.3. A finite-time Π-path is a locally Lipschitz path in R d respecting the speed limits imposed by Π. More precisely, it is a continuous

R d -valued function ξ : [0, T ] → R d ,
with T finite, such that for almost all t ∈ [0, T ], either:

• the speed is zero: ξ ′ (t) = 0; • or the path follows a line in Π: there is a v ≥ |ξ ′ (t)| such that (ξ(t) + ξ ′ (t)R, v) ∈ Π.
We call T = T (ξ) the time length of the path ξ, or just its time for short.

An infinite-time Π-path ξ is the same, with T (ξ) = ∞, except that its domain is [0, ∞).

A Π-path is a finite or infinite-time Π-path.

In an abuse of notation, we write ξ ∈ Π.

Notice that the image of a Π-path is not necessarily contained in the silhouette S. It only needs to have speed zero outside S. The remark is especially relevant in dimension at least three, where the lines never cross. However, since the lines are dense in R d , it turns out that there are paths joining any pair of points, without any segment in R d \ S. We give a clearer intuition of their tree-like structure in the proof of Theorem 3.1 and Figure 1.

We write Π ab = {ξ ∈ Π : ξ(0) = a and ξ(T (ξ)) = b} for any two points a and b.

The following theorem is a union of results from [START_REF] Kendall | From random lines to metric spaces[END_REF] paper.

Theorem 2.4. Almost surely, all finite-time Π-paths have finite Euclidean length.

Almost surely, there are finite-time Π-paths between each pair of points of R d . Moreover, for any two points a and b, the infimum T ab of time lengths T (ξ) of Π-paths ξ ∈ Π ab is attained.

Hence, R d with the metric d(a, b) = T ab is a random metric geodesic space.

We call this metric time length or Π-length. Time diameters and similar notions are defined in the same way.

We denote by N the random network made by all the geodesics connecting all pairs of points in R d . Our aim is to show that N is a SIRSN.

It is often possible to define similar metrics on other sets Γ of marked lines, though they might not be geodesic. We then speak of Γ-length. The typical case is when we restrict Π to a subset of lines L, yielding Γ = Π L and Π L -length.

We now introduce some notation and remarks to make easier manipulating paths and geodesics:

• If ξ ∈ Π ab , we often write ξ ab instead. We cover each ball Bi with a r1-net, and connect each pair of balls of the net with a segment, be it a point (a). We then do the same at each scale, for rn+1-nets of the balls of the rn-nets (b). Each point belongs to a ball of the r1-net, so we build a path between two points starting from the segment connecting their balls (c). We then (d) and (e) connect the points to the segment endpoints with the segment connecting their balls in their respective r2-nets. At stage n, the path (f) is made of 2 n segments at each scale n.

• Concatenation of Π-paths is denoted ξ ac = ξ ab ξ bc , that is, ξ ac (t) = ξ ab (t) if t < T (ξ ab ), and ξ ac (t) = ξ bc (t -T (ξ ab )) if t ≥ T (ξ ab ). • We use the letter g for geodesics, and usually g ab for a geodesic from a to b. We say that g ab is unique if there is a unique geodesic from a to b. • In an abuse of notation, we identify a Π-path ξ with its image in R d whenever it is clear. Hence, we may write x ∈ ξ if there is a time t such that ξ(t) = x. Similarly, if g ab is unique and c, d ∈ g ab , we say that g cd is included in

g ab . • If g ab is unique and c ∈ g ab , then g ab = g ac g cb . • T (g ab ) = T ab . • For a line l ∈ Π and a Π-path ξ : [0, T ] → R d , we define the intersection length of ξ and l as L ξ (l) = m 1 (l ∩ ξ([0, T ])).
• If the intersection length of ξ and l is not zero, we say that l is in the support of ξ, or that it is supporting ξ. We write l ⊏ ξ. Moreover, we denote the support of ξ by

L ξ = {l ∈ Π : L ξ (l) > 0}. • We define the intersection time of l and ξ as T ξ (l) = m 1 ([0, T ] ∩ ξ -1 (l)).
• In particular, almost surely, for all geodesics g, we have the following equality and decompositions:

L g (l) = v(l)T g (l)
for all l ∈ Π,

T (g) = l∈Lg T g (l) (2) = l∈Lg v(l)L g (l). • If the support of ξ is included in L, that is L ξ ⊂ L, we say that ξ is Π L -path. We abuse notation by writing ξ ∈ Π L . • Similarly, we write ξ ∈ Π ab L if ξ ∈ Π L and ξ ∈ Π ab . Finally, a few more generic notation. We call internal ε-net of a subset A of R d any maximal subset x 1 , . . . , x k of A such that |x i -x j | ≥ ε for all i = j.
For a set A ⊂ R d , we write A r for its r-widening, that is the Minkowski sum A r = A ⊕ B(0, r). We denote the maximal speed of a set of lines L by v max (L). That is, v max (L) = sup l∈L v(l). Notice that if those lines all hit a compact set K, this supremum is a maximum. We abuse notation by writing v max (A) = v max ([A]) for A ∈ R d . We use C, c, c 1 , . . . , c i for any positive constant.

3. Π-diameters of sets. We start with giving a more quantitative version of Theorem 3.6 in [START_REF] Kendall | From random lines to metric spaces[END_REF] article. Namely, we show that in a given precompact set A, any two points can be joined in finite time, and that the largest time between two such points-the Π-diameter of A-is not too big with high probability: this random variable has more than an exponential moment. We include a generalization that we will need later on, by allowing the possibility of ignoring lines hitting forbidden areas F . Theorem 3.1. Recall that d ≥ 2 and γ > d. Let α min = 2 (γ-1)/(γ-d) . Let Ω < Ω max = (4α min ) 1-d and define α max = Ω -1/(d-1) /4. Choose α such that α min < α < α max , and note in particular that α > 1.

Let A and F be two subsets of R d , such that, for some r > 0:

• A is connected.

• From any x ∈ A r/(α-1) , the solid angle µ

(o) d-1 ([F -x]) of F is less than Ω. • A may be covered by • N balls B i of radius r.
Then there is a T 1 depending only on α, Ω, γ and d such that, for any

ε max = 1/(2 • N (2α + 1) d ) > ε > 0, with probability 1 -ε/ε max , the diameter of A on Π [A r/(α-1) ]\[F ] satisfies the bound T A,F = sup x,y∈A inf ξ∈Π xy [A r/(α-1) ]\[F ] T (ξ) ≤ T r, • N ln 1 ε 1/(γ-1) with (3) T r, • N = • N T 1 r (γ-d)/(γ-1) .
In particular, this maximal time has all exponential moments, and more: for any δ < T -1/(γ-1) r,

• N , we have

E[exp(δT γ-1 A,F )] < ∞. (4)
The proof is a slight variation on that of Theorem 3.6 in [START_REF] Kendall | From random lines to metric spaces[END_REF] article.

Proof of Theorem 3.1. Since A is connected and covered by

• N open balls B i of radius r, we may build a path between any two points of A by concatenating at most • N paths between two points of A belonging to the same ball B i of the cover.

We now recursively build a path between each pair of points x 0 and y 0 of B i , in a binary tree-like fashion. First, we specify

r n = rα -n .
We will choose corresponding speed limits v n later. Given such v n :

• We call A 0 the set of balls {B i } 1≤i≤ • N .
• To any ball B (n) ∈ A n , we associate an internal r n+1 -net of that ball. It may be viewed as a collection of balls B (n+1) of radius r n+1 . We then define A n+1 as the set of all these balls B (n+1) for all B (n) together. • We have thus built nested internal r n -nets.

• For any two balls B (n+1) i and B (n+1) j belonging to the internal r n+1 -net of the same ball B (n) in A n , we find a line of speed at least v n that hits both B (n+1) i and B (n+1) j , but not F . We will have to prove this is possible with high enough probability.

• For x n and y n , both belonging to B (n) ∈ A n , we may then find two points

x n+1 and y n+1 such that: x n and x n+1 (resp., y n and y n+1 ) belong to the same ball

B (n+1) i ∈ A n (resp., B (n+1) j
), and x n+1 and y n+1 both belong to the same line of speed at least v n .

• We may then build a path between x n and y n as a concatenation of three paths:

ξ xnyn = ξ xnx n+1 ξ x n+1 y n+1 ξ y n+1 yn .
The middle one is a segment. The other two are paths between points of the same ball in A n+1 .

As illustrated in Figure 1, we thus obtain a path between x 0 and y 0 that is made of exactly 2 n segments for each n, each at speed at least v n between two balls of the same internal r n+1 -net of a ball of radius r n . Moreover, since the points x 0 and y 0 are in A, all of the segments are between points of the Minkowski sum A ∞ n=1 B(0, r n ) = A r/(α-1) . This construction has built a path for each pair of points x 0 and y 0 in B i . Since segments between balls of the same internal r n+1 -net of a ball of radius r n are at most (2r n + 2r n+1 ) long, and are at speed at least v n , the

Π [A r/(α-1) ]\[F ] -diameter T A,F of A is bounded from above by T A,F ≤ • N ∞ n=1 2 n 2r n + 2r n+1 v n , (5)
on the event that this construction is possible. Now to control the probability of this event, we need:

• a bound on the number of pairs of balls in the same r n -net;

• a bound on the probability that the fastest line hitting two such balls but not F is slower than v n .

We obtain the first bound by using the formula r n = α -1 r n-1 . Indeed, each r n -net of a r n-1 -ball is then the same as a α -1 -net of a radius 1 ball. Since the balls B(s i , 1/(2α)) centered on the points of such a α -1 -net are disjoint, and all included in a ball of radius 1 + 1/(2α), a volume argument shows that there at most (2α + 1) d balls in each r n -net. So that there are at most We now consider these lines that hit both of two r n+1 -balls B(x, r n+1 ) and B(y, r n+1 ) in an internal r n+1 -net of a r n -ball, but that do not hit F . We have seen that they were in [A r/(α-1) ]. We may then use the hypothesis of the theorem on the solid angle of F .

We want a bound on

µ d ([B(x, r n+1 )] ∩ [B(y, r n+1 )] ∩ [F ] c ).
Now, as illustrated in Figure 2, let D(x, r n+1 /2) be the hyperdisk centered on x with radius r n+1 /2 and included in the hyperplane perpendicular to the vector xy. It is included in B(x, r n+1 ). Moreover, for any z ∈ D(x, r n+1 /2), the ball B(z + yx, r n+1 /2) is included in B(y, r n+1 ). Now we may write

µ d ([B(x, r n+1 )] ∩ [B(y, r n+1 )] ∩ [F ] c ) ≥ m d-1 (D(x, r n+1 /2)) × inf z∈D(x,r n+1 /2) µ (o) d-1 ([B(y -x, r n+1 /2)] ∩ [F -z] c ) ≥ m d-1 (D(x, r n+1 /2)) × (µ (o) d-1 ([B(y -x, r n+1 /2)]) -Ω). Now, y -x ≤ 2r n = 2αr n+1 . So that the lines in [B(y -x, r n+1 /2)] are in a cone of angle θ 0 such that sin(θ 0 ) ≤ (4α) -1 . So that by formula (1): µ (o) d-1 ([B(y -x, r n+1 /2)]) ≤ (4α) 1-d . (6) Since α < α max , we have (4α) 1-d -Ω > 0. Moreover, with ν d-1 the (d -1)-volume of a unit (d -1)-ball, we have m d-1 (D(x, r n+1 /2)) = ν d-1 r n+1 2 d-1 , µ d ([B(x, r n+1 )] ∩ [B(y, r n+1 )] ∩ [F ] c ) ≤ ν d-1 ((4α) 1-d -Ω) r n+1 2 d-1 = c α,Ω r d-1 n+1 ,
using the notation c α,Ω to summarize and emphasize that this bound depends on α and Ω, but not on n, r, or any other feature of A and F . We thus get

P[v max ([B(x, r n+1 )] ∩ [B(y, r n+1 )] ∩ [F ] c ) ≤ v n ] ≤ exp -c α,Ω r d-1 n+1 v γ-1 n .
Multiplying by the number of relevant pairs of ball, we then obtain that the construction is possible except on an event of probability at most

∞ n=0 • N (2α + 1) d(n+1) exp -c α,Ω r d-1 n+1 v γ-1 n . (7) Taking v n = r (d-1)/(γ-1) n+1 ((n + 1)c α,Ω ln(1/ε)) 1/(γ-1)
and replacing in bound ( 7), we see that this becomes less than n+1) ) = ε max , so that ε max does not depend on A or F except through α and • N . Replacing v n and r n with their value in the bound (5), we get

∞ n=0 • N (2α + 1) d(n+1) ε n+1 ≤ ε ε max , for ε < 1/(2 • N (2α + 1) d(
T A,F ≤ • N ∞ n=1 2 n+1 (1 + α) r n+1 v n = • N (1 + α)c 1/(γ-1) α,Ω ∞ n=2 (2α -(γ-d)/(γ-1) ) n n 1/(γ-1) × r (γ-d)/(γ-1) ln 1 ε 1/(γ-1)
,

where the first parentheses correspond to T 1 and T 1 is finite since α > α min .

We have thus proved formula (3) of the theorem. The moment (4) is simple integration:

E[exp(δT γ-1 A,F )] ≤ C + 1 ε max εmax 0 exp δ T r, • N ln 1 ε 1/(γ-1) γ-1 dε ≤ C + 1 ε max εmax 0 ε -δT 1/(γ-1) r, • N dε < ∞.
Here, we use δ < T

-1/(γ-1) r,

• N and C corresponds to the integral between ε max and 1, bounded by the value of T A,F for ε = ε max .

Remark 3.1. If no lines are forbidden, that is if F = ∅, then α can be taken as big as we wish, so that the lines used all hit as small a widening of A as we want.

We may slightly generalize the theorem: instead of using a forbidden area F , we could use different conditions for which lines to accept. The important property is that we must have enough relevant lines hitting pairs of balls in a r n+1 -net.

There are a few optimisations that could be used to gain slightly in the constants. For example, we have written the proof with one subnet inside each ball. If we had used a single r n -net of a correctly widened A, we would have only about n+1) pairs of ball, allowing a bigger ε max . The result stays essentially the same, however, as proven by the following proposition.

• N 2 d α d(
Proposition 3.2. For any two points x and y, their Π-distance T xy does not have a moment with higher exponent on the time T xy than in formula (4). That is, for any δ > 0, for any η > γ -1, we have

E[exp(δT η xy )] = ∞.
Proof. Say that |x -y| = r. A path from x to y has to go from x to the border of B(x, r). Hence, it must use lines hitting B(x, r) for a length at least r. So that T xy is controlled by the fastest line hitting B(x, r). Now,

P[v max (B(x, r)) ≤ v ε ] = exp(-c(r)v 1-γ ε ) = ε with v ε = 1 c(r) ln 1 ε 1/(1-γ)
, where c(r) depends only on r. So that on an event of probability at least ε, we have the bound -1) . Hence, for some positive constant c 3 depending on δ, η and r:

T xy ≥ r/v ε = c 2 (r)(ln(1/ε)) 1/(γ
E[exp(δT η xy )] ≥ 1 0 exp -c 3 ln 1 ε η/(γ-1) dε = ∞, since η/(γ -1) > 1.
4. Almost sure uniqueness of Π-geodesics. In this section, we prove that the network N satisfies the property 1 of a SIRSN, that is that between two specified points x and y in R d , there is almost surely only a unique route. Since routes are the Π-geodesics, this is equivalent to almost sure uniqueness of the geodesic g xy .

The case in dimension 2 has already been established in [START_REF] Kendall | From random lines to metric spaces[END_REF] paper. The following proof, on the other hand works in all dimensions more than 2, as stated in Theorem 4.8. Note that it does not work in dimension 2.

The strategy is the following:

• We introduce a concept of many directions, with the following property. If a Π-path has many directions near a point x, any finite Π-path supported by the same lines contains x. • We show that almost surely all geodesics have many directions near all the ends of their component segments, except for the two extremal points. This is the step where d ≥ 3 is needed. • We show that for specified x and y in R d , almost surely all geodesics from

x to y are supported exactly on the same lines. • So that almost surely all such geodesics contain the same segment ends, and this will prove they are the same.

The author thinks the proof is very technical for something that looks clear enough, but could not find an easier way. Maybe the need to work with tree-like paths in dimension at least three is the reason why there is no obvious argument. Hopefully, the concept of many directions can be useful elsewhere.

We first state two technical lemmas we need for the proofs in Section 4.1. We introduce the notion of "many directions" and give some cases where paths have many directions in Section 4.2, culminating in Lemma 4.6. We prove that geodesics must use the same lines in Section 4.3, and end the proof of uniqueness in Section 4.4. 4.1. Technical lemmas. The first lemma yields a control on the proportion of balls in a nested set that are hit by lines faster than a threshold appropriately scaling with their size.

Lemma 4.1. Let d ≥ 2. Let α > 1 be a scale factor. We write p = α 1-d < 1. Let B i = B(x i , r i ) for 1 ≤ i ≤ n be a set of nested balls with r i = r 0 /α i for some r 0 . For some v 0 , define

v i = v 0 p i/(γ-1) , V 0 = {(l, v) ∈ Π : v ≥ v 0 }, V i = {(l, v) ∈ Π : v i-1 ≥ v ≥ v i }.

J. KAHN

Define now H i as the number of balls B i+k smaller than B i that are hit by lines faster than v i , and I n as the number of balls B i that are hit by lines faster than v i-1 , that is,

H i = #{k > 0 : V i ∩ [B i+k ] = ∅}, I n = #{i ≤ n : ∃k > 0 : [B i ] ∩ V i-k = ∅} ≤ n-1 i=0 H i . Then λ = E[#{V i ∩ [B i ]}] = (1 -p)ω d-1 r d-1 0 /(2v γ-1 0
) independently of i ≥ 1. Then, for any δ > 0:

P[I n > δn] ≤ (1 + λδ) 1 + δ δ δ p δ n . ( 8
)
Precise but more cumbersome bounds are given in equations ( 11) and ( 12).

Proof. We have

E[#{V i ∩ [B i+k ]}] = E[#{V i ∩ [B i ]}]p k = λp k for all i ≥ 1 and k ≥ 0, E[#{V 0 ∩ [B k ]}] = λp k ∞ m=0 p m = 1 1 -p λp k for all k ≥ 0.
Thus,

P[H i = 0] ≤ 1 for all i ≥ 0, P[H i = k > 0] = P[V i ∩ [B i+k ] = ∅ and V i ∩ [B i+k+1 ] = ∅] = exp(-λp k+1 ) -exp(-λp k ) using [B i+1 ] ⊂ [B i ] ≤ 1 -exp(-λ(p k -p k+1 )) ≤ λp k (1 -p) for i ≥ 1.
Similarly,

P[H 0 = k > 0] = exp - λp k+1 1 -p -exp - λp k 1 -p ≤ λp k .
Hence, for all 0 < a < 1/p:

E[a H i ] ≤ 1 + ∞ k=1 λp k (1 -p)a k = 1 + λ(1 -p) ap 1 -ap for all i ≥ 1, E[a H 0 ] ≤ 1 + ∞ k=1 λp k a k (9) = 1 + λ ap 1 -ap , E[a In ] ≤ E[a n-1 i=0 H i ] ∨ 1 ≤ 1 + λ(1 -p) ap 1 -ap n 1 + ap(λ -1) 1 + ap(λ(1 -p) -1) (10) ≤ 1 + λ ap 1 -ap n .
We now use the Markov inequality:

P[I n > δn] ≤ E[a In ] a δn , (11)
and optimize upon a. Exact optimization requires solving a degree-two equation and yields a cumbersome solution, so we shall only use here the solution for the second approximation when λ = 1, that is a = δ/((1 + δ)p), so that ap/(1ap) = δ. Using (10), we get

P[I n > δn] ≤ 1 + λap/(1 -ap) 1 + λ(1 -p)ap/(1 -ap) 1 + λ(1 -p) ap 1 -ap n a -δn = 1 + λδ 1 + λ(1 -p)δ (1 + λ(1 -p)δ) 1 + δ δ δ p δ n (12) ≤ (1 + λδ) 1 + δ δ δ p δ n .
The second lemma gives a guarantee that except on exceedingly rare events; no significant fraction of uniformly randomly oriented lines are clumped together in a small number of directions. Lemma 4.2. Let (X , d, µ) be a metric space with a probability measure µ, and such that for all positive and small enough ε, for any point x in X , the volume of the ball is bounded in this way:

c 1 ε d-1 ≤ µ[B(x, ε)] ≤ c 2 ε d-1 , (13)
for c 1 and c 2 constants depending only on the space (X , d, µ).

Let α > β > δ > 0. Consider {s i } i∈I a n -η -net of X . Consider {x j } j≤αn αn random µ-i.i.d. points in X .

J. KAHN

Then there is no subset of βn points in {x j } that are all contained in at most δn balls of the net B(s i , n -η ), except on an event of sub-exponential probability, at most (Cn (β-δ)(η(d-1)-1) ) -n with C depending only on α, β and δ, c 1 and c 2 .

Moreover, the projective space

(P R d-1 , θ, µ (o)
d-1 ) satisfies the hypotheses for (X , d, µ). Here θ(l 1 , l 2 ) is the angle between two lines, and µ

(o)
d-1 is the natural probability measure on P R d-1 , defined in Section 2.

Proof. Since all the points in the n -η -net are in disjoint balls of radius n -η /2, there are at most c 3 n η(d-1) points in the net, for n big enough. Now, with c 4 , c 5 , c 6 depending on α, β and δ: P[There are βn points x j all contained in δn balls B(s i , n -η ) of the net] ≤ #{subsets of βn points} # {subsets of δn balls} × P[βn specific points are all contained in δn specific balls]

≤ αn βn c 3 n η(d-1) δn (δnc 2 n -η(d-1) ) βn
≤ 2 αn (c 4 n η(d-1)-1 ) δn (c 5 n 1-η(d-1) ) βn = (c 6 n (β-δ)(η(d-1)-1) ) -n .

In the projective space, where points are seen as lines through the origin in R d , a ball of radius θ 0 is exactly a cone of aperture θ 0 . We recall formula (1) and θ/2 ≤ sin(θ) ≤ θ for positive small θ, and we conclude that property (13) is indeed satisfied.

Many directions.

Having many directions near a point x intuitively means that the lines used near the point have so many different unit vectors that the only way to touch all those lines (a tour ) with a finite curve is by touching most of them near x. Definition 4.3. For a set of lines L = {l j } j∈J and a subset of the Euclidean space X ⊂ R d , a L-tour in X is a curve f in X such that for all j ∈ J , there is a t j such that f (t j ) ∈ l j . If f is rectifiable, the tour is said to be finite; else it is infinite.

Recalling the notation L ξ for the support of ξ: Definition 4.4. A finite Π-path ξ has many directions near a point x if, for all ε > 0, all L ξ -tours in R d \ B(x, ε) are infinite.

As a remark, this concept is only interesting in dimension at least three: in dimension two, a circle is usually a tour, and it is finite. Proposition 4.5. Let two finite Π-paths ξ and η. If ξ has many directions near a point x ∈ R d , and its support is included in that of η, that is,

L ξ ⊂ L η , then x ∈ η.
Proof. By Theorem 2.4, the finite Π-path η has finite Euclidean length. Moreover, L ξ ⊂ L η , so that η is a L ξ -tour in R d . Since ξ has many directions near x, there is no finite

L ξ -tour in R d \ B(x, ε), for any ε > 0. So that B(x, ε) ∩ η = ∅. Any finite Π-path is closed in R d , hence x ∈ η. Lemma 4.6. Let d ≥ 3.
Let l be a prescribed line independent of Π. Almost surely, for all x ∈ l, for any y / ∈ l, all geodesics g xy have many directions near x.

Proof. It is sufficient to show that the claim holds for all x ∈ l ∩B(0, R), for all R > 0. It is also sufficient to work with a fixed ε, and prove that for any y / ∈ l ε the ε-widening of l, for any geodesic g xy , all L gxy -tours on R d \ B(x, ε) have infinite length.

Let r n = r 0 /α n for r 0 = ε and an α > 1 big enough to be determined later. We consider one-dimensional internal rn 4 -nets N n of B(0, R) ∩ l. In particular, there are at most 4R rn + 1 points in N n . Now, for any point x n in N n , we may build a set of nested balls {B i } i≤n depending on x n , with the following properties:

• The ball B n is centred on x n .

• All balls B i = B(x i , r i ) are centred on a point x i in the net N i .

• The centres lie deep inside the previous ball, that is

x i ∈ B(x i-1 , r i-1 4 ).
This stems from the fact that N i-1 is an r i-1 4 -net. We also use the notation of Lemma 4.1 for v i and V i . We have to choose a good speed v 0 .

We then show that the nested balls have the following properties, with a T to be determined later, except on an event of probability o(r -1 n ): 1. There are at least 2n 5 balls B i that no line faster than v i-1 hits. 2. There are at least 5n 6 indices i such that the time diameter of B(x i ,

7r i 8 )\ B(x i , r i 2 ) on Π [B i ]\[B i+1
] is less than T α -i(γ-d)/(γ-1) . 3. There are at least 5n 6 balls B i that are hit by at most τ lines of speed between v i and v i-1 , for some fixed τ . Moreover, all those lines have independent, uniformly random directions.

We substitute δ = 3 5 in equation ( 8), and use p = α 1-d ≤ α -2 -since d ≥ 3-and λ = O(v 1-γ 0 ) = O(ln α). We obtain P For less than 2n 5 indices i, no line faster than v i-1 hits the ball

B i ≤ (c ln(α)α -6/5 ) n = o(α -n ).
Let us now consider a geodesic g xy from a point y outside B 0 to a point x inside B n . Since the balls are nested, they are all crossed by the geodesic. Even the sets A i = B(x i , 7r i 8 ) \ B(x i , r i 2 ) introduced in the proof of property 2 are all crossed, that is we must pass from the spherical boundary S(x i , 7r i 8 ) to the smaller boundary S(x i , r i 2 ). If the three properties are satisfied, then there are at least n 15 indices i for which the conditions are simultaneously satisfied. For such an i, by property 2 the geodesic will go from S(x i , 7r i 8 ) to S(x i , r i 2 ) in time at most T α -i(γ-d)/(γ-1) . Since the two boundaries are 3r i 8 apart, the geodesic must use a line with speed more than

3r i 8T α -i(γ-d)/(γ-1) = v 0 α -i(d-1)/(γ-1) = v i within A i . Now, A i ⊂ B i
and, by property 1, there is no line faster than v i-1 in B i . So that the geodesic must use a line in V i ∩ [B i ], whose cardinal is less than τ by property 3. Since the v i are disjoint, we have proved that the geodesic must use at least n 15 distinct lines among a set of size at most τ n of lines with uniformly random direction.

We may then apply Lemma 4.2.

We take 1 > η > 1/(d -1) and δ = 1/20. With probability 1 -O(n -cn ), all geodesics from a point outside B 0 to a point inside B n must use at least n/20 lines (depending on the geodesic), each with a direction in a different ball of a n -η -net of the projective space. Since there are at most a constant number c 1 of points in a n -η -net at distance less than 3n -η from a given point, we may choose n/(20c 1 ) of those lines, so that each pair of them makes an angle at least n -η .

Let us consider a fixed r 0 = ε. Since d(x i , x i-1 ) ≤ r i-1 4 and x ∈ B(x n , r n ), and since r i = εα -i = o(εn -η ) for i > c 2 ln n, we know that B i ⊂ B(x, εn -η /3) for i > c 2 ln n. Among our n/(20c 1 ) lines, at most τ hit each B i . Hence, up to removing c 3 ln n of our n/(20c 1 ) lines, all those lines hit the ball B(x, εn -η /3). So that, by elementary geometry illustrated in Figure 3, for any two lines l 1 and l 2 in our collection, no point of l 1 \ B(x, ε) is closer to a point of l 2 \ B(x, ε) than εn -η /4.

We have thus proved that for any geodesic g xy with x ∈ B n and y / ∈ B 0 , any L gxy -tour in R d \ B(x, ε) must contain c 4 n points that are c 5 n -η apart pairwise. Hence, it has length at least c 6 n 1-η , going to infinity with n. 3. We project on the vector space spanned by l1 and l2, with l1 parallel to the first coordinate and x as the origin. All points of l1 then have second coordinate at most n -η ε/3 in absolute value. On the other hand, let A be a point in l2 ∩ B(x, n -η ε/3) and B a point in l2 \ B(x, ε). Then the vector -→ AB has absolute second coordinate at least (ε -n -η ε/3) sin(n -η ) > 11 12 εn -η for large n, so that B has absolute second coordinate at least 7 12 εn -η .

All those properties were obtained except on a set of probability o(α -n ). Since the net N n has cardinal of order α n , this is true simultaneously for all sets of nested balls built on all the points x n in N n , except on an event of probability ε n going to zero.

Letting n go to infinity yields the lemma.

Geodesics use the same lines.

Theorem 4.7. For all x and y in R d , almost surely all geodesics g xy are supported on exactly the same lines.

Proof. A similar result is used during the proof of Theorem 4.4 in [START_REF] Kendall | From random lines to metric spaces[END_REF] article. The idea of the proof is to "slow down" the lines not used by a specific geodesic. Then all geodesics that use one of those lines become slower and are no longer geodesics. The set of slowed speeds has infinite measure relative to the initial speeds.

Almost surely, there exists a finite R such that all geodesics from x to y are included in B(0, R), by Theorem 2.6 of Kendall. Almost surely, for any R, there are countably many lines intersecting B(0, R), all with different speeds v 1 > v 2 > • • • (the information here is that there is a measurable order-preserving bijection from N to the inverse line speeds). We then write l i for the line with speed v i .

Let i ∈ N and let us fix all the other speeds v j for j = i. Let us suppose there is a speed v = i between v i-1 and v i+1 such that if v i = v = i , then there are at least two geodesics g i xy and g ¬i xy from x to y, one of which is supported by l i , and the other not. That is l i ⊏ g i xy and l i ⊏ g ¬i xy . Now, the time length of a path not supported by l i does not depend on v i . So that g ¬i xy is the fastest of these paths for all v i , with constant time. On the other hand, by decomposition (2), the time length of

g i xy is decreasing in v i . Hence, if v i > v =
i , all geodesics from x to y are supported by

l i . Conversely, if v i < v =
i , no path supported by l i is a geodesic from x to y. Indeed, such a path would be as fast as g ¬i xy at speed v i , hence faster at speed v = i . So that, when the other speeds are fixed, there is at most one value v = i of v i such that l i is in the support of some geodesic from x to y and not in the support of another such geodesic. Now, we may disintegrate the measures on the line speeds. For almost all fixed line speeds for all lines except l i , the measure µ i for v i has a density (namely, it is proportional to v -γ i 1 v i-1 ≤v i ≤v i+1 ). Hence, µ i ({v = i }) = 0. So that almost surely, either l i ⊏ g for all geodesics g from x to y, or l i ⊏ g for any such geodesic. This is true for all lines l i , completing the proof. 4.4. Almost sure uniqueness. We may now state this section's main result.

Theorem 4.8. In dimension d ≥ 2, for all x and y in R d , almost surely there is a unique geodesic g xy from x to y.

Proof. [START_REF] Kendall | From random lines to metric spaces[END_REF] proved the dimension 2 case in Theorem 4.4. We then assume from here on that d ≥ 3.

Consider any line l ∈ Π. We apply a Palm distribution argument: since Π is a Poisson process, Π \ {l} still has the same distribution as Π. So that almost surely, by Lemma 4.6, all geodesics on Π \ {l} with an endpoint z ∈ l have many directions near z. Since the lines are countable, this is true for all lines simultaneously.

The rigorous way of writing the former paragraph is through Slivnyak-Mecke formula [originally proved by [START_REF] Slivnyak | Some properties of stationary flows of homogeneous random events[END_REF]; see, e.g., [START_REF] Møller | Statistical Inference and Simulation for Spatial Point Processes[END_REF] book, Theorem 3.2, for a modern treatment]. A Poisson point process X with intensity µ takes value in the set of locally finite point configurations N lf . For any nonnegative measurable function h on R d × N lf , we have

E x∈X h(x, X \ {x}) = R d E[h(x, X)] dµ(x).
We apply the formula with the underlying point process for Π, so that x = (l, v) are marked lines. The function h is the indicator function

h((l, v), Π) = 1,
if ∃z ∈ l, y / ∈ l, g zy Π-geodesic such that g zy does not have many directions near z, 0, otherwise.

Lemma 4.6 then ensures that the expectation in the integrand in the right-hand side is uniformly zero, so that, almost surely, for all l ∈ Π, all geodesics on Π \ {l} with an endpoint z ∈ l have many directions near z.

Let g xy be a geodesic from x to y. Let {z i } be the set of endpoints of all the segments of the geodesic g xy except x and y. For any z i , since it is a segment endpoint (on line l), there is a u such that g uz i or g z i u is included in g xy , and such that l is not in the support of this sub-geodesic. Hence, this sub-geodesic is also a geodesic in Π \ {l}, and has many directions near z i . A fortiori, g xy has many directions near z i . Moreover, by Lemma 4.7 almost surely all other geodesics from x to y have the same support. Hence, all these geodesics include all the segment endpoints of all the geodesics from x to y. Now two geodesics from x to y must pass through the same points in the same order: indeed if g 2 xy = g 2 xa g 2 ab g 2 by and g 2 xy = g 2 xb g 2 ba g 2 ay , then g 1 xa g 2 ay or g 2 xb g 1 by would be shorter than both. So that all geodesics from x to y pass through their segment endpoints in the same order, so they are the same.

A byproduct of the proof is the following remark.

Corollary 4.9. Let d ≥ 3. Almost surely, for any point x not on a line of Π, that is x / ∈ S, all geodesics containing x have many directions near x.

Proof. We use the step in the former proof, that almost surely, for all l ∈ Π, all geodesics on Π \ {l} with an endpoint z ∈ l have many directions near z.

For any ε, since x / ∈ S, the geodesic to x will leave a line of Π at a point z ∈ B(x, ε/2). Now the restriction of the geodesic to g zx has many directions near z. Since B(z, ε/2) ⊂ B(x, ε), g has also many directions near x.

5. Geodesic length has finite expectation. This is property 3 of a SIRSN. T xy ≤ (n + 1) 1/(γ-1) T = T n . ( 16)

We now consider a collection of radii r l = 2 l r 0 for l between 0 and m, with r 0 and m to be chosen later, possibly depending on n, but independent of Π.

If L xy > r m , then L xy > r l for all l ∈ [0, m], so that constraint (15) must be satisfied for each r l . In particular, on the event (16), the following constraint is satisfied for all l ∈ [0, m]:

v max (B(x, r l )) ≥ r l /T n = v l . ( 17
)
We again drop the dependence on n in the notation of v l , and v l is independent of Π.

These constraints are simultaneously satisfied if and only if there is a strictly increasing sequence of (1 + k) integers 0 = l 0 , l 1 , . . . , l k between 0 and m such that

v l i+1 > v max (B(x, r l i )) ≥ v l i+1 -1 if i < k, v max (B(x, r l k )) ≥ v m .
We define the following events for all i ∈ [0, m], with the conventions l k+1 = m + 1 and r l -1 = 0:

A i = {v max (B(x, r l i )) ≥ v l i+1 -1 }, B i = {v l i+1 > v max (B(x, r l i )) ≥ v l i+1 -1 }, D i = {v max ([B(x, r l i )] \ [B(x, r l i-1 )]) ≥ v l i+1 -1 }.
Notice that the events do not depend only on i, but on the whole sequence of l i . Notation is easier this way. In particular, the former paragraph reads

P[L xy > r m |T xy ≤ T n ] ≤ m k=0 0=l 0 <•••<l k ≤m P[B 0 ∩ B 1 ∩ • • • ∩ B k-1 ∩ A k ]. ( 18
)
Let us consider the filtration generated by the lines intersecting B(x, r) for increasing r, that is F r = σ(Π [B(x,r)] ). Then A i , B i and D i are all F r l imeasurable, and D i is independent of F r l i-1 .

Moreover, the difference between A i and D i is only on the event that there is a line faster than v l i+1 -1 hitting B(x, r l i-1 ). Since l i+1 -1 ≥ l i , this never happens under B i-1 . So that A i ∩ B i-1 = D i ∩ B i-1 . From this, we deduce

P[B i |B 0 , . . . , B i-1 ] ≤ P[A i |B 0 , . . . , B i-1 ] since B i ⊂ A i = P[D i |B 0 , . . . , B i-1 ] since A i ∩ B i-1 = D i ∩ B i-1 (19) = P[D i ] since D i indep. of B j for j < i ≤ P[A i ] since D i ⊂ A i .
Recall that the number of lines faster than v hitting a ball of radius r is a Poisson variable with parameter cr d-1 v -(γ-1) , with c = µ d ([B(0, 1)]). We may then compute

P[A i ] = 1 -exp(-cr d-1 l i v -(γ-1) l i+1 -1 ) ≤ cr d-1 l i v -(γ-1) l i+1 -1 = cr d-1 l i 2 -(γ-1)(l i+1 -l i -1) v -(γ-1) l i = 2 -(γ-1)(l i+1 -l i -1) cr d-γ l i T γ-1 n (20) ≤ 2 -(γ-1)(l i+1 -l i -1) cr d-γ 0 T γ-1 n since r 0 ≤ r l i = 2 -(γ-1)(l i+1 -l i ) p(r 0 ) with p(r 0 ) = 2 γ-1 cr d-γ 0 T γ-1 n .
Recalling the convention l k+1 = m + 1, we obtain

P[B 0 ∩ B 1 ∩ • • • ∩ B k-1 ∩ A k ] ≤ P[B 0 ]P[B 1 |B 0 ] • • • P[A k |B 0 , B 1 , . . . , B k-1 ] ≤ k i=0 P[A i ] by (19) ≤ k i=0 2 -(γ-1)(l i+1 -l i ) p(r 0 ) by (20) = 2 -(γ-1)(m+1) p(r 0 ) k+1 .
Substituting into bound (18), we obtain

P[L xy > r m |T xy ≤ T n ] ≤ m k=0 0=l 0 <•••<l k ≤m 2 -(γ-1)(m+1) p(r 0 ) k+1 = m k=0 m k 2 -(m+1)(γ-1) p(r 0 ) k+1 (21) = 2 -(m+1)(γ-1) p(r 0 )(1 + p(r 0 )) m ≤ (2 -(γ-1) (1 + p(r 0 ))) m+1 . ( 22
)
Let κ < γ -1. We now choose our free parameters:

r 0 = 2 γ-1 cT γ-1 2 γ-1-κ -1 1/(γ-d) , so that 1 + p(r 0 ) = 2 γ-1-κ , m = ⌊(n + 1)/κ⌋.
Substituting into bound (22), we get n+1) .

P[L xy > r m |T xy ≤ T n ] ≤ 2 -(m+1)κ ≤ 2 -(
Since P[T xy > T n ] ≤ 2 -(n+1) , we have thus proved that with probability at least 1 -2 -n , the Euclidean length is bounded by

L xy ≤ r m = 2 (n+1)/κ (n + 1) 1/(γ-d) C,
where C is a positive constant depending on T and κ, but not on n.

Thus, L xy has a δ-moment for all δ < κ. Indeed,

E[L δ xy ] ≤ ∞ n=0 2 -n (2 (n+1)/κ (n + 1) 1/(γ-d) C) δ ≤ ∞ n=0 2 (δ/κ-1)n O(n δ/(γ-d) ) < ∞ if δ < κ.
Since κ is only constrained by κ < γ -1, we have a δ-moment for all δ < γ -1. Since γ > d ≥ 2, this completes the proof.

Remark 5.1. The main part of the proof is really just saying that the Euclidean diameter of a Π-ball has finite mean. Together with Theorem 3.1, this implies that the random metric space generated by the Π-length is almost surely homeomorphic to R d .

Notice that for κ close to γ -1, the main term in the sum ( 21) is the one for k = 0. In other words, it is easier to have one single extremely fast line close to x than to have many successively faster lines, if we want to be abnormally fast at each distance of x.

A first way to improve on the moments of L xy starts with noticing that if we use a line to go far away very fast, we need to use another line to come back, since a geodesic never crosses itself.

More precisely, the author conjectures that the structure yielding long geodesics with highest probability is the following: a line with speed at least 2r/T xy hits B(x, ε), another hits B(y, ε) and they hit a common ε-ball at distance r. Since the two first events have probability in r -(γ-1) and the other in r -(d-1) , we would conclude that E

[L 2γ+d-3 xy ] = ∞, but E[L δ xy ] < ∞ for all δ < 2γ + d -3.
6. Finite intensity of long-distance network. We now turn to property 4 of a SIRSN, that is their key property.

Intuitively, this means that the SIRSN contains "highways." If we look at all the geodesics simultaneously, truncating each geodesic by deleting balls around its endpoints, their total length in each compact set is finite: the geodesics largely re-use the same segments in each region. Contrast with the Euclidean case where the whole space is used.

In our context, we have to prove that the intensity p(1) of the following long-distance network F is finite: let {Ξ n , n ∈ N * } be a collection of Poisson processes on R d with intensity n times Lebesgue, all independent from Π, and coupled so that Ξ

n ⊂ Ξ n+1 . Write Ξ = n∈N * Ξ n . Then F = x,y∈Ξ (g xy \ (B(x, 1) ∪ B(y, 1))).
Notice that almost surely g xy is unique for all x and y, since the dense point set Ξ is countable.

By translational invariance, it is enough to prove that the intersection of F with a given ball has finite mean Hausdorff measure of dimension 1.

Indeed, if ℓ = m 1 (F ∩ B(x, r)), then E[ℓ] = ω d-1 r d-1 2
p(1). Notice that scale equivariance yields similar results if the long-distance network F is defined by removing balls of any fixed radius instead of radius 1.

The main argument relies on the pigeon-hole principle: a geodesic getting close to a prescribed point must use one of a very few fast lines close to that point, and must use them again to draw away. And by uniqueness of geodesics, two geodesics with two common points must agree between those points. Theorem 6.1. Let γ > d ≥ 2. With the above notation, let ℓ = m 1 (F ∩ B(0, 1 3 )) be the length of the long-distance network in B(0, 1 3 ). For ε < ε max , with probability at least 1ε, this length is less than C(ln(C 1 /ε)) 2 , for constants ε max , C and C 1 depending only on γ and d. Consequently, there is a finite moment of exponential form: for any δ < √ C,

E[exp(δ √ ℓ)] < ∞. ( 23
)
In particular, ℓ has finite mean.

Proof. Since Ξ is countable, by Theorem 4.8, almost surely all geodesics between its points are unique. In the proof, we only consider such geodesics and sub-geodesics, so that we assume uniqueness.

Consider the balls B(0, 1 3 ) and B(0, 2 3 ). We call their set difference B(0, 2 3 )\ B(0, 1 3 ) the border. Now if a point x ∈ B(0, 2 3 ), then B(0, 1 3 ) ⊂ B(x, 1). Hence, geodesics with an endpoint in B(0, 2 3 ) make no contribution to ℓ. We have ℓ ≤ m 1

x,y∈Ξ\B(0,2/3) g xy ∩ B 0, 1 3 .

Hence, geodesics g xy making contributions to ℓ are structured in the following way, illustrated in Figure 4.

• They hit B(0, 2 3 ) for the first time at point s on the corresponding sphere. • Then they hit B(0, 1 3 ) for the first time at point u on the corresponding sphere.

• Then they hit B(0, 1 3 ) for the last time at point v on the corresponding sphere.

• Then they hit B(0, 2 3 ) for the last time at point z on the corresponding sphere.

In particular, the contribution to ℓ is included in the sub-geodesic g uv . Now, uniformly on x and y, the time T sz between s and z is bounded by the time diameter of B(0, 2 3 ). So that, by Theorem 3.1, with probability 1ε/2, we have

T sz ≤ T ε (24) = T 2/3,1 ln 2 ε • ε max 1/(γ-1)
.

We call fast lines the lines faster than v ε = 1/(6T ε ). Conversely, lines slower than v ε are slow lines. We write V ε = S vε ∩ B(0, 2 3 ) for the intersection of all those fast lines with the ball B(0, 2 3 ). The number of fast lines hitting B(0, 2 3 ) is a Poisson variable with parameter λ

ε = ω d-1 (2/3) d-1 2v γ-1 ε = C 2 ln(C 1 /ε) for explicit constants C 1 and C 2 , with C 1 = 2/ε max ≥ 2.
We recall that the moment generating function of such a Poisson variable X is E[e tX ] = exp(λ ε (e t -1)), and use Chernoff bound to get

P[X ≥ C 3 λ ε ] ≤ e λε(e t -1) e -tC 3 λε = exp(λ ε (C 3 -1 -C 3 ln C 3 )) with e t = C 3 = C 1 ε C 2 (C 3 -1-C 3 ln C 3 ) ≤ ε 2 , with C 3 chosen big enough to have C 2 (C 3 -1 -C 3 ln C 3 ) ≤ -1.
Hence, with probability at least 1 -ε 2 , there are at most C 3 λ ε fast lines hitting B(0, 2 3 ). With probability at least 1ε both this event and T sz ≤ T ε are true. We assume both from now on.

Since T sz ≤ T ε , the intersection of g sz with slow lines has length at most v ε /T ε = 1 6 . So that, since s and u (resp., v and z) are at least 1 3 apart, the geodesic must have fast segments for length at least 1 6 between s and u (resp., v and z), that is,

m 1 (V ε ∩ g su ) ≥ 1 6 , m 1 (V ε ∩ g vz ) ≥ 1 6 . Now m 1 (V ε ) ≤ #{fast lines} • Diam B 0, 2 3 ≤ 4C 3 λ ε 3 = C 4 ln C 1 ε , so that m 1 ⊗ m 1 (V ε ⊗ V ε ) m 1 ⊗ m 1 (g su ∩ V ε ⊗ g vz ∩ V ε ) ≤ C 5 ln C 1 ε 2 .
Hence, by the pigeon-hole property as illustrated in Figure 5, we may find a maximal family {g i } of at most (C 5 (ln C 1 ε ) 2 + 1) geodesics such that: • g i is a geodesic between x i and y i in Ξ \ B(0, 2 3 ), passing through s i , u i , v i and z i defined as for s, u, v and z above.

• Any geodesic g xy contributing to ℓ crosses one of the g i when first and last crossing the border, that is, there are points t and w such that t ∈ g s i u i ∩ g su and w ∈ g v i z i ∩ g vz . By uniqueness of geodesics, g i and g xy coincide on g tw . In particular, they coincide on g uv . Hence, the intersection F ∩ B(0, 1 3 ) is included in the finite number of geodesics g u i v i . We may then conclude by separating contributions from fast and slow lines:

ℓ ≤ i m 1 (g u i v i ) ≤ m 1 (V ε ) + i m 1 (g u i v i ∩ (Π \ V ε )) ≤ C 4 ln C 1 ε + C 5 ln C 1 ε 2 + 1 • 1 6 ≤ C ln C 1 ε 2 .
Theorem 6.2. The network N made of the time geodesics is a SIRSN.

Proof. Property 1 of a SIRSN is a consequence of almost sure uniqueness of geodesics between two points, that is Theorem 4 in dimension at least 3, and Theorem 4.4. in [START_REF] Kendall | From random lines to metric spaces[END_REF] article in dimension 2.

Property 2 of a SIRSN is because the underlying Poisson line process is invariant by translation and rotation. As for change of scale, the underlying Poisson line process is invariant by a transformation where scale is multiplied by α and speed by α (d-1)/(γ-1) . Hence, all paths have their time length multiplied by the same α (γ-d)/(γ-1) , so that the geodesics are the same and N is invariant.

Property 3 of a SIRSN is Theorem 5.1. Property 4 of a SIRSN is Theorem 6.1.

Conclusion.

We have established that the improper Poisson line process with adequate speed limits yield a SIRSN.

Along the way, a few questions have been raised. Is there an easier, more natural way to prove uniqueness of geodesics? What are the tightest moments of the Euclidean length of a geodesic? When can we generalize this construction using geodesics from a random geodesic metric space?

On a more general note, we may wonder which property of our network N translate to general SIRSNs, or to SIRSNs made of geodesics of a metric space. For example, it should be easy to show that not all SIRSNs have the equivalent of Lemma 4.6 or Corollary 4.9: it is certainly not true for the binary hierarchy model by Aldous.

We might also raise a few typical questions in stochastic geometry. Is there only one geodesic connecting a prescribed point x to infinity, like in dimension two? In many models, infinite geodesics have an asymptotic direction.

For SIRSNs, this property looks unlikely, and characterizing the random walk of the angle as a function of the Π-distance to x looks worthwhile. What is the law of a typical cell in the tessellation generated by the network connecting the points of Ξ 1 , an intensity 1 Poisson point process?

Finally, another somewhat tangential direction of research would be to study more closely the properties of the random metric space. For example, being a SIRSN entails coalescence of geodesics, a very hyperbolic-like property. We may also draw comparisons with a well-known random metric space such as the Brownian map [see, e.g., Le [START_REF] Gall | Random geometry on the sphere[END_REF]].

The Brownian map is a random metric space homeomorphic to the sphere S 2 . It has Hausdorff dimension 4. All its geodesics minus their endpoints is of Hausdorff dimension 1. The cut-locus of its geodesics starting from a given point has Hausdorff dimension 2, and the topology of an open continuous tree.

On the other hand, we have shown that our metric space is homeomorphic to R d . It should be easy, by scaling arguments, to show that its Hausdorff dimension is (dγd)/(γd), which is bigger than d. In particular, with d = 2 and γ = 3, we have the same dimensions as the Brownian map. If any geodesic can be appropriately approximated by geodesics between points of Poisson point processes, it should also be easy to show that the geodesics minus their endpoints is of dimension 1. However, the cut-locus might have a very different behaviour.

Fig

  Fig.1. We cover each ball Bi with a r1-net, and connect each pair of balls of the net with a segment, be it a point (a). We then do the same at each scale, for rn+1-nets of the balls of the rn-nets (b). Each point belongs to a ball of the r1-net, so we build a path between two points starting from the segment connecting their balls (c). We then (d) and (e) connect the points to the segment endpoints with the segment connecting their balls in their respective r2-nets. At stage n, the path (f) is made of 2 n segments at each scale n.

•N

  (2α + 1) dn balls in A n , and at most• N (2α + 1) d(n+1) pairs of balls in the same r n -net.

Fig. 2 .

 2 Fig.2. Lines that hit both balls B(x, rn+1) and B(y, rn+1) but not F (not necessarily connected) contain lines through z ∈ D(x, rn+1/2) and B(z + x -y, rn+1/2). These are included in the cone of angle θ0 through z.

Fig.

  Fig.3. We project on the vector space spanned by l1 and l2, with l1 parallel to the first coordinate and x as the origin. All points of l1 then have second coordinate at most n -η ε/3 in absolute value. On the other hand, let A be a point in l2 ∩ B(x, n -η ε/3) and B a point in l2 \ B(x, ε). Then the vector -→ AB has absolute second coordinate at least (ε -n -η ε/3) sin(n -η ) > 11 12 εn -η for large n, so that B has absolute second coordinate at least 7 12 εn -η .

  Theorem 5.1. Let x, y ∈ R d . Then the Euclidean length of the Π-geodesic between x and y has finite expectation E[L xy ] < ∞. Proof. For any r, any Π-path containing x whose Euclidean length is more than r has to intersect B(x, r) on a length at least r. Hence, it must spend time at least r/v max (B(x, r)) in that ball. If the geodesic g xy has Euclidean length L xy and time length T xy , we thus obtain the constraint v max (B(x, r)) ≥ r/T xy for all r ≤ L xy . (15) By equation (3) of Theorem 3.1, there is a T such that with probability at least 1 -2 -(n+1)

Fig. 4 .

 4 Fig. 4. The geodesic from x to y hits B(0, 2 3 ) for the first time at s and the last time at z. It hits B(0, 1 3 ) for the first time at u and the last time at v.

Fig. 5 .

 5 Fig. 5. Close parallel curves in the figure agree. They are separated to make the figure more readable. The three thin black lines are the fast lines. The light dashed lines and black dotted curves are a family of geodesics {g i }. The solid curve connecting x and y is the geodesic gxy. The geodesic gxy has a common point t with the black dotted geodesic on a fast (black) line when first crossing the border, and another w when last crossing the border. Hence, they agree between u and v. Any other geodesic contributing to ℓ would meet one of the geodesics in the family {g i } in the same way.

J. KAHN

Acknowledgements. I would like to thank Wilfrid Kendall for introducing us to the problem during a talk, and helpful discussions since then. Remarks from a referee have greatly improved the presentation of the paper.

J. KAHN

The T will yield the v 0 we need to continue the proof, that is,

We deal with these properties in reverse order, and first consider property 3.

Since the sets of lines V i are disjoint, the events that more than τ lines in V i hit B i are mutually independent (in i), as are their directions. Moreover, since the B i are balls, the direction of the lines of the isotropic Poisson line process that hit it are uniformly random.

So that the number X n of such events is a binomial random variable B(n, q) where q is the probability of a single event. The Chernoff bound for a binomial is, for δ > q,

Here, it suffices to take δ = 1 6 . For α big enough, if, for example, we take q ≤ α -7 , the above bound is negligible with respect to α -n . Now the probability q of a single event is the probability that a Poisson random variable with parameter not depending on i is bigger than τ . We then just choose τ so that q ≤ α -7 . Now for property 2.

Since the sets of lines [B i ] \ [B i+1 ] are disjoint, each of the events that the time diameter of B(x i ,

] is less than T α -i(γ-d)/(γ-1) are independent. Arguing as for property 3, we merely have to choose T such that the probability q of a single event is less than α -7 . Now, by scaling, the sets

2 ) may all be covered by the same number • N of balls with radius r i 8 , and centres in A i . Moreover, A i is connected. Now the r i 8 -widening of A i is included in B i , and since x i+1 ∈ B(x i , r i 4 ), we know that x i+1 is at distance at least 1 8 of this widening. So that the maximum solid angle of B i+1 viewed from any point of the widening is a decreasing function of α, hitting zero when α goes to infinity. Thus, for α big enough, we may apply Lemma 3.1 with Ω < Ω max . Replacing ε in bound (3) with 1/(ε max α -7 ) to ensure q ≤ α -7 , we find that property 2 is ensured if we choose

(ln(α 7 /ε max )) 1/(γ-1)

= O(ln 1/(γ-1) α).

This choice of T ensures that v 0 = O(ln -1/(γ-1) α).

As for property 1, we apply Lemma 4.1.


D Bonamy

S Bernard-Bernardet

F Daviaud

L Laurent

Microdisplacements induced by a local perturbation inside a granular packing

Keywords: number͑s͒: 45.70.Qj, 45.70.Cc, 81.05.Rm

The microdisplacements generated by a small localized overload at the free surface are visualized experimentally inside a packing of steel beads. For a triangular packing, beads rearrangements remain confined in two inverted triangles on both sides of the applied overload. This pattern disappears for stronger disorder. A simple model allows us to account for these observations and to relate them to the stress function response measured via photoelastic visualizations. This provides a different tool to probe the mechanical Green's function in weakly confined packings of rigid grains the description of which is the most challenged.

I. INTRODUCTION

Force distribution in granular packing is rather counterintuitive. For instance, the pressure profile measured at the basis of a conical sand pile can present a ''dip'' as well as a maximum below the apex of the heap depending on the pile construction history ͓1͔. These results entailed intensive theoretical research, leading to several models differing significantly. A broad group of models, referred to as elasto-plastic models, considers granular media as elastic media as long as for any point the Mohr-Coulomb criterion is not reached ͓2͔. In the elastic domain, the components of the stress tensor obey the elliptic partial differential equation ͑PDE͒. Another class of models, called oriented stress linearity ͑OSL͒ models, questions the existence of an elastic regime and proposes rather to put the force chain's role forward, which leads to hyperbolic PDE ͓3͔. Finally, the last class of models, referred to as q models, assimilates the packing to a regular lattice where the force-considered only through its vertical component-is transmitted randomly from a given grain to its two neighbors beneath, which lead to parabolic PDE ͓4͔. By leading to PDE of different nature, these three approaches are mutually exclusive.

How to test the competing models? The best way would be to measure the stress response function under a layer of grains of constant thickness H perturbed by the addition of an infinitesimal localized overload at the free surface; OSL models foresee that the pressure profile exhibits two peaks whose width increases as ͱH, separated by a distance in- creasing linearly with H. For the same configuration, both elastic model and q model predict the existence of a single peak whose width increases linearly and as square root of H, respectively. Several experiments have been performed with this aim in view using either synchrone detection ͓5͔ or photoelastic visualization ͓6,7͔, but they have not allowed to clarify definitively the question. Depending on the investigated system, either the q model ͓6͔, the elastic model ͓5,7͔, or the OSL model ͓7͔ predictions are recovered. The stage of disorder in the packing appears as a crucial parameter ͓7,8͔, but its influence remains far from being understood.

Neither experiment ͓5,6͔ allows one to control the disorder in the packing. Moreover, the photoelastic experiments ͓6,7͔ present the drawback of considering soft grains, with a Young modulus 10 000 times smaller than the one of steel or glass grains, while the greater sources of disagreements between the different models concern precisely the hard grains packing. In this paper, we investigate the response of steel beads packings to a localized overload at the free surface by looking at the microdisplacements rather than the stress variations within packings of different disorder stages. We show that the spatial ordering of the particle is a key parameter for the distribution of microdisplacements within the packing. Ordered packings exhibit preferential propagation direction while disordered packings do not, as what was previously observed on photoelastic visualizations ͓7͔. The microdisplacements frames are claimed to be mainly related to the orientation map of the local forces induced by the overload. A simple model is developed to test this relationship.

II. EXPERIMENTAL SETUP

The experimental setup is illustrated in Fig. 1. It consists of a fixed drum of diameter D 0 ϭ45 cm and variable thickness , half-filled with steel beads of diameter dϭ3 Ϯ0.03 mm, of Young modulus Y ϭ200 GPa and of mass mϭ0.11 g. For such geometry, the stresses ͑resp. displace-ments͒ can be assumed to vanish at the free surface ͑resp. at the drum lower boundaries͒. Three kinds of packings are investigated: ͑a͒ a two dimensional ͑2D͒ ordered packing obtained by setting ϭ3.05 mm and by placing an item with a half hexagon shape in the lower half part of the drum; the packing is then monocrystalline with beads forming a triangular lattice ͓Fig. 2͑a͔͒; ͑b͒ a 2D disordered packing by retrieving the half hexagon from the previous packing and by adding randomly 100 cylinders with diameter of 5 mm. The crystalline grains size is then about 50 beads diameters ͓Fig. 2͑b͔͒; ͑c͒ a quasi-2D disordered packing by setting ϭ7 mm. Only beads in contact with the transparent side wall of the drum can be actually seen. This 2D cut of a 3D packing is then completely disordered ͓Fig. 2͑c͔͒. The localized overload consists of a rod with a plate on which different weights can be placed at its upper tip and a pad which allows one to spread the overload on five to seven beads depending on the packing geometry at its lower tip ͑Fig. 1͒. Beads are lighted via a continuous halogen lamp. The rod is put carefully at the center of the free surface of the packing. A first sequence of 100 frames of the constrained packing is recorded via a fast camera at a sampling rate of 250 Hz. The rod is then retrieved very slowly. A second sequence of 100 frames of the free packing is recorded. The frame resolution is 480ϫ420 pixels, one pixel corresponding to 0.224 mm. The two sequences are first averaged. This process allows one to greatly reduce the noise caused by lighting fluctuations or drum and camera intrinsic vibrations. The two resulting frames are subtracted, and then binarized. The beads that have moved when the tube was retrieved are then distinguished. Application of this frame processing to the motion of a bead translated with a micrometric translator shows that microdisplacements superior to 20 m are spotted unambiguously. This should be compared to the size of the cage where each bead is confined. In the packing of maximal volume fraction, the packing ͑a͒, this size is given by the scattering in the diameter and sphericity of beads, which is around 30 m. The microdisplacements entailed by the overload can then be localized but cannot be quantified. Each experiment is performed ten times by laying the rod to different places. All experimental results presented below are averaged over these ten realizations.

III. MICRODISPLACEMENTS DISTRIBUTION IN THE PACKING

Typical frames of the beads micromoved by the overload are represented in Figs. 2͑d-f͒ for packing ͑a͒, ͑b͒, and ͑c͒, respectively. For all these packings, the number of displaced beads increases with the overload. In the ordered packing ͓Fig. 2͑d͔͒, moving beads stand preferentially on either side of the overload: a dark triangle, i.e., an area without any microrearrangement, can be observed at the vertical of this one. This suggests this in that kind of packing, information of the overload existence propagates more likely along preferential directions. Beads close to these directions feel in a stronger way the overload presence than the ones-rather closer-just below it. In the disordered packing ͓Figs. 2͑e,f͔͒, the triangular pattern disappears and the area sensitive to the perturbation takes the shape of a half disk. Beads are all the more liable to rearrangements as they are close to the perturbation source, without any noticeable anisotropy.

These observations can be compared to the photoelastic visualizations of Geng et al. ͓7͔ exhibiting a propagative component in the stress response to a point force for ordered packings whereas such stress response is more like the one of an isotropic elastic material for disordered packings. Beads microdisplacements are then conjectured to be driven by the following scenario: The overload induces an additional force component to each bead. When this last one is oriented toward the boundaries of the drum, the bead motion is only due to contact deformation ͑a few nanometers for grains of Young Modulus Y ϭ200 GPa). Such displacements are too small to be detected by our visualization method; but when the force component is oriented toward the free surface and sufficient to lift the beads layer above it, displacements with an order of magnitude of the cage size, i.e., 30 m, are expected and can thus be detected ͓10͔.

IV. TOY MODEL

Now we propose to test this interpretation. Several models have been proposed to explain force distribution in a FIG. 2. Distribution of the displacements in different packing with a small overload put at the free surface. ͑a͒, ͑b͒, and ͑c͒ are the raw frames of a 1D triangular packing, a 2D disordered packing, and a quasi-2D disordered packing, respectively ͑see text for de-tails͒. The insets present the corresponding 2D FFT transforms. The six peaks observed in ͑a͒ are the signature of the triangular packing. These peaks become blurred in the disorder 2D packing ͑b͒ and disappear in the quasi-2D packing ͑c͒. The figures ͑d͒, ͑e͒, and ͑f͒ present the displacements distribution in packings ͑a͒, ͑b͒, and ͑c͒ when an overload of mass M ϭ1120 ͑adimensioned by the bead mass͒ is added at the center of the free surface. granular packing ͓4,8,9͔, but, to our knowledge, none of them allows one to account for beads microdisplacements. In this context, a minimal toy model has been developed. Its aim is not to reproduce quantitatively the observations, but rather to account qualitatively for the role of the disordercontrolled through a small set of parameters, ideally a single one-on both stress and displacements response functions. This model is described precisely in Ref. ͓11͔ and summarized below.

Grains are placed on a triangular lattice. Each grain is located through its coordinates (X,Z) ͑Fig. 3͒. An overload is then applied on the grain at the surface at the center of the lattice. The generated additional forces are characterized by three quantities: the position Pϭ(X,Z) of the bead to which it is applied, the norm w of the additional force and the angle ⌽ between this force, and the vertical ͑oriented from top to bottom͒. A force Fϭ1 is first applied to the bead O at the surface at the center of the lattice. This bead acquires an overload w(tϭ0) defined by Pϭ(0,0), wϭF, and ⌽ϭ0. This overload is transmitted to two of the bead neighbors at the time tϭ1, which then transmit their overload to two of their neighbors and so on. To be more precise, at a given time t, the overload w(t)ϭ( P,w,⌽) applied to the bead P ϭ(X,Z) and created to the last time step is transmitted to the beads P 1 and P 2 associated to the contact orientation 1 and 2 , the closest of ⌽ ͓Fig. 3͑a͔͒. Their locations (X 1 ,Z 1 ) and (X 2 ,Z 2 ) are thus given by X i ϭXϩsin i , Z i ϭZϪcos i for iϭ͕1,2͖ where both X and Z are adimensioned by the bead diameter. In a triangular packing of identical perfectly smooth beads, the two transmitted overload orientation ⌽ 1 and ⌽ 2 would coincide exactly with 1 and 2 . To encode the disorder of the real packing as well as the existence of a friction component of the contact force and the beads polydispersity, two random angles ␣ 1 and ␣ 2 are added; ⌽ i ϭ i ϩ␣ i for iϭ͕1,2͖ ͓Fig. 3͑b͔͒. These angles ␣ i are uniformly distributed between ͓Ϫ⌰,⌰͔ where the parameter ⌰ quantifies the disorder stage in the simulated packing. Finally, the norms w 1 and w 2 of the transmitted loads are given by the force balance of the bead P at the time t; we i⌽ ϭw 1 e i⌽ 1 ϩw 2 e i⌽ 2 .

The force network is then built in a hierarchical manner. Each overload w(t) has one parent and two children. The half-width L and the height H of the packing are set to L ϭ100 and Hϭ100, respectively, in bead size units. When a load reaches the boundary or the free surface, it does not propagate anymore. Boundaries are thus perfect absorbing boundaries. The number of transmitted load grows very rapidly as the network is built. A cutoff is then introduced. When the norm of a load becomes smaller than a threshold w c ϭ10 Ϫ4 , this does not propagate anymore. The simulation stops when all the loads are smaller than w c .

During the simulation, a bead can get a load w t e i⌽ t at a given time t whereas it has already acquired a load w t 1 e i⌽ t 1 at a time t 1 anterior to t ͓12͔. In this case, the bead will transmit only the load w t e i⌽ t since the component w t 1 e i⌽ t 1 has already been transmitted in the past ͓13͔. At the end of the simulation, the final load of this bead will be the sum of all the loads w t e i⌽ t it has got during the simulation.

After the simulation completion, one gets for each bead Pϭ(X,Z) the overload given by (w,). A new quantity ␦ associated to each bead is then introduced with account for the bead displacement, ␦ϭ1 when the bead has moved and ␦ϭ0 in the other case. The only free surface is for zϭ0

where beads can move in the semi-infinite plane zϽ0. A bead located at Pϭ(X,Z) will thus move if the z projection of its total applied force w total ϭw 0 ϩw is negative (w 0 corresponds to the force component applied to this bead in the absence of the surcharge͒. Assuming that H is large compared to the width of the zone sensitive to the overload, w 0 is given on average by the hydrostatic pressure on this point: w 0 ϭ(1/r)(2/ͱ3)Z where r denotes the ratio between the initial force Fϭ1 and the bead mass. The ␦ variation is then given by ␦ϭ1, when w sin(Ϫ/2)у(1/r)(2/ͱ3)Z and ␦ ϭ0 otherwise.

A numerical experiment is thus developed according to two steps: ͑1͒ One simulates the distribution and the orientation of the overload entailed by a force Fϭ1 applied to the bead P 0 (0,0). ͑2͒ The displacements entailed by these overloads are then simulated. For a given set of parameters (⌰,r) both overload and displacement field are averaged over 50 different numerical experiments.

Figures 4͑a,b͒ present the simulated overload fields obtained for two values of ⌰. For triangular packings, disorder is mainly dominated by the friction mobilization at the grain/ grain contact. The angle ⌰ is then set to ⌰ϭ5°, which corresponds to a bead/bead friction coefficient of b ϭ0.1. In the quasi-2D packing, disorder is maximal and ⌰ is set to ⌰ϭ30°. The model captures qualitatively the behaviors observed experimentally by Geng et al. ͓7͔. In a triangular packing, the perturbation propagates along two preferential contact chains which make an angle of 60°between them. In a disordered packing, these two directions exist for low depth Z, but they become blurred when Z is increased.

Figures 4͑c,d͒ present the associated displacement field for the ordered packing (⌰ϭ5°) and the disordered packing (⌰ϭ30°), respectively. The parameter r has been set to r ϭ1000 to be compatible with our experimental measures. In the triangular packing, the triangular pattern is reproduced FIG. 3. Propagation rule of the overload from a given bead to two of its neighbors. ͑a͒ The orientation of the load w determines the two neighbors P 1 and P 2 which will support this charge. ͑b͒ The orientations 1 and 2 of the two children charges resulting from the transmission coincide with the two contact orientations 1 and 2 at which two random numbers ␣ and ␤ have been added, respectively.

BRIEF REPORTS

PHYSICAL REVIEW E 68, 042301 ͑2003͒

042301-3 qualitatively with displacements localized from one part to the other of the two referential directions of force propagation. When the disorder is increased, this pattern disappears.

The simulation accounts also for the fact that the extension of the area where beads can move decreases with increasing disorder. The influence of the perturbation intensity on the extension of the moving area has been also investigated, with r set to 500, 1000, and 2000 for ⌰ϭ5°͓14͔. These values are compatible with the ratio between the overload mass M and the beads mass investigated experimentally. In the experiment, this area extends at depth Z of 10d, 30d, and 35d for M ϭ620m, M ϭ1120m, and M ϭ2180m, respectively, while in the simulation, this area extends up to Zϭ7d, 10d, and 14d for rϭ500, 1000, and 2000. The correct orders of magnitude are recovered. Let us note, however that the lateral extension of the sensitive zone is much more important in the simulation than in the experiment.

V. CONCLUSION

In summary, the static of hard spheres packings has been investigated experimentally through the localization of the microdisplacements induced by a small overload added at the free surface. The spatial ordering of the grains appears as a key parameter, as previously reported by Geng et al. ͓7͔ concerning the stress function response in soft photoelastic grains packings. In the ordered packing, information of the surface localized overload propagates along preferential directions while the function response in disordered packings is isotropic. The microdisplacements are conjectured to be related to the orientations of the overloads induced by the perturbation, what has been tested through a toy model. Such methods allow one to probe extremely hard spheres packings contrary to photoelastic measurements and may provide a new test for the latest models ͓8͔ of static stresses distribution in granular packing. Another natural extension of this work is to investigate the microdisplacements generated by a small overload added on an inclined free surface. In particular, it would be very interesting to measure the change of the size of the area containing the moving beads when the inclination angle approaches the angle of repose. Work in this direction is underway.

FIG. 1 .

 1 FIG.1. Sketch of the experimental setup.

ACKNOWLEDGMENTS

We thank O. Dauchot for fruitful discussions, and C. Gasquet, V. Padilla, and P. Meininger for technical assistance.