The domino problem on groups of polynomial growth

Abstract

We conjecture that a finitely generated group has a decidable domino problem if and only if it is virtually free. We show this is true for all virtually nilpotent finitely generated groups (or, equivalently, groups of polynomial growth), and for all finitely generated groups whose center has a non-trivial, finitely generated and torsion-free subgroup.

Our proof uses a reduction of the undecidability of the domino problem on any such group $G$ to the undecidability of the domino problem on ${\mathbb{Z}}^2$, under the assumption that $G$ is not virtually free. This is achieved by first finding a thick end in $G$, and then relating the thick end to the existence of a certain structure, resembling a half-grid, by an extension of a result of Halin.