Ai-Hua Fan

AND J Örg Schmeling

Serge Troubetzkoy

DYNAMICAL DIOPHANTINE APPROXIMATION

come

A multifractal mass transference principle for Gibbs measures with applications to dynamical Diophantine approximation

Introduction

Let (X, d) be a complete metric space. Given a sequence {x n } n≥1 of points in X and a sequence {r n } n≥1 of positive numbers we define I({x n }, {r n }) : = lim n→∞ B(x n , r n ), F ({x n }, {r n }) : = X \ I({x n }, {r n }) where B(x n , r n ) denotes the ball of center x n with radius r n . By diophantine approximation we mean the study of the sets I({x n }, {r n }) and F ({x n }, {r n }).

Classic diophantine approximation is a special case. Let X = S 1 = R/Z be the unit circle equipped with the metric

x -y = inf k∈Z |(x -y) -k|.
Let {x n } = {nα (mod 1)} be the orbit of the irrational rotation determined by an irrational number α. Then 0 ∈ I({nα}, {r n }) means αn < r n holds for an infinite number of n's. This is nothing but the homogeneous diophantine approximation of α. More generally y ∈ I({nα}, {r n }) means αny < r n holds for an infinite number of n's. This is what is called inhomogeneous diophantine approximation. In [FS], based on the results in [ST], both I({nα}, {r n }) and F ({nα}, {r n }) have been analyzed for an irrational number α when r n = n -κ . The case for general sequence {r n } has been studied in [START_REF] Fan | A note on inhomogeneous diophantine approximation with a general error function[END_REF].

Another special case is the dynamical Borel-Cantelli lemma or shrinking target problem. Consider a measure preserving map T . A shrinking target is a sequence of balls with decreasing radius and with centers fixed or moving (more generally, other forms than balls are also allowed). The question is to study the set of orbits T n x (or equivalently of the initial points) which hit the target or equivalently which are well approximated by the target, see for example [HV] and the references therein.

There is another well studied case. Consider an i.i.d. sequence {x n } ⊂ S 1 uniformly distributed on the unit circle S 1 with respect to Lebesgue measure, a decreasing sequence of positive numbers {ℓ n } ⊂ R + and the associated random intervals (x n -ℓ n /2 (mod 1), x n +ℓ n /2 (mod 1)) (i.e. r n = ℓ n /2 in the above terminology). Since {x n } are independent and uniformly distributed, the Borel-Cantelli Lemma assures that almost surely (a.s. for short) we have I({x n }, {r n }) = S 1 except for a set of null Lebesgue measure, i.e. Lebesgue a.e. point in S 1 is covered infinitely often by the intervals with probability one if and only if ∞ n=1 ℓ n = ∞. Moreover ∞ n=1 ℓ n < ∞ implies that Lebesgue a.e. point in S 1 is covered finitely often with probability one. In 1956, Dvoretzky observed the possibility that all points in S 1 are covered infinitely often with probability one for some slowly decreasing sequence {ℓ n } [D]. In 1972, Shepp obtained a necessary and sufficient condition for all points in S 1 to be covered infinitely often with probability one [Sch]:

∞ n=1 1 n 2 exp(ℓ 1 + • • • + ℓ n ) = ∞.
This condition is satisfied for example by ℓ n = 1 n . Important contributions were made by J.P. Kahane, P. Billard, P. Erdós, S. Orey, B. Mandelbrot et al. See Kahane's book [K] for a full history and a complete reference up to 1985 and see [START_REF] Barral | Covering numbers of different points in Dvoretzky and Poisson coverings[END_REF][START_REF] Fan | How many intervals cover a point in Dvoretzky Covering?[END_REF][START_REF] Fan | Some topics in the theory of multiplicative chaos[END_REF][START_REF] Fan | Raret des intervalles recouvrant un point dans un recouvrement aleatoire[END_REF][START_REF] Fan | On the covering by small random Intervals[END_REF][START_REF] Jonasson | Dynamical models for circle covering: Brownian motion and Poisson updating[END_REF] for more recent developments.

In the present work, we consider the dynamics defined by the angle doubling map on the circle. We shall consider a generic orbit {x n } = {T n x} of this map relative to a Gibbs measure. Recall that the doubling map T : S 1 → S 1 is defined by T s = 2s (mod 1).

We are interested in the quantity

T n x -y = 2 n x -y < r n .
This is diadic diophantine approximation, homogeneous in the case y = 0 and inhomogeneous in the case y = 0. The sets I({x n }, {r n }) and F ({x n }, {r n }) are respectively the sets of y which are well aproximable or badly approximable with speed r n . In other words I is the set of points obeying a diophantine equation with speed r n . Our theorems are similar to Jarnik type results in number theory. For κ > 0 consider the special sequence r n = 1 n κ . Write J κ n (s) = (T n sr n (mod 1), T n s + r n (mod 1)). For s ∈ S 1 let

I κ (s) := ∞ N =1 ∞ n=N J κ n (s) = t ∈ S 1 : ∞ n=0 1 J κ n (s) (t) = ∞ , F κ (s) := ∞ N =1 ∞ n=N J κ n (s) c = t ∈ S 1 : ∞ n=0 1 J κ n (s) (t) < ∞ .
The following decomposition is obvious:

S 1 = F κ (s) ∪ I κ (s), F κ (s) ∩ I κ (s) = ∅.
It is easy to see by definition that if the orbit of s is dense, then I κ (s) is a residual set, in particular, I κ (s) = ∅. It is the case for a typical point s relative to an ergodic measure with full support. However, as we will see, it is possible for F κ (s) = ∅ for typical points. Let ν φ , ν ψ be two Tinvariant probability Gibbs measures on S 1 associated to normalized Hölder potentials φ and ψ (i.e. the pressures of φ and ψ are equal to zero). The measure ν φ will be used to describe the randomness and the measure ν ψ to describe sizes of sets. Let κ φ,ψ,S 1 : = sup {κ : ν ψ (I κ (s)) = 1 for ν φa.e. s} , κ F φ,S 1 : = sup {κ : F κ (s) = ∅ for ν φa.e. s} . We are interested in the following questions:

(Q1) How to determine the critical value κ φ,ψ ? More precisely when is I κ (s) of full ν ψ -measure for ν φ -almost every s?

(Q2) How to determine the critical value κ F φ,S 1 ? More precisely when is I κ (s) equal to S 1 for ν φ -almost every s ?

(Q3) What are the Hausdorff dimensions dim H (F κ (s)), dim H (I κ (s)) for ν φ -almost every s ?

Our answers to these questions are stated in the following theorems. Let

e -= inf ν:invariant (-φ)dν, e max = (-φ)dLeb, e + = sup ν:invariant (-φ)dν
where e -and e + are respectively the minimal and maximal local entropy of ν φ . Let E(t) be the entropy spectrum of ν φ , which is defined by

E(t) = dim H y : lim r→o log ν φ ((y -r, y + r)) log r = t .
It is well known that E(t) is continuous on [e -, e + ], strictly concave and real analytic in (e -, e + ) (see [P]).

Theorem 1.1. The critical value κ φ,ψ,S 1 satisfies

κ φ,ψ,S 1 = 1 (-φ)dν ψ .
Notice that the integral (-φ)dν ψ is nothing but the conditional entropy of ν φ relative to ν ψ . The theorem says that for ν φ -a.e s the set I κ (s) supports the Gibbs measure ν ψ if κ is small enough so that (-φ)dν ψ < 1 κ . Also notice that for fixed s, the question whether ν ψ (I κ (s)) = 1 is the shrinking target problem or dynamical Borel-Cantelli lemma (see [HV]).

Theorem 1.2. The critical value κ F φ,S 1 satisfies

κ F φ,S 1 = 1 e + .
The theorem says that if κ is so small that e + < 1 κ , then I κ (s) = S 1 or equivalently F κ (s) = ∅ for ν φ -a.e. s. This is the counterpart of the Kahane-Billard-Shepp condition for the random Dvoretzky covering.

Theorem 1.3. For ν φ -a.e. s we have

dim H F κ (s) = 1 if 1 κ ≤ e max E( 1 κ ) if 1 κ > e max .
Theorem 1.4. For ν φ -a.e. s we have

dim H I κ (s) =      1 κ if 1 κ ≤ h ν φ E( 1 κ ) if h ν φ < 1 κ < e max 1 if 1 κ ≥ e max .
We will transfer the problem to a similar one in a symbolic framework. As we shall see, our problem is closely related to hitting times and the later is related to local entropy.

The structure of the article is as follows. We start in section 2 with background on ergodic theory, symbolic dynamics, decay of correlations, and multi-fractal analysis. In this section we prove a "multi-relation" and a variational principal which are essential in the proofs of the main results. In section 3 we transfer the covering problem to the symbolic setting and relate then covering properties to hitting time asymptotic. In section 4 we prove a first simple relation between hitting times and local entropy. This yields the proof of the Ornstein-Weiss return time theorem in the special case of Gibbs measures and also allows us the determine the critical exponent κ φ,ψ . For the other exponents more sophisticated estimates are needed. Sections 5 and 6 contain the core estimates on the probabilities of hitting time events. The fundamental tools relating hitting times to the entropy spectrum are developed. In section 7 we study the structure of a short typical sequence.

In particular we make a substantial improvement in the mass transference principle [BV] to multi-fractal Gibbs states. Section 8 contains the results in the symbolic framework for the full shift while section 9 generalizes these results to subshifts of finite type. Finally in section 10 we prove the main theorems by transferring them from the shift space.

Background

Convention. All logarithms and exponential functions in this article are taken to base 2. With this convention the notions of entropy and dimension coincide in our setup.

Ergodic theory. We need various standard definitions from ergodic theory: the metric entropy of an invariant measure ν denoted by h ν , the notion of the Gibbs measure µ φ with respect to a potential φ and the topological entropy for non compact sets E denoted by h top (E). The definitions of all these notions can be found in [P].

Symbolic dynamics. We use various standard notions from symbolic dynamics. Let (Σ + 2 , σ) denote the one sided full shift on two symbols 0, 1. For y = (y i ) i≥0 ∈ Σ + 2 we denote a cylinder set by

C n (y) := [y 0 , y 1 , • • • , y n-1 ].
We will denote the length of the cylinder by |C n (y)| = n. We will denote by

π(y) = ∞ i=0 y i 2 i+1
the natural projection from Σ + 2 to S 1 . We consider the 1 2 -metric on Σ + 2 , i.e. for x, y ∈ Σ + 2 let d(x, y) = 1 2 n where n is the least integer such that x n = y n . The pull back of the circle metric ρ(x, y)

:= ∞ i=0 |x i -y i | 2 i+1 is almost equiv- alent in the sense that for x ∈ Σ + 2 the ratio diam ρ (C n (x))/ diam d (C n (x)
) is bounded from below and above uniformly in n and x. Thus Hausdorff dimensions do not change under the projection, for details see [S1]. We denote by µ max the measure of maximal entropy for the shift. The projection of µ max is the Lebesgue measure on the circle.

Fast decay of correlation.

One of the key tools in our study is fast decay of correlations. This is related to Ruelle's theorem on transfer operators. Recall that for a α-Hölder

potential φ : Σ + 2 → R, i.e. [φ] α := sup x,y |φ(x) -φ(y)|/d(x, y) α < ∞,
the transfer operator associated to φ is defined as follows

L φ f (x) = σy=x e φ(y) f (y).
This operator acts on the space of continuous functions C(Σ + 2 ) equipped with the supremum norm f ∞ and on the space of α-Hölder continuous functions H α (Σ 2 ) equipped with the Hölder norm

|f | := f ∞ + [f ] α .
The well known Ruelle theorem asserts that [Ru] (i) The spectral radius λ > 0 of L φ : H α → H α is an eigenvalue with an strictly positive eigenfunction h and there is a probability eigenmeasure ν for the adjoint operator L * φ , i.e. L * φ ν = λν. (ii) Choose h such that h, ν := hdν = 1. There exist constants c > 0 and 0 < β < 1 such that for any f ∈ H α we have

(2•1) λ -n L n φ f -f, ν h ≤ cβ n |f |. Let P (φ) =
log λ and call it the pressure of φ. The measure µ := hν, denoted by µ φ , is the so-called Gibbs measure associated to φ. Assume that φ is normalized, that is to say λ = 1. The Gibbs measure µ has the Gibbs property: there exists a constant γ > 1 such that

(2•2) 1 γ e Snφ(x) ≤ µ(C n [x]) ≤ γe Snφ(x)
holds for all x ∈ Σ 2 and all n ≥ 1 where

S n f (y) := n-1 j=0 f (σ j y).
The Gibbs property (2•2) implies the following quasi-Bernoulli property of µ φ : for any two cylinders A and B we have

(2•3) 1 γ 3 µ φ (A)µ φ (B) ≤ µ φ (A ∩ σ -|A| B) ≤ γ 3 µ φ (A)µ φ (B).
For the first inequality take a point x ∈ A ∩ σ -|A| B. By using three times the Gibbs property we get

µ φ (A ∩ σ -|A| B) ≥ 1 γ 2 S |A| φ(x)+S |B| (σ |A| x) ≥ 1 γ 3 µ φ (A)µ φ (B).
This quasi-Bernoulli property can be generalized in the following way.

Theorem 2.1 (Multi-relation). Let µ = µ φ be the Gibbs measure associated to a Hölder potential function φ. Let ω > 1 be a sufficiently large number.

For any cylinder D 0 and any finite number of cylinders D 1 , . . . , D k of length n we have

(2•4) γ -3 (1 -cβ n )) k ≤ µ D 0 ∩ k j=1 σ -[n 0 +j(n+d)] D j k j=0 µ(D j ) ≤ γ 3 (1 + cβ n )) k
where n 0 ≥ |D 0 | and d = d(n) : ⌊ωn⌋ (⌊a⌋ denoting the integral part of a real number a).

Proof. First remark that

D 0 ∩ k j=1 σ -[n 0 +j(n+d)] D j = D 0 ∩ σ -|D 0 | B where B = k j=1 σ -[n 0 -|D 0 |+j(n+d)] D j
is a finite union of disjoint cylinders, which we denote by B i 's. Applying the quasi-Bernoulli property (2•3) to A = D 0 and B = B i we get

1 γ 3 µ φ (D 0 )µ φ (B i ) ≤ µ φ (D 0 ∩ σ -|D 0 | B i ) ≤ γ 3 µ φ (D 0 )µ φ (B i ).
Sum over all B i 's and we get

