Persi Diaconis

Gilles Lebeau
email: lebeau@unice.fr

Laurent Michel

Geometric Analysis for the Metropolis Algorithm on Lipschitz Domains

This paper gives geometric tools: comparison, Nash and Sobolev inequalities for pieces of the relevent Markov operators, that give useful bounds on rates of convergence for the Metropolis algorithm. As an example, we treat the random placement of N hard discs in the unit square, the original application of the Metropolis algorithm.

Introduction and Results

Let Ω be a bounded, connected open subset of R d . We assume that its boundary, ∂Ω, has Lipschitz regularity. Let B 1 be the unit ball of R d and ϕ(z) = 1 vol(B 1 ) 1 B 1 (z) so that ϕ(z)dz = 1. Let ρ(x) be a measurable positive bounded function on Ω such that Ω ρ(x)dx = 1. For h ∈]0, 1], set

K h,ρ (x, y) = h -d ϕ x -y h min ρ(y) ρ(x) , 1 , (1.1)
and let T h,ρ be the Metropolis operator associated with these data, that is,

T h,ρ (u)(x) = m h,ρ (x)u(x) + Ω K h,ρ (x, y)u(y)dy, m h,ρ (x) = 1 - Ω K h,ρ (x, y)dy ≥ 0.
(1.2)

Then the Metropolis kernel T h,ρ (x, dy) = m h,ρ (x)δ x=y + K h,ρ (x, y)dy is a Markov kernel, the operator T h,ρ is self-adjoint on L 2 (Ω, ρ(x)dx), and thus the probability measure ρ(x)dx on Ω is stationary. For n ≥ 1, we denote by T n h,ρ (x, dy) the kernel of the iterated operator (T h,ρ ) n . For any x ∈ Ω, T n h,ρ (x, dy) is a probability measure on Ω, and our main goal is to get some estimates on the rate of convergence, when n → +∞, of the probability T n h,ρ (x, dy) toward the stationary probability ρ(y)dy.

A good example to keep in mind is the random placement of N non-overlapping discs of radius ε > 0 in the unit square. This was the original motivation for the work of Metropolis et al. [MRR + 53]. One version of their algorithm goes as follows: from a feasable configuration, pick a disc (uniformly at random) and a point within distance h of the center of the chosen disc (uniformly at random). If recentering the chosen disc at the chosen point results in a feasable configuration, the change is made. Otherwise, the configuration is kept as it started. If N is fixed and ε and h are small, this gives a Markov chain with a uniform stationary distribution over all feasable configurations. The state space consists of the N centers corresponding to feasible configurations. It is a bounded domain with a Lipschitz boundary when N ǫ is small (see Section 4, Proposition 4.1). The scientific motivation for the study of random packing of hard discs as a way of understanding the apparent existence of a liquid/solid phase transition for arbitrarily large temperatures (for suitably large pressure) is clearly described in Uhlenbeck [START_REF] Uhlenbeck | An outline of statistical mechanics[END_REF]Sect. 5,p. 18]. An overview of the large literature is in Lowen [START_REF] Löwen | Fun with hard spheres[END_REF]. Entry to the zoo of modern algorithms to do the simulation (particularly in the dense case) with many examples is in Krauth [START_REF] Krauth | Statistical Mechanics. Oxford Master Series in Physics[END_REF]. Further discussion, showing that the problem is still of current interest, is in Radin [START_REF] Radin | Random close packing of granular matter[END_REF].

We shall denote by g(h, ρ) the spectral gap of the Metropolis operator T h,ρ . It is defined as the largest constant such that the following inequality holds true for all u ∈ L 2 (ρ) = L 2 (Ω, ρ(x)dx).

u 2 L 2 (ρ) -(u|1) 2 L 2 (ρ) ≤ 1 g(h, ρ) (u -T h,ρ u|u) L 2 (ρ) , (1.3)
or equivalently, Ω×Ω |u(x)u(y)| 2 ρ(x)ρ(y)dxdy ≤ 1 g(h, ρ) Ω×Ω K h,ρ (x, y)|u(x)u(y)| 2 ρ(x)dxdy.

(1.4) Definition 1. We say that an open set Ω ⊂ R d is Lipschitz if it is bounded and for all a ∈ ∂Ω there exists an orthonormal basis R a of R d , an open set V = V ′ ×]α, α[ and a Lipschitz map η : V ′ →]α, α[ such that in the coordinates of R a , we have

V ∩ Ω = y ′ , y d < η(y ′ ) , (y ′ , y d ) ∈ V ′ ×] -α, α[ V ∩ ∂Ω = y ′ , η(y ′ ) , y ′ ∈ V ′ . (1.5)
Our first result is the following:

Theorem 1.1. Let Ω be an open, connected, bounded, Lipschitz subset of R d . Let 0 < m ≤ M < ∞ be given numbers. There exists h 0 > 0, δ 0 ∈]0, 1/2[ and constants C i > 0 such that for any h ∈]0, h 0 ], and any probability density ρ on Ω which satisfies for all x, m ≤ ρ(x) ≤ M , the following holds true.

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

C 1 (1 + λ) d/2 .
ii) The spectral gap g(h, ρ) 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)ρ(y)dy T V ≤ C 4 e -ng(h,ρ) .

(1.7)

The next result will give some more information on the behavior of the spectral gap g(h, ρ) when h → 0. To state this result, let

α d = ϕ(z)z 2 1 dz = 1 d ϕ(z)|z| 2 dz = 1 d + 2
(1.8) and let us define ν(ρ) as the largest constant such that the following inequality holds true for all u in the Sobolev space H 1 (Ω):

u 2 L 2 (ρ) -(u|1) 2 L 2 (ρ) ≤ 1 ν(ρ) α d 2 Ω
|∇u| 2 (x)ρ(x)dx, (1.9)

or equivalently,

Ω×Ω |u(x) -u(y)| 2 ρ(x)ρ(y)dxdy ≤ α d ν(ρ) Ω |∇u| 2 (x)ρ(x)dx.
(1.10)

Observe that for a Lipschitz domain Ω, the constant ν(ρ) is well-defined thanks to Sobolev embedding. For a smooth density ρ, this number ν(ρ) > 0 is closely related to the unbounded operator L ρ acting on on L 2 (ρ).

L ρ (u) = -α d 2 (△u + ∇ρ ρ .∇u) D(L ρ ) = u ∈ H 1 (Ω), -∆u ∈ L 2 (Ω), ∂ n u| ∂Ω = 0
(1.11)

We now justify and explain the choice of domain in (1.11). Background for the following discussion and tools for working in Lipschitz domains is in [START_REF] Adams | Pure and Applied Mathematics[END_REF].

When Ω has smooth boundary, standard elliptic regularity results show that for any u ∈ H 1 (Ω) such that -∆u ∈ L 2 (Ω), the normal derivative of u at the boundary, ∂ n u = -→ n (x).∇u| ∂Ω is well defined and belongs to the Sobolev space H -1/2 (∂Ω). Here, we denote by -→ n (x) the incoming unit normal vector to ∂Ω at a point x. In the case where ∂Ω has only Lipschitz regularity, the Sobolev spaces H s (∂Ω) are well defined for all s ∈ [-1, 1]. The trace operator, γ 0 (u) = u| ∂Ω maps H 1 (Ω) onto H 1/2 (∂Ω) = Ran(γ 0 ), and its kernel is Ker(γ 0 ) = H 1 0 (Ω). Equipped with the norm u H 1/2 = inf{ v H 1 , γ 0 (v) = u} it is an Hilbert space. Then, for any ϕ ∈ H 1/2 (∂Ω) * , there exists a unique v ∈ H -1/2 (∂Ω) such that ϕ(u) = ∂Ω vudσ for all u ∈ H 1/2 (∂Ω) (where σ is the measure induced on the boundary). For v ∈ H -1/2 (∂Ω), the support of v can be defined in a standard way. The trace operator acting on vector fields u ∈ (L 2 ) d with div(u) ∈ L 2 ,

γ 1 : u ∈ (L 2 (Ω)) d , div(u) ∈ L 2 (Ω) → H -1/2 (∂Ω),
(1.12) is then defined by the formula

Ω div(u)(x)v(x)dx = - Ω u(x).∇v(x)dx - ∂Ω γ 1 (u)v| ∂Ω dσ(x), ∀v ∈ H 1 (Ω). (1.13)
In particular, for u ∈ H 1 (Ω) satisfying ∆u = div∇u ∈ L 2 (Ω) we can define ∂ n u| ∂Ω = γ 1 (∇u) ∈ H -1/2 (∂Ω) and the set D(L ρ ) is well defined. From (1.13) we deduce that for any u ∈ H 1 (Ω) with ∆u ∈ L 2 and any v ∈ H 1 (Ω) we have

(L ρ + 1)u, v L 2 (ρ) = α d 2 ∇u, ∇v L 2 (ρ) + ∂ n u, ρv H -1/2 (∂Ω),H 1/2 (∂Ω) + u, v L 2 (ρ) . (1.14)
Then, it is standard that L ρ is the self-adjoint realization of the Dirichlet form

α d 2 Ω |∇u(x)| 2 ρ(x)dx.
(1.15)

A standard argument [RS78, Sects. 13, 14] using Sobolev embedding show that L ρ has a compact resolvant. Denote its spectrum by ν 0 = 0 < ν 1 < ν 2 < . . . and by m j the multiplicity of ν j . In particular, ν(ρ) = ν 1 . Observe also that m 0 = 1 since KerL is spanned by the constant function equal to 1.

of R d such that codim R d S j ≥ j, ∪ k≥j S k = S j , (1.17) then Ω is quasi-regular, since in that case, if v ∈ H -1/2 (∂Ω) is such that near a point x 0 , the support of v is contained in a submanifold S of codimension ≥ 2 in R d , then v = 0 near x 0 . This follows from the fact that the distribution u, φ = v, φ| ∂Ω on R d belongs to H -1 (R d ), and if u ∈ D ′ (R d ) is such that u ∈ H -1 (R d
) and sup(u) ⊂ {x 1 = x 2 = 0}, then u = 0. As an example, a cube in R d is quasi-regular. This 'piece-wise smooth' condition (often called "stratified") is easy to visualize. In our applications (Section 4) it was hard to work with products of stratified sets. The definition we give works easily with products and is exactly what is needed in the proof.

Theorem 1.2. Let Ω be an open, connected, bounded and Lipschitz subset of R d , such that ∂Ω is quasi-regular. Assume that the positive density ρ is continuous on Ω. Then

lim h→0 h -2 g(h, ρ) = ν(ρ). (1.18)
Moreover, if the density ρ is smooth on Ω, then for any R > 0 and ε > 0 such that ν j+1ν j > 2ε for ν j+2 < R, there exists h 1 > 0 such that one has for all h ∈]0,

h 1 ], Spec 1 -T h,ρ h 2 ∩]0, R] ⊂ ∪ j≥1 [ν j -ε, ν j + ε], (1.19)
and the number of eigenvalues of

1-T h,ρ h 2 in the interval [ν j -ε, ν j + ε] is equal to m j .
Theorem 1.1 is proved in Section 2. This is done from the spectrum of the operator by comparison with a 'ball walk' on a big box B containing Ω. One novelty is the use of 'normal extensions' of functions from Ω to B allowing comparison of the two Dirichlet forms. When the Dirichlet forms and stationary distributions for random walk on a compact group are comparible, the rates of convergence are comparable as well [DSC93, Lemma 5]. Here, the Metropolis Markov chain is far from a random walk on a group. Indeed, because of the holding implicit in the Metropolis algorithm, the operator does not have any smoothing properties. The transfer of information is carried out by a Sobolev inequality for a spectrally-truncated part of the operator. This is transfered to a Nash inequality and then an inductive argument is used to obtain decay bounds on iterates of the kernel. A further technique is the use of crude Weyl type estimates to get bounds on the number of eigenvalues close to 1. All of these enter the proof of the total variation estimate (1.7). All of these techniques seem broadly applicable.

Theorem 1.2 is proved in Section 3. It gives rigorous underpinnings to a general picture of the spectrum of the Metropolis algorithm based on small steps. This was observed and proved in special cases [START_REF] Diaconis | Micro-local analysis for the Metropolis algorithm[END_REF], [START_REF] Lebeau | Semiclassical analysis of a random walk on a manifold[END_REF]. The picture is this: because of the holding (or presence of the multiplier m h,ρ in (1.2)) in the Metropolis algorithm, the operator always has continuous spectrum. This is well isolated from 1 and can be neglected in bounding rates of convergence. The spectrum near 1 is discrete and for h small, merges with the spectrum of an associated Neumann problem. This is an analytic version of the weak convergence of the discrete time Metropolis chain to the Langevin diffusion with generator (1.11).

In Section 4, we return to the hard disc problem showing that a suitable power of the operators and domains involved satisfies our hypothesis. Precisely, in Theorem 4.6 we shall prove that the results of Theorem 1.1 and Theorem 1.2 hold true in this case.

A Proof of Theorem 1.1

Let us recall that

K h,ρ (x, y) = h -d ϕ x -y h min ρ(y) ρ(x) , 1 , (2.1)
so that T h,ρ (u) = u -Q h,ρ (u), Q h,ρ (u)(x) = Ω K h,ρ (x, y) (u(x) -u(y)) dy, ((1 -T h,ρ )u|u) L 2 (ρ) = 1 2 Ω×Ω |u(x) -u(y)| 2 K h,ρ (x, y)ρ(x)dxdy.
(2.2)

Observe that since Ω is Lipschitz, from (1.2) we get that for any h 0 > 0, there exists δ 0 > 0 such that for any density ρ with 0 ≤ m ≤ ρ(x) ≤ M one has sup x∈Ω m h,ρ (x) ≤ 1 -2δ 0 for all h ∈]0, h 0 ]. Thus the essential spectrum of T h is a subset of [0, 1 -2δ 0 ] and the spectrum of

T h in [1 -δ 0 , 1] is discrete. From the last line of 2.2, we get that if u ∈ L 2 is such that u = T h,ρ (u), then u(x) = u(y)
for almost all x, y ∈ Ω, |x -y| < h and since Ω is connected, u is constant. Therefore, 1 is a simple eigenvalue of T h,ρ . In particular, for any h > 0, the spectral gap satisfies

g(h, ρ) > 0 (2.3)
For the proof of Theorem 1.1, we will not really care about the precise choice of the density ρ. In fact, if ρ 1 , ρ 2 are two densities such that m ≤ ρ i (x) ≤ M for all x, then

ρ 2 (x) ≤ ρ 1 (x) 1 + ρ 1 -ρ 2 ∞ m , K h,ρ 1 (x, y)ρ 1 (x) ≤ K h,ρ 2 (x, y)ρ 2 (x) 1 + ρ 1 -ρ 2 ∞ m ,
(2.4) and this implies, using the definition (1.4) of the spectral gap and of ν ρ ,

g h,ρ 1 g h,ρ 2 ≤ 1 + ρ 1 -ρ 2 ∞ m 3 , ν ρ 1 ν ρ 2 ≤ 1 + ρ 1 -ρ 2 ∞ m 3 .
(2.5)

In particular, it is sufficient to prove (1.6) for a constant density. The proof that for some δ 0 > 0, independent of ρ, one has Spec(T h,ρ ) ⊂ [-1 + δ 0 , 1] for all h ∈]0, h 0 ] is the following: one has

(u + T h,ρ u|u) L 2 (ρ) = 1 2 Ω×Ω K h,ρ (x, y)|u(x) + u(y)| 2 ρ(x)dxdy + 2(m h,ρ u|u) L 2 (ρ) . (2.6)
Therefore, it is sufficient to prove that there exists h 0 , C 0 > 0 such that the following inequality holds true for all h ∈]0, h 0 ] and all u ∈ L 2 (Ω):

Ω×Ω h -d ϕ x -y h |u(x) + u(y)| 2 dxdy ≥ C 0 u 2 L 2 (Ω) .
(2.7)

Let ω j ⊂ Ω, ∪ j ω j = Ω be a covering of Ω such that diam(ω j ) < h and for some C i > 0 independent of h, vol(ω j ) ≥ C 1 h d , and for any j, the number of k such that ω j ∩ ω k = ∅ is less than C 2 . Such a covering exists as Ω is Lipschitz. Then

C 2 Ω×Ω h -d ϕ x -y h |u(x) + u(y)| 2 dxdy ≥ j ω j ×ω j h -d ϕ x -y h |u(x) + u(y)| 2 dxdy ≥ j h -d 1 |B 1 | ω j ×ω j |u(x) + u(y)| 2 dxdy ≥ j 2h -d 1 |B 1 | vol(ω j ) u 2 L 2 (ω j ) ≥ 2C 1 |B 1 | u 2 L 2 (Ω) .
(2.8)

From (2.8), we get that (2.7) holds true.

For the proof of (1.6) we need a suitable covering of Ω. Given ǫ > 0 small enough, there exists some open sets Ω 0 , . . . , Ω N such that {x ∈ R d , dist(x, Ω) ≤ ǫ 2 } ⊂ ∪ N j=0 Ω j , where the Ω j 's have the following properties:

1. Ω 0 = {x ∈ Ω, d(x, ∂Ω) > ǫ 2 }.
2. For j = 1, . . . , N , there exists r j > 0, an affine isometry R j of R d and a Lipschitz map

ϕ j : R d-1 → R such that, denoting φj (x ′ , x d ) = (x ′ , x d + ϕ j (x ′ )) and φ j = R j • φj , we have φ j is injective on B(0, 2r j )×] -2ǫ, 2ǫ[ Ω j = φ j (B(0, r j )×] -ǫ, ǫ[) Ω j ∩ Ω = φ j (B(0, r j )×]0, ǫ[) φ j (B(0, 2r j )×]0, 2ǫ[) ⊂ Ω (2.9)
We put our open set Ω in a large box B =]-A/2, A/2[ d and define an extension map E : L 2 (Ω) → L 2 (B). For j = 0, . . . , N we let χ j ∈ C ∞ 0 (Ω j ) be such that j χ j (x) = 1 for dist(x, Ω) ≤ ǫ 2 . For any function u ∈ L 2 (Ω), let u j , j = 0, . . . , N be defined in a neighborhood of Ω j by u

j = u • φ j • S • φ -1 j , where S(x ′ , x d ) = (x ′ , -x d ) if x d < 0 and S(x ′ , x d ) = (x ′ , x d ) if x d ≥ 0. For x ∈ Ω ∩ Ω j , one has u j (x) = u(x) and we define E(u)(x) = N j=0 χ j (x)u j (x).
(2.10)

We observe that φ-1 j (x) = (x ′ , x dϕ j (x ′ )). Consequently, as ϕ j is Lipschitz-continuous, then φ j and φ -1 j are also Lipschitz-continuous. Hence, formula (2.10), gives us an extension map from

L 2 (Ω) into L 2 (B), which is also bounded from H 1 (Ω) into H 1 (B). For u ∈ L 2 (Ω), v ∈ L 2 (B), set E h,ρ (u) = ((1 -T h,ρ )u|u) L 2 (ρ) , E h (v) = B×B,|x-y|≤h h -d |v(x) -v(y)| 2 dxdy.
(2.11)

Since for A large, E(u) vanishes near the boundary of B, we can extend v = E(u) as an Aperiodic function on R d , and write its Fourier series v

(x) = E(u)(x) = k∈Z d c k (v)e 2iπkx/A with c k (v) = A -d B e -2iπkx/A v(x)dx. Then E(u) 2 L 2 (B) = A d k |c k | 2 ≃ u 2 L 2 (Ω) , E(u) 2 H 1 (B) = A d k (1 + 4π 2 k 2 /A 2 )|c k | 2 ≃ u 2 H 1 (Ω) .
(2.12) Moreover, one gets

E h (v) = A d k |c k | 2 θ(hk), θ(ξ) = |z|≤1 |e 2iπξz/A -1| 2 dz.
(2.13)

Observe that the function θ is nonnegative, quadratic near 0 and has a positive lower bound for |ξ| ≥ 1. The next two lemmas show that the Dirichlet forms for u ∈ L 2 (Ω) and its extension to L 2 (B) are comparable.

Lemma 2.1. For all α > 1, there exists C > 0 and h 0 > 0 such that

E αh,ρ (u) ≤ CE h,ρ (u) ∀u ∈ L 2 (Ω), ∀h ∈]0, h 0 ]. (2.14)
Proof. Using (2.2) and (2.4), we observe that it suffices to prove the lemma in the case where ρ(x) = ρ is constant, and we first we show the result when Ω is convex. In that case, since

|u(x) -u(y)| ≤ |u(x) -u( x+y 2 )| + |u( x+y 2 ) -u(y)|, one has E αh,ρ (u) = (hα) -d 2vol(B 1 ) Ω Ω 1 |x-y|≤αh |u(x) -u(y)| 2 ρdxdy ≤ 2(hα) -d vol(B 1 ) Ω Ω 1 |x-y|≤αh |u(x) -u( x + y 2 )| 2 ρdxdy = 2(hα/2) -d vol(B 1 ) φ(Ω×Ω) 1 |x-y|≤ αh 2 |u(x) -u(y)| 2 ρdxdy, (2.15)
where φ(x, y) = (x, x+y 2 ). As Ω is convex φ(Ω × Ω) ⊂ Ω × Ω and we get E αh,ρ (u) ≤ 4E αh 2 ,ρ (u). Iterating this process we obtain the anounced result for convex domains.

In the general case, we use the local covering introduced in (2.9). Let Ω + i = Ω i ∩ Ω (respectively

Ω - i = Ω i ∩ (R d \ Ω)) and U i (h) = {(x, y) ∈ Ω + i × Ω, |x -y| ≤ αh}. Since by (2.2), Ω ⊂ ∪ i Ω + i , we have E αh,ρ (u) ≤ N i=0 E i αh,ρ (u) with E i αh,ρ (u) = (αh) -d 2vol(B 1 ) U i (h) 1 |x-y|≤αh |u(x) -u(y)| 2 ρdxdy.
(2.16)

Let us estimate E 0 αh,ρ (u). For h ∈]0, ǫ 2 /α[ and (x, y) ∈ U 0 (h), we have [x, y] ⊂ Ω. Therefore, the change of variable φ(x, y) = (x, x+y

2 ) maps U 0 (h) into Ω 0 × Ω and we get as above

E 0 αh,ρ (u) ≤ 2(αh) -d vol(B 1 ) U 0 (h) 1 |x-y|≤αh |u(x) -u( x + y 2 )| 2 ρdxdy ≤ 4E αh 2 ,ρ (u).
(2.17)

For i = 0 and h > 0 small enough, we remark that

U i (h) ⊂ Ω+ i × Ω+ i , where Ω± i = φ i (B(0, 2r i )×{0 < ±x d < 2ǫ}). Denoting Q i = B(0, r i )×]0, ǫ[, Qi = B(0, 2r i )×]0, 2ǫ[, we can use the Lipschitz- continuous change of variable φ i : Qi → Ω+ i ⊂ Ω to get E i αh,ρ (u) ≤ (αh) -d 2vol(B 1 ) Qi Qi J φ i (x)J φ i (y)1 |φ i (x)-φ i (y)|≤αh |u • φ i (x) -u • φ i (y)| 2 ρdxdy (2.18)
where the Jacobian J φ i of φ i is a bounded function defined almost everywhere. As both φ i , φ -1 i are Lipschitz-continuous, there exists M i , m i > 0 such that for all x, y ∈ Qi we have

m i |x -y| ≤ |φ i (x) -φ i (y)| ≤ M i |x -y|. Therefore, E i αh,ρ (u) ≤ Ch -d Qi Qi 1 |x-y|≤ αh m i |u • φ i (x) -u • φ i (y)| 2 ρdxdy, (2.19)
where C denotes a positive constant changing from line to line. As Qi is convex, it follows from the study of the convex case that

E i αh,ρ (u) ≤ Ch -d Qi Qi 1 |x-y|≤ h M i |u • φ i (x) -u • φ i (y)| 2 ρdxdy ≤ Ch -d
Qi Qi

1 |φ i (x)-φ i (y)|≤h |u • φ i (x) -u • φ i (y)| 2 ρdxdy ≤ Ch -d Ω+ i Ω+ i 1 |x-y|≤h |u(x) -u(y)| 2 ρdxdy ≤ C i E h,ρ (u),
(2.20) and the proof is complete.

Lemma 2.2. There exist C 0 , h 0 > 0 such that the following holds true for any h ∈]0, h 0 ] and any

u ∈ L 2 (ρ). E h,ρ (u)/C 0 ≤ E h (E(u)) ≤ C 0 E h,ρ (u) + h 2 u 2 L 2 . (2.21)
As a byproduct, there exists C 1 such that for all h ∈]0, h 0 ], any function u ∈ L 2 (ρ) such that

u 2 L 2 (ρ) + h -2 ((1 -T h,ρ )u|u) L 2 (ρ) ≤ 1 admits a decomposition u = u L + u H with u L ∈ H 1 (Ω), u L H 1 ≤ C 1 , and u H L 2 ≤ C 1 h.
Proof. Using the second line of (2.4), we may assume that the density ρ is constant. The proof of the left inequality in (2.21) is obvious. For the upper bound, we remark that there exists

C > 0 such that E h (E(u)) ≤ C N j=0 (E j,1 h + E j,2 h ) with E j,1 h = h -d B×B 1 |x-y|≤h |χ j (x) -χ j (y)| 2 |u j (x)| 2 dxdy (2.22) and E j,2 h = h -d B×B 1 |x-y|≤h |χ j (y)| 2 |u j (x) -u j (y)| 2 dxdy.
(2.23)

As the functions χ j are regular, there exist some χj ∈ C ∞ 0 (B) equal to 1 near the support of χ j such that

E j,1 h ≤ Ch -d B χj (x)|u j (x)| 2 B 1 |x-y|≤h |x -y| 2 dy dx ≤ Ch 2 u 2 L 2 (Ω) .
(2.24)

In order to estimate E j,2 h one has to estimate the contribution of the points x ∈ Ω, y / ∈ Ω and x /

∈ Ω, y / ∈ Ω. All the terms are treated in the same way and we only examine

E j,3 h = h -d Ω×(B\Ω) 1 |x-y|≤h |χ j (y)| 2 |u j (x) -u j (y)| 2 dxdy = h -d Ω+ j ×Ω - j 1 |x-y|≤h |χ j (y)| 2 |u(x) -u • φ j • S • φ -1 j (y)| 2 dxdy, (2.25)
with S defined below (2.9). Let σ : R d → R d be the symmetry with respect to {y d = 0}, so that Sσ = Id on {y d < 0}. We use the Lipschitz-continuous change of variable

