# Does every polycube tiling imply a regular polycube tiling?

Let's define d-polycubes to be a union of unit hypercubes from the $\mathbb Z^d$ tiling of d-dimensional Euclidean space which has connected interior. Given a tiling of $\mathbb R^d$ by identical copies of a d-polycube, we call this tiling regular if all the centers of the hypercubes have integer coordinates (i.e. the hypercubes fit together in a $\mathbb Z^d$ lattice).

I haven't been able to make much progress on the following seemingly simple and natural question:

If a given d-polycube tiles $\mathbb R^d$, must it also tile this space regularly?

I believe I have the $d=2$ case by a simple argument. As long as one has a connected tiled region with a concave boundary one can show that the adjacent 2-polycube (a.k.a. polyomino) at that corner must be placed to fit next to the squares of the already placed polyominoes so that edges meet edges and vertices meet vertices. We continue this until we tile the entire plane or we reach a convex region. Since the allowed angles are $\pi/2, \pi, 3\pi/2$ then we must have a rectangle. Now we can tile the space with translations of this rectangle.

However this doesn't work in $d\geq 3$ and I'm having trouble coming up with an argument in that case.

-
"must it also tile this space regularly?" Could you please be specific: What is "this space"? Thank you! – Joseph O'Rourke Apr 7 '12 at 0:58
I'm referring to $\mathbb R^d$. – Gjergji Zaimi Apr 7 '12 at 3:08
Can't you look at the induced tiling on a 2-dimensional subset? Can you say anything about induced tilings? Also, what about "brick wall" tilings where the centers of bricks in adjacent rows are offset by half a brick? Do you have something that excludes that kind of tiling? Gerhard "Ask Me About System Design" Paseman, 2012.04.06 – Gerhard Paseman Apr 7 '12 at 5:05
Using Konig's lemma it would be sufficient to prove the following statement: For any k there is an n (naturals) such that if some polycubes (not necessarily congruent) cover n^d (without holes and overlaps), then they have a regular arrangement that covers k^d. Do you have a counterexample to this stronger statement? Even this seems very innocent, even if we don't require connectedness. – domotorp Apr 7 '12 at 10:33
I feel like any irregular tiling is only "stupidly irregular", as in the example diagram you provided in the question statement. In that case, the entire tiling is just made out of disjoint unions of regular subtilings (the vertical strips), and these disjoint pieces are just put together in an unnecessarily irregular way. Are there any truly irregular tilings that are not the union of "nice" regular subtilings? – Pat Devlin Apr 9 '12 at 21:38

## 1 Answer

I am almost sure that the answer is no. Your question is strongly related to Keller's conjecture which turned out to be false. There a tiling of $\mathbb Z^{10}$ was given by translates of the unit cube such that the center of each translate is a halfinteger. Moreover, the tiling has a very strong lattice-like structure, 1024 cubes whose center is in $[0,2]^{10}$ are translated by every vector from $2\mathbb Z^{10}$.

Of course, the cube won't give a counterexample to your question. But you can divide each cube from this construction to like $3^{99}$ little cubes and then "dig little tunnels" among adjacent cubes to make sure the resulting polyominos only fit in the given way. This leaves many details to work out and I am not 100% sure it can be done but looks like a promising approach.

-
The link should be en.wikipedia.org/wiki/Keller%27s_conjecture – Marc van Leeuwen Sep 8 '12 at 17:22
Thx, I finally managed to fix it but I think something is wrong with MO as the link does not copy correctly, I had to edit it manually. – domotorp Sep 9 '12 at 21:13
Thank you for the pointer to Keller's conjecture. One thing I'm still interested is a proof for low dimensions like 3 and 4, where the statement is hopefully still true. – Gjergji Zaimi Sep 9 '12 at 21:15