7
$\begingroup$

The title nearly says it all: what is the fewest number of cubes that can be fused face-to-face into a polyhedron that does not fill space? The smallest that seemed like a sure non-tiler to me was 9: seven in a ring missing one "corner", plus one above one of the "middle" cubes of this ring, and a final one fused to that one, positioned above the hole in the ring. Then there seemed to be no way fill the hole in the ring with another copy of this polycube -- but EDIT: as Georgios points out in a comment to his answer, you can actually interlock a pair of these to get a simply-connected compound. So the smallest truly obvious non-filler is a decacube, consisting of an 8-ring with two attached to a middle cube to "cap" the hole.

But I wouldn't be surprised if there were an octacube or heptacube non-space-filler, and if so, I suspect it's well-known to some folks. However, I can't seem to find a reference, even though the answer to the corresponding question for polyominoes in 2D is easy to find, e.g. MathWorld notes that all but four heptominoes tile the plane, as all smaller polyominoes do.

$\endgroup$

2 Answers 2

7
$\begingroup$

Edit: As mentioned in the comments, this answer was incorrect. The linked source's claims are wrong. I've included some updated analysis above the break.

I've verified with my own tiling solver that every heptacube tiles space - at most four copies are needed for any heptacube to form a translationally-tiling patch. Interestingly, all four heptacubes that require more than two copies to form a translationally-tiling patch are planar (the first three in the image below, and a tiling heptomino shown in the first image at this page).

The unique octacube which does not tile space is the 3D version of the "donut" octomino:

* * *
*   *
* * *

It is able to cover a $6\times6\times7$ box, but not a $6\times7\times7$ box.


Wrong answer below


From http://www.recmath.com/PolyPages/PolyPages/index.htm?Tiling.htm:

All polycubes up to and including the hexacubes will tile space.


However, of the four heptominoes that do not tile space (shown below), the latter three still don't tile when you "elevate" them to three dimensions.

enter image description here

The first heptomino pictured above does, however - in fact, it tiles a $2\times 5\times 7$ box:

enter image description here

So the answer is $7$ cubes. (I don't recall if there are nonplanar heptacubes that don't tile space - I would guess so, but don't know of examples offhand.)

As a remark, "elevating" a lower-dimensional failure will always produce tilers of a higher-dimensional space eventually - see Tiling with Arbitrary Tiles for a proof that every polyomino tiles $\mathbb{Z}^d$ for some $d$. (In fact, the result holds even when an arrangement of cells is disconnected!)

$\endgroup$
6
  • 2
    $\begingroup$ Wow, I assumed the 7-ring would tile space, by first linking through itself to make a simply connected 14-cube, which I imagined was simple enough that it would fill space. Which of the three "elevated" non-fillers is it easiest to see won't work? $\endgroup$ Commented May 18, 2021 at 0:24
  • 1
    $\begingroup$ Actually, the 7-ring heptacube does fill space - contrary to what's implied in the PolyPages link in this (unfortunately inadvertently) incorrect answer - as discovered by Georgios Papoutsis (github.com/gepa71/whuts-solver), and possibly independently by Moritz Firsching (although I am not clear on that). In fact, their computational results indicate all heptacubes fill space, and show that the 8-ring is the sole octacube that does not. Hopefully George or Moritz will post an answer here I will accept, or else in a few days I will post their results with diagrams for the key cases. $\endgroup$ Commented May 24, 2021 at 22:02
  • $\begingroup$ P.S. Thanks to Matt Parker for connecting this question to the work of Georgios and Moritz, and my apologies for inadvertently writing "George" in the second mention of him in my previous comment, which sadly I can no longer edit. $\endgroup$ Commented May 24, 2021 at 22:18
  • $\begingroup$ @GlenWhitney: Wow, thanks for the update! I'd love to see what these tilings look like, if you have an illustration (otherwise I'll try to make one myself). $\endgroup$ Commented May 25, 2021 at 1:38
  • $\begingroup$ See Georgios's answer now updated with some lovely pictures. Do we know if the PolyPages are still being maintained, and if so, who the maintainers are? @RavenclawPrefect, have you reached out to them, or should I try to? Thanks! $\endgroup$ Commented May 25, 2021 at 17:44
6
$\begingroup$

I recently wrote some code based on Matt Parker's Hypercube Folding Video, and run it with all heptacubes, octacubes and nonocubes. It found tilings for all heptacubes, all but one octacube (the donut shaped one), and all but six five nonocubes.

My code and all tilings found so far are in my whuts-solver github repository.

Please note, my code does not prove that a solution does NOT exist for some polycube, it only verifies ones that exist. Moritz Firsching has done some similar work and to my understanding he has proven that the donut-octacube does indeed not tile space, but I will let him comment on this part.

These are the nonocubes I could not find a tiling for yet:

Nonocubes 10958, 25373, 4921, 4931, 22768

All other solutions are in the github repository in the directories <n>cubes_solutions, these are as json, with "base_blocks" a list of coordinates of where to position some of the polycubes, and "offsets" showing three directions (and distances), to repeat the pattern to get a full tiling.

I will update later with some visualisations for the tiling produced for the three heptacubes that were mentioned as non-tiling in another answer.

Edit: For reference, the three heptacube claimed to not tile space in a separate answer are numbered 144, 556 and 272 in my enumeration, the tilings for these can be found in the files heptacube_solutions/solution_0NNN.json in the repository.

Edit: In the meantime, my solver (after running for 4 days) found a solution for one more of the nonocubes (number 1345 in my numbering in github), the primitive block is composed of 12 nonocubes! Since this is an exhaustive search, this is the simplest possible solution for this nonocube (assuming a periodically repeating tiling of course). Also, here is an image showing the tiling for the three heptacubes mentioned in another answer:

tilings for heptacubes 144, 556 and 272

Edit: Here is an image for the two nonocubes (4921 and 4931) and how they can generate an interlocking pattern each:

enter image description here

$\endgroup$
5
  • 1
    $\begingroup$ One comment regarding the "obviously" non-tiling nonocubes you describe in your question (4921 and 4931 in my numbering), it turns out it IS possible to interlock two of them to fill up each other's holes, so theoretically they could also turn out to tile space (although my code didn't find anything yet). $\endgroup$ Commented May 25, 2021 at 8:31
  • $\begingroup$ Wow, the interlocking of pairs of the ring nonocubes in your picture of five current non-fillers is hard to visualize. I am pretty sure I see how they fit, but a picture would be lovely if it's easy to produce one. $\endgroup$ Commented May 25, 2021 at 17:51
  • $\begingroup$ Georgios, how hard would it be to enhance your code to check if the ring octocube "elevated" to an octotesseract fills 4-space? If it does, then there's hope for a nice progression: all hexominoes tile the plane, all heptacubes fill space, and maybe all octotesseracts fill 4-space. Of course, to really check that, you'd also have to check that all of the octotesseracts that do not come from elevations of octocubes fill 4-space. I have no idea how many of those there are, and whether it would be at all feasible for your suitable extended program to check them. $\endgroup$ Commented May 25, 2021 at 18:01
  • $\begingroup$ I added an image for the interlocking nonocubes with the hole (4921 and 4931). In the meantime I am working on extending my code to 4 dimensions to check for octotesseracts, I will update if I have any results on that. $\endgroup$ Commented May 25, 2021 at 19:07
  • $\begingroup$ Cool! I've asked about your results from that search on this related question: math.stackexchange.com/questions/4156024/… $\endgroup$ Commented May 30, 2021 at 16:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .