Tyll Krueger
email: tyll.krueger@pwr.edu.pl

AND Arnaldo Nogueira
email: arnaldo.nogueira@univ-amu.fr

Serge Troubetzkoy
email: serge.troubetzkoy@univ-amu.fr

Serge Troubetzkoy On

ON THE COMPLEXITY OF POLYGONAL BILLIARDS

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

How complex is the billiard dynamics in a polygon? According to Katok this is one of the two main open questions concerning arbitrary polygonal billiards [START_REF] Katok | Billiard table as a playground for a mathematician[END_REF] or even one of the five most resistant problems in dynamics [START_REF] Katok | Five most resistant problems in dynamics[END_REF]. This question has been the subject of many articles. The first such result, due to Boldrighini, Keane and Marchetti, and independently to Sinai, is that the metric entropy of the billiard map with respect to the Liouville measure (and thus of the billiard flow) is zero [START_REF] Boldrighini | Billiards in polygons[END_REF][START_REF] Ya | Introduction to ergodic theory[END_REF][START_REF] Ya | Topics in ergodic theory[END_REF]. Katok proved that the metric entropy of every invariant measure is zero as well [START_REF] Katok | The growth rate for the number of singular and periodic orbits for a polygonal billiard[END_REF].

To refine these results one can study two quantities. A saddle connection is an orbit segment starting and ending at a corner of the polygon. The quantity N g (t) denotes the number of saddle connections with geometric length at most t and N c (n) denotes the number of saddle connections with combinatorial length at most n, here the number of links of a saddle connection is called its combinatorial length. Label the sides of the polygon by a finite alphabet A and code the forward orbit of a point by the sequence of sides it hits. The other quantity traditionally studied is p(n) the number of distinct words of length n which arise in this coding. Cassaigne, Hubert and Troubetzkoy showed that (1)

p(n) = n-1 j=0 N c (j)
for all convex polygons [CaHuTr]. The proof given in [CaHuTr] shows that this formula actually also holds for non-convex simply connected 1 polygons since any n-cell is convex ( [START_REF] Katok | The growth rate for the number of singular and periodic orbits for a polygonal billiard[END_REF]). A similar formula with possible low order correction terms was shown for all polygons by Bedaride [Be], correction terms are necessary for non simply connected polygons.

Masur showed that 0 < lim inf Ng(t) t 2

≤ lim sup Ng(t) t 2

< ∞ for any rational polygon [START_REF] Masur | Lower bounds for the number of saddle connections and closed trajectories of a quadratic differential, Holomorphic functions and moduli[END_REF][START_REF] Masur | The growth rate of trajectories of a quadratic differential[END_REF]. Elementary arguments show that an analogous result holds for N c (n), thus the [CaHuTr] relationship implies that 0 < lim inf p(n) n 3 ≤ lim sup p(n) n 3 < ∞ for any rational polygon. Suppose Q is an arbitrary polygon, for two point x, y ∈ Q let N g (x, y, t) denote the number of paths of length at most t connecting x to y. In 1986, in an unpublished, but widely circulated letter to Masur, Boshernitzan showed that for fixed ε > 0 and x ∈ Q, for Lebesgue a.e. y we have lim N (x,y,t)

t 2+ε
= 0 and lim inf N (x,y,t)

t 2+ε
< ∞, this result was published by Gutkin and Rams in 2009 [GuRa]. In this letter Boshernitzan also showed that there exist Q, x, y such that N (x, y, t) = 0 for all t > 0, seemingly the first result about non-illumination for polygonal billiards.

Katok's result implies that each of N g (t), N c (n) and p(n) grows subexponentially in any polygon, in particular the topological entropy of the billiard shift map σ Q : Σ Q → Σ Q is zero, where Σ Q denotes the collection of all infinite codes obtained in the polygon Q. Different proofs of zero topological entropy were given by Galperin, Krueger and Troubetzkoy [GaKrTr], as well as by Gutkin and Haydn [START_REF] Gutkin | Topological entropy of generalized polygon exchanges[END_REF][START_REF] Gutkin | Topological entropy of polygon exchange transformations and polygonal billiards[END_REF].

Scheglov has improved this for special classes of polygons, he first showed that for almost every triangle N c (n) grows slower than e n ε for every ε > 0 [Sc1, Sc2], and then he showed that for almost every right triangle

N c (n) ≥ n 2 √ 3
-ε infinitely often for every ε > 0 [START_REF] Scheglov | Complexity lower bound for typical right triangular billiards[END_REF]. For each m ≥ 3 and each k ≥ 1 Hooper exhibited an open set of m-gons for which lim inf t→∞ N g (t)/(t log k (t)) > 0 [Ho]. Troubetzkoy showed that p(n) grows at least quadratically in any polygon [Tr].

In this article we first study the functions N g (t), N c (n) and p(n) for topologically typical polygons. For generic polygons, up to fluctuations the number or saddle connections grows quadratically, and the complexity of generic polygons grows cubically (Theorem 1), other than Scheglov's right triangle result, these are the first polynomial growth result known for irrational billiards, and the exponents agree with the growth exponent of rational billiards.

