2 Preliminaries and the odd case

We begin with the case of $k$ odd. This is technically much simpler than the general case, and allows us to demonstrate some of the main ideas in the proof of Theorem 2 in a less complicated setting.

Throughout this section, $T$ is fixed, and $k\geqslant 3$ . We will not yet assume that $k$ is odd, because the tools that we are about to develop will be relevant to the general case too.

We start with an important definition from [Reference Gruslys, Leader and Tan8]: a string is a one-dimensional infinite line in $\mathbb{Z}^{d}$ with every $(k+1)$ th point removed. Crucially, a string is a disjoint union of copies of $T$ .

We cannot tile $\mathbb{Z}^{d}$ with strings, as each string intersects $[k+1]^{d}$ in either 0 or $k$ points, and $(k+1)^{d}$ is not divisible by $k$ . However, we could try to tile $\mathbb{Z}^{d}$ by using strings in $d-1$ of the $d$ possible directions, leaving holes that can be filled with copies of $T$ in the final direction. We therefore consider $\mathbb{Z}^{d}$ as consisting of slices equivalent to $\mathbb{Z}^{d-1}$ , each of which will be partially tiled by strings: that is, a subset of each $\mathbb{Z}^{d-1}$ slice will be tiled by strings.

Given a partial tiling of the discrete torus $\mathbb{Z}_{k+1}^{d-1}=(\mathbb{Z}/(k+1)\mathbb{Z})^{d-1}$ by lines with one point removed, we can lift it to $\mathbb{Z}^{d-1}$ by filling $\mathbb{Z}^{d-1}$ with repeating copies of $\mathbb{Z}_{k+1}^{d-1}$ (regarded as $[k+1]^{d-1}$ ). This produces a partial tiling of $\mathbb{Z}^{d-1}$ by strings. We will restrict our attention to these tilings at first, as they are easy to work with.

We will call a set $X\subset \mathbb{Z}_{k+1}^{d-1}$ a hole in $\mathbb{Z}_{k+1}^{d-1}$ if $\mathbb{Z}_{k+1}^{d-1}\setminus X$ can be tiled with strings. One particularly useful case of this is when $d=3$ and $X$ either has exactly one point in each row of $\mathbb{Z}_{k+1}^{2}$ or exactly one point in each column of $\mathbb{Z}_{k+1}^{2}$ . Then $X$ is clearly a hole, since a string in $\mathbb{Z}_{k+1}^{2}$ is just a row or column minus a point.

The following result will allow us to fill the gaps in the final direction, assuming we have chosen the partial tilings of the $\mathbb{Z}^{d-1}$ slices carefully.

We will now prove Theorem 3. We know that if $X\subset \mathbb{Z}_{k+1}^{2}$ has one point in each row or column then $X$ is a hole of size $k+1$ . Since $k+1$ is even, we can try to choose $X_{n}$ in each slice $\mathbb{Z}_{k+1}^{2}\times \{n\}$ so that $\bigcup _{n\in \mathbb{Z}}X_{n}$ is the disjoint union of $(k+1)/2$ sets $Y_{i}$ of the form in Lemma 4.

We can do this as follows.

For $n\equiv 0,k+1,\ldots ,2k-1~(\text{mod}~3k)$ , let $X_{n}=\{(0,0),(1,1),\ldots ,(k-1,k-1),(k,k)\}$ .

For $n\equiv k,2k+1,\ldots ,3k-1~(\text{mod}~3k)$ , let $X_{n}=\{(0,0),(0,1),(2,2),(2,3),\ldots ,(k-1,k-1),(k-1,k)\}$ .

For $n\equiv 2k,1,\ldots ,k-1~(\text{mod}~3k)$ , let $X_{n}=\{(0,1),(1,1),(2,3),(3,3),\ldots ,(k-1,k),(k,k)\}$ .

Then let $X=\bigcup _{n\in \mathbb{Z}}(X_{n}\times \{n\})\subset \mathbb{Z}_{k+1}^{2}\times \mathbb{Z}$ .

Each $X_{n}$ is a hole, so we can tile $(\mathbb{Z}_{k+1}^{2}\times \mathbb{Z})\setminus X$ with strings. Also, $X$ is the disjoint union of sets of the form $Y$ from Lemma 4: for $0\leqslant i\leqslant (k-1)/2$ , let $S_{i}=\{(2i,2i),(2i,2i+1),(2i+1,2i+1)\}$ . Then $X\cap (S_{i}\times \mathbb{Z})$ is precisely the set $Y$ generated from $S_{i}$ in the proof of Lemma 4. Hence $T$ tiles $X$ .

