Let $T\neq \emptyset$ be a finite subset of $\mathbb{Z}\times\mathbb{Z}$. We say that $\mathbb{Z}^2 = \mathbb{Z}\times\mathbb{Z}$ is parquettable by $T$ if there is a partition $\frak P$ of $\mathbb{Z}^2$ such that for every $P\in {\frak P}$ there is a bijective linear map $\ell_P: \mathbb{Z}^2 \to \mathbb{Z}^2$ and an element $c_P\in \mathbb{Z}^2$ such that for the affine map $f_P:\mathbb{Z}^2\to\mathbb{Z}^2$ defined by $x\mapsto \ell_P(x) + c_P$ we have $$f_P(T) = P.$$

Given $T\subseteq \mathbb{Z}^2$, is it decidable whether $\mathbb{Z}^2$ is parquettable by $T$?

  • 6
    $\begingroup$ Just to restate: $T$ parquets $\mathbf{Z}^2$ if there's a partition of $\mathbf{Z}^2$ by affine translates of $T$. $\endgroup$
    – YCor
    Dec 1, 2022 at 18:35
  • 3
    $\begingroup$ The problem is at worst co-c.e., since having a tiling is equivalent to tiling arbitrarily large finite regions of the plane, and a failure of this can be discovered by a finite stage of searching. So we can answer No correctly in finite time. $\endgroup$ Dec 1, 2022 at 19:09
  • $\begingroup$ Right @YCor - that's the elegant & concise formulation. $\endgroup$ Dec 2, 2022 at 9:09


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy