MOSER ITERATION FR ÉD Éric Bernicot

Thierry Coulhon
email: thierry.coulhon@univ-psl.fr

Dorothee Frey
email: dorothee.frey@anu.edu.au

Frédéric Bernicot
email: frederic.bernicot@univ-nantes.fr

GAUSSIAN HEAT KERNEL BOUNDS THROUGH ELLIPTIC

Keywords: . 1991 Mathematics Subject Classification. 58J35, 42B20 Heat kernel lower bounds, Hölder regularity of the heat semigroup, gradient estimates, Poincaré inequalities, De Giorgi property, Riesz transform

. This relies in particular on a new notion of L p Hölder regularity for a semigroup and on a characterization of (P 2 ) in terms of harmonic functions.

Contents

18 5. L p De Giorgi property and Caccioppoli inequality 25 6. L 2 Poincaré inequality through harmonic functions 29 Appendix A. From Poincaré to De Giorgi 32 Appendix B. A self-improving property for reverse Hölder inequalities 39 References 40

1. Introduction 1.1. The Dirichlet form setting. The reader who does not care about generality but is satisfied by a wide range of interesting examples can skip this section and in the rest of the paper think of M as a complete Riemannian manifold satisfying the volume doubling property and L its (nonnegative) Laplace-Beltrami operator. However, the more general setting we are about to present covers many more examples, see [START_REF] Gyrya | Neumann and Dirichlet heat kernels in inner uniform domains[END_REF].

Let M be a locally compact separable metrisable space equipped with a Borel measure µ, finite on compact sets and strictly positive on any non-empty open set.

For Ω a measurable subset of M , we shall often denote µ (Ω) by |Ω|.

Let L be a non-negative self-adjoint operator on L 2 (M, µ) with dense domain D ⊂ L 2 (M, µ). Denote by E the associated quadratic form

E(f, g) = M f Lg dµ,
for f, g ∈ D, and by F its domain, which contains D. Assume that E is a strongly local and regular Dirichlet form (see [START_REF] Fukushima | Dirichlet forms and symmetric Markov processes[END_REF][START_REF] Gyrya | Neumann and Dirichlet heat kernels in inner uniform domains[END_REF] for precise definitions). As a consequence, there exists an energy measure dΓ, that is a signed measure depending in a bilinear way on f, g ∈ F such that

E(f, g) = M dΓ(f, g)
for all f, g ∈ F. A possible definition of dΓ is through the formula

(1.1) ϕ dΓ(f, f ) = E(ϕf, f ) - 1 2 E(ϕ, f 2 ),
valid for f ∈ F ∩ L ∞ (M, µ) and ϕ ∈ F ∩ C 0 (M ). Here C 0 (M ) denotes the space of continuous functions on M that vanish at infinity. According to the Beurling-Deny-Le Jan formula, the energy measure satisfies a Leibniz rule, namely (1.2) dΓ(f g, h) = f dΓ(g, h) + gdΓ(f, h), for all f, g ∈ F ∩ L ∞ (M, µ) and h ∈ F, see [START_REF] Fukushima | Dirichlet forms and symmetric Markov processes[END_REF]Section 3.2]. One can define a pseudo-distance d associated with E by (1.3) d(x, y) := sup{f (x) -f (y); f ∈ F ∩ C 0 (M ) s.t. dΓ(f, f ) ≤ dµ}.

Throughout the whole paper, we assume that the pseudo-distance d separates points, is finite everywhere, continuous and defines the initial topology of M (see [START_REF] Sturm | Analysis on local Dirichlet spaces I. Recurrence, conservativeness and L p -Liouville property[END_REF] and [START_REF] Gyrya | Neumann and Dirichlet heat kernels in inner uniform domains[END_REF]Subsection 2.2.3] for details). When we are in the above situation, we shall say that (M, d, µ, E) is a metric measure (strongly local and regular) Dirichlet space. Note that this terminology is slightly abusive, in the sense that in the above presentation d follows from E.

For all x ∈ M and all r > 0, denote by B(x, r) the open ball for the metric d with centre x and radius r, and by V (x, r) its measure |B(x, r)|. For a ball B of radius r and λ > 0, denote by λB the ball concentric with B and with radius λr. We sometimes denote by r(B) the radius of the ball B. Finally, we will use u v to say that there exists a constant C (independent of the important parameters) such that u ≤ Cv and u v to say that u v and v u.

We shall assume that (M, d, µ) satisfies the volume doubling property, that is (VD) V (x, 2r) V (x, r), ∀ x ∈ M, r > 0.

It follows that there exists ν > 0 such that (VD ν ) V (x, r) r s ν V (x, s), ∀ x ∈ M, r ≥ s > 0, which implies V (x, r) d(x, y) + r s ν V (y, s), ∀ x, y ∈ M, r ≥ s > 0.

An easy consequence of (VD) is that balls with a non-empty intersection and comparable radii have comparable measures. We shall say that (M, d, µ, E) is a doubling metric measure Dirichlet space if it is a metric measure space endowed with a strongly local and regular Dirichlet form and satisfying (VD).

1.2. Heat kernel estimates. Let (M, d, µ, E) be a doubling metric measure Dirichlet space. The Dirichlet form E gives rise to a strongly continuous semigroup (e -tL ) t>0 of self-adjoint contractions on L 2 (M, µ). In addition (e -tL ) t>0 is submarkovian, that is 0 ≤ e -tL f ≤ 1 if 0 ≤ f ≤ 1. It follows that the semigroup (e -tL ) t>0 is uniformly bounded on L p (M, µ) for p ∈ [1, +∞]. Also, (e -tL ) t>0 is bounded analytic on L p (M, µ) for 1 < p < +∞ (see [START_REF] Stein | Topics in harmonic analysis related to the Littlewood-Paley theory[END_REF]), which means that (tLe -tL ) t>0 is bounded on L p (M, µ) uniformly in t > 0. Moreover, due to the doubling property (VD), the semigroup has the conservation property (see [START_REF] Grigor'yan | On stochastically complete manifolds[END_REF][START_REF] Sturm | Analysis on local Dirichlet spaces I. Recurrence, conservativeness and L p -Liouville property[END_REF]), that is e -tL 1 = 1, ∀ t > 0.

In particular, the above assumptions rule out the case of a non-empty boundary with Dirichlet boundary conditions, see the comments in [35, pp. 13-14].

Under our assumptions, according to [28, Theorems 7.2.1-7.2.2], e -tL has a kernel, that is for all t > 0 a measurable function p t : M × M → R + such that e -tL f (x) = M p t (x, y)f (y) dµ(y), a.e. x ∈ M.

We shall call p t the heat kernel associated with L (in fact with (M, d, µ, E)). Then p t (x, y) is nonnegative and symmetric in x, y since e -tL is positivity preserving and self-adjoint for all t > 0.

One may naturally ask for upper and lower estimates of p t (for upper estimates, see for instance the recent article [START_REF] Boutayeb | A new approach to pointwise heat kernel upper bounds on doubling metric measure spaces[END_REF] and the many relevant references therein; for lower estimates, we will give more references below). A typical upper estimate is (DUE) p t (x, y) 1

V (x, √ t)V (y, √ t)
, ∀ t > 0, a.e. x, y ∈ M.

This estimate is called on-diagonal because if p t happens to be continuous then (DUE) can be rewritten as

(1.4) p t (x, x) 1 V (x, √ t) , ∀ t > 0, ∀ x ∈ M.
Under (VD), (DUE) self-improves into a Gaussian upper estimate (see [33, Theorem 1.1] for the Riemannian case, [START_REF] Coulhon | Gaussian heat kernel bounds via Phragmén-Lindelöf theorem[END_REF]Section 4.2] for a metric measure space setting): (UE) p t (x, y) 1 V (x, √ t) exp -d 2 (x, y) Ct , ∀ t > 0, a.e. x, y ∈ M.

The proof of this fact in [START_REF] Coulhon | Gaussian heat kernel bounds via Phragmén-Lindelöf theorem[END_REF]Section 4.2] relies on the following Davies-Gaffney estimate which was proved in our setting in [START_REF] Sturm | Analysis on local Dirichlet spaces II. Upper Gaussian estimates for the fundamental solutions of parabolic equations[END_REF]: for all open subsets E, F ⊂ M , f ∈ L 2 (M, µ) supported in E, and t > 0, (1.5)

F |e -tL f | 2 dµ 1/2 ≤ e -d 2 (E,F ) 4t E |f | 2 dµ 1/2
, where d(E, F ) denotes the distance between E and F . For more on the Davies-Gaffney estimate, see for instance [START_REF] Coulhon | Gaussian heat kernel bounds via Phragmén-Lindelöf theorem[END_REF]Section 3].

It is well-known on the contrary that the matching Gaussian lower bound

(LE) p t (x, y) 1 V (x, √ t) exp - d 2 (x, y) ct , ∀ t > 0, a.e. x, y ∈ M
does not always follow from (DUE) (see [START_REF] Benjamini | Heat kernel lower bounds on Riemannian manifolds using the old ideas of Nash[END_REF]). Conversely, under (VD), (LE) implies (UE) (see [START_REF] Boutayeb | From lower to upper estimates of heat kernels in doubling spaces[END_REF]Theorem 1.3] and [START_REF] Coulhon | Geometric aspects of Nash and Gagliardo-Nirenberg inequalities[END_REF]).

It is not too difficult to prove in our situation that the conjunction of the upper and lower bounds (UE) and (LE) (that is, (VD) and (LE)) is equivalent to a uniform parabolic Harnack inequality, see [START_REF] Fabes | A new proof of Moser's parabolic Harnack inequality via the old ideas of Nash[END_REF] as well as [6, Section 1]. One also knows ( [START_REF] Gyrya | Neumann and Dirichlet heat kernels in inner uniform domains[END_REF]Theorem 2.32]) that this Harnack inequality self-improves into a Hölder regularity estimate for the heat kernel: there exists η ∈ (0, 1]

(H η ) |p t (x, z) -p t (y, z)| d(x, y) √ t η p t (x, z),
for all t > 0 and a.e. x, y, z ∈ M such that d(x, y) ≤ √ t. Note that, if (H η ) holds for some η ∈ (0, 1], p t admits in particular a continuous version.

What is also true, but much more difficult to prove (see [START_REF] Grigor'yan | The heat equation on non-compact Riemannian manifolds[END_REF], [START_REF] Saloff-Coste | A note on Poincaré, Sobolev, and Harnack inequalities[END_REF], [START_REF] Saloff-Coste | Uniformly elliptic operators on Riemannian manifolds[END_REF], [START_REF] Saloff-Coste | Parabolic Harnack inequality for divergence form second order differential operators[END_REF], [START_REF] Saloff-Coste | Aspects of Sobolev-type inequalities[END_REF], [START_REF] Sturm | Analysis on local Dirichlet spaces III. The parabolic Harnack inequality[END_REF], as well as [START_REF] Gyrya | Neumann and Dirichlet heat kernels in inner uniform domains[END_REF]Theorem 2.31]) is that (UE) + (LE) is also equivalent to (VD) together with the following scale-invariant Poincaré inequality (P 2 ):

(P 2 ) - B f -- B f dµ 2 dµ 1/2 r B dΓ(f, f ) 1/2
, for every f ∈ D and every ball B ⊂ M with radius r. Here -B f dµ = 1 |B| B f dµ denotes the average of f on B. A somewhat simplified proof of the main implication, namely the one from (VD) + (P 2 ) to (UE) + (LE), has been given in [START_REF] Hebisch | On the relation between elliptic and parabolic Harnack inequalities[END_REF]. One of the outcomes of the present article will be to provide a further simplification (see the proof of Theorem 4.3 below) as well as a short proof of the main result in [START_REF] Hebisch | On the relation between elliptic and parabolic Harnack inequalities[END_REF] (see Theorem 4.4 below).

1.3. L p Poincaré inequalities and gradient estimates. The above scale-invariant Poincaré inequality (P 2 ) quantifies the control of the oscillation of functions by the Dirichlet form. As it happens in many instances in analysis, it is important to have at hand a full scale of conditions for p ∈ [1, +∞], not just p = 2. This requires to have, beyond the notion of L 2 norm of the gradient provided by the Dirichlet form, a notion of L p norm of the gradient, hence a pointwise notion of length of the gradient.

The relevant notion in our general setting is the one of "carré du champ" (see for instance [START_REF] Gyrya | Neumann and Dirichlet heat kernels in inner uniform domains[END_REF] and the references therein). The Dirichlet form (or its energy measure) admits a "carré du champ" if for all f, g ∈ F the energy measure dΓ(f, g) is absolutely continuous with respect to µ. Then the density Υ(f, g) ∈ L 1 (M, µ) of dΓ(f, g) is called the "carré du champ" and satisfies the following inequality

(1.6) |Υ(f, g)| 2 ≤ Υ(f, f )Υ(g, g).
In the sequel, when we assume that (M, d, µ, E) admits a "carré du champ", we shall abusively denote [Υ(f, f )] 1/2 by |∇f |. This has the advantage to stick to the more intuitive and classical Riemannian notation, but one should not forget that one works in a much more general setting (see for instance [START_REF] Gyrya | Neumann and Dirichlet heat kernels in inner uniform domains[END_REF] for examples), and that one never uses differential calculus in the classical sense. We shall summarise this situation by saying that (M, d, µ, E) is a metric measure Dirichlet space with a "carré du champ".

We can now formulate the L p versions of the scale-invariant Poincaré inequalities, which may or may not be true and, contrary to the Hölder regularity conditions for the heat semigroup, do depend on p ∈ [1, +∞). More precisely, for p ∈ [1, +∞), one says that (P p ) holds if

(P p ) - B f -- B f dµ p dµ 1/p r - B |∇f | p dµ 1/p , ∀ f ∈ F,
where B ranges over balls in M of radius r. Recall that (P p ) is weaker and weaker as p increases, that is (P p ) implies (P q ) for q > p, see for instance [START_REF] Hajlasz | Sobolev met Poincaré[END_REF], and the p = ∞ version is trivial in the Riemannian setting (see however interesting developments for more general metric measure spaces in [START_REF] Durand-Cartagena | The ∞-Poincaré inequality in metric measure spaces[END_REF]). On the Euclidean space, (P p ) holds for all p ∈ [1, +∞]. On the connected sum of two copies of R n , (P p ) is valid if and only if p > n, as one can see by adapting the proof of [START_REF] Hajlasz | Sobolev met Poincaré[END_REF]Example 4.2]. More interesting examples follow from [START_REF] Heinonen | Quasiconformal maps in metric spaces with controlled geometry[END_REF]Theorem 6.15], see also [START_REF] Durand-Cartagena | Geometric characterisations of p-Poincaré inequalities in the metric setting[END_REF]Section 5]. On conical manifolds with compact basis, (P p ) holds at least for p ≥ 2 (see [START_REF] Coulhon | Estimations inférieures du noyau de la chaleur sur les variétés coniques et transformée de Riesz[END_REF]). A deep result from [START_REF] Keith | The Poincaré inequality is an open ended condition[END_REF] states if that (P p ) holds for some p ∈ (1, +∞), then (P p-ε ) holds for some ε > 0. Finally the set {p ∈ [1, +∞]; (P p ) holds on M } may be either {+∞}, or [1, +∞], or of the form (p M , +∞] for some p M > 1.