Then we go on to study the metric version of the complexity or the slow entropy of the billiard in an arbitrary polygon. We give an almost sure polynomial lower bound estimate on the decay of the size of an n-cell (Theorem 3) and prove that this bound has significant deviations (Theorem 5). Theorem 3 implies that the upper metric complexity of the billiard shift in the sense of Ferenczi [Fe] and the upper slow entropy of the billiard shift in the sense of Katok and Thouvenot [KaTh] have polynomial upper bounds (Corollary 4).

Background material

2.1. Polygonal billiards. Let Q be a planar polygon. The billiard flow φ t in Q is the free motion of a point particle with unit speed and specular reflections from the boundary; the reflections are not defined at corners of the polygon. The phase space (a) P Q of φ t is the set of all inner pointing unit vectors, i.e.,

P Q = {(x, ψ) : x ∈ Q, ψ ∈ [0, 2π), the vector (x, ψ) points into Q }.
The billiard map S is the first return map of the billiard flow to the boundary ∂Q, it is not defined for points for which the next arrival to the boundary is a vertex. The phase space P Q of the billiard map is the set of inward pointing unit vectors with foot point in the boundary of Q and in this case we will denote the foot point by s (rather than x). We will use the arc length parametrization of ∂Q. The direction θ of a vector z = (s, θ) will refer to the angle the vector makes with the positive direction of the boundary. We fix the positive orientation on ∂Q and define the angle at the vertices of Q by one sided continuity.

We label the sides of an m-gon Q by an m-element alphabet A and code each forward orbit by the sequence of sides it hits. For any z ∈ P Q such that S n (z) is defined the n-cell C n (z) is the open set of points for which S n is defined and whose coding sequence up to time n as coincides with z's coding sequence, equivalently it is the largest open set containing z for which the billiard map S n is continuous. Katok showed that each n-cell is a convex polygon whose boundary has at most Kn sides where K is an explicit constant, and each side of an n-cell is a branch of the singularity set of order j where 0 ≤ j ≤ n, i.e., points where T j is not defined but T j-1 is defined [Ka1, Lemma 4].

Let λ and µ denote the invariant Liouville measure for the billiard flow, respectively, the billiard map, in our coordinates they are given by dλ = dx dψ and dµ = sin θ dθ ds. We consider the L 1 metric d((s, θ), (s , θ )) = |s -s | + |θ -θ | on P Q and denote the L 1 -ball in P Q centered at z of radius ε by B(z, ε). We also consider the metric ρ((x, ψ), (x , ψ )) = ||x -x || 2 + |ψ -ψ | on P Q , and notice that the two metrics agree when restricted to a single side of the boundary.

To define a topology on the set of polygons with a fixed number of sides, we define a basis of as follows. Let Q be a polygon and assume ε is small enough such that the ε-neighborhoods of the vertices of Q are pairwise disjoint. Then Q is in the open ε-neighborhood of Q if there is exactly one vertex of Q in the open ε neighborhood of each vertex of Q. (a) We use italic for the flow in contrast to P Q for the map.

Polynomial entropy.

The notion of topological slow entropy, or polynomial entropy, was first defined and studied by Kůrka, Penne and Vaienti [KuPeVa] in 2002 and independently by Marco [Mar1] in 2013. For a subshift the lower and upper polynomial entropies are defined as

h poly (Σ, σ) = lim inf n→∞ ln p(n) ln n , h poly (Σ, σ) = lim sup n→∞ ln p(n) ln n .
Here p(n) denotes the number of distinct words of length n in Σ.

2.2.1. Previous results on polynomial entropy and billiards. Marco studied the upper polynomial entropy of billiards in smooth convex tables, he showed that the upper polynomial entropy of the billiard map in a circle is 1, is 2 for non-circular ellipses, and at least 2 for any other smooth convex billiard table [START_REF] Marco | Entropy of billiard maps and a dynamical version of the Birkhoff conjecture[END_REF].

2.3. Metric complexity or slow entropy. We define the Ferenczi's metric complexity or Katok-Thouvenot's slow entropy in the setting of shift spaces [Fe, KaTh]. Let Σ be a (one-sided) shift space over the alphabet A and σ : Σ → Σ the left shift map, which preserves an invariant measure ν.

For two words a, b ∈ A k we consider the d or Hamming distance d(a, b) := 1 k #{i : a i = b i }. For x ∈ Σ let B(x, n, ε) := {y ∈ Σ : d(x 0,n-1 , y 0,n-1) ) < ε} where x 0,n-1 denotes the truncation of x to its first n symbols. By [GaKrTr] the partition into cylinders of length 1 (i.e., the sides of Q) is a generating partition for the shift map Σ Q , thus the definition of metric complexity becomes somewhat simpler in this setting [Fe, KaTh, Cor 1]. Let P (n, ε) denote the smallest number P such that there exists a subset of Σ of measure at least 1 -ε covered by at most P balls B(x, n, ε). Let g : N → N be an increasing function. We say (Σ, σ, ν) has upper metric complexity or upper slow entropy at most g

