Gilles Lebeau
email: lebeau@unice.fr

Laurent Michel
email: lmichel@unice.fr

Spectral analysis of hypoelliptic random walks

We study the spectral theory of a reversible Markov chain associated to a hypoelliptic random walk on a manifold M . This random walk depends on a parameter h ∈]0, h 0 ] which is roughly the size of each step of the walk. We prove uniform bounds with respect to h on the rate of convergence to equilibrium, and the convergence when h → 0 to the associated hypoelliptic diffusion.

Introduction and Results

The purpose of this paper is to study the spectral theory of a reversible Markov chain associated to a hypoelliptic random walk on a manifold M . This random walk will depend on a parameter h ∈]0, h 0 ] which is roughly the size of each step of the walk. We are in particular interested, as in [DLM11] and [DLM11], to get uniform bounds with respect to h, on the rate of convergence to equilibrium. The main tool in our approach is to compare the random walk on M with a natural random walk on a nilpotent Lie group. This idea was used by Rotschild-Stein [START_REF] Rothschild | Hypoelliptic differential operators and nilpotent groups[END_REF] to prove sharp hypoelliptic estimates for some differential operators.

Let M be a smooth, connected, compact manifold of dimension m, equipped with a smooth volume form dµ such that M dµ = 1. We denote by µ the associated probability on M . Let X = {X 1 , . . . , X p } be a collection of smooth vector fields on M . Denote G the Lie algebra generated by X . In all the paper we assume that the X k are divergence free with respect to dµ ∀k = 1, . . . , p,

M X k (f )dµ = 0, ∀f ∈ C ∞ (M ) (1.1)
and that they satisfy the Hörmander condition ∀x ∈ M, G x = T x M.

(1.2)

Let r ∈ N be the smallest integer such that for any x ∈ M , G x is generated by commutators of length at most r. For k = 1, . . . , p and x 0 ∈ M , denote R ∋ t → e tX k x 0 the integral curve of X k starting from x 0 at t = 0.

Let h ∈]0, h 0 ] be a small parameter. Let us consider the following simple random walk x 0 , x 1 , ..., x n , ... on M , starting at x 0 ∈ M : at step n, choose j ∈ {1, ..., p} at random and t ∈ [-h, h] at random (uniform), and set x n+1 = e tX j x n .

Due to the condition div(X j ) = 0, this random walk is reversible for the probability µ on M . It is easy to compute the Markov operator T h associated to this random walk: for any bounded and measurable function f : M → R define

T k,h f (x) = 1 2h h -h
f (e tX k x)dt (1.3) Since the vector fields X k are divergence free, for any f, g, we have

M T k,h f (x)g(x)dµ = M f (x)T k,h g(x)dµ.
and the Markov operator associated to our random walk is

T h f (x) = 1 p p k=1 T k,h f (x) (1.4)
One has T h (1) = 1, T h L ∞ →L ∞ = 1, and T h can be uniquely extended as a bounded self-adjoint operator on L 2 = L 2 (M, dµ) such that T h L 2 →L 2 = 1. In the following, we will denote t h (x, dy) the distribution kernel of T h , and t n h the kernel of T n h . Then, by construction, the probability for the walk starting at x 0 to be in a Borel set A after n step is equal to

P (x n ∈ A) = A t n h (x 0 , dy)
The goal of this paper is to study the spectral theory of the operator T h and the convergence of t n h (x 0 , dy) towards µ as n tends to infinity. Since T h is Markov and self adjoint, its spectrum is a subset of [-1, 1]. We shall denote by g(h) the spectral gap of the operator T h . It is defined as the best constant such that the following inequality holds true for all u ∈ L 2

u 2 L 2 -u, 1 2 L 2 ≤ 1 g(h) u -T h u, u L 2 (1.5)
The existence of a non zero spectral gap means that 1 is a simple eigenvalue of T h , and the distance between 1 and the rest of the spectrum is equal to g(h). Our first result is the following Theorem 1.1 There exists h 0 > 0, δ 1 , δ 2 > 0, A > 0, and constants C i > 0 such that for any h ∈]0, h 0 ], the following holds true.

i) The spectrum of T h is a subset of [-1 + δ 1 , 1], 1 is a simple eigenvalue of T h , and Spec(T h ) ∩ [1δ 2 , 1] is discrete. Moreover, for any 0 ≤ λ ≤ δ 2 h -2 , the number of eigenvalues of T h in [1h 2 λ, 1] (with multiplicity) is bounded by C 1 (1 + λ) A .

ii) The spectral gap satisfies

C 2 h 2 ≤ g(h) ≤ C 3 h 2 (1.6)
and the following estimate holds true for all integer n sup x∈Ω t n h (x, dy)µ T V ≤ C 4 e -ng(h) (1.7)

Here, for two probabilities on M , νµ T V = sup A |ν(A)µ(A)| where the sup is over all Borel sets A, is the total variation distance between ν and µ.

We describe now the spectrum of T h near 1. Let H 1 (X ) be the Hilbert space H 1 (X ) = {u ∈ L 2 (M ), ∀j = 1, . . . , p, X j u ∈ L 2 (M )}

Let ν be the best constant such that the following inequality holds true for all u ∈ H 1 (X )

u 2 L 2 -u, 1 2 L 2 ≤ E(u) ν , (1.8)
where

E(u) = 1 6 M p k=1
|X k u| 2 dµ (1.9)

By the hypoelliptic theorem of Hörmander (see [START_REF] Hörmander | The analysis of linear partial differential operators[END_REF], Vol 3), one has H 1 (X ) ⊂ H s (M ), for some s > 0. On the other hand, standard Taylor expansion in formula (1.3) show that for any fixed smooth function g ∈ C ∞ (M ), one has the following convergence in the space C ∞ (M ) lim h→0 1 -T h h 2 g = L(g), (1.10)

where the operator L = -1 6p k X 2 k is the positive Laplacian associated to the Dirichlet form E(u). It has a compact resolvant and spectrum ν 0 = 0 < ν 1 = ν < ν 2 < .... Let m j be the multiplicity of ν j . One has m 0 = 1 since Ker(L) is spaned by the constant function 1 thanks to the Chow theorem ([Cho39]). In fact, for any x, y ∈ M there exists a continuous curve connecting x to y which is a finite union of pieces of trajectory of one of the fields X j . Theorem 1.2 One has lim h→0 h -2 g(h) = ν (1.11)

Moreover, for any R > 0 and ε > 0 such that the intervals [ν jε, ν j + ε] are disjoint for ν j ≤ R, there exists h 1 > 0 such that for all h ∈]0, h 1 ]

Spec( 1 -T h h 2 )∩]0, R] ⊂ ∪ j≥1 [ν j -ε, ν j + ε] (1.12)
and the number of eigenvalues of 1-T h h 2 with multiplicities, in the interval [ν jε, ν j + ε], is equal to m j .

The paper is organized as follows:

In section 2, we recall some basic facts on nilpotent Lie groups, and we recall the Goodman version (see [START_REF] Goodman | Lifting vector fields to nilpotent Lie groups[END_REF]) of one of the main results of the Rotschild-Stein paper.

In section 3, the main result is the proposition 3.1 which gives a lower bound on a suitable power T P h of T h . This in particular allows to get a first crude but fundamental bound on the L ∞ norms of eigenfunctions of T h associated to eigenvalues close to 1.

Section 4 is devoted to the study of the Dirichlet form associated to our random walk. The fundamental result of this section is proposition 4.1. It allows to separate clearly the spectral theory of T h in low and high frequencies with respect to the parameter h. Many tools in this section are essentially an adaptation to the semi-classical setting of the ideas contained in the Rotschild-Stein paper [START_REF] Rothschild | Hypoelliptic differential operators and nilpotent groups[END_REF].

Section 5 is devoted to the proof of theorems 1.1 and 1.2. With propositions 3.1 and 4.1 in hands, the proof follows the strategy of [DLM11] and [START_REF] Diaconis | Metropolis algorithm on convex polytops[END_REF], but with some differences and simplifications. This section contains also a paragraph on the Fourier analysis associated to T h that will be useful in 6.

Section 6 is devoted to the proof of the convergence when h → 0 of our Markov chain to the hypoelliptic diffusion on the manifold M associated to the generator L = -1 6p k X 2 k . This is probably a well known result for specialists, but we have not succeed to find a precise reference. Since this convergence follows as a simple byproduct of our estimates, we decide to include it in the paper.

Finally, the appendix contains two lemmas. Lemma 7.1 shows how to deduce from proposition 4.1 a Weyl type estimate on the eigenvalues of T h in a neighborhood of 1. Lemma 7.2 is an elementary cohomological lemma on the Schwartz space of the nilpotent Lie algebra N .

The lifted operator to a nilpotent Lie algebra

We will use the notation N q = {1, . . . , q}. For any family of vector fields Z 1 , . . . , Z p and any multi-index α = (α 1 , . . . , α k ) ∈ N k p denote |α| = k the length of α and let

Z α = H α (Z 1 , ..., Z p ) = [Z α 1 , [Z α 2 , . . . [Z α k-1 , Z α k ] . . .] (2.1)
Let Y 1 , . . . , Y p be a system of generators of the free lie algebra with p generators F and let A ∞ be a set of multi-indexes such that (Y α ) α∈A ∞ is a basis of F.

Introduce N the free up to step r nilpotent Lie algebra generated by p elements Y 1 , . . . , Y p , and let N be the corresponding simply connected Lie group. We have the decomposition

N = N 1 ⊕ . . . ⊕ N r (2.2)
where N 1 is generated by Y 1 , . . . Y p and N j is spanned by the commutators

Y α = H α (Y 1 , ..., Y p ) with |α| = j for 2 ≤ j ≤ r. Let A = {α ∈ A ∞ , |α| ≤ r} and A r = {α ∈ A, |α| = r}.
The family (Y α ) α∈A is a basis for N and for any r ∈ N r , {Y α , α ∈ A r } is a basis of N r . We denote by D = ♯A the dimension of N . The action of R + on N is given by

t.(v 1 , v 2 , ..., v r ) = (tv 1 , t 2 v 2 , ..., t r v r ) An homogeneous norm | |v| | which is smooth in N \ o N is given by | |v| | = ( j |v j | (2r!)/j ) 1/(2r!)
where |v j | is an euclidian norm on N j , and

Q = j dim(N j )
is the quasi homogeneous dimension of N . We will identify the Lie agebra N with the Lie group N by the exponential map, i.e the product law a.b on N is given by exp(a.b) = exp(a)exp(b).

In particular, one has with this identification a -1 = -a for all a ∈ N . To avoid notational confusion, we will use sometime the notation e = o N , so that a.e = e.a = a for all a ∈ N . For Y ∈ T e N ≃ N , we denote by Ỹ the left invariant vector field on

N such that Ỹ (o N ) = Y , i.e Ỹ (f )(x) = d ds (f (x.sY )| s=0
The right invariant vector field on N such that Z(o N ) = Y is defined by

Z(f )(x) = d ds (f (sY.x)| s=0
Here, sY is the usual product of the vector Y ∈ N by the scalar s ∈ R. For a ∈ N , let τ a be the diffeomorphism of N defined by τ a (u) = a.u. One has

Ỹ (a) = dτ a (e)(Y ) Example 2.1 The standard 3d-Heisenberg group is N = R 2 x,y ⊕ R t ≃ R 3 , with the product law (x, y, t).(x ′ , y ′ , t ′ ) = (x + x ′ , y + y ′ , t + t ′ + xy ′ -yx ′ )
and the left invariant vector fields associated respectively to the vectors (1, 0, 0), (0, 1, 0) and (0, 0, 1) are in that case

Ỹ1 = ∂ ∂x -y ∂ ∂t , Ỹ2 = ∂ ∂y + x ∂ ∂t , and
∂ ∂t = 1 2 [ Ỹ1 , Ỹ2 ]
In general, for x = (x 1 , ..., x r ) and y = (y 1 , ..., y r ), x j , y j ∈ N j , the product law is given by (x 1 , ..., x r ).(y 1 , ..., y r ) = (z 1 , ..., z r )

z j = x j + y j + P j (x <j , y <j ) (2.3)
with the notation x <j = (x 1 , ..., x j-1 ), and where P j is a polynomial of degree j with respect to the homogeneity on N , i.e P j ((t.x) <j , (t.y) <j ) = t j P j (x <j , y <j ) which is compatible with the identity t.(x.y) = (t.x).(t.y).

Let λ : N → G be the unique linear map such that for any α ∈ A, λ(Y α ) = X α . Then λ is a Lie homomorphism "up to step r":

λ([Y α , Y β ]) = [X α , X β ] (2.4)
for any multi-indexes α, β such that |α| + |β| ≤ r. Let x 0 ∈ M . There exists a subset A x 0 ⊂ A such that (X α (x)) α∈Ax 0 is a basis of T x M for any x close to x 0 . Therefore, there exists a neighborhood Ω 0 of the origin o N in N and a neighborhood V 0 of x 0 in M such that the map Λ u) x 0 ) is injective. Since Λ is a submersion, there exists a system of coordinates θ : R m × R n → N defined near o N , where m + n = D, such that Λθ : R m → M is a system of coordinates near x 0 and in these coordinates one has Λ(x, y) = x. We thus may assume that in these coordinates one has Ω 0 = V 0 × U 0 where U 0 is a neighborhood of 0 ∈ R n .

Λ : u = α∈A u α Y α ∈ Ω 0 → e λ(u) x 0 = e α∈A uαX α x 0 is a submersion from Ω 0 onto V 0 , and the map W x 0 : C ∞ (V 0 ) → C ∞ (Ω 0 ) defined by W x 0 f (u) = f (e λ(
Example 2.2 Take for example the two vectors fields in R 2 , X 1 = ∂ x , X 2 = x∂ y so that [X 1 , X 2 ] = ∂ y . Then on take for N the 3d-Heisenberg group, and the map λ is given by, with

T = 2∂ t = [Y 1 , Y 2 ] λ(u 1 Y 1 + u 2 Y 2 + u 3 T ) = u 1 X 1 + u 2 X 2 + u 3 [X 1 , X 2 ] = u 1 ∂ x + (u 3 + u 2 x)∂ y Thus we get e λ(u) (x, y) = (x + u 1 , y + u 3 + u 2 x + 1 2 u 1 u 2 ) (2.5) Let I h = {|u 1 | < h, |u 2 | < h, |u 3 | < h 2 }. One has V ol(I ǫ,h ) = 8h 4 .
Observe on this example that the set Bh,(x,y) = {e λ(u) (x, y), u ∈ I h }, when (x, y) is fixed and h small, has volume of order: h 2 when x = 0, and h 3 when x = 0.

Let us now recall the notion of order of a vector field used in [START_REF] Rothschild | Hypoelliptic differential operators and nilpotent groups[END_REF] and [START_REF] Goodman | Lifting vector fields to nilpotent Lie groups[END_REF]. Denote {δ t } t>0 the one parameter group of dilating automorphisms on N :

δ t Y α = t |α| Y α .
Let Ω be a compact neighborhood of o N in N . For any m ∈ N, let

C ∞ m = {u ∈ C ∞ (Ω, R), f (u) = O(| |u| | m )}.
We have the filtration

C ∞ (Ω) = C ∞ 0 ⊇ C ∞ 1 ⊇ . . ., and C ∞ m .C ∞ n ⊆ C ∞ m+n . Let T : C ∞ (Ω) → C ∞ (Ω). We say that T is of order less than k at 0, if T (C ∞ m ) ⊆ C ∞ m-k for all integers m ≥ 0. If ∂ α denotes the differentiation in the direction Y α , then a vector field T = α ϕ α ∂ α is of order ≤ k iff ϕ α ∈ C ∞ |α|-k for all α, with the convention C ∞ m = C ∞ 0 for m ≤ 0.
The following result is the Goodman version of one of the results of the article [START_REF] Rothschild | Hypoelliptic differential operators and nilpotent groups[END_REF] by L.Rothschild and E.Stein.

Theorem 2.3 Decreasing Ω 0 if necessary, there exists C ∞ vector fields Z 1 , . . . , Z p on Ω 0 such that for any α ∈ A we have i)

Z α W x 0 = W x 0 X α ii) Z α = Y α + R α , where R α is a vector field of order ≤ |α| -1 at 0. iii) Z α = H α (Z 1 , ..., Z p ) for all α ∈ A.
Observe that in the previous coordinate system (x, y) on Ω 0 , one can write for α ∈ A

