número incontable de mosaicos de Penrose

Question

Estoy interesado en el alicatado de Penrose, aunque no soy un experto, así que pido disculpas por adelantado.

Se sabe que el número de tilings de Penrose diferentes es incontable. Esto puede deducirse del método de Bruijn, de inducir estos mosaicos a partir de una sección transversal de un mosaico regular (cúbico) en 5 dimensiones (pero tal vez estoy mezclando aquí entre las dos áreas, ya que no me queda claro del método de Bruijn si el tamaño de los mosaicos en sí varía para cada sección transversal). Sin embargo, en el libro de Martin Gardner " Cifrado de Penrose Tiles a Trapdoor " (o PDF de los dos primeros capítulos ), el autor describe una forma de Conway para demostrar -de otra manera- que el número de tilings de Penrose diferentes es incontable.

Sin embargo, este método no lo tengo nada claro. Aquí está la descripción de Gardner para el método de Conway:

La prueba de Conway de la incontabilidad de los patrones de Penrose (Penrose lo había demostrado antes de una manera diferente) puede resumirse como sigue. En la etiqueta de la cometa un lado del eje de simetría $L$ El otro $R$ (para izquierda y derecha). Haga lo mismo en el dardo, utilizando $l$ y $r$ . Ahora elige un punto al azar en la baldosa. Anota la letra que da su ubicación en el azulejo. Infla el patrón un paso, anota la ubicación del mismo punto en una baldosa de segunda generación y vuelve a registrar la letra. Continuando a través de inflaciones superiores, se genera una secuencia infinita de símbolos que es un etiquetado único del patrón original visto, por así decirlo, desde el punto seleccionado.

[ ] No todas las secuencias posibles de los cuatro símbolos pueden producirse de esta manera, pero se puede demostrar que las que etiquetan diferentes patrones se corresponden en número con el número de puntos de una línea.

¿Cómo induce este método una función biyectiva a los puntos de la recta?

Answer 1

El conjunto de tilings (que llamaré $T$ ) corresponde en número a los puntos de una línea, por lo que esto afirma esencialmente que $\lvert T\rvert=\lvert\mathbb R\rvert=\mathfrak c$ . En lugar de establecer una biyección, también puede establecer dos inyecciones.

Límite superior de la cardinalidad

$\lvert T\rvert\le\lvert\mathbb R\rvert$ es fácil: interpretar $L,R,l,r$ como dígitos $0,1,2,3$ y toda la secuencia infinita como fracción decimal. Dado que el dígito $9$ no se produce, no hay que preocuparse por cosas como $0.99\!\ldots=1$ para saber que toda secuencia infinita corresponde exactamente a un número real. Así que tienes un mapa inyectivo desde $T$ a $[0,1)\subset\mathbb R$ .

Incontabilidad de las secuencias

$\lvert T\rvert\ge\lvert\mathbb R\rvert$ es más difícil. Podrías interpretar los números racionales como fracciones con base $4$ Así, cada dígito correspondería a una de las letras. También podrías hacer el siguiente preprocesamiento:

$$f(x):=\begin{cases} L,g(x) &\text{if } x\in[0,1) \\ R,g(1/x) &\text{if } x\in[1,\infty) \\ l,g(-x) &\text{if } x\in(-1,0) \\ r,g(-1/x)&\text{if } x\in(\infty,-1] \end{cases}$$

Esto mapeará cualquier $x$ a la gama $[0,1]$ que puede utilizarse como entrada para la segunda función $g$ que representa ese número en base $4$ y así se convierte en una secuencia. Se podría escribir $1=0.333\!\ldots_4$ o ajustar la definición de $f$ un poco (por ejemplo, utilizando $1-g(1/x)$ en el segundo caso) para asegurarse de que sólo traduce números del rango $[0,1)$ para que puedas concentrarte en los dígitos después del punto.

Incontabilidad de las etiquetas de puntos

Así que en este punto, tienes una función inyectiva de $\mathbb R$ a secuencias infinitas en estas cuatro letras. Pero ahora tienes un problema técnico:

No todas las secuencias posibles de los cuatro símbolos pueden producirse de esta manera

Hay que averiguar las condiciones exactas de qué secuencias pueden y cuáles no pueden producirse de este modo. Mi opinión es que puedes demostrar que sólo hay contablemente muchas secuencias prohibidas, por lo que las secuencias restantes seguirían siendo incontables.

