Jean-Christophe Mourrat

Daniel Valesin

PHASE TRANSITION OF THE CONTACT PROCESS ON RANDOM REGULAR GRAPHS

Keywords: 82C22; 05C80 interacting particle system, contact process, random graph, configuration model

We consider the contact process with infection rate λ on a random (d + 1)-regular graph with n vertices, Gn. We study the extinction time τ Gn (that is, the random amount of time until the infection disappears) as n is taken to infinity. We establish a phase transition depending on whether λ is smaller or larger than λ 1 (T d ), the lower critical value for the contact process on the infinite, (d + 1)-regular tree: if λ < λ 1 (T d ), τ Gn grows logarithmically with n, while if λ > λ 1 (T d ), it grows exponentially with n. This result differs from the situation where, instead of Gn, the contact process is considered on the d-ary tree of finite height, since in this case, the transition is known to happen instead at the upper critical value for the contact process on T d .

Introduction

Let G = (V, E) be a locally finite and connected graph. The contact process on G with parameter λ > 0 is the continuous-time Markov process (ξ t ) t 0 on the space of subsets of V whose transitions are given by:

(1.1) for every x ∈ ξ t , ξ t → ξ t \ {x} with rate 1, for every x / ∈ ξ t , ξ t → ξ t ∪ {x} with rate λ |{y ∈ ξ t : {x, y} ∈ E}|, where for a set A, we write |A| to denote its cardinality. We identify subsets of V with elements of {0, 1} V (through the indicator function). The contact process is usually thought of as a model for the spread of an infection in a population. Vertices of the graph are interpreted as individuals, and states 0 and 1 indicate that an individual is healthy or infected, respectively. An infected site recovers with rate 1 and infects a neighbouring site with rate λ times the number of connecting edges (we will allow for multiple edges connecting a given pair of vertices). We refer the reader to [START_REF] Liggett | Stochastic interacting systems: contact, voter and exclusion processes[END_REF] for a thorough introduction to the contact process, including the facts that we state without proof in this introduction.

We denote by (ξ A t ) t 0 the contact process on G with initial configuration ξ A 0 ≡ A. If A = {x}, we write (ξ x t ) instead of (ξ {x} t

). We write P G,λ for a probability measure under which the contact process with parameter λ on G is defined.

The extinction time τ A G for the contact process on G = (V, E) with initial configuration A ⊆ V is defined by τ A G = inf{t : ξ A t = ∅}. Since the dynamics only allows for new infections to appear by transmission, the configuration ∅ is absorbing, so we have ξ A t = ∅ for any t τ A G . We write τ G instead of τ G G and τ x G instead of τ {x} G . When the contact process is considered on infinite graphs, a central question is whether we have survival or extinction of the infection.

For a graph G = (V, E), a finite set A ⊆ V and λ > 0, define p ext G,A,λ = P G,λ τ A G < ∞ = P G,λ ∃t 0 : ξ A t = ∅ for all t t 0 , p loc ext G,A,λ = P G,λ ∃t 0 : ξ A t ∩ A = ∅ for all t t 0 , the probabilities of extinction and local extinction of the contact process with parameter λ on G started from ξ A 0 ≡ A. It can be shown that we either have p ext G,A,λ = 1 for all A or p ext G,A,λ < 1 for all A; likewise, either p loc ext G,A,λ = 1 for all A or p loc ext G,A,λ < 1 for all A. We say that the contact process

• dies out if p ext G,A,λ = 1 for all A; • survives weakly (or globally but not locally) if p ext G,A,λ < 1 and p loc ext G,A,λ = 1 for all A;

• survives strongly (or locally) if p loc ext G,A,λ < 1 for all A.

We let λ 1 (G) = sup{λ : p ext G,A,λ = 1} and λ 2 (G) = sup{λ : p loc ext G,A,λ = 1}.

It is well known that for

G = Z d , 0 < λ 1 (Z d ) = λ 2 (Z d ) =: λ c (Z d ) < ∞.
For G = T d , the infinite, (d + 1)-regular tree (with d 2), the situation is quite different, as we then have 0 < λ 1 (T d ) < λ 2 (T d ) < ∞. In this case, if we take λ such that λ 1 (T d ) < λ < λ 2 (T d ) and start the process from a single infection at a vertex x, then the infection has a chance of surviving, but it can only do so by propagating outwards from x; any finite neighbourhood of x only carries the infection for a finite amount of time, as required in the definition of weak survival.

The contact process on finite graphs (deterministic or random) has also been the subject of much investigation; below we will survey some of the past work that is most relevant to the object of interest of this paper. Let us start noting that for finite graphs, there is no question of survival or extinction: if G is finite, the infection almost surely disappears in finite time. One is thus interested in the behaviour of the infection before it disappears. The typical course of action goes as follows: we fix λ and the parameters that define the graph, then take a size parameter (e.g. the number of vertices) to infinity, so as to obtain a sequence of graphs G n , and consider the asymptotic behaviour of some random quantity X n associated with the contact process on G n . Common choices for X n are the extinction time τ Gn and the average proportion of infected vertices before τ Gn . Of particular interest are the cases in which the asymptotic behaviour of X n depends sensitively on the choice of λ and the set of parameters that define the graph; this dependency can sometimes be related to a phase transition of the contact process on an infinite graph that is in some sense approximated by G n .

This project has been first carried out for G n equal to the subgraph of Z d induced by the vertices contained in a box of side length n; see [CGOV84, Sc85, DL88, Ch94, DS88, Mo93, Mo99], or [Li99, Section I.3] for an overview. As suggested in the previous paragraph, the behaviour of τ Gn exhibits a phase transition that mimics the phase transition of the contact process on Z d : τ Gn grows logarithmically or exponentially with the volume of G n respectively if λ is taken smaller or larger than λ c (Z d ).

Let us now turn to finite trees. Let T d denote the d-ary tree of height . In other words, T d is a tree with a distinguished vertex o (called the root) so that o has degree d, all vertices at distance between 1 and -1 from o have degree d + 1 and all vertices at distance from o have degree 1. In [START_REF] Stacey | The contact process on finite homogeneous trees[END_REF], bounds were obtained on τ T d for different values of λ, and these bounds were improved in [START_REF] Cranston | The contact process on finite trees revisited[END_REF] to yield the result below.

Theorem 1.1. [CMMV13] (a) For any λ ∈ (0, λ 2 (T d )), there exists c ∈ (0, ∞) such that, as → ∞, τ T d log |T d | → c in probability. (b) For any λ ∈ (λ 2 (T d ), ∞), there exists C ∈ (0, ∞) such that, as → ∞, log τ T d |T d | → C in probability.
Moreover, τ T d divided by its expectation converges in distribution to the exponential distribution with parameter 1.

In short, the asymptotic behaviour of the extinction time on T d has a phase transition at the value λ = λ 2 (T d ). It is worth mentioning that the above theorem remains true if T d is replaced by Td , defined as the subgraph of T d induced by the vertex set given by a distinguished root vertex o and all vertices at graph distance at most from o (T d is obtained from Td by removing one of the sub-trees emanating from the root of Td ).

The main goal of this paper is to investigate the asymptotic behaviour of the extinction time of the contact process on random (d + 1)-regular graphs, which we now describe. Fix n ∈ N, the number of vertices, with the restriction that n(d + 1) be even. Let us define a random graph G n with vertex set V n = {1, . . . , n}. We endow each vertex with d + 1 half-edges; attaching two half-edges (say, one belonging to vertex i and another to vertex j) produces an edge between i and j. Then, any perfect matching on the set of half-edges produces a graph (again we note that we allow for multiple edges between two vertices and also edges with both extremities at a single vertex). We choose one perfect matching uniformly at random from all the (n(d + 1) -1) • (n(d + 1) -3) • • • 3 • 1 possibilities, and this produces the random edge set E n . Obviously, G n is a (d + 1)-regular graph; by using an alternate construction of G n that is described in Section 3, it is easy to show that, for any R, with probability tending to 1 as n → ∞, the ball of radius R around a given vertex has no cycle, and is thus isomorphic to Td R . We write P n for the law of G n , and P n,λ for a probability measure under which both G n and the contact process on G n with parameter λ are defined. Our main result is Theorem 1.2. (a) For every λ ∈ (0, λ 1 (T d )) there exists C < ∞ such that

lim n→∞ P n,λ [τ Gn < C log(n)] = 1. (b) For every λ ∈ (λ 1 (T d ), ∞) there exists c > 0 such that lim n→∞ P n,λ [τ Gn > e cn ] = 1.
Let us stress the most important point: contrary to the situation in Theorem 1.1, the behaviour of the extinction time has here a phase transition at λ 1 (T d ) instead of λ 2 (T d ). Although surprising at first, this phenomenon can be understood as follows: when is large, the tree T d as seen from a vertex chosen uniformly at random does not at all locally look like T d . For example, with non-vanishing probability, the random vertex is a leaf of T d . The notion of local limit of a sequence of graphs, as formalized in [START_REF] Benjamini | Recurrence of distributional limits of finite planar graphs[END_REF], captures such features, and one can check that T d does not converge locally to T d , but rather to another infinite graph called the canopy tree CT d (see [Be,Example 5.14] for details). Moreover, one can show that

(1.2) λ 1 (CT d ) = λ 2 (CT d ) = λ 2 (T d )
(local survival for λ > λ 2 (T d ) can be derived from [CMMV13, Theorem 1.6], while extinction for λ λ 2 (T d ) follows from [Li99, Proposition 4.57]). In light of this, the logarithmic-exponential phase transition for the extinction time on T d does happen at the lower critical value of the limiting graph after all, but one must take into account that this limiting graph is the canopy tree.

It would be very interesting to find wider classes of graphs (such as the configuration model described below, or see [vdH] for an exposition) for which one can prove that the same phase transition occurs at the lower critical value of the limiting graph. This is reminiscent of the question of the locality of the percolation critical probability, see [START_REF] Benjamini | Is the critical percolation probability local?[END_REF], [Be, Section 5.2], [START_REF] Martineau | Locality of percolation for abelian Cayley graphs[END_REF] and [START_REF] Song | Locality of percolation critical probabilities: uniformly nonamenable case[END_REF].

The graph G n is a particular case of the class of graphs known as the configuration model. Whereas for G n we assumed that all degrees are taken equal to d + 1, in the configuration model one allows for a random degree sequence, typically i.i.d. from some fixed degree distribution. The contact process on these graphs has lately received attention ([CD09, MMVY12, MVY13]). In particular, it was proved that, if the degree distribution is a power law (and the graph is assumed to be connected), then the extinction time grows exponentially with the number of vertices regardless of the value of λ. In this sense, one can say that the contact process on the configuration model with a power law degree distribution has no phase transition: it is "always supercritical". Theorem 1.2 shows that, if the degrees are constant, then there is a phase transition. In fact, putting together Lemma 4.2 below with the main result of [START_REF] Mountford | Exponential extinction time of the contact process on finite graphs[END_REF], we get Theorem 1.3. Let G n,d be the set of connected graphs with n vertices and degree bounded by d + 1.

(a) For any λ ∈ (0, λ 1 (T d )), there exists C < ∞ such that

lim n→∞ inf G∈G n,d P G,λ [τ G < C log n] = 1.
(b) For any λ ∈ (λ c (Z), ∞), there exists c > 0 such that

lim n→∞ inf G∈G n,d P G,λ [τ G > e cn ] = 1.
In particular, if we take the contact process on the configuration model with a degree distribution with bounded support, the extinction time exhibits a phase transition on λ. A problem that we believe to be of much interest is whether such a phase transition also occurs if the degree distribution has unbounded support, but a light tail. Equally interesting is the corresponding question for supercritical Erdős-Rényi random graphs. In this direction, we refer the reader to the very recent remarkable results of [START_REF] Ménard | Percolation by cumulative merging and phase transition for the contact process on random graphs[END_REF], where existence of a phase transition for the contact process on certain graphs with unbounded degrees, such as Delaunay triangulations of R d , is shown.

We now comment on the proofs of the two parts of Theorem 1.2. Part (a) relies on the fact, stated in Lemma 4.2, that the contact process on any graph of degree bounded by d + 1 is stochastically dominated (in terms of the number of infected vertices) by a contact process with the same λ on T d . Although this is a very elementary and natural statement, we did not find it in the literature, so we give a proof, which relies on the concept of universal covering of a graph. Once Lemma 4.2 has been established, we invoke known bounds for the extinction time of the contact process on T d in the extinction regime in order to conclude the proof of part (a).