(n) if lim ε→0 lim sup n→∞ P (n, ε) g(n) ≤ 1.

Statements of results

Theorem 1. For each ≥ 3 there is a dense G δ -set G of polygons with sides such that for each Q ∈ G there exists an infinite strictly increasing integer sequence (m k ) such that

lim k→∞ log N Q g (m k ) log m k = lim k→∞ log N Q c (m k ) log m k = 2, and lim k→∞ log p Q (m k ) log m k = 3.
Corollary 2. For each Q ∈ G the polynomial entropies satisfy

h poly (Σ Q , σ Q ) ≤ 3 ≤ h poly (Σ Q , σ Q ).
We turn to the study of the metric complexity of polygonal billiards. The set of points whose billiard orbit hits a given finite sequence of sides of length n is called an n-cell, and C n (z) denotes the n-cell containing the point z. The main result of [GaKrTr] is that for each non-singular z the set C n (z) converges to the point z if and only if z is aperiodic. Our first result in this direction is an almost sure lower bound estimate on the speed of this convergence. Let P Q denote the phase space of the billiard map and B(z, ε) denotes the L 1 -ball in P Q centered at z of radius ε. The next result and its corollary improve implicit results of Sinai [START_REF] Ya | Introduction to ergodic theory[END_REF][START_REF] Ya | Topics in ergodic theory[END_REF].

Theorem 3. Let Q be a polygon and f : N → N be a monotonically increasing function such that 1 nf (n) is summable. Then there is a dense G δ -set G ⊂ P Q of full µ measure such that for every z ∈ G there exists n 0 ≥ 0 such that for all n ≥ n 0 we have

B z, 1 n 3 f (n) ⊂ C n (z).
As previously mentioned the partition into cylinders of length is a generating partition, thus we get the following corollary.

Corollary 4. The upper metric complexity or upper slow entropy of the billiard shift is at most n 6 (f (n)) 2 where f : N → N is any monotonically increasing function such that 1 nf (n) is summable.

Our next result shows that the lower bound 1/(n 3 f (n)) in Theorem 3 can have rather large deviations.

Theorem 5. Let Q be a polygon and f : N → N be a monotonically increasing function. Then there is a dense G δ -set G ⊂ P Q of full µ measure such that for every z ∈ G there exists an infinite strictly increasing sequence n i such that

B z, 1 n 2 i f (n i ) ⊂ C n i (z).
Theorems 3 and 5 have analogs for arbitrary invariant measures as well as for higher dimensional polyhedra, these results will be stated in Section 6.

Complexity of typical polygonal billiards

4.1. Estimates in small neighborhoods of a rational polygon. We prove Theorem 1 by approximating irrational billiards by rational billiards. To do this we need to give lower and upper bounds on how many saddle connections of length n or how many n-cells can occur in a polygon close to a given rational polygon. Thus in this section we will emphasize the Q dependence of the functions

N Q c (n) and p Q (n).
Proposition 6. Suppose Q is a rational polygon. Then there exist constants 0 < C ≤ C and 0 < K ≤ K such that for each n 0 ≥ 1 and each ε ∈ (0, 1) there exists an open set U whose closure contains Q such that

Cn 2 ≤ N Q c (n) ≤ (C/ε)n 2+ε and Kn 3 ≤ p Q(n) ≤ (K/ε)n 3+ε for all Q ∈ U and all 1 ≤ n ≤ n 0 .
We begin by a simple Lemma which proves the lower bound of the Proposition.

Lemma 7. Fix a polygon Q and n 0 ≥ 1, then there exists δ > 0 such that

N Q c (n) ≥ N Q c (n) and p Q(n) ≥ p Q (n) for all 1 ≤ n ≤ n 0 and all Q ∈ B(Q, δ).
Proof. The second inequality follows from the first inequality by (1). Consider a saddle connection γ of combinatorial length at most n. Consider it in its unfolding. Except for the starting and ending vertices the distance of γ to the other vertices is strictly positive. The unfolding varies continuously with the polygon in the sense that the vertices of the unfolded picture vary continuously, thus we can choose a small neighborhood of Q for which γ persists. The lemma follows since the collection of saddle connections of combinatorial length at most n 0 is finite.

For the upper bound we need to work quite a bit more. A saddle chain is a finite union of saddle connections which are on a straight line in an unfolding. A crucial point is that under perturbation saddle chains can create new saddle connections.

Lemma 8. Suppose Q is a rational polygon with sides, such that N Q c (n) ≤ Cn 2 for all n ≥ 1. Fix n 0 and ε ∈ (0, 1), then there exists an open set of polygons U containing Q such that

