ON THE COMPLEXITY OF POLYGONAL
BILLIARDS

Tyll Krueger, Arnaldo Nogueira, Serge Troubetzkoy

► To cite this version:

Tyll Krueger, Arnaldo Nogueira, Serge Troubetzkoy. ON THE COMPLEXITY OF POLYGONAL BILLIARDS. Journal of modern dynamics, 2025, 21, pp.579-596. 10.3934/jmd.2025011. hal-04327851

HAL Id: hal-04327851

https://hal.science/hal-04327851v1

Submitted on 6 Dec 2023

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY-SA 4.0 - Attribution - ShareAlike - International
License
# ON THE COMPLEXITY OF POLYGONAL BILLIARDS

TYLL KRUEGER, ARNALDO NOGUEIRA, AND SERGE TROUBETZKOY

**ABSTRACT.** We show that the complexity of the billiard in a typical polygon grows cubically and the number of saddle connections grows quadratically along certain subsequences. It is known that the set of points whose first $n$-bounces hits the same sequence of sides as the orbit of an aperiodic phase point $z$ converges to $z$. We establish a polynomial lower bound estimate on this convergence rate for almost every $z$. This yields an upper bound on the upper metric complexity and upper slow entropy of polygonal billiards. We also prove significant deviations from the expected convergence behavior. Finally we extend these results to higher dimensions as well as to arbitrary invariant measures.

## 1. 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 [Ka2] or even one of the five most resistant problems in dynamics [Ka3]. 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 [BoKeMar, Si1, Si2]. Katok proved that the metric entropy of every invariant measure is zero as well [Ka1].

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 $\mathcal{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) \qquad p(n) = \sum_{j=0}^{n-1} 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
polygons since any $n$-cell is convex ([Ka1]). A similar formula with
possible low order correction terms was shown for all polygons by Be-
daride [Be], correction terms are necessary for non simply connected
polygons.

Masur showed that $0 < \liminf \frac{N_g(t)}{t^2} \le \limsup \frac{N_g(t)}{t^2} < \infty$ for any rational polygon [Mas1, Mas2]. Elementary arguments show that an analogous result holds for $N_c(n)$, thus the [CaHuTr] relationship implies that $0 < \liminf \frac{p(n)}{n^3} \le \limsup \frac{p(n)}{n^3} < \infty$ for any rational polygon.

Suppose $Q$ is an arbitrary polygon, for two point $x, y \in 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 $\varepsilon > 0$ and $x \in Q$, for Lebesgue a.e. $y$ we have $\lim_{\frac{N(x,y,t)}{t^{2+\varepsilon}} = 0}$ and $\liminf_{\frac{N(x,y,t)}{t^{2+\varepsilon}} < \infty}$, 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 $\sigma_Q : \Sigma_Q \to \Sigma_Q$ is zero, where $\Sigma_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 [GuHa1, GuHa2].

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\varepsilon}$ for every $\varepsilon > 0$ [Sc1, Sc2], and then he showed that for almost every right triangle $N_c(n) \ge n^{\frac{2}{\sqrt{3}}-\varepsilon}$ infinitely often for every $\varepsilon > 0$ [Sc3]. For each $m \ge 3$ and each $k \ge 1$ Hooper exhibited an open set of $m$-gons for which $\liminf_{t\to\infty} 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).

## 2. BACKGROUND MATERIAL

### 2.1. Polygonal billiards.
Let $Q$ be a planar polygon. The billiard flow $\phi_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 $P_Q$ of $\phi_t$ is the set of all inner pointing unit vectors, i.e.,

$$ \mathcal{P}_Q = \{(x, \psi) : x \in Q, \psi \in [0, 2\pi), \text{ the vector } (x, \psi) \text{ points into } Q\}. $$

The billiard map $S$ is the first return map of the billiard flow to the boundary $\partial 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 $\partial Q$. The direction $\theta$ of a vector $z = (s, \theta)$ will refer to the angle the vector makes with the positive direction of the boundary. We fix the positive orientation on $\partial 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 $\mathcal{A}$ and code each forward orbit by the sequence of sides it hits. For any $z \in 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 \le j \le n$, i.e., points where $T^j$ is not defined but $T^{j-1}$ is defined [Ka1, Lemma 4].

Let $\lambda$ and $\mu$ denote the invariant Liouville measure for the billiard flow, respectively, the billiard map, in our coordinates they are given by $d\lambda = dx d\psi$ and $d\mu = \sin\theta d\theta ds$. We consider the $L_1$ metric $d((s, \theta), (s', \theta')) = |s - s'| + |\theta - \theta'|$ on $P_Q$ and denote the $L_1$-ball in $P_Q$ centered at $z$ of radius $\varepsilon$ by $B(z, \varepsilon)$. We also consider the metric $\rho((x, \psi), (x', \psi')) = ||x - x'||_2 + |\psi - \psi'|$ 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 $\varepsilon$ is small enough such that the $\varepsilon$-neighborhoods of the vertices of $Q$ are pairwise disjoint. Then $\hat{Q}$ is in the open $\varepsilon$-neighborhood of $Q$ if there is exactly one vertex of $\hat{Q}$ in the open $\varepsilon$ neighborhood of each vertex of $Q$.

<footnote>(a) We use italic for the flow in contrast to $P_Q$ for the map.</footnote>
2.2. **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

$$ \underline{h}_{\text{poly}}(\Sigma, \sigma) = \liminf_{n \to \infty} \frac{\ln p(n)}{\ln n}, \quad \bar{h}_{\text{poly}}(\Sigma, \sigma) = \limsup_{n \to \infty} \frac{\ln p(n)}{\ln n}. $$

Here $p(n)$ denotes the number of distinct words of length $n$ in $\Sigma$.

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 [Mar2].

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 $\Sigma$ be a (one-sided) shift space over the alphabet $\mathcal{A}$ and $\sigma: \Sigma \to \Sigma$ the left shift map, which preserves an invariant measure $\nu$.

For two words $a, b \in \mathcal{A}^k$ we consider the $\bar{d}$ or Hamming distance $\bar{d}(a, b) := \frac{1}{k}\#\{i : a_i \neq b_i\}$. For $x \in \Sigma$ let $\mathcal{B}(x, n, \varepsilon) := \{y \in \Sigma : \bar{d}(x_{0,n-1}, y_{0,n-1}) < \varepsilon\}$ 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 $\Sigma_Q$, thus the definition of metric complexity becomes somewhat simpler in this setting [Fe, KaTh, Cor 1]. Let $P(n, \varepsilon)$ denote the smallest number $P$ such that there exists a subset of $\Sigma$ of measure at least $1 - \varepsilon$ covered by at most $P$ balls $\mathcal{B}(x, n, \varepsilon)$. Let $g: \mathbb{N} \to \mathbb{N}$ be an increasing function. We say $(\Sigma, \sigma, \nu)$ has *upper metric complexity* or *upper slow entropy* at most $g(n)$ if

$$ \lim_{\varepsilon \to 0} \limsup_{n \to \infty} \frac{P(n, \varepsilon)}{g(n)} \le 1. $$

3. STATEMENTS OF RESULTS

**Theorem 1.** For each $\ell \ge 3$ there is a dense $G_\delta$-set $G$ of polygons with $\ell$ sides such that for each $Q \in G$ there exists an infinite strictly increasing integer sequence $(m_k)$ such that

$$ \lim_{k \to \infty} \frac{\log N_g^Q(m_k)}{\log m_k} = \lim_{k \to \infty} \frac{\log N_c^Q(m_k)}{\log m_k} = 2, \quad \text{and} \quad \lim_{k \to \infty} \frac{\log p^Q(m_k)}{\log m_k} = 3. $$

**Corollary 2.** For each $Q \in G$ the polynomial entropies satisfy

$$ \underline{h}_{\text{poly}}(\Sigma_Q, \sigma_Q) \le 3 \le \bar{h}_{\text{poly}}(\Sigma_Q, \sigma_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, \varepsilon)$ denotes the $L_1$-ball in $P_Q$ centered at $z$ of radius $\varepsilon$. The next result and its corollary improve implicit results of Sinai [Si1, Si2].

**Theorem 3.** Let $Q$ be a polygon and $f: \mathbb{N} \to \mathbb{N}$ be a monotonically increasing function such that $\frac{1}{nf(n)}$ is summable. Then there is a dense $G_\delta$-set $G \subset P_Q$ of full $\mu$ measure such that for every $z \in G$ there exists $n_0 \ge 0$ such that for all $n \ge n_0$ we have

$$B\left(z, \frac{1}{n^3 f(n)}\right) \subset 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: \mathbb{N} \to \mathbb{N}$ is any monotonically increasing function such that $\frac{1}{nf(n)}$ is summable.

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

**Theorem 5.** Let $Q$ be a polygon and $f: \mathbb{N} \to \mathbb{N}$ be a monotonically increasing function. Then there is a dense $G_\delta$-set $G \subset P_Q$ of full $\mu$ measure such that for every $z \in G$ there exists an infinite strictly increasing sequence $n_i$ such that

$$B\left(z, \frac{1}{n_i^2 f(n_i)}\right) \subset 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.

# 4. 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_c^Q(n)$ and $p^Q(n)$.
**Proposition 6.** Suppose $Q$ is a rational polygon. Then there exist constants $0 < \underline{C} \le \overline{C}$ and $0 < \underline{K} \le \overline{K}$ such that for each $n_0 \ge 1$ and each $\varepsilon \in (0,1)$ there exists an open set $U$ whose closure contains $Q$ such that

$$ \underline{C}n^2 \le N_c^{\hat{Q}}(n) \le (\overline{C}/\varepsilon)n^{2+\varepsilon} \quad \text{and} \quad \underline{K}n^3 \le p^{\hat{Q}}(n) \le (\overline{K}/\varepsilon)n^{3+\varepsilon} $$
for all $\hat{Q} \in U$ and all $1 \le n \le 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 \ge 1$, then there exists $\delta > 0$ such that $N_c^{\hat{Q}}(n) \ge N_c^Q(n)$ and $p^{\hat{Q}}(n) \ge p^Q(n)$ for all $1 \le n \le n_0$ and all $\hat{Q} \in B(Q, \delta)$.

