2
$\begingroup$

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$?

Improve this question
$\endgroup$
3
  • 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
    Commented 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$
    – Joel David Hamkins
    Commented Dec 1, 2022 at 19:09
  • $\begingroup$ Right @YCor - that's the elegant & concise formulation. $\endgroup$
    – Dominic van der Zypen
    Commented Dec 2, 2022 at 9:09

0

Reset to default

You must log in to answer this question.