ψ j : y ∈ Ω + j → φ j • σ • φ -1 j (y) ∈ Ω - j to get E j,3 h ≤ Ch -d Ω+ j ×Ω + j 1 |x-ψ j (y)|≤h |χ j • ψ j (y)| 2 |u(x) -u(y)| 2 dxdy.
(2.26)

We claim that there exists β > 0 such that

|ψ j (y) -x| ≥ β -1 |x -y| ∀(x, y) ∈ Ω+ j × Ω + j .
(2.27) Indeed, as both φ j and φ -1 j are Lipschitz-continuous, (2.27) is equivalent to finding β > 0 such that

|σ(y) -x| ≥ β -1 |x -y| ∀(x, y) ∈ φ -1 j ( Ω+ j × Ω + j ), (2.28)
which is obvious with β = 1. From (2.27) it follows that for some α > 1, one has

E j,3 h ≤ Ch -d Ω+ j ×Ω + j 1 |x-y|≤αh |u(z) -u(y)| 2 dzdy ≤ CE αh,ρ (u), (2.29)
and the upper bound is then a straightforward consequence of Lemma 2.1.

The by-product is obtained by projecting the extension v = E(u) on low frequencies h|k| ≤ 1 and high frequencies h|k| > 1 and the fact that the function θ is quadratic near 0 and has a positive lower bound for |ξ| ≥ 1. The proof of Lemma 2.2 is complete.

We are in position to prove the estimate (1.6) on the spectral gap. To show the right inequality, it suffices to plug a function u ∈ C ∞ 0 (Ω) into (1.3) with support contained in a small ball Q ⊂ Ω and such that Ω u(x)ρ(x)dx = 0. As Q is convex, it follows from Taylor's formula that for such u, we have u -T h u, u = O(h 2 ).

To show the left inequality in (1.6), we first observe that it is clearly satisfied when Ω is convex. Indeed, given u ∈ L 2 (Ω) we have by Cauchy-Schwarz

Ω×Ω |u(x) -u(y)| 2 dxdy ≤ Ch -1 K(h)-1 k=0 Ω×Ω |u (x + k (y -x)) -u (x + (k + 1) (y -x)) | 2 dxdy, (2.30) where K(h) is the greatest integer ≤ h -1 and K(h) = 1. With the new variables x ′ = x+k (y-x), y ′ = x + (k + 1) (y -x), one has dx ′ dy ′ = d dxdy and we get Ω×Ω |u(x) -u(y)| 2 dxdy ≤ Ch -d-1 K(h) Ω×Ω 1 |x ′ -y ′ |< diam(Ω) |u(x ′ ) -u(y ′ )| 2 dx ′ dy ′ ,
(2.31) By lemma 2.1, this proves the left inequality in (1.6) in the case where Ω is convex.

In the general case, we can find some open sets contained in Ω, ω j ⊂⊂ Ω + j ⊂⊂ Ω+ j , j = 1, . . . , N +M such that for j = 1, . . . , N , Ω + j , Ω+ j are given in the previous lemma, (

Ω + j ) j=N +1,...,N +M are convex Ω 0 ⊂ ∪ M +N j=N +1 Ω + j , Ω ⊂ ∪ N +M j=1 ω j , and where A ⊂⊂ B means that A Ω ⊂ B. Hence for h > 0 small enough, E h,ρ (u) ≥ C N +M j=1 h -d Ω + j × Ω+ j 1 |x-y|<h (u(x) -u(y)) 2 dxdy ≥ C N j=1 h -d Q j × Qj 1 |φ j (x)-φ j (y)|<h (u • φ j (x) -u • φ j (y)) 2 dxdy + C N +M j=N +1 h -d Ω + j × Ω+ j 1 |x-y|<h (u(x) -u(y)) 2 dxdy.
(2.32)

From the estimate proved precedently in the convex case, we know that there exists a > 0 independant of h such that the second sum in (2.32) is bounded from below by

Ch 2 N +M j=N +1 ω j ×Ω + j (u(x) -u(y)) 2 dxdy ≥ Ch 2 N +M j=N +1 ω j ×Ω,|x-y|<a (u(x) -u(y)) 2 dxdy. (2.33)
On the other hand, thanks to the fact that φ j is a Lipschitz diffeomorphism, there exists α > 0 such that 1 |x-y|<h/α ≤ 1 |φ j (x)-φ j (y)|<h ≤ 1 |x-y|<αh . Using the convexity of Q i and Lemma 2.1 it follows that the first sum in the right hand side of (2.32) is bounded from below by

Ch 2 N j=1 ω j ×Ω,|x-y|<a (u(x) -u(y)) 2 dxdy.
(2.34)

Combining (2.32), (2.33) and (2.34), we get

E h,ρ (u) ≥ Ch 2 Ω×Ω,|x-y|<a (u(x) -u(y)) 2 dxdy (2.35)
for some fixed a > 0 independant of h. Since by (2.3) we have g(a, ρ) > 0, we get

E h,ρ (u) ≥ Ch 2 Ω×Ω (u(x) -u(y)) 2 dxdy (2.36)
The proof of (1.6) is complete.

Lemma 2.3. There exists

