Computational Aspects of Escher Tilings by Ellen Gethner Ph.D. The Ohio State University, 1992 M . A . University of Washington, 1983 A.B . Smith College, 1981 A THESIS SUBMITTED IN PARTIAL F U L F I L L M E N T OF THE REQUIREMENTS FOR THE DEGREE OF Doctor of Philosophy in THE FACULTY OF GRADUATE STUDIES (Department of Computer Science) We accept this thesis as conforming to the required standard The University of British Columbia April 2002 © Ellen Gethner, 2002 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of 6^fy7c£ 5cTcA)c E The University of British Columbia Vancouver, Canada Date A PEr i 1001 DE-6 (2/88) Abstract At the heart of the ideas of the work of Dutch graphic artist M.C. Escher is the idea of automation. We consider one such problem that was inspired by some of his earlier and lesser known work [MWS96, Sc90, Sc97, Er76, Es86]. From a finite set of (possibly overlapping) connected regions within a unit square (Figure 1), is it possible to make a prototile with concatenated and colored copies of the original square tile (Figure 2), such that the pattern in the plane arising from tiling with the prototile • uniformly colors connected components, and • distinctly colors overlapping components (Figure 3)? The answer is yes, that such a prototile exists for any (suitably defined) de-sign confined to a unit square. We present a proof of existence and an efficient (and implementable) algorithm to construct prototiles. Moreover, in the existence proof, it will become apparent that a prototile for a given design may not be unique (up to concatenation). In such a situation, there are infinitely many "measurably dif-ferent" prototiles. The secret of each design is encoded by either one or infinitely many (number theoretic) lattices; we will show how to extract all possible lattices by using techniques from graph theory and graph algorithms. Finally, from a certain point of view, the prototiles that we construct are canonical. We begin an analysis of the canonical prototiles by making a connection from lattices to binary quadratic forms to class number. ii \ /X Figure 1: A design for which there is a ... Figure 2 : ...colored prototile... Figure 3: ...that wallpapers the plane with suitably matching colors. i i i Contents Abstract ii Contents iv List of Figures vi Acknowledgements x Dedication xii 1 Preliminary Remarks 1 1.1 Decidability 1 1.2 Graphics and Aesthetics 3 2 Motivation and History 5 2.1 Statement of Problem 8 2.2 Weighty Definitions 9 2.3 An Escher tile and Two Big Tiles 16 2.4 Prior Work on Escher tiles 17 3 Escher tiles: Toolbox 22 3.1 Graph Theory 22 iv 3.2 What the Graphs Have to Offer 28 3.3 Number Theory 35 4 Detailed Example 49 4.1 Get a Collision-Free Vector 54 4.2 Big Tile Dimensions 61 4.3 Assigning The Colors 61 5 Mirabile Dictu: Existence Proof 65 5.1 A Few More Tools 65 5.2 Coloring the Cosets 74 6 Efficient Big Tile Construction: The ColorFast Algorithm 84 7 Toward a Classification 90 7.1 Irreducible and Reducible Big Tiles 90 7.2 Irreducible Big Tiles as Tools 95 7.2.1 In Search of the Chromatic Number of T 95 7.2.2 In Search of Inequivalent A-Colored Big Tiles 98 8 Future Work 103 8.1 Generalizations 103 8.2 Machinery Applied to Graph-Coloring and VLSI Design 104 Bibliography 106 Appendix A Art Gallery 110 Index 115 v List of Figures 1 A design for which there is a i i i 2 ...colored prototile i i i 3 ...that wallpapers the plane with suitably matching colors i i i 2.1 Grid of subsquares to be used as a template for a 2x 2 Escher tile 6 2.2 A motif M designed by M. C. Escher 6 2.3 2x2 Escher tile that uses all four aspects of the motif in Figure 2.2 7 2.4 Fragment of doubly periodic wallpaper pattern produced by the Escher tile in Figure 2.3 8 2.5 One motif piece among many inside an Escher tile: Definitions 2.2.1 and 2.2.2 10 2.6 Fragment of the Escher wallpaper pattern generated by the Es-cher tile in Figure 2.5 11 2.7 The black motif piece is contiguous with five other motif pieces: Definition 2.2.5 12 2.8 Contiguous, related, and intersecting motif pieces: Definition 2.2.5 and Definition 2.2.6 . . . 13 2.9 Distinct and overlapping wallpaper components: Definition 2.2.8 15 2.10 Another Escher tile produced by the motif in Figure 2.2 17 vi 2.11 Fragment of singly periodic wallpaper pattern produced by the Escher tile in Figure 2.10 18 2.12 A three-colored 1x3 Big Tile for the Escher tile in Figure 2.10 . 19 2.13 A four-colored 4x4 Big Tile for the Escher tile in Figure 2.10 . . 20 2.14 x = y 20 3.1 An Escher tile in home position surrounded by eight other Es-cher tiles. Motif piece (m 4,0,0) is contiguous with (m 3,1,0) and (m3,0,0) is contiguous with (m 4 , -1 ,0) . Therefore, the pe-riod graph (see Figure 3.2) contains directed edge (m 4 , m3) with vector label [1,0] and directed edge (m 3 , m 4) with vector label [—1,0] (as well as many other edges) 42 3.2 The period graph for the Escher tile in Figure 3.1 43 3.3 The overlap graph for the Escher tile in Figure 3.1 . . . . . . . . 43 3.4 A fat spanning tree of the period graph in Figure 3.2 44 3.5 Unravelling the Escher tile puzzle with a set of generating motif pieces. A ghost of (m 3 , —2,1) is (m 3 ,0, 2) 45 3.6 Trivially periodic Escher tile 46 3.7 Singly periodic Escher tile 46 3.8 Component that is doubly periodic 47 3.9 Singly periodic Escher tile with natural period [1, -3] 47 3.10 Natural period [1,-3]; collision-free vector [1,0]; forbidden vec-tor [0,-1] 48 4.1 An Escher tile: Big Tile to be determined 51 4.2 Period graph, G T , for T in Figure 4.1 52 4.3 A fat spanning tree, ST, for GT 53 vn I fr" 4.4 The fat spanning tree, £ T with vertices embedded in correct locations relative to (mi, 0,0) 54 4.5 Set of generating motif pieces gen(T, 0,0) 55 4.6 A potential ghost of m 4 56 4.7 A potential ghost of m 9 57 4.8 The ghost of m 3 58 4.9 The ghost of m2 59 4.10 The overlap graph 60 4.11 An eight-colored 8 x 8 Big Tile for the Escher tile in Figure 4.1. This corresponds to the lattice generated by {[2, -2] , [3,1]}. . . . 63 4.12 A different eight-colored Big Tile for the Escher tile in Figure 4.1. This corresponds to the lattice generated by {[2, —2], [—4,0]}. 64 5.1 Motif pieces that intersect elements of gen(T, 0,0) for the Es-cher tile in Figure 3.9 80 5.2 Overlap graph for the Escher tile in Figure 3.9 81 5.3 Palette associated with [3,0] and [0,2] 81 5.4 A singly periodic Escher tile with natural period [2,1] 82 5.5 A palette 82 5.6 Set of colored motif pieces that serve as generators for a colored tile: the palette and coloring function C A are extracted from vectors [2,1] and [6,0] 82 5.7 A 6-colored Big Tile for the Escher tile in Figure 5.4 83 7.1 An Escher tile 91 7.2 A reducible Big Tile for the Escher tile in Figure 7.1 91 viii A. 1 Minimal area need not correspond to minimal coloring I l l A.2 A deceptive Escher tile I l l A.3 The deceptive tile unravelled 112 A.4 A hidden message 112 A.5 Escher tile whose period graph is disconnected 113 A.6 Fragment of wallpaper pattern for the Escher tile in Figure A.5 113 A.7 Another of Escher's designs 114 ix Acknowledgements M.C. Escher is a controversial figure in the Art World because of the innovative and mathematical methods that he employed. In the literature, one need not look far to find Escher ruminating about his peculiar position amongst the different cul-tures of science, mathematics and art; he never seems to have resolved to his own satisfaction where, in fact, he belonged. Vive la difference! I am a Mathematician and now nearly have the good fortune to be called a Computer Scientist. Though many aspects of the two cultures are at odds, there are some wonderful exceptions; the group of Theoretical Computer Scientists is one such. It is an honor to count myself a member of that group. It seems fitting, therefore, that the problem addressed by this thesis was inspired by some of the earlier attempts of M.C. Escher to automate combinatorial patterns. This work was not done in isolation: I am grateful to my fellow Theoreti-cians at the University of British Columbia for their collegiality and collaboration. In particular, I would like to thank Francois Anton, Alex Brodsky, Allen Clement, Stephane Durocher, and Mark McCann for many good conversations, both schol-arly and otherwise. I thank my committee members Anne Condon, Will Evans, and Joel Friedman for their ideas and input, and for their support for this work. I am grateful to M.C. Escher, Rick Mabry, Doris Schattschneider, and Stan Wagon for their colorful combinatorial investigations that led to my current work. I thank the latter three for the use of their Mathematica package Escher.m, which was an invaluable investigative tool, and is also responsible for some of the graphics in this thesis. Special thanks to Doris Schattschneider for reading this manuscript and for her many insightful comments and suggestions. And I thank my family for their support for and acceptance of my nonstandard career choices. x Finally, I offer my deepest respect and appreciation to my supervisors, David Kirkpatrick and Nick Pippenger. I have greatly enjoyed and benefited from their breadth and depth of knowledge in concert with their humor and good cheer. The opportunity to work with them has been a rare and special privilege. E L L E N G E T H N E R The University of British Columbia April 2002 xi To Maurits Cornells Escher xii Chapter 1 Preliminary Remarks We begin by giving some examples of problems that have been studied in computer science and that are related either directly or indirectly to the problem that is the focus of this thesis. The areas that we will consider are decidability of certain kinds of tiling problems, and computer graphics and aesthetics. 1.1 Decidability A problem, phrased as language membership, is said to be decidable [Pa94, C086] if regardless of the input, there is procedure (algorithm) that outputs the correct answer of "yes" or "no" in a finite number of steps. Some examples are • Travelling Salesperson Given a finite set of cities C = {ci,..., Ck}, a dis-tance function d : C x C —> Z (the integers), and a bound B, is there a tour that visits each city exactly once, ends where it began, and does so with an accumulated distance of at most Bl • FSA Do two particular finite state automata recognize the same language? 1 • Tiling or Domino Problem Given infinitely many copies of a finite set of unit square tiles with colored edges, can the plane be tiled by translation in such a way that the sides abut and colors match? The bulk of this thesis considers a variation on the tiling problem whose origin lies in sketchbooks of M.C. Escher [Sc90, Er76]; it will be described in Chapter 2. We mention some results that are related to the Domino problem. A con-jecture of H . Wang [Wa74], that any set of tiles that tile the plane must admit a periodic tiling of the plane, was proved false by R. Berger [Be66] who produced a set of 20426 tiles that admit no periodic tiling; Berger later produced another such aperiodic set of tiles with cardinality 104. R. Robinson [Ro71] constructed an aperi-odic set of tiles with only six elements. The Penrose tiles [Pe78, GS87] are a pair of quadrilateral tiles together with matching conditions that admit no periodic tiling of the plane. To date, it is not known if there exists a single tile (a connected region of R2) that only tiles the plane aperiodically. Problems of the tiling ilk have captured the attention of scholars in many areas, included among them mathematicians (ge-ometry and number theory), computer scientists (decision problems, verification, graphics), artists (Alhambran designs), physicists and chemists (crystallography), and philosophers to name a few. See for example, [Ma76], [Ho79], [Es86], [Sc90], [Pe78],[Er76], [KSOOa], [KSOOb], and [MR01]. Outputting a "yes" or "no" answer upon any input to the original square tile problem is known to be equivalent to the halting problem, and so is undecidable [Pa94]. As such, not surprisingly, variations on the problem have surfaced. For example, Szegedy [Sz98] expands on the notion of tile T and allows as acceptable input a finite union of elements from Z x Z (lattice points in the plane), which is called a finite cluster. A tiling is then a covering of Z x Z with nonoverlapping 2 translates of T. For an arbitrary such T no algorithm is known to determine whether or not T tiles Z x Z , and Szegedy studies two special instances of the problem: \T\ = p, where p is a prime number, and |T|=4. In both cases he gives an efficient algorithm that decides whether or not an arbitrary T with the appropriate cardinality tiles Z x Z . He also generalizes the problem away from Z x Z to an abstract problem for arbitrary finitely generated abelian groups. 1.2 Graphics and Aesthetics Many of the ideas behind the work of M.C. Escher lend themselves to computer automation. Two notable examples are • C. Kaplan and D. Salesin's Escherization [KSOOa], • 1. D. Schattschneider's Escher's Combinatorial Patterns, [Sc97, Sc90] and 2. R. Mabry, S. Wagon, and D. Schattschneider's Automating Escher's Combinatorial Patterns [MWS96]. The former paper presents an algorithm that, upon given any motif (in their case, a decorated subset of K 2 , referred to as a "closed Figure"), outputs a new motif that is "close" to the original and that tiles the plane (for examples, see [KSOOb]). The technique used is simulated annealing, and their algorithm performs well on many convex or nearly convex motifs, and hence on many of Escher's original de-signs. The authors maintain that "Unlike most research projects in computer graph-ics, this one is motivated more by intellectual curiosity than by practical import." 3 The latter papers inspired the problem that is addressed in this thesis. Like the tiling problems mentioned in Section 1.1, the input will be information con-tained in a closed unit square, but with more complicated matching conditions than those imposed on the boundaries. The conditions arise from a problem of aesthetics and visualization, and in particular on some of the sketches found in Escher's note-books [Sc90]. The problem is difficult to state in brief terms, but can be illustrated visually. We will do so in Chapter 2. At the outset, the problem may be viewed as a decidability problem (the question of the existence of a particular geometric object) that will eventually be answered in the affirmative. An affirmative answer to the question and an array of interesting examples provoke questions of classifica-tion. Moreover, underlying the work is that we seek an efficient (polynomial-time) algorithm that constructs what we will define as a Big Tile. 4 Chapter 2 Motivation and History A problem inspired by M.C. Escher that has recently initiated a variety of papers [Da97, Ge02, MWS96, Sc97, Wa99] is described as follows [Es86, Sc90]. Produce a potato and a sharp knife. Cut the potato in half and square off the flat face of one of the halves. Carve an interesting design into the square face. Call this design a motif. Also consider the designs created by the cyclic group of rotations acting on the square-with-carved-design. Each such new design is called an aspect of the original motif. Ultimately, use the four aspects of the motif as ink stamps. Escher's idea, which he hoped to sell to a tiling company, was to make a square tile to be used for filling the plane with a periodic pattern. For example, in the grid shown in Figure 2.1 stamp each subsquare with any of the four aspects of the motif (one of Escher's own) in Figure 2.2. There are four subsquares and thus 44 = 256 tiles that can be produced. Take a particular tile T and create a pattern in the Euclidean plane by taking the image of T under Z x Z. The result is a doubly periodic wallpaper pattern. See Figures 2.3 and 2.4. Let Ti and T 2 be two tiles and W\, W2 be their respective doubly periodic wallpaper patterns. Tiles Ti and T 2 are inequivalent if for every isometry a we have o{Wx) ^WL. 5 1 2 Figure 2.1: Grid of subsquares to be used as a template for a 2x2 Escher tile Each tile yields a periodic wallpaper pattern, but some different-looking tiles yield wallpaper patterns that are equivalent up to isometry. Escher, who wanted to sell his idea to a tile company, wondered about the following question [Sc90, Sc97]: up to isometry, how many inequivalent 2x2 tiles in up to four aspects are there? The unexpected answer, which Escher calculated by brute force, is 23. Schattschneider in [Sc97] verified Escher's calculation by way of Burnside's Lemma. Gethner gen-eralized Escher's result by giving an exact formula for the number of inequivalent m x m tiles in up to four aspects [Ge02] for any m G Z + . Figure 2.2: A motif M designed by M . C. Escher 6 Figure 2.3: 2x2 Escher tile that uses all four aspects of the motif in Figure 2.2 In particular Theorem 2.0.1 (Gethner): Let N4(m) denote the number of inequivalent m x m Escher tiles with motifs in up to four aspects. Then k\m fclm + a ( m ) ( m 2 4 m 2 / 4 + 3m24m^2-1)}, (2.1) where a(m) 1 ifm is even 0 ifm is odd, rk is the number of (not necessarily distinct) prime divisors ofk, and $ is the Euler <p function. Escher also made use of the unused half of the potato: he carved a reflection of the original motif, thereby increasing the total number of aspects to eight. The number of inequivalent 2 x 2 tiles in up to eight aspects turned out to be 154, which was verified computationally by Davis [Da97]. 7 Figure 2.4: Fragment of doubly periodic wallpaper pattern produced by the Escher tile in Figure 2.3 Escher, Mabry, Schattschneider, and Wagon [MWS96, Sc90] were inspired to think about coloring and subsequently automating the coloring. The purpose of Section 2.1 is to make precise the set-up for the coloring question to which they alluded. The purpose of the remaining chapters is to lay the foundation for an af-firmative answer to a question of existence, present an efficient and implementable algorithm that produces a Big Tile, to allude to aspects of classification, and to suggest possibilities for future research. 2.1 Statement of Problem Escher's problem appears to start in the realm of geometry and in modern terms, in visualization. To give a precise statement of the problem, we need many definitions. 8 2.2 Weighty Definitions L e t S y be the subset of R 2 given by {(x,y) : i — \ <x<i+\,j-\ < y < j + That is, Sij is a closed square region with area one and center (i, j) and i, j e Z . In the previous section, Escher used a motif that was composed of many individual motif pieces. Definition 2.2.1 (Motif Piece): A motif piece (m, i, j) is a connected subset ofSij such that dSij f] m is a finite union of closed intervals, where dSitj is the boundary ofSitj. In the long run, the problem we are after begins with some design composed of motif pieces inside a unit square. For the coloring problem that we will address, it does not matter what method the artist used to construct the design. The previous section simply describes one method (among infinitely many) that an artist could use. Definition 2.2.2 (Escher tile): An Escher tile T is given by T = {(mi, 0,0), (m2, 0, 0 ) , . . . , (rrik, 0, 0)}, where T is a finite nonempty set of motif pieces satisfy-ing 1. (rrii, 0, 0) n( m j ' ° ' 0) D dSo.o = 0 whenever i ^ j (no pair of motif piece intersect on the boundary), 2. (rrii, 0, 0) % <9So,o (no motif piece is contained in the boundary), and 3. (rrii, 0, 0) % \JiseA (mjs, 0, 0)for A C { 1 , . . . , k) (no motif piece is contained in the union of other motif pieces). See Figure 2.5 for an illustration of one motif piece among many that define an Escher tile. 9 Remarks: • An Escher tile is an artistic design contained in a closed unit square. • Given an Escher tile T = {(mi, 0,0), (m 2 ,0 ,0 ) , . . . , (mk, 0,0)} the motif pieces are distinct elements of a set, though as subsets of R 2 , it may be the case that (m,, 0, 0) f](mj, 0, 0) ^ 0 for some i ^ j. • In the ensuing discussions for which the location of an abstract motif piece (mt, i, j) is not relevant, we denote (mt, i, j) by a capital letter such as M or N or perhaps Mt or A^. Figure 2.5: One motif piece among many inside an Escher tile: Definitions 2.2.1 and 2.2.2 Definition 2.2.3 (Wallpaper Pattern): Given an Escher tile T, the Escher wall-paper pattern generated by T is the periodic plane pattern arising from taking the elementwise image ofT under the map Z x Z, and is denoted by Wall(T). Notation: We will generate the map Z x Z by a and /3, where for any point (x, y) € R2, a((x, y)) := (x + 1, y) and (3((x, y)) := (x, y + 1). In general for integers r and s, ar(3s((x, y)) — (x + r, y + s). For our purposes, given an arbitrary motif piece (mt,i,j) we write ar/3s((mt, i,j)) = (mt,i+ r,j + s). See Figure 2.6 for a fragment of the wallpaper pattern generated by the Escher tile in Figure 2.5. 10 Figure 2.6: Fragment of the Escher wallpaper pattern generated by the Escher tile in Figure 2.5 With an Escher tile T = { ( m i , 0,0), ( m 2 , 0 , 0 ) , . . . , (mk, 0,0)}, the wallpa-per pattern given by Wall(T) is the set { a r / 3 s ( ( m i , 0,0)) : r, s G Z } | J {ar/3s((m2, 0, r, s G Z } | J . . . (J {arPs{(mk, 0, 0)) : r, s G Z } . That is, WaH(T) is simply the (necessarily infinite) set of all possible East-West and North-South integer translates of the elements of T. Definition 2.2.4 (Location of a Motif Piece): A motif piece (mt, r, s) has location (r, s), the center of the unit square in which mt resides. In Definition 2.2.2, the definition of Escher tile, we choose the motif pieces to have location (0, 0) for no other reason than convenience; any fixed location would serve the same purpose. 11 Definition 2.2.5 (Contiguous motif pieces): A motif piece is contiguous with it-self. Two motif pieces M and N in different locations are contiguous ifMf]N ^ 0. Figure 2.7: The black motif piece is contiguous with five other motif pieces: Definition 2.2.5 That is, a motif piece is contiguous with itself and two motif pieces in dis-tinct locations are contiguous if and only if they intersect on the boundaries of translates of 50,0; the intersection of distinct contiguous motif pieces is necessarily a finite union of vertical and horizontal line segments, some of which may be points [St81]. Figure 2.7 shows several contiguous motif pieces. Definition 2.2.6 (Related motif pieces): Two (not necessarily distinct) motif pieces M and N are said to be related if there exists a finite sequence of motif pieces {Ni, N2,..., Nt} such that M = N\, N — Nt and Ni is contiguous with A^+i for i = l,...,t-l. 12 Figure 2.8: Contiguous, related, and intersecting motif pieces: Definition 2.2.5 and Definition 2.2.6 See Figure 2.8 for an example of contiguous, related, and intersecting motif pieces. The subset of E 2 given by \ J l i = 1 Ni is necessarily connected, whereas two or more motif pieces in the same location that intersect are not necessarily related. Contiguous motif pieces are related, but related motif pieces are not necessarily contiguous. Definition 2.2.7 (Wallpaper component): Given a motif piece M , the wallpaper component generated by M , denoted W ( M ) , is the set { N : N is a motif piece related to M } . Clearly "related" is an equivalence relation on the set of all motif pieces in Wall(T) arising from a given Escher tile T. Consequently, an Escher wallpaper 13 component is an equivalence class of motif pieces whose elementwise union is a connected subset of R 2 . Thus, the set of Escher wallpaper components partitions Wall(T) into (possibly infinitely many) disjoint sets, each of whose elementwise union is a connected subset of R2. It is important to continue to emphasize the distinction between set intersec-tion and the intersection of motif pieces (subsets of R 2), particularly in light of the next definition. Definition 2.2.8 (Overlapping components): Two distinct wallpaper components W(M) and W(N) are said to overlap if there exists (ms,i,j) G W(M) and {mt,i,j) 6 W(N) such that (ms,i, j) f]{mt,i, j) ^ 0. See Figure 2.9 for an example of a pair of distinct overlapping wallpaper components. The original Escher tile can be seen in any subsquare. The following lemma is a direct consequence of Definition 2.2.8 and the Z x Z periodicity of Wall(T). Lemma 2.2.9 (Overlaps of W((mi,0,0))): Let T — { ( m i , 0,0), . . . , (mk, 0,0)} be an Escher tile. Distinct wallpaper components W ( ( m i , a, b)) andW((mi, u, v)) overlap if and only ifW((mi, 0,0)) and W((mi, a — u,b — v)) overlap. At last we have the means to give the definition of Big Tile, the idea of which leads to nontrivial questions of existence and classification. In a word, a Big Tile for an Escher tile T will be an m x n rectangular region consisting of ran concatenated copies of T with lower left subsquare centered at (0,0) and sides parallel to the standard axes; each motif piece in the Big Tile will be assigned a color from a set of cardinality A . Finally, the image of the Big Tile under mZ x nL produces the original pattern Wall(T) colored in such a way that wallpaper components are 14 Figure 2.9: Distinct and overlapping wallpaper components: Definition 2.2.8 uniformly colored and distinct overlapping wallpaper components are colored with different colors. We give the formal definition next. Definition 2.2.10 (Big Tile): Given an Escher tile T — {(mi, 0,0),..., (m*, 0,0)} a A-colored mxn Big Tile for T denoted BT{A, m, n), is laden with the following requirements. Let M,N € Wall(T) be arbitrary. • There exists a function, CA, that assigns some color from among A colors to each motif piece contained inside the mxn region that contains the Big Tile. That is C A : {mi, . . . ,mfc} x mZ x nZ —y COLORS is onto and \COLORS\ = A. We write (m s, to signify the colored motif piece ms in location • BT(A, m, n) = \J(i,j)ezmxZn LUi *> J * ) A , and after "tiling" the plane with the image of BT(A, m, n) under mZ x nZ, w Ziave 15 1. forevery(ms,il,j1)and(mt,i2,j2) e W(M)wehaveCA((ms,il,jl)) = CA((mt, i2,j2)) (alternatively we write CA{W{M)) — CA{W(N)), 2. if W(M) and W(N) overlap and are distinct, then CA(W(M)) ^ CA(W(N)), and 3. there does not exist a A-colored Big Tile, B'T such that B? is composed of concatenated copies of B'T (with sides abutting). The Main Questions: 1. Given an arbitrary Escher tile T, does a Big Tile BT for T exist? 2. If BT exists for a particular Escher tile, must it be unique? 3. If BT exists and is not unique, what can be said about the set of Big Tiles for T? How do the number of colors and size of a Big Tile depend on the size of the input (number of motif pieces and boundary intersections)? 4. If the answer to Question 1 is "yes" then is there an efficient algorithm to construct i ? r ? 5. What can be said about the classification of the set of Big Tiles for an arbitrary Escher tile T? A picture is worth 10,000 words. In the next section we give an example. 2.3 An Escher tile and Two Big Tiles The Escher tile given in Figure 2.10 was designed by M.C. Escher and produced by a Mathematica package implemented by Mabry and Wagon in [MWS96, Wa99]. Recall that there are 154 inequivalent Escher tiles that arise from taking rotations 16 and reflections of Escher's original motif (see Chapter 2) and arranging them in a 2x2 grid. By way of the same package it is shown by trial and error that a Big Tile exists for each of these 154 Escher tiles. Specifically, upon input of an Escher tile T together with a correct guess of the Big Tile dimensions, a graphical representation of a Big Tile is given as output. However, if an incorrect guess is made (say m x n), then an m x n tile CT will be returned: the image of CT under mZ x nZ yields a wallpaper pattern whose wallpaper components are uniformly colored but for which there exists at least one pair of overlapping components that are colored the same. See Figure 2.12 for an example of a 3-colored 1 x 3 Big Tile for the Escher tile in Figure 2.10. Figure 2.10: Another Escher tile produced by the motif in Figure 2.2 The Big Tile for the Escher tile of Figure 2.10 is not unique. A 4x4 Big Tile is shown in Figure 2.13 that requires four colors. In fact, as will become evident in Section 5.1, there are infinitely many es-sentially different Big Tiles for the Escher tile in Figure 2.10. 2.4 Prior Work on Escher tiles Aside from Escher's original sketches, only the paper by Mabry, Wagon, and Schattschnei-der [MWS96] has addressed the question of the decidability of the Big Tile prob-lem, though they present the problem in terms of programming and visualization. 17 Figure 2.11: Fragment of singly periodic wallpaper pattern produced by the Escher tile in Figure 2.10 They use a brute-force approach to show that Big Tiles exist for each of 154 Escher tiles that arise from the motif and the reflection of the motif in Figure 2.2. Their program works as follows: 1. Upon input of a given Escher tile T, make a guess as to the dimensions of a potential Big Tile for T. Suppose the guess ism x n. 2. One copy of T is placed in each of the m x n subsquares, and every intersec-tion of a motif piece with the boundary of its unit square in each of the m x n subsquares is labelled with a variable. 3. If two or more boundary intersections in a given subsquare belong to the same motif piece, then the same variable is assigned to each such boundary intersection. 18 Figure 2.12: A three-colored 1x3 Big Tile for the Escher tile in Figure 2.10 4. Two adjacent copies of T may have nontrivial intersection along a boundary. Suppose copy A has a boundary intersection labelled x and adjacent copy B has a boundary intersection labelled y, and further suppose that the boundary intersections corresponding to x and y intersect. Assign x = y and do so for all such contiguous motif pieces (see Figure 2.14). This subroutine ensures that motif pieces inside the m x n region that belong to a connected subset of R 2 will be assigned the same color, and gives rise to a set of many equations and many unknowns (though the system is sparse) to be solved by techniques from linear algebra. 5. Construct a graph which contains a vertex for each wallpaper component, and two vertices are adjacent if and only if the corresponding connected regions inside the mxn region overlap. 6. Vertex-color this graph and if possible assign different colors to overlapping 1 9 Figure 2.13: A four-colored 4x4 Big Tile for the Escher tile in Figure 2.10 wallpaper components. 7. If an incorrect Big Tile size is input, then the program returns as visual output a rectangular tile whose internal connected components are uniformly colored and whose opposing boundaries have correctly matching colors. T i l e A T i l e B Figure 2.14: x = y The authors construct a database of Big Tile sizes, one for each of the 154 Escher tiles constructed by way of Escher's original motif. They did so by brute force: they looked at large fragments of wallpaper and made guesses for Big Tile sizes. Most, though not all, of the Big Tile sizes yield minimally colored Big Tiles. 20 In the next chapter we discuss a method to prove the existence of a Big Tile for an arbitrary Escher tile. 21 Chapter 3 Escher tiles: Toolbox 3.1 Graph Theory Two basic tools are required for the Big Tile existence theorem: the period graph of T and the overlap graph of T. The period graph of T is a directed labelled multigraph whose vertices are in one-to-one correspondence with the motif pieces of T, and whose directed la-belled edges identify contiguous motif pieces. That is, an Escher tile in the (0,0) position is surrounded by eight other Escher tiles whose centers are (i, j) with i, j G {—1,0,1} and can be thought of as being north, south, east, west, northwest, northeast, southwest, or southeast of the tile in the "home" position. In the period graph, two vertices ms and mt are adjacent if and only if (ms, 0,0) D (mt, i, j) = 0 for some i,j £ {—1,0,1} (with at least one of i or j not equal to 0); the directed edge (ms,mt) is labelled with the vector See Figure 3.1 for an Escher tile together with it's eight surrounding Escher tiles. Figure 3.2 shows the period graph for the Escher tile in Figure 3.1. The vertices of the overlap graph are equivalence classes of vertices of the period graph: two distinct period graph vertices will be equivalent exactly when the 22 two corresponding motif pieces are related; the vertices of the overlap graph will be called jE-vertices. Two equivalent vertices necessarily belong to the same Escher wallpaper component, and hence it is worthwhile early on to identify such occur-rences. Two distinct £?-vertices V\ and V2 will be adjacent in the overlap graph of T if and only if there is non-trivial intersection in E 2 among motif pieces associated with Vi and motif pieces associated with V2. That is, adjacent .E-vertices in the overlap graph belong to distinct overlapping Escher wallpaper components must receive different colors in any Big Tile for T. Precisely, Definition 3.1.1 (Period Graph of an Escher tile). LetT = {(mu 0,0), (m2,0,0), ..., (rrik ,0,0)} be an Escher tile. The period graph of T, denoted GT, is a labelled directed graph constructed by the following rules. 1. (Vertices) V(GT), the vertices ofGr, are in one-to-one correspondence with the motif pieces ofT. Define to be the vertex that corresponds to (rrii, 0, 0) fori = l,...,k. 2. (Edges) E(GT), the edges ofGr, are directed and given by (vs, vt) G E(GT) labelled with if and only if • (i,j) ± (0,0), and • (ms,0,0)r)(mt,i,j) ^ 0 . We write £(vs, vt) = to denote the vector label of directed edge (vs,vt). On those occasions for which we must identify each coordinate of a vector label sepa-rately, we define £i(vs, vt) — i and£2(vs, vt) = j. 23 In essence, the period graph is a road map that tells one how to walk along a wallpaper component without fear of derailment. The following proposition follows directly from Definition 3.1.1. Proposition 3.1.2 (Vector Labels and Edges are Bidirectional Pairs): Let T be an Escher tile with period graph GT- Then (vs,vt) G E(GT) ifandonlyif(vt,vs) G E(GT)- Moreover, £(ys,vt) = —£(vt,vs). Most of the time, we restrict our attention to an Escher tile whose period graph is connected, although in general a period graph need not be connected. Each connected component of a period graph corresponds to an Escher tile whose motif pieces are a subset of T; we make this idea precise in the next definition. Definition 3.1.3 (Escher tile Induced by a Subgraph of the Period Graph): Let T be an Escher tile with period graph GT and suppose GT has N connected com-ponents given by G\,... ,GN- Let i G {1, . . . , N} and suppose V(Gi) = {v^, vi2„ • • • > vi3} far some s < q. Then the Escher tile induced by Gi is the set of motif pieces {(m^ ,0,0) (mi2,0,0),..., (mis ,0,0)}. Absent from the period graph is information about when and if distinct wall-paper components overlap. That is the purpose of the next two definitions. Definition 3.1.4 (E-vertex): Given the period graph GT far an Escher tile T, Vi and Vj in V(GT) are said to be equivalent if and only if (m^ , 0,0) and (rrij, 0,0) are related. The equivalence class ofvi G V(GT) under the relation related is said to be an E-vertex, and is denoted \VJ\. Note that an E-vertex represents a collection of motif pieces in a single Escher tile that belong to the same component in the wallpaper pattern. We have the machinery to define the overlap graph of T. 24 Definition 3.1.5 (Overlap Graph of an Escher tile): Let T be an Escher tile with period graph GT- The overlap graph of T, denoted Or, is a simple, undirected, unlabelled graph constructed by the following rules. 1. (Vertices) The vertex set of Or, denoted V(OT), is exactly the set of E-vertices ofV(GT)-2. (Edges) Suppose [vi], [VJ] G V(OT) with [vi] f][vj] = 0. In other words, [vi] and [VJ] are distinct. Define [vi] to be adjacent to [VJ] in OT if and only if 3vw G [vi] and vz G [VJ] such that (mw, 0, 0) f](mz, 0, 0) ^ 0. In particular, a pair of adjacent E-vertices corresponds to a pair of unrelated motif pieces contained in the unit square S0,o, and therefore are elements of dis-tinct overlapping wallpaper components. This information is crucial to have since eventually we must color such a pair of wallpaper components with distinct colors. Figure 3.3 shows the overlap graph for the Escher tile in Figure 3.1. Often it will be helpful to use the undirected unlabelled graph that underlies the period graph. Definition 3.1.6 (Agglomerated Period Graph): Let GT be the period graph for Escher tile T. The agglomerated period graph of GT is the undirected graph obtained from GT by dropping the order from the edges in E(GT), removing the vector labels and multiple edges. The agglomerated period graph is denoted by GT-Though the agglomerated period graph has no multiple edges, it may have loops. An analysis of all nontrivial simple cycles (including loops) in the agglomerated period graph will extract inherent periodicities of the wallpaper pattern. 25 Definition 3.1.7 (Agglomerated Spanning Tree): Let T be an Escher tile with period graph GT and agglomerated period graph GT- An agglomerated spanning tree of GT is a spanning tree O/GT, and is denoted by ST-Once we have an agglomerated spanning tree, useful information can be gained by reinstating the information about the edges of ST that was suppressed when GT was agglomerated. Definition 3.1.8 (Fat Spanning Tree): Let T be an Escher tile with agglomerated spanning tree ST- A fat spanning tree of ST, denoted ST, is the agglomerated spanning tree with the multiplicities, directions, and vector labels inherited from the corresponding edges of the period graph GT-See Figure 3.4 for the fat spanning tree for the period graph in Figure 3.2. It will be useful to keep track of the edges that were removed from both the period graph and agglomerated period graph when the agglomerated spanning tree and fat spanning tree were constructed. Definition 3.1.9 (Agglomerated Removed Edges): Let T be an Escher tile with agglomerated period graph GT and agglomerated spanning tree ST- The removed edges of GT is the set E(GT) \ E(ST), and is denoted RT-That is, RT is the set of edges that were removed from the agglomerated period graph when the agglomerated spanning tree was constructed. Finally, we reinstate the directions, multiplicities and vector labels to ele-ments of RT in the next definition. Definition 3.1.10 (Fat Removed Edges): Let T be an Escher tile with agglom-erated removed edges RT- The fat removed edges of T, denoted RT, is E(GT) \ E(ST)- That is, RT is the set RT with the directions, multiplicities and vector labels reinstated. 26 It is an easy consequence of Definitions 3.1.9 and 3.1.10 that \RT\ = 2 | i? T | . Later on, for the purpose of coloring wallpaper components and in light of Lemma 2.2.9, it is important to identify • [r, s] G Z 2 for which W((rai, 0,0)) does not overlap W({rn\, r , s)), and • [r, 5] G Z 2 for which W((mu 0, 0)) = W((mu r, s)). The former vectors help to identify distinct wallpaper components that may legitimately be colored with the same color. On the other hand, the latter vectors are the periodicities inherent in the wallpaper pattern. We name these two kinds of vectors in the next definitions. Definition 3.1.11 (Collision-Free Vector for T) : Let T be an Escher tile whose period graph is connected. Any [r, s] G Z 2 for which W ( ( m i ,0,0)) does not overlap W ( ( m i , r , s ) ) is a collision-free vector for T, and the set of all such vectors is denoted A(T). At the other end of the spectrum, vectors that are "forbidden" (formally defined in Section 5.1) are essentially those vectors that are not collision-free. See Figure 3.10. Definition 3.1.12 (Inherent Periodicities in Wall(T)): Let T be an Escher tile whose period graph is connected. Any [r,s] € Z 2 for which W((mi, 0, 0)) = TV ( ( m i , r, s)) is an inherent period of Wall(T). The next chapter is devoted to extracting (inherent) periodicity properties and overlap information from the components of the graphs GT and OT- Some-times GT alone contains enough information to produce a Big Tile for T. On those occasions for which the graph OT must be relied upon, the Big Tile problem gains more depth. 27 3.2 What the Graphs Have to Offer Given an Escher tile T with period graph GT, we associate a trail (any sequence of adjacent vertices) in GT with a 2-dimensional vector value [r, s] G Z 2 by adding the vector labels of all edges in the trail. This idea will be made precise in Definition 3.2.1. A trail in GT encodes a walk on a fragment of a wallpaper component along (not necessarily distinct) contiguous motif pieces. Each step is either North, South, East, West, Northeast, Southeast, Southwest, or Northwest. Often we must keep track of the relative locations of motif pieces on such a walk. To do so, we define the vector value of a trail next. Definition 3.2.1 (Vector value of a trail in GT)'- Let T be an Escher tile with period graph GT and suppose Tr — {vai,..., vat} is a trail in GT- The vector value of Tr is given by Kvaj, vaj+l )• That is, the vector value of a trail Tr is the sum over all vector labels of the directed edges in Tr. Furthermore, a trail {t> a i,... ,vat} in GT together with one motif piece (mai, x, y) uniquely specifies a set of motif pieces, one for each vertex in Tr, that are related to (mai,x,y). So, an Escher wallpaper walker who starts a walk on motif piece in location (xi, yi) and walks along trail Tr whose vector value is [^ 2,2/2] will finish the walk in location (x2 — x i , y2 — yi)-Definition 3.2.2 (Set of Motif Pieces Induced by a Trail in GT): Let T be an Escher tile with period graph GT and suppose Tr = {vai, ..., vat} is a trail in GT-For any a,b G Z, we define the set of motif pieces induced by Tr and (mai, a, b) to be t / i i ^ Tr((mai,a,b)) := (m a i ,a ,&)u (J I m a , , a - ^ £ I { V J , vj+1), b - ^ £2{VJ, vj+1) i=2 V 3=1 3=1 J 28 In other words, suppose we are standing on (mai, a, b) and wish to walk along the sequence of contiguous (and hence related) motif pieces dictated by Tr = {vai, • • •, vat}. We necessarily walk from (mai,a, b) to a copy of ma2. The location of ma2 is (a — i\(vai, v a 2 ) , b — h(vai,va2))- That is, we walk to a new location along a pair of contiguous motif pieces dictated by the vector label of (vai,va2). In general, suppose ( m ^ , ! , ! / ) is the motif piece corresponding to v a i _ i - Then (mai,x - M v . ^ a J , ! / - (-2{vai_^vai))is the motif piece corresponding to va% in Tr. So, the coordinates of the location of mai corresponding to vai £ T r are obtained by keeping track of where we started (namely at (a, b)) and summing over all vector labels of consecutive edges in Tr up to and including the edge (u a i_!, vai). Definition 3.2.3 (Nontrivial and Trivial Circuits in GT): Let Circ be a circuit in the period graph of an Escher tile. Circ is said to be nontrivial if the vector value of Circ in GT is not [0,0]. A circuit whose vector value is [0, 0] is said to be trivial. It turns out that the non-trivial circuits in GT (or lack thereof) will play an important role in the construction of a Big Tile. We will often exploit the association between circuits and vectors by referring to "linearly independent circuits" when the context is clear. Moreover, exploiting any spanning tree of the agglomerated period graph will give rise to a set of motif pieces, all related, that generate Wall(T). Definition 3.2.4 (Generating Motif Pieces): Let T = { ( m b 0 ,0) , . . . , (mk, 0, 0)} be an Escher tile whose period graph GT is connected. Define a set of generating motif pieces of T, denoted gen(T, a, b), as follows. 1. Let ST be the fat spanning tree of agglomerated spanning tree ST-2. Let Px be the unique path in ST from v\ to vxfor x = 2 , . . . , k and [ix,jx] be the vector value ofPx in ST-29 Then a set of generating motif pieces for T is gen(T, a, b) := {(mi, a, b), '(m 2, a+ «2, b + j2), (mk, a + ik, b + jk)}. For s = 1,..., k, we say that (ms, a + is, b + js) G gen(T, a, b) is a generating motif piece for T. Most often we use gen(T, 0,0) = {(mu0,0), [m2,i2,32), (mk,ik,jk)}. A set of generating motif pieces for an Escher tile is, in effect, a set of translated elements of T whose union is a rearrangement of the original motif pieces that forms a con-nected subset of R 2 . In fact an Escher tile whose period graph is connected is like a set of jumbled puzzle pieces that are unscrambled by gluing together the set of generating motif pieces with instructions from the fat spanning tree. Figure 3.5 is an example of an Escher tile together with a set of generating motif pieces. An ex-ample of an Escher tile, its period graph, a fat spanning tree and a set of generating motif pieces are given in Figures 4.1, 4.2, 4.4, and 4.5. Definition 3.2.5 (Ghost Motif Piece and Ghost Vector): Let T = {(mi, 0,0), (m2, 0, 0), . . . , (mk, 0, 0)} be an Escher tile whose period graph GT is connected. Let ST be an agglomerated spanning tree ofGT- Suppose gen(T, 0, 0) = {(mi ,0,0), ..., (mk ,ik,jk)} is a set of generating motif pieces that arise by way of ST- A ghost motif piece of (m s , is,js) G gen(T, 0,0) is any motif piece (ms, a, b) such that • (a,b) ^ (is,js) and • (m s , a, b) is contiguous with some element ofgen(T, 0, 0). The vector [a — is,b — js] is a ghost vector for T. A ghost motif piece (or simply ghost) is necessarily contiguous with a gen-erating motif piece: the ghost vector that translates a ghost to it's generator will help identify inherent periods in the wallpaper pattern. For example in Figure 3.5, note that ghost vector [2,1] translates ghost (m 3 , —2,1) to generator (m 3 ,0, 2). 30 The next lemma and corollary are immediate and useful consequences of Definition 3.2.5. Lemma 3.2.6 (Finitely Many Ghost Vectors): Let T = {(mi, 0,0), (m 2 ,0,0), ..., (rrik, 0,0)} be an Escher tile whose period graph is connected. Then there are only finitely many ghost vectors for T. Proof: Any set of generating motif pieces is contained within a square of side length k. By Definition 3.2.5, a ghost motif piece is contained within a square of side length k + 2 (expand the original by one unit in all directions). | Corollary 3.2.7 (Ghost Vectors are Bounded in Length by 0(k)): Let T = {(mi, 0, 0), (m 2 , 0, 0), . . . , (rrik, 0, 0)} be an Escher tile whose period graph is connected. If [a, b] is any ghost vector for T then \a\, \b\ < k + 1. Finally, in the remainder of this section, we will show that the ghost vectors (inherent periodicities in their own right) are the building blocks for the inherent periodicities in the Escher wallpaper pattern Wall(T). Lemma 3.2.8 (Ghost Vectors as Building Blocks of Inherent Periodicities): Let T = {mi, 0, 0), . . . , (m*;, 0,0)} be an Escher tile whose period graph is connected and suppose a set of generating motif pieces for T is gen(T, 0, 0) = {(mi, 0, 0), ..., (m-k, iki jk)}- Then (ms, a, b) is related to (ms, c, d) if and only if there exists X\,..., %N G Z such that a b where {gi , . . . , grsr} is the set of ghost vectors for T. XiEi-\ r - X j v g N , 31 Moreover, • for any (ms, a, b)), (ms, c, d) G Wall(T), we have W((ms , a, b)) = W((ms, c, d)) if and only if equation (3.1) holds for some X i , ..., x^. Proof: Motif piece (ms, a, b) is related to (ms, c, d) if and only if (ms, a, b) and (ms, c, d) belong to the same wallpaper component. Let Walk = {N± = (ms, a, b), N2, ..., Nj = (ms, c, d)} be a sequence of contiguous motif pieces that describes a walk from (ms, a, b) to (ms, c, d). We know that Wall(T)= | J gen(T,x,y), where the union is disjoint, and thus Walk is represented by a (not necessarily distinct) sequence gen(T, x\,yi), gen(T, x2, y2), • • •, gen(T, XQ, yo). In particu-lar, Walk alternates between subwalks within a set of generating motif pieces and an exit from that set of generating motif pieces to the next gen(T, xa,ya). The exit necessarily takes place from a generator in gen(T, Xi, yi) to its ghost in gen(T, xi+i,yi+i). Say the vector value of the walk from this generator to its ghost is gi-We now determine the vector value of Walk. First, since (ms, a, b) G gen(T, %u yi) we have a = xi+is and b = yi+js. Similarly, c = xR + is andrf = yR+js. The subwalk in gen(T, xi,yi) starts on (ms, a, b) and must end on (mtl ,a — itl,b — jtl), where (m t l , x2 + itl, y2 +jh) G gen(T, x2,y2)isa ghost of (mtl ,a-it,b-jt). Let gi x be the associated ghost vector. Then the vector value of the walk from (ms, a, b) to {mtl, x2 + itl, y2 + jh) is xi + ih - a x i + ih - x i - i s hi ~ i's + g h = + g i i = Vi + hi - b Vi + Jti - 2/i - Js Jh ~ js 32 In general the walk from (ms, a, b) to (ms, c, d) has vector value given by + gi 3 + • • • - is ih ~ ih + Sh + Jtl ~~ Js jt2 -jti + itQ - V i + gitQ_x + is ~ itQ JtQ ~~' JtQ-l Js — JtQ — S i l "t~ Si2 + ' " ' + SiQ_i > as desired. For the second claim, W((ms, a,b)) = W((ms, c, d)) if and only if (ms, a, b) and (ms, c, d) are related if (and by the first part of this proof) if and only if equation (3.1) holds. This completes the proof. | Lemma 3.2.9 (Circuits in GT are Linear Combinations of Ghost Vectors): Let T be an Escher tile whose period graph GT is connected. Suppose Circ = {v^, ..., vis} is a circuit in GT whose vector value is [a, b] [0, 0]) and let (gi, . . . , g N} be the set of ghost periods for T. Then a b = Zlgl H rXNgw Proof: Choose any x,y G Z . Motif pieces (ms,x,y) and (ms,x + a,y + b) are contained in the set of motif pieces induced by Circ and (ms, x, y). Therefore (ms, x, y) and (ms, x + a, y + b) are related. By Lemma 3.2.8, a b Zlgl + H^ATgN, as desired. | We summarize the results from this section. 33 • By Definition 2.2.6, (ms, a, b) is related to (ms, c, d) if and only if there is a walk along contiguous motif pieces from (ms, a, b) to (ms, c, d). • By Definition 3.1.1, there is a walk along contiguous motif pieces from (ms, a, b) to (ms, c, d) if and only if there is a circuit in GT given by {vs,vi2, ..., Vs}- • • By Lemma 3.2.8, (ms, a, b) is related to (ms, c, d) if and only if = Z l g l + H X A r g N , c — a d-b where g i , . . . , g N are the ghost vectors of T, and xx, ..., G Z . We conclude that the vector value of any circuit in GT is an integer linear combination of ghost vectors for T. Moreover, by the second claim in Lemma 3.2.8, all integer linear combinations of the ghost vectors for T exactly characterize the set of vectors [A, B] such that W((mx,x, y)) = W((m1,x + A,y + B)). Thus, the subspace of Z 2 spanned by the ghost vectors GV := {#i, . . . , # A T } describe the inherent periodicities in Wall(T). In the next section we rely on this characterization of inherent periodicities to define, essentially, three kinds of Escher tiles (whose period graphs are connected): • the subspace spanned by GV is trivial, or • the subspace spanned by GV is one-dimensional, or • the subspace spanned by GV is two-dimensional. The machinery is in place: in the next section we outline how to use it. 34 3.3 Number Theory The period graph of an Escher tile contains much information, some of which can be extracted by using number theory. The crux of the matter is that • nontrivial circuits in the period graph can be viewed as vectors in Z 2 (by way of their vector values), • the vector value of any circuit in GT is a linear combination of ghost vectors, GV, and • the subspace spanned by G V has dimension 0,1 or 2. • If the subspace of Z 2 spanned by G V does not have full rank, then we sup-plement GV with either one or two collision-free vectors, as needed. • Ultimately, we associate an Escher tile with a pair of linearly independent vectors from Z 2 . A l l integer linear combinations of such a vector pair forms a (number theoretic) lattice. This special lattice will be the main tool with which we construct a Big Tile for T. The next three definitions serve to distinguish among the three possible ranks of the subspace spanned by the ghost vectors of an Escher tile. Definition 3.3.1 (Component of GT is trivially periodic): Let C(GT) be a con-nected component of period graph GT of an Escher tile T. If the Escher tile T' induced by C(GT) has no ghost vectors, then V is said to be trivially periodic. An Escher tile that is trivially periodic will have a wallpaper component that is bounded by a disk in the plane. See Figure 3.6. 35 Definition 3.3.2 (Component of GT is singly periodic): Let C(GT) be a con-nected component of period graph GT of an Escher tile T. Let T' be the Escher tile induced by C(GT)- If the dimension of the subspace spanned by the ghost vectors for 7" is one, then V is said to be singly periodic. In particular, if GV = { x i U , x2u, . . . , xNu}, then the natural period forT' is gcd(xi, ..., XN)U. That is, the natural period, which is a priori an inherent period, is the small-est (in Euclidean length) vector [^ 1,^ 2] for which there are related motif pieces in different locations, (ms, a, b) and (ms, c, d) such that Pl a — c P2 b -d Moreover, an Escher tile that is singly periodic will have a connected component that is infinite, but that is contained in a band of finite width. See Figure 3.7. Definition 3.3.3 (Component of GT is doubly periodic): Let C{GT) be a con-nected component of period graph GT of an Escher tile T and suppose T" is the Escher tile induced by C(GT)- If the dimension of the subspace spanned by the ghost vectors G V for T' is two, then T' is said to be doubly periodic. Any basis for GV is a pair of natural periods for T". An Escher tile that is doubly periodic will have a component that is un-bounded in all directions; it cannot be contained in any half-plane. See Figure 3.8 for an example of an Escher tile whose period graph has a doubly periodic compo-nent. For the most part we will concentrate on Escher tiles whose period graphs have only one connected component. Figure 3.9 is a singly periodic Escher tile with natural period [1, —3]. Figure 3.10, a fragment of the wallpaper pattern generated 36 by the Escher tile in Figure 3.9, shows three vectors: the natural period ([1, —3]), a collision-free vector ([1, 0]), and a forbidden vector ([0, —1]). Next we use the natural period(s) of C(GT) to give a more concise descrip-tion of wallpaper components than that given by Definition 2.2.7. Lemma 3.3.4 (Wallpaper Component Description): Let T — {(mi, 0, 0), . . . , (mk, 0, 0)} be an Escher tile and suppose GT is is connected. • Suppose GT is singly periodic with natural period \pi,P2] and let ST be an agglomerated spanning tree for GT that yields gen(T, 0, 0) = {(mi, 0, 0), (m2,i2, J2)i • • •, (™>k,ik,3k)}- ThenW((ml,r,s))= {{(m^r + k0pu s + k0p2), (m 2 , r-i2+koPi, s-j2+k0p2), . . . , (m f c, r-ik + k0pi, s-jk+k0p2)} : k0 G Z}. • Suppose GT is doubly periodic with natural periods [pi,p2] and [qi, ft], and let §T be an agglomerated spanning tree for GT that yields gen(T, 0, 0) = {(mi, 0,0), (m2,i2,j2), •-., (rnk,ik,jk). ThenW((mur,s)) = {{{m1,r + koP\ + l0qi, s + k0p2 + /oft), (™2, r - i2 + k0pi + l0qi, s-j2 + k0p2 + /oft), ..., (mk, r -ik + koPi + l0qi, s - jk + k0p2)} : A;0, l0 € Z} . Proof: Case 1 (GT is singly periodic with natural period [pi,p2]): By Defi-nitions 2.2.7 and 3.1.1, in general, if (ms,ii,ji) and (mt,i2,j2) G W((mi,r,s)) are distinct, then there exists a nonempty path GT from vs to vt. In our particular situation, (mi, i,j) G W((mi,r, s)) with (i,j) ^ (r, s) if and only if there exists a nonempty circuit, Circ, in G T beginning (and ending) on vL. Since GT is singly periodic, the vector value of Circ is /cobi,P2] for some /c0 £ Z . Alternatively, i = r + /c0pi and j = s + A;0p2, as needed. Now suppose (mx,i,j) G W((m!,r, s)) for some x G { 2 , . . . , k}. There is a path from (mx, r, s) along contiguous motif pieces in W((mi,r, s)) if and only if 37 there is a corresponding path P from vx to v\. HP is the unique path from vx to v\ in ST, the agglomerated spanning tree of GT then i = —ix + r and j = — jx + s. If P is not the unique path from v\ to vx in S V then suppose P' is. In other words the vector value of P' is [ix, jx]. The concatenation of P with the reversal of P' yields a circuit starting (and ending) at V\ and passing through vx. By necessity, the vector value of the circuit is ko\pi,p2] for some k0 ^ 0. So, on one hand, the vector value of Circ is k0\pi,p2] and on the other hand the vector value of Circ is the difference of the vector values of P and P'. In all, the vector value of P is then h[Pi,P2\ ~ [ix,3x] = [-ix + koPu -jx + k0p2]. Alternatively, i = r - i x + k0pi and j = s — jx + k0p2. In summary, the set of locations that contain translates of my in W((mi,r, s)) is given by {{r-iy + kopx, s-jy + k0p2 : k0 £ Z} for y = 1,..., k. Case 2 (Gr is doubly periodic with natural periods [pi,£>2] and [qi, tfe]): A sim-ple modification of the proof of Case 1 gives us that the set of locations that contain translates of my in W((m,i,r, s)) is given by {(r — iy + k0pi + loq2, s — jy + k0p2 + I0Q2 • k0,l0 E Z} for y = 1,..., k. | Finally, we will use ghost motif pieces and vectors to produce the natural periods (if there are any) of an Escher tile. Proposition 3.3.5 (Use Ghost Motif Pieces to Extract Natural Periods): Let T = {(mi, 0, 0), . . . , (m-h, 0, 0)} be an Escher tile whose period graph GT is con-nected Let GV be the set of ghost vectors for T. The natural periods ofT can be extracted from GV inO(k2) time. Proof: By Lemma 3.2.6 and Corollary 3.2.7 there are 0(k2) ghost vectors each of whose entries is bounded (in absolute value) by 0(k). Suppose T is singly periodic and let the set of ghost vectors be G V = {X\VL, ..., xtu}. By Definition 3.3.2, the natural period of T is gcd(^i, . . . , xt)u. Since 38 t = 0(k2) and X j = 0(k) for i = 1,..., k, finding the greatest common divisor can be done in 0(k2) time. Suppose T is doubly periodic. By Definition 3.3.3, Lemma 3.2.6 and Lemma 3.2.9, a pair of natural periods for T is a basis for the vector space spanned by G V . Since \GV\ =0(k2) and the entries of each element of GV are bounded in absolute value by 0(k), finding a basis can be done in 0(k) time [Co95]. | The purpose of the next definition is to identify a particular translate of m i for an arbitrary Escher wallpaper component W((mi, r, s)) whose component in the period graph is singly periodic. We have m i in location ( r , s) belonging to W((mi, r, s)). When a wallpaper component corresponds to graph component of GT that is singly periodic (in a sense, the hardest case) we subtract integer multiples of the only periodicity [ p i , p 2 ] from [r, s] to find translates of mx in W ( ( m i , r, s)). The translate of m x closest to and above or on the x—axis will be a special copy of m i and its y-coordinate defined to be the height of W((mi, r, s)). For exam-ple, when the height of W((m-i,r,s)) turns out to be 0, then W((mi,r,s)) is a horizontal translate (or rightward shift) of W((mi, 0,0)). Definition 3.3.6 (Height of a singly periodic wallpaper component): Let T be a singly periodic Escher tile with natural period [ p i , p 2 ] . The height of W ( ( m i ,r,s)) is s (mod P2) and is denoted height(W((m-i, r, s))). Escher tiles for which the period graph has some connected components that are not doubly periodic provide flexibility in the outcome of a Big Tile. We will see that a doubly periodic Escher tile is encoded by a pre-determined number-theoretic lattice, and gives no choice as to the assignment of colors in a Big Tile, and is in a sense the easiest case to consider. The essence of the global solution, that of exis-tence of a Big Tile for arbitrary Escher tiles, lies in the choice of one collision-free vector in the singly periodic case, and in the choice of a pair of linearly independent 39 collision-free vectors in the trivially periodic case. One has the sense that there is a minimal (with respect to the associated lattice) such vector pair that will do the trick. Any vector pair that survives the minimality conditions and respects the in-herent periodicities will be fair game for use in creating a Big Tile. Not surprisingly, since we are after a rectangular Big Tile, and since we are going to use a lattice L to find one, it will be important to find the smallest rectangular sublattice of L. Lemma 3.3.7 (Smallest Rectangular Sublattice of Lattice): Suppose L = < [Pi, P2], [qi, Q2] > is the lattice generated by \puP2], [91,92] £ ^ 2 and let A = Pi92 — P29i- The smallest rectangular sublattice of L is L' = < [|gcd(^2 ^ , 0], [0> |gcdut i ,9 i ) | ] > • Proof: If there are x, y G Z such that Pi 9i r + y — P2 _ 92 0 then Pi 9i X r P2 92 _ . y . 0 in which case X 1 92 -Qi r y ~ A -P2 Pi 0 or alternatively, X A . y . -p2r A Thus, r = — — r because r G Z and Iri is minimal. A similar argument shows that the smallest nonzero value of \s\ for which [0, s] G L is s = gcd(^ qiy This completes the proof. | 40 Our next task will be to gain some understanding about how to find one or two collision-free vectors for an Escher tile whose period graph is connected and either singly or trivially periodic. To find suitable collision-free vectors, we call upon OT, the overlap graph of T; we explain the use of overlap graph by way of a detailed example. 41 Figure 3.1: An Escher tile in home position surrounded by eight other Escher tiles. Motif piece (m 4, 0, 0) is contiguous with (m 3 ,1, 0) and (m 3, 0, 0) is con-tiguous with (m 4, —1,0). Therefore, the period graph (see Figure 3.2) contains directed edge ( r a 4 , ra3) with vector label [1,0] and directed edge ( r a 3 , m 4) with vector label [—1,0] (as well as many other edges). 42 44 Figure 3.5: Unravelling the Escher tile puzzle with a set of generating motif pieces. A ghost of (m 3 , —2,1) is (m 3 , 0, 2) 45 Figure 3.6: Trivially periodic Escher tile Figure 3.8: Component that is doubly periodic Figure 3.9: Singly periodic Escher tile with natural period [1, —3] 47 Figure 3.10: Natural period [1, —3]; collision-free vector [1,0]; forbidden vector [o,-i] 48 Chapter 4 Detailed Example Begin by inputting an Escher tile T = {(mi, 0, 0), (m 2 , 0, 0), . . . , (m 9 , 0, 0)}: see Figure 4.1. We keep track of the pairwise intersections of elements of T in the overlap graph OT, and also of the intersections of elements of T with dSo,o. • Construct GT, the period graph for T; see Figure 4.2. • Let ST be a spanning tree of the agglomerated period graph GT- An example is shown in Figure 4.3. • We gain some insight by drawing the vertices and edges of the spanning tree in Figure 4.3 in the plane so that the vertices that represent motif pieces are in their correct physical locations under the assumption that m x is in location (0,0). See Figure 4.4. • By way of the fat spanning tree ST, a set of generating motif pieces (see Definition 3.2.4) is given by gen(T, 0,0) = {(mi, 0,0), (m 2 ,0,1), (m 3 , 2,0), (m 4 ,1,0), (m 5 ,1,1), (m 9 ,1,1), (m 6 , 2,1), (m 7 ,3,1), (m 8 , 3, 2)}, which is shown in Figure 4.5. 49 Let RT be the set of edges that were removed from GT when the spanning tree ST was constructed. In this example, RT = {(u 4, Vg), (v2, v3)}. Let RT = E(GT) \ E(ST)- That is, return the multiple edges and vector labels to elements of R. Then RT = {(w4, vg) labelled [0, —1], (vg, i>4) labelled [0,1], (v2,v3) labelled [0,1], (v3,v2) labelled [0, -1]}. Thus, there are potentially four ghost motif pieces: {(m 4 ,1,0), (m 9 ,1,1), (m 3 , 0, 2), (m 2 , 2, —1)}. A l l of these motif pieces are contiguous with generating motif pieces, but not all give rise to ghost vectors as we shall see. We wish to determine if the motif piece corresponding to an endpoint of a re-moved edge is in a location that is different than its corresponding generating motif piece; when such a situation occurs, we have identified a ghost vector. - For example, (m 4,1,0) lives directly below (m 9 ,1,1), and is shown in Figure 4.6 in dark gray. Since (m 4,1,1) lands in the same location as generating (m 4 , 1, 0), no information is gained. - Similarly, the ghost of (m 9 , 1,1) lives directly above the generator (m 4 , 1, 0), and lands in the same location as the original (m 9 ,1,1), so no information is gained. See Figure 4.7. - What about the ghosts of (m 2,0,1) and (m 3 , 2,0)? The ghost of (m 3 , 2, 0) lives directly above (m2,0,1) and is shown in Figure 4.8. - Since the locations of (m 3 ,0, 2) and (m 3 , 2,0) satisfy [0 - 2, 2 - 0] = - [2 , -2 ] , we conclude that [2,-2] is a ghost vector for the Escher tile in this example. - The last motif piece to check is the ghost of (m 2 ,0,1). In general, the number of ghost motif pieces is at most 2|i?r|- The ghost of (m2,0,1) lives directly below (m 3,2,0) as shown by Figure 4.9. 50 - Since generator (m 2,0,1) and ghost (m 2 , 2, —1) satisfy [0 — 2,1 —(-1)] = [2, -2] , we find (again) that [2, -2] is a ghost vector of T. Figure 4.1: An Escher tile: Big Tile to be determined We conclude that the Escher tile T is singly periodic with period [2, -2] because there is only one ghost vector. The previous example illustrates (one case of) a theorem guaranteeing that the natural period(s) of Escher tiles can be found in polynomial time. We now have a method by which we can compute the /^-vertices of the over-lap graph. Detect-reIated-motif-pieces-in-location-(0,0) algorithm: If Escher tile T is doubly periodic, we need not worry about detecting related motif pieces because the Big Tile is unique and predetermined. In fact we do not need to use the overlap graph, as we shall see in Section 5.1. In that case, first assume that T is singly periodic with natural period \p\, p 2]. Recall that gen(T, 0, 0) = {(mi, 0,0), ( m 2 , i 2 , j 2 ) , (mk,ik,jk)}. Let (ms,is, js)-. (™*,h,jt) €• gen(T,0,0) with s f t. Since (ma,i„ja) is related to (mt,it,jt), 51 Figure 4.2: Period graph, GT, for T in Figure 4.1 we have (m s,0,0) is related to (mt,it — is,jt — js). Hence, (m s ,0,0) is related to (mt, 0,0) if and only if (mt, 0,0) is related to (mt, it - is,jt — js). By Lemma 3.3.4, (mt, 0,0) is related to (mt, it — is,jt — js) if and only if is ~ it = k0 Pi js - jt . P 2 . for integer k0 0. Practically speaking, in the singly periodic case, we have reduced the prob-lem of detecting which motif pieces in an Escher tile are related to that of comparing 52 Figure 4.3: A fat spanning tree, ST> for GT the locations of elements of gen(T, 0, 0) with their corresponding ghosts. In this example, (m 5,0,0) and (m 9,0,0) are related because ( m 5 , l , l ) , (m 9,1,1) € gen(T, 0,0) are related since [ 1 - 1 , 1 - 1 ] = [0,0] is a multiple of [2, -2] so that v5 G [vg]. (In the trivially periodic case, the agglomerated spanning tree is unique and thus a set of generating motif pieces necessarily places related motif pieces in the same location.) 53 Figure 4.4: The fat spanning tree, ST with vertices embedded in correct loca-tions relative to (mi, 0,0) 4.1 Get a Collision-Free Vector Next we seek a collision-free vector that is linearly independent with [2, —2], the natural period of T. To find such a vector we will use the Overlap Graph of T. See Figure 4.10. Remark: At most 14 distinct Escher wallpaper components overlap W((m\, 0,0)). (In general the "14" will be replaced by twice the number of edges in the overlap graph.) Idea of Proof: By Definition 2.2.7, W((mi, 0,0)) is the set of all motif pieces related to (mi, 0,0). By Lemma 3.3.4, the set of all translates of (mi, 0,0) that belong to W((mi,0,0)) have locations given by {(2k, — 2k) : k G Z} . Simi-larly the set of translates of (m 2,0,0) that belong to W((m2,0,1)) have locations given by {(2k, 1 - 2k) : k G Z}. The set of translates of (m 3,0,0) that be-long to W((mu 0,0)) have locations given by {(2 + 2k,-2k : k G Z}. The 54 Figure 4.5: Set of generating motif pieces gen(T, 0, 0) set of translates of (m 4,0,0) that belong to W((mx, 0,0)) have locations given by {(1 + 2k, -2k) : k G Z}. The set of translates of (m5, 0, 0) and (m 9 , 0, 0) that belong to W((mi, 0, 0)) have locations given by {(1 + 2k, 1 — 2k) : k G Z}. The set of translates of (m 6 , 0, 0) that belong to to W((mi, 0, 0)) have locations given by {(2 + 2k, \ - 2k) : k G Z}. The set of translates of (m 7,0,0) that belong to to W((mi, 0,0) have locations given by {(3 + 2k, 1 — 2k) : A; G Z}. The set of translates of (m 8 , 0, 0) that belong to to W((mx, 0, 0)) have locations given by {{3 + 2k,2-2k) : k G Z}. Thus, to find a wallpaper component that overlaps W((mi, 0,0)), it suf-fices to pick for example, (m 4 ,1 + 2fc, —2k) and find all motif pieces that overlap (m 4 ,1 + 2k, —2k) (and in general, find all motif pieces that overlap elements of gen(T, 0, 0).) With that goal in mind, note that (m,, 1 + 2k, -2k) n ( r a 4 , 1 + 2k, —2k) ^ 0 if and only if (m 4 ,1, 0) fl {rrii, 1, 0) ^ 0 , which is true if and only if (m 4,0,0) n (rrii, 0,0) ^ 0 . But this is precisely the information contained in the overlap graph OT, namely which motif pieces in a given unit square have nontrivial intersection as subsets of R 2 . In all, for each i?-vertex [v] in the overlap graph, 55 Figure 4.6: A potential ghost of m 4 there are deg([u]) motif pieces that overlap the equivalence class of motif pieces contained in [v]. Hence, there are at most Yl[v]eoT d e s(M) = ^ distinct wallpaper components that overlap W((mi, 0,0)). A nearly immediate consequence is that there exists a vector [r, s] such that W((TOI,0, 0)) and W((mi,r, s)) do not overlap, which is what we are after. In fact, it won't be hard to generalize away from this example and characterize the set of all vectors [r, s] for which W((mx, 0, 0)) does not overlap W((mi, r, s)) for any connected component of the period graph of an Escher tile T. For now, though, we set our sights lower since we are after existence. Re-call that the goal for the singly periodic example in this section is to find a second vector [r, s] linearly independent with [2, —2] and such that W((mi,r, s)) does not overlap W((mi, 0,0)). It suffices to find the (at most) 14 wallpaper components that overlap W((mi, 0,0)), and then, for example, find a translate of W((mi, 0,0)) that is not in the set of wallpaper components that overlap W ( ( m i , 0,0)). The fol-lowing are the details of computations that enable us to find suitable collision-free vector(s). 56 mi )—{ m4 ) — ( m3 Figure 4.7: A potential ghost of m 9 The Actual Work: Since (mi, 0,0) and (m 8,0,0) are not overlapped by any motif pieces, it suffices to study the pairwise intersections among (m 2 , 0,1), (m 3 , 2, 0), (m 4 ,1 , 0) (m 5 i 9 ,1,1), (m 6 , 2,1), and (m 7 , 3,1). We use gen(T, 0, 0) as a set of generators together with the natural period [2, —2] to choose motif pieces (mi, x, y) such that y = 0 or y = 1 (the height of the wallpaper component) as generators for all wallpaper components under consideration. This gives us an easy way to see when two wallpaper compo-nents are the same. Motif piece (m 2,0,1) is overlapped by . W((m 4 , 0 , l ) ) W((mu-1,1)), • H/((m 6 ,0 , l ) ) W((mu-2,0)), • W((m7,0,1)) W((mu-3, 0)), and • W{(m5,9,0,l)) = W((m1,-2,l)). Motif piece (m 3,2,0) is overlapped by 57 0 Figure 4.8: The ghost of m 3 • W{(m6, 2,0)) = W((rnu 0, -1)) = W((mu -2,1)) . Motif piece (m 4,1,0) is overlapped by . W((m2,1,0)) = W((mi,-l,l)), • W{(m6,l,0)) = ^ ( (m! , -3 ,1 ) ) , and . W((m7,1,0)) = W((mi,-4,1)). Motif piece (m 5 > 9,1,1) is overlapped by . W((m2,l,l)) = W((ml,l,0)). Motif piece (m 6,2,1) is overlapped by • W{{m2,2,l)) = W{{mx,2,0)), • i y ( (m 3 , 2 , l ) ) = W((m 1 ,0 , l ) ) ,and • W((m4,2,l)) = W((ml,l,l)). Motif piece ( ra 7 ,3 ,1 ) is overlapped by 58 Figure 4.9: The ghost of m 2 • H/((m 2 ,3 , l ) ) = W ( ( m i , 3 , 0 ) ) a n d • W((m4,3,l)) = W((mi,2,l)). From a wallpaper component W((mi, a, b)) that overlaps W((mi,0,0)) (with b — 0 or b = 1 for this singly periodic example with natural period [—2, 2]) we know that any vector in the set {[a, b] + k[-2,2] : k € Z} is not available as a collision-free vector for Escher tile T. The previous list, once the repetitions have been eliminated, yields the complete list of vectors that are not available as collision-free vectors: • { [ - l , l ] + fc[-2,2] : k e Z}, • {[-2,0] + fc[-2,2] :keZ}, • {[-3,0] + fc[-2,2] : k G Z}, 59 Figure 4.10: The overlap graph • {[-2,1] + fc[-2,2] : k G Z}, • {[-3,1] + A;[-2,2] : k G Z} , • {[-4,1] + fc[-2,2] : k G Z}, • {[1,0] + A;[-2,2] : k G Z} , • {[2,0] + A;[-2,2] : k G Z}, • {[0,l] + A;[-2,2] : A; G Z}, • {[1,1] + 2, 2] : k G Z} , • {[3,0] + fc[-2,2] : A; G Z}, and • {[2,1] + A;[-2, 2] : k G Z}. Since neither of the sets {[3,1] +A;[-2, 2] : A; G Z} nor {[-4,0] + k[-2, 2] : A: G Z} are in the previous list, both [3,1] and [—4,0] are available as collision-free vectors. Moreover, the lattices < [-2,2], [3,1] > and < [-2, 2], [-4,0] > are inequivalent, which will lead to the construction of two inequivalent 8-colored Big Tiles for the Escher tile of this example. 60 4.2 Big Tile Dimensions We return to a more general setting: suppose the oracle has, upon input of Escher tile T, given you the pair of linearly independent vectors [pi,p 2], [91, 92] £ Z 2 that are collision-free and/or natural periods for T (depending on the input). Let A = \P1Q2 — P2Qi\- The Big Tile, BT, we will construct requires A colors. The dimen-sions of BT will be , ,,A—r, by , • . , A — V l ; the oracle tells us that the dimensions 1 |gcd(P2,<?2)| •> |gcd(pi,gi)| were arrived at by finding the smallest rectangular sublattice of the lattice < [pi, p 2], [?i> 92] > (see Lemma 3.3.7). Now, given any location (r, s) in the region (0 < r < | g c d(p 2 q 2 ) | and 0 < s < [gcd^ assign a color to (mi,r, s). The colors are chosen from a set of colors called a palette. The palette contains A colors, one for every pair where [i,j] is a coset representative of < [pi,p2]> [91,92] >, the lattice generated by [pi,p2] and [91,92]. Visually, the palette is the half-open parallelogram spanned by [pi,p2] and [qi, q2}. Loosely speaking, we color each copy of m,\ inside the palette with the color corresponding to the location of each such rri\. Extending the correct colors to the remaining motif pieces in the rest of the subsquares in the Big Tile region follows with some minor work that exploits some information contained in a spanning tree of the agglomerated period graph GT- We will illustrate the work by continuing the example. 4.3 Assigning The Colors The Escher tile T in our example was singly periodic with period [2,-2] and in section 4.1 we found that [3,1] could be used as a collision-free vector. A Big Tile parameterized by [2, -2] and [3,1] requires |2 x 1 — (3 x (—2))| = 8 colors. The palette has dimensions 8 x 1 , and linear algebra, elementary number theory, and 61 a final use of the locations of the set of generating motif pieces found in section 4.1, Figure 4.5 are all that are needed to assign colors to all of the motif pieces whose locations are in the Big Tile region. In particular we can encode the col-oring instructions in a pair of permutations: one horizontal and the other vertical. For example, the horizontal color permutation is given by (12345678) and can be extracted directly from the palette. The meaning of the permutation is: if motif piece (rrii, r, s) is known to be assigned color c, then (m„ r + j, s) must be assigned color c + j (mod 8). The vertical coloring permutation is given by (1,1 + 1 x 5 (mod 8), 1 + 2 x 5 (mod 8), 1 + 3 x 5 (mod 8), 1 + 4 x 5 (mod 8), 1 + 5 x 5 (mod 8), 1 + 6 x 5 (mod 8), 1 + 7 x 5 (mod 8)) = (16385274). That is, if say motif piece (rrii, r, s) is known to have color c, then (rrii, r,s + j) must be assigned color c + 5j (mod 8). This information can be captured in a set of nine instruc-tions to color all of the motif pieces in the Escher tile T with location (r, s): Let (rrii, t) mean "assign color t to motif piece rrii in location (r, s)." The coloring in-structions for tile T in location (r, s) are given by (T, r, s) = {(mi, 1 + r + 5s (mod 8)), (m 2 ,6 + r + 5s (mod 8)), (m 3 ,5 + r + 5s (mod 8)), (m 4 ,7 + r + 5s (mod 8)), (m 5 ,4 + r + 5s (mod 8)), (m 6,6 + r + 5s (mod 8)), (m 7 ,1 + r + 5s (mod 8)), (m 8 ,0 + r + 5s (mod 8)), (m 9 ,0 + r + 5s (mod 8))}. The visual output of the eight-colored 8 x 8 Big Tile for the Escher tile given in Figure 4.1 is shown in Figure 4.11. This method illustrates the outline of an efficient algorithm for producing a Big Tile for an arbitrary Escher tile T. Moreover, this example was chosen to illustrate another idea, that of the idea of essentially "different" A-colored Big Tiles for a given Escher tile. Recall that [3,1] was a valid collision-free vector for the construction of a Big Tile for the Escher tile given in Figure 4.1. Another valid choice is [—4,0], 62 Figure 4.11: An eight-colored 8 x 8 Big Tile for the Escher tile in Figure 4.1. This corresponds to the lattice generated by {[2, —2], [3,1]}. and it is interesting to note that |det 0 Idet -2 3 2 1 - 8. Note also that the lattice generated by the vector pair {[2, —2], [-4,0]} is not equivalent to the lattice generated by {[—2, 2], [3,1]} (this requires an argument using a basic tool from number theory [Ap76]). A different eight-colored Big Tile for T, corre-sponding to the lattice generated by {[2, -2] , [-4,0]}, is shown in Figure 4.12. In the next Chapter we will prove that a Big Tile exists for any Escher tile. 63 Figure 4.12: A different eight-colored Big Tile for the Escher tile in Figure 4.1. This corresponds to the lattice generated by {[2, —2], [—4,0]}. 64 Chapter 5 Mirabile Dictu: Existence Proof The purpose of this chapter is to verify the allegations of previous chapters, namely that a Big Tile exists for an arbitrary Escher tile. First we study an Escher tile whose period graph is connected. That a Big Tile exists for an arbitrary Escher tile will follow with very little extra work. The Big Tile existence proof will be accom-plished by constructing a Big Tile for T with tools from Chapter 3. In Chapter 6 we will massage the construction into an efficient algorithm. In Chapter 7 we will shed light on why the Big Tiles arising from our construction are canonical, and follow with a canonical representation of Big Tiles that will shed some light on the chromatic number of an Escher tile, and also under what circumstances there exist two measurably different A-colored Big Tiles for a fixed value of A . These ideas are intended to be catalysts for a future classification of Big Tiles. 5.1 A Few More Tools It is of seminal importance to detect when two distinct wallpaper components over-lap. 65 Lemma 5.1.1 (Find Collision-Free Vectors): LetT = {(mi, 0 ,0) , . . . , (mk, 0,0)} be an Escher tile whose period graph has one connected component and suppose T is either trivially or singly periodic. l.IfT is singly periodic with natural period \pi,P2], then there exist infinitely many [91,92] G Z 2 linearly independent with [pi,p2], such that ( IJ M)f]( U N ) = 0-MelV((mi,0,0)) NeW({mi,qi,qi)) 2. IfT is trivially periodic, then there exist infinitely many linearly independent vector pairs {[pi,p 2], [91,92] £ Z 2 } such that ( U M)f l( U Ar) = 0> M € W ( ( m i , 0 , 0 ) ) JVeW ( ( m i , p i , p 2 ) ) and ( U M ) fK U N) = 0-M € W ( ( m i , 0 , 0 ) ) N G W ( ( m i , 9 i , 9 2 ) ) Proof: Case 1: We draw upon the many and varied tools from Chapter 3. We have: • an Escher tile T with a connected period graph GT that is singly periodic with natural period [pi,p 2], • an agglomerated spanning tree ST that gives rise to a set of generating motif pieces gen(T, 0,0) = {(mi, 0,0), ( m 2 , i 2 , J2), • • •, (mk,ik,jk)}, and 66 • the overlap graph, OT, which tells us if one equivalence class of motif pieces in any given location intersects another in the same location. We need: • a characterization of the set F(T) of "forbidden" wallpaper components {W((mu a, b))} that overlap W{[mi, 0, 0)). We will use 0T to find F(T), which is represented by a set of forbidden vectors, F(T). We will show that \F(T) \ is finite, but more importantly, we will show that Z 2 \ F(T) is nonempty and in fact infinite. The Procedure: First we find F(T). Suppose W((mua,b)) overlaps W((mu0,0)). By Def-inition 2.2.8, two such wallpaper components overlap if and only if 3 (ms, x, y) £ W((mi,0,0)) and (mt, x, y) £ W((mua,b)) such that Mf)N ^ 0 . For example if M is motif piece mi in some location, then the location must be (k0pi, k0p2) for some k0 £ Z . In that case, N = (ms, k0pi, k0p2) for some s £ { 1 , . . . , k}. By the construction of W((mx, 0, 0)) (see Definition 2.2.7) (mi,k0pi, &0P2) f l ( m s , hp2) ^ 0 if and only if (m x , 0,0) f | (rns, 0, 0) ^ 0 . In gen-eral, for (mt,a,b) £ W((mi,0,0)) we have (a, b) = (-it + k0 p i , -jt+ k0p2), which means (mt, -it+ Ar0pi,-jt + k0p2) f | (ms, -it + k0pi ,-jt + k0p2) ^ 0 if and only if (mt, 0,0) f](ms, 0,0) ^ 0. That is, wallpaper components that overlap W((mi, 0,0)) can be tracked to precisely those pairs of motif pieces in location (0,0) that intersect one another, which is exactly the information given by the over-lap graph OT, a finite graph. That is, to find a bound for the number of wallpaper components that overlap W((mi, 0,0)), it suffices to count the number of motif pieces that intersect each element (m s , is,js) £ gzn(T, 0,0); but (ms, is,js) is in-tersected by exactly deg([v„]) distinct motif pieces, where [vs] is an E-vertex of the 67 overlap graph OT- Thus, an upper bound for the number of wallpaper components that overlap W((mx,0,0)) is YI ° M N ) ' which is twice the number of edges in OT, this quantity does not always give the exact number of distinct wallpaper components that overlap W((mx, 0,0)) because two different pairs of intersecting motif pieces may belong to the same wallpaper component, as is the case in the detailed example in Chapter 4. (Figure 5.1 shows a set of generating motif pieces gen(T, 0, 0) for the Es-cher tile in Figures 3.9 and 3.5 and all of the motif pieces that overlap elements of gen(T, 0, 0). See Figure 5.2 for the overlap graph of T.) Now, suppose the finite set of forbidden wallpaper components that over-lap W^rm, 0, 0)) is given by F(T) = {W((mu au h)),..., W((mu at, bt))}. Though each forbidden wallpaper component W((mi,as,bs)) is encoded by an infinite set of forbidden vectors, namely {[as + k0pi,bs + k0p2] • k0 £ Z} , we can assume without loss of generality that 0 < bs < p2fors — 1,..., k by using bi = height(W((mi, ai, bi)) (Definition 3.3.6). Consider H = {[M,0] : M £ Z} (or else {[0,M] : M £ Z} if it so happens thatp2 = 0). Only finitely many elements of H can correspond to elements F(T) leaving infinitely many vector candidates that can be used to identify Escher wallpaper components that do not overlap W((mx, 0,0)). We conclude that there exist infinitely many vectors [qi, q2] £ Z 2 such that W((mi, 0, 0)) does not overlap W((mx, qi, q2)). This completes the first (and hard-est) case. Case 2: Suppose T is trivially periodic. We modify the argument given in Case 1 to apply to this case. In particular, finding an upper bound for the number 68 of wallpaper components that overlap W((mi, 0,0)) can be accomplished by ex-amining all pairs of overlapping motif pieces in each location of the set of gen-erating motif pieces, which is, again, twice the number of edges in the overlap graph so that the set of forbidden wallpaper components is finite. Say the set is F(T) = {W((mi, a-i, h)),..., W((mi, at, bt)). Since T has no natural periods, the set of vectors {[ax, bx],..., [at, bt}} uniquely identifies the forbidden vectors F(T). In that case any vector in [x, y] e Z 2 \ F(T) has the property that W((mi,x, y)) does not overlap W((m,i, 0,0)). This concludes Case 2 and the proof. | We have, now, a constructive method to identify a pair of "good'' linearly independent vectors [px, p2], [qx, q2] € Z 2 with an Escher tile whose period graph is connected. The lattice L = < \pi,p2}, [<Zi, (fe] > will be all we need to construct a Big Tile for T. Lemma 5.1.1 gives fuel to the idea of constructing a Big Tile from a lattice. We make these ideas precise in the next several definitions. Definition 5.1.2 (Forbidden Vectors and Determinants): Let T = { ( m i , 0,0), ..., (trik, 0, 0)} be an Escher tile whose period graph is connected, and is either singly or trivially periodic. By Lemma 5.1.1 the number of wallpaper components that overlap W((m\, 0, 0)) is finite and can be characterized by a set of vectors F(T). Let F(T) = {W((mu au bx)), W((mt,at,bt))} be the finite set of wall-paper components that overlap W((mi, 0, 0)). • If T is singly periodic with natural period \pi,p2], then F(T) = {[ax + koPi, h + k0p2], ...,[at + kopi, bt + k0p2] : k0 G Z and 0 < h < p2 for i = l . . . , * } . • IfT is trivially periodic then F(T) — {[ax, bx],..., [at, bt]}. We say that F(T) is the set of forbidden vectors for T, and 69 • ifT is trivially periodic, for any [n, r 2], [si, s2] £ F(T), we say \ris2 — r2S\\ is a forbidden determinant for T. • If T is singly periodic with natural period \pi,p2] then for any [qi,q2] £ F(T), we say \piq2 — p2qx\ is a forbidden determinant for T. Note that in the singly periodic case, the complement of F(T) in Z 2 is ex-actly the set of collision-free vectors for T. In the singly periodic case there are infinitely many vectors that identify the finitely many forbidden wallpaper components that overlap W((mi, 0, 0)) but as it turns out there are only finitely many forbidden determinants, as we demonstrate in the next lemma. Lemma 5.1.3 (Finitely Many Forbidden Determinants): Let T be an Escher tile whose period graph is connected and is either trivially periodic or else singly periodic with natural period [pi,p2]. Then there are only finitely many forbidden determinants for T. Proof: If T is trivially periodic then by the proof of Lemma 5.1.1 there are only finitely many forbidden vectors, and hence by Definition 5.1.2 there are only finitely many forbidden determinants. If T is singly periodic with natural period \p\,p2], then by the proof of Lemma 5.1.1 the set of forbidden vectors for T is given by F(T) = {[«i + k0pi, bx + kQp2],..., [at + k0pi, bt + kQp2] : k0 £ Z and 0 < b{ < p2 for i — 1,..., t). Since |det px a{ + hpi | = |det Pl CLi p2 h + k0p2 Pi k there are only finitely many forbidden determinants for T. | 70 We have enough vocabulary to narrow the field of allowable vectors even further; we wish to restrict to allowable vector pairs {[pi,P2], [91,92]} such that Pi 9i |det P2 92 is strictly larger than any forbidden determinant. Definition 5.1.4 (Color-Safe Determinant): Let T be an Escher tile whose period graph is connected, and is either singly or trivially periodic. Let F = { A x , . . . , At} be the set of forbidden determinants for T. Then a color-safe determinant for T is any integer A such that A > maxAieF{Ai\. Definition 5.1.5 (Color-Safe Lattice): Let T be an Escher tile whose period graph is connected and suppose A(T) is the set of collision-free vectors for T in the triv-ially and singly periodic cases. • Suppose T is trivially periodic. Let \p\,P2\ a n d [91,92] £ A(T) be linearly independent and suppose \p1q2 — P2911 is a color-safe determinant for T. Then the lattice < [pi,p 2], [91,92] > is said to be a color-safe lattice for T . • Suppose T is singly periodic with natural period [pi, p2] and let [qx, q2] G A(T). If \p\q2 — p2q\\ is a color-safe determinant for T then the lattice < [Pi, P2], [91,92] > is a color-safe lattice for T. • Suppose T is doubly periodic with natural (linearly independent) periods [pi,p2] and [91,92]- Then the lattice < [^ 1,^ 2], [91,92] > is a color-safe lattice for T. It will be necessary to know that if L =< \puP2], [91,92] > is a color-safe lattice then any sublattice of L is color-safe. 71 Lemma 5.1.6 (Sublattice of Color-Safe Lattice is Color-Safe): Let T be an Es-cher tile with color-safe lattice L. Then for any sublattice L' C L we have V is color-safe for T. In particular, if[r, s] G L' then W((mx, 0, 0)) does not overlap W((mur,s)). Proof: Suppose V =< [ax, a2], [bx, b2] > is a sublattice of L =< [pi,p2], [91, q2] >• Then 3xx, yx, x2, y2 G Z such that and a i Pi + yi qi P2 92 h = x2 Pi + 2/2 9i b2 P2 92 which means ax bx XxPi + 2/i9i X2P1 + J/291 a2 b2 XlP2 + 2/192 X2P2 + 2/292 and thus X1P1 + 2/i9i X2P1 + 2/29i 1 X1P2 + 2/i92 x2p2 + y2q2 J But XxPx + 2/i9i X2P1 + 2/29i , |det I [ X1P2 + 2/i92 x2p2 + ?/292 J = |(P29i -P192)(Z22/1 - ^12/2)| > \P2q1 ~ Pi92 I because [ax, a2] and [61, b2] are linearly independent and xx,y\,x2,y2 G Z. In that case, since L is a color-safe lattice, |p 2 9i — P192I is a color-safe determinant and thus so is |(p 29i - Pi92)(^22/i ~ £12/2) I- We conclude that 11 = < [a l 5 a 2], [61, b2] > is color-safe. | The following corollary is a direct consequence of Lemma 5.1.6. 72 |det ax bx | = |det a2 b2 Corollary 5.1.7 (Vector in a Color-Safe Lattice is Collision-Free): Let T be an Escher tile T whose period graph is connected and for which L is a color-safe lattice. Then any v € L is a collision-free vector for T. Finally, it will be useful to find an upper bound for the area of a color-safe lattice in terms of k, the number of motif pieces in an Escher tile. This area is the absolute value of the determinant of the matrix of generating vectors. Proposition 5.1.8 (Color-Safe Lattice of Area at Most 0(k2)): Let T = {(mi, 0, 0), . . . , (mk, 0, 0)} be an Escher tile whose period graph is connected. • IfTis doubly periodic with natural periods [pi,p2] and [qi, q2] then < [pi, P2], [qi, 92] >. the color-safe lattice, satisfies \piq2 — P2Qi \ < (k + l)2. • IfT is singly periodic with natural period \px, p2] then < [pi, p2], [2k+2, 0] > is a color-safe lattice for T as long as p2 ^ 0. If p2 = 0, then < [pi,p2], [0, 2k + 2] > is a color-safe lattice for T. • IfT is trivially periodic, then < [2k + 3, 0], [0, 2k + 3] > is a color-safe lattice forT. Proof: If T is doubly periodic, the claim follows from Corollary 3.2.7. Sup-pose T is singly periodic with natural period [pi,P2] and without loss of gener-ality assume px ^ 0. By the proof of Lemma 5.1.1, we identify the finitely many wallpaper components that overlap W((mx, 0,0)) by examining the motif pieces that intersect each element of a set of generating motif pieces gen(T, 0,0) = {(mi,0,0), (mk,ik,jk)}- Suppose, for example, (ms,is,js) € gen(T,0,0) and that (ms,is,js)n (mt,is,js) for some t ^ s. Then (mt,is,js) is related to (mi, is — it,js — jt) and lies in the same forbidden wallpaper component W((mt, h, js)) = W((mi, is - it, js - jt)). By the proof of Lemma 3.3.5, \js - jt\ < \p2\. Hence, the height of W((mt, is, js)) is 73 • js - jt if js ~ Jt > 0, or else • js ~jt + \P2\ if j* ~jt<0. In the former case, the forbidden vector that we use to identify W((mt, is, js)) is [ia ~ h, js - jt], and in the latter case is [is -it±p1, j„ - jt ± p2]. In both cases, since by Corollary 3.2.7 we have \pi\ < k + 1, we have shown that any forbidden vector [a, b] for T has the property that \a\ < 2k + 2. If T is trivially periodic, then by a similar argument, the forbidden vectors all have entries bounded (in absolute value) by k. Thus, we are assured that we may use one of [2A; + 3, 0] or [0, 2k + 3] as a collision-free vector for T in the singly periodic case, and both of [2k + 3, 0] or [0, 2k + 3] as collision-free vectors in the trivially periodic case. In all cases we have shown that there exists a color-safe lattice whose fundamental region has area 0(k2). | We have worked hard to associate special lattices with an Escher tile T whose period graph is connected. The lattice < [p i ,p2] , [91,92] > is an abelian group that has \p\q2 — Piqi \ cosets. In the next section we will color the cosets of a color-safe lattice, extend the coloring to the wallpaper components in Wall(T), and extract a | p i 9 2 — p 2 9 i |-colored Big Tile for T. 5.2 Coloring the Cosets For the purpose of assigning colors to all of the motif pieces in Wail(T) we define the palette, which requires as input a linearly independent vector pair from Z 2 . Subsequently we define the colored tile, which requires an Escher tile and a palette as input. Definition 5.2.1 (Palette): Suppose \p\,p2] and [91,92] € Z 2 are linearly indepen-dent, let A = \piq2 - p2qi| and L =< \pi,p2], [91,92] >• The palette correspond-74 ing to [pi, p2], [qi, ft] is {[i, j] + L : i, j G Z}, and is denoted by Palette([pi, p2], [qi, q2]). In other words, the palette is the set of A distinct cosets of the lattice L. Often we denote [i, j] + L by [i, j]. We were first introduced to the palette in Chapter 4, where visually speaking we think of the palette as the half-open parallelogram P spanned by \px, p2] and [qi, q2] and the colors are labelled by the A lattice points contained in P. See Figure 5.3 for an example of a set of six distinct coset representatives of the palette corresponding to [3,0] and [0, 2]. In Chapter 6, which contains a polynomial-time algorithm that constructs a Big Tile, we will benefit from knowing that for any arbitrary linearly independent [pi,p2] and [qx, q2] G Z 2 , we can always find a rectangular array of distinct coset representatives for Palette([px, p2], [qx, q2]). This important fact will ultimately make the coloring instructions for a Big Tile constructed with Palette(\pi p2], [qx, q2}) easy to specify. Lemma 5.2.2 (Rectangular Array of Distinct Coset Reps): Suppose \px,p2] and [qi-, ft] £ Z 2 are linearly independent, and let A = \pxq2 — p2qi\- Then a set of distinct coset representatives for Palette(\p\, p2], [qx, q2]) is given by {(i, j) : 0 < l< igcdfrU)!' 0 < j < |gcd(p2,^ 2)|}. Proof: Let m = lgcd{p2m)l and n' = |gcd(p 2 ,ft) | . By Proposition 3.3.7, \m\ is minimal such that [m, 0] G L and that n' is at most as large as the smallest verti-cal shift in Palette(\pi, p2], [qx, ft]). As such, all of the elements of Palette(\pi, P2], [qi, ft]) are contained (with repetitions) within the infinite vertical strip X = {[hj] • 0 < i < m, j G Z}. Now consider Y = : 0 < i < m, 0 < j < n'} and note that \Y\ = A. By the minimality of m, any pair of elements in a row or column of Y must be distinct. Now, if all coset representatives of Palette(\p\, 75 Pi], [<7i, Qi]) in Y are distinct, we are done. Otherwise, without loss of generality, assume that [0,0] and both represent the same coset in Palette([pi, p2], [91, q2]) for some ^ [0,0] in Y and with i minimal. Consider the parallelogram spanned by [m, 0] and Since n' is at most as large as the smallest vertical shift < \pi, p2], [qi, q2] >, we must have i ^ 0. For any [a, b] G Z 2 we have [a + m,b] = [a, b] and hence the half-open parallelogram spanned by [m, 0] and [0, j] represents the same set of cosets as the half-open parallelogram spanned by [m, 0] and [i, j]. In fact every point in Y is represented by some point in the paral-lelogram spanned by [m, 0] and [0, j]. In that case, by the minimality of i, no other coset representatives of Palette(\pi, p2], [qi, q2]) can be contained in X, which is a contradiction. We may conclude, then, that the elements of Y represent the A elements of Palette(\pi,p2], [<?i, q2]). | The author wishes to thank Joel Friedman for the inspiration for this elegant proof. Next we construct a colored tile for an Escher tile T whose period graph has only one connected component. The colored tile will consist of concatenated copies of T, sides abutting, whose motif pieces are colored by way of Palette(\pi, Pi], [<7i) 92]), and whose dimensions depend upon pi,p2, qi and q2. Definition 5.2.3 (colored tile): Let T = {(mi, 0 ,0) , . . . , (m*, 0,0)} be an Escher tile and assume GT, the period graph for T, is connected. Suppose [p\,p2] and [qi 1 92] G Z 2 are linearly independent, and let L =< \pi,p2], [91, 92] >• 1. Set A = \p1Q2 — p2qi\, m = , , , A — r r , andn = , , , A — r , . L f i ^ rzHL\> |gcd(p2,92)|' |gcd(pi,<7i)| 2. Let ST be an agglomerated spanning tree of GT, and gen(T, 0,0) = {(mi, 0, 0), (m 2 , «2, J2)) • • •, (wijb ik, jk)} a set of generating motif pieces obtained from the fat spanning tree ST-76 3. Define the coloring function CA. LetCA : Wall(T) -^-Palette(\pi, p2], [91,92]) by CA({ms, i, j)) := [-i8 + i,-js + j}. A colored tile for T parameterized by [pi, p2] [91,92] and denoted Cx([pi, p 2], [91,92]) set {{ms,i, j , C A ( ( m i , - z , + i , - j s + j')) : z G Z m , ; ' G Z n , s = 1,..., A;}, where the fourth entry assigns a color from Palette([pi, p2], [gi, g2]) to m s m location (i, j) by way of the coloring function CA. Visually, Cr([Pi,p 2 ], [91, <fe]) is a | g c d ( ^ g 2 ) | x | g c d ( ^ g i ) | rectangle with lower left unit subsquare centered at (0, 0), and sides parallel to the standard axes. Each unit subsquare centered at a lattice point contains a copy of T whose motif pieces are colored by the function CA. The work behind the scenes of the construction of a colored tile is this: we place a copy of m\ inside each unit subsquare centered at a lattice point contained in Palette([p\, p2], [91, 9 2]) and color each such copy of (mi,i,j) with the coset + L. A copy of mi in location is related to each of {(m 2 , i2 + 1J2 + j), • • •, (m*, k + hjk + j)}, and CA assigns color [i, j] + L to this particular set of motif pieces related to (mi, i, j). Note that the set {(mi,i,j), (7712,12 + «, J'2 + j), • ..,(mk,ik + i,jk + j)} is simply gen(T,i,j) or alternatively, is the set gen(T, 0,0) translated elementwise by the vector [i, j]. See Figures 5.4 and 5.6 for an example of an Escher tile T and six translated (and colored) copies of gen(T, 0,0) that are derived from the palette corresponding to [2,1] and [6,0]. The vector [2,1] is the natural periodicity of T and [6,0] is a collision-free vector for T. A Big Tile for T can be found in Figure 5.7. We are ready to prove that a Big Tile exists for an Escher tile whose period graph has one connected component. Theorem 5.2.4 (Big Tile for Escher tile with Connected Period Graph): Let T = {(mi, 0,0), (m 2,0,0), . . . , (mk, 0,0)} be an arbitrary Escher tile whose pe-riod graph GT is connected. Then there exists a Big Tile for T. 11 Proof: The Escher tile T is trivially, singly, or doubly periodic. By Proposition 5.1.8, there exists a color-safe lattice for T in all three cases. Suppose one such is < \pi,p2], [91,92] >• Let C T = C T ( [ P I , p2], [91,92]) be the colored tile for T colored by Palette(\pi, p2], [91, 92]). We claim that CT is a Big Tile for T. In order to verify the claim, by Lemma 2.2.9 it suffices to show 1. C A ( M ) = CA{N) for every M,N G W((mi, 0, 0)), in which case we write CA(W((mi, 0,0)) to mean the one color from Palette(\pi, p2], [qi, q2]) that is assigned to every motif piece in W((mi, 0,0)), and 2. if CA(W((mu 0,0)) = CA(W((mu i,j)), therxWiirri!,0,0)) mdW((mu i, j)) do not overlap. Part 1: The wallpaper components are uniformly colored by construction because by Lemma 3.3.7 the rectangular lattice < [j^ dT^plT)! > 0],[0, lattice of < [px, p2], [qx, q2] >. That is, the coloring of Wall(T) assigned by way of the cosets of < [pi,p 2], [91,92] > is inherited by any sublattice of L. Part 2: Suppose ^ ( ^ ( f m i , 0, 0))) = C A ( W ( ( 7 7 7 , I , i , j))). By the construction of CT the colored tile generated by [px, p2] and [91,92], we know that [i, j] G < [px, p2], [9i, 92] >• In that case i = xp\ + yqx and j = xp2 + yq2 for some x, y G Z . Without loss of generality assume that at least one of \pi,p2] or [91,92] is a collision-free vector for T (if both are natural periodicities then W((m\, 0,0)) = W({rn\, i, j)), which has been disallowed). Suppose [pi,p2] is not a natural period and [91,92] is a natural period. Then W((mi,i,j)) — W((mi,xpi + yq\,xp2 + yp2)) = W((m-i, xpi, xp2)). By Corollary 5.1.7, since [xpi,xp2] G L, W((rrii, 0,0)) does not overlap W((m\, xpx,xp2)). Hence, wallpaper components that are colored the same do not overlap. | At last we have the means to prove that a Big Tile exists for any Escher tile. 78 Theorem 5.2.5 (Big Tile for Arbitrary Escher tile): Let T be an Escher tile. Then there exists a Big Tile for T. Proof: Let GT be the period graph for T and suppose GT has N connected com-ponents. Consider the N Escher tiles induced by the connected components GT (see Definition 3.1.3): Tu T2, ..., TN. By Theorem 5.2.4, there is a Big Tile for Ti for i = 1, . . . , N. Let BTi = B^i^i, rrii, ni) be a Aj-colored rrii x n>i Big Tile for T{. For each use a new set of colors; being wasteful is not relevant for showing existence. Let m = l cm(mi , . . . , mN) and n = lcm (n i , . . . , nN). A Big Tile for T, then, consists of the concatenation of — x — copies of Birp inside an mxn rectangular region for i = 1,..., N. The number of colors used will be Now that we know that a Big Tile exists for any Escher tile, we have two tasks ahead of us. First we describe an algorithm called ColorFast, that constructs a Big Tile for an Escher tile whose period graph is connected (which easily extends to any Escher tile). The algorithm will be linear in the total number of intersec-tions of motif pieces along the boundary of 5*0,0, the unit square in which T is located. Our last task, at least for purposes of this thesis, is to make a connection between irreducible Big Tiles and positive definite binary quadratic forms with inte-ger coefficients. We view the Big Tile constructed in the proof of Theorem 5.2.4 as canonical, and it is the canonical Big Tiles for which we will make the connection to binary quadratic forms. 79 Figure 5.1: Motif pieces that intersect elements of gen(T, 0,0) for the Escher tile in Figure 3.9 80 Figure 5.2: Overlap graph for the Escher tile in Figure 3.9 0,1 1,1 2,1 0,0 1,0 2,0 Figure 5.3: Palette associated with [3,0] and [0,2] 8 1 Figure 5.4: A singly periodic Escher tile with natural period [2,1 Figure 5.5: A palette Figure 5.6: Set of colored motif pieces that serve as generators for a colored tile: the palette and coloring function C A are extracted from vectors [2,1] and [6,0] 82 Figure 5.7: A 6-colored Big Tile for the Escher tile in Figure 5.4 83 Chapter 6 Efficient Big Tile Construction: The ColorFast Algorithm The purpose of this Chapter is to describe a general polynomial-time algorithm, ColorFast, to construct a Big Tile for an Escher tile T whose period graph is con-nected. For the most part, ColorFast was used in the detailed example given in Section 4 and we will formalize that procedure with a few speedups along the way. Abstractly, an Escher tile is specified by T — {(mi, 0 ,0) , . . . , (mk, 0,0)}, where (rrii, 0, 0) is a connected subset of S0t0 f ° r * = 1, • • •, the pairwise inter-section of the k motif pieces, and the set of intersections of each piece with dSo$ are given. The latter is assumed to be pre-sorted. For an implementation, one need only assume that each motif piece is a finite (connected) union of polygons. For the purpose of constructing a Big Tile for T, we only need to specify how many motif pieces there are, which pairs intersect, and the finite sorted set of boundary intersec-tions for each. With that information, ColorFast will return the dimensions of a Big Tile, BT, together with a finite set COLORS of colors, and a function that takes a motif piece in BT as input and returns an element of COLORS to assign to that motif piece. In the end, it is up to the artist to design the Escher tile and construct 84 the Big Tile, although the latter task could be delegated to, say, a tile company. Most of the procedures that are called in the ColorFast algorithm will be fa-miliar, but we give a brief description and the runtime for each. Let n = max(k2,I), where / is the total number of intersections of motif pieces of Escher tile T with dSQfi. • An Escher tile is input as T = {motifpieces,overlaps,boundaryintersections}, where overlaps has information containing the pairwise intersection of ele-ments of motifpieces and boundaryintersections contains for the bottom, top, right, and left sides, as well as NW, SE, NE, SW corners, a pre-sorted list of motif piece intersections along dS0,o-• PeriodGraph stores vertices (one for each motif piece in T) and directed edges. The directed edges can be obtained by comparing elements boundary-intersections in 0(n) time since boundaryintersections is presorted. Once this step has been accomplished we remove any multiple edges that contain the same vector label. Thus, the period graph will have 0(k2) edges. • AgglomeratedPeriodGraph can be obtained in 0(k2) time by suppressing information (namely the vector labels and edge directions and multiplicities) contained in PeriodGraph. • AgglomeratedSpanningTree can be obtained in 0(k2) time by using a breadth first search tree [CLR89]. • FatSpanningTree takes as input a spanning tree of the agglomerated period graph GT and reinstates the multiple edges, directions, and vector labels from the period graph GT- This can be done in 0(k2) time. • GeneratingMotifPieces extracts, in 0(k) time, a location for each motif piece, from the fat spanning tree. 85 RemovedEdges takes as input the agglomerated period graph GT and an agglomerated spanning tree ST, and returns the edges that were removed from GT when ST was constructed. That is, RemovedEdges(GT, ST) = E(GT) \ E(ST)- This can be done in 0(k2) time. FatRemovedEdges is E(GT) \ E(ST) and can be found in 0(k2) time by reinstating information in RemovedEdges. GhostMotifPieces is a list of 0(k2) edges and each endpoint produces a location relative to a related generating motif piece. This can be done in 0(k2) time. GhostVectors finds all ghost vectors by comparing locations of each gener-ating motif piece with the location of its potential ghost, by way of RT and ST, which takes time 0(k2). NaturalPeriods returns the natural period(s) of T (if there are any). If T is singly periodic, the greatest common divisor of 0(k2) scalars that are bounded by O(k) must be computed (see Definition 3.3.2 and Lemma 3.2.7). If T is doubly periodic, find a basis of subspace of 1? spanned by the ghost vectors of T. If T is trivially periodic, NaturalPeriods returns the empty set. In the worst case, this step takes time O(k)2 [Co95]. Palette. By Lemma 5.2.2, a set of distinct coset representatives for the lattice < [Pi.Pa], [91,92] > is reps := {[i,j] : 0 < i < \scd£2,g2)l 0 < J < |gcd(p2, 92)|}, where A = \pxq2 - p2qi\. The call to Palette([pi,p2], [91, 92]) will return reps, which by Proposition 5.1.8 has size 0(k2). ColorSafeLattice returns two vectors. If T is singly periodic with natural pe-riod [pi,p 2], ColorSafeLattice returns {[pi,p 2], [2k+3,0]} ifp2 ^ 0 or returns 86 {[Pi) P2], [0, 2k + 3]} if P2 = 0. If T is trivially periodic, ColorSafeLattice re-turns {[2fc + 3,0], [0,2k + 3]}. By Proposition 5.1.8, ColorSafeLattice returns a color-safe lattice. This step can be done in time 0(k2). • BigTilelnstructions simply returns two positive integers m and n and a set of verbal instructions for the color to be assigned to each (mt, a, b) e BT-Specifically, if periods = {[pi, P2], [<?i, 92]} then _ |Plg2 — P2gl I |gcd(p2,92)| and \PlQ2 - P 2 9 1 I 77, =Z . |gcd(pi,gi)| ' By Lemma 3.2.7, this step takes at most 0(\g(k)) steps since \pi\, \p2\, \qi\, and |g 2 | are bounded by 0(k) [CLR89]. The verbal instructions are as follows. Motif piece (mt, a, b) is colored the same as (mi, a — it,b — jt) (where (mt, it, jt) e gen(T, 0,0)). Therefore, the color assigned to (mi, a — it,b — jt) is (i1, j') where - f = b- jt (mod p2) with, say, b-jt = qp2 + j' and 0 < f < p2, and - i' = (a — it — qpi) (mod m). In other words, given an arbitrary motif piece (mt, a, b) e Wall(T), first we find a translate of (mi, 0,0) that is related to (m t , a, b) by way of (mt, it, jt) € gen(T,0,0). That is, ( m b a — it,b — jt) is related to (mtra,b). Next we use the Euclidean Algorithm to find a quotient q and remainder j' such that b — jt = qp2 + j', where by Definition 3.3.6, we have j' is the height of W((mu a, b)). Finally, it remains to specify the location of the copy of mi that belongs to W((mt, a, b)) whose y— coordinate is j'. This location 87 is simply ((a — it — qpi) (mod m), b - jt - qP2)- In surnmary, (mt, a, 6) is colored ((a — it — qpi) (mod m), b — jt — qp2). We present the ColorFast algorithm next: Algorithm ColorFast(T) Initialization • input T = {motifpieces, overlaps, boundaryintersections} Procedure 1. GT <— PeriodGraph(mota/pieces, boundaryintersections) 2. GT <— AgglomeratedPeriodGraph(Gx) 3. ST <- SpanningTree(GT) 4. ST <- FatSpanningTree(S'r) 5. generators GeneratingMotifPieces(Sr) 6. i2y RemovedEdges (GT, ST) 7. fatremovededges <— FatRemovedEdges^x) 8. ghosts •<— GhostMotifPieces(generators, fatremovededges) 9. ghostvectors <— GhostVectors(ghosts, generators) 10. periods <— Na,tuia\Periods(ghostvectors, generators) 11. if length(periods) = 2 (a) colors <— Palette(periods) 88 (b) return BigTileInstructions(colors, generators) 12. else if length(periods) = 1 (a) colors <— Pdlette(periodsU[2k + 3, 0]) or Palette (periodsU [0, 2k + 3]) (b) return BigTileInstructions(colors, generators) 13. else (a) colors «- Palette([2A; + 1,0], [0, 2k + 3]) (b) return BigTileInstructions(colors, generators) 14. end In summary, the most costly part of ColorFast is the construction of the period graph which, in the worst case, takes 0(n) steps. A l l of the work following the construction takes at most 0(k2) steps. Therefore, we have shown Theorem 6.0.6 (ColorFast is a Polynomial-Time Algorithm): LetT — {(mi ,0,0), (m 2 , 0,0), . . . , (mk, 0,0)} be an Escher tile whose period graph GT is connected. Let I be the total number of intersections of motif pieces in T with dSo,o- Let n = max(k2,1), where k is the number of motif pieces in T. The algorithm Color-Fast takes time 0(n). 89 Chapter 7 Toward a Classification 7.1 Irreducible and Reducible Big Tiles To some extent, the Big Tiles constructed in Section 5.1 are canonical, by which we mean that given an arbitrary A-colored Big Tile for Escher tile T whose period graph is connected, we can always find a ^-colored Big Tile for T that exhibits the same structure as the Big Tiles constructed in Chapter 5.1 and with 5 < A . This observation suggests the next definition, that of an irreducible Big Tile; we will adopt irreducible Big Tiles as our canonical representation. Definition 7.1.1 (Irreducible and Reducible Big Tiles): Let T be an Escher tile and BT a A-colored m x n Big Tile for T and let CA((ms,i, j)) denote the color assigned to motif piece (ms, The Big Tile BT is said to be irreducible if 1. forevery(ms,i1,j1),(ms,i2,J2) G BT, whenever CA{(ms, iu = C A ( ( m s , «2J 32)), \h - i2\ < m and \jx - j2\ < n then [ix - i2,jx - j2] is an integer linear combination of natural periods ofT, and 2. CA((rna,ii,ji)) / CA({ms,i2,j2) if either ii = i2 or ji = j2for allix,i2 G Z m andji,j2 G Znforall s = 1,..., k. 90 Otherwise, BT is said to be reducible. Thus , an irreducible B i g T i l e is one in wh ich the same co lor ing of a mo-tif piece does not occur in any row or any co lumn . In particular, i f T is t r iv ia l ly periodic, by Def in i t ion 7.1.1 every occurrence o f mot i f piece ras in an irreducible B i g T i l e for T is assigned a different color. Figures 2.12, 2.13, 4 .11, and 4.12 are examples of irreducible B i g Ti les . See Figure 7.2 for an example a reducible B i g T i l e for the Escher tile in Figure 7.1. Figure 7.1: An Escher tile Figure 7.2: A reducible Big Tile for the Escher tile in Figure 7.1 Definition 7.1.2 (Lattice-Encoded Big Tile): Let T be an Escher tile whose pe-riod graph is connected and BT = Br(A, ra, n) a A-colored mxn Big Tile for T. 91 The lattice < [pi, p2\, [qi, 92] > £ Z 2 encodes BT ifBr is equivalent to the colored tile generated by Palette(\pi, p2], [qi, q2]) andT. Lemma 7.1.3 (Irreducible Big Tile is Encoded by a Lattice): LetT = {(mi ,0,0), ..., (rrik ,0,0)} be an Escher tile whose period graph is connected and suppose and BT := £ x ( A , m, n) is an irreducible Big Tile for T. Then there exists a lattice that encodes BT-Proof: Let a set of generating motif pieces for T be given by gen(T, 0,0) = {(mi, 0,0), (m2,12,32), {mk,ik,jk)}-Case 1: Suppose T is trivially periodic. We claim that the lattice L =< [m, 0], [0,n] > encodes BT. By Definition 7.1.1, every translate of (mi, 0,0) in BT is colored with a different color so that a palette is given by the cosets of L. Since the period graph is connected, all motif pieces in BT must be colored with some color from Palette([m, 0], [0,n]). Thus, A = mn. Moreover, the locations of all motif pieces mi that are colored with [0,0] must be {(xm, yn) : x, y G Z}. In general, because the period graph is connected, an arbitrary (m s , i, j) G BT is colored [i — h,j — js] (because (ms,i,j) is related to (mx,i — is,j — js), which is colored [i — h,j — js]- Trivially, the dimensions of BT satisfy m = | c^o n)| a n ( * n = | g c d ^ Q ) | . Thus, BT is the colored tile generated by Palette([m, 0], [0, n]) and T. Case 2: Suppose T is singly periodic with natural period [pi,p2] and for now as-sume p2 ^ 0. We claim that BT is the colored tile generated by < [pi, p2], [m, 0] > andT. First we show that A = \p2m\: let (mi,i,j) G Wall(T) be arbitrary and colored c. By Definitions 7.1.1 and 2.2.10, 3i,j such that 0 < i < m, 0 < j < p2, and (mi,i,j) is colored c. That is, without loss of generality we can assume j is the height of W((mi, i,j)) and since BT is a Big Tile of width m, we can use j (mod m). Because UMe9en(T,o,o) M is a connected subset of R2, the remaining 92 motif pieces in Wall(T) must be colored from the same set of colors. In that case, we see that A < mp2- Moreover, by Definition 7.1.1, if 0 < «i, «2 < m and 0 < Ji,J2 < P2 and ( m i , i i , j i ) and ( m 1 , i 2 , j2) are colored the same, then [i± — hji - 32] = [koPi, k0p2] for some k0 £ Z . Since 0 < ji,j2 < p2 we have k0 = 0, which means ix = i2 and ji = j2. In particular, A > p2m and thus altogether A = \p2m\. What can we say about the value of n? The previous argument shows that we can label the colors of BT with the A = \mp2\ cosets of the lattice < [m, 0], [^1,^2] >• By Definition 7.1.1 for 0 < j < n, we know that (mi, 0, j) can-not be colored [0,0]. Our argument so far has shown that the set of all locations of mi that are colored [0, 0] is given by {(xpi + ym, yp2) : x, y e Z} . Thus, |n| must be minimal (and nonzero) such that 0 m pi = X + y n 0 P2 or equivalently, -X 1 P2 -Pi 0 . y . p2m 0 m n —pin , mn n => x = r and y = , r = - j— \p2m\ \p2m\ \p2\ By the proof of Lemma 3.3.7, n = j ^ ^ . Trivially, we have m = We conclude that BT, in this case, is the colored tile generated by Palette([pi, p2], [m, 0]), and hence by Definition 7.1.2 is encoded by the lattice < [pi, P2], [m, 0] >. Case 3: Suppose T is doubly periodic with natural periods [pi,p2J and [ft, ft]- We claim that BT is encoded by the lattice L =< \pi,p2], [ft, ft] >. Since T is doubly 93 periodic, by Definition 2.2.7, the wallpaper pattern WalliT) contains only finitely many wallpaper components, one for each of the \p\q2 — P2Qi\ cosets of L. Let (mi,hj) £ WalliT) be arbitrary and suppose (mi,i,j) is colored c. Then for any € L we have (mi, i,j) is colored c because (mi, i,j) is related to (mi, i,j). Moreover, if W((mi,0,0)) and W((mi,o,6)) are distinct (i.e., [a, b] g" L), then W((mi , 0,0)) overlaps W((m1: a, b)). Thus, all of the wallpaper components must be colored with \pxq2 — P2Qi \ different colors and so we label each with a coset of L. So far, we have shown that A = \piq2 — p2q\ | and that the colors can be labelled with cosets. It remains to show that m and n satisfy the requirements of Definition 5.2.3. But by assumption, BT is irreducible and hence m and n must be minimal such that m Pi + yi Qi 0 P2 Q2 and 0 Pi + Z/2 Qi = x2 n P2 Q2 for some X\,y\,x2, y2 £ Z.The proof of Lemma 3.3.7 yields m = |gCd(p2 Q2)\ and n = | g c d ^ Thus, BT, in this case, is the colored tile generated by Palette([pi, P2], [Qi, Q2]) and T, and hence BT is encoded by the lattice < [pi,;?2], [<Zi, Q2] >, as desired. | In fact, the lattice that encodes an irreducible Big Tile is unique. Corollary 7.1.4 (The Lattice that Encodes a Big Tile is Unique): Let T be a doubly periodic Escher tile whose period graph is connected and suppose L = < \pijP2}, [91,92] > encodes an irreducible Big Tile B r ( A , m , n). If L' = < [ri ,r 2 ] , [si, s2] > is another lattice that encodes BT- Then V = L. 94 Proof: By Definitions 7.1.2 and 5.2.3 and the proof of Lemma 7.1.3, we have \rxS2 — r2Si \ = A and that [m, 0], [0, n] e L and [ra, 0], [0, n] € V. Hence, L = V, as desired. | Finally, the following corollary is a direct consequence of Lemma 7.1.3. Corollary 7.1.5 (Doubly Periodic Escher tile: Unique Big Tile): Let T be an Escher tile whose period graph is connected. Then the Big Tile for T is unique and irreducible. 7.2 Irreducible Big Tiles as Tools 7.2.1 In Search of the Chromatic Number of T By Theorem 5.2.5, given any Escher tile T, there exists a Big Tile for T. Hence, it makes sense to define the chromatic number of T. Definition 7.2.1 (Chromatic Number of an Escher tile): Let T be an arbitrary Escher tile and B = { A i , A2, • • •, } be the set of all positive integers Afar which there exists a A-colored Big Tile for T and without loss of generality assume A , < A i + 1 whenever \B\ > 1 and A j , Ai+X G B. By Theorem 5.2.5, B is nonempty. The chromatic number of T, denoted x(T), is given by x(T) = Ax. That is, the chromatic number of an Escher tile is the smallest (positive) integer A for which there exists a A-colored Big Tile for T. For example, three is the chromatic number of the Escher tile in Figure 2.10; an irreducible Big Tile for this coloring is in Figure 2.12. Irreducible Big Tiles were useful in the existence theorems in Chapter 5.1 (Theorems 5.2.4 and 5.2.5), and now will prove useful as a tool to investigate some special cases of Escher tiles for which we can actually compute x(T). First we prove that when in search of 95 x{T) we need look no further than the collection of irreducible Big Tiles for T. By Corollary 7.1.5, all Escher tiles for which the period graph is connected and doubly periodic have a unique Big Tile, which up to concatenation, is irreducible. In fact we can find the unique lattice that encodes the one irreducible Big Tile for T and thus, in this special case we can compute xCO- As a next natural step in an analysis of the chromatic number, we analyze Escher tiles whose period graphs are connected and either trivially or singly periodic. The end result will be that a reducible A— colored Big Tile for T leads to an irreducible 5— colored Big Tile for T where 5 < A . In other words, when searching for x(T) for such an Escher tile, we need look no further than the collection of irreducible Big Tiles for T. Lemma 7.2.2 (Reducible BT(A,m,n) ->• Irreducible BT(5 < A ,m ' ,n ' ) ) : Let T be an Escher tile with connected period graph that is either trivially or singly periodic and suppose B?(A, m, n) is a reducible Big Tile for T. Then there exists an irreducible Big Tile for T, BT(<5, m', n') such that 8 < A. Proof: Case 1: Let T be trivially periodic and suppose 0 < ii,i2 < m, 0 < * 2 , J 2 < n, ^ (12,32), and ( m i , i i , and (mi,i 2,j 2) are colored with the same color (since BT(A, m, n) is reducible, such a pair must exist). Suppose ii — i2 = pi and ji — j2 = p2. Without loss of generality (by using an appropriate vector translation and by periodicity) we may assume (mi, 0,0) and (mi,pi,p2) with 0 < pi < m and 0 < p2 < n are colored the same. Among all motif pieces colored the same as (mi, 0,0) within BT(A, m, n), choose pi to be minimal and positive (otherwise do the same for p2). Then the set of lattice points within the parallelogram spanned by [0,n] and [^ 1,^ 2] contain copies of m x all colored with distinct colors by the minimality of p i . Thus, A > pin. (If it so happens that pi = 0 simply re-run the argument with a minimal p2 and use the parallelogram spanned by [pi,2>2] and [m, 0] concluding that A > p2m.) Now construct an irreducible Big 96 Tile for T using Palette ([pi,p2], [0, n]). The resulting Big Tile requires |pin| colors and has area b H _ bil" 2 |gcd(n,p2)| |gcd(pi,0)| |gcd(n,p2)|" Case 2: Suppose T is singly periodic with natural period [pi,p2]. If the copies of m\ located at lattice points contained in the half-open parallelogram spanned by [0, n] and [pi,p2] (or use [m, 0] if it so happens that p2 = 0) are all colored with different colors then A > |mp 2| in which case simply construct the irreducible Big Tile BT(\mp2l , Jf,1"' . fr"',,), which has area , fc1"' „ , If,1"' = , 1 W |gcd(n,p2)|' |gcd(pi,0)| ^' |gcd(n,p2)| |gcd(pi,0)| |gcd(n,p2)|' just as in the previous case. Otherwise, without loss of generality (using a shift if necessary) there is some translate of mi, say (mi, qi,q2), contained in the half-open parallelogram spanned by [pi,p2] and [0, n] that is colored the same as (m 1 ; 0, 0). Among all such (mi, qi, q2) choose 1^1 to be minimal. Then the translates of mi contained in parallelogram spanned by [pi, p2] and [qx, q2] are colored with different colors, which means that A > \p\q2 — p2q\\. In that case simply construct an irreducible |pi^ 2 — p2qx\ —colored Big Tile for T with Palette(\pi, p2], [qx, q2}). I The good news is that in any attempt to determine x{T) it suffices to study only the irreducible Big Tiles for T. The bad news is that there is no guarantee that extracting an irreducible Big Tile from a reducible one will yield an irreducible Big Tile that is smaller in area than the reducible one. Finally, by Lemma 5.1.8 and Lemma 7.2.2 we can give an upper bound for X(T). Theorem 7.2.3 (Upper Bound for x(T)): Let T = {mu 0,0), . . . , (mk, 0,0)} be an Escher tile whose period graph has N connected components. Then x{T) < N{2k + 3)2. Proof: Suppose the period graph of T has Af connected components and let 7\ , . . . , TN be the Escher tiles induced by each component (Definition 3.1.3). By Proposi-97 tion 5.1.8, for each Tj there is an irreducible Big Tile for Tj that requires at most (2k + 3) 2 colors. Since there are JV components, and by the construction given in Theorem 5.2.5, there is a Big Tile for T that requires at most N(2k + 3) 2 colors. I We can do somewhat better for an Escher tile whose period graph is con-nected and doubly periodic: we can compute the chromatic number exactly. Theorem 7.2.4 (Chromatic Number of Doubly Periodic Escher tile): Suppose T is an Escher tile whose period graph is connected, and let [ p i , p2] and [qx, q2] be natural periods for T. Then\{T) = \piq2 — p2qi\. Proof: Since T is doubly periodic, the Big Tile is unique and irreducible by Corol-lary 7.1.5. Thus, x(T) = \piq2 - p2qx|. | 7.2.2 In Search of Inequivalent A-Colored Big Tiles By Lemma 7.1.2 and Corollary 7.1.4, an irreducible Big Tile for Escher tile T cor-responds to a unique lattice. Say this lattice can be generated by u = [ux,u2 and v = [vi, v2 u • u u • V u • V V • V Consider the Gram Matrix [Co95, Va91] of u and v, namely The Binary Quadratic Form (herein referred to as BQF) that we associate with BT is f(x,y) := [x,y] ward calculation shows that u u u v X u v v V y . A straightfor-f(x, y) = (u\ + u\)x2 + 2(ulVl + u2v2)xy + (v\ + v22)y2 (7.1) The discriminant of an arbitrary BQF ax2 + bxy + cy2 is given by b2 - Aac. If we let A = uxv2 — u2vx, then the discriminant of / in equation 7.1 is —4A 2 . 98 Let BT be an irreducible Big Tile for Escher tile T whose period graph is connected. We will make a connection between irreducible A-colored Big Tiles for T and BQFs with integer coefficients of discriminant —4A 2 . In particular, we wonder under what circumstances we can find two or more irreducible A -colored Big Tiles for T. That would entail finding two color-safe lattices L = < [Pi,P2].[?i,92] > and V = < [p[,p'2Wi,q2] > f o r T s u c h t h a t P1Q2 - P2<7i = P1Q2 ~ P2Q1 but for which L ^ V. It is well understood in the realm of Analytic Number Theory (see for example [Ap76]) under what circumstances two lattices are equivalent, and we mention briefly how the mechanics work. To do so, we need a definition for the modular group, and an understanding of a particular group action of the modular group on the set of BQFs of a fixed discriminant. Definition 7.2.5 (Modular Group): The modular group T(l) is r ( i ) := a j3 7 6 : a, f3,7,6 € Z and aS — ^ 7 = 1 (7.2) That is, the modular group is the set of all 2 x 2 matrices with integer entries and determinant 1. It is not hard to see that T(l) is a group under matrix multiplication. Next we define an action of T(l) on the set of BQFs with integer coefficients and of discriminant D. In particular, let f(x, y) = ax2 + bxy + cy2, suppose b2 - 4ac = D, and say that a B 7 S Then the action of M on / is given by M e r ( i ) . f\M := f(ax + Py,^x + 5y) a(ax + f3y)2 + b(ax + (3y)((3x + 73/) + c(^x + 6y)' 99 = (aa2 + baj + c^2)x2 + (2aa(j + b(a5 + £7) + 2cy5)xy + (a/32 + b(38 + cd2)y2. We see that f\M is a BQF with integer coefficients. Moreover, if we let A = (aa2 + kry + C 7 2 ) , B = (2aa/3 + b(a8 + /37) + 2c7<5), and C = (aft2 + b/35 + c52), then the discriminant of f\M is 5 2 - 4AC = (a6 - h)2(b2 - Aac) = D since aS — ^ 7 = 1 and 62 — 4ac = D. So, the described action of T(l) on the set of BQFs of discriminant D is indeed a group action [GaOl]. What will be of use to us is that under the group action so described, the number of orbits is finite. Specifically [Bu89], Theorem 7.2.6 (Finitely Many Orbits): Let BQFD be the set of all binary quadratic forms with integer coefficients of discriminant D < 0. Then the number of orbits of BQFD under the action o /T(l) is finite. In particular, Definition 7.2.7 (Class Number): Let BQFD be the set of all binary quadratic forms with integer coefficients of discriminant D < 0. The number of orbits of BQFD under the action o /T( l ) is called the class number of D, and denoted h(D). In our situation, we make a connection between irreducible A-colored Big Tiles BT with the set BQF_iA2 as follows. We have 1. an Escher tile T whose period graph is connected, 2. an irreducible A-colored Big Tile BT for T, 100 3. the unique lattice L generated by [p\,p2] and [qi, q2] that encodes BT (satis-fying \piq2 - p2qx \ = A) , and 4. a BQF of discriminant —4A 2 to associate with BT, namely (p\ + p\)x2 + 2(pi9i + Vi<h)xy + (q\ + q2)y2 by way of the Gram Matrix for \p\,p2] and Again, from [Ap76] we have Theorem 7.2.8 (Equivalence of Lattices): Two integer lattices L = < [pi,P2].[9i, q2] > and V = < [Pi,P2],[Qi, Q2] > are equivalent (meaning L = V) if and only if there exists 7 5 €T(1) such that a (3 Pi Qi ' P'l Q'i' 7 5 P2 92 P2 92 Inescapably, we are led to a method of differentiating between irreducible A-colored Big Tiles. Definition 7.2.9 (Inequivalent A-Colored Big Tiles): Let T be an Escher tile whose period graph is connected and suppose BT and B'T are both irreducible A-colored Big Tiles for T and encoded by lattices L and L' respectively. Then BT is equivalent to B'T if and only if L is equivalent to V. Alternatively BT is inequivalent to B'T if and only ifL is inequivalent to L'. The following theorem is a direct consequence of Theorem 7.2.8, the nature of the correspondence between a A-colored irreducible BT and B Q F _ i A 2 , and Definition 7.2.9. 101 Theorem 7.2.10 (Inequivalent A-Colored Big Tiles): Let T be an Escher tile whose period graph is connected and suppose BT and B ' T are both irreducible A-colored Big Tiles for T. If BT is inequivalent to B ' T , then h(—4A2) > 1. In fact, the two inequivalent and irreducible 8-colored Big Tiles in the example in Chapter 4 were constructed from the two inequivalent color-safe lattices 2 3 and 2 - 4 - 2 1 - 2 0 where [2, —2] where the Escher tile T was singly periodic with natural period [2, —2] and collision-free vectors [—4,0] and [3,1]. Faced with a particular D for which we want to compute h(D), brute force methods are adequate [Bu89]. On the other hand, general results are much harder to come by. So, for our purposes, we simply use the class number as a tool that provides a necessary condition on A that tells us that there is a possibility of more than one irreducible A-colored Big Tile for T. We end this chapter with one more theorem with thanks, again, to the class number. Theorem 7.2.11 (Finitely Many Inequivalent A-Colored Irreducible Big Tiles): Let T be an Escher tile whose period graph is connected, and let A be any positive integer. Then the number of inequivalent irreducible A-colored Big Tiles for T is finite and at most h(—4A2). 102 Chapter 8 Future Work 8.1 Generalizations The following is a sample of ideas for generalizing the methods in this thesis. 1. Ask and answer the Escher Big Tile question for regular-hexagon tilings in the Euclidean plane. 2. Ask and answer the Escher Big Tile question for equilateral-triangle tilings in the Euclidean plane. 3. Ask and answer the Escher Big Tile question for regular tilings of the hyper-bolic plane. 4. Replace the translation group Z x Z with another group (finitely generated and abelian? other wallpaper groups?) What can be asked and what can be answered? 5. The methods of this thesis should carry through to an analogue of the Big Tile existence question for 3-dimensional cubical tilings of R 3 . 103 8.2 Machinery Applied to Graph-Coloring and VLSI Design The machinery that we built for constructing Big Tiles may shed light on an open problem that lives among the areas computational geometry, VLSI design, and graph coloring. Problem: A rectangle visibility graph G (RVG) is a simple graph whose ver-tices are represented by nonoverlapping rectangles in the plane and whose sides are parallel to the x— and y—axes; two vertices are adjacent if and only if they have either a horizontal or a vertical visibility [HSV99]. Rectangle visibility graphs are thickness-two graphs: they can be decomposed into (at most) two planar graphs G\ and G2, such that V(G) = V(GX), V(G) = V(G2), E(G) = E(GX) (J E(G2), and E(Gx) f]E(G2) = 0. In general, a thickness-A; graph is a simple graph that can be decomposed into k planar layers. Finding the thickness of an arbitrary graph is of interest to VLSI designers since thickness may be viewed as a measure of the minimum number of layers required to design a computer chip whose network is given by G and such that no two wires cross. The maximum value of the chro-matic number of an arbitrary thickness-two graph is known to lie between 9 and 12 [Hu93, HR90, Ga80], and has an application to the testing of printed circuit boards [GJS76]. A complete graph on eight vertices, K8, has a representation as an RVG. No R V G that requires more than eight colors is known [HSV99]. Conjecture: Let G be an arbitrary RVG. Then x(G) < 8. It is not hard to show that the vertices of any R V G can be represented by rectangles 104 whose corners have integer coordinates. As such, perhaps a modification of the period graph will be a tool that can be used to prove the conjecture. The edges will be weighted with vectors that have integer entries and contain information about type of visibility (horizontal or vertical, to the left of or to the right of etc), and the shortest distance between two vertices: the present best guess is that the vectors will live in Z 4 . 105 Bibliography [Ap76] Tom M . Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976. [Be66] Robert Berger, The undecidability of the domino problem, Memoirs of the A M S , 66(1966), 72pp. [Bu89] Duncan A. Buell, Binary Quadratic Forms: Classical Theory and Modern Computations, Springer-Verlag, 1989. [Co86] Daniel I.A. Cohen, Introduction to Computer Theory, Wiley, 1986. [Co95] Henri Cohen, A Course in Computational Number Theory, Springer-Verlag, 1995. [CLR89] Thomas H . Cormen, Charles E. Leiserson, and Ronald L . Rivest, In-troduction to Algorithms, McGraw Hil l , 1989. [Da97] Dan Davis, On a tiling scheme from M. C. Escher, The Electronic Jour-nal of Combinatorics, v. 4, no. 2(1997) #R23. [Er76] Bruno Ernst, The Magic Mirror of M.C. Escher, Ballantine Books, 1976. 106 [Es86] George A. Escher, Potato Printing, A Game for Winter Evenings, M. C. Escher: Art and Science, H.S.M. Coxeter, M . Emmer, R. Penrose, M . Teuber, eds. Amsterdam: North Holland, 1986, 9-11. [GaOl] Joseph A. Gallian, Contemporary Abstract Algebra, 5th ed., Houghten Mifflin, 2001. [Ga80] Martin Gardner, Mathematical Games, Scientific American, 242(1980), 14-19. [GJ79] Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman & Co, 1979. [GJS76] Michael R. Garey, David S. Johnson, and H.C So, An application of graph coloring to printed circuit testing, IEEE Transactions: Circuits and Systems, CAS-23(1976), 591-599. [Ge02] Ellen Gethner, On a generalization of a combinatorial problem posed by M. C. Escher, to appear in Congressus Numerantium, 2002. [GS87] Branko Grunbaum and Geoffrey Shephard, Tilings and Patterns, Free-man & Co, 1987. [HR90] Nora Hartsfield and Gerhard Ringel, Pearls of Graph Theory, Aca-demic Press, 1990. [Ho79] Douglas Hofstadter, Goedel, Escher, Bach: An Eternal Golden Braid, Basic Books, 1979. [Hu93] Joan P. Hutchinson, Coloring ordinary maps, maps of empires, and maps of the moon, Mathematics Magazine, 66(1993), 211-226. 107 [HSV99] Joan P. Hutchinson, Thomas Shermer, and Andrew Vince, On rep-resentations of some thickness-two graphs, Computational Geometry, Theory and Applications, 13(1999), 161-171. [KSOOa] Craig S. Kaplan and David H . Salesin, Escherization, Siggraph 2000, A C M Press / A C M SIGGRAPH / Addison Wesley Longman, 499-510. [KSOOb] Craig S. Kaplan and David H . Salesin, Escherization Website, www.cs.washington.edu/homes/csk/tile/escherization.html. [MWS96] Rick Mabry, Stan Wagon, and Doris Schattschneider, Automating Escher's combinatorial patterns, Mathematica in Education and Re-search, v. 5, no. 4(1996), 38-52. [Ma76] Caroline H . MacGillavry, Fantasy and Symmetry: The Periodic Draw-ings of M.C. Escher, Abrams, 1976. [MR01] Cristopher Moore and John Michael Robson, Hard Tiling Problems with Simple Tiles, Discrete and Computational Geometry 26(4) (2001) 573-590. [Pa94] Christos H. Papadimitriou, Computational Complexity, Addison Wes-ley, 1994. [Pe78] Roger Penrose, Pentaplexity, Eureka, 39(1978) 16-22. [Ro71] Raphael M . Robinson, Undecidability and nonperiodicity for tilings of the plane, Inventiones Mathematicae, 12 (1971), 177-209. [Sc90] Doris Schattschneider, Visions of Symmetry: Notebooks, Periodic Drawings, and Related Work of M.C. Escher, Freeman & Co, 1990, 44-52. 108 [Sc97] Doris Schattschneider, Escher's combinatorial patterns, The Elec-tronic Journal of Combinatorics, v. 4, no. 2(1997) #R17. [St81] Karl R. Stromberg, An Introduction to Classical Real Analysis, Wadsworth, 1981. [Sz98] Mario Szegedy, Algorithms to tile the infinite grid with finite clusters, Proceedings of the IEEE Symposium on Foundations of Computer Sci-ence, 137-147. [Va91] Brigitte Vallee, Gauss' Algorithm Revisited, Journal of Algorithms, 12 (1991), 556-572. [Wa99] Stan Wagon, Mathematica in Action, 2nd ed., Springer/Telos, 1999. [Wa74] Hao Wang, Notes on a class of tiling problems, Collection of articles dedicated to Andrzej Mostowski on his sixtieth birthday, VIII, Funda-menta Mathematicae, 82 (1974/75), 295-305. 109 Appendix A Art Gallery Over time we have learned to expect the unexpected. Figure A. 1 shows examples of two Big Tiles (the Escher tile can be found in any subsquare) for which an increase in area does not correspond to an increase in the number of colors needed. The Big Tile on the left has area 18 and requires six colors, whereas the Big Tile on the right has area 16 and requires eight colors. Figure A.2 shows an example of an Escher tile that at first glance seems to be composed of many unrelated motif pieces. Upon analyzing the overlap graph, we find that nearly all of the motif pieces are related, and that a Big Tile for T is l x l and requires only one color. A fragment of the Escher wallpaper is shown in Figure A.3. 110 Figure A. 1: Minimal area need not correspond to minimal coloring Figure A.2: A deceptive Escher tile 111 Figure A 3 : The deceptive tile unravelled 112 Figure A.5: Escher tile whose period graph is disconnected Figure A.6: Fragment of wallpaper pattern for the Escher tile in Figure A.5 113 Figure A.7: Another of Escher's designs 114 Index agglomerated period graph, 25 agglomerated removed edges, 26 Big Tile, 15 chromatic number of an Escher tile, 95 class number, 100 collision-free vector, 27 color-safe determinant, 71 color-safe lattice, 71 colored tile, 76 contiguous motif pieces, 11 doubly periodic, 36 E-vertices (overlap graph), 24 Escher tile, 9 Escher tile induced by a subgraph of the period graph, 24 fat removed edges, 26 fat spanning tree, 26 forbidden vectors and determinants, 69 generating motif pieces, 29 1 ghost motif piece, 30 height of singly periodic wallpaper com-ponent, 39 induced Escher tile, 24 inequivalent A-Colored Big Tiles, 101 inherent periodicities of a wallpaper pattern, 27 irreducible Big Tile, 90 lattice-encoded Big Tile, 91 location of motif piece, 11 modular group, 99 motif pieces induced by a trail in the period graph, 28 motifpiece, 9 natural period, 35 natural periods, 36 nontrivial circuit in the period graph, 29 overlap graph, 24 overlapping wallpaper components, 14 palette, 74 period graph, 23 puzzle pieces, 30 reducible Big Tile, 90 related motif pieces, 12 singly periodic, 35 trivial circuit in the period graph, 29 trivially periodic, 35 vector value of a trail in the period graph, 28 wallpaper component, 13 Wallpaper pattern, 10
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Computational aspects of Escher tilings
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Computational aspects of Escher tilings Gethner, Ellen 2002
pdf
Page Metadata
Item Metadata
Title | Computational aspects of Escher tilings |
Creator |
Gethner, Ellen |
Date Issued | 2002 |
Description | At the heart of the ideas of the work of Dutch graphic artist M.C. Escher is the idea of automation. We consider one such problem that was inspired by some of his earlier and lesser known work [MWS96, Sc90, Sc97, Er76, Es86]. From a finite set of (possibly overlapping) connected regions within a unit square (Figure 1), is it possible to make a prototile with concatenated and colored copies of the original square tile (Figure 2), such that the pattern in the plane arising from tiling with the prototile • uniformly colors connected components, and • distinctly colors overlapping components (Figure 3)? The answer is yes, that such a prototile exists for any (suitably defined) design confined to a unit square. We present a proof of existence and an efficient (and implementable) algorithm to construct prototiles. Moreover, in the existence proof, it will become apparent that a prototile for a given design may not be unique (up to concatenation). In such a situation, there are infinitely many "measurably different" prototiles. The secret of each design is encoded by either one or infinitely many (number theoretic) lattices; we will show how to extract all possible lattices by using techniques from graph theory and graph algorithms. Finally, from a certain point of view, the prototiles that we construct are canonical. We begin an analysis of the canonical prototiles by making a connection from lattices to binary quadratic forms to class number. |
Extent | 4696675 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-09-22 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
IsShownAt | 10.14288/1.0051682 |
URI | http://hdl.handle.net/2429/12987 |
Degree |
Doctor of Philosophy - PhD |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2002-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_2002-731677.pdf [ 4.48MB ]
- Metadata
- JSON: 831-1.0051682.json
- JSON-LD: 831-1.0051682-ld.json
- RDF/XML (Pretty): 831-1.0051682-rdf.xml
- RDF/JSON: 831-1.0051682-rdf.json
- Turtle: 831-1.0051682-turtle.txt
- N-Triples: 831-1.0051682-rdf-ntriples.txt
- Original Record: 831-1.0051682-source.json
- Full Text
- 831-1.0051682-fulltext.txt
- Citation
- 831-1.0051682.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051682/manifest