Incontabilidad de los tilings

Como me recordaba Daniel en un comentario, lo que hemos trabajado hasta ahora (al menos si consigues demostrar la contabilidad de las secuencias que no son tilings) demuestra que hay incontables secuencias que describen un patrón visto desde una baldosa determinada . Pero hay infinitas baldosas de las que se podría etiquetar el patrón y seguiría siendo el mismo patrón que debería contarse una sola vez.

Dos secuencias denotan el mismo patrón si coinciden después de algún punto $k$ . Así, puede generar etiquetas alternativas para el mismo patrón modificando posteriormente los elementos de la secuencia, empezando por el primero. Tienes cuatro opciones para el primer elemento de la secuencia, y para cada uno de ellos cuatro para el segundo, y así sucesivamente. Podría explorar todas las posibles modificaciones de la secuencia en una búsqueda de amplitud, por lo que sólo hay un número contable (es decir $\lvert\mathbb N\rvert=\aleph_0$ ) de estos.

Entonces, ¿por qué eso no rompe la incontabilidad de $T$ ? No estoy seguro de cómo te sientes, pero (al menos por el momento) un argumento contrario me funciona mejor. Supongamos que sólo hubiera un número contable de tilings en $T$ representado por cualquier secuencia adecuada para cada uno. Entonces se podría utilizar el $\mathbb N^2$ iteración: Toma la etiqueta original del primer mosaico, luego la etiqueta original del segundo mosaico seguida de la primera modificación del primer mosaico, luego la etiqueta original del tercer mosaico seguida de la primera modificación del segundo mosaico seguida de la segunda modificación del primer mosaico, y así sucesivamente. Al final se enumerarían todas las etiquetas de puntos, por lo que sólo podría haber $\lvert\mathbb N^2\rvert=\lvert\mathbb N\rvert=\aleph_0$ de estos. Esto es una contradicción con la incontabilidad de las secuencias de etiquetas que mostramos antes.

Ahora que lo pienso, esto sólo muestra $\lvert T\rvert>\aleph_0$ pero se necesitaría la hipótesis del continuo para deducir $\lvert T\rvert=\mathfrak c$ de esto. Así que si alguien tiene una mejor explicación (que todavía funciona en un nivel intuitivo) de por qué $\mathfrak c/\aleph_0=\mathfrak c$ siéntase libre de editar este post, comentar o proporcionar su propia respuesta.

Answer 2

Esta es una bonita declaración general:

Reclamación: Si $T$ es un mosaico repetitivo, aperiódico y FLC, entonces hay un número incontable de mosaicos (hasta la traslación) que son localmente isomorfos a $T$ .

Cualquier mosaico de Penrose $T$ es FLC, aperiódico y repetitivo, y cualquier otro mosaico $T'$ es un mosaico de Penrose si y sólo si $T$ y $T'$ son localmente isomorfas.

Es necesario explicar estos términos.

1. Por un alicatado Me refiero a una cobertura de algún espacio euclidiano $\mathbb{R}^d$ por baldosas, cada una de las cuales es un subconjunto acotado de $\mathbb{R}^d$ y son los cierres de sus interiores, que no se cruzan más que en sus límites.
2. Un mosaico es finitamente localmente complejo o FLC (con respecto a las traslaciones) si, para cualquier radio dado $R$ sólo hay un número finito de $R$ -parches. Por un $R$ -parche Me refiero a un conjunto de baldosas de $T$ dado como precisamente el conjunto de baldosas que intersecan alguna bola de radio $R$ . Deberías poder convencerte fácilmente de que una condición suficiente para la FLC es que las baldosas de $T$ son poligonales, se encuentran cara a cara, y que sólo hay un número finito de parches formados por dos baldosas que se encuentran a lo largo de una cara común (hasta la traslación).
3. Un mosaico es aperiódico aquí, si no existe algún vector no nulo $x$ tal que $T=T+x$ .
4. Un mosaico es repetitivo (con respecto a las traducciones) si, para cualquier $R$ existe alguna $R'$ de manera que cada $R$ -parche, hasta la traducción, se puede encontrar en cada $R'$ - bola. Por supuesto, asumiendo que las baldosas no pueden ser arbitrariamente pequeñas, esto implica fácilmente que el mosaico es FLC. En este caso la repetitividad pide que, además de tener sólo un número finito de $R$ -parches, estos $R$ -también se pueden encontrar parches relativamente densa dentro del mosaico (esta es una bonita noción de "orden" del mosaico: ¡ser repetitivo y aperiódico es especial!).
5. Decimos que $T$ y $T'$ son localmente isomorfo si cada $R$ -parche de $T$ es un $R$ -parche de $T'$ y viceversa. En otras palabras, si usted vive en cualquiera de los dos $T$ o $T'$ entonces no se podría descartar una de ellas utilizando sólo información local a un radio finito dado. Obsérvese que si un mosaico es admitido por algunas reglas locales de emparejamiento, de modo que las baldosas se encuentran de alguna manera acordada, entonces, por supuesto, lo mismo es cierto de cualquier mosaico localmente isomorfo (por lo que si su definición de un mosaico de Penrose es cualquier cosa que pueda ser construida a partir de baldosas de Penrose, entonces está claro que cualquier mosaico localmente isomorfo a un mosaico de Penrose es también un mosaico de Penrose).