N Q c (n) ≤ 9C ε n 2+ε for all Q ∈ U and 1 ≤ n ≤ n 0 .
Proof. Throughout the proof length will refer to combinatorial length. We need to understand how new saddle connections can arise when perturbing Q. We claim the new saddle connections can only arise from a saddle chain. To see this fix a polygon Q 0 and a small enough neighborhood U of Q 0 so that we can identify sides and vertices of all the polygons in U . Consider a continuous one parameter family {Q t ∈ U : t ∈ [0, 1)}. We fix a labelling of the vertices and edges of all the Q t . Suppose that there is a saddle connection γ t connecting a vertex v 1 to a vertex v 2 with code w in all Q t for t ∈ (0, 1) but that this saddle connection does not exist in Q 0 . We consider convergence in the unfolded picture, and use the same symbols for saddle connection in the unfolding and in the polygon. Consider the unfoldings of Q t along γ t . Both γ t and the associated unfoldings vary continuously with t. (b) As t → 0, the connections γ t converge to a straight line segment γ 0 connecting v 1 to v 2 in the unfolding of Q 0 , since by assumption this is not a saddle connection there must be one or more vertices in between the two vertices, i.e., the saddle connection γ t has degenerated to a saddle chain γ 0 , which proves our claim. We remark that a whole side of the polygon can block the saddle connection, thus for the purpose of this proof a side of a polygon is considered to be a saddle connection, remember that this is not the case in the Cassaigne, Hubert, Troubetzkoy formula, this plays no role in our estimates since there are only finitely many such saddle connections or saddle chains.

We would like to choose the perturbation of the polygon small enough that a saddle chain of length strictly less than n 0 does not create a new saddle chain of length at most n 0 , however this turns out impossible in general, and we allow the creation of certain special saddle chains as we will now explain. Consider any saddle connection γ of length n < n 0 , and let γ ± denote its two forward continuations of length n 0 . Note that either of these could be a saddle chain. Fix one of these, say γ + and consider the associated unfolding. Let V γ + denote the set of vertices of the unfolding contained in γ + and V denote the vertices of the unfolding not in γ + Consider the collection SC(γ + ) of all saddle connections in the unfolding connecting vertices in V γ + to vertices in V .

Let Θ(Q, γ + ) be the minimal angle between the direction of γ + and the directions of SC(γ + ). Note that the γ + dependence of Θ is actually on dependence on the unfolding of γ + . By assumption Θ(Q, γ + ) > 0, furthermore as long a Θ remains strictly positive it varies continuously with the perturbation. We require δ to be so small that for all Q ∈ U Θ( Q, γ + ) > Θ(Q, γ + )/2, i.e., if any new saddle chain is created in only visits vertices from V γ + . An example of such a new saddle chain is shown in the Figure 1, our estimates are worst case estimates for which we have counted this new saddle chain as having created all possible saddle connections. The final choice of δ must satisfy this requirement for each saddle connection of length at most n 0 and of course for γ -as well.

Thus to make our estimate we need to understand how many saddle chains there are and how many saddle connections a saddle chain can create under perturbation. Figure 2 depicts such a situation, a saddle chain consisting of three saddle connections of length 1 creates two additional saddle connections of length 2 and one additional saddle connection of length 3.

(b) More precisely, the unfolding can be viewed as a polygon in the plane, and the vertices of this polygon vary continuously with t. Consider a saddle chain consisting of j saddle connections in a polygon Q. Consecutive pairs of the j + 1 endpoints are by definition connected by a saddle connection in Q. Each non-consecutive pair of the j + 1 endpoints of the j saddle connections can possibly create a new saddle connection (such as in Figure 2). Thus a saddle chain consisting of j saddle connections can create at most j+1 2 -j ≤ j 2 new saddle connections.

Fix ε ∈ (0, 1), n 0 ≥ 1. Let K = 2/ε and consider 1 ≤ n ≤ n 0 . We split the saddle chains of combinatorial length at most n into K ≥ 2 classes according to the combinatorial length of the shortest saddle connection in the saddle chain. For each 1 ≤ i ≤ K let a i := i K . Then let I 1 := [0, a 1 ] and for 2 ≤ i ≤ K let I i := (a i-1 , a i ]. A chain is in group i if the shortest generalized diagonal in the chain is of combinatorial length n a with a ∈ I i . For small n some of these groups can be empty, but that does not effect our upper bound.

We would like to enumerate saddle chains by the shortest saddle connection contained in them. The starting point of the saddle chain plays a role, for example there could be a saddle chain ending with a saddle connection, and a different one starting with the same saddle connection. Fix a saddle connection γ of length j < n which appears in a saddle chain of length at most n. Let E ± (γ) be the two extensions by one sided continuity of γ obtaining by extending γ backwards and forwards by n -j. The length of E ± (γ) is 2n -j. Each saddle chain of length n containing γ must be contained in E + (γ) or in E -(γ). We consider the longest saddle chain γ± contained in each of E ± (γ), the worst case estimate is that γ± is of length 2n -j < 2n. Thus there are at most 2