As a side note, we remark that Lemma 4.2 also applies to infinite graphs, and as a consequence we prove: Theorem 1.4. If λ λ 1 (T d ), then the contact process with parameter λ on any graph with degree bounded by d + 1 dies out.

The proof of part (b) of Theorem 1.2 is more involved, and relies on a geometric property of G n (Theorem 3.4). The idea can be roughly summarised as follows. Assume that at time 0, there are δn infected vertices (δ > 0 small) with the property that within distance r of each of these vertices, one can find a copy of T d , the copies (and the paths to them) being pairwise disjoint. Let us say that a set satisfying this property is regenerative. If can be chosen sufficiently large, then after some time, the infection will spread to kδn vertices with k large, except for an event whose probability is exponentially small in n. The crucial geometric property of G n that we need is that if k is sufficiently large, then with probability tending to 1, any subset of size kδn contains a regenerative subset of size δn. This enables to iterate the argument. Since the probability of failure of a given step is exponentially small, the extinction time must be exponentially long.

In Section 2, we give a summary of the notation we use, an exposition of the graphical construction of the contact process and some known results about the contact process on trees. Sections 3 and 4 are devoted to proving parts (b) and (a) of Theorem 1.2 respectively.

Notation and preliminary results

2.1. Summary of notation for sets and graphs. For a set A, we write |A| for the cardinality of A and 1 A for the indicator function of A.

We will bother the reader with defining graphs, because we want to allow loops (edges between a vertex and itself) and multiple edges with the same endpoints, and this requires some care with the notation. Given sets V and E and a function We may abuse notation and write v ∈ G instead of v ∈ V when convenient. Also, we will omit the presence of the function ζ, simply writing G = (V, E) as is usual.

The degree of a vertex is the number of non-loop edges that contain it plus twice the number of loops that contain it. The graph distance between vertices x and y is the length of a shortest path between x and y, and is denoted by dist(x, y), or dist G (x, y) when we want to make the graph explicit. A cycle is a sequence of vertices x 0 , . . . , x k so that x 0 , . . . , x k-1 are all distinct, x k = x 0 and for each i, x i and x i+1 are neighbours.

The set E of oriented edges of G is defined as follows: for each non-loop e ∈ E, we add to E two oriented edges corresponding to the two possible orientations of e; for each loop in e, we also add to E two "oriented edges" from x to x (though this will be quite unimportant). A generic element of E will be denoted by e. Note that, if there are k edges containing x and y, then there are 2k oriented edges containing x and y. We write v 0 ( e) and v 1 ( e) to denote the starting and ending vertex of e, respectively. We also let u( e) ∈ E denote the unoriented edge to which e is associated.

A rooted graph is a pair (ρ, G) where G is a graph and ρ ∈ G. Given two rooted graphs (ρ, G) and (ρ , G ) with G = (V, E), G = (V , E ), we say that f :

V → V is an embedding of (ρ, G) into (ρ , G ) if • f (ρ) = ρ , • f is injective,
• for every u, v ∈ V , the number of edges in G containing u and v is less than or equal to the number of edges of G containing f (u) and f (v).

(Of course, if G and G have no loops or multiple edges between vertices, the last property means that f (u) and f (v) are neighbours in G whenever u and v are neighbours in G.) We say that (ρ , G ) embeds (ρ, G) if there exists an embedding of (ρ, G) into (ρ , G ); that (ρ, G) and (ρ , G ) are isomorphic if each embeds the other.

For the rest of the paper, we fix d 2 and omit d from T d and T d , thus writing T and T respectively. The root of T is denoted by o.

2.2. Graphical construction of the contact process. Almost every paper on the contact process contains a brief exposition of its graphical construction, so this is by now quite a redundant addition. We nevertheless include it here because we allow our graphs to contain loops and parallel edges, so we need to be careful with the notation to avoid confusion.

Fix a graph G = (V, E) and an infection rate λ > 0. Assume given the following families of independent Poisson point processes on [0, ∞): (T e ) e∈ E , all with rate λ, and (D x ) x∈V , all with rate 1. We now imagine G is embedded on the xy-plane and add marks on the vertical lines (V ∪ E) × [0, ∞) as follows: for each x and each t ∈ D x , we add a so-called recovery mark at (x, t), and for each e and each t ∈ T e , we add a so-called transmission arrow at ( e, t).

Given x, y ∈ V and 0 s t, we say that (x, s) and (y, t) are connected by an infection path (and write (x, s) ↔ (y, t)) if there exists a right-continuous function

γ : [s, t] → V such that • γ(s) = x, γ(t) = y, • (r, γ(r)) / ∈ D γ(r) for all r ∈ [s, t], • γ(r-) = γ(r) implies r ∈ T e for some e with v 0 ( e) = γ(r-), v 1 ( e) = γ(r).
In other words, (r, γ(r)) s r t must be a path from (x, s) to (y, t) which does not cross any recovery mark and is allowed to traverse transmission arrows.

For

x ∈ V , let ξ x t = {y ∈ V : (x, 0) ↔ (y, t)}; for A ⊆ V , let ξ A t = ∪ x∈A ξ x t .
Then, (ξ A t ) t 0 is a Markov process on {0, 1} V with the same distribution as the process defined earlier in (1.1). The graphical construction has the advantage that all the contact processes ((ξ A t ) t 0 ) A⊆V are defined in the same probability space and, if A ⊆ B, then ξ A t ⊆ ξ B t for all t. Note also that ξ A s+t = ∪ x∈ξ A t {y : (x, t) ↔ (y, t + s)}.

2.3. Known results on the contact process on T. We now list some definitions and results about the contact process on T which we will need; all of them can be found in Section I.4 of [START_REF] Liggett | Stochastic interacting systems: contact, voter and exclusion processes[END_REF]. The reader is encouraged to skip this subsection and refer back to it when each result is needed. We start defining a "generation number" function : T → Z as follows. Take an embedding κ :

Z → T so that κ(0) = o. If x ∈ κ(Z), set (x) = κ -1 (x). If x /
∈ κ(Z), let y be the first vertex of κ(Z) reached in a path from x to κ(Z); set (x) = (y) + dist(x, y). Now, given ρ > 0, as in [START_REF] Liggett | Stochastic interacting systems: contact, voter and exclusion processes[END_REF] equation (4.23), page 87, we put

φ λ (ρ) = lim t→∞ E T,λ x∈T ξ o t (x) • ρ (x) 1 t
; the limit is shown to exist (page 87). In Proposition 4.27(a) and (b) we respectively have

(2.1) φ λ (ρ) = φ λ 1 ρd and (2.2) E T,λ [|ξ o t |] C λ • φ λ (1) t , t 0,
for some constant C λ > 0. In Proposition 4.44(a), we have

(2.3) 1 √ d ρ < ρ and φ λ (ρ ) 1 =⇒ φ λ (ρ) < φ λ (ρ ).
As in equation (4.48), page 96, we define for λ > 0

(2.4)

β(λ) = lim n→∞ P T,λ [∃t : ξ t (κ(n)) = 1] 1 n ;
again the limit is shown to exist (page 96). Regarding β, we will need the following facts, which can be found in Theorem 4.83, Corollary 4.87 and Theorem 4.130 of [Li99]:

(2.5)

β(λ) < 1 √ d =⇒ φ λ (β(λ)) = φ λ 1 β(λ) • d = 1, (2.6) β(λ 1 ) = 1 d , (2.7) β is strictly increasing in [0, λ 2 (T)].

Supercritical regime

The goal of this section is to prove part (b) of Theorem 1.2. We first state for later usage a classical large deviation result on binomial random variables, whose proof is standard. Lemma 3.1. Let Bin(m, p) denote a binomial random variable with parameters m ∈ N and p ∈ [0, 1] (defined with respect to the measure P, say). For every δ 0, (δ) , where

P[Bin(m, p) (p + δ)m] e -mψp
ψ p (δ) = sup λ λ(p + δ) -log(1 -p + pe λ ) = (p + δ) log p + δ p + (1 -p -δ) log 1 -p -δ 1 -p . (3.1)
We will need the following estimate: Lemma 3.2. For every λ > λ 1 (T), there exist R, p 0 > 0 and α 0 > 1 such that, for large enough,

P T ,λ |ξ o R | α 0 p 0 .
Proof. Let T ∞ be the infinite, rooted, d-ary tree (that is, the infinite rooted tree in which the root o has degree d and all other vertices have degree d + 1). In [START_REF] Salzano | A new proof that for the contact process on homogeneous trees, local survival implies complete convergence[END_REF] it is shown that for every λ > λ 1 (T), there exist U > 0, γ > 1 and p > 0 such that, for ∈ N large enough,

(3.2) P T∞,λ |ξ o U | γ p,
where β(λ) is defined in (2.4). We remark that:

(1) the above estimate follows from equation (2.6) in [START_REF] Salzano | A new proof that for the contact process on homogeneous trees, local survival implies complete convergence[END_REF];

(2) the running hypothesis in [START_REF] Salzano | A new proof that for the contact process on homogeneous trees, local survival implies complete convergence[END_REF] is that λ > λ 2 (T), but (3.2) holds true more generally, for λ > λ 1 (T). Indeed, its proof depends on two ingredients. First, their Lemma 1, which in fact holds for any λ > 0. Second, an argument involving branching processes (see the paragraphs preceding their equation (2.6)) which is applicable as long as d • β(λ) > 1. By (2.6) and (2.7), this is indeed the case when λ > λ 1 (T); (3) we can then choose γ as any constant between 1 and d • β(λ).

Using equation (4.76) in [START_REF] Liggett | Stochastic interacting systems: contact, voter and exclusion processes[END_REF], one can readily show that there exists S > 0 such that, for all t > 0,

P
P T ,λ |ξ o R | α 0 .
We have the following consequence of the above result:

Lemma 3.3. For every λ > λ 1 (T) and r > 0, there exist R, σ > 0 and α > 1 such that for every large enough, the following holds. For any graph G with vertices x, y such that dist(x, y) r and (y, G) embeds (o, T ), we have

P G,λ |ξ x R | α > σ.
Proof. Let R, p 0 and α 0 be as in the previous lemma; we have

P G,λ |ξ x R( +1) | α 0 P G,λ [ξ x R (y) = 1] • P G,λ |ξ y R | α 0 P G,λ [ξ x R (y) = 1] • p 0 .
We can now find σ > 0 that bounds the right-hand side from below uniformly on dist(x, y) ∈ {1, . . . , r} (one can guarantee that the event {ξ x R (y) = 1} occurs by making finitely many prescriptions on Poisson processes in the graphical construction on a geodesic path connecting x and y and the time interval [0, R]). We then pick any α ∈ (1, α 0 ); the result follows from observing that α -1 0 > α for large enough.

We say that a set of vertices W ⊆ V n is -regenerative if there exists a family (G v ) v∈W of subgraphs of G n that are pairwise disjoint and such that for every v ∈ W , the following two conditions hold:

• G v contains v,

• there exists x ∈ G v such that the distance in G v between x and v is 4 and (x, G v ) embeds (o, T ). The crucial geometric property of G n that we need is Theorem 3.4 (Finding large regenerative subsets). For any ∈ N and ε > 0 sufficiently small (depending on ), the following holds with P n -probability tending to 1 as n tends to infinity. From every W ⊆ V n of cardinality at least εn, one can extract an -regenerative subset of cardinality at least ε 40d 6 n. Remark 3.5. In what follows, in order to prevent the notation from getting too heavy, we will pretend that certain quantities, such as εn in the above proposition, are integers. It should be clear that in a correct but overscrupulous writing, one should take the pertinent integer parts or add or subtract 1 at certain places, but that this does not change our proofs in any relevant way.

We prove part (b) of Theorem 1.2 using Theorem 3.4, before turning to the proof of the latter.

Proof of part (b) of Theorem 1.2. We fix λ > λ 1 (T), and choose constants according to the following steps:

(1) let α, R, σ correspond to λ and r = 4, as in Lemma 3.3;

(2) take large enough, as required by Lemma 3.3, and also so that α > 80d 6 σ ;

