Does every polyomino tile R^n for some n? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T05:51:48Z http://mathoverflow.net/feeds/question/49915 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/49915/does-every-polyomino-tile-rn-for-some-n Does every polyomino tile R^n for some n? Timothy Chow 2010-12-19T23:29:28Z 2011-01-20T08:53:59Z <p>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.</p> <p>A <i>polyomino</i> 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.</p> <p>Given a polyomino $P$ in $\mathbb{R}^m$, I can <i>lift</i> 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$.</p> <p>Obviously, not all polyominos tile space.</p> <blockquote> <p>Is it true that given <i>any</i> 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}$?</p> </blockquote> <p>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.</p> http://mathoverflow.net/questions/49915/does-every-polyomino-tile-rn-for-some-n/50003#50003 Answer by Adam Chalcraft for Does every polyomino tile R^n for some n? Adam Chalcraft 2010-12-20T22:10:21Z 2010-12-20T22:10:21Z <p>@Tim: Thanks for posting the question.</p> <p>@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$.</p> <p>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".</p> http://mathoverflow.net/questions/49915/does-every-polyomino-tile-rn-for-some-n/50008#50008 Answer by fedja for Does every polyomino tile R^n for some n? fedja 2010-12-20T23:06:21Z 2010-12-21T00:26:55Z <p>It is wrong but may give someone an idea.</p> <p>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.</p> <p>In 2D the 7 by 7 square frame has the same properties and is connected..</p> http://mathoverflow.net/questions/49915/does-every-polyomino-tile-rn-for-some-n/51133#51133 Answer by Erich Friedman for Does every polyomino tile R^n for some n? Erich Friedman 2011-01-04T16:19:02Z 2011-01-04T16:19:02Z <p>The best-known results for tiling rectangles in 2-D can be found here:</p> <p><a href="http://www2.stetson.edu/~efriedma/mathmagic/0299.html" rel="nofollow">http://www2.stetson.edu/~efriedma/mathmagic/0299.html</a></p> http://mathoverflow.net/questions/49915/does-every-polyomino-tile-rn-for-some-n/51822#51822 Answer by Adam Chalcraft for Does every polyomino tile R^n for some n? Adam Chalcraft 2011-01-12T05:05:32Z 2011-01-12T05:05:32Z <p>@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).</p> <p>I am endebted to Imre Leader for the idea behind this proof.</p> http://mathoverflow.net/questions/49915/does-every-polyomino-tile-rn-for-some-n/52226#52226 Answer by domotorp for Does every polyomino tile R^n for some n? domotorp 2011-01-16T10:37:57Z 2011-01-20T08:53:59Z <p>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.</p> <p>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.</p> <p>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.</p> <p>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.</p>