\section{Introduction}

B. H. Neumann [{\bf N\/}] introduced outer billiards in
the late 1950s and J. Moser [{\bf M1\/}]
popularized the system in the 1970s as a toy model
for celestial mechanics.
Outer billiards is a discrete self-map of $\R^2-P$,
where $P$ is a bounded convex planar set as
in Figure 1.1 below.
Given $p_1 \in \R^2-P$, one
defines $p_2$ so that
the segment $\overline{p_1p_2}$ is tangent to $P$ at its
midpoint and $P$ lies to the right of the ray
$\overrightarrow{p_1p_2}$.  The map $p_1 \to p_2$
is called {\it the outer billiards map\/}.
The map is almost everywhere defined and
invertible.   See [{\bf T1\/}] for a survey of 
outer billiards.

\begin{center}
\resizebox{!}{2.2in}{\includegraphics{Pix/intro1.eps}}
\newline
{\bf Figure 1.1:\/} Outer billiards relative to $P$.
\end{center}

Usually, the main object of study is the orbit $\{p_n\}$ of the
point $p_1$.   These orbits are both complicated
and interesting.   When $P$ is a convex polygon,
the orbits frequently have a fractal structure.
Aside from a few cases, the structure of the
orbits is not yet well understood. 

It turns out that it is sometimes 
productive to study not the orbit itself
but rather a certain {\it acceleration\/} of the
orbit.   Roughly speaking,  the acceleration we have
in mind amounts to considering
the first return map to a certain infinite
strip in the plane.   We call this acceleration
{\it the pinwheel dynamics\/}, because it is
based on the pinwheel map that we studied
in [{\bf S3\/}].   We give a full account
of the pinwheel map in \S \ref{pm} and
recall some of the results of [{\bf S3\/}] in
\S \ref{discuss}.   We point out, however,
that this paper does not rely on any of
the results in [{\bf S3\/}].  The work
here is self-contained.

The first purpose of this paper is to introduce
an object called the {\it arithmetic graph\/}.  The arithmetic
graph is a polygonal path $\Gamma(P,p) \subset \R^{n}$ that one associates
to the pinwheel dynamics of $p=p_1$.
One can view this graph as a geometric incarnation of the
symbolic coding of the pinwheel dynamics.
The arithmetic graph is quite similar to the lattice paths studied
by Vivaldi et. al. [{\bf V\/}] in connection with interval
exchange transformations.    We will define
the arithmetic graph in \S \ref{ag0}, right after
defining the pinwheel map.

In case $P$ is a kite -- i.e. a convex quadrilateral having a diagonal
that is a line of symmetry -- we have studied the arithmetic graph
in great detail.
In [{\bf S1\/}] we analyzed the graph
$\Gamma(P,p)$, where $P$ is the
Penrose kite and $p$ is a specially chosen point.
For this pair, we showed that $\Gamma(P,p)$ is
{\it coarsely self-similar\/}, in the sense that a
certain rescaled limit of $\Gamma(P,p)$ is a
self-similar fractal curve.  See \S \ref{lim} for
a formal definition of what we mean by a
{\it rescaled limit\/}.   

We used the coarse self-similarity of the
arithmetic graph in this case
to conclude that the orbit of $p$ is unbounded
relative to $P$.  This provided the first example
of an outer billiards system with unbounded orbits.
In [{\bf S2\/}] we studied the arithmetic graphs
relative to kites in general, and 
showed that outer billiards has unbounded orbits
when defined relative to any irrational kite.
In \S \ref{penrose} we will show some of
the nicest pictures of arithmetic graphs
associated to kites.

The irrational kites are
the only known examples \footnote{It is worth
mentioning that Dolgopyat and Fayad show in
[{\bf DF\/}] that outer billiards also has unbounded
orbits when defined relative to a semi-disk.}
 of polygons for which
outer billiards has unbounded orbits.
Since the arithmetic graph turns out to be a decisive
tool for establishing the unboundedness 
results for kites, we
think that it will also be a useful tool for
polygonal outer billiards more generally.
Compare Theorem \ref{unbound0} (a
result quoted from [{\bf S3\/}])
and the discussion following it.

Even in the case when all the orbits are known
to be bounded, as they are for so-called
{\it quasi-rational\/} polygons -- see
[{\bf VS\/}], [{\bf K\/}], [{\bf GS\/}] -- we think
that the arithmetic graph should shed light on the
dynamics.  
(See the end of \S \ref{discuss} for a definition
of {\it quasi-rational\/}.)
 In particular, the arithmetic graph
sheds light on the dynamics relative to the
regular polygons.  The regular polygons are
nice examples of quasi-rational polygons.