X α = j a α,j (x) ∂ ∂x j , Z α = j a α,j (x) ∂ ∂x j + l b α,l (x, y) ∂ ∂y l (2.6)
As an obvious consequence of this theorem, we have the following, with W = W x 0 , and λ(u) = α∈A u α Z α . Proposition 2.4 Let f ∈ C 0 (V 0 ) and let ω 0 ⊂⊂ Ω 0 be a neighborhood of o N . Then, there exists r 0 > 0 such that for all | |u| | ≤ r 0 , and v ∈ ω 0 , we have

(W f )(e λ(u) v) = W (f u )(v) (2.7)
where the function f u is defined near x 0 by f u (x) = f (e λ(u) x).

Using this proposition, we can easily compute the action of W on the operator T h acting on functions with support close to x 0 . We get immediatly

W T h = T h W, T h = 1 p p k=1 T k,h (2.8)
where for u ∈ N small.

T k,h g(u) = 1 2h h -h
g(e tZ k u)dt (2.9)

Using the notation T α = T α k ,h . . . T α 1 ,h for any multi-index α = (α 1 , . . . , α k ) we get for any

u ∈ N close to o N such that Λ(u) = x T α f (x) = W (T α f )(u) = 1 (2h) k [-h,h] k (W f )(e t 1 Zα 1 . . . e t k Zα k u)dt 1 . . . dt k (2.10)

Rough bounds on eigenfunctions

Let us recall from section 2, that for u = α∈A u α Y α ∈ N , the vector field λ(u) on M is defined by λ(u) = α∈A u α X α . Let ǫ > 0 and I ǫ,h be the neighborhood of o N in N defined by

I ǫ,h = {u = α∈A u α Y α , u α ∈] -ǫh |α| , ǫh |α| [ }
For any x ∈ M we define a positive measure S ǫ h (x, dy) on M by the formula

∀f ∈ C 0 (M ), f (y)S ǫ h (x, dy) = h -Q u∈I ǫ,h f (e λ(u) x) du (3.1)
where du = Π α du α is the left and right invariant Haar measure on N . Let us introduce the numerical sequence (b n ) n∈N * defined by b 1 = 1 and b n+1 = 2b n + 2, so that for all n ∈ N * , we have b n = 3.2 n-1 -2. For all r = 1, . . . , r denote a r = ♯A r = dim N r , and let P = r r=1 a r b r .

Proposition 3.1 There exists ǫ > 0, c > 0 and h 0 > 0 such that for all h ∈]0,

h 0 ], x ∈ M t P h (x, dy) = ρ h (x, dy) + cS ǫ h (x, dy) (3.2)
where ρ h (x, dy) is a non-negative Borel measure on M for all x ∈ M .

Remark 3.2 As in [DLM11], one can deduce from proposition 3.1 that the inequality (3.2) holds true for t N h (x, dy) as soon as N ≥ P , eventually with different constants ǫ > 0, c > 0 and h 0 > 0 depending on N .

Before proving this proposition, let us give two simple but fundamental corollaries. Like in [DLM11], these two corollaries will play a key role in the proof of theorems 1.1 and 1.2. Here, we use the same notation for a bounded measurable family in x of non negative Borel measure k(x, dy) and the corresponding operator

f → K(f )(x) = f (y)k(x, dy) acting on L ∞ .
Corollary 3.3 There exists h 0 > 0 and γ < 1 such that for all h ∈]0, h 0 ] and all

x ∈ M ρ h (x, dy) L ∞ →L ∞ ≤ γ < 1 (3.3)
Proof. By definition, the non-negative measure ρ h is given by ρ h (x, dy) = t P h (x, dy) -cS ǫ h (x, dy). Therefore

| M f (x)dρ h (x, dy)| ≤ f L ∞ M dρ h (x, dy) ≤ f L ∞ (1 -c inf x∈M M S ǫ h (x, dy)) (3.4)
since t P h (x, dy) is a Markov kernel. From (3.1), one has M S ǫ h (x, dy) = h -Q meas(I ǫ,h ) = (2ǫ) D . Combined with (3.4), this implies the result.

Corollary 3.4 Let a ∈]γ P , 1] be fixed. There exists C = C a > 0 such that for any λ ∈ [a, 1] and any f ∈ L 2 (M, dµ) we have

T h f = λf =⇒ f L ∞ ≤ Ch -Q 2 f L 2 (3.5) Proof. Suppose T h f = λf , then T P h f = λ P f . Hence, S ǫ h f = λ P f -ρ h (f ) and then S ǫ h f L ∞ ≥ λ P f L ∞ -γ f L ∞ ≥ c a f L ∞ (3.6)
with c a = a Pγ. On the other hand, since u → e λ(u) x is a submersion from a neighborhood of o N ∈ N onto a neighborhood of x ∈ M , we get by Cauchy-Schwarz inequality

|S ǫ h f (x)| ≤ h -Q meas(I ǫ,h ) 1/2 ( u∈I ǫ,h |f (e λ(u) x)| 2 du) 1/2 ≤ Ch -Q/2 f L 2 (M ) (3.7)
Putting together (3.6) and (3.7), we obtain the anounced result.

Le us now prove Proposition 3.1. We have to show that there exists c, ǫ > 0 independent of h small, such that for any non negative continous function f on M , one has T P h f (x) ≥ cS ǫ h f (x). Since M is compact and the operator T h moves supports of functions at distance at most h, we can assume without loss of generality that f is supported near some point x 0 ∈ M where we can apply the results of section 2. Recall λ(u) = α∈A u α Z α . From proposition 2.4 one has f (e λ(u) x) = W (f )(e λ(u) w) for any w close to o N such that Λ(w) = x. Using also (2.8), we are thus reduce to prove that there exists c, ǫ > 0 independent of h small such that for any non negative continuous function g on N supported near o N , one has

T P h g(w) ≥ ch -Q u∈I ǫ,h
g(e λ(u) w) du (3.8)

For any non-commutative sequence (A k ) of operators, we denote Π K k=1 A k = A K . . . A 1 (i.e A 1 is the first operator acting). Endowing A r with the lexicographical order, we can write A r = {α 1 < . . . < α ar } and for any non-commutative sequence (B α ) indexed by A, we define Π α∈Ar B α = Π ar j=1 B α j and Π α∈A B α = Π r r=1 Π α∈Ar B α .

Let α = (α 1 , ..., α k ) ∈ N k p , and t = (t 1 , ..., t k ) ∈ R k close to 0. One defines by induction on |α| a smooth diffeomorphism φ α (t) of N near o N , with φ α (0) = Id, by the following formulas: If |α| = 1 and α = j ∈ {1, ..., p}, set φ α (t)(w) = e tZ j w.

If |α| = k ≥ 2, set α = (j, β), with β ∈ N k-1 p and t = (t 1 , t ′ ) with t ′ ∈ R k-1 and set φ α (t) = φ -1 β (t ′ )e -t 1 Z j φ β (t ′ )e t 1 Z j (3.9)
Observe that φ α (t) = Id if one of the t j is equal to 0. The map (t, w) → φ α (t)(w) is smooth, and one has in local coordinates on N and for t close to 0

φ α (t)(w) = w + (Π 1≤l≤|α| t l ) Z α (w) + r α (t, w) (3.10)
with r α (t, w) ∈ (Π 1≤l≤|α| t l )O(|t|). From (3.9), one get easily by induction on k the following lemma.

Lemma 3.5 For 2 ≤ k ≤ r, there exists maps:

ǫ k : {1, . . . , b k } → {±1}, ℓ k : {1, . . . , b k } → {1, . . . , k}, j k : {1, . . . , b k } → {1, . . . , p} such that ǫ k (1) = 1, ǫ k (b k /2) = -1, ℓ k (1) = 1, ℓ k (b k /2) = 1, ♯ℓ -1 k (j) = 2 j for j ≤ k -1, ♯ℓ -1 k (k) = 2 k-1 , j k (m) = α ℓ k (m)
, and such that for all t = (t 1 , ..., t k ) one has

φ α (t) = b k m=1 e ǫ k (m)t ℓ k (m) Z j k (m) (3.11)
Since g is non negative, one has

T P h g(w) ≥ 1 p P α∈A b |α| k=1 T j |α| (k),h g(w) (3.12)
Therefore, we are reduced to prove that there exists ǫ, c > 0 independent of h small and w near o N such that the following inequality holds true.

h -P [-h,h] P g α∈A b |α| k=1 e t |α|,k Z j |α| (k) w dt ≥ ch -Q z∈I ǫ,h
g(e Then, from lemma 3.5 we have the following identity for any t

= (t α ) α∈A ∈ R Q . Φ w • κ(t) = Π α∈A φ α (t α )w (3.17)
From (3.10) and Campbell-Hausdorff formula, one gets

Π α∈A φ α (t α )w = e β∈A f β (t)Z β w f β (t) = Π 1≤l≤|β| t β,l + g β ((t γ ) |γ|<|β| ) + r β (t) (3.18)
with g β an homogeneous polynomial of degree |β| depending only on (t γ ) |γ|<|β| and r

β (t) ∈ O(|t| |β|+1 ). Let δ ∈] 1 2 , 1[ and define ξ = (ξ α,k ) α∈A,k∈N |α| ∈ R Q by ξ α,1 = 0 and ξ α,k = δh for k = 2, . . . , |α|. Let ζ : R D -→ R Q be the map defined by the formula s = (s α ) α∈A → (ζ α,k (s)) α∈A,k∈N |α| ζ α,1 (s) = s α , and ζ α,k (s) = 0 ∀k ≥ 2 (3.19)
and let σ : R P -D -→ R P be the map defined by the formula

v = (v α,k ) α∈A,k=2,...,b |α| → (σ α,k (v)) α∈A,k=1,...,b |α| σ α,1 (v) = 0, and σ α,k (v) = v α,k ∀k = 1 (3.20) Set κξ (u, v) = κ(ζ(u) + ξ) + σ(v)
, and let Ψ w : R D × R P -D → N be defined by

Ψ w (u, v) = Φ w (κ ξ (u, v)) (3.21)
Then, it follows from (3.15) that there exists smooth maps φα,w (u, v) such that

Ψ w (u, v) = e α∈A φα,w(u,v)Z α w (3.22)
From (3.17) one has

Ψ w (u, 0) = Φ w (κ(ζ(u) + ξ)) = Π α∈A φ α (u α , δh, ..., δh)w and therefore from (3.18) we get, since κξ (u, v) is linear in ξ, u, v φα,w (u, v) = u α (δh) |α|-1 + g α,w ((u γ ) |γ|<|α| , δh) + p α,w (u, δh, v) + q α,w (u, δh, v) (3.23)
where g α,w (u, s) is a homogenous polynomial of degre |α| depending only on u γ for |γ| < |α|, p α,w (u, s, v) is a homogenous polynomial of degre |α| in (u, s, v) such that p α,w (u, s, 0) = 0, and q α,w (u, s, v) ∈ O((u, s, v) 1+|α| ) near (u, s, v) = (0, 0, 0). Moreover, from φ α (0, δh, ..., δh) = Id, one get g α,w (0, s) = 0 and also q α,w (0, s, 0) = 0. Observe that w is just a smooth parameter in the above constructions. Thus, we will remove the dependance in w in what follows. Define now

Q : R P = R D × R P -D -→ R P (u, v) = ((u α ) α∈A , (v α,k ) α∈A,k=2,...,b |α| ) → (( φα (u, v)) α∈A , v) (3.24)
and for η, ǫ > 0 let

∆ ǫ,η = {(u, v) = ((u α ) α∈A , (v α,k ) α∈A,k=2,...,b |α| ) ∈ R P , |u α | < ǫh, and |v α,k | < ηh for all α, k} Lemma 3.6 Let δ ∈] 1 2 , 1[ be fixed. There exists 0 < η << ǫ < 1/2 and h 0 > 0 such that the restriction Q ǫ,η of Q to ∆ ǫ,η enjoys the following: 1. there exists U ǫ,η open neighbourhood of 0 ∈ R P such that Q ǫ,η : ∆ ǫ,η → U ǫ,η is a C ∞ diffeomorphism.
2. there exists some constant C > 0 such that for all h ∈]0, h 0 ] and all

(u, v) ∈ ∆ ǫ,η h Q-D /C ≤ JQ ǫ,η (u, v) := | det(D (u,v) Q ǫ,η )| ≤ Ch Q-D 3. there exists M ≥ 1 such that for all h ∈]0, h 0 ] the set U ǫ,η contains I ǫ/M,h ×] -ηh, ηh[ P -D where I ǫ/M,h = α∈A ] -ǫh |α| /M, ǫh |α| /M [.
Proof. The proof is just a scaling argument. Set u α = hũ α , v α,k = hṽ α,k and φα = h |α| z α . Then the map Q becomes after scaling Q : (ũ, ṽ) → (z, ṽ), and from (3.23) one has z α = ũα δ |α|-1 + g α ((ũ γ ) |γ|<|α| , δ) + p α (ũ, δ, ṽ) + hq α (ũ, δ, ṽ, h) p α (ũ, δ, 0) = 0, qα (ũ, δ, ṽ, h) is smooth and vanish at order |α| + 1 at 0 as a function of (ũ, δ, ṽ) and g α (0, δ) = 0, qα (0, δ, 0, h) = 0. From the triangular structure above, it is obvious that Q is a smooth diffeomorphism at 0 ∈ R P , such that Q(0) = 0. Thus, for η << ǫ, h ≤ h 0 small and M >> 1, we get the inclusion

{|z α | < ǫ/M, |ṽ α,k | < η}) ⊂ Q({|ũ α | < ǫ, |ṽ α,k | < η}). One has by construction | det(D (u,v) Q)| = h Q-D | det(D (ũ,ṽ) Q)|. The proof of lemma 3.6 is complete.
It is now easy to verify that (3.13) holds true. One has det D (u,v) κξ = 1 for all (u, v) ∈ R P and for 1 2 < δ < 1, and 0 < η << ǫ < 1/2 there exists some numbers -1 < α i < β i < 1, i = 1, . . . , P -D depending only on ǫ, η, δ and such that κξ

