Let $\mathcal{T} \subset \mathbb{Z}^n$ be a finite set. Let $\Lambda \subset \mathbb{Z}^n$ be a full rank lattice. We say that $\mathcal{T}$ is a $\Lambda$-tile for $\mathbb{Z}^n$ if the following two conditions are satisfied:

(i) $(\mathcal{T} + \lambda_1) \cap (\mathcal{T} + \lambda_2) = \emptyset$ for all $\lambda_1,\lambda_2 \in \Lambda$ with $\lambda_1 \neq \lambda_2$.

(ii) $\bigcup_{\lambda \in \Lambda}{(T+\lambda)} = \mathbb{Z}^n$.

There are many interesting open problems concerning tiles. For instance, a 40 year old conjecture of Golomb and Welch states that the $\ell_1$ ball (in $\mathbb{Z}^n$) of radius $r$ does not tile $\mathbb{Z}^n$ unless $r = 1$ or $n = 2$.

My question is what is the complexity of the following problem: Given $n$ and $\mathcal{T}$, decide whether there exists $\Lambda$ such that $\mathcal{T}$ is a $\Lambda$-tile for $\mathbb{Z}^n$. Is there a reference for that?

isdecidable in 2 dimensions, by showing that if $\mathcal T$ tiles, then it does so periodically). $\endgroup$2more comments