(N Q c (n a i ) -N Q c (n a i-1 )) < 2N Q c (n a i ) ≤ 2Cn 2a i such saddle chains.
Suppose γ is of length n a with a ∈ I i . In the next paragraph we explain the estimates for E + (γ), the estimates for E -(γ) are similar.

There are two cases, the first case is when γ is the shortest saddle connection in all saddle chain of length n containing it, so the shortest saddle connection in E + (γ). It follows that the longest saddle chain in E + (γ) can consist of at most j = 2n/n a i-1 saddle connections. Applying the argument from above yields that E + (γ) can create at most j 2 = (2n/n a i-1 ) 2 new saddle connections. Now suppose that γ is the shortest saddle connection in some saddle chain of length n, but not the shortest in some other saddle chain of length n. In this case, we redefine E + (γ) by extending γ only up to the first shorter saddle connection. Let m < 2n be the length of the redefined E + (γ). Repeating the above arguments yields the longest saddle chain in E + (γ) can consist of at most j = m/n a i-1 < 2n/n a i-1 saddle connections and E + (γ) can create at most j 2 = (m/n a i-1 ) 2 < (2n/n a i-1 ) 2 new saddle connections.

Combining these estimates yields that the number of possible new generalized diagonals emerging from a chain in group i is bounded from above by Cn 2a i (2n/n a i-1 ) 2 = 4Cn 2+2a i -2a i-1 = 4Cn 2+2/K . Since we have K groups the total number of newly generated generalized diagonals emerging from chains of length n is bounded by 4KCn 2+2/K = 4 2/ε Cn 2+2/K ≤ (9C/ε)n 2+ε .

Proof of Proposition 6. The lower bounds follow from Lemma 7 by choosing C and K = C/2 the corresponding constants for the rational polygon Q.

On the other hand the upper bound follows from Lemma 8 combining with the formaula p(n) = n-1 j=0 N c (j) from [CaHuTr] to Q ∈ U yields

p Q(n + 1) ≤ N c (0) + 8C ε n m=1 m 2+ε ≤ N c (0) + 8C ε n+1 1 x 2+ε dx ≤ N c (0) + 8C ε(3 + ε) (n + 1) 3+ε .
Thus we can choose a strictly positive constant K such that p Q(n) ≤ (K/ε)n 3+ε for all 1 ≤ n ≤ n 0 .

4.2. Proof of Theorem 1. Fix ≥ 3. Consider a dense set {Q i } of rational polygons with sides. For short we will write N i c (n) for N Q i c and p i (n) for p Q i (n). For each Q i we consider the constants C i , K i , C i , K i given by Proposition 6, applied to ε i := 1/i and n i so large that

(2) max log(C i ) log n i , log(K i ) log n i , log(iC i ) log n i , log(iK i ) log n i < 1 i .
According to Proposition 6 we can choose an open set

U i for Q i , ε i , n i , such that for all Q ∈ U i we have log(N Q c (n i )) log n i ≥ log(C i n 2 i ) log n i = 2 + log(C i ) log n i > 2 - 1 i log(p Q (n i )) log n i ≥ log(K i n 3 i ) log n i = 3 + log(K i ) log n i > 3 - 1 i and log(N Q c (n i )) log(n i ) ≤ log(iC i n 2 i ) log(n i ) = 2 + log(iC i ) log(n i ) < 2 + 1 i . log(p Q (n i )) log(n i ) ≤ log(iK i n 3 i ) log(n i ) = 3 + log(iK i ) log(n i ) < 3 + 1 i . Now consider the dense G δ -set G := k≥2 i≥k U i .
For each Q ∈ G there is an increasing sequence i k such that 2 -

1 i k < log(N Q c (n i k )) log(n i k ) < 2 + 1 i k 3 - 1 i k < log(p Q (n i k )) log(n i k ) < 3 + 1 i k hold for each i k . Setting m k := n i k yields lim k→∞ log N Q c (m k ) log m k = 2 and lim k→∞ log p Q (m k ) log m k = 3.
The assertion, lim k→∞

log N Q g (m k ) log m k = lim k→∞ log N Q c (m k ) log m k
, follows after a slight modification of the proof. For each polygon Q there are positive constants

L Q < d(Q) := diameter(Q) and N 0 such that if γ is a saddle connection of combinatorial length n ≥ N 0 then its geometric length is contained in the interval [L Q n, d(Q)n]. Thus implies that N g (L Q n) ≤ N c (n) ≤ N g (d(Q)n). The stated result is scale invariant, so we can assume d(Q) = 1, thus we obtain N c (n) ≤ N g (n) ≤ N c ( n/L Q ). We immediately conclude lim k→∞ log N Q g (m k ) log m k ≥ lim k→∞ log N Q c (m k ) log m k = 2.
To prove the reverse inequality we will modify the above construction so that not only

log N Q c (m k ) log m k = 2 but also log N Q c ( m k /L Q ) log m k
= 2, which will finish the proof.

To prove the reverse inequality note that the constant L Q depends weakly on Q, it can be chosen constant in a neighborhood N of Q. In the rest of the proof we fix the neighborhood and the constant L := L Q . Now in the previous construction in (2) we additionally require that if

Q i ∈ N then n i satisfies log(iC i /L 2 ) log n i < 1 i and applying Proposition 6 to Q i , ε i , n i /L . Then log N Q g (m k ) log m k ≤ log N Q c ( m k /L ) log m k ≤ log(iC i (n i /L) 2 ) log(n i ) = 2 + log(iC i /L 2 ) log(n i ) ≤ 2 - 1 i .
To improve Theorem 1 from a subsequence result to a result for all n, one would need to have effective bounds on the various constants and the rate of approximation, this seems difficult.

Metric complexity of polygonal billiards

We begin by a geometric result, we will show that points whose orbit stays far from the boundary of the phase space must have a large n-cell. The boundary ∂P Q of the phase space P Q consists of vectors tangent to a side of the polygon Q and vectors whose foot point is a vertex of Q. If Q is not convex then the flow orbit of a point z ∈ P Q can pass close to a vertex with neither z nor S(z) being close to a vertex (Figure 3), this motivates the following definition. For z ∈ P Q let t(z) denote the geometric length of the orbit segment between z and S(z). Let

(3)

B a := {z ∈ P Q : φ t (z) ∈ B(∂P Q , a) for some t ∈ [0, t(z)]}
and for T > 0 let

G T a := {z ∈ P Q : φ t (z) ∈ B a for 0 ≤ t ≤ T }. Let T n := n • diam(Q). Proposition 9. For each polygon Q, a > 0, n ≥ 1, and z ∈ G Tn a we have B(z, a/(2 + T n )) ⊂ C n (z)
Proof. There is a strictly positive constant k 2 depending only on Q such that any orbit segment φ [0,T ] (z) makes at most k 2 T collisions, thus (4)

P Q \ G T a = {z ∈ P Q : φ t (z) ∈ B a for some 0 ≤ t ≤ T } ⊂ 0≤j≤k 2 T S -j B a . z S(z) d z z S(z) v w d z z S(z) v w Figure 3. Three examples of z ∈ B a . Suppose z ∈ G T a .
For calculational convenience we consider a flowbased version of n-cells, let C T (z) ⊂ P Q be the maximal neighborhood of z (in P Q ) such that φ T | C T is continuous. A billiard orbit segment of geometric length diam(Q) must make at least one bounce. It follows that a billiard orbit segment of geometric length T must make at least T /diam(Q) bounces, and thus

C T (z) ⊂ C T /diam(Q) (z).
Note that C k 2 T (z) ⊂ C T (z), but we will not use this.

Our goal is to estimate the largest δ > 0 such that B(z, δ) ⊂ C T (z); δ is always assumed small enough so that this inclusion holds.

Call a subset of parallel vectors in B(z, δ) a horizontal segment. By assumption φ T is continuous on B(z, δ), and thus when restricted to a horizontal segment it is an isometry.

We call a subset of vectors in B(z, δ) with the same base point in B(z, δ) a vertical segment. Now we will consider the action of φ T on vertical segments. Let ⊂ B(z, δ) be the vertical segment with lower endpoint (s, θ 0 ) and upper endpoint (s, θ 1 ) where 2δ = θ 1 -θ 0 . For r ∈ [0, 1] let θ r := (θ 1 -θ 0 )r + θ 0 , so = {z r := (s, θ r ) : 0 ≤ r ≤ 1}. In the unfolding of the orbit segment z to φ T (z), the image φ T ( ) =: {z r,T := (x r,T , θ r ) : 0 ≤ r ≤ 1} is an arc of angle δr of a circle of radius T (Figure 4), thus in the unfolding we trivially have the following bound ||x 0,T -xr,T || < T δr for each 0 ≤ r ≤ 1. On the other hand θ r -θ 0 = δr. Thus in the phase space P Q we have ρ(z 0,T , z r,T ) ≤ T δr+δr = (T +1)δr for each 0 ≤ r ≤ 1. Now we will combine the above horizontal and vertical estimates. For z 1 = (s 1 , θ 1 ), z 2 = (s 2 , θ 2 ) ∈ B(z, δ) we consider z 3 = (s 1 , θ 2 ). The estimates of the previous two paragraphs and the triangle inequality yield

ρ(φ T (z 1 ), φ T (z 2 )) ≤ ρ(φ T (z 1 ), φ T (z 3 )) + ρ(φ T (z 3 ), φ T (z 2 )) ≤ δ + (T + 1)δ = (2 + T )δ.
We have arrived at the punch line of the geometric estimate. If z ∈ G T a , we have ρ(φ t (z), ∂P ) ≥ a for all 0 ≤ t ≤ T . Thus if δ satisfies δ(2 + T ) < a or equivalently δ < a/(2 + T ) then all points in B(z, δ) belong to C T (z) and thus we have B(z, a/(2 + T )) ⊂ C T /diam(Q) (z). Proof of Theorems 3 and 5. The first step of the proof is to estimate the quantity µ(B a ). If Q is convex we have

