Guy Barles

Some Homogenization Results for Non-Coercive Hamilton-Jacobi Equations

Keywords: Homogenization, Hamilton-Jacobi Equations, ergodic problems, levelset approach, viscosity solutions AMS subject classifications : 35B27, 35F20, 35F25, 49L25

Recently, C. Imbert & R. Monneau study the homogenization of coercive Hamilton-Jacobi Equations with a u/ε-dependence : this unusual dependence leads to a non-standard cell problem and, in order to solve it, they introduce new ideas to obtain the estimates on the oscillations of the solutions. In this article, we use their ideas to provide new homogenization results for "standard" Hamilton-Jacobi Equations (i.e. without a u/ε-dependence) but in the case of non-coercive Hamiltonians. As a by-product, we obtain a simpler and more natural proof of the results of C. Imbert & R. Monneau, but under slightly more restrictive assumptions on the Hamiltonians.

Introduction

In this article, we are interested in homogenization problems for first-order Hamilton-Jacobi Equations. The originality of this work is to provide results in the case of noncoercive Hamiltonians and applications to non-standard problems. Before describing more specifically our contributions, we want to point out that most of the new ideas used in this paper are borrowed from Imbert & Monneau [START_REF] Imbert | Homogenization of first-order equations with u/εperiodic Hamiltonians[END_REF] who study the homogenization of (coercive) Hamilton-Jacobi Equations with a u ε /ε-dependence, namely

u ε t + H(ε -1 x, ε -1 u ε , Du ε ) = 0 in R n × (0, +∞), ( 1
)
where H is a continuous and coercive Hamiltonian. In fact, the starting point of the present work and one of its main motivations was to solve such problems, maybe under more restrictive assumptions than in [START_REF] Imbert | Homogenization of first-order equations with u/εperiodic Hamiltonians[END_REF] but (i) with simpler and more natural methods and (ii) with a clearer explanation of the involved phenomenas. We will come back later on [START_REF] Alvarez | Homogenization of Hamilton-Jacobi equations in perforated sets[END_REF] and, in particular, we will explain the connections between the standard problems we are first dealing with and these non-standard problems.

In order to emphasize the main new ideas in our approach, we are not going to try to consider the most general framework but we restrict ourselves to a model case which carries the main difficulties. More precisely, we are going to study the limit as ε → 0 of the solution U ε (x, y, t) of the Hamilton-Jacobi Equation

U ε t + F (ε -1 x, ε -1 y, ε -1 t, D x U ε , D y U ε ) = 0 in R n+1 × (0, +∞), (2)
where x ∈ R n , y ∈ R, t ∈ (0, +∞), F (x, y, t, p x , p y ) is a continuous function on R 2n+3 which is Z n -periodic in x and 1-periodic in y and t. More precise conditions on F will be given later on but we point out that F is assumed to be coercive with respect to p x but not with respect to p y and this is the key new point. In order to give a flavour of the type of Hamiltonians we are able to consider, a typical example is

F (x, y, t, p x , p y ) = a(x, t)|p x | β + b(x, y, t)|p y | -f (x, t) ,
where a, b, f are Lipschitz continuous function with the right periodicity in x, y, t with a(x, t) ≥ η > 0 in R n × [0, +∞) and β ≥ 1. In particular, no sign condition is imposed on b, it may change sign and even the term b(x, y, t)|p y | can be replaced as well by a linear term b(x, y, t)p y .

In order to understand the contribution of this work, we recall that the theory of homogenization for first-order Hamilton-Jacobi Equation started with the famous unpublished work of Lions, Papanicolaou & Varadhan [START_REF] Lions | Homogenization of Hamilton-Jacobi Equations[END_REF] who completely solve the problem in the case of time-independent, periodic and coercive Hamiltonians i.e. for the above equation when F (x, y, p x , p y ) → +∞ when |p x | + |p y | → +∞, uniformly w.r.t x and y.

Then, to the best of our knowledge, such an assumption was used (one way or the other) in all the works concerning the homogenization of Hamilton-Jacobi Equations : for more general periodic situations (cf. Ishii [START_REF] Ishii | Homogenization of the Cauchy problem for Hamilton-Jacobi equations[END_REF]), for problems set in bounded domains (cf. Alvarez [START_REF] Alvarez | Homogenization of Hamilton-Jacobi equations in perforated sets[END_REF], Horie & Ishii [START_REF] Horie | Homogenization of Hamilton-Jacobi equations on domains with small scale periodic structure[END_REF]), for equation with different structure (cf. Alvarez & Ishii [START_REF] Alvarez | Hamilton-Jacobi equations with partial gradient and application to homogenization[END_REF]), for deterministic control problems in L ∞ (cf. Alvarez & Barron [START_REF] Alvarez | Homogenization in L ∞[END_REF]), for almost periodic Hamiltonians (cf. Ishii [START_REF] Ishii | Almost periodic homogenization of Hamilton-Jacobi equations[END_REF]) and for Hamiltonians with stochastic dependence (cf. Souganidis [START_REF] Souganidis | Stochastic homogenization of Hamilton-Jacobi equations and some applications[END_REF]).

The reason why this coercivity assumption plays a central role, is that it allows to solve the so-called "cell problem" which provides the homogenized equation, i.e. the homogenized Hamiltonian. When F is independent of time, this problem, which turns out to be an ergodic problem, consists in solving the pde

F (x, y, D x v + p x , D y v + p y ) = λ in R n+1 ,
and in showing that, for any (p x , p y ), there exists a unique constant λ = F (p x , p y ) such that this equation has a bounded (periodic) solution. In general, solving this cell problem is the main difficulty and, in most cases, the fact that F is, indeed, the homogenized Hamiltonian, follows rather easily. It is worth pointing out, anyway, that, in order to have a comparison result for the limiting equation, one has to prove that F satisfies suitable properties and this may be a difficulty in some cases. We refer the reader to Section 4 for a discussion in this direction.

In this framework, the role of the coercivity is rather clear since it provides an easy bound on Dv = (D x v, D y v) once one knows that F (x, y, D x v + p x , D y v + p y ) is bounded and this is a key argument to solve the cell problem. Up to now (again, to the best of our knowledge), no work (except perhaps partially [START_REF] Souganidis | Stochastic homogenization of Hamilton-Jacobi equations and some applications[END_REF]) succeeded to find an argument to solve this cell problem by pde methods in a general way which avoids the coercivity assumption on F (and actually one of the main question is to find the right set of assumptions to do it). Furthermore, when F depends on t, one has to find a space-time periodic solution of

v t + F (x, y, t, D x v + p x , D y v + p y ) = F (p x , p y ) in R n+1 × R , (3)
and the assumptions to do it seem even stronger (cf. Souganidis and the author [START_REF] Barles | Space-time periodic solutions and long-time behavior of solutions to quasi-linear parabolic equations[END_REF]). However it is worth pointing out that the pure pde approach we describe above for both homogenization and ergodic problems can be replaced, in some cases, by an approach using either optimal control (if F is convex) or differential games methods : in this framework, results do exist for non-coercive Hamilton-Jacobi Equations, the coercivity assumption being replaced by either controllability or non-resonance assumptions. We refer the reader to Alvarez and Bardi [START_REF] Alvarez | Viscosity solutions methods for singular perturbations in deterministic and stochastic control[END_REF][START_REF] Alvarez | Singular perturbations of nonlinear degenerate parabolic PDEs: a general convergence result[END_REF][START_REF] Alvarez | Ergodic problems in differential games[END_REF], Arisawa [START_REF] Arisawa | Ergodic problem for the Hamilton-Jacobi-Bellman Equation. I. Existence of the ergodic attractor[END_REF][START_REF] Arisawa | Ergodic problem for the Hamilton-Jacobi-Bellman Equation[END_REF], Arisawa and Lions [START_REF] Arisawa | On ergodic stochastic control[END_REF] and Artstein and Gaitsgory [START_REF] Artstein | The value function of singularly perturbed control systems[END_REF], Bardi [11] for results in this direction.

In order to solve problems like (3) in a general way and once for all (p x , p y ), we consider the ergodic problem : find a constant λ such that the equation

w t + G(x, y, t, D x w, D y w) = λ in R n+1 × R , (4)
has a bounded (periodic) solution. In fact, with our approach, we obtain a weaker but sufficient result which can take two possible forms : we can prove that there exists a unique constant λ such that we have either approximate continuous (but not necessarily Lipschitz continuous) periodic solutions or exact, possibly discontinuous, periodic sub and supersolutions. This result is the first main contribution of the paper and this is where we use in a key way the ideas of Imbert & Monneau [START_REF] Imbert | Homogenization of first-order equations with u/εperiodic Hamiltonians[END_REF] ; an unusual feature of the proof is the estimate of the oscillation max R n+1 ×R (w) -min R n+1 ×R (w) which replaces the classical gradient estimate and relies on two very original arguments. Once ( 4) is solved, the result for the homogenization problem follows by using the usual arguments : indeed, it is enough to (essentially) apply the result to (3) for any (p x , p y ), then to obtain suitable properties for F and finally to use the "perturbed test function's method" of Evans [START_REF] Evans | The perturbed test function method for viscosity solutions of nonlinear PDE[END_REF][START_REF] Evans | Periodic homogenisation of certain fully nonlinear partial differential equations[END_REF], even if, to prove the convergence, we have to introduce an additional argument to take care of the rather weak properties we impose on F in the variables x, t and p x . We refer the reader to the papers of Alvarez & Bardi [START_REF] Alvarez | Viscosity solutions methods for singular perturbations in deterministic and stochastic control[END_REF][START_REF] Alvarez | Singular perturbations of nonlinear degenerate parabolic PDEs: a general convergence result[END_REF] for a general approach of singular perturbation problems for fully nonlinear, possibly degenerate, elliptic or parabolic equations; this approach applies to homogenization problems, including in the case of first-order Hamilton-Jacobi Equations, and, in particular, the authors clarify the connections between ergodic and homogenization problems in a general setting. Now we come back to (1) which seems to have nothing to do with the above (rather) classical problem. Roughly speaking, the connection consists in considering (1) as the equation of the motion of the graph y = u ε (x, t) and to introduce the associated level set equation which is an equation in R n+1 . Since, intuitively, the level set equation should play a role only on the moving hypersurface, this leads to replace ε -1 u ε (x, t) by ε -1 y and to transform (1) in a standard (but a priori non-coercive) homogenization problem. The rigourous justification of this formal (but convincing) argument is easy by following the article of Giga & Sato [START_REF] Giga | A level set approach to semicontinuous viscosity solutions for Cauchy problems[END_REF] which is exactly describing the way to do it for firstorder equations (see also the paper of Biton, Ley & the author [START_REF] Barles | A geometrical approach to the study of unbounded solutions of quasilinear parabolic equations[END_REF] for motion by Mean Curvature). Compared to the article of Imbert & Monneau [START_REF] Imbert | Homogenization of first-order equations with u/εperiodic Hamiltonians[END_REF], this approach leads to more restrictive assumptions on H but to a far simpler proof and to more natural and understandable arguments. Typically the results of [START_REF] Imbert | Homogenization of first-order equations with u/εperiodic Hamiltonians[END_REF] apply for all H of the form