δ 0 ∈]0, 1/2[ such that Spec(T h,ρ ) ∩ [1 -δ 0 , 1] is discrete, and for any 0 ≤ λ ≤ δ 0 /h 2 , the number of eigenvalues of T h in [1 -h 2 λ, 1] (with multiplicity) is bounded by C 1 (1 + λ) d/2 . Moreover, any eigenfuntion T h (u) = λu with λ ∈ [1 -δ 0 , 1] satisfies the bound u L ∞ ≤ C 2 h -d/2 u L 2 .
(2.37)

Proof. To get (2.37), we just write that since λ is not in the range of m h , one has

u(x) = 1 λ -m h (x) Ω h -d ϕ x -y h min ρ(y) ρ(x) , 1 u(y)dy,
and we apply Cauchy-Schwarz. The important point here is the estimate on the number of eigenvalues in [1h 2 λ, 1] by a power of λ. This is obtained by the min-max and uses (2.21). The min-max gives: if for some closed subspace

F of L 2 (ρ) with codim(F ) = N one has for all u ∈ F , h -2 ((1 -T h )u|u) L 2 (ρ) ≥ λ u 2 L 2 (ρ)
, then the number of eigenvalues of T h in [1h 2 λ, 1] (with multiplicity) is bounded by codim(F ) = N . Then, we fix c > 0 small enough, and we choose for F the subspace of functions u such that their extension v = E(u) is such that the Fourier coefficients satisfy c k (E(u)) = 0 for |k| ≤ D with hD ≤ c. The codimension of this space F is exactly the number of k ∈ Z d such that |k| ≤ D, since if p is a trigonometric polynomial such that E * (p) = 0, we will have Ω p(x)u(x)dx = 0 for any function u with compact support in Ω and such that E(u) = u, and this implies p = 0. Thus codim(F ) ≃ (1 + D) d . On the other hand, the right inequality in (2.21) gives for

u ∈ F , h -2 ((1 -T h )u|u) L 2 (ρ) ≥ C 0 (D 2 -C 1 ) u 2
L 2 (ρ) for universal C 0 , C 1 , since by (2.13), there exists C > 0 such that one has θ(hk)h -2 ≥ CD 2 for all D ≤ c/h and all |k| > D. The proof of our lemma is complete.

We are now ready to prove the total variation estimate (1.7). We use the notation T h = T h,ρ and T n h,x 0 = T n h,ρ (x 0 , dy). Let Π 0 be the orthogonal projector in L 2 (f ) on the space of constant functions Π 0 (u)(x) = 1 Ω (x) Ω u(y)ρ(y)dy.

(2.38) Then 2 sup

x 0 ∈Ω T n h,x 0 -ρ(y)dy T V = T n h -Π 0 L ∞ →L ∞ .
(2.39) 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,ρ .
(2.40)

Observe that since we know that for h 0 small, the estimate (1.6) holds true for any ρ, we may assume n ≥ Ch -2 . In order to prove (2.40), we split T h into three pieces, using spectral theory.

Let 0 < λ 1,h ≤ • • • ≤ λ j,h ≤ λ j+1,h ≤ • • • ≤ h -2 δ 0 be such that the eigenvalues of T h in the interval [1 -δ 0 , 1[ are the 1 -h 2 λ j,h , with associated orthonormal eigenfunctions e j,h , T h (e j,h ) = (1 -h 2 λ j,h )e j,h , (e j,h |e k,h ) L 2 (ρ) = δ j,k . (2.41) Then we write T h -Π 0 = T h,1 + T h,2 + T h,3 with T h,1 (x, y) = λ 1,h ≤λ j,h ≤h -α
(1h 2 λ j,h )e j,h (x)e j,h (y),

T h,2 (x, y) = h -α <λ j,h ≤h -2 δ 0
(1h 2 λ j,h )e j,h (x)e j,h (y),

T h,3 = T h -Π 0 -T h,1 -T h,2 .
(2.42)

Here α > 0 is a small constant that will be chosen later. One has

T n h -Π 0 = T n h,1 + T n h,2 + T n h,3
, and we will get the bound (2.40) for each of the three terms. We start by very rough bounds. Since there are at most Ch -d eigenvalues λ j,h and using the bound (2.37), we get that there exists C independent of n ≥ 1 and h such that

T n 1,h L ∞ →L ∞ + T n 2,h L ∞ →L ∞ . ≤ Ch -3d/2 (2.43) 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,3 T n 3,h L ∞ →L ∞ . ≤ Ch -3d/2 (2.44) Next we use (1.2) to write T h = m h + R h with m h L ∞ →L ∞ ≤ γ < 1, R h L 2 →L ∞ ≤ C 0 h -d/2 . (2.45)
From this, we deduce that for any p = 1, 2, . . . , one has

T p h = A p,h +B p,h , with A 1,h = m h , B 1,h = R h and the recurrence relation A p+1,h = m h A p,h , B p+1,h = m h B p,h + R h T p h . Thus one gets, since T p h is bounded by 1 on L 2 , A p,h L ∞ →L ∞ ≤ γ p , B p,h L 2 →L ∞ ≤ C 0 h -d/2 (1 + γ + • • • + γ p ) ≤ C 0 h -d/2 (1 -γ).
(2.46)

Let θ = 1 -δ 0 < 1 so that T 3,h L 2 →L 2 ≤ θ.
Then one has

T n 3,h L ∞ →L 2 ≤ T n 3,h L 2 →L 2 ≤ θ n ,
and for n ≥ 1, p ≥ 1, one gets, using (2.46) and (2.44),

T p+n 3,h L ∞ →L ∞ = T p h T n 3,h L ∞ →L ∞ ≤ A p,h T n 3,h L ∞ →L ∞ + B p,h T n 3,h L ∞ →L ∞ ≤ Ch -3d/2 γ p + C 0 h -d/2 θ n (1 -γ).
(2.47)

Thus we get, for some C > 0, µ > 0,

T n 3,h L ∞ →L ∞ ≤ Ce -µn , ∀h, ∀n ≥ 1/h, (2.48)
and thus the contribution of T n 3,h is far smaller than the bound we have to prove in (2.40). Next, for the contribution of T n 2,h , we just write, since there are at most Ch -d eigenvalues λ j,h and using the bound (2.37),

T n h,2 (x, y) = h -α <λ j,h ≤h -2 δ 0 (1 -h 2 λ j,h
) n e j,h (x)e j,h (y),

T n 2,h L ∞ →L ∞ ≤ Ch -3d/2 (1 -h 2-α ) n .
(2.49)

Thus we get for some C α > 0,

T n 2,h L ∞ →L ∞ ≤ C α e -nh 2-α 2 , ∀h, ∀n ≥ h -2+α/2 , (2.50)
and thus this contribution is still neglectible for h ∈]0, h 0 ] for h 0 small. It remains to study the contribution of T n h,1 . Let E α be the (finite dimensional) subspace of L 2 (ρ) spanned by the eigenvectors e j,h , λ j,h ≤ h -α . By Lemma 2.3, one has dim(E α ) ≤ Ch -dα/2 . We next prove a Sobolev-type inequality for the form E h,ρ . For background on Sobolev and the following Nash inequality, see [START_REF] Diaconis | Nash inequalities for finite Markov chains[END_REF], [START_REF] Saloff-Coste | Lectures on finite Markov chains[END_REF].

Lemma 2.4. There exist α > 0, p > 2 and C independent of h such that for all u ∈ E α , the following inequality holds true:

u 2 L p ≤ Ch -2 E h,ρ (u) + h 2 u 2 L 2 .
(2.51)

Proof. Clearly, one has for u = λ 1,h ≤λ j,h ≤h -α a j e j,h ∈ E α ,

E h,ρ (u) + h 2 u 2 L 2 = λ 1,h ≤λ j,h ≤h -α h 2 (1 + λ j,h )|a j | 2 . Take u ∈ E α such that h -2 (E h,ρ (u) + h 2 u 2 L 2 ) ≤ 1. Then by (2.21), one has h -2 E h (E(u)) ≤ C 0 . Let ψ(t) ∈ C ∞ 0 (R) be equal to 1 near t = 0, and for v(x) = k∈Z d c k (v)e 2iπkx/A , set v = v L + v H , v L (x) = k∈Z d ψ(h|k|)c k (v)e 2iπkx/A . (2.52) Then v = v L + v H is a decomposition of the extension v = E(u) in low frequencies (v L ) and high frequencies (v H ). One has v L (x) = R d h -d θ( x-y h )v(y)
dy, where θ is the function in the Schwartz space defined by θ(2πz/A) = ψ(|z|). Hence, the map v → v L is bounded uniformly in h on all the spaces L q for 1 ≤ q ≤ ∞. Then, from (2.13) we get

v L H 1 (B) ≤ C.
(2.53)

Thus, with u L = v L | Ω and u H = v H | Ω , we get u L H 1 (Ω) ≤ C so by Sobolev for p < 2d d-2 , u L L p ≤ C. (2.54)
One the other hand, one has also by (2.21),

h -2 E h (E(e j,h )) ≤ C 0 (1 + λ j,h ), (2.55)
and this implies, by (2.13),

h -2 E(e j,h ) H 2 L 2 ≤ C 0 (1 + λ j,h ) ≤ C 0 (1 + h -α ).
(2.56)

Thus for α ≤ 1, we get E(e j,h ) H L 2 ≤ Ch 1/2 . On the other hand, since e j,h L ∞ ≤ Ch -d/2 , using the definition of the low frequency cut-off we get

E(e j,h ) H L ∞ ≤ E(e j,h ) L ∞ + E(e j,h ) L L ∞ ≤ C E(e j,h ) L ∞ ≤ Ch -d/2 .
By interpolation we can find some p > 2 such that

E(e j,h ) H L p ≤ C 0 h 1/4 . (2.57) Thus one gets, for u = λ 1,h ≤λ j,h ≤h -α a j e j,h ∈ E α with h -2 (E h,ρ (u) + h 2 u 2 L 2 ) ≤ 1, u H L p ≤ λ 1,h ≤λ j,h ≤h -α |a j | E(e j,h ) H L p ≤ C 0 h 1/4 dim(E α ) 1/2 u L 2 ≤ Ch 1/4 h -dα/4 .
(2.58)

Our lemma follows from (2.54) and (2.58) if one takes α small. Observe that here, the estimate on the number of eigenvalues (i.e., the estimation of the dimension of E α ) is crucial. The proof of Lemma 2.4 is complete.

From Lemma 2.4, 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 ≤ Ch -2 E h,ρ (u) + h 2 u 2 L 2 u 1/D L 1 , ∀u ∈ E α .
(2.59)

For λ j,h ≤ h -α , one has h 2 λ j,h ≤ 1, and thus for any

u ∈ E α , one gets E h,ρ (u) ≤ u 2 L 2 -T h u 2 L 2
and thus we get, from (2.59),

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 α .
(2.60)

From (2.48) and (2.50), and

T n h -Π 0 = T n h,1 + T n h,2 + T n h,3
, we get that there exists C 2 such that

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

c n = T n+p 1,h g 2 L 2 .
(2.63)

Then 0 ≤ c n+1 ≤ c n , and from (2.60) and (2.62), we get

c 1+ 1 2D n ≤ Ch -2 c n -c n+1 + h 2 c n T n+p 1,h g 1/D L 1 ≤ CC 1/D 2 h -2 c n -c n+1 + h 2 c n .
(2.64)

From this inequality, we deduce that there exist

A ≃ CC 2 sup 0≤n≤h -2 (2 + n)(1 + h 2 -(1 -1 n+2 ) 2D
) 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 , and thus there exist C 0 which depends only on C, C 2 , D, such that for N ≃ h -2 , one has c N ≤ C 0 . This implies

T N +p 1,h g L 2 ≤ C 0 g L 1 , (2.65)
and thus taking adjoints,

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

N + p ≃ h -2 , T N +p+n 1,h g L ∞ ≤ C 0 (1 -h 2 λ 1,h ) n g L 2 .
(2.67)

And thus for n ≥ h -2 ,

T n 1,h L ∞ →L ∞ ≤ C 0 e -(n-h -2 )h 2 λ 1,h = C 0 e λ 1,h e -ngap , ∀h, ∀n ≥ h -2 . (2.68)
This concludes the proof of Theorem 1.1.

Remark 1. We believe that (2.37) is true with a power of Λ instead of a power of h with λ = 1-h 2 Λ. We have no proof for this which is why we use a Nash inequality for T 1,h .

Remark 2. The above proof seems to apply for a more general choice of the elementary Markov kernel h -d ϕ( x-y h ). Replace ϕ by a positive symmetric measure of total mass 1 with support in the unit ball, and let T h be the Metropolis algorithm with this data. Assume that one is able to prove that for some δ 0 > 0 one has Spec(T h ) ⊂ [-1 + δ 0 , 1] for all h ≤ h 0 , and that for some power M , one has for some C, c > 0,

T M h (x, dy) = µ h (x, dy) + Ch -d 1 |x-y|≤ch ρ(y)dy, µ h (x, dy) ≥ 0.
Then there exists γ < 1 such that µ h L ∞ ≤ γ. Moreover, the right inequality in (2.21) and (2.37) are still valid for T M h . Also, the spectral gap of T M h is given by formula (1.4) with T M h (x, dy) in place of K h,ρ (x, y)dy, and therefore the left inequality in (1.6) holds true, and the right one is true, since if ρ is constant, for any θ ∈ C ∞ 0 (Ω), one has u -T h u ∈ O(h 2 ). We shall use these remarks in the study of the hard disc problem, in Section 4.

A Proof of Theorem 1.2

In this section, we suppose additionally that Ω is quasi-regular (Definition 2). For a given continuous density ρ, using (2.5) and an approximation of ρ in L ∞ by a sequence of smooth densities ρ k on Ω, one sees that the first assertion (1.18) of Theorem 1.2 is a consequence of the second one (1.19). Assume now that ρ is smooth.

Lemma 3.1. Let θ ∈ C ∞ (Ω) be such that sup(θ) ∩ Γ sing = ∅ and ∂ n θ| Γreg = 0. Then, with Q h,ρ defined in (2.2), L ρ defined in (1.11), Q h,ρ (θ) = h 2 L ρ (θ) + r, r L 2 ∈ O(h 5/2 ). (3.1)
Proof. For θ ∈ C ∞ (Ω) and x ∈ Ω, we can use the Taylor formula to get

Q h,ρ (θ)(x) = 1 vol(B 1 ) A(x,h) min 1 + h ∇ρ(x) ρ(x) .z + O(h 2 |z| 2 ), 1   -h∇θ(x).z - h 2 2 i,j z i z j ∂ x i ∂ x j θ(x) + O(h 3 |z| 3 )   dz, (3.2) with A(x, h) = {z ∈ R d , |z| < 1, x + hz ∈ Ω}. As A(x, h) = A + (x, h) ∪ A -(x, h), with A ± (x, h) = {z ∈ A(x, h), ±(ρ(x + hz) -ρ(x)) ≥ 0},

it follows by an easy computation that

Q h,ρ (θ)(x) = - h vol(B 1 ) ∇θ(x). A(x,h) zdz - h 2 2vol(B 1 ) d i,j=1 ∂ x i ∂ x j θ(x) A(x,h) z i z j dz - h 2 vol(B 1 ) A -(x,h) ∇ρ(x) ρ(x)
.z∇θ(x).zdz + r(x)

=f 1 (x) + f 2 (x) + f 3 (x) + r(x), (3.3) with r L ∞ (Ω) = O(h 3 ). Let χ = 1 d(x,∂Ω)<2h
, then for j = 2, 3,

χf j L 2 (Ω) ≤ χ L 2 (Ω) f j L ∞ (Ω) = O(h 5/2 ), (3.4)
thanks to the support properties of χ. Moreover, for x ∈ sup(1χ), A(x, h) = {|z| < 1} and the change of variable z → -z shows that (1

-χ)f 2 = -(1 -χ) α d f 2 (x) = - α d 2 h 2 ∆θ(x) + r(x), (3.5) with r L 2 = O(h 5/2 ). To compute f 3 (x) for x ∈ sup(1 -χ), we first observe that |f 3 (x)| ≤ Ch 2 |∇ρ(x)||∇θ(x)|. We thus get 1 |∇ρ|≤h 1/2 f 3 L ∞ ≤ Ch 5/2 ∇θ L ∞ . At a point x where |∇ρ(x)| ≥ h 1/2 , we may write z = t ∇ρ(x) |∇ρ(x)| + z ⊥ , t = z.∇ρ(x)
|∇ρ(x)| and z ⊥ .∇ρ(x) = 0. In these coordinates, one has

A -(x, h) = {|z| < 1, (t, z ⊥ ), t|∇ρ(x)| + O(h(t 2 + |z ⊥ | 2 )) ≤ 0}. From |∇ρ(x)| ≥ h 1/2 we get that the symmetric difference R between A -(x, h) and {t ≤ 0} satisfies meas(R) = O(h 1/2 ) (the symmetric difference of two sets A, B is A ∪ B \ A ∩ B). Therefore 1 |∇ρ|≥h 1/2 (1-χ)f 3 (x) = -h 2 1 |∇ρ|≥h 1/2 (1 -χ)(x) vol(B 1 ) {|z|<1,∇ρ(x).z≤0} ∇ρ(x) ρ(x)
.z∇θ(x).zdz +r(x), (3.6) with r L ∞ = O(h 5/2 ). Using the change of variable z → z -2z ⊥ , we get

1 |∇ρ|≥h 1/2 (1 -χ)f 3 (x) = -h 2 1 |∇ρ|≥h 1/2 α d 2 (1 -χ)(x) ∇ρ(x) ρ(x) .∇θ(x) + r(x), (3.7)
and therefore, using (3.4), we get

f 3 (x) = -h 2 α d 2 ∇ρ(x) ρ(x) .∇θ(x) + r(x), (3.8)
with

r L 2 = O(h 5/2 ). It remains to show that f 1 L 2 (Ω) = O(h 5/2
). Using the change of variable z → -z we easily obtain (1-χ)f 1 = 0. Hence, it suffices to show that

f ′ 1 (x, h) = χ A(x,h) z.∇θ(x)dz satisfies f ′ 1 L ∞ (Ω) = O(h).
As Γ sing is compact and sup(θ) ∩ Γ sing = ∅, this is a local problem near any point x 0 of the regular part Γ reg of the boundary. Let ψ be a smooth function such that near x 0 = (0, 0) one has Ω = {x d > ψ(x ′ )}. For x close to x 0 one has

A(x, h) = z ∈ R d , |z| < 1, x d + hz d > ψ(x ′ + hz ′ ) .
(3.9)

Set A 1 (x, h) = z ∈ R d , |z| < 1, x d + hz d > ψ(x ′ ) + h∇ψ(x ′ )z ′ , (3.10)
then the symmetric difference R between A(x, h) and A 1 (x, h) satisfies meas(R) = O(h) uniformly in x close to x 0 . This yields

f ′ 1 (x, h) = ∇θ(x).v(x, h) + r(x), v(x, h) = A 1 (x,h) zdz, (3.11)
with r L ∞ = O(h). Let ν(x) be the vector field defined by ν(x) = (-∇ψ(x ′ ), 1). Observe that v(x, h) = φ( ψ(x ′ )-x d h|ν(x)| ) ν(x) |ν(x)| with φ(a) = |z|<1,z 1 >a z 1 dz, vanishes for dist(x, ∂Ω) > Ch and that for x ∈ ∂Ω, ν(x) is collinear to the unit normal to the boundary -→ n (x). Since ∂ n θ| Γreg = 0, we thus get

f ′ 1 L ∞ = O(h).
The proof of our lemma is complete.

Let us recall that we denote 1 = ν 0 < ν 1 < • • • < ν j < . . . the eigenvalues of L ρ and m j the associated multiplicities. We introduce the bilinear form

a ρ (u, v) = α d 2 ∇u, ∇v L 2 (ρ) + u, v L 2 (ρ) .
(3.12)

This defines an Hilbertian structure on H 1 (Ω) which is equivalent to the usual one. We write . H 1 ρ for the norm induced by a ρ . We denote

D 0 = θ ∈ C ∞ (Ω), θ = 0 near Γ sing , ∂ n θ |Γreg = 0 . (3.13) Lemma 3.2. D 0 is dense in H 1 (Ω).
Proof. Let f ∈ H 1 (Ω) be orthogonal to D 0 for a ρ . Then, it is orthogonal to C ∞ 0 (Ω) so that (L ρ + 1)f = 0 in the sense of distributions. In particular -∆f ∈ L 2 (Ω). Hence we can use the Green formula (1.14) to get for any θ ∈ D 0 , since a ρ (f, θ) = 0,

∂ n f, ρθ H -1/2 ,H 1/2 = 0.
(3.14)

For any ψ ∈ C ∞ 0 (Γ reg ), using smooth local coordinates we can find ψ in D 0 such that ψ|∂Ω = ψ. Consequently,

∂ n f, ρψ H -1/2 ,H 1/2 = ∂ n f, ρ ψ H -1/2 ,H 1/2 = 0. (3.15) Hence, ∂ n f |Γreg = 0. This shows that ∂ n f |∂Ω ∈ H -1/2 is supported in Γ sing . From (1.16) this implies ∂ n f |∂Ω = 0. This shows that f ∈ D(L ρ ).
As the operator L ρ + 1 is strictly positive, this implies f = 0. The proof of our lemma is complete.

We are now in position to achieve the proof of Theorem 1.2. We first observe that if

ν h ∈ [0, M ] and ψ h ∈ L 2 (ρ) satisfy ψ h L 2 = 1, h -2 Q h,ρ ψ h = ν h ψ h ,
then thanks to Lemma 2.2 the family (ψ h ) h∈]0,1] is relatively compact in L 2 (ρ) so that we can suppose (extracting a subsequence h k ) that ν h → ν and ψ h → ψ in L 2 (ρ), ψ L 2 = 1, and moreover by Lemma 2.2, the limit ψ belongs to H 1 (ρ). Given θ ∈ D 0 , it follows from self-ajointness of Q h,ρ and Lemma 3.

