EXTENSIONS SYMBOLIQUES EN R ÉGULARIT É INTERM ÉDIAIRE SUR Les Surfaces

David Burguet

SYMBOLIC EXTENSIONS IN INTERMEDIATE SMOOTHNESS ON SURFACES

come

Introduction

By a dynamical system (X, T ) we mean a continuous map T on a compact metrizable space X. One well studied class of dynamical systems are the symbolic ones, i.e. closed subset Y of A Z , with a finite alphabet A, endowed with the shift S. Such a pair (Y, S) is also called a subshift. Given a dynamical system (X, T ) one wonders if there exists a symbolic extension (Y, S) of (X, T ), i.e. a subshift (Y, S) along a continuous map π : Y → X such that π • S = T • π. We first observe that dynamical systems with symbolic extensions have necessarily finite topological entropy. When a dynamical system has symbolic extensions we are interested in minimizing their entropy. The topological symbolic extension entropy h sex (T ) = inf{h top (Y, S) : (Y, S) is a symbolic extension of (X, T )} estimates how the dynamical system (X, T ) differs from a symbolic extension from the point of view of entropy. The problem of the existence of symbolic extensions leads to a deep theory of entropy which was developed mainly by M.Boyle and T.Downarowicz, who related the existence of symbolic extensions and their entropy with the convergence of the entropy of (X, T ) computed at finer and finer scales [START_REF] Boyle | The entropy theory of symbolic extensions[END_REF].

By using a result of J.Buzzi [START_REF] Buzzi | Intrinsic ergodicity for smooth interval maps[END_REF] involving Yomdin theory, M.Boyle, D.Fiebig, U.Fiebig [START_REF] Boyle | Residual entropy, conditional entropy and subshift covers[END_REF] proved that C ∞ maps on a compact manifold admit principal symbolic extensions, i.e. symbolic extensions which preserve the entropy of invariant measures [START_REF] Boyle | Residual entropy, conditional entropy and subshift covers[END_REF]. On the other hand C 1 maps without symbolic extensions have been built in several works [START_REF] Downarowicz | Symbolic extension entropy in smooth dynamics[END_REF], [START_REF] Asaoka | Hyperbolic set exhibing C 1 -persistent homoclinic tangency for higher dimensions[END_REF], [START_REF] Burguet | Examples of C r interval map with large symbolic extension entropy[END_REF].

In the present paper we consider dynamical systems of intermediate smoothness, i.e. C r maps T on a compact manifold with 1 < r < +∞ (we mean that T admits a derivative or order ⌈r -1⌉ which is r -⌈r -1⌉-Hölder). T.Downarowicz and A.Maass have recently proved that C r maps of the interval f : [0, 1] → [0, 1] with 1 < r < +∞ have symbolic extensions [START_REF] Downarowicz | Smooth interval maps have symbolic extensions[END_REF]. More precisely they showed that h sex (f ) ≤ h top (f ) + log f ′ ∞ r-1 . The author built explicit examples [START_REF] Burguet | Examples of C r interval map with large symbolic extension entropy[END_REF] proving this upper bound is sharp. Similar C r examples with large symbolic extension entropy have been previously built by T.Downarowicz and S.Newhouse for diffeomorphisms in higher dimension [START_REF] Downarowicz | Symbolic extension entropy in smooth dynamics[END_REF]. The results of T.Downarowicz and A.Maass have been extended by the author in any dimension to nonuniformly entropy expanding maps (i.e. C 1 maps whose ergodic measures with positive entropy have nonnegative Lyapunov exponents) of class C r with 1 < r < +∞ [START_REF] Burguet | Symbolic extensions for C r nonuniformly entropy expanding maps[END_REF]. More recently the author also proved the existence of symbolic extensions for C 2 surface local diffeomorphisms [START_REF] Burguet | C 2 surface diffeomorphisms have symbolic extensions[END_REF]. T.Downarowicz and S.Newhouse have conjectured in [START_REF] Downarowicz | Symbolic extension entropy in smooth dynamics[END_REF] that C r maps on a compact manifold with r > 1 have symbolic extensions. The following theorem answers affirmatively to this conjecture in dimension 2 and extends thus the results of [START_REF] Burguet | C 2 surface diffeomorphisms have symbolic extensions[END_REF]. When T : M → M is a C 1 map on a compact Riemannian manifold (M, ) we denote by R(T ) the exponential growth of the derivative, i.e. R(T ) = lim n→+∞ log + DT n n . This quantity does not depend on the choice of the Riemannian metric on M .

Theorem 1. Let T : M → M be a C r map on a compact surface M with r > 1. Then T admits symbolic extensions and h sex (T ) ≤ h top (T ) + 4R(T ) r -1 Moreover, if T is a local surface diffeomorphism, then

h sex (T ) ≤ h top (T ) + R(T ) r -1
The paper is organized as follows. We first recall the background of the theory of symbolic extensions and properties of continuity of the sum of the positive Lyapunov exponents. Following S.Newhouse we also recall how the local entropy is bounded from above by the local volume growth of smooth disks. Then we state our main results and as in [START_REF] Burguet | C 2 surface diffeomorphisms have symbolic extensions[END_REF] we reduce them to a Reparametrization Lemma of Bowen's balls in a similar (but finer) approach of the classical Yomdin theory. The last sections are devoted to the proof of the Reparametrization Lemma.

Preliminaries

In the following we denote M(X, T ) the set of invariant Borel probability measures of the dynamical system (X, T ) and M e (X, T ) the subset of ergodic measures. We endow M(X, T ) with the weak star topology. Since X is a compact metric space, this topology is metrizable. We denote by dist a metric on M(X, T ). It is well known that M(X, T ) is compact and convex and its extreme points are exactly the ergodic measures. Moreover if µ ∈ M(X, T ) there exists an unique Borel probability measure M µ on M(X, T ) supported by M e (X, T ) such that for all Borel subsets B of X we have µ(B) = ν(B)dM µ (ν). This is the so called ergodic decomposition of µ. A bounded real Borel map f : M(X, T ) → R is said to be harmonic if f (µ) = Me(X,T ) f (ν)dM µ (ν) for all µ ∈ M(X, T ). It is a well known fact that affine upper semicontinuous maps are harmonic. The measure theoretical entropy h : M(X, T ) → R + is always harmonic [START_REF] Walters | An introduction to ergodic theory[END_REF] but is not upper semicontinuous in general. It may not be upper semicontinuous even for C r map for any r ∈ R + [START_REF] Misiurewicz | Diffeomorphism without any measure with maximal entropy[END_REF]. However h is upper semicontinuous for C ∞ maps [START_REF] Newhouse | Continuity properties of entropy[END_REF].

If f is a bounded real Borel map defined on M e (X, T ), the harmonic extension f of f is the function defined on M(X, T ) by :

f (µ) := Me(X,T ) f (ν)dM µ (ν)
It is easily seen that f coincides with f on M e (X, T ) and that f is harmonic.

2.1. Entropy structure. The measure theoretical entropy function can be computed in many ways as limits of nondecreasing sequences of nonnegative functions defined on M(X, T ) (with decreasing sequences of partitions, formula of Brin-Katok,...). The entropy structures are such particular sequences whose convergence reflect the topological dynamic : they allow for example to compute the tail entropy [START_REF] Burguet | A direct proof of the tail variational principle and its extension to maps[END_REF] [START_REF] Downarowicz | Entropy structure[END_REF], but also especially the symbolic extension entropy [START_REF] Boyle | The entropy theory of symbolic extensions[END_REF] [START_REF] Downarowicz | Entropy structure[END_REF] (see below for precise statements).

We skip the formal definition of entropy structures, but we recall a basic fact. Two nondecreasing sequences, (h k ) k∈N and (g k ) k∈N , of nonnegative functions defined on M(X, T ) are said to be uniformly equivalent if for all γ > 0 and for all k ∈ N, there exists l ∈ N such that h l > g kγ and g l > h kγ. Two entropy structures are uniformly equivalent and any nondecreasing sequence of nonnegative functions which is uniformly equivalent to an entropy structure is itself an entropy structure. In other terms the set of entropy structures is an equivalence class for the above relation.

We recall now Lemma 1 of [START_REF] Burguet | C 2 surface diffeomorphisms have symbolic extensions[END_REF] which relates the entropy structures of a given dynamical system with those of its inverse and powers. Lemma 1. Let (X, T ) be a dynamical system with finite topological entropy and let H = (h k ) k∈N be an entropy structure of T p with p ∈ N\{0} (when T is a homeomorphism

we consider p ∈ Z \ {0}). Then the sequence 1 |p| H| M(X,T ) = h k | M(X,T ) |p| k∈N
defines an entropy structure of T .

We finally check that the minimum of two entropy structures defines again an entropy structure.

Lemma 2. Let (X, T ) be a dynamical system with finite topological entropy. If H = (h k ) k and G = (g k ) k are two entropy structures, then min(H, G) := (min(h k , g k )) k is also an entropy structure.

Proof : Let γ > 0 and k ∈ N. As H and G are both entropy structures, they are in particular uniformly equivalent. Therefore there exists an integer l such that h l > g kγ and g l > h kγ. We can assume that l > k so that h l ≥ h k by monotonicity of H. Therefore h l > min(h k , g k )γ and min(h l , g l ) > h kγ.

Tail entropy.

In order to study the properties of upper semicontinuity of the entropy function of a dynamical system and in particular the existence of measures of maximal entropy, M.Misiurewicz introduced in the seventies the following quantity which is now known as the tail entropy of the system. Let us first recall some usual notions relating to the entropy of dynamical systems (we refer to [START_REF] Walters | An introduction to ergodic theory[END_REF] for a general introduction to entropy).

Consider a continuous map T : X → X with (X, d) a compact metric space. Let n ∈ N and δ > 0. A subset F of X is called a (n, δ) separated set when for all x, y ∈ F there exists 0 ≤ k < n such that d(T k x, T k y) ≥ δ. Let Y be a subset of X. A subset F of Y is called a (n, δ) spanning set of Y when for all y ∈ Y there exists z ∈ F such that d(T k y, T k z) < δ for all 0 ≤ k < n. Given a point x ∈ X we denote by B(x, n, δ) the Bowen's ball centered at x of radius δ and length n :

B(x, n, δ) := {y ∈ X, d(T k y, T k x) < δ for k = 0, ..., n -1}
The tail entropy, h * (T ), of (X, T ) is then defined by

h * (T ) := lim ǫ→0 lim sup n→+∞ sup x∈X 1 n log min {♯C : F is a (n, δ) spanning set of B(x, n, ǫ)}
This quantity is a topological invariant which estimates the entropy appearing at arbitrarily small scales. The tail entropy bounds from above the defect of upper semicontinuity of the entropy function [START_REF] Misiurewicz | Topological conditional entropy[END_REF] :

