The symbolic dynamics of tiling the integers

A finite collectionP of finite sets tiles the integers iff the integers can be expressed as a disjoint union of translates of members ofP. We associate with such a tiling a doubly infinite sequence with entries fromP. The set of all such sequences is a sofic system, called a tiling system. We show that, up to powers of the shift, every shift of finite type can be realized as a tiling system.

Authors and Affiliations

1. Department of Mathematics, Wesleyan University, 06459-0128, Middletown, CT, USA

   Ethan M. Coven

2. Department of Mathematics, Indiana University-Purdue University at Indianapolis, 46202-3216, Indianapolis, IN, USA

   William Geller

3. Department of Mathematics, Hofstra University, 11549, Hempstead, NY, USA

   Sylvia Silberger

4. Department of Mathematics, University of California Davis, 95616, Davis, CA, USA

   William Thurston

Corresponding author

Correspondence to Ethan M. Coven.

Some of this work was done at the Mathematical Sciences Research Institute (MSRI), where research is supported in part by NSF grant DMS-9701755. The first two authors thank K. Schmidt for useful conversations and ideas.

Reprints and permissions