Since $(\mathbb{Z}_{k+1}^{2}\times \mathbb{Z})\setminus X$ can be tiled with strings, we can partially tile $\mathbb{Z}^{3}$ with strings, leaving a copy of $X$ empty in each copy of $\mathbb{Z}_{k+1}^{2}\times \mathbb{Z}$ . We can tile all of these copies of $X$ with $T$ , so $T$ tiles $\mathbb{Z}^{3}$ , completing the proof of Theorem 3.

3 The general case

We now move on to general $k$ .

We will assume throughout that $T$ is fixed and $k\geqslant 3$ .

For even $k$ , the construction used to prove Theorem 3 does not work, as all holes in $\mathbb{Z}_{k+1}^{2}$ have size $(k+1)^{2}-mk$ for some $m$ , and this is always odd, so we cannot use Lemma 4. The same is true if we replace 2 with a larger dimension, or if, as in [Reference Gruslys, Leader and Tan8], we use strings in which every $(2k+1)$ th point, rather than every $(k+1)$ th point, is removed. We will therefore need a new idea.

Instead of using strings in $d-1$ out of $d$ directions, we could only use them in $d-2$ directions and fill the gaps with copies of $T$ in the two remaining directions. We will show that this approach works in the case $d=2$ , giving a tiling of $\mathbb{Z}^{4}$ . The strategy will be to produce a partial tiling of each $\mathbb{Z}^{3}$ slice and use the construction from Lemma 4 to fill the gaps with tiles in the fourth direction.

We will again build partial tilings of $\mathbb{Z}^{2}$ , and therefore of higher dimensions, from partial tilings of the discrete torus $\mathbb{Z}_{k+1}^{2}$ . The following result is a special case of one proved in [Reference Gruslys, Leader and Tan8].

The sets $S$ of size 3 that we will use in Lemma 4 will have two points, say $x_{1}$ and $x_{2}$ , in one $\mathbb{Z}_{k+1}^{2}$ layer and one point, say $x_{3}$ , in another layer. Every layer will contain points from exactly one such set $S$ . Let $Y$ be the set constructed from $S$ in the proof of Lemma 4. In a given slice $\mathbb{Z}^{3}\times \{n\}$ , there are therefore two cases:

1. (1) $Y\cap (S\times \{n\})=\{x_{1},x_{3}\}\times \{n\}$ or $\{x_{2},x_{3}\}\times \{n\}$ ;

2. (2) $Y\cap (S\times \{n\})=\{x_{1},x_{2}\}\times \{n\}$ .

In case (1), each $\mathbb{Z}_{k+1}^{2}$ layer contains exactly one point of $Y$ ; $T$ then tiles the rest of the layer by Proposition 6.

In case (2), some of the layers contain two points of $Y$ , and some of the layers contain no points. Holes of size 0 and 2 do not exist, so we will need copies of $T$ in the third direction to fill some gaps (where $Y$ consists of copies of $T$ in the fourth direction). The following lemma provides us with a way to do this.

Lemma 7. Let $A\subset \mathbb{Z}^{d}$ , $|S|=3k$ . Then there exists $B\subset S\times \mathbb{Z}$ such that $T$ tiles $B$ , and