H(x, y, t, p) = a(x, t)(|p| 2 + 1) β/2 + g(x, y, t) ,
where a, g are continuous periodic functions with a > 0 in R n × R and 0 < β ≤ 1, while here we have to consider the case β = 1. Finally, it is worth pointing out that Imbert & Monneau [START_REF] Imbert | Homogenization of first-order equations with u/εperiodic Hamiltonians[END_REF] use also an extension to R n+1 by adding a extra variable but with no clear interpretation of this new variable which is just a trick in the proof.

The paper is organized as follows : in the first section, we study the ergodic problem (4); this is the occasion to present the key assumptions on G (and therefore on F ) which describe the structure of the problem allowing the lack of coercivity. In Section 2, we apply this result to the cell problem and we solve the homogenization problem; to do so, we show that F (p x , p y ) is a continuous function, which depends also continuously on F . Then, in Section 3, we consider the problem (1): we describe the Giga & Sato [START_REF] Giga | A level set approach to semicontinuous viscosity solutions for Cauchy problems[END_REF] approach and the assumptions on H to apply it; the conclusion then follows from the results of Section 2. Finally, we provide remarks on the possible variants and extensions of the above results in Section 4.

Acknowledgments :

The author wishes to thank Martino Bardi for interesting comments on the first version of this paper and, in particular, for pointing out some missing references. He also thanks the anonymous referees for their careful reading of the paper and their very constructive remarks.

The non-coercive ergodic problem

In order to state the result, we have to impose two kinds of assumptions: first some basic assumptions which ensure existence, uniqueness and comparison properties for the problems we are going to introduce and then structure conditions which allow to obtain the estimates we need to solve the ergodic problem. Again, to focus on the main ideas of the proof, we are not going to provide the most sophisticated assumptions but the simplest relevant ones.

(H1) G(x, y, t, p x , p y ) is a continuous function in R 2n+3 , Z n -periodic in x, 1-periodic in y and t.

(H2) Either G is independent of t and G(x, y, p x , p y ) → +∞ when |p x | → +∞, uniformly w.r.t. (x, y) ∈ R n × R and |p y | ≤ R for any R > 0, or G depends on t and there exists constants

C 1 , C 2 > 0 such that G(x, y, t, p x , 0) ≥ C 1 |p x | -C 2 in R n × R × R × R n .
(H3) The function G is locally Lipschitz continuous w.r.t. y, t, p y and there exists l ∈ R and C 3 , C 4 , C 5 ≥ 0 such that, for almost every ξ = (x, y, t, p

x , p y ) ∈ R 2n+3 |D y G(ξ)| ≤ C 3 |p y + l| , |D t G(ξ)| ≤ C 4 (1 + |p y | + |G(ξ)|) , |D py G(ξ)| ≤ C 5 .
Our result is the following Theorem 1.1 Under assumptions (H1)-(H3), we have (i) For any α > 0, there exists a unique continuous, space-time periodic solution w α of

w α t + G(x, y, t, D x w α , D y w α ) + αw α = 0 in R n+1 × R , which is independent of t if G is independent of t.
(ii) There exists a constant K = K(G) depending only on G through C 0 := ||G(x, y, t, 0, 0)|| ∞ , l and the coercivity assumption (H2), such that max

R n+1 ×R w α -min R n+1 ×R w α ≤ K .
In particular, if G depends on t, then

K = K(C 0 , C 1 , C 2 ,

l).

(iii) There exists a unique constant λ such that the equation

w t + G(x, y, t, D x w, D y w) = λ in R n+1 × R , (5)
admits bounded, possibly discontinuous, sub and supersolutions.

(iv) If v 0 is bounded uniformly continuous in R n+1 , there exists a unique solution v of the initial value problem

v t + G(x, y, t, D x v, D y v) = 0 in R n+1 × (0, +∞) , (6)
v(x, y, 0) = v 0 (x, y) in R n+1 , (7)
which is bounded and uniformly continuous in R n+1 × [0, T ] for all T > 0; moreover we have

lim t→+∞ t -1 v(x, y, t) = -λ , the limit being uniform in R n+1 .
We have chosen to state Theorem 1.1 in that way for several reasons : first, even if the result (i) seems to be classical, it is not the case because the assumptions (H1)-(H3) are not completely standard and it may not be so clear that the w α -equation has a unique solution. Indeed, we only assume G to be continuous in x, which is a very weak assumption, but this is compensated by the coercivity of G in p x . To prove (i) which is the first (slight) difficulty of the proof, we borrow arguments from P.L. Lions and the author [START_REF] Barles | Remarks on existence and uniqueness results for first-order Hamilton-Jacobi equations[END_REF] and the author [START_REF] Barles | Uniqueness and regularity results for first-order Hamilton-Jacobi equations[END_REF]. Then (ii) is the main step but (curiously) not the most technical one. (iii) is one of the possible conclusion but if one insists to use continuous "correctors", then (ii) implies that, for any δ > 0, if α is small enough, we have

λ -δ ≤ w α t + G(x, y, t, D x w α , D y w α ) ≤ λ + δ in R n+1 × R ,
since, as usual and by using (ii), λ is the uniform limit of -αw α . Finally (iv) is an other classical characterization of the ergodic constant λ.

Proof : We provide the proof in the case when G actually depends on t, the other case being simpler (see the remark at the end of the section).