**Proof.** The second inequality follows from the first inequality by (1). Consider a saddle connection $\gamma$ of combinatorial length at most $n$. Consider it in its unfolding. Except for the starting and ending vertices the distance of $\gamma$ 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 $\gamma$ persists. The lemma follows since the collection of saddle connections of combinatorial length at most $n_0$ is finite. $\square$

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 $\ell$ sides, such that $N_c^Q(n) \le \overline{C}n^2$ for all $n \ge 1$. Fix $n_0$ and $\varepsilon \in (0,1)$, then there exists an open set of polygons $U$ containing $Q$ such that

$$ N_c^{\hat{Q}}(n) \le \frac{9\overline{C}}{\varepsilon}n^{2+\varepsilon} \quad \text{for all } \hat{Q} \in U \text{ and } 1 \le n \le 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 \in U : t \in [0,1)\}$. We fix a labelling of the vertices and edges of all the $Q_t$. Suppose that there is a saddle connection $\gamma^t$ connecting a vertex $v_1$ to a vertex $v_2$ with code $w$ in all $Q_t$ for $t \in (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
$\gamma^t$. Both $\gamma^t$ and the associated unfoldings vary continuously with $t$. $^{(b)}$
As $t \to 0$, the connections $\gamma^t$ converge to a straight line segment $\gamma^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 $\gamma^t$ has degenerated to a
saddle chain $\gamma^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, Troubet-
zkoy 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 $\gamma$ of length
$n < n_0$, and let $\gamma^\pm$ denote its two forward continuations of length $n_0$.
Note that either of these could be a saddle chain. Fix one of these, say
$\gamma^+$ and consider the associated unfolding. Let $V_{\gamma^+}$ denote the set of
vertices of the unfolding contained in $\gamma^+$ and $V'$ denote the vertices of
the unfolding not in $\gamma^+$. Consider the collection $\mathrm{SC}(\gamma^+)$ of all saddle
connections in the unfolding connecting vertices in $V_{\gamma^+}$ to vertices in
$V'$.

Let $\Theta(Q, \gamma^+)$ be the minimal angle between the direction of $\gamma^+$ and
the directions of $SC(\gamma^+)$. Note that the $\gamma^+$ dependence of $\Theta$ is actually
on dependence on the unfolding of $\gamma^+$. By assumption $\Theta(Q, \gamma^+) > 0$,
furthermore as long a $\Theta$ remains strictly positive it varies continuously
with the perturbation. We require $\delta$ to be so small that for all $\hat{Q} \in U$
$\Theta(\hat{Q}, \gamma^+) > \Theta(Q, \gamma^+)/2$, i.e., if any new saddle chain is created in
only visits vertices from $V_{\gamma^+}$. 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 $\delta$ must satisfy this requirement
for each saddle connection of length at most $n_0$ and of course for $\gamma^-$ 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.

<footnote><sup>(b)</sup>More precisely, the unfolding can be viewed as a polygon in the plane, and
the vertices of this polygon vary continuously with *t*.</footnote>
<figure><img src="image_2.png" /><figcaption>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).</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>FIGURE 2. A saddle chain consisting of 3 saddle connections (dash-dotted on the left) can create 3 additional connections (dotted on the right).</figcaption></figure>

Now we turn to our estimate. The number of saddle chains in $\mathcal{Q}$ of length at most $n$ is bounded above by $2N_c^Q(n)$ since any saddle connection in $\mathcal{Q}$ can be the start of at most 2 saddle chains.

