Answer to Q1: All of the 261.
I looked at this question because of a video of Matt Parker and wrote an algorithm to find solutions. See here for an example of how a solution would look like. I dumped all solutions on github. For some cases I list multiple solutions. The files start with a number followed by an underscore and the number is between 0 and 260 corresponding to one of the unfoldings in this list.
129 <--- Number of unfolding (this time 0-indexed)
[[-2, -2, 0], [1, 1, 1]] <---- the box, we put it in
Boolean Program (maximization, 1152 variables, 428 constraints) <---
some information to ignore
32.0 <--- How many of the voxels in the cube are covered (here it
happens to be all of them)
[(-2, -2, 0), (-1, -2, 0), (-1, -2, 1), (-1, -1, 0), (-1, 0, 0), (-1,
1, 0), (0, -2, 1), (1, -2, 1)]
[(-2, -2, 1), (-2, -1, 0), (-2, -1, 1), (-2, 0, 0), (-2, 1, 0), (-1,
-1, 1), (0, -1, 1), (1, -1, 1)]
[(-2, 0, 1), (-1, 0, 1), (0, 0, 1), (1, -2, 0), (1, -1, 0), (1, 0, 0),
(1, 0, 1), (1, 1, 1)]
[(-2, 1, 1), (-1, 1, 1), (0, -2, 0), (0, -1, 0), (0, 0, 0), (0, 1, 0),
(0, 1, 1), (1, 1, 0)]
(the last rows are then the coordinates of the copies of the
unfolding, whatever sticks out of the box fits in another one..)
Here is an example of one of the two one that fit in a 4x4x2 box ( in an exploded view, you can shift them together and they neatly fit into a 4x4x2 box, which can then be stacked to obtain a tiling.:
Answer to Q2: One way is to use integer programming.
The basic idea is to take a box with volume divisible by 8 as a fundamental domain and to cover it as much as possible with non-overlapping copies of an unfolding and make sure that the stuff that sticks out of the bottom actually fits into gaps at the top and so on.
Here's a two-dimensional example:
The tile:
A 5x6 box filled with copies of that tile:
A tiling produced from this:
This can be formulated a as an integer program and it turns out that those 261 unfoldings all have feasible solution for some smallish box (for most 4x4x4 is enough).
Setting up the integer program is just a few lines of sage:
from sage.combinat.tiling import Polyomino
import itertools
def get_mod_points(point, diff):
for coeffs in itertools.product([-1, 0, 1], repeat=diff.length()):
yield vector([diff[i]*coeffs[i] + point[i] for i in range(diff.length())])
def milp_mod_box(tile, inner_box, outer_box, solver=None):
# tile, inner_box and outer_box are `Polyomino`.
begin, end = inner_box.bounding_box()
diff = vector(end) - vector(begin)
diff += vector([1]*diff.length())
tiles = [Q for Q in tile.isometric_copies(outer_box)]
p = MixedIntegerLinearProgram(solver=solver, maximization=True)
x = p.new_variable(binary=True)
for i in inner_box:
cons = p.sum(sum([int(j in T) for j in get_mod_points(i, diff)])*x[T] for T in tiles) == 1
p.add_constraint(cons)
for i in outer_box:
p.add_constraint(p.sum(x[T] for T in tiles if i in T) <= 1)
p.set_objective(p.sum(x[T] for i in inner_box for T in tiles if i in T))
return p, x
Here we optimize for having as much voxels filled in the box as possible, but only so that the solutions look nicer, it would give valid tilings even without setting that objective.
A similar integer programming approach could be used to prove that a certain polyomino is not a space filler: We can check for larger and larger boxes that if it is not possible to cover them completely with non-overlapping copies of the original polyomino, but this wasn't necessary.
Update:
I added 3d-plots of all solutions to 3d-renderings of all 261 unfoldings page. When you click on the number of each one you get a 3d-rending of copies of that unfolding mostly in a box (drawn in grey), which then can be used to tile the plane.
Note this is a different order than the one above (and it starts indexing with $1$.
#213 is the Dalí-unfolding, needs 8 pieces in the prototile.
#3 is the only one that only needs 3 pieces (in a 4x3x2 box) (what a coincidence..)
#72 and #159 are the ones that perfectly fit in a 4x4x2 box.
#139 needs a long 8x2x2 box.
Following up on the comments about using spanning trees and automorphism groups. It does seem to me that perhaps the best way to do this would be to compute the number of different spanning trees of the hyperoctahedral graph up to symmetries of the hyperoctahedron. As Peter Taylor and Brendan McKay have noted, one can use Burnside's lemma to do this. I think this will be easier, because it seems likely that about half of all symmetries will not fix any spanning trees (see below), and that most spanning trees are not fixed by any symmetry. If this is true, most of the computation would be finding a small number of spanning trees that are fixed by reflections of the hyperoctohedron. On the other hand, it seems like computing the number of trees with an appropriate pairing would require solving several instances of the graph isomorphism problem to make sure you aren't overcounting.
The rest of this post is not about computation, but rather about general conjectures. I think (tho I haven't sat down to prove) that rotations will never fix a spanning tree. If this is so, then, after counting the number of spanning trees of the hyperoctohedral graph (which can be done using the matrix-tree theorem), we could use a very simple version of Burnside's lemma to get bounds on the number of nets. Specifically, let $N_d$ be the number of nets of the hypercube in $\mathbf{R}^d$, and let $F(d) = \frac{(2d)^{d-2} (d-1)^d}{d!}$ (this is the same number that Brendan mentions). Then, assuming (as I believe) that no rotation fixes a spanning tree, we get that
$F(d) \leq N_d \leq 2F(d).$
For some small $d$, the bounds look like this:
| $d$ |
Bounds |
| 2 |
$\frac{1}{2} \leq 1 \leq 1$ |
| 3 |
$8 \leq 11 \leq 16$ |
| 4 |
$216 \leq 261 \leq 432$ |
| 5 |
$8533\frac{1}{3} \leq 9694 \leq 17066\frac{2}{3}$ |
The table makes it look like the lower bound is probably closer to the truth. Looking at the ratios $N_d/F(d)$ for the numbers you've computed, Brendan says they appear to be going to 1. I'm a little less sure, since it looks like the rate at which they decrease is going down as $d$ increases, but with such a small dataset it's hard to tell. I'd guess that $N_d/F(d)$ approaches a constant near $1.08$. If it turns out I'm wrong, at least I'll have Legendre to keep me company.
Update: So I started being a little more sophisticated and factoring in what to me are the most obvious symmetries that fix some spanning trees – reflections that interchange only two opposite points. Let the number of spanning trees of the hyperoctohedron in $\mathbf{R}^d$ be $T_d$. Then we can choose a pair of opposite points in $d$ ways. For a spanning tree to be fixed by this reflection, these opposite vertices must both connect to the same vertex, and in order for it to be a tree they can only connect to a single vertex, and we can choose that vertex in $(2d-2)$ ways. Finally, we need a spanning tree of the rest of the hyperoctohedron, but that's actually the same as a spanning tree of the $d-1$ octohedron. So the number of trees fixed by one of these reflections is $(2d-2)T_d$, and there are $d$ such reflections. When we factor this into our lower bound we get $N_d \geq F(d) + (d-1)F(d-1)$.
This is enough to show that $N_d/F(d)$ does not approach 1, since
$\frac{N_d}{F(d)} \geq \frac{F(d) + (d-1)F(d-1)}{F(d)} \xrightarrow{x\to\infty} 1 + \frac{1}{2e^2}.$
I think there's still one more class of reflections contributing a significant number of fixed spanning trees. I'll update as soon as I find it. Right now my prediction for $N_{11}$ is $3.30\times 10^{15}$.
Update: I realized this construction can be extended a little bit. After you fix two opposite vertices and remove them, you're looking at a hyperoctohedron in $\mathbf{R}^{d-1}$. Now, instead of just taking any spanning tree, you can take a spanning tree and an automorphism fixing that spanning tree $\sigma$. If you let $\alpha$ be the automorphism reflecting the two opposite vertices we chose, then you can connect up your two chosen vertices to the chosen tree, and then you get that the whole thing is fixed by $\sigma \circ \alpha$.
I haven't taken the time to work this into the lower bound. However, it does show that my initial conjecture that no rotation fixes a spanning tree is off, which means there's a more subtle reason why certain automorphisms cannot fix a spanning tree.
I think that if you're careful enough, then doing this construction with spanning forests on the $d-1$ hyperoctohedron, and then connecting the forest into a tree with your two chosen vertices, should exhaust all the possibilities when $d$ is odd. When $d$ is even I think there's going to be special spanning trees that don't fit this construction.
Update: I think actually there's actually a better repair than the one I mentioned above. The graph we're considering can actually be thought of as two complete graphs $K_d$ connected up in a certain way. So, you have several symmetries that flop two copies of $K_d$. If you fix one of these symmetries, you can get trees which are fixed by this symmetry by the following recipe:
- Choose a rooted spanning tree for $K^d$.
- Connect the two copies of $K^d$ by an edge between the two roots.
It seems like understanding the exact count of these spanning trees is going to involve understanding automorphisms of rooted trees on $d$ vertices. As far as I can tell, there is no closed form solution for this problem, but perhaps there are good enough asymptotics on the rooted tree problem to give good asymptotics for the problem of nets of cubes.
Best Answer
I implemented the ideas in the paper using Mathematica. I pushed it a bit further to actually generate the images below. You can download this Mathematica notebook to see the code and detailed explanation.
You might notice Dali's original in the middle of the third row from the bottom.