Multiplicidad Uniforme

Sin duda alguna uno de los trabajos más elegantes y sobresalientes es el denominado ``Endomorphisms and Automorphisms of the Shift Dynamical Systems'' publicado por Gustav A. Hedlund en 1969 [Hedlund 69]. El escrito se presenta elegantemente mediante una exposición de dinámica simbólica y sistemas dinámicos de corrimiento. Los análisis de los sistemas dinámicos de corrimiento a través de sus aspectos topológicos y teóricos de medida permite llegar a resultados muy relevantes.

La elegancia del teorema fundamental de estructura hace posible la derivación de numerosos resultados concernientes a las transformaciones de corrimientos conmutativos.

La estructura local relacionada con la estructura global resulta ser una cuestión importante que se presenta en cualquier sistema dinámico en donde la existencia y las propiedades de las transformaciones contínuas conmutan con el grupo de acción. La inducción de un mapeo global a partir de uno local se presenta a través de la definición de un mapeo de bloques (palabras) de símbolos de una longitud específica en símbolos simples y extendiendo este mapeo en una manera natural en secuencias infinitas.

En el análisis de los autómatas celulares lineales reversibles, debemos empezar por conocer las propiedades que cumplen los autómatas sin Jardín del Edén, es decir, donde toda secuencia tenga al menos un ancestro. Relacionado a esta idea, en el trabajo de Hedlund encontramos un concepto fundamental al cual él denomina Multiplicidad Uniforme.

La multiplicidad uniforme en un autómata celular reversible nos dice que cada cadena de estados tiene el mismo número de ancestros que las demás cadenas; y este número es igual al número de nodos del diagrama de de Bruijn.

Se parte de un autómata celular reversible $(K,r,\phi,C_o)$, con las siguientes convensiones:

• $\phi ^{-1}$ es la regla inversa de $\phi$
• A los ancestros de una secuencia de estados $S \in K^*$ los representaremos como ${\phi}^{-1}(S)$
• La evolución de $S \in K^*$ la representaremos como $\phi(S)$
• La cardinalidad de un conjunto $N$ elementos se representará con $\vert N\vert$

En seguida vamos a parafrasear algunos de los resultados más importantes del trabajo de Hedlund [Hedlund 69]. La indicación (Resultado $(m.n)$) en cada uno de los siguientes enunciados indica la sección en que aparece el mismo enunciado en el trabajo original de Hedlund.

Nuestro interés es usar estos resultados dentro del contexto de los autómatas celulares lineales. La relevancia para los casos reversibles estriba en que los siguientes resultados nos indicarán cuales son las propiedades que tienen los autómatas celulares sin Jardín del Edén. El primer resultado nos dá un comportamiento cuantitativo de los ancestros de una cadena y se presenta a contunuación.

Hedlund 1   (Resultado (5.2)) Sea $m$ y $n \in \mathbb{Z}^+$. Si $S \in K^{m}$ cumple que $\vert{\phi}^{-1}(S)\vert=n$ y para todo $s \in K$ se cumple que $\vert{\phi}^{-1}(Ss)\vert \geq n$. Entonces $\vert{\phi}^{-1}(Ss)\vert =n$ para todo $s \in K$.

Prueba: Tomemos a ${\phi}^{-1}(S)=\{A_0,\ldots,A_{n-1}\}={\cal A}$; tomemos a $SK$ como las secuencias formadas al concatenar $S$ con todo elemento de $K$. Si ${\phi }^{-1}(S)={\cal A}$, entonces ${\phi }^{-1}(SK)={\cal A}K$ lo cual cubre todas las posibilidades de ancestros de $SK$.

Para una cadena $As \in {\cal A}K$, su evolución, $\phi(As)$ pertenece a $SK$ si y solo si $A$ es un bloque de longitud $m+2r$ tal que $\phi(A)=S$, es decir, si $A \in {\cal A}$.

Figura 3.3: ${\phi }^{-1}(S)={\cal A}$ y ${\phi }^{-1}(SK)={\cal A}K$

De este modo el número de ancestros de las secuencias $SK$ está dado por la suma de los ancestros de toda posible secuencia $Ss$; es decir:

$$\vert{\phi}^{-1}(SK)\vert =nk=\sum_{s \in K}{\mid {\phi}^{-1}(Ss) \mid }$$ (3.1)

Sabemos por el enunciado que $\vert{\phi}^{-1}(Ss)\vert \geq n$ para cada $s \in K$. Si para cualquier $s \in K$, se cumple que $\vert{\phi }^{-1}(Ss)\vert > n$, se tiene entonces que $\vert{\phi}^{-1}(SK)\vert > nk$ lo cual es una contradicción.

Figura 3.4: Si $\vert{\phi }^{-1}(Ss)\vert > n$ para alguna $s \in K$ no se cumple que $\vert{\phi }^{-1}(SK)\vert = nk$

De aquí concluimos que $\vert{\phi}^{-1}(Ss)\vert =n$ para cada $s \in K$. $\blacksquare$

Lo que indica el resultado anterior es que en un autómata celular lineal reversible, el número de ancestros de cualquier secuencia se mantendrá igual no importando que tanto extendamos la misma. Una cuestión importante ahora, es conocer cual es este número de ancestros, esto se responderá en el siguiente resultado.