∀µ ∈ M(X, T ), lim sup ν→µ h(ν) -h(µ) ≤ h * (T )
In general the supremum of the defect of upper semicontinuity of the entropy function differs from the tail entropy. But it is easily seen that for any entropy structure (h k ) k of (X, T ), we have lim sup ν→µ h(ν)-h(µ) ≤ lim k lim sup ν→µ (h-h k )(ν) and T.Downarowicz proved then the following variational principle [START_REF] Downarowicz | Entropy structure[END_REF] (see also [START_REF] Burguet | A direct proof of the tail variational principle and its extension to maps[END_REF]) :

sup µ∈M(X,T ) lim k lim sup ν→µ (h -h k )(ν) = lim k sup µ∈M(X,T ) (h -h k )(µ) = h * (T ) (1)
By using Yomdin theory J.Buzzi [START_REF] Buzzi | Intrinsic ergodicity for smooth interval maps[END_REF] established the following upper bound on the tail entropy of C r maps T on a compact manifold M with r > 1 :

h * (T ) ≤ dim(M ) r R(T ) (2)
This inequality is known to be sharp for noninvertible maps [START_REF] Buzzi | Intrinsic ergodicity for smooth interval maps[END_REF], [START_REF] Ruette | Mixing C r maps of the interval without maximal measure[END_REF]. We will prove in the present paper a similar sharp upper bound on the tail entropy of C r surface diffeomorphisms with r > 1 (see Theorem 5 below).

When h * (T ) = 0 the dynamical system (X, T ) is said to be asymptotically h-expansive. For example, uniformly hyperbolic dynamical systems or piecewise monotone interval maps are asymptotically h-expansive. Then entropy structures are converging uniformly to the entropy function. There exist therefore measures of maximal entropy by upper semicontinuity of the entropy function and also symbolic extensions preserving the entropy of invariant measures (see Theorem 2 below). According to Inequality (2) it is also the case of C ∞ maps on a compact manifold.

Symbolic extension entropy function.

A symbolic extension of (X, T ) is a subshift (Y, S) of a full shift on a finite number of symbols, along with a continuous surjection π : Y → X such that T • π = π • S. Given a symbolic extension π : (Y, S) → (X, T ) we consider the extension entropy h π ext : M(X, T ) → R + defined for all µ ∈ M(X, T ) by :

h π ext (µ) = sup π * ν=µ h(ν)
Then the symbolic extension entropy function, h sex : M(X, T ) → R + , is :

h sex = inf h π ext
where the infimum holds over all the symbolic extensions of (X, T ). By convention, if (X, T ) does not admit any symbolic extension we simply put h sex ≡ +∞. Recall we defined in the introduction the topological symbolic extension entropy h sex (T ) as the infimum of the topological entropy of the symbolic extensions of (X, T ) (as previously we put h sex (T ) = +∞ when there are no such extensions). M.Boyle and T.Downarowicz proved that these two quantities are related by the following variational principle :

h sex (T ) = sup µ∈M(X,T ) h sex (µ) (3)
We present now the major Symbolic Extension Entropy Theorem of [START_REF] Boyle | The entropy theory of symbolic extensions[END_REF] which allows to compute the symbolic extension entropy function from the properties of convergence of any entropy structure. We follow the exposition in [START_REF] Burguet | Symbolic extensions and Continuity properties of the entropy[END_REF]. Let S(X, T ) be the set of nonnegative upper semicontinuous functions defined on M(X, T ) to which we add the function constant equal to +∞. Let (h k ) k be an entropy structure, we define an increasing operator on S(X, T ), denoted by T sex , as follows :

T sex : S(X, T ) → S(X, T ) f → µ → lim k lim sup ν∈M(X,T ),ν→µ (f + h -h k ) (ν)
One easily checks from the uniform equivalence relation that T sex does not depend on the choice of the entropy structure (h k ) k . We also observe that the tail variational principle can be written as sup µ∈M(X,T ) T sex 0(µ) = h * (T ). By using the affine structure of the set of invariant probability measures M.Boyle and T.Downarowicz proved that the least fixed point of T sex (whose existence is ensured by Tarski-Knaster Theorem) coincides with the infimum of the affine fixed points of T sex . We recall now the Symbolic Extension Entropy Theorem : Theorem 2. (Theorem 5.5 of [START_REF] Boyle | The entropy theory of symbolic extensions[END_REF]) The affine fixed points of T sex are exactly the functions h π exth, i.e. f is a nonnegative affine upper semicontinuous function on M(X, T ) fixed by T sex if and only if there exists a symbolic extension π such that f = h π ext -h. Moreover h sexh is the least fixed point of T sex .

When (X, T ) is asymptotically h-expansive, then the zero function is a fixed point of T sex because entropy structures are converging uniformly. Therefore such systems (including C ∞ maps on compact manifold) admit symbolic extensions π : (Y, S) → (X, T ) with h π ext = h. This result was first proved by M.Boyle, D.Fiebig and U.Fiebig [START_REF] Boyle | Residual entropy, conditional entropy and subshift covers[END_REF].

The Passage Theorem of T.Downarowicz and A.Maass [START_REF] Downarowicz | Smooth interval maps have symbolic extensions[END_REF] gives a weaker condition for an affine upper semicontinuous function on M(X, T ) to be fixed by T sex : one only needs to consider the lim sup in ergodic measures ν in the definition of T sex . More precisely a nonnegative affine upper semicontinuous function f on M(X, T ) is a fixed point of T sex if and only if lim sup ν∈Me(X,T ),ν→µ (f + hh k ) (ν) = f (µ) for all µ ∈ M(X, T ). This can be restated as follows :

Theorem 3 (Downarowicz, Maass). [19][17] Let (X, T ) be a dynamical system with finite topological entropy. Let g be a nonnegative upper semicontinuous affine function on M(X, T ) such that for every γ > 0, for every µ ∈ M(X, T ) and for every entropy structure H = (h k ) k∈N there exists k µ ∈ N and δ µ > 0 such that for every ergodic measure ν satisfying dist(ν, µ) < δ µ it holds that :

(h -h kµ )(ν) ≤ g(µ) -g(ν) + γ (4)
Then there exists a symbolic extension π : (Y, S) → (X, T ) such that h π exth = g. In particular h sexh ≤ g.

It follows from the uniform equivalence relation that the assumptions of Theorem 3 hold as soon as they are satisfied by one particular entropy structure.

Newhouse local entropy.

We recall now the "Newhouse local entropy". Let x ∈ X, ǫ > 0, δ > 0, n ∈ N and F ⊂ X a Borel set, we define :

H(n, δ|x, F, ǫ) := log max ♯E : E ⊂ F B(x, n, ǫ) and E is a (n, δ) separated set H(n, δ|F, ǫ) := sup x∈F H(n, δ|x, F, ǫ) h(δ|F, ǫ) := lim sup n→+∞ 1 n H(n, δ|F, ǫ) h(X|F, ǫ) := lim δ→0 h(δ|F, ǫ)
Then for any ergodic measure ν we put :

h N ew (X|ν, ǫ) := lim α→1 inf ν(F )>α h(X|F, ǫ)
Finally we extend the function h N ew (X|•, ǫ) to M(X, T ) by the harmonic extension. Given a nonincreasing sequence (ǫ k ) k∈N converging to 0, we consider the sequence

H N ew T = (h N ew k ) k∈N with h N ew k := h -h N ew (X|., ǫ k )
for all integers k. A similar quantity with minor differences was first introduced by S.Newhouse in [START_REF] Newhouse | Continuity properties of entropy[END_REF]. T.Downarowicz proved this sequence defines an entropy structure [START_REF] Downarowicz | Entropy structure[END_REF] for homeomorphisms and the author extended the result in the noninvertible case [START_REF] Burguet | Entropy and local complexity of differentiable dynamical sytems[END_REF].

2.5. Lyapunov exponents. Let (M, ) be a compact Riemannian manifold of dimension d and let T : M → M be a C 1 map. We denote

D x T = sup v∈TxM -{0} DxT (v) v
the induced norm of the differential D x T of T at x and DT = sup x∈M D x T the supremum norm of the differential of T . We consider an ergodic T -invariant measure ν.

According to Oseledet's theorem [START_REF] Oseledets | A multiplicative ergodic theorem. Lyapunov characteristic numbers for dynamical systems[END_REF], there exist real numbers

χ 1 (ν) ≥ ... ≥ χ d (ν) ≥ -∞, an increasing sequence of measurable invariant subbundles of the tangent space {0} = G d+1 ⊆ G d ⊆ ... ⊆ G 1 = T M and a Borel set F with ν(F ) = 1 such that for all x ∈ F and all v i ∈ G i \ G i+1 with i = 1, ..., d we have lim n→+∞ 1 n log D x T n (v i ) = χ i (ν)
The real numbers χ i (ν) are the well-known Lyapunov exponents of ν (sometimes we use also the notations χ i (ν, T ) to avoid ambiguities). We prove now elementarily that the harmonic extension of the sum of the positive Lyapunov exponent is upper semicontinuous. In the one dimensional case it was proved by T.Downarowicz and A.Maass by using a clever argument of convexity (see Fact 2.5 of [START_REF] Downarowicz | Smooth interval maps have symbolic extensions[END_REF]). We just adapt the proof of [START_REF] Burguet | C 2 surface diffeomorphisms have symbolic extensions[END_REF] which only deals with the dimension d = 2. If S : M → M is a C 1 map we denote by Λ k D x S the map induced by the differential map D x S on the k th exterior power Λ k T x M (with 1 ≤ k ≤ d) of the tangent space of M at x ∈ M and by k the induced norm on the space of multilinear maps on Λ k T x M . Lemma 3. For all 1 ≤ e ≤ d and for all µ ∈ M(M, T ), we have :

e i=1 χ + i (µ) = inf n∈N 1 n max k=1,...,e log + Λ k D x T n k dµ(x)
In particular e i=1 χ + i : M(M, T ) → R + is upper semicontinuous.

Proof :

For all integers n > 0 we consider the function f n : M(M, T ) → R + defined by :

∀µ ∈ M(M, T ), f n (µ) = max k=1,...,e log + Λ k D x T n k dµ(x)
This function is clearly continuous and affine, and therefore harmonic. Also (

f n (µ)) n∈N is a subadditive sequence for all µ ∈ M(M, T ). It follows from Oseledet's theorem that e i=1 χ + i (ν) = lim n→+∞ fn(ν) n
for all ergodic measures ν. Consider now a general measure µ ∈ M(M, T ). We have :

e i=1 χ + i (µ) := Me(M,T ) e i=1 χ + i (ν)dM µ (ν) = Me(M,T ) lim n→+∞ f n (ν) n dM µ (ν)
Obviously f n (ν) ≤ e log + DT for all ergodic measures ν. Therefore by applying the theorem of dominated convergence we get :

e i=1 χ + i (µ) = lim n→+∞ Me(M,T ) f n (ν) n dM µ (ν)
and by harmonicity of f n :

e i=1 χ + i (µ) = lim n→+∞ f n (µ) n
But the sequence (f n (µ)) n∈N is subadditive so that :

e i=1 χ + i (µ) = inf n∈N f n (µ) n
We conclude that e i=1 χ + i is an upper semicontinuous function as an infimum of a family of continuous functions.

Clearly the function e i=1 χ + i is uniformly bounded from above by

R e (T ) := lim sup n sup x∈X 1 n max k=1,...,e log + Λ k D x T n k
With the previous notations we have also R e (T ) ≤ eR(T ) and R 1 (T ) = R(T ). In fact the following variational principle holds [START_REF] Burguet | Entropy and local complexity of differentiable dynamical sytems[END_REF] :

sup µ e i=1 χ + i (µ) = R e (T )
We notice that the harmonic extension e i=1 χ + i can be rewritten in the most common way as e i=1 χ + i = M e i=1 χ + i (x)dµ(x) where (χ i (x)) i=1,...,d denotes the Lyapunov exponents of a regular point x ∈ M .

In the special case e = d we also recall that the sum of all the Lyapunov exponents (positive or not) are given by

d i=1 χ i (µ) = M log Jac x (T )dµ(x)
In the following we are interesting in the entropy of ergodic measures. We denote by χ + (resp.

χ -) the sum of all the positive (resp. negative) Lyapunov exponents. The Ruelle-Margulis inequality states that for a C 1 map T : M → M on a compact manifold M the entropy h T (ν) of an ergodic measure ν is bounded from above by the sum of its positive Lyapunov exponents. When T is a diffeomorphism it is easily seen by applying the Ruelle-Margulis inequality to T and its inverse T -1 and by using the equality h T (ν) = h T -1 (ν) that any ergodic measure ν ∈ M e (M, T ) with non zero entropy has at least one positive and one negative Lyapunov exponent, moreover

h(ν) ≤ min χ + (ν), - χ -(ν)
2.6. Local entropy and volume growth. In this section we recall Theorem 2 of [START_REF] Newhouse | Continuity properties of entropy[END_REF] (in fact an intermediate result in its proof) which relates the Newhouse local entropy of an ergodic measure with the local volume growth of smooth disks. We begin with some definitions. Let T : M → M be a C r map on a compact manifold with r > 1. We fix a Riemannian metric on the manifold M and we endow M with the induced distance. A C 1 map σ from the unit square [0, 1] k of R k to M , which is a diffeomorphism onto its image, is called a k-disk. For any k-disk σ and for any χ > 0, γ > 0 and C > 1, we consider the set H n T (σ, χ, γ, C) of points of [0, 1] k whose exponential growth of the derivative of the n-first iterations of T composed with σ is almost equal to χ :

H n T (σ, χ, γ, C) := t ∈ [0, 1] k : ∀1 ≤ j ≤ n, C -1 e (χ-γ)j ≤ D t T j • σ ≤ Ce (χ+γ)j
We also denote by |σ| the k-volume of σ, i.e. |σ| = |Λ k D t σ|dλ(t) where dλ is the Lebesgue measure on [0, 1] k . Then given χ > 0, γ > 0, C > 1, x ∈ M , n ∈ N and ǫ > 0 we define the local volume growth of σ at x with respect to these parameters as follows :

V n,ǫ x (σ|χ, γ, C) := T n-1 • σ| H n T (σ,χ,γ,C)∩σ -1 (B(x,n,ǫ))
Fix an ergodic measure ν and let l ν be the codimension of the first Lyapunov eigenspace G i with χ i (ν) < 0. In [START_REF] Newhouse | Continuity properties of entropy[END_REF] S.Newhouse proved by using Pesin theory that for some ǫ > 0 depending only on the manifold M and for any 1 > α > 0 and γ > 0 there exist a Borel set F α of ν-measure larger than α and a l ν -disk σ of class C ∞ , such that for all δ > 0 one can find a constant C > 1 depending only on F α and another constant D depending only on δ and F α satisfying for all n ∈ N and for all x ∈ F α :

H(n, δ|x, F α , ǫ) ≤ De γn V n,ǫ x (σ|χ 1 (ν), γ, C) (5)
In fact F α is a Pesin set and the l ν -disk can be chosen to be the exponential map restricted to a neighborhood of the unstable distribution at some point of F α . In the following we will consider only smooth 1-disks σ : [0, 1] → R d . We denote by σ ′ the derivative Dσ of the curve σ.

Statements

We first state in this section the main result of this paper by specifying Theorem 1 at the measure theoretic level. It will be deduced, by using the Estimate theorem, from the below Main Proposition which gives an upperbound on the Newhouse local entropy involving the positive Lyapunov exponents. The proof of this proposition is the topic of the next sections. Theorem 4. Let T : M → M be a C r surface map (resp. local surface diffeomorphism) with r > 1. Then there exists a symbolic extension π : (Y, S) → (X, T ) with

h π ext -h = 2 χ + (µ) r -1 resp. = χ + 1 (µ) r -1
In particular, for all µ ∈ M(M, T ),

h sex (µ) -h(µ) ≤ 2 χ + (µ) r -1 resp. χ + 1 (µ) r -1
The above theorem will follow from the following Main Proposition by applying the Estimate Theorem to the upper semicontinuous affine function g = 2 χ + r-1 or g = As the functions h π ext , χ + 1 and χ + are upper semicontinuous it follows from Theorem 4 that the entropy function of a C r surface map with r > 1 is a difference of nonnegative upper semicontinuous functions. In particular generic measures are continuity points of the entropy function. In general this is false for C 1 maps. We refer to [START_REF] Burguet | Symbolic extensions and Continuity properties of the entropy[END_REF] for further details on the links between the symbolic extension entropy and the properties of continuity of the entropy function.

We give now a new upper bound on the tail entropy of C r surface diffeomorphisms with r > 1. The examples built in [START_REF] Downarowicz | Symbolic extension entropy in smooth dynamics[END_REF] show that this upper bound is sharp.

Theorem 5. Let T : M → M be a C r surface diffeomorphisms with r > 1. Then, for all µ ∈ M(X, T ), we have

T sex 0(µ) ≤ χ + 1 (µ) r
and in particular,

h * (T ) ≤ R(T ) r
Theorem 4 and Theorem 5 will both follow from the following proposition.

Main Proposition . Let T : M → M be a C r map with r > 1 on a compact manifold M of dimension d. Let µ be a T -invariant measure and fix some γ > 0.

Then there exist δ µ > 0, an entropy structure (h k ) k and k µ ∈ N such that for every ergodic T -invariant measure ν with dist(ν, µ) < δ µ and either with at most one nonnegative Lyapunov exponent or with all Lyapunov exponents nonnegative (i.e. l ν is equal to either 0, 1 or d) it holds that :

(h -h kµ )(ν) ≤ l ν r -1   lν i=1 χ + (µ) - χ + (ν)   + γ (6)
In the case l ν = d it is a direct consequence of the Main Theorem of [START_REF] Burguet | Symbolic extensions for C r nonuniformly entropy expanding maps[END_REF] that we recall below. Then, to prove the proposition we only need to consider the case l ν ≤ 1 and we finally conclude by considering the minimum of the two entropy structures, the one corresponding to the case l ν ≤ 1 and the other corresponding to the case l ν = d (see Lemma 2). It is worth noting that when d = 1 Inequality (6) can be obtained by two ways which seem to be different : the first one due to T.Downarowicz and A.Maass by studying the critical set and the second one presented in the present paper which follows from the Reparametrization Lemma stated in the next section.

We think that this statement should hold for any ergodic measure without condition on its Lyapunov spectrum. It will implies Theorem 4 in any dimension. Let us just do it in the two dimensional case. We first recall the main result of [START_REF] Burguet | Symbolic extensions for C r nonuniformly entropy expanding maps[END_REF] which is a generalization of the approach of T.Downarowicz and A.Maass. [START_REF] Burguet | Symbolic extensions for C r nonuniformly entropy expanding maps[END_REF]) Let T : M → M be a C r map, with r > 1, on a compact manifold of dimension d. Let µ be an invariant measure and fix some γ > 0.

