A strongly aperiodic shift of finite type for the discrete Heisenberg group

Ayse A. Sahin, Michael Schraudner, Ilie Ugarcovici

Published 2020-09-16Version 1

We explicitly construct a strongly aperiodic subshift of finite type for the discrete Heisenberg group. Our example builds on the classical aperiodic tilings of the plane due to Raphael Robinson. Extending those tilings to the Heisenberg group by exploiting the group's structure and posing additional local rules to prune out remaining periodic behavior we maintain a rich projective subdynamics on $\mathbb Z^2$ cosets. In addition the obtained subshift is an almost 1-to-1 extension of a strongly aperiodic, minimal sofic shift. As a consequence of our construction we establish the undecidability of the emptiness as well as the extension problem for shifts of finite type on the Heisenberg group.