5
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ A recent paper addressing this in $\mathbb Z^2$ is arxiv.org/abs/1602.05738 (it is shown that tileability is decidable in 2 dimensions, by showing that if $\mathcal T$ tiles, then it does so periodically). $\endgroup$
    – Anthony Quas
    Commented Mar 14, 2016 at 18:02
  • 1
    $\begingroup$ Thank you for the reference. The paper you mentioned deals with the non-lattice case, which is way more complicated... $\endgroup$
    – Campello
    Commented Mar 15, 2016 at 9:01
  • $\begingroup$ So I'm trying to understand which is your question: 1) Given $\mathcal T$ and $\Lambda$, is it NP-complete to decide if $\mathcal T$ is a $\Lambda$-tile? or 2) Given $\mathcal T$, is it NP-complete to decide if $\mathcal T$ is a $\Lambda$-tile for some lattice $\Lambda$? I think the answer to 1) is that it's P. $\endgroup$
    – Anthony Quas
    Commented Mar 15, 2016 at 12:07
  • $\begingroup$ Thanks, I changed the text. It is more like 2). Can you elaborate on 1)? $\endgroup$
    – Campello
    Commented Mar 16, 2016 at 0:10
  • $\begingroup$ So here's my attempt at 1): Given $\Lambda$, form a matrix whose columns are a basis for $\Lambda$. I believe the necessary and sufficient condition for $\mathcal T$ to be a $\Lambda$-tile is (a) $|\det A|=|\mathcal T|$ and (b)$A^{-1}(\mathbf u-\mathbf v)\not\in\mathbb Z^n$ for all distinct $\mathbf u$ and $\mathbf v$ in $\mathcal T$. $\endgroup$
    – Anthony Quas
    Commented Mar 16, 2016 at 4:24

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .