Open Questions in Aperiodic Tilings

University Of Arkansas, Fayetteville AR

Investigators

Abstract

Abstract Award: DMS-0072573 Principal Investigator: Chaim Goodman-Strauss For nearly 40 years, beginning with work by H. Wang and R. Berger, the undecidability of certain questions regarding tilings and aperiodic tilings have been studied. But as we extend our horizons and consider tilings in more general contexts than the Euclidean Plane, we see that many foundational questions are still open. In any particular, reasonably well-defined setting (e.g., "tilings in the hyperbolic plane by polygonal tiles, moved about by orientation-preserving isometries"), there are several intertwined questions that may be asked: 1) Is there a general method to determine whether a given set of prototiles admits a tiling that includes a specified configuration? (Is the "Completion Problem" decidable?; 2) Is there a general method to determine whether a given set of prototiles can tile the space at all? (Is the "Domino Problem" decidable?) 3) Is there a "weakly aperiodic" protoset? (Such a protoset admits no tiling with a compact fundamental domain.); 4) Is there a "strongly aperiodic" protoset? (Such a protoset admits no tiling that is invariant under an infinite-cyclic symmetry); 5) Is there a computable bound on the Heesch number of protosets?; Is there a computable bound on the isohedral number of protosets?; 7) Is the period problem decidable? We consider conjectures concerning some of these questions in two settings that have been thought about for 20 years: protosets in the hyperbolic plane and monotiles in the Euclidean plane; and we sketch a number of proposed approaches to these problems. We feel these techniques should generalize and shed light on many foundation al issues in discrete geometry. We hope the project will be significant in several ways. First, these problems, which have largely been seen as isolated from each other, can all be seen as tightly connected. It is anticipated that techniques will arise that will shed light on several aspects of this problem. But moreover, the techniques under consideration may link these questions in several topics in low-dimensional geometric topology and combinatorial algebra. Finally, questions of decidability and tractability are one of the central concerns of theoretical computer science; form one point of view, we are simply exploring a particular example, but hope that the techniques we develop will be of more general use.