(2•5) 1 γ 3 µ φ (D 0 )µ φ (B) ≤ µ φ (D 0 ∩ σ -|D 0 | B) ≤ γ 3 µ φ (D 0 )µ φ (B).
Notice that the invariance of µ φ implies

µ φ (B) = µ φ k j=1 σ -[(j-1)(n+d)] D j .
Combining this with the equation (2•5), it suffices to prove

(2•6) (1 -cβ n )) k ≤ µ k j=1 σ -[(j-1)(n+d)] D j k j=1 µ(D j ) ≤ (1 + cβ n )) k .
Actually we can prove a little more. For simplicity, we will use Ef to denote the integral f dµ and write f 1 = f L 1 (µ) . From the inequality

|E(f • σ n • g)| = |E(f • L n g)| ≤ L n g ∞ f 1
(applied to g -Eg and f ) and Ruelle's theorem, we deduce that for nonnegative Hölder functions g and f we have

1 -c β n |g -Eg | Eg ≤ E(f • σ n • g) Ef Eg ≤ 1 + c β n |g -Eg | Eg .
Inductively, for a finite number of functions

g 1 , • • • , g k ∈ H α and for integers 0 = n 1 < n 2 < • • • < n k we have k-1 j=1 1 -c β n j+1 -n j |g j -Eg j | Eg j ≤ E k j=1 g j • σ n j k j=1 Eg j ≤ k-1 j=1 1 + c β n j+1 -n j |g j -Eg j | Eg j .
To get (2•6), we apply these inequalities to characteristic functions of cylinders g j = 1 D j . In fact, since all cylinders D j have the same length n, we have

|g j | = 1 + 2 αn , 1 Eg j = 1 µ(D j ) ≤ γ2 n maxx(-φ(x))
(the inequality is a consequence of the Gibbs property). Take d := ⌊ωn⌋ with a sufficiently large ω so that β ω 2 α+max(-φ) < 1. Take n j such that n 1 = 0 and n j+1n j = n + d for j ≥ 2 and the equation (2•6) follows.

We will refer to this inequality as the multi-relation property of the Gibbs measure µ φ .

Multi-fractal analysis.

Furthermore we will use various notions from multi-fractal analysis which can also be found in the reference [P]. The notion of Hausdorff dimension of a set will be denoted by dim H . For a point y ∈ Σ + 2 and an invariant measure ν we denote the lower local entropy of ν at y by

(2•7) h ν (y) := lim n→∞ - 1 n log ν(C n (y)).
We define the local entropy h ν (y) if the limit exists. For a function f : Σ + 2 → R we denote the ergodic sum by

S m f (y) := m-1 j=0 f (σ j y).
We denote a Gibbs measure with respect to a Hölder potential φ by µ φ .

Without loss of generality we may assume that the potential is normalized so that its pressure P (φ) = 0. Then

(2•8) h µ φ (y) = -lim n→∞ 1 n S n φ(y)
and h µ φ (y) satisfies a similar relation when the limit exists. If ν is an ergodic invariant measure then for ν a.e. y h µ φ (y) = -

Σ + 2 φ dν.
Furthermore if ν is another Gibbs measure µ ψ then for µ ψ a.e. y

(2•9)

h µ φ (y) = -P ′ (ψ + tφ)| t=0 .
Multi-fractal analysis deals with the study of the entropy spectrum

E(t) := E -φ (t) := h top y : h µ φ (y) = t .
The following conditional variational is well known ( [BSS, FF, FFW]).

Theorem 2.2 (Variational principle I). Let φ be a Hölder function. For any t ∈ R, we have

(2•10) E(t) = sup ν: invariant h(ν) : (-φ)dν = t .
We also have

(2•11) E(t(q)) = P (qφ) -qP ′ (qφ) = h µ -P (qφ)+qφ
where t(q) = -P ′ (qφ). The range of the function t(q) is an interval [e -, e + ], possibly degenerate to a singleton.

Let us state some more useful facts concerning the variational principle. The function t(q) is invertible on the interval [e -, e + ]. If t is not in this interval, then there is no point y ∈ Σ + 2 with local entropy equal to t. The entropy E(t) attains its maximum at the value

e max = t(0) = Σ + 2 (-φ)dµ max .
We have t(q) ≤ e max if and only if q ≥ 0. Furthermore

e + = max µ:invariant (-φ) dµ, e -= min µ:invariant (-φ) dµ.
The entropy spectrum is concave and real analytic in the interval (e -, e + ). Its graph lies below the diagonal. Moreover the interval [e -, e + ] is degenerate if and only if φ is cohomologous to the constant -h top , i.e. the measure µ φ is the measure of maximal entropy. In the degenerate case we have e -= e + = h top and E(h top ) = h top . For typical potentials in the sense of Baire, E(e -) = E(e + ) = 0.

We will need the following variational principle.

Theorem 2.3 (Variational principle II). Let φ be a Hölder function. For any t ∈ R, we have

h top h µ φ (y) < t = h top h µ φ (y) < t = sup s<t E(s), h top h µ φ (y) ≥ t = h top h µ φ (y) ≥ t = sup s≥t E(s).
Proof. Let us start with the proof of the first fact. From the trivial fact

h µ φ (y) < t ⊃ h µ φ (y) < t ⊃ s<t {h µ φ (y) = s},
we get immediately the following inequalities

h top h µ φ (y) < t ≥ h top h µ φ (y) < t ≥ sup s<t E(s).
Since sup t<emax E(t) = 1 the converse inequalities are trivial in the case t ≥ e max . It remains to consider the case t < e max . Notice that we have .

Figure 1. The entropy spectrum for typical, nontypical and degenerate potentials.

E(t) = sup s<t E(s)
. Also notice that there exists a positive number q(t) > 0 such that min q≥0 (P (qφ) + qt) = P (q(t)φ) + q(t)t = E(t).

Now let y be any point such that h µ φ (y) < t. For q = q(t) > 0 we can apply Equation (2•8) to yield

h µ -P (qφ)+qφ (y) = lim n→∞ - 1 n S n -P (qφ) + qφ (y) = P (qφ) + q lim n→∞ - 1 n S n φ(y) ≤ P (qφ) + qt = E(t).
Thus applying the mass distribution principle (see Theorem 7.2 of [P]) yields

h top h µ φ (y) < t ≤ E(t)
, which completes the proof of the first line.

The second fact may be similarly proved. We just point out the following differences that

h µ φ (y) ≥ t ⊃ h µ φ (y) ≥ t ⊃ s≥t {h µ φ (y) = s},
and that for t > e max there exists a negative number q(t) < 0 such that E(t) = P (q(t)φ) + q(t)t.

Covering questions are described by hitting times

It is well known that the doubling map is semi-conjugate to the shift map on Σ + 2 . As we shall see, the initial covering questions can be translated into similar questions concerning the shift map and these question are described by the hitting time that we are going to define. We will also see that hitting times are related to local entropy.

For

x ∈ Σ + 2 and C a cylinder let τ (x, C) := inf{l ≥ 1 : σ l x ∈ C} be the first hitting time of C by x. For x, y ∈ Σ + 2 let τ n (x, y) := τ (x, C n (y)) (3•1) α(x, y) := lim n→∞ 1 n log τ n (x, y). Let F κ (x) := {y ∈ Σ + 2 : y ∈ ∩ ∞ N =1 ∪ n≥N C ⌊κ log n⌋ (σ n x)}, I κ (x) := {y ∈ Σ + 2 : y ∈ ∩ ∞ N =1 ∪ n≥N C ⌊κ log n⌋ (σ n x)}.
We have the following trivial decomposition

Σ + 2 = F κ (x) ∪ I κ (x), F κ (x) ∩ I κ (x) = ∅.
Suppose that µ φ , µ ψ are σ-invariant probability Gibbs measures on Σ + 2 . Let

κ φ,ψ,Σ + 2 := sup{κ : µ ψ (I κ (x)) = 1 for µ φ -a.e. x}, κ F φ,Σ + 2 := sup{κ : F κ (x) = ∅ for µ φ -a.e. x}.
One of our goals is to determine the values of both critical exponents κ φ,ψ,Σ + 2 and κ F φ,Σ + 2 and the other one is to compute the Hausdorff dimensions of F κ (x) and

I κ (x). Let O(x) = {σ n x : n ≥ 0}, O + (x) = O(x) \ {x}. Lemma 3.1. There exists an integer n 0 ≥ 1 such that y = σ n 0 x (i.e. y ∈ O + (x)) if and only if the hitting time sequence τ k (x, y) is bounded. Proof. If y = σ n 0 x then it is obvious that τ k (x, y) ≤ n 0 for all k. Conversely, suppose there is a positive constant such that τ k (x, y) ≤ K. Fix an integer 1 ≤ t ≤ K such that τ k i (x, y) = t holds for an infinite subsequence k i . Then σ t x ∈ C k i (y) for all i. Letting i → ∞ we get σ t x = y. Lemma 3.2. y ∈ Σ + 2 : α(x, y) > 1 κ ⊂ F κ (x) ⊂ y ∈ Σ + 2 : α(x, y) ≥ 1 κ ∪ O + (x), y ∈ Σ + 2 : α(x, y) < 1 κ \ O + (x) ⊂ I κ (x) ⊂ y ∈ Σ + 2 : α(x, y) ≤ 1 κ .
Proof. The top left and bottom right inclusions imply one another. Let us prove the bottom right inclusion. Suppose y ∈ I κ (x). Then y ∈ C ⌊κ log n⌋ (σ n x) or equivalently σ n x ∈ C ⌊κ log n⌋ (y) for infinitely many n. Thus τ ⌊κ log n⌋ (x, y) ≤ n for infinitely many n, which implies α(x, y) ≤ κ -1 . The top right and bottom left inclusions imply one another. So, it remains to prove the bottom left inclusion. Suppose α := α(x, y) < κ -1 and y ∈ O + (x). Take ε > 0 such that κ < 1 α+ε . By the definition of α := α(x, y), there is a subsequence k i such that log

τ k i (x, y) ≤ (α + ε)k i , i.e. k i ≥ log τ k i (x,y) α+ε
. The definition of τ k i (x, y) implies that

σ τ k i x ∈ C k i (y) ⊂ C log τ k i α+ε (y) ⊂ C ⌊κ log τ k i ⌋ (y).
Since y ∈ O + (x) the previous lemma yields that τ k i is not bounded. Thus

σ n x ∈ C ⌊κ log n⌋ (y) or equivalently y ∈ C ⌊κ log n⌋ (σ n x) for infinitely many n = τ k i .
We should point out that points y on the orbit O + (x) have the property that α(x, y) = 0 < 1/κ, but they are not necessarily contained in I κ (x). For example, if x is an eventually periodic point but not periodic and if y is on the orbit O + (x) but not in the cycle of x, then y ∈ I κ (x). However, for µ φ -almost all x, we have the following situation.

Lemma 3.3. For µ φ a.e. x, we have

O(x) ⊂ I κ (x) if 1 κ > h µ φ and O(x) ⊂ F κ (x) if 1 κ < h µ φ . Proof. Let y ∈ O(x)
where x is not eventually periodic. Then there exists a unique integer n 0 ≥ 0 such that y = σ n 0 x. Define the hitting time after n 0 by

τ (n 0 ) n (x, y) := inf{k > n 0 : σ k x ∈ C n (y)} = τ n (σ n 0 x, y) + n 0 . Since y ∈ O + (σ n 0 x)) Lemma 3.1 implies that τ (n 0 ) n (x, y) → ∞ as n → ∞. Let (3•2) α (n 0 ) (x, y) = lim n→∞ 1 n log τ (n 0 ) n (x, y).
Hence

y ∈ I κ (x) if α (n 0 ) (x, y) < 1 κ , and y ∈ F κ (x) if α (n 0 ) (x, y) > 1 κ . Now α (n 0 ) (x, y) = α(y, y) = α(σ n 0 x, σ n 0 x).
Thus applying the Ornstein-Weiss return time theorem [OW] yields that α(x, x) = h µ φ for µ φ -a.e. x. Finally the invariance of µ implies that α(σ n x, σ n x) = h µ φ for µ φ a.e. x and for all n.

Hitting time and local entropy: basic relation

As Lemmas 3.2 and 3.3 show, we have to study the hitting time α(x, y) of the Gibbs measure µ φ . We will show that the hitting time is related to the local entropy. Local entropy have been well studied in the literature.

In this section, we start with a basic relation between hitting times and local entropy. This allows us to compute the critical value κ φ,ψ,Σ + 2 . Let us first introduce a generalized notion of local entropy. Let (C n ) be a sequence of (arbitrary) cylinders with length |C n | = n. We define the lower local entropy of the sequence (C n ) by

(4•1) h µ φ ({C n }) := lim n→∞ - log µ φ (C n ) n .
4.1. Basic relation. We have the following basic relation between local entropy and the hitting times.

Theorem 4.1. Suppose that µ φ is a Gibbs measure associated to a Hölder potential φ and that (C n ) is a sequence of (arbitrary) cylinders of length n.

Then for µ φ a.e. x we have

(4•2) lim n→∞ log τ (x, C n ) n = h µ φ ({C n })
Proof. A special case of this theorem was proven by Chazottes [C]. The proof follows the idea of Chazottes closely. We include it for completeness. Let τ n (x) := τ (x, C n ). Note that the Gibbs property implies µ φ (C n ) → 0. Fix ε > 0 and let

A n := x ∈ Σ + 2 : τ n (x)µ φ (C n ) < 2 -εn , B n := x ∈ Σ + 2 : τ n (x)µ φ (C n ) > 2 εn . We will prove that µ φ (A n ∪ B n ) ≤ µ φ (A n ) + µ φ (B n ) < ∞.
Once we have shown this we apply the first part of the Borel-Cantelli lemma to conclude the proof. First consider the series µ φ (A n ), which is simpler to handle. We have

A n ⊂ A 0 n ∪ • • • ∪ A m n where A i n := {x ∈ Σ + 2 : σ i x ∈ C n }, m = ⌊2 -εn /µ φ (C n )⌋. Since µ φ (A i n ) = µ φ (A j n ) = µ φ (C n ), this yields µ(A n ) ≤ 2 -εn µ φ (C n ) + 2 µ φ (C n ) ≤ 2 -ǫn + 2µ φ (C n ).
Now we distinguish two cases:

h µ φ ({C n }) > 0 and h µ φ ({C n }) = 0. In the first case, µ φ (C n ) decays exponentially fast, so that µ φ (C n ) < ∞, then µ φ (A n ) < ∞. In the second case, since µ φ (C n ) → 0, we can find some subsequence n k such that k µ φ (C n k ) < ∞ so that k µ φ (A n k ) < ∞. So lim n→∞ log τ (x, C n ) n ≤ lim k→∞ log τ (x, C n k ) n k = 0.
Now we turn to the analysis of the series

µ φ (B n ). Choose a big ω > 0 and d := d(n) := ⌊ωn⌋. Let B i n := {x : σ i(n+d) x ∈ C n }, m := ⌊2 εn /µ φ (C n )(n + d)⌋ -1. Thus B n ⊂ B 0 n ∩ • • • ∩ B m n = D 0 ,...,Dm D 0 ∩ σ -(n+d) D 1 ∩ • • • ∩ σ -m(n+d) D m
where the D i are cylinders (not necessarily distinct) of length n disjoint from C n . Thus, by the multi-relation property, we get

µ φ (B n ) ≤ D 0 ,...,Dm µ φ (D 0 ∩ σ -(n+d) D 1 ∩ • • • ∩ σ -m(n+d) D m ) ≤ (1 + cβ d ) m D 0 ,...,Dm m i=0 µ φ (σ -i(n+d) D i ) ≤ [(1 + cβ d )(1 -µ φ (C n ))] m+1 ≤ 1 - µ φ (C n ) 2 m+1 ≤ e -(m+1)µ φ (Cn)/2
≤ e -2 ǫn-1 /(n+d) .

Corollary 4.2. For any y ∈ Σ + 2 and for µ φ a.e. x α(x, y) = h µ φ (y).

An application of Fubini's Theorem yields

Corollary 4.3. Let ν be a probability measure on Σ + 2 . Then for µ φ × ν a.e. (x, y) we have α(x, y) = h µ φ (y).

The hitting time α(x, x) is what we called the return time. The following result due to Ornstein and Weiss [OW] concerning the return time is well known and holds for all ergodic measures. For Gibbs measures, it can be similarly proved as the above theorem.

Corollary 4.4. For µ φ a.e. x we have

α(x, x) = α(σ k x, σ k x) = h µ φ (x) = h µ φ (∀k ≥ 1).
4.2. Determination of κ φ,ψ,Σ + 2 . Recall thatφdµ ψ is nothing but the conditional entropy of µ φ relative to µ ψ . As a direct consequence of Lemma 3.2 and Chazottes' theorem, we get immediately the following critical value.

Theorem 4.5. Let φ and ψ be Hölder functions on Σ + 2 . We have

κ φ,ψ = 1 -Σ 2 φ dµ ψ = - 1 d dt P (ψ + tφ)| t=0
.

Proof. Suppose that µ φ and µ ψ are ergodic Gibbs measures with P (φ) = P (ψ) = 0. Corollary 4.3 implies that for µ φ × µ ψ a.e. (x, y)

α(x, y) = h µ φ (y) = - Σ 2 φ dµ ψ = - d dt P (ψ + tφ)| t=0 .
Thus applying Lemma 3.2 yields the assertion of the theorem.

5. Big hitting probability and Study of F κ (x)

We will give answers to question (Q2) and to the part of question (Q3) concerning F κ (x).

Big hitting probability.

Heuristically points of small local entropy (i.e. large "local measure") are hit with big probability. More precisely we have Lemma 5.1 (Big hitting probability).

Let K := 2 hn . Fix L cylinders C 1 , • • • C L of length n satisfying µ φ (C i ) ≥ 2 -(h-γ)n . Then µ φ {x : ∃C ∈ {C i } such that τ n (x, C) > K} ≤ 2 -λn
for any positive λ for sufficiently large n. For a fixed C, let G C be the set of points in Σ + 2 in which the chosen cylinder C, considered as a word, does not appear up to time K. In particular, it does not appear at times n

+ d, • • • , m(n + d). Thus µ φ (G C ) ≤ D 0 ,...,Dm µ φ (D 0 ∩ σ -n+d D 1 ∩ • • • ∩ σ -m(n+d) D m ).
By the multi-relation property, we get

µ φ (G C ) ≤ (1 + cβ d ) m+1 D 0 ,...,Dm m i=0 µ φ (σ -i(n+d) D i ) = (1 + cβ d )(1 -min C i µ φ (C i )) m ≤ 1 - 1 2 min C i µ φ (C i ) m .
Summing over all the L(≤ 2 n ) possible cylinders C yields

µ φ {x : ∃C ∈ {C i } such that τ n (x, C) > K} ≤ C µ φ (G C ) ≤ L 1 - 1 2 min C i µ φ (C i )) m ≤ L 1 - 1 2 min C i µ φ (C i )) 2 γn /(min C i µ φ (C i )(1+ω)n) ≤ const • 2 n • e -1/2 2 γn /(1+ω)n ≤ 2 -λn
for any positive λ and sufficiently large n.

The set of late hits.

Let us recall that {y ∈ Σ + 2 : α(x, y) ≥ t} is random but {y ∈ Σ + 2 : h µ φ (y) ≥ t} is deterministic (i.e. independent of x). The following theorem is deduced from Lemma 5.1 (big hitting probability) and Corollary 4.3 (Ornstein-Weiss type theorem on return times).

Theorem 5.2. For any t ≥ 0 and for µ φ a.e. x we have

(5•1) {y ∈ Σ + 2 : α(x, y) ≥ t} ⊂ {y ∈ Σ + 2 : h µ φ (y) ≥ t}.
Moreover if ν is any probability measure on Σ 2 , then for µ φ a.e. x we have

{y ∈ Σ + 2 : α(x, y) ≥ t} ν = {y ∈ Σ + 2 : h µ φ (y) ≥ t}. Proof. The case t = 0 is trivial. Assume t > 0. Let H ≥t (x) = {y ∈ Σ + 2 : α(x, y) ≥ t}, E ≥t = {y ∈ Σ + 2 : h µ φ (y) ≥ t}.
By definition, we have

H ≥t (x) = ε>0 lim n→∞ H n,ε (x)
with H n,ε (x) = {y : τ n (x, y) ≥ 2 (t-ε)n }, and

E ≥t = ε>0 lim n→∞ E n,ε with E n,ε (x) = {y : µ φ (C n (y)) ≤ 2 -(t-2ε)n }.
Thus it remains to prove that for µ φ -a.e. x there exists n(x) > 0 such that

H n,ε (x) ⊂ E n,ε ∀n ≥ n(x). Equivalently E c n,ε ⊂ H c n,ε (x) ∀n ≥ n(x). Notice that E c n,ε is the union of all n-cylinders C such that µ φ (C) > 2 -(t-2ε)n . Let C n,ε be the set of all these cylinders. Applying Lemma 5.1 to {C 1 , • • • , C L } := C n,ε leads to n µ φ {x ∈ Σ 2 : ∃C ∈ C n,ε s.t. τ n (x, C) ≥ 2 (t-ε)n } < ∞.
So, by the Borel-Cantelli lemma, for µ φ -a.e. x, for large n and for all C ∈ C n,ε we have x). This proves the first assertion. To prove the second assertion, it suffices to show that for µ φ -a.e. x we have ν{y ∈ Σ 2 : h µ φ (y) ≥ t, α(x, y) < t} = 0.

τ n (x, C) < 2 (t-ε)n , i.e. C ⊂ H c n,ε (
Let

E = {(x, y) : α(x, y) = h µ φ (y)}, E x = {y : α(x, y) = h µ φ (y)}.
By Corollary 4.3, we have µ φ × ν(E) = 1. Then Fubini's theorem asserts that for µ φ -a.e. x we have ν(E x ) = 1, i.e.

ν(E c x ) = ν{y : α(x, y) = h µ φ (y)} = 0. We conclude by noticing

{y : h µ φ (y) ≥ t, α(x, y) < t} ⊂ E c x .
We should point out that (5•1) is equivalent to

(5•2) {y ∈ Σ + 2 : h µ φ (y) < t} ⊂ {y ∈ Σ + 2 : α(x, y) < t}.
This justifies our heuristics that points of small local entropy are hit early. We point out that the inverse inclusion of (5•2) does not hold. Actually for t < e -, the deterministic set {y ∈ Σ + 2 : h µ φ (y) < t} is empty, but if 1/κ < t, the random set {y ∈ Σ + 2 : α(x, y) < t} contains I κ (x) which is a residual set. 5.3. Computation of dim H {y : α(x, y) ≥ t} and dim H F κ (x).

Theorem 5.3. For µ φ -a.e. x, we have

dim H y : α(x, y) ≥ t = dim H y : h µ φ ≥ t .
Proof. By the second variational principle (Theorem 2.3), there exists an s ≥ t such that

(5•3) dim H {y : h µ φ ≥ t = dim H µ -P (q(s)φ)+q(s)φ .
Applying Corollary 4.3 (with ν = µ -P (q(s)φ)+q(s)φ ) implies that µ -P (q(s)φ)+q(s)φ ({y :

h µ φ (y) = α(x, y) = s}) = 1 for µ φ -a.e. x.
It follows that for µ φ -a.e. x we have

dim H {y : α(x, y) ≥ t} ≥ dim H {y : h µ φ (y) = α(x, y) = s} ≥ dim µ -P (q(s)φ)+q(s)φ .
This, together with (5•3), implies

dim H y : α(x, y) ≥ t ≥ dim H y : h µ φ ≥ t µ φ -a.e.
Now we turn to the reverse inequality. Observe the following decomposition

{y : α(x, y) ≥ t} = {α(x, y) ≥ t, h µ φ (y) < t} ∪ {α(x, y) ≥ t, h µ φ (y) ≥ t}. Since dim H {h µ φ (y) ≥ t, α(x, y) ≥ t} ≤ dim H {h µ φ (y) ≥ t},
it suffices to remark that {y : h µ φ (y) < t, α(x, y) ≥ t} = ∅ for µ φ a.e. x.

By this theorem, Lemmas 3.2 and 3.3, and the second variational principle (Theorem 2.3) we get Theorem 5.4. For µ φ -a.e. x we have

h top (F κ (x)) = 1 for 1 κ ≤ e max , h top (F κ (x)) = h µ q(κ)φ for e max ≤ 1 κ < e +
where q(κ) is chosen such that h µ φ (y) = 1 κ for µ q(κ)φ a.e. y. We also have

F κ (x) = ∅ (or equivalently I κ (x) = S 1 ) if 1 κ > e + , F κ (x) = ∅ (or equivalently I κ (x) = S 1 ) if 1 κ < e + .
Remark that the case 1 κ = e + is not covered by the theorem because E(t) is not continuous at t = e + . We have the upper bound dim H F 1/e + ≤ E(e + ). A result due to Kahane for the random covering shows that a strict inequality may occur ( [K], p.160).

Small hitting probability and upper bound of

dim H {y : α(x, y) ≤ s} 6.1. Small hitting probability.

Lemma 6.1 (Small hitting probability).

Let K := 2 an , L := 2 bn , N := 2 cn with a > 0, b > 0, c > 0. Fix L different cylinders C 1 , • • • C L of length n satisfying µ φ (C i ) ≤ 2 -(a+γ)n . Then if γ > max(b -c, 0
), for any positive λ and sufficiently large n we have

µ φ {x : τ n (x, C i ) ≤ K for N different cylinders among the C i } ≤ 2 -λn .
Proof. Let S be the set in question. That x ∈ S means there exist times

ℓ 1 < ℓ 2 < • • • < ℓ N < K and different cylinders C i 1 , C i 2 , • • • , C i N such that σ ℓ 1 x ∈ C i 1 , σ ℓ 2 x ∈ C i 2 , • • • , σ ℓ N x ∈ C i N .
In this sequence (ℓ k ) of length N there is a subsequence of N/(3n + d) terms, denoted (τ j ) such that τ jτ j-1 ≥ 3n + d. For example, we may take τ j = ℓ (3n+d)j . Thus x ∈ S implies

σ τ 1 x ∈ C j 1 , σ τ 2 x ∈ C j 2 , • • • , σ τ N ′ x ∈ C j N ′ for N ′ := N/(3n + d) different cylinders taken from the list C 1 , C 2 , • • • , C L .
Thus to each x ∈ S we can associate the sequences (τ j ) and (C j k ). Thus

x ∈ C(x) := σ -τ i (C j i )
and S is covered by the union of C(x). The multi-relation property implies that the measure of C(x) is bounded by

max 1≤i≤L µ φ (C i ) N ′ (1 + cβ d ) N ′ .
Now, we have to estimate the number of different (disjoint) sets C(x). First we have L N ′ choices for the N ′ different cylinders from the list of L words. Then we can choose K N ′ places (i.e. we fix the sequence τ j ) to put the chosen words in order to determine C(x) . Finally we have N ′ ! ways to arrange words into these N ′ (now fixed) places.

Thus the measure of the set in question can be majorized by

L N ′ K N ′ • N ′ ! • max C i µ φ (C i ) N ′ • (1 + cβ d ) N ′ . This is equal to L! (L -N ′ )! • K! (K -N ′ )!N ′ ! • (max C i µ φ (C i )) N ′ • (1 + cβ d ) N ′ .
Next using the estimates

L! (L -N ′ )! ≤ L N ′ , K! (K -N ′ )!N ′ ! ≤ const • K N ′ • e N ′ N ′ N ′
(the second one is implied by Stirling's formula), we conclude that the measure is majorized by

const • L N ′ • K N ′ • e N ′ • N ′-N ′ • 2 -(a+γ)n N ′ • (1 + cβ) N ′ = const • 2 bn • 2 an • e • 2 -cn • 2 -(a+γ)n • (1 + cβ d ) N ′ ≤ const e • (1 + cβ d ) • 2 (b-c-γ)n N ′ .
Provided γ > bc, this is less that 2 λn for any positive λ and sufficiently large n.

6.2. Upper bound of dim H {y : α(x, y) ≤ s}.

Theorem 6.2. If h µ φ < s < e max then for µ φ -a.e. x we have

(6•1) h top {y : α(x, y) ≤ s} ≤ E(s).
If 0 < s ≤ h µ φ then for all x we have

(6•2) h top {y : α(x, y) ≤ s} ≤ s. Proof. Let A x (s) = {y : α(x, y) ≤ s} .
The case s ≤ h µ φ is simple. In fact, if a > s, we have

A x (s) ⊂ lim n→∞ {y : τ n (x, y) ≤ 2 an } = lim n→∞ 2 an k=1 C n (σ k x). Since C m (σ k x) ⊂ C n (σ k x) for m > n, we have A x (s) ⊂ ∞ n=1 2 an k=1 C n (σ k x).
We have h top A x (s) ≤ a since {C n (σ k )} 1≤k≤2 an is a cover of for A x (s) by 2 an cylinders of length n. We conclude by letting a ↓ s. Remark that h top A x (s) ≤ s holds for any non negative s.

We turn to the case h µ φ < s ≤ e max . We start with a remark. For δ > 0 and n ≥ 1 and 0

< h 1 < h 2 , let L n (h 1 , h 2 ) := L n (h 1 , h 2 , δ) be the set of cylinders C of length n such that 2 -(h 2 -δ)n ≤ µ φ (C) ≤ 2 -(h 1 +δ)n .
Then for n sufficiently large (depending on h 1 , h 2 and δ) we have

Card L n (h 1 , h 2 ) ≤ 2 nE(h 2 ) if h 2 < e max Card L n (h 1 , h 2 ) ≤ 2 nE(h 1 ) if h 1 > e max .
In fact, assume h 2 < e max (the other case may be similarly proved). There exists a positive number q such that E(h 2 ) = P (q) + h 2 q. Then 2

-q(h 2 -δ)n Card L n (h 1 , h 2 ) ≤ C∈Ln(h 1 ,h 2 ) µ φ (C) q ≤ 2 n(P (q)+qδ) . Write A x (s) = A x (s) ∩ y : h µ φ (y) ≤ s A x (s) ∩ y : h µ φ (y) > s .
Since h top {y : h µ φ (y) ≤ s} ≤ E(s), it suffices to show

(6•3) h top A x (s) ∩ y : h µ φ (y) > s ≤ E(s). Let H(h ′ , h ′′ ) = y : h ′ ≤ h µ φ (y) ≤ h ′′ .
If all choices s < h ′ < h ′′ such that h ′′ < e max or h ′ > e max the formula

h top (A x (s) ∩ H(h ′ , h ′′ )) ≤ E(s)
holds, then the equation ( 6•3) also holds.

Let s < h 1 + δ < h ′ < h ′′ < h 2 -δ with h 1 close to h ′ and h 2 close to h ′′ . Remark that y ∈ H(h ′ , h ′′ ) implies that C n (y)) ∈ H(h 1 , h 2 ) for infinitely many n's. In other words H(h ′ , h ′′ ) ⊂ ∞ m=1 ∞ n=m C∈Ln(h 1 ,h 2 ) C.

That is to say, for any fixed

m, n≥m L n (h 1 , h 2 ) is a cover of H(h ′ , h ′′ ).
Now we construct a cover of A x (s) ∩ H(h ′ , h ′′ ). For any s < a < h 1 , let

L n (x; a, h 1 , h 2 ) = {C ∈ L n (h 1 , h 2 ) : τ (x, C) ≤ 2 an }, N n (x; a, h 1 , h 2 ) = Card L n (x; a, h 1 , h 2 ). Clearly n≥m L n (x; a, h 1 , h 2 ) is a cover of A x (s) ∩ H(h ′ , h ′′ ), because A x (s) ⊂ ∞ m=1 ∞ n=m C:τ (x,C)≤2 an C. Let γ = h 2 -a if h 2 ≤ e max , or γ = h 1 -a if h 1 > e max . Since E ′ (t) < 1 when t > h µ φ , we have E(a + γ) -E(a) < γ, i.e. E(a + γ) -γ < E(a).
We apply the Small Hitting Probability Lemma to b = E(a + γ) and c = E(a) to get

n µ φ {x : N n (x; a, h 1 , h 2 , ) > 2 nE(a) } < ∞.
By the Borel-Cantelli Lemma, for µ φ -a.e. x, we have

N n (x; a, h 1 , h 2 ) ≤ 2 nE(a) for n ≥ n(x). So, if m ≥ n(x), for any ǫ > 0 we have n≥m C∈Ln(x;a,h 1 ,h 2 ) (diam C) E(a)+ǫ ≤ n≥m 2 -n(E(a)+ǫ) • 2 nE(a) ≤ n≥m 2 -nǫ < ∞. Since n≥m L n (x; a, h 1 , h 2 ) is a cover of A x (s) ∩ H(h ′ , h ′′ ), we have proved dim A x (s) ∩ H(h ′ , h ′′ ) ≤ E(a) + ǫ.
We finish the proof by letting first ε ↓ 0 and then a ↓ s. Theorem 6.3. If h µ φ < s < e max then for µ φ -a.e. x we have h top {y : α(x, y) ≤ s} = E(s).

Proof. We simply need to prove the reverse inequality of (6•1) in Theorem 6.2. By multi-fractal analysis there is a Gibbs measure with entropy E(s) supported on {y : h µ φ (y) = s}. Then Corollary 4.3 implies the result. For 0 < s < h µ φ , the opposite inequality of (6•2): h top {y : α(x, y) ≤ s} ≥ s also holds. But its proof is much more involved. It can not be deduced from the mass transference principle as stated in [BV] since µ φ has nontrivial entropy spectrum. In the next section we make a substantial improvement in the mass transference principle to multi-fractal Gibbs states. In order to prove it, we need to undertake a full investigation of the structure of typical sequences.

Typical sequences and Lower bound of dim H {y : α(x, y) ≤ c}

Recall that µ φ is a Gibbs measure associated to a normalized Hölder potential φ. A cylinder C of length n is said to be a (n, ε)-cylinder if

2 -(h+ε)n ≤ µ φ (C) ≤ 2 -(h-ε)n
where h = h φ denotes the entropy of µ φ . We denote by C n,ε the set of all (n, ε)-cylinders. Sometimes we will say that a (n, ε)-cylinder is a good cylinder or the word determining a (n, ε)-cylinder is a good word. As we shall prove, a relatively short typical word contains plenty of good subwords of a fixed length and they are even different.

The following notations will be used. For a set S, ♯S will denote the cardinality of S.

7.1. Frequency of good words in a typical orbit. Lemma 7.1. Let µ φ be a Gibbs measure with entropy h := h µ φ > 0. For any ε > 0, there exist an integer n(ε) ≥ 1 and a Borel set G ε with µ φ (G ε ) > 1 -ε such that for any x ∈ G ε and any n ≥ n(ε), the cylinder

C = C n (x) is a (n, ε)-cylinder. Consequently, if n ≥ n(ε), we have (1 -ε)2 (h-ε)n ≤ ♯C n,ε ≤ 2 (h+ε)n .
Proof. By the Shannon McMillan Breiman theorem, for µ φ -a.e. x we have

lim n→∞ - log µ φ (C n (x)) n = h.
Then by Egorov's theorem, there is a number n(ε) ≥ 1 such that the set

G ε := y ∈ Σ 2 : - 1 n log µ φ (C n (y)) ∈ [h -ε, h + ε], ∀n > n(ε) has measure µ φ (G ε ) > 1 -ε. The upper estimate ♯C n,ε ≤ 2 (h+ε)n follows from 2 -(hµ+ε)n ♯C n,ε ≤ C∈Cn,ε µ φ (C) ≤ 1. The lower estimate (1 -ε)2 (h-ε)n ≤ ♯C n,ε follows from G ε ⊂ C∈Cn,ε C and 1 -ε ≤ µ φ (G ε ) ≤ C∈Cn,ε µ φ (C) ≤ 2 -(hµ-ε)n ♯C n,ε .
We call the set G ε the set of ε-good points. By the definition of G ε , we have

G ε = ∞ n=n(ε) C∈Cn,ε C.
Hence it is a G δ set. We will write it as a decreasing limit of open sets in the following manner

G ε = ∞ N =n(ε) N n=n(ε) C∈Cn,ε C.
This representation of G ε is useful in the proof of the following lemma.

Lemma 7.2. Let 0 < ε < 1/2 and let L ′ ≥ 1 be an arbitrary integer. For any cylinder D of length L ′ , we have

µ φ (D ∩ σ -|D| G ε ) ≥ 1 2γ 4 2 -L ′ φ ∞
where γ > 1 is the constant involved in the Gibbs property of µ φ (2•2).

Proof. We first recall the following quasi-Bernoulli property of µ φ (2•3): for any two cylinders A and B we have B). Let us prove the lemma. The set G ε is the decreasing limit of the open sets

µ φ (A ∩ σ -|A| B) ≥ 1 γ 3 µ φ (A)µ φ (
G N,ε = N n=n(ε) C∈Cn,ε C.
Observe that G N,ε is a union of cylinders of length N. Thus we have

µ φ (D ∩ σ -|D| G ε ) = lim N →∞ µ φ (D ∩ σ -|D| G N,ε ) = lim N →∞ C µ φ (D ∩ σ -|D| C)
where C varies over all N-cylinders contained in G N,ε . First applying the quasi-Bernoulli property and then using the fact that

µ φ (G N,ε ) ≥ 1 -ε > 1/2, yields C µ φ (D ∩ σ -|D| C) ≥ µ φ (D) γ 3 C µ φ (C) = µ φ (D) γ 3 µ φ (G N,ε ) ≥ µ φ (D) 2γ 3 .
To conclude, it suffices to remark that

µ φ (D) ≥ 1 γ 2 -|D| φ ∞
which is assured by the Gibbs property of µ φ .

The next theorem essentially says that a typical word of length 2 cL ′′ contains many good subwords of length n with an arbitrary but fixed prefix D of length L ′ . We keep the notations n(ǫ) and G ǫ appearing in Lemma 7.1.

Theorem 7.3. Let c > 0 be fixed. Let 0 < ε < min( 1 2 , c), 0 < η < 1 2 and L ′ ≥ 1. There exist an integer n(ε, η, L ′ ) ≥ L ′ + n(ε) and a Borel set E(ε, η, L ′ ) with µ φ (E(ε, η, L ′ )) > 1 -η such that if x ∈ E(ε, η, L ′ ) and L ′′ > n(ε, η, L ′ ), for each L ′ -cylinder D there are at least 2 (c-ε)L ′′ points of the finite orbit σ j x (2 L ′ + 1 ≤ j ≤ 2 cL ′′ ), which fall into D ∩ σ -L ′ G ε .
Proof. Let m(L ′ ) := 1 2γ 4 2 -L ′ φ|∞ be the lower bound which appeared in the last lemma. For x ∈ Σ 2 , define

n D,L ′ ,ε (x) := inf    n ∈ N : 1 N 2 L ′ +N j=2 L ′ +1 1 D∩σ -L ′ Gε (σ j x) > 1 2 m(L ′ ), ∀N ≥ n    and n L ′ ,ε (x) = max D n D,L ′ ,ε (x).
By Lemma 7.2 and Birkhoff's ergodic theorem we have

µ φ (x ∈ Σ 2 : n L ′ ,ε (x) < ∞) = 1.
So, for any η > 0, there exists an integer n(L ′ , ε, η) such that the Borel set

E(L ′ , ε, η) := {x ∈ Σ 2 : n L ′ ,ε (x) ≤ n(L ′ , ε, η)} satisfies µ φ (E(L ′ , ε, η)) > 1 -η. Fix n(L ′ , ε, η) ≥ 1 sufficiently large so that 1 2 m(L ′ )[2 εn(L ′ ,ε,η) -2 L ′ ] ≥ 1, n(L ′ , ε, η) -L ′ ≥ n(ε), 2 cn(L ′ ,ε,η) -2 L ′ ≥ n(L ′ , ε, η). Assume x ∈ E(L ′ , ε, η) and L ′′ ≥ n(L ′ , ε, η). Since N := 2 cL ′′ -2 L ′ ≥ n(L ′ , ε, η), we have 2 cL ′′ j=2 L ′ +1 1 D∩Gε (σ j x) ≥ 1 2 m(L ′ )[2 cL ′′ -2 L ′ ] ≥ 1 2 m(L ′ )[2 εn(L ′ ,ε,η) -2 L ′ ] • 2 (c-ε)L ′′ ≥ 2 (c-ε)L ′′ .
Let C be a cylinder of length n. If C n (σ j x) = C, we say that the cylinder C is seen in x at time j. Let ε > 0, L ′ < L ′′ and let D be a cylinder of length L ′ . For any x ∈ Σ 2 , we define a finite tree, denoted T (x, D, L ′ , L ′′ , ε), as follows:

• the nodes of

T (x, D, L ′ , L ′′ , ε) are all those cylinders D ⋆ G ′ , where G ′ is a (ℓ -L ′ , ε)-cylinder with L ′ + n(ε) ≤ ℓ ≤ L ′′
, each of which contains at least one (L ′′ , 2ε)-cylinder seen in x at a moment between the time 2 L ′ + 1 and the time 2 cL ′′ ;

• a ℓ-cylinder D ⋆ G ′ ∈ T (x, D, L ′ , L ′′ , ε) is the parent of a (ℓ + 1)- cylinder D ⋆ G ′′ ∈ T (x, D, L ′ , L ′′ , ε) if and only if G ′′ ⊂ G ′ . Fix L ′ < L ′′ . For L ′ + n(ε) ≤ ℓ ≤ L ′′ , denote T (x, D, ℓ, ε) := ♯{D ⋆ G ′ ∈ T (x, D, L ′ , L ′′ , ε) : |D ⋆ G ′ | = ℓ}.
Theorem 7.3 implies that if L ′′ satisfies the condition of Theorem 7.3 and if x ∈ E(L ′ , ε, η), then in between the times 2 L ′ + 1 and 2 cL ′′ , for each L ′ -cylinder D we can see at least 2 (c-ε)L ′′ cylinders of length L ′′ in x of the form

(7•1) D ⋆ G ′ (G ′ ∈ C L ′′ -L ′ ,ε ).
By the quasi-Bernoulli property (2•3), it is easy to see that if L ′′ is sufficiently larger than L ′ then the cylinders D ⋆ G ′ are good in the sense

(7•2) G := D ⋆ G ′ ∈ C L ′′ ,2ε .
Thus we have

T (x, D, L ′′ , ε) ≥ 2 (c-ε)L ′′ .
Next we will prove that with big probability, for all

L ′ + n(ε) ≤ ℓ ≤ L ′′ T (x, D, ℓ, ε) ≥ 2 (c-2ε)ℓ . 7.2. Trees associated to a typical orbit. Assume that L ′′ ≥ n(L ′ , ε, η). Let L ′ + n(ε) ≤ ℓ ≤ L ′′ , x ∈ E(L ′ , ε, η), and D be a L ′ -cylinder. By definition T (x, D, ℓ, ε) is the number of different cylinders of the form D ⋆ G ′ with G ′ ∈ C ℓ-L ′ ,ε
each of which contains at least one (L ′′ , 2ε)-cylinder belonging to the list

C L ′′ (σ j x), 2 L ′ + 1 ≤ j ≤ 2 cL ′′ .
Theorem 7.4. There exists n 0 (ε) such that for sufficiently large L ′′ and for

L ′ + n 0 (ε) ≤ ℓ ≤ L ′′ we have µ φ x ∈ E(L ′ , ε, η) : T (x, D, ℓ, ε) ≤ 2 (c-2ε)(ℓ-L ′ ) ≤ 2 -2 (c-2ε)L ′′ .
In the rest of this subsection and the next two subsections we prepare for the proof of this theorem, which will be presented in the subsection 7.5. We need to estimate the measures

µ φ {x ∈ E(L ′ , ε, η) : T (x, D, ℓ, ε) = K} for K ≤ 2 (c-2ε)(ℓ-L ′ )
. We will do that in the following.

For 1

≤ t ≤ L ′′ + d (where d := [ωL ′′ ]), let Λ t = 2 L ′ + k(L ′′ + d) + t : 0 ≤ k ≤ 2 cL ′′ -2 L ′ L ′′ + d . Fix K cylinders C 1 , • • • , C K ∈ C ℓ-L ′ ,ε . Let Υ t (x; C 1 , C 2 , • • • , C K ) = ♯ j ∈ Λ t : C L ′′ (σ j x) ∈ C L ′′ ,2ε implies C L ′′ (σ j x) ⊂ D ⋆ C
where

D ⋆ C := K i=1 D ⋆ C i . T (x, D, ℓ, ε) = K means there exist K different (ℓ -L ′ , ε)-cylinders, say C 1 , C 2 , • • • , C K such
that all (L ′′ , 2ε)-cylinders seen in x in between the times 2 L ′ + 1 and 2 cL ′′ are contained in some of the D ⋆ C i 's, i.e. contained in D ⋆ C. On the other hand, by Theorem 7.3, there are at least 2 (c-ε)L ′′ of the (L ′′ , 2ε)-cylinders seen in x in between the times 2 L ′ + 1 and 2 cL ′′ . So, for at least one t the number of the (L ′′ , 2ε)-cylinders seen at moments belonging to Λ t and contained in D ⋆ C is at least 2

(c-ε)L ′′ L ′′ + d . Thus we get {x ∈ E(L ′ , ε, η) : T (x, D, ℓ, ε) = K} ⊂ L ′′ +d t=1 C 1 ,••• ,C K E t (C 1 , • • • , C K ) Since B ∈C L,ε µ φ (B) ≤ µ φ (G c L,ε ) ≤ ε, we get µ φ (A i ) ≤ γ 3 (ε(1 + β d )) i µ φ (A)µ φ (G).
Thus

µ φ (x ∈ A : C L (σ ι A (x) x) = G) ≤ γ 3 µ φ (A)µ φ (G) ∞ i=0 (ε(1 + β d )) i = γ 3 1 -ε(1 + β d ) µ φ (A)µ φ (G).
We finish the proof by observing that β < 1.

7.4. Estimation of µ φ (E t (C 1 , • • • , C K )).
Let t be fixed. We define inductively

ι 1 (x) = inf{j ∈ Λ t : C L ′′ (σ j x) ∈ C L ′′ ,2ε }; ι k+1 (x) = inf{j ∈ Λ t : j > ι k (x); C L ′′ (σ j x) ∈ C L ′′ ,2ε }. Let (7•3) n := 2 (c-ε)L ′′ L ′′ + d .
We have

ι i (x) < ∞ if x ∈ E t (C 1 , • • • , C K ), and if i ≤ n. Then (7•4) µ φ (E t (C 1 , • • • , C K )) ≤ µ φ x : σ ι i (x) x ∈ F i , 1 ≤ ∀i ≤ n
where the sum is taken over all F i 's with the property

F i ∈ C L ′′ ,2ε , F i ⊂ D ⋆ C (1 ≤ ∀i ≤ n).
Lemma 7.7. Let n ≥ 1 and let F i ∈ C L ′′ ,2ε with 1 ≤ i ≤ n. We have

µ φ x : C L ′′ (σ ι i (x) x) = F i ; i = 1, 2, • • • , n ≤ γ 3 1 -4ε n n i=1 µ φ (F i ).
Proof. We prove it by induction on n. Let

Q n = {x : C L ′′ (σ ι i (x) x) = F i ; i = 1, 2, • • • , n}. Write Q n+1 = Q n ∩ {x : C L ′′ (σ ι n+1 (x) x) = F n+1 }.
Notice that Q n is a disjoint union of cylinders, say

Q n = A j .
Furthermore if x ∈ A j we have

C L ′′ (σ ι n+1 (x) x) = F n+1 ⇐⇒ C L ′′ (σ ι A j (x) x) = F n+1 .
such that for any x ∈ E * k (ε), any L k-1 -cylinder D and any

L k-1 + n 0 (ε) ≤ ℓ ≤ L k we have T (x, D, ℓ, ε) ≥ 2 (c-2ε)(ℓ-L k-1 ) . Define E * (ε) = ∞ k=1 E * (L k , ε).
Equations ( 7•11) and ( 7•12) imply that

µ φ (E * k (ε))) ≥ 1 -ε 2 k and (7•13) µ φ (E * (ε)) ≥ 1 - ∞ k=1 ε 2 k = 1 -ε.
For x ∈ E * (ε), we have

(7•14) T (x, D, ℓ, ε) ≥ 2 (c-2ε)(ℓ-L k-1 )
for all L k-1 -cylinders D and all L k-1 + n 0 (ε) ≤ ℓ ≤ L k . Now, for each x ∈ E * (ε), we construct a Cantor set as follows.

First step: for n 0 (ε) ≤ ℓ ≤ L 1 , consider the family C ℓ (x) of (ℓ, ε)-cylinders which contain at least one (L 1 , 2ε)-cylinder seen in x between the times 1 and 2 cL 1 . This yields a tree T L 1 (x) of height L 1 . The nodes of the tree T L 1 (x) are the (ℓ, ε)-cylinders, with n 0 (ε) ≤ ℓ ≤ L 1 , belonging to C ℓ (x). The edges are defined by the containment relation. We will extend this tree inductively.

Second step: Let k ≥ 2. Suppose that we have constructed a tree T L k-1 (x) of height L k-1 . We will construct a tree of height L k . Let

L ′ = L k-1 , L ′′ = L k .
Fix a L ′ -cylinder D seen in x before time 2 cL ′ , which is the label of a node of the tree T L k-1 (x) at level L k-1 . For L ′ + n 0 (ε) ≤ ℓ ≤ L ′′ , take all (ℓ, ε)-cylinders that contain at least one (L ′′ , 2ε)-cylinder of the form D ⋆ G seen in x between the times 2 L ′ + 1 and 2 cL ′′ . As before we denote this family by C ℓ (x) (both D and G varying). The tree T L k (x) is obtained from T L k-1 (x) by adding branches to each D. That is to say, by splitting D into (ℓ, ε)-cylinders belonging to C ℓ (x).

We define

C ∞ (x) = ∞ k=1 L k ℓ=L k-1 +n 0 (ε) C∈C ℓ (x) C.
We have C ∞ (x) ⊂ {y : α(x, y) ≤ c}, since for any y ∈ C ∞ (x) and for all k ≥ 1 y ∈

C∈C L k (x) C,
i.e. y ∈ C L k (σ j x) for some

2 L k-1 + 1 ≤ j ≤ 2 cL k . We claim that dim H C ∞ (x) ≥ c -2ε. In fact, for L k-1 + n 0 (ε) ≤ ℓ ≤ L k , we have log 2 ♯C ℓ (x) ≥ (c -2ε)(ℓ -L k-1 ) + k-1 j=1 (c -2ε)(L j -L j-1 ) ≥ (c -2ε)ℓ Define a probability measure ν on C ∞ (x) by ν(C) = 1 ♯C ℓ (x) (∀C ∈ C ℓ (x) and l ∈ N).
It is clear that (note n(ε) does not depend on L k )

ν(C) ≤ 2 -(c-2ε)ℓ .
Thus we have proved that with probability bigger than 1ε we have dim H {y : α(x, y) ≤ c} ≥ c -2ε.

Remark: The proofs in this section can be used to obtain a more precise estimate on the growth rate of the tree, however this estimate is not necessary for our purpose. Namely one can show that

L k-1 ≪ l ≤ c h L k then T (x, D, l, ε) ≥ 2 (h-3ε)l .
This implies that the upper box counting dimension of the corresponding Cantor set is h -3ε while the lower box dimension equals the Hausdorff dimension equals c -2ε.

Results for the full shift

Our strategy is to prove all the theorems in the symbolic framework and then transfer them to the circle. Let us get together the already obtained results in the symbolic framework.

Lemma 8.1. For 0 < κ < ∞ we have µ φ -a.e.

sup{E(t) : 1 t ≤ κ} ≥ dim H F κ (x) ≥ sup{E(t) : 1 t < κ}.
For κ ≤ 1/h µ φ (i.e. 1/κ ≥ h µ φ ) we have µ φ -a.e.

sup{E(t) : 1 t ≥ κ} ≥ dim H I κ (x) ≥ sup{E(t) : 1 t > κ},
and for κ > 1/h µ φ (i.e. 1/κ < h µ φ ) we have µ φ -a.e.

dim H I κ (x) = 1/κ.
Proof. The first line is a consequence of Lemma 3.2, Theorem 5.3 and Theorem 2.3. The second line is a consequence of Lemma 3.2, Theorem 6.2 and Theorem 2.3.

The third line is a direct consequence of Lemma 3.2, Theorems 6.2 and 7.9.

Corollary 8.2. Let 1/κ ∈ (e -, e + ). Then for µ φ a.e.

x dim H F κ (x) = max ν-ergodic {h ν : α(x, y) ≤ 1 κ ν -a.e.y}.
For 1/κ ∈ (h µ φ , e + ) and µ φ a.e.

x

dim H I κ (x) = max ν-ergodic {h ν : α(x, y) ≥ 1 κ ν -a.e.y}.
The properties of the entropy spectrum which were stated in the background section immediately imply the following corollary.

Corollary 8.3. For 1/κ ∈ (e -, e + ) and µ φ a.e. x we have sup

-P ′ (q)≥ 1 κ [P (qφ) -P ′ (qφ)q] ≥ dim H F κ (x) ≥ sup -P ′ (q)> 1 κ [P (qφ) -P ′ (qφ)q] .
For 1/κ ∈ (h µ φ , e + ) and µ φ a.e. x we have sup

-P ′ (q)≤ 1 κ [P (qφ) -P ′ (qφ)q] ≥ dim H I κ (x) ≥ sup -P ′ (q)< 1 κ [P (qφ) -P ′ (qφ)q] .
If we consider a typical potential, then the function E(t) is continuous on the nontrivial interval (e -, e + ), equals 0 on the endpoints (see [S2]). Hence the right hand side and left hand side inequalities in Lemma 8.1 and Corollary 8.3 are equal. Since the maximum value of E(t) is attained at the value t = -Σ + 2 φ dµ max and equals h top (Σ + 2 ) = 1 we have the following corollary.

Corollary 8.4. For a typical potential and µ φ a.e. x we have

dim H F κ (x) = h top (Σ + 2 ) = 1 for κ ≥ 1 -φ dµ max .
,

dim H I κ (x) = h top (Σ + 2 ) = 1 for κ ≤ 1 -φ dµ max .
.

Let q κ be the number such that P

′ (q κ φ) = -1 κ . Then dim H F κ (x) = E 1 κ = P (q κ φ) + 1 κ q κ for κ < 1 -φ dµ max .
,

dim H I κ (x) = E 1 κ = P (q κ φ) + 1 κ tq κ for 1 h µ φ ≥ κ > 1 -φ dµ max .
.

Finally we come to the answer of the symbolic version of question (Q2).

We list some facts concerning E A (α) which are needed to modify the proofs.

(1) Clearly the restriction φ| Σ A is a Hölder function.

(2) Let P A (ψ) be the pressure of a potential ψ : Σ A → R related to the subsystem σ : Σ A → Σ A . Then

P A (φ| Σ A ) ≤ 0.
This a consequence of the variational principle:

P A (φ| Σ A ) = max µ inv on Σ A (h µ + Σ A φ dµ) ≤ max µ inv on Σ (h µ + Σ φ dµ) = P (φ) = 0.
(3) φ A (x) := φ| Σ A -P A (φ| Σ A ) is normalized in the sense that P A (φ A ) = 0. (4) Let µ φ A be the Gibbs measure on Σ A associated to φ A . It is related to the original Gibbs measure µ φ by

µ φ A (C n (x)) ≈ e Snφ A (x) = e Snφ(x)-nP A (φ| Σ A ) ≈ e -nP A (φ| Σ A (φ) µ φ (C n (x)) for x ∈ Σ A .
Here ≈ means that the ratio is bounded between two constants independent of n. (5) Consequently, if one of the local entropies h µ φ A (x) or h µ φ (x) is well defined then both are well defined and we have

h µ φ A (x) = h µ φ (x) + P A (φ| Σ A ), x ∈ Σ A .
(6) The following spectrum is well known from multi-fractal analysis

E A (β) := dim H {y ∈ Σ A : h µ φ A (y) = β}.
The condition h µ φ A (y) = β is equivalent to lim n→∞ n -1 (S n (-φ A )(y)) = β. Now, by ( 5) and ( 6), we get that the spectrum E A (•) is expressed in term of the known spectrum E A (•):

E A (α) = dim H {y ∈ Σ A : h µ φ (y) = α} = dim H {y ∈ Σ A : h µ φ A (y) = α + P A (φ)} = E A (α + P A (φ)).

Furthermore, the set {y ∈ Σ

A : h µ φ (y) = α} is empty, so E A (α) = 0 unless (9•1) ẽ- A ≤ α + P A (φ) ≤ ẽ+ A
where ẽ+ A , ẽ-A are respectively the maximal and minimal entropy of h µ φ A . That is

ẽ+ A = sup suppµ⊂Σ A (-φ A )dµ = sup suppµ⊂Σ A (-φ)dµ + P A (φ| σ A ) ẽ- A = inf suppµ⊂Σ A (-φ A )dµ = inf suppµ⊂Σ A (-φ)dµ + P A (φ| Σ A ). Define e - A := inf suppµ⊂Σ A (-φ)dµ, e + A := sup suppµ⊂Σ A (-φ)dµ. So, (9•1) is equivalent to e - A ≤ α ≤ e + A . Thus E A (α) ≤ E(α) because E A (α + P A (φ)) = sup suppµ⊂Σ A (-φ A )dµ=α+P A (φ) h µ = sup suppµ⊂Σ A (-φ)dµ=α h µ ≤ sup (-φ)dν=α h ν = E(α).
Let e max A be the unique value for which E A (α) attains its maximum (supported by the Parry measure). In particular E A (e max A ) = dim H (Σ A ). Then we can conclude Theorem 9.1.

dim H F κ A (x) = dim H (Σ A ) if 1 κ ≤ e max A E A ( 1 κ ) if 1 κ > e max A and F κ A (x) = ∅ if 1 κ > e + A .
Theorem 9.2.

dim H I κ A (x) =      1 κ + P A (φ| Σ A ) if -P A (φ| Σ A ) ≤ 1 κ ≤ h µ φ A -P A (φ| Σ A ) E A ( 1 κ ) if h µ φ A -P A (φ| Σ A ) ≤ 1 κ ≤ e max A dim H (Σ A ) if 1 κ ≥ e max A and I κ A (x) = ∅ if 1 κ < -P A (φ| Σ A ).
Remark: Unlike the full shift case I κ A (x) is empty for large κ. Proof. The only statement in the two theorems which differs from the full shift is that

I κ A (x) may be empty. Fix ε > 0. Let 1 κ < -P A (φ| Σ A ) -ε. Then by (9•1) we have h µ φ (y) ≥ ẽ- A -P A (φ| Σ A ) for all y ∈ Σ A . Then, by Lemma 3.2 I κ A (x) ⊂ y ∈ Σ A : α(x, y) < 1 κ + ǫ = {y ∈ Σ A : α(x, y) < 1 κ + ǫ, h µ φ (y) ≥ ẽ- A -P A (φ| Σ A )} ⊂ {y ∈ Σ A : α(x, y) < -P A (φ| Σ A ), h µ φ (y) ≥ ẽ- A -P A (φ| Σ A )} ⊂ ∞ j=0 {y ∈ Σ A : h µ φ (y) ∈ jε, (j + 1)ε + ẽ- A -P A (φ| Σ A )}. and (10•3) I κ (π(x)) ⊂ π(y) : α * (x, y) ≤ 1 κ .
Next we need the following lemma to prove the reverse inequalities.

Lemma 10.2. For any x ∈ Σ + 2 and ν an ergodic Borel probability measure different from δ 0 ∞ and δ 1 ∞ we have

α * (x, y) = α(x, y) ν -a.e.
Proof. We will prove that α + (x, y) ≥ α(x, y) almost everywhere. The proof for α -(x, y) ≥ α(x, y) a.e. is similar. Since α * (x, y) = min{α -(x, y), α(x, y), α + (x, y)}, this will imply the lemma. Fix ǫ > 0. Let 1 n be the characteristic function of the cylinder set consisting of n 1's. Since ν is not concentrated on 1 ∞ we can find an n ǫ sufficiently large that τ + m (x, y) ≥ τ k-1 (x, y). For a given x, the more 1's at the end of C m (y) is the only way to enlarge the difference of x's hitting times of C + m (y) and C m (y). Let n > n 0 , m > n-l-1 and assume that we have a block of n + l ones at the end (l > n). Then (10•4) becomes τ + m (x, y) ≥ τ m-n-l-1 (x, y). The worst situation is when this block occurs very early. We are going to estimate this first occurrence. First we observe that

ǫ > 1 m S m 1 n (y) ≥ l m .
This implies that the first occurrence of the block in question is not earlier than mnl -1 ≥ m -2l > m(1 -2ǫ). Letting ǫ → 0 we obtain the result.

We continue with the proof of the theorem. For any Borel set A we have Let t(κ) = q(κ) if 1 κ ≥ e max and t(κ) = 0 otherwise. Suppose ε > 0. By continuity of the multi-fractal spectrum we have Thus π(y) ∈ F κ (π(x)) for µ qtκ-ε)φ a.e. y and dim H F κ ≥ h µ t(κ-ε)φ . Taking the limit ε → 0 shows dim H F κ (π(x)) ≥ h µ t(κ)φ = dim H π(F κ (x)).

This completes the proof for the set F κ . It remains to show that dim H I κ (π(x)) ≤ dim H π(I κ (x)). If 1 κ ≥ e max then this is trivial since dim H π(I κ (x)) = 1. Observe that for any κ we have dim H I κ π(x) ≤ 1 κ . To see this consider the natural covering (T n π(x) -1 n κ , T n π(x) + 1 n κ ) of I κ (π(x)). The s-covering sum is

1 n κs < ∞ if s > 1 κ . Therefore, if 0 < 1 κ ≤ h µ φ , we have dim I κ (π(x)) ≤ 1 κ = dim H (I κ (x)). Finally if h µ φ ≤ 1
κ < e max the for any Hölder function φ ∈ H α (S 1 ) let φ = φ • π. We have φ ∈ H α (Σ 2 ) and φ(x 1 , . . . , x n 01 ∞ ) = φ(x 1 , . . . , x n , 10 ∞ ) thus by the Gibbs property we have By Theorem 5.2 for µ φ -a.e. x we have that the last set is contained in {y : α * (x, y) < 1 κ , h µ φ (y) ≥ 1 κ }.

Thus Lemma 6.1 implies that for any ε > 0 there are at most C(ε) • 2E( 1 κ )n cylinders of length n needed to cover {y : α * (x, y) < 1 κ , h µ φ (y) ≥ 1 κ + ε} . Hence dim H (I κ (π(x))\π(I κ (x)) ≤ E( 1 κ ) = dim H π(F κ (x)).

Corollary 10.3. For µ φ a.e. x we have F κ (π(x)) = ∅ if 1 κ > e + . In Theorem 2.3 and Corollary 4.3 we can ignore the delta measure on fixed points since they have zero entropy and therefore do not give any contribution. This transfer procedure allows us to conclude the following Theorems and Corollaries from the analogous results of the section 8. These results contain more information than those stated in the introduction, thus we reformulate them. We set ν φ = µ φ • π -1 .

Theorem 10.4. (Theorem 1.1) κ φ,ψ = 1 -S 1 φ dν ψ = 1 hν φ (y) = - Corollary 10.6. For ν φ a.e. s sup -P ′ (q)≥ 1 κ [P (qφ) -P ′ (qφ)q] ≥ dim H F κ (s) ≥ sup

-P ′ (q)> 1 κ [P (qφ) -P ′ (qφ)q] .
For ν φ a.e. s and for κ < 1/h ν φ sup -P ′ (q)≤ 1 κ [P (qφ) -P ′ (qφ)q] ≥ dim H I κ (s) ≥ sup

Proof.

  We have L possibilities for the cylinder C. Let m := ⌊K/(1 + ω)n⌋ -1. Fix a choice C from these L cylinders and let D 0 , . . . , D m denote any cylinders of length n (possibly with repetition), which are disjoint from C. Choose ω > 0 so that β ω < 2 e + . Let d := d(n) := ⌊ωn⌋.

  If C and D are cylinders, we denote by C ⋆ D the cylinder C ∩ σ -|C| D. If we read C and D as words, C ⋆ D is nothing but the concatenation of the words C and D. Let d ≥ 1 be an integer, by C ⋆ d D we mean C ∩ σ -(|C|+d) D, i.e.

1

  n (x) dν(x) < ǫ (∀n > n ǫ ). Now let y be a generic point for ν. Then there is ann 0 = n 0 (y) > n ǫ such that 1 m S m 1 n (y) < ǫ (∀m > n 0 ).Let us consider the structure of C + m (y).C + m (y) = [y 1 • • • y m-1 1] if y = y 1 • • • y m-1 0 • • • C + m (y) = [y 1 • • • y k-1 100 • • • 0] if y = y 1 • • • y k-1 011 • • • 1y m+1 • • • . It follows that C + m (y) ⊂ C k-1 (y)where k = k(y, m) is characterized by y k = 0 and y j = 1 (∀k < j ≤ m}). Thus(10•4)

  dim H πA = h top (A) since diam π(C) = 2 -|C| for any cylinder set C. Thus applying Theorem 5.3 yields dim H π(F κ (x)) = h top (F κ (x)) = h µq(κ)φ .

  lim ε→0 h t(κ-ε)φ = h t(κ)φ and h µ t(κ-ε)φ (yκ-ε)φ -a.e. y.By Corollary 4.3 for µ φ × µ q(κ-ε)φ for a.e. (x, y) we haveα * (x, y) = α(x, y) = h µ φ (y) > 1 κ .

  µ φ (y) = h µ φ (y) for all y ∈ Σ 2 . Consider the setI κ (π(x))\π(I κ (x)) = {y : π(y) ∈ I κ (π(x)), y ∈ F κ (x)} ⊂ {y : α * (x, y) < 1 κ , α(x, y) ≥ 1 κ }.

  qφ) -P ′ (qφ)q] . Corollary 10.7. (Theorems 1.3 and 1.4) For a typical potential φ and ν φ a.e. s we havedim H F κ (s) = dim H (S 1 ) = h top (S 1 ) = 1 for 1/κ ≤φ dLeb., dim H I κ (s) = dim H (S 1 ) = h top (S 1 ) = 1 for 1/κ ≥φ dLeb..