(3) take ε corresponding to as in Theorem 3.4. Assume G n satisfies the property stated in Theorem 3.4, namely every W ⊆ V n with |W | εn has an -regenerative subset of cardinality ε 40d 6 n.

We will now prove that, for some constant c > 0 which does not depend on n,

(3.3) for all W ⊆ V n with |W | εn, P Gn |ξ W R | εn 1 -e -cn .
This will imply the statement of Theorem 1.2. We fix W with |W | εn and extract from it an -regenerative subset W of cardinality n := ε 40d 6 n; we enumerate its elements, W = {v 1 , . . . , v n }. By the definition of -regenerative sets, there exist pairwise disjoint subgraphs of G, G v1 , . . . , G v n such that v i ∈ G vi and there exists

x i ∈ G vi such that dist(v i , x i ) = 4 and (x i , G vi ) embeds (o, T ).
For each v i , let (ζ vi t ) t 0 be the contact process on G vi , started from only v i infected, and built using the same family of Poisson processes as the original contact process on G.

If i = j,
E i = |ζ vi R | α , 1 i n .
We then have P Gn [E i ] σ. Thus, by standard large deviation estimates for binomial random variables (see Lemma 3.1), we have

P Gn   n i=1 1 Ei σ 2 n   1 -e -c(ε,σ)n .
Finally, if the event in the above probability occurs, we have

|ξ W R | α • n i=1 1 Ei α • σ 2 n > εn.
This completes the proof.

We now give some definitions and preliminary results for the proof of Theorem 3.4. We say that a set of vertices W ⊆ V is well separated if the following two properties hold:

• for every v ∈ W , the 3-neighbourhood of v is cycle-free (for r ∈ N, the r-neighbourhood of a vertex v ∈ V is the set of vertices w whose distance to v is at most r), • for every two distinct v, w ∈ W , the 3-neighbourhoods of v and w are disjoint.

The key step of the proof lies in the following proposition.

Proposition 3.6 (Key estimate). For every ∈ N, there exists c > 0 such that for every ε > 0 suficiently small (depending on ) and every n large enough, P the set {1, . . . , εn} is well separated but has no -regenerative subset of size εn/5 (cε 6 5 ) εn .

Remark 3.7. In order to prove Theorem 3.4, we will use a union bound over all sets of cardinality εn. Roughly speaking, there are about ε -εn such sets (ε 1). So the crucial point in Proposition 3.6 is that the exponent 6 5 appearing there is strictly larger than 1.

Before proving this key estimate, we introduce some terminology. A semi-graph g = (V, E, H) is a triple consisting of a set V of vertices, a set E of edges between points of V , and a set H of half-edges, each half-edge being attached to some vertex in V . Given two half-edges h and h , we write h + h to denote the edge obtained by "gluing together" the half-edges h and h (that is to say, if h is attached to a vertex v and h to a vertex w, then h + h is an edge connecting v and w). The distance in the semi-graph g is simply the distance in the graph (V, E).

Consider the semi-graph g = (V n , E, H) such that E = ∅ and each vertex in V n has exactly d + 1 half-edges. We can construct a random regular graph with distribution P n by the following recursive procedure. Take an arbitrary half-edge h in H (call it the elected half-edge); take a half-edge h uniformly at random in H \ {h}; add the edge h + h to the set E, remove the half-edges h and h from H; repeat until the set of half-edges is empty. (Recall that we assume (d + 1)n to be even, so that there is an even number of half-edges to begin with). The resulting random graph has law P n . A feature of this procedure that will be crucial in our reasoning is that at each step, we have the freedom to choose the elected half-edge as we wish among the half-edges of H.

It will be convenient to write operations on sets such as those done in the above construction in the more symbolic form

(3.4) E ← E ∪ {h + h }, H ← H \ {h, h }.
Proof of Proposition 3.6. Fix ∈ N. Also fix ε ∈ (0, 1) and n ∈ N; for the moment we do not specify their choice. We take the semi-graph g = (V n , E, H) such that E = ∅ and such that every site has exactly (d + 1) half-edges. We denote by W the set of vertices {1, . . . , εn}. As long as there is a half-edge h attached to a vertex at distance 2 or less from W, we choose this as the elected half-edge, pick another half-edge h uniformly at random from H \ {h}, and do the operations in (3.4). When there is no longer any such half-edge, the graph is still incomplete, but we can already decide if W is well separated, since we have revealed all the 3-neighbourhoods of vertices in W (and nothing more). If the set is not well separated, we can stop. On the event that the set is well separated, we continue our construction of the graph, with the aim of showing that W will contain a good subset of size εn/5 with high probability. Let F be the set of vertices still having (d + 1) half-edges at this point. We call elements of F fresh vertices (they are still unseen by our construction of the graph). Elements of W will be called seeds. Recall that since we consider only the event that W is well separated, for every seed ρ, the 3-neighbourhood of ρ, rooted at ρ, is isomorphic to (o, T 3 ); moreover, every vertex x at distance 3 from ρ has exactly d half-edges attached to it at this point.

Below we will give a procedure to continue electing half-edges and thus continue the construction of the graph; at any point in the construction, we say that a seed ρ is active if there are at least 3 half-edges attached to vertices at distance 3 from ρ (as of now, there are (d + 1)d 3 such half-edges).

A seed that is not active will be called quiet. As of now, every seed is active. We let ρ be any active seed (as of now, this only means that we take ρ ∈ W), and run the pass described below.

The pass started from the active seed ρ.

Let V be the set of vertices at distance 3 or less from ρ and let E be the set of edges with both extremities in V . Let H be the set of half-edges attached to vertices of V ; by the definition of an active seed, H has at least 3 elements.

Let v ∈ V be at distance strictly less than + 4 from ρ as measured in the graph (V , E), and such that there is a half-edge h ∈ H attached to it. If such a v does not exist, then declare that the pass is a success and stop. Otherwise, pick h uniformly at random in H \ {h}, and let v be the vertex to which it is attached. If v / ∈ F, then declare that a collision occurs (say that it is a short collision if moreover, v ∈ V ; that it is a long collision otherwise).

• If it is the second time during the pass that a collision occurs, then declare that the pass is a failure, do the updates

(3.5) E ← E ∪ {h + h }, H ← H \ {h, h },
and stop the pass. • If it is the first time during the pass that a collision occurs, do the updates

(3.6) E ← E ∪ {h + h }, H ← H \ {h, h }, H ← H \ {h, h },
and go back to . • If a collision does not occur (that is, if v ∈ F), then do the updates

E ← E ∪ {h + h }, H ← H \ {h, h }, H ← H \ {h}, V ← V ∪ {v }, F ← F \ {v }, E ← E ∪ {h + h },
and finally add the remaining half-edges of v to H. Then go back to .

Observation 3.8. In (3.6), we only need to remove h from H in case of a short collision; if the collision is long, then h is not an element of H at this point.

We then iterate this pass, always starting with an active seed that has not been the starting point of any previous pass, until every seed is quiet or has already been used as the starting point of a pass.

We now list some important observations concerning the effect of passes.

Observation 3.9 (The effect of a successful pass). If the pass is a success, we define

G ρ = (V , E). This subgraph of G n is a tree satisfying: (a) ρ is in the vertex set, (b) there exists x ∈ V such that dist G ρ (ρ, x) = 4 and (x, G ρ ) embeds (o, T ).
Let us verify (b); to this end, we introduce some notation. Given a vertex x ∈ V , we let V x be the set of vertices y ∈ V such that the unique path in G ρ from y to ρ contains x, then let E x be the set of edges of E with both extremities in V x , and finally let G ρ,x = (V x , E x ). Now, if there were no collisions in the pass, then there are at least three distinct vertices

x 1 , x 2 , x 3 such that dist G ρ (x i , ρ) = 4 and (x i , G ρ,xi
) is isomorphic to (o, T ) for each i, so (b) holds. If one collision occurred in the pass, then at most two of these subtrees is compromised by missing edges, so that there still exists some x with dist G ρ (x, ρ) = 4 and (x, G ρ,x ) isomorphic to (o, T ). Apart from satisfying the properties listed above, G ρ does not intersect any subgraph G ρ obtained from previous passes. Observation 3.11 (Many passes). It may occur, due to half-edges being removed in collisions, that a seed becomes inactive before it is used in a pass (let us say that it is then ruined). Recall that for a seed ρ,

• there are initially (d + 1)d 3 half-edges attached to vertices at distance 3 from ρ; • ρ remains active as long as at least 3 of these half-edges are present;

• any given pass which starts from some other seed ρ can cause the removal of at most two of these half-edges.

In conclusion, it takes at least (d+1)d 3 -3 2 passes started from other seeds to ruin the seed ρ. Taking this into account we see that, if we run the pass t times, then at most t + t • 2 (d + 1)d 3 -3 seeds become inactive (namely, those that are being explored by each pass and those that are ruined by collisions). In other words, since we start with |W| = εn seeds, we can run the pass at least Let us now estimate the probability that a pass is a failure. By observation 3.10, the probability to find a collision while running an iteration of instruction (that is, at each moment in the pass in which we pick a half-edge uniformly at random) is bounded above by

dc |W| (d + 1)(n -c |W|) c ε 1 -c ε .
Hence, the probability that a double collision is found during a pass (or in other words: the pass fails due to the occurrence of two collisions) is smaller than

P Bin c , c ε 1 -c ε 2 ,
where we used the fact that during one pass, we iterate instruction at most c times. Hence, we can choose ε sufficiently small (depending on d and ) so that Hence, the probability above is bounded by (cε 6 5 ) |W| for some constant c independent of ε.

To sum up, we have shown that in our procedure, we • run at least 4 5 εn passes; • have at most 3 5 εn failed passes with probability larger than 1 -(cε 6 5 ) |W| . This is exactly what we need to conclude, as was explained in Observation 3.9.

Corollary 3.12. For every ∈ N and ε > 0 sufficiently small, P from every well-separated set W ⊆ V n of size εn, one can extract an -regenerative subset of size εn/5 n→∞ ----→ 1.

Proof. Take c, ε corresponding to as in Proposition 3.6. For large enough n, the probability for a given well-separated set W ⊆ V n of size εn not to contain any -regenerative subset of size εn/5 is smaller than (cε 6 5 ) εn . We prove the corollary by a union bound, counting the total number of sets W ⊆ V n of size εn. This number is n εn n εn (εn)! .

Using the fact that log n! n log n -n (which can be proved by induction on n), we see that log n εn εn log n -εn log(εn) + εn = εn 1 + log 1 ε .

By reducing the value of ε > 0 if necessary, we can ensure that (cε 6 5 ) εn exp εn 1 + log 1 ε tends to 0 as n tends to infinity, and this proves the result.

Proof of Theorem 3.4. The number of cycles in G n of size bounded above by 3 remains tight as n tends to infinity (in order to see this, it suffices to check that the expectation of the number of such cycles remains bounded). In particular, with probability tending to 1, there are less than √ n cycles of size bounded by 3. We assume from now on that the event that there are no more than √ n cycles of size bounded by 3 is realized.

For any site v ∈ V , the size of its 6-neighbourhood is no more than

1 + (d + 1) + (d + 1)d + • • • + (d + 1)d 5 4d 6 .
We observe that if m ∈ N and U is a set of m vertices, we can extract from U a subset of m/(4d 6 ) vertices whose 3-neighbourhoods are pairwise disjoint. To see this, let x 1 be an arbitrary point of U . Then, the set U obtained by removing from U all points that belong to the 6-neighbourhood of x 1 has size at least m -4d 6 . Moreover, the 3-neighbourhood of any point of U is disjoint from the 3-neighbourhood of x 1 . We then let x 2 be an arbitrary point of U , and continue this procedure until x m/(4d 6 ) is defined. Now assume that W is a set of εn vertices. By the above, we can find W ⊆ W with at least εn/(4d 6 ) vertices so that the 3-neighbourhoods of vertices in W are all disjoint. As there are no more than √ n cycles of size bounded above by 3, assuming n is large enough that √ n < εn/(8d 6 ), we can further obtain W ⊆ W with |W | > εn/(8d 6 ) vertices so that W is well-separated. The desired conclusion then follows immediately from Corollary 3.12.

Subcritical regime

We start from the following consequence of well-known estimates for the subcritical contact process on trees. Proof. The proof will depend on the fact that, for any λ < λ 1 (T), there exist c 0 , C 0 > 0 such that (4.1)

E T,λ [|ξ o t |] C 0 e -c0t
, t 0. This is proved as follows. For λ < λ 1 (T), (2.6) and (2.7) give β(λ) < 1 d . Together with (2.5), this shows that φ λ (ρ) = 1 for some ρ > 1. Then, using (2.3), we get φ λ (1) < 1, and then (2.2) gives the desired equation (4.1).

Let us now show how (4.1) completes the proof of our proposition. Noting that

|ξ A t | = |∪ x∈A ξ x t | x∈A |ξ x t |, we have P T,λ |ξ A t | = ∅ E T,λ |ξ A t | C 0 |A|e -c0t .
The proof is completed by taking C = 2/c 0 .

Part (a) of Theorem 1.2 is a consequence of the above proposition and the following result: Proof. Since the contact process is unaffected by the presence of edges that start and end at the same vertex (loops), we assume that G has none.

We will now recall the concept of universal covering of the graph G; we will construct from G a new graph T = (V, E) with certain desirable properties. We start fixing a reference vertex x ∈ V . We say that a sequence γ = ( e 1 , . . . , e n ) of oriented edges of E is a non-backtracking path from x if v 0 ( e 1 ) = x and, for 1 i < n, v 1 ( e i ) = v 0 ( e i+1 ) and u( e i ) = u( e i+1 ) (recall that, for an oriented edge e, v 0 ( e), v 1 ( e) and u( e) respectively denote the starting vertex, ending vertex and undirected edge associated to e). Let V be the set of all non-backtracking paths from x, including an empty path which we denote by o. For any γ, γ ∈ V with γ = ( e 1 , . . . , e n ) and γ = ( e 1 , . . . , e n , e n+1 ), we connect γ and γ by an edge; this defines the edge set E of T . Finally, put ψ(o) = x and, for γ = ( e 1 , . . . , e n ), put ψ(γ) = v 1 ( e n ), the ending vertex of the path γ. It is now easy to check that T and ψ satisfy the properties:

(a) T is a tree with degree bounded by d + 1; (b) for every γ ∈ V, letting x = ψ(γ) ∈ V , we have for all y ∈ V, |{edges of E with extremities x and y}| = |{γ ∈ V : γ and γ are neighbours in T , ψ(γ ) = y}| .

(in case x is connected to each of its neighbours by a single edge, this just says that ψ maps the neighbourhood of γ bijectively to the neighbourhood of x).

For v ∈ V , the set ψ -1 (v) is called the fiber of v. Define the set of configurations of {0, 1} V that have at most one particle per fiber, Given B ∈ Ω T , we define the constrained contact process on T , (ζ B t ) t 0 , as follows. We set ζ B 0 = B and let ζ evolve as a contact process on T with the restriction that we suppress every transition which would result in a configuration not in Ω T , that is, births on vertices belonging to fibers already containing infected vertices. Formally, (ζ t ) has generator

Ω T =    ζ ∈ {0, 1} V : γ∈ψ -1 (v)
Lf (ζ) = γ∈V f (ζ 0→γ ) -f (ζ) + λ • {γ,γ }∈E: ζ(γ)=1 1 {ζ 1→γ ∈Ω T } • f (ζ 1→γ ) -f (ζ) ,
where ζ i→γ is the configuration obtained by modifying ζ so that γ is set to state i. Noting that G is finite, and hence ζ has at most |V | infected vertices at any given time, it is not hard to see that the above generator indeed gives rise to a Feller process on Ω [0,∞) T

. In fact, ζ can be constructed from a Harris system on T , with the extra care of ignoring any transmission mark which would cause a fiber to become doubly occupied. Also, using property (b) of T and ψ stated above, it is easy to show that (π(ζ B t )) t 0 has the same distribution as the contact process on G started from π(B). Now, if we start from A ⊆ V , we can choose an arbitrary B ∈ Ω T such that π(B) = A and conclude that τ A G has the same distribution as inf{t : ζ B t = ∅}. By seeing T (and hence B) as a subset of T, we have that ζ B is stochastically dominated by the contact process on T started from B infected, and hence inf{t : ζ B t = ∅} is stochastically dominated by τ B T . This completes the proof.

Let G be a graph and x a vertex of G. Given the contact process on G started from a single infection at x, (ξ x t ) t 0 , define κ x G = sup{dist(x, y) : y ∈ ξ x t for some t 0}.

ζ

  : E → {subsets of V with cardinality 1 or 2}, the triple G = (V, E, ζ) is a graph; elements of V are vertices and elements of E are edges. e ∈ E is said to be an edge between vertices x and y if ζ(e) = {x, y}; if such an edge exists, we say that x and y are neighbours. If ζ(e) = {x}, we say e is a loop at x.

2 .

 2 T∞,λ [ξ o s (y) = 0 for all s t and y with dist(o, y) St] P T,λ [ξ o s (y) = 0 for all s t and y with dist(o, y) St] > 1 -p Combining these two estimates and setting R = S -1 and α 0 = γ R/U > 1 we get p 2 P T∞,λ |ξ o R | α 0 , ξ o s (y) = 0 for all s R and y with dist(o, y)

  Observation 3.10 (Many fresh sites). During one pass, at most c := (d + 1)d 3 + (d + 1)d 4 + • • • + (d + 1)d +4 iterations of the instruction are performed, so in particular at most c vertices are removed from the set F of fresh vertices. Initially, there are n -|W|(1 + (d + 1) + (d + 1)d + (d + 1)d 2 ) fresh vertices. Since we start with |W| active seed vertices, we can run the pass no more than |W| times. At any given time, there are thus at least n -c |W| fresh vertices, where c := 1 + (d + 1) + (d + 1)d + • • • + (d + 1)d +4 .

  out of active seeds (since d 2).

  (3.7) the probability for a pass to fail is less than c ε 2 , where c = (c c ) 2 . The probability that at least 3 5 εn passes fail due to double collisions is thus bounded by P Bin |W|, c ε 2 3 5 εn = P Bin εn, c ε 2 3 5 εn , using (3.7) and the fact that we run at most |W| passes. Applying Lemma 3.1 with m = εn = |W| , p = c ε 2 and p + δ = 3 5 , we see that this probability is bounded by exp

Proposition 4. 1 .

 1 For any λ < λ 1 (T), there exists C > 0 such that lim n→∞ sup A⊆T:|A|=n P T,λ τ A T > C log n = 0.

Lemma 4. 2 .

 2 For any finite graph G = (V, E) with degree bounded by d + 1, A ⊆ V and t > 0, P G,λ τ A G > t sup B⊆T:|B|=|A| P T,λ τ B T > t .

.

  ζ(γ) ∈ {0, 1} for all v ∈ V    Define the projection π : Ω T → {0, 1} V by [π(ζ)](v) = γ∈ψ -1 (v) ζ(γ) for v ∈ V .We abuse notation and, for a set B ⊆ V, we write B ∈ Ω T if 1 B ∈ Ω T .

Lemma 4. 3 .

 3 For any finite graph G with degree bounded by d + 1, any vertex x of G and k > 0,P [κ x G > k] P [κ o T > k] . Proof.Repeating the construction in the previous lemma, we note that, if ψ(γ) = x and ψ(γ ) = y, then dist T (γ, γ ) dist G (x, y), and we then see thatκ x G is stochastically dominated by sup{dist T (γ, γ ) : γ ∈ ζ {γ} tfor some t 0}. The latter is in turn stochastically dominated by κ o T , completing the proof.Proof of Theorem 1.4. In order to show that the contact process on G dies out, it suffices to show, for any vertex x, thatP [τ x G < ∞] = 1. Denote by B G (x,r) the subgraph of G induced by the set of vertices at graph distance at most r from x. Then, P [τ x G < ∞] = lim r→∞ P [κ x G r] = lim r→∞ P κ x B G (x,r+1) r lim r→∞ P [κ o T r] = 1.


Jean-Christophe Mourrat

Felix Otto

CORRELATION STRUCTURE OF THE CORRECTOR IN STOCHASTIC HOMOGENIZATION

Keywords: MSC 2010 35B27, 35J15, 35R60, 82D30 homogenization, random media, two-point correlation function

Recently, the quantification of errors in the stochastic homogenization of divergence-form operators has witnessed important progress. Our aim now is to go beyond error bounds, and give precise descriptions of the effect of the randomness, in the large-scale limit. This paper is a first step in this direction. Our main result is to identify the correlation structure of the corrector, in dimension 3 and higher. This correlation structure is similar to, but different from that of a Gaussian free field.

Introduction

Consider the solution u ε : R d → R of the equation

1 -∇ • A • ε ∇ u ε = f,
where f is a bounded smooth function, A is a random field of symmetric matrices on R d , and ε > 0. If A is uniformly elliptic and has a stationary ergodic law, then u ε is known to converge as ε → 0 to u h , the solution of

(1 -∇ • A h ∇) u h = f,
where A h is the (constant in space, deterministic) homogenized matrix. This asymptotic result becomes more interesting if we can

(1) devise (provably) efficient techniques to compute the homogenized matrix;

(2) estimate the error in the convergence of u ε to u h .

Doing so requires to introduce some additional assumption on the type of correlations displayed by the random coefficients; we assume from now on that they have a finite range of dependence. These problems were discussed in several works [Yu86, CI03, BP04, Bo09, Mo11, CS14, CF15] (see also [START_REF] Caffarelli | Rates of convergence for the homogenization of fully nonlinear uniformly elliptic pde in random media[END_REF][START_REF] Armstrong | Quantitative stochastic homogenization of elliptic equations in nondivergence form[END_REF] for nondivergence form operators), but optimal error bounds were worked out only recently in [GO11, GO12, GM12, GNO15] for (1), and in [START_REF] Mourrat | Kantorovich distance in the martingale CLT and quantitative homogenization of parabolic equations with random coefficients[END_REF][START_REF] Gloria | An optimal quantitative two-scale expansion in stochastic homogenization of discrete elliptic equations[END_REF] for (2) (in the discrete-space setting).

While controlling the size of the errors in homogenization is useful, it would be better (and it is our aim) to describe precisely what the errors look like when ε is small. As an analogy, if the convergence of u ε to u h is a law of large numbers, then we are looking for a central limit theorem.

The present paper is a first step towards this goal. In a discrete-space setting, it was proved in [START_REF] Gloria | An optimal variance estimate in stochastic homogenization of discrete elliptic equations[END_REF] that stationary correctors exist for d 3 (recall that we assume that the random coefficients have a finite range of dependence). In this case, let us write φ ξ for the (stationary) corrector in the direction ξ [see (2.2)]. Under a minor smoothness assumption on the random coefficients, we show that for large x, the correlation φ ξ (0) φ ξ (x) becomes very close to (1.1)

K ξ (x) := ∇G h (y) • Q (ξ) ∇G h (y -x) dy,
where G h is the Green function of the homogenized operator -∇ • A h ∇, and Q (ξ) is a d × d symmetric matrix that can be expressed in terms of correctors, see (2.4).

This result paves the way for the understanding of the full scaling limit of ε -d-2

2 φ(•/ε), seen as a random distribution. Indeed, the main missing ingredient is now to show that for any bounded, smooth test function f , the properly rescaled random variable x∈Z d φ(x)f (εx) converges in law to a Gaussian. This will be done in [START_REF] Mourrat | Scaling limit of the corrector in stochastic homogenization[END_REF].

This result on the corrector suggests (via a formal two-scale expansion) a scaling limit for ε -d/2 (u ε (•) -u ε (•) ) as well. This will be addressed in [START_REF] Mourrat | Scaling limit of fluctuations in stochastic homogenization[END_REF].

Related works. We now give a brief overview of related works. These can be divided into three groups.

First, the questions that we consider here in dimension d 3 have been investigated in dimension 1. One can benefit from this setting to gain a better understanding of the effect of long-range correlations of the coefficients [START_REF] Bal | Random integrals and correctors in homogenization[END_REF][START_REF] Gu | Random homogenization and convergence to integrals with respect to the Rosenblatt process[END_REF].

Second, similar questions have been explored for the homogenization of operators other than those considered here. Typically, one considers a deterministic operator perturbed by the addition of a rapidly oscillating random potential [FOP82, Ba08, Ba10, Ba11, BJ11, BGGJ12, GB15]. We refer to [START_REF] Bal | Limiting models for equations with large random potential; a review[END_REF] for a review.

