Which unfoldings of the $d$-dimensional hypercube tile $(d{-}1)$-space?

Question

A six year old question, Which unfoldings of the hypercube tile $3$-space?, has just been answered by Moritz Firsching: All $261$ unfoldings tile space! So now we know:

• For $d=2$, the unfolding of the square tiles $\mathbb{R}$.
• For $d=3$, each of the $11$ unfoldings of the $\mathbb{R}^3$-cube tile $\mathbb{R}^2$.
• For $d=4$, each of the $261$ unfoldings of the $\mathbb{R}^4$-hypercube tile $\mathbb{R}^3$.

The natural next question (also posed at MESE) is:

Q. Is it true that, for every $d$, each of the unfoldings of the $d$-dimensional cube tiles $\mathbb{R}^{d-1}$? If not, up to which $d$ does this hold?

Brute-force calculation may be limited by the combinatorics: Number of hypercube unfoldings, OEIS:A091159: $$1,11,261,9694,502110,33064966,2642657228 ,\ldots $$

Added. I should add that recently Satyan Devadoss and his students proved that no unfolding of a $d$-dimensional hypercube self-overlaps, i.e., each forms a net.

DeSplinter, Kristin, Satyan L. Devadoss, Jordan Readyhough, and Bryce Wimberly. "Nets of higher-dimensional cubes." Canad. Conf. Comput. Geom. 2020, pp.114-120. CCCG proceedings link.

Answer 1

Linear unfoldings

A category of unfoldings that can always be tiled are the linear ones. Let's say an unfolding is branching if there is a (d-1)-hypercube with at least 3 adjacent hypercubes. I then define linear unfoldings as those that don't branch.

Examples:

• https://whuts.org/unfolding/1 is linear
• https://whuts.org/unfolding/8 is also linear
• https://whuts.org/unfolding/18 is branching

Here is a table of how many unfoldings are linear

$d$	Linear (A271215)	Total (A091159)
2	1	1
3	4	11
4	24	261
5	184	9694
6	1911	502110
7	24252	33064966

Now we can use some results of the article in CCCG you linked. In particular lemma 2, which states:

Let $T$ be a spanning tree of the $n$-Roberts graph with a coordinate system. If direction $x$ is used in the unfolding along some path of $T$, direction $-x$ will not be used in the unfolding along this path

Because I have restricted to linear unfoldings, the tree $T$ is linear. Therefore there is a path trough all vertices in $T$. From the lemma it then follows: if we follow the unfolding from one end to another, we will only move in one direction of each dimension. Let's call these directions the positive direction of each dimension in (d-1)-space. Now lets associate each (hyper-)cube with a point in $\mathbb Z^{d-1}$. fix the start cube at $(0, 0, \ldots, 0)$, we can give the others coordinates as well. For the first example this will look like this:

$$(0,0,0),(0,1,0),(1,1,0),(1,1,1),(2,1,1),(2,2,1),(3,2,1),(3,2,2)$$

Notice that between adjacent cubes exactly one coordinate increases by 1. Because of this the sum of the coordinates also increases by one each step. Now suppose we place a copy of the unfolding with it's start cube at $(0,1,-1)$:

$$(0,1,-1),(0,2,-1),(1,2,-1),(1,2,0),(2,2,0),(2,3,0),(3,3,0),(3,3,1)$$

There cannot be any overlap with the other one. Suppose otherwise, there is a cube in common. Let's label the cubes of the unfolding from $0$ to $2d-1$, from start to finish. Now suppose the conflicting cube has label $i$ in the original unfolding, and $j$ in the copy. Then the sum of coordinates of that cube is $(0+0+0)+i=(0+1+-1)+j$, which gives $i=j$. That would imply all cubes of the unfolding conflict. But then we get $(0,0,0)=(0,1,-1)$ for the start cube, a contradiction.