.Figure 2 .

 2 Figure 2. The dimension graphs in the typical, nontypical and degenerate cases. The graph of dim H F κ (s) is dotted and the graph of dim H I κ (s) is solid.

Acknowledgment The authors thank L.-M. Liao and Q.-L. Li for their useful remarks.

where the second union is taken over all possible collections C 1 , • • • , C K of (ℓ -L ′ , ε)-cylinders, and where

Therefore, using the fact that the number of (ℓ -L ′ , ε)-cylinders is at most 2 (h+ε)(ℓ-L ′ ) , we have proved Lemma 7.5.

7.3. Generalized quasi Bernoulli property.

In order to estimate the measure µ φ (E t (C 1 , • • • , C K )), we need the following generalized quasi Bernoulli property.

Let A be any cylinder and L ≥ 1 be any integer. For x ∈ A, we define

where d(L) = ⌊ωL⌋ for some big ω > 1 (see Theorem 2.1).

Lemma 7.6 (Generalized quasi Bernoulli property). Let A be any cylinder, G ∈ C L,ε and ι A be defined as above. Then

Proof. Notice that

where

For i = 0, we have

For i ≥ 1, we have

So, by the multi-relation (2•4) we get

Thus, using the generalized Bernoulli property (Lemma 7.6), we have