Third, there is a deep connection between the corrector studied in the present paper and so-called ∇ϕ interface models [START_REF] Funaki | Stochastic interface models[END_REF]. At a heuristic level, one can think of the corrector as the zero-temperature limit of such an interface model (with a bond-dependent potential). The scaling limit of the interface model with convex, homogeneous potential was shown to be the Gaussian free field [NS97, [START_REF] Giacomin | Equilibrium fluctuations for ∇ϕ interface model[END_REF][START_REF] Miller | Fluctuations for the Ginzburg-Landau ∇φ interface model on a bounded domain[END_REF]. In view of this, one may expect (as was suggested in [BB07, Conjecture 5]) the correlations of the corrector to be described by a Gaussian free field as well. However, our results show that such is not the case in general. One way to see this is to observe that the Fourier transform of

K ξ is (1.2) p • Q (ξ) p (p • A h p) 2 (p ∈ R d ),
while it should be of the form

(1.3) 1 p • Bp (p ∈ R d )
for some symmetric, positive definite matrix B, if the correlations were those of a Gaussian free field. By considering coefficients with small ellipticity ratio, one can produce examples where (1.2) cannot be reduced to (1.3). The proof given in [START_REF] Naddaf | On homogenization and scaling limit of some gradient perturbations of a massless free field[END_REF] that the interface model rescales to the Gaussian free field (and the proof of the dynamical version of this in [START_REF] Giacomin | Equilibrium fluctuations for ∇ϕ interface model[END_REF]) uses a Helffer-Sjöstrand representation of the correlations. We will also use this representation here, but with an important difference. In the case of the interface model, the Helffer-Sjöstrand representation readily enables to express the correlations of the interface as the averaged Green function of some operator, and the crux is then to show that this operator can be homogenized. In our case, the representation has a less clear interpretation. But it has to be so, since otherwise this would lead to Gaussian-free-field correlations.

Recently, a very interesting and direct connection was put forward in [START_REF] Biskup | Scaling limit for a class of gradient fields with nonconvex potentials[END_REF] between certain interface models with homogeneous but possibly non-convex potentials and the corrector considered here. The authors obtained the scaling limit of interface models with such potentials and zero tilt. They point out that the understanding of models with non-zero tilt could be obtained from the understanding of the scaling limit of the corrector. We refer to [BS11, Section 6] for more on this.

Organization of the paper. The precise setting and results of this paper are laid down in the next section. The Helffer-Sjöstrand representation of correlations is introduced in Section 3. Section 4 recalls several crucial estimates on the corrector and the Green function. The goal of Section 5 is to justify, in a weak sense, the two-scale expansion of the gradient of the Green function. The proof of the main result is then completed in Section 6.

Precise setting and results

We consider the (non-oriented) graph (Z d , B) with d 3, where B is the set of nearest-neighbor edges. Let (e 1 , . . . , e d ) be the canonical basis of Z d . For every edge e ∈ B, there exists a unique pair (e, i) ∈ Z d × {1, . . . d} such that e links e to e + e i . Given such a pair, we write e = e + e i . We call e the base point of the edge e. For f : Z d → R, we let ∇f : B → R be the gradient of f , defined by

∇f (e) = f (e) -f (e).
We write ∇ * for the formal adjoint of ∇, that is, for

F : B → R, ∇ * F : Z d → R is defined via (∇ * F )(x) = d i=1 F ((x -e i , x)) -F ((x, x + e i )).
For such F , we define AF (e) = a e F (e), where (a e ) are real numbers taking values in a compact subset of (0, +∞). The operator of interest is ∇ * A∇.

While a standard assumption for our purpose would be that (a e ) are independent and identically distributed, the technicalities of the proof will be reduced by assuming that they are also smooth in the following sense. We give ourselves a family (ζ e ) e∈B of independent standard Gaussian random variables (we write P for the law of this family on Ω = R B , and • for the associated expectation). The coefficients (a e ) e∈B are then defined by a e = a(ζ e ), where a : R → R is a fixed twice differentiable function with bounded first and second derivatives (and taking values in a compact subset of (0, +∞)).

Under these conditions, it is well-known that there exists a constant matrix A h such that ∇ * A∇ homogenizes over large scales to the continuous operator -∇ • A h ∇.

Let ξ be a fixed vector of R d . For µ > 0, let φ ξ,µ be the unique stationary solution of (2.1)

µφ ξ,µ + ∇ * A(ξ + ∇φ ξ,µ ) = 0.
It is proved in [START_REF] Gloria | An optimal variance estimate in stochastic homogenization of discrete elliptic equations[END_REF] that (recall that we assume d 3) φ ξ,µ converges in L 2 (Ω) to the unique stationary solution φ ξ of (2.2)

∇ * A(ξ + ∇φ ξ ) = 0.
The function φ ξ is called the (stationary) corrector in the direction ξ. We use φ i as shorthand for φ ei . In equations such as (2.2), ξ is to be understood as the function from B to R such that ξ(e) = ξ • (e -e).

Let Here is our main result.

Theorem 2.1 (structure of correlations). Recall that we assume d 3. Let E 0 be the set of edges with base-point 0 ∈ Z d , let G h : R d → R be the Green function of the (continuous-space) homogenized operator -∇

• A h ∇, let Q (ξ) = (Q (ξ)
jk ) 1 j,k d be the matrix defined by

(2.4) Q (ξ) jk = e∈E0 (e j + ∇φ j )(e)(ξ + ∇φ ξ )(e) ∂ e a e (L + 1) -1 ∂ e a e (e k + ∇φ k )(e)(ξ + ∇φ ξ )(e) ,
and let K ξ (x) be defined by (1.1). There exists a constant C < ∞ such that for every x ∈ Z d \ {0},

(2.5) | φ ξ (0) φ ξ (x) -K ξ (x)| C log 2 |x| * |x| d-1 .
Remark 2.2. When e j is interpreted as a function over B as in (2.4), it is to be understood as ξ is in (2.2), that is, e j (e) is 1 if the edge e is parallel to the basis vector e j , and is 0 otherwise.

Remark 2.3. The operator L is the infinitesimal generator of the Ornstein-Uhlenbeck semigroup on R B , and P is a reversible measure for the associated dynamics. For more general distributions of coefficients, one may replace L by the infinitesimal generator of the Glauber dynamics, that is, to keep the definition (2.3), but with ∂ e changed for ∂ e f = E[f | (a e ) e =e ] -f (in which case (L + 1) -1 must be replaced by L -1 in (2.4)). The setting we have chosen reduces the amount of technicality mostly by allowing us to use the chain rule for derivation.

Remark 2.4. We learn from Proposition 3.2 and Theorem 4.1 that the tensor Q (ξ) is well-defined. From the identity

(2.6) ξ • Q (ξ) ξ = e∈E0 (ξ + ∇φ ξ )(e)(ξ + ∇φ ξ )(e) ∂ e a e (L + 1) -1 ∂ e a e (ξ + ∇φ ξ )(e)(ξ + ∇φ ξ )(e) ,
which follows from the linearity of φ ξ in ξ, we learn that Q (ξ) is positive semi-definite. In particular, the Fourier transform of K ξ is non-negative.

Moreover, Q (ξ) is non-degenerate as soon as the derivative of the function a : R → R is everywhere positive. Indeed, if the expression (2.6) vanishes for ξ = ξ, the strict positivity of the operator implies that for any e ∈ E 0 , ∂ e a e (ξ + ∇φ ξ ) 2 (e) and thus (ξ + ∇φ ξ ) 2 (e) vanishes almost surely. This in turn implies that e∈E0 (ξ + ∇φ ξ )(e)a e (ξ + ∇φ ξ )(e) = ξ • A h ξ vanishes. By the non-degeneracy of the homogenized tensor A h , this yields as desired ξ = 0. The same argument also implies that the null space of Q (ξ) is contained in the hyperplane orthogonal to A h ξ.

Remark 2.5. There is no simple relation between the quartic form defined by Q (ξ) jk and the quadratic form A h , besides that ξ Q (ξ) ξ is bounded from below by (ξ •A h ξ) 2 up to a multiplicative constant. As was noted in the introduction, K ξ is not the Green function of a second-order operator in general. While its Fourier transform has the right sign and homogeneity, it is not the inverse of a quadratic form.

Remark 2.6. By polarization of the quartic form

Q (ξ)
jk in the ξ-variables, one also obtains a result for covariances φ ξ (0) φ ξ (x) with ξ = ξ.

Remark 2.7. We expect that at least if the environment is sufficiently mixing (as for instance when its correlations are of finite range), then there exists a matrix Q (ξ) [whose explicit expression may differ from that given in (2.4)] such that the largescale correlations of the correctors are described by (1.1) and (2.5).

Hellfer-Sjöstrand representation

Proposition 3.1 (Helffer-Sjöstrand representation of correlations, [HS94, Sj96, NS97]). Let f, g : Ω → R be centered square-integrable functions such that for every e ∈ B, ∂ e f and ∂ e g are in L 2 (Ω). We have

f g = e∈B ∂ e f (L + 1) -1 ∂ e g .
Proof. The claim is similar to (and simpler than) that obtained in [NS97, Section 2.1]. We recall the proof briefly for the reader's convenience. By density, we can restrict our attention to functions f, g that depend only on a finite number of (ζ e ) e∈B , and also by density, we may assume f and g to be smooth functions. Recalling the definition of L in (2.3), we arrive at

∂ e g = (L + 1)G e = (L + 1)∂ e u.
In particular, ∂ e u ∈ L 2 (Ω) and

f g = f L u = e ∂ e f ∂ e u = e ∂ e f (L + 1) -1 ∂ e g .
In order to conclude, it suffices to check that the range of the operator L is dense in the set of centered square-integrable functions. If g ∈ L 2 (Ω) is smooth, depends on a finite number of (ζ e ) e∈B and is in the orthogonal complement of Ran(L ), then

g L g = 0 = e |∂ e g| 2 ,
so g is constant. It follows that the orthogonal complement of Ran(L ) is the set of constant functions, and this completes the proof.

The following additional information on (L + 1) -1 will turn out to be useful.

Proposition 3.2 (contraction of L p ). For every p 2, the operator (L + 1) -1 is a contraction from L p (Ω) to itself.

Proof. Let Λ be a finite subset of B, and let F Λ the set of real functions of (ζ e ) e∈Λ .

We define H 1 Λ as the completion of the set of smooth functions in F Λ for the scalar product (u, v)

H 1 Λ = u v + e∈Λ ∂ e u ∂ e v .
For every

f ∈ H 1 Λ , there exists a unique u ∈ H 1 Λ such that (3.2) ∀v ∈ H 1 Λ , (u, v) H 1 Λ = f v
, and this is nothing but the weak formulation of the equation (L +1)u = f . For every ε > 0, let ψ ε (x) = ε -1 arctan(εx) be a "nice" (in particular, bounded) approximation of the function

x → x. One can check that if v ∈ H 1 Λ , then ψ ε (v |v| p-2 ) ∈ H 1 Λ . Hence, for u ∈ H 1 Λ satisfying (3.2), (u, ψ ε (u |u| p-2 )) H 1 Λ = f ψ ε (u |u| p-2
) , and we recall that

(u, ψ ε (u |u| p-2 )) H 1 Λ = u ψ ε (u |u| p-2 ) + e∈Λ ∂ e u ∂ e ψ ε (u |u| p-2 ) . Since u → ψ ε (u |u| p-2
) is an increasing function, it follows that for every e,

∂ e u ∂ e ψ ε (u |u| p-2 ) 0,
and thus

u ψ ε (u |u| p-2 ) f ψ ε (u |u| p-2
) . By the monotone convergence theorem, the left-hand side converges to |u| p = u p p as ε tends to 0. The right-hand side is bounded by

f p |ψ ε (u |u| p-2 )| p/p-1 1-1/p f p u p-1 p ,
where we have used |ψ ε (x)| |x|. We have thus shown

u p p f p u p-1 p ,
that is, u p f p , and this implies the theorem.

Using the fact that (L + 1) -1 is a contraction on L 2 (Ω), we deduce the following covariance estimate, which parallels those appearing in [NS97, NS98] (Brascamp-Lieb inequality), [GNO15, Definition 1] and [GO12, Lemma 3].

Corollary 3.3 (covariance estimate). For f and g as in Proposition

3.1, | f g | e∈B (∂ e f ) 2 1/2 (∂ e g) 2 1/2 .

Estimates on the corrector and the Green function

The aim of this section is to gather several known estimates on the Green function and on the corrector. Theorem 4.1 (existence and integrability of the corrector [START_REF] Gloria | An optimal variance estimate in stochastic homogenization of discrete elliptic equations[END_REF]). Recall that we assume d 3. For every µ > 0, there exists a unique stationary solution φ ξ,µ to equation (2.1). Moreover, for every p 1, |φ ξ,µ (0)| p and |∇φ ξ,µ (e)| p (e ∈ B) are uniformly bounded in µ > 0. The limit

φ ξ = lim µ→0 φ ξ,µ
is well-defined in L p (Ω) and is the unique stationary solution to (2.2).

A direct consequence of this result is: Proof. Let p 1. By Chebyshev's inequality,

P[|φ ξ (0)| x] E[|φ ξ (0)| p ] x p (x > 0),
so for any ε > 0, by a union bound,

P n -β max x∈Bn |φ ξ (x)| ε |B n | E[|φ ξ (0)| p ] (εn β ) p .
The first part of the corollary follows by taking p large enough and applying the Borel-Cantelli lemma. The second part is obtained in the same way.

We write G(x, y) for the Green function between points x and y in Z d , i.e. G(x, y) = (∇ * A∇)

-1 (x, y) (the dependence on (a e ) e∈B is kept implicit in the notation). For µ > 0, we also let G µ (x, y) = (µ + ∇ * A∇) -1 (x, y). Regularity theory ensures the following decay properties of the Green function (see for instance [Mo15, Proposition 3.6] for a proof adapted to our context).

Theorem 4.3 (pointwise estimates on the Green function). There exist

C < ∞, c > 0 and α > 0 such that for every µ ∈ [0, 1/2] and ζ ∈ Ω, (4.1) G µ (0, x) C |x| d-2 * e -c √ µ|x| (x ∈ Z d ), (4.2) |∇G µ (0, e)| C |e| d-2+α * e -c √ µ|e| (e ∈ B).
It was recently shown in [START_REF] Marahrens | Annealed estimates on the Green's function[END_REF] that, after averaging over the environment, the rates of decay of the gradient and mixed second gradient of the Green function behave as in the homogeneous case (see also [START_REF] Mourrat | First-order expansion of homogenized coefficients under Bernoulli perturbations[END_REF]Remark 11.2] for the fact that the estimates hold uniformly over µ).

Theorem 4.4 (annealed estimates on the gradients of the Green function [MO13]).

For every 1 p < ∞, there exists C < ∞ such that for every µ ∈ [0, 1/2] and every e, e ∈ B, Remark 4.7. Recalling that we assume a e to be of the form a(ζ e ) with a differentiable, we can rewrite ∂ e a e as a (ζ e ).

|∇G µ (0, e)| p 1/p C |e| d-1 * , |∇∇G µ (e,
Remark 4.8. Contrary to φ ξ,µ , the corrector φ ξ is not well-defined for every value of (ζ e ) ∈ Ω, but only on a set of full probability measure. In order to prove a statement similar to Proposition 4.6 for φ ξ instead of φ ξ,µ , it is thus necessary to show first that φ ξ is defined on a subset of Ω large enough that speaking of ∂ e φ ξ be meaningful. We will however not show this here, since for our purpose, it is always possible to bypass this problem by approximating φ ξ by φ ξ,µ , computing the derivatives, and then passing to the limit µ → 0. These two propositions can be proved by differentiating the defining equation of, respectively, the corrector and the Green function, namely

µφ ξ,µ + ∇ * A(ξ + ∇φ ξ,µ ) = 0, (µ + ∇ * A∇)G µ (x, •) = 1 x .
We refer to [START_REF] Gloria | An optimal variance estimate in stochastic homogenization of discrete elliptic equations[END_REF] for details.

Two-scale expansion of the Green function

Note that since we assume the coefficients to be independent and identically distributed, the law of the coefficients is invariant under the rotations that preserve the lattice, and A h is thus a multiple of the identity, say A h = a h Id. We define the discrete homogenized Green function G h as the unique bounded solution of the equation

∇ * A h ∇G h = 1 0 ,
where A h in the formula above acts as the multiplication by a h on every edge. For f : Z d → R and x ∈ Z d , we write ∇ j f (x) to denote f (x + e j ) -f (x). If instead we take e ∈ B, we understand ∇ j f (e) to mean ∇ j f (e), that is, the gradient of f along the edge parallel to the vector e j having the same base-point as e. The goal of this section is to prove the following quantitative two-scale expansion of the gradient of the Green function.

∂ b g p 1 |e -y| d-1 * |b -y| d * |y -x| d *     ,
where e -x denotes the translation of the edge e by the vector -x.

We define z :

Z d → R by (5.2) z(x) = G(0, x) -G h (x) - d j=1 φ j (x) ∇ j G h (x).
Proposition 5.4 (equation for z [PV81, GNO14]). Let A i (x) stand for a x,x+ei . Write ∇ 2 G h for the matrix with entries

∇ * i ∇ j G h (1 i, j d). Let R be the matrix with entries (R ij ) satisfying (R -A h ) ij = -A i (1 i j + ∇ i φ j ) (• -e i ) (1 i, j d),
where 1 i j = 1 i=j . For e ∈ B in the direction of e i , let

h(e) = -   A d j=1 φ j (• + e i )∇∇ j G h   (e),
and denote the R d×d -scalar product of two matrices M and N by M : N (that is, the sum of all terms after entry-wise product). We have

(5.3) ∇ * A∇z = R : ∇ 2 G h + ∇ * h.
Remark 5.5. The crucial feature of the right-hand side of (5.3) is that it involves only the second derivatives of G h (this is precisely what one aims for when defining z).

Another aspect that will turn out to be important for our purpose is that R(x) = 0. This follows from the fact (see e.g. [Kü83, (3.17)]) that the (i, j)-th entry of the homogenized matrix A h is equal to

A i (1 i j + ∇ i φ j ) = e i •
A(e j + ∇φ j ) . Proof. We follow the line of argument given in the first step of the proof of [GNO14, Theorem 1] (itself inspired by the first proof of [PV81, Theorem 3]). For f :

Z d → R, we write ∇ * i f (x) = f (x -e i ) -f (x).
To begin with, we observe that the following discrete Leibniz rules hold, for f, g : Z d → R:

∇ i (f g) = (∇ i f )g + f (• + e i )∇ i g, ∇ * i (f g) = (∇ * i f )g + f (• -e i )∇ * i g. Recall that by definition, ∇ * A∇G(0, •) = 1 0 = ∇ * A h ∇G h , and thus, ∇ * A∇(G(0, •) -G h ) = ∇ * (A h -A)∇G h .
Writing A h,i for the i-th diagonal coefficient of the (diagonal) matrix A h , we can express the right-hand side above as

d i=1 ∇ * i (A h,i -A i )∇ i G h .
We now need to compute (5.4)

∇ * A∇ (φ j ∇ j G h ) .
By the Leibniz rule,

∇ i (φ j ∇ j G h ) = (∇ i φ j )∇ j G h + φ j (• + e i )∇ i ∇ j G h .
Hence, the term in (5.4) is equal to

d i=1 ∇ * i [A i (∇ i φ j ∇ j G h + φ j (• + e i )∇ i ∇ j G h )] .
We can thus rewrite ∇ * A∇z as

d i=1    ∇ * i (A h,i -A i )∇ i G h - d j=1 ∇ * i [A i (∇ i φ j ∇ j G h + φ j (• + e i )∇ i ∇ j G h )]    = d i=1    A h,i ∇ * i ∇ i G h - d j=1 ∇ * i A i (1 i j + ∇ i φ j )∇ j G h + φ j (• + e i )∇ i ∇ j G h    ,
where we used the fact that A h is constant. By the definition of the corrector, we have

d i=1 ∇ * i A i (1 i j + ∇ i φ j ) = ∇ * A(e j + ∇φ j ) = 0,
so by the Leibniz rule,

d i,j=1 ∇ * i A i (1 i j + ∇ i φ j )∇ j G h = d i,j=1 A i (1 i j + ∇ i φ j ) (• -e i ) ∇ * i ∇ j G h ,
and the conclusion follows.

As a consequence, we get the following representation for z.

Proposition 5.6 (representation for z). For every x ∈ Z d ,

(5.5) z(x) = y∈Z d G(x, y) R : ∇ 2 G h (y) + b∈B ∇G(x, b)h(b).
Proof. Let z(x) denote the right-hand side of (5.5), which is well-defined by Corollary 4.2. Letting z = z -z, one can check thanks to Proposition 5.4 that ∇ * A∇z = 0. In particular, This sum tends to 0 as n tends to infinity. To see this, we come back to the definitions of z and z, given respectively in (5.2) and in the right-hand side of (5.5). Using Corollary 4.2, Theorem 4.3 and Proposition A.1 of the appendix, we obtain that for every β > 0, almost surely,

|z(x)| = o 1 |x| d-2-β (|x| → ∞), |∇z(e)| = o 1 |e| d-2+α-β (|e| → ∞)
(where α comes from Theorem 4.3), and the same relations hold for z replaced by z, and thus also for z replaced by z. Since d 3, we can take β > 0 sufficiently small to ensure that 2(d -2) + α -2β > d -1, and we obtain that the sum in (5.6) tends to 0 as n tends to infinity.

To sum up, we obtained that lim n→+∞ e∈Bn ∇z(e) • A∇z(e) = 0.

Since A is positive definite, we conclude that z is a constant. Now, both z and z tend to 0 at infinity, so in fact z = 0, and this concludes the proof.

Proof of Theorem 5.1. Let us first see that it suffices to show that (5.7)

| g ∇z(e) | C     g p log |e| * |e| d * + y∈Z d b∈B ∂ b g p 1 |e -y| d-1 * |y -b| d * |y| d *     .
Note that, by the Leibniz rule,

∇ i z(x) = ∇ i G(0, x) -∇ i G h (x) - d j=1 [∇ i φ j (x) ∇ j G h (x) + φ j (x + e i ) ∇ i ∇ j G h (x)] .
In order to prove that (5.7) implies (5.1), it is thus sufficient to show that

(5.8) | g φ j (x + e i ) ∇ i ∇ j G h (x) | C g p log |x| * |x| d * . This is true since |∇ i ∇ j G h (x)| |x| -d * , | g φ j (x + e i ) | g 2 φ j 2 ,
φ j 2 is finite by Theorem 4.1, and we assume p 2. We now turn to the proof of (5.7). From Proposition 5.6, we learn that

∇z(e) = y∈Z d ∇G(e, y)(R : ∇ 2 G h )(y) + b∈B

∇∇G(e, b)h(b).

We now proceed to show that each of the two terms (5.9)

y∈Z d g ∇G(e, y)(R : ∇ 2 G h )(y) , (5.10) b∈B | g ∇∇G(e, b)h(b) |
is bounded by the right-hand side of (5.7).

Step I.1. We begin with (5.9), which is the more delicate. As noted in Remark 5.5, the random variable R is centered, so the expectation appearing within the absolute value in (5.9) is in fact a correlation. We thus wish to apply Corollary 3.3 and write

(5.11) g ∇G(e, y)(R :

∇ 2 G h )(y) b∈B [∂ b (g ∇G(e, y))] 2 1/2 [∂ b (R : ∇ 2 G h )(y)] 2 1/2 .
However, recalling that

(R -A h ) ij (y) = -A i (1 i j + ∇ i φ j ) (y -e i ),
we see that a slight difficulty appears because we have not given a meaning to ∂ b φ j . As was anticipated in Remark 4.8, this need not bother us. If we formally extend Proposition 4.6 to the case µ = 0, we arrive at the formal expression

(5.12) ∂ b (R ij (y)) = ∂ b a b -1 b=(y-ei,y) (1 i j + ∇ i φ j )(y -e i ) + A i (y -e i )∇∇G(y -e i , b)(ξ + ∇φ j )(b) .
The point now is that although we do not wish to discuss the sense of (5.12) as a derivative, we can take it as a definition of the random variable ∂ b (R ij (y)), and observe that (5.11) holds. To see this, we approximate the left-hand side of (5.11) by introducing a small mass µ > 0. We introduce

(A µ h ) ij = A i (1 i j + ∇ i φ j,µ ) and R µ by setting (R µ -A µ h ) ij (y) = -A i (1 i j + ∇ i φ j,µ ) (y -e i ) (
where of course φ j,µ = φ ej ,µ ). We can now write the left-hand side of (5.11) as the limit as µ tends to 0 of

g ∇G(e, y)(R µ : ∇ 2 G h )(y) .
Applying Proposition 3.1 on this term is now legitimate, and by Proposition 4.6,

(5.13) ∂ b (R µ ij (y)) = ∂ b a b -1 b=(y-ei,y) (1 i j + ∇ i φ j,µ )(y -e i ) + A i (y -e i )∇∇G µ (y -e i , b)(ξ + ∇φ j,µ )(b) .
By taking the limit µ → 0, it follows that (5.11) holds with ∂ b R defined by (5.12).

Step I.2. By Hölder's inequality, it follows from Theorems 4.1 and 4.4 that

(∂ b R : ∇ 2 G h ) 2 (y) 1/2 1 |b -y| d * |y| d * ,
where stands for up to a multiplicative constant that only depends on d and the Lipschitz constant of a. On the other hand, using Proposition 4.9, we see that Using Hölder's inequality (in conjunction with the strict inequality p > 2) and Theorem 4.4, we are led to

[∂ b (g ∇G(e, y))] 2 1/2 ∂ b g p |e -y| d-1 * + g p |b -e| d * |b -y| d-1 * .
So we obtain from (5.11) the inequality

(5.14) g ∇G(e, y)(R : ∇ 2 G h )(y) b∈B ∂ b g p |e -y| d-1 * + g p |b -e| d * |b -y| d-1 * 1 |b -y| d * |y| d * ,
and the term appearing in (5.9) is bounded (up to a constant) by

y∈Z d b∈B ∂ b g p |e -y| d-1 * + g p |b -e| d * |b -y| d-1 * 1 |b -y| d * |y| d * .
To see that this is bounded by the right-hand side of (5.7), it suffices to observe that

y∈Z d 1 |b -y| 2d-1 * |y| d * 1 |b| d * and (5.15) b∈B 1 |b -e| d * |b| d * log |e| * |e| d * .
These two facts are proved in Proposition A.1 of the appendix.

Step II. We now turn to the analysis of (5.10). We note that b∈B

| g ∇∇G(e, b)h(b) | b∈B g 2 (∇∇G(e, b)h(b)) 2 1/2 .
Using the explicit form of h given by Proposition 5.4 together with Theorems 4.1 and 4.4, we arrive at

(∇∇G(e, b)h(b)) 2 1/2 1 |b -e| d * |b| d * .
In view of (5.15), we have shown that the term in (5.10) is bounded by a constant times

g 2 log |e| * |e| d * ,
which is a better bound than needed.

Proof of Theorem 2.1

Proof of Theorem 2.1. Our starting point is the identity (6.1)

φ ξ (0)φ ξ (x) = e∈B ∂ e φ ξ (0) (L + 1) -1 ∂ e φ ξ (x) , with (6.2) ∂ e φ ξ (y) = -∂ e a e ∇G(y, e)(ξ + ∇φ ξ )(e) (y ∈ Z d ).
As in Step I.1 of the proof of Theorem 5.1, we do not mean to discuss the meaning of ∂ e φ ξ (y) as a derivative of φ ξ (y). Rather, it suffices for our purpose to observe that the identity in (6.1) holds with ∂ e φ ξ (0) and ∂ e φ ξ (x) defined by (6.2). This follows easily by approximating φ ξ by φ ξ,µ , applying Propositions 3.1 and 4.6, and letting µ tend to 0.

Replacing ∂ e φ ξ (0) and ∂ e φ ξ (x) by their definitions, the summand in the righthand side of (6.1) becomes (6.3) ∂ e a e ∇G(0, e)(ξ + ∇φ ξ )(e) (L + 1) -1 ∂ e a e ∇G(x, e)(ξ + ∇φ ξ )(e) .

We see that two ∇G terms appear in this expectation. We will "pull out of the expectation" each of these ∇G terms using Theorem 5.1. These form the two first steps of the proof. The last step discusses how to replace ∇G h by its continuous-space counterpart ∇G h .

Step 1. Defining

g e (x) = ∂ e a e (ξ + ∇φ ξ )(e) (L + 1) -1 ∂ e a e ∇G(x, e)(ξ + ∇φ ξ )(e),
we see that we can rewrite the term in (6.3) as b,e (x) + g

(2)

b,e (x) + g

(3)

b,e (x) + g e a e ∇G(x, e)(ξ + ∇φ ξ )(e). As before, we do not wish to discuss the meaning of (6.5) as a derivative, but rather use the fact that if ∂ b g e (x) is defined in this way, then by the usual approximation argument, g e (x) ∇G(0, e) - Hence, up to a multiplicative constant, the left-hand side of (6.4) is smaller than the sum of the following two terms:

(6.6) e∈B log |e| * |e -x| d-1 * |e| d * , (6.7) e,b∈B y∈Z d 1 |b -e| d * 1 |e -x| d-1 * + 1 |b -x| d-1 1 |e -y| d-1 * |b -y| d * |y| d * .
By Remark A.2 of the appendix, the sum in (6.6) is dominated by a constant times the right-hand side of (6.4). As for the sum in (6.7), we can further split it into the sum of (6.8) , and the proof of (6.4) is complete.

Step 2. Recall that we have written φ ξ (0) φ ξ (x) as e∈B g e (x)∇G(0, e) , so we proved in Step 1 that (6.10) For j ∈ {1, . . . , d}, we let ge,j = ∂ e a e (ξ + ∇φ ξ )(e) (L + 1) -1 ∂ e a e (e j + ∇φ j )(e)(ξ + ∇φ ξ )(e), and observe that since (L + 1) -1 is symmetric, (6.13) g e (x) (e j + ∇φ j )(e) = ge,j ∇G(x, e) .

φ ξ (0) φ ξ (x) -
We let ∂ b ge,j = g(1) b,e,j + g(1) b,e,j + g(3) b,e,j + g(4) b,e,j , where

Q (ξ,e) jk ∇ k G h (e -x) log |e -x| * |e -x| d * + y∈Z d b∈B 1 |b -e| d * |e -y| d-1 * |b -y| d * |y -x| d * ,
and thus by (6.13), up to a multiplicative constant, the left-hand side of (6.11) is smaller than (6.14)

e∈B 1 |e| d-1 *     log |e -x| * |e -x| d * + y∈Z d b∈B 1 |b -e| d * |e -y| d-1 * |b -y| d * |y -x| d *     .
From Remark A.2 of the appendix, we have

e∈B 1 |e| d-1 * log |e -x| * |e -x| d * log 2 |x| * |x| d-1 * .
The remaining sum from (6.14) can be bounded, using Proposition A.1 repeatedly, by

y∈Z d e∈B log |e -y| * |e| d-1 * |e -y| 2d-1 * |y -x| d * y∈Z d 1 |y| d-1 * |y -x| d * log |x| * |x| d-1 * ,
and this finishes the proof of (6.11).

Step 3. Note that by the stationarity of the environment, the matrix Q (ξ,e) depends on the edge e only through its orientation. On the other hand, the quantities ∇ j G h (e) and ∇ j G h (e -x) depend on the edge e only through its base point. We also observe that the matrix Q (ξ) introduced in (2.4) is by definition e∈E0 Q (ξ,e) . Hence, the previous steps of the proof have led us, see (6.10) and (6.11), to (6.15)

φ ξ (0) φ ξ (x) - y∈Z d d j,k=1 ∇ j G h (y)Q (ξ) jk ∇ k G h (y -x) log 2 |x| * |x| d-1 * .
In order to complete the proof of Theorem 2.1, it thus suffices to show that

y∈Z d d j,k=1 ∇ j G h (y)Q (ξ) jk ∇ k G h (y -x) -K ξ (x) log |x| * |x| d-1 * ,
where K ξ was introduced in (1.1). We learn from Proposition A.3 of the appendix that

∇ j G h (y) - ∂G h ∂y j (y) 1 |y| d .
As a consequence,

y∈Z d \{0} 1 j,k d ∇ j G h (y)Q (ξ) jk ∇ k G h (y -x) - ∂G h ∂y j (y)Q (ξ) jk ∇ k G h (y -x) y∈Z d \{0} 1 |y| d |y -x| d-1 * log |x| * |x| d-1 * ,
where we used Proposition A.1 of the appendix in the last step. Similarly,

y∈Z d \{0,x} 1 j,k d ∂G h ∂y j (y)Q (ξ) jk ∇ k G h (y -x) - ∂G h ∂y j (y)Q (ξ) jk ∂G h ∂y k (y -x) log |x| * |x| d-1 * .
Moreover, one can check that

y∈Z d \{0,x} 1 j,k d ∂G h ∂y j (y)Q (ξ) jk ∂G h ∂y k (y -x) - y+[0,1] d ∂G h ∂y j (y )Q (ξ) jk ∂G h ∂y k (y -x) dy log |x| * |x| d-1 * .
In these computations, we have been forced to drop some terms indexed by y ∈ {0, x}. But it is easy to check that these terms are negligible, for example (In both statements, the sign hides a multiplicative constant that does not depend on x ∈ Z d .)

Proof. We give a unified proof of these two results, although it will be apparent that the proof of the first statement alone can be slightly simplified. We thus assume 1 |y -x| β * .

Up to a constant, this last sum is bounded by

1 if β > d, log |x| * if β = d, |x| d-β * if β < d.
Thus, this second contribution is always at most of the order of the first, and this concludes the proof. Let η(x) = (2π) -d/2 e -|x| 2 /2 . We note that

∂G h ∂x k (x) - ∂G h ∂x k * η (x) 1 |x| d ,
where * denotes the convolution. This can be seen for instance using the explicit formula for the Green function,

G h (x) = 1 (d -2)γ d | det(A h )| (x • A -1 h x) (d-2)/2
, where γ d denotes the area measure of the unit sphere. The regularization by convolution permits us to write down the Fourier representation

∂G h ∂x k * η (x) = 1 (2π) d R d - ip j p • A h p e -|p| 2
/2 e -ip•x dp.

In order to prove the proposition, it thus suffices to show that T (e -ipj -1)

s(p) e -ip•x dp - R d - ip j p • A h p e -|p| 2 /2 e -ip•x dp 1 |x| d .
We select a smooth cut-off function χ(p) that is equal to one near p = 0 and is compactly supported in T. We use it to split the left-hand side into

  Note that the commutator [∂ e , ∂ * e ] satisfies (3.1) [∂ e , ∂ * e ] = 1 e=e . Let us first assume that there exists a function u ∈ L 2 (Ω) such that g = L u. Writing G = ∂u, we observe that ∂ e g = ∂ e ∂ * G = e ∂ e ∂ * e G e = e ([∂ e , ∂ * e ] + ∂ * e ∂ e ) G e = G e + e ∂ * e ∂ e G e , where we used (3.1) and the fact that ∂ e G e = ∂ e ∂ e u = ∂ e G e in the last step.

  Corollary 4.2 (almost-sure control of the corrector). Let B n = {-n, . . . , n} d and let B n be the set of edges whose base-point is in B n . For every β > 0, almost surely, lim n→+∞ n -β max x∈Bn |φ ξ (x)| = 0 and lim n→+∞ n -β max e∈Bn |∇φ ξ (e)| = 0.

  e )| p 1/p C |e -e| d * . Remark 4.5. Notice that ∇G(x, e) (for x ∈ Z d and e ∈ B) denotes the gradient of G(x, •) evaluated at the edge e. Similarly, ∇∇G(e, e ) denotes the gradient of ∇G(•, e ) evaluated at the edge e.We conclude this section by recalling useful computations of vertical derivatives. The following two propositions are borrowed from [GO11, Lemmas 2.4 and 2.5].Proposition 4.6 (derivatives of the corrector [GO11]). For every µ > 0, x ∈ Z d and e ∈ B, the approximate corrector φ ξ,µ (x) is differentiable with respect to ζ e and ∂ e φ ξ,µ (x) = -∂ e a e ∇G µ (x, e)(ξ + ∇φ ξ,µ )(e).

Proposition 4. 9

 9 (derivatives of the Green function [GO11]). For every µ 0, x, y ∈ Z d and e ∈ B, the Green function G µ (x, y) is differentiable with respect to ζ e and ∂ e G µ (x, y) = -∂ e a e ∇G µ (x, e)∇G µ (y, e).

  Theorem 5.1 (quantitative two-scale expansion of the Green function). For every p > 2, there exists C < ∞ such that the following holds.If g : Ω → R is in L p (Ω) and is differentiable with respect to ζ b with ∂ b g ∈ L p (Ω)for every b ∈ B, then for every e ∈ B, (5.1) g ∇G(0, e) -d j=1 ∇ j G h (e) g (e j + ∇φ j )(e) Remark 5.2. Applying Theorem 5.1 with g = 1, we obtain that | ∇G(0, e) -∇G h (e)| C log |e| * |e| d * . Remark 5.3. By translation, under the assumptions of Theorem 5.1, we also have g ∇G(x, e) -d j=1∇ j G h (e -x) g (e j + ∇φ j )(e)

  e)| + |z(e)|) |∇z(e)|.

