The domino problem on groups of polynomial growth. ArXiv e-prints

ABSTRACT. We characterize the virtually nilpotent finitely generated groups (or, equiva-lently by Gromov’s theorem, groups of polynomial growth) for which the Domino Problem is decidable: These are the virtually free groups, i.e. finite groups, and those having Z as a subgroup of finite index. 1