The vertices of a regular polygon have
coordinates that lie in a cyclotomic field.
When $p$ lies in this same field, one can view
certain projections of $\Gamma(p)$ as
``Galois conjugates'' of the orbits.
In somewhat the same way that the
full list of Galois conjugates of an algebraic number
sheds light on the number, the arithmetic graph
sheds light on the orbits associated to a polygon
with algebraic vertices.


This brings us to the main purpose of our paper.
We will concentrate on outer billiards for the
regular octagon, a polygon that we scale so
its vertices are the $8$th roots of unity.
The outer billiards dynamics for the regular
octagon are well understood from certain
points of view, but we will show that 
the study of the arithmetic graphs in
the regular octagon case leads to a big
surprise:  There is a
fractal loop $\Gamma$ in $\R^4$ which has the following
three properties.

\begin{itemize}

\item One planar projection $\pi_3$ of $\Gamma$ is an
embedded fractal loop reminiscent of the Koch
snowflake.  See Figure 1.2 below.  We call
this fractal {\it the snowflake\/}.  We give
a precise definition in \S \ref{snowflake}.

\item Another planar projection $\pi_2$ of $\Gamma$
is a fractal set reminiscent of the Sierpinski
carpet.  See Figure 1.3 below for an approximate
picture.  We call this fractal {\it the carpet\/}.
We give a precise definition in \S \ref{carpet}.

\item $\Gamma$ is the rescaled limit of the arithmetic
graphs associated to any sequence of {\it odd\/} periodic
orbits.
We give a precise definition of {\it rescaled limit\/} in
\S \ref{lim}.
\end{itemize}

It turns out that all the periodic orbits intersect a certain
strip in $3^k$ points for some integer $k$.   See
\S \ref{renorm}. We call the
orbit {\it odd\/} if $k$ is odd.
In Figure 1.2, the odd orbits are 
arithmetically closed orbits are lightly colored.
What we actually prove is slightly weaker than what we
have just said.  For technical reasons, we only consider
odd orbits that lie outside the first layer of big grey
octagons in Figure 1.3.

\begin{center}
\resizebox{!}{2.5in}{\includegraphics{Pix/snowflake.ps}}
$\hskip 10 pt$
\resizebox{!}{2.5in}{\includegraphics{Pix/carpet1.eps}}
\newline
{\bf Figure 1.2:\/} The snowflake and the carpet
\end{center}

\begin{center}
\resizebox{!}{3.3in}{\includegraphics{Pix/octagon0.ps}}
\newline
{\bf Figure 1.3:\/} Periodic orbits associated to the octagon
\end{center}  


By considering the correspondence
between our two fractals, we produce a surjective
continuous map from the snowflake
to the carpet.
This map is ``symmetry respecting'' in a
certain formal sense that we discuss
in \S \ref{fractal}.  See \S \ref{map}
for a description of the map from
the snowflake to the carpet.
What is surprising is that this canonical
map between two seemingly unrelated fractals
actually arises ``naturally'', in connection
with outer billiards on the octagon.

For the sake of comparison, we now discuss the
situation for other regular polygons.For $n=3,4,6$,
 outer billiards on the regular $n$-gon
is rather trivial and easy to describe.  In all these
cases, there is a familiar periodic tiling of the plane,
such that the dynamics permutes the tiles.  In the
case $n=4$ we get the usual square tiling.  In
the cases $n=3,6$ we get a tiling by hexagons
and triangles.

For the case $n=5$,
Tabachnikov [{\bf T2\/}] analyzes the situation in detail.
The recent paper [{\bf BC\/}] builds on the work
in [{\bf T2\/}] and describes the
symbolic dynamics for the periodic orbits in great detail.
We are interested in something different, namely
the pinwheel dynamics, but the two are closely related.
In the case of the regular pentagon, our construction
produces a pair of embedded fractal curves, both akin to
the Koch snowflake, that arise as geometric
limits of arithmetic graphs associated to periodic orbits.
See \S \ref{penta}.
For the sake of brevity, we do not present proofs
of the statements we make for the regular pentagon.
We are mainly interested in the octagon, and
the analysis we give in the case of the octagon
could be fairly easily redone for the
pentagon.

The four cases $n=5,10,8,12$ are all quite similar
to each other, and possible to understand completely.
In these cases,
outer billiards on the regular $n$-gon has an efficient
renormalization scheme that allows one to give 
(at least in principle) a complete description of what is going on.
The special properties of these values of $n$ is that the
corresponding $n$th roots of unity lie in quadratic
number fields.   In the case $n=10$,  we get the
same two snowflakes as in the case $n=5$.
We leave the case $n=12$, which is mildly
more complicated than any of the other
quadratic cases, to the experimentally minded reader.