We will also consider estimates on the gradient (or "carré du champ") of the semigroup, which were introduced in [START_REF] Auscher | Riesz transform on manifolds and heat kernel regularity[END_REF], namely, for p ∈ [1, +∞],

(G p ) sup t>0 √ t|∇e -tL | p→p < +∞,
which is equivalent to the interpolation inequality

(1.7) |∇f | 2 p Lf p f p , ∀ f ∈ D
(see [START_REF] Coulhon | Riesz meets Sobolev[END_REF]Proposition 3.6]). As far as examples are concerned, (G ∞ ) holds on manifolds with non-negative Ricci curvature ( [START_REF] Li | On the parabolic kernel of the Schrödinger operator[END_REF]), Lie groups with polynomial volume growth ( [START_REF] Saloff-Coste | Analyse sur les groupes de Lie à croissance polynomiale[END_REF]), and co-compact covering manifolds with polynomial growth deck transformation group ( [START_REF] Dungey | Heat kernel estimates and Riesz transforms on some Riemannian covering manifolds[END_REF], [START_REF] Dungey | Some remarks on gradient estimates for heat kernels[END_REF]). On the other hand, conical manifolds with a compact basis provide a family of doubling spaces (M, d, µ, E) with a "carré du champ" satisfying (UE) and (LE) such that for every p 0 > 2 there exist examples in this family where (G p ) holds for 1 < p < p 0 and not for p ≥ p 0 , see [START_REF] Li | La transformation de Riesz sur les variétés coniques[END_REF], [START_REF] Li | Estimations du noyau de la chaleur sur les variétés coniques et ses applications[END_REF], [START_REF] Coulhon | Estimations inférieures du noyau de la chaleur sur les variétés coniques et transformée de Riesz[END_REF]. We are going to complete the picture for 2 < p < +∞ and by the same token simplify the proof of the case p = 2.

First, relying on a variant of the Davies-Gaffney estimate that holds in our setting, we will prove in Section 2 that for 2 ≤ p < +∞, the combination (G p ) + (P p ) implies the upper estimate (DUE) and therefore (UE).

Then, in Section 3, we shall study the transition from (UE) to (LE) in the spirit of [START_REF] Coulhon | Off-diagonal heat kernel lower bounds without Poincaré[END_REF] and [START_REF] Boutayeb | Heat kernel lower Gaussian estimates in the doubling setting without Poincaré inequality[END_REF]. The main novelty here will be a notion of L p η-Hölder regularity of the heat kernel: for p ∈ [1, +∞] and η ∈ (0, 1], we shall say that property (H η p,p ) holds if for every 0 < r ≤ √ t, every pair of concentric balls B r , B √ t with respective radii r and √ t, and every function f ∈ L p (M, µ),

(H η p,p ) - Br e -tL f -- Br e -tL f dµ p dµ 1/p r √ t η B √ t -1/p f p ,
with the obvious modification for p = +∞. Crucial to our approach is Theorem 3.4 below where we prove the equivalence, under (VD) and (UE), between the Gaussian lower bound (LE) and the existence of some p ∈ [1, +∞) and η > 0 such that (H η p,p ) holds, a property which turns out to be independent of p ∈ [1, +∞). As a consequence, we shall give a quick proof of the fact that under (VD ν ), (G p ) + (P p ) for p > ν implies (UE) + (LE), which had been proved in [START_REF] Coulhon | Off-diagonal heat kernel lower bounds without Poincaré[END_REF]Thm. 5.2] in the polynomial volume growth case. We also recover the main result of [START_REF] Boutayeb | Heat kernel lower Gaussian estimates in the doubling setting without Poincaré inequality[END_REF]. Later, we shall see that the limitation p > ν in the above implication is artificial. But the interest of this first approach is that it does not require any kind of Moser iteration.

In Section 4, we turn to the case p = 2. We give a simple proof of the implication from (VD) + (P 2 ) to (UE) + (LE); the only remaining non-trivial part is the implication from (VD) + (P 2 ) to the most classical De Giorgi property (DG 2 ), which is recalled in Appendix A. With similar arguments, we also obtain a new proof of the result from [START_REF] Hebisch | On the relation between elliptic and parabolic Harnack inequalities[END_REF] that the elliptic regularity together with a scale-invariant local Sobolev inequality imply the parabolic Harnack inequality (Theorem 4.4).

Section 5 is devoted to considerations on L p versions of De Giorgi property and Caccioppoli inequality, which may be of independent interest and are used anyway in the sequel.

Then Section 6 is devoted to the proof of Poincaré inequality (P 2 ) under (G p ) + (P p ) for any p ∈ (2, +∞). It relies on on Proposition 5.3 and on Appendix B where a self-improving property of reverse Hölder estimates is spelled out.

Sections 4 and 6 together yield the following statement, which summarises most of our results: Theorem 1.1. Let (M, d, µ, E) be a doubling metric measure Dirichlet space with a "carré du champ". Assume (G p 0 ) and (P p 0 ) for some p 0 ∈ [2, +∞). Then the heat kernel satisfies the two-sided Gaussian estimates (UE) and (LE).

One can also formulate the above result by saying that in our setting (G p 0 )+(P p 0 ) for p 0 > 2 implies (P 2 ). Finally (G p ) + (P p ) is stronger and stronger as p increases above 2. Theorem 1.1 can be combined with the main result in [START_REF] Auscher | Riesz transform on manifolds and heat kernel regularity[END_REF] and yield results on Riesz transforms.

Since our results avoid parabolic Moser iteration, which is very hard to run directly in a discrete time setting (see [START_REF] Delmotte | Parabolic Harnack inequality and estimates of Markov chains on graphs[END_REF]), they are well suited to an extension to random walks on discrete graphs. As a matter of fact, our Appendix A is inspired by [START_REF] Auscher | Riesz transform on manifolds and Poincaré inequalities[END_REF], but on the other hand our approach below gives a simpler proof of the main result in [START_REF] Auscher | Riesz transform on manifolds and Poincaré inequalities[END_REF] by avoiding the iteration step in [3, Proposition 4.5].

From Poincaré and gradient estimates to heat kernel upper bounds

In this section we shall need a version of the Davies-Gaffney estimate (1.5) which also includes the gradient, namely (2.1)

F |e -tL f | 2 dµ 1/2 + √ t F |∇e -tL f | 2 dµ 1/2 e -c d(E,F ) 2 t E |f | 2 dµ 1/2
, for some c > 0, all open subsets E, F ⊂ M , f ∈ L 2 (M, µ) supported in E, and t > 0, d(E, F ) being the distance between E and F . The proof of this fact in [4, Section 3.1] works in our setting of a Dirichlet space with a "carré du champ". Indeed, the proof relies on the following inequality: for ϕ a non-negative cut-off function with support S,

ϕ|∇e -tL f | 2 dµ ≤ |e -tL f | 2 |∇ϕ| 2 dµ 1/2 S |∇e -tL f | 2 dµ 1/2 (2.2) + ϕ|e -tL f ||Le -tL f |dµ,
which follows from (1.1), (1.2), and (1.6).

Proposition 2.1. Let (M, d, µ, E) be a metric measure Dirichlet space with a "carré du champ" satisfying (VD). Then the combination of (G p ) with (P p ) for some p ∈ [2, +∞) implies (UE).

Proof. Assume first 2 < p < +∞. From the self-improving property of (P p ) (see [START_REF] Keith | The Poincaré inequality is an open ended condition[END_REF]), there exists p ∈ (2, p) such that (P p) holds. Then, by interpolating between the L 2 Davies-Gaffney estimate for ∇e -tL contained in (2.1) and (G p ), one obtains that for t > 0 the operator √ t∇e -tL satisfies L p-L p off-diagonal estimates at the scale √ t. Similarly, by interpolating the uniform L ∞ boundedness with (2.1), one sees that the semigroup e -tL also satisfies such estimates. Namely, for some c > 0,

(2.3) √ t|∇e -tL | L p(B)→L p( B) + e -tL L p(B)→L p( B) exp -c d 2 (B, B) t ,
for every t > 0 and all balls B, B. On the other hand, the (P p) Poincaré inequality self-improves into a (P p,q ) inequality for some q > p (given by q -1 = p-1 -ν -1 if p < ν, q = +∞ if p < ν and any q > ν if p = ν, see [START_REF] Franchi | Self-improving properties of John-Nirenberg and Poincaré inequalities on space of homogeneous type[END_REF]). That is, for every ball B of radius √ t, one has

- B f -- B f dµ q dµ 1/q √ t - B |∇f | p dµ 1/p . Hence - B e -tL f -- B e -tL f dµ q dµ 1/q - B √ t∇e -tL f p dµ 1/p
, for all t > 0 and f ∈ L p(M, µ). It follows by Jensen's inequality that

- B e -tL f q dµ 1/q - B e -tL f p dµ 1/p + - B √ t∇e -tL f p dµ 1/p .
Then from (2.3), we deduce that for every pair of balls B, B of radius

√ t one has (2.4) e -tL L p(B)→L q ( B) exp -c d 2 (B, B) t | B| 1 q -1 p .
We now use [START_REF] Boutayeb | A new approach to pointwise heat kernel upper bounds on doubling metric measure spaces[END_REF], and refer to it for more details. Set V r (x) := V (x, r), and denote abusively by w the operator of multiplication by a function w. Using doubling, (2.4) may be written as

V 1 p -1 q √ t e -tL L p(B)→L q ( B) exp -c d 2 (B, B) t .
By the doubling property, we may sum this inequality over a covering of the whole space at the scale √ t and deduce (V E p,q ), which is

sup t>0 V 1 p -1 q √ t e -tL p→q < +∞.
By duality, one obtains (EV q ,p ), that is

sup t>0 e -tL V 1 p -1 q √ t q →p < +∞.
Then by interpolation [START_REF] Boutayeb | A new approach to pointwise heat kernel upper bounds on doubling metric measure spaces[END_REF]Proposition 2.1.5] between (V E p,q ) and (EV q ,p ), one obtains (V EV r,r , 1

r -1 2 ), that is sup t>0 V 1 r -1 2 √ t e -tL V 1 r -1 2 √ t r→r < +∞, where 1 ≤ r < 2 is given by 1 r = 1 2 ( 1 p + 1 q ) = 1 2 + ( 1 p -1 q )
. Then (EV r,2 ) holds by [START_REF] Boutayeb | A new approach to pointwise heat kernel upper bounds on doubling metric measure spaces[END_REF]Remark 2.1.3]. Thanks to the L 1 -uniform boundedness of the semigroup, the extrapolation [10, Proposition 4.1.9] yields (EV 1,2 ), hence (DUE) by [10, Proposition 2.1.2] and (UE) by [START_REF] Coulhon | Gaussian heat kernel bounds via Phragmén-Lindelöf theorem[END_REF]Section 4.2].

Finally, if p = 2, one can run the above proof by setting directly p = 2. Alternatively, one can see by [START_REF] Coulhon | Geometric aspects of Nash and Gagliardo-Nirenberg inequalities[END_REF]Section 5] that (P 2 ) and (VD) imply the so-called Nash inequality (N ) and apply [10, Theorem 1.2.1].

Remark 2.2. The case 1 ≤ p < 2 of Proposition 2.1 follows trivially from the case p = 2.

Remark 2.3. One may avoid the use of the highly non-trivial result from [START_REF] Keith | The Poincaré inequality is an open ended condition[END_REF] by assuming directly (G p ) and (P q ) for some q ∈ (2, p).

L p Hölder regularity of the heat semigroup and heat kernel lower bounds

The following statement is valid in a more general setting than the one presented in Section 1 and used in Section 2: it is enough to consider a metric measure space (M, d, µ) satisfying (V D), endowed with a semigroup (e -tL ) t>0 acting on L p (M, µ), 1 ≤ p ≤ +∞. For 1 ≤ p ≤ +∞ let us write the L p -oscillation for u ∈ L p loc (M, µ) and B a ball: (a) for all 0 < r ≤ √ t, every pair of concentric balls B r , B √ t with respective radii r and √ t, and every function f ∈ L p (M, µ),

p-Osc B (f ) := - B |f -- B f dµ| p dµ 1/p , if p < +∞ and ∞-Osc B (f ) := ess sup B |f -- B f dµ|.
(H η p,p ) p-Osc Br (e -tL f ) r √ t η B √ t -1/p f p .
(b) for all 0 < r ≤ √ t, every pair of concentric balls B r , B √ t with respective radii r and √ t, and every function f ∈ L p (M, µ),

(H η p,∞ ) ess sup x,y∈Br e -tL f (x) -e -tL f (y) r √ t η B √ t -1/p f p . Remark 3.2. It is easy to see that (H η p,∞
) is equivalent to the following condition, which justifies its name: for all 0 < r ≤ √ t, every pair of concentric balls B r , B √ t with respective radii r and √ t, and every function f ∈ L p (M, µ),