1 that 0 = (h -2 Q h,ρ -ν h )ψ h , θ L 2 (ρ) = ψ h , (L ρ -ν h )θ L 2 (ρ) + O(h 1/2 ).
(3.16)

Making h → 0 we obtain ψ, (L ρν)θ L 2 (ρ) = 0 for all θ ∈ D 0 . It follows that (L ρν)ψ = 0 in the distribution sense, and integrating by parts that ∂ n ψ vanishes on Γ reg . Since ψ ∈ H 1 (ρ), we get as above using (1.16) that ∂ n ψ = 0, and it follows that ψ ∈ D(L ρ ). This shows that ν is an eigenvalue of L ρ , and thus (1.19) is satisfied. Moreover, by compactness in L 2 of the sequence ψ h , one gets that for any ǫ > 0 small enough, there exists h ǫ > 0 such that

♯Spec(h -2 Q h,ρ ) ∩ [ν j -ǫ, ν j + ǫ] ≤ m j , (3.17)
for h ∈]0, h ǫ ] with h ǫ > 0 small enough. It remains to show that there is equality in (3.17), and we shall proceed by induction on j. Let ǫ > 0, small, be given such that for 0 ≤ ν j ≤ M + 1, the intervals I ǫ j = [ν jǫ, ν j + ǫ] are disjoint. Let (µ j ) j≥0 be the increasing sequence of eigenvalues of h -2 Q h,ρ , σ N = N j=1 m j and (e k ) k≥0 the eigenfunctions of L ρ such that for all k ∈ {1+σ N , . . . , σ N +1 }, one has (L ρ -ν N +1 )e k = 0. As 0 is a simple eigenvalue of both L ρ and Q h,ρ , we have clearly ν 0 = µ 0 = 0 and m

0 = 1 = ♯Spec(h -2 Q h,ρ ) ∩ [ν 0 -ǫ, ν 0 + ǫ].
Suppose that for all n ≤ N ,

m n = ♯Spec(h -2 Q h,ρ ) ∩ [ν n -ǫ, ν n + ǫ]. Then, one has by (1.19), for h ≤ h ε , µ 1+σ N ≥ ν N +1 -ǫ. (3.18) By the min-max principle, if G is a finite dimensional subspace of H 1 with dim(G) = 1 + σ N +1 , one has µ σ N +1 ≤ sup ψ∈G, ψ =1 h -2 Q h,ρ ψ, ψ L 2 (ρ) (3.19)
Thanks to Lemma 3.2, for all e k , 0 ≤ k ≤ σ N +1 and all α > 0, there exists e k,α ∈ D 0 such that e ke k,α H 1 ρ ≤ α. Let G α be the vector space spanned by the e k,α , 0 ≤ k ≤ σ N +1 . For α small enough, one has dim(G α ) = 1 + σ N +1 . From Lemma 3.1, one has

h -2 Q h,ρ e k,α , e k ′ ,α L 2 (ρ) = L ρ e k,α , e k ′ ,α L 2 (ρ) + O α (h 1/2 ). (3.20) Since e k,α ∈ D 0 , one has L ρ e k,α , e k ′ ,α L 2 (ρ) = α d 2 ∇e k,α , ∇e k ′ ,α L 2 ρ and ∇e k,α , ∇e k ′ ,α L 2 ρ = ∇e k , ∇e k ′ L 2 ρ + O(α). Therefore, for ψ ∈ G α , ψ = 1, we get h -2 Q h,ρ ψ, ψ L 2 (ρ) ≤ ν N +1 + Cα + O α (h 1/2 ).
(3.21)

Taking α > 0 small enough and h < h α , we obtain from (3.19) and (3.21),

µ σ N +1 ≤ ν N +1 + ǫ.
Combining this with (3.18) and (3.17), we get

m N +1 = ♯Spec(h -2 Q h,ρ ) ∩ [ν N +1 -ǫ, ν N +1 + ǫ].
The proof of Theorem 1.2 is complete.

Application to Random Placement of Non-Overlapping Balls

In this section, we suppose that Ω is a bounded, Lipschitz, quasi-regular, connected, open subset of R d with d ≥ 2. Let N ∈ N, N ≥ 2 and ǫ > 0 be given. Let O N,ǫ be the open bounded subset of

R N d , O N,ǫ = x = (x 1 , . . . , x N ) ∈ Ω N , ∀ 1 ≤ i < j ≤ N, |x i -x j | > ǫ .
We introduce the kernel

K h (x, dy) = 1 N N j=1 δ x 1 ⊗ • • • ⊗ δ x j-1 ⊗ h -d ϕ x j -y j h dy j ⊗ δ x j+1 ⊗ • • • ⊗ δ x N , (4.1)
and the associated Metropolis operator on L 2 (O N,ǫ )

T h (u)(x) = m h (x)u(x) + O N,ǫ u(y)K h (x, dy), (4.2) with m h (x) = 1 - O N,ǫ K h (x, dy). (4.3)
The operator T h is Markov and self -adjoint on L 2 (O N,ǫ ). The configuration space O N,ǫ is the set of N disjoint closed balls of radius ǫ/2 in R d , with centers at the x j ∈ Ω. The topology of this set, and the geometry of its boundary is generally hard to understand, but since d ≥ 2, O N,ǫ is clearly non-void and connected for a given N if ǫ is small enough. The Metropolis kernel T h is associated to the following algorithm: at each step, we choose uniformly at random a ball, and we move its center uniformly at random in R d in a ball of radius h. If the new configuration is in O N,ǫ , the change is made. Otherwise, the configuration is kept as it started.

In order to study the random walk associated to T h , we will assume that N and ǫ are such that N ǫ is small enough. Under this condition, we prove in Proposition 4.1 that the open set O N,ǫ is connected, Lipschitz and quasi-regular, and in Proposition 4.4 we prove that the kernel of the iterated operator T M h (with M large, but independent of h) admits a suitable lower bound, so that we will be able to use Remark 2 at the end of Section 2. The main results are collected together in Theorem 4.6 below.

We define Γ reg and Γ sing the set of regular and singular points of ∂O N,ǫ as follows. Denote

N N = {1, . . . , N }. For x ∈ O N,ǫ set R(x) = {i ∈ N N , x i ∈ ∂Ω}, S(x) = {τ = (τ 1 , τ 2 ) ∈ N N , τ 1 < τ 2 and |x τ 1 -x τ 2 | = ǫ} , r(x) = ♯R(x), s(x) = ♯S(x).
(4.4)

The functions r and s are lower semi-continuous and any

x ∈ O N,ǫ belongs to ∂O N,ǫ iff r(x)+s(x) ≥ 1. Define Γ reg = x ∈ O N,ǫ , s(x) = 1 and r(x) = 0 ∪ x ∈ O N,ǫ , s(x) = 0, R(x) = {j 0 } and x j 0 ∈ ∂Ω reg (4.5)
and Γ sing = ∂O N,ǫ \ Γ reg . Then Γ sing is clearly closed, and the Γ reg is the union of smooth disjoint hypersurfaces in R N d .

Proposition 4.1. There exists α > 0 such that for N ǫ ≤ α, the set O N,ǫ is connected, Lipschitz and quasi-regular.

Remark 3. Observe that in the above Proposition, the smallness condition on ǫ is N ǫ ≤ α where α > 0 depends only on Ω. The condition N ǫ d ≤ c, which says that the density of the balls is sufficiently small, does not imply that the set O N,ǫ has Lipschitz regularity. As an example, if Ω =]0, 1[ 2 is the unit square in the plane, then x = (x 1 , . . . , x N ), x j = ((j -1)ǫ, 0), j = 1, . . . , N , with ǫ = 1 N -1 is a configuration point in the boundary ∂O N,ǫ . However, ∂O N,ǫ is not Lipschitz at x: otherwise, there would exist ν j = (a j , b j ) such that (x 1 + tν 1 , . . . , x N + tν N ) ∈ O N,ǫ for t > 0 small enough, and this implies a 1 > 0, a j+1 > a j and a N < 0 which is impossible.

Proof. For ν ∈ S p-1 , p ≥ 1 and δ ∈]0, 1[, denote Γ ± (ν, δ) = {ξ ∈ R p , ± ξ, ν > (1 -δ)|ξ|, | ξ, ν | < δ} .
(4.6)

We remark [START_REF] Adams | Pure and Applied Mathematics[END_REF] that an open set O ⊂ R p is Lipschitz if and only if it satisfies the cone property:

∀a ∈ ∂O, ∃δ > 0, ∃ν a ∈ S p-1 , ∀b ∈ B(a, δ) ∩ ∂O we have b + Γ + (ν a , δ) ⊂ O and b + Γ -(ν a , δ) ⊂ R p \ O. (4.7)
Let us first show that O N,ǫ is connected for N ǫ small. For x ∈ O N,ǫ define

I(x) = inf i =j |x i -x j |. (4.8)
Then I(x) > ǫ and we have the following lemma.

Lemma 4.2. There exists α 0 > 0 such that for any N ∈ N, ǫ > 0 with N ǫ ≤ α 0 , there exists δ N,ǫ > 0 such that for any x ∈ O N,ǫ with I(x) < α 0 /N , there exists a continuous path γ : [0, 1] → O N,ǫ such that γ(0) = x and I(γ(1)) ≥ I(x) + δ N,ǫ .

Proof. As Ω is bounded and Lipschitz, a compactness argument shows that there exists δ 0 > 0, r 0 > 0 such that

∀x 0 ∈ Ω, ∃ν ∈ S d-1 , ∀x ∈ B(x 0 , r 0 ) ∩ Ω, x + Γ + (ν, δ 0 ) ⊂ Ω ∀x 0 ∈ ∂Ω, ∃ν ∈ S d-1 , ∀x ∈ B(x 0 , r 0 ) ∩ ∂Ω, x + Γ -(ν, δ 0 ) ⊂ R d \ Ω. (4.9) Let α 0 < min(δ 0 , r 0 )/100. For K ∈ N * denote δ K = α 0 /K 3 , ρ K = 10α 0 /K 2 .
Observe that it suffices to show the following statement:

∀K ∈ N * , ∀ǫ ∈]0, α 0 /K], ∀N ∈ N K , ∀x ∈ O N,ǫ s.t. I(x) < α 0 /K, ∃γ ∈ C([0, 1], O N,ǫ ), s.t. γ(0) = x, I(γ(1)) ≥ I(x) + δ K and ∀t ∈ [0, 1], |x -γ(t)| ∞ ≤ N ρ K (4.10)
Let K ≥ 1 and 0 < ǫ < α 0 /K. We proceed by induction on N ∈ N K . (Recall that N K = {0, 1, . . . , K}.) In the case N = 1, there is nothing to show. Suppose that the above property holds true at rank N -1 and let x ∈ O N,ǫ be such that I(x) < α 0 /K (this is possible since ǫ < α 0 /K). Introduce the equivalence relation on N N defined by i ≃ x j iff x i and x j can be connected by a path lying in ∪ k∈N N B(x k , 40α 0 /K) and denote by c(x) the number of equivalence class.

Suppose that c(x) ≥ 2. Then there exists a partition N N = I ∪ J, such that N I = ♯I ≥ 1, N J = ♯J ≥ 1 and for all i ∈ I, j ∈ J, |x ix j | > 40α 0 /K. By induction, there exists a path

γ I : [0, 1] → Ω N I ∩{(x i ) i∈I , ∀i = j, |x i -x j | > ǫ} such that γ I (0) = (x i ) i∈I , I(γ I (1)) ≥ I(γ I (0))+δ K and |γ I (0) -γ I (t)| ∞ < N I ρ K .
The same construction for the set J provides a path γ J with the same properties. Define the path γ on [0, 1] by (γ(t)

) i = (γ I (t)) i for i ∈ I and (γ(t)) j = (γ J (t)) j for j ∈ J. Since 40α 0 /K -(N I + N J )ρ K > α 0 /K + δ K > ǫ, γ has values in O N,ǫ and we have I(γ(1)) ≥ I(x) + δ K as well as |x -γ(t)| ∞ < max(N I , N J )ρ K ≤ (N -1)ρ K .
(4.11)

Suppose now that there is only one equivalence class. Then for all k ∈ N N , |x 1x k | ≤ 40α 0 N/K ≤ 40α 0 < r 0 , were r 0 is defined in (4.9). In particular, there exists ν ∈ S d-1 such that for all y ∈ B(x 1 , 40α 0 ) ∩ Ω, y + Γ + (ν, δ 0 ) ⊂ Ω. On the other hand, we can suppose without loss of generality that

x 1 , ν ≤ • • • ≤ x N , ν .
(4.12)

For j ∈ {1, ..., N } set a j = jρ K and

γ(t) = (x 1 + ta 1 ν, ..., x N + ta N ν), t ∈ [0, 1] (4.13) Then, one has |x -γ(t)| ∞ ≤ sup a j = N ρ K , x j + ta j ν ∈ Ω since N ρ K ≤ δ 0 , and for i < j |(x j + ta j ν) -(x i + ta i ν)| 2 = |x j -x i | 2 + 2t(a j -a i ) x j -x i , ν + t 2 |a j -a i | 2 ≥ |x j -x i | 2 + t 2 |a j -a i | 2 (4.14)
Thus one has

I(γ(1)) 2 ≥ I(x) 2 + ρ 2 K ≥ (I(x) + δ K ) 2 (4.15)
The proof of lemma 4.2 is complete.

Using this lemma, it is easy to show that O N,ǫ is connected for N ǫ small. For x ∈ O N,ǫ , define

I x = {y ∈ O N,ǫ , ∃γ ∈ C ([0, 1], O N,ǫ ) , γ(0) = x, γ(1) = y} . (4.16)
We first show easily that there exists y ∈ I x such that I(y) ≥ α 0 /N if N ǫ < α 0 . Let M = max y∈Ix I(y). As I is a bounded function, M is finite and given γ ∈]0, δ N,ǫ /2[, there exists y 1 ∈ I x such that I(y 1 ) ≥ Mγ. If I(y 1 ) < α 0 /N , Lemma 4.2 shows that there exists y 2 ∈ I x such that I(y 2 ) ≥ I(y 1 ) + δ N,ǫ > M which is impossible. This shows that there exists y ∈ I x such that I(y) ≥ α 0 /N . Now by 4.9, for any x ∈ Ω, there exists ν x ∈ S d-1 such that x + tν x ∈ Ω for t ∈ [0, δ 0 ] and dist(x + tν x , ∂Ω) ≥ t sin θ 0 with cos θ 0 = 1δ 0 . Let α 1 = α 0 sin θ 0 /20. Then for N ε ≤ α 1 , and

I(y) ≥ α 0 /N , γ(t) = (y 1 + tα 0 /4N ν y 1 , ..., y N + tα 0 /4N ν y N ), t ∈ [0, 1] is a path in O N,ǫ
and one has with γ(1) = y ′ = (y ′ 1 , ..., y ′ N ), I(y ′ ) ≥ α 0 /2N , and dist(y ′ j , ∂Ω) > 3ε for all j. Let C N,ǫ be the set of x ∈ O N,ǫ such that I(x) ≥ α 0 /2N and dist(x j , ∂Ω) > 3ε for all j. It remains to show that for any x, y ∈ C N,ǫ there exists a continous path γ from x to y, with values in O N,ǫ for N ǫ ≤ α 1 . Decreasing α 0 we may assume 6c d α d 0 < vol(Ω) with c d = vol(B(0, 1)). Decreasing α 1 , we get that for any x, y ∈ C N,ǫ with N ǫ ≤ α 1 , there exists z ∈ C N,ǫ such that

|x p -z q | ≥ α 0 /2N and |y p -z q | ≥ α 0 /2N ∀p, q ∈ N N .
(4.17)

One can easily choose the z j by induction, since for any x, y ∈ O N,ǫ and any z 1 , ..., z l ∈ Ω with 0

≤ l ≤ N -1 we have vol(∪ N j=1 B(x j , α 0 /N ) ∪ N j=1 B(y j , α 0 /N ) ∪ l j=1 B(z j , α 0 /N )) ≤ 3N c d α d 0 N -d < vol(Ω)/2 < vol({x ∈ Ω, dist(x, ∂Ω)} > 3ǫ).
Thus we are reduced to showing that if y, z ∈ C N,ǫ satisfy 4.17, there exists a continuous path γ from y to z, with values in O N,ǫ if N ǫ ≤ α 1 . We look for a path γ of the form

γ = γ N • • • • • γ 1 ,
where the path γ j moves only the jth ball from y j to z j . Let us explain how to choose γ j . As Ω is connected, there exists an analytic path γ1 which connects y 1 to z 1 in Ω. We have to modify the path γ1 in a new path γ 1 in order that

|γ 1 (t) -y j | > ǫ ∀j ∈ {2, . . . , N }. (4.18) Let K = {t ∈ [0, 1], ∃j 0 ∈ {2, . . . , N }, |γ 1 (t) -y j 0 | ≤ 2ǫ}. If K is empty, we set γ 1 = γ1 . If K is non empty, since the path γ1 is analytic and I(y) ≥ α 0 /2N > 4ǫ, K is a disjoint union of intervals, K = [a 1 , b 1 ] ∪ ... ∪ [a L , b L ]
and for any l ∈ {1, ..., L} there exists a unique j l such that |γ 1 (t)y j l | ≤ 2ǫ for t ∈ [a l , b l ]. For t / ∈ K we set γ 1 (t) = γ1 (t) and for t ∈ [a l , b l ] we replace γ1 by a continuous path γ 1 connecting γ1 (a l ) to γ1 (b l ) on the sphere |xy j l | = 2ǫ which is contained in Ω. Then γ 1 (t) is continuous. Moreover, as I(y) > 4ǫ, for any j ∈ {2, ..., N } and t ∈ [0, 1] we have |γ 1 (t)y j | ≥ 2ǫ. In particular, the path t ∈ [0, 1] → (γ 1 (t), y 2 , . . . , y N ) has values in O N,ǫ and connects y and ỹ := (z 1 , y ′ ). From (4.17) it is clear that ỹ ∈ C N,ǫ and that (4.17) holds true with y replace by ỹ. This permits iterating the construction to build a continuous path from y to z. Thus O N,ǫ is connected for N ǫ < α 1 .

Let us now prove that ∂O N,ǫ has Lipschitz regularity for N ǫ ≤ r 0 /2, where r 0 is given by 4.9. For a given ǫ, we will prove this fact by induction on N ∈ [1, r 0 /2ǫ]. The case N = 1 is obvious since ∂Ω is Lipschitz. Let x ∈ ∂O N,ǫ . The equivalence relation i ≃ j iff x i and x j can be connected by a path lying in the union of closed balls of radius ǫ/2, gives us a partition {1, . . . , N } = ∪ r k=1 F k such that

|x i -x j | > ǫ ∀k = l, ∀i ∈ F k , ∀j ∈ F l ; |x n l -x n l+1 | = ǫ ∀k, ∀i = j ∈ F k , ∃(n l ) ∈ F k , 1 ≤ l ≤ m, n 1 = i, n m = j. (4.19) The Cartesien product O 1 × O 2 of two bounded Lipschitz open subsets O i ⊂ R d i has Lipschitz regularity.
Thus, if r ≥ 2, the induction hypothesis on N shows that ∂O N,ǫ has Lipschitz regularity near x. Thus we may assume r = 1, and therefore, for all i, j one has |x i -

x j | ≤ ǫ(N -1) ≤ r 0 /2.
Thus there exists x 0 ∈ Ω such that x i ∈ B(x 0 , r 0 /2), and 4.9 gives us a unit vector ν and δ 0 > 0. We set

ξ i = αx i + ν (4.20)
with α > 0 small such that tξ i ∈ Γ + (ν, δ 0 /2) for t > 0 small. We choose β > 0, ρ > 0, t 0 > 0 such that β << αǫ 2 , β << δ 0 , ρ << αǫ 2 , ρ << r 0 , t

0 |ξ i | 2 << αǫ 2 , t 0 << δ 0 . Let x ∈ ∂O N,ǫ be such that |x j -x j | ≤ ρ and θ i ∈ R d be such that |θ i | ≤ β. Let ξ i = ξ i + θ i , and ξ = (ξ 1 , • • • , ξ N ). One has tξ i ∈ Γ + (ν, δ 0 ) for t ∈]0, t 0 ] and tξ i ∈ Γ -(ν, δ 0 ) for t ∈ [-t 0 , 0[. From x i -x j , ξ i -ξ j = x i -x j , ξ i -ξ j + O(β) = α|x i -x j | 2 + O(β + ρ) (4.21) and |(x i + tξ i ) -(x j + tξ j )| 2 = |x i -x j | 2 + 2t x i -x j , ξ i -ξ j + t 2 |ξ i -ξ j | 2 (4.22)
we get that the function t ∈ [-t 0 , t 0 ] → g i,j (t) = |(x i + tξ i ) -(x j + tξ j )| 2 is strictly increasing. Since by 4.9 we have

x i + tξ i ∈ Ω for t ∈]0, t 0 ], we get x + tξ ∈ O N,ǫ for t ∈]0, t 0 ]. It remains to show x + tξ / ∈ O N,ǫ for t ∈ [-t 0 , 0[. If
there exists two indices i, j such that |x ix j | = ǫ, this follows from g i,j (t) < ǫ 2 for t < 0. If there exists one indice i such that x i ∈ ∂Ω, this follows from tξ i ∈ Γ -(ν, δ 0 ) and the second line of 4.9 which implies

x i + tξ i / ∈ Ω for t ∈ [-t 0 , 0[. Thus ∂O N,ǫ is Lipschitz.
Let us finally prove that O N,ǫ is quasi-regular. Let u ∈ H -1/2 (∂O N,ǫ ) be supported in Γ sing . We have to show that u is identically zero. This is a local problem near any point x ∈ Γ sing . Let x be such that s(x) = 0, R(x) = {j 0 } (say j 0 =1) and

x j 0 ∈ ∂Ω sing . Denote D N,ǫ = {x ∈ (R d ) N , |x i -x j | > ǫ, ∀1 ≤ i < j ≤ N }. Let χ be a cut-off function supported near x such that sup(χ) ⊂ (R d ×Ω N -1 )∩D N,ǫ . Then, for any ψ ∈ C ∞ 0 (Ω N -1 ) the linear form u ψ defined on H 1/2 (∂Ω) by u ψ , f = χu, f (x 1 )ψ(x 2 , . . . , x N ) (4.23)
is continuous and supported in ∂Ω sing . As ∂Ω is quasi-regular, it follows that u ψ is equal to zero for all ψ and hence, χu = 0. Therefore, we can suppose that u is supported in the set {r(x)+s(x) ≥ 2}.

Let v be the distribution on

R N d v, ϕ = u, ϕ| ∂O N,ǫ (4.24)
Then v ∈ H -1 (R N d ) and its support is equal to sup(u). The Sobolev space H -1 is preserved by bi-Lipschitz maps. Therefore, if there exists a bi-Lipschitz map Φ defined near x such that locally one has Φ(sup(u)) ⊂ {y 1 = y 2 = 0}, then u is identically 0 near x. For n ∈ N, n ≥ 2, introduce the following property:

(P n ) : for any x ∈ Γ sing with r(x) + s(x) = n, we have u = 0 near x. (4.25)

This property is proved by induction on n. By lower semicontinuity of the functions r and s, we may assume in the proof that for x ∈ sup(u) close to x, one has r(x) = r(x) and s(x) = s(x) and hence R(x) = R(x) and S(x) = S(x). Therefore, we are reduced to proving that for x ∈ Γ sing with r(x) + s(x) ≥ 2 and u ∈ H -1/2 (∂O N,ǫ ) supported in R(x) = R(x) and S(x) = S(x), we have u = 0 near x .

First assume r(x) = s(x) = 1. Then, we can suppose without losing generality, that u is supported near x in G = (∂Ω × Ω N -1 ) ∩ {|x ix 2 | = ǫ} for some i ∈ {1, 3, . . . , N }. Denoting x i = (x i,1 , . . . , x i,d ), we may assume that near x, G is given by two equations,

x 1,1 = α(x ′ 1 ), x ′ 1 = (x 1,2 , ..., x 1,d ) x 2,k = β(x ′ 2 , x i ), x ′ 2 = (x 2
x) = (x 1,1 -α(x ′ 1 ), x 2,k -β(x ′ 2 , x i ), x ′ 1 , x ′ 2 , x 3 , . . . , x N ) defines a local bi-Lipschitz homeomorphism of R N d such that ν • G ⊂ {0} 2 × R N d-2
. Therefore, ν * (v) vanishes identically near ν(x) and hence u is null near x.

We may thus assume that s(x) ≥ 2 or r(x) ≥ 2. In the case s(x) ≥ 2, the support of u near x is contained in a set A of the form

|x 1 -x 2 | = |x 2 -x 3 | = ǫ or |x 1 -x 2 | = |x 3 -x 4 | = ǫ. Since A is a subvariety of R N d of
codimension 2, we get as above that u is null near x. In the case r(x) ≥ 2, the support of u near x is contained in a set B of the form ∂Ω × ∂Ω × R (N -2)d which is near x bi-Lipschitz homeomorphic to (y 1 = y 2 = 0) × R N d-2 , and thus u is null near x. The proof of Proposition 4.1 is complete. Define for j ∈ N N the two functions π j from R N d to R N d and σ j from R d to R N d by π j (x 1 , . . . , x j , . . . , x N ) = (x 1 , . . . , 0, . . . , x N ), σ j (y) = (0, . . . , y, . . . , 0), (4.27) so that x = π j (x) + σ j (x j ). The following geometric lemma will be the main ingredient of the proof of Proposition 4.4.

Lemma 4.3. Let α 0 = r 0 /10 with r 0 given by 4.9. For all N ∈ N and ǫ ∈]0, α 0 /N ], there exists δ N,ǫ > 0 and a finite covering (U l ) l of O N,ǫ such for all l, there exists j and ν ∈ S d-1 such that

x + σ j (Γ + (ν, δ N,ǫ )) ⊂ O N,ǫ ∀x ∈ U l ∩ O N,ǫ . (4.28)
Proof. Since O N,ǫ is compact, we have to prove that for any given x 0 ∈ O N,ǫ , there exist r > 0, δ = δ N,ǫ > 0, j and ν ∈ S d-1 such that (4.28) holds true for x ∈ O N,ǫ ∩ B(x 0 , r). This means that we can select one ball, and that moving only this ball by a vector in Γ + (ν, δ) while keeping the other balls fixed, results in an admissible configuration. We shall proceed by induction on N ≥ 1.

For N = 1, this is true since Ω is Lipschitz. Let N ≥ 2. If one can write {1, . . . , N } as the disjoint union I ∪ J with ♯I ≥ 1, ♯J ≥ 1, and

|x 0 i -x 0 j | ≥ 5ǫ ∀i ∈ I, ∀j ∈ J, (4.29)
then, by the induction hypothesis, the result is true for some δ N,ǫ ∈]0, 4ǫ[. Thus, using the definition of α 0 , we may assume that all the x 0 i are in a small neighborhood of a given point y 0 ∈ Ω and sup k |x 0 ky 0 | ≤ r 0 /2. By 4.9 there exist ν, δ 0 > 0, r 0 > 0 such that y ∈ Ω and |yy 0 | ≤ r 0 =⇒ y + Γ + (ν, δ 0 ) ∈ Ω (4.30)

It remains to show that there exist j, r ′ 0 ∈]0, r 0 [, and ν ′ , δ ′ 0 > 0, with Γ + (ν ′ , δ ′ 0 ) ⊂ Γ + (ν, δ 0 ), such that for all x = (x 1 , . . . , x N ) ∈ O N,ǫ with dist(x, x 0 ) ≤ r ′ 0 , and all z ∈ x j + Γ + (ν ′ , δ ′ 0 ), one has |zx k | > ǫ for all k = j. This will be a consequence of the following property:

∀β > 0, ∃j, ∃ν ′ ∈ S d-1 s.t. |ν ′ -ν| ≤ β and ν ′ .(x 0 j -x 0 k ) > 0 ∀k = j. (4.31)
In fact, if (4.31) holds true, first take β small enough, such that for all ν ′ ∈ S d-1 with |ν ′ -ν| ≤ β there exists δ ′ 0 > 0 with Γ + (ν ′ , δ ′ 0 ) ⊂ Γ + (ν, δ 0 ); then (4.31) gives us a pair ν ′ , j such that ν ′ .(x 0 jx 0 k ) > 0 ∀k = j. For r ′ 0 > 0, δ ′ 0 > 0 small enough, we get for all ξ ∈ Γ + (ν ′ , δ ′ 0 ) and all x ∈ O N,ǫ , dist(x, x 0 ) ≤ r ′ 0 , that inf k =j ξ.(x jx k ) ≥ δ ′ 0 |ξ|, and thus there exists t 0 such that for t ∈ [0, t 0 ] and k = j, the function t → |x k -(x j + tξ)| 2 is strictly increasing for all x ∈ O N,ǫ , dist(x, x 0 ) ≤ r ′ 0 and all ξ ∈ Γ + (ν ′ , δ ′ 0 ).

Let us show that (4.31) holds true. If j → ν.x 0 j achieve its maximum at a single j, then (4.31) is obvious with ν = ν ′ . Otherwise, the set A = {ν ′ ∈ S d-1 , ∃j = k, ν ′ .(x 0 jx 0 k ) = 0} is contained in a finite union of equators in the sphere S d-1 , with ν ∈ A, and thus (4.31) is still obvious by taking ν ′ ∈ S d-1 \ A close to ν. The proof of Lemma 4.3 is complete.

For k ∈ N * denote B k = B R k (0, 1) the unit Euclidean ball and ϕ k (z) = 1 vol(B k ) 1 B k (z). Proposition 4.4. Let N, ǫ be given such that Lemma 4.3 holds true. There exists h 0 > 0, c 0 , c 1 > 0 and M ∈ N * such that for all h ∈]0, h 0 ], one has