∂

  b (g ∇G(e, y)) = (∂ b g)∇G(e, y) + g ∂ b ∇G(e, y) = (∂ b g)∇G(e, y) -g (∂ b a b )∇∇G(e, b)∇G(y, b).

g

  e (x) ∇G(0, e) , and we wish to justify that (6.4) e∈B g e (x) ∇G(0, e) -d j=1 ∇ j G h (e) g e (x) (e j + ∇φ j )(e) log 2 |x| * |x| d-1 * . In order to apply Theorem 5.1 for this purpose, we need to compute ∂ b g e (x) for every b ∈ B. From the commutation relation in (3.1), it follows that ∂ b L = (L + 1) ∂ b , and thus ∂ b (L + 1) -1 = (L + 2) -1 ∂ b . From this observation, we get that (6.5) ∂ b g e (x) = g (1)

  (x) = -∂ e a e ∂ b a b ∇∇G(e, b)(ξ + ∇φ ξ )(b) (L + 1) -1 ∂ e a e ∇G(x, e)(ξ + ∇φ ξ )(e), g (2) b,e (x) = -∂ e a e (ξ + ∇φ ξ )(e) (L + 2) -1 ∂ e a e ∂ b a b ∇∇G(e, b) [∇G(x, b)(ξ + ∇φ ξ )(e) + ∇G(x, e)(ξ + ∇φ ξ )(b)] , g (3)b,e (x) = 1 e=b ∂ 2 e a e (ξ + ∇φ ξ )(e) (L + 1) -1 ∂ e a e ∇G(x, e)(ξ + ∇φ ξ )(e), andg (4)b,e (x) = 1 e=b ∂ e a e (ξ + ∇φ ξ )(e) (L + 2) -1 ∂ 2

∇

  j G h (e) g e (x) (e j + ∇φ j )(e) g e (x) p log |e| * |e| d * + y∈Z d b∈B ∂ b g e (x) p 1 |e -y| d-1 * |b -y| d * |y| d * . From Proposition 3.2 and Theorems 4.1 and 4.4, we learn that g e (x) p 1 |e -x| d-1 * and ∂ b g e (x) p 1 |b -e| d * 1 |e -x| d-1 * + 1 |b -x| d-1 * .

∇.∇∂

  j G h (e) g e (x) (e j + ∇φ j )(e) log 2 |x| * |x| d-1 * j G h (e) g e (x) (e j + ∇φ j )(e) -d k=1 ∇ j G h (e)Q (ξ,e) jk ∇ k G h (e -x)log 2 |x| * |x| d-1 *, e a e (e j + ∇φ j )(e)(ξ + ∇φ ξ )(e) (L + 1) -1 ∂ e a e (e k + ∇φ k )(e)(ξ + ∇φ ξ )(e) .

g( 1

 1 ) b,e,j = -∂ e a e ∂ b a b ∇∇G(e, b)(ξ +∇φ ξ )(b) (L +1) -1 ∂ e a e (e j +∇φ j )(e)(ξ +∇φ ξ )(e), g(2) b,e,j = -∂ e a e ξ + ∇φ ξ )(e) (L + 2) -1 ∂ e a e ∂ b a b ∇∇G(e, b) [(e j + ∇φ j )(b)(ξ + ∇φ ξ )(e) + (e j + ∇φ j )(e)(ξ + ∇φ ξ )(b)] , g(3) b,e,j = 1 e=b ∂ 2 e a e (ξ + ∇φ ξ )(e) (L + 1)

  jk ∂G h ∂y k (u -x) du 1 |x| d-1 * (x ∈ Z d \ {0}),so the proof is complete.Appendix A. Basic estimates on discrete convolutions and Green functionsProposition A.1. For every α > d and β ∈ (0, α],

