On the domino problem of the Baumslag-Solitar groups

Abstract

<p>In [1] we construct aperiodic tile sets on the Baumslag-Solitar groups BS(m, n). Aperiodicity plays a central role in the undecidability of the classical domino problem on Z2, and analogously to this we state as a corollary of the main construction that the Domino problem is undecidable on all Baumslag-Solitar groups. In the present work we elaborate on the claim and provide a full proof of this fact. We also provide details of another result reported in [1]: there are tiles that tile the Baumslag-Solitar group BS(m, n)but none of the valid tilings is recursive. The proofs are based on simulating piecewise affine functions by tiles on BS(m, n).<br></p>