{'fraction_non_alphanumeric': 0.045238342507010074, 'fraction_numerical': 0.020812130023886176, 'mean_word_length': 3.4746967795901296, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 32, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Outer Billiards, Arithmetic Graphs, and the Octagon

Outer Billiards is a geometrically inspired dynamical system based on a convex shape in the plane. When the shape is a polygon, the system has a combinatorial flavor. In the polygonal case, there is a natural acceleration of the map, a first return map to a certain strip in the plane. The arithmetic graph is a geometric encoding of the symbolic dynamics of this first return map. In the case of the regular octagon, the case we study, the arithmetic graphs associated to periodic orbits are polygonal paths in R^8. We are interested in the asymptotic shapes of these polygonal paths, as the period tends to infinity. We show that the rescaled limit of essentially any sequence of these graphs converges to a fractal curve that simultaneously projects one way onto a variant of the Koch snowflake and another way onto a variant of the Sierpinski carpet. In a sense, this gives a complete description of the asymptotic behavior of the symbolic dynamics of the first return map. What makes all our proofs work is an efficient (and basically well known) renormalization scheme for the dynamics.


Introduction
B. H. Neumann [N] introduced outer billiards in the late 1950s and J. Moser [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 ∈ R 2 − P , one defines p 2 so that the segment p 1 p 2 is tangent to P at its midpoint and P lies to the right of the ray − − → p 1 p 2 . The map p 1 → p 2 is called the outer billiards map. The map is almost everywhere defined and invertible. See [T1] for a survey of outer billiards. 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 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 the pinwheel dynamics, because it is based on the pinwheel map that we studied in [S3]. We give a full account of the pinwheel map in §2.2 and recall some of the results of [S3] in §2.5. We point out, however, that this paper does not rely on any of the results in [S3]. The work here is self-contained.
The first purpose of this paper is to introduce an object called the arithmetic graph. The arithmetic graph is a polygonal path Γ(P, p) ⊂ 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. [V] in connection with interval exchange transformations. We will define the arithmetic graph in §2.3, 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 [S1] we analyzed the graph Γ(P, p), where P is the Penrose kite and p is a specially chosen point. For this pair, we showed that Γ(P, p) is coarsely selfsimilar , in the sense that a certain rescaled limit of Γ(P, p) is a self-similar fractal curve. See §4.1 for a formal definition of what we mean by a 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 [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 §3.1 we will show some of the nicest pictures of arithmetic graphs associated to kites.
The irrational kites are the only known examples 1 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 2.3 (a result quoted from [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 quasi-rational polygons -see [VS], [K], [GS] -we think that the arithmetic graph should shed light on the dynamics. (See the end of §2.5 for a definition of 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 Γ(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 8th 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 Γ in R 4 which has the following three properties.
• One planar projection π 3 of Γ is an embedded fractal loop reminiscent of the Koch snowflake. See Figure 1.2 below. We call this fractal the snowflake. We give a precise definition in §4.2.
• Another planar projection π 2 of Γ is a fractal set reminiscent of the Sierpinski carpet. See Figure 1.3 below for an approximate picture. We call this fractal the carpet. We give a precise definition in §4.4.
• Γ is the rescaled limit of the arithmetic graphs associated to any sequence of odd periodic orbits. We give a precise definition of rescaled limit in §4.1.
It turns out that all the periodic orbits intersect a certain strip in 3 k points for some integer k. See §7.4. We call the orbit 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.  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 §4. See §4.6 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 [T2] analyzes the situation in detail. The recent paper [BC] builds on the work in [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 §3.2. 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 nth 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 §3.4. In this case, the pictures reveal an explosion of complexity in a geometrically striking way. Our 4 figures in §3.4 give only the faintest hint of the complexity.
Here is the plan of the paper.
• Basic Definitions: In §2 we will define the arithmetic graph, and give explicit formulas in the case of the regular octagon.
• A Picture Gallery: In §3 we draw the arithmetic graphs for many examples, including the regular octagon. After reading §3.3, the reader should have a good intuitive idea of what our main theorem will say, even though we defer the formal statement until §5.1.
• Carpet and Snowflake: In §4 we define the snowflake and carpet fractals precisely, and discuss the relationship between them.
• Reduction to a Small Region: We state our main result, Theorem 5.2, at the beginning of §5. In §5 we reduce Theorem 5.2 to the study of periodic points in a very small region R 1 .
• Toy Example of Renormalization: In §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.
• Pinwheel Dynamics: In §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 §6 have a period 3 renormalization that is the key to their analysis.
• Substitution Scheme: In §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 vector assignment.
• Fixed Point of Renormalization: In §9 we modify the construction presented in §8, keeping the combinatorial part the same but changing the vector assignment. We see that the substitution scheme produces a kind of 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.
• Self-Similar Pattern Matching: In §10 we check by a combination of direct calculation and induction that our improved curves from §9 have the snowflake and the carpet as their limit. The key idea is that the improved curves and the fractals from §4 are self-similar in compatible ways. The final analysis completes the proof of the Main Result.
The reader might be interested to know that we have made two java programs, OctoMap 1 and 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 §4. OctoMap 2, a much more extensive program, starts with the dynamical system produced in §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 §7-10. One can find our applets, respectively, at the following address: • http://www.math.brown.edu/∼res/Java/OctoMap/Main.html • http://www.math.brown.edu/∼res/Java/OctoMap2/Main.html 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. I'd like to thank Gordon Hughes and Sergei Tabachnikov about interesting and inspiring conversations about outer billiards on regular polygons.

Strip Maps
Let Σ ⊂ R 2 be an infinite strip. Let V be a vector whose tail lies on one edge of Σ and whose head lies on the other. All this is shown in Figure 2.1. To (Σ, V ) we associate a strip map f : R 2 → Σ, defined by f (p) = p+nV , where n ∈ Z is chosen so that p + nV ∈ Σ. In the example shown, we have n = 2.

Remarks:
(i) f is not everywhere defined. It is not defined on a certain countable family of lines that are parallel to Σ. In particular f is not defined on the boundary of Σ. (ii) The pair (Σ, −V ) gives rise to the same map as the pair (Σ, V ). (iii) In case Σ is the horizontain strip bounded by the lines y = 0 and y = 1, and V = (0, 1), the map map f has the formula f (x, y) = (x, [y]), where [y] is the fractional part of y. In this case, f is not defined on the horizontal lines of integer height. Any other strip map is conjugate to this one by some affine transformation.

The Pinwheel Map
Let P be a convex n-gon. To P we associate n special pinwheel strip. Each pinwheel strip Σ is such that one component of ∂Σ contains an edge e of P , and vertices of P farthest from this boundary component lie on the centerline of Σ. See We orient the boundaries of a pinwheel strip Σ so that a person walking along a boundary component would see Σ on the left. Thus, the two boundary components are oriented in opposite directions. Say that a pointed strip is a strip, together with a choice of boundary component. We think of a pointed strip as pointing in the direction of the orientation on its preferred boundary component. To each n-gon we associate 2n pointed strips, 2 per pinwheel strip. We denote pointed strips by a pair (Σ, L), where L is a boundary component of the strip Σ.
To the pair (Σ, L) we associate a vector V as follows. We choose ǫ > 0 and let p be a point which is ǫ units from L, outside of Σ, and 1/ǫ units away from the origin. Of the two possible locations for p that the above conditions determine, we choose the one toward which L points. Figure 2.2 shows what we mean. We then let V = φ 2 (p) − p. Here φ 2 is the square of the outer billiards map. Our definition is independent of ǫ, provided that ǫ is sufficiently small.
where v is the vertex bisecting the segment joining p to φ(p) and w is the vertex bisecting the segment joining φ(p) to φ 2 (p). It is not hard to check that Σ and V are related as in §2.1. Thus, we have associated to P a total of 2n triples (Σ k , L k , V k ). Here (Σ k , L k ) is a pointed pinwheel strip and V k is the associated vector. We cyclically order these 2n triples in the following way. We choose a large circle C centered at the origin, and orient C counterclockwise. Each pair (Σ k , L k ) determines a point c k ∈ C, namely the intersection point of L k ∩ P towards which L k points. We order our triples so that the points c 1 , ..., c 2n occur in counterclockwise order along C. Figure 2.3 shows these points, in case P is the regular octagon. In Figure 2.3 we highlight the pointed strips Σ 15 and Σ 0 = Σ 16 .
Let f k be the strip map associated to the pair (Σ k , V k ). We say that the pinwheel map is the composition We say that p ∈ Σ 0 is preferred if, for all x ∈ P , the vector p − x has positive dot product with vectors parallel to L 0 . We call the subset of preferred points the preferred half of Σ 0 and denote it by H 0 . We usually restrict Φ to H 0 . Note that Φ need not carry H 0 to H 0 . However, if p ∈ H 0 is sufficiently far from Σ 0 − H 0 then Φ(p) ∈ H 0 .
Remark: For our purposes here, the boundary of H 0 (that separates H 0 from Σ 0 − H 0 ) is not important. What is important is the end of Σ 0 that H 0 determines. Below, and just for the case of the regular octagon, we will replace H 0 by a similar set, namely Σ 1 0 below, that is invariant under Φ.
Let φ denote the outer billiards map and let φ 2 be the square of the outer billiards map. Let O + (φ 2 , p) denote the forwards φ 2 -orbit of p.
Lemma 2.1 The following is true for all points p ∈ H 0 that lie sufficiently far from P . Let q be the first point in O + (φ 2 , p) that lies in H 0 . Then q = Φ(p).
Proof: For each point p ∈ R 2 − P for which φ 2 is well-defined, there is a vector V (p) such that φ 2 (p) − p = V (p). The function p → V (p) is locally constant. Let ∆ be the disk bounded by the large circle C, as in Figure 2.2. Let W k be the open acute wedge shaped region of R 2 − ∆ bounded by the lines L k−1 and L k . The vector V k has the property that V (p) = V k for at least some points p ∈ W k . But one can check easily that φ 2 is defined on all of W k provided that the circle C is taken large enough. Hence V (p) = V k for all p ∈ W k .

The Arithmetic Graph
Let p = p 0 ∈ Σ 0 be a point. As in the proof of Lemma 2.1, there are integers m 1 , ..., m 2n such that Let v 1 , ..., v n be the vertices of P , ordered clockwise around P . Let e 1 , ..., e n be the standard basis of R n . For each vector V = V k there are indices i and j such that V k = 2(v i − v j ). Of course, i and j depend on k, but we are suppressing this from our notation. We define We define We define Γ(P, p) to be the polygonal path in R n that starts at 0 and has consecutive vertices Φ(p), Φ 2 (p), etc.

Remarks:
(i) It might seem at first that Φ is somehow a "lift" of Φ to R n . This is only partially true. What is true is that Φ k is a map from Σ 0 to R n . This map is only defined on points where Φ k is well defined.
(ii) By construction the arithmetic graph is a lattice path in that its vertices lie in Z n . As remarked in the introduction, one should compare the lattice paths of [V].
(iii) There is a constant C ′ , depending only on P , such that |m k+n −m k | < C ′ . The reason is that the successive points p 1 , ..., p 2n are the vertices of a convex polygon that is centrally symmetric to within a bounded error. Hence, the edges of Γ(P, p) have length at most C, for some constant C depending only on P . This property is important when we take rescaled limits of the graph. (iv) There is an obvious projection π : R n → R 2 given by π(e k ) = v k . By construction, p + π(Γ(P, p)), meaning the translation of π(Γ(P, p)) by p, is exactly the forwards Φ orbit of p. What makes Γ(P, p) interesting is that sometimes other projections are much more revealing. We will illustrate this in the next chapter with many examples.

Formulas for the Octagon
Since we are concentrating on the regular octagon, it seems worthwhile giving explicit formulas in this case. Recall that the vertices of the regular octagon are ω k for k = 0, ..., 7. We let (ij) denote the line through ω i and ω k , oriented from i to j. We let k(ij) denote the image of (ij) after we apply reflection in ω k . Finally, we let [ij] denote the vector that points from ω i to 2ω j − ω i . Definition: The shaded region in Figure 2.4 is the subset of Σ 0 to the right of the line y = 2 + √ 2. We let Σ 1 0 denote this set.
To illustrate our notation by way of example, The triple (Σ 0 , L 0 , V 0 ) is specified by 0 : 6(23) We first list L 0 , then the other component of Σ 0 , and then V 0 . See Figure  2.4.
The listing for (Σ 2 , L 2 , V 2 ) is obtained from the one for (Σ 0 , L 0 , V 0 ) simply by incrementing all the indices by 1. That is And so on.

Discussion
Lemma 2.1 gives a precise relationship between the pinwheel map and the outer billiards map for points in H 0 that are far from P . The relationship between φ 2 and Φ for points near P is rather subtle, and it was the purpose of the paper [S3] to explain the relationship. Here we summarize some of the results from [S3]. These results are not needed for this paper, but they are worth knowing.
Here is a consequence of our work in [S3] Theorem 2.2 Suppose that all our constructions are made with respect to a convex polygon with no parallel sides. Then, the following holds for any sufficiently large disk ∆ centered at the origin. Let p ∈ Σ 0 − ∆. Then O + (φ 2 , p) returns to H 0 − ∆ if and only if O + (Φ, p) returns to H 0 − ∆, and the two points of return are the same.
There are two subtle points to Theorem 2.2. First, the forward orbits of p, in either case, might wind many times around P before returning to H 0 −∆ 0 . Second, Lemma 2.1 only applies to points of H 0 that are sufficiently far from P . After our orbits exit H 0 − ∆, then might wander quite close to P and only "come back out" much later on. However, magically, they "come back out" in exactly the same way. One consequence of Theorem 2.2 is Theorem 2.3 Suppose that all our constructions are made with respect to a convex polygon with no parallel sides. The pinwheel map Φ has unbounded orbits relative to P if and only if outer billiards has unbounded orbits relative to P .
We only proved these results for polygons without parallel sides because we wanted to avoid certain technical complications. We fully expect that the same results hold for all convex polygons. However, we have not yet worked out the details. For the present paper, which deals (rigorously) just with the regular octagon, we will prove something stronger than Theorem 2.2. Namely, in §5.3 we prove Lemma 2.4 (Invariance) For k = 1, 2, 3... let Σ k 0 ⊂ Σ 0 be the subset consisting of points lying to the right of the line The argument in Lemma 2.1 works directly for all orbits in Σ 1 0 . Accordindly, for points in Σ 1 0 , we can be sure that the pinwheel dynamics and the first return dynamics of the square outer billiards map coincide.
The Invariance Lemma implies that all forward orbits of both φ and Φ are bounded. By symmetry, the same goes for the backwards orbits. Hence, the Invariance Lemma implies Theorem 2.3 for the regular octagon. Compare §5.3. The Invariance Lemma is a special case of a general result concerning quasi-rational polygons. The polygon P is called quasi-rational if it may be scaled so that area(Σ k ∩ Σ k+1 ) ∈ Z ∪ ∞ for all k = 1, ..., 2n. Here indices are taken mod 2n, as usual. In case no sides of P are parallel, the above areas are all finite. For regular polygons, one can scale so that all the finite areas are 1. Hence, regular polygons are quasi-rational. Likewise, polygons with rational vertices are quasi-rational. As we mentioned in the introduction, it is proved in [VS], [K], and [GS] that all outer billiards orbits are bounded for a quasi-rational polygon. In [S3] we give a self-contained proof of this result, in case P has no parallel sides.
The case A = 1 corresponds to the square, a trivial case we ignore. K(A) is called (ir)rational iff A is (ir)rational. When A = p/q, we call the point (1/q, 1) the fundamental point, for reasons we explain in great detail in [S2] and briefly as follows. The orbit of any point (x, 1) has the same combinatorics as the point (1/q, 1) for any 0 < x < 2/q. For this reason, the point (1/q, 1) is a representative of the dynamics of points "arbitrarily close" to the top vertex of K(p/q) and on the same horizontal line as the vertex.
We will consider the arithmetic graphs for various choices of p/q. We will draw a certain projection of this graph into the plane. We will not specify the projection we use explicitly because it is tedious to do so. The fact is that Γ p/q lies in a thin neighborhood of a 2-plane in R 4 and a random projection will produce pictures very similar to ours. Indeed, any projection looks about the same, up to an affine transformation of R 2 . Consider the rational sequence {a n } which starts 0, 1 and obeys the rule a n = 4a n−1 + a n−2 . This sequence starts out 0, 1, 4, 17, 72, 305, . . .

We have lim
Here φ is the golden ratio.   We want to emphasize that our projection is such that the vertices of these polygons all lie in Z 2 . Were the polygons drawn to scale, each one would be about φ 3 ≈ 4.23 times as large as the predecessor. However, when we rescale them so that they are about the same size, a fractal structure emerges. Later in the paper, we will formalize what we mean to taking the rescaled limit of a sequence of arithmetic graphs, but we hope that the above informal discussion makes the general idea clear.
Another nice sequence of pictures is given by the quotients of the rational sequence {a n } where a 0 = 1 and a 1 = 2 and a n = 2a n−1 + a n−2 . In this case lim a n−1 /a n = √ 2 − 1. One of the quotients is 169/408. Figure 3.2 shows the picture of the corresponding arithmetic graph. One can see the fractal structure emerging just from this single polygon. There is one interesting feature of K p/q that one sees almost immediately. If pq is even, then K p/q is a closed embedded loop. If pq is odd, then K p/q is an open embedded polygonal curve. The difference derives from the fact that the orbit of (1/q, 1) is stable when pq is even and unstable when pq is odd. By this we mean that a small change in the kite parameter destroys the orbit of (1/q, 1) when pq is odd, but not when pq is even. We prove the above statements in [S2].
My program Billiard King 2 allows the reader to draw these pictures for any (smallish) rational parameter. Our monograph [S2] discusses these graphs in great detail. In fact, one could consider [S2] as an exploration of the arithmetic graphs associated to kites.

The Regular Pentagon
Let P be the regular pentagon. We scale P so that its vertices have the form ω k for k = 0, 1, 2, 3, 4. Here ω = exp(2πi/5) is the usual primitive 5th root of unity. In this case, we have maps π k : R 5 → C given by Here X = (x 0 , x 1 , x 2 , x 3 , x 4 ). The map π 1 is just the projection mentioned above. Note that π k and π 5−k agree up to complex conjugation. Thus, the only remaining interesting projection is π 2 . Relative to any convex polygon, any periodic point x lies in a convex polygon P x consisting of points that have exactly the same dynamics. The outer billiards map moves the tile P x around isometrically. The pictures we show of outer billiards will draw the orbits of these tiles, rather than the orbits of individual points, because the pictures are more revealing. Figure  3.3 shows the picture for the regular pentagon. In the case of the regular pentagon, there are two kinds of orbits, those lying in regular pentagon tiles and those lying in regular 10-gon tiles. This is worked out in [T2], and also discussed in [BC]. The smaller the tile, the longer the periodic orbit.
The left half of Figure 3.4 shows a plot of π 2 (Γ(P, p)), where p is a point of Σ 0 that lies inside a pentagonal tile. We choose the period to be fairly long, so that the actual size of the graph is quite large. One can see the emerging fractal structure in the rescaled picture. The right half of Figure  3.4 shows the corresponding picture for a periodic point that lies inside a 10gon tile. The reader can probably see that these tiles somehow fit together "hand-in-glove". Any choice of long periodic orbit will yield a picture that is essentially identical to one of the two above. In the case of the regular pentagon, the arithmetic graphs lie within a thin tubular neighborhood of a 2-plane in R 5 . Any other projection of the graph would look like an affine image of one of the two pictures shown above. This is why we say that, in the regular pentagon case, there are two fractal curves that somehow control the structure of the pinwheel dynamics.
As we remarked in the introduction, we do not offer proofs of these results, because we will give complete proofs of the analogous results for the regular octagon.

The Regular Octagon
Let P be the regular octagon. We scale P as in §2.4, and we define the projection maps as in §3.2. In the case, there are two interesting projections, π 2 and π 3 . (It turns out that π 4 always maps the graph into a line segment.) As we discuss in the introduction, in connection with Figure 1.3, we call a periodic orbit odd if it intersects Σ 1 0 , the half-strip from Figure 2.4., in 3 k points, for k odd. It turnso out that "half" the periodic orbits that start in Σ 1 0 have this property. The odd periodic orbits are the lightly colored ones in Figure 3.5 that happen to intersect Σ 1 0 . This includes all the lightly colored octagons that lie outside the first large ring of 8 octagons.  .6 shows some π 3 projections of the arithmetic graphs associated to odd orbits. For π 3 , the projections corresponding to the even orbits look similar. Note that Figure 1.2, which was drawn using the subdivision method discussed in §4.2, emerges as we rescale the pictures.  For the even orbits, the π 2 projection is an open curve that looks fairly similar. We refer the reader to the program OctoMap 2, where one can see much better pictures, in both the odd and even cases.

The Regular Heptagon
We can make the same constructions for the regular heptagon as we made for the regular pentagon and octagon. The analogue of Figure 3.3 exists, but is not yet understood. The two interesting projections in this case are π 2 and π 3 . Unlike the two cases we considered above, there is an explosion of distinct pictures in this case. Sometimes the π 2 projection looks nicer and sometimes the π 3 projection looks nicer. Sometimes both projections look incomprehensibly complex. Here are two simple examples, both π 2 projections. These examples do not even begin to capture the vast array of pictures one sees for the regular 7-gon. We encourage the experimentally-minded reader to explore the situation for themselves.

The Hausdorff Topology
Let K 1 , K 2 ⊂ R 2 be two compact subsets. We define δ(K 1 , K 2 ) to be the smallest ǫ such that K 1 is contained in the ǫ-tubular neighborhood of K 2 and vice versa. The function δ is known as the Hausdorff distance between K 1 and K 2 . Given any compact subset Ω ⊂ R 2 we let M(Ω) denote the set of compact subsets of Ω. Equipped with the function δ, the space M(Ω) is itself a compact metric space.
When we have a sequence of uniformly bounded compact subsets {K n } and we say that it converges, we mean that it converges in M(Ω) for some large compact Ω that contains all the individual sets. The set Ω just serves as a kind of container, so that we can speak about the convergence as taking place within a compact metric space. The notion of convergence we get is independent of the choice of Ω. Indeed, we could say more simply that One case of interest to is is when we have a sequence {P n } of polygons whose diameter tends to ∞. If we can a compact subset K and a sequence of similiarities {S n } such that S n (P n ) → K in the Hausdorff topology, then we call K a rescaled limit of {P n }. In this case, the contraction factor of S n necessarily tends to 0.

The Snowflake
We call the snowflake I 3 . Figure 4.1 shows the subdivision of a right-angled isosceles triangle into 5 smaller ones. If the long side of the triangle has length 1, then the square on the right hand side of the figure has side length √ 2 − 1. The three small triangles in the middle have the same size. To produce the snowflake, we start with the union of 8 isosceles triangles shown at the top right in Figure 4.2. Then we apply the subdivision rule iteratively. The Hausdorff limit is our snowflake. We denote this limit by I 3 . One nice feature of our construction is that I 3 contains all the vertices of the triangles at every stage of the construction, and the union of these vertices is dense in I 3 . Moreover, all these vertices lie in Z[ω], where ω is the usual primitive 8th root of unity. The triangles in our pictures are 2 colored in a natural way, according as to whether they point inward or outward. Assuming that we label a triange 0 if it points inward and 1 if it points outward, our subdivision rule changes the colors according to the following rule: 0 → 10001; 1 → 01110.
We will see the significance of this structure below when we examine the carpet.

A Hidden Symmetry of the Snowflake
For any right isosceles triangle T , let L(T ) denote the curve one obtains by iterating the basic snowflake substitution rule and taking a limit. Assuming that T has a distinguished side σ, let L(T, σ) denote the portion of L(T ) whose endpoints are the endpoints of σ. Let T , T 1 , and T 2 be the three right isosceles triangles shown in Figure  4.3. The two triangles T 1 and T 2 have the same size as each other, and are √ 2 − 1 times as large as T . Let A = L(T, σ), where σ is the edge of T bounded by the two white vertices. Let A 1 = L(T 1 , σ 1 ), where σ 1 is edge of T 1 bounded by the white and black vertex. Define A 2 = L(T 2 , σ 2 ) similarly.
Proof: Let d be the Hausdorff distance between A qnd A 1 ∪ A 2 . The substitution of T consists of 5 smaller triangles, T ′ 1 , ..., T ′ 5 , with T ′ 1 = T 1 and T ′ 2 ∪ T ′ 3 related to T 2 just as T 1 ∪ T 2 is related to T . There are edges σ ′ 2 and σ ′ 3 of T ′ 2 and T ′ 3 such that σ 2 = σ ′ 2 ∪ σ ′ 3 . The remaining triangles T ′ 4 and T ′ 5 lie to the left of the bottom white vertex of T .
. From this we see that the Hausdorff distance between A and A 1 ∪ A 2 is the same as the Hausdorff distance between A 2 and A ′ 2 ∪ A ′ 3 . But, by scaling, the latter distance is ( which of course forces d = 0. ♠

The Carpet
We call the carpet I 2 . The carpet is produced by substitution rule that is combinatorially identical to the one that produces the snowflake. This time, we have two shapes, parallelograms and trapezoids. The initial shapes have their vertices in Z 2 . Our figures below are accurate. Figure 4.4 illustrates how the parallelogram P is replaced by the sequence of 5 smaller parallelograms and trapezoids.
of smaller parallelograms and trapezoids. We say sequence here rather than union because the pieces in the sequence S T (T ) overlap each other. To make the substitution clear, we first draw P 1 ∪ T 2 ∪ T 3 . Then we add P 4 and P 5 . The partition is invariant under reflection in the vertical line of symmetry. Let X be a cyclically ordered finite list of parallelograms and trapezoids, similar to the ones above. We let |X| be the union of shapes in X. We let S P (X) denote the result of substituting S P (P ) for all parallelograms P ∈ X. Likewise we define S T (X). Note that S P (X) and S T (X) both have natural cyclic orders, inherited from the ordering on X. Our carpet is Here I 2 (0) is a union of 8 copies of T arranged in a square pattern that winds around twice. (We use 8 rather than 4 so that the seeds for I 2 and I 3 have the same cardinality.) Figure 4.6 shows the sets I 2 (n) produced by iterated substitution, for n = 0, 1, 2, 3. Since the pieces in overlap, there is more than one partition we could draw. We have chosen the partition in which every trapezoid is drawn above every parallelogram. .7 shows another substitution rule that generates I 2 . In Figure 4.7, we are showing how to replace a square by a subset of a square. Here we think of the dark triangles and quadrilaterals as markings that tell us how to orient the pieces when we iterate the basic rule. We obtained this rule by looking at Figure 4.6. The fractal obtained from this alternate rule is a subset of the Sierpinski carpet. It is obtained from the Sierpinski carpet by systematically deleting certain squares. Proof: We will start with the original rule and keep modifying it until we get to the alternate rule. Along the way, we show that the modifications don't change the limiting fractal.
For starters, we divide each parallelogram in half. In this way, we interpret the original substitution rule as a being generated by a rule for trapezoids and a rule for isosceles triangles. The left hand side of   Figure 4.5, we have drawn all the trapezoids on top. In drawing this piece, we arbitrarily chose to draw the left (divided) parallelogram on top of the right one. The substitution rule for the isosceles triangle does not respect the symmetry of the triangle. We record the asymmetry by orienting the hypotenuse of each triangle, as shown. The new substitution rule clearly generates I 2 . We still call our new rules S R and S T . Here R stands for a right isosceles triangle and T still stands for the trapezoid.  For the first modification, we add another trapezoid to S T (T ). This new trapezoid appears in S R (S T (T )), so the new rule rule generates the same limit. We give the same names to our new substitution rules. For the second modification, we delete two of the isosceles triangles. Call the deleted triangles R 1 and R 2 . Observe that S R (R k ) ⊂ S T (T ) for k = 1, 2. Therefore, the latest subdivision rule has the same limit as the original. We again call the generators of the rule S T and S R . This time S T and S R replace one piece by a union of pieces that have pairwise disjoint interiors.
From here it is a simple exercise to check that S R • S T implements the rules shown in Figure 4.7. ♠

The Map from the Snowflake to the Carpet
The initial seed for I 3 is a cyclically ordered list I 3 (0) of 8 isosceles triangles τ 1 , ..., τ 8 . The initial seed for I 2 is a cyclically ordered list I 2 (0) of 8 trapezoids T 1 , ..., T 8 , which wrap around twice, as we have already mentioned. We have a correspondence T i ↔ τ i between the two seeds.
Since the two substitution rules are combinatorially identical, we inductively get a surjective map from the triangles in I 3 (n) to the quadrilaterals in I 2 (n). This map respects the cyclic ordering on both sets, and it also respects the relation of descendence. Say that a shape τ n of I j (n) is a descendent of a shape τ m of I j (m) if the substitution rule, applied n − m times, to τ m , produces a list of shapes that contains τ n .
We define φ : I 3 → I 2 by taking the limit of our correspondence. Given x ∈ I 3 we can find a sequence {τ n } of triangles, with τ n ∈ X 3 (n), that accumulates on x. We define φ(x) to be the limit of the corresponding quadrilaterals in I 2 .
Proof: Suppose that {τ ′ n } is another sequence of triangles that converges to x ∈ I 2 . Let S n and S ′ n be the shapes of I 2 (n) corresponding respectively to τ n and τ ′ n . It suffices to prove that diam(S n ∪ S ′ n ) → 0. Call two triangles in I 3 (m) close if they are either identical or else consecutive in the cyclic order. Let d n be the largest integer such that τ n and τ ′ n are descendents of close triangles in I 3 (d n ). Since the distance between τ n and τ ′ n converges to 0, and I 3 is evidently an embedded curve, d n → ∞. We make the same definitions as above for I 2 . We can find close shapes Σ n and Σ ′ n in I 2 (d n ) such that S n is a descendent of Σ n and S ′ n is a descendent of Σ ′ n . Note that Σ n and Σ ′ n have intersecting boundaries in all cases. Also, the diameters of these shapes tends to 0 with n.
Essentially the same proof shows that φ is continuous. Since all the approximating correspondences are surjective, φ is surjective as well.
Remark: Note that we could get an equally canonical map if we compose φ with some isometry of I 2 or I 3 . This basic (though trivial) ambiguity comes up in Statement 3 of our Main Theorem below.

Geometry of the Map
Now we give some geometrical information about the map φ : I 3 → I 2 defined in the previous section. Note that I 3 contains the vertices of triangles in I 3 (n) for all n. Say that a special point of I 3 is a right-angled vertex of I 3 (n) for some n. The set A 3 of special points is dense in I 3 .
Say that a special point of I 2 is a midpoint of the long edge of some trapezoid in I 2 (n). We could equally define the special points to be the centers of the parallelograms. The two definitions coincide. Let A 2 denote the set of special points of I 2 . The set A 2 is the set of midpoints of the edges of the countable family of squares that arises from the substitution rule explained in §4.5.
Proof: Let v ∈ A 3 be some point. Then v is the right-angled vertex of a triangle τ 0 of I 3 (n) for some n. Note that v is also the right vertex of a triangle τ k of I 3 (n + k) for k = 1, 2, 3... The triangles τ 1 , τ 2 , ... all have the same type, either inward pointing or outward pointing.
Consider the outward pointing case first. In this case the quadrilateral T k of I 2 (n + k) corresponding to τ k is a trapezoid. Inspecting our subdivision rule, we see that T k+1 is the middle trapesoid of S T (T k ). Looking at Figure  4.5, we see that T k and T k+1 have a common distinguished point. This holds for all j.
In the inward pointing case, the quadrilateral P k corresponding to τ k is a parallelogram. Here P k+1 is the middle parallelogram of S P (P k ). But these parallelograms have a common center. The intersection P k = φ(v) is this common center. Looking at Figure 4.5 again, we see that the centers of the parallelograms coincide with distinguished points of trapezoids. So, again Our argument so far shows that φ(A 3 ) ⊂ A 2 . Any x ∈ A 2 is the distinguished point of some trapezoid T of some I 2 (n). But then there is a triangle τ of I 3 (n) which corresponds to τ . By construction x = φ(v), for the right vertex v of τ . Therefore φ(A 3 ) = A 2 . ♠ Let B 3 ⊂ I 3 denote the set of points that are acute vertices of triangles in I 3 (n) for all the different n. Then B 3 is dense in I 3 . Let B 2 ⊂ I 2 denote the set of vertices of quadrilaterals in I 2 (n) all the different n. The set B 2 is the set of corners of the distinguished squares mentioned above in connection with A 2 . The curve I 3 looks "oscillatory" in the neighborhood of any x ∈ B 3 . Any line through x intersects I 3 infinitely often in every neighborhood of x.
Proof: The proof is similar to the one for the previous result, so we will be a bit sketchy. Any x ∈ B 3 (n) is the acute vertex of a triangle τ k in I 3 (n + k). The triangle τ k+1 is either the first or last triangle in the list of 5 triangles in I 3 (n+k +1) that replaces τ k . Whether τ k+1 is "first" or "last" is independent of k.
Let T k be the quadrilateral of I 2 (n + k) corresponding to τ k . By construction, these quadrilaterals all share a common vertex, and φ(x) must be this common vertex. This shows that φ(B 3 ) ⊂ B 2 . The proof that B 2 ⊂ φ(B 3 ) is just as in the previous result. ♠ Remark: It is worth pointing out one more feature of the map φ: It is far from 1 to 1. The set I 2 (n), considered as a list of quadrilaterals, contains multiple copies of the same trapezoid. Many trapezoids appear 2 n times in I 2 (n). From this we see that, for any n, there are 2 n segments of I 3 that φ identifies. For this reason, the canonical surjection from I 3 to I 2 is a many-toone map. We think if it is a kind of fractal version of the universal covering map from the line to the circle.

A Hidden Symmetry of the Carpet
The snowflake has a hidden symmetry, as discussed in §4.3. Given the close correspondence between the carpet and the snowflake, we would expect a combinatorially identical hidden symmetry to appear for the carpet. This is indeed the case. In this section we describe the symmetry and sketch the proof.
The hidden symmetry of the carpet manifests itself in two ways, and this at first seems different from what happens with the snowflake. However, in the case of the snowflake, there are really two kinds of right-angled isosceles triangles, so the symmetry there actually does arise in two ways. The left side of Figure 4.7 shows a large parallelogram and two smaller shaded trapezoids. We can generate a subset of a suitably scaled copy of the carpet starting with the large parallelogram as a seed and then considering the portion of the resulting limit that connects the two white dots in Figure  4.7. Let A denote the resulting set. Likewise, we start with each shaded trapezoid as a seed, and consider the portion of the resulting limit that connects a black dot to a white dot. Let A 1 and A 2 be the resulting sets.
The right hand side of Figure 4.7 shows a trapezoid and two shaded parallelograms. We let B and B 1 and B 2 be the portions of carpets produced by the same construction as we did for the As, but interchanging the roles of black and white.
Proof: The proof here is formally isomorphic to what we did for the snowflake. We omit the details. ♠

Statement of the Result
Let ω = exp(2πi/8) be the usual primitive 8th root of unity. Let P be the regular octagon whose vertices are powers of ω. Let Σ 0 be the pinwheel strip associated to P as in §3.3. Let Σ 1 0 ⊂ Σ 0 denote the half-strip that lies to the right of the line x = 1 + Lemma 5.1 Relative to the the pinwheel map for the regular octagon, any periodic orbit that intersects Σ 1 0 nontrivially does so in exactly 3 k points for some k = 0, 1, 2.... Given a periodic point x ∈ Σ 1 0 , we define |x| to be the exponent k such that the pinwheel orbit of x intersects Σ 1 0 exactly 3 k times. We call a sequence {x n } ∈ Σ 1 0 a good sequence if |x n | → ∞ as n → ∞ and he congruence of |x n | mod 4 is odd, and independent of n.
Recall that π 2 and π 3 are the projections from R 8 to R 2 defined in the previous chapter. Define Let φ : I 3 → I 2 be the canonical surjection described above.
Theorem 5.2 (Main Theorem) Let {x n } be a good sequence. Also, let A n ⊂ R 8 be the arithmetic graph of x n . Then the following is true.
1. π 2 (A n ) and π 3 (A n ) are closed polygons for all n.
2. Let S k,n be dilation by s −|xn| k about the origin. Then the following limit exists.
5. Identifying points on π 3 (A n ) and π 2 (A n ) if they come from the same point on A n , we get a polygonal surjectin φ n : S 3,n π 3 (A n ) → S 2,n π 2 (A n ).
We have lim n→∞ φ n = F • φ. Here F is an isometry of I 2 and φ : I 3 → I 2 is the canonical surjection from the snowflake to the carpet.

Remarks:
(i) Experimentally, we see that Theorem 5.2 also holds when we consider sequences of points in Σ 0 − Σ 1 0 , but these cases lead to annoying complications. We are interested in establishing a nice robust version of the phenomenon, but not necessarily the sharpest possible version. (ii) The limits are exactly the same when |x n | ≡ 1 mod 4 and when |x n | ≡ 3 mod 4. The only thing that changes is the global isometry F . In the former case, F is orientation preserving (and can be taken to be the identity) and in the other case F is orientation reversing.
The rest of the paper is devoted to proving Theorem 5.2.

Restricting the Domain
Let P be the regular octagon, and let Σ 0 be the pinwheel strip described in §2.4. Consider the octagons O + k and O − k share a common vertex and fit inside Σ 0 as shown in Figure  5.2. Figure 5.2 shows the cases k = 1, 2, but the remaining cases look the same. We let R k be the region of Σ 0 bounded by Figure 5.2 shows the region R 1 , which is the main region of interest to us. Note that R k is translation equivalent to R 1 for all k ≥ 1, so the picture in Figure 5.2 is typical.
The first purpose of this chapter is to prove the Invariance Lemma. This result implies that each R k is forward invariant under the pinwheel map. Following this, we will prove Lemma 5.3 Each R k is an invariant set for the pinwheel map. Furthermore, if Theorem 5.2 is true for sequences in R 1 then it is true as originally stated.

The Pattern of Octagons
let P be as above. The octagons we described above are part of the infinite pattern of octagons shown in Figure 5.3. Figure 5.3 shows a part of an infinite set of octagons that, as it turns out, is invariant under the outer billiards map. Figure 5.3 also shows the strip Σ 0 .
The remaining octagons interpolate between these dark ones. The octagons are situated in such a way that the outer billiards map is entirely defined on the interior of each one. The octagons come in an infinite family of rings, or necklaces N 1 , N 2 , N 3 , .... The octagons O ± k are precisely the two octagons of Σ 0 ∩ N k . Compare [GS] and [K]. Call two octagons O 1 ∈ N k and O 2 ∈ N k+1 close if they are as close together as possible. Two close octagons determine a polygonal region "between them" like the one that is shaded in Figure 5.4. Call such a region a buffer . If the two octagons belong to the sector from Figure 5.4, then the buffer is mapped between N k and N k+1 . But then, by symmetry, all buffers are mapped between N k and N k+1 . But every point between N k and N k+1 is contained in a buffer. ♠

Invariant Domains in the Strip
Let Σ ′ 0 denote those points in Σ 0 that lie to the central octagon P . A point p lies in Σ ′ 0 if every vector pointing from P to p has positive x coordinate. Let Φ ′ : Σ ′ 0 → Σ ′ 0 be the first return map of the φ 2 , the square outer billiards map.
Proof: For k ≥ 2, the region between N k and N k+1 intersects Σ ′ 0 exactly in the set R k . ♠

Remark:
The region between N 1 and N 2 intersects Σ 0 in a set that is somewhat larger than R 1 ., as one can see by looking carefully at Figure 5.3. It is for this reason that Corollary 5.5 fails for R 1 .
Corollary 5.6 For k ≥ 4 the set R k is invariant under Φ, the pinwheel map.
Proof: For k ≥ 4 the argument in Lemma 2.1 goes through, and shows that Φ = Φ ′ . ♠ Below we will prove the following result.
Corollary 5.8 The set R k is Φ-invariant for all k ≥ 1.
Proof: By Lemma 5.7, translation by the vector 4( √ 2 + 1, 1) conjugates the action of Φ on R 1 to the action of Φ on R 5 . We already know that R 5 is invariant under Φ and the conjugation property implies the same result for R 1 . A similar argument takes care of R 2 and R 3 . We have already handled the remaining cases. ♠ Remark: Note that Φ and Φ ′ do not coincide on R 1 , because Corollary 5.5 is false for R 1 whereas Corollary 5.8 is true. These maps in fact coincide for k = 2, 3, 4....

Proof of the Invariance Lemma:
We want to show that Σ k 0 is Φ invariant. Let N + k be the set of half-octagons obtained by taking the right halves of all the octagons in N k . Since φ 2 is a piecewise translation, the set N + k is invariant under φ 2 . But then the set Hence, by the argument in Lemma 2.1, the set S k is Φ-invariant for k ≥ 4. As in the proof of Corollary 5.8, we now conclude that S k is Φ invariant for all k = 1, 2, 3... Finally Proof of Lemma 5.3: Suppose we want to prove Theorem 5.2 for a sequence of periodic points {x n } in Σ 1 0 . Since Φ is the identity on each of the orbits N k , we have x n ∈ R kn for large n. Chopping off the initial portion of the sequence, we can assume that x n ∈ R kn for all n.
By Lemma 5.7, we can find a point y n ∈ R 1 ∪ R 2 such that x n and y n have the same arithmetic graph. Hence, it suffices to prove Theorem 5.2 for the sequence {y n } ∈ R 1 ∪ R 2 .
The intersection R 1 ∪ R 2 is a single point, namely ζ = (2 + 2 √ 2, 1). We call two points specially related if reflection through ζ interchanges the two points. We check by hand the following property, which we call Property P: If y and z are specially related then Φ(y) and Φ(z) are specially related and Φ(y) + Φ(z) = 0.
From Property P we see that the arithmetic graphs of y and z are isometric to each other. Using this basic principle, we can replace each y n ∈ R 2 by the specially related point z n without changing the isometry type of the rescaled limits of the arithmetic graphs. ♠ Remark: In §7 we will explain in detail how we actually check Property P.

Equivalent Points in Strips
The rest of the chapter is devoted to the proof of Lemma 5.7. In this section we make a general observation about strip maps. In the section following this one, we will apply our observation to the case of the regular octagon.
Let Σ 1 and Σ 2 be non-parallel strips. Let V and W 1 , W 2 be the three vectors shown in Figure 5.3. We say that p, q ∈ Σ 1 are related if p − q = kW 1 for some integer k. Likewise, we say that p, q ∈ Σ 2 are related if p − q = kW 2 for some integer k. Lemma 5.9 Let f be the strip map associated to (Σ 2 , V ). If p, q ∈ Σ 1 are related then f (p), f (q) ∈ Σ 2 are related.
Proof: Our statement is an affinely invariant one. So, we normalize our strips so that they are perpendicular and each have width 1. In this case, f translates the horizontal squares A, B, C, ... to the vertical squares with the same labels. If p, q ∈ Σ 1 are related then they are in the same positions relative to the horizontal squares that contain them. But then f (p), f (q) ∈ Σ 2 are in the same position relative to the vertical squares that contain them. Hence f (p) and f (q) are related. ♠
The vector W 0 = W 1 is parallel to both pointed strips Σ 0 and Σ 1 . The vector W 2 = W 3 is parallel to both Σ 2 and Σ 3 , and so on. We say that two points p, q ∈ Σ k−1 are equivalent We let µ k−1 (p, q) be the integer in Equation 17. Let f k be the strip map associated to (Σ k , V k ), as in §2.3. Let m k (p) be as in Equation 2. That is, Lemma 5.10 Let f = f k . If p, q ∈ Σ k−1 are equivalent and k is odd, then f (q), f (q) are equivalent in Σ k and µ k (f (p), f (q)) = µ k−1 (p, q); m k (p) = m k (q).
Proof: By rotational symmetry, it suffices to consider the case k = 2. In this case, the strips Σ 1 and Σ 2 , as well as the vectors W 1 and W 2 and V = V 2 are related precisely as discussed in §5.5. Lemma 5.9 now implies that p and q are equivalent in Σ 2 and µ 2 (p, q) = µ 1 (p, q). Referring to Figure 5.4, which is an affine image of the octagon picture, the number µ 1 (p, q) counts the number of parallelograms one needs to shift in order to move p over to q. For instance, if p were in parallelogram A and q were in parallelogram C in Figure 5.4, then µ 0 (p, q) = 2. From Figure 5.4, we see clearly that m 2 (q) = m k (p) + µ 1 (p, q). ♠ Now we can finish the proof of Lemma 5.7. Suppose that p, q ∈ Σ 0 are equivalent. Let µ = µ 0 (p, q). Then, referring to Equation 4, we have Equality 1 comes from Lemmas 5.10 and 5.11, and Equality 2 comes from the fact that V 6 − = V 2 and V 8 = − V 4 .

The Map
The work in the previous chapter reduces the proof of Theorem 5.2 to the study of the pinwheel map Φ : R 1 → R 1 , where R 1 is shown in Figure 5.2. This first return map turns out to be a polygon exchange map. In this chapter, we will briefly discuss a simpler but related polygon exchange map. Though the simpler map is not the one we will ultimately study in our proof of Theorem 5.2, we think that it will prepare the reader for the more complicated system we do study. First, the basic shapes that arise in the simple system here arise in the more complicated system we study later. Second, both the system here and the one we do study have a renormalization scheme. It is the renormalization scheme for the first return map that leads to the self-similar nature of the arithmetic graphs.
The dynamical system we study here is well known, and indeed also arises in the study of outer billiards: It is the first return map to a certain invariant domain for a dynamical system generated by the outer billiards map and the rotational symmetry group of the regular octagon. Compare [T2] and [BC]. The system is a self map of the kite-shaped region X, shown as the shaded region in Figure 6.1. The region X is best defined in terms of a large regular octagon. The smaller regular octagon, which is a subset of X, is drawn in for later reference. As shown in Figure 6.2, the region X can be partitioned in two ways into right angled isosceles triangles, There is a unique orientation-preserving isometry φ A : A 1 → A 2 . The map φ A rotates 3π/4 radians clockwise about the center of the small octagon in Figure 6.1. Likewise, there is a unique orientation preserving isometry φ B : B 1 → B 2 . The map φ B rotates π/4 radians counterclockwise about the center of the big octagon in Figure 6.1. We have a map φ : X → X which restricts to φ A on A 1 and φ B on B 1 . The map φ is defined except on the segment common to A 1 and B 1 .

The Renormalization Scheme
Let O ⊂ X denote the inner octagon in Figure 6 Figure 6.3. We have partitioned X ′ into two pieces, which we call A ′ 1 and B ′ 1 . The third power φ 3 maps X ′ to itself. Figure 6.2 shows the pieces A ′ 2 = φ(A ′ 1 ) and A ′ 3 = φ(A ′ 2 ) and B ′ 2 = φ(B ′ 1 ) and B ′ 3 = φ(B ′ 2 ). We have not drawn A ′ 4 , B ′ 4 ⊂ X ′ , but we observe that A ′ 4 and B ′ 4 relate to A ′ 1 and B ′ 1 in the same say that A 2 and B 2 relate to A 1 and B 1 . More precisely, there is an orientation reversing dilation Θ : X ′ → X such that on X ′ . The map Θ is the remormalization map. Having Θ by itself is nice, but we have a second property that really pins things down. Namely, In other words, every point of X − O lies in the orbit of a point in X ′ .

The Periodic Points
Our remormalization scheme allows us to get a complete understanding of the periodic points of φ.
that has tile-period 3. We set The tiles O ′ k for k = 0, 1, 2 all have tile-period 3. They comprise a tile-orbit. Now we iterate. By Equation 21, the three octagons all have tile-period 9. Setting we produce 9 small octagons O ′′ 0 , ..., O ′′ 8 that all have tile-period 9. Next, we produce 27 small octagons O  Thus, we have produced, for each n = 0, 1, 2, 3..., a periodic octagonal tile having tile-period 3 n . We claim that every periodic point is contained in one of these octagons. To see this, we use Equation 22. Clearly, the only periodic points of order 1 lie in O 0 . Suppose N is the smallest positive integer for which we have not proven our result. Let y ′ be a periodic point of period N.
Since N > 1, we have y ′ ∈ X − O. By Equation 22, the point y ′ lies in the orbit of some point x ′ ∈ X ′ . Let x = Θ(x ′ ). Note that φ(X ′ ) and φ 2 (X ′ ) are disjoint from X ′ . Since φ N (x ′ ) = x ′ , we must therefore have N = 3M for some integer M. But then, by Equation 21, we see that x has period M. By induction, x lies in one of our octagonal tiles. But then, by construction, so does x ′ . Now we know that x ′ is one of the periodic points we have already studied. So, the same goes for y ′ , the original point of interest to us.
Using the renormalization scheme, we have been able to classify all the periodic points of the system. Incidentally, we note that the complement of the octagons has dimension larger than 1, and the set of points where some iterate of φ is undefined has dimension 1. Therefore, φ has some aperiodic points. This is the same argument Tabachnikov [T2] gives for the regular pentagon.

The Partition
We will work with the region R 1 from Lemma 5.3. Both sides of Figure 7.1 show R 1 . Note that R 1 is the union of 4 copies of the region X from the previous chapter.  into the maximal pieces on which Φ and Φ are constant, and the right hand side shows the images of these pieces under Φ. We will give coordinates for these tiles below.
Just knowing that Φ is a piecewise translation, we can nearly pin down the action of Φ from Figure 7.1. The problem is that there are some pairs of triangles, having identical shading, that are translates of each other. Such pairs are specially situated: One triangle in each such pair lies on the left hand side of R 1 and the other triangle lies in the right hand side. To pin down the action of Φ exactly, we mention that Φ maps any triangle on the left (respectively right) hand side of R 1 to a triangle on the right (respectively left) hand side of R 1 .
Remark: It seems worth also mentioning that Φ maps any quadrilateral or pentagon on the left (respectively right) hand side of R 1 to another quadrilateral or pentagon on the left (respectively right) hand side of R 1 . Finally, Φ fixes each of the central octagons.
Φ has one obvious symmetry and one hidden symmetry. Let ρ 1 be the order-2 rotation about the center point of R 1 . Then Φ commutes with ρ.
To describe the hidden symmetry, we observe that it is better to think of R 1 as a subset of an infinite cylinder. Define σ(x, y) = (x, y+2). The squaredmap σ 2 maps the bottom boundary of Σ 0 to the top one. The quotient, obtained by identifying the two boundary components, is a cylinder. We think of R 1 as a subset of this cylinder, so that certain pieces on the top of R 1 are contiguous with pieces on the bottom. This point of view makes the picture look more symmetric. Consider the magenta pentagon K ′ shown on the middle left hand side of Figure 7.1. Let K ′′ be the magenta triangle such that K = K ′ ∪ K ′′ is a kite, isometric to the rest of the kites in the picture. Φ(K ′ ) lies at the very top of R 1 and Φ(K ′′ ) lies at the very bottom. Under the identification we have been discussing, Φ(K ′′ ) is just the continuation of Φ(K ′ ). So, when we think of R 1 as a subset of a cylinder, K is a single tile on which Φ is constant. The other pentagon/triangle pair on the left hand side of Figure 7.1 has the same analysis. Considered this way, we see that the partition of R 1 consists just of kites, triangles, and octagons.
Finally, we mention the hidden symmetry. Once we interpret R 1 as being a subset of the cylinder, Φ commutes with σ.
Remark: It turns out that Φ does not share the same symmetries. That is, it is not true that the maps Φ and Φ • ρ and Φ • σ coincide. However, as we will see, there is some relation between these maps.

Notation and Coordinates
This section does not contribute to the mathematics at all. We include it for readers who would like to see explicit coordinates to that they can reproduce our experiments and calculations on their own. Let Let O 3 be the red octagon in Figure 7.  Figure 7.2 below. Now we distinguish 4 special points.
• The point c 2 = (3s, 3)/2 is the center of the top half of R 1 .
• The point c 3 = (2 + √ 2, 2) is the center of O 3 .   Figure 7.2 shows the B labels. The union B 2 ∪ B 3 is the kite that lies to the left of the red octagon in Figure  7.1. We have tried to shade B 3 in such a way that we point out O 4 ⊂ B 3 .
(28) We divide these coordinates in half to get the coordinates of B 3 .
We divide these coordinates in half to get the coordinates of B 3 . We can deduce the remaining coordinates just from what we have already given. For instance, The remaining polygons in the partition of R 1 all have the form Here either B = B j or B = B 2 ∪ B 3 . Now we explain briefly how we verify that the return map Φ is as stated. We explain this for B 3 . The check is the same for the remaining files. Recall that Φ = f 16 •...•f 1 , where f k is the strip map associated to the pair (Σ k , V k ). We verify that there are integers m 1 , ..., m 16 such that And so on. By convexity we just have to check this on the vertices of B 3 . This is a short calculation we omit. This calculation shows not only that Φ(B 3 ) = B 16 3 , but also that Φ is constant on the interior of B 3 .

The Compressed System
Let R ⊂ R 1 denote the top half of R 1 . The region R is colored red and magenta on the left half of Figure 7.1. Note that R is a fundamental domain for the action of σ on R 1 . We define a new dynamical system Ψ : R → R as follows: In other words, we use the action of σ to move everything into R. • B 5 = ρ 5 3 (B 1 ) and B 6 = ρ 5 3 (B 2 ∪ B 3 ) and B 7 = ρ 5 3 (B 4 ). • B 8 = ρ 2 3 (B 1 ) and B 9 = ρ 2 3 (B 2 ∪ B 3 ) and B 10 = ρ 2 3 (B 4 ).
The regions B 5 , B 6 , B 7 all lie in the upper right corner of R. The regions B 8 , B 9 , B 10 lie in the middle of R on the left side. The remaining 11 regions are symmetrically placed with respect to the first 11. Again for the record, the red colored regions are 4, 6, 7, 8, 9; j = 0, 1.
We will use this notation system in the next chapter, just so that we can list things in a completely explicit way.  Figure 7.1 does for Φ. The left hand side shows the partition of R into maximal regions on which Ψ is constant. The blue polygons are the ones on which Ψ = Φ and the red polygons are the ones on which Ψ = σ • Φ. The right hand side shows the images of these pieces under Ψ. Once we mention that Ψ is a piecewise translation that maps all the triangles on the left (respectively right) side of R to triangles on the right (respectively left) side of R, the partitions alone determine Ψ. We also remark that Ψ maps the kites and pentagons on the left (respectively right) side of R to the left (respectively right) side of R.
The map Ψ has a symmetry that it inherits from Φ, and also a new one. First, Ψ commutes with the rotation ρ 2 about the center point of R. Second, the partition on the right hand side of Figure 7.3 is a mirror image of the one on the left. (The line of symmetry joins the centers of the red octagons.) Finally, Ψ moves the one partition to its mirror image by way of translations.

Classification of Periodic Orbits
Lemma 7.1 p ∈ R is a periodic point for Ψ if and only if p is a periodic point for Φ.
Proof: We write φ 0 = ψ 0 = p. Let φ n be the nth iterate of φ 0 under Φ and let ψ n be the nth iterate of ψ 0 under Ψ. Since Φ commutes with σ, we have where d n counts the number of k ∈ {0, ..., (n − 1)} for which ψ k lies in a blue region in the partition of R (on the left side of Figure 7.3.) Suppose that p has Φ-period n. Then φ n = φ 0 . This means that σ dn (ψ n ) = ψ 0 . Since both ψ n and ψ 0 belong to R, we must have d n even. Hence ψ n = ψ 0 . This shows that the p is periodic for Ψ. On the other hand, suppose that p has Ψ-period n. Then ψ n = ψ 0 . If d n is even then φ n = φ 0 . If d n is odd, then d 2n = 2d n because ψ n+k = ψ k for each k = 0, ..., n. Hence φ 2n = φ 0 . Hence p is Φ-periodic. ♠  We will establish the result about the packing using a renormalization scheme that is very similar to the one used in the previous chapter. The remormalization scheme is based on the dilation We have Θ(S) = R, where S ⊂ R is the portion of R between the two octagons O 1 , O 2 ⊂ R. The left hand side of Figure 7.4 below shows R in blue. We will use the renormalization scheme to classify the periodic points of Ψ.
. Then • There is a self-similar packing of regular octagons in S, each of which is translation equivalent to O k 1 (or O k 2 ) for some k. (See Figure 7.4.) • Every periodic point of Ψ belongs to one of the octagon interiors, and its period is the same as the tile-period of the octagon containing it.
• Every octagon in the packing has tile period 3 k for some k = 0, 1, 2, ..., and such an octagon either lies in the orbit of O k 1 or the orbit of O k 2 . These are the blue octagons in Figure 7.4.

Proof:
We see by inspection that φ 3 (S ′ ) ⊂ S ′ . Indeed, the left hand side of Figure 7.5 shows S in blue, the middle picture shows Ψ(S) in blue, and the right hand side shows Φ 2 (S) in blue. Proof: A short calculation establishes the following two facts.
The same analysis as in the previous chapter produces the packing of octagons, together with the claims about their tile periods. The only new feature of the situation here is that the map Ψ is a piecewise translation, whereas the map from the previous chapter had a rotational component. Since Ψ is a piecewise translation, each point in a octagonal tile has exactly the same period as the tile itself. ♠

Proof of Lemma 5.1
Thanks to the analysis done in §5 it suffices to prove that every periodic point of R 1 has Φ-period 3 k for some k = 0, 1, 2, .... We have already worked out the structure of the periodic points of the Ψ-system, and we will use this to get the desired information about the periodic points of the Φ-system. There is a 2 to 1 map F : R 1 → R. which, by construction, carries periodic points of Φ to periodic points of Ψ. Moreover, this map conjugates the action of Φ on R 1 to the action of Ψ on R. From this, we see that every Φ-periodic orbit has period either 3 k or 2 × 3 k .
A parity check rules out the second possibility. Given a Ψ-periodic orbit p 0 , p 1 , ..., p N −1 , we let σ i = 0 if p 0 lies in a blue region of R and other wise σ i = 1. We just need to check that N −1 i=0 σ i is even. We check that the parity of the sum is preserved under the renormalization operation. Since the sum obviously works out for the large octagons -i.e., when N = 1, it works out in general.
The parity check is a finite calculation, as we now explain. Suppose we start with a point z ∈ R. Let w 0 = Θ −1 (R). Let w j = Ψ j (w 0 ). We just have to prove that σ ≡ σ 0 + σ 1 + σ 2 mod 2. The pattern repeats exactly for the second 11 regions. This completes the proof of Lemma 5.1.

The Basic Approach
Let R 1 be our basic region, partitioned as on the left hand side of Figure 7.1.
To each region r ∈ R 1 we choose and p ∈ r and define g k (r) = π k ( Φ(p)).
Here Φ(p) ∈ Z 8 is the vector from Equation 4. Since Φ is constant on the region r, we see that our definition is independent of the choice of p ∈ r. If p is part of some orbit, then g k (p) ∈ R 2 is the side of the edge of π k (Γ) that corresponds to (p, Φ(p)).
Given an initial point p 0 ∈ R 1 we consider the forward orbit p 0 , p 1 , p 2 , ... We have a sequence of regions r 0 , r 1 , r 2 , ... and a corresponding sequence g k (r 0 ), g k (r 1 ), g k (r 2 ), ... These vectors are the successive sides of the projection π k • Γ(p).

The Compressed Approach
Given the nice renormalization scheme we discussed in the previous chapter, we prefer to work with the compressed system Ψ : R → R, as defined in §7.3. The region R is colored as in Figure 7.3.
Recall that R is the top half of R 1 . Let R ′ be the bottom half. Let p 0 , p 1 , p 2 , ... be a Ψ orbit in R. Let q 0 , q 1 , q 2 be a Φ orbit in R 1 such that p 0 = q 0 . Let σ i = 0 if p i lies in a blue region of R on the left hand side of Figure 7.3, and σ i = 1 otherwise.
We define the accumulated parity That is, we count the number of times that the orbit lands in a red region on the left hand side of Figure 7.3. The sequence {s n } is a binary sequence that keeps track of whether p n = q n or not. The accumulated parity is the additional information that lets us "lift" an Ψ orbit on R to a Φ orbit on R 1 .
Lemma 8.1 s n = 0 if and only if p n = q n .
Proof: This follows from two facts. First, σ i = 0 iff Φ(q i ) and q i lie in the same half of R 1 , Second, Φ : R 1 → R 1 commutes with the map interchanging R and R ′ . ♠ To each region r ∈ R, we associate 4 vectors according to the following rule.
Our notation is as follows.
In the next section we will explain how these vector assignments combine with a combinatorial substitution rule to generate the graphs.

The Substitution Approach
Suppose that we have some orbit p 0 , p 1 , p 2 , .... We let and consider the renormalized orbit p ′ 0 , p ′ 1 , p ′ 2 , .... Let s j = σ 0 + ... + σ j−1 be the accumulated parity of the original orbit. Likewise define s ′ j . Let r j be the region of R containing p j , and likewise define r ′ j . In §7.5 we explained the sense in which the renormalization scheme respects the accumulated parities. This fact implies that Given equation 44, the pair (s j , r j ) determines the triple Recall that we have chosen a particular listing for these 44 possible (region, parity) pairs. What we are saying is that the numerical code for the original orbit determines the numerical code for the renormalized orbit, by way of a substitution scheme in which one number is replaced by 3 numbers. Here is one quarter of the substitution rule.
0 → 9 25 39 1 → 10 14 5 2 → 10 12 17 3 → 10 12 16 4 → 9 23 27 5 → 8 36 28 6 → 8 35 17 7 → 9 24 6 8 → 9 26 6 9 → 9 26 7 10 → 9 25 40 The rest of the pattern can be deduced from symmetry and from what we have already written. We point out two involutions on the set {0, ..., 43}. The first of these has the action n → n ± 22. The second one has the action n → We start with 0, and iterate the substitution rule k times. Then we replace each number by the relevant vector. The resulting list of vectors is the set of edges of the projection of the arithmetic graph. We call the resulting path G 2 (k) or G 3 (k), depending on whether we use the G 2 vectors or the G 3 vectors.
To generate G 2 (2) we go one more step. , 25, 39 → 9, 26, 7, 32, 34, 38, 41, 2, 28. Then we make all the substitutions and accumulate the vectors. We discover in this case that G 2 (2) is not closed. We check that G 2 (k) is closed if k = 1, 3, 5, 7 and open if k = 2, 4, 6, 8. In §9.3 we will prove that this pattern persists for all k. Our proof there, in particular, implies Statement 1 of the Main Theorem.
9 Taking a Better Limit 9.1 Subsequential Limits Note that G 2 (k) and G 3 (k) have natural parametrizations, coming from the ordering on the edges. Define We notice that Γ 2 (k) and Γ 2 (k + β) closely follow each other as parametrized curves when β = 4. This property does not hold for smaller β. When β = 2, the two curves Γ 2 (k) and Γ 2 (k + β) are close in the Hausdorff metric, but not close as parametrized curves. We also notice that Γ 3 (k) and Γ 3 (k + β) closely follow each other closely when β = 2 but not when β = 1. Note that β = 4 is the lowest number that works well for both curve families. This accounts for the dependence on the mod 4 congruence that appears in the Main Theorem, which involves the subsequential limits The 4th power of our substitution rule is our basic object of study. With this rule, each number is replaced by 81 numbers. In geometric terms, each G 2 vector g 2 (n) is replaced by a polygonal path g ′ 2 (n) of length 81. This path consists of 81 other G 2 vectors, scaled down by √ 3. Likewise, each G 3 vector g 3 (n) is replaced by a polygonal path g ′ 3 (n) of length 81. Let Rg 2 (n) denote the vector that points from the tail of g ′ 2 (n) to the head of g ′ 2 (n). Likewise define Rg 3 (n). We notice that g i (n) and Rg i (n) are nearly the same vector for each choice i = 2, 3 and each n = 0, ..., 43. We think of R as a renormalization operator , which replaces one vector by another one that is very close to it. It makes sense to define R k g i (n) as follows: • We iterate the substitution rule 4k times.
• We replace each number by the appropriate g i vector.
The key to analyzing our limits is to looked at the fixed point of the renormalization operator.

The Fixed Point of Renormalization
For motivational purposes (only) we mention the Perron-Frobenius Theorem.
Theorem 9.1 (Perron-Frobenius) Let T : R n → R n be a linear transformation represented by a matrix with all positive entries. Then T has (up to scale) a unique unit positive eigenvector u. Moreover, if v is any positive vector v, then we have v n → u, where v n = T n (v)/ T n (v) .
It turns out that g i (n) and Rg i (n) are not in general the same vector. The Perron-Frobenius Theorem suggests to us that we consider the alternate assignment n → λ i (n) := lim s→∞ R s g i (n).
Doing things this way is analogous to finding the Perron-Frobenius eigenvector of a transformation T by taking the limit of iterates of T applied to some conveniently chosen initial vector v. In case the limit u is expected to have nice properties -e.g. algebraic coordinates -one might hope to guess u by looking at the decimal expansions of a fairly high iterate. Once we have made a guess, it is trivial to verify that it works. This is what we did. Our new assignment for G 2 has the same symmeties as in Equation 40, so the 10 vectors we list suffices to describe the whole thing.
This assignment has the same symmetries as the original one, and these symmetries let one deduce the remaining vectors in the assignment. The starred equalities indicate that no change has been made. Curiously, we have new = old + ǫ(1, −1); ǫ ∈ {−1, 0, 1}.
That is, the factor of σ k is replaced by 0 in Equation 41. In light of these symmetries, our 10 vectors below determine the whole thing.
Let Λ i (k) denote the version of Γ i (k) produced by the new vector assignments. Our new assignments are nicer, but we need to prove that the Λ paths have the same limits as the Γ paths. Once we know this, we can throw out the arithmetic graphs, and work with the much nicer Λ paths. The rest of the chapter is devoted to analyzing and equating the relevant limits. Figure 9.2 shows Γ 3 (3) and Γ 3 (7). Notice that these curves follow each other pretty well, but that a few of the vertices of Γ 3 (7) do not lie on Γ 3 (3). Figure 9.3 shows the improved Λ 3 (3) and Λ 3 (7). These curves are better related to each other. Note also that Γ 3 (7) and Λ 3 (7) are really just about the same curve. Proof: Let L k be the unscaled version of Λ k . The main idea in our proof is showing that G k and L k have the same endpoints. Assuming this result, it suffices to prove our result for the L curves. But the Λ curves are just scaled version of the L curves. So, it suffices to prove our result for the Λ curves. Given the endpoint-preserving property of our ideal substitution rule -see Equation 51 -we see that Λ i (k) is closed if and only if Λ i (k + 4) is closed. We check the conclusion of this lemma for the first few cases, and then apply the induction step to take care of the remaining cases.
Now we come to the interesting part of the proof, showing that each G curve has the same endpoints as the corresponding L curve. We treat G 2 and L 2 first. All paths start at the origin, so we just have to see that the other endpoints match. That is, we need to prove that Here {n i } is the numerical code for the relevant pair of paths, and N is the total combinatorial length. As we remarked above -see Equation 48 -we always have δ(n) = ǫ(1, −1) for ǫ ∈ {−1, 0, 1}. We check by hand the following 44 equations.
Here (m 1 , m 2 , m 3 ) is the substitution for n. Equation 53 implies that the sum in Equation 52 is invariant under substitution. We check that the sum is 0 in the first 4 cases, and then we see by induction that it is always 0. The proof for G 3 and L 3 works in the same way. This time, we have δ(n) = ǫ(0, 2) for ǫ ∈ {−1, 0, 1}. ♠

Proof of Statement 2
Let G and L be the unscaled versions of Γ and Λ respectively, as in the proof of Lemma 9.2. Say that a distinguished strand of G is one that comes from repeated substitution applied to a single edge. Likewise define distinguished strands of L. Such strands consist of 3 k segments. Any distinguished strand σ determines a vector V (σ) that points from the starting point to the ending point.
Lemma 9.3 Let g and l be corresponding distinguished strands of G(n) and L(n). Then V (g) and V (l) differ by at most 2 units.
Proof: Let g ′ and l ′ be the distinguished strands of the paths G(n − 1) and L(n−1) which give rise to g and l, respectively, upon substitution. The same argument as in Lemma 9.2 shows that By induction, we are reduced to the case of single edges. Now we apply Equations 48 and 50. ♠ Corollary 9.4 The distance between any corresponding vertices of G i (n) and L i (n) is at most 4 log 3 (n).
Proof: Both G i (n) and L i (n) start at (0, 0). Suppose we want to consider the kth vertices. Let γ be the arc of G i connecting (0, 0) to the kth vertex. Likewise define λ.
Using the base 3 expansion of k as a guide, we can decompose γ and λ into at most 2 log 3 (n) distinguished arcs. Our lemma now follows from the previous result and the triangle inequality. ♠ Lemma 9.5 Let i be 2 or 3. The sequences {Λ i (1 + 4k)} and {Λ i (3 + 4k)}, considered as a sequence of parametrized curves, converge in the L ∞ norm as k → ∞.
Proof: We will consider the first of these sequences. The second one has the same proof. The edges of Λ i (4k + 5) are obtained by replacing each edge of Λ(4k + 1) by a length 81 polygonal path that has the same endpoint. Define Each edge of Λ(4k + 5) is 1/9 = ( √ 3) −4 times as long as an edge of the same type in Λ(4k + 1). By similarity, we have once k is large enough that Λ i (1 + 4k) contains all the edge types. It suffices to take k = 1, in fact. Equation 55 implies that the distance between two successive curves in our sequence decreases exponentially. Hence, our curves form a Cauchy sequence in the space Map(S 1 , R 2 ), equipped with the L ∞ topology. Hence, our sequence converges. ♠ The following result implies Statement 2 of the Main Theorem.
Lemma 9.6 The sequences {Γ i (1 + 4k)} and {Γ i (3 + 4k)}, considered as a sequence of parametrized curves, converge in the L ∞ norm as k → ∞. The limits in this case coincide with the limits in Lemma 9.5.
Proof: We prove this first for i = 2. The i = 3 case is essentially the same. By Corollary 9.4, the distance between corresponding points of G 2 (1+4k) and L 2 (1 + 4k) is at most 4 log(8k). But then, by scaling, the distance between corresponding points of Γ 2 (1+4k) and Λ 2 (1+4k) is at most 4 log 3 (8k)( √ 3) −k , a quantity that tends to 0 exponentially fast. ♠ 10 The End of the Proof

Scaling Constants
In this chapter, we prove Statements 3, 4, and 5 of the Main Theorem.
Let I 2 and I 3 be suitably scaled versions of the sets discussed in §4. For i = 2, 3 and j = 1, 3 let Λ ij be the limit of the sequence {Λ i (j + 4k)}. To finish the proof of the Main Theorem, we need to show that Λ 21 = Λ 23 = I 2 ; Λ 31 = Λ 33 = I 3 .
Our first order of business is to explain how to scale I 2 and I 3 . Figure 10.1: I 2 seed and Λ 2 (1).
We will deal with I 2 first. Figure 10.1 shows the initial seed for I 2 , scaled so that it is well situated with respect to Λ 2 (1). By construction, Λ 2 (1) is an isosceles triangle with vertices (0, 0) and (3, 1) and (1, 3). Given the way that the I 2 seed sits with respect to this triangle, we deduce that the center of I 2 is (3/2, 3/2) and the left corner is (−3/2, 3/2). This gives us the copy of I 2 mentioned in the Main Theorem. Now we deal with I 3 . Figure 10.2 shows Λ 2 (1) and the union I 3 (1) of triangles obtained by applying the substitution operator to the I 3 seed. Λ 3 (1) is an isosceles triangle, with vertices (0, 0); The point (0, 0) is the apex of the triangle, the top vertex. This is enough to determine the placement of I 3 . Here is the nicest way we can think of describing the scaling. Let s = 1 + √ 2. This is the scaling factor that came up in the previous chapter. The I 3 seed consists in 8 isosceles triangles. One of the isosceles triangles has vertices (0, 0), (1/2, −s/2) and (−s/2, −1/2). This gives us the version of I 3 mentioned in the Main Theorem. Note that all the vertices of I 3 , as we have scaled it, lie in Q[ √ 2].

Proof of Statement 3
Let I 2 and I 3 be scaled as in the previous section. By Equation 51, we see that Λ ij contains the vertices of all the polygons of which it is a limit. Moreover, by scaling, the vertices of the approximating polygons become dense in Λ ij as the number of sides tends to ∞. We passed to the limit of renormalization precisely to arrange these two properties. We want to understand the sets in Equation 56 just from the placement various finite collections of vertices. Given the properties enjoyed by the vertices, we can establish Equation 56 simply by showing, for i = 1, 2 and for all odd j that the vertices of the polygons approximating Λ ij are contained in I i and become dense in I i as j → ∞.
We will deal with i = 3 first. Figure 10.3 shows a piece of the I 3 (3), together with a piece of Λ 3 (3). Notice that all the vertices of Λ 3 (3) in sight coincide with right-angled vertices of I 3 (3). Notice also that there seems to be (most of) a smaller copy of Figure 10.1 sitting near the top of Figure 10.3. Say that a special vertex of I 3 is a vertex of a right-angled triangle of some I 3 (n). We check by direct (computer) calculation that every vertex of Λ 3 (j) is a special vertex of I 3 for j = 1, 3, 5, 7, 9. This is an easy calculation that takes place entirely inside Q[ √ 2]. We can't make an infinite number of explicit calculations to deal with each successive polygon, so we describe a method, based on self-similarity, that proves everything we need from a finite number of calculations. For ease of exposition, we will work entirely with the sequence Λ 3 (1 + 4k). The sequence Λ 3 (3 + 4k) has a similar treatment. It is convenient to set Λ 3 = Λ 31 . So, Λ 3 is the limit of the sequence we are considering.
The polygon Λ 3 (1) is just a triangle, and too small to be of any use to us (beyond what we have already done with it above.) So, we consider the next polygon in the sequence. Each edge of Λ 3 (5) is a scaled copy of some λ 3 (n). We call n the type of the edge. The type belongs to the set S = {1, ..., 43} − {11, 22, 33}. Inspecting the numerical sequence associated to Λ 3 (5) -see §8.3 -we check that Λ 3 (5) has every possible type edge. We check the same thing for Λ 3 (9).
Suppose that A ⊂ Λ 3 (5) is an edge of type n and B ⊂ Λ 3 (9) is an edge of type n. The pair (A, B) determines a homothety Given the way Λ 3 is the limit of our sequence, we have Here Λ 3 (A) is the portion of Λ 3 between the endpoints of A, and likewise for Λ 3 (B). So, H is a homothety that carries a small portion of Λ 3 to an even smaller portion. We call H a special homothety associated to the pair (A, B). Every such pair gives rise to a special homothety. We call H good if Here I 3 (A) is the portion of I 3 bounded by the endpoints of A. Likewise we define I 3 (B). This definition makes sense because we have shown that the endpoints of A and B both lie in I 3 . Just to be clear, we mean that H sets up a bijection between I 3 (A) and I 3 (B) that maps endpoints to endpoints. Below, we will prove the following result.
The Good Homothety Lemma involves a finite number of special homotheties. We will show in the next section how one verifies that a special homothety is good using a finite calculation. Indeed, one can practically see this by inspection using our program OctoMap 2. Before we prove the Good Homothety Lemma, let us explain what it does for us. Suppose we want to show that the vertices of Λ 3 (13) lie in I 3 . Let v be a vertex of Λ 3 (13). If v is also a vertex of Λ 3 (9), we are already finished. Otherwise, there is some edge B of Λ 3 (9) such that v is one of the vertices associated to the replacement of B. That is, v lies on the polygonal path of Λ 3 (13) connecting the endpoints of B. Choose and edge A of Λ 3 (5) that has the same type as B.
Continuing in this way, we see that all vertices of Λ 3 (1+4k) lie in I 3 for all positive k. To take care of density, we let d k denote the maximum distance from a point of I 3 to a vertex of Λ 3 (1 + 4k). Since our special homotheties scale distances by a factor of √ 2 − 1, we see that In particular d k → 0 as k → ∞. This proves that the vertices of Λ 3 (1 + 4k) becomes dense in I 3 as k → ∞.
In short, the Good Homothety Lemma implies Statement 3 of the Main Theorem.

Proof of the Good Homothety Lemma
In §4.2 we described the basic substitution rule for the snowflake, in which each isosceles triangle is replaced by 5 smaller ones. We started with a seed, consisting 8 isosceles triangles arranged in a cyclic pattern, and then iteratively replaced each triangle by the smaller ones.
Here we describe a more conservative approach to the construction. Let L 1 and L 2 be finite cyclically ordered lists of isosceles triangles. We write L 1 → L 2 if one obtains L 2 from L 1 by replacing one of the triangles of L 2 by the 5 smaller ones from the substition rule and adjusting the cyclic ordering in the obvious way. We call a list L of triangles admissible if we have a finite chain I 3 (0) = L 0 → ... → L n . The specific lists I 3 (n), produced in §4.2 are examples of admissible lists.
We say that a special vertex of I 3 is a right-angled vertex of some I 3 (n). An equivalent definition is that a special vertex of I 3 is a right-angled vertex of some admissible list. Let {v k } be a finite list of special vertex. We say that an admissible list L is compatible with {v k } if each point v k is a vertex of some triangle in L. We say that L is the minimal pattern for {v k } if L is compatible with {v k } and there is no L ′ such that L ′ → L and L ′ is compatible with {v k }.
Remark: For our proof of the Good Homotopy Lemma, we do not need to know that the minimal pattern associated to a finite list of vertices is unique, but we emphasize that the minimial pattern is unique. The uniqueness comes from the tree-like nature of the subdivision rule. We simply start with the seed and replace triangles only when necessary. After a finite number of steps we arrive at the minimial pattern.
Let A be a line segment whose endpoints are special vertices of I 3 . We let J ′ 3 (A) be the minimal pattern associated to the endpoints of A. We don't care so much about the whole pattern, but only the portion related to A. We let J 3 (A) denote the portion of J ′ 3 (A) that lies between the two endpoints of A. Figure 10.4 shows the minimal pattern J 3 (A) when A is a certain type-1 edge of Λ 3 (5). The figure we have shown is completely representative of the local picture for the type 1 edges of Λ 3 (5). The associated minimal patterns are all the same. This is not really so surprising, because these vectors all are translates of each other. We also check that the local picture looks the same for all type 1 edges of Λ 3 (9). That is, the picture looks the same up to a scale factor of √ 2 − 1. So, suppose that A is a type 1 edge of Λ 3 (5) and B is a type 1 edge of Λ 3 (9). Then H(A, B) carries J 3 (A) to J 3 (B) because the patterns are identical up to scale. But J 3 (A) and J 3 (B) respectively determine I 3 (A) and I 3 (B). Hence H carries I 3 (A) to I 3 (B), as desired. This proves the Good Homotopy Lemma for edges of type 1. The key idea is that the minimal pattern J 3 (A) only depends on the type of A, up to scale.  .5 shows the minimal patterns associated to the types 2, 3, and 4. All the edge types except those of the form 6 + 11k and 9 + 11k have the same property we have already discussed. The local picture is the same, independent of the edge. By inspection, we see that the Good Homotopy Lemma holds for for all edge types except the 8 types we have mentioned.
For each of the remaining edge types, there are two local pictures. up to rotation, these two local pictures are the same for each of the edge types. Figure 10.6 shows the two pictures associated to the edges of type 6 + 11k. The edges are vertical.

Proof of Statement 4
In considering I 2 we make all the same definitions that we made for I 3 , except that we redefine what we mean by a special point. In the case of I 3 , the special points are the right-angled vertices of the triangles. In the case of I 2 , we call a point special if it has one of two properties: • It is the center point of a parallelogram of some admissible list.
• It is the center of the long edge of a trapezoid of some admissible list.
We check directly that every vertex of I 2 (j) is a special point, for the initial values j = 1, 3, 5, 7, 9. This check entirely involves calculations with rational points. We want to extend this result for all odd j. As in the Λ 3 case, we ignore the sequence Λ(4k + 3) and concentrate on the sequence Λ(4k + 1). The other sequence has essentially the same treatment.
To finish the proof, we just have to prove the analogue of the Good Homothety Lemma for I 2 . Given the combinatorially identical subdivision rules that produce I 2 and I 3 , it makes sense to say that a minimal pattern associated to I 2 is isomorphic to a minimal pattern associated to I 3 : The canonical bijection between the I 3 -shapes and the I 3 -shapes carries the one pattern to the other. For j = 1, 3, 5, 7, 9 we make the following observation: The minimial pattern associated to some edge of Λ 2 (j) is isomorphic to the minimal pattern associated to the corresponding edge of Λ 3 (j). There is a perfect correspondence between the two kinds of patterns.
Given the combinatorial isomorphism between the I 3 -patterns and the I 2 -patterns, the proof of the Good Homothety Lemma goes through, word for word for all the edges except those of type 6 + 11k and 9 + 11k. In these cases, there are two combinatorial types of minimial pattern, and we must make a separarate analysis. Figure 10.7 shows the relevant portions of the minimal patterns associated to edges of type 6 + 11k. On the left hand side we have a chain of 3 quadrilaterals and on the right hand side we have a chain of 4 quadrilaterals. The first two pieces agree on both sides. When we chop two pieces off, and superimpose what remains of the left and right sides, we get exactly the left hand side of Figure 4.7, the figure we used to illustrate the hidden symmetry of the carpet. The rest of the proof is just like what we did for the Λ 3 case, except that we use Lemma 4.6in place of Lemma 4.1.
The edges of type 9 + 11k have the same treatment. This completes the proof of the Good Homotopy Lemma in the I 2 case, and thereby completes the proof of Statement 4 of the Main Theorem.

Proof of Statement 5
Statement 5 takes a bit of unwrapping. We start with an arbitrary sequence {x n } of good points in the half-strip Σ 1 0 , and we let A n be the arithmetic graph corresponding to x n . We want to understand the map φ n : S 3,n π 3 (A n ) → S 2,n π 2 (A n ) Here S 2,n and S 3,n are the dilations discussed in the Main Theorem.
In light of the analysis done in the previous chapter, we can assume that S k,n π k (A n ) = Γ k (n).
Here n is odd, and Γ k (n) is as in §9.1. For ease of exposition, we now make the blanket assumption that n ≡ 1 mod 4. The case when n ≡ 3 mod 4 has the same treatment. The two paths Γ 2 (n) and Γ 3 (n) have the same number of sides, and so there is a canonical map φ n : Γ 3 (n) → Γ 2 (n).
There is a canonical map from Γ k (n) to Λ k (n), and this gives us a map ψ n : Λ 3 (n) → Λ 2 (n).
Our strategy is to first analyze the sequence {ψ n } of maps and then use Lemma 9.5 to get the desired information about {φ n }.
There is a sense in which ψ n and φ are compatible, we we now explain. The map φ is the limit of a sequence of canonical bijections between the admissible I 3 -patterns of triangles and the admissible I 2 -patterns of quadrilaterals. We call this bijection the shape bijection. We denote it by Φ. Note that Φ is canonical only up to composition with isometries of I 2 and I 3 . This accounts for the isometry F that appears in Statement 5 of the Main Theorem.
Given an edge e 3 of Λ 3 (n), there are two triangles T 1 and T 2 in the minimal pattern Λ 3 (e 3 ) whose right-angled vertices are the endpoints of e 3 . Let e 2 = ψ n (e 3 ) be the edge of Λ 2 corresponding to e 3 . We say that the pair (e 3 , e 2 ) is compatible if the endpoints of e 2 are special points of the two shapes Φ(T 1 ) and Φ(T 2 ). In case Φ(T 1 ) is a parallelogram, the relevant endpoint of e 2 should be the center point of this parallelogram. In case Φ(T 1 ) is a trapezoid, the relevant endpoint of e 2 should be the midpoint of the long side of this trapezoid.
We check that all relevant edge-pairs are compatible for n = 1, 3, 5, 7, 9. But our proofs of the Good Homotopy Lemma, in the two cases, involved combinatorially identical sets in each case. That is, whatever we did in the I 3 case carries over to the I 2 case via the shape bijection. From this we see, by induction and symmetry, that all relevant edge-pairs are compatible for all odd positive integers n.
Given this notation of compatibility, we have for some isometry F . The convergence takes place in the sense that the graph of ψ n converges, to the graph of φ in the Hausdorff topology. In particular, the left hand side of Equation 66 does have a limit. But Lemma 9.6 now says that lim n→∞ φ n = lim n→∞ ψ n .
Putting the two equations together gives us Statement 5 of the Main Theorem. This completes our proof of the Main Theorem.