Prueba de la reclamación: Dejemos que $T$ que satisfaga las condiciones de la demanda. En primer lugar, elijamos un punto de control en el interior de cada clase de traslación de la baldosa. Sólo consideraremos los mosaicos para los que un punto de control correspondiente a la baldosa central se encuentra en el origen.

Por supuesto, cualquier mosaico localmente isomorfo corresponde a alguna secuencia de $1$ -centrado en el origen, seguido de un $2$ -centrado en el origen, seguido de ..., donde el $n$ -centrada en el origen es una extensión de la $(n-1)$ -parche. A la inversa, dada dicha secuencia, no es muy difícil ver que debe ser localmente isomorfa a $T$ (por repetitividad, cada subparcela finita de $T$ debe encontrarse en el mosaico definido por dicha secuencia). Contemos el número de tales secuencias.

Supongamos que para cada $n$ -parche $P$ existen al menos dos formas distintas de extenderlo a algún $(n+c_P)$ -parche, para algunos $c_P>0$ . Dado que sólo hay un número finito de $n$ -por FLC, existen al menos dos formas distintas de ampliar cualquier $n$ -parche a un $(n+c_n)$ -parche, donde $c_n>0$ es sólo el máximo de la $c_P$ que se extienden sobre $n$ -parches $P$ . Vemos que el número de secuencias es al menos tan grande como el conjunto de secuencias contables sobre un conjunto de dos elementos, y $|2^{\mathbb{N}}|$ es incontable. Obsérvese que sólo hay un número contable de puntos de control en cualquier mosaico dado, por lo que el número de mosaicos que se toman hasta la traslación debe seguir siendo incontable.

Así que vemos que sólo tenemos que demostrar que cualquier $n$ -parche de $P$ tiene al menos dos extensiones distintas. Supongamos que no. Entonces existe alguna $P$ que sólo puede ampliarse de alguna manera única. Por repetitividad, existen al menos dos puntos de control distintos $x$ y $y$ en $T$ cuyo $R$ -los parches son traducciones de $P$ . Pero como $P$ sólo puede extenderse de forma única, debemos tener que $T-x$ y $T-y$ son iguales, por lo que $T = T + (y-x)$ , lo que contradice la aperiodicidad.

---

Permítanme anotar un par de cosas después de esa prueba. En primer lugar, por supuesto, la aperiodicidad es necesaria para tener un número incontable de tilings localmente isomórficos. Lo que parece ver de la prueba es que, de hecho, sólo necesitamos la condición ligeramente más fuerte (llamémosla (C)) de que toda clase de traslación de parche finito tiene al menos dos extensiones distintas. En realidad, esto no bastante se desprende de esta prueba, porque una secuencia consistente de parches del mosaico no necesita ser localmente isomorfa al original (pero será "localmente derivable" de él: todos sus parches finitos son parches finitos de $T$ ). Así que sustituir repetitivo por (C) y localmente isomorfo por localmente derivable sigue permitiendo la misma demostración sencilla.

Como ejemplo de un mosaico aperiódico que no satisface (C), tomemos un mosaico cuadrado periódico, pero coloreemos un único cuadrado de forma diferente a todos los demás (o añadamos una "muesca" a éste, si queremos forzarlo todo geométricamente). Entonces este mosaico es FLC y aperiódico pero no satisface (C). Y, por supuesto, sólo hay un número contable de mosaicos que son localmente isomorfos (o incluso derivables) a él.

