79

This is a question posed by Adam Chalcraft. I am posting it here because I think it deserves wider circulation, and because maybe someone already knows the answer.

A polyomino is usually defined to be a finite set of unit squares, glued together edge-to-edge. Here I generalize it to mean a finite set of unit hypercubes, glued together facet-to-facet.

Given a polyomino $P$ in $\mathbb{R}^m$, I can lift it to a polyomino in a higher-dimensional Euclidean space $\mathbb{R}^{m+n}$ by crossing it with a unit $n$-cube: the lifted polyomino is just $P\times [0,1]^n$.

Obviously, not all polyominos tile space.

Is it true that given any polyomino $P$ in $\mathbb{R}^m$, there exists some $n$ such that the lifted polyomino $P\times [0,1]^n$ tiles $\mathbb{R}^{m+n}$?

Many people's first instinct is that multiply-connected polyominos (those with "holes" in them) can't possibly tile, but you can get inside holes if you lift to a high enough dimension.

Timothy Chow
  • 78,129
  • 6
    It's a cute question, Tim, but I would guess the answer is no, perhaps already for 1-dim polyominos. Try ooooooooo oo ooo oooooooo and see how that works out – Igor Pak Dec 20 '10 at 01:07
  • 2
    Igor, what is "ooooooo..."? – Amit Kumar Gupta Dec 20 '10 at 04:35
  • 3
    The interval in $\mathbb R$ of length 25 minus three intervals of length 1, starting at 9, 12, and 16. – Allen Knutson Dec 20 '10 at 04:39
  • Do you allow only tiling by translate of the polyomino, or are rotations and inversions allowed as well? – Moshe Schwartz Dec 20 '10 at 08:46
  • Don't you impose to polyominos to be connected ? – Denis Serre Dec 20 '10 at 08:54
  • @Igor & Timothy: I thought polyominos are inductively defined by gluing a unit hypercube to a previously constructed polyomino along a facet? Perhaps Timothy can clarify. Much thanks. – Tony Huynh Dec 20 '10 at 15:40
  • @Denis and Tony: I think Adam assumed connected, but I admit I don't see why Igor's suggestion is a counterexample. Anyway, if it is, then I'd guess that there's a 2-dimensional connected counterexample obtained by connecting up the components of Igor's example in some way. @Moshe: Rotations are certainly allowed. As for reflections, if there's a counterexample when reflections are disallowed, that would still be interesting. – Timothy Chow Dec 20 '10 at 16:24
  • 2
    @Tim & others: Sorry for the confusion. I am not claiming that this tile is a counterexample (though I did check 2- and 3-dim). All I am saying that since the problem is very much unclear in rather simple special cases, hoping that the answer is always yes is perhaps too optimistic. The connectivity is not mentioned in the question and doesn't seem terribly relevant; I agree with Tim on this. Anyhow, there is no need to trust my intuition - see for yourself if you can tile the space with this tile. – Igor Pak Dec 20 '10 at 18:36
  • @Tim, I was a bit confused, since the question as posed assumes polyominos have to be connected ("glued together facet-to-facet"), and you say you assumed Adam intended connectedness. But Adam himself has said that he doesn't want to assume connectedness (see his answer below), and people seem to have interpreted the question to not require connectedness anyways (Igor's initial comment, for instance). Perhaps you want to edit your question to reflect the fact that there are two related questions of interest, one where polyominos are assumed to be connected, and one where they're not. – Amit Kumar Gupta Dec 21 '10 at 02:30
  • @Amit: I think the comments already address the connectedness issue just fine. I don't think it matters much what you assume about connectedness, so perhaps being vague about the issue is the best way to convey the fact that I don't think it's important. By the way, I'd argue that "glued together facet-to-facet" doesn't have to imply connected. – Timothy Chow Dec 21 '10 at 16:28
  • What we do know is that all (possibly disconnected) polyminos made of at most four squares tile the plane. – Zsbán Ambrus Dec 27 '10 at 14:05
  • 2
    @all How can a 5x5 square with the middle square removed, tile any R^n? Which n ? – fastforward Feb 11 '11 at 12:37
  • 3
    @fastforward: I don't know, but if your worry is that the hole can't be filled, it's enough to lift to $\mathbb{R}^4$. Suppose the first tile is in a horizontal plane, centered at the origin. In "our" 3D slice of $\mathbb{R}^4$, the second tile will be partially visible as a vertical stack of five cubes going through the hole. Shift over to the "next" 3D slice of $\mathbb{R}^4$ and the first tile will disappear but you'll see another vertical stack of five cubes. Shift over again and you'll see four cubes (the middle cube will be missing). The next two shifts will have five cubes again. – Timothy Chow Feb 11 '11 at 14:59
  • 1
    I just heard that this problem has been solved recently, hopefully there will be a write-up soon. – domotorp Feb 19 '15 at 13:41
  • @domotorp: Very interesting! What else do you know? Where did you hear this? Who solved it? – Timothy Chow Feb 19 '15 at 14:55
  • 2
    I heard it in Cambridge, it was Imre Leader and his student, whose name unfortunately I don't know. – domotorp Feb 19 '15 at 20:17