Remark A. 2 .

 2 The proof of Proposition A.1 can be adapted to yield, for every β ∈ (0, d], y∈Z d log |y| * |y| d * |y -x| β * log 2 |x| * |x| β * . Proposition A.3. For every k ∈ {1, . . . , d},∇ k G h (x) -∂ ∂x k G h (x) 1 |x| d .Proof. Recall that A h is a diagonal matrix, the diagonal entries of which we denote by A h,1 , . . . , A h,d . For p ∈ [-π, π] d , lets(p) = 2 d j=1 A h,j (1 -cos(p j )).Using Fourier transforms, one can represent the Green function G h asG h (x) = 1 (2π) d T e -ip•x s(p) dp, where T = [-π, π] d . Similarly, ∇ j G h (x) = 1 (2π) d T (e -ipj -1)s(p) e -ip•x dp.

T ( 1

 1 -χ)(p) (e -ipj -1)s(p) e -ip•x dp andR d f (p) e -ip•x dp,wheref (p) = χ(p) (e -ipj -1) s(p) + ip j p • A h p e -|p| 2 /2can be considered to be defined on all R d . By the properties of χ,(1 -χ)(p) (e -ip j -1) s(p)is a smooth periodic function on T, so that we obtain by integrations by parts thatT (1 -χ)(p) (e -ipj -1) s(p) e -ip•x dpdecays faster than any negative power of |x|. Hence it suffices to show that (A.1)R d f (p) e -ip•x dp 1 |x| d .One can decompose f asf (p) = -p 2 j 2p • A h p + f (p),so that f is "more regular" than f close to the origin. One can then show by integration by parts that ) e -ip•x dp 1 |x| d for any x ∈ R d . Since (∂ 2 G h /∂x 2 j * η)(x) |x| -d , the proof is complete.

  ∂ e denote the weak derivative with respect to the random variable ζ e , which we may call a vertical derivative. The formal adjoint of ∂ e is ∂ * e = -∂ e + ζ e . We write ∂f = (∂ e f ) e∈B . For F = (F e ) e∈B , we write ∂ * F = e ∂ * We write |x| for the L 2 -norm of x ∈ Z d . In order to keep light notation, we let |x| * = |x| + 2 (so that for instance log |x| * is bounded away from 0).

		e F e , and we let
	(2.3)	L = ∂

* ∂.

  = 1 e=b ∂ e a e (ξ + ∇φ ξ )(e) (L + 2) -1 ∂ 2 e a e (e j + ∇φ j )(e)(ξ + ∇φ ξ )(e).

	and
	g(4) b,e,j As before (and because of Remark 5.3), this definition ensures that
	d
	ge,j ∇G(x, e) -	∇ k G h (e -x) ge,j (e k + ∇φ k )(e)
	k=1
	ge,j p	log |e -x| * |e -x| d *	+	y∈Z d	∂ b ge,j p	|e -y| d-1 *	1 |b -y| d * |y -x| d *	.
				b∈B
	Moreover, we infer from Proposition 3.2 and Theorems 4.1 and 4.4 that for any
	1 p < ∞ (and thus in particular the p > 2 needed above)
			ge,j p 1
	and	∂ b ge,j p	1 |b -e| d *	.
	Since
		ge,j (e k + ∇φ k )(e) = Q	(ξ,e) jk ,
	we obtain that
	ge,j ∇G(x, e) -

-1 ∂ e a e (e j + ∇φ j )(e)(ξ + ∇φ ξ )(e), d k=1

Acknowledgements. We would like to thank Marek Biskup for stimulating discussions about this problem.


Autonomous Machine Learning F. Alexandre Inspiration from human learning sets the focus on one essential but poorly studied characteristic of learning: Autonomy.

One remarkable characteristic of human learning is that, whereas we are in general not excellent in one specific domain, we are quite good in most of them, and able to adapt when a new problem appears. We are versatile and adaptable, which are critical properties for autonomous learning: we can learn in a changing and uncertain world. With neither explicit labels, nor data preprocessing or segmentation, we are able to pay attention to important information and neglect noise. We define by ourselves our goals and the means to reach them, self-evaluate our performances and re-exploit previously learned knowledge and strategies in some different context. In contrast, recent advances in Machine Learning exhibit impressive results, with powerful algorithms surpassing human performances in some very specific domains of expertise, but these models still have very poor autonomy.

Our Mnemosyne Inria project-team is working in the Bordeaux Neurocampus with medical and neuroscientist teams to develop systemic models in computational neuroscience, focusing on these original characteristics of human learning. Whereas our primary goal is to develop models of the different kinds of memory in the brain and of their interactions, with the objective to exploit them to study neurodegenerative diseases, another important outcome of our work is to propose original models in Machine Learning integrating some of these important characteristics.

We believe that important steps toward autonomous learning can be made along these lines of research: Developing an interacting system of memories: Specific circuits in the brain are mobilized to learn explicit knowledge and others to learn procedures. Besides modeling these circuits, studying their interactions is crucial to understand how one system can supervise another, resulting in a more autonomous learning. In the domain of perceptual learning in the medial temporal lobe, we model episodic memories storing important events in one trial, and forming later, by consolidation in other circuits, new semantic categories. In the domain of decision-making in the loops between the prefrontal cortex and the basal ganglia, we model cerebral mechanisms by which goal-directed behavior relying on explicit evaluation of expected rewards can later become habits, automatically triggered with less flexibility but increased effectiveness.

Coping with uncertainty:

We learn the rules that govern the world and consider it uncertain for two main reasons: it can be predictable up to a certain level (stochastic rules) or non-stationary (changing rules). Whereas standard probabilistic models are rather good at tackling the first kind of uncertainty, nonstationarity in a dynamic world raises more difficult problems. We are studying how regions of the medial prefrontal cortex are detecting and evaluating the kind and the level of uncertainty by monitoring recent history of performance at managing correctly incoming events. These regions are also reported to activate the release of neuromodulators like monoamines, known to play a central role in adaptation to uncertainties [START_REF] Yu | Uncertainty, Neuromodulation and Attention[END_REF]. In a nutshell, instead of developing large sets of circuits to manage uncertainty as stable rules in various contexts, the cerebral system has rather developed a general-purpose system adaptable to uncertainty with hyperparameters sensitive to meta-learning by neuromodulation, as we are currently trying to understand more precisely [START_REF] Carrere | Modeling the sensory roles of noradrenaline in action selection[END_REF].

Embodiment for emotional learning:

One important source of autonomy is due to our body itself that tells us what is good or bad for us; what must be searched or avoided. Pavlovian learning is modeled to detect and learn to predict biologicallysignificant aversive and appetitive (emotional) stimuli which are key targets for attentional processing and for the organization of behavior. This learning can be done autonomously if the model of the cerebral system is associated to a substrate corresponding to the body, including sensors for pain and pleasure. A step further, we extend the study of the Pavlovian rules to integrate the effects of Pavlovian responses onto the body and the neuromodulatory system.

From motivation to self-evaluation:

Considering the brain and the body also introduces physiological needs, fundamental to introduce internal goals in addition to the external goals evoked above. This is the basis for renewed approaches regarding reinforcement learning, defining criteria more complex than a simple scalar representing an abstract reward. In humans, another important source of information for learning autonomously is based on selfevaluation of the performances. It is noticeable that both motivation and self-evaluation processing are central in cognitive control [3] and reported to be located in the anterior part of the prefrontal cortex, as we endeavor to integrate in our models.

In addition to developing models to explore each of these mechanisms in interaction with neuroscience and medicine, we also integrate them in a common platform defining the adaptive characteristics of an autonomous agent exploring an unknown virtual world together with the characteristics of its artificial body. Beyond Machine Learning, this numerical testbed is also a precious simulation tool for our medical and neuroscientist colleagues.