We get a space-filling tiling if we place copies at each point where the sum of coordinates is a multiple of $2d$.
There is no overlap, by the argument as before. If two (hyper-)cubes of two different foldings conflict, they have the same coordinate sum modulo $2d$. This implies they have the same index in the unfolding, which implies the start cubes of both overlap leading to a contradiction.
There is also no empty spaces. By definition each spot where the sum of coordinates is a multiple of $2d$ is filled by all start cubes. All spots with remainder $i$ modulo $2d$ then get filled with the cubes at index $i$.

Expanding the method

I have added this section to expand on my comments. It demonstrates how the method described can be expanded to proof more unfoldings tileable. As a running example I will use the class of crosses.

A multi-dimensional cross is an unfolding of the $d$-cube, which has $2d$ dimension-$(d-1)$ cubes at the following coordinates:

$$\begin{align}\{&(0,0,\ldots,0);& &(-1,0,\ldots,0);& &(0,-1,0,\ldots,0);& &\ldots;& &(0,0,\ldots,-1);&\\ &(2,0,\ldots,0);& &(\quad 1,0,\ldots,0);& &(0,\quad 1,0,\dots,0);& &\ldots;& &(0,0,\ldots,\quad 1)\}& \end{align}$$

If you tried to tile a cross without rotation/reflection, you will get stuck. This means we can't simply use the mod $2d$ method above. Therefore we need to expand the method to fit multiple orientations of an unfolding. For the cross it is sufficient to use two orientations, the original and the one with the long end the other way. I will show that these together tile the plane by an injective mapping of their cubes onto $0, \ldots, 4d-1$.

This mapping will be a linear equation of the coordinates, modulo $4d$. For the cross I will use the following mapping: $f(x_1, x_2, \ldots, x_{d-1}) = 1\cdot x_1 + 3\cdot x_2 + 5 \cdot x_3 + \ldots + (2d-3)\cdot x_{d-1} \mod 4d$.

So what will a cross look like after applying this mapping. Obviously the center cube, $(0,\ldots,0)$ is mapped to $0$. The extra cube $(2,0,\ldots,0)$ is mapped to $2$. All the other cubes will be mapped to $\pm (2i+1) \mod 4d$ for $i=0$ to $d-1$. The image of the mapping will look as follows (for d=5):

####.#.#.....#.#.#.#

Now we do the same for the rotated cross. Note that inverting an even number of axes is equivalent to an 180° rotation. We say that the rotated cross is formed by inverting the cross along $x_1$ and $x_2$. The inversion along $x_2$ swaps the cubes at $(0,1,0,\ldots,0)$ and $(0,-1,0,\ldots,0)$; but that still gives the same shape. Similarly the inversion along $x_1$ swaps $(1,0,\ldots,0)$ and $(-1,0,\ldots,0)$, but it also moves $(2,0,\ldots,0)$ to $(-2,0,\ldots,0)$. If we apply the mapping to the rotated cross, the image will be mostly the same. There is only one difference, corresponding to the move of the extra cube.

##.#.#.#.....#.#.###

If we then move the rotated cross in $(d-1)$-space, the image after mapping gets rotated. If we move the rotated cross in the right way (rotate 11), we can get the image to look as follows:

....#.#.#####.#.#.#. -- moved rotated cross
####.#.#.....#.#.#.# -- original cross

which perfectly fills the gaps the original cross left behind. This implies we can fill space by placing a cross at each position where $f(x_1,\ldots, x_{d-1})=0$, and a rotated cross at each position where $f(x_1,\ldots, x_{d-1})=2d+1$.

This method allows us to show that 248 / 261 hypercube unfoldings tile the plane with at most one extra unfolding rotated 180° from the original. I have not yet tried the 90° rotations as those are harder to implement. Instead I relaxed the "even number of axes reversed" to "any number of axes reversed", which then could show that all 261/261 unfoldings tile 3D space with at most one extra rotated/reflected piece.

I have now run the method on all 5-cube unfoldings. They all (9694/9694) tile 4D space, using only a single extra rotated version, no reflections were needed. For every of those foldings it was tileable with the all-axis-flip rotation.