(∆ ǫ,η ) is contained in the set ∆ ǫ,η = {(t, s), t ∈ [-ǫh, ǫh] D , s ∈ P -D i=1 [α i h, β i h]}.
Using again the positivity of g and the change of variable κ, we obtain, with a constant c > changing from line to line

h -P [-h,h] P g(Φ(t))dt ≥ h -P ∆ǫ,η g(Φ(t))dt ≥ h -P κξ (∆ǫ,η) g(Φ(t))dt ≥ ch -P ∆ǫ,η g(Φ • κξ (u, v))dudv = ch -P ∆ǫ,η g(Ψ(u, v))dudv (3.25)
Thanks to Lemma 3.6, we can use the change of variable Q ǫ,η to get

h -P ∆ǫ,η g(Ψ(u, v))dudv ≥ ch D-P -Q Uǫ,η g(e α∈A zαZ α w)dzdv ≥ ch -Q I ǫ ′ ,η g(e α∈A zαZ α w)dz = ch -Q z∈I ǫ ′ ,h
g(e λ(z) w) dz (3.26) whith ǫ ′ = ǫ/M and M is given by Lemma 3.6. The proof of proposition 3.1 is complete.

Dirichlet form

Let E h be the rescaled Dirichlet form associated to the Markov kernel

T h 0 ≤ E h (u) = ( 1 -T h h 2 u|u) L 2 , u ∈ L 2 (M, dµ) (4.1)
The main result of this section is the following proposition.

Proposition 4.1 Under the hypoelliptic hypothesis (1.2), there exists C, h 0 > 0 such that the following holds true for all h ∈]0, h 0 ]: for all u ∈ L 2 (M, dµ) such that

u 2 L 2 + E h (u) ≤ 1 (4.2) there exists v h ∈ H 1 (X ) and w h ∈ L 2 such that u = v h + w h , ∀j, X j v h L 2 ≤ C, w h L 2 ≤ Ch (4.3)
This proposition is easy to prove when the vector fields X j span the tangent bundle at each point, by elementary Fourier analysis. Under the hypoelliptic hypothesis, the proof is more involved, and will be done in several steps.

Step 1: Localization and reduction to the nilpotent Lie algebra.

Let us first verify that for all

ϕ ∈ C ∞ (M ), there exists C ϕ independent of h ∈]0, 1] such that E h (ϕu) ≤ C ϕ ( u 2 L 2 + E h (u)) (4.4) One has 1 -T h = 1 p p k=1 (1 -T k,h ) and 2((1 -T k,h )u|u) = M 1 2h h -h |u(x) -u(e tX k x)| 2 dt dµ(x)
Since sup x∈M |ϕ(x)ϕ(e tX k x)| ≤ C|t|, this implies for some constant C ϕ and all k

((1 -T k,h )ϕu|ϕu) ≤ C ϕ (((1 -T k,h )u|u) + h 2 u 2 L 2 )
and therefore, (4.4) holds true. Thus, in the proof of proposition 4.1, we may assume that u ∈ L 2 (M, dµ) is supported in a small neighborhood of a given point x 0 ∈ M where theorem 2.3 applies. More precisely, with the notations of section 2, we may assume in the coordinate system Λθ centered at

x 0 ≃ 0 that u is supported in the closed ball B m r = {x ∈ R m , |x| ≤ r} ⊂ V 0 . Let χ(y) ∈ C ∞ 0 (U 0 ) with support in B n r ′ ⊂ U 0 , such that χ(y)dy = 1. Set g(x, y) = χ(y)u(x). One has g(x, y) = χ(y)W x 0 (u)(x, y). By hypothesis, one has u 2 L 2 + E h (u) ≤ 1 This implies for all k 2((1 -T k,h )u|u) = M 1 2h h -h |u(x) -u(e tX k x)| 2 dt dµ(x) ≤ ph 2
Thus, for any compact K ⊂ U 0 , there exist C K such that for all k and h ∈]0, h 0 ], one has

V 0 ×K 1 2h h -h |u(x) -u(e tX k x)| 2 dt dxdy ≤ C K h 2 (4.5)
Here, h 0 is small enough so that e tX k x remains in V 0 for |t| ≤ h 0 and x ∈ B r . Let φ(x, y) = χ(y).

One has sup x,y |φ(x, y)φ(e tZ k (x, y))| ≤ C|t| and g L 2 ≤ C. Thus, decreasing h 0 , we get from (4.5) that there exists a constant C independent of k and h ∈]0, h 0 ] such that

V 0 ×U 0 1 2h h -h |g(x, y) -g(e tZ k (x, y))| 2 dt dxdy ≤ Ch 2 (4.6)
Therefore, there exists C 0 independent h ∈]0, h 0 ] such that one has

g 2 L 2 (N ) + p j=1 h -2 V 0 ×U 0 1 2h h -h |g(x, y) -g(e tZ k (x, y))| 2 dt dxdy ≤ C 0 (4.7)
Lemma 4.2 There exists C 1 , h 0 > 0 such that for all h ∈]0, h 0 ], any g with support in B m r ×B n r ′ , such that (4.7) holds true can be written on the form

g = f h + l h , p k=1 Z k f h L 2 (V 0 ×U 0 ) ≤ C 1 , l h L 2 (V 0 ×U 0 ) ≤ C 1 h
Let us assume that lemma 4.2 holds true. Then one can write

g = χ(y)u(x) = f h + l h . Let ψ(x, y) ∈ C ∞ 0 (V 0 × U 0 ) equal to 1 near B m r × B n r ′ . Set v h = ψ(x, y)f h (x, y)dy, w h = ψ(x, y)l h (x, y)dy One has v h + w h = ψ(x, y)χ(y)u(x)dy = χ(y)u(x)dy = u(x) and w h L 2 ≤ Ch. Moreover, we get from (2.6) X k (v h ) = (Z k - l b k,l (x, y) ∂ ∂y l )ψ(x, y)f h (x, y)dy Since f h , Z k (f h ) ∈ O L 2 (1) and b ∂ ∂y l (ψf h )dy = -∂ ∂y l (b)ψf h dy ∈ O L 2
(1), we get that (4.3) holds true. We are thus reduced to prove lemma 4.2.

For any given k, the vector field Z k is not singular; thus, decreasing V 0 , U 0 if necessary, there exists coordinates (z 1 , .., z D ) = (z 1 , z ′ ) such that Z k = ∂ ∂z 1 . Using Fourier transform in z 1 , we get that if g satisfies (4.7), one has

2 (1 - sin hζ 1 hζ 1 )|ĝ(ζ 1 , z ′ )| 2 dζ 1 dz ′ = 1 2h h -h |1 -e itζ 1 | 2 dt|ĝ(ζ 1 , z ′ )| 2 dζ 1 dz ′ ≤ C ′ 0 h 2 (4.8)
Let a > 0 small. There exists c > 0 such that (1-

sin hζ 1 hζ 1 ) ≥ ch 2 ζ 2 1 for h|ζ 1 | ≤ a and (1-sin hζ 1 hζ 1 ) ≥ c for h|ζ 1 | > a. Since g(z 1 , z ′ ) = 1 2π h|ζ 1 |≤a e iz 1 ζ 1 ĝ(ζ 1 , z ′ )dζ 1 + 1 2π h|ζ 1 |>a e iz 1 ζ 1 ĝ(ζ 1 , z ′ )dζ 1 = v h,k + w h,k , we get from (4.8) that g satisfies for some C 0 independent of h ∈]0, h 0 ] g L 2 (N ) ≤ C 0 , support(g) ⊂ V 0 × U 0 ∀k, g = v h,k + w h,k Z k v h,k L 2 (N ) ≤ C 0 , w h,k L 2 (N ) ≤ C 0 h (4.9)
and we want to prove that the decomposition g = v h,k + w h,k may be choosen independent of k, i.e there exists C > 0 independent of h such that

g = v h + w h ∀k, Z k v h L 2 (N ) ≤ C w h L 2 (N ) ≤ Ch (4.10)
In order to prove the implication (4.9) ⇒ (4.10) we will construct operators Φ, C j , B k,j , R l , depending on h, acting on L 2 functions with support in a small neighborhood of o N in N , with values in L 2 (N ), such that Φ, C j , B k,j , R l , C j hZ j , B k,j hZ k are uniformly in h bounded on L 2 and

1 -Φ = p j=1 C j hZ j + hR 0 Z j Φ = p k=1 B k,j Z k + R j (4.11)
and then we set

v h = Φ(g), w h = (1 -Φ)(g)
With this decomposition of g, we get

w h = p j=1 C j hZ j (v h,j + w h,j ) + hR 0 (g) ∈ O L 2 (h) Z k (v h ) = p j=1 B j,k Z j (v h,j + h 1 h w h,j ) + R k (g) ∈ O L 2 (1)
We are thus reduced to prove the existence of the operators Φ, C j , B k,j , R l , with the suitable bounds on L 2 , and such that (4.11) holds true. This is a problem on the Lie algebra N with vector fields Z j given by the Rothschild-Stein Goodman theorem 2.3. We will first do this construction in the special case where the vector fields Z j are equal to the left invariant vector fields Ỹj on N . In that special case, we will have R l = 0 in formula (4.11). We will conclude in the general case by a suitable h-pseudodifferential calculus.

Step 2: The case of left invariant vector fields on N .

Let f * u be the convolution on N f * u(x) = N f (x.y -1 )u(y)dy = N f (z)u(z -1 .x)dz
Here, dy is the left (and right) invariant Haar measure on N , which is simply equal to the Lebesgue measure dy 1 ...dy r in the coordinates used in formula (2.3). Then for u ∈ L 1 (N ), the map f → f * u is bounded on L q (N ) by u L 1 for any q ∈ [1, ∞]. The vector fields Ỹj are divergence free for the Haar measure dy.

If f is a function on N , and a ∈ N , let τ a (f ) be the function defined by τ a (f )(x) = f (a -1 .x). One has for any a ∈ N and Y ∈ T e N ≃ N , τ a Ỹ = Ỹ τ a and the following formula holds true:

τ a (f ) = δ a * f Ỹ f = f * Ỹ δ e (4.12)
Let us denote by T h the scaling operator

T h (f )(x) = h -Q f (h -1 .x). One has h.(x -1 ) = (h.x) -1 and T h (f * g) = T h (f ) * T h (g).
The action of T h on the space D ′ (N ) of distributions on N , compatible with the action on functions, is given by < T h (T ), φ >=< T, x → φ(h.x) >. Thus one has T h δ e = δ e and T h ( Ỹj (δ e )) = h Ỹj (δ e ) for j ∈ {1, ..., p}.

Let S(N ) be the Schwartz space on N , and ϕ ∈ S(N ), with N ϕ(x)dx = 1. For h ∈]0, 1], let Φ h be the operator defined by

Φ h (f ) = f * ϕ h , ϕ h (x) = h -Q ϕ(h -1 .x) = T h (ϕ) (4.13)
Since the Jacobian of the transformation x → h.x is equal to h Q , one has ϕ h L 1 = ϕ L 1 for all h ∈]0, 1], and therefore the operator Φ h is uniformly bounded on L 2 .

If we define the operators B k,j,h by B k,j,h (f ) = f * T h (ϕ k,j ), with ϕ k,j ∈ S(N ), the equation

Ỹj Φ h = p k=1 B k,j,h Ỹk is equivalent to find the ϕ k,j ∈ S(N ) such that Ỹj ϕ = p k=1
Ỹk δ e * ϕ k,j (4.14)

One has N Ỹj (ϕ)(x)dx = 0, and since f → Ỹk δ e * f is the right invariant vector field

Z k on N such that Z k (o N ) = Y k ,
∈]0, 1] bounded on L 2 . (one has B k,j,h (h Ỹk (f )) = f * T h ( Ỹk (δ e ) * ϕ k,j ) and Ỹk (δ e ) * ϕ k,j ∈ S(N )). Let now c j ∈ C ∞ (N \ {o N }) be Schwartz for | |x| | ≥ 1, and quasi homogeneous of degree -Q + 1 near o N (i.e c j (t.x) = t -Q+1 c j (x) for 0 < | |x| | ≤ 1 and t > 0 small). Let C j,h be the operators defined by C j,h (f ) = f * T h (c j ). Then the equation 1 -Φ h = j C j,h h Ỹj is equivalent to solve δ e -ϕ = j Ỹj δ e * c j (4.15)
In order to solve (4.15), we denote by E ∈ C ∞ (N \ {o N }) the (unique) fundamental solution, quasi homogeneous of degree -Q + 2 on N of the hypoelliptic equation (for the existence of E, we refer to [Fol75], theorem (2.1), p.172)

δ e = p j=1 Z 2 j (E), Z j (f ) = Ỹj δ e * f Let ψ ∈ C ∞ 0 (N ) with ψ(x) = 1 near e = o N .
We will choose c j of the form

c j = ψZ j (E) -d j , d j ∈ S(N ) (4.16)
Then the equation (4.15) is equivalent to solve

ϕ + p j=1 [Z j , ψ]Z j (E) = ϕ 0 = p j=1 Z j (d j ) (4.17) One has ϕ 0 ∈ S(N ) and N ϕ 0 (x)dx = 0 since N ϕ(x)dx = 1 and N p j=1 [Z j , ψ]Z j (E)dx = -N p j=1 ψZ 2
j (E)dx = -1. Thus, the equation (4.14) is solvable thanks to lemma 7.2. Moreover, since c j ∈ L 1 (N ), the operators C j,h are uniformly in h bounded on L 2 . It remains to verify that the operators C j,h h Ỹj are uniformly in h bounded on L 2 . One has

C j,h h Ỹj (f ) = f * T h (Z j (c j )). Since T h (f ) L 2 = h -Q/2 f L 2 it
is equivalent to prove that the operator g → g * Z j (c j ) is bounded on L 2 . By construction one has Z j (c j ) = ψZ 2 j (E)+l j , l j ∈ S(N ).

With the terminology of [Fol75], the distribution Z 2 j (E) is homogeneous of degree 0 (i.e quasi homogeneous of degree -Q), thus of the form Z 2 j (E) = a j δ e + f j where f j ∈ C ∞ (N \ {o N }), quasi homogeneous of degree -Q and such that b<|u|<b ′ f j (u)du = 0. Thus by [Fol75], proposition 1.9, p.167, the operator g → g * Z j (c j ) is bounded on L 2 .

Step 3: A suitable h-pseudodifferential calculus on N .

Let Z α be the smooth vector fields defined in a neighborhood Ω of o N in N given by the Goodman theorem 2.3. In this last step, we will finally construct the operators such that (4.11) holds true. We first recall the construction of the map Θ(a, b) which play a crucial role in the construction of a parametrix for hypoelliptic operators in [START_REF] Rothschild | Hypoelliptic differential operators and nilpotent groups[END_REF]. Let ϕ ∈ S(N ), with N ϕ(x)dx = 1. By step 2, there exists functions ϕ k,j ∈ S(N ), and