Hedlund 2   (Resultado (5.3)) Sea $m$ y $n \in \mathbb{Z}^+$, sea $K$ el conjunto de estados del autómata celular con $\vert K\vert=k$. Si $S \in K^{m}$ cumple que $\vert{\phi}^{-1}(S)\vert=n$ y $\vert{\phi}^{-1}(SES)\vert = n$ para cada $E \in K^{2r}$, entonces $n=k^{2r}$.

Prueba: Definamos los siguientes conjuntos que utilizaremos en la demostración:

$$\begin{array}{rcl} {\phi}^{-1}(S)=\{A_1,\ldots,A_n\}&=&{\cal... ...{\cal E} &=& {K}^{2r} \\ {\cal B} &=& {\cal AA} \end{array}$$

Como cada $A_i \in {\cal A}$ tiene tantos elementos como $m+2r$, cada $B \in {\cal B}$ es de longitud $2m+4r$ y su evolución, $\phi(B)$, es de longitud $2m+2r$.

Ya que $\phi(A_i)=\phi(A_j)=S$, se tiene que $\phi(B)$ es de la forma $SES$; donde $E \in {\cal E}$ aparece en medio de cada evolución de $(A_iA_j)$. Es decir, ${\cal AA} \subseteq \phi^{-1}(S{\cal E}S)$.

Toda evolución de cualquier secuencia $B$ pertenece al conjunto $S{\cal E}S$ sin que falte ningún elemento de ${\cal E}$ pues el mapeo global es sobreyectivo (no existe el Jardín del Edén), en otras palabras, todos los ancestros del conjunto $S{\cal E}S$ están contenidos en el conjunto ${\cal AA}$. Es decir, $\phi^{-1}(S{\cal E}S) \subseteq {\cal AA}$; de aquí llegamos a que:

$$\vert\phi^{-1}(S{\cal E}S)\vert={\cal AA}$$ (3.2)

Figura 3.5: Ancestros de las secuencias $S{\cal E}S$

Dado que $\vert{\cal A}\vert = n$, se tiene que $\vert{\cal AA}\vert = n^2$.

Del enunciado, sabemos que $\vert{\phi}^{-1}(SES)\vert = n$ para cada $E \in {\cal E}$ con $\vert{\cal E}\vert = k^{2r}$. Si tomamos en cuenta todos los ancestros de $S{\cal E}S$ entonces $\vert{\phi}^{-1}(S{\cal E}S)\vert=nk^{2r}$.

Figura 3.6: El total de ancestros de $S{\cal E}S$ es $nk^{2r}$

De este modo llegamos a que $n^2=nk^{2r}$, por lo que $n=k^{2r}$. $\blacksquare$

Lo que este resultado nos aporta es que si el número de ancestros de una secuencia se mantiene para las extensiones de la misma, este número es igual a $k^{2r}$. Haciendo uso de los dos resultados anteriores, hagamos una generalización del comportamiento cuantitativo de los ancestros en un autómata celular lineal reversible.

Hedlund 3   (Resultado (5.4)) En un autómata celular lineal reversible se cumplen dos condiciones:

1. Todas las secuencias tienen el mismo número de ancestros.
2. El número de ancestros de cada secuencia es $k^{2r}$.

Prueba: Para $m$ y $n \in \mathbb{Z}^+$, definamos a ${\cal S}=K^{m}$ como el conjunto de secuencias de longitud $m$. Por el hecho de que el autómata es reversible, el mapeo entre configuraciones es sobreyectivo, por lo que toda secuencia de estados tiene al menos un ancestro.

Tomemos a $n$ como el mínimo número de ancestros que tenga alguna $S \in {\cal S}$. Para dicha secuencia, el valor de $n$ se mantendrá (resultado 1) cumpliendo además que $n=k^{2r}$ (resultado 2).

Todos los posibles ancestros de ${\cal S}$ se encuentran en el conjunto $K^{m+2r}$; el total de número de elementos de este conjunto es $\vert{K}^{m+2r}\vert = {k}^{m+2r}$. Por otro lado, dado que $n$ es el mínimo número de ancestros de toda cadena en ${\cal S}$, y como $\vert{\cal S}\vert = k^m$ , entonces minimamente hay tantos ancestros como $k^{m+n}$ con $n=k^{2r}$.

Si existe alguna cadena en ${\cal S}$ con un número de ancestros mayor que $n$, entonces se cumple que $\vert{\phi}^{-1}({\cal S})\vert > {k}^{m+2r}$ lo cual no puede ser pues no hay mas ancestros que $\vert{K}^{m+2r}\vert = {k}^{m+2r}$. Por lo tanto cada cadena en ${\cal S}$ tiene $n$ ancestros con $n=k^{2r}$. $\blacksquare$

Por los resultados anteriores sabemos entonces cual es el número de ancestros de una secuencia y que este valor es el mismo para todas las demás secuencias de un autómata celular lineal reversible. Hay que señalar que el número de ancestros concuerda con el número de nodos en el diagrama de de Bruijn.