(3.1) ∞-Osc Br (e -tL f ) r √ t η B √ t -1/p f p .
Proposition 3.1 is an easy consequence of a well-known characterisation of Hölder continuous functions in terms of the growth of their L p oscillations on balls. This result is due to Meyers [START_REF] Meyers | Mean oscillation over cubes and Hölder continuity[END_REF] in the Euclidean space, and its proof was later simplified, see e.g. [START_REF] Giaquinta | Multiple integrals in the calculus of variations and nonlinear elliptic systems[END_REF]III.1]. It can be formulated in terms of embeddings of Morrey-Campanato spaces into Hölder spaces. The proof goes through in a doubling metric measure space setting (see [START_REF] Auscher | Gaussian lower bounds for random walks from elliptic regularity[END_REF]Proposition 2.6] for an L 2 version). We give a proof for the sake of completeness. Lemma 3.3. Let (M, d, µ) be a metric measure space satisfying (VD). Let 1 ≤ p < +∞ and η > 0. Then for every function f ∈ L p loc (M, µ) and every ball B in (M, d, µ),

f C η (B) := ess sup x,y∈B x =y |f (x) -f (y)| d η (x, y) f C η,p (B) := sup B⊂6B p-Osc B (f ) r η ( B) . Proof. Let x, y ∈ B be Lebesgue points for f . Let B i (x) = B(x, 2 -i d(x, y)), for i ∈ N. Note that for all i ∈ N, B i (x) ⊂ B 0 (x) ⊂ 3B. Write f (x) -- B 0 (x) f dµ ≤ i≥0 - B i (x)
f dµ --

B i+1 (x) f dµ ≤ i≥0 - B i+1 (x)
f --

B i (x) f dµ dµ ≤ i≥0 - B i+1 (x)
f --

B i (x) f dµ p dµ 1/p i≥0 p-Osc B i (x) (f ),
where the last inequality uses doubling. It follows that

f (x) -- B 0 (x) f dµ ≤ i≥0 [r (B i (x))] η f C η,p (B) = i≥0 2 -ηi d η (x, y) f C η,p (B) d η (x, y) f C η,p ( B) ,
as well as the similar estimate with the roles of x, y exchanged. Finally, since B 0 (y), B 0 (x) ⊂ 2B 0 (x) with comparable measures by doubling,

- B 0 (x) f dµ -- B 0 (y) f dµ ≤ - B 0 (x) f dµ -- 2B 0 (x) f dµ + - B 0 (y) f dµ -- 2B 0 (x) f dµ - 2B 0 (x) f -- 2B 0 (x) f dµ dµ ≤ - 2B 0 (x) f -- 2B 0 (x) f dµ p dµ 1/p = p-Osc 2B 0 (x) (f ), hence - B 0 (x) f dµ -- B 0 (y) f dµ ≤ d η (x, y) f C η,p ( B) .
The claim follows by writing

|f (x) -f (y)| ≤ f (x) -- B 0 (x) f dµ + - B 0 (x) f dµ -- B 0 (y) f dµ + f (y) -- B 0 (y) f dµ .
Proof of Proposition 3.1. The implication from (H η p,∞ ) to (H η p,p ) is obvious by integration. The case p = +∞ of the converse is similar to Remark 3.2.

Assume (H η p,p ) for 1 ≤ p < +∞. Let t > 0, and B r a ball of radius 0 < r ≤ √ t. From Lemma 3.3, we deduce that for f ∈ L p (M, µ), a.e. x, y ∈ B r ,

(3.2) |e -tL f (x) -e -tL f (y)| r η sup B⊂6Br p-Osc B (e -tL f ) r η ( B)
.

Now (H η p,p ) yields p-Osc B (e -tL f ) r η ( B) t -η/2 | B√ t | -1/p f p ,
• (LE) is equivalent to the existence of some p ∈ [1, +∞) and some η ∈ (0, 1]
such that (H η p,p ) holds; • The property "there exists η > 0 such that (H η p,p ) holds" is independent of p ∈ [1, +∞). One can in fact prove that the property (H η p,p ) itself is pindependent of p ∈ [1, +∞], up to an arbitrarily small loss on η. We will not pursue this here.

Proof of Theorem 3.4. First assume (H η p,p ) for some p ∈ [1, +∞] and some η > 0. By Proposition 3.1, we know that this estimate self-improves into (H η p,∞ ). Fix a point z ∈ M and consider the function f = p t (•, z). Then (H η p,∞ ) yields

|p 2t (x, z) -p 2t (y, z)| d(x, y) √ t η B √ t -
p t (•, z) p V (z, √ t) 1 p -1
and that

V -1 (z, √ t) p 2t (z, z).
For these two classical facts, see for instance [14, Theorem 3.1]. Hence

|p 2t (x, z) -p 2t (y, z)| d(x, y) √ t η V (z, √ t) B √ t 1/p V (z, √ t) -1 d(x, y) √ t η V (z, √ t) B √ t 1/p p 2t (z, z).
Note that this estimate is nothing but a slightly weaker form of the classical Hölder estimate (H η ) from the introduction.

In particular, for x = z and every y ∈ B(x, √ t) we deduce that

|p 2t (x, x) -p 2t (y, x)| d(x, y) √ t η p 2t (x, x). (3.5)
It is well-known that (LE) follows (see for instance [START_REF] Coulhon | Off-diagonal heat kernel lower bounds without Poincaré[END_REF]Theorem 3.1]).

Assume now (LE). Since we have assumed (UE), it follows, through the equivalence of (UE) + (LE) with the parabolic Harnack inequality (see [START_REF] Saloff-Coste | Parabolic Harnack inequality for divergence form second order differential operators[END_REF]Proposition 3.2] or [START_REF] Gyrya | Neumann and Dirichlet heat kernels in inner uniform domains[END_REF]), that there exist θ ∈ (0, 1) such that, for a.e.

x, y ∈ B r , 0 ≤ r < √ t, and a.e. z ∈ M

(3.6) |p t (x, z) -p t (y, z)| 1 V (z, √ t)V (x, √ t) r √ t θ (
this is yet another version of (H η )). On the other hand, (UE) and doubling imply that

(3.7) |p t (x, z) -p t (y, z)| p t (x, z) + p t (y, z) 1 V (x, √ t) exp -c d 2 (x, z) √ t . If d(x, z) ≤ √ t, V (z, √ t) V (x, √ t) B √ t and (3.6) yields |p t (x, z) -p t (y, z)| 1 B √ t r √ t θ .
If d(x, z) ≥ √ t, one multiplies the square roots of (3.6) and (3.7) to obtain

|p t (x, z) -p t (y, z)| 1 V 1/4 (z, √ t)V 3/4 (x, √ t) r √ t θ/2 exp -c d 2 (x, z) √ t = 1 V (x, √ t) r √ t θ/2 V (x, √ t) V (z, √ t) 1/4 exp -c d 2 (x, z) √ t 1 B √ t r √ t θ/2
, where the last inequality uses again doubling. Now we proceed as in [14, Theorem 3.1]. We have just shown that

p t (x, .) -p t (y, .) ∞ 1 B √ t r √ t θ/2
.

The heat semigroup being submarkovian,

p t (x, .) -p t (y, .) 1 ≤ 2.
It follows by Hölder inequality that for 1

≤ p < +∞ (3.8) p t (x, .) -p t (y, .) p B √ t -1/p r √ t θ/2p , for a.e. x, y ∈ B r , 0 ≤ r < √ t. Now |e -tL f (x) -e -tL f (y)| ≤ M |p t (x, z) -p t (y, z)||f (z)| dµ(z) ≤ p t (
p t (x, y) 1 V (x, t 1/m ) exp - d(x, y) m Ct 1/(m-1)
, ∀ t > 0, a.e. x, y ∈ M.

Then one can easily check that the above remains true by replacing everywhere the scaling factor √ t by t 1/m . One could also consider the more general heat kernel estimates from [37, Section 5], where the equivalence with matching Harnack inequalities is proved, see also [START_REF] Barlow | On the equivalence of parabolic Harnack inequalities and heat kernel estimates[END_REF].

An alternative proof of the second statement in Theorem 3.4 can be given using [9, Theorem 6] instead of Proposition 3.1. We leave the details to the reader. Conversely, a natural follow-up of the end of the proof of Theorem 3.4 is to get the results from [START_REF] Boutayeb | Heat kernel lower Gaussian estimates in the doubling setting without Poincaré inequality[END_REF], that is the extension of [START_REF] Coulhon | Off-diagonal heat kernel lower bounds without Poincaré[END_REF]Theorem 4.1] to the doubling setting. There is nothing essentially new here, but we shall give a proof of [START_REF] Boutayeb | Heat kernel lower Gaussian estimates in the doubling setting without Poincaré inequality[END_REF]Proposition 10] for the sake of completeness.

We first need to introduce the notion of reverse doubling. It is known (see [START_REF] Grigor'yan | Upper bounds of heat kernels on doubling spaces[END_REF]Proposition 5.2]), that, if M is unbounded, connected, and satisfies (VD ν ), one has a so-called reverse doubling volume property, namely there exist 0 < ν ≤ ν and c > 0 such that, for all r ≥ s > 0 and

x ∈ M c r s ν ≤ V (x, r) V (x, s) .
Let us say that (M, d, µ) satisfies (VD ν,ν ) if, for all r ≥ s > 0 and

x ∈ M , c r s ν ≤ V (x, r) V (x, s) ≤ C r s ν .
For the sake of simplicity we shall set ourselves in the Gaussian case (m = 2 in the notation of Remark 3.6), but the general case is similar.

Theorem 3.7. Let (M, d, µ, E) be a metric measure Dirichlet space satisfying (VD ν,ν ) and the upper Gaussian estimate (UE). Then (LE) holds if and only if, for some (all) p ∈ (1, +∞), some α > ν p and α > ν p ,

|f (x) -f (y)| 1 V 1/p (x, d(x, y)) d α (x, y) L α/2 f p + d α (x, y) L α /2 f p , ∀ f ∈ D, x, y ∈ M .
Proof. Assume (LE). Let 1 < p < +∞, α, α > 0 to be chosen later, and k ∈ N such that k > max α 2 , α 2 . Let f ∈ D. Thanks to (UE) and to the fact that by reverse doubling V (x, r) → +∞ as r → +∞, e -tL f → 0 in L 2 (M, µ), as t → +∞ (see [12, Section 3.1.2] for details). Since e -tL f is bounded in L 1 (M, µ), e -tL f → 0 in L p (M, µ) by duality and interpolation. Thus one can write

f = c(k) +∞ 0 t k-1 L k e -tL f dt, hence |f (x) -f (y)| ≤ c(k) +∞ 0 t k-1 |L k e -tL f (x) -L k e -tL f (y)| dt = c(k) +∞ 0 t k-1 |e -(t/2)L L k e -(t/2)L f (x) -e -(t/2)L L k e -(t/2)L f (y)| dt.
Now for r = d(x, y) and 0 < √ t ≤ r, we get from (3.4) and (VD ν )

|e

-(t/2)L L k e -(t/2)L f (x) -e -(t/2)L L k e -(t/2)L f (y)| ≤ p t (x, .) -p t (y, .) p L k e -(t/2)L f p ≤ ( p t (x, .) p + p t (y, .) p ) L k e -(t/2)L f p V (x, √ t) -1/p t -(k-α 2 ) L α/2 f p V (x, r) -1/p r √ t ν/p t -(k-α 2 ) L α/2 f p ,
where the last inequality uses the analyticity of (e -tL ) t>0 on L p (M, µ). For 0 ≤ r < √ t, we can write as in the end of the proof of Theorem 3.4,

|e -(t/2)L L k e -(t/2)L f (x) -e -(t/2)L L k e -(t/2)L f (y)| ≤ p t (x, .) -p t (y, .) p L k e -(t/2)L f p B √ t -1/p r √ t θ/2p t -(k-α 2 ) L α /2 f p .

Now reverse doubling yields

|e

-(t/2)L L k e -(t/2)L f (x) -e -(t/2)L L k e -(t/2)L f (y)| V (x, r) -1/p r √ t θ 2p + ν p t -(k-α 2 ) L α /2 f p . Finally |f (x) -f (y)| V (x, r) -1/p L α/2 f p r ν/p r 2 0 t k-1 t -ν 2p -k+ α 2 dt + V (x, r) -1/p L α /2 f p r θ 2p + ν p +∞ r 2 t k-1 t -θ 4p -ν 2p -k+ α 2 dt.
The above integrals converge if α > ν p and α < θ 2p + ν p , in which case one obtains

|f (x) -f (y)| V (x, r) -1/p r α L α/2 f p + r α L α /2 f p .
One can choose any α > ν p and some α > ν p . The converse is easy, see [9, Theorem 6]. In [START_REF] Coulhon | Off-diagonal heat kernel lower bounds without Poincaré[END_REF]Thm. 5.2], it is proved that if the volume growth is polynomial of exponent ν ≥ 2, then (R p ) and (P p ) for ν < p < +∞ imply (LE). Using the equivalence between (G p ) and (1.7), it is easy to see that the same proof works with (G p ) instead of (R p ). Our next theorem extends this result to the doubling case, and in addition its proof is more direct. Theorem 3.9. Let (M, d, µ, E) be a metric measure Dirichlet space with a "carré du champ" satisfying (VD ν ). Assume (G p ) and (P p ) for some p ∈ (ν, +∞). Then (LE) holds.

Proof. Replacing f with e -tL f in (P p ), we have, for every t > 0 and every ball B r of radius r > 0,

p-Osc Br (e -tL f ) r - Br |∇e -tL f | p dµ 1/p . If B √ t is concentric with B r and √ t ≥ r, - Br |∇e -tL f | p dµ 1/p B √ t |B r | 1/p - B √ t |∇e -tL f | p dµ 1/p , hence by (VD ν ) - Br |∇e -tL f | p dµ 1/p √ t r ν p B √ t -1/p |∇e -tL f | p √ t r ν p B √ t -1/p f p √ t ,
where the last inequality follows from (G p ). Gathering the two above estimates yields

p-Osc Br (e -tL f ) r √ t 1-ν p B √ t -1/p f p ,
that is (H η p,p ) with η = 1 -ν p ∈ (0, 1) since p > ν. By Proposition 2.1, (UE) also holds. We conclude by applying Theorem 3.4.

Remark 3.10. In the above statement, (P p ) is necessary, since (LE) implies (P 2 ), but (G p ) is not, as the example of conical manifolds shows (see [START_REF] Coulhon | Estimations inférieures du noyau de la chaleur sur les variétés coniques et transformée de Riesz[END_REF]).

Remark 3.11. For p = +∞, the above proof with the obvious modifications shows that (G ∞ ) together with (UE) implies (LE). This also follows from [17, Corollary 2.2] and the fact that (G ∞ ) and (UE) imply the matching pointwise estimate of the gradient of the heat kernel.

Let us give an alternative proof of Theorem 3.9, which is more direct, but does not shed the same light on the range 2 ≤ p ≤ ν (see Section 4 below) as the above one.

We shall start with a lemma which is close to [START_REF] Hajlasz | Sobolev met Poincaré[END_REF]Theorem 5.1] and to several statements in [START_REF] Coulhon | Espaces de Lipschitz et inégalités de Poincaré[END_REF] (for the polynomial volume growth case), but we find it useful to formulate and prove it in the following simple and natural way, which is in fact inspired by [START_REF] Hajlasz | Sobolev met Poincaré[END_REF]Theorem 3.2]. Lemma 3.12. Let (M, d, µ, E) be a metric measure Dirichlet space with a "carré du champ" satisfying (VD ν ). Then (P p ) for some p > ν implies the following Morrey inequality: for every function f ∈ D and almost every x, y ∈ M ,

(3.9) |f (x) -f (y)| d(x, y) V 1/p (x, d(x, y)) |∇f | p .
Proof. Let x, y be Lebesgue points for f . Let

B i (x) = B(x, 2 -i d(x, y)), for i ∈ N 0 .
As in Lemma 3.3, one has

f (x) -- B 0 (x) f dµ ≤ i≥0 p-Osc B i (x) (f ),
Then using (P p ) and (VD ν ) which yields |B 0 (x)| 2 iν |B i (x)|, we can write

f (x) -- B 0 (x) f dµ i≥0 2 -i d(x, y) - B i (x) |∇f | p dµ 1/p i≥0 2 -i d(x, y) 2 iν |B 0 (x)| 1/p B i (x) |∇f | p dµ 1/p i≥0 2 -i(1-ν p ) d(x, y)|B 0 (x)| -1/p |∇f | p d(x, y)|B 0 (x)| -1/p |∇f | p ,
where we used p > ν. Similarly we have

f (y) -- B 0 (y) f dµ d(x, y)|B 0 (y)| -1/p |∇f | p d(x, y)|B 0 (x)| -1/p |∇f | p ,
where |B 0 (x)| |B 0 (y)| follows from doubling. Finally, as in Lemma 3.3,

- B 0 (x) f dµ -- B 0 (y) f dµ ≤ - 2B 0 (x) f -- 2B 0 (x) f dµ p dµ 1/p
, and by (P p )

- B 0 (x) f dµ -- B 0 (y) f dµ d(x, y)|B 0 (x)| -1/p |∇f | p .
The claim follows.

We can now derive Theorem 3.9 easily. Replacing f with e -tL f in the conclusion of Lemma 3.12 and applying (G p ) yields

|e -tL f (x)-e -tL f (y)| d(x, y) V 1/p (x, d(x, y)) |∇e -tL f | p d(x, y) √ t [V (x, d(x, y))] -1/p f p , hence by (VD ν ) (3.10) |e -tL f (x) -e -tL f (y)| d(x, y) √ t 1-ν p |B √ t | -1/p f
|e -tL f (x) -e -tL f (y)| r √ t 1-ν p |B √ t | -1/p f p .
This is nothing but (H η p,∞ ) with η = 1 -ν p ∈ (0, 1), and we conclude by using (UE) as in the beginning of the proof of Theorem 3.4.

Poincaré inequalities and heat kernel bounds: the L 2 theory

The so-called De Giorgi property or Dirichlet property on the growth of the Dirichlet integral for harmonic functions was introduced by De Giorgi in [START_REF] Giorgi | Sulla differenziabilita de analiticita delle estremali degli integrali multipli regolari[END_REF], for L a second order divergence form differential operator with real coefficients on R n : there exists ε ∈ (0, 1) such that for all r ≤ R, every pair of concentric balls B r , B R with radii r, R and all functions u ∈ W 1,2 (R n ) harmonic in 2B R , i.e. Lu = 0 in 2B R , one has (4.1) -

Br |∇u| 2 dµ 1/2 R r ε - B R |∇u| 2 dµ 1/2
.

The De Giorgi property was subsequently used in many works and in various situations to prove Hölder regularity for solutions of inhomogeneous elliptic equations and systems (see for instance [START_REF] Giaquinta | Introduction to regularity theory for nonlinear elliptic systems[END_REF]).

The idea to look at the heat equation as a Laplace equation where the RHS is a time derivative, and to deduce parabolic regularity results from elliptic ones by using a non-homogeneous equivalent version of De Giorgi property was introduced in [START_REF] Auscher | Regularity theorems and heat kernel for elliptic operators[END_REF] for L a second order operator in divergence form on R n . In [START_REF] Auscher | Gaussian lower bounds for random walks from elliptic regularity[END_REF], the same ideas are applied in a discrete geometric setting, and the role of Poincaré inequalities clearly appears to ensure the elliptic regularity and the equivalence between the homogeneous and non-homogeneous versions of De Giorgi. This is the approach we will follow here, while taking full advantage of Theorem 3.4. We shall consider the following non-homogeneous version of De Giorgi property. With the help of Lemma 4.7 below, one shows that this formulation is a priori weaker than the one in [2, Proposition 4.4]. We shall see in the proof of Proposition 4.2 in Appendix A that under (UE) it is equivalent to (4.1). Definition 4.1 (De Giorgi property). Let (M, d, µ, E) be a metric measure Dirichlet space with a "carré du champ" and L the associated operator. We say that (DG 2,ε ) holds if the following is satisfied: for all r ≤ R, every pair of concentric balls B r , B R with respective radii r and R, and for every function f ∈ D, one has

(DG 2,ε ) - Br |∇f | 2 dµ 1/2 R r ε - B R |∇f | 2 dµ 1/2 + R Lf L ∞ (B R ) .
We sometimes omit the parameter ε, and write (DG 2 ) if (DG 2,ε ) is satisfied for some ε ∈ (0, 1).

Let us now state the counterpart of a result of [START_REF] Auscher | Gaussian lower bounds for random walks from elliptic regularity[END_REF] in the discrete setting. For the convenience of the reader, we give a proof in Appendix A. Proposition 4.2. Let (M, d, µ, E) be a doubling metric measure Dirichlet space with a "carré du champ". Then (P 2 ) implies (DG 2 ).

We are now in a position to give a simple proof of the main result of [START_REF] Grigor'yan | The heat equation on non-compact Riemannian manifolds[END_REF], [START_REF] Saloff-Coste | A note on Poincaré, Sobolev, and Harnack inequalities[END_REF], and [START_REF] Sturm | Analysis on local Dirichlet spaces III. The parabolic Harnack inequality[END_REF]. For simplicity let us denote in what follows, for B a ball and f ∈ L 2 loc (M, µ):

Osc B (f ) := 2-Osc B (f ) = - B |f -- B f dµ| 2 dµ 1/2 .
Theorem 4.3. Let (M, d, µ, E) be a doubling metric measure Dirichlet space with a "carré du champ". Then (P 2 ) implies (LE).

Proof. Applying (P 2 ) to e -tL f for t > 0 and f ∈ L 2 (M, µ) on a ball B r for r > 0 yields

(4.2) Osc Br (e -tL f ) r - Br |∇e -tL f | 2 dµ 1/2 .
According to Proposition 4.2, (DG 2,ε ) holds for some ε > 0, hence

- Br |∇e -tL f | 2 dµ 1/2 (4.3) √ t r ε   - B √ t |∇e -tL f | 2 dµ 1/2 + √ t ess sup x∈B √ t |Le -tL f (x)|   ≤ √ t r ε |B √ t | -1/2 |∇e -tL f | 2 + √ t ess sup x∈B √ t |Le -tL f (x)|
for some ε ∈ (0, 1), 0 < r ≤ √ t and B √ t with radius

√ t concentric to B r . By (G 2 ), (4.4
x∈2B √ t |tLe -tL f (x)| |B √ t | -1/2 f 2 .
Putting together (4.2), (4.3), (4.4) and (4.5) yields

Osc Br (e -tL f ) r √ t 1-ε |B √ t | -1/2 f 2 ,
that is, (H η 2,2 ) with η = 1 -ε > 0. This implies (LE) according to Theorem 3.4. The original proofs of Theorem 4.3 went through the parabolic Harnack inequality; some [START_REF] Saloff-Coste | A note on Poincaré, Sobolev, and Harnack inequalities[END_REF][START_REF] Saloff-Coste | Uniformly elliptic operators on Riemannian manifolds[END_REF][START_REF] Saloff-Coste | Parabolic Harnack inequality for divergence form second order differential operators[END_REF][START_REF] Saloff-Coste | Aspects of Sobolev-type inequalities[END_REF][START_REF] Sturm | Analysis on local Dirichlet spaces III. The parabolic Harnack inequality[END_REF]] used a parabolic Moser iteration, another one [START_REF] Grigor'yan | The heat equation on non-compact Riemannian manifolds[END_REF] tricky geometric arguments. In [37, Section 4.2], a shorter proof was given, which went in three steps (with a fourth one, borrowed from [START_REF] Fabes | A new proof of Moser's parabolic Harnack inequality via the old ideas of Nash[END_REF], to deduce parabolic Harnack from (LE)). The first one is to derive an elliptic regularity estimate from (VD) and (P 2 ). We do not change this step, which relies on the elliptic Moser iteration; we give a proof for the sake of completeness in Proposition A.4 below. The second step is to obtain (UE). Our approach in Proposition 2.1 is particularly simple since p = 2. The third step is a lower bound on the Dirichlet heat kernel inside a ball whose radius is the square root of the time under consideration. This is not trivial (see [37, pp. 1457-1462]) and here lies our main simplification. We first push step one a little further by deducing (DG 2 ) from the elliptic regularity. We could then deduce the parabolic regularity as in [2, Section 4]). Instead, we use the self-improvement of Hölder regularity estimates on the semigroup from Proposition 3.1 and Theorem 3.4.

Introduce the scale-invariant local Sobolev inequality

(LS q ) f 2 q 1 V 1-2 q (x, r) f 2 2 + r 2 E(f ) ,
for every ball B = B(x, r), every f ∈ F supported in B(x, r), and for some q > 2. This inequality was introduced in [START_REF] Saloff-Coste | A note on Poincaré, Sobolev, and Harnack inequalities[END_REF] and was shown, under (VD), to be equivalent to (DUE) in the Riemannian setting. The equivalence was stated in our more general setting in [START_REF] Sturm | Analysis on local Dirichlet spaces II. Upper Gaussian estimates for the fundamental solutions of parabolic equations[END_REF]. See also [START_REF] Boutayeb | A new approach to pointwise heat kernel upper bounds on doubling metric measure spaces[END_REF] for many reformulations of (LS q ), an alternative proof of the equivalence with (DUE), and more references.

The main aim of [START_REF] Hebisch | On the relation between elliptic and parabolic Harnack inequalities[END_REF] is to prove that the elliptic Harnack inequality, or an equivalent elliptic regularity estimate, together with (LS q ), or equivalently (UE), implies the parabolic Harnack inequality. It is enough in this respect to prove (LE), since as we already said the parabolic Harnack inequality follows from (UE) + (LE). This phenomenon falls in the circle of the ideas we are developing in the present work, and, using a transition trick from estimates for harmonic functions to estimates for all functions together with Theorem 3.4, we will now offer a simple proof of [START_REF] Hebisch | On the relation between elliptic and parabolic Harnack inequalities[END_REF]Theorem 3.1]. Let us say that u ∈ F is harmonic on a ball B if Lu = 0 in the weak sense on B. Note that the following statement involves diam(M ) as we want to treat by the same token the cases M bounded and unbounded. In a first reading one can certainly assume diam(M ) = +∞. Theorem 4.4. Let (M, d, µ, E) be a doubling metric measure Dirichlet space with a "carré du champ" satisfying (LS q ) for some q > 2. Assume that the following elliptic regularity estimate holds: there exists α > 0 and δ ∈ (0, 1) such that for every x 0 ∈ M , R > 0 with R < δ diam(M ), u ∈ F harmonic in B(x 0 , R) and x, y ∈ B(x 0 , R/2), one has

(ER) |u(x) -u(y)| d(x, y) R α Osc B(x 0 ,R) (u).
Then (LE) follows.

Remark 4.5. It is known that (P 2 ) implies (LS q ) for some q > 2, see for instance Before we start the proof of Theorem 4.4, recall that (LS q ) for some q > 2 implies the following relative Faber-Krahn inequality

(F K) Ω |f | 2 dµ 1/2 r |Ω| V (x, r) β Ω |∇f | 2 dµ 1/2
for some β > 0, all balls B(x, r), x ∈ M , r ∈ (0, δ diam(M )) with some δ < 1, and all f ∈ F supported in Ω ⊂ B(x, r). See for instance [START_REF] Hebisch | On the relation between elliptic and parabolic Harnack inequalities[END_REF]Theorem 2.5], as well as [START_REF] Boutayeb | A new approach to pointwise heat kernel upper bounds on doubling metric measure spaces[END_REF]Section 3.3].

In particular, one has (4.6)

B(x,r) |f | 2 dµ 1/2 r B(x,r) |∇f | 2 dµ 1/2
, for all balls B(x, r), x ∈ M , r ∈ (0, δ diam(M )) with some δ < 1, and all f ∈ F supported in B(x, r). We will need the following result inspired by [START_REF] Auscher | Gaussian lower bounds for random walks from elliptic regularity[END_REF]Lemma 4.2]. Note that the role classically played by ellipticity in such Lax-Milgram type arguments is played here by (4.6). Lemma 4.6. Let (M, d, µ, E) be a doubling metric measure Dirichlet space with a "carré du champ" satisfying (4.6). Let f ∈ D and consider an open ball B ⊂ M . Then, there exists u ∈ F such that f -u ∈ F is supported in the ball B and u is harmonic in B: for every φ ∈ F supported on B M dΓ(u, φ) = 0, where we recall that dΓ is the energy measure associated with the Dirichlet form E. Moreover, we have

(4.7) - B |∇(f -u)| 2 dµ 1/2 + - B |∇u| 2 dµ 1/2 - B |∇f | 2 dµ 1/2 .
Proof. Consider the space of functions