Proposition 1. (Main Theorem of

Then there exist δ µ > 0, an entropy structure (h k ) k and k µ ∈ N such that for every ergodic measure ν with dist(ν, µ) < δ µ it holds that :

(7) (h -h kµ )(ν) ≤ d (f (µ) -f (ν)) r -1 - χ -(ν) + γ
where f (ξ) = max log Jac x (T )dξ(x), 0 for all invariant measures ξ.

When T is a local diffeomorphism then ξ → log Jac x (T )dξ(x) is continuous on M(M, T ). Then, with the notations of the above theorem, we have (hh kµ )(ν) ≤ χ -(ν) + 2γ for ν close enough to µ. In particular if (hh kµ )(ν) > 2γ then ν has at least one negative Lyapunov exponent (and also at least a positive one by Ruelle-Margulis inequality).

We deduce now the theorems of this section from the above proposition.

Proof of Theorem 4 : As we follows the strategy of [START_REF] Downarowicz | Smooth interval maps have symbolic extensions[END_REF] we only sketch the proof. First we consider the case of local surface diffeomorphisms. According to the above remark it is enough to consider ergodic measures with one negative and one positive Lyapunov exponent. Then one just applies the Estimate Theorem with g = χ + 1 r-1 which is an upper semicontinuous function satisfying (4) by assumption. We prove similarly Theorem 4 for general surface maps by applying the Estimate Theorem with g = 2 χ + r-1 .

Proof of Theorem 5 : Let (h k ) k be an entropy structure of (M, T ) and let µ ∈ M(X, T ). By Ruelle-Margulis inequality we have for all ν ∈ M(M, T )

(h -h k )(ν) ≤ min χ + 1 (ν), h -h k + χ + 1 r -1 (ν) - χ + 1 (ν) r -1
By taking the lim sup when ν goes to µ we have for all integers k lim sup

ν→µ (h -h k )(ν) ≤ sup ν∈M(X,T ) min χ + 1 (ν), lim sup ξ→µ h -h k + χ + 1 r -1 (ξ) - χ + 1 (ν) r -1
and since

χ + 1
r-1 is a fixed point of T sex by Theorem 4 we have when k goes to infinity

lim k lim sup ν→µ (h -h k )(ν) ≤ sup ν∈M(X,T ) min χ + 1 (ν), lim k lim sup ξ→µ h -h k + χ + 1 r -1 (ξ) - χ + 1 (ν) r -1 ≤ sup ν∈M(X,T ) min χ + 1 (ν), χ + 1 (µ) r -1 - χ + 1 (ν) r -1
As a continuous piecewise affine function in χ + 1 (ν) the right member min χ + 1 (ν),

χ + 1 (µ) r-1 - χ + 1 (ν) r-1
attains its maximum at

χ + 1 (µ) r
and is therefore bounded from above by

χ + 1 (µ)
r . We conclude according to the tail variational principle (1) that h * (T ) ≤ R(T ) r .

We already have noticed that the inequality h * (T ) ≤ dR(T ) r due to J.Buzzi holds for any C r maps on a compact manifold M of dimension d. By adapting the proof it is not difficult to also prove T sex 0(µ) ≤ dχ + 1 (µ) r for all µ ∈ M(M, T ) [START_REF] Burguet | Entropy and local complexity of differentiable dynamical sytems[END_REF]. But we do not know if in this inequality we can replace dR(T ) (resp. dχ + 1 (µ)) by max 1≤e≤d R e (T ) (resp. χ + (µ)).

Bounding local entropy of curves with a Reparametrization Lemma of Bowen balls

In a similar way as in [START_REF] Burguet | C 2 surface diffeomorphisms have symbolic extensions[END_REF] we reduce now the Main Proposition to a result of reparametrization of 1-disk σ in Bowen balls by volume contracting maps. Then the local volume growth and thus the Newhouse local entropy of some ergodic measure ν is just bounded from above by the logarithmic growth of the number of reparametrizations. In fact we only need to reparametrize Bowen balls on a set of large ν measure. As one can assume the entropy and thus the maximal Lyapunov exponent χ 1 (ν) to be nonzero it is enough to consider the intersection of Bowen balls with the set H n T (σ, χ 1 (ν), γ, C) for small γ > 0 and for any C > 1. This is one of the main differences with Yomdin theory where the whole Bowen ball is reparametrized by volume contracting maps.

In [START_REF] Burguet | C 2 surface diffeomorphisms have symbolic extensions[END_REF] we do not use Newhouse estimate (which involves Pesin theory) of the local entropy with the local volume growth. Then we had to reparametrize not only curves but the intersection of Bowen balls with finite hyperbolic sets which are in general not one dimensional. The present situation is of course easier and allows us to get C r estimates.

We denote H : [1, +∞[→ R the function defined by

H(t) = -1 t log( 1 t ) -(1 -1 t ) log(1 - 1 t ). Moreover [x]
is the usual integer part of x if x > 0 and zero if not (i.e. [x] is the largest nonnegative integer k such that max(x, 0) ≥ k). Afterwards we also use the notation ⌈x⌉ to denote the usual ceiling function (i.e. ⌈x⌉ is the smallest integer k such that x ≤ k). We recall that a map T between two smooth Riemannian manifolds is said of class C r with r > 0 when it admits a derivative of order ⌈r -1⌉ which is r -⌈r -1⌉-Hölder. We denote then by T r the r -⌈r -1⌉-Hölder norm of the ⌈r -1⌉-derivative of T . Observe that if T is C r then T is C s for all 0 ≤ s ≤ r. When ⌈r -1⌉ < s ≤ r we have moreover T s ≤ C T r with a constant C depending only on the Riemannian manifolds. Finally T 0 will denote the usual supremum norm of T .

Reparametrization Lemma . Let T : M → M be a C r map with r > 1 on a compact Riemannian manifold M .

Then for all χ > 0, γ > 0 and C > 1, there exist ǫ > 0 depending only on T s , s = 1, ..., [r], r and a universal constant A > 0 with the following properties.

For all x ∈ M , for all positive integers n and for all 1-disks σ : [0, 1] → M of class C r with max s=1,...,[r],r σ s ≤ 1, there exist a family F n of affine maps from [0, 1] to [0, 1] and a real positive number B depending only on σ, such that with λ + n (x, T ) :=

1 n n-1 j=0 log + D T j x T the following properties hold : (i) ∀ψ ∈ F n , ∀0 ≤ l ≤ n, D(T l • σ • ψ) ≤ 1, (ii) H n T (σ, χ, γ, C) ∩ σ -1 (B(x, n + 1, ǫ)) ⊂ ψ∈Fn ψ([0, 1]), (iii) log ♯F n ≤ 1 r -1 1 + H([λ + n (x, T ) -χ] + 3) λ + n (x, T ) -χ n + An + B.
We deduce now the Main Proposition from the above statement by following [START_REF] Burguet | C 2 surface diffeomorphisms have symbolic extensions[END_REF]. In the proof the terms λ + n (x, T ) for typical ν points x and χ will be respectively related with the maximal Lyapunov exponent of µ and ν where ν is an ergodic measure near an invariant measure µ. Moreover the quantity H([λ + n (x, T )χ] + 3) will be negligible.

Proof of the Main Proposition assuming the Reparametrization Lemma :

Let µ ∈ M(M, T ) and let γ > 0. By Lemma 3 we choose p µ ∈ N \ {0} such that

χ + 1 (µ) = inf n∈N log + D x T n dµ(x) n ≥ log + D x T pµ dµ(x) p µ - (r -1)γ 4 .
One can also assume p µ large enough such that H p µ (r-1)γ 4 R(T ) < (r-1)γ 4 and A+2γ pµ < γ 4 . We will prove the statement of the Main Proposition with the entropy structure 1 pµ H N ew T pµ | M(M,T ) (see Lemma 1). By continuity of µ → log + D y T pµ dµ(y) and by upper semicontinuity of χ + 1 one can choose the parameter δ µ > 0 such that for all ergodic measures ν with dist(ν, µ) < δ µ we have :

log + D y T pµ dν(y) -log + D y T pµ dµ(y) < (r -1)γ 4 , χ + 1 (µ) > χ + 1 (ν) - (r -1)γ 4 .
We fix some ergodic measure ν with dist(µ, ν) < δ µ with at most one nonnegative Lyapunov exponent. One can assume h(ν) > 3γ 4 because 1 pµ h N ew T pµ (M |ν, ǫ µ ) ≤ h(ν) and the right member of Inequality ( 6), 1 r-1 χ + 1 (µ)χ + 1 (ν) + γ, is larger than 3γ 4 . In particular we have by Ruelle-Margulis inequality χ + 1 (ν) ≥ h(ν) > 0. The measure ν need not be ergodic under T pµ but has at most p µ ergodic components ν which all satisfy χ i (ν, T pµ ) = p µ χ i (ν) for all i = 1, ..., d and thus l ν = l ν = 1.

We fix such an ergodic component ν. For any 0 < α < 1 we let F α be the Borel set of ν measure larger than α as in Section 2.6.

One can also assume by the ergodic theorem that (λ + n (x, T pµ )) n∈N are converging uniformly in x ∈ F α to log + D y T pµ dν(y) and that F α ⊂ G α with G α as in Section 2.6 for T pµ and ν.

Let σ : [0, 1] → M be a 1-disk associated to F α and ν satisfying Inequality (5), i.e. with ǫ and D as in ( 5)

H T pµ (n, δ|x, F α , ǫ) ≤ De γn V n,ǫ
x,T pµ (σ|χ 1 (ν), γ, C) We apply now the Reparametrization Lemma to T pµ , σ and to a given point x ∈ F α : there exist ǫ > ǫ µ > 0 depending only on T pµ s , s = 1, ..., [r], r, a real number B depending only on χ 1 (ν), γ, C and σ s , T pµ s , s = 1, ...[r], r, and families (F n ) n of affine maps from [0, 1] to [0, 1] satisfying the properties (i)-(ii)-(iii) of the Reparametrization Lemma. By (i) the volume of T n-1 • σ • ψ is less than or equal to 1 for all ψ ∈ F n . Therefore we have with (ii)

V n,ǫ
x,T pµ (σ|χ 1 (ν), γ, C) ≤ ♯F n and it follows from (iii) that :

h T pµ (M |F α , ǫ µ ) ≤ lim n→+∞ sup x∈Fα 1 r -1 1 + H([λ + n (x, T pµ ) -χ 1 (ν)] + 3) λ + n (x, T pµ ) -χ 1 (ν) + A + 2γ
According to the definition of F α we have :

lim n→+∞ inf x∈Fα λ + n (x, T pµ ) -χ 1 (ν) = lim n→+∞ sup x∈Fα λ + n (x, T pµ ) -χ 1 (ν) = log + D y T pµ dν(y) -χ 1 (ν) ≥ 0
Now we distinguish cases :

• either log + D y T pµ dν(y) < χ 1 (ν) + p µ (r-1)γ 4
, then the term

lim n→+∞ sup x∈Fα H([λ + n (x, T pµ ) -χ 1 (ν)] + 3) (λ + n (x, T pµ ) -χ 1 (ν)) is bounded from above by log(2) log + D y T pµ dν(y) -χ 1 (ν) which is less than log(2)p µ (r-1)γ 4 . • or log + D y T pµ dν(y) ≥ χ 1 (ν)+p µ (r-1)γ 4
, then we have lim

n→+∞ inf x∈Fα λ + n (x, T pµ )- χ 1 (ν) ≥ p µ (r-1)γ 4
. But we choose p µ large enough so that R(T )H p µ (r-1)γ 4

< (r-1)γ 4
. It follows that :

lim n→+∞ sup x∈Fα H([λ + n (x, T pµ ) -χ 1 (ν)] + 3) (λ + n (x, T pµ ) -χ 1 (ν)) ≤ H p µ (r-1)γ 4 p µ R(T ) ≤ p µ (r-1)γ 4
We get finally in both cases :

h T pµ (M |F α , ǫ µ ) ≤ 1 r -1 log + D y T pµ dν(y) -χ 1 (ν) + p µ γ 4 + A + 2γ
Then by letting α go to 1 we obtain since A+2γ pµ < γ 4 :

1 p µ h N ew T pµ (M |ν, ǫ µ ) ≤ 1 (r -1)p µ log + D y T pµ dν(y) -χ 1 (ν) + γ 2
The above inequality holds for all ergodic components ν of ν and then also for ν by harmonicity :

1 p µ h N ew T pµ (M |ν, ǫ µ ) ≤ 1 (r -1)p µ log + D y T pµ dν(y) -p µ χ 1 (ν) + γ 2 (8)
Now we deduce from the choice of δ µ that :

log + D y T pµ dν(y) -p µ χ 1 (ν) ≤ log + D y T pµ dµ(y) -p µ χ 1 (ν) +
(r -1)γ 4 and then by the choice of p µ we get :

1 p µ log + D y T pµ dν(y) -p µ χ 1 (ν) ≤ χ + 1 (µ) -χ + 1 (ν) + (r -1)γ 2
Together with Inequality (8) we conclude that 1

p µ h N ew T pµ (M |ν, ǫ µ ) ≤ 1 r -1 χ + 1 (µ) -χ + 1 (ν) + γ.
The end of this paper deals with the proof of the Reparametrization Lemma. We first state the key ingredients. The first one is a combinatorial argument which allows us to work with subset of Bowen balls of length n where the defect of multiplicativity of the norm DT DT k •σ DT k+1 •σ is fixed for k = 0, ..., n -1. Then we recall Yomdin reparametrization lemma and a Landau-Kolmogorov inequality which will be used to get C r estimates of the Newhouse local entropy. Finally we explain how bound the local volume of a C 1 curve by assuming that the derivative of this curve oscillates little.

Technical lemmas

This section is devoted to some useful technical lemmas for the proof of the Reparametrization Lemma presented in the last section. 5.1. Combinatorial Lemma. We first begin with a usual combinatorial lemma which was already used by T.Downarowicz and A.Maass in [START_REF] Downarowicz | Smooth interval maps have symbolic extensions[END_REF] and by the author in [START_REF] Burguet | C 2 surface diffeomorphisms have symbolic extensions[END_REF].

Definition 1. Let S ∈ N and n ∈ N. We say that a sequence of n positive integers

K n := (k 1 , ..., k n ) admits the value S if 1 n n i=1 k i ≤ S.
The number of sequences of n positive integers admitting the value S is exactly the binomial coefficient nS n . When S is large enough this term is exponentially small in nS. More precisely we have the following lemma (recall that H denotes the function defined from [1, +∞[ by

H(t) = -1 t log( 1 t ) -(1 -1 t ) log(1 -1 t )
). Lemma 4. The logarithm of the number of sequences of n positive integers admitting the value S is at most nSH(S) + 1.

We refer to [START_REF] Flum | Parametrized Complexity Theory[END_REF] (Lemma 16.19) for a proof. In the two next subsections we present the tools which allows us to get C r estimates of the symbolic extension entropy function in contrast with [START_REF] Burguet | C 2 surface diffeomorphisms have symbolic extensions[END_REF] where the author only deals with C 2 maps.

Estimates à la Yomdin.

We recall now the heart of Yomdin theory which estimates the "local differential complexity" of intermediate smooth maps. The proof is based on a powerful Semi-algebraic Lemma due to M.Gromov [START_REF] Gromov | Entropy, homology and semi-algebraic geometry[END_REF] (see also [START_REF] Burguet | A Proof of Yomdin-Gromov algebraic Lemma[END_REF] for a complete proof of Gromov's statement). Lemma 5. [START_REF] Gromov | Entropy, homology and semi-algebraic geometry[END_REF] Let k and d be positive integers and let s > 0 be a positive real number. For any positive real number a > 0 and for any C s map g : [0, 1] k → R d with g s ≤ a, there exists a family of real analytic maps F from [0, 1] k to itself such that :

• φ∈F φ([0, 1] k ) ⊃ x ∈ [0, 1] k , g(x) ≤ a , • φ t ≤ 1 for all t = 1, 2, ..., [s] + 1, • g • φ t ≤ a 12e for t = min(1, s), 2..., [s], s, • ♯F ≤ C with a universal constant C depending only on k, d and s.
In fact this is a functional version of Lemma 3.4 of [START_REF] Gromov | Entropy, homology and semi-algebraic geometry[END_REF] but the proofs are the same. The constant 1 12e may be replaced by any other universal constant. We choose this one for convenience of computation in the final proof of the Reparametrization Lemma.

The Semi-algebraic Lemma [START_REF] Gromov | Entropy, homology and semi-algebraic geometry[END_REF] claims that the statement holds for polynomial functions without any condition on the derivatives, but the constant C may depend on the degree. Then to prove the general case one approximates the given intermediate smooth function by its Lagrangian polynomial. The hypothesis on the highest order derivative makes the approximation good enough to conclude the proof.

To bound the local volume growth of k-disks Y.Yomdin uses Lemma 5 in a dynamical context. More precisely, given a C r map T : M → M on a compact manifold M and a k-disk σ with T n • σ s ≤ 1, he applies it with a = 1, s = r and g = T n • σ. Then it follows from (iii) that the k-volume of T n • σ is universally bounded from above. To ensure the condition on the s-norm we have to subdivide a general disk in C ste DT nk r subdisks so that the exponential rate of the local volume growth of a k-disk is bounded by k R(T ) r replacing if necessary T by an iteration of T .

Here we use Lemma 5 only to reparametrize areas where the oscillation of the derivative of (T n •σ) ′ is small compared to its size. Thus we will apply Lemma 5 with s = r -1 to the derivative (T n • σ) ′ . That's why we get the factor 1 r-1 (and not 1 r as above) in the estimates of the Newhouse local entropy given by the Main Proposition. The constant a will be chosen to be the norm of the derivative of T n • σ at typical points. Then in the case of 1-disks an easy geometrical argument presented in Subsection 5.4 allows us to bound the local volume growth.

5.3.

A Landau-Kolmogorov type Inequality. Yomdin's reparametrization maps are semi-algebraic and it seems difficult to control from below the size of their derivative. Therefore we just use affine maps in the proof of the Reparametrization Lemma. The key ingredient to control the derivatives is then the following classical Landau-Kolmogorov type inequality due to L.Neder [START_REF] Neder | Abschätzung für die Einleitungen einer reellen Funktion eines reellens Arguments[END_REF]. Lemma 6. [START_REF] Neder | Abschätzung für die Einleitungen einer reellen Funktion eines reellens Arguments[END_REF] Let g : [0, 1] → R d be a C s map with s > 0. Then, there exists a universal constant C depending only on s and d such that

∀k = 0, 1, ..., [s], g k ≤ C ( g 0 + g s )
For the sake of completeness we give a short proof of this result, that we borrow from [START_REF] Devore | Constructive Approximation, Grundlehren der mathematischen Wissenschaften[END_REF] (Theorem 5.6). In this reference the result is stated for integers 2 ≤ s but it can be easily extended to the general case 1 < s ∈ R as follows.

Proof : Without loss of generality we may assume d = 1. Let x ∈ [0, 1 2 ]. From Taylor's formula, we have for all 0 ≤ u ≤ 1 2 :

g(x + u) = g(x) + ug ′ (x) + ... + u ⌈s-2⌉ ⌈s -2⌉! g (⌈s-2⌉) (x) + u 0 (u -t) ⌈s-2⌉ ⌈s -2⌉! f ⌈s-1⌉ (x + t)dt = g(x) + ug ′ (x) + ... + u ⌈s-2⌉ ⌈s -2⌉! g (⌈s-2⌉) (x) + u ⌈s-1⌉ ⌈s -1⌉! g (⌈s-1⌉) (x) + u 0 (u -t) ⌈s-2⌉ ⌈s -2⌉! g ⌈s-1⌉ (x + t) -g ⌈s-1⌉ (x) dt
As g (⌈s-1⌉) is s -⌈s -1⌉ Hölder the integral remainder term

R(x, u) = u 0 (u -t) ⌈s-2⌉
⌈s -2⌉! g ⌈s-1⌉ (x + t)g ⌈s-1⌉ (x) dt can be bounded as follows

|R(x, u)| ≤ u 0 (u -t) ⌈s-2⌉ t s-⌈s-1⌉ ⌈s -2⌉! g s dt ≤ u s 1 0 (1 -x)⌈s -2⌉x s-⌈s-1⌉ dx ⌈s -2⌉! g s dt ≤ u s B(s + 1 -⌈s -1⌉ , ⌈s -1⌉) g s ⌈s -1⌉! (9)
where B denotes the usual beta function. Then we choose arbitrarily real numbers 0 < λ 1 < ...λ ⌈s-1⌉ < 1 and we let A be the Vandermonde matrix given by A :=

λ j i 1≤i,j≤⌈s-1⌉
. We have

g x + λ i 2 -g(x) -R x, λ i 2 i = A g (i) (x) i!2 i i
As the determinant of A is nonzero this system of equations can be solved and we have according to Inequality (9) for all x ∈ [0, 1 2 ]

g (i) (x) i! ≤ C ( g 0 + g s )
where C is a constant depending only on s and on the real numbers λ 1 < ... < λ ⌈s-1⌉ . We argue similarly for x ∈ [ 1 2 , 1] by considering -1 2 ≤ u ≤ 0. This concludes the proof of the lemma.

We will apply this lemma with s = r-1 to the derivative (T n •σ) ′ with T n := T n •...•T 1 for a sequence (T n ) n of C r maps defined on the unit ball of R d and for a smooth 1-disk σ : [0, 1] → R d .

5.4.

Curves with small oscillations of the derivative. In the present subsection we give an alternative strategy to bound the local volume of a C 1 curve σ : [0, 1] → R d , that is the length of σ| σ -1 (B(0,1)) . We assume now that we control the oscillation of the derivative of σ (instead of the r-derivative in Yomdin's approach). More precisely we want the ratio σ ′ (t)-σ ′ (s) σ 1 to be small uniformly in t, s ∈ [0, 1]. Then the following easy geometrical argument allows us to bound the local volume of σ. This idea was already exploited in [START_REF] Burguet | C 2 surface diffeomorphisms have symbolic extensions[END_REF] under a slightly different form (Proposition 8 of [START_REF] Burguet | C 2 surface diffeomorphisms have symbolic extensions[END_REF]). In the following the space R d is always endowed with the usual euclidean norm and B(x, r) will denote the ball of radius r centered at x ∈ R d . Lemma 7. Let σ : [0, 1] → R d be a C 1 curve satisfying the following properties [START_REF] Asaoka | Hyperbolic set exhibing C 1 -persistent homoclinic tangency for higher dimensions[END_REF]

σ([0, 1]) ∩ B(0, 1) = ∅, (2) σ ′ (t) -σ ′ (s) ≤ σ 1 3 for all t, s ∈ [0, 1].
Then, there exists

[a, b] ⊂ [0, 1] such that • σ([0, 1]) ∩ B(0, 1) ⊂ σ([a, b]) ⊂ B(0, √ d), • (b -a) σ 1 ≤ √ 3d.
Proof : Let w ∈ [0, 1] with σ(w) ∈ B(0, 1). The hypothesis (2) on the derivative σ ′ of σ implies that σ ′ (s) lies in the cone

C := {u ∈ R d , |∠u, σ ′ (w)| ≤ π 6 } for all s ∈ [0, 1
]. Indeed we have for all s ∈ [0, 1] :

σ ′ (s) sin ∠σ ′ (s), σ ′ (w) ≤ σ ′ (s) -σ ′ (w) ≤ σ 1 3 ≤ σ ′ (s)
2 where the last inequality follows, with s 0 ∈ [0, 1] such that σ ′ (s 0 ) = σ 1 , from :

σ ′ (s) ≥ σ ′ (s 0 ) -σ ′ (s) -σ ′ (s 0 ) ≥ σ 1 - 1 3 σ 1 = 2 3 σ 1
We consider the cube S of size √ d containing the unit ball B(0, 1) whose faces are either orthogonal or parallel to σ ′ (w). If σ(t) does not belong to S for some t > w then σ(s) stays out of S for s > t (see the picture above). Similarly if σ(t) is not in S for some t < w then so does σ(s) for s < t. Therefore if we set a = sup{s ≤ w : σ(s) ∈ S} and b = inf{s ≥ w : σ(s) ∈ S} we have

σ([0, 1]) ∩ B(0, 1) ⊂ σ([a, b]) ⊂ B(0, √ d)
Finally we check the second item :

(b -a) σ 1 ≤ 3 2 b a σ ′ (u) du ≤ √ 3 b a σ ′ (u).σ ′ (w) σ ′ (w) du ≤ √ 3 b a σ ′ (u)du ≤ √ 3 σ(a) -σ(b) ≤ √ 3d
6. Reparametrization of (n, ǫ) Bowen balls : proof of the Reparametrization Lemma

Let M be a compact manifold of dimension d and let T : M → M be a C r map with r > 1. As in Yomdin theory, we consider the local dynamic at one point. We fix a Riemannian structure on M and we denote by R inj the radius of injectivity and by exp : T M (R inj ) → M the exponential map, where T M (r) := {(x, u), u ∈ T x M, u x < r}. We fix R < R ′ < R inj such that T (B(x, R)) ⊂ B(T x, R ′ ) for all x ∈ M . Let x ∈ M and n ∈ N. We consider the map T x n :

T T n-1 x M (R) → T T n x M (R ′ ) defined by T x n = exp -1 T n x • T • exp T n-1 x . For all ǫ < R √ d , we put T x n,ǫ = ǫ -1 T x n (ǫ.) : B(0, √ d) → T T n x M ≃ R d and T x ǫ := (T x n,ǫ ) n∈N .
Observe that for all small universal constant A there exists ǫ > 0 depending only on max s=min(2,r),3,...,[r],r D s T such that D s T x n,ǫ ≤ A -1 for all s = min(2, r), 2, ..., [r], r and n ∈ N. We extend the definition of H n T to this framework by defining for all 1-disks σ and for all real numbers χ > 0, γ > 0 and C > 1 the set :

H n T (σ, χ, γ, C) := t ∈ [0, 1] ∩ σ -1 B(n, √ d) : ∀1 ≤ i ≤ n, C -1 e (χ-γ)i ≤ D t T i • σ ≤ Ce (χ+γ)i
We define now subsets of the Bowen ball B(n+1, 1) where the defect of multiplicativity of the norm of the composition

DT i+1 • D(T i • σ) is prescribed at each step 1 ≤ i ≤ n. Definition 2. Let T := (T n ) n∈N be a sequence of C 1 maps from B(0, √ d) ⊂ R d to R d and let σ : [0, 1] → R d be a 1-disk of class C 1 . Let K n := (k 1 , .
.., k n ) be a sequence of n positive integers, we denote by H(K n ) the subset of σ -1 (B(n + 1, 1)) defined by :

(10) H(K n ) := t ∈ [0, 1] ∩ σ -1 (B(n + 1, 1)) : ∀1 ≤ i ≤ n, log + D t (T i • σ) max(1, D T i •σ(t) T i+1 ) D t (T i+1 • σ) + 1 = k i
In the next lemma we estimate as in [START_REF] Burguet | C 2 surface diffeomorphisms have symbolic extensions[END_REF] the numbers of such sets intersecting H n T (σ, χ, γ, C) by using the combinatorial argument of Lemma 4. We write λ + n :=

1 n n-1 i=0 log + D 0 T i .
When T is the sequence T x ǫ for some ǫ > 0 and x ∈ M we have λ

+ n = λ + n (x, T ) = 1 n n-1 i=0 log + D T i x T . If we assume (11) ∀n ∈ N ∀z, z ′ ∈ B(0, √ d), max( D z T n , 1) max( D z ′ T n , 1) ≤ 2 then we have for all y ∈ B(n, √ d) λ + n - 1 n n-1 i=0 log + D y T i ≤ log 2
The condition ( 11) is fulfilled as soon as the uniform norm of second derivative (or the r -1 Hölder norm when r < 2) of each T n is less than 1/ √ d. Under this condition we also notice that that for two points t, s lying in H(K n ) and satisfying 1 2

D t (T n • σ) ≤ D s (T n • σ) ≤ 2 D t (T n • σ) the derivative of T n+1
• σ at t and s have also almost the same size. More precisely we have

1 4e D t (T n+1 • σ) ≤ D s (T n+1 • σ) ≤ 4e D t (T n+1 • σ) (12)
This last remark will be used in the proof of Proposition 2. We state now the application of the combinatorial fact of Lemma 4.

David Burguet

Lemma 8. Let χ > 0, 1 3 > γ > 0 and C > 1 and let T := (T n ) n∈N be a sequence of C r maps from B(0, √ d) to R d such that max( DzTn ,1) max( D z ′ Tn ,1) ≤ 2 for all n ∈ N and for all z, z ′ ∈ B(0, √ d).

Then there exists an integer N depending only on C such that for all n > N and for all 1-disks σ : [0, 1] → R d of class C 1 the number of sequences K n-1 such that H(K n-1 ) has a non empty intersection with H n T (σ, χ, γ, C) is bounded above by

e 3n-2 e (n-1)(λ + n -χ)H([λ + n -χ]+3) Proof : Indeed if t ∈ H n T (σ, χ, γ, C), then n-1 i=0 log + D T i •σ(t) T i+1 -log D t (T n • σ) ≤ n(λ + n + log 2 -χ + γ) + log C. Thus the sequence log D t (T i • σ) max( D T i •σ(t) T i+1 , 1) D t (T i+1 • σ) + 1 i=1,...,n-1 admits the value [λ + n -χ] + 3 for n > log C 1-log 2-1 3
. We apply finally the combinatorial Lemma 4 to conclude the proof.

The Reparametrization Lemma follows now directly from Lemma 8 and the following Proposition 2 applied to the sequences T = T x ǫ for all x ∈ M and for ǫ > 0 small enough. Then for all integers n, for all 1-disks σ of class C r with max s=1,...,[r],r σ s ≤ 1 and for all sequences K n-1 = (k 1 , ..., k n-1 ) of n -1 positive integers there exists a family G n of affine maps φ n : [0, 1] → [0, 1] satisfying the following properties :

(i) ∀φ n ∈ G n , σ • φ n ([0, 1]) ⊂ B(n + 1, √ d), (ii) ∀φ n ∈ G n , ∀k = 0, ..., n, ∀s = 1, min(2, r), 3, ..., [r], r, T k • σ • φ n s ≤ 1, (iii) ∀φ n ∈ G n , ∀ min(1, r -1) ≤ s ≤ r -1, (T n • σ) ′ • φ n s ≤ 1 3 (T n • σ) ′ • φ n 0 , (iv) H(K n-1 ) ∩ σ -1 (B(n + 1, 1)) ⊂ φn∈Gn φ n ([0, 1]), (v) log ♯G n ≤ B + An + 1 r-1 n-1 i=1 k i , with B depending only on σ. When d = 1 it follows from the property (T n • σ) ′ • φ n min(1,r-1) ≤ 1 3 (T n • σ) ′ • φ n 0 that the derivative of T n • σ does not
vanish on the image of each φ n , which lies thus in a monotone branch of T n • σ. Therefore our result recovers the estimates on the number of monotone branches intersecting H(K n ) obtained in [START_REF] Downarowicz | Smooth interval maps have symbolic extensions[END_REF].

The main difference with the reparametrization result presented in [START_REF] Burguet | C 2 surface diffeomorphisms have symbolic extensions[END_REF] is the affine property of the reparametrization charts. Moreover, as these charts are in this paper one dimensional this makes much easier the proof because the changes of charts φ n+1 • φ -1 n are just affine maps of [0, 1]. Observe also that we do not assume any hyperbolicity condition on the reparametrized subset of the Bowen ball contrarily to Proposition 12 of [START_REF] Burguet | C 2 surface diffeomorphisms have symbolic extensions[END_REF].

The conditions on the reparametrization maps are stronger than in Yomdin theory where only (ii) is required. However we only consider here one dimensional disks -Yomdin's approach applies in any dimension -and we do not reparametrized the whole Bowen ball but only a subset with a fixed growth of the derivative.

Proof : We argue by induction on n. The initial step is easily checked. We assume the existence of the family G n and we build G n+1 . Let φ n ∈ G n . We cover the unit interval into [e kn r-1 ] + 1 subintervals of size e -kn r-1 . We reparametrize them from [0, 1] by affine contractions θ n+1 . We let ψ n+1 := φ n • θ n+1 . From now on we focus on maps ψ n+1 whose image intersects the set

H(K n ) ∩ σ -1 (B(n + 2, 1))
Fix such a map ψ n+1 and choose w ∈ [0, 1] such that ψ n+1 (w) belongs to the previous set. Let us first prove that

(T n+1 • σ) ′ • ψ n+1 r-1 ≤ 2 (T n+1 • σ) ′ • ψ n+1 (w)
To simplify the notations we write T ′ n+1 for the differential DT n+1 of T n+1 . Then, according to the chain rule derivative we have

(T n+1 • σ) ′ • ψ n+1 = T ′ n+1 • (T n • σ • ψ n+1 ) × (T n • σ) ′ • ψ n+1
By the induction hypothesis (iii) the s-norm of (T n • σ) ′ • ψ n+1 for min(1, r -1) ≤ s ≤ r -1 satisfies

(T n • σ) ′ • ψ n+1 s ≤ 1 3 θ n+1 s 1 (T n • σ) ′ • φ n 0
We consider now the first term T ′ n+1 • (T n • σ • ψ n+1 ) of the product. We first recall that

• for an integer β the β-derivative of a product or a composition of smooth functions is an universal polynomial in the α-derivatives of each term with integers α = 0, ..., β, • for a positive real number 0 < β ≤ 1 the β-Hölder norm f × g β of a product f g is less than or equal to f 0 g β + g 0 f β while the β-Hölder norm f • g β of a composition f • g is less than or equal to f β g β 1 . Therefore, by the induction hypothesis (ii), we have for all min(1, r -1) ≤ s ≤ r -1

T ′ n+1 • (T n • σ • ψ n+1 ) s ≤ C θ n+1
(T n+1 • σ) ′ • ψ n+1 r-1 ≤ 2 (T n+1 • σ) ′ • ψ n+1 (w) (13)
Now we apply Lemma 5 to the C r-1 map (T n+1 • σ) ′ • ψ n+1 with a = 4e (T n+1 • σ) ′ • ψ n+1 (w) . We let F ψ n+1 be the associated family of reparametrization maps. For any ξ n+1 ∈ F ψ n+1 we have in particular

(T n+1 • σ) ′ • ψ n+1 • ξ n+1 min(1,r-1) ≤ 1 3 (T n+1 • σ) ′ • ψ n+1 (w)
From now on we only consider the maps ξ n+1 ∈ F ψ n+1 such that the image of ψ n+1 • ξ n+1 meets H(K n ). Since (T n • σ) ′ • φ n min(1,r-1) ≤ 1 3 (T n • σ) ′ • φ n 0 which as seen earlier implies (T n • σ) ′ • φ n (t) ≤ 2 (T n • σ) ′ • φ n (s) for all t, s ∈ [0, 1] we have by the inequalities (12)

1 8e (T n+1 • σ) ′ • ψ n+1 (w) ≤ (T n+1 • σ) ′ • ψ n+1 • ξ n+1 0 ≤ 8e (T n+1 • σ) ′ • ψ n+1 (w)
Let η n+1 : [0, 1] → ξ n+1 ([0, 1]) ⊂ [0, 1] be an affine reparametrization of ξ n+1 ([0, 1]). It follows from the above Landau-Kolmogorov Inequality of Lemma 6 that for all min(1, r-1) ≤ s ≤ r -1 we have

(T n+1 • σ) ′ • ψ n+1 • η n+1 s ≤ C (T n+1 • σ) ′ • ψ n+1 • η n+1 0 + (T n+1 • σ) ′ • ψ n+1 • η n+1 r-1 ≤ C (T n+1 • σ) ′ • ψ n+1 • ξ n+1 0 + (T n+1 • σ) ′ • ψ n+1 r-1 ≤ C (T n+1 • σ) ′ • ψ n+1 (w) ≤ C (T n+1 • σ) ′ • ψ n+1 • η n+1 0
where the universal constant C may change at each step of the previous sequence of inequalities.

By dividing the unit interval into [3C] + 1 subintervals of size < 1/3C and by reparametrizing them affinely one can assume (

T n+1 • σ) ′ • ψ n+1 • η n+1 s ≤ 1 3 (T n+1 • σ) ′ • ψ n+1 • η n+1 0 .
Now for any map T n+1 • σ • ψ n+1 • η n+1 we let [a η n+1 , b η n+1 ] be the subinterval of [0, 1] given by Lemma 7. We reparametrize ψ n+1 • η n+1 | [aη n+1 ,bη n+1 ] from [0, 1] by an affine contraction to get new maps that we denote by φ n+1 , i.e. φ n+1 (t) := ψ n+1 • η n+1 a η n+1 + (b η n+1a η n+1 )t for all t ∈ [0, 1]. By construction the family G n+1 of affine maps φ n+1 satisfy properties (i) and (iv). Moreover, since the map ψ n+1 • η n+1 satisfies (iii) then so does φ n+1 . Therefore, we only need to check (ii) for the family G n+1 at step n + 1.

By Lemma 7 we have T n+1 • σ • φ n+1 1 ≤ √ 3d. It only remains to check (ii) for the family G n+1 at step n + 1 for the derivative of order min(2, r) ≤ s ≤ r. By using successively the affine property of φ n+1 , property (iii) and the above case s = 1, we have for min(2, r) ≤ s ≤ r :

T n+1 • σ • φ n+1 s = (T n+1 • σ) ′ • φ n+1 s-1 × φ n+1 1 ≤ 1 3 (T n+1 • σ) ′ • φ n+1 0 × φ n+1 1 ≤ 1 3 T n+1 • σ • φ n+1 1 ≤ d 3
As previously done we may suppose this last constant to be one, should we multiply the number of reparametrization maps by d 3 + 1. This concludes the proof of the lemma.

χ + 1 r- 1 .

 11 Remark that Theorem 1 stated in the introduction is the topological version of Theorem 4 : it is deduced by the usual variational principle for the entropy and the variational principle for the symbolic extension entropy (Equation (3)). According to the examples built in [20] the upper bound on the symbolic extension entropy function in Theorem 4 is sharp in the case of local surface diffeomorphism. More precisely S.Newhouse and T.Downarowicz exhibit examples of C r surface diffeomorphisms with r > 1 which admit an hyperbolic periodic measure γ p with h sex (γ p ) = χ + 1 (γp) r-1 . However the optimality of the upper bound in the general case is open.

From

  now on we consider a general sequence T := (T n ) n∈N of C r maps with r > 1 from B(0, √ d) ⊂ R d to R d with T n (0) = 0 for all n ∈ N. By convention we set T 0 = Id| B(0, √ d) . For each n ∈ N we denote by T n the composition T n • ... • T 0 defined on B(n, √ d) where B(n, ρ) is the Bowen ball centered at 0 of length n and size ρ > 0, i.e. B(n, ρ) := {y ∈ R d : ∀k = 0, ..., n -1, T k y < ρ}.

Proposition 2 .

 2 Let T := (T n ) n∈N be a sequence of C r maps with r > 1 from B(0, √ d) ⊂ R d to R d with sup n∈N T ′ n < +∞ and sup n∈N, 2≤s≤rT n s ≤ A -1 where A is a universal constant depending only on r and d which we specify later on in the proof.

-1 1 (

 1 where C is a constant depending only on r and d. Finally we get by replacing this constant by another one which we denote again by C :(T n+1 • σ) ′ • ψ n+1 r-1 ≤ θ n+1 rT n • σ) ′ • φ n 0 1 3 T ′ n+1 • (T n • σ • ψ n+1 ) 0 +C sup min(2,r)≤k≤r T n+1 k ≤ e -kn (T n • σ) ′ • φ n 0 max( T ′ n+1 0 ,But it follows from the induction hypothesis (iii) with s = min(1, r -1) that(T n • σ) ′ • ψ n+1 (w) ≥ 2 3 (T n • σ) ′ • φ n 0and we can choose the constant A large enough to ensure firstlyC sup p∈N, min(2,r)≤k≤r T p k ≤ CA -1 ≤ 1 3and secondly for all x ∈ B(0, √ d)max( T ′ n+1 0 , 1) ≤ 2 max(1, T ′ n+1 (x) ) Therefore we have (T n+1 • σ) ′ • ψ n+1 r-1 ≤ 2 3 e -kn (T n • σ) ′ • φ n 0 max( T ′ n+1 0 , 1) ≤ e -kn (T n • σ) ′ • ψ n+1 (w) max( T ′ n+1 0 , 1) ≤ 2e -kn (T n • σ) ′ • ψ n+1 (w) max( T ′ n+1 (T n • σ • ψ n+1 (w)) , 1) and since ψ n+1 (w) belongs to H(K n ) we obtain


Solen Quiniou
email: solen.quiniou@irisa.fr

Éric Anquetil
email: eric.anquetil@irisa.fr

Sabine Carbonnel
email: sabine.carbonnel@irisa.fr

Statistical Language Models for On-line Handwritten Sentence Recognition

This paper investigates the integration of a statistical language model into an on-line recognition system in order to improve word recognition in the context of handwritten sentences. Two kinds of models have been considered: n-gram and n-class models (with a statistical approach to create word classes). All these models are trained over the Susanne corpus and experiments are carried out on sentences from this corpus which were written by several writers. The use of a statistical language model is shown to improve the word recognition rate and the relative impact of the different language models is compared. Furthermore, we illustrate the interest to define an optimal cooperation between the language model and the recognition system to re-enforce the accuracy of the system.

Introduction

The emergence of new devices such as PDA's and Tablet PC's allows users to write larger pieces of texts. Handwriting recognition systems can thus take advantage of the linguistic context of a word to improve their accuracy. This paper focus on the impact of language models in an on-line handwriting recognition system where word recognition has already been addressed [START_REF] Carbonnel | Lexical Post-Processing Optimization for Handwritten Word Recognition[END_REF].

The technique the most frequently used in handwriting recognition to incorporate linguistic knowledge comes from speech recognition. In this field, statistical language models (often n-gram models) are the most commonly applied [START_REF] Jelinek | Statistical Methods for Speech Recognition[END_REF].

Several works in off-line handwritten sentence recognition make use of language models [START_REF] Marti | Using a Statistical Language Model to Improve the Performance of an HMM-Based Cursive Handwriting Recognition System[END_REF][START_REF] Zimmermann | N-Gram Language Models for Offline Handwritten Text Recognition[END_REF][START_REF] Vinciarelli | Offline Recognition of Unconstrained Handwritten Texts using HMMs and Statistical Language Models[END_REF]. The bigram model used in [START_REF] Marti | Using a Statistical Language Model to Improve the Performance of an HMM-Based Cursive Handwriting Recognition System[END_REF] was built on the Lancaster-Oslo/Bergen (LOB) corpus and was shown to decrease the word error rate by 25.7%. In [START_REF] Vinciarelli | Offline Recognition of Unconstrained Handwritten Texts using HMMs and Statistical Language Models[END_REF] the relative influence of unigram, bigram and trigram language models is investigated. The bigram model was shown to outperform the unigram model while the trigram one didn't lead to further improvements, in terms of perplexity as well as of word recognition rate. Whereas the influence of language models and of word recognition system outputs were the same in these works, the weight of the language model against the recognition system is optimized in [START_REF] Zimmermann | N-Gram Language Models for Offline Handwritten Text Recognition[END_REF]. The word error rate is thus decreased by 47.4% with a bigram model and by 54.4% with a trigram one (leading to a 81.8% word recognition rate).

In on-line recognition of handwritten sentences, the use of n-gram language models is quite recent [START_REF] Perraud | N-Gram and N-Class Models for On Line Handwriting Recognition[END_REF][START_REF] Marukatat | Sentence Recognition through Hybrid Neuro-Markovian Modeling[END_REF]. In [START_REF] Perraud | N-Gram and N-Class Models for On Line Handwriting Recognition[END_REF] a combination of a statistical bi-class model with 500 classes and a syntactical biclass model with 210 POS tags (Part Of Speech tags) was used to reorder N-best sentence hypotheses. This model even outperformed a bigram model since respective decrease in word error rates were 33.8% and 32.4% (the word recognition rate for the combined biclass model being 77.5%). Furthermore, this combined model was shown to be more compact than the bigram one. In [START_REF] Marukatat | Sentence Recognition through Hybrid Neuro-Markovian Modeling[END_REF], the use of bigram models (created on different corpuses) is investigated. The bigram model built on the test set achieves a 50% reduction in the word error rate (corresponding to a 85.1% word recognition rate) whereas it leads to a decrease of 15.1% when built on the Susanne corpus. The decrease is lower with the model built on the Susanne corpus since this corpus doesn't fit with the test sentences.

Since we deal with on-line recognition on potentially low memory devices, a particular attention is paid on the size of the models. According to this constraint we study the integration of different language models (n-gram and n-class models) and compare their performance and compactness. We also focus on an optimal cooperation between the language model and the recognition system by highlighting the impact of a language weight. Section 2 explains the recognition problem in a statistical way while section 3 describes the language modeling used. An overview of the recognition system is given in section 4 and the integration of language models are related in section 5. Finally, section 6 draws some conclusions.

Sentence recognition problem

The aim of sentence recognition is to find the most likely sequence of words Ŵ between candidate sequences W given a signal S (the handwritten sentence to recognize):

Ŵ = arg max W p(W |S). ( 1
)
By applying a Maximum A Posteriori (MAP) approach, equation 1 can be rewritten as:

Ŵ = arg max W p(S|W ) p(W ) (2)
where p(S|W ) is the a posteriori probability of the signal S for the given sentence W and is estimated by the recognition system often based on HMM's (we call this term graphical model); p(W ) is the a priori probability of the sequence W , often given by a statistical language model. Since these probabilities are small, their decimal logarithms are used instead. Furthermore, a language weight γ (also called Grammar Scale Factor) is introduced in order to balance the influence of the language model against the graphical model. Consequently equation 2 becomes:

Ŵ = arg max W log [p(S|W )] + γ log [p(W )] . (3)

Statistical language modeling

Statistical language modeling aims at capturing regularities of a language by use of statistical inference on a corpus of that language [START_REF] Manning | Foundations of Statistical Natural Language Processing[END_REF]. The a priori probability of a sentence W = w n 1 = w 1 . . . w n of n words is thus given by:

p(W ) = n i=1 p(w i |h i ) (4)
where

h i = w 1 . . . w i-1 is called history of word i.
The main problem with equation 4 is the high number of histories leading to a tremendous number of probabilities to estimate. Furthermore, most of these probabilities occur too few times to be estimated reliably. A solution to issue this problem is to merge histories in equivalence classes:

p(W ) = n i=1 p(w i |h i ) = n i=1 p(w i |Φ i (h i )) (5)
where Φ i (h i ) assigns to history h i its equivalence class. There are several techniques to define Φ i (h i ), the simplest one being n-gram language models.

N -gram language models

N -gram language models merge histories ending with the same n-1 words, in equivalence classes:

p(W ) = n i=1 p(w i |w i-1 i-n+1 ). (6)
The probability p(w i |w i-1 i-n+1 ) given by equation 6 is the relative frequency of the sequence w i i-n+1 in a corpus: [START_REF] Manning | Foundations of Statistical Natural Language Processing[END_REF] where N (.) stands for the number of occurrences of a certain event. One problem with this approach is that the model fits to the training corpus and probabilities of non-occurring n-grams (i.e. sequences of n words) are estimated to zero.

p(w i |w i-1 i-n+1 ) = N (w i i-n+1 ) w i-1 i-n+1
One solution to issue this is called smoothing. It first reduces probabilities of n-grams occurring in the corpus, then redistributes this mass of probabilities among n-grams never encountered. Among different smoothing techniques we chose the Kneser-Ney modified interpolated method, shown in [START_REF] Chen | An Empirical Study of Smoothing Techniques for Language Modeling[END_REF] to be very efficient. Nonetheless one limit of this approach is that non-zero probabilities will be assigned to n-grams impossible from a linguistic point of view.

N -class language models

For their part, n-class models merge words in classes. In that case, the probability of a word is based on its class and on those of the previous words:

p(w i |w i-1 i-n+1 ) = p(w i |C i ) p(C i |C i-1 i-n+1 ) (8)
where p(w i |C i ) is the probability of the word w i in its class

C i and p(C i |C i-1 i-n+1
) is the probability of the class C i to occur given the history of classes C i-1 i-n+1 . There are two main approaches to create word classes. They can correspond to defined categories which are often the grammatical nature of words (i.e. POS tags). Classes can also be created by a statistical approach which merge words that share the same context. We consider only the latter here and classes are created with the incremental version of the Brown algorithm [START_REF] Brown | Class-Based N-Gram Models of Natural Language[END_REF].

Quality of a model

The quality of a language model is measured in terms of perplexity (PP) [START_REF] Manning | Foundations of Statistical Natural Language Processing[END_REF]:

P P = 2 H ( 9
)
where

H = 1 n i p(w i |h i
) is an estimation of the entropy of the model (measured over a text). Intuitively the perplexity can be viewed as the average number of words among which w i has to be chosen knowing history h i .

The quality of a recognition system is measured in terms of word recognition rate but since no relationship is clearly established between perplexity and word recognition rate [START_REF] Jelinek | Statistical Methods for Speech Recognition[END_REF], the language model with the lowest perplexity doesn't necessarily lead to the highest word recognition rate.

After presenting statistical language modeling, we describe the overall recognition system. We then focus on the integration of word language models into this system.

Overview of the on-line handwriting recognition system

Word recognition level

Our on-line word recognition system RESIFMot [START_REF] Carbonnel | Lexical Post-Processing Optimization for Handwritten Word Recognition[END_REF] is based on an analytic approach which segments the words according to different hypotheses of letter allographs (see figure 1). The system realizes a physical segmentation based on singularities detection in the signal which provides several logical segmentation hypotheses. Words are then segmented according to different allographs. These allograph hypotheses are organized in a segmentation graph representing all the possible segmentations. An adapted version of our character recognition system RESIFCar [START_REF] Anquetil | Integration of an On-line Handwriting Recognition System in a Smart Phone Device[END_REF] is used afterwards to validate the coherent segmentation hypotheses and to identify each allograph hypothesis.

The output of the system is an ordered list of character strings resulting of the segmentation graph exploration. The results are ranked according to the adequation measure between allographs and letter models, the spatial coherence between two allographs and character n-gram probabilities.

The lexical post-processing is finally used to retrieve the nearest word of these results in a dictionary [START_REF] Carbonnel | Lexicon Organization and String Edit Distance Learning for Lexical Post-Processing in Handwriting Recognition[END_REF]. The output of this post-processing is an ordered list of candidate words.

Sentence recognition level

Figure 2 describes the structure of the sentence recognition system. Every handwritten word of the segmented sentence is given as an input of the word recognition system which outputs an ordered list of candidate words associated with a likelihood depending on the lexical post-processing. A word graph is then created with these lists. In that graph, each node represents a (n-1)-gram w i-1 i-n+1 (and is valuated by the likelihood of word w i-1 ) and each edge from node n 1 to node n 2 (respectively representing (n-1)-grams w i-1 i-n+1 and w i i-n+2 ) is valuated by the language model probability p(w i |w i-1 i-n+1 ). This syntactical post-processing step is performed with the Viterbi search algorithm which finds the best path in the graph (corresponding to the likeliest sentence), using word likelihoods and n-gram probabilities as given by equation 3.

Language model integration: experiments and results

Corpus and data acquisition

The language models (character and word based) and the lexicon were extracted with the SRILM toolkit [START_REF] Stolcke | SRILM -An Extensible Language Modeling Toolkit[END_REF] from the Susanne corpus [START_REF] Sampson | English for the Computer: The Susanne Corpus and Analytic Scheme[END_REF]. This corpus contains 6,895 sentences (129,460 words); the vocabulary was closed over it and includes 14,392 words.

The handwritten material consists of unconstrained sentences from the Susanne corpus which were written on a Tablet PC by several different writers (figure 3 shows some written words). The sentences were segmented manually into words in order to evaluate the influence of a language model without any bias brought by uncorrect segmentation. We first present the influence of the language weight when a language model is integrated into the recognition system. Then we compare bigram and trigram models to each other and finally biclass and triclass models as well.

Influence of the language weight

Equation 3 combines information from word recognition system and language model in the probabilistic case. Since our system is not probabilistic but gives to a handwritten word a likelihood to be the word we want to recognize, we use an approximation of this equation.

For now the optimal value of the language weight γ is set empirically. Figure 4 shows the evolution of the word recognition rate as a function of γ. The two curves (corresponding to bigram and trigram language models) shows a comparable behavior and the optimal value of γ is near 0.3 (the relative impact of both models is not the point here and would be presented in section 5.3). Furthermore, we can see the importance of this weight since the word recognition rate is 86.3 % with the bigram model when γ=1 (graphical and language models have the same impact) whereas it is 90.3 % with the optimal value of γ.

Bigram model vs trigram model

Here the influence of bigram and trigram models on the recognition is compared to the baseline system (i.e. without language model). Table 1 presents perplexity of both models as well as word recognition rate (also given for the baseline system). The decrease in perplexity from bigram to trigram models is not very important. The same conclusion can be drawn from word recognition rate, showing here a correlation of these two indicators. The fact that the trigram model doesn't perform a significant improvement can be explain by the small amount of trigrams in the test set which are effectively estimated in the model (4.4 %). The influence of a language model is thus shown since the reduction of word error rate is 44.6 % for the bigram model and 45.1 % for the trigram one (compared to the baseline system). In fact, words whose benefit is the highest are small functional words (e.g. 'for', 'to', 'the'. . . ).

N -class models: optimizing the number of classes

We investigated here the use of statistical classes. First we focus on the optimal number of classes and then we compare these models to n-gram models, especially in terms of numbers of parameters.

Figure 5 gives the word recognition rate for biclass and triclass models considering different number of classes (the rate for bigram and trigram models are also reminded). We can see that even with 50 classes, the word recognition rate is 88.2 % which is pretty close to the rate obtained with the bigram model. One interesting observation is that the biclass model with 400 classes achieves the same recognition rate than the bigram model (the same conclusion can be drawn from the triclass model with 400 classes and the trigram one). One explanation of that lies in the generalization power of word class clustering. This is particularly benefical when the amount of training data is too small to estimate reliably n-grams probabilities. Apart from its generalization power, one advantage of nclass models is their compacity. Because words are grouped in classes, the number of n-class probabilities is lower than those of n-grams. These probabilities correspond to the parameters of the system (in the case of n-class models, these parameters also include probabilities of words in their classes). Table 2 shows the word recognition rate and the number of parameters for some biclass and triclass models and for the bigram and trigram ones. As can be seen, for the same word recognition rate the biclass model with 400 classes has twice as less parameters as the bigram model (so is the triclass model over the trigram one). Furthermore, with about 16,000 parameters the biclass model with 50 classes achieves an already good word recognition rate.

Conclusion

This paper investigates the integration of a statistical language model in a handwritten sentence recognition system. Considering language models built on the Susanne corpus which is relatively small (6,895 sentences and 129,460 words), the results of the experiments show that while a bigram model significantly decreases the word error rate, no further improvements are obtained with a trigram model. We also addresses the use of statistical biclass and triclass models which are interesting because of their compactness.

An optimal language weight was shown to be important. For now this weight is chosen empirically but further work will concern a better combination between the recognition system and the language model based on an automatic supervised learning. Moreover other information provided by the word recognition system could also be integrated in the computation of word likelihoods (e.g. adequation between the word and its graphical shape). Concerning n-class models, only a statistical approach for their creation has been considered and the use of syntactical classes will be explored as well as the combination of both types of classes. Finally, it will be interesting to evaluate the impact of models built on larger corpuses on the recognition accuracy.

Figure 1 .

 1 Figure 1. Word recognition system.

Figure 2 .

 2 Figure 2. Sentence recognition system.

  Each writer wrote 20 sentences and shares the first 10 (150 words) with the other writers while the latest 10 were chosen randomly in a set of 109 sentences (1,770 words). The training set includes 138 sentences (2,217 words) written by 7 writers and the test set 80 sentences(1,196 words) written by 4 writers independent from those of the training set. All sentences of both sets were excluded from the corpus used for the construction of the language models.

Figure 3 .

 3 Figure 3. Sample words from the base.

Figure 4 .

 4 Figure 4. Evolution of the word recognition rate over bigram and trigram models weights.

Figure 5 .

 5 Figure 5. Evolution of the word recognition rate over the number of classes.

Table 1 . Comparison of bigram and trigram models.

 1

		Bigram Trigram Baseline
	Perplexity	279.4	268.5	-
	Word rec. rate 90.3 % 90.4 %	82.5 %

Table 2 . Comparison of biclass, triclass, bi- gram and trigram models.

 2 Word rec. rate 88.2 % 90.3 % 90.4 % 90.3 % 90.4 % Nb. of param. 16,105 41,112 54,335 86,054 91,882

	Biclass Biclass Triclass Bigram Trigram
	(50) (400) (400)