$$\begin{eqnarray}|B\cap (S\times \{n\})|=\left\{\begin{array}{@{}ll@{}}k+1\quad & \text{if }n\equiv 1,\ldots ,k~(\text{mod}~2k),\\ k-1\quad & \text{if }n\equiv k+1,\ldots ,2k~(\text{mod}~2k).\end{array}\right.\end{eqnarray}$$

The reasoning behind this lemma is that there exist sets $X\subset \mathbb{Z}_{k+1}^{2}\times \mathbb{Z}$ that are missing exactly $k+1$ points in every $\mathbb{Z}_{k+1}^{2}$ layer and can be tiled with strings. If we take $d=2$ in Lemma 7, we would like to choose such a set $X$ and a set $A\subset \mathbb{Z}_{k+1}^{2}$ (abusing notation slightly, as $\mathbb{Z}_{k+1}^{2}$ is not actually a subset of $\mathbb{Z}^{2}$ ) such that the resulting $B$ in Lemma 7 is disjoint from $X$ . Then $(\mathbb{Z}_{k+1}^{2}\times \mathbb{Z})\setminus (B\cup X)$ contains either two or zero points in each $\mathbb{Z}_{k+1}^{2}$ layer, which is what we wanted.

In order for this construction to work, we need the set $B\cap (A\times \{n\})$ to be a hole whenever it has size $k+1$ , and to be a subset of a hole of size $k+1$ whenever it has size $k-1$ , so that we actually can tile the required points with strings. By observing the forms of the sets $B\cap (A\times \{n\})$ in the proof of Lemma 7, we see that it is sufficient to choose the $a_{n}$ such that for all $n$ , $\{a_{n},\ldots ,a_{n+k}\}$ is a hole. Here we regard the indices $n$ of the points $a_{n}$ of $A$ as integers modulo $3k$ , so $a_{3k+1}=a_{1}$ and so on. The following proposition says that we can do this.

From now on, $a_{n}$ refers to the points defined in the above proof. This proposition is the motivation for choosing the value $6k$ in the proof of Lemma 7.

We can now prove Theorem 5. We will need three distinct partial tilings of $\mathbb{Z}^{3}$ slices, corresponding to the three cases in the proof of Lemma 4 with $d=3$ . The repeating unit in each of these partial tilings will have size $(k+1)\times (k+1)\times 6k$ , so we will work in $\mathbb{Z}_{k+1}^{2}\times \mathbb{Z}_{6k}$ .

We start by choosing the sets $S$ as in Lemma 4. These will be as follows.

For $n=1,\ldots ,k$ , $S_{n}=\{(0,0,n),(a_{n},n+k),(a_{k+1},n+k)\}$ .

For $n=k+1,\ldots ,2k$ , $S_{n}=\{(0,0,n+k),(a_{n},n+2k),(a_{2k+1},n+2k)\}$ .

For $n=2k+1,\ldots ,3k$ , $S_{n}=\{(0,0,n+2k),(a_{n},n+3k),(a_{1},n+3k)\}$ .

We will refer to the points in $S_{n}$ as $x_{n,1},x_{n,2},x_{n,3}$ in the order given.

We can construct a set $Y_{n}\subset \mathbb{Z}^{4}$ from each $S_{n}$ using the construction in the proof of Lemma 4. Let $Y=\bigcup _{1\leqslant n\leqslant 3k}Y_{n}$ . For a given $m\in \mathbb{Z}$ , there are two possibilities for the structure of $Y\cap (\mathbb{Z}_{k+1}^{2}\times \mathbb{Z}_{6k}\times \{m\})$ .

1. (1) The set $Y\cap (\mathbb{Z}_{k+1}^{2}\times \mathbb{Z}_{6k}\times \{m\})$ consists of pairs of the form $\{x_{n,1},x_{n,2}\}$ or $\{x_{n,1},x_{n,3}\}$ . Then it contains exactly one point in each $\mathbb{Z}_{k+1}^{2}$ layer. We can therefore tile $(\mathbb{Z}_{k+1}^{2}\times \mathbb{Z}_{6k}\times \{m\})\setminus Y$ entirely with strings, by Proposition 6.

2. (2) The set $Y\cap (\mathbb{Z}_{k+1}^{2}\times \mathbb{Z}_{6k}\times \{m\})$ consists of pairs of the form $\{x_{n,2},x_{n,3}\}$ . Then it contains either 2 or 0 points in each $\mathbb{Z}_{k+1}^{2}$ layer.

   If $A=\{a_{1},\ldots ,a_{3k}\}$ , and $B$ is the set constructed from $A$ in the proof of Lemma 7, then, by the choice of the $S_{n}$ , the sets $B$ and $Y\cap (\mathbb{Z}_{k+1}^{2}\times \mathbb{Z}_{6k}\times \{m\})$ are disjoint. Furthermore, if $C$ is the union of these two sets, then, for every $n$ , $C\cap (\mathbb{Z}_{k+1}^{2}\times \{n\}\times \{m\})=\{a_{r},\ldots ,a_{r+k}\}$ for some $r$ , and by Proposition 8, this contains either one point in every row or one point in every column and is therefore a hole.

   Since $T$ tiles $B$ , it also tiles $(\mathbb{Z}_{k+1}^{2}\times \mathbb{Z}_{6k}\times \{m\})\setminus Y$ .

Also, $T$ tiles $Y$ by Lemma 4. Hence $T$ tiles $\mathbb{Z}_{k+1}^{2}\times \mathbb{Z}_{6k}\times \mathbb{Z}$ , and therefore also $\mathbb{Z}^{4}$ , completing the proof of Theorem 5.

4 The 4 modulo 8 case

To finish the proof of Theorem 2, all that remains is to prove the following.

We will prove this by constructing partial tilings of each $\mathbb{Z}^{2}$ slice and filling in the gaps using the construction from the proof of Lemma 4. We will define three subsets $X_{1}$ , $X_{2}$ , $X_{3}$ of $\mathbb{Z}^{2}$ and show that $T$ tiles each of them. However, two of these tilings will not make use of strings.

Let $S_{1}=\{(x,x+n(k+1))\mid n\in \mathbb{Z},x\equiv 2n,2n+1,2n+2,2n+3~(\text{mod}~8)\}$ .

Let $S_{2}=\{(x,x+n(k+1))\mid n\in \mathbb{Z},x\equiv 2n+4,2n+5,2n+6,2n+7~(\text{mod}~8)\}$ .

Let $S_{3}=\{(x,x+n(k+1)+1)\mid n\in \mathbb{Z},x\equiv 2n+2,2n+3,2n+4,2n+5~(\text{mod}~8)\}$ .

Let $X_{1}=\mathbb{Z}^{2}\setminus (S_{2}\cup S_{3})$ , $X_{2}=\mathbb{Z}^{2}\setminus (S_{1}\cup S_{3})$ , $X_{3}=\mathbb{Z}^{2}\setminus (S_{1}\cup S_{2})$ .

Let the first coordinate be horizontal and the second vertical.

$X_{3}$ is $\mathbb{Z}^{2}$ with every $(k+1)$ th diagonal removed, so each row (or column) is $Z$ with every $(k+1)$ th point removed, that is, a string. Hence $T$ tiles $X_{3}$ .

We will show that $X_{1}$ can be tiled with vertical copies of $T$ and $X_{2}$ can be tiled with horizontal copies of $T$ .

Note that $(x,x+n(k+1))+(2,k+3)=(x+2,(x+2)+(n+1)(k+1))$ . Also, if $x\equiv 2n+r~(\text{mod}~8)$ , then $x+2\equiv 2(n+1)+r~(\text{mod}~8)$ . Hence, by the definitions of $S_{2}$ and $S_{3}$ , we see that $X_{1}$ is invariant under translation by $(2,k+3)$ . To show that vertical copies of $T$ tile $X_{1}$ , it therefore suffices to show that $T$ tiles the columns $X_{1}\cap (\{0\}\times \mathbb{Z})$ and $X_{1}\cap (\{1\}\times \mathbb{Z})$ .

But in fact, if $(0,y)\in S_{2}$ , then $0\equiv 2n+4\text{ or }2n+6~(\text{mod}~8)$ , so $1\equiv 2n+5\text{ or }2n+7~(\text{mod}~8)$ , so also $(1,y+1)\in S_{2}$ . The converse also holds, and the same is true for $S_{3}$ . Thus we only need to check the case $x=0$ :

$(0,n(k+1))\in S_{2}$ for $n\equiv 1,2,5,6~(\text{mod}~8)$ , that is, $n\equiv 1,2~(\text{mod}~4)$ ;

$(0,n(k+1)+1)\in S_{3}$ for $n\equiv 2,3,6,7~(\text{mod}~8)$ , that is, $n\equiv 2,3~(\text{mod}~4)$ .

Therefore $(0,y)\notin X_{1}$ for $y\equiv k+1,2(k+1),2(k+1)+1,3(k+1)+1~(\text{mod}~4(k+1))$ , so copies of $T$ beginning at positions $1$ and $2(k+1)+2$ modulo $4(k+1)$ tile $X_{1}\cap (\{0\}\times \mathbb{Z})$ .

Hence $T$ tiles $X_{1}$ .

Note that $(x,x+n(k+1))+(k+2,1)=(x+k+2,(x+k+2)+(n-1)(k+1))$ .

Since $k\equiv 4~(\text{mod}~8)$ , if $x\equiv 2n+r~(\text{mod}~8)$ then $x+k+2\equiv 2(n-1)+r~(\text{mod}~8)$ . Hence $X_{2}$ is invariant under translation by $(k+2,1)$ , by the definitions of $S_{1}$ and $S_{3}$ . To show that horizontal copies of $T$ tile $X_{2}$ , it is therefore enough to show that $T$ tiles the row $X_{2}\cap (\mathbb{Z}\times \{0\})$ .

We can express $S_{1}$ as $\{(y-n(k+1),y)\mid y\equiv -n,1-n,2-n,3-n~(\text{mod}~8)\}$ .

Similarly $S_{3}=\{(y-n(k+1)-1,y)\mid y\equiv 3-n,4-n,5-n,6-n~(\text{mod}~8)\}$ .

Therefore $(-n(k+1),0)\in S_{1}$ for $n\equiv 0,1,2,3~(\text{mod}~8)$ , and $(-n(k+1)-1,0)\in S_{3}$ for $n\equiv 3,4,5,6~(\text{mod}~8)$ .

Hence $(x,0)\notin X_{2}$ for $x\equiv 0,2(k+1)-1,3(k+1)-1,4(k+1)-1,5(k+1)-1,5(k+1),6(k+1),7(k+1)~(\text{mod}~8(k+1))$ , so copies of $T$ beginning at positions $k+1,3(k+1),5(k+1)+1,7(k+1)+1$ modulo $8(k+1)$ tile $X_{2}\cap (\mathbb{Z}\times \{0\})$ .

Hence $T$ tiles $X_{2}$ .

The set $S_{1}\cup S_{2}\cup S_{3}$ can be partitioned into sets of the form $S=\{x_{1},x_{2},x_{3}\}$ , where $x_{1}=(x,y)\in S_{1}$ , $x_{2}=(x+4,y+4)\in S_{2}$ , $x_{3}=(x+2,y+3)\in S_{3}$ . Then $|S|=3$ , so we can construct the corresponding set $Y\subset \mathbb{Z}^{3}$ as in Lemma 4. Now, given $n\in \mathbb{Z}$ , $(S\times \{n\})\setminus Y=\{x_{i}\}$ for some $i\in \{1,2,3\}$ . Then $Y\cap (X_{i}\times \{n\})=\emptyset$ . If we do this for all such sets $S$ , and let $U$ be the (disjoint) union of the resulting sets $Y$ , then $U\cap (X_{i}\times \{n\})=\emptyset$ , and $\mathbb{Z}^{2}\times \{n\}\subset U\cup (X_{i}\times \{n\})$ . Recall that $T$ tiles each $Y$ and therefore $U$ .

We can do this for every $n$ , choosing a partial tiling $X_{i}$ for the corresponding $\mathbb{Z}^{2}$ layer. Together with $U$ , these form a tiling of $\mathbb{Z}^{3}$ by $T$ . This completes the proof of Theorem 9, and therefore also the proof of Theorem 2.

5 Open problems

Theorem 2, together with the result that a punctured interval $T=\underbrace{\mathtt{XXXXX}}_{k}\!\mathtt{.}\!\underbrace{\mathtt{XXXXX}}_{k}$ does not tile $\mathbb{Z}^{2}$ for $k\geqslant 3$ , determines the smallest dimension $d$ such that $T$ tiles $\mathbb{Z}^{d}$ in the cases $k$ odd and $k\equiv 4~(\text{mod}~8)$ . However, for other values of $k$ , we do not know whether the smallest such dimension $d$ is 3 or 4.

It is also natural to consider more general tiles. The next non-trivial case is that of an interval with a non-central point removed. One might wonder if there is an analogue of Theorem 2 for these tiles.

For general one-dimensional tiles, Gruslys et al [Reference Gruslys, Leader and Tan8] conjectured that there is a bound on the dimension in terms of the size of the tile.

This conjecture remains unresolved. The authors of [Reference Gruslys, Leader and Tan8] showed that if $d$ always exists then $d\rightarrow \infty$ as $t\rightarrow \infty$ , by exhibiting a tile of size $3d-1$ that does not tile $\mathbb{Z}^{d}$ . This gives a simple lower bound on $d$ ; better bounds would be of great interest.