Let us recall that (Y α a = H α (Y 1 , ..., Y p ) ∈ T e N , α ∈ A) is a basis of T e N .
c j ∈ C ∞ (N \ {o N }), Schwartz for | |x| | ≥ 1, quasi homogeneous of degree -Q + 1 near o N , such that the following holds true. Ỹj (ϕ) = p k=1 Z k (ϕ k,j ) δ e -ϕ = j Z j (c j ) (4.22)
Let ω 0 ⊂⊂ ω 1 be small neighborhoods of o N such that Θ(y, x) is well defined for (y, x) ∈ ω 0 × ω 1 , and χ ∈ C ∞ 0 (ω 1 ) be equal to 1 in a neighborhood of ω 0 . We define the operators Φ h , B k,j,h and C j,h for 1 ≤ j, k ≤ p by the formulas

Φ h (f )(x) = χ(x) h -Q N ϕ(h -1 .Θ(y, x))f (y)dy B k,j,h (f )(x) = χ(x) h -Q N ϕ k,j (h -1 .Θ(y, x))f (y)dy C j,h (f )(x) = χ(x) h -Q N c j (h -1 .Θ(y, x))f (y)dy (4.23)
All these operators are of the form

A h (f )(x) = h -Q N g(x, h -1 .Θ(y, x))f (y)dy (4.24)
where the function g(x, .) is smooth in x, with compact support ω 1 , and takes values in L 1 (N ), i.e sup x∈ω 1 ∂ β x g(x, .) L 1 (N ) < ∞ for all β. The function A h (f ) is well defined for f ∈ L ∞ (N ) such that support(f ) ⊂ ω 0 . We have introduce the cutoff χ(x) just to have A h (f )(x) defined for all x ∈ N , and one has A h (f )(x) = 0 for all x / ∈ ω 1 .

Lemma 4.3 Let g(x, .) be smooth in x with compact support in ω 1 , with values in L 1 (N ). Then the operator A h defined by (4.24) is uniformly in

h ∈]0, 1] bounded from L q (ω 0 ) into L q (N ) for all q ∈ [1, ∞].
Proof. The proof is standard. By interpolation, it is sufficient to treat the two cases q = ∞ and q = 1. In the case q = ∞, the jacobian of the change of coordinates y → u = Θ(y, x) is bounded by C for all x ∈ ω 1 , y ∈ ω 0 . Thus we get

|A h (f )(x)| ≤ C f L ∞ (ω 0 ) h -Q N |g(x, h -1 .u)|du = C f L ∞ (ω 0 ) g(x, .) L 1 Since x → g(x, .) is smooth in x with values in L 1 (N ), one has C ∞ = sup x∈ω 1 g(x, .) L 1 < ∞. Thus we get A h (f ) L ∞ ≤ CC ∞ f L ∞ (ω 0 ) .
For q = 1, we first extend g as a smooth L-periodic function of x ∈ N , with L large enough, g(x, u) = k∈Z D g k (u)e 2iπk.x/L , the equality being valid for x ∈ ω 1 . Observe that g k L 1 (N ) is rapidly decreasing in k. Then one has

A h (f )(x) = k A h,k (f )(x)e ik.x/L , A h,k (f )(x) = h -Q N g k (h -1 .Θ(y, x))f (y)dy
The jacobian of the change of coordinates (x, y) → (u = Θ(y, x), y) is bounded by C for all (x, y) ∈ ω 1 × ω 0 , and one has

ω 1 |A h,k (f )(x)|dx ≤ Ch -Q N ω 0 |g k (h -1 .u)||f (y)|dydu = C f L 1 g k L 1
Thus we get sup h∈]0,1] A h,k L 1 = d k with d k rapidly decreasing in k, and this implies

sup h∈]0,1] A h L 1 ≤ k d k < ∞. The proof of lemma 4.3 is complete.
Observe that in the special case Z j = Ỹj , using (4.21), we get that the operators Φ h , B k,j,h , C j,h defined by the formula (4.23) are precisely equal, up to the factor χ(x), to the operators we have constructed in step 2.

In the general case, it remains to show the following:

i) The operators R l,h defined by

R 0,h = h -1 1 -Φ h - p j=1 C j,h hZ j R j,h = Z j Φ h - p k=1 B k,j,h Z k , 1 ≤ j ≤ p (4.25) are uniformly bounded in h ∈]0, 1] on L 2 .
ii) The operators C j,h hZ j and B k,j,h hZ k , k > 0 are uniformly bounded in h ∈]0, 1] on L 2 .

For the verification of i) and ii), we just follow the natural strategy which is developed in [START_REF] Rothschild | Hypoelliptic differential operators and nilpotent groups[END_REF]. If f is a function defined near a ∈ N , let Φ a (f ) be the function defined near 0 in N ≃ T e N by Φ a (f )(u) = f (Φ(a, u)). The following fundamental lemma is proven in [START_REF] Rothschild | Hypoelliptic differential operators and nilpotent groups[END_REF] (theorem 5) and also in [START_REF] Goodman | Lifting vector fields to nilpotent Lie groups[END_REF] (section 5, "Estimation of the error").

Lemma 4.4 For all j ∈ {1, ..., p}, and a ∈ N near e, the vector field V j,a defined near 0 in N

V j,a (g) = Φ a (Z j (Φ -1 a g)) -Ỹj (g) (4.26)
is of order ≤ 0 at 0. If we introduce the system of coordinates (u α ) = (u l,k ) with l(α) = |α| and 1 ≤ k ≤ a l = dim(N l ), we thus have

V j,a = r l=1 a l k=1 v j,l,k (a, u) ∂ ∂u l,k (4.27)
where the functions v j,l,k (a, u) are smooth and satisfy

v j,l,k (a, u) ∈ O(| |u| | l ).
Let us denote by A h [g] an operator of the form (4.24). Recall that g(x, u) is smooth in x with compact support in ω 1 , with values in L 1 (N ). More precisely, we have two cases to consider: a) g is Schwartz in u, and b) g is smooth in u in N \ {o N }), Schwartz for | |u| | ≥ 1, and quasi homogeneous of degree -Q+1 near o N . We have to compute the kernel of the operators

Z j A h [g] and A h [g]Z j .
We first compute the kernel of Z j A h (g). For any fixed y, perform the change of coordinates x = Φ y (u) so that Θ(y, x) = u. Denote Z x j the vector field Z j acting on the variable x. Using lemma 4.4, we get

Z j (A h [g](f ))(x) = h -Q N Z x j (g(x, h -1 .Θ(y, x)))f (y)dy = h -Q N h -1 ( Ỹ u j g)(x, h -1 .Θ(y, x))f (y)dy + h -Q N (Z x j g)(x, h -1 .Θ(y, x))f (y)dy + r l=1 a l k=1 h -Q N v j,l,k (y, Θ(y, x))h -l ∂g ∂u l,k (x, h -1 .Θ(y, x))f (y)dy (4.28)
By lemma 4.3, the second term in (4.28) is uniformly bounded in h ∈]0, 1], from L 2 (ω 0 ) into L 2 (N ). The same holds true for the third term. To see this point, following the proof of lemma 4.3, first write v j,l,k (y, u) = n v j,l,k,n (u)e 2iπn.y/L , with v j,l,k,n (u) rapidly decreasing in n and O(| |u| | l ) near u = o N . We are then reduce to show that an operator of the form is of order 0).

R h (f ) = h -Q N h -l G(Θ(y, x)) ∂g ∂u l,k (x, h -1 .Θ(y, x))f (y)dy with G(u) smooth and G(u) ∈ O(| |u| | l ), is uniformly bounded in h ∈]0, 1] from L 2 (ω 0 ) into L 2 (N )
If we denote by R h any operator uniformly bounded on L 2 , we have thus proven

Z j A h [g] = h -1 A h [ Ỹ u j g] + R h (4.29)
Let us now compute the kernel of A h [g]Z j . The basic observation is the following identity (recall u -1 = -u and Z j (f ) = Ỹj (δ e ) * f is the right invariant vector field such that Z j (0) = Y j )

-Ỹj f (-u) = Z j (f )(-u) (4.30)
Let l j be the smooth function such that t Z j = -Z j + l j . For any given x perform the change of coordinates y = Φ x (u). By (4.20), one has Θ(y, x) = -Θ(x, y) = -u. We thus get from lemma 4.4 and (4.30) the following formula:

A h [g](Z j (f ))(x) = h -Q N g(x, h -1 .Θ(y, x))Z j (f )(y)dy = h -Q N (-Z y j + l j (y))(g(x, h -1 .Θ(y, x)))f (y)dy = h -Q N h -1 (Z u j g)(x, h -1 .Θ(y, x))f (y)dy + h -Q N g(x, h -1 .Θ(y, x))l j (y)f (y)dy + r l=1 a l k=1 h -Q N v j,l,k (x, -Θ(y, x))h -l ∂g ∂u l,k (x, h -1 .Θ(y, x))f (y)dy (4.31)
As above, this gives the identity, with R h uniformly bounded on L 2

A h [g]Z j = h -1 A h [Z u j g] + R h (4.32)
Observe that formulas (4.22), (4.29) and (4.32) imply that (4.25) holds true. Moreover, from (4.32) and lemma 4.3, the operators B k,j,h hZ k , k > 0 are uniformly bounded in h ∈]0, 1] on L 2 . In order to get from (4.32) the same uniform bounds for the operators C j,h hZ j , we just observe that in the case where g(x, u) is quasi homogeneous in u of degree -Q + 1 near o N , one has Z u j g(x, u) = C j (x)δ e + f j (x, u) with b<|u|<b ′ f j (x, u)du = 0 and we conclude as in the end of step 2 by the proposition 1.9 of [Fol75]. The proof of proposition 4.1 is complete.

Proof of theorems 1.1 and 1.2

This section is devoted to the proof of theorems 1.1 and 1.2. Let B h be the bilinear form associated to the rescaled Dirichlet form

E h B h (f, g) = ( 1 -T h h 2 f |g) L 2 , f, g ∈ L 2 (M, dµ) (5.1) Proposition 5.1 Let f ∈ H 1 (X ). Let (r h , γ h ) ∈ H 1 (X ) × L 2 such that r h converge weakly (when h → 0) in H 1 (X ) to r ∈ H 1 (X ), and sup h γ h L 2 < ∞. Then lim h→0 B h (f, r h + hγ h ) = 1 6p p k=1 (X k f |X k r) L 2 (5.2) Proof. Write r h = r + r ′ h . The weak limit of r ′ h in H 1 (X ) is 0. Since B h (f, r h ) = B h (f, r) + B h (f, r ′
h ), we have to prove the two assertions:

lim h→0 B h (f, r) = 1 6p p k=1 (X k f |X k r) L 2 , ∀f, r ∈ H 1 (X ) (5.3)
and under the hypothesis that the weak limit of

r h in H 1 (X ) is 0 lim h→0 ( 1 -T k,h h 2 f |r h + hγ h ) L 2 = 0, ∀k ∈ {1, ..., p} (5.4)
In order to verify (5.4), since M is compact, we may assume that f is supported in a small neighborhood of a point x 0 ∈ M where the Goodman theorem 2.3 applies. With the notations of section 2, we may thus assume in the coordinate system Λθ centered at x 0 ≃ 0 that f, r h , γ h are supported in the closed ball

B m r = {x ∈ R m , |x| ≤ r} ⊂ V 0 . Let χ(y) ∈ C ∞ 0 (U 0 ) with support in B n r ′ ⊂ U 0 , such that χ(y)dy = 1 and write dµ(x) = ρ(x)dx with ρ smooth. For u, v ∈ L 2 (M ) supported in B m r , one has (u|v) L 2 = V 0 u(x)v(x) dµ(x) = V 0 ×U 0 u(x)ρ(x)χ(y)v(x) dxdy Set f (x, y) = W x 0 (f )(x, y) = f (x), rh (x, y) = ρ(x)χ(y)r h (x), γh (x, y) = ρ(y)χ(y)γ h (x). We get from (2.8) ( 1 -T k,h h 2 f |r h + hγ h ) L 2 = V 0 ×U 0 1 -Tk,h h 2 f rh + hγ h dxdy (5.5)
Observe that γh is bounded in L 2 (V 0 × U 0 ). Since the injection H 1 (X ) ⊂ L 2 (M ) is compact, r h converge strongly to 0 in L 2 , and therefore rh converge strongly to 0 in L 2 (V 0 × U 0 ). Moreover, Z k (r h ) converge weakly to 0 in L 2 (V 0 × U 0 ). Finally, since Tk,h increase the support of at most ≃ h, we may replace f by F = θ(y) f with θ ∈ C ∞ 0 equal to 1 near the support of χ. Then F is compactly supported in V 0 × U 0 and satisfies F ∈ L 2 and Z k F ∈ L 2 . Since the vector field Z k is not singular, decreasing V 0 , U 0 if necessary, there exists coordinates (z 1 , .., z D ) = (z 1 , z ′ ) such that Z k = ∂ ∂z 1 . One has dxdy = q(z)dz with q > 0 smooth. Set qr h = R h , qγ h = Q h . Using Fourier transform in z 1 , it remains to show lim h→0

I h = 0, I h = h -2 (1 - sin(hξ 1 ) hξ 1 ) F (ξ 1 , z ′ ) Rh (ξ 1 , z ′ )dξ 1 dz ′ lim h→0 J h = 0, J h = h -1 (1 - sin(hξ 1 ) hξ 1 ) F (ξ 1 , z ′ ) Qh (ξ 1 , z ′ )dξ 1 dz ′ (5.6) Recall that Q h is bounded in L 2 , R h converge strongly to zero in L 2 , ∂ z 1 R h converge weakly to zero in L 2 and F, ∂ z 1 F ∈ L 2 .
We write the first integral in (5.6) on the form

I h = ψ(hξ 1 )ξ 1 F (ξ 1 , z ′ )ξ 1 Rh (ξ 1 , z ′ )dξ 1 dz ′ with ψ(x) = x -2 (1 -sin(x) x ). One has ψ ∈ C ∞ (R) and |ψ(x)| ≤ C 1 1+x 2 .
Then we write I h = I 1,h + I 2,h with I 1,h defined by the integral over |ξ 1 | ≤ M and I 2,h defined by the integral over |ξ 1 | > M . Since ξ 1 Rh (ξ 1 , z ′ ) is bounded in L 2 , and ψ ∈ L ∞ we get by Cauchy-Schwarz

|I 2,h | ≤ C( |ξ 1 |>M |ξ 1 F (ξ 1 , z ′ )| 2 dξ 1 dz ′ ) 1/2 → 0 when M → ∞
On the other hand, one has ψ(x) = ψ(0) + τ (x) with ψ(0) = 1/6 and sup x∈R τ (x)/x ≤ C 0 . Thus we get

I 1,h = 1 6 |ξ 1 |≤M ξ 1 F (ξ 1 , z ′ )ξ 1 Rh (ξ 1 , z ′ )dξ 1 dz ′ + |ξ 1 |≤M τ (hξ 1 )ξ 1 F (ξ 1 , z ′ )ξ 1 Rh (ξ 1 , z ′ )dξ 1 dz ′ (5.7)
For any fixed M , the first term in (5.7) goes to 0 when h → 0 since ξ 1 Rh (ξ 1 , z ′ ) converge weakly to 0 in L 2 and ξ 1 F (ξ 1 , z ′ ) ∈ L 2 . Since ξ 1 Rh (ξ 1 , z ′ ) is bounded in L 2 by say A, by Cauchy-Schwarz, the second term is bounded by C 0 hM A ∂ z 1 F L 2 . Thus one has lim h→0 I h = 0. We proceed exactly in the same way to prove lim h→0 J h = 0: one has with xψ = φ

J h = φ(hξ 1 )ξ 1 F (ξ 1 , z ′ ) Qh (ξ 1 , z ′ )dξ 1 dz ′ and we use the fact that φ ∈ L ∞ , Qh (ξ 1 , z ′ ) is bounded in L 2 , φ(0) = 0 and φ(x)/x ∈ L ∞ (R) .
Let us now verify (5.3). From (1.10) this is obvious if f is smooth and r ∈ H 1 (X ). Standard smoothing arguments show that C ∞ (M ) is dense in H 1 (X ). Let now f ∈ H 1 (X ) and choose

f h ∈ C ∞ (M ) converging strongly to f in H 1 (X ). Then lim h→0 (X k f h |X k r) L 2 = (X k f |X k r) L 2 and from (5.4) one has also lim h→0 B h (f h , r) = lim h→0 B h (r, f h ) = B h (f, r).
The proof of proposition 5.1 is complete.

Proof of theorem 1.1.

Let |△ h | be the rescaled (non negative) Laplacien associated to the Markov kernel T h :

|△ h | = 1 -T h h 2 (5.8)
From proposition 4.1 and lemma 7.1, there exists h 0 > 0 and C 4 , C 5 > 0 independent of h ∈]0, h 0 ], such that Spec(|△ h |) ∩ [0, λ] is discrete for all λ ≤ C 4 h -2 and one has the Weyl type estimate #(Spec

(|△ h |) ∩ [0, λ]) ≤ C 5 < λ > dim(M )/2s , ∀λ ≤ C 4 h -2 .
(5.9)

In particular, since T h (1) = 1, 1 is an isolated eigenvalue of T h . Let us verify that 1 is a simple eigenvalue of

T h . Let f ∈ L 2 = L 2 (M, dµ) such that T h (f ) = f . One has for any g ∈ L 2 ((1 -T h )g|g) L 2 = 1 2 |g(x) -g(y)| 2 t h (x, dy)dµ(x) (5.10)
Thus we get for all k ∈ {1, ..., p}

M h -h |f (x) -f (e tX k x)| 2 dtdµ(x) = 0 This gives f (x) -f (e tX k x) = 0 for almost all (x, h) ∈ M ×] -h, h[. Therefore, one has X k f = 0 in D ′ (M )
for all k, and this implies f = Cte thanks to Hörmander and Chow theorems. One can also give a more direct argument: one has T P h (f ) = f , and therefore if one use 5.10 with the Markov kernel T P h and proposition 3.1, we get u) x is a submersion, this implies f (x)f (y) = 0 for almost all (x, y) in a neighborhood of the diagonal in M × M , and therefore f = Cte.

M u∈I ǫ,h |f (x) -f (e λ(u) x)| 2 dudµ(x) = 0 Since u → e λ(
Let us now verify that there exists δ 1 > 0 such that for all h ∈]0, h 0 ], the spectrum of T h is a subset of [-1 + δ 1 , 1]. It is sufficient to prove that the same holds true for an odd power T 2N +1 h of T h . We are thus reduce to show that there exists h 0 , C 0 > 0 such that the following inequality holds true for all h ∈]0, h 0 ] and all f ∈ L 2 (Ω):

(f + T 2N +1 h f |f ) L 2 = 1 2 M ×M t 2N +1 h (x, dy)|f (x) + f (y)| 2 dµ(x) ≥ C 0 f 2 L 2 .
(5.11)

Take N large enough such that proposition 3.1 applies for T 2N +1 h , i.e t 2N +1 h (x, dy) ≥ cS ǫ h (x, dy). Then we are reduce to show that there exists C independent of h such that

M ×M S ǫ h (x, dy)|f (x) + f (y)| 2 dµ(x) ≥ C f 2 L 2 .
(5.12)

From the definition (3.1) of S ǫ h , we get

M ×M S ǫ h (x, dy)|f (x) + f (y)| 2 dµ(x) = M h -Q u∈I ǫ,h |f (x) + f (e λ(u) x)| 2 dudµ(x) = B
Define A by the formula

A = M h -2Q u∈I ǫ/2,h v∈I ǫ/2,h
|f (e λ(v) y) + f (e λ(u) y)| 2 dudvdµ(y)

Since λ(v) is divergence free as a linear combination with constant coefficients of commutators of the vector fields X k , the change of variables e λ(v) y = x gives

A = M h -2Q u∈I ǫ/2,h v∈I ǫ/2,h |f (x) + f (e λ(u-v) x)| 2 dudvdµ(x)
Therefore, one has for some constant c ǫ > 0 independent of h, B ≥ c ǫ A. Clearly, one has

M Re u∈I ǫ/2,h v∈I ǫ/2,h
f (e λ(v) y)f (e λ(u) y)dudv dµ(y) ≥ 0 and this implies, still using the change of variables e λ(v

) y = x A ≥ 2 M h -2Q u∈I ǫ/2,h v∈I ǫ/2,h |f (e λ(v) y)| 2 dudvdµ(y) = 2ǫ D M h -Q v∈I ǫ/2,h |f (e λ(v) y)| 2 dvdµ(y) = 2ǫ 2D M |f (x)| 2 dµ(x)
(5.13) From (5.13) and B ≥ c ǫ A, we get that (5.12) holds true.

Lemma 5.2 There exists C 2 , C 3 > 0 such that the spectral gap of T h satisfies

C 2 h 2 ≤ g(h) ≤ C 3 h 2 (5.14)
Proof. The right inequality in (5.14) is an obvious consequence of the min-max principle since for any f ∈ C ∞ (M ) one has lim h→0

1-T h

h 2 f = L(f ). From (5.9), we get that for any a ∈]0, 1], m a = ♯(Spec(T h ) ∩ [1ah 2 , 1[) is bounded by a constant independent of h small, and we have to verify that there exists h 0 > 0 and a > 0 independent of h ∈]0, h 0 ] such that m a = 0. If this is not true, there exists two sequences ǫ n , h n → 0 and a sequence

f n ∈ L 2 , with f n L 2 = 1 and (f n |1) L 2 = M f n dµ = 0 such that T hn f n = (1 -h 2 n ǫ n )f n This implies E hn (f n ) = ǫ n . Using proposition 4.1, we get f n = v n + h n γ n with sup n γ n L 2 < ∞ and v n H 1 (X ) ≤ C.
The hypoelliptic theorem of Hörmander implies the existence of s > 0 such that one has H 1 (X ) ⊂ H s (M ), hence the injection H 1 (X ) ⊂ L 2 (M ) is compact. As a direct byproduct, we get (up to extraction of a subsequence) that the sequence f n converge strongly in L 2 to some f ∈ H 1 (X ), and v n converge weakly in H 1 (X ) to f . Set v n = f + r n . Then r n converge weakly to 0 in H 1 (X ), f n = f + r n + h n γ n , and one has

E hn (f n ) = E hn (f ) + 2Re(B hn (f, r n + hγ n )) + E hn (r n + h n γ n )
Since one has E h (.) ≥ 0, proposition 5.1 implies

1 6p p k=1 X k f 2 L 2 = lim n→∞ E hn (f ) ≤ lim inf n→∞ E hn (f n ) = 0 (5.15)
and therefore f = Cte. But since f n converge strongly in L 2 to f , one has f L 2 = 1 and (f |1) L 2 = M f dµ = 0. This is a contradiction. The proof of lemma 5.2 is complete

To conclude the proof of theorem 1.1, it remains to prove the total variation estimate (1.7). Let Π 0 be the orthogonal projector in L 2 (M, dµ) onto the space of constant functions

Π 0 (f )(x) = M f dµ (5.16) Then 2sup x∈M t n h (x, dy) -µ T V = T n h -Π 0 L ∞ →L ∞
(5.17) Thus, we have to prove that there exist C 0 , h 0 , such that for any n and any h ∈]0, h 0 ], one has

T n h -Π 0 L ∞ →L ∞ ≤ C 0 e -ng(h) (5.18)
Observe that since g(h) ≃ h 2 , and

T n h -Π 0 L ∞ →L ∞ ≤ 2
, in the proof of (5.18), we may assume n ≥ Ch -2 with C large. Let E h,L be the (finite dimensional) subspace of L 2 (M, dµ) span by the eigenvectors e j,h of |△ h |, associated with eigenvalues λ j,h ≤ C 4 h -2 , with C 4 > 0 small enough. Here, the subscript L means "low freqencies". Recall from (5.9) dim(E h,L ) ≤ Ch -dim(M )/2s . We will denote by J h the set of indices

J h = {j, λ j,h ≤ C 4 h -2 } (5.19)
Lemma 5.3 There exist p > 2 and C independent of h ∈]0, h 0 ] such that for all u ∈ E h,L , the following inequality holds true

u 2 L p (M ) ≤ C(E h (u) + u 2 L 2 ) (5.20)
Proof. We denote by C > 0 a constant independent of h, changing from line to line. Let

u ∈ E h,L such that E h (u) + u 2 L 2 ≤ 1. From proposition 4.1, one has u = v h + w h with v h H 1 (X ) ≤ C and w h L 2 ≤ Ch. From the continuous imbedding H 1 (X ) ⊂ H s (M ) ⊂ L q (M ) with s > 0, q > 2, s = dim(M )(1/2 -1/q), we get v h L q ≤ C
One has u = λ j,h ≤C 4 h -2 z j,h e j,h with λ j,h ≤C 4 h -2 |z j,h | 2 ≤ 1. From corollary 3.4, one has for C 4 > 0 small enough e j,h L ∞ ≤ Ch -Q/2 . Therefore by Cauchy-Schwarz we get

u L ∞ ≤ Ch -Q/2 ( λ j,h ≤C 4 h -2 |z j,h | 2 ) 1/2 (dim(E h,L )) 1/2 ≤ Ch -Q/2-dim(M )/4s
(5.21)

From the proof of proposition 4.1 (see lemma 4.3), one has

v h L ∞ ≤ C u L ∞ . Thus we get w h L ∞ ≤ u L ∞ + v h L ∞ ≤ Ch -Q/2-dim(M )/4s
. Since w h L 2 ≤ Ch we get by interpolation that there exists q ′ > 2 such that w h L q ′ ≤ C Then (5.20) holds true with p = min(q, q ′ ) > 2. The proof of lemma 5.3 is complete.

We are now ready to prove (5.18), essentially following the strategy of [DLM11], but with some simplifications. We split T h in 2 pieces, according to the spectral theory. We write

T h -Π 0 = T h,1 + T h,2 with T h,1 (x, y) = λ 1,h ≤λ j,h ≤C 4 h -2
(1h 2 λ j,h )e j,h (x)e j,h (y)

(5.22)

One has T n h -Π 0 = T n h,1 + T n h,2
, and we will get the bound (5.18) for each of the two terms. We start by very rough bounds. From e j,h

L ∞ ≤ Ch -Q/2 , |(1 -h 2 λ j,h )| ≤ 1, we get with A = Q/2 + dim(M )/4s,
as in the proof of (5.21) with C independent of n ≥ 1 and h

T n h,1 L ∞ →L ∞ ≤ T n h,1 L 2 →L ∞ . ≤ Ch -A (5.23) Since T n h is bounded by 1 on L ∞ , we get from T n h -Π 0 = T n h,1 + T n h,2 T n h,2 L ∞ →L ∞ . ≤ Ch -A (5.24)
Let P be the integer defined at the beginning of section 3. Let M h be the Markov operator M h = T P h . Write n = kP + r with 0 ≤ r < P . From proposition 3.1 and corollary 3.3 one has

M h = ρ h + R h with ρ h L ∞ →L ∞ ≤ γ < 1, R h L 2 →L ∞ ≤ C 0 h -Q/2 .
(5.25)

From this, we deduce that for any k = 1, 2, . . . , one has

M k h = A k,h +B k,h , with A 1,h = ρ h , B 1,h = R h and the recurrence relation A k+1,h = ρ h A k,h , B k+1,h = ρ h B k,h + R h M k h . Thus one gets, since M k h is bounded by 1 on L 2 , A k,h L ∞ →L ∞ ≤ γ k , B k,h L 2 →L ∞ ≤ C 0 h -Q/2 (1 + γ + • • • + γ k ) ≤ C 0 h -Q/2 (1 -γ). (5.26) Let θ = 1 -C 4 < 1 so that T h,2 L 2 →L 2 ≤ θ. Then one has T n h,2 L ∞ →L 2 ≤ T n h,2 L 2 →L 2 ≤ θ n (5.27)
For m ≥ 1, k ≥ 1, and 0 ≤ r < P -1, one gets, using the fact that T h is bounded by 1 on L ∞ and (5.24), (5.26), and (5.27)

T kP +r+m h,2 L ∞ →L ∞ = T r h M k h T m h,2 L ∞ →L ∞ ≤ M k h T m h,2 L ∞ →L ∞ ≤ A k,h T m h,2 L ∞ →L ∞ + B k,h T m h,2 L ∞ →L ∞ ≤ Ch -A γ k + C 0 h -Q/2 θ m (1 -γ).
(5.28)

Thus we get, that there exists C > 0, µ > 0, and a large constant B >> 1 such that

T n h,2 L ∞ →L ∞ ≤ Ce -µn , ∀h, ∀n ≥ B log(1/h), (5.29)
and thus the contribution of T n h,2 is far smaller than the bound we have to prove in (5.18). It remains to study the contribution of T n h,1 . From lemma 5.3, using the interpolation inequality u

2 L 2 ≤ u p p-1 L p u p-2 p-1 L 1 , we deduce the Nash inequality, with 1/d = 2 -4/p > 0 u 2+1/d L 2 ≤ C(E h (u) + u 2 L 2 ) u 1/d L 1 , ∀u ∈ E h,L (5.30)
For λ j,h ≤ C 4 h -2 , one has h 2 λ j,h ≤ 1, and thus for any u ∈ E h,L , one gets

E h (u) ≤ u 2 L 2 - T h u 2
L 2 , thus we get from 5.30