Lemma 7.8.

Proof. By the last lemma, we have

where the sum is taken over all collections F 1 , . . . , F n ' consisting of different (L ′′ , 2ε)-cylinder contained in D ⋆ C. Recall that ñ is defined in (7•3).

Since

, we have

So,

7.5. Number of branches of a tree: Proof of Theorem 7.4. By Lemmas 7.5 and 7.8, we have

and for ℓ ≤ L ′′ , we have on one hand

and on the other hand

which implies that there exists an integer n 0 (ε) such that if ℓ -L ′ ≥ n 0 (ε) we have

So, from (7 •5), (7•6) and(7•7) we get

¿From (7•8) and ( 7•9), we get

Summing over all K ≤ 2 (c-2ε)(ℓ-L ′ ) , we obtain

for large L ′′ , because 2

-2 (c-ε)L ′′ 2(L ′′ +d) tends to zero superexponentially fast.

7.6. The Cantor set and lower bound of dim H {y : α(x, y) ≤ c}.

The next theorem is an improvement of the mass transference principle [BV] to the multi-fractal measure µ φ .

Theorem 7.9. (Multi-fractal mass transference principle) For 0 < c < h µ φ , and for µ φ -a.e. x we have

Proof. Let ε > 0 be an arbitrary small number. We can find an increasing sequence of integers (L k ) k≥0 such that

Lemma 8.5. For µ φ a.e. x we have

Proof. ¿From multi-fractal analysis, it is well known that

Therefore

by Lemma 3.2, Lemma 3.3 and Theorem 5.2.

Using the techniques developed in the previous sections we can conclude a strong theorem on the structure of typical sequences. The subword structure of a typical sequence up to time L is completely determined by the entropy spectrum of the measure.

Corollary 8.6. Consider n ≪ L sufficiently large, a typical point x and the set of cylinders C n of length n satisfying µ(C n ) ∼ 2 -βn which are subwords of the cylinder C L (x), i.e. the orbit of x hits the cylinder C n before time L.

Here a n ∼ b n means that the ratio a/b is subexponential in n.

Extensions to subshifts of finite type

The previous results can be extended in a canonical way to subshifts of finite type: Σ + 2 is replaced by a subshift space Σ A and µ φ and µ ψ by two Gibbs measures of the subsystem σ : Σ A → Σ A . Extensions to symbolic spaces of several symbols are also obvious.

Here we consider another kind of extension. Given a compact subset K in Σ + 2 . What can we say about K ∩ I κ (x) and K ∩ F κ (x) ? We assume that the reference measures µ φ and µ ψ are Gibbs measure of the full shift

. We can answer this question when K = Σ A is a subshift of finite type. The proofs are still slight modifications of those for the full shift, thus we only sketch them briefly here. We will emphasize the differences.

Let Σ A ⊂ {0, 1} N be a subshift of finite type. We are interested in the following two sets:

and µ φ is of full support and ergodic.

The analysis of these sets is related to the determination of the following restricted entropy spectrum: Recall thatφdµ ψ is nothing but the conditional entropy of µ φ relative to µ ψ . Let

) and N = 1 implies that each of the (countably many) sets on the right hand side is empty for µ φ -a.e. x.

Transferring to the circle

In this section we show that the results of the section 8 hold for the doubling map of the circle, i.e. replacing F κ (x), I κ (x) by F κ (s), I κ (s). Recall that the projection π : Σ → S was defined in the section 2. For y ∈ Σ

n (y) denotes the cylinder of length n preceding C n (y) in the lexicographical order and C + n (y) denotes the immediate successor. Theorem 10.1. For µ φ a.e. x we have

to S 1 is an interval around π(x). Moreover we have