T M h (x, dy) = µ h (x, dy) + c 0 h -N d ϕ N d x -y c 1 h dy, (4.32)
where for all x ∈ O N,ǫ , µ h (x, dy) is a positive Borel measure.

Proof. For x, y ∈ O N,ǫ , we set dist(x, y) = sup 1≤i≤N |x i -y i |. For N ≥ 1, denote by K h,N the kernel given in (4.1). It is sufficient to prove the following: there exists h 0 > 0, c 0 , c 1 > 0 and M (N ) ∈ N * such that for all h ∈]0, h 0 ], one has for all nonnegative function f ,

K M (N ) h,N (f )(x) ≥ c 0 h -N d y∈O N,ǫ ,dist(y,x)≤c 1 h f (y)dy. (4.33)
First note that it is sufficient to prove the weaker version: for all x 0 ∈ O N,ǫ , there exist M (N, x 0 ), r = r(x 0 ) > 0, c 0 = c (x 0 ) > 0, c 1 = c 1 (x 0 ) > 0, h 0 = h 0 (x 0 ) > 0 such that for all h ∈]0, h 0 ], all x ∈ O N,ǫ and all nonnegative function

f dist(x, x 0 ) ≤ 2r =⇒ K M (N,x 0 ) h,N (f )(x) ≥ c 0 h -N d y∈O N,ǫ ,dist(y,x)≤c 1 h f (y)dy. (4.34)
Let us verify that (4.34) implies (4.33). Decreasing r(x 0 ) if necessary, we may assume that any set {dist(x, x 0 ) ≤ 2r(x 0 )} is contained in one of the open set U l of Lemma 4.3. There exists a finite set F such that O N,ǫ ⊂ ∪ x 0 ∈F {dist(x, x 0 ) ≤ r(x 0 )}. Let M (N ) = sup x 0 ∈F M (N, x 0 ), c ′ i = min x 0 ∈F c i (x 0 ) and h ′ 0 = min x 0 ∈F h 0 (x 0 ). One has to check that for any x 0 ∈ F and any x with dist(x, x 0 ) ≤ r(x 0 ), the right inequality in (4.34) holds true with M (N ) = M (N, x 0 ) + n in place of M (N, x 0 ) for some constants c 0 , c 1 , h 0 . Let l be such that dist(x, x 0 ) ≤ r(x 0 ) implies x ∈ U l . Let j and Γ + (ν, δ) be given by Lemma 4.3. Clearly, if f is nonnegative, one has

K M (N,x 0 )+1 h,N (f )(x) ≥ 1 N h -d x+σ j (z)∈O N,ǫ ϕ(z/h)K M (N,x 0 ) h,N (f )(x + σ j (z))dz (4.35) For dist(x, x 0 ) ≤ 2r(x 0 ) -c ′ 1 h/2, and |z| ≤ c ′ 1 h/2, z ∈ Γ + (ν, δ), one has dist(x + σ j (z), x 0 ) ≤ 2r(x 0 ) and by (4.28), x + σ j (z) ∈ O N,ǫ . Moreover, dist(y, x) ≤ c ′ 1 h/2 =⇒ dist(y, x + σ j (z)) ≤ c ′ 1 h. From (4.35
) and (4.34) we thus get, with a constant C δ depending only on the δ given by Lemma 4.3, and for h

≤ h ′ 0 , dist(x, x 0 ) ≤ 2r(x 0 ) -c ′ 1 h/2 =⇒ K M (N,x 0 )+1 h,N (f )(x) ≥ C δ N c ′ 0 h -N d y∈O N,ǫ ,dist(y,x)≤c ′ 1 h/2 f (
) ≤ 2r(x 0 ) -c ′ 1 h =⇒ K M (N,x 0 )+n h,N (f )(x) ≥ C δ N n c ′ 0 h -N d y∈O N,ǫ ,dist(y,x)≤c ′ 1 h 2 n f (y)dy. (4.37)
Since n is bounded, we get the desired result with h 0 = min(min x 0 ∈F r(x 0 )/c ′ 1 , h ′ 0 ). To complete the proof, let us show (4.34) by induction on N . The case N = 1 is obvious. Suppose that (4.34) holds for N -1 discs. Let x 0 ∈ O N,ǫ be fixed. Thanks to Lemma 4.3, we can suppose that there exists an open neighborhood U of x 0 , a direction ν ∈ S d-1 and δ > 0 such that (4.28) holds with j = 1. Let us denote x = (x 1 , x ′ ) and define

K h,N = K h,N,1 + K h,N,> (4.38) with K h,N,1 f (x) = h -d N (y 1 ,x ′ )∈O N,ǫ ϕ x 1 -y 1 h f y 1 , x ′ dy 1 . (4.39) We also denote G(ν, δ) = {x 1 ∈ Γ + (ν, δ), |x 1 | > δ 2 }.
Then, we have the following: Lemma 4.5. For any δ ′ ∈]0, δ/2], there exists C > 0, α > 0, h 0 > 0 and r 0 > 0 such that ∀r ∈]0,

r 0 ], ∀h ∈]0, h 0 ], ∀x ∈ U ∩ O N,ǫ , ∀x ∈ x + h(G(ν, δ ′ ) × B(0, r) N -1 ) with x′ ∈ O N -1,ǫ , we have x ∈ O N,ǫ and K h,N,> f (x) ≥ CK αh,N -1 (f (x 1 , .)) x′ , (4.40)
for any nonnegative function f . In particular, for all M ∈ N * , there exists C, r 0 , h 0 , α as above such that ∀x ∈ U ∩ O N,ǫ and ∀x ∈ x + h(G(ν, δ ′ ) × B(0, r) N -1 ), we have

K M h,N,> f (x) ≥ CK M αh,N -1 (f (x 1 , .)) x′ . (4.41)
Proof. Inequality (4.41) is obtained easily from (4.40) by induction on M . To prove (4.40), observe that for nonnegative f and α ∈]0, 1[ we have

K h,N,> f (x) ≥ h -d N N j=2 A j,α,h (x) f (x 1 , . . . , y j , . . . , xN )dy j , (4.42)
with A j,α,h (x) = {z ∈ Ω, |x j -z| < αh and ∀k = j, |x k -z| > ǫ}. Let B j,α,h (x) = {z ∈ Ω, |x j -z| < αh and ∀k = 1, j, |x k -z| > ǫ}. Then A j,α,h ⊂ B j,α,h and we claim that for α, r > 0 small enough and x ∈ x + h(G(ν, δ ′ ) × B(0, r) N -1 ) with x′ ∈ O N -1,ǫ , we have B j,α,h (x) = A j,α,h (x). Indeed,

let x1 = x 1 + hu 1 with u 1 ∈ G(ν, δ ′ ) and x′ ∈ O N -1,ǫ be such that |x j -x j | < hr. Then for z ∈ B j,α,h (x), |x 1 -z| = |x 1 -x j + hv 1 |, (4.43)
with v 1 = u 1 +

x j -x j h + xj -z h . Taking α, r small enough (w.r.t. δ) it follows that v 1 ∈ Γ + (ν, δ). Consequently, Lemma 4.3 shows that |x 1 -z| > ǫ and hence z ∈ A j,α,h (x) (the same argument shows that x ∈ O N,ǫ ). Therefore,

K h,N,> f (x) ≥ h -d N N j=2 B j,α,h (x) f (x 1 , . . . , y j , . . . , xN )dy j = (N -1)vol(B d ) N K αh,N -1 (f (x 1 , .)) x′ , (4.44)
and the proof of Lemma 4.5 is complete.

Using this lemma we can complete the proof of (4.34). Let p ∈ N, α ∈]0, α 0 ] and x ∈ O N,ǫ , then

K p+1 h,N f (x) ≥ K h,N,1 K p h,N,> f (x) ≥ h -d N (z 1 ,x ′ )∈O N,ǫ ,z 1 ∈x 1 +hG(ν,δ ′ ) K p h,N,> f z 1 , x ′ dz 1 ≥ C h -d N (z 1 ,x ′ )∈O N,ǫ ,z 1 ∈x 1 +hG(ν,δ ′ ) K p αh,N -1 (f (z 1 , .)) x ′ dz 1 , (4.45)
thanks to Lemma 4.5. From the induction hypothesis we can choose p ∈ N so that

K p+1 h,N f (x) ≥ Ch -N d (z 1 ,x ′ )∈O N,ǫ ,z 1 ∈x 1 +hG(ν,δ ′ ) |x ′ -y ′ |<αh,y ′ ∈O N -1,ǫ f z 1 , y ′ dy ′ dz 1 (4.46)
Hence, for any β ∈]0, 1] we get

K p+2 h,N f (x) ≥ K p+1 h,N K h,N,1 f (x) ≥ Ch -N d D α,β,h (x) f y 1 , y ′ γ h (x, y 1 )dy 1 dy ′ , (4.47) with D α,β,h (x) = y ∈ O N,ǫ , |x ′ -y ′ | < αh, |x 1 -y 1 | < βh (4.48) and γ h (x, y 1 ) = h -d (z 1 ,x ′ )∈O N,ǫ ,z 1 ∈x 1 +hG(ν,δ ′ ) 1 |z 1 -y 1 |<h dz 1 . (4.49)
We have to show that γ h is bounded from below by a positive constant, uniformly with respect to (x, y 1 ) when Plugging this lower bound into (4.47), gives

