GROWTH RATES FOR GEOMETRIC COMPLEXITIES
AND COUNTING FUNCTIONS IN POLYGONAL
BILLIARDS
EUGENE GUTKIN AND MICHAL RAMS
Abstract. We introduce a new method for estimating the growth
of various quantities arising in dynamical systems. We apply our
method to polygonal billiards on surfaces of constant curvature.
For instance, we obtain power bounds of degree two plus epsilon
for billiard orbits between almost all pairs of points in a planar
polygon.
Introduction and overview
Complexity of a dynamical system is measured with respect to a
coding of its orbits. The coding, in turn, is determined by partitioning
the phase space of the system into elementary pieces. For dynami-
cal systems with singularities, such as polygonal billiards, connected
components in the complement to the singular set yield a natural par-
tition. Convexity of its atoms with respect to the geodesic structure in
the phase space imposed by geometric optics, is crucial in the study of
billiard complexity [7].
In the present study, as well as in [7], P is a geodesic polygon in
a surface of constant curvature. Let, for concreteness, P be a planar
polygon. We denote by fP (n) the number of words of length n gener-
ated by coding billiard orbits by visited domains of regularity. When
P is simply connected, this coincides with the coding by sides in P . It
is known that fP (n) is subexponential in n [3, 6], and for general P
no better bound is known. If P is a rational polygon (i. e., its angles
are commensurable with π [4]), fP (n) = O(n
3) [1, 7]. The current
conjecture is that for any planar polygon fP (n) = O(n
d) [5].
In order to advance the understanding of billiard complexity, we
introduce the notion of partial complexities. Let Ψ be the phase space,
and let P be the defining partition. Iterating the dynamics we obtain
an increasing tower Pn of partitions; the full complexity is f(n) =
Date: October 31, 2018.
Key words and phrases. Geodesic polygon, billiard map, billiard flow, complex-
ity, counting functions, unfolding of orbits, covering space, exponential map.
http://arxiv.org/abs/0704.1975v1
2 EUGENE GUTKIN AND MICHAL RAMS
|Pn|. If R ⊂ Φ, let Pn(R) be the induced tower of its partitions. The
partial complexity based on R is fR(n) = |Pn(R)|. Particular partial
complexities have been studied earlier. For instance, in [8] we obtained
polynomial bounds on direction complexity, which is one of the partial
complexities investigated here.
In this work we introduce a new general approach to estimating par-
tial complexities. The setting is as follows. There is a family of subsets
Rθ foliating the phase space. Let fθ(n) be the partial complexity with
base Rθ. Let gθ(n) be the counting function for singular billiard or-
bits starting from Rθ. Under appropriate assumptions, fθ(n) and gθ(n)
have the same growth, as n → ∞. See section 4.
Let θ ∈ Θ, the parameter space. Suppose that we bound the average
counting function G(n) =
gθ(n). Tchebysheff inequality and the
zero-one law yield bounds for individual gθ(n) valid for almost all θ ∈ Θ.
See section 2. Combined with preceding remarks, these yield estimates
on partial complexities for almost all values of the parameter.
This is the general scheme for our approach to partial complexities.
This work implements this scheme for polygonal billiards. We will now
describe the contents of the paper in more detail.
In section 1 we investigate counting functions and their averages. We
establish the relevant framework in sufficient generality, with the view
towards a broad range of geometric-dynamic applications. The main
results are Propositions 1 and 2 respectively. These yield geometric
formulas for averages of counting functions which are valid under mild
assumptions of transversality type.
Section 2 is analytic, and also quite general. The setting is as follows.
There is a family of positive functions, gθ(p), of positive argument
(p ∈ N and p ∈ R+ in the discrete and continuous cases respectively),
depending on parameter θ ∈ Θ. Set G(p) =
gθ(p)dθ. From upper
bounds on G(p) we derive estimates on individual gθ(p); they are valid
for almost all θ. Precise formulations depend on the details of the
situation. See Propositions 3 and 4.
Section 3 sets the stage for applications to billiard dynamics. Our
billiard table is a geodesic polygon, P , in a simply connected surface
of constant curvature. There are two versions of billiard dynamics:
the billiard flow and the billiard map. In our discussion of partial
complexities, it is convenient to treat them separately. Accordingly,
section 3 consists of several subsections; each subsection deals with a
particular partial complexity for a particular kind of billiard dynamics.
We use two geometric parameters for partial complexities: the direc-
tion and the position. The direction complexity tells us how the set of
COMPLEXITY, ETC 3
phase points starting in the same direction splits after bouncing off of
the sides of P . The direction complexity is defined for planar polygons.
The position complexity tells us about the splitting of beams of billiard
orbits emanating from a point of P . It is defined in all cases.
In each of the subsections of section 3 we define a counting function
and check the assumptions of section 1; then we evaluate the integral
over the parameter space, i. e., we compute the average counting func-
tions. It turns out that they have geometric meanings. Here is a sample
of results from section 3. Let GP (l) be the average position counting
function for the billiard flow in a geodesic polygon P . For planar poly-
gons we have GP (l) = c0(P )l
2. See Corollary 2 in section 3.2. For
polygons in S2 we have GP (l) = c+(P )l + c
+(P )f(l) where f is a uni-
versal periodic function. See Corollary 3 in section 3.4. For polygons
in H2 we have GP (l) = c−(P ) cosh l. See Corollary 4 in section 3.5.
The coefficients in these formulas depend on how many corners P has
and on the number of obstacles in its interior.
Section 4, again, is quite general. In this section we obtain relation-
ships between partial complexities with one-dimensional base sets and
counting functions. The main result of this section is Proposition 5.
It says that if the bases are one-dimensional, then the difference be-
tween the partial complexity and the counting function is bounded, as
time goes to infinity. Other assumptions on the base have to do with
convexity in the phase space. The framework of this section is that of
piecewise convex transformations [7].
In section 5 we specialize again to polygonal billiards. Combining the
material of preceding sections, we obtain bounds on the position and
direction complexities for the billard flow and the billiard map. Here is
a sample of our results. Let P be a euclidean polygon. Let θ ∈ S1 (resp.
z ∈ P ) be any direction (resp. position). Let fdθ(n) (resp. hz(l)) be
the direction complexity for the billiard map (resp. position complexity
for the billiard flow). Then for almost all directions θ (resp. for almost
all positions z) we have fdθ(n) = O(n
1+ε) (resp. hz(l) = O(l
2+ε)),
where ε > 0 is arbitrary. See Corollary 6 and Corollary 8. Let now P
be a spherical polygon, and let hz(l) be the position complexity for the
billiard flow in P . Then for almost every z ∈ P there is a C = C(z)
and arbitrarily large l such that hz(l) ≤ Cl. See Corollary 10. For
any ε > 0 and almost every z ∈ P we have hz(l) = O(l
1+ε). See
Corollary 11.
In the study of polygonal billiards the device of unfolding billiard
orbits is indispensable [4]. If P ⊂ M , and β is a billiard orbit in P ,
its unfolding is a geodesic in M . Several arguments in section 3 use
4 EUGENE GUTKIN AND MICHAL RAMS
the technique of lifting billiard orbits to the universal covering space
of P .1 This notion was not written up in the billiard literature. In our
Appendix section 6 we present the relevant definitions and propositions.
Proposition 6 puts forward the main property of the universal covering
space of a geodesic polygon. It relates the unfoldings and the liftings of
billiard orbits. The proofs in section 3 use Corollary 13 of Proposition 6,
which deals with the pullbacks of lebesgue measures under unfoldings.
In order to put our results into perspective, we will now briefly sur-
vey the literature on billiard complexities. The subexponential growth
of (full) billiard complexity for arbitrary euclidean polygons is estab-
lished in [3] and [6]. Both proofs are indirect, in that they do not yield
explicit subexponential bounds. On the other hand, for rational eu-
clidean polygons the complexity is cubic. This is contained in [1] for
convex and in [7] for all rational polygons. The arguments in [1] and
[7] rely on a theorem in [11]; it says that the number of billiard orbits
between any pair of corners in a rational polygon grows quadratically
in length. From our viewpoint, this is a statement about the position
counting functions gz(l). It says that gz(l) = O(l
2) if P ⊂ R2 is ra-
tional and z ∈ P is a corner. By comparison, our Corollary 8 and
Proposition 5 yield that gz(l) = O(l
2+ε) for any ε > 0 and almost all
z ∈ P where P ⊂ R2 is an arbitrary polygon. The directional com-
plexity fdθ(n) has been studied in [8] and [9]. The work [9] concerns
the directional complexity for the billiard in a rational, planar polygon
P . Assume that P is convex. Then [9] derives an explicit formula for
fdθ(n), valid for minimal directions θ. (The set of nonminimal direc-
tions is countable.) By this formula, fdθ(n) = O(n). On the other
hand, [8] shows that fdθ(n) = O(n
d) for any P ⊂ R2 and an arbitrary
θ. The degree d in the bound does not depend on θ. Our Corollary 6
estimates the complexity fdθ(n) for an arbitrary polygon P ⊂ R
2. It
says that fdθ(n) = O(n
1+ε) for any ε > 0 and almost all directions θ.
It is plausible that the bounds like Corollary 8, Corollary 6, etc hold
for any point z ∈ P , any direction θ ∈ S1, etc.
1. Averages of counting functions
In this section we introduce the framework of counting functions
in differentiable dynamics. We will apply it to the billiard dynamics
later on. Our phase spaces are “manifolds”. By this we will mean
compact manifolds with boundaries, corners, and singular points, in
general. Our setting involves i) a foliation of the phase space by closed
1Not to be confused with the concept of universal covering space in topology.
COMPLEXITY, ETC 5
submanifolds that are fibers for a projection onto a manifold of smaller
dimension; ii) a submanifold in the phase space, transversal to the
fibers; iii) a weight function on the product of the phase space and
the time. See the details below. The dynamics in question may be
discrete or continuous. We will expose the two cases separately. The
two subsections that follow are parallel, and the treatments differ in
technical details.
1.1. Discrete dynamics. Let T : X → X, T−1 : X → X be piecewise
diffeomorphisms with the following data.
1. There is a fibration η : X → Θ whose base is a compact manifold
and whose fibers Rθ = η
−1(θ) are compact submanifolds, such that
dim(Rθ) = dim(X)− dim(Θ). We will use the notation X = ∪θ∈ΘRθ.
2. There is a closed submanifold, Y ⊂ X , dim(Y ) = dim(Θ), such that
for k ∈ −N2 the manifolds T k(Y ) are transversal to the fibers Rθ.
3. There is a weight function, i. e., a continuous, non-negative function
w(x, t) on X × N. The function w may depend only on time, e. g.,
w = χn, the indicator function of [0, n− 1].
Remark 1. Condition 2 may be weakened, as follows.
2′. There is a closed submanifold, Y ⊂ X , and a set Θex ⊂ Θ of measure
zero such that for k ∈ −N and θ ∈ Θ\Θex the manifolds T
k(Y ) and Rθ
are transversal. All of our results remain valid if we replace condition 2
by the weaker condition 2′. However, in our applications to polygonal
billards, condition 2 may not hold only for polygons in surfaces of
positive curvature. See section 3.4. To simplify the exposition, we will
assume in what follows that Θex = ∅.
In view of condition 2, Γ(θ) = {(x, k) : x ∈ Rθ, k ∈ N, T
k(x) ∈ Y } is
a countable (at most) set. The sets Γk(θ) = {(x, k) : x ∈ Rθ, T
k(x) ∈
Y } are finite for all k ∈ N, and Γ(θ) = ∪Γk(θ).
We define the weighted counting function by
(1) g(θ;w) =
(x,k)∈Γ(θ)
w(x, k).
The pure counting function gn(θ) corresponds to the weight w = χn.
We have
(2) gn(θ) =
|Γk(θ)|.
2By convention, N = 0, 1, . . . .
6 EUGENE GUTKIN AND MICHAL RAMS
Proposition 1. Let dθ, dy be finite, lebesgue-class measures on Θ, Y
respectively. Then for k ∈ N there are functions rk(·) ≥ 0 on Y ,
determined by the data 1) and 2) alone, such that
g(θ;w)dθ =
w(T−k · y, k)rk(y)
Proof. For any k ∈ N set fk = η ◦ T
−k : Y → Θ. By conditions 1 and
2, fk is a local diffeomorphism. Therefore f
k (dθ) = rk(y) dy.
It suffices to establish equation (3) for the special case w(x, i) = 0 if
i 6= k. A point x ∈ X contributes to the integral in the left hand side
of equation (3) iff T k ·x ∈ Y , or equivalently, η(x) = fk(y), y ∈ Y . The
claim follows by a straightforward change of variables.
1.2. Continuous dynamics. Let bt : Ψ → Ψ be a flow of piecewise
diffeomorphisms on a phase space Ψ with the following data.
1. There is a fibration q : Ψ → Z with a compact base and fibers
q−1(z) = Rz ⊂ Ψ, transversal to the flow. We will use the notation
Ψ = ∪z∈ZRz.
2. There is a closed submanifold, M ⊂ Ψ, dim(M) = dim(Z) − 1,
transversal to the flow, and such that N = ∪t∈R
bt · M is transversal
to the fibers Rz.
3. There is a weight function, i. e., a continuous, non-negative function
w(x, t) on Ψ × R+. In a special case, w depends only on time, e. g.,
w = χl, the indicator function of [0, l].
In view of condition 2, G(z) = {(x, t) : x ∈ Rz, 0 ≤ t, b
t(x) ∈ M} is
a countable (at most) set. The sets Gl(z) = {(x, t) : x ∈ Rz, 0 ≤ t ≤
l, bt(x) ∈ M} are finite for all l ∈ R+, and G(z) = ∪Gl(z).
We define the weighted counting function by
(4) g(z;w) =
(x,t)∈G(z)
w(x, t).
The pure counting function gl(z) corresponds to the weight w = χl.
We have
(5) gl(z) = |Gl(z)|.
Proposition 2. Let dz, dm be finite, lebesgue-class measures on Z,M
respectively; let dt be the lebesgue measure on R. Then there exist a
3Our results remain valid if the set of parameters Z
⊂ Z where the transversal-
ity fails has measure zero. See Remark 1. In what follows, by condition 2′ we will
mean the weakened condition 2 either in the setting of section 1.2 or section 1.1.
COMPLEXITY, ETC 7
positive function r(·) on M × R+, determined by the data 1) and 2),
and such that
g(z;w)dz =
w(b−t ·m, t)r(m, t)dmdt
Proof. We define the mapping f : M × R+ → Z by f = q ◦ b
By conditions 1 and 2, f has full rank almost everywhere. The pull-
back by f of dz is absolutely continuous with respect to dmdt, hence
f ∗(dz) = r(m, t)dmdt.
For 0 < l set wl(x, t) = w(x, t)χl(t), and let gl(z;w) be the corre-
sponding counting function. Set Il(w) =
gl(z;w)dz. A point, x ∈ Ψ,
contributes to Il(w) iff x ∈ ϕ(M× [0, l]). Under the change of variables
dz = d(q ◦ ϕ(m, t)) = r(m, t)dmdt, we have
Il(w) =
M×[0,l]
w(b−t ·m, t)r(m, t)dmdt.
In the limit l → ∞, we obtain the claim.
1.3. Special cases. We will discuss a few special cases of Proposition 1
and Proposition 2. First, the discrete version. The function gn(θ)
counts the number of visits in Y of points x ∈ Rθ during the first n
steps of their journey. Set ρk =
rk(y)dy, and Rn =
k=0 ρk. Then
ρk is the volume of Yk = T
−k(Y ) with respect to the measure η∗(dθ).
Proposition 1 yields
gn(θ)dθ = Rn.
In the continuous case the function gl(z) counts the number of visits
in M of orbits bt · x, x ∈ Rz, during the period 0 ≤ t ≤ l. Let R(l) be
the volume of the manifold Nl ⊂ Ψ with respect to the measure q
∗(dz).
Proposition 2 yields
gl(z)dz = R(l).
2. Bounds on counting functions
In this section we analyze the setting of section 1 from the measure
theoretic viewpoint. This allows us to obtain pointwise upper bounds
on counting functions in a broad spectrum of situations.
Let X, µ be a finite measure space. Let f(x; t) (for t ∈ R+) be a
family of nonnegative L1 functions on X . Set
(9) F (t) =
f(x; t)dµ(x).
8 EUGENE GUTKIN AND MICHAL RAMS
Lemma 1. For almost every x ∈ X there exists C = C(x) > 0 such
that for arbitrarily large n ∈ N there is t ≥ n satisfying f(x, t) < CF (t).
Proof. For 0 < C and n ∈ N let
Bn(C) = {x ∈ X : CF (t) < f(x; t) ∀t > n},
and set
B(C) =
Bn(C).
Integrating the inequality above, we obtain µ(Bn(C)) ≤ C
−1 for any n.
Thus µ(B(C)) ≤ C−1, and hence µ(∩C∈R+B(C)) = 0. But ∩C∈R+B(C) ⊂
X is the complement of the set of points x ∈ X satisfying the hypoth-
esis of the lemma.
Let the setting be as in Lemma 1. In addition, we suppose that
i) the functions f(x; t) are nondecreasing in t and ii) F (t) → ∞.
Lemma 2. Let ε > 0 be arbitrary. Then for almost every x ∈ X there
exists T = T (x, ε) > 0 such that for all t > T we have
(10) f(x; t) ≤ F (t)(1 + log(1 + F (t)))1+ε.
Proof. Denote by f(x; t−) (resp. F (t−)) the limits of f(x; s) (resp.
F (s)), as s → t from the left. For n ∈ N set tn = inf{t : F (t) ≥ 2
Then F (t(n+1)
−) ≤ 2F (tn). Let An ⊂ X be the set of points satisfying
the inequality
(11) f(x; t−n ) ≤
F (tn
−)(1 + log(1 +
F (tn
−)))1+ǫ.
It suffices to prove that the set
Ak has full measure. Indeed,
for x ∈ An and t ∈ [tn, tn+1) we have
f(x; t) ≤ f(x; t−n+1) ≤
F (tn+1
−)(1 + log(1 +
F (tn+1
−))1+ε
≤ F (tn)(1 + log(1 + F (tn)))
1+ε ≤ F (t)(1 + log(1 + F (t)))1+ε.
Thus, the points x ∈
Ak have the property equation (10).
If Bn ⊂ X is any sequence of sets, we set lim supn→∞Bn =
Let Bn be the complement of An inX . Then lim supn→∞Bn is the com-
plement of
Ak. It remains to prove that µ(lim supn→∞Bn) =
By Tchebysheff inequality, we have
(12) µ(Bn) ≤ 2(1 + log(1 +
F (tn
−)))−(1+ε).
COMPLEXITY, ETC 9
Set µn = µ(Bn). Suppose first that F is a continuous function. Then
F (tn
−) = F (tn) = 2
n. By equation (12)
µn ≤ 2(1 + log(1 + 2
n))−(1+ε),
hence the series
µn converges. Since
µ(lim sup
Bn) ≤
for any n0 ∈ N, the claim follows.
In general, F need not be continuous. It is thus possible that tn =
tn+1 for some n ∈ N, implying Bn = Bn+1. From the series
we drop the terms µn such that Bn = Bn−1. By equation (12), the
remaining terms satisfy
µn ≤ 2(1 + log(1 + 2
n−2))−(1+ε).
Now the preceding argument applies.
In sections 3, 5 we will apply these results in the billiard setting. In
section 3 we will estimate the integrals equation (9), hence the bounds
provided by Lemmas 1, 2 will be more specific. The propositions below
anticipate these applications.
Proposition 3. Let the setting and the assumptions be as in Lemma
2. Let 0 < ε be arbitrary.
1. Let F (t) = O(tp) for 0 < p. Then for almost every x ∈ X we have
f(x; t) = O(tp+ε).
2. Let F (t) = O(eat) for 0 < a. Then for almost every x ∈ X we have
f(x; t) = O(e(a+ε)t).
Proof. The first claim is immediate from Lemma 2 and (log t)1+ε =
o(tε). The second claim follows the same way from t1+ε = o(eεt).
For applications to the billiard map we need a counterpart of Proposi-
tion 3 for integer-valued time. We state it below. Its proof is analogous
to the proof of Proposition 3. Moreover, the discrete time case may be
formally reduced to the continuous time case. We leave details to the
reader.
Let X, µ be a finite measure space. Let f(x;n), n ∈ N be a sequence
of nonnegative L1 functions on X such that for every x ∈ X the nu-
merical sequence f(x;n) is nondecreasing. Set F (n) =
f(x;n)dµ.
Proposition 4. Let 0 < ε be arbitrary. Then the following claims
hold.
10 EUGENE GUTKIN AND MICHAL RAMS
1. Let F (n) = O(np) for 0 < p. Then for almost every x ∈ X we have
f(x;n) = O(np+ε).
2. Let F (n) = O(ean) for 0 < a. Then for almost every x ∈ X we have
f(x;n) = O(e(a+ε)n).
Remark 2. All of the bounds f(·) = O(·) in preceding propositions
are equivalent to the formally stronger bounds f(·) = o(·).
3. Counting functions for polygonal billiard
We will now apply the preceding material to the billiard dynamics.
Our billiard table will be a geodesic polygon either in the euclidean
plane R2, or the round sphere S2, or the hyperbolic plane H2. We refer
to [4], [7], and section 6 for the background.
3.1. Direction counting functions for billiard maps in euclidean
polygons. Let P ⊂ R2 be a euclidean polygon, and let T : X(P ) →
X(P ) be the billiard map. Elements of the phase space X = X(P )
are oriented geodesic segments in R2 with endpoints in ∂P . A segment
x ∈ X ending in a corner of P is singular; the element Tx is not well
defined. A billiard orbit x, Tx, . . . , T k−1x is a singular orbit of length
k if T k−1x is the first singular element in the sequence.
Assigning to x ∈ X its direction, η(x) ∈ S1, we obtain a fibration
η : X → S1 with fibers Rθ ⊂ X . See figure 1. We define the counting
function gdθ(n) for singular orbits in direction θ as the number of phase
points x ∈ Rθ that yield singular orbits of length k ≤ n.
Theorem 1. Let P ⊂ R2 be an arbitrary polygon. Let K(P ) be the
set of its corners. Let α(v) be the angle of v ∈ K(P ). Let dθ be the
lebesgue measure on S1.
Let K ⊂ K(P ). Then
gdθ(n; v)dθ =
Proof. It suffices to prove the claim for a singleton, K = {v}. Let
Y = Y (v) ⊂ X be the set of segments x ∈ X ending at v. Let dy be
the angular measure on Y . These data fit into the setting of section 1.1,
and gdθ(n; v) is the pure counting function.
Let B(z, α) be a conical beam of light with apex angle α emanating
from z ∈ R2. After reflecting in ∂P , it splits into a finite number of
beams B(zi, αi) satisfying
αi = α. The preservation of light volume
is due to the flatness of ∂P .
COMPLEXITY, ETC 11
By preceding remark, the functions rk(·) of Proposition 1 satisfy
rk(·) ≡ 1. The claim now follows from the special case of Proposition 1
considered in section 1.3.
Let p, q be the numbers of corners, obstacles in P . Let κ(P ) =
p+ 2q − 2. Thus, P is simply connected iff q = 0 iff κ(P ) = p− 2.
Corollary 1. Let P ⊂ R2 be an arbitrary polygon. Then
gdθ(n)dθ = πκ(P )n.
Proof. Follows from Theorem 1 via
v∈K(P ) α(v) = (p+ 2q − 2)π.
Figure 1. Base sets for billiard counting functions
12 EUGENE GUTKIN AND MICHAL RAMS
3.2. Position counting functions for billiard flows in euclidean
polygons. Let P ⊂ R2 be a polygon, and let bt : Ψ → Ψ be the
billiard flow. See section 6 for details. For z ∈ P and v ∈ K(P ) let
gcz(l; v) be the number of billiard flow orbits that start from z ∈ P and
wind up at v by time l. Then gcz(l) =
v∈K(P ) gcz(l; v) is the number
of singular billiard orbits of length at most l starting from z. This is
the position counting function for the billiard flow in P .
Theorem 2. Let P ⊂ R2 be a euclidean polygon, and let dz be the
lebesgue measure on P . Then for any K ⊂ K(P ) we have
(15) 2
gcz(l; v)dz =
Proof. It suffices to prove the claim for K = {v}. We view elements
of Ψ as pairs z, θ where z ∈ P is the basepoint, and θ is the direction.
Let M = {(v, θ) : (v,−θ) ∈ Ψ}. Let q : Ψ → P be the obvious
projection. Its fibers Rz are the base sets for the counting functions
gcz(l; v). See figure 1. Set w = χl. These data satisfy the assumptions
of Proposition 2, and gcz(l; v) is the pure counting function.
We set dm to be the angular measure, and compute the function
r(m, t) in equation (6). By Corollary 13 in section 6, r = tχl. Propo-
sition 2 implies the claim.
When K = K(P ), the left hand side in equation (15) is the average
of the position counting function. The argument of Corollary 1 yields
the following.
Corollary 2. Let P ⊂ R2 be an arbitrary polygon. Then
(16) 2
gcz(l)dz = πκ(P )l
3.3. Position counting functions for billiard maps in euclidean
polygons. We will now discuss two billiard map analogs of the pre-
ceding example. Let P ⊂ R2 be a euclidean polygon, and let T :
X(P ) → X(P ) be the billiard map. The phase space X = X(P )
consists of pairs (s, α) where s is the arclentgh parameter on ∂P , and
0 < α < π is the outgoing angle. See [4, 7] and section 6 for details.
An orbit x, Tx, . . . , T k−1x is singular, of (combinatorial) length k if its
last segment ends at a corner of P .
Let s ∈ ∂P , v ∈ K(P ). Define GDs(n; v) to be the set of phase
points (s, α) ∈ X whose orbits of length less than or equal to n end at
COMPLEXITY, ETC 13
v. Set
gds(n; v) = |GDs(n; v)|, gods(n; v) =
(s,α)∈GDs(n;v)
sinα.
The expressions
gds(n) =
v∈K(P )
gds(n; v), gods(n) =
v∈K(P )
gods(n; v)
are the pure position counting function and the optical position counting
function for the billiard map in P .
Let z ∈ R2 and let γ ⊂ R2 be an oriented piecewise C1 curve.
Denote by dzs the projection of the arclength form ds of γ onto the
direction perpendicular to the line from z to s ∈ γ. The integral
dzs = |opt(γ, z)| ≤ |γ| is the optical length of γ viewed from z.
Let z ∈ P . Unfolding k-segment billiard orbits emanating from z,
we obtain a set of linear segments in R2. Let ∂z(P ; k) ⊂ R
2 be the
curve traced by their endpoints. We say that ∂z(P ; k) ⊂ R
2 is the
outer boundary of P , as viewed from z, after k iterates.
Theorem 3. Let P be a euclidean polygon, and let K ⊂ K(P ) be a set
of corners. Then
gds(n; v)ds =
|∂v(P ; k)|;
gods(n; v)ds =
|opt(∂v(P, k))|.
Proof. It suffices to prove the claims for a singleton, K = {v}. Let η :
X → ∂P be the natural projection. Using the arclength parametriza-
tion, we identify ∂P with the interval [0, |∂P |] ⊂ R. For 0 ≤ s ≤ |∂P |
let Rs = η
−1(s) ⊂ X be the fiber. Then Rs are the base sets for
the counting functions gds(n; v), gods(n; v). See figure 1. Let Y =
Y (v) ⊂ X be the set of phase points whose T−1-orbits emanate from
v. The assumptions of section 1.1 are satisfied. The weight functions
are w(s, α, t) = χn(t) and wo(s, α, t) = sinα ·χn(t) for the two cases at
hand. Let ϕ be the angle parameter on Y . The measures on ∂P and
Y have densities ds and dϕ respectively.
The integrals in the right hand side of equation (3) are over the curves
∂v(P ; k), 0 ≤ k ≤ n− 1. The integrands are ds(ϕ) and sinα · ds(ϕ) =
dvs(ϕ) in respective cases.
We will need estimates on lengths and optical lengths.
14 EUGENE GUTKIN AND MICHAL RAMS
Lemma 3. For any polygon P ⊂ R2 there exist 0 < c1 < c2 < ∞ such
that for n sufficiently large
|opt(∂v(P, k))| ≤ c2n
2, c1n
|(∂v(P, k))|.
Proof. There exist positive constants d1, d2 and m0 ∈ N, such that
for any orbit γ of the billiard map with m > m0 segments, we have
d1|γ| ≤ m ≤ d2|γ| [4].
Let v ∈ K(P ). We will estimate
|opt(∂v(P, k))|, as n → ∞.
Let θ1 ≤ θ ≤ θ2 be the angular parameter for orbits emanating from v;
let r(θ) be the geometric length of the orbit. Suppose that r1 ≤ r(θ) ≤
r2. Then the optical length in question is sandwiched between the
lengths of circular arcs of radii r1, r2 of angular size θ2−θ1. By preceding
remarks, if k is sufficiently large, the bounds r1, r2 are proportional to
k. The total angular size does not depend on k. Hence, for sufficiently
large k we have linear upper and lower bounds on
v∈K |opt(∂v(P, k))|.
The other inequality follows from |opt(∂v(P, k))| ≤ |∂v(P, k)|.
3.4. Position counting functions for billiard flows in spherical
polygons. The study is analogous to the planar case discussed in sec-
tion 3.2; we will use the same notation whenever this does not lead to
confusion. We denote by dz the lebesgue measure on S2, and by α(v)
the angle of a corner of P . Set
(20) ζ(x) = 1− cosx−
Theorem 4. Let P ⊂ S2 be a geodesic polygon, and let K ⊂ K(P ).
gcz(l; v)dz =
l + ζ(l− π⌊l/π⌋)
Proof. It suffices to prove the claim when K = {v}. Let M = M(v) ⊂
Ψ be as in section 3.2, and let dα be the angular measure on it. The
assumptions 1, 3 of section 1 are satisfied; the transversality of bt ·M
and Rz may fail for at most a countable set of parameters Pex ⊂ P . See
Remark 3 in section 6. Hence, condition 2′ is fullfilled, and the results
of section 1.2 hold. The function gcz(l; v) is a pure counting function.
The claim now follows from Proposition 2 and Corollary 13.
Let κ(P ) be as in section 3.1.
COMPLEXITY, ETC 15
Corollary 3. Let P ⊂ S2 be an arbitrary polygon. Then
gcz(l)dz = (κ(P )π + area(P ))
l + ζ(l − π⌊l/π⌋)
Proof. For a spherical polygon we have
v∈K(P ) α(v) = area(P ) +
κ(P )π. Substitute this into equation (21).
3.5. Position counting functions for billiard flows in hyper-
bolic polygons. Our treatment and our notation are modelled on
section 3.4. We denote by dz the lebesgue measure on H2, and by α(v)
the angles of corners.
Theorem 5. Let P ⊂ H2 be a geodesic polygon, and let K ⊂ K(P ).
gcz(l; v)dz =
cosh l.
Proof. We repeat verbatim the proof of Theorem 4, and use claim 2 in
Corollary 13.
Let κ(P ) be as in section 3.1.
Corollary 4. Let P ⊂ H2 be a polygon. Then
gcz(l)dz = (κ(P )π − area(P )) cosh l.
Proof. Repeat the argument of Corollary 3; use the formula
v∈K(P ) α(v) =
κ(P )π− area(P ) relating the angles and the area of geodesic polygons
in H2.
4. Relating partial complexities and counting functions
In this section we establish a framework that will allow us to study
the complexity of a wide class of dynamical systems. Our motivation
comes from the billiard dynamics. In fact, polygonal billiard is the
target of applications for our results. The framework is more general,
however. The following observations served as our guiding principles.
First, natural partitions of the billiard-type systems are geared to the
singularities. Second, the billiard dynamics satisfies a certain convexity
property that is instrumental in the study of complexity. These princi-
ples are manifest in the framework of piecewise convex transformations
There are two approaches to the billiard dynamics: The billiard flow
and the billiard map. See section 6. The framework of piecewise convex
16 EUGENE GUTKIN AND MICHAL RAMS
transformations is geared to the billiard map. We begin by establishing
its counterpart for flows.
4.1. Piecewise convex transformations and piecewise convex
flows. A piecewise convex transformation is a triple (X,Γ, T ), whereX
is a two-dimensional convex cell complex, Γ ⊂ X is the graph formed by
the union of one-cells, and T : X → X is an invertible map, regular on
the two-cells of the complex, and compatible with the convex structure
Let Ψ be a compact manifold, with boundary and corners, in general.
Let bt : Ψ → Ψ be a flow, possibly with singularities; let X ⊂ Ψ be
a cross-section. We will assume that the singular set of the flow is
contained in X . For z ∈ X let τ+(z), τ−(z) be the times when z ∈ Ψ
first reaches X under bt, b−t for 0 < t. We assume that for any z ∈ Ψ\X
there is 0 < ε = ε(z) such that bt(z) is regular for |t| < ε.
A piecewise convex flow is determined by the following data: A flow,
bt : Ψ → Ψ, a cross-section, X ⊂ Ψ, and the structure of a convex cell
complex on X , compatible with the poincare map. Billiard flows for
polygons on surfaces of constant curvature are piecewise convex flows
4.2. Partial complexities for maps and flows. Let (X,Γn, T
n) be
the iterates of a piecewise convex transformation (X,Γ, T ).4 Let F (Γn)
be the finite set of open faces of Γn; these are the continuity regions for
T n. The function f(n) = |F (Γn)| is the (full) complexity of (X,Γ, T ).
Let R ⊂ X be a closed subset. Set
FR(n) = {A ∈ F (Γn) : A ∩R 6= ∅}.
Definition 1. The function fR(n) = |FR(n)| is the partial complexity
of the piecewise convex transformation (X,Γ, T ) based on the subset
Let bt : Ψ → Ψ be a piecewise convex flow, and let R ⊂ Ψ be a closed,
convex set transversal to the flow. For 0 < l let OR(l) be the set of
regular flow orbits of length l starting from R. Let α0, α1 ∈ OR(l). A
homotopy is a continuous family of regular orbits αp ∈ OR(l), 0 ≤ p ≤
1, interpolating between α0, α1. We will say, for brevity, that the orbits
α0, α1 are R-homotopic. We denote by HR(l) the set of R-homotopy
classes.
Definition 2. The function hR(l) = |HR(l)| is the partial complexity
(based on R) of the piecewise convex flow bt : Ψ → Ψ.
4 They are piecewise convex transformations as well [7].
COMPLEXITY, ETC 17
Figure 2. Removing a vertex in a graph
4.3. Partial complexities and counting functions. In what fol-
lows we assume that R ⊂ Ψ is a convex graph without isolated vertices.
For x ∈ R its valence val(x) is the number of edges of x minus one.
In particular, if x is an interior point of an edge, then val(x) = 1. Set
val(R) = maxx∈R val(x). We endow R \ {x} with the graph structure
where x is replaced by 1+val(x) vertices; each of them is the endpoint
of a unique edge. If x, y, z, . . . ∈ R are distinct points, then the induc-
tively defined graph structure on R without x, y, z, . . . does not depend
on the order of removing these points. We will denote this graph by
R \ {x, y, z, . . .}. See figure 2 for an illustration.
Let E(R) and V (R) be the sets of edges and vertices, and let c(R)
be the number of connected components of the graph. Let hi = hi(R)
be the betti numbers of R, and set χ(R) = |V (R)| − |E(R)|. Then
c(R) = h0, χ(R) = h0 − h1.
Lemma 4. Let R be a finite graph, and let x1, . . . , xp ∈ R be distinct
points. Then
(25) χ(R) +
val(xi) ≤ c(R \ {x1, . . . , xp}) ≤ c(R) +
val(xi).
If R is a forest, then the bound on the right in equation (25) becomes
an equality.
18 EUGENE GUTKIN AND MICHAL RAMS
Proof. It suffices to prove the claims when R is connected, and we
remove a single vertex, x. Equation (25) becomes
(26) χ(R) + val(x) ≤ c(R \ {x}) ≤ c(R) + val(x).
We have |V (R \ {x})| = |V (R)| + val(x), |E(R \ {x})| = |E(R)|, and
χ(R\{x}) = χ(R)+val(x). Equivalently, we have χ(R\{x}) = h0(R)+
val(x)−h1(R) and h0(R\{x}) = h0(R)+val(x)+(h1(R \ {x})− h1(R)).
The former (resp. latter) identity implies the left (resp. right) inequal-
ity in equation (26).
When R is a tree, we have c(R \ {x}) = c(R) + val(x), and the
remaining claim follows.
We will introduce counting functions for singular orbits of the billiard
map and the billiard flow.
By definition, an orbit α = {bt(z), 0 ≤ t ≤ l}, does not pass through
singular points in Ψ. It is regular if it does not contain any singu-
lar points in Ψ; it is singular if one of its endpoints is singular. The
set SR(l) of singular orbits of length at most l, based in R, is finite.
The quantities gcR(l) = |SR(l)| and gdR(n) = |R ∩ Γn| are the count-
ing functions for singular orbits based in R for the flow and the map
respectively.
Now we will relate partial complexities and counting functions. We
do this for a piecewise convex flow bt : Ψ → Ψ and for a piecewise
convex transformation (X,Γ, T ). In both cases the partial complexity is
based on a 1-dimensional subset, say R. Recall that gcR(l), gdR(n) are
the respective counting functions, and hR(l), fR(n) are the respective
complexities. We will refer to these situations as the continuous case
and the discrete case respectively.
Proposition 5. Let the setting be as above. Then the following state-
ments hold.
1. In the continuous case there exist h0 ∈ N and l0 ∈ R+ such that
hR(l) = h0 + gcR(l) for l0 ≤ l. 2. In the discrete case there exist
f0, n0 ∈ N such that for n0 ≤ n we have fR(n) = f0 + gdR(n).
Proof. In both cases the graph R is equipped with a tower of finite sets,
say X(l) and Xn respectively. Let X∞ ⊂ R be their union. We will
compare the number of connected components of graphs R\X(l), R\Xn
with the cardinalities of these sets.
We consider the discrete case, leaving the continuous case to the
reader. Let m < n be any pair of natural numbers. By (the proof of)
COMPLEXITY, ETC 19
Lemma 4,
c(R \Xn)− c(R \Xm) = [h1(R \Xn)− h1(R \Xm)] +
x∈Xn\Xm
val(x).
We have h1(R \ Xn) ≤ h1(R \ Xm); the inequality holds iff Xn \
Xm breaks cycles in R \ Xm. Since the sequence h1(R \ Xk) ∈ N is
nonincreasing, it stabilizes. Thus, there exists n1 ∈ N such that for
n1 ≤ m < n we have h1(R \Xn) = h1(R \Xm).
The set of points x ∈ R satisfying 1 < val(x) is finite. Thus, there
exists n2 ∈ N such that if n2 ≤ k and x ∈ X∞ \Xk, then val(x) = 1.
Set n0 = max(n1, n2). Then for n0 ≤ m < n the above equation
yields c(R \Xn)− c(R \Xm) = |Xn \Xm|. Specializing to m = n0, we
obtain fR(n) = (fR(n0)− gdR(n0)) + gdR(n).
5. Bounds on partial complexities for the billiard
We will use the preceding material to derive bounds on partial com-
plexities for the polygonal billiard.
5.1. Direction complexities for billiard maps in euclidean poly-
gons. We use the setting and the notation of section 3.1. For a polygon
P and a direction θ, we denote by fdθ(n) the partial complexity with
base Rθ. This is the complexity in direction θ.
Corollary 5. For lebesgue almost all directions θ there is C = C(θ)
and there are arbitrarily large n such that fdθ(n) ≤ Cn.
Proof. Each Rθ is a convex graph in the phase space [7]. By Lemma 1
and Corollary 1, the counting functions gdθ(n) have the desired proper-
ties. By the second claim of Proposition 5, the directional complexities
do as well.
Corollary 6. For any ε > 0 and almost every direction θ we have
fdθ(n) = O(n
1+ε).
Proof. The proof goes along the lines of the proof of Corollary 5. In-
stead of Lemma 1, we use Proposition 4 (the first claim).
5.2. Position complexities for billiard flows in euclidean poly-
gons. Let P be a euclidean polygon, and let z ∈ P be any point. We
consider the billiard flow in P , and use the setting of section 3.2. Thus,
gcz(l) is the position counting function for orbits emanating from z. We
denote by hz(l) the corresponding partial complexity.
Corollary 7. For almost every point z there is a positive number C =
C(z) such that hz(l) ≤ Cl
2 for arbitrarily large l.
20 EUGENE GUTKIN AND MICHAL RAMS
Proof. The sets Rz satisfy the assumptions of section 4. The claim
follows from Lemma 1, Corollary 2 and the continuous case in Propo-
sition 5.
Corollary 8. For any ε > 0 and almost every z ∈ P we have hz(l) =
O(l2+ε).
Proof. The proof is similar to the preceding argument, and we use the
first claim in Proposition 3 instead of Lemma 1.
5.3. Position complexities for billiard maps in euclidean poly-
gons. This is the billiard map analog of the preceding example. Let
P be a euclidean polygon, and let s ∈ ∂P . We use the setting of sec-
tion 3.3. There we have defined the counting functions gds(n), gods(n).
Let fs(n) be the partial complexity corresponding to gds(n). This is
the position complexity for the billiard map.
Corollary 9. Let P ⊂ R2 be a polygon such that
k=1 |∂v(P ; k)|
has a quadratic upper bound.5 Then for almost all s ∈ ∂P we have
fs(n) = O(n
2+ε) for any 0 < ε.
Proof. The sets Rs ⊂ X satisfy the assumptions of section 4. We use
Theorem 3, Lemma 3, and apply Proposition 5.
The estimate of Corollary 9 on fs(n) is conditional, because in gen-
eral we have no efficient upper bound on
|∂v(P ; k)|.
5.4. Position complexities for billiard flows in spherical poly-
gons. We use the setting of section 3.4. For a spherical polygon,
P ⊂ S2, and z ∈ P , let hz(l) be the position complexity.
Corollary 10. For almost every point z ∈ P there is C = C(z) and
there are arbitrarily large l such that hz(l) ≤ Cl.
Proof. The sets Rz satisfy the assumptions of section 4. We use Lemma 1,
Corollary 3, and Proposition 5.
Corollary 11. For any ε > 0 and almost every z ∈ P we have hz(l) =
O(l1+ε).
Proof. See the proof of Corollary 8.
5This holds if P is a rational polygon [11].
COMPLEXITY, ETC 21
5.5. Position complexities for billiard flows in hyperbolic poly-
gons. This material is the hyperbolic plane counterpart of section 3.2,
and we use the setting of section 3.5.
Corollary 12. Let P ⊂ H2 be a geodesic polygon, let z ∈ P , and let
hz(l) be the position complexity. Then for almost every point z ∈ P we
have hz(l) = O(e
(1+ε)l).
Proof. We verify that the sets Rz satisfy the assumptions of section 4,
and mimick the proof of Corollary 8; we use Corollary 4, Proposition 3,
and the continuous case of Proposition 5.
6. Appendix: Covering spaces for polygonal billiards
Let M be a simply connected surface of constant curvature, and let
P ⊂ M be a connected geodesic polygon. We normalize the metric so
that the curvature is either zero (M = R2), or one (M = S2), or minus
one (M = H2).
Let A be the set of sides in P . We will denote its elements by a, b, . . . .
For a side, say a ∈ A, let sa ∈ Iso(M) be the corresponding geodesic
reflection. We associate with P a Coxeter system (G,A) [2]. We denote
by σa, σb, · · · ∈ G the elements corresponding to a, b, . . . ∈ A. They
generate G. The defining relations are σ2a = 1 and (σaσb)
n(a,b) = 1;
the latter arise only for the sides a, b with a common corner if the
angle, θ(a, b), between them is π-rational. In this case n(a, b) is the
denominator of θ(a, b)/π. Otherwise n(a, b) = ∞.
To any “generalized polyhedron” P corresponds a topological space
C endowed with several structures, and a Coxeter system [2]. Our
situation fits into the framework of [2], and we apply its results. First,
C is a differentiable surface. Second, C is tiled by subsets Pg, g ∈ G,
labelled by elements of the Coxeter group G; we call them the tiles, and
identify Pe with P . The group G acts on C properly discontinuously,
preserving the tiling: g · Ph = Pgh.
Since Pe is identified with P ⊂ M , it inherits from M a riemann-
ian structure. The action of G is compatible with this structure, and
extends it to all of C. This riemannian structure generally has cone
singularities at vertices of the tiling C = ∪g∈GPg.
6 Around other points
this riemannian structure is isometric to that of M ; in particular, ex-
cept for cone points, C has constant curvature. The group G acts on C
by isometries.
6Each vertex, v, corresponds to a corner of P . The metric at v is regular iff the
corner angle is π/n, n = 2, 3, . . . .
22 EUGENE GUTKIN AND MICHAL RAMS
Definition 3. The space C endowed with the riemannian structure,
the isometric action of G and the G-invariant tiling C = ∪g∈GPg is the
universal covering space of the geodesic polygon P ⊂ M .
If X is a riemannian manifold (with boundary and singularities,
in general), we denote by TX = ∪x∈XTxX its unit tangent bundle.
The classical construct of geodesic flow, GtX : TX → TX , extends to
manifolds with boundaries and singularities. In particular, GtX makes
sense when X = M,P , or C. Another classical construct, the expo-
nential map, also extends to our situation. For x ∈ X as above, and
(v, t) ∈ TxX × R+, we set expX(v, t) ∈ X be the base-point of G
X(v).
We will use the notation expxX to indicate that we are exponentiating
from the point x. If X is nonsingular, then expxX : TxX × R+ → X is
a differentiable mapping. For X with singularities, such as our P and
C, the maps expxX are defined on proper subsets of TxX × R+; these
subsets have full lebesgue measure. Generally, the maps do not extend
by continuity to all of TxX × R+.
Let X, Y be nonsingular riemannian manifolds of the same dimen-
sion; let ϕ : X → Y be a local isometry. It induces a local dif-
feomorphism Φ : TX → TY commuting with the geodesic flows:
Φ ◦GtX = G
Y ◦Φ. The exponential maps commute as well: ϕ ◦ exp
Y ◦ dxϕ. These relationships hold, in particular, for coverings of
nonsingular riemannian manifolds. Suitably interpreted, they extend
to (branched) coverings of riemannian manifolds with boundaries, cor-
ners, and singularities. In our case X = C, while Y = M , or Y = P .
We will now define the mappings f : C → P, F : TC → TP and
ϕ : C → M, Φ : TC → TM .
The identification Pe = P defines f, ϕ on Pe. To extend them to all
of C, we use the tiling C = ∪g∈GPg and the actions of G on C and M .
In order to distinguish between these actions, we will denote them by
g · x and g(x) respectively. Then there is a unique x ∈ Pe such that
z = g · x. We set f(z) = x ∈ P and ϕ(z) = g(x) ∈ M . By basic
properties of Coxeter groups [2], the mappings f, ϕ are well defined.
Moreover, f : C → P and ϕ : C → M are the unique G-equivariant
mappings which are identical on Pe.
7 By construction, both mappings
are continuous; they are diffeomorphisms in the interior of each tile,
Pg ⊂ C, and on the interior of the union of any pair of adjacent tiles.
The potential locus of non-differentiability for both f and ϕ is the
set V of vertices in the tiling C = ∪g∈GPg. We have V = f
−1(K(P ))
where K(P ) is the set of corners of P . By equivariance, ϕ(V ) =
7The action of G on P is trivial.
COMPLEXITY, ETC 23
∪g∈Gg(K(P )) ⊂ M .
8 There are two kinds of points in V : vertices
coming from the corners of P with π-rational and π-irrational angles.
Their cone angles are integer multiples of 2π and are infinite respec-
tively. Vertices v ∈ V with cone angle 2π are, in fact, regular points
in C, and the mappings f, ϕ are both regular there. Around a vertex
v with cone angle 2kπ > 2π the mapping ϕ is differentiable, but not a
diffeomorphism; it is locally conjugate to z 7→ zk. Near such a vertex,
ϕ is a branched covering of degree k. At a vertex with infinite cone
angle, ϕ has infinite branching.
Remark 3. The set ϕ(V ) ⊂ M is countable. (It is finite iff the
group generated by geodesic reflections in the sides of P is a finite
Coxeter group. Typically, ϕ(V ) ⊂ M is a dense, countable set.)
Let M = S2, and let z 7→ z′ denote the antipodal map. Set F =
P ∩ (ϕ(V ) ∪ (ϕ(V ))′). Points of F are exceptional, in the following
sense. Let z ∈ P be such that the beam Rz of billiard orbits emanat-
ing from z contains a sub-beam focusing at a corner of P . Then z ∈ F .
This follows from Proposition 6 below.
Thus, F contains all points z ∈ P for which the transversality as-
sumption in Condition 2 of section 1.2 fails. Since F is countable, the
set of exceptional parameters has measure zero, and Condition 2′ is
satisfied. See Remark 1 in section 1.
Furthermore, the mappings f and ϕ are local isometries. They are
isometries on every tile Pg ⊂ C; we have f(Pg) = P , ϕ(Pg) = g(P ) ⊂
M . Let g · a be a side of Pg, let h = σag and let Ph be the adjacent
tile. The maps f : Pg → P, Ph → P and ϕ : Pg → g(P ), Ph → h(P ) are
coherent around the common (open) side g · a. The map f is never an
isometry on Pg ∪Ph; for ϕ this is the case iff the interiors of g(P ), h(P )
are disjoint in M . The latter generally fails for nonconvex P .
By coherence of f and ϕ across the sides separating adjacent tiles,
we lift them to the tangent bundles, obtaining the mappings of unit
tangent bundles F : TC → TP , Φ : TC → TM , which are also defined
on vectors based at the vertices of the tiling C = ∪g∈GPg. Let v be a
vertex, and let α be the angle of the corner f(v) ∈ K(P ). Then Φ :
TvC → Tϕ(v)M is m-to-1 if α = mπ/n and ∞-to-1 if α is π-irrational.
The geodesics γ(t) in C cannot be further extended (generally) once
they reach a vertex. All other geodesics in C are defined for −∞ < t <
8 The representation M = ∪g∈Gg(P ) is not a tiling, in general.
24 EUGENE GUTKIN AND MICHAL RAMS
Using the inclusion P ⊂ M , we identify TP with the subset of TM
consisting of M-tangent vectors with base-points in P , and directed in-
ward. Any v ∈ TP defines the billiard orbit in P , β(t) = expP (tv), 0 ≤
t, and the geodesic in M , γ(t) = expM(tv), 0 ≤ t. They are related
by the canonical unfolding of billiard orbits. This is an inductive pro-
cedure which replaces the consecutive reflections about the sides of P
by consecutive reflections of the “latest billiard table” g(P ) about the
appropriate side, yielding the next billiard table h(P ), and continuing
the geodesic straight across the common side of g(P ) and h(P ). See [4]
in the planar case and [7], section 3.1, in the general case. Let x ∈ P
and let v ∈ TxP . We denote by βv (resp. γv) the billiard orbit in P
(resp. the geodesic in M) that emanates from x in the direction v. The
unfolding operator, Ux : βv 7→ γv, preserves the parametrisations.
Proposition 6. Let x ∈ P, v ∈ TxP . Identify P and Pe ⊂ C and let
x ∈ Pe, v ∈ TxC be the corresponding data. Then for t ∈ R+ we have
(27) Ux(expP (v, t)) = ϕ(expC(v, t)).
Proof. We will freely use the preceding discussion. As t ∈ R+ goes to
infinity, expP (v, t) runs with the unit speed along a billiard orbit in P .
The curve exp
(v, t) is the geodesic in C defined by the data (x, v), and
ϕ(exp
(v, t)) is the geodesic in M emanating from x in the direction
v. The billiard orbit in P and the geodesic in M are related by the
unfolding operator.
For x ∈ P let ExP = TxP ×R+ be the full tangent space (or the full
tangent cone) at x. If S ⊂ TxP is a segment, let ESxP = S × R+ be
the corresponding subcone. We use the analogous notation for x ∈ C
or x ∈ M . In polar coordinates (t, θ) in R2 the lebesgue measure on
ExP is given by the density tdtdθ.
Corollary 13. Let x ∈ P ⊂ M be arbitrary, and let expxP : ExP → P
be the exponential mapping. The pull-back by expxP of the lebesgue
measure on P to ExP is the smooth measure with the density dν(t, θ).
1. When M = R2, we have dν = tdtdθ.
2. When M = H2, we have dν = sinh tdtdθ.
3. When M = S2, we have dν = | sin t|dtdθ.
Proof. By Proposition 6, the measure in question coincides with the
pullback to the tangent space ExM of the riemannian measure on M
by the exponential map ExM → M . The latter is well known.
We point out that the preceding material has a billiard map version.
We will briefly discuss it now. Let β(t) = (z(t), θ(t)), t ∈ R, be an orbit
COMPLEXITY, ETC 25
of the billiard flow. We obtain the corresponding billiard map orbit
βd(k), k ∈ Z, by restricting β(t) to the consecutive times tk such that
z(tk) ∈ ∂P . The correspondence β(·) 7→ βd(·) is invertible. This allows
us to formulate the billiard map versions of the universal covering space,
the lifting of billiard map orbits to the universal covering space, and the
relationship between the liftings and the unfoldings, à là Proposition 6.
Since we are not directly using this material in the body of the paper,
we spare the details.
References
[1] J. Cassaigne, P. Hubert and S. Troubetzkoy, Complexity and growth for polyg-
onal billiards, Ann. Inst. Fourier 52 (2002), 835 – 847.
[2] M.W. Davis, Groups generated by reflections and aspherical manifolds not cov-
ered by Euclidean space, Ann. Math. 117 (1983), 293 – 324.
[3] G. Galperin, T. Krüger and S. Troubetzkoy, Local instability of orbits in polyg-
onal and polyhedral billiards, Comm. Math. Phys. 169 (1995), 463 – 473.
[4] E. Gutkin, Billiards in polygons, Physica 19 D (1986), 311 – 333.
[5] E. Gutkin, Billiard dynamics: A survey with the emphasis on open problems,
Reg. & Chaot. Dyn. 8 (2003), 1 – 13.
[6] E. Gutkin and N. Haydn, Topological entropy of polygon exchange transfor-
mations and polygonal billiards, Erg. Theo. & Dyn. Syst. 17 (1997), 849 –
[7] E. Gutkin and S. Tabachnikov, Complexity of piecewise convex transforma-
tions in two dimensions, with applications to polygonal billiards on surfaces of
constant curvature, Moscow Math. J. 6 (2006), 673 – 701.
[8] E. Gutkin and S. Troubetzkoy, Directional flows and strong recurrence for
polygonal billiards, Pitman Res. Not. Math. 362 (1996), 21 – 45.
[9] P. Hubert, Complexité de suites définies par des billards rationnels, Bull. Soc.
Math. Fr. 123 (1995), 257 – 270.
[10] A. Katok and B. Hasselblatt, Introduction to the Modern Theory of Dynamical
Systems, Cambridge University Press, Cambridge 1995.
[11] H. Masur, The growth rate of trajectories of a quadratic differential, Erg. Theo.
& Dyn. Syst. 10 (1990), 151 – 176.
IMPA, Rio de Janeiro, Brasil and UMK, Torun, Poland; IMPAN,
Warszawa, Poland
E-mail address : gutkin@impa.br,gutkin@mat.uni.torun.pl;rams@impan.gov.pl
	Introduction and overview
	1. Averages of counting functions
	1.1. Discrete dynamics
	1.2. Continuous dynamics
	1.3. Special cases
	2. Bounds on counting functions
	3. Counting functions for polygonal billiard
	3.1. Direction counting functions for billiard maps in euclidean polygons
	3.2. Position counting functions for billiard flows in euclidean polygons
	3.3. Position counting functions for billiard maps in euclidean polygons
	3.4. Position counting functions for billiard flows in spherical polygons
	3.5. Position counting functions for billiard flows in hyperbolic polygons
	4. Relating partial complexities and counting functions
	4.1. Piecewise convex transformations and piecewise convex flows
	4.2. Partial complexities for maps and flows
	4.3. Partial complexities and counting functions
	5. Bounds on partial complexities for the billiard
	5.1. Direction complexities for billiard maps in euclidean polygons
	5.2. Position complexities for billiard flows in euclidean polygons
	5.3. Position complexities for billiard maps in euclidean polygons
	5.4. Position complexities for billiard flows in spherical polygons
	5.5. Position complexities for billiard flows in hyperbolic polygons
	6. Appendix: Covering spaces for polygonal billiards
	References

  We introduce a new method for estimating the growth of various quantities
arising in dynamical systems. We apply our method to polygonal billiards on
surfaces of constant curvature. For instance, we obtain power bounds of degree
two plus epsilon in length for the number of billiard orbits between almost all
pairs of points in a planar polygon.

Introduction and overview
Complexity of a dynamical system is measured with respect to a
coding of its orbits. The coding, in turn, is determined by partitioning
the phase space of the system into elementary pieces. For dynami-
cal systems with singularities, such as polygonal billiards, connected
components in the complement to the singular set yield a natural par-
tition. Convexity of its atoms with respect to the geodesic structure in
the phase space imposed by geometric optics, is crucial in the study of
billiard complexity [7].
In the present study, as well as in [7], P is a geodesic polygon in
a surface of constant curvature. Let, for concreteness, P be a planar
polygon. We denote by fP (n) the number of words of length n gener-
ated by coding billiard orbits by visited domains of regularity. When
P is simply connected, this coincides with the coding by sides in P . It
is known that fP (n) is subexponential in n [3, 6], and for general P
no better bound is known. If P is a rational polygon (i. e., its angles
are commensurable with π [4]), fP (n) = O(n
3) [1, 7]. The current
conjecture is that for any planar polygon fP (n) = O(n
d) [5].
In order to advance the understanding of billiard complexity, we
introduce the notion of partial complexities. Let Ψ be the phase space,
and let P be the defining partition. Iterating the dynamics we obtain
an increasing tower Pn of partitions; the full complexity is f(n) =
Date: October 31, 2018.
Key words and phrases. Geodesic polygon, billiard map, billiard flow, complex-
ity, counting functions, unfolding of orbits, covering space, exponential map.
http://arxiv.org/abs/0704.1975v1
2 EUGENE GUTKIN AND MICHAL RAMS
|Pn|. If R ⊂ Φ, let Pn(R) be the induced tower of its partitions. The
partial complexity based on R is fR(n) = |Pn(R)|. Particular partial
complexities have been studied earlier. For instance, in [8] we obtained
polynomial bounds on direction complexity, which is one of the partial
complexities investigated here.
In this work we introduce a new general approach to estimating par-
tial complexities. The setting is as follows. There is a family of subsets
Rθ foliating the phase space. Let fθ(n) be the partial complexity with
base Rθ. Let gθ(n) be the counting function for singular billiard or-
bits starting from Rθ. Under appropriate assumptions, fθ(n) and gθ(n)
have the same growth, as n → ∞. See section 4.
Let θ ∈ Θ, the parameter space. Suppose that we bound the average
counting function G(n) =
gθ(n). Tchebysheff inequality and the
zero-one law yield bounds for individual gθ(n) valid for almost all θ ∈ Θ.
See section 2. Combined with preceding remarks, these yield estimates
on partial complexities for almost all values of the parameter.
This is the general scheme for our approach to partial complexities.
This work implements this scheme for polygonal billiards. We will now
describe the contents of the paper in more detail.
In section 1 we investigate counting functions and their averages. We
establish the relevant framework in sufficient generality, with the view
towards a broad range of geometric-dynamic applications. The main
results are Propositions 1 and 2 respectively. These yield geometric
formulas for averages of counting functions which are valid under mild
assumptions of transversality type.
Section 2 is analytic, and also quite general. The setting is as follows.
There is a family of positive functions, gθ(p), of positive argument
(p ∈ N and p ∈ R+ in the discrete and continuous cases respectively),
depending on parameter θ ∈ Θ. Set G(p) =
gθ(p)dθ. From upper
bounds on G(p) we derive estimates on individual gθ(p); they are valid
for almost all θ. Precise formulations depend on the details of the
situation. See Propositions 3 and 4.
Section 3 sets the stage for applications to billiard dynamics. Our
billiard table is a geodesic polygon, P , in a simply connected surface
of constant curvature. There are two versions of billiard dynamics:
the billiard flow and the billiard map. In our discussion of partial
complexities, it is convenient to treat them separately. Accordingly,
section 3 consists of several subsections; each subsection deals with a
particular partial complexity for a particular kind of billiard dynamics.
We use two geometric parameters for partial complexities: the direc-
tion and the position. The direction complexity tells us how the set of
COMPLEXITY, ETC 3
phase points starting in the same direction splits after bouncing off of
the sides of P . The direction complexity is defined for planar polygons.
The position complexity tells us about the splitting of beams of billiard
orbits emanating from a point of P . It is defined in all cases.
In each of the subsections of section 3 we define a counting function
and check the assumptions of section 1; then we evaluate the integral
over the parameter space, i. e., we compute the average counting func-
tions. It turns out that they have geometric meanings. Here is a sample
of results from section 3. Let GP (l) be the average position counting
function for the billiard flow in a geodesic polygon P . For planar poly-
gons we have GP (l) = c0(P )l
2. See Corollary 2 in section 3.2. For
polygons in S2 we have GP (l) = c+(P )l + c
+(P )f(l) where f is a uni-
versal periodic function. See Corollary 3 in section 3.4. For polygons
in H2 we have GP (l) = c−(P ) cosh l. See Corollary 4 in section 3.5.
The coefficients in these formulas depend on how many corners P has
and on the number of obstacles in its interior.
Section 4, again, is quite general. In this section we obtain relation-
ships between partial complexities with one-dimensional base sets and
counting functions. The main result of this section is Proposition 5.
It says that if the bases are one-dimensional, then the difference be-
tween the partial complexity and the counting function is bounded, as
time goes to infinity. Other assumptions on the base have to do with
convexity in the phase space. The framework of this section is that of
piecewise convex transformations [7].
In section 5 we specialize again to polygonal billiards. Combining the
material of preceding sections, we obtain bounds on the position and
direction complexities for the billard flow and the billiard map. Here is
a sample of our results. Let P be a euclidean polygon. Let θ ∈ S1 (resp.
z ∈ P ) be any direction (resp. position). Let fdθ(n) (resp. hz(l)) be
the direction complexity for the billiard map (resp. position complexity
for the billiard flow). Then for almost all directions θ (resp. for almost
all positions z) we have fdθ(n) = O(n
1+ε) (resp. hz(l) = O(l
2+ε)),
where ε > 0 is arbitrary. See Corollary 6 and Corollary 8. Let now P
be a spherical polygon, and let hz(l) be the position complexity for the
billiard flow in P . Then for almost every z ∈ P there is a C = C(z)
and arbitrarily large l such that hz(l) ≤ Cl. See Corollary 10. For
any ε > 0 and almost every z ∈ P we have hz(l) = O(l
1+ε). See
Corollary 11.
In the study of polygonal billiards the device of unfolding billiard
orbits is indispensable [4]. If P ⊂ M , and β is a billiard orbit in P ,
its unfolding is a geodesic in M . Several arguments in section 3 use
4 EUGENE GUTKIN AND MICHAL RAMS
the technique of lifting billiard orbits to the universal covering space
of P .1 This notion was not written up in the billiard literature. In our
Appendix section 6 we present the relevant definitions and propositions.
Proposition 6 puts forward the main property of the universal covering
space of a geodesic polygon. It relates the unfoldings and the liftings of
billiard orbits. The proofs in section 3 use Corollary 13 of Proposition 6,
which deals with the pullbacks of lebesgue measures under unfoldings.
In order to put our results into perspective, we will now briefly sur-
vey the literature on billiard complexities. The subexponential growth
of (full) billiard complexity for arbitrary euclidean polygons is estab-
lished in [3] and [6]. Both proofs are indirect, in that they do not yield
explicit subexponential bounds. On the other hand, for rational eu-
clidean polygons the complexity is cubic. This is contained in [1] for
convex and in [7] for all rational polygons. The arguments in [1] and
[7] rely on a theorem in [11]; it says that the number of billiard orbits
between any pair of corners in a rational polygon grows quadratically
in length. From our viewpoint, this is a statement about the position
counting functions gz(l). It says that gz(l) = O(l
2) if P ⊂ R2 is ra-
tional and z ∈ P is a corner. By comparison, our Corollary 8 and
Proposition 5 yield that gz(l) = O(l
2+ε) for any ε > 0 and almost all
z ∈ P where P ⊂ R2 is an arbitrary polygon. The directional com-
plexity fdθ(n) has been studied in [8] and [9]. The work [9] concerns
the directional complexity for the billiard in a rational, planar polygon
P . Assume that P is convex. Then [9] derives an explicit formula for
fdθ(n), valid for minimal directions θ. (The set of nonminimal direc-
tions is countable.) By this formula, fdθ(n) = O(n). On the other
hand, [8] shows that fdθ(n) = O(n
d) for any P ⊂ R2 and an arbitrary
θ. The degree d in the bound does not depend on θ. Our Corollary 6
estimates the complexity fdθ(n) for an arbitrary polygon P ⊂ R
2. It
says that fdθ(n) = O(n
1+ε) for any ε > 0 and almost all directions θ.
It is plausible that the bounds like Corollary 8, Corollary 6, etc hold
for any point z ∈ P , any direction θ ∈ S1, etc.
1. Averages of counting functions
In this section we introduce the framework of counting functions
in differentiable dynamics. We will apply it to the billiard dynamics
later on. Our phase spaces are “manifolds”. By this we will mean
compact manifolds with boundaries, corners, and singular points, in
general. Our setting involves i) a foliation of the phase space by closed
1Not to be confused with the concept of universal covering space in topology.
COMPLEXITY, ETC 5
submanifolds that are fibers for a projection onto a manifold of smaller
dimension; ii) a submanifold in the phase space, transversal to the
fibers; iii) a weight function on the product of the phase space and
the time. See the details below. The dynamics in question may be
discrete or continuous. We will expose the two cases separately. The
two subsections that follow are parallel, and the treatments differ in
technical details.
1.1. Discrete dynamics. Let T : X → X, T−1 : X → X be piecewise
diffeomorphisms with the following data.
1. There is a fibration η : X → Θ whose base is a compact manifold
and whose fibers Rθ = η
−1(θ) are compact submanifolds, such that
dim(Rθ) = dim(X)− dim(Θ). We will use the notation X = ∪θ∈ΘRθ.
2. There is a closed submanifold, Y ⊂ X , dim(Y ) = dim(Θ), such that
for k ∈ −N2 the manifolds T k(Y ) are transversal to the fibers Rθ.
3. There is a weight function, i. e., a continuous, non-negative function
w(x, t) on X × N. The function w may depend only on time, e. g.,
w = χn, the indicator function of [0, n− 1].
Remark 1. Condition 2 may be weakened, as follows.
2′. There is a closed submanifold, Y ⊂ X , and a set Θex ⊂ Θ of measure
zero such that for k ∈ −N and θ ∈ Θ\Θex the manifolds T
k(Y ) and Rθ
are transversal. All of our results remain valid if we replace condition 2
by the weaker condition 2′. However, in our applications to polygonal
billards, condition 2 may not hold only for polygons in surfaces of
positive curvature. See section 3.4. To simplify the exposition, we will
assume in what follows that Θex = ∅.
In view of condition 2, Γ(θ) = {(x, k) : x ∈ Rθ, k ∈ N, T
k(x) ∈ Y } is
a countable (at most) set. The sets Γk(θ) = {(x, k) : x ∈ Rθ, T
k(x) ∈
Y } are finite for all k ∈ N, and Γ(θ) = ∪Γk(θ).
We define the weighted counting function by
(1) g(θ;w) =
(x,k)∈Γ(θ)
w(x, k).
The pure counting function gn(θ) corresponds to the weight w = χn.
We have
(2) gn(θ) =
|Γk(θ)|.
2By convention, N = 0, 1, . . . .
6 EUGENE GUTKIN AND MICHAL RAMS
Proposition 1. Let dθ, dy be finite, lebesgue-class measures on Θ, Y
respectively. Then for k ∈ N there are functions rk(·) ≥ 0 on Y ,
determined by the data 1) and 2) alone, such that
g(θ;w)dθ =
w(T−k · y, k)rk(y)
Proof. For any k ∈ N set fk = η ◦ T
−k : Y → Θ. By conditions 1 and
2, fk is a local diffeomorphism. Therefore f
k (dθ) = rk(y) dy.
It suffices to establish equation (3) for the special case w(x, i) = 0 if
i 6= k. A point x ∈ X contributes to the integral in the left hand side
of equation (3) iff T k ·x ∈ Y , or equivalently, η(x) = fk(y), y ∈ Y . The
claim follows by a straightforward change of variables.
1.2. Continuous dynamics. Let bt : Ψ → Ψ be a flow of piecewise
diffeomorphisms on a phase space Ψ with the following data.
1. There is a fibration q : Ψ → Z with a compact base and fibers
q−1(z) = Rz ⊂ Ψ, transversal to the flow. We will use the notation
Ψ = ∪z∈ZRz.
2. There is a closed submanifold, M ⊂ Ψ, dim(M) = dim(Z) − 1,
transversal to the flow, and such that N = ∪t∈R
bt · M is transversal
to the fibers Rz.
3. There is a weight function, i. e., a continuous, non-negative function
w(x, t) on Ψ × R+. In a special case, w depends only on time, e. g.,
w = χl, the indicator function of [0, l].
In view of condition 2, G(z) = {(x, t) : x ∈ Rz, 0 ≤ t, b
t(x) ∈ M} is
a countable (at most) set. The sets Gl(z) = {(x, t) : x ∈ Rz, 0 ≤ t ≤
l, bt(x) ∈ M} are finite for all l ∈ R+, and G(z) = ∪Gl(z).
We define the weighted counting function by
(4) g(z;w) =
(x,t)∈G(z)
w(x, t).
The pure counting function gl(z) corresponds to the weight w = χl.
We have
(5) gl(z) = |Gl(z)|.
Proposition 2. Let dz, dm be finite, lebesgue-class measures on Z,M
respectively; let dt be the lebesgue measure on R. Then there exist a
3Our results remain valid if the set of parameters Z
⊂ Z where the transversal-
ity fails has measure zero. See Remark 1. In what follows, by condition 2′ we will
mean the weakened condition 2 either in the setting of section 1.2 or section 1.1.
COMPLEXITY, ETC 7
positive function r(·) on M × R+, determined by the data 1) and 2),
and such that
g(z;w)dz =
w(b−t ·m, t)r(m, t)dmdt
Proof. We define the mapping f : M × R+ → Z by f = q ◦ b
By conditions 1 and 2, f has full rank almost everywhere. The pull-
back by f of dz is absolutely continuous with respect to dmdt, hence
f ∗(dz) = r(m, t)dmdt.
For 0 < l set wl(x, t) = w(x, t)χl(t), and let gl(z;w) be the corre-
sponding counting function. Set Il(w) =
gl(z;w)dz. A point, x ∈ Ψ,
contributes to Il(w) iff x ∈ ϕ(M× [0, l]). Under the change of variables
dz = d(q ◦ ϕ(m, t)) = r(m, t)dmdt, we have
Il(w) =
M×[0,l]
w(b−t ·m, t)r(m, t)dmdt.
In the limit l → ∞, we obtain the claim.
1.3. Special cases. We will discuss a few special cases of Proposition 1
and Proposition 2. First, the discrete version. The function gn(θ)
counts the number of visits in Y of points x ∈ Rθ during the first n
steps of their journey. Set ρk =
rk(y)dy, and Rn =
k=0 ρk. Then
ρk is the volume of Yk = T
−k(Y ) with respect to the measure η∗(dθ).
Proposition 1 yields
gn(θ)dθ = Rn.
In the continuous case the function gl(z) counts the number of visits
in M of orbits bt · x, x ∈ Rz, during the period 0 ≤ t ≤ l. Let R(l) be
the volume of the manifold Nl ⊂ Ψ with respect to the measure q
∗(dz).
Proposition 2 yields
gl(z)dz = R(l).
2. Bounds on counting functions
In this section we analyze the setting of section 1 from the measure
theoretic viewpoint. This allows us to obtain pointwise upper bounds
on counting functions in a broad spectrum of situations.
Let X, µ be a finite measure space. Let f(x; t) (for t ∈ R+) be a
family of nonnegative L1 functions on X . Set
(9) F (t) =
f(x; t)dµ(x).
8 EUGENE GUTKIN AND MICHAL RAMS
Lemma 1. For almost every x ∈ X there exists C = C(x) > 0 such
that for arbitrarily large n ∈ N there is t ≥ n satisfying f(x, t) < CF (t).
Proof. For 0 < C and n ∈ N let
Bn(C) = {x ∈ X : CF (t) < f(x; t) ∀t > n},
and set
B(C) =
Bn(C).
Integrating the inequality above, we obtain µ(Bn(C)) ≤ C
−1 for any n.
Thus µ(B(C)) ≤ C−1, and hence µ(∩C∈R+B(C)) = 0. But ∩C∈R+B(C) ⊂
X is the complement of the set of points x ∈ X satisfying the hypoth-
esis of the lemma.
Let the setting be as in Lemma 1. In addition, we suppose that
i) the functions f(x; t) are nondecreasing in t and ii) F (t) → ∞.
Lemma 2. Let ε > 0 be arbitrary. Then for almost every x ∈ X there
exists T = T (x, ε) > 0 such that for all t > T we have
(10) f(x; t) ≤ F (t)(1 + log(1 + F (t)))1+ε.
Proof. Denote by f(x; t−) (resp. F (t−)) the limits of f(x; s) (resp.
F (s)), as s → t from the left. For n ∈ N set tn = inf{t : F (t) ≥ 2
Then F (t(n+1)
−) ≤ 2F (tn). Let An ⊂ X be the set of points satisfying
the inequality
(11) f(x; t−n ) ≤
F (tn
−)(1 + log(1 +
F (tn
−)))1+ǫ.
It suffices to prove that the set
Ak has full measure. Indeed,
for x ∈ An and t ∈ [tn, tn+1) we have
f(x; t) ≤ f(x; t−n+1) ≤
F (tn+1
−)(1 + log(1 +
F (tn+1
−))1+ε
≤ F (tn)(1 + log(1 + F (tn)))
1+ε ≤ F (t)(1 + log(1 + F (t)))1+ε.
Thus, the points x ∈
Ak have the property equation (10).
If Bn ⊂ X is any sequence of sets, we set lim supn→∞Bn =
Let Bn be the complement of An inX . Then lim supn→∞Bn is the com-
plement of
Ak. It remains to prove that µ(lim supn→∞Bn) =
By Tchebysheff inequality, we have
(12) µ(Bn) ≤ 2(1 + log(1 +
F (tn
−)))−(1+ε).
COMPLEXITY, ETC 9
Set µn = µ(Bn). Suppose first that F is a continuous function. Then
F (tn
−) = F (tn) = 2
n. By equation (12)
µn ≤ 2(1 + log(1 + 2
n))−(1+ε),
hence the series
µn converges. Since
µ(lim sup
Bn) ≤
for any n0 ∈ N, the claim follows.
In general, F need not be continuous. It is thus possible that tn =
tn+1 for some n ∈ N, implying Bn = Bn+1. From the series
we drop the terms µn such that Bn = Bn−1. By equation (12), the
remaining terms satisfy
µn ≤ 2(1 + log(1 + 2
n−2))−(1+ε).
Now the preceding argument applies.
In sections 3, 5 we will apply these results in the billiard setting. In
section 3 we will estimate the integrals equation (9), hence the bounds
provided by Lemmas 1, 2 will be more specific. The propositions below
anticipate these applications.
Proposition 3. Let the setting and the assumptions be as in Lemma
2. Let 0 < ε be arbitrary.
1. Let F (t) = O(tp) for 0 < p. Then for almost every x ∈ X we have
f(x; t) = O(tp+ε).
2. Let F (t) = O(eat) for 0 < a. Then for almost every x ∈ X we have
f(x; t) = O(e(a+ε)t).
Proof. The first claim is immediate from Lemma 2 and (log t)1+ε =
o(tε). The second claim follows the same way from t1+ε = o(eεt).
For applications to the billiard map we need a counterpart of Proposi-
tion 3 for integer-valued time. We state it below. Its proof is analogous
to the proof of Proposition 3. Moreover, the discrete time case may be
formally reduced to the continuous time case. We leave details to the
reader.
Let X, µ be a finite measure space. Let f(x;n), n ∈ N be a sequence
of nonnegative L1 functions on X such that for every x ∈ X the nu-
merical sequence f(x;n) is nondecreasing. Set F (n) =
f(x;n)dµ.
Proposition 4. Let 0 < ε be arbitrary. Then the following claims
hold.
10 EUGENE GUTKIN AND MICHAL RAMS
1. Let F (n) = O(np) for 0 < p. Then for almost every x ∈ X we have
f(x;n) = O(np+ε).
2. Let F (n) = O(ean) for 0 < a. Then for almost every x ∈ X we have
f(x;n) = O(e(a+ε)n).
Remark 2. All of the bounds f(·) = O(·) in preceding propositions
are equivalent to the formally stronger bounds f(·) = o(·).
3. Counting functions for polygonal billiard
We will now apply the preceding material to the billiard dynamics.
Our billiard table will be a geodesic polygon either in the euclidean
plane R2, or the round sphere S2, or the hyperbolic plane H2. We refer
to [4], [7], and section 6 for the background.
3.1. Direction counting functions for billiard maps in euclidean
polygons. Let P ⊂ R2 be a euclidean polygon, and let T : X(P ) →
X(P ) be the billiard map. Elements of the phase space X = X(P )
are oriented geodesic segments in R2 with endpoints in ∂P . A segment
x ∈ X ending in a corner of P is singular; the element Tx is not well
defined. A billiard orbit x, Tx, . . . , T k−1x is a singular orbit of length
k if T k−1x is the first singular element in the sequence.
Assigning to x ∈ X its direction, η(x) ∈ S1, we obtain a fibration
η : X → S1 with fibers Rθ ⊂ X . See figure 1. We define the counting
function gdθ(n) for singular orbits in direction θ as the number of phase
points x ∈ Rθ that yield singular orbits of length k ≤ n.
Theorem 1. Let P ⊂ R2 be an arbitrary polygon. Let K(P ) be the
set of its corners. Let α(v) be the angle of v ∈ K(P ). Let dθ be the
lebesgue measure on S1.
Let K ⊂ K(P ). Then
gdθ(n; v)dθ =
Proof. It suffices to prove the claim for a singleton, K = {v}. Let
Y = Y (v) ⊂ X be the set of segments x ∈ X ending at v. Let dy be
the angular measure on Y . These data fit into the setting of section 1.1,
and gdθ(n; v) is the pure counting function.
Let B(z, α) be a conical beam of light with apex angle α emanating
from z ∈ R2. After reflecting in ∂P , it splits into a finite number of
beams B(zi, αi) satisfying
αi = α. The preservation of light volume
is due to the flatness of ∂P .
COMPLEXITY, ETC 11
By preceding remark, the functions rk(·) of Proposition 1 satisfy
rk(·) ≡ 1. The claim now follows from the special case of Proposition 1
considered in section 1.3.
Let p, q be the numbers of corners, obstacles in P . Let κ(P ) =
p+ 2q − 2. Thus, P is simply connected iff q = 0 iff κ(P ) = p− 2.
Corollary 1. Let P ⊂ R2 be an arbitrary polygon. Then
gdθ(n)dθ = πκ(P )n.
Proof. Follows from Theorem 1 via
v∈K(P ) α(v) = (p+ 2q − 2)π.
Figure 1. Base sets for billiard counting functions
12 EUGENE GUTKIN AND MICHAL RAMS
3.2. Position counting functions for billiard flows in euclidean
polygons. Let P ⊂ R2 be a polygon, and let bt : Ψ → Ψ be the
billiard flow. See section 6 for details. For z ∈ P and v ∈ K(P ) let
gcz(l; v) be the number of billiard flow orbits that start from z ∈ P and
wind up at v by time l. Then gcz(l) =
v∈K(P ) gcz(l; v) is the number
of singular billiard orbits of length at most l starting from z. This is
the position counting function for the billiard flow in P .
Theorem 2. Let P ⊂ R2 be a euclidean polygon, and let dz be the
lebesgue measure on P . Then for any K ⊂ K(P ) we have
(15) 2
gcz(l; v)dz =
Proof. It suffices to prove the claim for K = {v}. We view elements
of Ψ as pairs z, θ where z ∈ P is the basepoint, and θ is the direction.
Let M = {(v, θ) : (v,−θ) ∈ Ψ}. Let q : Ψ → P be the obvious
projection. Its fibers Rz are the base sets for the counting functions
gcz(l; v). See figure 1. Set w = χl. These data satisfy the assumptions
of Proposition 2, and gcz(l; v) is the pure counting function.
We set dm to be the angular measure, and compute the function
r(m, t) in equation (6). By Corollary 13 in section 6, r = tχl. Propo-
sition 2 implies the claim.
When K = K(P ), the left hand side in equation (15) is the average
of the position counting function. The argument of Corollary 1 yields
the following.
Corollary 2. Let P ⊂ R2 be an arbitrary polygon. Then
(16) 2
gcz(l)dz = πκ(P )l
3.3. Position counting functions for billiard maps in euclidean
polygons. We will now discuss two billiard map analogs of the pre-
ceding example. Let P ⊂ R2 be a euclidean polygon, and let T :
X(P ) → X(P ) be the billiard map. The phase space X = X(P )
consists of pairs (s, α) where s is the arclentgh parameter on ∂P , and
0 < α < π is the outgoing angle. See [4, 7] and section 6 for details.
An orbit x, Tx, . . . , T k−1x is singular, of (combinatorial) length k if its
last segment ends at a corner of P .
Let s ∈ ∂P , v ∈ K(P ). Define GDs(n; v) to be the set of phase
points (s, α) ∈ X whose orbits of length less than or equal to n end at
COMPLEXITY, ETC 13
v. Set
gds(n; v) = |GDs(n; v)|, gods(n; v) =
(s,α)∈GDs(n;v)
sinα.
The expressions
gds(n) =
v∈K(P )
gds(n; v), gods(n) =
v∈K(P )
gods(n; v)
are the pure position counting function and the optical position counting
function for the billiard map in P .
Let z ∈ R2 and let γ ⊂ R2 be an oriented piecewise C1 curve.
Denote by dzs the projection of the arclength form ds of γ onto the
direction perpendicular to the line from z to s ∈ γ. The integral
dzs = |opt(γ, z)| ≤ |γ| is the optical length of γ viewed from z.
Let z ∈ P . Unfolding k-segment billiard orbits emanating from z,
we obtain a set of linear segments in R2. Let ∂z(P ; k) ⊂ R
2 be the
curve traced by their endpoints. We say that ∂z(P ; k) ⊂ R
2 is the
outer boundary of P , as viewed from z, after k iterates.
Theorem 3. Let P be a euclidean polygon, and let K ⊂ K(P ) be a set
of corners. Then
gds(n; v)ds =
|∂v(P ; k)|;
gods(n; v)ds =
|opt(∂v(P, k))|.
Proof. It suffices to prove the claims for a singleton, K = {v}. Let η :
X → ∂P be the natural projection. Using the arclength parametriza-
tion, we identify ∂P with the interval [0, |∂P |] ⊂ R. For 0 ≤ s ≤ |∂P |
let Rs = η
−1(s) ⊂ X be the fiber. Then Rs are the base sets for
the counting functions gds(n; v), gods(n; v). See figure 1. Let Y =
Y (v) ⊂ X be the set of phase points whose T−1-orbits emanate from
v. The assumptions of section 1.1 are satisfied. The weight functions
are w(s, α, t) = χn(t) and wo(s, α, t) = sinα ·χn(t) for the two cases at
hand. Let ϕ be the angle parameter on Y . The measures on ∂P and
Y have densities ds and dϕ respectively.
The integrals in the right hand side of equation (3) are over the curves
∂v(P ; k), 0 ≤ k ≤ n− 1. The integrands are ds(ϕ) and sinα · ds(ϕ) =
dvs(ϕ) in respective cases.
We will need estimates on lengths and optical lengths.
14 EUGENE GUTKIN AND MICHAL RAMS
Lemma 3. For any polygon P ⊂ R2 there exist 0 < c1 < c2 < ∞ such
that for n sufficiently large
|opt(∂v(P, k))| ≤ c2n
2, c1n
|(∂v(P, k))|.
Proof. There exist positive constants d1, d2 and m0 ∈ N, such that
for any orbit γ of the billiard map with m > m0 segments, we have
d1|γ| ≤ m ≤ d2|γ| [4].
Let v ∈ K(P ). We will estimate
|opt(∂v(P, k))|, as n → ∞.
Let θ1 ≤ θ ≤ θ2 be the angular parameter for orbits emanating from v;
let r(θ) be the geometric length of the orbit. Suppose that r1 ≤ r(θ) ≤
r2. Then the optical length in question is sandwiched between the
lengths of circular arcs of radii r1, r2 of angular size θ2−θ1. By preceding
remarks, if k is sufficiently large, the bounds r1, r2 are proportional to
k. The total angular size does not depend on k. Hence, for sufficiently
large k we have linear upper and lower bounds on
v∈K |opt(∂v(P, k))|.
The other inequality follows from |opt(∂v(P, k))| ≤ |∂v(P, k)|.
3.4. Position counting functions for billiard flows in spherical
polygons. The study is analogous to the planar case discussed in sec-
tion 3.2; we will use the same notation whenever this does not lead to
confusion. We denote by dz the lebesgue measure on S2, and by α(v)
the angle of a corner of P . Set
(20) ζ(x) = 1− cosx−
Theorem 4. Let P ⊂ S2 be a geodesic polygon, and let K ⊂ K(P ).
gcz(l; v)dz =
l + ζ(l− π⌊l/π⌋)
Proof. It suffices to prove the claim when K = {v}. Let M = M(v) ⊂
Ψ be as in section 3.2, and let dα be the angular measure on it. The
assumptions 1, 3 of section 1 are satisfied; the transversality of bt ·M
and Rz may fail for at most a countable set of parameters Pex ⊂ P . See
Remark 3 in section 6. Hence, condition 2′ is fullfilled, and the results
of section 1.2 hold. The function gcz(l; v) is a pure counting function.
The claim now follows from Proposition 2 and Corollary 13.
Let κ(P ) be as in section 3.1.
COMPLEXITY, ETC 15
Corollary 3. Let P ⊂ S2 be an arbitrary polygon. Then
gcz(l)dz = (κ(P )π + area(P ))
l + ζ(l − π⌊l/π⌋)
Proof. For a spherical polygon we have
v∈K(P ) α(v) = area(P ) +
κ(P )π. Substitute this into equation (21).
3.5. Position counting functions for billiard flows in hyper-
bolic polygons. Our treatment and our notation are modelled on
section 3.4. We denote by dz the lebesgue measure on H2, and by α(v)
the angles of corners.
Theorem 5. Let P ⊂ H2 be a geodesic polygon, and let K ⊂ K(P ).
gcz(l; v)dz =
cosh l.
Proof. We repeat verbatim the proof of Theorem 4, and use claim 2 in
Corollary 13.
Let κ(P ) be as in section 3.1.
Corollary 4. Let P ⊂ H2 be a polygon. Then
gcz(l)dz = (κ(P )π − area(P )) cosh l.
Proof. Repeat the argument of Corollary 3; use the formula
v∈K(P ) α(v) =
κ(P )π− area(P ) relating the angles and the area of geodesic polygons
in H2.
4. Relating partial complexities and counting functions
In this section we establish a framework that will allow us to study
the complexity of a wide class of dynamical systems. Our motivation
comes from the billiard dynamics. In fact, polygonal billiard is the
target of applications for our results. The framework is more general,
however. The following observations served as our guiding principles.
First, natural partitions of the billiard-type systems are geared to the
singularities. Second, the billiard dynamics satisfies a certain convexity
property that is instrumental in the study of complexity. These princi-
ples are manifest in the framework of piecewise convex transformations
There are two approaches to the billiard dynamics: The billiard flow
and the billiard map. See section 6. The framework of piecewise convex
16 EUGENE GUTKIN AND MICHAL RAMS
transformations is geared to the billiard map. We begin by establishing
its counterpart for flows.
4.1. Piecewise convex transformations and piecewise convex
flows. A piecewise convex transformation is a triple (X,Γ, T ), whereX
is a two-dimensional convex cell complex, Γ ⊂ X is the graph formed by
the union of one-cells, and T : X → X is an invertible map, regular on
the two-cells of the complex, and compatible with the convex structure
Let Ψ be a compact manifold, with boundary and corners, in general.
Let bt : Ψ → Ψ be a flow, possibly with singularities; let X ⊂ Ψ be
a cross-section. We will assume that the singular set of the flow is
contained in X . For z ∈ X let τ+(z), τ−(z) be the times when z ∈ Ψ
first reaches X under bt, b−t for 0 < t. We assume that for any z ∈ Ψ\X
there is 0 < ε = ε(z) such that bt(z) is regular for |t| < ε.
A piecewise convex flow is determined by the following data: A flow,
bt : Ψ → Ψ, a cross-section, X ⊂ Ψ, and the structure of a convex cell
complex on X , compatible with the poincare map. Billiard flows for
polygons on surfaces of constant curvature are piecewise convex flows
4.2. Partial complexities for maps and flows. Let (X,Γn, T
n) be
the iterates of a piecewise convex transformation (X,Γ, T ).4 Let F (Γn)
be the finite set of open faces of Γn; these are the continuity regions for
T n. The function f(n) = |F (Γn)| is the (full) complexity of (X,Γ, T ).
Let R ⊂ X be a closed subset. Set
FR(n) = {A ∈ F (Γn) : A ∩R 6= ∅}.
Definition 1. The function fR(n) = |FR(n)| is the partial complexity
of the piecewise convex transformation (X,Γ, T ) based on the subset
Let bt : Ψ → Ψ be a piecewise convex flow, and let R ⊂ Ψ be a closed,
convex set transversal to the flow. For 0 < l let OR(l) be the set of
regular flow orbits of length l starting from R. Let α0, α1 ∈ OR(l). A
homotopy is a continuous family of regular orbits αp ∈ OR(l), 0 ≤ p ≤
1, interpolating between α0, α1. We will say, for brevity, that the orbits
α0, α1 are R-homotopic. We denote by HR(l) the set of R-homotopy
classes.
Definition 2. The function hR(l) = |HR(l)| is the partial complexity
(based on R) of the piecewise convex flow bt : Ψ → Ψ.
4 They are piecewise convex transformations as well [7].
COMPLEXITY, ETC 17
Figure 2. Removing a vertex in a graph
4.3. Partial complexities and counting functions. In what fol-
lows we assume that R ⊂ Ψ is a convex graph without isolated vertices.
For x ∈ R its valence val(x) is the number of edges of x minus one.
In particular, if x is an interior point of an edge, then val(x) = 1. Set
val(R) = maxx∈R val(x). We endow R \ {x} with the graph structure
where x is replaced by 1+val(x) vertices; each of them is the endpoint
of a unique edge. If x, y, z, . . . ∈ R are distinct points, then the induc-
tively defined graph structure on R without x, y, z, . . . does not depend
on the order of removing these points. We will denote this graph by
R \ {x, y, z, . . .}. See figure 2 for an illustration.
Let E(R) and V (R) be the sets of edges and vertices, and let c(R)
be the number of connected components of the graph. Let hi = hi(R)
be the betti numbers of R, and set χ(R) = |V (R)| − |E(R)|. Then
c(R) = h0, χ(R) = h0 − h1.
Lemma 4. Let R be a finite graph, and let x1, . . . , xp ∈ R be distinct
points. Then
(25) χ(R) +
val(xi) ≤ c(R \ {x1, . . . , xp}) ≤ c(R) +
val(xi).
If R is a forest, then the bound on the right in equation (25) becomes
an equality.
18 EUGENE GUTKIN AND MICHAL RAMS
Proof. It suffices to prove the claims when R is connected, and we
remove a single vertex, x. Equation (25) becomes
(26) χ(R) + val(x) ≤ c(R \ {x}) ≤ c(R) + val(x).
We have |V (R \ {x})| = |V (R)| + val(x), |E(R \ {x})| = |E(R)|, and
χ(R\{x}) = χ(R)+val(x). Equivalently, we have χ(R\{x}) = h0(R)+
val(x)−h1(R) and h0(R\{x}) = h0(R)+val(x)+(h1(R \ {x})− h1(R)).
The former (resp. latter) identity implies the left (resp. right) inequal-
ity in equation (26).
When R is a tree, we have c(R \ {x}) = c(R) + val(x), and the
remaining claim follows.
We will introduce counting functions for singular orbits of the billiard
map and the billiard flow.
By definition, an orbit α = {bt(z), 0 ≤ t ≤ l}, does not pass through
singular points in Ψ. It is regular if it does not contain any singu-
lar points in Ψ; it is singular if one of its endpoints is singular. The
set SR(l) of singular orbits of length at most l, based in R, is finite.
The quantities gcR(l) = |SR(l)| and gdR(n) = |R ∩ Γn| are the count-
ing functions for singular orbits based in R for the flow and the map
respectively.
Now we will relate partial complexities and counting functions. We
do this for a piecewise convex flow bt : Ψ → Ψ and for a piecewise
convex transformation (X,Γ, T ). In both cases the partial complexity is
based on a 1-dimensional subset, say R. Recall that gcR(l), gdR(n) are
the respective counting functions, and hR(l), fR(n) are the respective
complexities. We will refer to these situations as the continuous case
and the discrete case respectively.
Proposition 5. Let the setting be as above. Then the following state-
ments hold.
1. In the continuous case there exist h0 ∈ N and l0 ∈ R+ such that
hR(l) = h0 + gcR(l) for l0 ≤ l. 2. In the discrete case there exist
f0, n0 ∈ N such that for n0 ≤ n we have fR(n) = f0 + gdR(n).
Proof. In both cases the graph R is equipped with a tower of finite sets,
say X(l) and Xn respectively. Let X∞ ⊂ R be their union. We will
compare the number of connected components of graphs R\X(l), R\Xn
with the cardinalities of these sets.
We consider the discrete case, leaving the continuous case to the
reader. Let m < n be any pair of natural numbers. By (the proof of)
COMPLEXITY, ETC 19
Lemma 4,
c(R \Xn)− c(R \Xm) = [h1(R \Xn)− h1(R \Xm)] +
x∈Xn\Xm
val(x).
We have h1(R \ Xn) ≤ h1(R \ Xm); the inequality holds iff Xn \
Xm breaks cycles in R \ Xm. Since the sequence h1(R \ Xk) ∈ N is
nonincreasing, it stabilizes. Thus, there exists n1 ∈ N such that for
n1 ≤ m < n we have h1(R \Xn) = h1(R \Xm).
The set of points x ∈ R satisfying 1 < val(x) is finite. Thus, there
exists n2 ∈ N such that if n2 ≤ k and x ∈ X∞ \Xk, then val(x) = 1.
Set n0 = max(n1, n2). Then for n0 ≤ m < n the above equation
yields c(R \Xn)− c(R \Xm) = |Xn \Xm|. Specializing to m = n0, we
obtain fR(n) = (fR(n0)− gdR(n0)) + gdR(n).
5. Bounds on partial complexities for the billiard
We will use the preceding material to derive bounds on partial com-
plexities for the polygonal billiard.
5.1. Direction complexities for billiard maps in euclidean poly-
gons. We use the setting and the notation of section 3.1. For a polygon
P and a direction θ, we denote by fdθ(n) the partial complexity with
base Rθ. This is the complexity in direction θ.
Corollary 5. For lebesgue almost all directions θ there is C = C(θ)
and there are arbitrarily large n such that fdθ(n) ≤ Cn.
Proof. Each Rθ is a convex graph in the phase space [7]. By Lemma 1
and Corollary 1, the counting functions gdθ(n) have the desired proper-
ties. By the second claim of Proposition 5, the directional complexities
do as well.
Corollary 6. For any ε > 0 and almost every direction θ we have
fdθ(n) = O(n
1+ε).
Proof. The proof goes along the lines of the proof of Corollary 5. In-
stead of Lemma 1, we use Proposition 4 (the first claim).
5.2. Position complexities for billiard flows in euclidean poly-
gons. Let P be a euclidean polygon, and let z ∈ P be any point. We
consider the billiard flow in P , and use the setting of section 3.2. Thus,
gcz(l) is the position counting function for orbits emanating from z. We
denote by hz(l) the corresponding partial complexity.
Corollary 7. For almost every point z there is a positive number C =
C(z) such that hz(l) ≤ Cl
2 for arbitrarily large l.
20 EUGENE GUTKIN AND MICHAL RAMS
Proof. The sets Rz satisfy the assumptions of section 4. The claim
follows from Lemma 1, Corollary 2 and the continuous case in Propo-
sition 5.
Corollary 8. For any ε > 0 and almost every z ∈ P we have hz(l) =
O(l2+ε).
Proof. The proof is similar to the preceding argument, and we use the
first claim in Proposition 3 instead of Lemma 1.
5.3. Position complexities for billiard maps in euclidean poly-
gons. This is the billiard map analog of the preceding example. Let
P be a euclidean polygon, and let s ∈ ∂P . We use the setting of sec-
tion 3.3. There we have defined the counting functions gds(n), gods(n).
Let fs(n) be the partial complexity corresponding to gds(n). This is
the position complexity for the billiard map.
Corollary 9. Let P ⊂ R2 be a polygon such that
k=1 |∂v(P ; k)|
has a quadratic upper bound.5 Then for almost all s ∈ ∂P we have
fs(n) = O(n
2+ε) for any 0 < ε.
Proof. The sets Rs ⊂ X satisfy the assumptions of section 4. We use
Theorem 3, Lemma 3, and apply Proposition 5.
The estimate of Corollary 9 on fs(n) is conditional, because in gen-
eral we have no efficient upper bound on
|∂v(P ; k)|.
5.4. Position complexities for billiard flows in spherical poly-
gons. We use the setting of section 3.4. For a spherical polygon,
P ⊂ S2, and z ∈ P , let hz(l) be the position complexity.
Corollary 10. For almost every point z ∈ P there is C = C(z) and
there are arbitrarily large l such that hz(l) ≤ Cl.
Proof. The sets Rz satisfy the assumptions of section 4. We use Lemma 1,
Corollary 3, and Proposition 5.
Corollary 11. For any ε > 0 and almost every z ∈ P we have hz(l) =
O(l1+ε).
Proof. See the proof of Corollary 8.
5This holds if P is a rational polygon [11].
COMPLEXITY, ETC 21
5.5. Position complexities for billiard flows in hyperbolic poly-
gons. This material is the hyperbolic plane counterpart of section 3.2,
and we use the setting of section 3.5.
Corollary 12. Let P ⊂ H2 be a geodesic polygon, let z ∈ P , and let
hz(l) be the position complexity. Then for almost every point z ∈ P we
have hz(l) = O(e
(1+ε)l).
Proof. We verify that the sets Rz satisfy the assumptions of section 4,
and mimick the proof of Corollary 8; we use Corollary 4, Proposition 3,
and the continuous case of Proposition 5.
6. Appendix: Covering spaces for polygonal billiards
Let M be a simply connected surface of constant curvature, and let
P ⊂ M be a connected geodesic polygon. We normalize the metric so
that the curvature is either zero (M = R2), or one (M = S2), or minus
one (M = H2).
Let A be the set of sides in P . We will denote its elements by a, b, . . . .
For a side, say a ∈ A, let sa ∈ Iso(M) be the corresponding geodesic
reflection. We associate with P a Coxeter system (G,A) [2]. We denote
by σa, σb, · · · ∈ G the elements corresponding to a, b, . . . ∈ A. They
generate G. The defining relations are σ2a = 1 and (σaσb)
n(a,b) = 1;
the latter arise only for the sides a, b with a common corner if the
angle, θ(a, b), between them is π-rational. In this case n(a, b) is the
denominator of θ(a, b)/π. Otherwise n(a, b) = ∞.
To any “generalized polyhedron” P corresponds a topological space
C endowed with several structures, and a Coxeter system [2]. Our
situation fits into the framework of [2], and we apply its results. First,
C is a differentiable surface. Second, C is tiled by subsets Pg, g ∈ G,
labelled by elements of the Coxeter group G; we call them the tiles, and
identify Pe with P . The group G acts on C properly discontinuously,
preserving the tiling: g · Ph = Pgh.
Since Pe is identified with P ⊂ M , it inherits from M a riemann-
ian structure. The action of G is compatible with this structure, and
extends it to all of C. This riemannian structure generally has cone
singularities at vertices of the tiling C = ∪g∈GPg.
6 Around other points
this riemannian structure is isometric to that of M ; in particular, ex-
cept for cone points, C has constant curvature. The group G acts on C
by isometries.
6Each vertex, v, corresponds to a corner of P . The metric at v is regular iff the
corner angle is π/n, n = 2, 3, . . . .
22 EUGENE GUTKIN AND MICHAL RAMS
Definition 3. The space C endowed with the riemannian structure,
the isometric action of G and the G-invariant tiling C = ∪g∈GPg is the
universal covering space of the geodesic polygon P ⊂ M .
If X is a riemannian manifold (with boundary and singularities,
in general), we denote by TX = ∪x∈XTxX its unit tangent bundle.
The classical construct of geodesic flow, GtX : TX → TX , extends to
manifolds with boundaries and singularities. In particular, GtX makes
sense when X = M,P , or C. Another classical construct, the expo-
nential map, also extends to our situation. For x ∈ X as above, and
(v, t) ∈ TxX × R+, we set expX(v, t) ∈ X be the base-point of G
X(v).
We will use the notation expxX to indicate that we are exponentiating
from the point x. If X is nonsingular, then expxX : TxX × R+ → X is
a differentiable mapping. For X with singularities, such as our P and
C, the maps expxX are defined on proper subsets of TxX × R+; these
subsets have full lebesgue measure. Generally, the maps do not extend
by continuity to all of TxX × R+.
Let X, Y be nonsingular riemannian manifolds of the same dimen-
sion; let ϕ : X → Y be a local isometry. It induces a local dif-
feomorphism Φ : TX → TY commuting with the geodesic flows:
Φ ◦GtX = G
Y ◦Φ. The exponential maps commute as well: ϕ ◦ exp
Y ◦ dxϕ. These relationships hold, in particular, for coverings of
nonsingular riemannian manifolds. Suitably interpreted, they extend
to (branched) coverings of riemannian manifolds with boundaries, cor-
ners, and singularities. In our case X = C, while Y = M , or Y = P .
We will now define the mappings f : C → P, F : TC → TP and
ϕ : C → M, Φ : TC → TM .
The identification Pe = P defines f, ϕ on Pe. To extend them to all
of C, we use the tiling C = ∪g∈GPg and the actions of G on C and M .
In order to distinguish between these actions, we will denote them by
g · x and g(x) respectively. Then there is a unique x ∈ Pe such that
z = g · x. We set f(z) = x ∈ P and ϕ(z) = g(x) ∈ M . By basic
properties of Coxeter groups [2], the mappings f, ϕ are well defined.
Moreover, f : C → P and ϕ : C → M are the unique G-equivariant
mappings which are identical on Pe.
7 By construction, both mappings
are continuous; they are diffeomorphisms in the interior of each tile,
Pg ⊂ C, and on the interior of the union of any pair of adjacent tiles.
The potential locus of non-differentiability for both f and ϕ is the
set V of vertices in the tiling C = ∪g∈GPg. We have V = f
−1(K(P ))
where K(P ) is the set of corners of P . By equivariance, ϕ(V ) =
7The action of G on P is trivial.
COMPLEXITY, ETC 23
∪g∈Gg(K(P )) ⊂ M .
8 There are two kinds of points in V : vertices
coming from the corners of P with π-rational and π-irrational angles.
Their cone angles are integer multiples of 2π and are infinite respec-
tively. Vertices v ∈ V with cone angle 2π are, in fact, regular points
in C, and the mappings f, ϕ are both regular there. Around a vertex
v with cone angle 2kπ > 2π the mapping ϕ is differentiable, but not a
diffeomorphism; it is locally conjugate to z 7→ zk. Near such a vertex,
ϕ is a branched covering of degree k. At a vertex with infinite cone
angle, ϕ has infinite branching.
Remark 3. The set ϕ(V ) ⊂ M is countable. (It is finite iff the
group generated by geodesic reflections in the sides of P is a finite
Coxeter group. Typically, ϕ(V ) ⊂ M is a dense, countable set.)
Let M = S2, and let z 7→ z′ denote the antipodal map. Set F =
P ∩ (ϕ(V ) ∪ (ϕ(V ))′). Points of F are exceptional, in the following
sense. Let z ∈ P be such that the beam Rz of billiard orbits emanat-
ing from z contains a sub-beam focusing at a corner of P . Then z ∈ F .
This follows from Proposition 6 below.
Thus, F contains all points z ∈ P for which the transversality as-
sumption in Condition 2 of section 1.2 fails. Since F is countable, the
set of exceptional parameters has measure zero, and Condition 2′ is
satisfied. See Remark 1 in section 1.
Furthermore, the mappings f and ϕ are local isometries. They are
isometries on every tile Pg ⊂ C; we have f(Pg) = P , ϕ(Pg) = g(P ) ⊂
M . Let g · a be a side of Pg, let h = σag and let Ph be the adjacent
tile. The maps f : Pg → P, Ph → P and ϕ : Pg → g(P ), Ph → h(P ) are
coherent around the common (open) side g · a. The map f is never an
isometry on Pg ∪Ph; for ϕ this is the case iff the interiors of g(P ), h(P )
are disjoint in M . The latter generally fails for nonconvex P .
By coherence of f and ϕ across the sides separating adjacent tiles,
we lift them to the tangent bundles, obtaining the mappings of unit
tangent bundles F : TC → TP , Φ : TC → TM , which are also defined
on vectors based at the vertices of the tiling C = ∪g∈GPg. Let v be a
vertex, and let α be the angle of the corner f(v) ∈ K(P ). Then Φ :
TvC → Tϕ(v)M is m-to-1 if α = mπ/n and ∞-to-1 if α is π-irrational.
The geodesics γ(t) in C cannot be further extended (generally) once
they reach a vertex. All other geodesics in C are defined for −∞ < t <
8 The representation M = ∪g∈Gg(P ) is not a tiling, in general.
24 EUGENE GUTKIN AND MICHAL RAMS
Using the inclusion P ⊂ M , we identify TP with the subset of TM
consisting of M-tangent vectors with base-points in P , and directed in-
ward. Any v ∈ TP defines the billiard orbit in P , β(t) = expP (tv), 0 ≤
t, and the geodesic in M , γ(t) = expM(tv), 0 ≤ t. They are related
by the canonical unfolding of billiard orbits. This is an inductive pro-
cedure which replaces the consecutive reflections about the sides of P
by consecutive reflections of the “latest billiard table” g(P ) about the
appropriate side, yielding the next billiard table h(P ), and continuing
the geodesic straight across the common side of g(P ) and h(P ). See [4]
in the planar case and [7], section 3.1, in the general case. Let x ∈ P
and let v ∈ TxP . We denote by βv (resp. γv) the billiard orbit in P
(resp. the geodesic in M) that emanates from x in the direction v. The
unfolding operator, Ux : βv 7→ γv, preserves the parametrisations.
Proposition 6. Let x ∈ P, v ∈ TxP . Identify P and Pe ⊂ C and let
x ∈ Pe, v ∈ TxC be the corresponding data. Then for t ∈ R+ we have
(27) Ux(expP (v, t)) = ϕ(expC(v, t)).
Proof. We will freely use the preceding discussion. As t ∈ R+ goes to
infinity, expP (v, t) runs with the unit speed along a billiard orbit in P .
The curve exp
(v, t) is the geodesic in C defined by the data (x, v), and
ϕ(exp
(v, t)) is the geodesic in M emanating from x in the direction
v. The billiard orbit in P and the geodesic in M are related by the
unfolding operator.
For x ∈ P let ExP = TxP ×R+ be the full tangent space (or the full
tangent cone) at x. If S ⊂ TxP is a segment, let ESxP = S × R+ be
the corresponding subcone. We use the analogous notation for x ∈ C
or x ∈ M . In polar coordinates (t, θ) in R2 the lebesgue measure on
ExP is given by the density tdtdθ.
Corollary 13. Let x ∈ P ⊂ M be arbitrary, and let expxP : ExP → P
be the exponential mapping. The pull-back by expxP of the lebesgue
measure on P to ExP is the smooth measure with the density dν(t, θ).
1. When M = R2, we have dν = tdtdθ.
2. When M = H2, we have dν = sinh tdtdθ.
3. When M = S2, we have dν = | sin t|dtdθ.
Proof. By Proposition 6, the measure in question coincides with the
pullback to the tangent space ExM of the riemannian measure on M
by the exponential map ExM → M . The latter is well known.
We point out that the preceding material has a billiard map version.
We will briefly discuss it now. Let β(t) = (z(t), θ(t)), t ∈ R, be an orbit
COMPLEXITY, ETC 25
of the billiard flow. We obtain the corresponding billiard map orbit
βd(k), k ∈ Z, by restricting β(t) to the consecutive times tk such that
z(tk) ∈ ∂P . The correspondence β(·) 7→ βd(·) is invertible. This allows
us to formulate the billiard map versions of the universal covering space,
the lifting of billiard map orbits to the universal covering space, and the
relationship between the liftings and the unfoldings, à là Proposition 6.
Since we are not directly using this material in the body of the paper,
we spare the details.
References
[1] J. Cassaigne, P. Hubert and S. Troubetzkoy, Complexity and growth for polyg-
onal billiards, Ann. Inst. Fourier 52 (2002), 835 – 847.
[2] M.W. Davis, Groups generated by reflections and aspherical manifolds not cov-
ered by Euclidean space, Ann. Math. 117 (1983), 293 – 324.
[3] G. Galperin, T. Krüger and S. Troubetzkoy, Local instability of orbits in polyg-
onal and polyhedral billiards, Comm. Math. Phys. 169 (1995), 463 – 473.
[4] E. Gutkin, Billiards in polygons, Physica 19 D (1986), 311 – 333.
[5] E. Gutkin, Billiard dynamics: A survey with the emphasis on open problems,
Reg. & Chaot. Dyn. 8 (2003), 1 – 13.
[6] E. Gutkin and N. Haydn, Topological entropy of polygon exchange transfor-
mations and polygonal billiards, Erg. Theo. & Dyn. Syst. 17 (1997), 849 –
[7] E. Gutkin and S. Tabachnikov, Complexity of piecewise convex transforma-
tions in two dimensions, with applications to polygonal billiards on surfaces of
constant curvature, Moscow Math. J. 6 (2006), 673 – 701.
[8] E. Gutkin and S. Troubetzkoy, Directional flows and strong recurrence for
polygonal billiards, Pitman Res. Not. Math. 362 (1996), 21 – 45.
[9] P. Hubert, Complexité de suites définies par des billards rationnels, Bull. Soc.
Math. Fr. 123 (1995), 257 – 270.
[10] A. Katok and B. Hasselblatt, Introduction to the Modern Theory of Dynamical
Systems, Cambridge University Press, Cambridge 1995.
[11] H. Masur, The growth rate of trajectories of a quadratic differential, Erg. Theo.
& Dyn. Syst. 10 (1990), 151 – 176.
IMPA, Rio de Janeiro, Brasil and UMK, Torun, Poland; IMPAN,
Warszawa, Poland
E-mail address : gutkin@impa.br,gutkin@mat.uni.torun.pl;rams@impan.gov.pl
	Introduction and overview
	1. Averages of counting functions
	1.1. Discrete dynamics
	1.2. Continuous dynamics
	1.3. Special cases
	2. Bounds on counting functions
	3. Counting functions for polygonal billiard
	3.1. Direction counting functions for billiard maps in euclidean polygons
	3.2. Position counting functions for billiard flows in euclidean polygons
	3.3. Position counting functions for billiard maps in euclidean polygons
	3.4. Position counting functions for billiard flows in spherical polygons
	3.5. Position counting functions for billiard flows in hyperbolic polygons
	4. Relating partial complexities and counting functions
	4.1. Piecewise convex transformations and piecewise convex flows
	4.2. Partial complexities for maps and flows
	4.3. Partial complexities and counting functions
	5. Bounds on partial complexities for the billiard
	5.1. Direction complexities for billiard maps in euclidean polygons
	5.2. Position complexities for billiard flows in euclidean polygons
	5.3. Position complexities for billiard maps in euclidean polygons
	5.4. Position complexities for billiard flows in spherical polygons
	5.5. Position complexities for billiard flows in hyperbolic polygons
	6. Appendix: Covering spaces for polygonal billiards
	References