Applying the left inclusion, it follows that

Hence dim H (F κ π(x)) ≤ dim H π(F κ (x)), and similarly dim H (I κ π(x)) ≥ dim H π(I κ (x)). We turn to the reverse inequalities. For this we define

x, y), τ n (x, y), τ + n (x, y)} and α * (x, y) = min{α -(x, y), α(x, y), α + (x, y)} where α * , α -, α + are defined in the corresponding way. Therefore in analogy to Lemma 3.2

Let q κ be the number such that

Remark: 1) If κ > 1 then l n < ∞ and we can not cover Lebesgue almost all points infinitely often no matter which orbit we consider. Thus it is likely that the dimension of I κ (s) is less than 1. In the degenerate case this is clear. To see this in the nondegenerate case note that since the graph of the entropy spectrum is below the diagonal we have 1 = h top = E(e max ) < e max . Therefore the maximum dimension (i.e. 1) is attained for κ < 1.

2) For a non typical potential we have possibly discontinuities of the function E(t) at e ± . At these points the upper and lower estimates of Corollary 10.6 do not coincide. This indicates that the question about infinite versus finite covering can not be completely answered in terms of the exponent κ. At this point the answer might depend on a constant c where l n = c n ν . This is in particular the case for the i.i.d. case mentioned in the introduction. The dynamical analog is Lebesgue measure whose entropy spectrum is degenerate. Therefore we can not get any information about the sequence c n which resembles the i.i.d. case. Theorem 10.8. (Theorem 1.2) For ν φ a.e. s we have F κ (s) = ∅ for κ < 1 inf µ ergodic φ dµ = κ F φ,S 1 .

These results are summarized in Figure 2.

Remark: The result of Corollary 8.6 can also be transferred to the circle. The interpretation of this result is as follows. The distribution of a typical orbit up to time L is completely determined by the entropy spectrum of the measure.


Eulalie Coevoet

Adrien Escande

Christian Duriez

Optimization-based inverse model of Soft Robots with Contact Handling

This paper presents a physically-based algorithm to interactively simulate and control the motion of soft robots interacting with their environment. We use the Finite Element Method (FEM) to simulate the non-linear deformation of the soft structure, its actuators, and surroundings, and propose a control method relying on a quadratic optimization to find the inverse of the model. The novelty of this work is that the deformations due to contacts, including self-collisions, are taken into account in the optimization process. We propose a dedicated and efficient solver to handle the linear complementarity constraints introduced by the contacts. Thus, the method allows interactive transfer of the motion of soft robots from their task space to their actuator space while interacting with their surrounding. The method is generic and tested on several numerical examples and on a real cable-driven soft robot.

I. INTRODUCTION

Soft robotics is an emerging opportunity to re-think the way robots are designed, used, and controlled, and to provide new capabilities. Using soft materials or flexible structures, these robots take motion by deformation. In opposition to articulated rigid structures, the kinematics do not only depend on the geometry, but also on the material properties. Moreover, they have a theoretical infinite number of degrees of freedom and it is hard to get an analytic model that describes the mechanical behavior with accuracy. These characteristics make their modeling and control more complex, particularly when the robot is being deformed by contact with its environment. This issue has been identified as a challenging open problem by several reviews on soft robotics [START_REF] Trivedi | Soft robotics: Biological inspiration, state of the art, and future research[END_REF] [2] [START_REF] Rus | Design, fabrication and control of soft robots[END_REF]. In this work, we propose the first generic method for obtaining the inverse model of a soft robot in contact with a known environment. We use the Finite Element Method (FEM) for modeling the deformations and Lagrangian constraints for actuators. The inverse model is obtained by optimization and allows interactive control of the motion.

Soft robots are usually inspired by living organisms, such as snakes, octopi, or caterpillars that have a continuously highly deformable structure. The compliance of these bodies is particularly suitable for exploration and manipulation in cluttered and sensitive environments. Using large strain deformation, they can reduce or extend their nominal dimensions, bend, and adapt their shape to the environment. This compliance in the interaction reduces risks of damage for both the robot and its surrounding. This makes them ideal for safe interaction with human beings and especially for use in medical applications such as surgery. Therefore, it is essential to propose a control approach that takes into account possible collisions and adjusts the deformations needed to reach a desired position. Collisions and contacts handling are very challenging because they significantly increase the complexity of the control. In this paper, we propose an algorithm that includes contacts in the optimization process and a specific solver to compute the resolution at interactive rates (between 30Hz and 100Hz).

II. RELATED WORKS

A. Soft robot motion control

Several difficulties are experienced in the modeling and control of soft robots: First, the number of actuators is finite while the number of degrees of freedom is infinite. Therefore, many DoFs of the robot are not directly controllable. Second, the actuators can also be redundant and several possible deformable postures can lead to the same position of the end effector of the robot. Third, many new parameters (material properties, external loads, weight...) have an influence on the posture of the robot.

The kinematics of soft robots has been studied in the particular case of continuum robots [START_REF] Webster | Design and kinematic modeling of constant curvature continuum robots: A review[END_REF] [START_REF] Marchese | Design, kinematics, and control of a soft spatial fluidic elastomer manipulator[END_REF]. The authors use the hypothesis of a piece-wise constant curvature to keep a geometrical approach to the kinematics and simplify the problem. The approach is then based on defining the bending deformation of soft segments as curvatures. But this hypothesis requires a specific design of the robot and no external and local load. For soft robots with non-continuous curvature, a first approach based on the mechanical modeling and a real-time FEM simulation of the structure and its actuators was proposed in [START_REF] Duriez | Control of elastic soft robots based on real-time finite element method[END_REF] [START_REF] Largilliere | Real-time control of soft-robots using asynchronous finite element modeling[END_REF]. Our paper extends these works by using a specific solver to handle interactions and self-collisions in the simulation. In this paper, the inverse problem is formulated as a Quadratic Program (QP) with linear complementarity constraints.

B. Inverse model of deformation with contact handling

Inverse FEM simulation with contact handling has been used in a few works in computer graphics, to control motion of actuated virtual soft bodies [8] [9] [10] [START_REF] Tan | Soft body locomotion[END_REF]. In [START_REF] Kim | Direct control of simulated non-human characters[END_REF] and [START_REF] Liu | Simulation and control of skeleton-driven soft body characters[END_REF] the authors propose to control simulated skeletondriven deformable characters in near real-time. They use a penalty-based contact model to simulate collision. However, in some cases, in order to make the character use the ground for push off, they temporarily create a hard constraint between a bone and the ground. In our work, we made no assumption on the characteristics of a contact, allowing each contact to be used for the actuation. We use Signorini's law Fig. 1: Illustration of the quantities of eq. 3 for a deformable robot with cable actuation (in blue), in the presence of an obstacle (grey square). E * is the desired position for the controlled point E.

to model the collision and guarantee a physical response. While more general, this makes the problem harder to solve in real-time. In [START_REF] Tan | Soft body locomotion[END_REF], the authors use FEM and muscle fibers actuation to simulate a soft body character's locomotion. The solver we propose in this paper to handle the complementarity constraints introduced by Signorini's law, is similar to theirs. However, in this study, we propose to find the inverse of the model of real robots. The method has realtime performance thanks to, among others, a projection of the model in the space of the optimization variables. To the best of our knowledge, this paper is the first work in soft robotic to propose an interactive motion control in the task space which handles interactions with the environment.

III. METHOD

A. Inverse problem formulation

The goal is to find how to actuate the robot so that selected points reach desired positions. We use the FEM implementation provided by the framework Sofa [START_REF] Faure | Sofa: A multi-model framework for interactive physical simulation[END_REF] and a tetrahedral or hexahedral mesh representation of the robot body to simulate the deformation of the volume structure. The tetrahedral volumetric meshes are generated with the software Gmsh or the CGALPlugin of Sofa.

The configuration of the robot at a given time is obtained by solving the static equilibrium between the internal forces of the deformable structure f (x), the external loads f ext (such as gravity) and the contributions of actuators H T a λ a and contacts H T c λ c , yielding:

f (x) = -f ext -H T a λ a -H T c λ c , (1)
with H T the direction of the effort applied by the constraints (actuators and contacts) on the FEM nodes and λ the intensity of this effort. At each time step i of the simulation, we compute a linearization of the internal forces:

f (x i ) ≈ f (x i-1 ) + K(x i-1 )dx (2)
where K(x) is the tangent stiffness matrix that depends on the current position of the FEM nodes, and dx is the difference between consecutive positions in time dx = x ix i-1 . The size of the matrix K is related to the number of FEM nodes, which is often very large. An optimization in the motion space would then be computationally expensive. Instead, we project the model in the space of the actuation and contact variables, leading to (see [START_REF] Duriez | Control of elastic soft robots based on real-time finite element method[END_REF] for more details):

  δ e δ a δ c   =   W ea W ec W aa W ac W ca W cc   λ a λ c +   δ free e δ free a δ free c   (3)
δ max ≥ δ a ≥ δ min (4) λ max ≥ λ a ≥ λ min (5) 0 ≤ λ c ⊥ δ c ≥ 0 (6)
where matrices c) are homogeneous to a compliance, and gather the mechanical coupling between effector points e, actuators a and contacts c. We thus have a relation between the actuator and contact forces, λ a and λ c , the shift between controlled points and their desired positions δ e , the displacement (or volume growth for pneumatic actuation) of actuator δ a and the gap between two colliding points δ c (see Fig. 1). Eq. ( 4) and ( 5) respectively are, constraints on actuators such as limits on the cables displacements, and limits on actuation forces. In this work, we follow Signorini's law for contact [START_REF] Duriez | Control of elastic soft robots based on real-time finite element method[END_REF]. We do not consider friction. This law guaranties that there is no interpenetration and that the contact forces are well oriented. The values δ free e , δ free a and δ free c respectively corresponds to the shift δ e , the displacement (or volume growth) δ a , and the interpenetration δ c computed during a free motion, that is when solving the structure with no effort on actuators and contacts, i.e λ a = 0 and λ c = 0 (see [START_REF] Duriez | Control of elastic soft robots based on real-time finite element method[END_REF]). We note n a and n c the number of actuator and contact forces.