1. We start by (i). We just sketch the proof and refer to [START_REF] Barles | Remarks on existence and uniqueness results for first-order Hamilton-Jacobi equations[END_REF], [START_REF] Barles | Uniqueness and regularity results for first-order Hamilton-Jacobi equations[END_REF] and [START_REF] Barles | Solutions de viscosité des équations de Hamilton-Jacobi. Collection[END_REF] for the (easy) details. As it is classical in viscosity solutions' theory, the existence of w α relies on having a Strong Comparison Result for the equation, the existence being obtained by the Perron's method extended to the framework of viscosity solutions by Ishii [START_REF] Ishii | Perron's method for Hamilton-Jacobi equations[END_REF]. Here, because of the periodicity of G, Perron's method can be applied in the set of periodic subsolutions (by remarking that if w is as a subsolution, w(x, y, t) := sup{w(x + l, y + k, t + m, l ∈ Z n , k, m ∈ Z} is still a subsolution), we can prove the comparison result only for periodic sub and supersolution which avoids problems with the unboundedness of the domain.

To prove this comparison result, we argue in the following way: if u is an usc periodic subsolution and v a lsc periodic supersolution of the equation, we approximate max R n+2 (u -v) by max R 2n+4 (Ψ) where Ψ = Ψ η,β is given by

Ψ(x 1 , x 2 , y 1 , y 2 , t, s) := u(x 1 , y 1 , t) -v(x 2 , y 2 , s) - (x 1 -x 2 ) 2 η 2 - (y 1 -y 2 ) 2 β 2 - (t -s) 2 β 2 ,
where η, β > 0 are small constants devoted to tend to 0. Because of the periodicity of u and v, the usc function Ψ achieves its maximum at some point, which is still denoted (x 1 , x 2 , y 1 , y 2 , t, s) for the sake of simplicity of notations (but which depends on η and β). We set

p x := 2(x 1 -x 2 ) η 2 , p y := 2(y 1 -y 2 ) β 2 , p t := 2(t -s) β 2 .
The viscosity solutions inequalities for u and v read

p t + G(x 1 , y 1 , t, p x , p y ) + αu(x 1 , y 1 , t) ≤ 0 , (8)
p t + G(x 2 , y 2 , s, p x , p y ) + αv(x 2 , y 2 , s) ≥ 0 .
At this point we recall the well-known fact that

(x 1 -x 2 ) 2 η 2 + (y 1 -y 2 ) 2 β 2 + (t -s) 2 β 2 → 0 as β, η → 0 . (9)
(We point out here that this is true since we deal with time-space periodic sub and supersolutions).

This implies, in particular, that p t = o(β -1 ) and since u and v are bounded, we may as well assume that, for β small enough, the above viscosity inequalities holds with G β = min(β -1 , max(G, -β -1 )), which has the same properties as

G except that |D t G β (ξ)| ≤ C 4 (1 + |p y | + β -1 ).
Subtracting the above viscosity sub and supersolutions inequalities and using (H3) then yield

α(u(x 1 , y 1 , t) -v(x 2 , y 2 , s)) ≤ G β (x 2 , y 1 , t, p x , p y ) -G β (x 1 , y 1 , t, p x , p y ) +C 3 |p y + l||y 1 -y 2 | + C 4 |t -s|(1 + |p y | + β -1 ) .
The argument is then the following : we first fix β and let η tend to 0. Because of (H2) and inequality [START_REF] Arisawa | Ergodic problem for the Hamilton-Jacobi-Bellman Equation[END_REF], the x-gradient term p x remains bounded since p t , p y remains bounded ; furthermore, since u and v are periodic, we may also assume that (x 1 , x 2 , y 1 , y 2 , t, s) remains in a compact subset of R 2n+4 ; therefore the passage to the limit η → 0 can be done by using only the continuity of G β (or, equivalently, of G), all terms being convergent up to a subsequence.

Therefore, we are left with

α(u(x 1 , y 1 , t) -v(x 2 , y 2 , s)) ≤ C 3 |p y + l||y 1 -y 2 | + C 4 |t -s|(1 + |p y | + β -1 ) ,
and the conclusion follows by letting β tend to 0 : the terms of the right-hand side converge to 0 because of ( 9), while we know that u(

x 1 , y 1 , t) -v(x 2 , y 2 , s) → max R n+2 (u -v);
we reach the conclusion that max R n+2 (u -v) ≤ 0 and the proof of (i) is complete.

2. We further remark that, either by construction or by comparison with constants, we have min

x,y,t

[-G(x, y, t, 0, 0)] ≤ αw α ≤ max x,y,t [-G(x, y, t, 0, 0)] . (10)
In particular, ||αw α || ∞ ≤ C 0 .

3. Now we turn to (ii). The idea of Imbert & Monneau consists in estimating separately the behavior of w α in (x, t) and in y. For the estimate in (x, t), we introduce the function w(x, t) := max y∈R w α (x, y, t) , which, using (H2) and the estimate on αw α given in Step 2, is a space-time periodic subsolution of

w t + C 1 |D x w| -(C 0 + C 2 ) ≤ 0 in R n × R .
But the Oleinik-Lax Formula shows that, for any x, t and for any s ≤ t w(x, t) ≤ min

|z-x|≤C 1 (t-s) [w(z, s)] + (C 0 + C 2 )(t -s) ,
and therefore, for any S > 0

w(x, t) ≤ min 0≤t-s≤S min |z-x|≤C 1 (t-s) [w(z, s)] + (C 0 + C 2 )(t -s) .
Choosing (x, t) such that w(x, t) = max R n ×R w and choosing S large enough in order that the set {(z, s); 0 ≤ t -s ≤ S , |z -x| ≤ C 1 (t -s)} contains a whole period, we deduce that max

R n ×R w -min R n ×R w ≤ K 1 , (11)
where K 1 depends only on C 0 , C 1 and C 2 .

4. Next we consider the behavior of w α in y. We are going to show that D y (w α (x, y, t)+ly) has the same sign as l. We only do it in the case l < 0, the case l > 0 being treated in an analogous way. If l = 0 then w α is independent of y : indeed, since G(x, y, t, p x , 0) is independent of y by (H3), by using the same arguments as in the proof of (i), one can build a solution for this new Hamiltonian which depends only on x and t and which is also a solution of the G equation. Therefore, by uniqueness, w α = w α (x, t).

To prove that y → w α (x, y, t) + ly is nonincreasing for l < 0, we consider

M := max{w α (x, y 1 , t) -w α (x, y 2 , t) + l(y 1 -y 2 ); x ∈ R n , t ∈ R, y 1 ≥ y 2 } .
We have to show that this maximum is nonpositive. To do so, we argue by contradiction assuming that M > 0 and we introduce the function

χ(x 1 , x 2 , y 1 , y 2 , t, s) := w α (x 1 , y 1 , t) -w α (x 2 , y 2 , s) - (x 1 -x 2 ) 2 η 2 - [(y 1 -y 2 ) -] 2 β 2 +l(y 1 -y 2 ) - (t -s) 2 β 2 .
The function χ has indeed a maximum since w α is continuous and periodic (hence bounded) and since l is strictly negative, the term l(y 1 -y 2 ) controls (y 1 -y 2 ) + which therefore remains bounded.

Denoting by (x 1 , x 2 , y 1 , y 2 , t, s) a maximum point of χ and

a = 2(t -s) β 2 , p x = 2(x 1 -x 2 ) η 2 , p y = -l + 2(y 1 -y 2 ) - β 2 ,
we have the viscosity inequalities

a + G(x 1 , y 1 , t, p x , p y ) + αw α (x 1 , y 1 , t) ≤ 0 , a + G(x 2 , y 2 , s, p x , p y ) + αw α (x 2 , y 2 , s) ≥ 0 .
Using (H3), we have

|G(x 1 , y 1 , t, p x , p y ) -G(x 1 , y 2 , t, p x , p y )| ≤ 2C 3 [(y 1 -y 2 ) -] 2 β 2 ,
and subtracting the above inequalities, we are left with α(w α (x 1 , y 1 , t) -w α (x 2 , y 2 , s)

+ l(y 1 -y 2 )) ≤ G(x 2 , y 2 , s, p x , p y ) -G(x 1 , y 2 , t, p x , p y ) + 2C 3 [(y 1 -y 2 ) -] 2 β 2 + αl(y 1 -y 2 ) .
To conclude, we argue as in the proof of the comparison result : first, by periodicity we may assume that (x 1 , y 1 , t) and (x 2 , y 2 , s) remain in a compact subset of R n × R × R; next, by classical arguments, all the penalization terms tend to 0. In particular, (y 1 -y 2 ) -= o(β) and this yields αl(y 1 -y 2 ) ≤ o(β) since l < 0. Therefore we first fix β and let η tend to 0 and then we let β tend to 0, using the same arguments as above. This gives the inequality αM ≤ 0 and the conclusion. 5. To prove (ii), it is enough to put together the two above informations and again we do it only for l < 0: we consider two points (x, y, t) and (x ′ , y ′ , t ′ ) such that w α (x, y, t) = max R n+2 w α and w α (x ′ , y ′ , t ′ ) = min R n+2 w α , and we denote by y the smallest point z ≥ y ′ such that w(x ′ , t ′ ) = w α (x ′ , z, t ′ ); we recall that w α is periodic and therefore y -y ′ ≤ 1. We have

w α (x, y, t) = w(x, t) ≤ w(x ′ , t ′ ) + K 1 ≤ w α (x ′ , y, t ′ ) + K 1 ≤ w α (x ′ , y ′ , t ′ ) + l(y ′ -y) + K 1 ≤ w α (x ′ , y ′ , t ′ ) -l + K 1 .
which concludes the proof of (ii). 6. For the proof of (iii), we notice that w α -min w α is bounded and so is α min w α since ||αw α || ∞ ≤ C 0 . Without loss of generality, we may assume that -α min w α converges to a constant λ and, along the same subsequence, the half-relaxed limits of w α -min w α , denoted by w and w, provide respectively a bounded subsolution and a bounded supersolution of ( 5). Now we show that there exists a unique constant λ such that (5) has a bounded subsolution and a bounded supersolution. First, we assume that there exists λ such that (5) has a bounded subsolution ũ. By comparison result for the initial value problem (a result proved in a similar way as in the stationary case), using that ũ -λt and w -λt are respectively sub and supersolution of equation ( 6), we deduce max R n+2 (ũ -w)(x, y, t) ≤ max R n+2 (ũ -w)(x, y, 0) + t( λ -λ) .

Since ũ and w are bounded, by dividing by t > 0 and letting t tend to +∞, we obtain λ -λ ≥ 0. The reverse inequality is obtained by the same argument assuming that there exists a bounded supersolution for the same constant.

7. Finally we prove (iv). The proof of the existence and uniqueness of the solution v follows along the line of the proof of (i) with few additional classical arguments and therefore we skip it. In order to prove the convergence property, we use w and w defined in step 6 above. Since v 0 , w and w are bounded, there exist constants c, c such that

c + w(x, y, 0) ≤ v 0 (x, y) ≤ c + w(x, y, 0) in R n+1 .
But c + w(x, y, t) -λt and c + w(x, y, t) -λt are respectively sub and supersolution of (6) and, by comparison, we deduce c + w(x, y, t) -λt ≤ v(x, y, t) ≤ c + w(x, y, t) -λt in R n+1 × (0, +∞) .

Dividing by t and using the fact that w and w are bounded provide the property we wanted to prove. And the proof of Theorem 1.1 is complete.

Remark 1.1 In the case where G is independent of t, w α is also independent of t since w α (x, y, t) and w α (x, y, t+h) are both solutions of the equation for any h ∈ R and therefore, by uniqueness, w α (x, y, t) = w α (x, y, t + h) for any h ∈ R. But maybe a more simple approach in this case is to solve the stationary equation directly and not to consider the evolution equation. In the above proof, the only change concerns the estimate obtained through w = w(x) : indeed w is a subsolution of

min y∈R G(x, y, Dw, 0) ≤ C 0 in R n ,
and this inequality together with the coercivity asssumption on G, shows that ||Dw|| ∞ ≤ K, where K depends only on G through C 0 and the coercivity. The function w being Z nperiodic in x, this gives the bound on the oscillation and even a more precise information.

Homogenization of the non-coercive equation

In order to state and prove the homogenization result, we first need to identify the homogenized Hamiltonian and its properties.

Lemma 2.1 Assume that F satisfies the assumptions (H1)-(H3) with l = 0 in (H3).

For any (p x , p y ) ∈ R n × R, there exists a unique constant F (p x , p y ) such that (3) has a bounded space-time periodic solution. The function F (p x , p y ) is a continuous function of (p x , p y ). Moreover, if (F k ) k is a sequence of functions satisfying the same assumptions as F and uniformly in k, and which converges locally uniformly to

F on R 2n+3 , then F k → F locally uniformly in R n × R.
Proof : The first part of the result is an immediate consequence of Theorem 1.1 applied to G(x, y, t, q x , q y ) = F (x, y, t, q x + p x , q y + p y ) .

The continuity of F comes from all the estimates we have : first we have a bound on F (p x , p y ) which is coming from (10) (recall that -αw α converges uniformly to λ), namely min x,y,t [F (x, y, t, p x , p y )] ≤ F (p x , p y ) ≤ max x,y,t [F (x, y, t, p x , p y )] .

Then we have also the bounds on the oscillations of the associated sub and supersolution v, v, typically through K 1 given by [START_REF] Bardi | On differential games with long-time-average cost[END_REF] in the time dependent case, which depend only on (p x , p y ), F and l = p y .

Indeed, if the sequence ((p k x , p k y )) k is converging to (p x , p y ), then, up to a subsequence, F (p k x , p k y ) converges to µ ∈ R. But if v k and v k are bounded sub and supersolution associated respectively to (p k x , p k y ), then they are uniformly bounded and the half-relaxed limit method provides v and v which are the sub and supersolution associated to (p x , p y ) and the constant µ. By the uniqueness result of Theorem 1.1 (iii), this implies µ = F (p x , p y ) and since this is true for any converging subsequence of (F (p k x , p k y )) k , the continuity is proved.

Finally the proof for the F k relies on the same type of arguments and therefore we skip it.

The homogenization result is then the Theorem 2.1 Assume that F satisfies the assumptions (H1)-(H3) with l = 0 in (H3).

If the U ε are continuous viscosity solutions of ( 2) associated with the initial data U ε (x, y, 0) = U 0 (x, y) in R n × R where U 0 is bounded uniformly continuous in R n+1 , then, as ε → 0, U ε → U locally uniformly in R n+1 × (0, +∞), where U is the unique solution of

U t + F (D x U, D y U) = 0 in R n+1 × (0, +∞), ( 12
)
with the same initial datum U 0

Proof : We just sketch it since it follows essentially by classical arguments. We first remark that, if A := max(||U 0 || ∞ , ||F (x, y, t, 0, 0)|| ∞ ), then -A(1 + t) and A(1 + t) are respectively sub and supersolution of the problem and, by comparison, we have

-A(1 + t) ≤ U ε (x, y, t) ≤ A(1 + t) in R n+1 × (0, +∞) ;
therefore, the U ε 's are uniformly bounded.

Then we use the half-relaxed limit method and set u := lim sup * U ε , u = lim inf * U ε . We show how to prove that u is a subsolution of ( 12), the proof that u is a supersolution being analogous.

If φ is a smooth function and (x, y, t) is a strict maximum point of u -φ, we use the perturbed test-function's method in the following way: we set p x = D x φ(x, y, t), p y = D y φ(x, y, t) and let V be a bounded space-time periodic supersolution of (3) associated to (p x , p y ) and to the function

F k (x, y, t, q x , q y ) = min {F (x ′ , y, t ′ , q ′ x , q y ) ; |x ′ -x|, |t ′ -t|, |q ′ x -q x | ≤ k -1 } , for k ≥ 1.
We introduce the function

U ε (x, y, t) -φ(x, y, t) -εV (ε -1 x ′ , ε -1 y ′ , ε -1 t ′ ) - |x -x ′ | 2 δ 2 - |y -y ′ | 2 δ 2 - |t -t ′ | 2 δ 2 .
It is easy to see (and standard) that, as ε → 0 and δ → 0 with δ ≪ ε, the maximum points of this function converge to (x, y, t, x, y, t). Performing standard computations (which we recall in the Appendix for the reader's convenience) with fixed k leads to the inequality

φ t (x, y, t) + F k (D x φ(x, y, t), D y φ(x, y, t)) ≤ 0 , (13)
and we use Lemma 2.1 to conclude by letting k → ∞.

We just point out that the F k -trick allows to take into account the rather weak conditions we impose on F (x, y, t, q x , q y ) in x, t and q x : indeed, if (x, y, t, x ′ , y ′ , t ′ ) is a maximum point of the above function, we have, on one hand, |D x φ(x, y, t) -D x φ(x, y, t)| ≤ k -1 for ε and δ small enough because (x, y, t) → (x, y, t) when ε, δ → 0; on the other hand, since the terms

|x-x ′ | 2 δ 2 , |t-t ′ | 2 δ 2 are bounded, then |ε -1 x ′ -ε -1 x|, |ε -1 t ′ -ε -1 t| ≤ k -1 if δ ≪ ε is small enough. Therefore F k (ε -1 x ′ , ε -1 y ′ , ε -1 t ′ , D x φ(x, y, t) + q x , q y ) ≤ F (ε -1 x, ε -1 y ′ , ε -1 t, D x φ(x, y, t) + q x , q y ) ,
which is the inequality needed in the proof because the dependence in y, y ′ and q y is taken into account by (H3). Without this argument, we would face a difference of F -terms which is not a priori small. A more detailed argument is given in the appendix.

We end the proof by remarking that we have a Strong Comparison Result for the F equation since F is continuous and just depends on (p x , p y ) and this allows to compare the subsolution u and the supersolution u to get the complete answer (see, for example, Ley [START_REF] Ley | Lower-bound gradient estimates for first-order Hamilton-Jacobi equations and applications to the regularity of propagating fronts[END_REF]). This point may be a difficulty in more general cases and we refer the reader to Section 4 for remarks in this direction.

3 Homogenization of the u ε /ε -equation

In this section, we consider (1) and even a more general time dependent one, namely

u ε t + H(ε -1 x, ε -1 u ε , ε -1 t, Du ε ) = 0 in R n × (0, +∞), (14)
together with the initial data

u ε (x, 0) = u 0 (x) in R n . ( 15
)
where u 0 is bounded, uniformly continuous in R n and the Hamiltonians

H ∈ C(R n × R × R n ) satisfies the assumptions (H4) H(x, u, t, p) is a locally Lipschitz function in R n × R × R × R n , Z n -periodic in x,
1 periodic in u and t. Moreover there exists a constant C such that, for almost every

(x, u, t, p) in R n × R × R × R n |D t H(x, u, t, p)| ≤ C(1 + |H(x, u, t, p)|) , |D u H(x, u, t, p)| , |D p H(x, u, t, p)| ≤ C.
(H5) H is coercive in p, i.e.

H(x, u, t, p) → +∞ as |p| → +∞ uniformly w.r.t. x ∈ R n , u, t ∈ R.

In addition to these assumptions, we have to add a "geometrical" assumption which ensures that ( 14) is the graph-equation associated to a level-set equation in R n+1 . A priori this requires only (H6w) There exists an Hamiltonian H ∞ satisfying (H4)-(H5) such that

H ∞ (x, u, t, p) = lim s↓0 sH(x, u, t, s -1 p) .
but we use below a slightly more restrictive one (H6s) There exists a constant

C such that |D p H(x, u, t, p) • p -H(x, u, t, p)| ≤ C a.e. in R × R n × R n .
"w" is for weak and "s" is for strong. Below we just use the notation (H6) for (H6s) but keeping in mind the notation H ∞ introduced in (H6w).

Before providing the result, we point out that both (H6w) and (H6s) hold for H(x, t, u, p) = c(x, t)|p|+g(u, t) if c, g are Lipschitz, periodic functions with c(x, t) ≥ η > 0 in R n . Notice that g may change sign or be negative.

The result is the following Theorem 3.1 Assume that H satisfies (H4)-(H6). Then the sequence (u ε ) ε converges locally uniformly to a function u which is the unique solution of an equation of the type

u t + H(Du) = 0 in R n × (0, +∞), (16)
with u(x, 0) = u 0 (x) in R n . (17)
The Hamiltonian H can be interpreted as an homogenized Hamiltonian for a standard homogenization problem in dimension n+ 1 and is characterized by the following property: λ = -H(p) is the unique constant such that, if w is the solution of

w t + H(x, w, t, Dw) = 0 in R n × (0, +∞), (18) w
(x, 0) = p • x + w 0 (x) in R n , (19)
where w 0 is a bounded uniformly continuous function, then w(x, t) -p • x -λt is uniformly bounded in R n × (0, +∞). In particular

-H(p) = lim t→+∞ t -1 w(x, t) ,
the limit being uniform in R n .

Proof :

1. From R n to R n+1 : we interpret the equation for u ε as the equation of the motion of a graph and we introduce the level-sets equation in R n+1 . To do so, we use (a slight modification of) the approach used by Giga & Sato [START_REF] Giga | A level set approach to semicontinuous viscosity solutions for Cauchy problems[END_REF] for Hamilton-Jacobi Equations (see also Biton, Ley and the author [START_REF] Barles | A geometrical approach to the study of unbounded solutions of quasilinear parabolic equations[END_REF] for the Mean Curvature Equation). The function U ε (x, y, t) := u ε (x, t) -y solves

U ε t + |D y U ε |H(ε -1 x, ε -1 U ε + ε -1 y, ε -1 t, |D y U ε | -1 D x U ε ) = 0 in R n+1 × (0, +∞), U ε (x, y, 0) = u 0 (x) -y in R n+1 .
In the sequel, it is convenient to use the notation X = (x, y), P = (p x , p y ) and to introduce the Hamiltonian F defined by

F (X, t, P ) := |p y |H(x, y, t, |p y | -1 p x ) if p y = 0, H ∞ (x, y, t, p x ) otherwise.
By the assumptions (H4)-(H6) on H, tedious but straightforward computations show that F satisfies (H1)-(H3) ((H6s) provides, in particular, the Lipschitz continuity in p y ). It is worth pointing out that, in (H2), since F is homogeneous of degree 1, the coercivity of F in p x or the stronger property required in the t-dependent case are, in fact, equivalent.

We finally consider χ ε (X, t) := 1 1 {U ε (•,t)≥0} where, here and below, 1 1 A denotes the indicator function of the set A. Following [START_REF] Barles | Front propagation and phase field theory[END_REF], it is easy to see that it solves

χ ε t + F (ε -1 X, ε -1 t, Dχ ε ) = 0 in R n+1 × (0, +∞), χ ε (x, 0) = 1 1 {u 0 (x)-y≥0} in R n+1 .
Indeed the result is obvious if either U ε (x, t) > 0 or U ε (x, t) < 0 because χ ε is constant in a neighborhood of (x, t) and the equation is a trivial consequence of the fact that F (X, t, 0) = 0 for any X and t. Hence we are left with the case when U ε (x, t) = 0, where the arguments of [START_REF] Barles | Front propagation and phase field theory[END_REF] provide the answer by using the continuity of U ε . In fact, in the equation, the dependence in U ε is treated as a dependence in X and t ; the change of variables of [START_REF] Barles | Front propagation and phase field theory[END_REF] is done only at the level of the derivatives. This explains why the dependence in U ε disappears from this equation.

2.

Homogenization in R n+1 . The χ ε -equation can be homogenized by using almost readily Section 2, the only slight difficulty being the discontinuous initial data and solutions. In fact, if χ := lim sup * χ ε , χ := lim inf * χ ε , u := lim sup * u ε , u := lim inf * u ε , we have the following: χ and χ are respectively viscosity sub and supersolutions of

χ t + F (Dχ) = 0 in R n+1 × (0, +∞), (20)
with χ(X, 0) ≤ 1 1 {u 0 (x)-y≥0} , χ(X, 0) ≥ 1 1 {u 0 (x)-y>0} in R n+1 , and χ(X, t) = 1 1 {u(x,t)-y≥0} , χ(X, t) = 1 1 {u(x,t)-y>0} in R n+1 × (0, +∞).

We also point out that F is homogeneous of degree 1.

3.

Reconstruction of the result in R n . Let u : R n × (0, +∞) → R be the solution of

u t + F (D x u, -1) = 0 in R n × (0, +∞), u(x, 0) = u 0 (x) in R n .
By the arguments of Soner, Souganidis and the author [START_REF] Barles | Front propagation and phase field theory[END_REF], since u(x, t)-y is the solution of the level set equation ( 20) associated to the initial data u 0 (x) -y, we have χ(X, t) ≥ 1 1 {u(x,t)-y>0} and χ(X, t) ≤ 1 1 {u(x,t)-y≥0} in R n+1 × (0, +∞).

Indeed, it is proved in [START_REF] Barles | Front propagation and phase field theory[END_REF] that 1 1 {u(x,t)-y>0} and 1 1 {u(x,t)-y≥0} are respectively the minimal supersolution and the maximal subsolution associated to the initial data 1 1 {u 0 (x)-y≥0} . By the form of χ and χ given in Step 2, this yields

u(x, t) ≤ u(x, t) ≤ u(x, t) ≤ u(x, t) in R n × (0, +∞).
Therefore u = u = u in R n × (0, +∞) and this proves the first part of the result with H(p) := F (p, -1). 4. To prove the last part of the result, we apply the same approach : if U : R n+1 × (0, +∞) → R is the solution of the level set equation

U t + F (X, t, DU) = 0 in R n+1 × (0, +∞), (21)
with initial data p•x+w 0 (x)-y, we first have {(x, y, t); w(x, t) = y} ⊂ {(x, y, t); U(x, y, t) = 0}.

On the other hand, if v 1 and v 2 are bounded space-time periodic functions which are respectively an usc subsolution and a lsc supersolution of (3) associated to P = (p x , -1), then the functions v 1 (X, t) + P • X -F (P )t, v 2 (X, t) + P • X -F (P )t are respectively sub and supersolution of ( 21); since, we may assume in addition that max R n+2 v 1 (X, t) ≤ w 0 ≤ min R n+2 v 2 (X, t) in R n+1 , we have by using a comparison result

v 1 (X, t) + P • X -F (P )t ≤ U(X, t) ≤ v 2 (X, t) + P • X -F (P )t in R n+1 × (0, +∞) .
Notice that, since H satisfies (H4) and (H6), F is Lipschitz continuous in P , uniformly in X and we can use a property of "finite speed of propagation" for the level set equation, which simplifies the comparison arguments and avoids problem with the unboundedness of the domain.

If w(x, t) = y, then U(x, t) = 0, P • X = p • x -w(x, t) and this inequality gives

v 1 (X, t)+p•x-w(x, t)-F (P )t ≤ 0 ≤ v 2 (X, t)+p•x-w(x, t)-F (P )t in R n ×(0, +∞) , or equivalently v 1 (X, t) ≤ w(x, t) -p • x + F (P )t ≤ v 2 (X, t) in R n × (0, +∞) .
Since H(p) = F (p, -1) and v 1 , v 2 are bounded, this gives the first part of the result. Then, dividing by t and letting t → ∞, we obtain the second one. And the proof is complete.

Extensions and Remarks

The results of the preceding sections can be extended in several directions. First, in Section 2, we can consider stationary homogenization problems. In fact, as we suggest it in the introduction, these problems are simpler provided that we have a suitable dependence in u ε .

Next, the one-dimensional variable y can be replaced by a multi-dimensional variable (y 1 , • • • , y m ) provided that one has the right structure on G (and therefore on F ), namely for G (H3') The function G is locally Lipschitz continuous w.r.t. y = (y 1 , • • • , y m ), t, p y and there exists l

= (l 1 , • • • , l m ) ∈ R m and C 3 , C 4 , C 5 ≥ 0 such that, for all i = 1, • • • , m and for almost every ξ = (x, y, t, p x , p y ) ∈ R 2(n+m)+1 |D y i G(ξ)| ≤ C 3 |p y i + l i | , |D t G(ξ)| ≤ C 4 (1 + |p y | + |G(ξ)|) , |D py G(ξ)| ≤ C 5 .
With this assumption, the proof of Theorem 1.1 remains the same : the only slight difference is that we have to do the estimates for all the D y i (w α (x, y, t) + l i y i ) and the first inequality for |D y i G(ξ)| above implies that we can do it separately for each i.

For the homogenization problems, we may have additional dependences in x, y, t and not only in the fast variables ε -1 x, ε -1 y, ε -1 t. In this case, x, y, t become parameters in the ergodic-cell problem as are p x , p y . The main additional difficulties consists, on one hand, in obtaining the right dependence of F (x, y, t, p x , p y ) in x, y, t in order to have a Strong Comparison Result for the limiting equation and, on the other hand, in the convergence proof, to take care of the lack of uniform continuity of F in x, y, t. It is worth pointing out that this last difficulty arises since we do not have (a priori) Lipschitz continuous solutions for the ergodic-cell problem.

For the first difficulty, since one can prove, in an analogous way as in the proof of Lemma 2.1, that F (x, y, t, p x , p y ) is continuous, then the dependence in x does not create any problem. But the dependence in t and y seems less clear and we do not see how to show that (typically) |D y F (x, y, t, p x , p y )| ≤ C(1 + |p y |) and an analogous property for the t-dependence. Here the fact not to have a Lipschitz continuous solution of the ergodic-cell problem creates a difficulty and we do not know how to solve it.

On the contrary, the second difficulty can be solved by using a similar trick to the F k -one and is not a real problem.

Finally, even if, in this paper, we restrict ourselves to the case of first-order equations, there are easy extensions to second-order equations : for example, Theorem 1.1 extends without any difficulty if we add a u yy to the equation, which corresponds to homogenization problems with a vanishing viscosity term of the form ε 2 u ε yy . Such type of extensions will be considered in a future work.

Appendix : Proof of ( 13) Since (x, y, t) is a strict maximum point of u -φ, standard arguments show that, for ε and δ small enough, the function

U ε (x, y, t) -φ(x, y, t) -εV (ε -1 x ′ , ε -1 y ′ , ε -1 t ′ ) - |x -x ′ | 2 δ 2 - |y -y ′ | 2 δ 2 - |t -t ′ | 2 δ 2 ,
has a local maximum point near (x, y, t, x, y, t). We denote it by (x, y, t, x ′ , y ′ , t ′ ) for the sake of notational simplicity. Moreover we know that (x, y, t, x ′ , y ′ , t ′ ) converges to (x, y, t, x, y, t) as ε, δ → 0 and

|x -x ′ | 2 δ 2 + |y -y ′ | 2 δ 2 + |t -t ′ | 2 δ 2
→ 0 as δ → 0 for any ε > 0.

We set

q x := 2(x -x ′ ) δ 2
, q y := 2(y -y ′ ) δ 2 , q t := 2(t -t ′ ) δ 2 .

The viscosity inequalities for U ε at (x, y, t) and for V at (ε -1 x ′ , ε -1 y ′ , ε -1 t ′ ) (after applying the obvious unscaling) read φ t (x, y, t) + q t + F (ε -1 x, ε -1 y, ε -1 t, D x φ(x, y, t) + q x , D y φ(x, y, t) + q y ) ≤ 0 , q t + F k (ε -1 x ′ , ε -1 y ′ , ε -1 t ′ , q x + p x , q y + p y ) ≥ F k (p x , p y )

where we recall that p x = D x φ(x, y, t) and p y = D y φ(x, y, t). But, by the above recalled property on the penalization terms, we have

|ε -1 x -ε -1 x ′ | 2 + |ε -1 t -ε -1 t ′ | = ε -1 δo(1)
where o(1) → 0 as ε, δ → 0 , and, on the other hand, since (x, y, t) → (x, y, t), we have |(D x φ(x, y, t) + q x ) -(q x + p x )| → 0 as ε, δ → 0 .

Therefore if we choose δ ≪ ε and ε, δ small enough, we have

|ε -1 x -ε -1 x ′ | 2 , |ε -1 t -ε -1 t ′ |, |(D x φ(x, y, t) + q x ) -(q x + p x )| ≤ k -1 . (22)
Next, we use this information together with (H3) to obtain F (ε -1 x, ε -1 y, ε -1 t, D x φ(x, y, t) + q x , D y φ(x, y, t) + q y ) ≥ F (ε -1 x, ε -1 y ′ , ε -1 t, D x φ(x, y, t) + q x , D y φ(x, y, t) + q y ) -C 3 |ε -1 y -ε -1 y ′ ||D y φ(x, y, t) + q y | -C 5 |D y φ(x, y, t) -D y φ(x, y, t)| .

And thanks again to the property on the penalization terms, we can choose δ small enough in order to have |ε -1 y -ε -1 y ′ ||D y φ(x, y, t) + q y | = o(1) as ε, δ → 0 .

Using this and ( 22) yields the final estimate of F (ε -1 x, ε -1 y, ε -1 t, D x φ(x, y, t)+q x , D y φ(x, y, t)+ q y ), namely F k (ε -1 x ′ , ε -1 y ′ , ε -1 t, D x φ(x, y, t) + q x , D y φ(x, y, t) + q y ) -o(1) .

In order to conclude, it suffices to subtract the above viscosity inequalities and to use this information : this yields φ t (x, y, t) -o(1) ≤ -F k (p x , p y ) , and we let ε, δ tends to 0, choosing δ sufficiently small compared to ε.

Remark 4.1 This detailed proof shows why the "F k -trick" can be useful : without using it, we would have to compare the terms F (ε -1 x, ε -1 y, ε -1 t, D x φ(x, y, t) + q x , D y φ(x, y, t) + q y ) and F (ε -1 x ′ , ε -1 y ′ , ε -1 t ′ , q x + p x , q y + p y ). As the above proof shows it, the "good" assumption (H3) allows to treat the differences in y and D y u and it seems to be a natural assumption to do it. But, for the x and t variables, we do not have such type of assumption and the "F k -trick" seems the only way to handle the corresponding differences.

We have choosen to present this "F k -trick" in this way in order to point out the difference between having (H3) and not having it, but we could have defined F k in a different way in order that it takes care of all the variables.


Bedaride Nicolas
email: nicolas.bedaride@univ-cezanne.fr

DIRECTIONAL COMPLEXITY OF THE HYPERCUBIC BILLIARD

We consider a minimal rotation on the torus T d of direction ω. A natural cellular decomposition of the torus is associated to this map. We consider an infinite orbit for this map. We compute the complexity of the associated word. Under some hypothesis on the direction, we obtain an exact formula which shows that the order of magnitude is n d . This result is related to the billiard map inside a hypercube of R d+1 .

Introduction

Sturmian words are infinite words over a two-letter alphabet that have exactly n+1 factors of length n for each integer n. The number of factors, of a given length, of an infinite word is called the complexity function. These words have been introduced by Morse-Hedlund, [START_REF] Morse | Symbolic dynamics II. Sturmian trajectories[END_REF]. Consider a rotation of angle α on the torus T 1 . Consider a two-letter alphabet corresponding to the intervals (0; 1 -α) and (1 -α; 1). Then, the orbit of any point under the rotation is coded by an infinite word. This word is a sturmian word if and only if α is an irrational number. If α is rational, then the rotation is periodic and the word is periodic.

In this paper we consider rotation on the torus T d of direction ω, see Section 4.4. We want to compute the complexity function of this map related to the natural partition. In the case of d = 2 the function has been computed by Arnoux, Mauduit, Shiokawa and Tamura [START_REF] Arnoux | Complexity of sequences defined by billiard in the cube[END_REF] (dimension 3). Unfortunately this result was false, and we need some additional hypothesis on the direction, see [START_REF] Bedaride | Billiard complexity in rational polyhedra[END_REF] and [START_REF] Bedaride | Classification of cubic billiard trajectories[END_REF] for a classification of complexity along the direction. The computation has been done by Baryshnikov [START_REF] Yu | Complexity of trajectories in rectangular billiards[END_REF] in any dimension under some hypothesis on the direction. The complexity function is a polynomial in n of degree d. Here we present a new proof of this result under some more general hypothesis on the direction.

This problem is related to the complexity of a billiard trajectory inside a cube of R d+1 . The definition of the billiard map inside a polyhedron P is the following: A billiard ball, i.e. a point mass, moves inside a polyhedron P with unit speed along a straight line until it reaches the boundary ∂P , then instantaneously changes direction according to the mirror law, and continues along the new line. Label the sides of P by symbols from a finite alphabet A whose cardinality equals the number of faces of P . The orbit of a point corresponds to a word in the alphabet A.

In the case of the cube where we code the parallel faces by the same letters, the infinite words obtained for an initial point of direction ω are equal to 1 the infinite words obtained by a rotation on the torus T d of direction ω, see Lemma 2.

In the context of the polygonal billiard some results are known on the complexity function. For the square (coded with two letters) we obtain Sturmian words and complexity n + 1, see the famous paper of Morse and Hedlund [START_REF] Morse | Symbolic dynamics II. Sturmian trajectories[END_REF]. It has been generalized to any rational polygon by Hubert [START_REF] Hubert | Complexité de suites définies par des billards rationnels[END_REF]. He proves that the complexity is always linear in n. For an irrational polygon the only general result is that the billiard in a polygon has zero entropy, see Katok [START_REF] Katok | The growth rate for the number of singular and periodic orbits for a polygonal billiard[END_REF] or [START_REF] Gal Perin | Local instability of orbits in polygonal and polyhedral billiards[END_REF], and thus the complexity grows sub-exponentially. For any convex polyhedron the same fact is true, see [START_REF] Bedaride | Entropy of polyhedral billiard[END_REF].

Our result is the following, the definitions are given in the upcoming sections.

Theorem 1. Consider the unit cube of R d+1 , and code it by an alphabet with d + 1 letters. Let ω be a B-direction, and consider a billiard word in the direction ω. Denote the complexity of this word by p(n, d, ω). For n, d ∈ N, the map ω → p(n, d, ω) is constant on the set of B-directions. Moreover if we denote it by p(n, d) we have

p(n + 2, d) -2p(n + 1, d) + p(n, d) = d(d -1)p(n, d -2) ∀ n, d ∈ N.
Corollary 1. For a B-direction, we have

p(n, d, ω) = min(n,d) i=0 n!d! (n -i)!(d -i)!i! ∀ n, d ∈ N.
Convention: We assume that p(n, 0) = p(0, d) = 1 for all integers n, d.

Overview of the proof

In Section 3 we define the different notions of a direction and give the precise statement of the theorem. In Section 4 we recall different facts about word combinatorics, billiard maps and the relationship between the billiard map and rotations on the torus. In section 5 we prove two lemmas used at the end of the proof. In section 6 the proof of Theorem 1 begins. The computation of the complexity function can be reduced to the computation of the number of bispecial words, see Lemma 1. In Proposition 1 we relate the number of the bispecial words to the number of words associated to generalized diagonals of the direction ω. In Proposition 2 we show that a diagonal is given by two subspaces of dimension d -2. Different properties of diagonals are studied in Section 8. In Proposition 4 we prove that the number of words associated to certain diagonals can be computed using a projection. Moreover, this number is proportionnal to the complexity function corresponding to a fixed direction in a hypercube of dimension d -2. Proposition 3 allows us to compute the number of diagonals. To finish the proof of Proposition 4, we prove the following fact in Corollary 4: The projection of a diagonal onto an appropriate subspace does not change the number of words associated to this diagonal. The end of the proof of Theorem 1 consists of a series of inductions on d and n. To start the induction we recall in Section 10 the result obtained in the case d = 2.

Definitions

In this section we give some definitions usefull to the statement of the different theorems.

Definition 1. We define several notions of independance for a vector in R d+1 . Let d be an element of N.

• The real numbers (a i ) 1≤i≤d+1 are independent over Q if and only if

d+1 i=1 r i a i = 0, r i ∈ Q =⇒ r i = 0 ∀i ∈ [1, d + 1]. • A vector ω = (ω i ) 1≤i≤d+1 ∈ R d+1 is called an irrational direction if
and only if: The real numbers (ω i ) 1≤i≤d+1 are independent over Q.

• A vector ω = (ω i ) 1≤i≤d+1 ∈ R d+1 is called a totally irrational direc- tion if

and only if:

The real numbers (ω i ) 1≤i≤d+1 are independent over Q, and the real numbers (ω -1 i ) 1≤i≤d+1 are independent over Q.

• A vector ω = (ω i ) 1≤i≤d+1 ∈ R d+1 is called a B-direction if and only if:
The real numbers (ω i ) 1≤i≤d+1 are independent over Q, and for each subset I ⊂ {1 . . . d + 1} of cardinality three, the real numbers (ω -1 i ) i∈I are independent over Q. Remark 1. We have the implications: ω is a totally irrational direction =⇒ ω is a B-direction =⇒ ω is an irrational direction. Now we recall the theorem of Baryshnikov [START_REF] Yu | Complexity of trajectories in rectangular billiards[END_REF].

Theorem 2 (Baryshnikov). Consider an unit cube of R d+1 , we code it by an alphabet with d + 1 letters. Let ω be a totally irrational direction, consider a billiard word in the direction ω, denote the complexity of this word by p(n, d, ω). Then we have

p(n, d, ω) = min(n,d) i=0 n!d! (n -i)!(d -i)!i! ∀ n, d ∈ N.
4. Background 4.1. Combinatorics. For this section a general reference is [START_REF] Fogg | Substitutions in dynamics, arithmetics and combinatorics[END_REF].

Definition 2. Let A be a finite set called the alphabet. By a language L over A we mean always a factorial extendable language: a language is a collection of sets (L n ) n≥0 , where the only element of L 0 is the empty word. Each L n consists of words of the form a 1 a 2 . . . a n with a i ∈ A, such that for each v ∈ L n there exists a, b ∈ A with av, vb

∈ L n+1 . For all v ∈ L n+1 , if v = au = u b with a, b ∈ A, then u, u ∈ L n . The complexity function p : N → N is defined by p(n) = card(L n ).
First of all we recall a result of Cassaigne concerning combinatorics of words [START_REF] Cassaigne | Complexité et facteurs spéciaux[END_REF]. Definition 3. An infinite word v over the alphabet A is a sequence (v n ) n∈N such that v n ∈ A for every integer n. A subword w of v of length n is a finite word such that there exists n 0 ∈ N and w = v n 0 v n 0 +1 . . . v n 0 +n-1 . The set of subwords of length n is denoted by L n . If v is an infinite word defined over a finite alphabet, then the union L = L n forms a language. The complexity of u is by definition the complexity of L. Definition 4. Let L(n) be an extendable, factorial language. For any n ≥ 1 let s(n

) := p(n + 1) -p(n). For v ∈ L(n) let m l (v) = card{u ∈ A, uv ∈ L(n + 1)}, m r (v) = card{w ∈ A, vw ∈ L(n + 1)}, m b (v) = card{u ∈ A, w ∈ A, uvw ∈, L(n + 2)}. A word is call right special if m r (v) ≥ 2, left special if m l (v) ≥ 2
and bispecial if it is right and left special. Let BL(n) be the set of the bispecial words.

Cassaigne [START_REF] Cassaigne | Complexité et facteurs spéciaux[END_REF] has shown: Lemma 1. For any language L the complexity function satisfies for all integer n: s

(n + 1) -s(n) = v∈BL(n) i(v), where i(v) = m b (v) -m r (v) -m l (v) + 1.
For the proof of the lemma we refer to [START_REF] Cassaigne | Complexité et facteurs spéciaux[END_REF] or [START_REF] Cassaigne | Complexity and growth for polygonal billiards[END_REF].

4.2. Billiard maps. We recall some facts from billiard theory. Additional details can be found in [START_REF] Tabachnikov | [END_REF] or [START_REF] Masur | Rational billiards and flat structures[END_REF].

Let C be an unit cube of R d+1 . A billiard ball, i.e. a point mass, moves inside C with unit speed along a straight line until it reaches the boundary ∂C, then instantaneously changes direction according to the mirror law, and continues along the new line. More precisely, the billiard map T is defined on a subset X of ∂C × RP d by the following method (where RP d is the projective space of dimension d ≥ 1): First we define the set X ⊂ ∂C × RP d . A point (m, ω) belongs to X if and only if one of the two following conditions holds:

(1) The line m + R[ω] intersects a face of C of dimension less than d -1, where [ω] is a vector of R d+1 which represents ω.

(2) A segment of the line m + R[ω] is included inside the face of C which contains m. We define X as the set

X = (∂C × RP d ) \ X .
Now we define the map T : Consider (m, ω) ∈ X, then we have T (m, ω) = (m , ω ) if and only if the segment mm is colinear to [ω], and if

[ω ] = s[ω],
where s is the linear reflection over the face which contains m .

T : X → ∂C × RP d T : (m, ω) → (m , ω )
Remark 2. In the sequel we identify RP d with the unit vectors of R d+1 (i.e we identify ω and [ω]). 4.3. Notations for the billiard map. Label the faces of C by d + 1 symbols from a finite alphabet A such that the two opposite faces of the cube are coded by the same symbols. To the orbit of a point in a direction ω we associate the word in the alphabet A which is given by the sequence of faces of the billiard trajectory.

The set of points (m, ω) such that for all integers n, T n (m, ω) ∈ X is denoted by X ∞ . The infinite word associated to a point (m, ω) in X ∞ is denoted by v m,ω .

Definition 5. Consider the billiard map T inside the cube, and a point (m, ω) ∈ X ∞ . We define the complexity p(n, m, ω) by the complexity of the infinite word v m,ω (see Definition 3). We call it the directional complexity. In the right hand picture we examplify how the study of the billiard orbit can be performed on the big square, where we identify the opposite sides. Thus we obtain a torus, and the map is a translation on this torus:

For ω ∈ R d+1 , a rotation T ω of direction ω on the torus is a map defined as follows.

R d+1 /Z d+1 → R d+1 /Z d+1 T ω : (x i ) i≤d+1 → (x i + ω i ) i≤d+1 .

Figure 1 explains the following result:

Lemma 2. Let ω ∈ RP d , and consider the billiard map T in the cube of R d+1 . Then it is equivalent to study the orbit (T n (m, ω)) n or the orbit (T n ω (m)) n . 4.5. Minimality. Definition 6. A direction ω ∈ RP d is called minimal if, for all point m, the projection of the sequence (T n (m, ω)) n∈N in ∂C is dense in ∂C.

The following lemma deals with minimality of billiard words. This minimality depends on algebraic properties of the translation direction.

Lemma 3. Let ω = (ω i ) 1≤i≤d+1 be an unit vector of R d+1 . Consider the billiard map in the cube of R d+1 . Then the direction ω is minimal if and only if ω is an irrational direction.

The proof of this lemma is based on Kronecker's lemma, see [START_REF] Hardy | An introduction to the theory of numbers[END_REF]. 4.6. Remarks. The following lemma is very useful in the following.

Lemma 4. Consider an orthogonal projection on a face of the cube. The orthogonal projection of a billiard trajectory is a billiard trajectory inside the face which itself is a cube of lower dimension.

Definition 7. Let v = v 0 . . . v n be a billiard word. We define the cell of v as the subset of {(m, ω) ∈ ∂P × RP d } given by the conditions that ∀i, 0 ≤ i ≤ |v| -1, π 1 (T i (m, ω)) ∈ v i .
In this formula π 1 represents the projection into the first variable. And v i represents the letter and the face of the cube coded by this letter.

Throughout the proof we consider billiard trajectories inside the cube as lines on R d+1 with the above introduced unfolding.

Combinatorial lemmas

In this part we prove different results which will be used in the end of the proof.

Lemma 5. For all n > d we have:

d i=0 n!d!(d + 1 -i) (n -i)!(d -i)!i! = d i=0 (n + 1)!d! (n + 1 -i)!(d -i)!i! .
Proof. Consider the vector space given by all polynomials of degree less or equal to d. This space has the two following basis

(e i ) -1≤i≤d-1 = (1, X, X(X -1), . . . , X(X -1) . . . (X -d + 1)), (e i ) -1≤i≤d-1 = (1, X + 1, (X + 1)X, . . . , (X + 1)X . . . (X -d + 2))
, where e i = X(X -1) . . . (X -i), e i = (X + 1)X . . . (X + 1 -i) if i ≥ 0 and e -1 = e -1 = 1 by convention.

For i ≥ 0, since we have e j = (X + 1)X . . . (X -(j -1)) = (X -j + j + 1)X . . . (X -(j -1)), we deduce : e j = e j + (j + 1)e j-1 ∀j ≥ 0 Now consider a polynomial P of degree d. It can be expressed as

P = d-1 i=-1 b i e i . P = b -1 + d-1 i=0 b i e i ,
The preceding formula gives

P = b -1 + d-1 i=0 b i e i + d-1 i=0 b i (i + 1)e i-1 , P = b -1 + d-1 i=0 b i e i + d-2 i=-1 b i+1 (i + 2)e i , P = b -1 + b 0 + b d-1 e d-1 + d-2 i=0 [b i + (i + 2)b i+1 ]e i .
(1)

P = b d-1 e d-1 + d-2 i=-1 [b i + (i + 2)b i+1 ]e i .
Thus we have an expression of P inside the basis (e i ) i .

The sum

A = d i=0 (n + 1)!d! (n + 1 -i)!(d -i)!i!
is a polynomial on n of degree d.

Moreover we have, for all i ≥ 1:

(n + 1)! (n + 1 -i)! = e i-1 (n).
We denote

a i = d! (d-i)!i! .
We will obtain the expression of A inside the basis (e i ):

A = 1 + d i=1 a i e i-1 (n). A = 1 + d-1 i=0 a i+1 e i (n). A = d-1 i=-1 d! (d -i -1)!(i + 1)! e i .
Then, by Equation 1, we deduce the following formula:

A = b d-1 e d-1 (n) + d-2 i=-1 [ d! (i + 1)!(d -i -1)! + d!(i + 2) (i + 2)!(d -i -2)! ]e i (n), A = b d-1 e d-1 (n) + d! d-2 i=-1 [ i + 2 + (i + 2)(d -i -1) (i + 2)!(d -i -1)! ]e i (n), A = a d e d-1 (n) + d! d-2 i=-1 (i + 2)(d -i) (i + 2)!(d -i -1)! e i (n), A = e d-1 (n) + d! d-2 i=-1 (d -i) (i + 1)!(d -i -1)! e i (n), A = d! d-1 i=-1 (d -i) (i + 1)!(d -i -1)! e i (n), A = d! d i=0 (d -i + 1) (i)!(d -i)! e i-1 (n), A = d i=0 (d + 1 -i)d!n! (d -i)!i!(n -i)! .
s(n + 1, d) -s(n, d) = d(d -1)p(n, d -2).
Then we have:

s(n, d) = dp(n, d -1) ∀n ≥ 0, ∀d ≥ 2.
Proof. We give a proof by induction on n.

The equality is true for n = 0. We have

dp(n, d -1) = d + d i≤n-1 s(i, d -1).
By induction we deduce

dp(n, d -1) = d + d(d -1) i≤n-1 p(i, d -2).
Then we apply the hypothesis and obtain

dp(n, d -1) = d + i≤n-1 [s(i + 1, d) -s(i, d)]. dp(n, d -1) = s(n, d).
The induction process is finished, and the Lemma is proved.

First part

Remark that the hypothesis on the direction implies that a billiard word in direction ω is not in one of the d + 1 coordinates hyperplane. Definition 9. We say that a diagonal, between A and B, is of combinatorial length n if the orbit segment passes through n cubes. We denote it by d(A, B) = n. We denote the diagonals of direction ω and combinatorial length n by Diag(n, d, ω).

Diag(n, d, ω) = {(A, B) faces of dimension d -1, ∃p, q ∈ A, B pq//ω d(A, B) = n}.
In the following we only consider diagonals of combinatorial length n whose initial segment is in the cube [0, 1] d+1 . Moreover, all the diagonals will be in the direction ω.

We denote the fact that an orbit in the diagonal γ has code v by v ∈ γ. This section is devoted to the proof of the following result:

Proposition 1. Let d be an integer greatest than 1.

(2)

v∈BL(n,d,ω) i(v) = γ∈Diag(n,d,ω) v∈γ 1.
6.2. Lemmas. For the proof we need the following lemmas.

Lemma 7. We consider a word v in L(n, d) with n ≥ 2, consider the unfolding of the billiard trajectories which are coded by v and start inside the cube [0; 1] d+1 . Then for all i, 0 ≤ i ≤ n -1, there exists only one face corresponding to the letter v i .

Proof. First we consider the intersection of the cell of v with RP d . This set is a proper subset of an octant since n ≥ 2. Now we make the proof by contradiction. We consider the first time j where two different faces appear. There exist two lines starting form a face (corresponding to v j-1 ) which pass through these two different faces. These faces are different but are coded by the same letter, thus they are in two different hypercubes. Thus the two directions are in different octant, contradiction.

Lemma 8. Let v be a bispecial word in BL(n, d, ω), then there exists only one diagonal, of direction ω, associated to this word.

Proof. We consider a bispecial word v. We consider the faces which prolong v into a word of length n + 1. We claim that these faces always intersect. By Lemma 7 these faces are in a same hypercube. They correspond to different letters of the coding, thus these faces intersect (by definition of the coding).

The claim is proved. Thus those faces have a non empty intersection. Thus there exists a trajectory which has v as coding and starts on the face of dimension d -1. Consider the same intersection with the prefix, we have built a diagonal associated to this word. By construction it is unique.

Now we can prove

Lemma 9. Consider a word v element of BL(n, d, ω). We claim that

i(v) = 1.
Proof. We know that there is only one diagonal associated to this word.

Let γ be a diagonal, and v the associated word. Since the faces A, B are of dimension d -1 they are at the intersection of two faces of dimension d. Since we have a B direction, it can not pass through the boundary of A or B.

Thus we have m r (v) = m l (v) = 2. Clearly the diagonal is in the interior of the cell, thus a small perturbation of the diagonal still leaves in the interior of the cell. Thus all the possibilities exist and m b = 4, and thus i(v) = 1.

The phase space is the set of points of the boundary of the cube with a direction. Thus it is of dimension 2d. In the phase space a word corresponds to a cell which is a manifold of dimension 2d.

We call discontinuity of v a set of points in the cell such that their orbits intersect a face of dimension d -1.

Let us remark that a discontinuity is of dimension at most 2d -1, and that a diagonal is in the intersection of two discontinuities. 6.3. Proof of Proposition 1. We consider the map

f : BL(n, d, ω) → Diag(n, d, ω). f : v → γ.
Lemma 8 implies that f is well defined and onto, thus

card(BL(n, d, ω)) = γ∈Diag(n,d,ω) card(f -1 (γ)).
By definition we have card(f -1 (γ)) = v∈γ 1, we deduce

v∈BL(n,d,ω) i(v) = γ∈Diag(n,d,ω) v∈γ i(v).
Then Lemma 9 finishes the proof.

Diagonals

Consider a diagonal between two faces A, B of dimension d -1, the aim of this section is to prove Proposition 2. For each diagonal γ of direction ω between two faces A, B of dimension d -1, there exists two subspaces a, b of dimension d -2 such that:

For all point in a there exists a point in b which belongs to the orbit of the initial point in the billiard flow of direction ω, moreover we have:

γ v∈γ(A,B) i(v) = a,b v∈γ 1.
The diagonal γ is the collection of trajectories in the direction ω which passes through two faces A, B of dimension d -1. If we consider any face A, B with the good distance, it is possible that an associated diagonal do not exist: Indeed the direction is fixed and each orbit can pass through a third edge, see example in the cube of R 3 [START_REF] Bedaride | Billiard complexity in rational polyhedra[END_REF]. The case where the direction is not fixed is treated in [START_REF] Bedaride | Billiard complexity in the cube[END_REF].

Lemma 10. Let A, B be two faces of dimension d -1 and ω a direction. We consider

γ A,B = {m ∈ A, m + Rω ∩ B = ∅}. Then γ A,B has

one of the following equation

(1) There exists i, j ∈ [1 . . . d + 1] such that nω i = pω j , with n, p ∈ N.

(2) There exists i, j • If n is at a position i less or equal than d -1, and p is at position d or d + 1, we obtain

∈ [1 . . . d + 1] such that m i + nω i ω j = p with n, p ∈ N. (3) There exists i, j ∈ [1 . . . d + 1] such that ω j m i -ω i m j = nω i -pω j with n, p ∈ N.
λω d = p m i + λω i = n
This gives the second equation.

• If n and p are at position less than d -1, we obtain a system of two equations

m i + λω i = n m j + λω j = p
We eliminate λ and we obtain the equation of case (3).

Corollary 2. Let A, B, C i , i = 1 . . . l be l + 2 faces of dimension d -1 and ω a minimal direction. We have the equivalence

γ A,B = i γ A,C i ⇐⇒ ω is not a B direction.
Proof. We consider the three functions which appear in Lemma 10.

     f (m) = nω i -pω j , g(m) = m i + nω i ω j -p, h(m) = ω j m i -ω i m j -(nω i + pω j ).
The diagonals γ A,B , γ A,C i have equations of the type f, g, h by preceding Lemma (with different n, p, i, j). Now without loss of generality we treat the case l = 1. The sets γ A,B , γ A,C are equal if and only if two of the preceding functions are equal on a set of positive measure. If two functions are equals for all m, it implies that they are of the same form. For example f can not be equal to g on a set of positive measure, thus we have different cases:

• If we have several times the map f , it implies the relation

nω i -pω j = n ω k -p ω l .
The coefficients of the direction are dependant over Q: contradiction with the minimality of the direction.

• If we have several times the map h, we obtain nω i + pω j = n ω i + p ω j which is impossible for the same argument.

• Thus the two equations are of the second form. We obtain

q ω i ω j -q ω i ω k = p -p , q ω j - q ω k = p -p ω i .
Thus ω is not a B direction. The converse is easy by the same argument. Proof. We make the computation for b, (it is exactly the same method for a). It represents the points which form a diagonal. The cylinder A + Rω is of dimension d = 1 + d -1. We use the dimension formula

dimE ∩ F = dimE + dimF -dim(E + F ).
In this case we have E = A + Rω, F = B. We deduce that the intersection of this cylinder with B is of dimension Proof.

d + d -1 -(d + 1) = d -2.
• First of all we consider the faces of dimension d which are at combinatorial length n of A. We claim that the points (b i ) i≤d+1 of these faces verify

d+1 i=1 i = n.
The proof is made by induction on n. It is clear for n = 1, now consider a billiard trajectory of length n, it means that just before the last face we intersect another face of the same cube. These face is at combinatorial length n -1, and we can apply the induction process. Now consider a point of these faces, denote by (c i ) i≤d+1 its coordinates. We verify easily that

d+1 i=1 b i - d+1 i=1 c i = 1 for all point b 0 , c.
This finishes the proof of the claim.

• Now there are two cases along if A, B are in a same hyperplane or not. If they are not in a same hyperplane the coordinates of point in B have the form given in the second point of the Lemma. Now assume A, B are contained in a hyperplane. The fixed coordinates of all points in A and B are at the same places. Then we project on the plane generated by these coordinates. On the plane of projection the images of A, B are two points with integer coordinates (0; 0) and (n d ; n d+1 ). The diagonal projects on a line passing through these two points. To be sure that γ A,B is not the union of γ A,C i we can verify that this line does not contain integer points. The condition gcd(n d+1 , n d ) = 1 is equivalent to this property.

Corollary 3. A diagonal in a B direction is of the second form.

Proof. Consider a diagonal in a B direction. By preceding lemma there are two cases for the coordinates of the faces of start and go. In the first case, we have a rational relation between ω d and ω d+1 see equation (1) of Lemma 10.

Number of diagonals.

We consider the different diagonals of length n in direction ω.

Proposition 3. Let ω be a B direction, then we obtain:

card(Diag(n, d, ω)) = d(d -1) ∀n ∈ N * .
Proof. First consider the face A of dimension d -1. We can always assume that the points of A have the following coordinates t a 1 . . . a d-1 , 0, 0 .

We use Lemma 10, and we must compute the number of different faces B.

Since the direction is a B direction, we can not have case (1), see preceding

Corollary. Now case (2) correspond to the choice of one integer inside the first (d -1) coordinates, and one integer inside the last two coordinates. It gives 2(d -1) possibilities. Case (3) corresponds to the case of two integers inside the first d -1 coordinates, it gives (d -1)(d -2) possibilities. The total number of faces B is finally the sum of these numbers:

(d -1)(d -2) + 2(d -1) = d(d -1).

Projections

First we define the notion of coordinates spaces:

Definition 11. The space R d+1 has a basis (e i ) such that the edges of the cube are parallel to the vectors e i . Then we say that a linear space H is a coordinate space if there exists I ⊂ {1 . . . d + 1} such that (e i ) i∈I is a basis of H.

We denote by π H the orthogonal projection on H. We recall that a diagonal is given by two subspaces a, b.

Here we prove The intersection with the plane X d = c gives points of coordinates

t λa 1 + cω 1 /ω d , λa 2 + cω 2 /ω d , . . . , λa d-1 + cω d-1 /ω d , c, cω d+1 /ω d
Thus the projection by π H gives an hyperplane parallel to a, thus of dimension d -2. 9.1. Words. During the proof of Proposition 4, if γ is a diagonal between a and b we must compute the number of words in the diagonal. The set a is partitioned in several sets a i , and each set a i corresponds to a different word of the diagonal. We must compute the number of sets of these partition to prove our result. We will project these trajectories inside the space H, and compute the number of words inside this subspace. All the trajectories of one diagonal are in a space of dimension d -1. If we project on H we vanish two letters and keep d -1 letters.

In the space R d+1 the letter i appears in a word v ∈ γ, if and only if the plane X i = c, c ∈ R intersects < a, b >. The preceding lemma shows that the projection of this set does not vanish. But this projection does not coincide with a letter of the natural coding of billiard inside H for all letter since dimH = d -1. Thus we will add two letters to the natural coding of H to keep an alphabet with d + 1 letters, and we denote by L π(A),π(B) , the sets of all projections of the diagonals words.

Remark 3. In figure 4 we assume that H is of dimension two, and we draw the two codings on H. One is with 2 = d -1 letters and one with 4 = d + 1 letters.

Lemma 14. The map π H can be extended to billiard words.

π H : L A,B → L π H (A),π H (B) π H : v → π H (v)
The proof will explain the definition of π H (v).

Proof. We consider a billiard trajectory between A and B. Assume it has v for coding. Then we consider the image of the line by π. It is a billiard trajectory inside the unit cube of R d-1 , since the projection is an orthogonal projection by Lemma 4. We denote its coding by π H (v).

dimImπ = d -1 = dim < a, b >, we deduce dimH = dimH -1 = d -1, thus dimπ(H ) = d -1.
Thus there is no erasure in the projection, and π is injetive. Remark that some hyperplanes can project into spaces which have not integer coordinates, see preceding Lemma. Then we apply Lemma 15, and the map π is surjective. It suffices to consider the word v associated to the diagonal between A and B, with A = π(A) and m is the length of the word π(v). Now the space H is of dimension d -1, thus there are d -1 faces for the cube in this space. If we consider all the trajectories in direction π(ω) which start from these d -1 faces we have obtained all the billiard trajectories of length n -m in this space. With preceding notations we can denote the complexity in the natural language by p(n, d -2, ω ) and in the new coding by p(n, d -2, ω ). If we denote n 0 = n -m we deduce

γ v∈γa 1 = p(n -n 0 , d -2, π(ω)). Now we claim (d -1)p(n, d -2, ω ) = p(n, d -2, ω ).
When we pass from one coding to the other, it is similar to code the billiard inside the cube with a same letter for the parallel faces or not .Thus the two complexities are proportional, and the factor equals d -1. The proof finishes with this claim.

Dimension three

In this section we recall some facts about dimension three. This will be used in the next section, where we prove Theorem 1 by induction on d.

In [START_REF] Bedaride | Billiard complexity in rational polyhedra[END_REF] we prove the following result: Theorem 3. Assume ω is a B direction of RP 2 , then we have p(n, 2, ω) = n 2 + n + 1. s(n + 1, 2, ω) -s(n, 2, ω) = 2. Proposition 3 has showed that there are two diagonals in this case, thus the second point of the theorem is proved here. In fact it was proved in [START_REF] Bedaride | Billiard complexity in rational polyhedra[END_REF] with another method for d = 2. It implies that for all γ ∈ Diag(n, 2, ω) we have v∈γ 1 = 1. This finishes the computation of p(n, 2, ω). Remark that for d = 2, the set of B directions equals the set of totally irrational directions. In the following we denote the diagonal by the faces of start and end (A; B).

• We make an induction on d. The hypothesis is The complexity map p(n, d, ω) is independent of ω for all n. This finishes the proof of the Theorem. Remark that in the case d = 0, there is only one letter and we have p(n, 0) = 1, thus the formula of Theorem 1 is true for d = 2.

11.2. Proof of Baryshnikov's formula. In this section we prove Corollary 1. First we can omit the direction in the notation, with the help of Theorem 1. We will prove the formula by induction on n for all d.

For n = 0 the formula is true. It is clear that n → p(n, d) is a polynomial function on n, thus we only compute its value for n > d, by analyticity it will be the same for n ≤ d.

Then Lemma 6 gives:

  4.4. Unfolding: definition and example. The unfolding is a very useful tool in the study of billiards behavior. Consider a billiard trajectory in a polyhedron. To draw the orbit, we must reflect the line each time it hits a face of the polyhedron. The unfolding consists of reflecting the polyhedron through the face while continuing along the same line.Althought we deal with the cube of d + 1 dimensions, the figures are made for the square.Example 1. The billiard orbit of (m, ω) appears as sequence of intersections of the line m+Rω with the lattice Z d+1 , see Figure1. In the left hand picture we represent a billiard orbit inside the square by a dotted curve. It is unfolded into the line which intersects Z 2 .

Figure 1 .

 1 Figure 1. Unfolding.

Lemma 6 .

 6 Consider a sequence (p(n, d)) n,d∈N , where n, d are two integers such that p(0, d) = 1, p(1, d) = d + 1 for all d, and p(n, 0) = 1 for all n. Define s(n, d) = p(n + 1, d) -p(n, d) for all d > 0. Assume that for all integers n, d ≥ 2 we have

Figure 2 .

 2 Figure 2. Unfolding of billiard trajectories and diagonals

Proof.

  First we can assume that the point m ∈ A have coordinates of the following form t m 1 , . . . m d-1 , 0, 0 . Then each point of B have two coordinates equal to integers n, p. Thus its coordinates are of the form: t b 1 , . . . n, . . . p, . . . b d-1 . If the line m + Rω intersects B it means that there exists λ such that m + λω ∈ B. Then there are three choices, depending on the position of n, p in the coordinates. • If n, p are at positions d, d + 1 we obtain a system of the form λω d = n λω d+1 = p This gives equation (1).

7. 1 .

 1 Diagonal and words. Now we consider a B direction, and a diagonal in this direction. We know it exists by Corollary 2. We denote by A, B the faces related to the diagonal, and define the sets a, b by Definition 10. With the same notations, we denotea = {m ∈ A, (m + Rω) ∩ B = ∅.}. b = {m ∈ B, (m + Rω) ∩ A = ∅.}.Lemma 11. Let γ be a diagonal corresponding to the faces A, B, then we have dima = dimb = d -2.

7. 2 .•

 2 Figure 3. Diagonal, words

Proposition 4 .

 4 For all coordinates space H of dimension d -1 there exists n 0 ∈ N, ω ∈ RP d-2 and a B direction, ω such that a∈H v∈(a,b) 1 = (d -1)p(n -n 0 , d -2, ω ). Lemma 13. Assume that H does not contains the vectors e d , e d+1 of the basis related to the cube. Denote the coordinates in this base by (X i ) i≤d+1 . Then the image by π H of the linear space intersection of X d = c, c ∈ R and < a, b >, the space generated by a and b, is of dimension d -2. Proof. By assumption we have that the points of a have the following coordinates t a 1 , a 2 , . . . a d-1 , 0, 0 Then the space < a, b > generated by a and b contains points with coordinates of the form t λa 1 + µω 1 , λa 2 + µω 2 , . . . λa d-1 + µω d-1 , µω d , µω d+1

Figure 4 .

 4 Figure 4. Different codings in H

Lemma 15 .

 15 Assume d ≥ 3, let v ∈ L(m, d -2, π(ω)) be a billiard word between two faces A, B of dimension d -2. Then for all integer n ≥ m + 1 there exists one and only one face B of dimension d -2 such that:d(A, B) = n, γ A,B is an element of Diag(n, d, ω), π(B) = B . Proof. First remark that dimπ(B) ≥ d -2. Indeed we have by definition dimπ(B) ≤ dimB. Now the global space is of dimension d + 1, thus the orthogonal of < A, B > is of dimension 1 since dim < A, B >= d. It implies that the dimension of π(B) is at least d -1 -1.By Lemma 12, we can always lift the face B in a face B with d(A, B) = n. We just have to translate B to the coordinate x d = n -m. This face B is unique. The only point to prove is that the trajectories between A, B form a diagonal. We make a proof by contradiction. Then each trajectory between A, B intersects another face C i . It implies that γ A,B is cover by some γ A,C i . Contradiction with Corollary 2. Corollary 4. The map π is a bijection. Proof. All the trajectories between A, B are inside the space < a, b >. If there are several words in a diagonal γ A,B , it means that the cylinder < a, b > is cut by different hyperplanes. The hyperplanes which cut < a, b > into a set of dimension d are not interesting, since they correspond to letter which appear in each word of γ A,B . Thus to count the number of words in γ A,B we must calculate the number of hyperplanes H which cut E a,b into a subspace H of codimension 1 into < a, b >. Since the projection π fulfills

9. 2 .

 2 Proof of Proposition 4. By Lemma 4 the projection of the billiard trajectory inside H is a billiard trajectory. This trajectories start into π(a) and finish into π(b). By Lemma 12, their combinatorial length are equal to n -m. Moreover the B-direction projects on a B-direction π(ω), by definition. By Corollary 4 we have v∈γa

11.

  Proof of the results11.1. Proof of Theorem 1. By Lemma 1 we must computeBL(n) i(v). ByProposition 1, we have:BL(n) i(v) = γ A,B v∈ γ A,B 1.This can be written ass(n + 1, d, ω) -s(n, d, ω) = H γ∈H v∈γ i(v).By Proposition 4 we have for any (A, B) which form a diagonalγ∈H v∈γ A,B 1 = (d -1)p(n -n 0 , d -2, ω ).Thus we haveBL(n) i(v) = H (d -1)p(n -n 0 , d -2, ω ).

  First the induction hypothesis is true for d = 2, see preceding Section. Now by preceding Proposition we haves(n + 1, d, ω) -s(n, d, ω) = H (d -1)p(n -n 0 , d -2, ω ).Then we use the induction hypothesis for d -2, and choose a direction ω such that n 0 = 0, see Proposition 4. Remark that such a direction can depend of the integer n.We deduces(n + 1, d, ω) -s(n, d, ω) = H (d -1)p(n, d -2).Thus the induction process is finished, and the claim is proved. Moreover Proposition 3 implies that card(A, B ∈ Diag(n, ω, d)) = d(d -1). Since dimH = d -1 we deduce that d -1 projections of diagonals are in the same space H. Thus there are d different classes of diagonals, in each class every diagonal belongs to the same space H. We deduce s(n + 1, d, ω) -s(n, d, ω) = d(d -1)p(n, d -2).

p

  (n + 1, d) = p(n, d) + dp(n, d -1).Now the induction hypothesis givesp(n + 1, d) = d i=0 n!d! (n -i)!(d -i)!i! + d d -1)! (n -i)!(d -1 -i)!i! . p(n + 1, d) = d-1 i=0 n!d! (n -i)!(d -1 -i)!i! !(d + 1 -i) (n -i)!(d -i)!i! + n! (n -d)! . p(n + 1, d) = d i=0 n!d!(d + 1 -i) (n -i)!(d -i)!i! .Now we use Lemma 5, and the induction process is finished.