Consider a saddle chain consisting of $j$ saddle connections in a polygon $\mathcal{Q}$. Consecutive pairs of the $j+1$ endpoints are by definition connected by a saddle connection in $\mathcal{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 $\binom{j+1}{2} - j \le j^2$ new saddle connections.

Fix $\varepsilon \in (0, 1)$, $n_0 \ge 1$. Let $K = \lceil 2/\varepsilon \rceil$ and consider $1 \le n \le n_0$. We split the saddle chains of combinatorial length at most $n$ into $K \ge 2$ classes according to the combinatorial length of the shortest saddle connection in the saddle chain. For each $1 \le i \le K$ let $a_i := \frac{i}{K}$. Then let $I_1 := [0, a_1]$ and for $2 \le i \le 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 \in 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 $\gamma$ of length $j < n$ which appears in a saddle chain of length at most $n$. Let $E_\pm(\gamma)$ be the two extensions by one sided continuity of $\gamma$ obtaining by extending $\gamma$ backwards and
forwards by $n-j$. The length of $E_\pm(\gamma)$ is $2n-j$. Each saddle chain of length $n$ containing $\gamma$ must be contained in $E_+(\gamma)$ or in $E_-(\gamma)$. We consider the longest saddle chain $\hat{\gamma}_\pm$ contained in each of $E_\pm(\gamma)$, the worst case estimate is that $\hat{\gamma}_\pm$ is of length $2n-j < 2n$. Thus there are at most $2(N_c^Q(n^{a_i}) - N_c^Q(n^{a_{i-1}})) < 2N_c^Q(n^{a_i}) \le 2\bar{C}n^{2a_i}$ such saddle chains.

Suppose $\gamma$ is of length $n^a$ with $a \in I_i$. In the next paragraph we explain the estimates for $E_+(\gamma)$, the estimates for $E_-(\gamma)$ are similar.

There are two cases, the first case is when $\gamma$ is the shortest saddle connection in **all** saddle chain of length $n$ containing it, so the shortest saddle connection in $E_+(\gamma)$. It follows that the longest saddle chain in $E_+(\gamma)$ can consist of at most $j = \lfloor 2n/n^{a_{i-1}} \rfloor$ saddle connections. Applying the argument from above yields that $E_+(\gamma)$ can create at most $j^2 = (2n/n^{a_{i-1}})^2$ new saddle connections.

Now suppose that $\gamma$ 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_+(\gamma)$ by extending $\gamma$ only up to the first shorter saddle connection. Let $m < 2n$ be the length of the redefined $E_+(\gamma)$. Repeating the above arguments yields the longest saddle chain in $E_+(\gamma)$ can consist of at most $j = \lfloor m/n^{a_{i-1}} \rfloor < \lfloor 2n/n^{a_{i-1}} \rfloor$ saddle connections and $E_+(\gamma)$ 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 $\bar{C}n^{2a_i}(2n/n^{a_{i-1}})^2 = 4\bar{C}n^{2+2a_i-2a_{i-1}} = 4\bar{C}n^{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 $4K\bar{C}n^{2+2/K} = 4\lceil 2/\varepsilon \rceil \bar{C}n^{2+2/K} \le (9\bar{C}/\varepsilon)n^{2+\varepsilon}$. $\square$

**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 formula $p(n) = \sum_{j=0}^{n-1} N_c(j)$ from [CaHuTr] to $\hat{Q} \in U$ yields

$$ 
\begin{aligned}
p^{\hat{Q}}(n+1) & \le N_c(0) + \frac{8\bar{C}}{\varepsilon} \sum_{m=1}^{n} m^{2+\varepsilon} \le N_c(0) + \frac{8\bar{C}}{\varepsilon} \int_{1}^{n+1} x^{2+\varepsilon} dx \\
& \le N_c(0) + \frac{8\bar{C}}{\varepsilon(3+\varepsilon)} (n+1)^{3+\varepsilon}.
\end{aligned}
$$

Thus we can choose a strictly positive constant $\bar{K}$ such that $p^{\hat{Q}}(n) \le (\bar{K}/\varepsilon)n^{3+\varepsilon}$ for all $1 \le n \le n_0$. $\square$
**4.2. Proof of Theorem 1.** Fix $\ell \ge 3$. Consider a dense set $\{Q_i\}$ of rational polygons with $\ell$ sides. For short we will write $N_c^i(n)$ for $N_c^{Q_i}$ and $p^i(n)$ for $p^{Q_i}(n)$. For each $Q_i$ we consider the constants $\underline{C}_i, \overline{K}_i, \underline{C}_i, \overline{K}_i$ given by Proposition 6, applied to $\varepsilon_i := 1/i$ and $n_i$ so large that

$$ (2) \quad \max \left( \left| \frac{\log(\underline{C}_i)}{\log n_i} \right|, \left| \frac{\log(\overline{K}_i)}{\log n_i} \right|, \left| \frac{\log(i\overline{C}_i)}{\log n_i} \right|, \left| \frac{\log(i\overline{K}_i)}{\log n_i} \right| \right) < \frac{1}{i}. $$

According to Proposition 6 we can choose an open set $U_i$ for $Q_i$, $\varepsilon_i$, $n_i$, such that for all $Q \in U_i$ we have

$$ \frac{\log(N_c^Q(n_i))}{\log n_i} \ge \frac{\log(\underline{C}_i n_i^2)}{\log n_i} = 2 + \frac{\log(\underline{C}_i)}{\log n_i} > 2 - \frac{1}{i} $$

$$ \frac{\log(p^Q(n_i))}{\log n_i} \ge \frac{\log(\overline{K}_i n_i^3)}{\log n_i} = 3 + \frac{\log(\overline{K}_i)}{\log n_i} > 3 - \frac{1}{i} $$

and

$$ \frac{\log(N_c^Q(n_i))}{\log(n_i)} \le \frac{\log(i\overline{C}_i n_i^2)}{\log(n_i)} = 2 + \frac{\log(i\overline{C}_i)}{\log(n_i)} < 2 + \frac{1}{i}. $$

$$ \frac{\log(p^Q(n_i))}{\log(n_i)} \le \frac{\log(i\overline{K}_i n_i^3)}{\log(n_i)} = 3 + \frac{\log(i\overline{K}_i)}{\log(n_i)} < 3 + \frac{1}{i}. $$

Now consider the dense $G_\delta$-set

$$ G := \bigcap_{k \ge 2} \bigcup_{i \ge k} U_i. $$

For each $Q \in G$ there is an increasing sequence $i_k$ such that

$$ 2 - \frac{1}{i_k} < \frac{\log(N_c^Q(n_{i_k}))}{\log(n_{i_k})} < 2 + \frac{1}{i_k} $$

$$ 3 - \frac{1}{i_k} < \frac{\log(p^Q(n_{i_k}))}{\log(n_{i_k})} < 3 + \frac{1}{i_k} $$

hold for each $i_k$. Setting $m_k := n_{i_k}$ yields $\lim_{k \to \infty} \frac{\log N_c^Q(m_k)}{\log m_k} = 2$ and $\lim_{k \to \infty} \frac{\log p^Q(m_k)}{\log m_k} = 3$.

The assertion, $\lim_{k \to \infty} \frac{\log N_c^Q(m_k)}{\log m_k} = \lim_{k \to \infty} \frac{\log N_c^Q(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) := \text{diameter}(Q)$ and $N_0$ such that if $\gamma$ is a saddle connection of combinatorial length $n \ge 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) \le N_c(n) \le N_g(d(Q)n)$. The stated result is scale invariant, so we can assume $d(Q) = 1$, thus we obtain $N_c(n) \le N_g(n) \le N_c(\lceil n/L_Q \rceil)$. We immediately conclude

$$ \lim_{k \to \infty} \frac{\log N_g^Q(m_k)}{\log m_k} \ge \lim_{k \to \infty} \frac{\log N_c^Q(m_k)}{\log m_k} = 2. $$
To prove the reverse inequality we will modify the above construction so that not only $\frac{\log N_c^Q(m_k)}{\log m_k} = 2$ but also $\frac{\log N_c^Q([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 $\mathcal{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 \in \mathcal{N}$ then $n_i$ satisfies

$$ \left| \frac{\log(i\overline{C_i}/L^2)}{\log n_i} \right| < \frac{1}{i} $$

and applying Proposition 6 to $Q_i, \varepsilon_i, [n_i/L]$. Then

$$ \begin{aligned} \frac{\log N_g^Q(m_k)}{\log m_k} &\le \frac{\log N_c^Q([m_k/L])}{\log m_k} \le \frac{\log(i\overline{C_i}(n_i/L)^2)}{\log(n_i)} \\ &= 2 + \frac{\log(i\overline{C_i}/L^2)}{\log(n_i)} \le 2 - \frac{1}{i}. \end{aligned} \quad \square $$

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.

## 5. 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 $\partial 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 \in 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 \in P_Q$ let $t(z)$ denote the geometric length of the orbit segment between $z$ and $S(z)$. Let

$$ (3) \quad B_a := \{z \in P_Q : \phi_t(z) \in B(\partial P_Q, a) \text{ for some } t \in [0, t(z)]\} $$

and for $T > 0$ let

$$ G_a^T := \{z \in P_Q : \phi_t(z) \notin B_a \text{ for } 0 \le t \le T\}. $$

Let $T_n := n \cdot \text{diam}(Q)$.

**Proposition 9.** For each polygon $Q$, $a > 0$, $n \ge 1$, and $z \in G_a^{T_n}$ we have

$$ B(z, a/(2 + T_n)) \subset C_n(z) $$

**Proof.** There is a strictly positive constant $k_2$ depending only on $Q$ such that any orbit segment $\phi_{[0,T]}(z)$ makes at most $k_2T$ collisions, thus (4)

$$ P_Q \setminus G_a^T = \{z \in P_Q : \phi_t(z) \in B_a \text{ for some } 0 \le t \le T\} \subset \bigcup_{0 \le j \le k_2 T} S^{-j} B_a. $$
<figure><img src="image_4.png" /><figcaption>FIGURE 3. Three examples of $z \in B_a$.</figcaption></figure>

Suppose $z \in G_a^T$. For calculational convenience we consider a flow-based version of $n$-cells, let $C_T(z) \subset P_Q$ be the maximal neighborhood of $z$ (in $P_Q$) such that $\phi_T|_{C_T}$ is continuous. A billiard orbit segment of geometric length $\mathrm{diam}(Q)$ must make at least one bounce. It follows that a billiard orbit segment of geometric length $T$ must make at least $T/\mathrm{diam}(Q)$ bounces, and thus

$$C_T(z) \subset C_{[T/\mathrm{diam}(Q)]}(z).$$

Note that $C_{[k_2T]}(z) \subset C_T(z)$, but we will not use this.

Our goal is to estimate the largest $\delta > 0$ such that $B(z, \delta) \subset C_T(z)$; $\delta$ is always assumed small enough so that this inclusion holds.

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

We call a subset of vectors in $B(z, \delta)$ with the same base point in $B(z, \delta)$ a vertical segment. Now we will consider the action of $\phi_T$ on vertical segments. Let $\ell \subset B(z, \delta)$ be the vertical segment with lower endpoint $(s, \theta_0)$ and upper endpoint $(s, \theta_1)$ where $2\delta = \theta_1 - \theta_0$. For $r \in [0, 1]$ let $\theta_r := (\theta_1 - \theta_0)r + \theta_0$, so $\ell = \{z_r := (s, \theta_r) : 0 \le r \le 1\}$. In the unfolding of the orbit segment $z$ to $\phi_T(z)$, the image $\phi_T(\ell) =: \{z_{r,T} := (\bar{x}_{r,T}, \theta_r) : 0 \le r \le 1\}$ is an arc of angle $\delta r$ of a circle of radius $T$ (Figure 4), thus in the unfolding we trivially have the following bound $||\bar{x}_{0,T} - \bar{x}_{r,T}|| < T\delta r$ for each $0 \le r \le 1$. On the other hand $\theta_r - \theta_0 = \delta r$. Thus in the phase space $P_Q$ we have $\rho(z_{0,T}, z_{r,T}) \le T\delta r + \delta r = (T+1)\delta r$ for each $0 \le r \le 1$.

Now we will combine the above horizontal and vertical estimates. For $z_1 = (s_1, \theta_1)$, $z_2 = (s_2, \theta_2) \in B(z, \delta)$ we consider $z_3 = (s_1, \theta_2)$. The estimates of the previous two paragraphs and the triangle inequality yield

$$ \begin{aligned} \rho(\phi_T(z_1), \phi_T(z_2)) &\le \rho(\phi_T(z_1), \phi_T(z_3)) + \rho(\phi_T(z_3), \phi_T(z_2)) \\ &\le \delta + (T+1)\delta = (2+T)\delta. \end{aligned} $$

We have arrived at the punch line of the geometric estimate. If $z \in G_a^T$, we have $\rho(\phi_t(z), \partial P) \ge a$ for all $0 \le t \le T$. Thus if $\delta$ satisfies $\delta(2 + T) < a$ or equivalently $\delta < a/(2 + T)$ then all points in $B(z, \delta)$ belong to $C_T(z)$ and thus we have $B(z, a/(2 + T)) \subset C_{[T/\mathrm{diam}(Q)]}(z)$.
<figure><img src="image_5.png" /><figcaption>FIGURE 4. Unfolding a vertical segment</figcaption></figure>

Applying this to $T_n := n \cdot \text{diam}(Q)$ yields the desired result. □

**Proof of Theorems 3 and 5.** The first step of the proof is to estimate the quantity $\mu(B_a)$. If $Q$ is convex we have

$$ (5) \qquad B_a \subset B(\partial P_Q, a) \cup S^{-1}B(\partial P_Q, a) $$

and thus there is a constant $k_1 > 0$ such that

$$ (6) \qquad \mu(B_a) \le 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, \theta) \in B_a \setminus (B(\partial P_Q, a) \cup S^{-1}B(\partial 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 non-convex vertex$^{(c)}$ to a side not containing this vertex (dotted segment in the figure). Among the points closest to the segment $\phi_{[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 $\theta'$ so that $z' = (s, \theta') \in 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 $\phi_{[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 $|\theta - \theta'| < \arcsin \frac{a}{d} < \frac{a}{d}$, and thus $z \in B(S, \frac{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) \qquad B_a \subset B(\partial P_Q, a) \cup B(S, a/d) \cup S^{-1}B(\partial 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 $\mu(B_a) \le k_1 a$.

<footnote>(c) i.e., the segment connecting two close enough points on the boundary of $Q$ on opposite sides of the vertex lies outside $Q$.</footnote>
This inequality combined with (4) and the fact that $\mu$ is S-invariant
implies we can choose a $k_3$ such that

$$
(8) \quad \mu(P_Q \setminus G_a^T) \le (k_2 T + 1)\mu(B_a) = (k_2 T + 1)k_1 a \le k_3 Ta.
$$

Now we have all the estimates necessary to make the $G_\delta$ argument.
Let $K := 2 + \operatorname{diam}(Q)$. For Theorem 3 let $a_n := \frac{K}{n^2 f(n)}$ while for
Theorem 5 let $a_n := \frac{K}{nf(n)}$ and consider the corresponding sets $B_{a_n}$.
Applying Proposition 9 to $z \in G_{a_n}^{T_n}$ yields $B(z, 1/(n^3 f(n))) \subset C_n(z)$,
resp. $B(z, 1/(n^2 f(n))) \subset C_n(z)$.

For both choices of $(a_n)$ Equation (8) yields $\mu(G_{a_n}^{T_n}) \to 1$ as $n \to \infty$.
Let

$$
G := \bigcap_{n_0 \ge 1} \bigcup_{n \ge n_0} G_{a_n}^{T_n}.
$$

Notice that $G$ is a dense $G_\delta$-set of full measure. If $z \in G$ then there
is an infinite sequence $n_i$ such that $z \in G_{a_{n_i}, T_{n_i}}$ for all $i$ which finishes
the proof of Theorem 5. To prove Theorem 3 we notice that $\mu(G_{a_n}^{T_n})$ is
summable and we apply the Borel-Cantelli lemma to the sets $G_{a_n}^{T_n}$ to
conclude that for a.e. $z \in G$ there is an $n_0$ such that for all $n \ge n_0$ we
have $z \in G_{a_n}^{T_n}$. $\square$

**Proof of Corollary 4.** Any notation in $\Sigma_Q$ which corresponds to a notation in $Q$ will be denoted with a bar, for example $\bar{\mu}$ denote the lift of the invariant measure $\mu$ to $\Sigma$ and $\bar{z} \in \Sigma_Q$ denote the code of $z \in P_Q$. For a point $z$ in the set $G$ from Theorem 3, the Theorem yields an $n_0$ such that $\bar{\mu}(\bar{z}_{[0,n-1]}) = \mu(C_n(z)) \ge \frac{\text{const}}{n^6 f(n)^2}$ for all $n \ge n_0$. Let $\bar{z}[0,n-1]$ denote the cylinder set corresponding to the word $\bar{z}_{0,n-1}$, here const is the normalizing constant of the measure $\mu$. Let $G_N := \{z \in G : n_0(z) \le N\}$. Since $G = \cup_{N \ge 1} G_N$ is of full measure for each $\varepsilon > 0$ we can choose $N$ such that $\mu(G_N) \ge 1 - \varepsilon$, thus its lift satisfies $\bar{\mu}(\bar{G}_N) > 1 - \varepsilon$. Since distinct cylinder sets are disjoint we obtain a cover of $\bar{G}_N$ by cylinders of measure at least $\frac{\text{const}}{n^6 f(n)^2}$, so there are at most $\frac{(1-\varepsilon)n^6 f(n)^2}{\text{const}}$ such cylinders. For each $z$ the cylinder set $\bar{z}_{[0,n-1]}$ is just the ball $B(\bar{z}, n, 0)$. Any cover by cylinders (0 balls) is a cover by $\varepsilon$ balls, thus the metric complexity can only be smaller than our estimate. $\square$

# 6. 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, $\nu$ an $S$-invariant measure, and $f: \mathbb{N} \to \mathbb{N}$ be a monotonically increasing function such that $\frac{1}{nf(n)}$
is summable. There exists a non-increasing sequence $(a_n)$ satisfying $\nu(B_{a_n}) < 1/n^2 f(n)$. For any such sequence there exists a set $G$ of full $\nu$-measure which is a dense $G_\delta$-subset of $\text{supp}(\nu)$ with the property that for every $z \in G$ there exists $n_0 \ge 0$ such that for all $n \ge n_0$ we have

$$B\left(z, \frac{a_n}{2 + n \cdot \text{diam}(Q)}\right) \subset C_n(z).$$

For the version of Theorem 5 we get:

**Theorem 11.** Let $Q$ be a polygon, $\nu$ an $S$-invariant measure, and $f: \mathbb{N} \to \mathbb{N}$ be a monotonically increasing unbounded function. There is a non-increasing sequence $(a_n)$ which satisfies $\nu(B_{a_n}) < K_0/nf(n)$. For any such sequence there is a set $G$ of full $\nu$-measure which is a dense $G_\delta$-subset of $\text{supp}(\nu)$ with the property that for every $z \in G$ there exists an infinite strictly increasing sequence $n_i$ such that

$$B\left(z, \frac{a_{n_i}}{2 + n_i \cdot \text{diam}(Q)}\right) \subset 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

$$(9) \qquad \nu(B_a) \le 2\nu(B(\partial Q, a)) + \nu(B(S, a)).$$

By definition $\nu$ is supported on the set of non-singular points, in particular $\nu(\partial P_Q) = 0$ and $\nu(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 \to 0$.

The sequences $(a_n)$ are implicitly defined, they differ from those in Theorems 3 and 5, but by definition the estimates of measures of the sets are the same as for $\mu$. Thus for both Theorems we have $\nu(P_Q \setminus G_n^{T_n}) \to 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)$. $\square$

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 \cdot \text{diam}(Q))$.

If there exists $a > 0$ such that $\nu(\{z \in P_Q : d(z, \partial P_Q) < a\}) = 0$ for sufficiently small $a$, then Theorem 10 tells us that for almost every $z$ there exists $n_0 \ge 0$ such that for all $n \ge n_0$ we have

$$B\left(z, \frac{a}{2 + n \cdot \text{diam}(Q)}\right) \subset 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 $\nu(B(\partial P_Q, a)) \le a^r$ for some $r > 0$ and all sufficiently small $a$. In this case, the conclusion of Theorem 10 reads for $\nu$-a.e. $z$ there exists $n_0$ such that for all $n \ge n_0$ we have

$$B\left(z, \frac{1}{\sqrt[r]{n^2 f(n)}(2 + n \cdot \text{diam}(Q))}\right) \subset C_n(z)$$

while the conclusion of Theorem 11 reads for $\nu$-a.e. $z$ there exists an infinite strictly increasing sequence $n_i$ such that

$$B\left(z, \frac{1}{\sqrt[r]{n_i f(n_i)}(2n_i + 1)}\right) \subset 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 $\mu$ denotes the Liouville measure we obtain $\mu(B_{a_n}) \le Ca_n^{2m-3}$ and $\mu(P_Q \setminus G_n) \le nCa_n^{2m-3}$. The estimate in Proposition 9 on linear separation does not change, thus for a version of Theorem 3 we choose $a_n = \frac{K}{\sqrt[r]{n^2 f(n)}}$ while for a version of Theorem 5 we use $a_n = \frac{K}{\sqrt[r]{nf(n)}}$ which yields the following two results.

**Theorem 12.** Let $Q$ be a polyhedron in $\mathbb{R}^m$ and $f: \mathbb{N} \to \mathbb{N}$ be a monotonically increasing function such that $\frac{1}{nf(n)}$ is summable. Then there is a dense $G_\delta$-set $G$ of full $\mu$-measure such that for every $z \in G$ there exists $n_0 \ge 0$ such that for all $n \ge n_0$ we have

$$B\left(z, \frac{1}{n^{2m-3}\sqrt[r]{n^2 f(n)}}\right) \subset C_n(z).$$

**Theorem 13.** Let $Q$ be a polyhedron in $\mathbb{R}^m$ and $f: \mathbb{N} \to \mathbb{N}$ be a monotonically increasing function. Then there is a dense $G_\delta$-set $G$ of full $\mu$-measure such that for every $z \in G$ there exists an infinite strictly increasing sequence $n_i$ such that

$$B\left(z, \frac{1}{n_i^{2m-3}\sqrt[r]{n_i f(n_i)}}\right) \subset C_{n_i}(z).$$
REFERENCES

[Be] N. Bedaride, *Billiard complexity in rational polyhedra*, Regul. Chaotic Dyn. 8 (2003) 97–104.

[BoKeMar] C. Boldrighini, M. Keane and F. Marchetti, *Billiards in polygons*, Ann. Probab. 6 (1978) 532–540.

[CaHuTr] J. Cassaigne, P. Hubert and S. Troubetzkoy, *Complexity and growth for polygonal billiards*, Ann. I. Fourier 52 (2002) 835–847.

[Fe] S. Ferenczi, *Measure-theoretic complexity of ergodic systems*, Israel J. Math., 100 (1997) 189–207.

[GaKrTr] G. Galperin, T. Krueger and S. Troubetzkoy, *Local instability of orbits in polygonal and polyhedral billiards*, Commun. Math. Phys. 169 (1995) 463–473.

[GuHa1] E. Gutkin and N. Haydn, *Topological entropy of generalized polygon exchanges*, Bull. Amer. Math. Soc. 32 (1995) 50–56.

[GuHa2] E. Gutkin and N. Haydn, *Topological entropy of polygon exchange transformations and polygonal billiards*, Ergod. Theory Dyn. Syst. 17 (1997) 849–867.

[GuRa] E. Gutkin and M. Rams, *Growth rates for geometric complexities and counting functions in polygonal billiards*, Ergod. Theory and Dyn. Syst. 29 (2009) 1163–1183.

[Ho] W.P. Hooper, *Lower bounds on growth rates of periodic billiard trajectories in some irrational polygons*, J. Mod. Dyn. 1 (2007) 649–663.

[Ka1] A. Katok, *The growth rate for the number of singular and periodic orbits for a polygonal billiard*, Commun. Math. Phys. 111 (1987) 151–160.

[Ka2] A. Katok, *Billiard table as a playground for a mathematician*. In V. Prasolov & Y. Ilyashenko (Eds.), Surveys in Modern Mathematics (London Mathematical Society Lecture Note Series, pp. 216-242). Cambridge University Press, 2005.

[Ka3] A. Katok, *Five most resistant problems in dynamics*. https://www.impan.pl/biuletyn/arch/5problems.pdf.

[KaTh] A. Katok and J.-P. Thouvenot, *Slow entropy type invariants and smooth realization of commuting measure-preserving transformations*, Ann. Inst. H. Poincaré Prob. Stat., 33 (1997) 323–338.

[KuPeVa] P. Kürka, V. Penné and S. Vaienti, *Dynamically defined recurrence dimension*, Discrete Contin. Dyn. Syst. 8 (2002) 137–146.

[Mar1] J.-P. Marco, *Polynomial entropies and integrable Hamiltonian systems*, Regul. Chaotic Dyn. 18 (2013) 623–655.

[Mar2] J.-P. Marco, *Entropy of billiard maps and a dynamical version of the Birkhoff conjecture*, J. Geom. Phy. 124 (2018) 413–420.

[Mas1] H. Masur, *Lower bounds for the number of saddle connections and closed trajectories of a quadratic differential*, Holomorphic functions and moduli, Vol. I (Berkeley, CA, 1986), 215–228, Math. Sci. Res. Inst. Publ., 10, Springer, New York, 1988.

[Mas2] H. Masur, *The growth rate of trajectories of a quadratic differential*, Ergod. Theory Dyn. Syst. 10 (1990) 151–176.

[Sc1] D. Scheglov, *Complexity growth of a typical triangular billiard is weakly exponential*, J. Anal. Math. 142 (2020) 105–124.

[Sc2] D. Scheglov, *Growth of periodic orbits and generalized diagonals for typical triangular billiards*, J. Mod. Dyn. 7 (2013) 31–44.

[Sc3] D. Scheglov, *Complexity lower bound for typical right triangular billiards*, arXiv:2207.00910

[Si1] Ya. G. Sinai, *Introduction to ergodic theory*, Mathematical Notes, 18, Princeton University Press, Princeton, N.J., 1976. 144 pp.

[Si2] Ya. G. Sinai, *Topics in ergodic theory*, Princeton Mathematical Series, 44, Princeton University Press, Princeton, NJ, 1994. 218 pp.

[Tr] S. Troubetzkoy, *Complexity lower bounds for polygonal billiards*, Chaos 8 (1998) 242–244.

WROCLAW UNIVERSITY OF TECHNOLOGY, FACULTY OF COMMUNICATION AND INFORMATION TECHNOLOGY, UL. JANISZEWSKIEGO 11/17, 50-372 WROCLAW, POLAND

Email address: tyll.krueger@pwr.edu.pl

AIX MARSEILLE UNIV, CNRS, I2M, MARSEILLE, FRANCE

Email address: arnaldo.nogueira@univ-amu.fr

AIX MARSEILLE UNIV, CNRS, I2M, MARSEILLE, FRANCE

Email address: serge.troubetzkoy@univ-amu.fr