(5) B a ⊂ B(∂P Q , a) ∪ S -1 B(∂P Q , a)
and thus there is a constant

k 1 > 0 such that (6) µ(B a ) ≤ k 1 a.
Such an estimate remains true in the non-convex case, although (5) does not hold.

To see that (6) holds we need to consider the measure of points in z = (s, θ) ∈ B a \(B(∂P Q , a)∪S -1 B(∂P Q , a)); such a point is depicted in red in the central and right parts of Figure 3. Let S consist of the points whose S-image is not defined, i.e., hits a vertex, for example the blue segment in Figure 3 starts in S. Let d be the smallest distance of a nonconvex vertex (c) to a side not containing this vertex (dotted segment in the figure). Among the points closest to the segment φ [0,t(z)] (z) there must be a vertex. There could be several of them, then we choose the last one to which the flow arrives, call it v. Then there is a direction θ so that z = (s, θ ) ∈ S, this is denoted in blue in the figure . It has length at least d. Consider the (green) segment starting at v and perpendicular to the segment φ [0,t(z)] (z), call its other end point w. By assumption the segment [v, w] it has length less that a. This right triangle with vertices z, v, w yields |θ -θ | < arcsin a d < a d , and thus z ∈ B(S, a d ). The d in this estimate could be improved in certain cases, for example in the right part of Figure 3, but this is not necessary for us. We have shown

(7) B a ⊂ B(∂P Q , a) ∪ B(S, a/d) ∪ S -1 B(∂P Q , a).
Since the set S is a smooth curve in the phase space, we again obtain a (different) constant k 1 > 0 such that µ(B a ) ≤ k 1 a.

This inequality combined with (4) and the fact that µ is S-invariant implies we can choose a k 3 such that (8) µ(P Q \ G T a ) ≤ (k 2 T + 1)µ(B a ) = (k 2 T + 1)k 1 a ≤ k 3 T a. Now we have all the estimates necessary to make the G δ argument. Let K := 2 + diam(Q). For Theorem 3 let a n := K n 2 f (n) while for Theorem 5 let a n := K nf (n) and consider the corresponding sets B an . Applying Proposition 9 to z ∈ G Tn an yields B(z, 1/(n

3 f (n))) ⊂ C n (z), resp. B(z, 1/(n 2 f (n))) ⊂ C n (z).
For both choices of (a n ) Equation ( 8) yields µ(G Tn an ) → 1 as n → ∞.

Let G := n 0 ≥1 n≥n 0 G Tn an .
Notice that G is a dense G δ -set of full measure. If z ∈ G then there is an infinite sequence n i such that z ∈ G an i ,Tn i for all i which finishes the proof of Theorem 5. To prove Theorem 3 we notice that µ(G Tn an ) is summable and we apply the Borel-Cantelli lemma to the sets G Tn an to conclude that for a.e. z ∈ G there is an n 0 such that for all n ≥ n 0 we have z ∈ G Tn an .

Proof of Corollary 4. Any notation in Σ Q which corresponds to a notation in Q will be denoted with a bar, for example μ denote the lift of the invariant measure µ to Σ and z ∈ Σ Q denote the code of z ∈ P Q . For a point z in the set G from Theorem 3, the Theorem yields an n 0 such that μ(z [0,n-1] ) = µ(C n (z)) ≥ const n 6 (f (n)) 2 for all n ≥ n 0 . Let z[0, n -1] denote the cylinder set corresponding to the word z0,n-1 , here const is the normalizing constant of the measure µ. Let G N := {z ∈ G : n 0 (z) ≤ N }. Since G = ∪ N ≥1 G N is of full measure for each ε > 0 we can choose N such that µ(G N ) ≥ 1 -ε, thus its lift satisfies μ( ḠN ) > 1 -ε. Since distinct cylinder sets are disjoint we obtain a cover of ḠN by cylinders of measure at least const n 6 f (n) 2 , so there are at most (1-ε)n 6 f (n) 2 const such cylinders. For each z the cylinder set z[0,n-1] is just the ball B(z, n, 0). Any cover by cylinders (0 balls) is a cover by ε balls, thus the metric complexity can only be smaller than our estimate.

Generalizations of metric complexity results

6.1. Other invariant measures. Both Theorems 3 and 5 have versions for an arbitrary invariant measure on P Q . We remind the reader that the set B a was defined in (3).

Theorem 10. Let Q be a polygon, ν an S-invariant measure, and f : N → N be a monotonically increasing function such that 1 nf (n) is summable. There exists a non-increasing sequence (a n ) satisfying ν(B an ) < 1/n 2 f (n). For any such sequence there exists a set G of full ν-measure which is a dense G δ -subset of supp(ν) with the property that for every z ∈ G there exists n 0 ≥ 0 such that for all n ≥ n 0 we have

