25
$\begingroup$

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.

$\endgroup$
7
  • 4
    $\begingroup$ Is it possible that for large enough values of $d$ there are unfoldings with "holes" in them, precluding tiling? $\endgroup$ May 16 at 0:23
  • $\begingroup$ @GerryMyerson: Excellent point! Might lead to an upperbound on the $d$ for which all tile $d{-}1$. $\endgroup$ May 16 at 0:43
  • 2
    $\begingroup$ @GerryMyerson Not all holes preclude tiling (depending on what you mean by hole). The shape consisting of ten cubes arranged like $ \begin{matrix} \square & \square & \square & \square \\ \square & & & \square \\ \square & \square & \square & \square \end{matrix} $ tiles $\mathbb{R}^3$. That said, I think that holes would be a good thing to look for, in that they should make tiling much more difficult. $\endgroup$ May 16 at 4:34
  • 2
    $\begingroup$ @GerryMyerson: In an unfolding of the cube, the squares are matched whole-edge to whole-edge, i.e., the dual (node=square) is connected. The dual of your example has four components; several squares share just a vertex. $\endgroup$ May 16 at 12:03
  • 1
    $\begingroup$ For $d=1$, the unfolding of the line segment does not tile the point, because it's too big. (But is it an unfolding?) $\endgroup$ May 16 at 12:30
6
$\begingroup$

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:

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.

$\endgroup$
5
  • $\begingroup$ Can be generalized a bit further. Instead of coordinate sum, you can use a linear combination of the coordinates module $2d$. Using a brute-force search that works for 134/261 hypercube unfoldings. $\endgroup$ May 17 at 16:17
  • $\begingroup$ Nice! A common way to express linearity is to say that the dual graph (each node a $(d{-}1)$-cube) is a path. $\endgroup$ May 17 at 17:49
  • $\begingroup$ Should "sum of coordinates divides $2d$" be "sum of coordinates is $0 \mod 2d$"? $\endgroup$
    – Sean D
    May 18 at 8:34
  • 1
    $\begingroup$ You're right, I have it the wrong way around, I will edit my answer $\endgroup$ May 18 at 8:50
  • $\begingroup$ I have made an interesting observation. In an earlier comment I mentioned that the technique I describe can be generalized with a linear equation of the coordinates, mod $2d$. If instead I do mod $2\cdot(2d)$ it is possible to fit a rotation/reflection of the unfolding as well. Doing this I am able to make a tiling for all 261/261 hypercube unfoldings; see This code $\endgroup$ May 31 at 10:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.