For any other positive integer $n$, outer billiards
on the regular $n$-gon is not well understood at all.
For the sake of comparison, we will draw some
pictures of arithmetic graphs associated to the
regular $7$-gon.  See
\S \ref{hept}.  In this case, the pictures reveal
an explosion of complexity in a geometrically striking
way.   Our $4$ figures in \S \ref{hept}
give only the faintest hint of the complexity.
\newline


Here is the plan of the paper.

\begin{itemize}
\item {\bf Basic Definitions:\/}
In \S 2 we will define the arithmetic graph,
and give explicit formulas in the case of
the regular octagon.
\item
{\bf A Picture Gallery:\/} In \S 3 we draw the arithmetic graphs
for many examples, including the regular
octagon.    After reading \S \ref{octopix},
the reader should have a good intuitive
idea of what our main theorem will say,
even though we defer the formal statement
until \S \ref{main result}.
\item
{\bf Carpet and Snowflake:\/}
In \S 4 we define the snowflake and
carpet fractals precisely, and discuss
the relationship between them.
\item
{\bf Reduction to a Small Region:\/}
We state our main result,
Theorem \ref{main}, at the beginning of \S 5.
In \S 5 we reduce Theorem \ref{main} to
the study of periodic points in a very small
region $R_1$.
\item
{\bf Toy Example of Renormalization:\/}
In \S 6 we study a simple and well-known
polygon exchange map that arises in connection
with outer billiards on the regular octagon.
The material in this chapter is not strictly necessary
for our formal proof, but the system we study here is
closely related to the one that comes from the 
pinwheel map.
\item
{\bf Pinwheel Dynamics:\/}
In \S 7, we describe the dynamics of the
pinwheel map on the region $R_1$.  Actually,
we reduce an even smaller region, $R$, which
is the top half of $R_1$.   The dynamical system on $R$
is the main dynamical system of interest to us.
Both the pinwheel map and the system 
from \S 6 have a period
$3$ renormalization that is the key to their
analysis.
\item
{\bf Substitution Scheme:\/}
In \S 8 we study the arithmetic graphs
produced by the dynamics on $R$.
Using the renormalization scheme, we describe
an efficient $2$-part method for generating the 
projections of the arithmetic graph of interest to us.
The first part of the method is combinatorial,
and involves a substitution scheme for
numerical sequences.  The second part is
geometrical, where we replace each number
in the created string by a certain vector.
We call this second half the {\it vector assignment}.
\item
{\bf Fixed Point of Renormalization:\/}
In \S 9 we modify the construction presented in
\S 8, keeping the combinatorial part the same
but changing the vector assignment.  We see that
the substitution scheme produces a kind of
{\it renormalization operator\/} defined on
the vector space of all possible vector
assignments.   This fixed point corresponds to
the Perron-Frobenius eigenvector.
 By taking the fixed point of
our operator as the new vector assignment,
we produce a nicer family of curves that
has the same rescaled limit.    
\item
{\bf Self-Similar Pattern Matching:\/}
In \S 10 we check by a combination of direct
calculation and induction that our improved
curves from \S 9 have the snowflake and
the carpet as their limit.   The key idea is
that the improved curves and the fractals
from \S 4 are self-similar in compatible ways.
 The final analysis completes the proof of the
Main Result.
\end{itemize}

The reader might be interested to know that we have
made two java programs, {\it OctoMap 1\/} and
{\it OctoMap 2\/}, which illustrate the mathematics
in this paper.  OctoMap 1 illustrates the snowflake
and carpet fractals in great detail, and gives an
interactive demonstration of the material in
\S 4.   OctoMap 2, a much more extensive
program, starts with the dynamical system produced
in \S 7 and illustrates all the key ideas that
go into the proof of the Main Theorem.
In particular, one can use OctoMap 2 to survey all
the computations we describe in \S 7-10.
One can find our applets, respectively, at the following address:
\begin{itemize}
\item http://www.math.brown.edu/$\sim$res/Java/OctoMap/Main.html
\item http://www.math.brown.edu/$\sim$res/Java/OctoMap2/Main.html
\end{itemize}
We strongly encourage the reader to look at these applets while reading
this paper.  They relate to this paper the same way that a cooked
meal relates to a recipe.
\newline

I'd like to thank Gordon Hughes and Sergei Tabachnikov about interesting
and inspiring conversations about outer billiards on regular polygons.
\newpage
{"config": "arxiv", "file": "1006.2782/1intro.tex"}