H := φ ∈ F ⊂ L 2 , supp(φ) ⊂ B .
Then, due to (4.6) the application

φ → φ H := |∇φ| L 2 (B)
defines a norm on H. Consequently, H equipped with this norm is a Hilbert space, with the scalar product

φ 1 , φ 2 H := B dΓ(φ 1 , φ 2 ). Since f ∈ D ⊂ F then the linear form φ → B dΓ(f, φ)
is continuous on H. By the Riesz representation theorem, there exists v ∈ H such that for every φ ∈ H

B dΓ(f, φ) = B dΓ(v, φ). We set u := f -v so that v = f -u being in H is supported in B.
Moreover for every φ ∈ H, φ is supported in B so the previous equality yields

M dΓ(u, φ) = M dΓ(f, φ) - M dΓ(v, φ) = 0.
Observe that since f -u is supported in B and u is harmonic on

B - B |∇(f -u)| 2 dµ = 1 |B| E(f -u, f -u) = 1 |B| M dΓ(f -u, f -u) = 1 |B| M dΓ(f, f -u).
Then by the locality property of the carré du champ and since f -u is supported in the ball B, we deduce that

- B |∇(f -u)| 2 dµ ≤ - B |∇f ||∇(f -u)| dµ ≤ - B |∇(f -u)| 2 dµ 1/2 - B |∇f | 2 dµ 1/2
.

So it follows that

- B |∇(f -u)| 2 dµ 1/2 - B |∇f | 2 dµ 1/2
which allows us to prove (4.7).

Proof of Theorem 4.4. Let u ∈ F be a function harmonic on a ball B R = B(x 0 , R) and write B r = B(x 0 , r) for r ≤ R with R ≤ δ diam(M ) (where we have chosen for δ the minimum of the two parameters in (F K) and (ER)). From (ER), it follows that

(4.8) Osc Br (u) r R α Osc B R (u).
Indeed, let 0 < r ≤ R/4. According to (ER), for every x ∈ B r ,

u(x) -- Br u(y) dµ(y) ≤ - Br |u(x) -u(y)| dµ(y) - Br d(x, y) R α dµ(y) Osc B R (u) r R α Osc B R (u).
Integrating over B r then gives

Osc Br (u) r R α Osc B R (u).
The case R/4 ≤ r ≤ R is trivial.

We will now extend this estimate to non-harmonic functions, namely prove that

(4.9) Osc Br (f ) r R α Osc B R (f ) + R r ν/2 R 2 - B R |Lf | 2 dµ 1/2
for all f ∈ D and concentric balls B r , B R with 0 < r ≤ R. Let f ∈ D. Since (F K) holds, one can invoke Lemma 4.6 below: there exists u ∈ F harmonic on B R such that f -u ∈ F is supported in the ball B R . One may write, using triangle inequality and (4.8),

Osc Br (f ) ≤ Osc Br (u) + Osc Br (f -u) r R α Osc B R (u) + Osc Br (f -u),
hence by triangle inequality again

(4.10) Osc Br (f ) ≤ r R α (Osc B R (f ) + Osc B R (f -u)) + Osc Br (f -u).
Let us start with estimating Osc B R (f -u):

Osc B R (f -u) - B R |f -u| 2 dµ 1/2
, and since f -u is supported in B R , by (F K) we have

- B R |f -u| 2 dµ 1/2 R - B R |∇(f -u)| 2 dµ 1/2 . Now, since f -u is supported on B R and u is harmonic on B R - B R |∇(f -u)| 2 dµ = 1 |B R | E(f -u, f -u) = 1 |B R | M dΓ(f -u, f -u) = 1 |B R | M dΓ(f, f -u) = 1 |B R | B R (f -u)Lf dµ ≤ 1 |B R | B R |f -u||Lf | dµ ≤ - B R |f -u| 2 1/2 - B R |Lf | 2 dµ 1/2 . From (F K), it follows that - B R |∇(f -u)| 2 dµ 1/2 R 1/2 - B R |∇(f -u)| 2 1/4 - B R |Lf | 2 dµ 1/4 , hence (4.11)
- B R |∇(f -u)| 2 dµ 1/2 R - B R |Lf | 2 dµ 1/2 .
Gathering the above inequalities yields (4.12)

Osc B R (f -u) - B R |f -u| 2 dµ 1/2 R 2 - B R |Lf | 2 dµ 1/2 . Now for Osc Br (f -u): by doubling Osc Br (f -u) - Br |f -u| 2 dµ 1/2 R r ν/2 - B R |f -u| 2 dµ 1/2
, therefore by (4.12)

(4.13) Osc Br (f -u) R r ν/2 R 2 - B R |Lf | 2 dµ 1/2 .
Finally, putting together (4.10), (4.12), (4.13),

Osc Br (f ) r R α Osc B R (f ) + r R α + R r ν/2 R 2 - B R |Lf | 2 dµ 1/2
, which yields (4.9). A standard iteration argument, Lemma 4.7 below, with

A(s) := s -1 Osc Bs (f ) and B(s) := - Bs |Lf | 2 dµ 1/2
, allows us to obtain for α ∈ (0, α)

Osc Br (f ) r R α Osc B R (f ) + R 2 Lf L ∞ (B R ) .
That holds for every r ≤ R with R ≤ δ diam(M ). Then if M is unbounded, we may choose R = √ t and replace f with e -tL f , which yields

Osc Br (e -tL f ) r √ t α Osc B √ t (e -tL f ) + tLe -tL f L ∞ (B √ t ) r √ t α |B √ t | -1/2 f 2 , (4.14)
where we used the Gaussian estimates for tLe -tL (see the proof of Theorem for all s, s such that r ≤ s ≤ s ≤ R and for some θ > 0. Let B : [r, R] → R + , and assume that

A(s) s s ε A(s ) + s s γ s B(s ), (4.16)
for every r ≤ s ≤ s ≤ R and for some ε ∈ (0, 1) and γ > 0. Then

A(r) R r ε A(R) + R sup r≤u≤R B(u) ,
for every ε ∈ (ε, 1).

Proof. Applying (4.16) with s and s = Ks gives, for some numerical constant C, A(s) ≤ CK ε A(Ks) + CK γ KsB(Ks).

We choose K > 1 large enough such that CK ε ≤ K ε for some fixed ε ∈ (ε, 1). It follows that, for r ≤ s < Ks ≤ R,

A(s) ≤ K ε A(Ks) + K γ+ε -ε+1 sB(Ks) ≤ K ε A(Ks) + K γ+2 s sup r≤u≤R B(u) .
By iterating for s = r, Kr, K 2 r, ..., K λ -1 r, where λ is such that K λ r = R, we deduce that

A(r) ≤K λ ε A(K λ r) +   λ -1 =0 (K r)K ε   K γ+2 sup r≤u≤R B(u) =K λ ε A(K λ r) +   λ -1 =0 K (1+ε )   rK γ+2 sup r≤u≤R B(u) K λ ε A(K λ r) + K λ (1+ε ) r sup r≤u≤R B(u) ≤K λ ε A(K λ r) + K λ r sup r≤u≤R B(u) ≤K λ ε A(K λ r) + R sup r≤u≤R B(u) .
The claim follows by using (4.15).

L p De Giorgi property and Caccioppoli inequality

We pursue the same ideas as in Section 4 but now for p > 2. To this end, we will rely on (G p ) and we will introduce L p versions, for p ∈ [1, +∞), of the De Giorgi property. Definition 5.1 (L p De Giorgi property). Let (M, d, µ, E) be a metric measure Dirichlet space with a "carré du champ" and L the associated operator. For p ∈ [1, +∞) and ε ∈ (0, 1), we say that (DG p,ε ) holds if the following is satisfied: for all r ≤ R, every pair of concentric balls B r , B R with respective radii r and R, and for every function f ∈ D, one has

(DG p,ε ) - Br |∇f | p dµ 1/p R r ε - B R |∇f | p dµ 1/p + R Lf L ∞ (B R ) .
We sometimes omit the parameter ε, and write (DG p ) if (DG p,ε ) is satisfied for some ε ∈ (0, 1).

Remark 5.2. For f ∈ D and 0 < r < R,

- Br |∇f | p dµ 1/p |B R | |B r | 1/p - B R |∇f | p dµ 1/p , hence if (VD ν ) holds, then - Br |∇f | p dµ 1/p R r ν/p - B R |∇f | p dµ 1/p .
Therefore if p > ν, one always has (DG p,ε ) with ε = ν p < 1. We have just seen that, for ν < p < +∞, (DG p ) is a trivial consequence of (VD ν ), and Proposition 4.2 states that (DG 2 ) follows from (VD) and (P 2 ). In the range 2 < p ≤ ν, property (DG p ) is more mysterious. The main result of this section is that, under (P 2 ) and (G p ) then (DG q ) holds for 2 ≤ q < p. In the L 2 situation, (DG 2 ) is obtained from (P 2 ) (as detailed in the Appendix A) through an extensive use of L 2 -Caccioppoli inequality for subharmonic functions. Although this L 2 inequality is relatively easy, its L p version is unknown (we will prove it only for harmonic functions) and so it is not clear how directly prove (DG p ) for some p > 2. Beyond the fact that Proposition 5.4 will play a crucial role in Section 6, we feel that these questions are interesting. Proposition 5.3. Let (M, d, µ, E) be a doubling metric measure Dirichlet space with a "carré du champ". Assume (P 2 ) and (G p ) for some p ∈ (2, +∞). Then (DG q ) holds for every q ∈ [2, p].

The proof of Proposition 5.3 will make use of an L p version of the Caccioppoli inequality. For p = 2, integration by parts yields easily a L 2 -Caccioppoli inequality (see for instance Lemma A.1) which enables one to deduce (DG 2 ) from (P 2 ) (Proposition 4.2). But obtaining an L p -Caccioppoli inequality for p > 2 seems more difficult and cannot be handled using integration by parts directly. We use (G p ) and the finite propagation speed property instead, and obtain: Proposition 5.4 (L p Caccioppoli inequality). Let (M, d, µ, E) be a doubling metric measure Dirichlet space with a "carré du champ" satisfying (UE). Assume (G p ) for some p ∈ [2, +∞]. Then for every q ∈ (1, p],

(5.1) r -

Br |∇f | q dµ 1/q - 2Br |f | q dµ 1/q + r 2 - 2Br |Lf | q dµ 1/q
for all f ∈ D and all balls B r of radius r.

Note that it would be easier, and sufficient for our purposes in this section, to prove only a non-local version of the above inequality:

r - B |∇f | q dµ 1/q ≥0 2 -N - 2 B |f | q dµ 1/q + r 2 - 2 B |Lf | q dµ 1/q .
We feel anyway that (5.1) may be of independent interest, and that it is worth the extra effort, namely the use of the finite propagation speed property. Since the heat semigroup satisfies Davies-Gaffney estimates (2.1), it is known (see e.g. [START_REF] Sturm | Analysis on local Dirichlet spaces II. Upper Gaussian estimates for the fundamental solutions of parabolic equations[END_REF], [START_REF] Sikora | Riesz transform, Gaussian bounds and the method of wave equation[END_REF] and [START_REF] Coulhon | Gaussian heat kernel bounds via Phragmén-Lindelöf theorem[END_REF]Section 3]) that √ L satisfies the finite speed propagation property (with a speed equal to 1 due to the normalization in (1.3)) for solutions of the corresponding wave equation. Consequently for every even function ϕ ∈ S(R) with supp φ ⊆ [-1, 1], every pair of Borel sets E, F ⊂ M and every r > 0, one has

1 E ϕ(r √ L)1 F = 0 if dist(E, F ) > r.
This follows from the Fourier inversion formula and the bounded Borel functional calculus of √ L, cf. [START_REF] Auscher | Calderón reproducing formulas and applications to Hardy spaces[END_REF]Lemma 4.4]. Moreover, since the Dirichlet form is strongly local, one also has

1 E |∇ϕ(r √ L)1 F | 2 = 0 if dist(E, F ) > r.
f = ϕ(r √ L)f + (I -ϕ(r √ L))f.
Since ϕ(0) = 1, one has

I -ϕ(r √ L) = r 0 √ Lϕ (s √ L) ds.
Using the finite propagation speed property applied to the functions ϕ and x → x -1 ϕ (x), we have that both ϕ(r √ L) and (r 2 L) -1 (1 -ϕ(r √ L)) satisfy the propagation property at speed 1 and so propagate at a distance at most r. As we have seen above, the same stills holds by composing with the gradient. Hence, for f ∈ D,

|∇f | L q (Br) |∇ϕ(r √ L)| q→q f L q (2Br) (5.2) + r 2 |∇(1 -ϕ(r √ L))(r 2 L) -1 | q→q Lf L q (2Br) .
Let us now estimate |∇ϕ(r √ L)| q→q and |∇(1-ϕ(r √ L))(r 2 L) -1 | q→q . For q > 2, (G q ) holds by interpolation between (G 2 ) and (G p ), and for q < 2, (G q ) always holds as we already said. By writing the resolvent via the Laplace transform as (1 + r 2 L) -1 = +∞ 0 e -t(1+r 2 L) dt, we deduce gradient bounds for the resolvent in L q , that is

|∇(1 + r 2 L) -1 | q→q +∞ 0 e -t |∇e -tr 2 L | q→q dt +∞ 0 e -t r √ t dt r -1 .
Denote ψ := ϕ or ψ := x → (1 -ϕ(x))/x 2 , and consider λ(x) = ψ(x)(1 + x 2 ). Hence ψ(r

√ L) = (1 + r 2 L) -1 λ(r √ L) and therefore |∇ψ(r √ L)| q→q ≤ |∇(1 + r 2 L) -1 | q→q λ(r √ L) q→q r -1 λ(r √ L) q→q .
Observe that λ ∈ S(R) since ϕ(0) = 1 and ϕ (0) = 0. By a functional calculus result (see e.g. [START_REF] Duong | Plancherel-type estimates and sharp spectral multipliers[END_REF], Theorem 3.1) which relies on (UE), we then have Coming back to (5.2), we obtain

|∇f | L q (Br) r -1 f L q (2Br) + r Lf L q (2Br) ,
which is the claim.