B z, a n 2 + n • diam(Q) ⊂ C n (z).
For the version of Theorem 5 we get:

Theorem 11. Let Q be a polygon, ν an S-invariant measure, and f : N → N be a monotonically increasing unbounded function. There is a non-increasing sequence (a n ) which satisfies ν(B an ) < K 0 /nf (n).

For any such sequence there is a set G of full ν-measure which is a dense G δ -subset of supp(ν) with the property that for every z ∈ G there exists an infinite strictly increasing sequence n i such that

B z, a n i 2 + n i • diam(Q) ⊂ C n i (z).
Proof of Theorems 10 and 11. The proof is a minor modification of the proof of Theorems 3 and 5. We begin by showing the existence of the sequences (a n ). Inclusion (7) yields By definition ν is supported on the set of non-singular points, in particular ν(∂P Q ) = 0 and ν(S) = 0. Thus we can choose (a n ) as in the statements of the two theorems since the right hand side of (9) goes to zero as a → 0. The sequences (a n ) are implicitly define, they differ from those in Theorems 3 and 5, but by definition the estimates of measures of the sets are the same as for µ. Thus for both Theorems we have ν(P Q \ G Tn n ) → 0 and for Theorem 10 we can apply the Borel-Cantelli Lemma. The rest of the proof follows from Proposition 9 in an identical fashion, the only difference being that we do not know the exact form of the sequence (a n ).

For irrational polygons we know very little about invariant measures. We give some sufficient conditions for which we can understand the growth of a n /(2 + n • diam(Q)).

If there exists a > 0 such that ν({z ∈ P Q : d(z, ∂P Q ) < a}) = 0 for sufficiently small a, then Theorem 10 tells us that for almost every z there exists n 0 ≥ 0 such that for all n ≥ n 0 we have

B z, a 2 + n • diam(Q) ⊂ C n (z).
This occurs for example for any invariant measure on a collection of periodic orbits which stay away from the boundary.

Suppose now that ν(B(∂P Q , a)) ≤ a r for some r > 0 and all sufficiently small a. In this case, the conclusion of Theorem 10 reads for ν-a.e. z there exists n 0 such that for all n ≥ n 0 we have

B z, 1 r n 2 f (n)(2 + n • diam(Q)) ⊂ C n (z)
while the conclusion of Theorem 11 reads for ν-a.e. z there exists an infinite strictly increasing sequence n i such that B z,

1 r n i f (n i )(2n i + 1) ⊂ C n i (z).
Of course the Liouville measure satisfies this with r = 1. Another example would be to take the uniform measure on a periodic cylinder. The boundary of a cylinder must touch a vertex somewhere, thus this also yields an example with r = 1 in any polygon with a periodic orbit.

6.2. Higher dimensions. Our techniques work for polyhedra in any dimension. In the m-dimensional case the phase space P Q of the billiard map is 2(m -1)-dimensional (m -1) spatial coordinates and (m -1) angular coordinates. The boundary of the phase space is then (2m-3)dimensional, coming from inner pointing vectors whose foot point is in the intersections of sides of the polyhedra, and the set of points tangent to a face. If again µ denotes the Liouville measure we obtain µ(B an ) ≤ Ca while for a version of Theorem 5 we use

a n = K 2m-3 √ nf (n)
which yields the following two results.

Theorem 12. Let Q be a polyhedron in R m and f : N → N be a monotonically increasing function such that 1 nf (n) is summable. Then there is a dense G δ -set G of full µ-measure such that for every z ∈ G there exists n 0 ≥ 0 such that for all n ≥ n 0 we have B z, 1

n 2m-3 n 2 f (n) ⊂ C n (z).
Theorem 13. Let Q be a polyhedron in R m and f : N → N be a monotonically increasing function. Then there is a dense G δ -set G of full µ-measure such that for every z ∈ G there exists an infinite strictly increasing sequence n i such that B z, 1

n i 2m-3 n i f (n i ) ⊂ C n i (z).

Figure 1 .

 1 Figure 1. After a small perturbation a saddle chain consisting of three saddle connections of length 1 (left) can create a saddle chain consisting of a saddle connection of length two and a saddle connection of length one (right).

Figure 2 .

 2 Figure 2. A saddle chain consisting of 3 saddle connections (dash-dotted on the left) can create 3 additional connections (dotted on the right).

Figure 4 .

 4 Figure 4. Unfolding a vertical segment

  a ) ≤ 2ν(B(∂Q, a)) + ν(B(S, a)).

2m- 3 n

 3 and µ(P Q \ G n ) ≤ nCa 2m-3 n . The estimate in Proposition 9 on linear separation does not change, thus for a version of Theorem 3 we choose a n = K 2m-3 √ n 2 f (n)

(c) i.e., the segment connecting two close enough points on the boundary of Q on opposite sides of the vertex lies outside Q.