¿Cualquier poliomino es un azulejo de R^n para algún n?

Question

Esta es una pregunta planteada por Adam Chalcraft. La publico aquí porque creo que merece una mayor difusión, y porque quizás alguien ya sepa la respuesta.

A poliomino suele definirse como un conjunto finito de cuadrados unitarios, pegados de canto a canto. Aquí lo generalizo para referirme a un conjunto finito de hipercubos unitarios, pegados de faceta a faceta.

Dado un poliomino $P$ en $\mathbb{R}^m$ Puedo ascensor a un poliomino en un espacio euclidiano de mayor dimensión $\mathbb{R}^{m+n}$ cruzándolo con una unidad $n$ -cubo: el poliomino levantado es sólo $P\times [0,1]^n$ .

Evidentemente, no todos los poliominios azulejan el espacio.

¿Es cierto que dado cualquier poliomino $P$ en $\mathbb{R}^m$ existe alguna $n$ tal que el poliomino levantado $P\times [0,1]^n$ azulejos $\mathbb{R}^{m+n}$ ?

El primer instinto de mucha gente es que los polominos de conexión múltiple (los que tienen "agujeros") no pueden embaldosarse, pero se puede entrar en los agujeros si se eleva a una dimensión suficientemente alta.

Answer 1

Una respuesta positiva a esta pregunta acaba de aparecer en el arXiv: Tiling with arbitrary tiles; Vytautas Gruslys, Imre Leader, Ta Sheng Tan; http://arxiv.org/abs/1505.03697

Answer 2

Aquí demuestro que no importa si consideramos sólo fichas de dominó conectadas o no, ya que hubo mucha discusión al respecto.

Supongamos que el poliomino original, P, es de dimensión d. Construiremos un poliominó conexo de 2d dimensiones, Q, que puede ser embaldosado con P. Claramente, esto demuestra la afirmación, ya que si es imposible embaldosar cualquier espacio con P, también es imposible hacerlo con Q.

Denotemos un ladrillo d dimensional suficientemente grande que contenga a P por R. Tomemos el poliomino P x R de 2d dimensiones, de modo que aquí cada cubo original de P es reemplazado por un ladrillo de 2d, 1 x R. Observemos que P x R está contenido en un ladrillo R x R. Rellena las partes que faltan de este ladrillo R x R con polominos 1 x P. Observa que esto significa que R x P también se llenará por completo. Este poliominó, Q, estará conectado, ya que podemos movernos libremente en cualquier parte de las primeras d coordenadas de R x P y en las últimas d coordenadas de P x R.

Nota: El complemento del conjunto así obtenido es R \P x R \P. Si repetimos esto, se puede conseguir que nuestro poliominó sea arbitrariamente denso, es decir, que llene al menos el 99% de un ladrillo.

Answer 3

@Erich: Ciertamente no es cierto que todo poliomino teja algún hipercuboide. Esta es una forma de ver esto. Considera el $n_1\times\ldots\times n_d$ hipercuboide. Indice de las células por $(x_1,\ldots,x_d)$ donde $0\leq x_i\leq n_i-1$ . Dar la célula $(x_1,\ldots,x_d)$ el valor $t^{x_1+\ldots+x_d}$ , donde $t$ es un indeterminado. Sumado a todo el hipercuboide, esto es $$\prod_{i=1}^d(1+t+\ldots+t^{n_i-1}),$$ por lo que sus raíces complejas están todas en el círculo unitario. Ahora tomemos un poliomino simétrico 1-d, y pongámoslo en el hipercuboide de manera que su valor tenga el grado mínimo en $t$ . Su valor es algún polinomio $p(t)$ . Ahora, dondequiera que pongas el poliominó, su valor es $t^k p(t)$ para algunos $k\geq 0$ . Si se alicata algo con el poliomino, el valor total es $q(t)p(t)$ para algún polinomio $q(t)$ . Así que si puedes embaldosar el hipercuboide, todas las raíces de $q(t)p(t)$ debe estar en el círculo unitario. En particular, todas las raíces de $p(t)$ debe estar en el círculo unitario. Elige un poliominó simétrico 1-d para el que esto sea falso. Por ejemplo, 1101011 (1 es un cuadrado, 0 es un agujero).

Estoy en deuda con Imre Leader por la idea de esta prueba.

Answer 4

@Tim: Gracias por publicar la pregunta.

@All: Estoy permitiendo todas las traslaciones y rotaciones. También estoy permitiendo las reflexiones, pero eso es irrelevante para la pregunta, porque siempre se puede obtener una reflexión rotando en una dimensión superior. No pretendo imponer que un poliominó sea conexo, es sólo una colección finita de cubos unitarios con vértices en $Z^n\subset R^n$ .

Por ejemplo, baldosas "o o" en 1 dimensión, baldosas "oo o" en 1 dimensión (permitiendo reflejos) o 2 (no permitiendo reflejos), baldosas "oo oo" en 2 dimensiones (ejercicio entretenido) y baldosas "oo ooo" en 2 dimensiones (más fácil). No sé la respuesta para "ooo ooo".

Answer 5

Los resultados más conocidos para el embaldosado de rectángulos en 2D se pueden encontrar aquí:

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