We are now ready to prove Proposition 5.3. To pass from (DG 2 ) to (DG q ) for 2 < q ≤ p we shall use Hölder estimates as in [START_REF] Hofmann | The Green function estimates for strongly elliptic systems of second order[END_REF]Lemma 2.3].

Proof of Proposition 5.3. Let B R denote a ball of radius R > 0, and let f ∈ F. Using Lemma 3.3 for p = 2 and (P 2 ), we can write

(5.3) f C η (B R ) f C η,2 (B R ) sup B⊂6B R r( B) 1-η - B |∇f | 2 dµ 1/2 .
for any η ∈ (0, 1). Now according to Proposition 4.2, (P 2 ) yields (DG 2,ε ) for some ε ∈ (0, 1). Choose η = 1 -ε. Then it follows from (5.3) together with (DG 2,ε ) that

f C 1-ε,2 (B R ) sup B⊂6B R r ε ( B) - B |∇f | 2 dµ 1/2 R ε - 24B R |∇f | 2 dµ 1/2 + R ess sup x∈24B R |Lf (x)| .
We then apply Jensen's inequality and obtain for q ≥ 2 (5.4)

f C 1-ε (B R ) R ε - 24B R |∇f | q dµ 1 q + R ess sup x∈24B R |Lf (x)| .
We now deduce (DG q ) for 2 < q ≤ p from (5.4) and (G p ). By (G p ) and Proposition 5.4 one has (5.1) for 2 < q ≤ p. Replacing f with f --Br f dµ in (5.1) yields (5.5) -

Br |∇f | q dµ 1/q r -1 - 2Br |f -- Br f dµ| q dµ 1/q + r - 2Br |Lf | q dµ 1/q .
for every ball B r with radius r > 0 and B r ⊂ B R . Now we can write

- 2Br |f -- Br f dµ| q dµ 1/q ≤ ess sup x,y∈2Br |f (x) -f (y)| ≤ r 1-ε f C 1-ε (B 2r ) ≤ r 1-ε f C 1-ε (B 2R )
and (5.4) yields

- 2Br |f -- Br f dµ| q dµ 1/q r 1-ε R ε - 48B R |∇f | q dµ 1/q + R ess sup x∈48B R |Lf (x)| . Consequently - Br |∇f | q dµ 1/q R r ε - 48B R |∇f | q dµ 1/q + R ess sup x∈48B R |Lf (x)| +r - 2Br |Lf | q dµ 1/q R r ε - 48B R |∇f | q dµ 1/q + R ess sup x∈48B R |Lf (x)| ,
which gives easily (DG q,ε ).

Let us finish this section by noting a consequence of [3, Theorem 0.4] and Proposition 5.3 on the De Giorgi property.

Corollary 5.5. Let (M, d, µ, E) be a doubling metric measure Dirichlet space with a "carré du champ" satisfying (P 2 ). Then there exists ε > 0 such that (DG p ) holds for every p ∈ [2, 2 + ε). . Since (4.6) holds, one can invoke Lemma 4.6: there exists u ∈ F harmonic on 4B such that f -u ∈ F is supported in the ball 4B. One may write, using the triangle inequality,

Osc B (f ) ≤ Osc B (u) + Osc B (f -u).
Using the assumption for u, we have

Osc B (u) r - B |∇u| 2 dµ 1/2 r - B |∇(f -u)| 2 dµ 1/2 + r - B |∇f | 2 dµ 1/2 . Moreover, since f -u is supported on 4B, then by (4.6), Osc B (f -u) - 4B |f -u| 2 dµ 1/2 r - 4B |∇(f -u)| 2 dµ 1/2 .
As a consequence, it follows that (6.1)

Osc B (f ) r - 4B |∇(f -u)| 2 dµ 1/2 + r - B |∇f | 2 dµ 1/2 .
Finally, by combining (4.7) and (6.1), we deduce that

Osc B (f ) r - 4B |∇f | 2 dµ 1/2
, which is the claim.

Let us recall the following equivalence between weak and strong Poincaré inequalities (combining [36, Theorem 3.1] and [START_REF] Keith | The Poincaré inequality is an open ended condition[END_REF]). Theorem 6.2. Let (M, d, µ, E) be a doubling metric measure Dirichlet space with a "carré du champ". Let p ∈ (1, ∞), and let f ∈ D. The (strong) L p Poincaré inequality (P p ) for f is equivalent to the weak version: there exists λ > 1 such that

(w-P p ) - B f -- B f dµ p dµ 1/p r - λB |∇f | p dµ 1/p
, where B ranges over balls in M of radius r.

We then state the following main result of this section: Theorem 6.3. Let (M, d, µ, E) be a doubling metric measure Dirichlet space with a "carré du champ". For every p > 2, the combination (G p ) with (P p ) yields (P 2 ), therefore the heat semigroup satisfies the two-sided Gaussian estimates (UE) and (LE).

Note that the last statement relies on the theorem of Saloff-Coste of which we have given a simplified version in Section 4.

Before proving the theorem, we need the following proposition, which relies on the self-improving property of reverse Hölder inequalities from Theorem B.1. Proposition 6.4. Let (M, d, µ, E) be a doubling metric measure Dirichlet space with a "carré du champ". Assume that for some p 0 ∈ (2, ∞), (P p 0 ) and (G p 0 ) hold. Then for every function f ∈ D and every ball B of radius r > 0, we have

- Br |f -- Br f dµ| 2 dµ 1/2 r - 2Br |∇f | 2 dµ 1/2 + r 2 Lf L ∞ (4Br) .
Let us first recall the following folklore result (see for instance [36, Theorem 5.1, 1.], [START_REF] Franchi | Self-improving properties of John-Nirenberg and Poincaré inequalities on space of homogeneous type[END_REF]Theorem 2.7] for similar statements). Lemma 6.5. Let (M, d, µ, E) be a doubling metric measure Dirichlet space with a "carré du champ". Assume that (P p ) holds for some 1 ≤ p < +∞. Then if q ∈ (p, +∞) is such that ν 1 p -1 q ≤ 1, the following Sobolev-Poincaré inequality holds:

(P p,q ) - Br f -- Br f dµ q dµ 1/q r - Br |∇f | p dµ 1/p
, for all f ∈ F, r > 0, and all balls B r with radius r.

Proof. This result is well-known if 1 < p < ν (see [36, for every ball B r of radius r and every f ∈ D. From [START_REF] Keith | The Poincaré inequality is an open ended condition[END_REF] we know that (P p 0 ) selfimproves into (P p 0 -ε ) for some ε > 0. Then , according to Lemma 6.5, if ε is small enough, (P p 0 -ε ) self-improves again into the Sobolev-Poincaré inequality (P p 0 ,p 0 -ε ) which yields

p 0 -Osc 2Br (f ) r - 2Br |∇f | p 0 -ε dµ 1/(p 0 -ε)
.

We therefore have First, the relative Faber-Krahn inequality (F K) (see Section 4 for a definition) implies an L 2 mean value property for harmonic functions.

Proposition A.2. Let (M, d, µ, E) be a doubling metric measure Dirichlet space with a "carré du champ" satisfying (UE). Assume (F K). Then one has, for all R > 0, x 0 ∈ M , and u ∈ F harmonic in B(x 0 , R), Consider ρ < r ≤ 2ρ with r ≤ R. Let χ be a Lipschitz function supported on B(x 0 , r), that equals 1 on B(x 0 , ρ) and such that ∇χ ∞ (r -ρ) -1 . Applying (F K) to χ(u -h) + (which is supported on B(x 0 , r)) for h ∈ R gives B(x 0 ,ρ) (u -h) 2 + dµ ≤ χ 2 (u -h) 2 + dµ r 2 a(h, r) V (x 0 , r)

2β B(x 0 ,r) |∇(u -h) + | 2 dµ + 1 (r -ρ) 2 B(x 0 ,r) (u -h) 2 + dµ ,
where we use the Leibniz rule for the gradient. Then, since u-h is harmonic, that is L(u -h) = 0 in B(x 0 , R), by [57, Lemma 2] we deduce that (u -h) + is nonnegative and subharmonic, that is L(u -h) + ≤ 0, in B(x 0 , R). So (u -h) + L(u -h) + ≤ 0 in B(x 0 , R). We then deduce from (A.1) that B(x 0 ,ρ) (u -h) 2 + dµ r 2 (r -ρ) 2 V (x 0 , r) -2β a(h, r) 2β B(x 0 ,r) (u -h) 2 + dµ ρ 2 (r -ρ) 2 V (x 0 , ρ) -2β a(h, r) 2β B(x 0 ,r) As we already observed at the beginning of the proof of Proposition A.2 in a similar situation, (u -k) + is subharmonic, therefore (A.1) yields

B(x 0 ,R/2) |∇(u -k) + | 2 dµ R -2 B(x 0 ,R) (u -k) 2 + dµ R -2 V (x 0 , R)(M (R) -k) 2 .
Thus (h -k) 2-ε a(h, R/2) V (x 0 , R) .

Since k i -k i-1 = M (R)-k 0 2 i
and M (R) -k i-1 = M (R)-k 0 2 i-1 , the above inequality yields a(k i , R/2)

2 ε V (x 0 , R) 2-ε ε (a(k i-1 , R/2) -a(k i , R/2)).
Using the fact that a(k i , R/2) is non-increasing in i, one obtains ia(k i , R/2)

2 ε ≤ i j=1 a(k j , R/2) 2 ε V (x 0 , R) 2-ε ε (a(k 0 , R/2) -a(k i , R/2)) ≤ V (x 0 , R) 2-ε ε a(k 0 , R/2).
Hence a(k i , R/2) V (x 0 , R) i -1 a(k 0 , R/2) V (x 0 , R)

ε 2 ≤ i -1 2 ε 2
.

We are now in a position to deduce the elliptic regularity estimate (ER) introduced in Theorem 4.4 from (P 2 ).

Proposition A.4. Let (M, d, µ, E) be a doubling metric measure Dirichlet space with a "carré du champ" satisfying (P 2 ). Then (ER) holds.

Proof. Recall first that (F K) holds according to Remark 4.5. Fix x 0 ∈ M , R > 0, and let u ∈ F be harmonic in B(x 0 , R). Let r ∈ (0, R/2]. By applying Proposition A.2 to u -K for any K ≤ M (2R), one obtains (A.6) M (R/2) -K (M (2R) -K) a(K, R) V (x 0 , R)

1/2 .
According to (A.6) applied in B(x 0 , r) with K = k i := k i (2r) = M (2r)-M (2r)-m(2r)

2 i+1
, there exists a constant C, independent of the main parameters, such that M (r/2) ≤ k i (2r) + C(M (2r) -k i (2r))

a(k i , r) V (x 0 , r)

1/2
.

Assume that a(k 0 , r) ≤ 1 2 V (x 0 , r), otherwise work with -u. Since (P 2 ) implies ( P 2-ε ) as we already pointed out, we can apply Lemma A.3. This yields a(k i , r) V (x 0 , r) ≤ Ci -ε/2 , therefore one can choose i large enough so that C a(k i , r) V (x 0 , r) We can now prove Proposition 4.2. This will be done in two steps: first (ER) yields a De Giorgi property for harmonic functions similar to (4.1). Second one derives the full (DG 2 ) by classical L 2 techniques.

Proposition 3 . 1 .

 31 Let (M, d, µ, L) as above. Let p ∈ [1, +∞] and η ∈ (0, 1]. Then the following two conditions are equivalent:

Remark 3 . 8 .

 38 One can take α = α if ν = ν , recovering in particular the polynomial volume growth case from [14, Theorem 4.1].

[ 51 ,

 51 Theorem 2.1], [18, Section 5]. We shall also see in Proposition A.4 below that (P 2 ) implies (ER). Thus Theorem 4.4 gives back Theorem 4.3.

Lemma 4 . 7 .

 47 Let 0 < r < R and consider a function A : [r, R] → R + such that

  Indeed, for every nonnegative, bounded and Lipschitz function χ E supported in E and g ∈ D supported in F , it follows from (1.1), (1.2), and (1.6) that M dµ.If d(E, F ) > √ r then ϕ(r √ L)g = 0 in the support of χ E , so χ E |∇ϕ(r √ L)g| 2 dµ = 0.This holds for every nonnegative, bounded Lipschitz function χ E supported in E, hence E |∇ϕ(r √ L)g| 2 dµ = 0. Proof of Proposition 5.4. Consider an even function ϕ ∈ S(R) with supp φ ⊆ [-1, 1] and ϕ(0) = 1. Consequently, ϕ (0) = 0, and x → x -1 ϕ (x) ∈ S(R) is even with Fourier support in [-1, 1], cf. [5, Lemma 6.1]. Fix a ball B r of radius r > 0, an exponent q ∈ (1, p] and split

  q→q r -1 .

6. L 2

 2 Poincaré inequality through harmonic functions Theorem 6.1. Let (M, d, µ, E) be a doubling metric measure Dirichlet space with a "carré du champ" satisfying (4.6). Suppose that every ball B of radius r > 0 and every function u ∈ D harmonic on 4B. Then ball B of radius r > 0 and every function f ∈ D. Proof. Let f ∈ D and B be a ball of radius r > 0. Recall that we denote the L 2 -oscillation of f over B by Osc B (f ) = -

.. 2 + r 2 -|Lf | p 0 dµ 1 /p 0 .

 2210 Let us apply Theorem B.1 to the functionala(B) := r -2B |Lf | p 0 dµ 1/p 0 ,which is regular, uniformly with respect to f . This gives -Using Hölder's inequality and (P p 0 ), we deduce that -4Br Bounding the last term by r 2 Lf L ∞ (4Br) then gives the desired estimate.We may now prove Theorem 6.3: where one uses (1.1). Consequently, by (1.2) and (1.6),

2 .

 2 Proof. Let x 0 ∈ M , R > 0 and u ∈ F such that Lu = 0 in B(x 0 , R). For h, r > 0 define M (r) = max x∈B(x 0 ,r) u(x), m(r) = min x∈B(x 0 ,r) u(x),A(h, r) = {x ∈ B(x 0 , r); u(x) ≥ h}, a(h, r) = µ(A(h, r)).

  (u -h)2 + dµ,where we used the doubling property and ρ r. Setu(h, ρ) = B(x 0 ,ρ) (u -h) 2 + dµ = A(h,ρ) (u -h) 2 dµ.The Poincaré inequality ( P 2-ε ) therefore yieldsB(x 0 ,R/2) |v| 2-ε dµ R 2-ε B(x 0 ,R/2) |∇v| 2-ε dµ. Hence (h -k) 2-ε a(h, R/2) R 2-ε B(x 0 ,R/2) |∇v| 2-ε dµ. Now (h -k) 2-ε a(h, R/2) R 2-ε A(k,R/2)\A(h,R/2) |∇u| 2-ε dµ.By Hölder,(h -k) 2-ε a(h, R/2) R 2-ε (a(k, R/2) -a(h, R/2)) ε/2 A(k,R/2)\A(h,R/2) ,R/2)\A(h,R/2) |∇u| 2 dµ ≤ A(k,R/2) |∇u| 2 dµ = B(x 0 ,R/2)|∇(u -k) + | 2 dµ.

2 -ε 2 (

 22 M (R) -k) 2-ε (a(k, R/2) -a(h, R/2)) ε 2

M

  (r/2) ≤ M (2r) -1 2 i+2 (M (2r) -m(2r)), hence M (r/2) -m(r/2) ≤ (M (2r) -m(2r)) 1 -1 2 i+2 . Set ω(r) = M (r) -m(r). One has ω(r/2) ≤ ηω(2r), ∀r ∈ (0, R/2],where η = 1 -1 2 i+2 ∈ (0, 1). It follows that there exist C, α > 0 such that ω(ρ) , y ∈ B(x 0 , R/2).Now, it follows easily from PropositionA.2 that max B(x 0 ,R/2)|u| 2-Osc B(x 0 ,R) (u), hence the claim.

  Remark 3.5. Let us emphasise two by-products of Theorem 3.4:

		t | are
	comparable, hence
	(3.3)	sup

where B√ t is the ball concentric to B with radius √ t. The balls B√ t and B √ t have the same radius and, if B ⊂ 6B r , it follows by doubling that | B√ t | and |B √ B⊂6Br

p-Osc B (e -tL f ) r η ( B) t -η/2 |B √ t | -1/p f p ,

and (3.2) together with (3.3) yield (H η p,∞ ). Following some ideas in [14, Theorem 3.1], we can now identify (H η p,p ) as the property needed to pass from (UE) to (LE). Theorem 3.4. Let (M, d, µ, E) be a metric measure Dirichlet space satisfying (VD) and the upper Gaussian estimate (UE). If there exist p ∈ [1, +∞] and η ∈ (0, 1] such that (H η p,p ) is satisfied, then the Gaussian lower bound (LE) holds. Conversely (LE) implies (H η p,p ) for all p ∈ [1, +∞) and some η ∈ (0, 1].

  √ t is any ball of radius √ t containing x, y (in particular, p t is continuous and p t (x, x) has a meaning).

	It
	follows from (VD) and (UE) that
	(3.4)

1/p p t (•, z) p , uniformly for a.e. x, y with d(x, y) ≤ √ t and where B

  Remark 3.6. Proposition 3.1 and Theorem 3.4 still hold in the context of sub-Gaussian estimates. Instead of (UE), let us assume that the heat kernel satisfies for some m > 2 (UE m )

x, .) -p t (y, .) p f p , which together with (3.8) yields (H η p,∞ ) with η = θ/2p, hence (H η p,p ) by Proposition 3.1.

  4.3). Property (H α 2,2 ) follows and Theorem 3.4 yields (LE). If the ambient space M is bounded, one can see that to get (LE) it is sufficient to check (4.14) for the scales √ t diam(M ), which is exactly what we just have proved. It remains to prove the next lemma which follows ideas of [1, Theorem 3.6] and [29, Lemma 2.1, Chapter III].

  Theorem 5.1,[START_REF] Auscher | Regularity theorems and heat kernel for elliptic operators[END_REF]). Note that the truncation property holds in our setting (see [48, Section 3,(o)]). If p > ν, a stronger L ∞ inequality is true ([36, Theorem 5.1, 2.]), and one gets the above by integration. If p = ν, one deduces the claim from [36, Theorem 5.1, 3.] by bounding from above the function t → t q by an exponential.

	Proof of Proposition 6.4. Proposition 5.4 yields
	-Br	|∇f | p 0 dµ	1/p 0	r p 0 -Osc 2Br (f )	2Br + r -	|Lf | p 0 dµ	1/p 0