W ij = H i K -1 H T j (i, j = e, a,
To control the robot, we want to find the actuation λ a so that effectors reach their desired positions. This corresponds to minimizing the norm δ e , while respecting the constraints (4), [START_REF] Marchese | Design, kinematics, and control of a soft spatial fluidic elastomer manipulator[END_REF], and [START_REF] Duriez | Control of elastic soft robots based on real-time finite element method[END_REF]. Using eq. ( 3) to get the expressions of δ e and δ c , we formulate the following Quadratic Program with (linear) Complementarity Constraints (QPCC):

min. λc,λa W ec λ c + W ea λ a + δ free e 2 (7) s.t. A λ a λ c ≥ b 0 ≤ λ c ⊥ W cc λ c + W ca λ a + δ free c ≥ 0
When no potential collision has been detected (n c = 0), the problem is a simple QP. Note that λ c is part of the optimization variables, which allows the controller to make use of contact forces to achieve the desired motion.

If the robot has a number of actuators greater than the DoFs of the controlled points, the QPCC may have an infinite number of solutions. In such case, we introduce in the minimization expression, the mechanical work of the actuator forces E = ∆δ a λ a , with ∆δ a = δ a -δ f ree a the displacements of the actuators during a time step. E is linked to the mechanical energy of the robot deformation. We then minimize the sum (||δ e ||2 + E), with chosen sufficiently small so that the deformation energy does not disrupt the quality of the controlled points positioning. In the implementation, we use = 1e -3 ||W T ea W ea || ∞ /||W aa || ∞ (with the norm ||.|| ∞ being the maximum absolute row sum of the matrix). A unique solution of the problem can then be found, without a significant impact on the quality of the solution. In the rest of the paper, we omit this damping term E, for the sake of clarity. It is straightforward to extend the developments below to incorporate it.

B. Quadratic program with linear complementarity constraint solver

Recent works in optimization have addressed the problem of linear and quadratic programs with linear complementarity constraints [START_REF] Hu | On linear programs with linear complementarity constraints[END_REF] [START_REF] Bai | On convex quadratic programs with linear complementarity constraints[END_REF]. They seek to find the global optimum of the problem and demonstrate that it can be accomplished in finite time. However, as finding the global minimum is difficult to achieve in real-time, we developed our own specific solver based on the decomposition method as mentioned in [START_REF] Chen | An active set method for mathematical programs with linear complementarity constraints[END_REF].

The complementarity constraints (6) defines 2 nc choices. Each of them can be characterized by a subset I of {1, . . . , n c } giving the elements of λ c that are forced to be zero. Let e i be the i-th column of the n c -by-n c identity matrix, and define S I as the matrix whose columns are the e i for i in I. Given a matrix M , M S I (respectively S T I M ) selects the columns (respectively rows) of M indexed by I. Likewise, we define SI for i not in I. S I SI is a permutation (and thus orthonormal) matrix. Given a complementarity choice I, QPCC (7) rewrites min.

λa,λc

W ea λ a + W ec λ c + δ f ree e 2 (8) s.t. Aλ a ≥ b (9)
S T I λ c = 0 (10)

S T I (W cc λ c + W ca λ a + δ free c ) ≥ 0 (11) SI T λ c ≥ 0 (12) SI T (W cc λ c + W ca λ a + δ free c ) = 0 (13)
This is a QP piece of (7) we refer to as QP I .

We propose an iterative method that starts from an initial feasible set I. After solving QP I , we inspect the state of the inequality constraints. If an inequality constraint has reached its boundary at the end of the optimization, it means that the solution may potentially be further optimized by pivoting the corresponding constraint. We set each inequality constraints that reached their boundary at the end of the optimization as candidate for pivot. To guarantee the convergence of the algorithm only one constraint can be pivoted at a time. As mentioned in [START_REF] Chen | An active set method for mathematical programs with linear complementarity constraints[END_REF], one way to determine which constraint should be the best candidate for pivot is to examine the values of the dual variables. In our implementation, we select the candidate with the greater dual variable. By pivoting the corresponding complementarity constraint we get a new QP with a different set of linear constraints. We solve this new problem and repeat the process until there is no more candidate for pivot, effectively solving a sequence of QP I .

A proof of the convergence of this kind of algorithm to a stationary point is given in [START_REF] Giallombardo | Multiplier convergence in trust-region methods with application to convergence of decomposition methods for mpecs[END_REF].

C. Reduced formulation

The above scheme can be improved by taking into account the specificity of our problem. Indeed, W cc is positive definite (because K is positive definite). As a result (see below equations), λ c is an affine function of λ a for a given I. This allows the removal of λ c from QP I to solve a smaller problem. We name this the reduced formulation. In the remainder of this section, we drop the index I for matrices S I and SI .

Using that λ c = S S S S T λ c = SS T λ c + S ST λ c , we get from eq. ( 10) that λ c = S ST λ c . Reintroducing this result in eq. ( 13), and solving for ST λ c yields:

ST λ c = -ST W cc S -1 ST W ca λ a + δ free
λ c = S (A I λ a + b I ) (14)
and QP I is equivalent to the following QP we name QP r I :

min.

λa

W ec SA I + W ea λ a + W ec Sb I + δ f ree e 2 (15)
s.t. Aλ a ≥ b A I λ a ≥ b I S T W cc SA I + W ca λ a + S T W cc Sb I + δ free e ≥ 0
We obtain QP r I by solving eqs. ( 10) and ( 13), what would have been done anyway by the QP solver. But we did so by leveraging the structure of the problem (with respect to λ a and λ c ), and we can take into account the fact that ST W cc S is positive definite 1 . In particular, we can use the Cholesky decomposition of ST W cc S to compute its inverse 2 , which is much cheaper computationally than the more general decomposition the QP solver would need to use. As a result, given the matrices W ij and A, and the vectors δ f ree i and b, solving QP I is slower than computing the matrices and vectors in QP r I and solving QP r I . The ratio between the two computation times depends on n a and n c . When n a >> n c , the timings are the similar (in particular, if n c = 0, both problems are the same). However, for a fixed n a , the reduced formulation becomes better and better as n c increases. For example, for (n a , n c ) = (3, 3), the average ratio is 1.25. It is 1.88 for (3, 10), and 7.82 for (3, 50). Usually, n c is much larger than n a so that the reduced formulation has a real computational advantage.

The computation time could be further reduced when we consider the sequence of resolutions performed in the iterative method described above. Indeed, in this case, two successive set I differ by only one element, so that we pass from one matrix ST W cc S to an other by adding or removing one row and one column. Therefore, there is no need to compute the Cholesky decomposition from scratch at each iteration, but it can rather be updated. The full decomposition is in O(k 3 ) where k is the size of the matrix, while the update is in O(k 2 ) [START_REF] Golub | Matrix computations[END_REF]. Preliminary tests show that this reduces the computation time by 20 -25% for all but the first iteration. We do not use this improvement yet in the controller.

D. Initialization

As mentioned above, our solver requires an initial feasible set I. In the implementation, this initial set is found by solving the contacts as a Linear Complementarity Constraint (LCP) while considering the actuator force λ a constant:

δ c = W cc λ c + W ca λ a + δ f ree c 0 ≤ λ c ⊥ δ c ≥ 0 ( 16
)
This system has a solution for any λ a because W cc is positive definite [START_REF] Murty | On the number of solutions of the complementarity problem and spanning properties of complementarity cones[END_REF]. Thus there is always at least one feasible set I. Furthermore, the solution is unique, and is given explicitly by eq. ( 14). The initial guess of λ a is either 0 or the solution of the previous QPCC optimization when it is available (warm start).

E. Visualization

A by-product of the reduced formulation is that it allows one to visualize the problem when n a is small (1,2 and partially for 3), even for complex contact configurations, with large n c . This is helpful to better understand the properties of the problem, and it also has an educational value.

For a given I, the two last constraints of QP r I defines a polytope P I (possibly empty or unbounded) in the space of λ a . A face of this polytope corresponds to one line of these constraints holding as an equality, i.e. a change of complementarity choice. Since for every λ a there is at least one I (and that when there are more than one, this corresponds precisely to changes of complementarity choices), the union of these polytopes cover the whole space of λ a . Two polytopes P I1 and P I2 may share a part of their boundaries, when one goes from I 1 to I 2 by at most n a changes (pivots).

Since for each λ a there is a unique λ c , we can express the cost function of the QPCC (7) as a function of λ a only (for a given I, it is the cost function of QP I ). We denote as c(λ a ) this function. It is defined by pieces, each piece support being a polytope P I . With this representation, the original QPCC can be seen as an optimization problem with a piecewise-defined cost function with only the constraint on the actuation: There are two local minima corresponding to pulling one cable or the other. Pulling slightly the lower cable (up to λ a1 ≈ 75N , local minimum with the green cross) lowers the beam but pulling more makes the end effector go up due to the lower contacts. Pulling on the upper cable makes use of the upper contacts to lower the end effector and reach the global minimum (red cross, λ a2 ≈ 495N ). One can see valleys along λ a1 = λ a2 . This is because the two cables are opposite, thus for a given λ a , λ a + (µ, µ) T (µ ∈ R) gives a similar (but not identical) end-effector displacement. Fig. 3: An example for the same robot and different positions of obstacles, with λ a ∈ [0, 2000] 2 . Starting from λ a = (0, 0) (thin red zone in the upper right), our solver iterates across the regions in that order: red, orange, dark purple, green, cyan, brown, and finally blue, where the global minimum (red cross) is obtained. Note that the order to choose the pivot has an impact here: one could also have gone from the dark purple region to the gray one, and ended up in local minimum.

IV. EXPERIMENTS AND RESULTS

A. Numerical examples

In this section we describe the results of our method on several numerical examples. We use qpOASES [START_REF] Ferreau | qpOASES: A parametric active-set algorithm for quadratic programming[END_REF] to solve the QPs. In each case we control one point of the model and the target is interactively moved by a user or follows a predefined trajectory.

1) Tower: the first example is a simulation of a soft body with four cavities actuated with pressure (Fig. 5). Each inflatable section being separate from the others by a self-collision region. In this example, having the controlled point (top of the body) reaches its desired position entail the use of self-collisions. Note that, as the solver converges to a stationary point and not the global solution, the contacts have to be active (λ c > 0) at the beginning of a QP resolution to be exploited by the actuation.

2) Rod: the second example is a simulation of a soft rod insertion into a pipe with a fork (Fig. 6). The rod has five actuators; four cables allow for orientation of the rod end-effector (up / down / left / right), and the fifth one moves the rod extremity along a fixed direction allowing its insertion into the pipe. Using our controller, we were able to optimize the five actuators so that the rod end-effector could be inserted in both branches. These results could be interesting, for instance, in interventional radiology, where therapeutic tools are inserted within the arteries through a catheter. We could imagine a simulation of the intervention, available in the operating room, and adapted to the patient's anatomy and physiology, to help the physician.

3) Beam: in Fig. 4 we show a simulation of a soft beam with one extremity fixed. The soft object is placed between two close obstacles that change the coupled direction between the actuators (two opposite cables) and the controlled point (tip of the beam). This simple example illustrates how the contacts are part of the optimization and can be used by the actuation to optimize the end-effector. 4) Two deformable bodies in contact: the last example is a simulation of two colliding soft bodies (Fig. 7), each body having some fixed part. The problem we want to solve in this inverse simulation is how to push the wall of a first deformable body, using an instrument, so that we can control a point of a second deformable body, thanks to transmission of forces allowed by contacts. In this example, we show that our method could have possible extension in medical applications (like medical robotics): Indeed, for some medical applications, it could be useful to know how much force/displacement to apply on a deformable wall (for instance with ultrasound probe when doing robotic assisted echography) in order to obtain a desired motion on an underlying deformable organ. Of course, dedicated study would be necessary to validate the use of the method in such an application. Here it just demonstrates the genericity of our algorithm and a potential larger use than soft robotics.

B. Real cable-driven soft robot

In this section we apply our method on a real cable-driven soft trunk-like robot made of silicone. In each experimental scenario we control the tip of the trunk and the target is interactively moved using a Gametrak device or follows a predefined trajectory.

The robot is actuated with eight cables. Four cables actuate a first section of the trunk while the other four go through the entire trunk (see Fig. 9), allowing it to perform a S-shape. In practice, we place flexible tubes inside the silicone that allows the cables to slip with low friction. To represent, in the simulation, the additional rigidity created by these tubes, we use a model of stiff springs in the direction of the tubes. The real trunk is attached to a platform moving along the robot direction, allowing a forward and backward displacement. This actuation is also modeled in the simulation. In this way, we were able to interactively drive the trunk end-effector between two cylinders using the optimization (see Fig. 8).

In Fig. 10, we show an example of the same robot but with a moving obstacle (a rigid cylinder). We used a Gametrak device to interactively update the position of the moving obstacle in the simulation. Using our algorithm we were able to find the new configurations of the robot actuation so that the end-effector keeps a fixed position. Having a realtime control of the robot motion could also be beneficial in scenarios where the robot actuation is changed, for example if a cable brakes. With feedback from the real robot we could interactively remove the broken cable from the simulation and get in real-time a new configuration for the actuators. In Fig. 11 we simulated this scenario, by interactively removing one of the eight cables of the trunk-like robot (top one of the section 2, see Fig. 9). The algorithm was able to find a new configuration without losing the end-effector position.

C. Performance

In this section, we give the computation time 3 of each simulation shown in this paper. The two main computation steps of the simulation are the computation of the matrices W ij (i, j = e, a, c) and the resolution of the sequence of QP problems. In Table . 12, we show the average computation time for these two main steps. We can see that thanks to the projection of the model in the space of the actuation and contact variable, we are able to compute simulations at interactive rates (between 30Hz and 100Hz), and that the decomposition method we use to solve the contacts allows us to maintain these interactive rates. For more complex geometries, a large number of nodes may be required. In that case, the size of the FEM matrix will be large as well and the computation of W will take time. We use the work of [START_REF] Courtecuisse | Asynchronous preconditioners for efficient solving of non-linear deformations[END_REF]

a

  We define A I and b I such that the above relation rewrites ST λ c = A I λ a + b I . Then we have the affine relation

  min. λa c(λ a ) (17) s.t. Aλ a ≥ b When n a is 1 or 2, it is possible to draw the graph of c. We give examples of such graphs for n a = 2 on Fig. 2 and 3.

Fig. 2 :

 2 Fig. 2: Piecewise cost function for the problem corresponding to Fig. 4 (left), with λ a ∈ [0, 500] 2 . Each colored region correspond to a complementarity choice I and is supported by the corresponding polytope (polygon in the 2d case) P I .There are two local minima corresponding to pulling one cable or the other. Pulling slightly the lower cable (up to λ a1 ≈ 75N , local minimum with the green cross) lowers the beam but pulling more makes the end effector go up due to the lower contacts. Pulling on the upper cable makes use of the upper contacts to lower the end effector and reach the global minimum (red cross, λ a2 ≈ 495N ). One can see valleys along λ a1 = λ a2 . This is because the two cables are opposite, thus for a given λ a , λ a + (µ, µ) T (µ ∈ R) gives a similar (but not identical) end-effector displacement.

Fig. 4 :

 4 Fig. 4: Soft beam actuated with two cables. In this simulation we control the beam end-effector position. The orange spheres are fixed rigid obstacles. The white sphere is the desired position.

Fig. 5 :Fig. 6 :

 56 Fig.5: Soft tower with four cavities actuated with pressure. The algorithm determines how to inflate each cavity to get the end-effector reach the desired position (white sphere). Self-collision points are represented by red lines.

Fig. 7 :

 7 Fig.7: Possible extension of the method: registration of colliding deformable bodies. The red squares are the fixed points. We control the position (white sphere) of a point of the red body by applying a force on the brown one.

Fig. 8 :

 8 Fig. 8: Top: Real cable-driven soft robot, Bottom: Corresponding motion computed by the simulated inverse model. The input of the inverse model is the motion of the robot's tip.

Fig. 9 :

 9 Fig. 9: Design of the soft trunk-like robot actuated with eight cables. A slice view (left) and a side view (right).

Fig. 10 :

 10 Fig. 10: Top: Real cable-driven soft robot, Bottom: Corresponding motion computed by the simulated inverse model. We interactively move an obstacle while the input of the inverse model is a fixed position of the robot's tip.

Fig. 11 :

 11 Fig. 11: Top: trunk-like robot inverse simulation. Bottom: same simulation, with same end-effector target, after interactively removed one cable. The algorithm finds a new configuration in real-time without losing the end-effector position.

Fig. 12 :

 12 Fig.12:The different examples simulated, with their model used, the average number of contacts, the number of DoFs and the computation time in ms of the matrices W ij construction and sequence of QPs resolution.

  on asynchronous preconditioners to reduce this time and allow to compute in real-time, simulations of a robot with around 6000 DoFs.

	Example	Model Cont. DoFs W(ms) QPs(ms)
	Tower	FEM	21	1680 10.53	0.445
	Rod	Beam	47	66	0.757	3.136
	Beam	FEM	16	480	2.003	0.15
	Two bodies FEM	16	2313 10.458 0.123
	Trunk	FEM	76	1665 23.288 5.529

It is a principal minor of the positive definite matrix Wcc.

Note that, following the recommended practice, we do not compute explicitly the inverse. Rather (see[START_REF] Golub | Matrix computations[END_REF]), given the Cholesky decomposition ST Wcc S = LL T , with L a lower triangular matrix, we computeA I b I = -L -T L -1 ST Wca δ free a, where the left multiplication by L -1 and L -T are obtained by forward and backward substitution.

On a desktop computer with an i7 Intel processor 3.60GHz changing environment, and we could also use this feedback to correct errors introduced by the model.

V. CONCLUSION AND FUTURE WORK

We proposed a generic method for interactive simulation and control of soft robots interacting with their environment. This method is based on a FEM simulation of the robot and QP with linear complementarity constraints. We were able to achieve fast inverse computation thanks to a reduced compliance matrix between controlled point, actuator and contact and dedicated optimization solver taking advantage of the problem properties. The method was applied to several numerical examples and on a real cable-driven soft robot.

This work focused on non frictional contact, but as a future work we will look forward on adding friction to the problem. We would also like to use this work for trajectory planning. Controlling the robot interactively can be interesting in applications such as assisting the medical intervention of catheter insertion. However, for other tasks like robot locomotion for instance, we may use the simulation as a tool for command planning. We are also looking forward to close the control loop with feedback information extracted from vision sensors. It would allow the robot to progress in a ACKNOWLEDGMENT The authors would like to thank Sanae Mahtal for her contribution on this project, and Mario Sanz Lopez for his precious help on building the trunk-like soft robot.

*Adrien Escande is supported by the