6 Answers6

38

A positive answer to this question has just appeared in the arXiv: Tiling with arbitrary tiles; Vytautas Gruslys, Imre Leader, Ta Sheng Tan; http://arxiv.org/abs/1505.03697

Francisco Santos
  • 1,492
19

Here I prove that it does not matter whether we consider only connected dominoes or not, as there was a lot of discussion about it.

Suppose that the original polyomino, P, is d dimensional. We will construct a 2d dimensional connected polyomino, Q, that can be tiled with P. Clearly, this proves the statement, as if it is impossible to tile any space with P, it is also impossible to do so with Q.

Denote a large enough d dimensional brick that contains P by R. Take the 2d dimensional polyomino P x R, so here every original cube of P is replaced by a 2d brick, 1 x R. Note that P x R is contained in an R x R brick. Fill in the missing parts of this R x R brick by 1 x P polyominos. Notice that this means that R x P will be also filled up completely. This polyomino, Q, will be connected, as we can freely move anywhere in the first d coordinates in R x P and in the last d coordinates in P x R.

Note: The complement of the set obtained this way is R\P x R\P. If we repeat this, then it can be achieved that our polyomino is arbitrarily dense, i.e. it fills out at least 99% of a brick.

domotorp
  • 18,332
  • 3
  • 54
  • 121
  • 2
    Looks nice, but did you mean $R \times P \cup P \times R$ at the end? I wonder if it would be useful to push that idea further and get things like $R \times P \times P \cup P \times R \times P \cup P \times P \times R$ (maybe possible or not, maybe useful or not, I haven't thought yet) – Dave Pritchard Jan 19 '11 at 18:18
  • Oh, I forgot to put their complement, now I fixed it, thx. I was trying for a while but could not finish the proof from here, but it is a very interesting question. I think we can get all sorts of things that you write, but we will always have a little gap of the form (R\P)^k this way. – domotorp Jan 20 '11 at 08:56
14

@Erich: It's certainly not true that every polyomino tiles some hypercuboid. Here's one way to see this. Consider the $n_1\times\ldots\times n_d$ hypercuboid. Index the cells by $(x_1,\ldots,x_d)$ where $0\leq x_i\leq n_i-1$. Give cell $(x_1,\ldots,x_d)$ the value $t^{x_1+\ldots+x_d}$, where $t$ is an indeterminate. Summed over the whole hypercuboid, this is $$\prod_{i=1}^d(1+t+\ldots+t^{n_i-1}),$$ so its complex roots are all on the unit circle. Now take a symmetric 1-d polyomino, and put it in the hypercuboid so that its value has minimal degree in $t$. Its value is some polynomial $p(t)$. Now wherever you put the polyomino, its value is $t^k p(t)$ for some $k\geq 0$. If you tile anything with the polyomino, the total value is $q(t)p(t)$ for some polynomial $q(t)$. So if you can tile the hypercuboid, all the roots of $q(t)p(t)$ must lie on the unit circle. In particular, all the roots of $p(t)$ must lie on the unit circle. Choose a symmetric 1-d polyomino for which this is false. For example, 1101011 (1 is a square, 0 is a hole).

I am endebted to Imre Leader for the idea behind this proof.

Adam Chalcraft
  • 381
10

@Tim: Thanks for posting the question.

@All: I am allowing all translations and rotations. I am also allowing reflections, but that's irrelevant to the question, because you can always get a reflection by rotating in one dimension higher. I do not intend to impose that a polyomino be connected, it's just a finite collection of unit cubes with vertices at $Z^n\subset R^n$.

For example, "o o" tiles in 1 dimension, "oo o" tiles in 1 dimension (allowing reflections) or 2 (not allowing reflections), "oo oo" tiles in 2 dimensions (entertaining exercise) and "oo ooo" tiles in 2 dimensions (easier). I don't know the answer for "ooo ooo".

Adam Chalcraft
  • 381
5

The best-known results for tiling rectangles in 2-D can be found here:

https://erich-friedman.github.io/mathmagic/0299.html

Zsbán Ambrus
  • 1,924
Erich Friedman
  • 51
2

It is wrong but may give someone an idea.

For 1D I would go for +oo+++ooooo+++oo+ (+ is a cell, o is a hole). The key point is that we have more holes than cells but still, each hole requires its own filler. Making the graph P->fillers of holes in P, we get the outbound degree 9 and the inbound degree 8. But for all poliominoes in a cube of size N, their fillers are in the cube of size N+100, so the number of fillers cannot exceed the number of poliominoes noticeably.

In 2D the 7 by 7 square frame has the same properties and is connected..

fedja
  • 59,730
  • 2
    The inbound degree can be larger - one cell can fill holes in several tiles. – Sergei Ivanov Dec 20 '10 at 23:38
  • Yes, that's a problem I overlooked. It is a bit hard to visualize tilings in $R^3$, not to say in higher dimensions. I'll see if I can fix it or do something else. – fedja Dec 21 '10 at 00:26