Acknowledgements

The first and the third author acknowledge financial support from the Hausdorff Research Institute for Mathematics in Bonn where part of this work was done. All authors are very grateful to Steve Hofmann and José María Martell for a fruitful discussion where they have pointed out the results of Appendix B. The second author would like to thank Estibalitz Durand-Cartagena for interesting discussions about Poincaré inequalities on metric spaces.

F. Bernicot's research is supported by ANR projects AFoMEN no. 2011-JS01-001-01 and HAB no. ANR-12-BS01-0013. T. Coulhon's research was done while he was employed by the Australian National University. It was supported by the Australian Research Council (ARC) grant DP 130101302. D. Frey's research is supported by the Australian Research Council (ARC) grants DP 110102488 and DP 120103692.

Proof of Theorem 6.3. First we already have seen that the combination (G p ) with (P p ) implies (DUE) (Proposition 2.1) and it is known that it yields (4.6). By Proposition 6.4, the combination (G p ) with (P p ) (for some p > 2) implies a weak Poincaré inequality (w -P 2 ) for all harmonic functions. Then from Theorem 6.1, we deduce a weak Poincaré inequality for every function of D. We conclude to the strong Poincaré inequality by Theorem 6.2.

An obvious by-product of Theorem 6.3 is the following monotonicity property for (G p ) + (P p ). Corollary 6. [START_REF] Barlow | On the equivalence of parabolic Harnack inequalities and heat kernel estimates[END_REF]. Let (M, d, µ, E) be a metric measure Dirichlet space with a "carré du champ" satisfying (VD). Then (G p ) + (P p ) for some p > 2 implies (G q ) + (P q ) for all q ∈ [2, p).

Appendix A. From Poincaré to De Giorgi

In this appendix, we give a self-contained proof for the fact that, under (VD), (P 2 ) implies the De Giorgi property (DG 2 ), as stated in Proposition 4.2. One method is to use the elliptic Moser iteration process from [START_REF] Moser | On Harnack theorem for elliptic differential equations[END_REF], see for instance [START_REF] Auscher | Gaussian lower bounds for random walks from elliptic regularity[END_REF]Sections 5 and 6]. The proof is given there in a discrete time and space setting, but adapts to our current setting. Another proof in [START_REF] Auscher | Gaussian lower bounds for random walks from elliptic regularity[END_REF] by-passes the difficult part of the Moser iteration process, namely the John-Nirenberg lemma, and uses instead the self-improvement property of Poincaré inequalities. This is the one we will present here.

In this appendix, we will assume for simplicity that diam(M ) = +∞. If on the contrary diam(M ) < +∞, it is enough to assume that R ≤ δ diam(M ), where δ is the parameter that has to appear in (F K) in that case, and to use doubling at the end of the argument.

We first need to state a version of the Caccioppoli inequality (5.1) in L 2 , but for subharmonic functions.

Lemma A.1. Let (M, d, µ, E) be a doubling metric measure Dirichlet space with a "carré du champ". For every x ∈ M , 0 < r < R and every u ∈ D with uLu ≤ 0 on B(x, R), one has

Proof. Consider a function χ belonging to F, supported on B(x, R), with values in [0, 1], and such that χ ≡ 1 on B(x, r) and |∇χ| ∞ (R -r) -1 . Such a function can easily be built in our setting from the metric d (see for instance [35, Section 2.2.6] for details).

Since uLu ≤ 0 on B(x, R) one may write

.

Due to the definition of d, this yields

By letting n go to infinity, one concludes that u(d, R/2) = 0. This means that for all x ∈ B(x

To go further, we will need to use scaled Poincaré inequalities and their consequences. Assuming (P 2 ), we know that there exists ε > 0 such that (P 2-ε ) holds [START_REF] Keith | The Poincaré inequality is an open ended condition[END_REF]. We will be working with the modified version

where f ranges in D and B in balls in M of radius r. The inequality ( P 2-ε ) is a consequence of (P 2-ε ), as can be seen by checking the inequality

To prove the latter, abbreviate B N (f ) := {y ∈ B; f (y) = 0} and write

From this, we deduce

, where in the last step we have used the elementary inequality 1 -(1 -x) 1/p ≥ x p for x ∈ [0, 1] and p ∈ [1, +∞).

Lemma A.3. Let (M, d, µ, E) be a doubling metric measure Dirichlet space with a "carré du champ" satisfying (UE) and (F K). Let ε ∈ (0, 1] and assume

where C does not depend on x 0 , R, or u.

Proof of Proposition 4.2. Consider a function u ∈ F harmonic in B R = B(x 0 , R). By Proposition A.4, we have (ER), and we have seen at the beginning of the proof of Theorem 4.4 that this implies

for B r = B(x 0 , r) and 0 < r ≤ R. Using the Caccioppoli inequality (A.1) and (P 2 ), we obtain

then the inequality still holds by (VD).

We can now deduce (DG 2 ) as follows (cf. [START_REF] Giaquinta | Multiple integrals in the calculus of variations and nonlinear elliptic systems[END_REF]Theorem 1.1] or [START_REF] Auscher | Regularity theorems and heat kernel for elliptic operators[END_REF]Theorem 3.6]). Let f ∈ D, x 0 ∈ M , and R > 0. As in the proof of Theorem 4.4, from Lemma 4.6 (since (F K) follows from (P 2 ) let consider u ∈ F be harmonic on B(x 0 , R) such that f -u ∈ F is supported in the ball B(x 0 , R). From (1.1), (1.2), and (1.6), we deduce

Using triangle inequality, then (VD) and (A.7), write, for 0 < r ≤ R,

Since (F K) follows from our assumptions, we can use (4.11) and together with (A.8) it follows that

, where γ = max{1 -α, ν 2 }. Applying Lemma 4.7 and since

one obtains (DG 2,ε ) for every ε ∈ (1 -α, 1).

Appendix B. A self-improving property for reverse Hölder inequalities

In this appendix, we shall describe a general self-improving property of reverse Hölder inequalities which is used in Proposition 6.4. These results are not new and already appeared in the literature (see e.g. [START_REF] Iwaniec | Hardy-Littlewood inequality for quasiregular mappings in certain domains in R n[END_REF]Theorem 2] and [START_REF] Heinonen | Nonlinear Potential Theory of Degenerate Elliptic Equations[END_REF]Subsection 3.38]). We give a proof for the sake of completeness.

Consider (M, d, µ) a doubling metric measure space. Let Q be the collection of all balls of the ambient space M , and consider a functional a : Q → [0, ∞). We say that a is regular if there exists a constant c > 0 such that for every pair of balls

Theorem B.1. Let 1 < p < q ≤ +∞. Consider a regular functional a. Let ω ∈ L 1 loc (M, µ) be a non-negative function such that for every ball B ⊂ M

Then, for every η ∈ (0, 1) and every ball B ⊂ M ,

+ a(2B).

In other words, the right-hand side exponent of a reverse Hölder inequality always self-improves.

Proof. Fix η ∈ (0, 1). For every ε ∈ (0, 1), consider

It is easy to observe that K(ε, η) is finite and bounded by ε -1 . We claim that K(ε, η) is uniformly bounded, with respect to ε. Indeed, assume that K(ε, η) ≥ 1 (else there is nothing to prove) and take a ball

, for any δ ∈ [0, 1]. Using Hölder's inequality with the particular choice δ = η(q-p) q-ηp gives us

Using (B.1), the assumption K(ε, η) ≥ 1 and the fact that 4B i ⊂ 2B, one obtains

(ω δ ω 1-δ ) p dµ Taking the supremum over all balls B then yields

which in turn yields, since K(ε, η) is finite and δ > 0 due to p < q, K(ε, η) 1.

This last estimate is uniform with respect to ε. Hence, by letting ε → 0, we obtain the desired conclusion.


Frank Vega Np

Frank Vega
email: vega.frank@gmail.com

NP versus PSPACE

Keywords: P, NP, PSPACE, PSPACE-complete, GEOGRAPHY 2000 MSC: 68-XX, 68Qxx, 68Q15

Introduction

The P versus NP problem is a major unsolved problem in computer science. This problem was introduced in 1971 by Stephen Cook [START_REF] Cook | The complexity of Theorem Proving Procedures[END_REF]. It is considered by many to be the most important open problem in the field [START_REF] Fortnow | The Status of the P versus NP Problem[END_REF]. It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute to carry a US$1,000,000 prize for the first correct solution.

The argument made by Alan Turing in the twentieth century states that for any algorithm we can create an equivalent Turing machine [START_REF] Turing | On Computable Numbers, with an Application to the Entscheidungsproblem[END_REF]. There are some definitions related with this model such as the deterministic or nondeterministic Turing machine. A deterministic Turing machine has only one next action for each step defined in its program or transition function [START_REF] Papadimitriou | Computational complexity[END_REF]. A nondeterministic Turing machine can contain more than one action defined for each step of the program, where this program is not a function, but a relation [START_REF] Papadimitriou | Computational complexity[END_REF].

Another huge advance in the last century was the definition of a complexity class. A language L over an alphabet is any set of strings made up of symbols from that alphabet [START_REF] Cormen | Introduction to Algorithms[END_REF]. A complexity class is a set of problems, which are represented as a language, grouped by measures such as the running time, memory, etc [START_REF] Cormen | Introduction to Algorithms[END_REF].

In computational complexity theory, the class P consists in all those decision problems (defined as languages) that can be decided on a deterministic Turing machine in an amount of time that is polynomial in the size of the input; the class NP consists in all those decision problems whose positive solutions can be verified in polynomial-time given the right information, or equivalently, that can be decided on a nondeterministic Turing machine in polynomial-time [START_REF] Goldreich | Np-Completeness[END_REF]. On the other hand, PS PACE is the class of all languages recognizable by polynomial space bounded deterministic Turing machines that halt on all inputs [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness, 1st Edition[END_REF].

The biggest open question in theoretical computer science is the following one: Is P equal to NP? There is another important complexity class called PSPACE-complete [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness, 1st Edition[END_REF]. A language L is PSPACE-complete if L is in PS PACE, and every PS PACE problem can be reduced in polynomialtime to L [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness, 1st Edition[END_REF]. We shall define a new problem called ODDPATH-HORNUNSAT. We shall show this problem is NP and PSPACE-complete. Since, PS PACE is closed under reductions and NP ⊆ PS PACE, then we have that NP = PS PACE [START_REF] Papadimitriou | Computational complexity[END_REF].

Theoretical framework

The SAT problem

We say that a language L 1 is polynomial-time reducible to a language L 2 , written L 1 ≤ p L 2 , if there exists a polynomial-time computable function f : {0, 1} * → {0, 1} * such that for all x ∈ {0, 1} * ,

x ∈ L 1 if and only if f (x) ∈ L 2 .
There is an important complexity class called NP-complete [START_REF] Goldreich | Np-Completeness[END_REF]. A language L ⊆ {0, 1} * is NP-complete if • L ∈ NP, and

• L ≤ p L for every L ∈ NP.
Furthermore, if L is a language such that L ≤ p L for some L ∈ NP-complete, then L is NP-hard [START_REF] Cormen | Introduction to Algorithms[END_REF]. Moreover, if L ∈ NP, then L ∈ NP-complete [START_REF] Cormen | Introduction to Algorithms[END_REF].

One of the first discovered NP-complete problems was S AT [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness, 1st Edition[END_REF]. An instance of S AT is a Boolean formula φ which is composed of • Boolean variables: x 1 , x 2 , .... ;

• Boolean connectives: Any Boolean function with one or two inputs and one output, such as ∧(AND), ∨(OR), (NOT), →(implication), ↔(if and only if); and

• parentheses.

A truth assignment for a Boolean formula φ is a set of values for the variables of φ, and a satisfying truth assignment is a truth assignment that causes it to evaluate to true. A formula with a satisfying truth assignment is a satisfiable formula. The S AT asks whether a given Boolean formula is satisfiable.

One convenient language is 3CNF satisfiability, or 3S AT [START_REF] Cormen | Introduction to Algorithms[END_REF]. We define 3CNF satisfiability using the following terms. A literal in a Boolean formula is an occurrence of a variable or its negation. A Boolean formula is in conjunctive normal form, or CNF, if it is expressed as an AND of clauses, each of which is the OR of one or more literals. A Boolean formula is in 3-conjunctive normal form, or 3CNF, if each clause has exactly three distinct literals.

For example, the Boolean formula

(x 1 ∨ x 1 ∨ x 2 ) ∧ (x 3 ∨ x 2 ∨ x 4 ) ∧ ( x 1 ∨ x 3 ∨ x 4 )
is in 3CNF. The first of its three clauses is (x 1 ∨ x 1 ∨ x 2 ), which contains the three literals x 1 ,

x 1 , and x 2 . In 3S AT , we are asked whether a given Boolean formula φ in 3CNF is satisfiable.

The HORNSAT problem

We say that a language L 1 is logarithmic-space reducible to a language L 2 , written

L 1 ≤ log L 2 , if there exists a logarithmic-space computable function f : {0, 1} * → {0, 1} * such that for all x ∈ {0, 1} * , x ∈ L 1 if and only if f (x) ∈ L 2 .
The logarithmic space reduction is frequently used for P and below [START_REF] Papadimitriou | Computational complexity[END_REF]. There is an important complexity class called P-complete [START_REF] Papadimitriou | Computational complexity[END_REF]. A language L ⊆ {0, 1} * is P-complete if

• L ∈ P, and

• L ≤ log L for every L ∈ P.
One of the P-complete problems is HORNS AT [START_REF] Papadimitriou | Computational complexity[END_REF]. We say that a clause is a Horn clause if it has at most one positive literal [START_REF] Papadimitriou | Computational complexity[END_REF]. That is, all its literals, except possibly for one, are negations of variables. An instance of HORNS AT is a Boolean formula φ in CNF which is composed only of Horn clauses [START_REF] Papadimitriou | Computational complexity[END_REF].

For example, the Boolean formula

( x 2 ∨ x 3 ) ∧ ( x 1 ∨ x 2 ∨ x 3 ∨ x 4 ) ∧ (x 1 )
is a conjunction of Horn clauses. The HORNS AT asks whether an instance of this problem is satisfiable [START_REF] Papadimitriou | Computational complexity[END_REF].

Directed graph notions

A directed graph (or digraph) G is a pair (V, E), where V is a finite set and E is a binary relation on V [START_REF] Cormen | Introduction to Algorithms[END_REF]. The set V is called the vertex set of G, and its elements are called vertices (singular: Vertex) [START_REF] Cormen | Introduction to Algorithms[END_REF]. The set E is called the edge set of G, and its elements are called edges [START_REF] Cormen | Introduction to Algorithms[END_REF].

If (u, v) is an edge in a directed graph G = (V, E), we say that (u, v) is outgoing from or leaves vertex u and is income to or enters vertex v. If (u, v) is an edge in a graph G = (V, E), we say that vertex v is adjacent to vertex u [START_REF] Cormen | Introduction to Algorithms[END_REF]. In a directed graph, the adjacency relation is not necessarily symmetric [START_REF] Cormen | Introduction to Algorithms[END_REF]. If v is adjacent to u in a directed graph, we sometimes write u → v.

A path of length k from a vertex u to a vertex u in a graph [START_REF] Cormen | Introduction to Algorithms[END_REF]. The length of the path is the number of edges in the path [START_REF] Cormen | Introduction to Algorithms[END_REF]. The path contains the vertices v 0 , v 1 , ..., v k and the edges (v 0 , v 1 ), (v 1 , v 2 ), ..., (v k-1 , v k ) [START_REF] Cormen | Introduction to Algorithms[END_REF]. If there is a path p from u to u , we say that u is reachable from u via p [START_REF] Cormen | Introduction to Algorithms[END_REF]. A path is simple if all vertices in the path are distinct [START_REF] Cormen | Introduction to Algorithms[END_REF].

G = (V, E) is a sequence of vertices < v 0 , v 1 , v 2 , ..., v k > such that u = v 0 , u = v k , and (v i-1 , v i ) ∈ E for i = 1, 2, ..., k

The GEOGRAPHY problem

A language L ⊆ {0, 1} * is PSPACE-complete if

• L ∈ PS PACE, and

• L ≤ p L for every L ∈ PS PACE.
Perhaps one the most fundamental problem for PS PACE is the game of GEOGRAPHY [START_REF] Papadimitriou | Computational complexity[END_REF]. GEOGRAPHY is an elementary-school game played by two players, called here "P1" and "P2" [START_REF] Papadimitriou | Computational complexity[END_REF]. We can formulate this games as follows: We have a directed graph G = (V, E) whose nodes are all the cities of the world, and such that there is an edge from city i to city j if and only if the last letter in the name of i coincides with the first letter in the name of j [START_REF] Papadimitriou | Computational complexity[END_REF]. Player P1 starts picking a node 1, then player P2 picks another node to which there is an edge from 1, say node 2. Player P1 then must reply picking a node to which there is an edge from 2 without taking the used nodes 1 and 2. In this way, with the player alternating, it is defined a simple path from G. The first player that cannot continue the path because all edges out of the current tip lead to nodes already used, loses [START_REF] Papadimitriou | Computational complexity[END_REF].

We can generalize this to any given directed graph G; this generalization may imply not only a planet with arbitrarily many cities, but, even less realistically, one with an arbitrarily large alphabet [START_REF] Papadimitriou | Computational complexity[END_REF]. Hence, the GEOGRAPHY would be the following computational problem: Given a directed graph G and a starting node 1, is it a win for P1? It is a proved result that the GEOGRAPHY belongs to PSPACE-complete [START_REF] Papadimitriou | Computational complexity[END_REF].

Results

Definition 3.1. A sat-graph, written SAT-G = (V, E, κ), is a directed graph G = (V, E) with a mapping function κ, such that κ maps each vertex u ∈ V to a Boolean formula. Definition 3.2. Given a sat-graph SAT-G = (V, E, κ) and a starting node u, the problem called as ODDPATH-HORNUNSAT consists in deciding whether exists a simple path of vertices

< v 0 , v 1 , v 2 , ..., v k > such that u = v 0 , κ(v 0 ) ∧ κ(v 1 ) ∧ κ(v 2 ) ∧ ... ∧ κ(v k ) ∈ HORNUNS AT ,
and the length of the path is odd.

Note: See the definition of simple and length of a graph path in section 2. HORNUNS AT would be the complement language of HORNS AT , that is, the instances of HORNS AT which are unsatisfiable (see section 2). Proof. Given a sat-graph SAT-G = (V, E, κ) and a starting node u, we can check in polynomialtime whether a path p =< v 0 , v 1 , v 2 , ..., v k > is a certificate of this instance just verifying that u = v 0 , checking that all vertices in the path are distinct, checking that the length of the path is odd, and verifying in polynomial-time whether κ(v 0 ) ∧ κ(v 1 ) ∧ κ(v 2 ) ∧ ... ∧ κ(v k ) ∈ HORNUNS AT since HORNUNS AT ∈ P due to P is closed under complement [START_REF] Papadimitriou | Computational complexity[END_REF]. Consequently, there is a polynomial-time verifier for ODDPATH-HORNUNSAT, and thus, ODDPATH-HORNUNSAT ∈ NP [START_REF] Papadimitriou | Computational complexity[END_REF]. Proof. ODDPATH-HORNUNSAT ∈ PS PACE, because NP ⊆ PS PACE [START_REF] Papadimitriou | Computational complexity[END_REF]. Given a directed graph G and a starting node u, we will create a sat-graph SAT-G, such that (G, u) ∈ GEOGRAPHY if and only if (SAT-G, u) ∈ ODDPATH-HORNUNSAT. For this purpose, we will do the following actions:

(1) First, we take the directed graph G = (V, E) and for each vertex v ∈ V, we create a new state v and add an edge v → v . We will call the vertex v as the clone vertex of v. In this way, we create a new graph G = (V , E ). ( 2) Next, for each vertex v ∈ V in the graph G = (V , E ), we create a new Boolean variable x v which will be linked to vertex v. We say that x v is represented by the vertex v.

(3) After that, we create a mapping function κ, such that for each vertex v ∈ V in the graph

G = (V , E ), we have κ(v) = x v if v has not outgoing edges or κ(v) = x v ∧ ( x v 1 ∨ x v 2 x v 3 ∨ ...∨
x v m ) when v has m > 0 outgoing edges, where x v is represented by the vertex v and x v 1 , x v 2 , x v 3 , ..., x v m are represented by the vertices v 1 , v 2 , ..., v m which are all the vertices that are adjacent to vertex v (see section 2 for definition of the adjacency relation). We will call this clause of all negated variables inside of κ(v) as the adjacency clause of v. (4) Finally, we obtain a sat-graph SAT-G = (V , E , κ).

All these steps can be done in polynomial-time just iterating through the vertices and edges of G. In the step (1), we need to iterate through the set of vertices V to add new |V| vertices and edges. The algorithm of insertion of a polynomial amount of new vertices and edges into a graph will take only a polynomial-time [START_REF] Cormen | Introduction to Algorithms[END_REF]. In the step (2), we need to iterate through the set of vertices V to create the Boolean variables of each vertex. This will only need a polynomial-time since |V | = 2 × |V|. Finally, in the step (3), we need to iterate through the set of vertices V and edges of E to create the mapping function κ. This would take a polynomial-time in relation to |V|. Now, suppose we take a simple path of vertices p =< v 0 , v 1 , v 2 , ..., v k > in SAT-G, such that u = v 0 and φ = κ(v 0 )∧κ(v 1 )∧κ(v 2 )∧...∧κ(v k ). We can see the inner formula x v 0 ∧ x v 1 ∧ x v 2 ∧...∧ x v k inside of φ is satisfiable, and therefore, whether φ is in HORNUNS AT or not depends principally of the adjacency clauses of vertices in p. Indeed, φ ∈ HORNUNS AT if and only if there is an adjacency clause of some vertex v i inside of φ which has all its negated Boolean variables represented by a vertex in p. Moreover, this will only happen in the adjacency clause of v k-1 , because in the other vertices of the path the respective adjacency clauses can be true, because the Boolean variables represented by the respective clone vertices can be false. Certainly, if φ ∈ HORNUNS AT , then v k (the last vertex in the path p) should necessarily be a clone vertex. The reason is this one: If the path p does not contain a clone vertex, then it would be impossible that the adjacency clause of some vertex v i (where p contains v i ) will be false for all truth assignment of φ, because we could always make true the adjacency clauses of vertices in p just evaluating the Boolean variables represented by the respective clone vertices in false. At the same time, it will be impossible that the path p could have a clone vertex different of the last one, because the clone vertices does not have outgoing edges.

But, what does this mean? It would mean, we cannot reach any adjacent vertex from vertex v k-1 that is not already visited in the path, except for its clone vertex. But, this is exactly what happens when a player loses in the game of GEOGRAPHY. In addition, the path p =< v 0 , v 1 , v 2 , ..., v k-1 > represents a winner path from the starting node u in the game of GEOGRAPHY, where the winner is player P1 if the length of p is even, else the winner is player P2. Therefore, as the path p contains another vertex (v k : The clone vertex of v k-1 ), then the winner will be P1 if the length of p is odd. Hence, we can conclude with the following result: 5 (G, u) ∈ GEOGRAPHY if and only if (SAT-G, u) ∈ ODDPATH-HORNUNSAT.

Since GEOGRAPHY belongs to PSPACE-complete, and the time of the reduction above is polynomial, then we obtain ODDPATH-HORNUNSAT ∈ PSPACE-complete.

Theorem 3 . 3 .

 33 ODDPATH-HORNUNSAT ∈ NP.

Theorem 3 . 4 .

 34 ODDPATH-HORNUNSAT ∈ PSPACE-complete.

Theorem 3 . 5 .

 35 NP = PS PACE.Proof. We prove ODDPATH-HORNUNSAT is NP and PSPACE-complete in Theorems 3.3 and 3.4. Since, PS PACE is closed under reductions and NP ⊆ PS PACE, then we have that NP = PS PACE[START_REF] Papadimitriou | Computational complexity[END_REF].