[Edición: Supongo que sólo he demostrado que hay al menos $|2^{\mathbb{N}}| = |\mathbb{R}|$ clases de traslación de tilings en la prueba anterior. Pero deberías ser capaz de ver fácilmente que sólo puede haber como máximo $|\mathbb{N}^{\mathbb{N}}| = |\mathbb{R}|$ . En efecto, un mosaico localmente isomorfo con punto de control en el origen se describe mediante una secuencia finita de elecciones de centrales $n$ -parche, con $n \in \mathbb{N}$ .]

Por último, permítanme señalar que los tilings de Penrose satisfacen las condiciones de la reivindicación. Esto se deduce fácilmente de su descripción como mosaico de sustitución (o jerárquico), o como mosaico de corte y proyección.

Answer 3

Antecedentes

Bien, lo primero que necesitamos aquí, que en realidad es una propiedad común, pero a veces difícil de demostrar, para un mosaico de sustitución, es que la sustitución (o regla de expansión) sea reconocible . ¿Qué significa "reconocible"? Significa que la sustitución tiene una inversa - esto se puede precisar si colocamos una métrica en el espacio de todos los tilings (Ver mi respuesta a esta pregunta ) - pero para nuestros propósitos diremos simplemente que un mosaico reconocible es un mosaico en el que hay una manera de tomar un mosaico, eliminar algunas aristas y desinflar de manera que volvamos a tener un mosaico por el mismo conjunto de prototipos, y si componemos este proceso con la sustitución entonces actúa como la identidad en el mosaico.

¿Qué es lo que nos proporciona el reconocimiento? Bueno, significa que si tenemos un mosaico $\mathcal{T}$ y elegimos algún azulejo $T$ en $\mathcal{T}$ , existe una forma bien definida, lo que se conoce como, $1$ - supertile $T_1$ que contiene $T=T_0$ y porque podemos continuar el proceso, también un $2$ -supertil $T_2$ , $3$ -supertil $T_3$ etc. El $1$ -supertile es sólo el nuevo azulejo expandido que $T$ es un subconjunto de cuando eliminamos las aristas durante el proceso de sustitución inversa.

Que los tilings de Penrose sean reconocibles es un problema no trivial que requiere demostración. Puede haber una forma elemental que sea especial para los mosaicos de Penrose, pero también hay un teorema de Mossé, y generalizado por Solomyak $^{[1]}$ que dice que cualquier mosaico de sustitución primitiva, aperiódico y localmente finito de $\mathbb{R}^n$ es reconocible (los tilings de Penrose satisfacen estas propiedades).

La prueba

Ahora que sabemos que cada baldosa $T$ en un mosaico de Penrose $\mathcal{T}$ tiene una secuencia bien definida de $n$ -supertiles $T_n$ podemos asociar a cada par $(\mathcal{T},T)$ esa secuencia. La llamaremos $s(\mathcal{T},T)$ . Lo primero que tenemos que demostrar es que para todo $T,T'\in\mathcal{T}$ tenemos que existe un $k\geq 0$ tal que $$\sigma^k(s(\mathcal{T},T))=\sigma^k(s(\mathcal{T},T'))$$ donde aquí $\sigma(a,b,c,d,\ldots)=(b,c,d,\ldots)$ es la función de desplazamiento en las secuencias. Esto es fácil de ver porque si $T$ y $T'$ son baldosas en un mosaico fijo de Penrose $\mathcal{T}$ entonces ambos están contenidos en alguna bola $B$ en el avión. Afirmo (y usted debería probar) que $B$ está totalmente contenida en algún $k$ -supertil $\hat{T}$ . De la reconocibilidad se deduce que $T_{k}=\hat{T}=T'_{k}$ y así $T_l=T'_l$ para todos $l\geq k$ Por lo tanto $\sigma^k(s(\mathcal{T},T))=\sigma^k(s(\mathcal{T},T'))$ .

Lo siguiente que tenemos que averiguar es cuándo una secuencia $s$ está asociado a un mosaico de Penrose. Como se ha comentado en El documento de Soljanin $^{[2]}$ Si asignamos a una baldosa el símbolo $0$ y el otro el símbolo $1$ entonces se puede demostrar que las únicas secuencias admisibles (las asociadas a un mosaico de Penrose) son las que no tienen la subcadena $11$ que aparecen en la secuencia. Llamemos al conjunto de secuencias admisibles $A=\{s\mid 11 \mbox{ does not appear in }s\}$ .