u 2+1/d L 2 ≤ Ch -2 (( u 2 L 2 -T h u 2 L 2 + h 2 u 2 L 2 ) u 1/d L 1 , ∀u ∈ E h,L (5.31)
From (5.29) and

T n h -Π 0 = T n h,1 + T n h,2
, we get that there exists C 2 such that for all h and all n ≥ B log(1/h) one has

T n 1,h L ∞ →L ∞ ≤ C 2 and thus since T 1,h is self adjoint on L 2 , T n 1,h L 1 →L 1 ≤ C 2 . Fix p ≃ B log(1/h). Take g ∈ L 2 such that g L 1 ≤ 1 and consider the sequence c n , n ≥ 0 c n = T n+p h,1 g 2 L 2
(5.32)

Then, 0 ≤ c n+1 ≤ c n and from 5.31 and

T n+p h,1 g ∈ E h,L , we get c 1+ 1 2d n ≤ Ch -2 (c n -c n+1 + h 2 c n ) T n+p h,1 g 1/d L 1 ≤ CC 1/d 2 h -2 (c n -c n+1 + h 2 c n ) (5.33)
Thus there exist A which depends only on C, C 2 , d, such that for all 0 ≤ n ≤ h -2 , one has c n ≤ ( Ah -2 1+n ) 2d (this is the key point in the argument, for a proof of this estimate, see [START_REF] Diaconis | What do we know about the metropolis algorithm[END_REF]). Thus for all 0 ≤ n ≤ h -2 and with p ≃ B log(1/h) one has

T n+p h,1 g L 2 ≤ ( Ah -2 1 + n ) d g L 1 (5.34) which implies by duality since T 1,h is selfadjoint on L 2 T n+p h,1 g L ∞ ≤ ( Ah -2 1 + n ) d g L 2 (5.35)
Thus there exist C 0 , such that for N ≃ h -2 , one has

T N +p h,1 g L ∞ ≤ C 0 g L 2 (5.36)
and so we get for any m ≥ 0 and with

N ≃ h -2 T N +p+m h,1 g L ∞ ≤ C 0 (1 -h 2 λ 1,h ) m g L 2 (5.37) Thus for n ≥ h -2 + N + p, since h 2 λ 1,h = g(h) and 0 ≤ (1 -r) m ≤ e -mr for r ∈ [0, 1], we get T n h,1 L ∞ →L ∞ ≤ C 0 e -(n-(N +p))g(h) = C 0 e (N +p)g(h) e -ng(h) ≤ C ′ 0 e -ng(h) (5.38)
The proof of theorem 1.1 is complete.

Proof of theorem 1.2

The proof of Theorem 1.2 is exactly the same that the one given in [START_REF] Diaconis | Metropolis algorithm on convex polytops[END_REF]. Let R > 0 be fixed. If ν h ∈ [0, R] and u h ∈ L 2 (M ) satisfy |△ h |u h = ν h u h and u h L 2 = 1, then, thanks to proposition 4.1, u h can be decomposed as u h = v h + w h with w h L 2 = O(h) and v h bounded in H 1 (X ). Hence (extracting a subsequence if necessary) it may be assumed that v h weakly converges in H 1 (X ) to a limit v and that ν h converges to a limit ν. Hence u h converge strongly in L 2 to v. It now follows from proposition 5.1 that for any f ∈ C ∞ (M ),

ν(f |v) = lim h→0 (f |ν h u h ) = lim h→0 (|△ h |(f )|u h ) = lim h→0 B h (f, v h + w h ) = 1 6p p k=1 (X k f |X k v) L 2 = (f |Lv)
(5.39) Since f is arbitrary, it follows that (Lν)v = 0 . By the Weyl type estimate (5.9) the number of eigenvalues |△ h | in the interval [0, R] is uniformly bounded. Moreover, the dimension of an orthonormal basis is preserved by strong limit. So the above argument proves that for any ǫ > 0 small, there exists h ǫ > 0 such that for h ∈]0, h ǫ ], one has

Spec(|∆ h |) ∩ [0, R] ⊂ ∪ j [ν j -ǫ, ν j + ǫ]
(5.40)

and ♯Spec(|∆ h |) ∩ [ν j -ǫ, ν j + ǫ] ≤ m j (5.41)
The fact that one has equality in (5.41) for ǫ small follows exactly like in the proof of theorem 2 iii) in [START_REF] Diaconis | Metropolis algorithm on convex polytops[END_REF]: this use only proposition 5.1, the min-max principle and a compactness argument. The proof of theorem 1.2 is complete.

Remark 5.4 Observe that the estimate (5.14) on the spectral gap is a direct consequence of theorem 1.2, and moreover observe that in the proof of theorem 1.2 we only use proposition 5.1 in the special case f ∈ C ∞ (M ), and that for f ∈ C ∞ (M ), proposition 5.1 is obvious. However, we think that the fact that proposition 5.1 holds true for any function f ∈ H 1 (X ) is interesting by itself, and since it is an easy byproduct of proposition 4.1, we decide to include it in the paper.

Elementary Fourier Analysis

We conclude this section by collecting some basic results on the Fourier analysis theory (uniformly with respect to h) associated to the spectral decomposition of T h . These results are consequences of the preceding estimates. We start with the following lemma which gives an honest L ∞ estimate on the eigenfunction e j,h ∈ E h,L . Recall < x >= (1 + x 2 ) 1/2 . Lemma 5.5 There exists C independent of h such that for any eigenfunction e j,h ∈ E h,L , e j,h L 2 = 1, associated to the eigenvalue 1h 2 λ j,h of T h the following inequality holds true

e j,h L ∞ ≤ C < λ j,h > d (5.42)
Proof. This is a byproduct of the preceding estimate (5.35). Apply this inequality to g = e j,h . This gives

(1 -h 2 λ j,h ) n+p e j,h L ∞ ≤ ( Ah -2 1 + n ) d (5.43) Thus we get with n ≃ h -2 < λ j,h > -1 e j,h L ∞ ≤ ( Ah -2 h -2 < λ j,h > -1 ) d (1 -h 2 λ j,h ) -h -2 <λ j,h > -1 -B log(1/h) ≤ C < λ j,h > d
(5.44)

The proof of lemma 5.5 is complete.

Let h 0 > 0 be a small given real number. We will use the following notations. If X is a Banach space, we denote by X h the space L ∞ (]0, h 0 ], X), i.e the space of functions h → x h from h ∈]0, h 0 ] into X such that sup h∈]0,h 0 ] x h X < ∞. For a ≥ 0, the notation x h ∈ O X (h a ) means that there exists C independent of h such that x h X ≤ Ch a , and

x h ∈ O X (h ∞ ) means x h ∈ O X (h a ) for all a. We denote C ∞ h = ∩ k≥0 C k h (M )
. Let Π h,L be the L 2 -orthogonal projection on E h,L , and denote Π h,2 = Id -Π h,L . Let (e j,h ) j∈J h be an orthonormal basis of E h,L with T h (e j,h ) = (1h 2 λ j,h )e j,h . For f ∈ L 2 we denote by c j,h (f ) = (f |e j,h ) the corresponding Fourier coefficient of f . Recall that J h is defined in (5.19).

Proposition 5.6 Let f h ∈ C ∞ h .
For all integer N , the following holds true.

|△ h | N f h ∈ C ∞ h and ∃ C N , sup h∈]0,h 0 ] j∈J h λ N j,h |c j,h (f h )| 2 ≤ C N (5.45)
Moreover, one has the following estimates

Π h,L (f h ) ∈ O L ∞ (M ) (1) (5.46) Π h,2 (f h ) ∈ O L ∞ (M ) (h N ) (5.47)
Proof. Let X be a vector field on M , and f ∈ C ∞ (M ). The smooth function F (t, x) = f (e tX x) satisfy the transport equation

∂ t F = X(f ), F (0, x) = f (x)
Thus, one has by Taylor expansion at t = 0, and for any integer N

F (t, x) = n≤N t n n! X n (f )(x) + t N +1 r N (t, x)
with r N (t, x) smooth. From the definition of T h , we thus get

T h f (x) n even ≤N h n (n + 1)! 1 p p k=1 X n k (f )(x) + h N +1 rN (h, x) with rN (h, x) ∈ C ∞ h . This implies for f h ∈ C ∞ h |△ h |f h = L(f h ) + h 2 g h , g h ∈ C ∞ h Therefore, one has |△ h |f h ∈ C ∞ h , hence by induction |△ h | N f h ∈ C ∞ h for all N .
The second assertion of (5.45) follows from sup h∈]0,h 0 ] g h L 2 < ∞ for any g h ∈ C ∞ h and the fact

j∈J h λ N j,h |c j,h (f h )| 2 = Π h,L |△ h | N f h 2 L 2 ≤ |△ h | N f h 2 L 2
For the proof of (5.46), we just write

Π h,L (f h ) = j∈J h c j,h (f h )e j,h
and we use the estimate (5.42) of lemma 5.5 to get the bound

Π h,L (f h ) L ∞ ≤ C j∈J h |c j,h (f h )| < λ j,h > d ≤ C j∈J h |c j,h (f h )| 2 < λ j,h > 2d+2N 1/2 j∈J h < λ j,h > -2N 1/2
From the Weyl type estimate (5.9), there exists N and C independent of h such that

j∈J h < λ j,h > -2N 1/2 ≤ C
and therefore (5.46) follows from (5.45). It remains to prove the estimate (5.47). We first prove the weaker estimate

Π h,2 (f h ) ∈ O L 2 (M ) (h N ) (5.48)
Observe that Π h,2 (f h ) satisfies for all N ≥ 1 the equation

h 2N Π h,2 (|△ h | N f h ) = (h 2 |△ h |) N Π h,2 (f h ) = (Id -T h Π h,2 ) N Π h,2 (f h ) (5.49)
By (5.27), the operator

Id -T h Π h,2 = Id -T h,2 is invertible on L 2 with inverse bounded by (1 -θ) -1 . Since |△ h | N f h ∈ C ∞ h we get from (5.49) Π h,2 (f h ) ∈ O L 2 (h 2N ). Set g h = Π h,2 (f h ). One has |△ h | N f h = Π h,L (|△ h | N f h ) + |△ h | N g h . From (5.45) and (5.46), one has Π h,L (|△ h | N f h ) ∈ O L ∞ (1). Thus we get |△ h | N g h ∈ O L ∞ (1) for any N . Let M h = T P h , and | △h | = (Id + T h + ... + T P -1 h )|△ h |. Then g h satisfies the equation h 2 | △h |g h = g h -M h g h (5.50)
As in (5.25), write M h = ρ h + R h . Since T h is bounded by 1 on L ∞ , one gets

g h -ρ h g h = h 2 r h + R h g h , r h = | △h |g h ∈ O L ∞ (1).
(5.51) By the second line of (5.25) and (5.48) one has R h g h ∈ O L ∞ (h ∞ ), and by the first line of (5.25), the operator Idρ h is invertible on L ∞ with inverse bounded by (1γ) -1 . Thus we get from (5.51)

g h ∈ O L ∞ (h 2 ). Since | △h |g h = Π h,2 (| △h |f h ) and | △h |f h ∈ C ∞ h , the same esti- mates shows | △h |g h = r h ∈ O L ∞ (h 2 ). Then (5.51) implies g h ∈ O L ∞ (h 4 ). By induction, we get g h ∈ O L ∞ (h 2N
) for all N . The proof of proposition 5.6 is complete.

Let F k = Ker(L -ν k ). Recall m k = dim(F k ) is the multiplicity of the eigenvalue ν k of L.
Let us denote by J k the set of indices j such that for h small, λ j,h is close to ν k , and F h,k = span(e j,h , j ∈ J k ). By theorem 1.2 and his proof, the set J k is independent of h ∈]0, h k ] for h k small, and one has

♯(J k ) = dim(F h,k ) = k for h ∈]0, h k ] . Let Π F k and Π F h,k the L 2 -orthogonal projectors on F k and F h,k . Lemma 5.7 For all f ∈ F k one has lim h→0 f -Π F h,k (f ) L ∞ = 0
(5.52)

Proof. For f ∈ F k , and h small, one has

f -Π F h,k (f ) = j∈J h \J k c j,h (f )e j,h + Π h,2 (f ) (5.53)
One has f ∈ C ∞ h , and thus by (5.47), we get

Π h,2 (f ) ∈ O L ∞ (h ∞ ) (5.54)
Since f ∈ F k , for any given j ∈ J h \J k , one has lim h→0 c j,h (f ) = lim h→0 (f |e j,h ) L 2 = 0. Therefore, it remains to proove lim

N →∞ sup h∈]0,h 0 ] j∈J h ,j≥N |c j,h (f )| e j,h L ∞ = 0 (5.55)
Let N >> ν k . From (5.42), Cauchy-Schwarz inequality, (5.45), and the Weyl type estimate (5.9), there exist N 0 and a constant C(f ) independent of h such that one has the estimate

j∈J h ,j≥N |c j,h (f )| e j,h L ∞ ≤ C j∈J h ,j≥N |c j,h (f )| < λ j,h > d ≤ C j∈J h |c j,h (f )| 2 < λ j,h > 2d+2N 0 1/2 j∈J h ,j≥N < λ j,h > -2N 0 1/2 ≤ C(f ) sup h∈]0,h 0 ] j∈J h ,j≥N < λ j,h > -2N 0 1/2 -→ 0 (N → ∞)
(5.56)

In fact, since by (5.9) one has ♯{j, λ j,h ≤ m} ≤ C 5 < m > dim(M )/2s , one can choose N 0 = 1 + dim(M )/4s. Then one has

sup h∈]0,h 0 ] j∈J h ,j≥N < λ j,h > -2N 0 ≤ C 5 m≥m(N ) < m > -2N 0 < m + 1 > dim(M )/2s
with m(N ) the bigger integer such that λ N,h ≥ m(N ) for any h ∈]0, h 0 ]. Observe that (5.9) implies lim N →∞ m(N ) = ∞. The proof of lemma 5.7 is complete.

The hypoelliptic diffusion

We refer to the paper of J.-M. Bismut [START_REF] Bismut | Martingales, the malliavin calculus,and hypoellipticity under general hörmander conditions[END_REF] and references therein for a construction of the hypoelliptic diffusion associated to the generator L.

For a given x 0 ∈ M , let X x 0 = {ω ∈ C 0 ([0, ∞[, M ), ω(0) = x 0 } be the set of continuous paths from [0, ∞[ to M , starting at x 0 , equipped with the topology of uniform convergence on compact subsets of [0, ∞[, and let B be the Borel σ-field generated by the open sets in X x 0 . We denote by W x 0 the Wiener measure on X x 0 associated to the hypoelliptic diffusion with generator L. Let p t (x, y)dµ(y) be the heat kernel, i.e the kernel of the self-adjoint operator e -tL , t ≥ 0. Then W x 0 is the unique probability on (X x 0 , B), such that for any 0 < t 1 < t 2 < ... < t k and any Borel sets A 1 , ..., A k in M , one has We denote by Y N the infinite product space Y N = {y = (y 1 , y 2 , ..., y n , ...), y j ∈ Y }. Equipped with the product topology, it is a compact metrisable space, and we denote by ρ N the product probability on Y N . Let M N be the infinit product space M N = {x = (x 1 , x 2 , ..., x n , ...), x j ∈ M }.

W x 0 (ω(t 1 ) ∈ A 1 , ω(t 2 ) ∈ A 2 , ..., ω(t k ) ∈ A k ) = A 1 ×A 2 ×...×A k p t k -t k-1 (x k , x k-1 )...p t 2 -t 1 (x 2 , x 1 )p t 1 (x 1 , x 0 )dµ(x 1 )dµ(x 2 )...dµ(x k ) ( 6
Equipped with the product topology, M N is a compact metrisable space. For h ∈]0, 1], and x 0 ∈ M , let π x 0 ,h be the continuous map from Y N into M N defined by π x 0 ,h ((k j , s j ) j≥1 ) = (x j ) j≥1 , x j = e s j hX k j ...e s 2 hX k 2 e s 1 hX k 1 x 0 (6.3)

We will use the notation X n h,x 0 = (π x 0 ,h ) n . This means that X n h,x 0 is the position after n step of the random walk starting at x 0 . Let P x 0 ,h be the probability on M N defined by P x 0 ,h = (π x 0 ,h ) * (ρ N ). Then by construction, one has for all Borel sets A 1 , ..., A k in M

P x 0 ,h (x 1 ∈ A 1 , x 2 ∈ A 2 , ..., x k ∈ A k ) = A 1 ×A 2 ×...×A k t h (x k-1 , dx k )...t h (x 1 , dx 2 )t h (x 0 , dx 1 ) (6.4)
Let j x 0 ,h be the map from Y N into X x 0 defined by, with y = ((k j , s j ) j≥1 )

j x 0 ,h (y) = ω ⇐⇒ ∀j ≥ 0, ∀t ∈ [0, h 2 ], ω(jh 2 + t) = e t h 2
hs j X k j x j with x j = (π x 0 ,h (y)) j if j ≥ 1 (6.5)

Let P x 0 ,h be the probability on X x 0 defined as the image of ρ N by the continuous map j x 0 ,h . Our aim is to prove the following theorem of weak convergence of P x 0 ,h to the Wiener measure W x 0 when h → 0.

Theorem 6.1 For any bounded continuous function ω → f (ω) on X x 0 , one has lim h→0 f dP x 0 ,h = f dW x 0 (6.6)

Observe that the proof below shows that our study of the Markov kernel T h on M is also a way to prove the existence of the Wiener measure W x 0 associated to the hypoelliptic diffusion. Let g be a Riemannian distance on M and let d g the associated distance. We start by proving that the family of probability P x 0 ,h is tight, hence compact by the Prohorov theorem. Proposition 6.2 For any ε > 0, there exists h ε > 0 such that the following holds true for any T > 0. lim

δ→0 sup h∈]0,hε] P x 0 ,h ( max |s-t|≤δ, 0≤s,t≤T d g (ω(s), ω(t)) > ε) = 0 (6.7)
Proof. We start with the following lemma.

Lemma 6.3 Let f ∈ C ∞ (M ).
There exists C such that for all h ∈]0, h 0 ], one has

∀δ ∈ [0, 1], sup nh 2 ≤δ T n h (f ) -f -nh 2 |△ h |f L ∞ ≤ Cδ 2 (6.8)
Proof. We may assume δ > 0 and n ≥ 1. Then nh 2 ≤ δ implies h ≤ √ δ. With the notation of section 5, one has

T n h (f ) -f -nh 2 |△ h |f = j∈J h c j,h (f ) (1 -h 2 λ j,h ) n -1 -nh 2 λ j,h e j,h + R(n, h) R(n, h) = T n h Π h,2 (f ) -Π h,2 (f + nh 2 |△ h |f ) (6.9)
One has |△ h |f ∈ C ∞ h by (5.45), T h is bounded by 1 on L ∞ , and nh 2 ≤ δ ≤ 1. Thus from (5.47) we get sup

nh 2 ≤δ R(n, h) L ∞ ∈ O(h ∞ ) ⊂ O(δ ∞ ) (6.10)
For all j ∈ J h one has h 2 λ j,h ∈ [0, 1] and for all x ∈ [0, 1]

|(1 -x) n -1 -nx| ≤ n(n -1) 2 x 2
Therefore we get

j∈J h c j,h (f ) (1 -h 2 λ j,h ) n -1 -nh 2 λ j,h e j,h L ∞ ≤ n 2 h 4 2 j∈J h λ 2 j,h |c j,h (f )| e j,h L ∞ (6.11)
By the Weyl type estimate (5.9), (5.42) and (5.45), there exists a constant C such that

sup h∈]0,h 0 ] j∈J h λ 2 j,h |c j,h (f )| e j,h L ∞ ≤ C
Therefore (6.8) is consequence of (6.10) and (6.11). The proof of lemma 6.3 is complete.

The proof of proposition 6.2 is now standard and proceeds as follows. Let ε 0 > 0 small with respect to the injectivity radius of the Riemannian manifold (M, g), and let ε ∈]0, ε 0 ] be fixed. One has

ρ N (d g (X n h,x 0 , x 0 ) > ε) = dg (y,x 0 )>ε t n h (x 0 , dy) = T n h (1 dg (y,x 0 )>ε )(x 0 ) (6.12) Let ϕ(r) ∈ C ∞ ([0, ∞[
) be a nondecreasing function equal to 0 for r ≤ 3/4 and equal to 1 for r ≥ 1. Set

ϕ x 0 ,ε (x) = ϕ( d g (x, x 0 ) ε ) (6.13)
Then ϕ x 0 ,ε is a smooth function , and from 1 dg (y,x 0 )>ε ≤ ϕ x 0 ,ε ≤ 1, we get since T h is Markovian,

0 ≤ T n h (1 dg (y,x 0 )>ε ) ≤ T n h (ϕ x 0 ,ε ) (6.14)
Since T h moves the support at distance ≤ ch, one has ϕ x 0 ,ε (x 0 ) + nh 2 (|△ h |ϕ x 0 ,ε )(x 0 ) = 0 for ch ≤ ε/2, From lemma 6.3, we thus get that there exists h ε > 0 and C ε such that

sup h∈]0,hε] sup nh 2 ≤δ T n h (ϕ x 0 ,ε )(x 0 ) ≤ C ε δ 2 (6.15)
Since M is compact, it is clear from the proof of lemma 6.3 that we may assume C ε independent of x 0 ∈ M . From (6.12), (6.14) and (6.15) we get sup

x 0 ∈M sup h∈]0,hε] sup nh 2 ≤δ ρ N (d g (X n h,x 0 , x 0 ) > ε) ≤ C ε δ 2 (6.16)
Let T > 0 be given. One has for h ∈]0, h ε ] the following inequalities.

ρ N (∃j < l ≤ h -2 T, (l -j)h 2 ≤ δ, d g (X j h,x 0 , X l h,x 0 ) > 4ε) ≤ C δ sup y 0 ∈M ρ N (∃j < l ≤ h -2 δ, d g (X j h,y 0 , X l h,y 0 ) > 4ε) ≤ C δ sup y 0 ∈M ρ N (∃j ≤ h -2 δ, d g (X j h,y 0 , y 0 ) > 2ε) ≤ 2C δ sup z 0 ∈M,nh 2 ≤δ ρ N (d g (X n z 0 , z 0 ) > ε)
(by (6.16)) ≤ 2CC ε δ (6.17)

In fact, for the first inequality in (6.17), we just use the fact that the interval [0, T ] is a union of ≃ C/δ intervals of length δ/2. The second inequality is obvious since the event {∃j < l ≤ h -2 δ, d g (X j h,y 0 , X l h,y 0 ) > 4ε} is a subset of {∃j ≤ h -2 δ, d g (X j h,y 0 , y 0 ) > 2ε}. For the third one, we use the fact that the event A = {∃j ≤ h -2 δ, d g (X j h,y 0 , y 0 ) > 2ε} is contained in B ∪ j<k (C j ∩ D j ) with B = {d g (X k h,y 0 , y 0 ) > ε} (k is the greatest integer ≤ δh -2 ), C j = {d g (X j h,y 0 , X k h,y 0 ) > ε}, D j = {d g (X j h,y 0 , y 0 ) > 2ε and d g (X l h,y 0 , y 0 ) ≤ 2ε for l < j}, and the fact that C j and D j are independent and the D j are disjoints.

Since P x 0 ,h = (j x 0 ,h ) * (ρ N ), (6.7) follows easily from (6.17) and the definition (6.5) of the map j x 0 ,h . The proof of proposition 6.2 is complete.

With the result of proposition 6.2, the proof of theorem 6.1 follows now the classical proof of weak convergence of a sequence of random walks in the Euclidian space R d to the Brownian motion on R d , for which we refer to ([KS88], chapter 2.4). We have to prove that any weak limit P x 0 of a sequence P x 0 ,h k , h k → 0, is equal to the Wiener measure W x 0 . We denote by ω h (t) the map from Y N into M defined by ω h (t)(y) = j x 0 ,h (y)(t). By theorem 4.15 of [START_REF] Karatzas | Brownian Motion and Stochastic Calculus[END_REF] it is sufficient to show that for any m ≥ 1, any 0 < t 1 < ... < t m , and any continuous function f (x 1 , ..., x m ) defined on the space M m , one has lim h→0 Y N f (ω h (t 1 ), ..., ω h (t m ))dρ N = f (x 1 , ..., x m )p tm-t m-1 (x m , x m-1 )...p t 2 -t 1 (x 2 , x 1 )p t 1 (x 1 , x 0 )dµ(x 1 )dµ(x 2 )...dµ(x m ) (6.18)

As in [START_REF] Karatzas | Brownian Motion and Stochastic Calculus[END_REF], we may assume m = 2. For a given t ≥ 0, let n(t, h) ∈ N be the greatest integer such that h 2 n(t, h) ≤ t. By (6.5)), one has for some c > 0 independent of h and y ∈ Y N , d g (ω h (t), X n(t,h) h,x 0 ) ≤ ch. Since f is uniformly continuous on M m , we are reduce to prove lim h→0 f (X n(t 1 ,h) h,x 0 , X n(t 2 ,h) h,x 0 )dρ N = f (x 1 , x 2 )p t 2 -t 1 (x 2 , x 1 )p t 1 (x 1 , x 0 )dµ(x 1 )dµ(x 2 ) (6.19) From (6.4), one has f (X (f (x 1 , .))(x 1 ) (x 0 ) = e -t 1 L e -(t 2 -t 1 )L (f (x 1 , .))(x 1 ) (x 0 ) (6.22) Since T n(t,h) h L ∞ ≤ 1 and e -tL L ∞ ≤ 1, the following "central limit" theorem will conclude the proof of theorem 6.1. Lemma 6.4 For all f ∈ C 0 (M ), and all t > 0, one has lim h→0 e -tL (f ) -T n(t,h) h (f ) L ∞ = 0 (6.23)

n(t 1 ,h) h,x 0 , X n(t 2 ,h) h,x 0 )dρ N = f (x 1 , x 2 )
Since one has T n(t,h) h L ∞ ≤ 1 and e -tL L ∞ ≤ 1, it is sufficient to prove that (6.23) holds true for f ∈ D, with D a dense subset of the space C 0 (M ), and therefore we may assume that f ∈ F k is an eigenvector of L associated to the eigenvalue ν k . We set n = n(t, h), and we use the notation of section 5. One has

T n h (f ) = j∈J k c j,h (f )(1 -h 2 λ j,h
) n e j,h + R t,h (f )

R t,h (f ) = j∈J h \J k c j,h (f )(1 -h 2 λ j,h
) n e j,h + T n h Π h,2 (f ) (6.24)

One has |(1h 2 λ j,h ) n | ≤ 1 and T h is bounded by 1 on L ∞ . By (5.54) and (5.55), we thus get

lim h→0 R t,h (f ) L ∞ = 0
One has lim h→0 (1h 2 λ j,h ) n(t,h) = e -tν k for all j ∈ J k . Moreover, one has ♯J k = m k and sup h∈]0,h 0 ] sup j∈J k e j,h L ∞ < ∞ by lemma 5.5. Therefore lemma 5.7 and e -tL (f ) = e -tν k f implies lim h→0 j∈J k c j,h (f )(1h 2 λ j,h ) n e j,he -tL (f ) L ∞ = 0

The proof of lemma 6.4 is complete.

Appendix

Let P = P (x, ∂ x ) be an elliptic second order differential operator on M , with smooth coefficients, such that P = P * ≥ Id, where P * is the formal adjoint on L 2 (M, µ) = L 2 . Let (e j ) j≥1 be an orthonormal basis of eigenfunctions of P in L 2 , and 1 ≤ ν 1 ≤ ν 2 ... be the associated eigenvalues. By the classical Weyl formula, one has #{j, ν 1/2 j ≤ r} ≃ r dim(X) (7.1)

For s ∈ R and f = j f j e j in the Sobolev space H s (M ), we set

v 2 H s = j ν s j |f j | 2 = (P s f |f ) L 2
Let us recall that this H s -norm depends on P , but an other choice for P gives an equivalent norm. The following elementary lemma is useful for us.

Lemma 7.1 Let s > 0 and A h = A * h ≥ 0, h ∈]0, 1] a family of non negative self-adjoint bounded operators acting on L 2 (M, µ). Assume that there exists a constant C 0 > 0 independent of h such that

((Id + A h )u|u) ≤ 1 ⇒ ∃(v, w) ∈ H s × L 2 such that u = v + w, v H s ≤ C 0 , w L 2 ≤ C 0 h (7.2) Let C 1 < 1 4C 2 0
. There exists C 2 > 0 independent of h such that Spec(A h ) ∩ [0, λ -1] is discrete for all λ ≤ C 1 h -2 and #(Spec(A h ) ∩ [0, λ -1]) ≤ C 2 < λ > dim(M )/2s , ∀λ ≤ C 1 h -2 (7.3)

Here, #(Spec(A h ) ∩ [0, r]) is the number of eigenvalues of A h in the interval [0, r] with multiplicities, and < λ >= √ 1 + λ 2 .

Proof. Let B h = Id + A h . Let C h be the bounded operator on L 2 defined by C h ( j u j e j ) = j min(h -1 , ν s/2 j )u j e j

For u = v + w one has

C h u 2 L 2 ≤ 2 C h v 2 L 2 + 2 C h w 2 L 2 ≤ 2( v 2 H s + h -2 w 2 L 2 )
From (7.2), we get for all u ∈ L 2 C h u 2 L 2 ≤ 4C 2 0 (B h u|u) (7.4)

For any non negative selfadjoint bounded operator T on L 2 , set for j ≥ 1

λ j (T ) = min dim(F )=j ( max u∈F, u L 2 =1 (T u|u))
It is well known that if #{j, λ j (T ) ∈ [0, a[} < ∞, the spectrum of T in [0, a[ is discrete and in that case, the λ j (T ) ∈ [0, a[ are the eigenvalues of T in [0, a[ with multiplicities. From (7.4), we get for all j ≥ 1 the inequality

λ j (B h ) ≥ 1 4C 2 0 λ j (C 2 h ) (7.5)
For all j such that ν s j < h -2 , one has λ j (C 2 h ) = ν s j , and therefore, for all λ < h -2 , we get from (7.1), #{j, λ j (C 2 h ) ≤ λ} ≤ C < λ > dim(M )/2s . Therefore, the spectrum of B h in [0, h -2 /4C 2 0 [ is discrete, and (7.3) follows from (7.5) and Spec(A h ) = Spec(B h ) -1. The proof of lemma 7.1 is complete.