|x 1 -y 1 | < βh. For z 1 ∈ x 1 + hG(ν, δ ′ ), one has |z 1 -y 1 | ≤ |z 1 -x 1 | + |x 1 -y 1 | ≤ hδ ′ + hβ < h for β and δ ′ small. Thus for |x 1 -y 1 | < βh one has γ h (x, y 1 ) = h -d (z 1 ,x ′ )∈O N,ǫ ,z 1 ∈x 1 +hG(ν,δ ′ ) dz 1 = u∈G(ν,δ ′ ) 1 (x 1 +hu,x ′ )∈O N,ǫ du. ( 4
K p+2 h,N ≥ Ch -N d D α,β,h (x) f (
|∆| N = - α d 2N ∆, D(|∆| N ) = u ∈ H 1 (O N,ǫ ), -∆u ∈ L 2 (O N,ǫ ), ∂ n u| ∂O N,ǫ = 0 . (4.53)
We still denote 0 = ν 0 < ν 1 < ν 2 < . . . the spectrum of |∆| N and m j the multiplicity of ν j . Our main result is the following.

Theorem 4.6. Let N ≥ 2 be fixed. Let ǫ > 0 be small enough such that Proposition 4.1 and Proposition 4.4 hold true. Let R > 0 be given and β > 0 such that the spectrum ν j of the Neumann Laplacian (4.53) satisfies ν j+1ν j > 2β for all j such that ν j+2 ≤ R.

There exists h 0 > 0, δ 0 ∈]0, 1/2[ and constants C i > 0 such that for any h ∈]0, h 0 ], the following hold true:

i) The spectrum of T h is a subset of [-1 + δ 0 , 1], 1 is a simple eigenvalue of T h , and Spec(T

h ) ∩ [1 -δ 0 , 1] is discrete. Moreover, Spec 1 -T h h 2 ∩]0, R] ⊂ ∪ j≥1 [ν j -β, ν j + β]; ♯Spec 1 -T h h 2 ∩ [ν j -β, ν j + β] = m j ∀ν j ≤ R;
(4.54)

and for any 0 ≤ λ ≤ δ 0 h -2 , the number of eigenvalues of T h in [1h 2 λ, 1] (with multiplicity) is bounded by C 1 (1 + λ) dN/2 .

ii) The spectral gap g(h) satisfies lim The rest of this section is devoted to the proof of Theorem 4.6. Let µ h (x, dy) be given by (4.32) and µ h (f )(x) = O N,ǫ f (y)µ h (x, dy). Thanks to the positivity of µ h (x, dy), using the Markov property of T M h and Lipschitz-continuity of the boundary, we get for some δ ′ 0 > 0, independant of h > 0, small enough

µ h L ∞ ,L ∞ ≤ 1 -inf x∈O N,ǫ O N,ǫ c 0 h -N d ϕ N d
xy c 1 h dy < 1δ ′ 0 .

(4.57)

Since by (4.32) µ h is self-adjoint on L 2 (O N,ǫ ), we also get

µ h L 1 ,L 1 ≤ 1 -δ ′ 0 , (4.58)
and by interpolation it follows that µ h L 2 ,L 2 ≤ 1δ ′ 0 . In particular the essential spectrum of T M h is contained in [0, 1δ ′ 0 ] so that σ ess (T h ) ⊂ [0, 1 -2δ 0 ] with 2δ 0 = 1 -(1δ ′ 0 ) 1/M . Thus Spec(T h ) ∩ [1δ 0 , 1] is discrete. Let us verify that, decreasing δ 0 > 0, we may also assume and define E h as in Section 2. Moreover, the identities (2.12) and (2.13) remain true with obvious modifications.

Lemma 4.7. There exist C 0 , h 0 > 0 such that the following holds true for any h ∈]0, h 0 ] and any u ∈ L 2 (O N,ǫ ): The rest of the proof of Theorem 4.6 follows the strategy of Sections 2 and 3. Using the spectral decomposition (2.41), (2.42) we get easily the estimates (2.48) and (2.50), and it remains to estimate T n h,1 . Following the proof of Lemma 2.4, we can find α > 0 small enough and C > 0 such that the following Nash inequality holds with 1/D = 2 -4/p > 0:

E h (E(u)) ≤ C 0 E h,M (u) + h 2 u 2 L 2 . ( 4
u 2+1/D L 2 ≤ Ch -2 E h,M (u) + h 2 u 2 L 2 u 1/D L 1 ,
∀u ∈ E α . (4.70)

From this inequality, we deduce that for k ≥ h -2 , T kM 1,h L ∞ ,L ∞ ≤ Ce -kM g(h) , (4.71) and this implies for k ≥ h -2 , since the contributions of T kM 2,h , T kM 3,h are negligible, h) . (4.72)

T kM h L ∞ ,L ∞ ≤ C ′ e -kM g(
As T h is bounded by 1 on L ∞ we can replace kM by n ≥ h -2 in (4.72) and (4.56) is proved. Assertion (4.55) is an obvious consequence of (4.54). The proof of (4.54) is the same as the one of Theorem 1.2. Thus, the following lemma will end the proof of Theorem 4.6. Π k =j 1 |x j +hz-x k |>ǫ 1 x j +hz∈Ω z.∂ j θ(x)dz (4.78) satisfies v L ∞ = O(h). Since dist(sup(θ), Γ sing ) > 0, there exists disjoint compact sets F l ⊂ {s(x) = 0, R(x) = l}, and F i,j ⊂ {r(x) = 0, S(x) = (i, j)} such that sup(χ 0 θ) ⊂ ∪ l {x, dist(x, F l ) ≤ 4h} ∪ i,j {x, dist(x, F i,j ) ≤ 4h} .

  .50) Using Lemma 4.3 again, we get for |x 1y 1 | < βh γ h (x, y 1 ) = u∈G(ν,δ ′ ) du = C 0 > 0.(4.51)

  h→0 + h -2 g(h) = ν 1 (4.55)and the following estimate holds true for all integer n:sup x∈O N,ǫ T n h (x, dy) -dy vol(O N,ǫ ) T V ≤ C 4 e -ng(h) . (4.56)

  Spec(T h ) ⊂ [-1 + δ 0 , 1].(4.59)Thanks to the Markov property of T M h , to prove this, it suffices to find M ∈ 2N + 1 such thatO N,ǫ O N,ǫ (u(x) + u(y)) 2 T M h (x, dy)dx ≥ δ 0 u 2 L 2 , (4.60)for any u ∈ L 2 (Ω). Thanks to the proof of Proposition 4.4, there exists M ∈ 2N + 1 such thatO N,ǫ O N,ǫ (u(x) + u(y)) 2 T M h (x, dy)dx ≥ c 0 h -N d O N,ǫ ×O N,ǫ (u(x) + u(y)) 2 ϕ N d xy c 1 h dxdy.(4.61)Hence, (4.59) follows from (4.61) and (2.7). Following the strategy of Section 2 we put O N,ǫ in a large box B =] -A/2, A/2[ N d and, thanks to Proposition 4.1, there is an extension map E :L 2 (O N,ǫ ) → L 2 (B) which is also bounded from H 1 (O N,ǫ ) into H 1 (B). Define E h,k (u) = (1 -T k h )u, u L 2 (O N,ǫ ), (4.62)

Lemma 4. 9 .

 9 Let θ ∈ C ∞ (O N,ǫ ) be such that sup(θ) ∩ Γ sing = ∅ and ∂ n θ| Γreg = 0. Then(1 -T h )θ = h 2 |∆| N θ + r, r L 2 = O(h 5/2 ). (4.73) Proof. Let θ ∈ C ∞ (O N,ǫ ) be such that sup(θ) ∩ Γ sing = ∅ and ∂ n θ| Γreg = 0 and denote Q h = 1 -T h . Then Q h = 1 N N j=1 Q j,h with Q j,h θ(x) = h -d vol(B 1 ) Ω 1 |x j -y|<h Π k =j 1 |x k -y|>ǫ (θ(x)θ (π j (x) + σ j (y))) dy. (4.74) Let χ 0 (x) = 1 dist(x,∂O N,ǫ )<2h. The same proof as in Section 3 shows that(1χ 0 )Q j,h θ(x) = -α d 2 h 2 ∂ 2 j θ(x) + O L ∞ (h 3 ), (4.75) so that (1χ 0 )Q h θ(x) = h 2 |∆| N θ(x) + O L 2 (h 3 ). (4.76)We studyχ 0 Q h θ. As χ 0 L 2 = O(h 1/2 ) it suffices to show that χ 0 Q h θ L ∞ = O(h 2 ).On the other hand, by Taylor expansion we haveχ 0 Q j,h θ(x) = -hχ 0 (x) vol(B 1 ) |z|<1 Π k =j 1 |x j +hz-x k |>ǫ 1 x j +hz∈Ω z.∂ j θ(x)dz + O L ∞ (h 2 ).(4.77) Hence, it suffices to show that v(x) = χ 0 (x) N j=1 |z|<1

  If x ∈ sup(χ 0 θ) is in {x, dist(x, F 1 ) ≤ 4h}, then the same parity arguments as in Section 3 show that v(x) = χ 0 (x)|z|<1,x 1 +hz∈Ω z.∂ 1 θ(x)dz = O(h). (4.79) If x ∈ sup(χ 0 θ) is in {x, dist(x, F 1,2 ) ≤ 4h}, then v(x) = χ 0 (x) |z|<1 z.(∂ 1 θ(x)1 |x 1 +hz-x 2 |>ǫ + ∂ 2 θ(x)1 |x 2 +hz-x 1 |>ǫ )dz (4.80)and the result follows from (x 1x 2 ).(∂ 1 θ -∂ 2 θ)(x) = 0(h) for {x, dist(x, F 1,2 ) ≤ 4h}, since ∂ n θ vanishes on the boundary |x 1x 2 | = ǫ.The proof of Lemma 4.9 is complete.

  To state our theorem, we need a basic definition: Definition 2. Let Ω be a Lipschitz open set of R d . We say that ∂Ω is quasi-regular if ∂Ω = Γ reg ∪ Γ sing , Γ reg ∩ Γ sing = ∅ with Γ reg a finite union of smooth hypersurfaces, relatively open in ∂Ω, and Γ sing a closed subset of R d such that v ∈ H -1/2 (∂Ω) and sup(v) ⊂ Γ sing =⇒ v = 0. More generally, the boundary is quasi-regular if it is 'piece-wise smooth' in the following sense: suppose Ω is a Lipschitz open set of R d such that ∂Ω = Γ reg ∪ Γ sing , Γ reg ∩ Γ sing = ∅, where Γ reg is a smooth hypersurface of R d , relatively open in ∂Ω, and Γ sing a closed subset of R d such that Γ sing = ∪ j≥2 S j where the S j are smooth disjoint submanifolds

(1.16)

Observe that 1.16 is obviously satisfied if ∂Ω is smooth, since in that case one can take Γ sing = ∅.

  ,1 , ..., x 2,k-1 , x 2,k+1 , ..., x 2,d ). Lipschitz and β smooth. Then, ν(

	with α
	(4.26)

  .63)Proof. Thanks to Lemma 2.2 we haveE h (E(u)) ≤ C 0 O N,ǫ ×O N,ǫ (u(x)u(y)) 2 c 0 h -N d ϕ N d xy c 1 h dydx + h 2 u L 2 (O N,ǫ ) . (4.64)Combined with (4.32), this shows thatE h (E(u)) ≤ C 0 O N,ǫ ×O N,ǫ (u(x)u(y)) 2 T M h (x, dy)dx + h 2 u L 2 (O N,ǫ ) , (4.65)and the proof is complete.Lemma 4.8. For any 0 ≤ λ ≤ δ 0 /h 2 , the number of eigenvalues of T h in [1h 2 λ, 1] (with multiplicity) is bounded by C 1 (1+λ) N d/2 . Moreover, any eigenfunction T h (u) = λu with λ ∈]1-δ 0 , 1] satisfies the bound u L ∞ ≤ C 2 h -N d/2 u L 2 . (4.66)Proof. Suppose that T h (u) = λu with λ ∈ [1δ 0 , 1], then T M h u = λ M u and thanks to (4.32), we get(µ hλ M )u L ∞ = O(h -N d/2 ). (4.67)The estimate (4.66) follows from (4.57). Let ζ k (λ, h) be the number of eigenvalues of T k h in the interval [1h 2 λ, 1] for h 2 λ < δ 0 . Thanks to Lemma 4.7, we can mimick the proof of Lemma 2.3 to getζ M (λ, h) ≤ C(1 + λ) N d/2 .Combining (4.68) and (4.69), we easily obtain the announced estimate. The proof of Lemma 4.8 is complete.

				(4.68)
	Then from (4.59), one has
	ζ 1 (λ, h) = ζ k	1 -(1 -h 2 λ) k h 2	, h .	(4.69)

* Supported in part by the National Science Foundation, DMS 0505673. † Supported in part by ANR equa-disp Blan07-3-188618 § Supported in part by ANR equa-disp Blan07-3-188618