\documentclass[11pt]{amsart}
\newtheorem{cor}{Corollary}[section]
\newtheorem{df}{Definition}[section]
\newtheorem{prop}{Proposition}[section]
\newtheorem{thm}{Theorem}%[section]
\newtheorem{lmm}{Lemma}[section]
\newenvironment{pf}{ Proof:}{ $\triangle$ \newline}
\newtheorem{rem}{Remark}%[section]
\newtheorem*{thm6}{Theorem 6}%[subsection]
\newtheorem*{thm4}{Theorem \ 4}%[subsection]
\pagestyle{plain}
\def\Bbb#1{\mbox{\Blackbb #1}}
\def\frak#1{\mbox{\frakfurt #1}}
\title{Uniform estimates on the number of collisions
in semi-dispersing billiards.}
% Information for first author
\author{ D. Burago}
% Address of record for the research reported here
\address{ Department of Mathematics,
The Pennsylvania State University, University Park, PA 16802 }
% Current address
%\curraddr{Department of Mathematics and Statistics,
%Case Western Reserve University, Cleveland, Ohio 43403}
\email{burago@math.psu.edu}
% \thanks will become a 1st page footnote.
\thanks{The first author is partially supported by the NSF Grant DMS
???. }
% Information for second author
\author{S. Ferleger}
\email{ferleger@math.psu.edu}
% Information for third author
\author{A. Kononenko}
\email{avk@math.psu.edu}
\begin{document}
\newfont{\Blackbb}{msbm10 scaled \magstep 0}
\newfont{\frakfurt}{eufm10 scaled \magstep 0}
\begin{abstract}
We use the methods of non-standard Riemannian geometry to obtain
complete
solutions of two classic billiard problems:
1. We establish
local uniform estimates on the number of collisions in non-degenerate
semi-dispersing billiards (moreover, our results apply to billiards
on arbitrary manifolds).
2. We find an explicit uniform estimate on the maximal possible number
of
collisions, in the infinite period of time, in an arbitrary system of
hard
spheres in empty space, in terms of the number of spheres, their masses
and
radii.
Our methods are based on the construction of a certain Alexandrov
space of
curvature bounded from above which geodesics naturally correspond to
the
trajectories of the billiard flow.
\end{abstract}
\maketitle
\section{Introduction.}
Estimating the number of collisions in a neighborhood of
a given point is a central problem in the
theory of billiard systems. Moreover,
the existence of a uniform estimate on the number of collisions is
related to
various important properties of a billiard system. For example,
the Sinai-Chernov formulas for the metric entropy of billiards are
proved under
the assumption that such an estimate exists (\cite{chernov-entropy},
\cite{sinai-entropy}).
It is quite obvious that if the boundary of the billiard has any
concave
parts then a trajectory can have arbitrarily many collisions in a
neighborhood of a ``point of concavity,'' and sometimes even infinitely
many
collisions (see, for example, \cite{vaserstein}). Therefore, the class
of billiards for which
uniform estimates are possible are the semi-dispersing billiards, which
have been studied extensively
in the numerous works (see the review in \cite{dynamicalsystems-2}).
The most
important examples of semi-dispersing billiards are the billiards that
correspond to hard balls gas models.
Vaserstein (1979, \cite{vaserstein}) and Galperin (1981,
\cite{galperin})
proved that in semi-dispersing billiards any trajectory has only
finitely
many collisions in any finite period of time.
Sinai (1978, \cite{sinai-angle}) proved the existence of a uniform
estimate
for billiards inside polyhedral angles, and pointed out that his
results should also hold for
semi-dispersing billiards in a neighborhood of a point $x$ with linearly
independent normals to the ``walls'' of the billiard at $x$ (see the
remark at the end of \cite{sinai-angle}).
In this paper we deal with semi-dispersing billiards
on arbitrary manifolds. All our results apply to the usual
billiards in $\Bbb{R}^k$ and $\Bbb{T}^k$.
First we prove that for semi-dispersing billiards on arbitrary
manifolds any
trajectory has only a finite number of collisions in a finite period of
time.
Then we establish local uniform estimates for such billiards under a
mild
non-degeneracy condition. We also give effective estimates on the
maximal number
of collisions and the size of the neighborhood in which they may occur
in terms
of the non-degeneracy condition and some
geometric properties of the manifold.
Some non-degeneracy condition is necessary to prohibit obvious
counter-examples.
We believe that our condition is not only sufficient but also necessary
for the
existence of a uniform estimate, and we plan to prove it in a
forthcoming paper.
In particular, our condition is always satisfied for a system of hard
balls in
empty space for which other more ``natural'' conditions, as, for
example, the
condition on the normals to the ``walls'' to be in the general position,
are
known to fail. For a system of balls in a jar with concave walls our
non-degeneracy condition is satisfied except for some special sets of
radii,
when it is possible to ``squeeze the balls tightly between the walls.''
Actually, it is known that in those situations the system may have
arbitrarily
many collisions locally.
As an application, we consider the systems of hard balls in empty
space. We
obtain a global uniform estimate on the maximal possible number of
collisions,
in the infinite time interval $(-\infty, \infty),$ for
hard balls systems in empty space, in terms of masses, radii and the
number
of balls. In spite of the fact that the finiteness of the number of
collisions
in such a system has been known for a long time (due to Vaserstein
(1979, \cite{vaserstein}) and Galperin (1981, \cite{galperin}) and also,
much
later, an alternative proof by Illner (1988, \cite{illner})), uniform
estimates
on the number of collisions were obtained only for the system of three
balls
of equal radii (by Thurston and Sandri (1964, \cite{thurston})) and for
systems of particles (balls of zero radius) on a line (by Galperin
(1981,
\cite{galperin})). \footnote{Notice that a system of particles
corresponds to a
billiard system only if the particles are on a line. In a higher
dimensional
space its behavior is very different from the balls of non-zero radii
(for
example, the future of the system is not uniquely determined by the
initial
conditions). Recently, however, Semenovich and Vaserstein
\cite{semenovich}
obtained explicit estimates on the number of collisions and some other
important results for systems of particles in $\Bbb{R}^k$ for arbitrary
$k.$}
Although this paper deals with ``dynamical'' and ``billiard'' types
of problems, our methods are purely geometrical. The gist of the
geometrical counterpart of our arguments is the following.
Consider a collection of Riemannian triangles with concave sides and
curvature bounded from above. Assume that one glues them along isometric
sides so that, at every vertex, the shortest homotopically non-trivial
loop in the link is no shorter than $2\pi$ (in angular metric). Then
it is known that the resulting intrinsic metric space is also (locally)
an Alexandrov space of curvature bounded from above. In this paper we
prepare all
necessary tools for generalizing this statement to higher dimensions.
In a forthcoming paper \cite{burago-entropy} we plan to address this
geometric problem, as well as to show some other dynamical
applications of our methods. We glue together finitely many copies of a
given
billiard and get a certain natural space which in a sense eliminates
the
discontinuity of the billiard flow. We obtain some estimates for
the topological entropy of a non-degenerate semi-dispersing billiard
$B.$ In
particular, we show the finiteness of the topological entropy for the
time-one
map. For the first-return map to the boundary we prove the finiteness of
the
topological entropy for non-degenerate semi-dispersing billiards with a
``finite
horizon'' (i.e. such billiards that the length of geodesics in $B$ is
bounded). Note that for billiards with ``infinite horizon''
the first-return map may have infinite
topological entropy (for example, the ``Lorentz gas,''
\cite{chernov-topentropy}).
\section{Summary of Results.}
\label{sec-construction}
Let $M$ be an arbitrary $C^2$ Riemannian manifold without boundary,
with bounded sectional
curvature and with the injectivity radius $r>0$. Consider a collection
of $n$
geodesically convex subsets ({\bf walls}) $B_i \subset M, i=1,\ldots,n$
of $M$, such that
their boundaries are $C^1$ submanifolds of codimension one. Let
$B=M\backslash(\bigcup_{i=1}^n{Int(B_i)}),$ where $Int(B_i)$ denotes the
interior
of the set $B_i.$ A semi-dispersing billiard flow (or a semi-dispersing
billiard system) acts on a certain subset of the unit tangent bundle to
$B$
(see, for example, \cite{dynamicalsystems-2} for the rigorous
definitions). The
projections of the orbits of that flow to $B$ are called the billiard
trajectories and correspond to free motions of particles inside $B.$
Namely, the particle moves inside the set $B$ with unit speed along a
geodesic until it reaches one of the sets $B_i$ ({\bf collision}) where
it
reflects according to the law ``the angle of incidence is equal to the
angle of
reflection.'' If it reaches one of the sets $B_i \bigcap B_j, i \neq j,$
the
trajectory is not defined after that moment. For any two points $X$, $Y$
of a
trajectory $T$ we will denote the piece of the trajectory between $X$
and $Y$
by $T(X,Y)$ and its length by $|T(X,Y)|.$
The following result is a variable curvature counter-part of the results
of
Vaserstein \cite{vaserstein} and Galperin \cite{galperin} and is an easy
corollary of our Comparison Lemma.
\begin{thm} \label{thm-finiteness} For any
trajectory the number of collisions during any finite time interval is
finite.
\end{thm}
An immediate corollary of Theorem~\ref{thm-finiteness} is that a
trajectory of
any point can be defined for all $t \in (-\infty,\infty)$ as long as it
does not
intersect $B_i \bigcap B_j, i \neq j.$
Now we introduce a non-degeneracy condition under which we establish
the
existence of uniform local estimates. This condition is weaker than
other non-degeneracy conditions that were considered in the
local estimate problem. Moreover, it has the important advantage of
not being
intrinsically local which, in particular, allows us to solve the global
problem
for hard balls (Section~\ref{sec-balls}).
The non-degeneracy of $B$ in a neighborhood of $x \in B$ follows, in
particular, from the following local condition: for any $I \subset
\{1,\ldots,n \}$ the intersection of the tangent cones to $B_i \bigcap
B,$ $i \in I$ at $x$ is equal to the tangent cone to $\bigcap_I (B_i
\bigcap B).$
\begin{df}
A billiard table $B$ is {\bf non-degenerate} in a subset $U\subset M$
(with constant $C>0$),
if for any
$I \subset \{1,\ldots,n \}$ and for any $y \in (U \bigcap B )\backslash
(\bigcap_{j \in I} B_j),$
$$ \max_{k \in I} \frac{dist(y,B_k)}{dist(y, \bigcap_{j \in I} B_j)}
\geq C,$$
whenever $\bigcap_{j \in I} B_j $ is non-empty.
\end{df}
Roughly speaking, it means that if a point is $d$-close to all the walls
from $I$ then it is $Cd$-close to their intersection.
We will say that B is {\bf non-degenerate} if there exist $\delta>0$ and
$C>0$
such that $B$ is non-degenerate, with constant $C,$ in any
$\delta$-ball.
>From here on out we denote by $K,r,n$ and $C$ the upper bound
on the curvature of $M$, its injectivity radius, the number of walls
$B_i$ and
the constant of non-degeneracy, respectively.
We will prove the following
\begin{thm}
\label{thm-2}
Let a semi-dispersing billiard $B $ be non-degenerate in an open
neighborhood
$U \subset M$ of $x \in U$. Then there exist a neighborhood $U_x$ of
$x$ and a
number $P_x$ such that every billiard trajectory entering $U_x$ leaves
it
after making no more than $P_x$ collisions with the walls. \end{thm}
As an immediate application of Theorem~\ref{thm-2} (or, to be more
rigorous, of
Proposition~\ref{prop-localestimate}) we obtain the following global
linear
estimate: \begin{cor} \label{cor-globalestimate} For any non-degenerate
semi-dispersing billiard there exists a constant $P$ such that, for
every $t,$
every trajectory
of the billiard flow makes no more than $P(t+1)$ collisions with the
boundary in the
time interval $[0,t].$ \end{cor}
Let $(T_1)^m$ be the $m$-th return map of the billiard flow to the
boundary $N$
of the phase space of the billiard flow.
To be more precise, $N$ consists of those points $X=(x,v)$ in the unit
tangent bundle
to $B$ that satisfy the following conditions
\begin{enumerate}
\item $X$ belongs to the domain of definition of the billiard flow
$T^t;$
\item $x$ belongs to the boundary of $B$ in $M.$
\end{enumerate}
Then, obviously, $T^t$ may be represented as a special flow over
$(T_1)^m$ under a function
$\tau_m: N \rightarrow \Bbb{R}.$ To be more precise, $\tau_m(X)$ is
equal to the
time that passes before the orbit of $T^t$ that starts at $X$ returns to
$N$
for the $m-th$ time.
A simple application of Theorem~\ref{thm-2} is the following
\begin{cor}
\label{cor-return}
For any non-degenerate semi-dispersing billiard there exist $m \in
\Bbb{N}$ and
$\epsilon >0$ such that $T^t$ is a special flow over $(T_1)^m$ under a
function
$\tau_m,$ with $\tau_m > \epsilon.$ \end{cor}
Now, consider a system of $N$ hard elastic balls in $\Bbb R^k$ that move
freely
and collide elastically. This means that if two balls collide they
reflect (that
is their speed vector change)
according to the following laws: In a (moving) coordinate system chosen
so that
the impulse of the pair of colliding balls with respect to this
coordinate
system is equal to zero
\begin{enumerate}
\item for each ball, the component of the speed vector parallel to the
common tangent
plane to the balls at the point of collision remains unchanged;
\item for each ball, the component of the speed vector
perpendicular to the common tangent plane to the balls at the point of
collision
changes sign.
\end{enumerate} (As usually, we assume that no more then two balls
collide with each other at any time.)
Effective estimates on the number of collisions and the size of the
neighborhood
allow us to prove the following global estimate:
\begin{thm}
\label{thm-exact}
In the system of $N$ hard elastic balls in $\Bbb R^k$ such that
the maximal mass and radius of the balls in the system are $M$ and $R$
and the
minimal ones are $m$ and $r,$ there can be no more
than $$ \left( 32 \sqrt{\frac{M}{m}} \frac{R}{r}N^{\frac{3}{2}} \right)
^{N^2}
$$ collisions in the infinite period of time $(-\infty, \infty).$
\end{thm}
\section{Plan of the Proof of Theorem~\ref{thm-2}.}
The proof is based on two geometric observations: the Comparison Lemma,
which is
proved in Section~\ref{sec-comparison} and the Shortening Procedure,
which is
explained in detail in Section ~\ref{sec-shortening}.
By a {\bf combinatorial type} of a trajectory $T(X,Y)$ we mean the
sequence
$B_{i_1}, \dots , B_{i_k}$ of the walls which it encounters. We say
that a
curve $\sigma(t), \sigma(0)=X, \sigma(1)=Y$ has the same combinatorial
type as
$T(X,Y)$ if it visits the same bodies $B_{i_j}$ as does $T(X,Y)$ in the
same
order, i.e., there are $0 \leq t_1 \leq t_2 \dots \leq t_k \leq 1$ with
$\sigma(t_j)
\in B_{i_j}$. Note that the inequalities are not strict, so rather than
visiting
$B_i$ and then $B_j$ the curve $\sigma(t)$ may visit their intersection
$B_i \cap B_j$
instead. For example, any curve between $X$ and $Y$ visiting the
intersection of
all $B_i$ has the same combinatorial type as any trajectory between $X$
and $Y$.
{\bf Comparison Lemma.} {\em Let $\Delta = \min(r,
\frac{1}{\sqrt{\max\{K,0\}}}).$
Then every
trajectory $T(X,Y)$ which lies inside some $\Delta$-ball is shorter than
every
other curve of the same combinatorial type, provided $|T(X,Y)| <
\Delta.$}
Though this statement may seem rather unexpected, it becomes very
transparent
when we construct a metric space where $T(X,Y)$ is a geodesic
(Section~\ref{sec-comparison}).
Since Theorem~\ref{thm-2} is a local existence result we can assume in
its proof that $Q=\bigcap_1^n B_i$ is non-empty. (Notice that
we do not require this in the Comparison Lemma.)
Theorem~\ref{thm-2} follows immediately from the following
statement:
{\em There exist $R(M,C)$ and $M(C,n)$ such that every trajectory
inside a
ball of radius $R$ on $M,$ which makes more than $M(C,n)$ collisions,
can be
shortened in its combinatorial class.}
Let us outline the construction of a shorter curve of the same
combinatorial
class (the detailed argument can be found in
Section~\ref{sec-shortening}).
Let $C>0$ be as in the non-degeneracy condition. We
define a {\bf special triple} to be any three points $X_1,$ $Y$ and
$X_2$ on $T$
such that \begin{enumerate} \item $X_1, X_2\in B_i,$ where
$i \in \{1,\ldots, n\}$ is such that
$\frac{dist(Y,B_i)}{dist(Y,Q)} \geq C;$
\item
$X_1$ precedes $Y$ on $T$ and $X_2$ follows $Y$ on $T.$ \end{enumerate}
For each special triple we consider two possible modifications
of the trajectory: \begin{enumerate}
\item join $X_1$ and $X_2$ by a shortest arc in $B_i$,
decreasing the length by some quantity $S;$
\item join $X_1$ with a point $q \in Q$ and then join $q$ and $X_2$.
\end{enumerate}
The
second modification may lead to some increase of the length, which,
however, can be estimated
by $SK(C),$ where $K(C)$ is a certain function of $C$
(Lemma~\ref{lmm-1}).
Hence, as soon as the number of such special triples exceeds $K(C)+1$,
we
choose one with the smallest value of $S$ and use modification (2) for
it
and modification (1) for others. This way we obtain a curve which is
shorter
than the original trajectory $T(X,Y),$ connects $X$ and $Y$
and visits $Q.$ Hence it has the same combinatorial type.
Contradiction.
To apply our results to
the hard balls gas, we notice that, for $M=\Bbb{R}^k$ and $\bigcap_i
B_i$
non-empty,
one can choose $R=\infty.$ Then we estimate $C$
(Section~\ref{sec-balls}) and thus obtain an estimate on $M(C,n).$
\section{Proof of the Comparison Lemma and of
Theorem~\ref{thm-finiteness}.}
\label{sec-comparison}
Given $T(X=X_0,Y=X_{j+1})$ with collision points $ X_1, \ldots, X_j$ we
construct a generalized Riemannian space (or Alexandrov's space, see
\cite{reshetnyak}) $\tilde{M}$ in the following way: take $j+1$
isometric
copies $M_i,$ $i=0,\ldots,j$ of $M$ and, for all $i=0,\ldots,j-1,$ glue
together $M_i$ and $M_{i+1}$ by the set $B_k,$ which contains $X_{i+1}.$
Notice
that by construction, for each $i $, there is a canonical isometric
embedding $E_i:M \rightarrow \tilde{M},$ which is an isometry between
$M$ and
$M_j$ and maps the subsets $B_i$ in $M$ into the subsets $B_i$ in $M_j.$
The curve $G(T(X,Y))=\bigcup_{i=0}^j E_i(X_{i}X_{i+1}) \in {\tilde{M}}$
is a geodesic in $\tilde{M}$ corresponding to the trajectory $T(X,Y)$ in
$M$ and it has the same length in $\tilde{M}$ as $T(X,Y)$ in $M.$
>From here on out we will denote the shortest geodesic in $M$ connecting
points
$X$ and $Y$ by $XY$ (when it is unique), and its length by $|XY|.$
Denote by $B_{\delta}(x)$
a ball of radius $\delta$ centered at $x
\in M.$
Let $\Delta$ be as in the Comparison Lemma.
Then $B_{\Delta} (x)$ is a simply-connected $P_K$-domain
(for a background information on non-regular Riemannian geometry
see \cite{reshetnyak}). Then, applying $j$ times Reshetnyak's theorem
\cite{reshetnyak}, we see that the $\Delta$-ball
$B_{\Delta}^{\tilde{M}}(x)$
around $x$ in $\tilde{M}$ is also a simply connected $P_K$-domain
with a
unique geodesic joining any two points. (Recall that Reshetnyak's
theorem
asserts that if we glue two $P_K$-domains by isometric convex sets then
we
obtain another $P_K$-domain.) The geodesic $G(T(X,Y))$ lies inside
$B_{\Delta}^{\tilde{M}}(x)$ and thus is the shortest curve inside
$\tilde{M}$
joining its end points $E_0(X) $ and $E_j(Y)$ in $\tilde{M}.$ Consider
a curve
$\sigma(t)$ between $X$ and $Y$ of the same combinatorial type as
$T(X,Y)$.
Then the curve $G(\sigma)= \bigcup_{i=0}^j E_i(\sigma[t_{i}, t_{i+1}])
\in
\tilde{M}$ has the same length as $\sigma(t)$ in $M$ and joins $E_0(X)
$ and
$E_j(Y)$ (here $t_0 =0,t_{j+1}=1$). Now, since $G(T(X,Y))$ is shorter
then
$G(r)$ we see that $T(X,Y)$ is shorter than $\sigma(t).$
{\bf Remark.} {\em Using the same arguments we see that for any $\delta
<
\Delta$ any piece of a trajectory inside $B_{\delta}(x),$ $x \in Q,$
has
length less than $2\delta.$}
{\em Proof of Theorem~\ref{thm-finiteness}.}
Assume that a finite length trajectory $T$ has infinitely many
collision points that accumulate to a point $q.$
Without loss of generality we may assume that $q \in Q$ (otherwise we
consider a
billiard system outside of a smaller number of bodies) and $T \subset
B_{\Delta}(q).$ Let $x_n, n=1,2,\ldots$ be the points of collision that
converge to $q.$ Clearly $|x_1q| <|T|,$ therefore we can find $k$ such
that
$|x_1q| +|qx_k| <|T(x_1,x_k)|$ which contradicts the Comparison Lemma
since
$T(x_1,x_k)$ has only a finite number of collisions.
Now we present an elementary proof of a weaker version of the Comparison
Lemma
for $M=\Bbb{R}^k$, which however can be used to complete the proofs of
all our
results for the case $M=\Bbb{R}^k.$ Namely, we show that if $Q=\bigcap
B_i$ is
non-empty, then $|Xq|+|qY| >|T(X,Y)|,$ for every $q \in Q.$
Fix an arbitrary point $q \in Q$ and a billiard trajectory
$T(X=x_0,Y=x_{j+1})$
in $B$ with the collision points $x_i \in \partial B, i=1, \ldots, j.$
Consider the triangulated surface which is formed by the triangles
$qx_ix_{i+1},
i=0, \ldots, j.$ Let $OX_0 \ldots X_{j+1} \in \Bbb R^2$ be the {\em
development}
of this surface.
The following simple lemma first appeared in the work of Vaserstein
\cite{vaserstein}.
{\bf Lemma.}
{\em The curve $\gamma=X_0 \ldots X_{j+1}$ is convex in the following
sense:
For any $i \in \{0,\ldots,j\},$ the whole $\gamma$ lies on the opposite
side
of $X_iX_{i+1}$ from $O.$}
Proof of the lemma is very simple and is based only on ``the angle of
intersection is equal to the angle of reflection'' property.
Now all we have to do is to notice that it follows from the convexity of
$\gamma$ that $$|Xq|+|qY| =|OX_0|+|OX_{j+1}| \geq
\sum_{i=0}^{j}|X_iX_{i+1}|=\sum_{i=0}^{j}|x_ix_{i+1}|=|T(X,Y)|.$$
We remark here that although the above lemma has been known for over 15
years
we noticed the elementary proof of the Comparison Lemma for
$\Bbb{R}^k$ only
after we proved the general case using the methods of non-regular
Riemannian
geometry and then tried to get an elementary proof by adjusting the
proofs of
the results about gluing $P_K$ domains to $\Bbb{R}^k.$ However, our
future
dynamical applications \cite{burago-entropy} essentially rely on the
non-elementary construction even in the case of billiards in
$\Bbb{R}^k$.
\section{Auxiliary Lemma}
\label{sec-auxilary}
Before we proceed with the proofs of our main results we need to prove
the following auxiliary lemma.
\begin{lmm}
\label{lmm-1}
There exists a constant $R(M,c)$ such that for any $A,B,C,E $ in a
ball $U$ of radius $R(M,c)$
the inequality $ \frac{dist (C,AB)}{|CE|} \geq c$ implies $$
\frac{|AE|+|EB|-|AC|-|CB|}{|AC|+|CB|-|AB|} \leq K(c)=32(1/c+1)^2.$$
In the case $M=\Bbb{R}^k$ one can take $R(M,c)=\infty,$ and
$K(c)=16(1/c+1)^2$
\end{lmm}
\begin{proof}
Let $D \in AB$ be the point closest to $C.$
We have $\frac{|ED|}{|CD|} \leq \frac{|CD|+|CE|}{|CD|} \leq c_1=1+1/c.$
Denote
$|CD|=d.$
First we will prove the lemma for $M=\Bbb{R}^k.$
We will consider two cases. The first case: $|AD| > 2c_1d$ and $|BD| >
2c_1d.$
Then $D$ belongs to the interior of $AB$ and thus $CD \perp AB.$
Note that in every right triangle with sides $y \leq x$ and hypotenuse
$z$ one has $\frac{y^2}{4x} \leq z-x \leq \frac{y^2}{2x}.$
Let $D_1$ be such that $D_1 \in (AB), ED_1 \perp AB.$ Then $D_1 \in AB$
and $|AD_1| \geq |AD|-|ED| \geq \frac{1}{2}|AD|,$ $|BD_1| \geq
\frac{1}{2}|BD|.$ Thus,
$$
|AE|+|EB|-|AB| =|AE|-|AD_1|+|EB|-|BD_1| \leq \frac{|ED_1|^2}{2|AD_1|}+
$$
$$
+\frac{|ED_1|^2}{2|BD_1|} \leq \frac{|ED|^2}{2}\left(
\frac{1}{|AD_1|}+\frac{1}{|BD_1|} \right) \leq
$$
$$
\leq \frac{c_1^2}{2}d^2\left( \frac{1}{|AD_1|}+\frac{1}{|BD_1|} \right)
\leq c_1^2d^2 \left( \frac{1}{|AD|}+\frac{1}{|BD|} \right),
$$
$$
|AC|+|CB|-|AB| = |AC|-|AD|+|BC|-|BD| \geq
\frac{d^2}{4|AD|}+\frac{d^2}{4|BD|} = $$
$$
= \frac{d^2}{4}\left( \frac{1}{|AD|}+\frac{1}{|BD|} \right).
$$
Therefore,
$$
\frac{|AE|+|EB|-|AC|-|CB|}{|AC|+|CB|-|AB|}=\frac{(|AE|+|EB|-|AB|)-(|AC|+|CB|-|AB|)}{|AC|+|CB|-|AB|}\leq$$
$$\leq 4c_1^2-1 = 3+\frac{8}{c}+\frac{1}{c^2} \leq 16(1/c+1)^2.
$$
Now we consider the second case: $|AD| \leq 2c_1d$ or $|BD| \leq
2c_1d.$ Then
$ |AE|+|EB|-|AB| \leq 2|ED| \leq 2c_1d, $
$$
|AC| + |CB|-|AB| \geq \sqrt{d^2+|AD|^2}+\sqrt{d^2+|BD|^2}-|AD|-|BD|
\geq
$$
$$
\geq d \left( \sqrt{1+\left( \frac{\min(AD,BD)}{|CD|}^2 \right)}
-\frac{\min(AD,BD)}{|CD|} \right) \geq$$ $$\geq d
(\sqrt{1+4c_1^2}-2c_1) \geq \frac{d}{8c_1},
$$
since $c_1>1.$ Therefore
$$
\frac{|AE|+|EB|-|AC|-|CB|}{|AC|+|CB|-|AB|} \leq 16\frac{c_1}{c} =
16/c+16/c^2 \leq 16(1/c+1)^2
$$
Lemma~\ref{lmm-1} is proved for $M=\Bbb{R}^N.$
Moreover, assuming that $R(M,c),$ and thus $d$ and $|AB|,$ are small
enough we see that \begin{equation}
\label{eq-1}
|AC|+|CB|-|AB| \geq d^2.
\end{equation}
Let us now prove the Lemma in the general case.
Assume that $R(M,c)$ is so small that for all $A,B \in U$ and $D \in
AB$ it is
possible to introduce normal coordinates along the geodesic $(AB)$
defined on the whole $U$ and with the
origin at $D.$
Let $f:U \rightarrow \Bbb{R}^m,$ where $m$ is the dimension of $M,$ be
the coordinate map. Then there exists a constant $L$ such that for any
$z \in U,$
$$
1-L(dist(z,AB))^2 \leq |D(f)(z)| \leq 1+L(dist(z,AB))^2.
$$
Let $A_1, B_1, C_1, D_1, E_1 \in \Bbb{R}^m$ be the images of
$A,B,C,D,E$ under $f.$
Then, from equation (1), it easily follows that
$$\frac{|AE|+|EB|-|AC|-|CB|}{|AC|+|CB|-|AB|}\leq $$
$$\leq
\frac{|A_1E_1|+|E_1B_1|-|A_1C_1|-|C_1B_1|+4Ld^2R(M,c)}{|A_1C_1|+|C_1B_1|-|A_1B_1|-3Ld^2R(M,c)}\leq
$$
$$\leq
2\frac{|A_1E_1|+|E_1B_1|-|A_1C_1|-|C_1B_1|}{|A_1C_1|+|C_1B_1|-|A_1B_1|}\leq
32(1/c+1)^2,$$
provided that $R(M,c)$ is small enough compared to $c$ and $L.$
This finishes the proof of
Lemma~\ref{lmm-1}.
\end{proof}
\section{Shortening Procedure and Proof of Theorem~\ref{thm-2}.}
\label{sec-shortening}
In proving Theorem~\ref{thm-2} we can and will assume that
$Q=\bigcap_1^n B_i$ is non-empty and that $x \in Q.$
Assume that $ B$ is non-degenerate in some neighborhood $U$ of $x$ with
constant $C.$ We will show that the conclusion of Theorem~\ref{thm-2}
is true
for $U_x=U \bigcap B_{\Delta/2}(x) \bigcap B_{R(M,C)}(x).$
First of all notice that from the Remark that follows the proof of
Comparison
Lemma we immediately see that Comparison Lemma is applicable to every
trajectory
inside $\bigcap B_{\Delta/2}(x)$ and, thus, to every trajectory inside
$U_x.$
Consider a trajectory $T$ inside $U_x.$
Recall that a triple $P=\{ X_1,Y,X_2 \} $ is called special if
\begin{enumerate}
\item $X_1,X_2 \in B_i,$ where $i \in \{1,\ldots, n\}$ is such that
$\frac{dist(Y,B_i)}{dist(Y,Q)}
\geq C;$
\item $X_1$ precedes $Y$ on $T$ and
$X_2$ follows $Y$ on $T.$ \end{enumerate}
For a special triple $P=\{X_1,Y,X_2\}$ we introduce the following
operations with $T:$
\begin{enumerate} \item Replace $T(X_1,X_2)$ by
$X_1E \bigcup EX_2,$ where $E \in Q$ is the point closest to $Y$ in
$Q.$
In this case we will say that we stretched $T$ with respect to
$P.$ We denote $|X_1E|+|EX_2|-|X_1Y|-|YX_2|$ by $S(P).$
\item Replace $T(X_1,X_2)$ by
$X_1X_2.$ In this case we will say that we contracted $T$
with respect to $P.$ We denote $|X_1Y|+|YX_2|-|X_1X_2|$ by $C(P).$
\end{enumerate}
Then by Lemma~\ref{lmm-1} we have
$$ S(P) \leq K(C)C(P).$$
Call a piece $T(a,b)$ of trajectory $T$ a {\bf full cycle} if $T$
intersects all bodies $B_i$ between the points $a$ and $b.$
Two full cycles will be called {\bf non-intersecting} if they
have no common points except maybe for the end points of
the cycles.
Let $L =[K(C)]+2 < 32(1/C+1)^2+2 < 32(1/C+2)^2.$
\begin{lmm}
\label{lmm-returns}
A trajectory inside $U_x$ can not have more than $2L$ pairwise
non-intersecting
full cycles. \end{lmm}
\begin{proof}
Assume that there are pairwise non-intersecting full cycles $T_j,$ $j
=\{1,\ldots, 2L \},$ numbered according to their order on $T.$
Let $T(a_1,b_1)$ and $T(a_2,b_2)$ be two consecutive full cycles. Set
$Y=a_2.$ Let $i$ be such that
$\frac{dist(Y,B_i)}{dist(Y,Q)} \geq C.$ Then there are points $X_1
\in
T(a_1,b_1)$ and $X_2 \in T(a_2,b_2)$ such that $X_1,X_2 \in B_i.$ Hence
each two consecutive full cycles contain a special
triple.
Therefore, inside $T$ we have at least $L$ special triples $P_q
=\{X_{1,q}, Y_q, X_{2,q} \},$ $q =\{1, \ldots, L\}.$ Moreover, $P_q
\subset T_{2q-1}
\bigcup T_{2q}.$
Consider, $S(P_q)$ and $C(P_q).$ Let $k$ be such that
$S(P_{k})=\min_{q}S(P_q).$
Let us stretch $T$ with respect to $P_k$ and contract it with respect
to $P_q$ for all $q \neq k.$ Denote the resulting curve by $T_1.$ Then
$|T| -|T_1| \geq (\sum_{q\neq k} C(P_q)) - S(P_k) \geq
(\sum_{q \neq k} \frac{1}{K(C)} S(P_q))- S(P_k)\geq \frac{L-1}{K(C)}
S(P_k) - S(P_k) >0.$ This contradicts the Comparison Lemma.
\end{proof}
\begin{prop}
\label{prop-localestimate}
Any piece of a trajectory that lies inside $U_x$ has no more than
$$M_n=(16 (1/C+2))^{2(n-1)}$$
collisions (where $n$ is the number of bodies $B_i$).
\end{prop}
\begin{proof}
We prove Proposition~\ref{prop-localestimate} by induction on the number
of bodies $B_i.$
Assume that for all $k0.$
Let us estimate $\max_{B_{m,l} \in I} dist(X, B_{m,l}).$
The distance from $X$ to any point $X'=F(c'_i)$ of $B_{m_1,l_1}$ is
no less than $$\sqrt{\frac{1}{2E}(m_{m_1}|c_{m_1}-c'_{m_1}|^2
+m_{l_1}|c_{l_1}-c'_{l_1}|^2)} \geq \sqrt{\frac{1}{2E}e^2/4} \geq
\frac{e}{2\sqrt{2E}}.$$
Therefore,
\begin{equation}
\label{1}
dist(X, B_{m_1,l_1}) \geq \frac{e}{2\sqrt{2E}}.
\end{equation}
Let us estimate $dist(X, \bigcap_{B_{m,l} \in I} B_{m,l}).$
Let $\lambda =\frac{2}{2+e}.$ Then, for all $B_{m,l} \in I$
\begin{equation}
\label{2}
\lambda d_{m,l} \leq r_m+r_l.
\end{equation}
Construct a graph $G$ in the following way:
\begin{enumerate} \item $G$ has $N$ vertices marked by the integers
$i=1,\ldots,N;$
\item Vertices $m$ and $l$ are connected by an edge if and only if
$B_{m,l} \in I.$
\end{enumerate}
Let $G=\bigcup_j G_j,$ where $G_j$ are the connected components of $G.$
Fix arbitrary vertices $v_j \in G_j$ (one in each connected component).
Consider dilations $H_j$ in $\Bbb{R}^k$ with the centers at $c_{v_j}$
and contraction coefficient $\lambda.$ Let $c'_i =H_{j}(c_i),$ where
$j$ is such that $i \in G_j.$
Then for all $i=1,\ldots,N$ the distance between $c'_i$ and $c_i$ is
not greater than
$$(N \max_{B_{m,l} \in I}d_{m,l})(1-\lambda) \leq
\frac{(2R+e)eN}{2+e}.$$
Let $X'=F(c'_i).$
Then equation (2) implies that $X' \in \bigcap_{B_{m,l} \in I} B_{m,l}.$
And
$$||X-X'||^{2}=\frac{1}{2E}\sum_i m_i |c_i-c'_i|^{2} \leq \frac{1}{2E}NM
\frac{(2R+e)^2 e^2N^2}{(2+e)^2} \leq \frac{1}{2E}N^3 M R^2 e^2.$$
Therefore,
\begin{equation}
\label{3}
dist(X,\bigcap_{B_{m,l} \in I} B_{m,l}) \leq
\frac{NRe\sqrt{MN}}{\sqrt{2E}}.
\end{equation}
>From equations (2) and (4) we have
$$C_{I,\Bbb{R}^{Nk}}(X) \geq \frac{1}{2RN\sqrt{MN}} $$ for any $I.$
Therefore $C=C_{I,\Bbb R^{Nk}}(X) \geq \frac{1}{2RN\sqrt{MN}}$ for all
$X \in \Bbb{R}^{kN}.$
Due to this fact and the remark after
Proposition~\ref{prop-localestimate} we
see that the maximal number of collisions is no greater than
$$(8(2RN\sqrt{MN}))^{N(N-1)-2} < (32RN\sqrt{MN})^{N^2}$$ which proves
Theorem~\ref{thm-exact}.
\centerline {\bf Acknowledgments.}
We would like to express out sincere gratitude to L.Vaserstein and
A.Semenovich for
drawing our attention to this problem, their constant interest in our
work and
many useful discussions, and to N.Chernov, G.Galperin, A.Katok and
Ya.Pesin for very helpful comments and corrections. We also would
like to
thank M.Brin who read a preliminary version of the paper and made many
corrections and improvements.
\bibliographystyle{plain}
\begin{thebibliography}{1}
\bibitem{burago-entropy}
D.Burago, S.Ferleger, A.Kononenko.
\newblock Topological entropy of semi-dispersing billiards.
\newblock {\em in preparation.}
\bibitem{chernov-entropy}
N.I.Chernov.
\newblock
New proof of Sinai's formula for the entropy of hyperbolic billiard
systems. Application to Lorentz gases and Bunimovich stadiums.
\newblock {\em Funct. Anal. Appl.}, 25, No.1:204-219, 1991.
\bibitem{chernov-topentropy}
N.I.Chernov.
\newblock
Topological entropy and periodic points of two-dimensional
hyperbolic billiards.
\newblock {\em Funct. Anal. Appl.}, 25, No.1:39-45, 1991.
\bibitem{galperin}
G.A.Gal'perin.
\newblock
Systems with locally interacting and repelling particles moving in
space.
\newblock {\em Tr. MMO}, 43, 142--196, 1981.
\bibitem{illner}
R.Illner.
\newblock
Finiteness of the number of collisions in a hard sphere particle system
in all space.
\newblock {\em Transport Theory Statist. Phys.}, 19, No.6:573-579, 1990.
\bibitem{reshetnyak}
Yu.G.Reshetnyak (ed.).
\newblock Geometry 4, non-regular Riemannian geometry.
\newblock {\em Encyclopedia of Mathematical Sciences}, Vol.70, 1993.
\bibitem{dynamicalsystems-2}
Ya.G.Sinai (ed.).
\newblock Dynamical Syastems 2.
\newblock {\em Encyclopedia of Mathematical Sciences}, Vol.2, 1989.
\bibitem{sinai-angle}
Ya.G.Sinai.
\newblock
Billiard trajectories in polyhedral angles.
\newblock {\em UMN}, 33, No.1:229--230, 1978.
\bibitem{sinai-entropy}
Ya.G.Sinai.
\newblock
Entropy per particle for the dynamical system of hard spheres.
\newblock {\em Harvard Univ. Preprint}, 1978.
\bibitem{semenovich}
A.Semenovich, L.Vaserstein.
\newblock
Uniform estimates on the number of collisions in particles' systems.
\newblock {\em preprint}
\bibitem{thurston}
W.Thurston, G.Sandri.
\newblock
Classical hard sphere 3-body problem.
\newblock {\em Bull. Amer. Phys. Soc.}, 9:386, 1964.
\bibitem{vaserstein}
L.N.Vaserstein.
\newblock
On systems of particles with finite range and/or repulsive interactions.
\newblock {\em Comm. Math. Phys.}, 69:31--56, 1979.
\end{thebibliography}
\end{document}