Una pregunta no trivial es, dada una secuencia admisible, ¿es su mosaico de Penrose asociado único? La respuesta es sí, y la prueba es bastante obvia. Una secuencia admisible te dice exactamente cómo colocar las baldosas para construir tu mosaico. Es esencialmente un conjunto de instrucciones para construir un mosaico de Penrose. La baldosa $T_0$ es lo que se coloca en el origen, $T_1$ es el $1$ -supertil que se corta y se extiende lejos de $T_0$ y así sucesivamente. La advertencia aquí es que es posible que estos supertiles sólo se extiendan en una dirección y no cubran todo el plano. No voy a entrar en detalles sobre por qué esto no es un problema, pero sólo hay que tener en cuenta que siempre podemos solucionar este problema utilizando una técnica conocida como collaring (Ver El documento de Anderson y Putnam $^{[3]}$ para más detalles).

Entonces, tenemos una biyección bien definida $A\to\{(\mathcal{T},T) \mid \mathcal{T} \mbox{ is a penrose tiling}, T\in \mathcal{T}\}$ . De nuestra discusión sobre la elección de diferentes baldosas como "baldosa semilla $T_0$ para un mosaico específico, entonces también obtenemos una biyección $A/{\sim}\to\{\mathcal{T} \mid \mathcal{T}\mbox{ is a Penrose tiling}\}$ donde dos secuencias $s,s'$ están relacionados por $\sim$ aquí si existe un $k$ tal que $\sigma^k(s)=\sigma^k (s')$ Así que $A/{\sim}$ es el conjunto de clases de secuencias admisibles eventualmente iguales.

Argumento del recuento

Reclamación: $A$ es incontable.

Prueba: Dejemos que $s$ estar en $A$ (y también sólo para hacer la vida más fácil asumir que no hay $k$ tal que $\sigma^k(s)\neq 000\ldots$ - al final esto sólo da cuenta de una única clase de equivalencia por lo que podemos ignorarlo). A continuación, $s$ tiene una secuencia asociada $d(s)$ de números naturales positivos $n_0,n_1,n_2,\ldots$ correspondiente al número de $0$ s que se producen entre el $1$ s que aparecen en $s$ . Por ejemplo, si $$s=00100010010100001\ldots$$ entonces $$d(s)=(2,3,2,1,4,\ldots).$$ Si $s$ comienza con un $1$ entonces establecemos $n_0=0$ . Está claro que $d(s)$ determina completamente $s$ y toda secuencia posible de números naturales positivos está asociada a una $s$ . El conjunto de todas las secuencias de naturales positivos es incontable, y también lo debe ser la secuencia de secuencias admisibles $A$ .

Reclamación: $A/{\sim}$ es incontable.

Prueba: Dejemos que $s$ representan una clase de equivalencia en $A/{\sim}$ . Sea $F$ sea el conjunto de todas las cadenas finitas de $0$ s y $1$ s. Existe una función inyectiva $[s]_{\sim}\to F$ dada por la asignación a $s'\in[s]_{\sim}$ la subcadena inicial más corta que se puede sustituir en $s'$ para recuperar la secuencia $s$ . Como $F$ es contable, se deduce que $[s]_{\sim}$ es contable para todo $s\in A$ .

Ahora, supongamos que $A/{\sim}$ no es incontable, entonces es contable y por tanto $A$ puede escribirse como una unión disjunta contable de conjuntos contables. Esto implicaría que $A$ es contable, lo que contradice la afirmación anterior. De ello se desprende que $A/{\sim}$ debe ser incontable.

Conclusión: Como corolario concluimos que $\{\mathcal{T} \mid \mathcal{T}\mbox{ is a Penrose tiling}\}$ es incontable.

---

$[1]$ B. Solomyak. La no periodicidad implica una composición única para los tilings autosimilares traslacionales finitos. Computación Discreta Geom. 20 (1998), 265-279.

$[2]$ E. Soljanin. Escribir secuencias en el plano. IEEE Trans. Inf. Thy. 48 (2002), 1344-1354

$[3]$ J. E. Anderson e I. F. Putnam. Invariantes topológicos para los tilings de sustitución y sus asociados $C^*$ -algebras. Teoría Ergódica Dynam. Systems, 18 (3) (1998), 509-537.