Lemma 7.2 Let N = N 1 ⊕...⊕N r be the free up to rank r nilpotent Lie algebra with p generators. Let (Y 1 , ..., Y p ) be a basis of N 1 and let (Z 1 , ..., Z p ) be the right invariant vector fields on N such that Z j (0) = Y j . Let S(N ) be the Schwartz space of N . Let ϕ ∈ S(N ), be such that N ϕdx = 0. Then there exists ϕ k ∈ S(N ) such that ϕ = where the p α,β are polynomials in u depending only on (u 1 , ..., u j ) with j < |β|. Therefore, there exists polynomials q α,β such that

∂ α = Z α + |β|>|α| Z β q α,β
Since the Schwartz space S(N ) is stable by multiplication by polynomials, we get from (7.7) that there exists φ α ∈ S(N ) such that ϕ = α∈A Z α (φ α ) (7.8)

For |α| > 1, there exists j ∈ {1, ..., p} and β with |β| = |α| -1 such that Z α = Z j Z β -Z β Z j . By induction on |α|, since the Schwartz space S(N ) is stable by the vector fields Z j , this shows that for any α and φ ∈ S(N ), there exists φ j ∈ S(N ) such that Z α (φ) = p j=1 Z j (φ j ). Thus (7.6) follows from (7.8). The proof of lemma 7.2 is complete.

  For a ∈ N close to e and u = α∈A u α Y α ∈ T e N close to 0, let Λ(u) = α∈A u α Z α and Φ(a, u) = e Λ(u) a (4.18) Clearly, (a, u) → (a, Φ(a, u)) is a diffeomorphism of a neighborhood of (e, 0) in N × T e N onto a neighborhood of (e, e) in N × N , and Φ(a, 0) = a. We denote by Θ(a, b) the map defined in a neighborhood of (e, e) in N × N into a neighborhood of o N in N ≃ T e N by Φ(a, Θ(a, b)) = b (4.19) For b = Φ(a, u), one has Φ(b, -u) = e Λ(-u) (e Λ(u) a) = e -Λ(u) (e Λ(u) a) = a . Thus one has the symmetry relation Θ(a, b) = -Θ(b, a) = Θ(b, a) -1 (4.20) Observe that in the special case Z j = Ỹj , Λ(u) is equal to the left invariant vector field on N such that Λ(u)(o N ) = u, i.e Λ(u) = ũ and Φ(a, u) = e ũa = a.u, and this implies in that case Θ(a, b) = a -1 .b (4.21)

  by a constant which depends linearly on a finite number of derivatives of G. Clearly, there exists such a constant C such that h -l |G(Θ(y, x))| ≤ C| |h -1 .Θ(y, x)| | l . Thus the result follows from the proof of lemma 4.3, since | |u| | l ∂g ∂u l,k (x, u) is L 1 in u in both case a) and b) (the vector field | |u| | l ∂ ∂u l,k

. 1 )

 1 Let us first introduce some notations. Let Y = {1, ..., p} × [-1, 1] and let ρ be the uniform probability on Y . For any function g(k, s) on Y , one has Y

  Let Y α = H α (Y 1 , ..., Y p ) and let Z α be the right invariant vector fields on N such that Z α (0) = Y α . Let u α , α ∈ A be the coordinates on N associated to the basis (Y α , α ∈ A) of N . Let ∂ α be the derivative in the direction of u α . Let ϕ ∈ S(N ) such that N ϕdx = 0. Using the Fourier transform in coordinates (u α ), and φ(0) = 0, one get easily that there exists functions ψ α ∈ S(N ) such thatϕ = α∈A ∂ α (ψ α ) (7.7)By (2.3), the vector field Z α is of the formZ α = ∂ α + |β|>|α| p α,β (u <|β| ) ∂ β = ∂ α + |β|>|α| ∂ β p α,β (u <|β| )

  : R P -→ N be the smooth map defined for s = (s α,k ) α∈A,k=1,...,b |α| ∈ R P by the formula Φ w (s) =

	Let Φ r	br	e s α,k Z j |α| (k) w	(3.14)
	r=1 α∈Ar	k=1
	Since (Z β (w)) β∈A is a basis of T w N , u = (u β ) β∈A → e β∈A u β Z β w is a local coordinate system centered at w ∈ N , and therefore, there exists smooth functions U β,w (s) such that
	Φ w (s) = e β∈A U β,w (s)Z β w	(3.15)
	Moreover, it follows easily from the Campbell-Hausdorff formula, that one has U β,w (s) ∈ O(s |β| ) near s = 0. Let now κ : R Q -→ R P the map defined by
	(t α,l ) α∈A,l∈N |α| → (ǫ α (k)t α,ℓ |α| (k) ) α∈A,k=1,...,b |α|	(3.16)
			λ(z) w) dz	(3.13)

w

  t n(t 2 ,h)-n(t 1 ,h) h (x 1 , dx 2 )tBy (6.19), (6.20), we have to show that for any continuous function f (x 1 , x 2 ) on the product space M × M , one has , x 2 )p t 2 -t 1 (x 2 , x 1 )p t 1 (x 1 , x 0 )dµ(x 1 )dµ(x 2 )

	h n(t 1 ,h)	(x 0 , dx 1 )	(6.20)
	lim h→0 M ×M = f (x 1 (6.21) f (x 1 , x 2 )t n(t 2 ,h)-n(t 1 ,h) h (x 1 , dx 2 )t n(t 1 ,h) h (x 0 , dx 1 )
	M ×M
	or equivalently
	lim

h→0 T n(t 1 ,h) h T n(t 2 ,h)-n(t 1 ,h) h

Acknowledgement: We thank Dominique Bakry who has motivated us to study this problem.


Jean-Claude Bermond

David Coudert

Gianlorenzo D'angelo

Fatima-Zahra Moataz

Diverse Routing with Star SRLGs †

Keywords: SRLG, Diverse Routing, Colored Graph

. Dans un réseau satisfaisant la propriété d'étoile, un lien peut être affecté par plusieurs SRLGs, mais tous les liens affectés par un même SRLG sont incidents à un même sommet. Nous avons trouvé des contre-exemples à l'algorithme polynomial proposé dans [9] pour le calcul de paires de chemins SRLG-disjoints dans les réseaux satisfaisants la propriété d'étoile. Puis, nous avons prouvé que ce problème est en fait NP-difficile. Plus généralement, nous avons montré que le problème du routage diversifié dans les réseaux avec la propriété d'étoile est NP-difficile, APX-difficile, et W [1]-difficile lorsque le paramètre est le nombre de chemins SRLG-disjoints. Enfin, nous avons caractérisé de nouvelles instances polynomiales, en particulier lorsque le degré maximum des sommets est 4, ou lorsque le réseau est acyclique.

Introduction

To ensure reliable communications, many protection schemes have been proposed. One of the most used, called dedicated path protection, consists in computing for each demand both a working and a protection path. A general requirement is that these paths have to be diversely routed, so that at least one of them can survive a single failure in the network. This method works well in a single link failure scenario, as it consists in finding two edge-disjoint paths between a pair of nodes. This is a well-known problem in graph theory for which there exist efficient polynomial time algorithms. However, the problem of finding two diversely routed paths between a pair of nodes becomes much more difficult in case of multiple correlated link failures that can be captured by the notion of SRLG (Shared Risk Link Group). In fact, an SRLG is a set of network links that fail simultaneously when a given event (risk) occurs. The scope of this concept is very broad. It can correspond, for instance, to a set of fiber links of an optical backbone network that are physically buried at the same location and therefore could be cut simultaneously (i.e. backhoe or JCB fade). It can also represent links that are located in the same seismic area, or radio links in access and backhaul networks subject to localized environmental conditions affecting signal transmission, or traffic jam propagation in road networks. Note that a link can be affected by more than one risk. In practice, the failures are often localized and common SRLGs are SRLGs verifying the star property [START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF] (coincident SRLGs in [START_REF] Doucette | Shared-risk logical span groups in span-restorable optical networks : Analysis and capacity planning model[END_REF]). Under this property, all links of a given SRLG share an endpoint. Such failure scenarios can correspond to risks arising in router nodes like card failures or to the cut of a conduit containing links issued from a node (see Figure 1).

Related work

In the context of SRLG, basic network connectivity problems have been proven much more difficult to address than their counterparts for single failures. For instance, the problem of finding a "SRLG-shortest" † Full version of this work is available in [START_REF] Bermond | Diverse Routing with the star property[END_REF]. st-path which is a path from node s to node t having the minimum number of risks has been proven NP-hard and hard to approximate in general . However, the problem can be solved in polynomial time in two generic practical cases corresponding to localized failures : when all risks verify the star property [START_REF] Coudert | Shared risk resource groups and colored graph : Polynomial and FPT optimisation problems[END_REF] and when risks are of span 1 (i.e. when a link is affected by at most one risk and links sharing a given risk form a connected component [START_REF] Coudert | Shared risk resource group : Complexity and approximability issues[END_REF]).

l 1 l 6 l 5 l 4 l 3 l 2 l 8 l 7 l 1 l 6 l 5 l 4 l 3 l 2 l 8 l 7 r 4 r 3 r 2 r 1 v v P ort1 P ort3 P ort2
The diverse routing problem in presence of SRLGs consists in finding two SRLG-disjoint paths between a pair of vertices (i.e. paths having no risk in common). It has been proven NP-complete in general [START_REF] Hu | Diverse routing in mesh optical networks[END_REF][START_REF] Ellinas | Routing and restoration architectures in mesh optical networks[END_REF][START_REF] Li | Fiber span failure protection in mesh optical networks[END_REF][START_REF] Modiano | Survivable lightpath routing : a new approach to the design of WDM-based networks[END_REF] and many heuristics have been proposed. The problem is polynomial in some specific cases of localized failures : when SRLGs have span 1 [START_REF] Coudert | Shared risk resource group : Complexity and approximability issues[END_REF], and in a specific case of SRLGs having the star property [START_REF] Datta | Graph transformation approaches for diverse routing in shared risk resource group (SRRG) failures[END_REF] in which a link can be affected by at most two risks and two risks affecting the same link form stars at different nodes (this result also follows from results of [START_REF] Coudert | Shared risk resource group : Complexity and approximability issues[END_REF]).

Our results

We studied the diverse routing problem when SRLGs have the star property and there are no restrictions on the number of risks per link. This case has been studied in [START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF] in which the authors claim that the diverse routing problem with the star property can be solved in polynomial time. Unfortunately their algorithm is not correct ; indeed we exhibited counterexamples for which their algorithm concludes to the non existence of two SRLG-disjoint paths although two such paths exist. We proved that the problem is in fact NP-complete (again, contradicting the supposed polynomiality of the algorithm of [START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF], unless P = NP). On the positive side, we showed that the diverse routing problem can be solved in polynomial time in particular subcases which are relevant in practice. Namely, we solved the problem when the number of SRLGs is bounded by a constant, when the maximum degree is at most 4 or when the input network is a directed acyclic graph. Finally, we considered the problem of finding the maximum number of SRLG-disjoint paths. This problem has been shown to be NP-hard in [START_REF] Li | Fiber span failure protection in mesh optical networks[END_REF]. We proved that it is also NP-hard under the star property.

Diverse Routing with star SRLGs

Counterexample

Luo and Wang have published in [START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF] an algorithm to find a pair of SRLG-disjoint paths with minimum total cost from a source s to a destination t in graphs with SRLGs satisfying the star property. We have proved the incorrectness of their algorithm with counterexamples.

Figure 2 shows a counterexample where we have 2 specific risks r 1 and r 2 = r 1 forming a star in v. We obviously have two SRLG-disjoint paths P 1 = {s, a, z, w, u, v, b,t} and P 2 = {s, a , w, u , v, b ,t} but if we ran the algorithm of [START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF], it will terminate concluding that no two SRLG-disjoint paths exist (see full version in [START_REF] Bermond | Diverse Routing with the star property[END_REF] for more details). Given a multi-colored graph mG and two vertices s and t. We say that two st-paths P 1 and P 2 are color-

disjoint if (∪ e∈P 1 R (e)) ∩ (∪ e∈P 2 R (e)) = /
0. The diverse routing problem defined in the introduction consists then in finding k color-disjoint paths and can be formulated formally as follows :

Problem 1 (k-Diverse Colored st-Paths, k-DCP). Given a multi-colored graph mG and two vertices s and t, are there k color-disjoint st-paths from s to t ?

Another related problem we studied aims at finding the maximum number of color-disjoint paths and can be stated formally as follows :

Problem 2 (Max Diverse Colored st-Paths, MDCP). Given a multi-colored graph mG and two vertices s and t, find the maximum number of color-disjoint st-paths.

NP-completeness

Theorem. The k-DCP problem is NP-complete for any fixed constant k ≥ 2, even if all the following properties hold :

-the star property ; -the maximum degree ∆ is fixed with ∆ ≥ 6 + k ; -CPE, EPC and ∆ c are fixed with either [CPE ≥ 4, EPC ≥ 2, and

∆ c ≥ 14 + k] or [CPE ≥ 2, EPC ≥ 4 and ∆ c ≥ 2 + k].
we proved the above theorem by using a reduction from the problem of finding a T -compatible path (or a path avoiding forbidden transitions), which was proved NP-complete in [START_REF] Szeider | Finding paths in graphs avoiding forbidden transitions[END_REF].

Let G = (V, E) be an undirected graph. A transition in v ∈ V is a pair of edges incident to v. To each vertex v we associate a set T (v) of admissible (or allowed) transitions in v. We call transition system the set E) be a graph and T a transition system. A path P = {v 0 , e 1 , v 1 , . . . , e k , v k } in G, with v i ∈ V , e i ∈ E, is said to be T -compatible if, for every 1 ≤ i ≤ k -1, the pair of edges {e i , e i+1 } is an admissible transition , i.e. {e i , e i+1 } ∈ T (v i ).

T = {T (v) | v ∈ V }. Let G = (V,

Problem 3 (T -Compatible path, T -CP).

Given a graph G = (V, E), two vertices s and t in V , and a transition system T , does G contain a T -compatible path from s to t ?

The reduction consists in transforming an instance T -CP on a graph G to an instance of 2-DCP on a colored graph mG . The transformation is such that every edge in G is substituted by 2 paths, of length 2 each, in mG and colors are assigned in mG such that two color-disjoint paths can cross a vertex in mG if and only if a path in G can cross the same vertex using an allowed transition (see full version in [START_REF] Bermond | Diverse Routing with the star property[END_REF] for more details).

Conclusion

Our results give an almost complete characterization of the problem of finding SRLG-disjoint paths in networks with SRLGs satisfying the star property. We summarize them all in Table 1.

R éf érences

FIGURE 1 :

 1 FIGURE 1: Example of localized risks : link l 4 shares risk r 2 , corresponding to Port 2 failure, with l 5 and l 6 , and shares risk r 4 , corresponding to a conduit cut, with links l 2 and l 3 .

r 2 r 2 FIGURE 2 : 2

 222 FIGURE 2: Example 2

TABLE 1 :

 1 Summary of complexity results.