Story Transcript
Universidad Nacional de Salta Facultad de Ciencias Exactas Departamento de Matemática
DINÁMICA SIMBÓLICA APUNTES DE CÁTEDRA NOVIEMBRE DE 2016
JORGE YAZLLE
CAMILO JADUR
Índice general Capítulo 1.
ESPACIOS SHIFT
1
1.
De niciones básicas
2.
Full shifts
1
3.
Los Espacios Shift
3
4.
Lenguajes
5
5.
Shifts de bloques
8
6.
Códigos de ventana deslizante
Capítulo 2.
1
10
SHIFTS DE TIPO FINITO
19
1.
Restricciones de tipo nito
19
2.
Grafos y sus shifts
22
3.
Representación de shifts de tipo nito por medio de grafos
27
4.
Desdoblamiento de estados
30
Capítulo 3. 1.
SHIFTS SÓFICOS
37
Presentaciones de shifts só cos
Capítulo 4.
37
ASPECTOS TOPOLOGICOS Y DINAMICOS DE LOS ESPACIOS SHIFT Z
A
40
1.
Una métrica para
2.
Sucesiones
42
3.
Cilindros. Conexidad
44
4.
Continuidad
45
5.
Sistemas dinámicos
47
Capítulo 5.
ENTROPÍA
40
50
1.
De nición y propiedades básicas
50
2.
Cálculo de la entropía de shifts só cos irreducibles
52
3.
Los puntos períodicos y la entropía
55
4.
Cálculo de la entropía de shifts só cos
57
Capítulo 6.
CÓDIGOS DE ESTADOS FINITOS
61
1.
Coloreo de rutas y presentaciones cerrantes a derecha
2.
Códigos de estados nitos
66
3.
Autovectores aproximados
67
4.
Construcción de códigos de estados nitos
71
0
61
Capítulo 1
ESPACIOS SHIFT 1. Un
letras.
De niciones básicas
alfabeto es un conjunto nito, Un bloque, o palabra, sobre
cuyos elementos se denominan un alfabeto
A
símbolos,
o también
es una sucesión nita (posiblemente
A. Formalmente, una palabra u sobre A es una función u del conjunto {x ∈ N : 1 ≤ x ≤ n} en A (para algún entero n ≥ 0). En el caso n = 0, se tiene la función vacía, o sucesión vacía, que llamaremos palabra vacía y denotaremos por ε. La longitud (o largo, o tamaño) de la palabra es n, es decir, la cantidad de términos de la sucesión, y se denota por |u|. La palabra vacía tiene largo 0. Para una palabra no vacía u, el k -ésimo término de la sucesión se denota, como es costumbre, mediante uk . Entonces, una palabra no vacía de largo n sobre A es u1 u2 · · · un , con ui ∈ A para todo i ∈ {1, . . . , n}. Un bloque de longitud n se llama un n-bloque. Dos palabras u y v son iguales si tienen el mismo largo n y, para todo j entre 1 y n, es uj = vj . n El conjunto de todas las palabras de largo n sobre un alfabeto A se designa por A , y el S ∞ n ∗ ∗ conjunto de todas las palabras sobre A se designa por A . Es decir, A = n=0 A . Notar n ∗ que, para todo n ≥ 0, A es un conjunto nito, en tanto que A es un conjunto que tiene una vacía) de letras de
cantidad in nita de elementos. Un alfabeto que a menudo usaremos es
y las palabras que sobre él pueden 0 1 . Tenemos que, en este caso, es A = {ε}, A = {000, 001, 010, 011, 100, 101, 110, 111}, etc. Además, A∗ =
sucesiones binarias
formarse se llaman {0, 1}, A2 = {00, 01, 10, 11},
A3 =
A = {0, 1},
{ε, 0, 1, 00, 01, 10, 11, . . .}. Sea u un bloque. Un subbloque (o subpalabra) i ≥ 1 tal que ∀k ∈ Z, 1 ≤ k ≤ |w| ⇒ wk = ui+k−1 .
de
u
es una palabra
w
tal que existe
De la de nición, se desprende que la
u = u1 · · · un es un n-bloque no vacío, sus subpalabras no vacías son de la forma ui · · · uj , en donde i, j son enteros tales que 1 ≤ i ≤ j ≤ n. Si w es subbloque de u, escribimos w v u, y decimos que w ocurre en u. Obviamente, w v u ⇒ |w| ≤ |u|. Si u y v son dos bloques sobre A, la concatenación de u y v es la nueva palabra que se obtiene al escribir los símbolos de u y, a continuación, los de v , sin ningún signo especial intermedio. La concatenación de u y v se escribe uv . Notar que, en general, uv 6= vu. Es directo ver que |uv| = |u|+|v|. De manera análoga, la concatenación de tres o más bloques es la palabra
palabra vacía es subbloque de cualquier palabra, y que si
que se obtiene de escribir los respectivos símbolos consecutivamente. La concatenación de un n bloque u consigo mismo una cantidad n de veces se designa por u . Formalmente:
n
u = Por ejemplo,
(01)3 = 010101,
Se cumple que para todo (um )n = umn .
ε uun−1
A,
si
n=0 n>0
013 = 0111. ∗ bloque u ∈ A y enteros y
2. Dado un alfabeto
si
se denomina
conjunto de todas las funciones de
Z
en
no negativos
m
y
n,
y
Full shifts
full shift sobre el alfabeto A, A.
um un = um+n
es
El full shift sobre 1
A
o
full A-shift,
se denota por
A
Z
.
al
2
1. ESPACIOS SHIFT
Una función de
Z
A
en
no es más que una sucesión bi-in nita de símbolos de
A,
que puede
escribirse así:
x = (xn )n∈Z = · · · x−2 x−1 x0 x1 x2 x3 · · · A = {0, 1} es la que tiene 0 en sus términos · · · 01010101010 · · · . la coordenada 0 de x, escribiremos un signo de puntuación
Un ejemplo de tales sucesiones bi-in nitas para impares, y
1
en sus pares, es decir,
Para tener una idea de cuál es a la izquierda de
x0 ,
así:
. . . x−2 x−1 .x0 x1 x2 . . . En nuestro ejemplo anterior, escribimos
· · · 010.10101010 · · · .
Debe quedar claro que el signo de puntuación no es un elemento del alfabeto, ni un término de la sucesión
x;
es sólo una manera de representar a
una referencia a sus posiciones. Z Los elementos de A reciben el nombre de
xi = yi para todo entero i. AZ no contiene palabras,
Notar que
de modo de tener
puntos. Cada punto es, entonces, una sucesión
bi-in nita, o tirilla bi-in nita, de símbolos. Dos puntos y sólo si,
· · · x−2 x−1 x0 x1 x2 · · ·
x = (xi )i∈Z
sino sucesiones bi-in nitas.
e
y = (yi )i∈Z
A∗
y
AZ
son iguales si,
no tienen ningún
elemento en común.
x = · · · x−2 x−1 x0 x1 x2 x3 · · · ∈ AZ , designamos por x[i,j] a la sucesión ( nita) de los símbolos de x que van desde la coordenada i hasta la coordenada j , ambas inclusive. Es decir, x[i,j] = xi xi+1 · · · xj−1 xj . Adoptamos la convención de que para i > j , x[i,j] = ε (formalmente, x[i,j] es la función u con dominio {n ∈ Z : 1 ≤ n ≤ j − i + 1} y codominio A tal que un = xi+n−1 ). Denotamos por x[i,∞) a la sucesión in nita a derecha xi xi+1 · · · , mientras que x(−∞,i] ∗ Z es la sucesión in nita a izquierda · · · xi−1 xi . Dados u ∈ A y x ∈ A , decimos que u ocurre en x, o también que u es palabra o bloque de x (y lo escribimos u v x) si existen enteros i, j tales que x[i,j] = u. Notar que la palabra vacía ocurre en cualquier punto del full shift: ∀x ∈ AZ , x[1,0] = ε. El (2k + 1)-bloque central de x es x[−k,k] . ∗ ∞ Z Para un bloque no vacío u = u1 · · · un ∈ A − {ε}, designamos por u al punto x ∈ A que resulta de la concatenación in nita (hacia ambos lados) de la palabra u consigo misma de modo que ∀i ∈ {0, . . . , n − 1} , xi = ui+1 : Dado
u∞ = · · · uuuuu.uuuuuu · · · = · · · u1 · · · un u1 · · · un .u1 · · · un u1 · · · un · · · 0 es u1 . Por ejemplo, si u = 011, entonces u∞ = · · · 011011.011011011 · · · , · · · 0110110.11011011 · · · = (110)∞ .
Obsérvese que la coordenada que no es el mismo que
2.1.
La transformación shift.
i de una sucesión (xi )i∈Z representa el valor de la sucesión en el minuto i.
Se puede pensar en el subíndice
como indicador del tiempo, de modo que
xi
El paso de una unidad de tiempo equivale entonces a desplazar (shift) cada coordenada de Z Z la sucesión un lugar hacia la izquierda. Esto de ne una transormación natural de A en A , llamada
transformación shift y denotada por σ , del siguiente modo: σ : AZ → AZ x 7→ y = σ (x)
con
yi = xi+1
x = (00111)∞ = · · · 00111.0011100111 · · · , entonces σ (x) = · · · 001110.011100111 · · · notación standard en teoría de sistemas dinámicos, usaremos σx para σ (x), y
Por ejemplo, si Conforme a
σxi
(σ (x))i . es una función biyectiva. Su inversa,
para
σ −1 , desplaza cada posición de una sucesión un lugar k hacia la derecha. Si k es un entero positivo, σ designa a la composición de σ consigo misma k veces, y produce el efecto de desplazar todas las coordenadas de una sucesión k lugares a la k −k −1 izquierda (σ xi = xi+k ), mientras que σ es la composición de σ consigo misma k veces, −k 0 y mueve k lugares a la derecha (σ xi = xi−k ). σ se de ne como la función identidad. Se k puede resumir todo diciendo que σ xi = xi+k , sea k positivo o no. Nótese que, en consecuencia, σ
3. LOS ESPACIOS SHIFT
xi = σ k xi−k . k ∈ Z.
Por ser composición de biyecciones,
Proposición 1.1.
σk
3
es una biyección de
AZ ,
para cualquier
Sean u ∈ A∗ , x ∈ AZ y k ∈ Z; se tiene que u v x ⇔ u v σ k x.
Demostración. Puesto que
x[i,j] = σ k x[i−k,j−k] ,
se tiene que
u v x ⇔ ∃i, j ∈ Z : u = x[i,j] = σ k x[i−k,j−k] ⇔ u v σ k x n ≥ 1 tal que σ n x = x, se llama punto periódico para σ , y, en ese caso, n es un período de x. Para el caso particular en que n = 1 (es decir, σx = x), x se llama punto jo para σ . Todo punto periódico es de la forma u∞ , con u ∈ A∗ . ∞ En particular, un punto jo para σ es de la forma a , para algún a ∈ A. Si x es periódico de período n, también es periódico de período 2n, 3n, . . . El menor de los números positivos k tales k que σ x = x se llama período mínimo de x. Un punto
x ∈ AZ
para el cual existe un
Sea x un punto periódico para σ de período mínimo n0 . Entonces, para cualquier entero positivo k , x tiene período kn0 . Lema 1.2.
k . Para k = 1, se cumple pues n0 es un período de σ (k+1)n0 x = σ n0 σ kn0 x = σ n0 x = x, por lo que (k + 1) n0 es
Demostración. Por inducción sobre
x.
Supongamos que
un período de
σ kn0 x = x.
Es
x.
Proposición 1.3. Sea x un punto periódico para σ de período mínimo n0 . x tiene período n si, y sólo si, n es múltiplo de n0 .
tiene período n. Sean n0 . Por el Lema 1.2, vemos que x = σ r σ kn0 x =
Demostración. Para la ida, supongamos que
n = kn0 + r con 0 ≤ r < r < n0 debe ser r = 0, y entonces n
es múltiplo de
x
k y r tales que σ r x, pero como
n0 .
La vuelta es el contenido del Lema 1.2.
3.
Los Espacios Shift
∗ una colección de bloques sobre un alfabeto A, es decir, F ⊆ A . Z Designamos por XF al subconjunto de A formado por todos aquellos puntos en los que Definición 1.4. Sea
F
no
ocurre ningún bloque de F . Es decir, XF =
x ∈ AZ : ∀f ∈ F, f
=
x ∈ AZ : ∀i, j ∈ Z, x[i,j] ∈ /F
no ocurre en
x
x∈ / XF ⇔ ∃i, j ∈ Z : x[i,j] ∈ F . continuación, algunos ejemplos sobre A = {0, 1}:
Obsérvese que A
Ejemplo 1.5. Si
F1 = ∅,
es
XF1 = AZ ,
pues trivialmente se tiene que
Z, x[i,j] ∈ / F1 . Ejemplo 1.6. Si
F2 = {0, 1},
es
Ejemplo 1.7. Si
F3 = {ε},
XF3 = ∅,
Ejemplo 1.8. Si
F4 = {0}, es XF4 = {1∞ }, pues cualquier que xi = 0, y entonces x[i,i] ∈ F4 .
una coordenada
i
tal
Ejemplo 1.9. Si
xi = 0,
es
xi+1 = 0
o
es
XF2 = ∅,
∀x ∈ AZ , x[0,0] ∈ F2 .
∀x ∈ AZ , x[1,0] = ε ∈ F3 .
pues
pues
∀x ∈ AZ , ∀i, j ∈
∞
F5 = {00, 01}, es XF5 = {1 } pues si un xi+1 = 1, y en cualquier caso x[i,i+1] ∈ F5 .
punto
x
distinto de
1∞
posee
punto
x
tiene una coordenada
(01)∞ , (010)∞ , (00100010)∞ , · · · 0000.10000 · · · , · · · 00100000.00000 · · · , · · · 00001000100101.01010010001000010000010 · · · . XF6 Z es precisamente el conjunto de puntos de A que no contienen dos 1 consecutivos. Este espacio shift es conocido como el shift de la razón de oro. Ejemplo 1.10. Si
F6 = {11},
algunos puntos de
XF6
son
4
1. ESPACIOS SHIFT
Ejemplo 1.11. Si
F7 = {1n : n ≥ 2},
Ejemplo 1.12. Si
F8 = A∗ ,
Ejemplo 1.13. Si
F9 = {102n+1 1 : n ∈ N}, XF9
es
es
X F7 = X F6 .
XF8 = ∅.
es precisamente el conjunto de puntos de
A
tales que entre dos ocurrencias consecutivas de 1 hay una cantidad par de 0 (es decir, Z n aquellos puntos x ∈ A tales que 10 1 v x ⇒ n es par). Este espacio shift es conocido como el
Z
shift par.
Proposición 1.14.
1. 2. 3.
Sean F y F 0 subconjuntos de A∗ . Entonces:
XF ∪F 0 = XF ∩ XF 0 XF ∩F 0 ⊇ XF ∪ XF 0 Si F ⊆ F 0 , entonces XF ⊇ XF 0 .
Demostración. Para la primera aserción,
x ∈ XF ∩ XF 0 ⇔ ∀u v x, u ∈ / F ∧u ∈ / F0 ⇔
∀u v x, u ∈ / F ∪ F 0 ⇔ x ∈ XF ∪F 0 . Para la segunda, si x ∈ XF y u v x, se tiene que u ∈ / F , por lo que u ∈ / F ∩ F 0 , y entonces x ∈ XF ∩F 0 ; de aquí que XF ⊆ XF ∩F 0 . Análogamente, XF 0 ⊆ XF ∩F 0 , y, de las dos contenciones anteriores, es XF ∪ XF 0 ⊆ XF ∩F 0 . Para la tercera, si x ∈ XF 0 y u v x, u ∈ / F 0 ⊇ F , y entonces u ∈ / F . Por lo tanto, x ∈ XF . F ⊆ A∗ ,
Z de la de nición de XF resulta claro que XF ⊆ A . Ahora bien, dado un Z ∗ subconjunto cualquiera X de A , ¾existirá siempre un F ⊆ A tal que X = XF ? Resulta que Dado
no siempre, y aquellos
X
para los que sí existe tal
F
reciben un nombre especial y son objeto
de nuestro estudio. Definición 1.15. Un
existe un
∗
F ⊆A
Pensamos en
sobre el alfabeto
A
es un conjunto
X ⊆ AZ
tal que
X = XF .
tal que
F
espacio shift
como en un conjunto de
bloques prohibidos para X .
Antes de ver ejemplos de subconjuntos de
AZ
que son o no espacios shift, veamos una
propiedad importante que cumplen los conjuntos que sí lo son. Proposición 1.16.
pertenece a X .
Sean X un espacio shift, x ∈ X y k ∈ Z. Entonces σ k x también
Demostración. Sea
k
F
tal que
X = XF .
Consideremos un bloque arbitrario
u
que ocurra
σ x. Por la Proposición 1.1, tenemos que también u ocurre en x, luego u no puede pertenecer F . Como u era un bloque arbitrario de σ k x, vemos que ningún bloque de σ k x está en F , por k k lo que σ x ∈ XF , es decir, σ x ∈ X .
en a
Sea X ⊆ AZ , y supongamos que existen x ∈ X y k ∈ Z tales que σ x∈ / X . Entonces X no es un espacio shift. Corolario 1.17.
k
Corolario 1.18.
Si X es un espacio shift y k ∈ Z, entonces σ k (X) = X .
y ∈ σ k (X), existe x ∈ X tal que y = σ k (x), que, de acuerdo a la k −k Proposición 1.16, está en X ; luego σ (X) ⊆ X . Esto también muestra que σ (X) ⊆ X , por k −k k k k −k lo que σ σ (X) ⊆ σ (X); pero como σ es biyectiva, se tiene que σ σ (X) = X , y k entonces tenemos que X ⊆ σ (X). Demostración. Si
La propiedad de ser
σ (X) = X
se llama
invariancia por shift
o
shift invariancia.
Los corolarios anteriores dicen que todo espacio shift es shift invariante, o, igualmente, que un conjunto que no es shift invariante no puede ser un espacio shift. Por ejemplo, el conjunto ∞ ∞ unitario X = {(01) } no es un espacio shift pues σ (01) = (10)∞ ∈ / X . Sin embargo, la shift invariancia de un conjunto no garantiza que éste sea un espacio shift.
4. LENGUAJES
5
{0, 1} en las que hay exactamente una coordenada 1 y el resto son todas 0. Es decir, X = (xi )i∈Z : ∃k ∈ Z : (xk = 1 ∧ ∀i 6= Si x ∈ X , σx también pertenece a X , es decir, X es invariante por shift. Sin embargo, veamos que X no es espacio shift. Para arribar a una contradicción, supongamos que lo fuera. k Quiere decir que existiría un F tal que X = XF . Debe ocurrir que ∀k ≥ 1, 0 ∈ / F (pues k ∞ ∀k ≥ 1, 0 v · · · 000000.1000000 · · · ∈ X ). Pero entonces 0 pertenecería a XF , con lo cual 0∞ ∈ X , que contradice la de nición de X . La contradicción proviene de suponer la existencia del conjunto F , es decir, de suponer que X es un espacio shift. Ejemplo 1.19. Sea
X
el conjunto de todas las sucesiones bi-in nitas sobre
Ejemplo 1.20. El conjunto vacío y el full shift
{0, 1}Z
son espacios shift, según se mostró
en los ejemplos 1.5 y 1.6. En general, cualquier full shift es un espacio shift. Los conjuntos y
XF6
X F4
de los ejemplos 1.8 y 1.10 son también espacios shift. Los ejemplos 1.8 y 1.9 muestran
que un mismo espacio shift puede ser descripto a través de diferentes colecciones de bloques
prohibidos. La restricción de
σ
a un espacio shift
X
será denotada por
σX .
En vistas del Corolario
es una biyección de X en X . Las de niciones anteriormente dadas para puntos jos y Z periódicos de A para σ son igualmente aplicables a un espacio shift X y su respectiva σX . 1.18,
σX
El siguiente resultado será útil en lo sucesivo, pues a rma que el conjunto de bloques prohibidos para un espacio shift puede verse como constituido por palabras de longitud al menos donde
N
N,
es cualquier entero positivo.
Sean X un espacio shift y N un entero positivo. Entonces, existe F ⊆ A tal que todo bloque en F tiene longitud al menos N , y X = XF . Proposición 1.21.
∗
Demostración. Siendo
X
un espacio shift, hay un
F1 = w ∈ AN : ∃u ∈ F 0 : u v w
F 0 ⊆ A∗
tal que
X = XF 0 .
Hagamos
F2 = {u ∈ F 0 : |u| > N }
F = F1 ∪ F 2 Es decir,
F
consta de todas las palabras de
aquellas palabras de largo Observar que que
N
F0
que tengan largo mayor que
N,
más todas F 0.
sobre el alfabeto que contengan una subpalabra que esté en
F1 ∩ F2 = ∅. Es directo ver que todo bloque en F
tiene largo al menos
N . Veamos
X = XF :
x∈ / XF
⇔ ∃i, j ∈ Z : x[i,j] ∈ F ⇔ ∃i, j ∈ Z : x[i,j] ∈ F1 ∨ x[i,j] ∈ F2 ⇔ ∃i, j ∈ Z : j − i + 1 = N ∧ ∃u ∈ F 0 : u v x[i,j] ∨ j − i + 1 > N ∧ x[i,j] ∈ F 0 ⇔ ∃u ∈ F 0 : u v x ⇔ x∈ / XF 0 = X
4. Definición 1.22. Un
Lenguajes
lenguaje sobre un alfabeto A es cualquier subconjunto de A∗ .
c ∗ es un lenguaje, designaremos por L a su complemento en A , es decir, el ∗ conjunto de todas las palabras de A que no pertenecen a L. Z Si X es un subconjunto de A (no necesariamente un espacio shift) y n un entero no En adelante, si
L
negativo, denotamos por de
X,
Bn (X)
al conjunto de bloques de longitud
n
que ocurren en puntos
es decir,
Bn (X) = {u ∈ An : ∃x ∈ X : u v x} Z n Por ejemplo, si X = A , entonces Bn (X) es precisamente A . Si X = X{11} , B1 (X) = {0, 1}, B2 (X) = {00, 01, 10}, B3 (X) = {000, 001, 010, 100, 101}.
es
B0 (X) = {ε},
6
1. ESPACIOS SHIFT
X = XF y f ∈ F , no puede haber un n tal que f ∈ Bn (X). Es decir, ∀n ∈ N, F ∩ Bn (X) = ∅. Sin embargo, bien puede ocurrir que un bloque de longitud n que no esté en F tampoco esté en Bn (X). Nótese que si
Definición 1.23. Sea
X
un subconjunto de
AZ
. El
lenguaje de X , denotado por B (X),
es el conjunto de todos los bloques que ocurren en puntos de
B (X) = {u ∈ A∗ : ∃x ∈ X : u v x} =
X. ∞ [
En otras palabras,
Bn (X)
n=0 Ejemplo 1.24.
B X{11} = {ε, 0, 1, 00, 01, 10, 000, 001, 010, 100, 101, . . .}.
Ejemplo 1.25. Sean
X1 = {(01)∞ , (10)∞ }
y
X2 = {(01)∞ };
se tiene que
B (X1 ) = {ε, 0, 1, 01, 10, 010, 101, 0101, 1010, . . .} = B (X2 ) a pesar de que
X1 6= X2 ;
notar, sin embargo, que
X1
es un espacio shift, mientras que
X2
no lo
es. Así como
F
se interpretaba como un conjunto de bloques prohibidos para
conjunto de bloques permitidos para shift
X,
decimos de él que
permitido en X .
XF .
XF , B (XF )
es el
Cuando un bloque está en el lenguaje de un espacio
ocurre en X , o que aparece en X , o que está en X , o que está X = XF , entonces F ∩ B (X) = ∅. esté en F tampoco esté en B (X).
Una consideración análoga a la de más arriba: si embargo, bien puede ocurrir que un bloque que no
Sin
Si un bloque está en el lenguaje de un espacio shift, la de nición nos dice que hay un punto del espacio en el cual, en determinada posición, encontramos ese bloque. Sin embargo, usando shift invariancia, podemos ver que el bloque aparece en algún punto del espacio en la coordenada que uno quiera. Proposición 1.26. Sean X un espacio shift, u un bloque en B (X), y k un entero. Entonces, existe x ∈ X tal que x[k,k+|u|−1] = u.
u ∈ B (X), existe x0 ∈ X tal que u v x0 , es decir, hay un i ∈ Z tal que x0[i,i+|u|−1] = u. Hagamos x = σ i−k x0 . Por Proposición 1.16, x pertenece a X , y x[k,k+|u|−1] = σ i−k x0[k,k+|u|−1] = x0[i,i+|u|−1] = u. Demostración. Dado que
No cualquier lenguaje (en el sentido de la de nición 1.22) es el lenguaje de algún espacio shift. Por ejemplo, resulta directo ver que el lenguaje de un espacio shift no vacío es un conjunto ∗ in nito, de modo que un subconjunto nito no vacío de A no puede ser el lenguaje de ningún espacio shift sobre
A.
Buscamos caracterizar a aquellos lenguajes que son los lenguajes de los
espacios shift.
Sean X un espacio shift y B (X) su lenguaje. Si v ∈ B (X), entonces: cualquier subbloque de v pertenece también a B (X). hay bloques u y w no vacíos en B (X) tales que uvw ∈ B (X).
Proposición 1.27.
1. 2.
v ∈ B (X), existen i, j ∈ Z y x ∈ X tales que v = x[i,j] . Si v 0 v v , v 0 ocurre también en x, de modo que v 0 ∈ B (X). Además, haciendo u = xi−1 y w = xj+1 , se tiene que u y w son bloques no vacíos que están en B (X) y que uvw = x[i−1,j+1] v x, por lo que uvw ∈ B (X). Demostración. Como
La proposición anterior establece condiciones necesarias para los bloques del lenguaje de un espacio shift. Resulta que esas condiciones son también su cientes: cualquier lenguaje cuyas palabras satisfagan esas condiciones, es el lenguaje de algún espacio shift. Proposición 1.28. Sea L un lenguaje con la propiedad de que para todo v ∈ L: (a) cualquier subbloque de v está en L, y (b) hay bloques no vacíos u y w en L tales que uvw está en L. Entonces L es el lenguaje de algún espacio shift.
4. LENGUAJES
Demostración. Consideremos el espacio shift
7
X = XLc ,
y veri quemos que
B (X) = L.
Lo haremos por doble inclusión:
v ∈ B (X), existe x ∈ X tal que v v x, de modo que v ∈ / Lc , o sea que v ∈ L. Sea ahora v un bloque de longitud n en L, digamos v = x0 · · · xn−1 . Por aplicación de la condición (b), hay bloques u y w , cuyos símbolos denotaremos, respectivamente, x−j · · · x−1 y xn · · · xk tales que el bloque v 0 = uvw = x−j · · · x−1 x0 · · · xn−1 xn · · · xk está en L. Aplicando 0 0 0 nuevamente la condición (b) a v hay bloques u = x−j 0 · · · x−j−1 y w = xk+1 · · · xk0 tales que el bloque x−j 0 · · · x−j−1 x−j · · · x−1 x0 · · · xn−1 xn · · · xk xk+1 · · · xk0 está en L. Continuando de esta manera, tenemos de nido xi para todo entero i, de modo tal que el punto x = (xi )i∈Z cumple que todos sus bloques están en L, y v = x[0,n−1] . Luego, x ∈ XLc , ya que ningún bloque de x c está en L , y v v x, por lo que v ∈ B (XLc ) = B (X). Si
De las dos proposiciones anteriores, vemos que un subconjunto de
A∗
es el lenguaje de algún
espacio shift si, y sólo si, todos sus bloques cumplen las propiedades (a) y (b) enunciadas en la Proposición 1.28. Hay una correspondencia biunívoca entre el conjunto de todos los espacios shift y el conjunto de todos los lenguajes de espacios shift. Es decir, el lenguaje de un espacio shift determina completamente a ese espacio shift. Dicho de otro modo, no hay dos espacios shift distintos que tengan el mismo lenguaje, según veremos a continuación. Proposición 1.29.
Sea X ⊆ AZ . X es un espacio shift si, y sólo si, X = XB(X)c .
Demostración. La vuelta es consecuencia inmediata de la de nición de espacio shift.
Demostraremos la ida por doble inclusión: todos sus bloques están en B (X) (por la de nición de c ninguno de ellos está en B (X) , y así x ∈ XB(X)c . Si
x
x ∈ X,
B (X)),
de modo que
Para la otra contención, dado que X es un espacio shift, hay un F tal que X = XF . Si ∈ XB(X)c y v v x, v ∈ / B (X)c , es decir, v ∈ B (X), por lo que v ∈ / F . Como v era un bloque
arbitrario de
x,
hemos demostrado que ningún bloque de
x
está en
F,
por lo que
quedando probada la otra inclusión. Corolario 1.30.
x ∈ XF = X ,
Sean X1 y X2 espacios shift. Entonces, X1 = X2 ⇔ B (X1 ) = B (X2 ).
Demostración. La ida es inmediata de la de nición de lenguaje de un espacio shift.
B (X1 ) = B (X2 ), X1 = XB(X1 )c = XB(X2 )c = X2
Para la vuelta, suponiendo que proposición anterior,
En este corolario, es esencial que
X1
y
X2
tenemos que
B (X1 )c = B (X2 )c ,
y, por la
sean espacios shift (ver ejemplo 1.25).
Todos estos resultados muestran que si bien un mismo espacio shift
X
puede ser descripto
a través de varios conjuntos prohibidos, hay un conjunto de bloques prohibidos maximal, que es el complemento del lenguaje de ese espacio shift: cualquier c que F ⊆ B (X) , pues ya sabemos que F ∩ B (X) = ∅.
F
tal que
X = XF
cumple con
Resumimos la correspondencia entre espacios shift y lenguajes de espacios shift a través de las siguientes ecuaciones:
L = B (XLc )
X = XB(X)c
La Proposición 1.29 tiene otro útil corolario, que dice que si un punto sus bloques en el lenguaje de un espacio shift a
X,
entonces el punto
x
x
de
AZ
tiene todos
necesariamente pertenece
X. Corolario 1.31.
Demostración.
X = XB(X)
c,
Sea X un subconjunto de AZ . X es un espacio shift si, y sólo si, ∀x ∈ AZ , ∀i, j ∈ Z, x[i,j] ∈ B (X) ⇒ x ∈ X Z Notemos que ∀x ∈ A , ∀i, j ∈ Z, x[i,j] ∈ B (X) ⇒ x ∈ X si, y sólo
de modo que el corolario se deduce directamente de la Proposición 1.29.
si,
8
1. ESPACIOS SHIFT
4.1.
Irreducibilidad.
v ∈ B (X). Por la Proposición 1.28, v puede ser extendido hacia ambos lados para formar un bloque uvw que también está en el lenguaje de X . Ahora bien, dados dos bloques u y w en B (X), puede no ser posible encontrar un bloque v tal que uvw esté en B (X). Ejemplo 1.32. Sea
1
Supongamos que
X
es un espacio shift, y que
y tomemos u y w en B (X). Ni u ni w pueden contener dos · · · 00000u0w0000000 · · · no contiene dos 1 consecutivos, y B (X).
X = X{11} ,
consecutivos. Entonces, el punto
por eso el bloque
u0w
está en
X = {0∞ , 1∞ }. Se tiene Sin embargo, no hay ningún bloque v tal que 1v0 contiene simultáneamente un 0 y un 1. Ejemplo 1.33. Sea
que
u = 1
y
w = 0
B (X). punto de X
están ambos en
esté en el lenguaje, pues ningún
Los espacios shift en los que dos bloques del lenguaje pueden ser enganchados a través de un tercer bloque forman una clase importante de espacios shift.
X es irreducible si para cualquier par de bloques u y B (X) tal que uvw pertenece a B (X). Un espacio shift que
Definición 1.34. Un espacio shift
w
en
B (X),
existe un bloque
no es irreducible se llama
v
en
reducible.
El espacio shift del ejemplo 1.32 es irreducible, en tanto que el del ejemplo 1.33 es reducible.
5.
Shifts de bloques
Hemos de nido un alfabeto como un conjunto nito de símbolos, sin exigir nada en especial
A
es un alfabeto y N es un entero positivo, cae también en la categoría N N de alfabeto el conjunto A . Por claridad notacional, cuando estemos pensando en A como a los símbolos. Si
alfabeto, representaremos su símbolos de la forma
aN
... a 2 a1 a1 a2 · · · aN . Nótese que cada ai ∈ A. AN es un alfabeto (cuyos elementos son en realidad bloques sobre otro alfabeto), N N Z Z tenemos derecho a pensar en la full A -shift, es decir, A . Dado un punto x de A , hay N Z que de manera bastante natural pueden asociarse a x. Los llamaremos, dos puntos de A respectivamente, βN (x) y γN (x). El siguiente diagrama ilustra cómo se obtienen a partir de x: en lugar de Ya que
x
= ···
x−1
βN (x) = · · ·
γN (x) = · · ·
xN −2 . . .
x0 x−1 x−1
x0
.
. . . . x −N +1 x−N
Nótese que, a partir de cada posición.
.
βN (x),
xN −1 . . .
x1 x0 xN −1 . . .
x1 x0
x1 xN
x2
... x 2 x1
x2N −1
xN +1 . . .
x3 x2 x3N −1
···
x3
xN +2 . . .
x4 x3 x4N −1
···
. . . . . . . . . ··· x x x N +1 2N +1 3N +1 xN x2N x3N
es posible recuperar
x,
leyendo los símbolos inferiores de
5. SHIFTS DE BLOQUES
βN
Formalizamos la de nición de
y de
γN :
9
Ambas son funciones de
AZ
en
AN
Z
, y se
de nen mediante:
xi+N −1
(βN (x))i = βN (x)
se llama la
. . .
xi+1 xi
(γN (x))i =
x(i+1)N −1 . . .
xiN +1 xiN
presentación en bloques de tamaño N , con solape, del punto
x. El término solape se re ere al hecho de que dos coordenadas consecutivas cualesquiera de βN (x) consisten en bloques u = u1 · · · uN y v = v1 · · · vN con u2 · · · uN = v1 · · · vN −1 . Cuando dos bloques u y v cumplen esto, es decir, que la cola de u (lo que queda de u luego de eliminar el primer símbolo) es igual a la cabecera de v (lo que queda de v luego de eliminar el último símbolo), decimos que u y v solapan progresivamente. Entonces, dos símbolos consecutivos de βN (x), vistos como bloques sobre A, solapan progresivamente, y de allí el nombre para βN . γN (x) se llama la presentación en bloques de tamaño N , sin solape, del punto x, por la razón de que no necesariamente se cumple la condición de solape progresivo entre coordenadas consecutivas de
γN (x).
Las de niciones anteriores pueden generalizarse de la siguiente manera:
X un espacio shift y N un entero positivo. Hagamos AN X = BN (X). N Z βN : X → AX mediante xi+N −1 . . . (βN (x))i = x
Definición 1.35. Sean
Se de ne la función
i+1
xi La imagen de X a través de [N ] se denota X . Es decir,
Análogamente, se de ne la
βN
se llama
presentación en N -bloques de X , con solape, y
X [N ] = {βN (x) : x ∈ X} = βN (X) N Z mediante función γN : X → AX x(i+1)N −1 . . . (γN (x))i = x iN +1
xiN La imagen de X a través de N se denota X . Es decir,
γN
se llama
presentación en N -bloques de X , sin solape,
X N = {γN (x) : x ∈ X} = γN (X) 0 1 0 2 Ejemplo 1.36. Sea X = X{11} . Entonces, AX = , , . 0 0 1 Si x = · · · 000.01010 · · · , entonces 0 0 0 1 0 1 0 β2 (x) = · · · . ··· 0 0 0 0 1 0 1 γ2 (x) =
···
0 0
.
1 0
1 0
···
X [2] = XF1 y que X 2 = XF2 con 0 0 1 0 1 1 0 0 F1 = , , , 0 1 0 0 0 0 1 1
Se puede mostrar que
y
10
1. ESPACIOS SHIFT
F2 = (notar que
F1
tiene cuatro elementos, y
F2
1 0
0 1
uno).
Por cuestiones de codi cación que más adelante detallaremos, de ahora en más estaremos más interesados en las presentaciones con solape que en las sin solape. Nótese que la función −1 βN actúa inyectivamente, de modo que es una biyección entre X y X [N ] . De este modo, βN es [N ] una función bien de nida desde X hacia X , o, más generalmente, desde el conjunto de todos N Z Z los puntos de A cuyos símbolos consecutivos solapan progresivamente hacia A . Será conveniente sobrecargar el símbolo
βN ,
manera: para
w = w1 · · · wm
m ≥ N, wN ... βN (w) = w con
2
de nimos
w1 Es directo ver que
βN
βN se pueda conN , de la siguiente
de manera que la función
siderar también para actuar sobre bloques de tamaño mayor o igual que
wN +1 . . .
w3 w2
wm
···
. . . w m−N +2 wm−N +1
actúa sobre bloques en forma inyectiva:
u 6= u0 ⇒ βN (u) 6= βN (u0 ).
Las presentaciones con (o sin) solape de cualquier espacio shift son también espacios shift.
Sea X un espacio shift sobre el alfabeto A. Para todo N ≥ 1, X [N ] es un espacio shift sobre el alfabeto BN (X). Proposición 1.37.
F 0 tal que X = XF 0 . En virtud de la Proposición 1.21, podemos 0 suponer que cada bloque de F tiene largo al menos N . Hagamos F1 = {βN (w) : w ∈ F 0 } F2 = uv ∈ (BN (X))2 : u y v no solapan progresivamente Demostración. Sea
F = F1 ∪ F 2 X [N ] = XF , con lo que quedará establecido que X [N ] es un espacio shift. [N ] Primero veamos que X ⊆ XF1 . Sea x e ∈ X [N ] , y u e un bloque en x e. Existe x ∈ X tal que βN (x) = x e, por lo que hay un bloque u de x tal que βN (u) = u e. Dado que que βN es inyectiva y que u ∈ / F 0 , vemos que u e∈ / F1 . Como u e era arbitrario, x e ∈ XF1 . [N ] Ahora veamos que X ⊆ XF2 : sabemos que si x e ∈ X [N ] , ocurre que ∀i ∈ Z, x ei y x ei+1 solapan progresivamente. Entonces, ningún bloque de x e de tamaño 2 puede estar en F2 (que tiene sólo bloques de tamaño 2), por lo que x e ∈ X F2 . [N ] Como X ⊆ XF1 y X [N ] ⊆ XF2 , se tiene, usando la Proposición 1.14, que X [N ] ⊆ XF1 ∩ XF2 = XF1 ∪F2 = XF . [N ] Veamos ahora que XF ⊆ X : sea x e ∈ XF = XF1 ∪F2 = XF1 ∩ XF2 . Entonces, x e ∈ XF1 y −1 Z x e ∈ XF2 . Como x e ∈ XF2 , podemos hacer x = βN (e x), el cual pertenece a A ; pero dado que x e ∈ XF1 , debe ser x ∈ XF 0 = X , y entonces x e ∈ X [N ] .
y veri quemos que
6.
Códigos de ventana deslizante
En Teoría de Códigos, interesan las maneras que hay de traducir un mensaje (fuente) sobre un alfabeto
A
en mensaje sobre otro alfabeto
U
(posiblemente el mismo que el del mensaje
fuente). Esto puede ser visto (sobre todo si el mensaje fuente es largo) como una manera de transformar puntos de un espacio shift en puntos de otro espacio shift, a través de una función. De las maneras en que esto se puede hacer, hay una clásica que explicamos seguidamente. Supongamos dados dos enteros
Φ
m
y
n,
con
m + n ≥ 0, y supongamos también dada una + n + 1 sobre A en símbolos de U . Entonces, y ∈ U Z es mirar el bloque que hay en una
que transforma bloques de tamaño m Z una manera de transformar un x ∈ A en un función
6. CÓDIGOS DE VENTANA DESLIZANTE
ventana de ancho la función
m+n+1
alrededor de la coordenada i-ésima de
11
x
y aplicarle a ese bloque
Φ para obtener la correspondiente coordenada del transformado. Más concretamente, y será Φ x[i−m,i+n] . Para calcular luego la (i + 1)-ésima coordenada
la i-ésima coordenada de de
y,
desplazamos toda la ventana una posición a la derecha, y repetimos. Llevando esto a
cabo para todo
i ∈ Z,
obtenemos el transformado de
la ventana, transformar usando
Φ
x.
Esta operación de ver el contenido de
y deslizar, motiva que la función transformadora reciba el
nombre de código de ventana deslizante, que abreviaremos CVD. Formalmente:
m, n ∈ Z con m + n ≥ 0, A y U alfabetos, X un espacio shift sobre A, y Φ una función de Bm+n+1 (X) en U . El código de ventana deslizante con memoria m y anticipación n inducido por Φ es la transformación φ : X → U Z de nida por y = φ (x) con yi = Φ x[i−m,i+n] . Definición 1.38. Sean
Notar, en la de nición de arriba, la distinción tipográ ca entre
φ
(que transforma tirillas
Φ (que transforma bloques de tamaño m + n + 1). Decimos que φ es inducida por Φ, o que Φ induce a φ, y, para expresar este hecho, escribimos φ = Φ[−m,n] . La función ∞ Φ se llama función de bloques, o función inductora, de φ. De los números m y n decimos que son, respectivamente, la memoria y la anticipación de φ (o también de Φ), por el hecho bi-in nitas) y
de que indican cuántas coordenadas del pasado y del futuro hay que conocer para obtener el transformado en la posición que corresponde al presente. Ejemplo 1.39.
A = {0, 1} , U = {A, B, C} , m = 1, n = 2, X = X{110,101} , Φ : B4 (X) → U
dada por
Φ (0000) = A Φ (0001) = A Φ (0010) = B Φ (0011) = A Φ (0100) = C Φ (1000) = B Φ (1001) = C Φ (1111) = A [−m,n]
φ = Φ∞ y x = · · · 001.000010010001 · · · , tenemos que φ (x) = · · · BC.BAABCCBCBA · pues φ (x)−2 = Φ x[−2−m,−2+n] = Φ x[−3,0] = Φ (0010) = B , φ (x)−1 = Φ x[−1−m,−1+n] = Φ x[−2,1] =Φ (0100) = C , φ (x)0 = Φ x[0−m,0+n] = Φ x[−1,2] = Φ (1000) = B , φ (x)1 = Φ x[1−m,1+n] = Φ x[0,2] = Φ (0000) = A, y así.
Entonces, si
A, U, X, x y Φ iguales que en el ejemplo anterior, excepto que m = 0, n = 3. φ (x) = · · · BCB.AABCCBCBA · · ·
Ejemplo 1.40.
En este caso,
Ejemplo 1.41.
1 = Φ (1),
y
F =
A = {0, 1} = U, X = AZ , m = 0 = n, Φ : B1 (X) → U x ∈ AZ , F (x) = 1∞ .
[−m,n] Φ∞ . Entonces, para todo
dada por
Φ (0) =
A cualquier alfabeto, X cualquier espacio shift sobre A, U = A, m = 0, n = [−m,n] 1, Φ (ab) = b, φ = Φ∞ . Entonces, φ = σX , pues, para x ∈ X, φxi = Φ (xi xi+1 ) = xi+1 = σX (x)i . Ejemplo 1.42.
A cualquier alfabeto, X cualquier espacio shift sobre A, U = A, m = 1, n = [−m,n] −1 0, Φ (ab) = a, φ = Φ∞ . Entonces, φ = σX , pues, para x ∈ X, φxi = Φ (xi−1 xi ) = xi−1 = −1 σX (x)i . Ejemplo 1.43.
U = AN (N ≥ 1), X cualquier espacio shift sobre A, y φ = βN (la presentación en N -bloques con solape de X ). Entonces φ es un CVD con memoria 0 y anticipación N − 1 inducido por Φ de nida como aN Φ (a1 · · · aN ) = ... a1 Ejemplo 1.44.
A
cualquier alfabeto,
12
1. ESPACIOS SHIFT
Ejemplo 1.45. En relación al ejemplo anterior,
X,
con memoria y anticipación
0,
inducido por
Φ
aN . . .
−1 βN
es también un CVD desde
Φ de nida
X [N ]
hacia
como
= a1
a1 Al igual que con la transformación shift obligatoriamente) la notación Los CVD para los cuales
σ , si φ es un CVD, φxi para (φ (x))i .
emplearemos (aunque no
φx para φ (x) y m = 0 = n se llaman códigos monobloque,
dado que actúan
mirando bloques que tienen un solo símbolo (el que corresponde al presente).
Y
Si un CVD φ con dominio X es tal que φ (X) es un subconjunto de algún espacio shift ⊆ U Z , podemos mirar a φ como una función entre los espacios shift X e Y , y diremos
entonces que el CVD es un código entre los espacios shift
X
e
Y.
φ entre dos espacios shift X e Y es un CVD. Para que lo sea, debemos Φ : Bm+n+1 (X) → B1 (Y ) tal que ∀x ∈ X, ∀i ∈ Z, φxi = posible el hallazgo de una función inductora, φ no es un CVD.
No cualquier función
m,
encontrar un
Φ x[i−m,i+n]
un
n
. Si no es
Ejemplo 1.46.
y una
A = {0, 1} = U, X = AZ , Y = U Z , φ : X → Y ∞ ∞ 0 si x = 0 φ (x) = 1∞ si x 6= 0∞
de nida por
φ no es un CVD. Supongamos que lo fuera. Debe haber una función inductora Φ m y anticipación n. Sea x = (xi )i∈Z de nido por xn+1 = 1, y xi = 0 para todo ∞ i 6= n + 1. Ya que )0 = 0 (pues φ0∞ = 0∞ ), debe ser Φ (0m+n+1 ) = 0. Pero entonces es (φ0 m+n+1 φx0 = Φ x[−m,n] = Φ (0 ) = 0. Contradicción, pues por la de nición de φ se tiene que ∞ φ (x) = 1 , de donde φx0 = 1. Veamos que
con memoria
A veces será conveniente agrandar el ancho de la ventana para la función inductora (sin modi car, obviamente, el CVD en cuestión). Para hacer esto, simplemente debemos ignorar las coordenadas añadidas a la ventana. Esto es lo que dice el siguiente resultado: Proposición 1.47. Sea φ : X → Y un código de ventana deslizante con memoria m y anticipación n. Sean M ≥ m y N ≥ n. Entonces existe un código de ventana deslizante φe : X → Y con memoria M y anticipación N tal que φe = φ. Demostración. Sea Φ : Bm+n+1 (X) → B1 (Y ) la función inductora de φ. e Φ : BM +N +1 (X) → B1 (Y ) mediante e (a−M a−M +1 · · · a−m · · · a−1 a0 a1 · · · an · · · aN ) = Φ (a−m · · · a0 · · · an ) Φ
De namos
] e i=Φ e [−M,N e x[i−M,i+N ] = φe = Φ . Sea x ∈ X . Para cualquier i ∈ Z, se tiene que φx ∞ e = φx. Como x es arbitrario, se sigue que φe = φ. Φ x[i−m,i+n] = φxi , y entonces φx y hagamos
Dado un código de ventana deslizante, se puede suponer que su memoria es igual a su anticipación. Corolario 1.48.
m y anticipación n inducido por una transformación de bloques Φ (que transforma bloques de tamaño m + n + 1 en símbolos), se puede de nir, de manera ∗ natural, una función Φ que transforma bloques de tamaño m + n + k (k ≥ 1), haciendo Dado un CVD con memoria
Φ∗ (a−m a−m+1 · · · a0 a1 · · · an−1 an an+1 · · · an+k−1 ) = Φ (a−m · · · an ) Φ (a−m+1 · · · an+1 ) · · · Φ (ak−m−1,n+k−1 ) Si además convenimos en que
Φ∗ ,
aplicado a un bloque de tamaño menor que
produce la palabra vacía, tenemos que, para
∗
Φ (a1 · · · ap ) =
p ≥ 0,
es
ε Φ (a1 · · · am+n+1 ) Φ∗ (a2 · · · ap )
si si
p 0, X ∼ Y ⇒ |{x ∈ X : x tiene período n}| = |{x ∈ Y : x tiene período n}|. 6.1.1. Recodi cación a códigos monobloque. Sea φ : X → Y un CVD. Mostraremos cómo e conjugado a X y φ a un CVD monobloque φe de X e a es posible recodi car X a un shift X Y . Este procedimiento se denomina recodi cación de φ a un código monobloque, y será de puntos periódicos de período cantidad de puntos de período
usado en varias demostraciones posteriores. Proposición 1.59. Sea φ : X → Y un código de ventana deslizante. Entonces existe un e , una conjugación ξ de X a X e y un código de ventana deslizante monobloque espacio shift X −1 e e φ : X → Y tales que ξ es una conjugación y φe ◦ ξ = φ. Si además φ es una conjugación, φe también lo es.
φ es inducida ◦ βm+n+1 . Dado
Φ con memoria m y anticipación n. −m Tomemos y ξ = que σ e y βm+n+1 son conjugaciones, y X e . Su inversa ξ −1 : X e →X teniendo en cuenta la Proposición 1.57, ξ es conjugación de X a X −1 −1 −1 m m está dada por ξ = βm+n+1 ◦ σXe , y es otra conjugación pues βm+n+1 y σXe lo son. De namos e → Y mediante φe = φ◦ξ −1 . Tenemos que φe es CVD, por ser la composición de dos CVD, y φe : X −1 e e e e → B1 (Y ) cumple que φ◦ξ = φ◦ξ ◦ξ = φ. Además, una función inductora para φ es Φ : B1 X Demostración. Supongamos que
e = X [m+n+1] X
−m σX e
por
16
1. ESPACIOS SHIFT
de nida por
pues para
x e =
xi+n . . .
xi . . .
an
.. . e Φ a0 . .. a−m
xi−m
e ∈X
= Φ (a−m · · · a0 · · · an )
se tiene que
i∈Z
xi+n+m
. . . m σXe (e x) = xi+m . . . xi y entonces, para cualquier entero
−1 m βm+n+1 σX x) = (xi )i∈Z ∈ X e (e i∈Z
j
se cumple que
−1 m exj = φ ξ −1 x e = Φ x = Φ φe e j = Φ βm+n+1 σX (e x ) [j−m,j+n] e [j−m,j+n]
xj+n . . .
xj . . .
xj−m de donde se ve que
φe es
un CVD monobloque.
Si se tiene además que con
φ,
por la Proposición
6.2.
φ es una conjugación, siendo φe la composición de la conjugación ξ −1 e una conjugación de X e a Y. 1.57, es φ
Imagen de un espacio shift por un código de ventana deslizante.
Hasta
ahora, hemos visto que un CVD φ actúa transformando puntos de un espacio shift X en Z puntos de algún full shift U . Cabe preguntarse cómo actúa globalmente φ, en el sentido de Z qué características tiene φ (X) como subconjunto de U . Mostraremos ahora que φ (X) es un espacio shift sobre el alfabeto
U.
Lema 1.60. Sea φ un código de ventana deslizante monobloque desde un espacio shift X hacia un full shift U Z . Entonces, φ (X) es un espacio shift sobre el alfabeto U .
A al alfabeto de X . Supongamos que φ está inducida por Φ : B1 (X) → U . Hagamos L = {Φ (w) : w ∈ B (X)}, y veri quemos que φ (X) = XLc , con lo que quedará probado que φ (X) es un espacio shift. 1. Sea y ∈ φ (X). Existe x ∈ X tal que y = φx. Sea u tal que u v y . Entonces existen i, j ∈ Z tales que u = y[i,j] = (φx)[i,j] = Φ x[i,j] , es decir, u = Φ (w) con w ∈ B (X). Luego, u ∈ L, por lo que u ∈ / Lc . Como u era un bloque arbitrario de y , vemos que y ∈ XLc . Entonces, φ (X) ⊆ XLc . 2. Sea y ∈ XLc . Entonces todo bloque de y está en L, de donde se deduce que para todo n ≥ 0, existe w ∈ B (X) tal que y[−n,n] = Φ (w). Porlo tanto, para todo n ≥ 0, (n) (n) (n) existe x ∈ X tal que x[−n,n] = w y φx(n) [−n,n] = Φ x[−n,n] = y[−n,n] . Usaremos (n) la sucesión x para encontrar un punto x ∈ X tal que φx = y , con lo que n∈N quedará probado que y ∈ φ (X), y, con ello, que XLc ⊆ φ (X). Como A es nito, hay Demostración. Llamemos
6. CÓDIGOS DE VENTANA DESLIZANTE
17
x(n) tienen igual símbolo a0 en la posición 0. Sea S0 el conjunto de todos esos n. Como A3 es nito, hay un subconjunto in nito S1 de S0 (n) y símbolos a−1 y a1 tales que ∀n ∈ S1 , x[−1,1] = a−1 a0 a1 . Continuando de esta manera, para cada k ≥ 1 conseguimos un subconjunto in nito Sk de Sk−1 y símbolos a−k y (n) ak tales que ∀n ∈ Sk , x[−k,k] = a−k · · · a0 · · · ak . De namos x = (ak )k∈Z . Ocurrirá que una cantidad in nita de
(n)
n
tales que
∀k ≥ 0, ∀n ∈ Sk , x[−k,k] = x[−k,k] .
Si u = x[i,j] para algunos enteros i y j , haciendo (n) x[−k,k] para cualquier n ∈ Sk , por lo que existe n ≥ 0
k = m´ax {|i| , |j|} será x[−k,k] = (n) tal que u v x ∈ X , es decir, u ∈ B (X); puesto que cualquier bloque de x está en el lenguaje del espacio shift X , se tiene que, por Corolario 1.31, x ∈ X . Sea ahora k ≥ 0. Tomemos n ∈ Sk tal que n ≥ k (tal elección es posible pues Sk es un conjunto in nito). Tenemos que
(n) (φx)[−k,k] = Φ x[−k,k] = Φ x[−k,k] = y[−k,k] Es decir,
∀k ≥ 0, (φx)[−k,k] = y[−k,k] .
Entonces,
φx = y .
Teorema 1.61. Sea φ un código de ventana deslizante desde un espacio shift X hacia un full shift U Z . Entonces, φ (X) es un espacio shift sobre el alfabeto U . Demostración. Por Proposición 1.59, existe un espacio shift
e y un CVD monobloque φe : X e → Y tales que φ = φe ◦ ξ . X →X e . Entonces, φ (X) = φe (ξ (X)) = φe X e , que, por Lema ξ (X) = X en consecuencia φ (X) es espacio shift sobre U .
6.3.
Inversa de una conjugación.
e, X
Como
una conjugación
ξ
ξ :
es conjugación, es
1.60, es un espacio shift, y
Mostremos ahora que la inversa de una conjugación
es siempre una conjugación.
Sea φ una conjugación monobloque del espacio shift X al espacio shift Y . es una conjugación de Y a X .
Lema 1.62.
Entonces, φ
−1
A el alfabeto para X y U el de Y . Supongamos que φ está inducida Φ : B1 (X) → B1 (Y ). Hagamos ψ = φ−1 . Debemos mostrar que ψ es un CVD biyectivo de Y a X . Por ser la inversa de una función biyectiva, ψ es también biyectiva, así que sólo resta Demostración. Sean
por
veri car que es CVD, para lo que usaremos la Proposición 1.53.
φ un CVD, tenemos que φ ◦ σX = σY ◦ φ, por lo que ψ ◦ φ ◦ σX ◦ ψ = ψ ◦ σY ◦ φ ◦ ψ , σX ◦ ψ = ψ ◦ σY . Por lo tanto, ψ cumple la condición de conmutar con σ . Supongamos que no existe un N ≥ 0 tal que para todo y ∈ Y , (ψy)0 dependa de (n) y[−N,N ] . Esto quiere decir que para cada n ≥ 0 existen y (n) e yb(n) en Y tales que y[−n,n] = (n) yb[−n,n] pero ψ y (n) 0 6= ψ yb(n) 0 . Llamemos x(n) = ψ y (n) y x b(n) = ψ yb(n) . Tenemos (n) que, para cada n ≥ 0, tanto x como x b(n) están en X , y además x(n) 6= b(n) pues x (n) ambos di eren en la coordenada 0. Consideremos las dos sucesiones en X , x y n∈N (n) 0 x b . Como A es nito, debe haber un símbolo a0 ∈ A, y un conjunto in nito S0 n∈N 0 (n) de enteros tal que ∀n ∈ S0 , x = a0 ; nótese que ∀n ∈ S00 , x b(n) 0 6= a0 . Puesto que 0 0 A es nito, debe in nito S0 de S0 tal que haber un símbolo b0 6= a0 y un subconjunto (n) (n) ∀n ∈ S0 , x b 0 = b0 . Observar que, entonces, ∀n ∈ S0 , x 0 = a0 6= b0 = x b(n) 0 . 3 0 Como la cantidad de bloques en A es nita, debe haber un subconjunto in nito S1 de S0 y símbolos a−1 y a1 tales que ∀n ∈ S10 , x(n) [−1,1] = a−1 a0 a1 , y consecuentemente 0 debe haber un subconjunto in nito S1 de S1 y símbolos b−1 y b1 tales que ∀n ∈ S1 , x b(n) 0 = b−1 b0 b1 . Notar que ∀n ∈ S1 , x(n) [−1,1] = a−1 a0 a1 6= b−1 b0 b1= x b(n) [−1,1] . Continuando de esta manera, para cada k ≥ 1 encontramos un subconjunto in nito Sk
1. Por ser
y entonces 2.
18
1. ESPACIOS SHIFT
a−k , ak , b−k y bk tales que ∀n ∈ Sk , x(n) [−k,k] = a−k · · · a0 · · · ak 6= b−k · · · b0 · · · bk = x b(n) [−k,k] . Tomemos x = (ak )k∈Z y x b = (bk )k∈Z . Obsérvese que ∀k ≥
de
Sk−1
y símbolos
(n)
0, ∀n ∈ Sk , x[−k,k] = x[−k,k]
yx b[−k,k]
(n)
= x b[−k,k] .
Si u = x[i,j] para algunos enteros i y j , (n) x[−k,k] para cualquier n ∈ Sk , por lo que existe
k = m´ax {|i| , |j|} será x[−k,k] = n ≥ 0 tal que u v x(n) ∈ X , es decir, u ∈ B (X); puesto que cualquier bloque de x está en el lenguaje del espacio shift X , se tiene que, por Corolario 1.31, x ∈ X . Igualmente, x b ∈ X . Además, x 6= x b pues x0 = a0 6= b0 = x b0 . Sea ahora k ≥ 0. Tomemos n ∈ Sk tal que n ≥ k (tal elección es posible pues Sk es un conjunto in nito). Tenemos que (n) (n) (n) (φx)[−k,k] = Φ x[−k,k] = Φ x[−k,k] = y[−k,k] = yb[−k,k] (n) = Φ x b[−k,k] = Φ x b[−k,k] = (φb x)[−k,k] haciendo
Es decir,
x 6= x b.
∀k ≥ 0, (φx)[−k,k] = (φb x)[−k,k] .
Contradicción a la inyectividad de
no hay un
N ≥0
tal que
ψy0
De allí, tendríamos que
φ. La contradicción y[−N,N ] .
φx = φb x
pese a ser
proviene de suponer que
es función de
Teorema 1.63. Sea φ una conjugación del espacio shift X al espacio shift Y . Entonces, φ−1 es una conjugación de Y a X .
e , una conjugación ξ : X → X e . Entonces e y una conjugación monobloque φe : X e → Y tales que ξ es conjugación y φ = φ◦ξ X −1 −1 −1 −1 e φ = ξ ◦ φ , y, por aplicación de Lema 1.62 y Proposición 1.57, φ resulta ser también una conjugación. Demostración. Por Proposición 1.59, existe un espacio shift
−1
Capítulo 2
SHIFTS DE TIPO FINITO Los espacios shift que pueden ser descriptos por un conjunto se llaman
shifts de tipo nito
nito
de bloques prohibidos
(abreviado STF). A pesar de ser los más simples, juegan un rol
fundamental en ciertas áreas de la Matemática, tales como sistemas dinámicos. Su estudio también ha proporcionado soluciones a problemas prácticos de importancia, tales como encontrar esquemas de codi cación e cientes para almacenar datos en discos de computadoras. Una razón por la que los STF son tan útiles es que tienen una representación sencilla usando un grafo nito dirigido. Preguntas sobre el shift pueden, a menudo, reformularse como preguntas sobre la matriz de adyacencia del grafo. Resultados básicos del álgebra lineal nos ayudan a analizar esta matriz y encontrar respuestas. En este capítulo, primero presentamos los STF, y damos algunos ejemplos típicos. Luego se explica las conexiones con los grafos dirigidos y las matrices, e introducimos la fundamental operación de desdoblamiento de estados. Concluimos con una breve descripción sobre el almacenamiento magnético, indicando por qué la shift de paso limitado (1,3) es la característica central de la mayoría de los métodos más usados para el almacenamiento de datos en discos rígidos de computadoras.
1.
Restricciones de tipo nito
Primero de nimos shifts de tipo nito, y luego explicamos el hecho de que tienen una propiedad (markoviana) de memoria nita. Definición 2.1. Un
shift de tipo nito (STF) es un espacio shift que puede describirse
por un conjunto nito de bloques prohibidos, es decir, un espacio shift algún conjunto nito
F
de bloques tal que
X
para el cual existe
X = XF .
Ya hemos tratado antes con varios STF.
AZ es un A = XF .
Ejemplo 2.2. El full shift
está prohibido, de modo que
STF: podemos tomar simplemente
Ejemplo 2.3. El shift de la razón de oro
F = {11},
obteniendo
F =∅
pues nada
Z
X
(ejemplo 1.10) es un STF, pues podemos tomar
X = XF .
X el conjunto de todos los puntos de {e, f, g}Z tales que e puede ser seguido sólo por e o por f , f puede ser seguido sólo por g , y g puede ser seguido sólo por e o por f . Entonces X es el espacio shift que resulta de tomar F = {eg, f e, f f, gg}, y, en consecuencia, es un STF. Ejemplo 2.4. Sea
Notemos que un STF
X
podría también describirse mediante un conjunto in nito de bloques
prohibidos. De hecho, la Proposición 1.29 muestra que ésto puede ocurrir siempre que
X
no
X es in nito. La de nición de STF sólo algún F adecuado. Z Supongamos que X ⊆ A es STF, y que X = XF para una colección nita F de bloques. Sea N la longitud del bloque más largo en F . Si formamos la colección FN de todos los bloques de longitud N sobre A que contienen algún subbloque en F , entonces tendremos que XFN = XF (prop. 1.21) y los bloques de FN tienen todos la misma longitud N . Por ejemplo, si A = {0, 1} y F = {11, 000}, entonces F3 = {110, 111, 011, 000}. A veces, será conveniente asumir que
sea el full shift, pues el complemento del lenguaje de pide que exista
19
20
2. SHIFTS DE TIPO FINITO
este procedimiento ya ha sido llevado a cabo, y que todos los bloques prohibidos tienen igual longitud. Si todos los bloques en
F
tienen longitud
N,
entonces
x ∈ AZ
está en
XF exactamente cuando x[i,i+N −1] ∈ / F para todo i ∈ Z, o, equivalentemente, cuando x[i,i+N −1] ∈ BN (XF ) para todo i ∈ Z (Supongamos que ∀i ∈ Z, x[i,i+N −1] ∈ / F . Sea u un bloque de x. Si |u| 6= N, u ∈ /F pues F tiene sólo bloques de tamaño N , y si |u| = N, u ∈ / F por la hipótesis; entonces ningún bloque de x está en F , por lo que x ∈ XF y ∀i ∈ Z, xi,i+N −1] ∈ B (XF ). Recíprocamente, si un bloque de tamaño N está en BN (XF ), no puede estar en F ). Luego, para determinar si x está o no en XF , sólo necesitamos escanear las coordenadas de x con una ventana de ancho N , y veri car que cada bloque visto a través de esta ventana está en la colección permitida BN (X). Esta observación es, a menudo, útil cuando se debe decidir si un dado espacio shift es o no de tipo nito. Ejemplo 2.5. El shift par
X
(ejemplo 1.13) no es un STF, pues, si lo fuera, existiría
N ≥1
y una colección de N -bloques tal que X = XF . En dicha colección, no puede haber bloques de la 0k , ni 0k 10l para ningún k, l ≥ 0, ya que 0∞ 10∞ ∈ X . Pero entonces 0∞ 102N +1 10∞ ∈ XF
forma
N -bloques
pues ninguno de sus
está en
F.
Sin embargo, ese punto no pertenece a
X
por la
de nición del shift par. Hay también una noción de memoria para un STF: Definición 2.6. Un shift de tipo nito
es de memoria M
una colección de bloques prohibidos que tienen todos longitud
si puede describirse mediante
M + 1. F M.
Para motivar esta de nición, supongamos que todos los bloques de Sea
u = a1 a2 . . . an
un bloque con longitud
u
máquina lee los símbolos de detecte si
u
n
mucho mayor que
tienen longitud
uno por vez, de izquierda a derecha. Para que esta máquina
contiene o no un bloque prohibido, sólo debe recordar los previos
leídos, es decir, necesita sólo Observación 2.7. Sea
bloques de longitud
M
X
M +1.
Supongamos que una
M
símbolos
espacios de memoria.
un STF de memoria
M,
descripto a través de un conjunto
F
de
M + 1.
u un bloque de A∗ que no contiene ningún subbloque en F . Esto no garantiza que u ∈ B(X). Por ejemplo: F = {10, 11}, u = 001. u no contiene subbloques en F , pero u∈ / B(X) pues X = {0∞ }. 0 M +1 Sea F = A − B(XF ). Entonces, F ⊆ F 0 , y XF 0 = XF . Para ver la primera aserción, si f ∈ F, |f | = M + 1 y f ∈ / B(XF ), luego f ∈ F 0 . Para la segunda, ya que F ⊆ F 0 , se tiene que XF 0 ⊆ XF . Si x ∈ XF y u es un bloque de longitud M + 1 que ocurre en x, u ∈ B(XF ), por lo que u ∈ / F 0 . Luego x no contiene bloques en F 0 , mostrando que x ∈ XF 0 y, consecuentemente, XF ⊆ XF 0 .
1. Sea
2.
Notar que un STF de memoria
M
es también de memoria
K
para todo
K ≥ M.
Un STF
de memoria 0 es simplemente un full shift, pues prohibir bloques de tamaño 1 es meramente quitar letras del alfabeto. Se puede pensar en un STF de memoria 1 como en uno dado por una colección de símbolos junto con una descripción de cuáles símbolos pueden seguir a cuáles, como en el ejemplo 2.4. Posteriormente veremos muchos ejemplos de tales STF de memoria 1. Proposición 2.8.
memoria M .
Si X es un shift de tipo nito, entonces hay un M ≥ 0 tal que X es de
X es de tipo nito, X = XF para alguna colección nita de M = 0. Si F = 6 ∅, sea M igual a la longitud del bloque más largo en F , menos 1. Nuestra discusión anterior muestra que X es descripto por FM +1 (el conjunto de todas las palabras de largo M + 1 que contienen algún subbloque en F ), por lo que X es de memoria M . Demostración. Ya que
bloques
F.
Si
F = ∅,
sea
1. RESTRICCIONES DE TIPO FINITO
21
El lenguaje de un STF está caracterizado por la propiedad de que si dos palabras se solapan lo sufuciente, pueden ser unidas a lo largo del solape para formar otra palabra en el lenguaje.
Sea X un espacio shift sobre el alfabeto A, y M ≥ 0. X es STF de memoria M si, y sólo si, ∀u, v, w ∈ A∗ , uv ∈ B(X) ∧ vw ∈ B(X) ∧ |v| ≥ M ⇒ uvw ∈ B(X) Teorema 2.9.
F una colección de bloques de M + 1 tal que X = XF . Sean u, v y w en A∗ tales que uv y vw estén en B(X) con |v| ≥ M . Existen x e y en X tales que x[i,i+|uv|−1] = uv , y[j,j+|vw|−1] = vw. Consideremos el punto z = x(−∞,i+|uv|−1] y[j+|v|,∞) = · · · xi−2 xi−1 uvwyj+|vw| yj+|vw|+1 · · · . No puede contener un bloque en F pues, al ser |v| ≥ M , una ventana de ancho M + 1 no puede ver simultáneamente símbolos de u, v y w , por lo que todo bloque que esta ventana vea corresponde a un bloque en x o en y . Entonces z ∈ X y uvw ∈ B(X). M +1 Para la su ciencia, de namos F = A − BM +1 (X), y veamos que X = XF . Si x ∈ X e i ∈ Z, x[i,i+M ] ∈ BM +1 (X), es decir, ∀i, x[i,i+M ] ∈ / F . Luego x ∈ XF , y se deduce que X ⊆ XF . Ahora, sea x ∈ XF . Mostremos, por inducción sobre n, que ∀n ≥ M, x[0,n] ∈ B(X). Para n = M es cierto pues x[0,M ] ∈ / F , por lo que x[0,M ] ∈ BM +1 (X), y, de allí, x[0,M ] ∈ B(X); esto muestra también que ∀n ∈ {0, . . . , M − 1}, x[0,n] ∈ B(X). Supongamos que x[0,n] ∈ B(X). Hagamos u = x[0,n−M ] , v = x[n−M +1,n] y w = xn+1 . Observemos que uv = x[0,n] ∈ B(X), vw = x[n−M +1,n+1] ∈ / F y |vw| = M + 1, por lo que vw ∈ BM +1 (X) ⊆ B(X). Además, |v| = M . Entonces uvw ∈ B(X), es decir, x[0,n+1] ∈ B(X). Un razonamiento análogo en la otra dirección muestra que ∀m, n ∈ Z, x[m,n] ∈ B(X), es decir, cualquier bloque en x está en B(X), y, siendo X espacio shift, x ∈ X , por lo que XF ⊆ X . Demostración. Para la necesidad de la condición, sea
tamaño
Ejemplo 2.10. El teorema anterior da otra forma de ver que el shift par X no es de tipo 2M +1 nito. Pues si lo fuera, sería de memoria M para algún M ≥ 1. Ya que 10 ∈ B(X) y que 2M +1 2M +1 0 1 ∈ B(X), deberíamos tener que 10 1 ∈ B(X), lo que violaría la de nición de shift
par.
φ con memoria 0 y anticipación 1 que tiene por dominio el shift de la X , inducido por Φ tal que Φ(00) = 1, Φ(01) = 0 = Φ(10). Ocurre que Φ(u) = 10k 1 2n si, y sólo si, existe n ≥ 0 tal que u = 0(01) 00, por lo que k = 2n. Luego, φ(X) ⊆ Y , donde Y es el shift par. Además, si y ∈ Y , es posible construir x ∈ X tal que y = φ(x) (teniendo 2k k en cuenta que si y[i,i+2k+1] = 10 1, entonces debe ser x[i,i+2k+2] = 0(01) 00). Entonces, φ es Consideremos el CVD
razón de oro
un código factor del shift de la razón de oro en el shift par, siendo el primero de tipo nito y el segundo no. Es fácil construir también códigos de ventana deslizante sobreyectivos desde espacios shift que no son de tipo nito hacia otros que sí lo son (por ejemplo, desde el shift par ∞ hacia {0 } por el CVD de memoria 0 y anticipación 0 inducido por Φ(0) = Φ(1) = 0). Sin embargo, las conjugaciones preservan el carácter de tipo nito. Teorema 2.11. Sea X un shift de tipo nito, e Y un espacio shift conjugado a X . Entonces Y es un shift de tipo nito.
A y U los alfabetos para X e Y respectivamente. Supongamos que M . Sea φ : X → Y una conjugación inducida por Φ, y ψ : Y → X su inversa, inducida por Ψ. Podemos suponer que φ y ψ tienen ambas la misma memoria y anticipación l . Sabemos que ψ ◦φ es código de ventana deslizante con memoria y anticipación 2l , y que una función inductora es Ψ ◦ Φ : B4l+1 (X) → B1 (X). Dicha composición de inductoras, aplicada a un bloque a−2l · · · a0 · · · a2l devuelve el carácter central a0 ; como consecuencia de ésto, si s, t y w son bloques con |s| = |t| = 2l , Φ ◦ Ψ(swt) = w . Mostraremos que Y es ∗ un STF de memoria M + 4l , usando el teorema anterior. Sean u, v, w ∈ U tales que uv ∈ B(Y ), vw ∈ B(Y ), |v| ≥ M + 4l, digamos v = v1 · · · vk con k ≥ M + 4l. Existen s, t ∈ B(Y ) : suv ∈ B(Y ), vwt ∈ B(Y ), |s| = |t| = 2l. Sea u0 = Ψ(suv1 · · · v2l ), w0 = Ψ(vk−2l+1 · · · vk wt). 0 0 Entonces Ψ(suv) = u Ψ(v) ∈ B(X), Ψ(vwt) = Ψ(v)w ∈ B(X). Como |v| ≥ M + 4, será 0 0 |Ψ(v)| = |v| − 2l ≥ M . Luego Ψ(suvwt) = u Ψ(v)w ∈ B(X). Por ello, Φ (Ψ(suvwt)) ∈ B(Y ), es decir, uvw ∈ B(Y ). Demostración. Sean
X
es un STF de memoria
22
2. SHIFTS DE TIPO FINITO
2.
Grafos y sus shifts
Un método fundamental para construir shifts de tipo nito se basa en un grafo nito dirigido, considerando la colección de todos los caminos bi-in nitos (es decir, sucesiones de aristas
consecutivas)
en el grafo. En un sentido que precisaremos más adelante, cualquier shift de tipo
nito fuede ser recodi cado en un shift de aristas. En esta sección, introducimos los shifts de aristas, y usamos la matriz de adyacencia del grafo para responder preguntas sobre su shift. Realmente, la razón por la que un shift de aristas puede ser entendido mucho mejor que un shift general es que podemos aplicar la potente maquinaria del álgebra lineal a su matriz de adyacencia. Comenzamos con las de niciones básicas concernientes a la teoría de grafos. Definición 2.12. Un grafo nito dirigido G es una cuaterna (V, Σ, i, t) donde: V es un conjunto nito cuyos elementos llamaremos vértices, nodos o estados. Σ es un conjunto nito cuyos elementos llamaremos aristas o arcos. i es una función de Σ en V . Para una arista a, i(a) se llama vértice inicial de a. También decimos que la arista a arranca en el nodo i(a). t es una función de Σ en V . Para una arista a, t(a) se llama vértice terminal de a. También decimos que la arista a termina en el nodo t(a).
Una manera cómoda de visualizar un grafo es mediante un dibujo donde los nodos se representan por círculos (con el nombre del nodo en su interior) y cada arista
i(a) hasta t(a), con un rótulo que indica su un grafo con V = {I, J} y ocho aristas, teniéndose que, por i(f ) = t(f ) = i(g) = t(g) = J , etc.
una echa desde
a
mediante
nombre. La gura 1 muestra ejemplo,
i(e) = I , t(e) = J ,
Figura 1.
Muchas veces, cuando hagamos referencia a distintos grafos en forma simultánea, emplearemos la notación
V (G), Σ(G), iG G en
inicial y terminal de un grafo
y
tG
para indicar conjuntos de nodos, aristas y funciones
particular.
G = (V, Σ, i, t) un grafo. Para nodos I, J de G, denotaremos por ΣI al conjunto de todas las aristas de G que J arrancan en I , es decir, ΣI = {a ∈ Σ : i(a) = I}. Similarmente, Σ denotará al conjunto J de todas las aristas de G que terminan en J , es decir, Σ = {a ∈ Σ : t(a) = J}. J Reservamos el símbolo ΣI para el conjunto de todas las aristas de G que empiezan en I y terminan en J , es decir ΣJI = {a ∈ Σ : i(a) = I ∧ t(a) = J}. Llamamos grado de salida J de I a |ΣI |, la cantidad de aristas que arrancan en I , y grado de entrada de J a Σ , la cantidad de aristas que llegan a J . La matriz de adyacencia AG del grafo G se de ne como la matriz J cuadrada de |V | × |V | indizada por V , cuyo elemento en la posición IJ es AIJ = ΣI . Es decir, AIJ es la cantidad de aristas de I a J en G. Un lazo, bucle o rulo en G es una arista a tal que i(a) = t(a). Un camino π en el grafo G es una sucesión nita de aristas π = e1 e2 · · · ek tal que ∀i ∈ {1, . . . , k − 1}, t(ei ) = i(ei+1 ). De nimos el vértice inicial del camino π como
Definición 2.13. Sea
2. GRAFOS Y SUS SHIFTS
23
i(π) = i(e1 ), el vértice inicial de la primera arista del camino, y el vértice nal de π como t(π) = t(ek ), el vértice nal de la última arista del camino. La longitud del camino π es la cantidad de aristas que contiene, denotada por |π|. Es decir, |π| = k . La sucesión vacía cumple también con la de nición de camino, con longitud 0 y vértices
G. Un ciclo en G es un un ciclo π = e1 · · · ek tal
inicial y nal idénticos, pudiendo ser cualquiera de los nodos de camino
π
en
G
que los estados
tal que i(π) = t(π). Un ciclo simple i(e1 ), . . . , i(ek ) son distintos.
G
en
Desde el punto de vista de la dinámica simbólica, interesa la
es
conectividad
de las aristas de
un grafo, no los nombres de las mismas ni de los vértices del grafo. Por ello, grafos diferentes pueden en realidad representar un mismo objeto desde ese punto de vista.
G y H , un homomor smo de G a H es un par de funciones (∂, Φ) con ∂ : V (G) → V (H) y Φ : Σ(G) → Σ(H) tales que ∀e ∈ Σ(G), iH (Φ(e)) = ∂ (iG (e)) y tH (Φ(e)) = ∂ (tG (e)). En caso de ser ambas funciones inyectivas, el homomor smo se llama inmersión de G en H . Si ambas funciones son biyectivas, se llama isomor smo entre G y H . Dos grafos se dicen isomorfos si hay un isomor smo entre ellos, y en ese caso escribimos G ∼ = H . Un isomor smo es, a los nes prácticos, simplemente un cambio de nombre Definición 2.14. Dados dos grafos
de nodos y aristas. La relación de ser isomorfos es una relación de equivalencia entre grafos. Definición 2.15. Un
Σ(G),
y las funciones
iH
subgrafo H tH
y
del grafo
G
son, respectivamente, las restricciones
En términos de matrices de adyacencia, si
H
V (H) ⊆ V (G), Σ(H) ⊆ de iG y tG a Σ(H).
es un grafo tal que
es subgrafo de
G se tiene que (AH )I,J ≤ (AG )I,J
I, J ∈ V (H).
para toda pareja de vértices
En cuanto a los isomor smos, se tiene que dos grafos
y
H
son isomorfos si, y sólo si,
AG = P AH P . Recordemos que una matriz de 0 o 1 que tiene exactamente un 1 en cada la, y exactamente un 1 en cada columna. Es fácil demostrar si P es matriz de permutación, P también lo es, y P −1 = P T . Si (∂, Φ) es un isomor smo entre G = (V, Σ, iG , tG ) y H = (W, Σ0 , iH , tH ), se de ne P con las indizadas según V (G) y columnas indizadas según V (H) mediante 1 si ∂(I) = J PI,J = 0 si ∂(I) 6= J Resulta directo chequear que P es matriz de permutación. Además, teniendo en cuenta que e ∈ ΣJI ⇐⇒ Φ(e) ∈ Σ∂J ∂I , a través de un cálculo rutinario se puede ver que (AG P )I,J = (P AH )I,J −1 para todos I, J , de modo que AG = P AH P . Recíprocamente, si G y H son grafos tales que admiten una matriz de permutación P tal −1 que AG = P AH P , considerando a las las de P en el mismo orden que las de AG y a las columnas de P en el mismo orden que las de AH , se de ne ∂I = J ⇐⇒ PI,J = 1. De la −1 condición AG = P AH P , se deduce que (AG )I,J = (AH )∂I,∂J , con lo que los grafos G y H son existe una matriz de permutación
P
G −1
tal que
permutación es una matriz cuadrada con entradas
isomorfos.
2.1.
Shifts de aristas.
Definición 2.16. Sea
denotado por
XG
o
XA ,
G
A continuación de niremos el espacio shift generado por un grafo. un grafo con matriz de adyacencia
A.
El
shift de aristas
es el conjunto de todos los caminos bi-in nitos de
G.
de
G,
Es decir:
XG = {x = (xk )k∈Z : ∀k ∈ Z, xk ∈ Σ ∧ t(xk ) = i(xk+1 )} Como puede verse, conjunto
Σ
XG
ΣZ ,
que tiene como alfabeto el
de aristas del grafo.
Ejemplo 2.17. Sean
Entonces, shift
es un subconjunto del full shift
XG1
X{eg,f e,f f,gg}
G1
y
G2
los grafos mostrados en la gura 2.
es el full shift sobre el alfabeto del ejemplo 2.4.
{0, 1, . . . , r−1}, mientras que XG2
es el espacio
24
2. SHIFTS DE TIPO FINITO
G1
G2 Figura 2.
Justi quemos que el uso del término shift para los shifts de aristas es adecuado.
Si G = (V, Σ, i, t) es un grafo, entonces XG es un espacio shift. Más aún, es un shift de tipo nito de memoria 1. Proposición 2.18.
Demostración. Consideremos la colección nita
F = {ef ∈ Σ2 : t(e) 6= i(f )} XG = XF : Sea x ∈ XG , y k ∈ Z. Debe ser t(xk ) = i(xk+1 ) por la de nición de xk xk+1 ∈ / F . Entonces, ningún bloque de x está en F , y x ∈ XF . Recíprocamente, sea x ∈ XF , y k ∈ Z. xk xk+1 ∈ / F , por lo que t(xk ) = i(xk+1 ). Como esto ocurre para todo k ∈ Z, se ve que x ∈ XG . Como F tiene todos sus bloques de tamaño 2, XG es un shift de tipo nito de memoria 1.
y mostremos que
XG .
Luego
Es sencillo demostrar que si
(∂, Φ)
es un isomor smo entre
G
G y
H son isomorfos, entonces XG y XH son conjugados: si H , Φ puede verse como la función inductora (biyectiva) de y
un código de ventana deslizante de memoria y anticipación 0, que, en vistas de la biyectividad de
Φ,
resultará ser una conjugación entre
También es fácil ver que si
H
XG
y
Observemos el grafo de la gura 3. En él, bi-in nito, pues desde
I = t(a)
XH . G, XH ⊆ XG . la arista a no
es subgrafo de
forma parte de ningún camino
no arranca ninguna arista. Podemos pensar en el nodo
en un nodo muerto. Una situación análoga ocurre con el nodo arista, de modo que las aristas
b
y
c
que arrancan en
J
J,
I
como
al cual no llega ninguna
tampoco pueden formar parte de un
camino bi-in nito.
Figura 3.
Definición 2.19. Un nodo de un grafo se llama
sale, ninguna arista.
nodo muerto si a él no llega, o de él no
2. GRAFOS Y SUS SHIFTS
Los nodos muertos de un grafo
G
25
pueden eliminarse, conjuntamente con todas las aristas
que a él llegan o salen, sin alterar el shift de aristas asociado. En el subgrafo que resulta de esta eliminación, pueden a su vez haber quedado nodos muertos. Sin embargo, repitiendo el proceso de eliminación sobre el subgrafo la cantidad de veces que sea necesaria hasta que no queden nodos muertos, se obtiene como resultado un subgrafo del grafo original que contiene todas las aristas que forman parte de algún camino bi-in nito en
G.
Ejemplo 2.20. La gura 4 muestra el resultado del proceso de eliminación de nodos muertos
del grafo de la gura 3.
Figura 4. Definición 2.21. Un grafo se llama
esencial si no contiene nodos muertos.
u1 · · · uk es un bloque de largo k que está en el lenguaje de XG , entonces G (si u v x ∈ XG , existe j ∈ Z tal que x[j+1,j+k] = u1 · · · uk , de donde, para cualquier n ∈ {1, . . . , k − 1}, es t(un ) = t(xj+n ) = i(xj+n+1 ) = i(un+1 ), por lo que u1 · · · uk es camino en G). Sin embargo, no es cierto que cualquier camino en un grafo G sea un bloque del lenguaje de XG . Por ejemplo, cualquier arista vinculada a un nodo muerto en un grafo no esencial es un camino de longitud 1 en G, pero no puede formar parte de un camino bi-in nito en G, por lo que no pertenece a B1 (XG ). Es fácil ver que si
u
es un camino en
Sea G un grafo esencial. Entonces, el conjunto de los caminos ( nitos) en G es un precisamente el conjunto de bloques en el lenguaje de XG . Lema 2.22.
Demostración. Por nuestros comentarios anteriores, ya sabemos que los bloques en el
lenguaje de
XG
son caminos en
G.
Probemos ahora que, bajo la hipótesis de que
G
es esencial,
G son bloques en el lenguaje de XG . Sea π un camino en G. Por ser G esencial, a1 que llega a i(π) y una arista b1 saliendo de t(π). Inductivamente, para cada k ≥ 2, hay una arista ak llegando a i(ak−1 ) y una arista bk−1 saliendo de t(bk ). Entonces, · · · a2 a1 πb1 b2 · · · es camino bi-in nito en G, y π ocurre en él. Luego, π está en B (XG ). Proposición 2.23. Si G = V (G), Σ(G), iG , tG es un grafo, existe un único subgrafo H de G tal que H esencial y XG = XH . los caminos de hay una arista
Σ(H) = B1 (XG ), es decir, el conjunto de todas las aristas de G que intervienen en algún camino bi-in nito en G. Hagamos V (H) = {i(a) : a ∈ Σ(H)}, el conjunto de nodos visitados por las aristas de H , y sean iH y tH las respectivas restricciones de iG y tG a Σ(H). Entonces H es subgrafo de G, y, en consecuencia, cualquier camino bi-in nito en H es también camino bi-in nito en G, así que XH ⊆ XG . Veamos que también XG ⊆ XH : si x ∈ XG , se tiene que para todo k ∈ Z, xk y xk+1 están ambos en B1 (XG ), y además tG (xk ) = iG (xk+1 ). Luego, para todo k ∈ Z, es xk ∈ Σ(H) y además tH (xk ) = tG (xk ) = iG (xk+1 ) = iH (xk+1 ), de donde x ∈ XH . Demostración. Sea
26
2. SHIFTS DE TIPO FINITO
H es esencial, pues si I ∈ V (H), debe haber una arista a ∈ Σ(H) tal que I = iG (a). Como a ∈ B1 (XG ), existe x ∈ XG tal que xk = a para algún k ∈ Z. Entonces tH (xk−1 ) = tG (xk−1 ) = iG (xk ) = iH (xk ) = I , mostrando que la arista xk−1 llega a I y la arista xk sale desde I. 0 Para ver que H es único, consideremos cualquier subgrafo esencial H de G tal que XH 0 = XG . Si hubiera una arista en H que no esté en H 0 o una en H 0 que no esté en H , sería B1 (XH ) 6= B1 (XH 0 ) (lema 2.22, considerando que H y H 0 son esenciales), por lo que B (XG ) = B (XH ) 6= B (XH 0 ), es decir, sería XG 6= XH 0 , y tendríamos una contradicción. Luego, H y H 0 tienen las mismas aristas, y siendo ambos esenciales, tienen también los mismos nodos, de donde concluimos que ambos son iguales. Además,
Ya que el subgrafo
H
de la proposición anterior contiene la única parte de
G
usada para la
dinámica simbólica, usualmente restringiremos nuestra atención a los grafos esenciales. La matriz de adyacencia de un grafo puede usarse para obtener información sobre la cantidad de caminos de longitud
n ≥ 0
en el grafo, y, consecuentemente, si el grafo es esencial, para
obtener la cantidad de bloques de tamaño Proposición 2.24.
1. 2.
n
en
B (XG ),
esto es,
|Bn (XG )|.
Sea G un grafo con matriz de adyacencia A, y sea n ≥ 0. Entonces:
Para vértices I, J cualesquiera en G, el número de caminos de longitud n desde I hasta J en G es (An )IJ , es decir, la posición IJ de la matriz An . El número de ciclos de longitud n en G es tr(An ), la traza de An , y es igual al número de puntos periódicos de XG de período n.
Demostración.
I, J ∈ V (G). Si I = J , (A0 )IJ = 1, y el único camino de I a J de longitud 0 es el camino vacío; si I = 6 J , (A0 )IJ = 0 y no hay camino en G de I a J de longitud 0. Luego, la proposición es verdadera para n = 0. Supongamos que la proposición es cierta para n. Un camino de I a J de longitud n + 1 consiste en un camino de longitud n de I a K seguido de una arista desde K hasta J , donde K es algún nodo. La cantidad de caminos de longitud n + 1 de I a J cuyo penúltimo vértice visitado es K es entonces la cantidad de caminos de longitud n de I a K multiplicada por la cantidad de aristas de K a J , que por hipótesis inductiva y de nición de matriz n de adyacencia es (A )IK AKJ . Para obtener todos los caminos desde I a J en G de longitud n + 1 hacemos variar a K en el conjunto de nodos de G y sumamos. Es decir, la cantidad de caminos de longitud n + 1 de I a J es X (An )IK AKJ
1. Probamos por inducción sobre
n.
Sean
K∈V (G) que es precisamente la de nición de
(An+1 )IJ ,
con lo que queda demostrada la primera
parte. 2. La primera parte del enunciado se sigue del ítem anterior y de la de nición de ciclo. ∞ Para la segunda parte, notar que que si π es un ciclo de longitud n en G, entonces π es un punto periódico en de período
n,
XG de período n, mientras que si x ∈ XG es un punto periódico x[0,n−1] debe ser un ciclo de longitud n en G. Esto establece una entre los ciclos en G de longitud n y los puntos en XG de período
entonces
correspondencia 1 a 1
n. Recordemos que un espacio shift
u, w ∈ B(X),
existe
v ∈ B(X)
X se dice irreducible si uvw ∈ B(X). Es fácil
tal que
lugar a shifts de aristas irreducibles.
para cualquier pareja de bloques caracterizar a los grafos que dan
3. REPRESENTACIÓN DE SHIFTS DE TIPO FINITO POR MEDIO DE GRAFOS
Definición 2.25. Un grafo
en
G,
existe un camino
reducible.
π
en
G
G
se dice
tal que
irreducible si para cualquier pareja I, J
i(π) = I
y
t(π) = J .
Si
G
27
de vértices
no es irreducible, se llama
La gura 5 muestra un ejemplo de grafo reducible, ya que no hay en él un camino desde hasta
I
J.
Figura 5.
Proposición 2.26.
shift irreducible.
Sea G un grafo esencial. G es irreducible si, y sólo si, XG es un espacio
G irreducible. Sean u, w ∈ B (XG ). Entonces u y w G (lema 2.22). Por ser G irreducible, hay un camino v en G desde t(u) hasta i(w), por lo que uvw es camino en G y, nuevamente por lema 2.22, uvw ∈ B (XG ). Supongamos ahora que XG es irreducible. Sean I, J vértices en G, y sean a y b aristas en G tales que t(a) = I , i(b) = J . Tales aristas existen pues G es esencial. Por lema 2.22, a y b están en B (XG ). Por irreducibilidad de XG , existe v ∈ B (XG ) tal que avb ∈ B (XG ). Tal v debe ser entonces camino en G desde t(a) hasta i(b), es decir, camino desde I hasta J . Luego, G es irreducible. Demostración. Primero supongamos
son caminos en
3.
Representación de shifts de tipo nito por medio de grafos
Hemos presentado, en la sección anterior, los shifts de aristas, que resultaron ser STF de memoria 1. Por lo tanto, un STF que no tenga memoria 1 no puede ser un shift de aristas. Más aún, el siguiente ejemplo muestra que hay STF de memoria 1 que no son shifts de aristas.
G tal que XG sea el shift de la razón de oro. Para XG = X{11} . Por prop. 2.23, podríamos suponer que G es esencial. Entonces debería contener exactamente dos aristas llamadas 0 y 1. La arista 1 debería ∞ iniciar en un nodo y terminar en otro distinto (de lo contrario, 1 estaría en XG , lo que no puede ser) y entonces la arista 0 debería ir desde t(1) hasta i(1) (pues en otro caso G no sería esencial). Pero entonces XG 6= X{11} , contradicción que proviene de suponer la existencia de tal G. Ejemplo 2.27. No existe un grafo
verlo, supongamos que
G
cumple que
A pesar de que los shifts de aristas aparecen como particulares shifts de tipo nito, mostraremos ahora que todo shift de tipo nito puede recodi carse a un shift de aristas.
Si X es un shift de tipo nito de memoria M , entonces X [M +1] es un shift de aristas. En consecuencia, todo shift de tipo nito es conjugado a un shift de aristas. Teorema 2.28.
M . Podemos suponer M ≥ 1. Sea F tal que X = XF , siendo todos los bloques en F de largo M + 1. Hagamos V = BM (X) y Σ = BM +1 (X). Para a = a1 a2 · · · aM aM +1 ∈ Σ, de namos i(a) = a1 · · · aM y t(a) = a2 · · · aM aM +1 . Puede verse que i(a) y t(a) están en V , ya que son subbloques de a1 · · · aM aM +1 ∈ B(X). De namos Demostración. Sea
X
un STF de memoria
28
2. SHIFTS DE TIPO FINITO
G = (V, Σ, i, t). Notar que, dados vértices I = a1 · · · aM y J = b1 · · · bM , hay una única arista de I a J si, y sólo si, a2 · · · aM = b1 · · · bM −1 y a1 · · · aM bM ∈ BM +1 (X). Es decir, hay arista de I a J si, y sólo si, I y J solapan progresivamente y el bloque obtenido de agregar a I el último símbolo de J está en BM +1 (X). [M +1] Veri quemos ahora que XG = X . Sea x ∈ XG . Se tiene que, para todo k ∈ Z, xk ∈ Σ (es decir, xk es un bloque de tamaño M +1 en el lenguaje de X ), y t (xk ) = i (xk+1 ). Pero si xk = a1 · · · aM +1 y xk+1 = b1 · · · bM +1 , es t (xk ) = a2 · · · aM +1 e i (xk+1 ) = b1 · · · bM . Se tiene entonces que xk y xk+1 solapan progresivamente. −1 De namos entonces x = βM +1 (x). Para cualquier k ∈ Z, x[k,k+M ] = xk ∈ BM +1 (X), por lo que x no tiene bloques en F , es decir, x ∈ X , y entonces x = βM +1 (x) pertenece a X [M +1] . [M +1] . Sea x tal que βM +1 (x) = x. Se tiene que, para cualquier k ∈ Z, Ahora sea x ∈ X es xk = xk · · · xk+M y xk+1 = xk+1 · · · xk+M +1 , por lo que xk ∈ BM +1 (X) = Σ y t(xk ) = xk+1 · · · xk+M = i(xk+1 ) de acuerdo a la de nición de G. Entonces, x ∈ XG . [M +1] La última a rmación del teorema se deduce del hecho de que X ∼ X . X = X{11} , X es STF de memoria 1. Tenemos que B1 (X) = {0, 1} = V y que B2 (X) = {00, 01, 10} = Σ. De nimos i(00) = i(01) = 0, i(10) = 1, t(00) = t(10) = 0 y t(01) = 1. El grafo (V, Σ, i, t) mostrado en la gura 6 es precisamente X [2] . Ejemplo 2.29. Si
Figura 6.
Dado un shift de aristas
XG ,
nos preguntamos si las presentaciones con solape de
XG
son
también shifts de aristas, y, en caso de serlo, si podemos construir los correspondientes grafos directamente a partir de
G.
Definición 2.30. Sea
G
un grafo, y sea
N
un entero positivo. Se de ne el grafo
G[N ]
del
siguiente modo:
G[1] = G. [N ] para N ≥ 2, los vértices de G son los caminos en G de longitud N − 1, y las aristas [N ] de G son los caminos en G de longitud N . Si a = a1 · · · aN es una arista, de nimos iG[N ] (a) = a1 · · · aN −1 y tG[N ] (a) = a2 · · · aN . Obsérvese que G[N ] es un grafo bien de nido. Ejemplo 2.31. Sea G = (V, Σ, i, t) con V = {I, J}, Σ = {e, f, g}, i(e = i(f ) = I , i(g) = J , t(e) = t(g) = I , t(f ) = J . G[1] es el propio G. G[2] tiene vértices {e, f, g} y aristas {ee, ef, f g, ge, gf }. G[3] tiene vértices {ee, ef, f g, ge, gf } y aristas {eee, eef, ef g, f ge, f gf, gee, gef, gf g}. Todos ellos se muestran en la gura 7. Proposición 2.32.
XG[N ] .
Si G es un grafo esencial y N es un entero positivo, entonces (XG )[N ] =
Demostración. Los símbolos para
(XG )[N ]
son los
N -bloques
de
XG ,
que son los caminos
N en G (lema 2.22). Pero éstos son precisamente los símbolos para XG[N ] . Una sucesión bi-in nita de estos símbolos está en ambos espacios shift precisamente cuando dos símbolos de largo
consecutivos solapan progresivamente, de donde se concluye el resultado.
3. REPRESENTACIÓN DE SHIFTS DE TIPO FINITO POR MEDIO DE GRAFOS
G[1]
G[2]
29
G[3]
Figura 7.
Un camino bi-in nito en un grafo
G
determina una sucesión bi-in nita de vértices de ese
grafo, a saber, los vértices que el camino bi-in nito atraviesa (pero a una sucesión bi-in nita de vértices puede corresponderle más de un camino bi-in nito, a menos que el grafo no posea
aristas en paralelo entre dos nodos). Formalmente, sea G = (V, Σ, i, t) un grafo, y sea (xk )k∈Z un punto de XG . Entonces, la sucesión bi-in nita de vértices que este camino bi-in nito determina Z es el punto (i(xk ))k∈Z , que pertenece al full shift V . Para considerar estos recorridos bi-in nitos, introducimos la matriz de incidencia de un grafo.
G = (V, Σ, i, t) un grafo con matriz de incidencia de G es la matriz B , de tamaño |V | × |V | con V , tal que, para vértices m, n ∈ V , 1 si (AG )mn > 0 Bmn = 0 si (AG )mn = 0 Definición 2.33. Sea
de adyacencia
G
desde
La
matriz
las y columnas indizadas por
(m, n) de la matriz de incidencia es 1 o 0, dependiendo m hacia n (en caso de haber, no importa cuántas hay).
Es decir, la entrada arista en
AG .
de si hay o no
Ahora consideraremos el conjunto de todas las sucesiones bi-in nitas de vértices que determinan los caminos bi-in nitos en Definición 2.34. Sea
G,
y que resultará ser también un espacio shift.
G = (V, Σ, i, t)
vértices de G es el conjunto
un grafo con matriz de incidencia
B.
El
shift de
ˆ G = (xk )k∈Z ∈ V Z : ∀k ∈ Z, Bx x = 1 X k k+1 Proposición 2.35.
Los shifts de vértices son shifts de tipo nito de memoria 1.
Demostración. Sea G = (V, Σ, i, t) un grafo con matriz de incidencia B . Consideremos ˆ G = XF . F = {mn ∈ V 2 : Bmn = 0}, y veamos que X ˆ G , y consideremos j, k ∈ Z. Si k − j + 1 6= 2, x[j,k] ∈ Sea x ∈ X / F (pues F contiene sólo ˆ G , es Bx x = 1, palabras de largo 2). Y si k−j +1 = 2, es x[j,k] = xj xj+1 , pero, por estar x en X j j+1 por lo que x[i,j] ∈ / F . Entonces ningún bloque de x pertenece a F , es decir, x ∈ XF . Recíprocamente, si x ∈ XF , se tiene que, para todo j ∈ Z, x[j,j+1] ∈ / F , de donde Bxj xj+1 = 1, ˆ G. por lo que x ∈ X ˆ G es un STF de memoria 1. Ya que todos los bloques de F tienen largo 2, se sigue que X Proposición 2.36.
1. 2. 3.
La familia de todos los shifts de tipo nito de memoria 1 es la familia de todos los shifts de vértices. Cualquier shift de aristas es un shift de vértices (en un grafo diferente). Si X es un shift de tipo nito de memoria M , X [M ] es un shift de vértices. De hecho, ˆ G = X [M ] y XG = X [M +1] . existe un grafo G tal que X
30
2. SHIFTS DE TIPO FINITO
Demostración.
1. La proposición 2.35 muestra que cualquier shift de vértices es un SFT de memoria 1. Ahora, sea
XF
un espacio shift con todos los bloques en
F
de largo 2. De namos un
G como sigue: su conjunto de vértices es V = B1 (XG ), y para m, n ∈ V , pongamos mn de m a n si, y sólo si, mn ∈ / F . La matriz de incidencia de G tendrá entonces, en la posición (m, n), un 1 si mn ∈ / F , y un 0 si mn ∈ F . Luego, un punto de Z ˆ V está en XG precisamente cuando para todo k ∈ Z, Bxk xk+1 = 1, o, equivalentemente, ˆ G = XF . cuando xk xk+1 ∈ / F , mostrando que X grafo
una única arista
2. El enunciado es consecuencia directa del ítem anterior y del hecho de que todo shift de aristas es un STF de memoria 1. 3. Veamos que el grafo G construido en la prueba del teorema 2.28, aparte de satisfacer [M +1] ˆ G = X [M ] . que XG = X , cumple que X
G construido tiene conjunto de vértices V = BM (X), y entre los vértices I = a1 · · · aM y J = b1 · · · bM hay arista si, y sólo si, a2 · · · aM = b1 · · · bM −1 y a1 · · · aM bM ∈ BM +1 (X). Es decir, llamando B a la matriz de incidencia, se tiene que BIJ = 1 si, y sólo si, I y J solapan progresivamente y el bloque obtenido de agregar a I el último símbolo de J está en BM +1 (X). Recordemos también que es X = XF para alguna colección F de bloques de tamaño M + 1. ˆ G . Se tiene que, para todo k ∈ Z, xk ∈ V , y Bx x Sea x ∈ X = 1, de donde xk k k+1 −1 y xk+1 solapan progresivamente. De namos x = βM (x). Se tiene que, para cualquier k ∈ Z, xk · · · xk+M ∈ BM +1 (X) (pues es el bloque que resulta de agregar a xk el último / F , y entonces x ∈ X , así que x ∈ X [M ] . símbolo de xk+1 ), es decir, xk · · · xk+M ∈ [M ] Ahora sea x ∈ X . Sea x tal que βM (x) = x. Se tiene que, para cualquier k ∈ Z, es xk = xk · · · xk+M −1 ∈ BM (X), xk+1 = xk+1 · · · xk+M ∈ BM (X), y xk · · · xk+M ∈ ˆ G. BM +1 (X), por lo que Bxk xk+1 = 1. Luego, x ∈ X Recordemos que el grafo
4.
Desdoblamiento de estados
El desdoblamiento de estados es un procedimiento para construir nuevos grafos a partir de uno dado. Comenzando con una partición del conjunto de aristas, cada estado es desdoblado en una cierta cantidad de estados derivados. Aunque el grafo resultante puede parecer muy distinto del original, ambos tienen shifts de aristas conjugados. Hay una operación inversa del desdoblamiento, llamada amalgama de estados. Resulta ser que cualquier conjugación entre shifts de aristas puede dividirse en una sucesión nita de desdoblamientos y amalgamas de estados. Esto, junto a aplicaciones para la producción de códigos de estados nitos, explica la crucial importancia del desdoblamiento de estados en dinámica simbólica. Comenzamos con una descripción del desdoblamiento de un solo estado, operación que
desdoblamiento elemental. Sea G un grafo con conjunto de estados V y conjunto de aristas Σ. Fijemos un estado I ∈ V , y supongamos, por el momento, que no hay bucles en I . Hagamos una partición del conjunto de aristas salientes de I (es decir, ΣI ) en dos subconjuntos 1 2 disjuntos no vacíos ΣI y ΣI . Construimos un nuevo grafo H , basándonos en esta partición, como 1 2 i sigue: el conjunto de estados es W = (V − {I}) ∪ {I , I }. Para cada arista e ∈ ΣI (donde i i es 1 o 2), pongamos una arista en H desde I hasta t(e) llevando el mismo nombre e (notar I que, como no hay bucles en I , t(e) 6= I , de modo que t(e) ∈ W ). Para cada f en Σ (es decir, 1 1 2 cada arista f llegando a I ), pongamos dos aristas f desde i(f ) hasta I y f desde i(f ) hasta 2 I . Todas las otras aristas de G (es decir, las que no están vinculadas al nodo I ) se copian en H con el mismo nombre e idénticos nodos inicial y terminal. Queda entonces completa la construcción de H . Hablando sin precisión, desdoblamos las aristas salientes y reproducimos las aristas entrantes a I . La gura 8 muestra cómo es la operación. denominaremos
4. DESDOBLAMIENTO DE ESTADOS
31
Figura 8.
G el grafo de la izquierda en la gura 9, y consideremos la partición de Σ2I = {b, c}. A la derecha de esa gura se muestra el grafo resultante I con esa partición.
Ejemplo 2.37. Sea
ΣI
dada por
Σ1I = {a}
de desdoblar el estado
y
Figura 9.
Supongamos que
H
se forma a partir de
G
desdoblando el estado
I,
como se describió
más arriba. A continuación construimos una conjugación entre sus shifts de aristas XG y XH . i I De namos la transformación monobloque Ψ : B1 (XH ) → B1 (XG ) mediante Ψ(f ) = f si f ∈ Σ I y Ψ(e) = e si e ∈ / Σ . En otras palabras, Ψ simplemente borra supraíndices. Es posible chequear (lo haremos más adelante) que borrar supraíndices de los caminos en
G,
de modo que
Ψ
H produce caminos en ψ : XH → XG . Ahora
induce un código de ventana deslizante monobloque
Φ : B2 (XG ) → B1 (XH ) mediante: si f∈ / ΣI f f 1 si f ∈ ΣI y e ∈ Σ1I Φ(f e) = 2 f si f ∈ ΣI y e ∈ Σ2I
de namos un código 2-bloque
Es decir,
Φ
se anticipa un símbolo y puede añadir un supraíndice, dependiendo de lo que ve.
G en 0 yanticipación 1. Puesto que agregar y eliminar supraíndices no tiene efecto, vemos que ψ φ(x) = x para todo x ∈ XG . Recíprocamente, los supraíndices están unívocamente determinados por la de nición 1 2 de Φ, ya que ΣI y ΣI son una partición de ΣI , de modo que φ ψ(y) = y para todo y ∈ XH . Luego, φ es una conjugación de XG en XH .
Es factible chequear (también lo haremos más adelante) que caminos de
H , y, por lo tanto, induce un CVD φ de XG
Ejemplo 2.38. Las acciones de
2.37 se muestran a continuación:
φ
y
ψ
en
XH
Φ
transforma caminos de
con memoria
sobre puntos típicos
x ∈ XG , y ∈ XH
del ejemplo
32
2. SHIFTS DE TIPO FINITO
x = ···
d
a
d
b
d
φ
↓
c
e
.a
d
↑
ψ
c
e
b
···
d
d1 a d2 b d2 c e1 . a d2 c e2 b · · · Notar que no gura el símbolo en y debajo de la última d de x, pues para ello hace falta conocer el símbolo a la derecha de dicha d. y = ···
El procedimiento general de desdoblamiento de estados es una extensión, en dos sentidos, del proceso elemental recientemente descripto: por un lado, las aristas salientes de un estado pueden particionarse en una cantidad de conjuntos que no necesariamente sea
2,
y, por otro
lado, se puede particionar simultáneamente los conjuntos de aristas salientes de todos los estados (incluyendo los que presentan bucles).
G = (V, Σ, iG , tGP ) un grafo. Para cada estado I ∈ V , sean de nidos un entero positivo m(I) tal que m(I) ≤ | I |, y una partición de ΣI en conjuntos disjuntos m(I) 1 2 (no vacíos) ΣI , ΣI , . . . , ΣI (es decir, m(I) ≥ 1 es la cantidad de átomos en la partición de ΣI ). Sea P la partición resultante de Σ. El grafo de estados desdoblados G[P] formado a partir de G usando P es el grafo (W, Σ0 , iH , tH ) de nido como sigue: k Conjunto de estados: W = I : I ∈ V ∧ 1 ≤ k ≤ m(I) . j 0 Conjunto de aristas: Σ = e : e ∈ Σ ∧ 1 ≤ j ≤ m tG (e) . n j n Función de nodos iniciales: iH (e ) = (iG (e)) donde n es tal que e ∈ Σi (e) . G j j Función de nodos terminales: tH (e ) = (tG (e)) . n j Es decir, si e ∈ Σ va de I a J en G, entonces existe n tal que e ∈ ΣI , y el estado inicial de e [P] n j j n j en G es I y el terminal es J ; es decir, e va de I a J . Un desdoblamiento elemental de G por el estado I ocurre cuando m(I) = 2 y m(J) = 1 para todo J 6= I . Definición 2.39. Sea
se tiene que m(J) = 1, los supraíndices 1 (en el nombre del 1 estado y de las aristas entrantes a J en el grafo desdoblado) se vuelven redundantes, y no hay Cuando para algún estado
J
problemas en omitirlos (pues se obtiene un grafo isomorfo), como hicimos en nuestras primeras discusiones respecto de los desdoblamientos elementales. Asumiremos que los elementos de las particiones de aristas salientes de cada nodo nunca son vacíos. Esto garantiza que el grafo obtenido de desdoblar estados en un grafo esencial (o irreducible) es también esencial (o irreducible). Observación 2.40. De la de nición del grafo desdoblado, se desprende que una arista
n
ej
k
n va de I hasta J si, y sólo si, e ∈ ΣI (lo cual implica que iG (e) = I ), tG (e) = J y j = k . Por n k ello, la cantidad de aristas desde I hasta J en el grafo desdoblado es precisamente la cantidad n de aristas en ΣI que terminan en J en el grafo G. Es decir,
0 0J k ΣI n ∩ Σ = ΣnI ∩ ΣJ para todos
k ∈ {1, . . . , m(J)}, n ∈ {1, . . . , m(I)}, I, J ∈ V (G).
el grafo de la izquierda en la gura 10, de modo que ΣI = {e, f } y {g}. Tomemos las siguientes particiones: Σ1I = {e}, Σ2I = {f } y Σ1J = {g}, de modo que = 2 y m(J) = 1. Entonces P = {Σ1I , Σ2I , Σ1J }. El grafo resultante del desdoblamiento se
Ejemplo 2.41. Sea
ΣJ = m(I)
G
muestra a la derecha en esa misma gura. Notar que, en particular, el bucle 1 1 2 1 2 desdobla en un bucle e en el estado I y otra arista e desde I hasta I .
e
en el estado
ΣI ,
a saber,
Σ1I = {e}
y
se
{e, f }Z . EsenΣ2I = {f }. El grafo
Ejemplo 2.42. La gura 11 muestra a la izquierda un grafo del full shift
cialmente, hay una sola partición no trivial de
I
4. DESDOBLAMIENTO DE ESTADOS
33
Figura 10.
resultante del desdoblamiento se muestra en la misma gura a la derecha, y puede advertirse que, salvo cambio de nombres, es esencialmente la presentación del full shift en bloques de tamaño
2
con solape.
Figura 11.
1 Ejemplo 2.43. Para el grafo G a la izquierda en la gura 12, sea P de nida por ΣI = {a}, [P] 2 2 1 1 ΣI = {b, c}, ΣJ = {d}, ΣK = {e} y ΣK = {f }. El grafo G se muestra a la derecha de esa misma gura.
Figura 12.
34
2. SHIFTS DE TIPO FINITO
Como la construcción de [P] que G es el grafo de
G[P]
usa particiones de conjuntos de aristas
desdoblamiento de salidas
una correspondiente noción de
formado a partir de
desdoblamientos de entradas,
salientes, decimos G usando P. Hay
usando particiones de conjuntos
de aristas entrantes. un grafo. Para cada estado I ∈ V , sea de nida una I I I partición de Σ en conjuntos disjuntos (no vacíos) Σ1 , Σ2 , . . . , Σm(I) , donde m(I) ≥ 1 es la canI tidad de conjuntos en la partición de Σ . Sea P la partición resultante de Σ. El Definición 2.44. Sea
G = (V, Σ, i, t)
I
grafo de desdoblamiento de entradas G[P] formado a partir de G usandoP tiene como conjunto de esta {Ik : I ∈ V ∧ 1 ≤ k ≤ m(I)} y como conjunto de aristas a ej : e ∈ Σ ∧ 1 ≤ j ≤ m i(e) J Si e ∈ Σ va de I a J en G, entonces existe j tal que e ∈ Σj , y el estado inicial de ei en G[P] Ii y el terminal es Jj . dos a
.
es
G el grafo a la izquierda en la gura 13. De namos P mediante ΣI1 = = {f }. El correspondiente G[P] se muestra en esa misma gura, a la
Ejemplo 2.45. Sea
{e}, ΣI2 derecha.
= {g}
J y Σ1
Figura 13.
también como un desdoblamiento de salidas de G (y similarmente para los desdoblamientos de entradas). También es apropiado dar Será conveniente considerar a un grafo isomorfo a
G[P]
un nombre a la operación inversa del desdoblamiento.
H
es un
desdoblamiento de un grafo G, y G es una amalgama
o a
G[P] ,
para alguna partición
Definición 2.46. Un grafo
de
H,
si
H
es isomorfo a
[P]
G
P
del conjunto de aristas de
G.
desdoblamiento de salidas, desdoblaamalgama de entradas. Notar que los isomor smos
Si hace falta mayor precisión, emplearemos los términos
miento de entradas, amalgama de salidas
o
de grafos, de acuerdo a nuestra de nición, pueden ser vistos como cualquiera de estas cuatro operaciones. Al igual que en los desdoblamientos elementales, los desdoblamientos en general producen grafos cuyos shifts de aristas son conjugados a los del grafo inicial.
Si un grafo H es un desdoblamiento de un grafo G, entonces los shifts de son conjugados.
Teorema 2.47.
aristas XG y XH
Demostración. Probaremos sólo para el caso de los desdoblamientos de salida, siendo el
otro caso similar. Ya que los isomor smos de grafos establecen conjugaciones, y que la composición de con[P] jugaciones es otra conjugación, alcanza con probar el resultado para el caso en que H = G . Mostraremos, en sucesivos pasos, que existen CVD ψ : XH → XG y φ : XG → XH tales que φ = ψ −1 , con lo que quedará demostrado que φ es una conjugación, y, por lo tanto, XG ∼ XH .
4. DESDOBLAMIENTO DE ESTADOS
De namos la transformación monobloque [0,0] y consideremos ψ = Ψ∞ .
35
Ψ : B1 (XH ) → B1 (XG )
mediante
Ψ (ej ) = e,
y ∈ XH , y tomemos k ∈ Z. Debe ser yk = ej , yk+1 = f m con e, f ∈ Σ y tH (e ) = iH (f m ); por de nición de H , esto implica que (tG (e))j = (iG (f ))n con n tal n que f ∈ Σi (f ) , de donde concluimos que tG (e) = iG (f ) (es decir, ef es camino en G) y G j que j = n, es decir, f ∈ Σi (f ) . Por lo tanto, G tG ((ψy)k ) = tG (Ψ(yk )) = tG Ψ(ej ) = tG (e) = iG (f ) = iG (Ψ(f m )) = iG ((ψy)k+1 ) Sea j
mostrando que
ψ(y) ∈ XG ,
y entonces
ψ (XH ) ⊆ XG ,
ψ : XH → XG
por lo que
es un
CVD monobloque bien de nido. Ahora de namos la transformación de bloques siguiente: si
ef ∈ B2 (XG ),
entonces existe un
Φ : B2 (XG ) → B1 (XH ) por j único j tal que f ∈ Σi (f ) , G
medio de lo y de nimos
[0,1] Φ∞ .
Φ(ef ) = ej . Consideremos φ = Sea x ∈ XG , y tomemos k ∈ Z. Tenemos que xk , xk+1 , xk+2 ∈ Σ, xk xk+1 , xk+1 xx+2 ∈ B2 (XG ), y existen I, J ∈ V tales que tG (xk ) = iG (xk+1 ) = I , tG (xk+1 ) = iG (xk+2 ) = J . n1 n2 n1 Sean n1 y n2 tales que xk+1 ∈ ΣI y xk+2 ∈ ΣJ . Entonces Φ(xk xk + 1) = xk y n2 Φ(xk+1 xk+2 ) = xk+1 . Luego, tH ((φx)k ) = tH (Φ(xk xk+1 )) = tH (xnk 1 ) = (tG (xk ))n1 = I n1 2 iH ((φx)k+1 ) = iH (Φ(xk+1 xk+2 )) = iH xnk+1 = (iG (xk+1 ))n1 = I n1 mostrando que
φ(x) ∈ XH ,
y entonces
φ (XG ) ⊆ XH ,
φ : XG → XH
por lo que
es un
CVD bien de nido.
x ∈ XG y k ∈ Z. Entonces (φx)k = Φ (xk xk+1 ) = xnk para algún n, y entonces (ψ(φx))k = Ψ ((φx)k ) = Ψ (xnk ) = xk . En consecuencia, (ψ ◦ φ)(x) = x para todo x ∈ XG . Recíprocamente, sean y ∈ XH y k ∈ Z. Razonando como antes, debe ser yk yk+1 = ej f m con f ∈ ΣjiG (f ) , por lo que (ψy)[k,k+1] = ef (con ef ∈ B2 (XG ) pues ψ(y) ∈ XG ) j j y entonces Φ(ef ) = e , así que (φ(ψy))k = Φ (ψy)[k,k+1] = Φ(ef ) = e = yk . En consecuencia, (φ ◦ ψ)(y) = y para todo y ∈ XH . Sean
Queda entonces demostrado que
φ : XG → XH
es código de ventana deslizante que posee función
inversa que es también código de ventana deslizante, por lo que
XG
y
XH
son conjugados.
H es un desdoblamiento de salidas de G, hay un XG , que se denomina código de amalgama de salidas, cuyo inverso es un código con memoria 0 y anticipación 1 llamado código de de desdoblamiento de salidas. Análogamente, si H es un desdoblamiento de entradas de G, tenemos un código de La demostración anterior muestra que si
código monobloque desde
XH
a
amalgama de entradas monobloque con inverso denominado código de desdoblamiento de entradas que tiene memoria 0 y anticipación 1. Del teorema previo, se deduce que si un grafo ( nita) de desdoblamientos y amalgamas de un grafo
H puede ser obtenido por una sucesión G, entonces XH ∼ XG (la conjugación es
la composición de los sucesivos códigos de desdoblamiento o amalgama). Aunque no lo haremos aquí, es posible probar también el recíproco: cualquier conjugación entre shifts de aristas puede escribirse como una composición de códigos de desdoblamientos y amalgamas. Este importante resultado se conoce como
4.1.
Teorema de la Descomposición.
Los desdoblamientos y las matrices de adyacencia.
Consideremos el ejem-
plo 2.43. Los estados de G y de su desdoblado son, respectivamente, V = {I, J, K} y W = {I 1 , I 2 , J 1 , K 1 , K 2 }. Podemos representar cómo los estados en W se derivan a partir de los estados en
V
por medio de la siguiente matriz
D
con las indizadas por
V
y columnas indizadas
36
2. SHIFTS DE TIPO FINITO
por
W
(en el orden dado):
1 1 0 0 0 D= 0 0 1 0 0 0 0 0 1 1 1 2 Por ejemplo, DI,I 1 = 1 = DI,I 2 pues I e I resultan de desdoblar DI,J 1 = 0 pues J 1 no procede del desdoblamiento de I .
el estado
I,
mientras que
Por otro lado, podemos especi car las cantidades de aristas en cada partición que terminan en un estado dado, por medio de la siguiente matriz indizadas por
V
E
con las indizadas por
W
y columnas
(en el orden dado):
E= donde, por ejemplo,
EI 1 ,J
0 0 1 0 1
1 1 0 1 0
0 1 0 0 0
es la cantidad de aristas en
Σ1I
que terminan en
J,
en este caso una
sola arista. Un cómputo directo muestra que el producto y que
ED
DE
es igual a la matriz de adyacencia de
G,
da la matriz de adyacencia del grafo desdoblado. Veremos ahora que esta situación
se cumple en general.
G = (V, Σ, i, t) un grafo, P una partición de salida de Σ, y H = G[P] . conjunto de vértices de H . La matriz de división D para P es la
Definición 2.48. Sea
W al V × W de nida
Designemos por matriz sobre
por
DI,J k = La
1 0
si si
I=J I 6= J
matriz de aristas E para P es la matriz sobre W × V EI n ,J
de nida por
= ΣnI ∩ ΣJ
De la observación 2.40, surge que EI n ,J corresponde a la cantidad de aristas en el grafo I n hasta J k (cualquiera sea k ∈ {1, . . . , m(J)}).
desdoblado que van desde desde
Las matrices de división y de aristas permiten obtener las matrices de adyacencia de los grafos involucrados en un desdoblamiento, de acuerdo al siguiente resultado. Teorema 2.49.
Sean G, P, H , D y E como en la de nición anterior. Entonces,
DE = AG
ED = AH
Demostración. Se tiene que
X
(DE)I,J =
DI,K EK,J =
X m(L) X L∈V i=1
K∈W
m(I)
DI,Li ELi ,J =
X
m(I)
DI,I i EI i ,J =
i=1
X
EI i ,J
i=1
m(I) m(I) X [ [ i J i J i J ΣI ∩ Σ = = ΣI ∩ Σ = ΣI ∩ Σ i=1 i=1 i=1 = ΣI ∩ ΣJ = (AG )I,J m(I)
mostrando que
DE = AG .
Por otro lado,
(ED)I i ,J j =
X
EI i ,K DK,J j = EI i ,J DJ,J j = EI i ,J
K∈V
j = ΣiI ∩ ΣJ = Σ0I i ∩ Σ0J = (AH )I i ,J j por lo que
ED = AH .
Capítulo 3
SHIFTS SÓFICOS Supongamos que las aristas de un grafo son rotuladas con símbolos de algún alfabeto
A,
con la posibilidad de que dos o más aristas puedan llevar el mismo rótulo. Cualquier camino Z biin nito en el grafo produce un punto en el full shift A por lectura de los rótulos de sus aristas, y el conjunto de todos los puntos que así pueden obtenerse se llama un shift só co. Los shifts só cos son importantes por un número de razones. Veremos en este capítulo que son precisamente aquellos espacios shift que son factores de shifts de tipo nito. Así, la clase de los shifts só cos es la más pequeña colección de espacios shift que contiene a los STF y que también contiene a todos los factores de cada espacio de la colección. Los shifts só cos son los análogos de los lenguajes regulares de la teoría de autómatas, y varios de los algoritmos que veremos en ÿ3.4 son adaptaciones de los de autómatas de estados nitos. Los shifts de tipo nito y los só cos son modelos naturales para almacenamiento y transmisión de la información; estudiaremos su uso en los códigos de estados nitos en el capítulo 5.
1.
Presentaciones de shifts só cos
Los shifts só cos se de nen usando grafos a cuyas aristas se asigna rótulos, donde varias aristas pueden llevar el mismo rótulo.
grafo rotulado G es un par (G, L), donde G es un grafo con conjunto rotuladora L : Σ → A asigna a cada arista e de G un rótulo L(e) del alfabeto A. El grafo subyacente de G es G. Un grafo rotulado se dice irreducible si su grafo Definición 3.1. Un
de aristas
Σ,
y la
subyacente es irreducible. A veces nos referiremos a un grafo rotulado simplemente como un grafo, y a estados o aristas del grafo subyacente
G
de un grafo rotulado
G
G . La rotuladora L de G. En un extremo,
como estados o aristas de
A a las aristas A = Σ y L(e) = e para toda e ∈ Σ, dando una rotulación uno a uno de aristas por sus nombres. En el otro extremo, A podría consistir de una única letra a y todas las aristas estarían rotuladas con a, es decir, L(e) = a para toda e ∈ Σ. Usualmente, L será no inyectiva, de modo que varias aristas llevarán el mismo rótulo. Aunque L no necesita ser sobreyectiva, toda letra que no esté en la imagen de L no son usadas. Usaremos normalmente caracteres como e, f o g para los nombres de las aristas, y a, b, c o enteros pequeños para sus rótulos. La
puede ser cualquier asignación de letras de un alfabeto podríamos tener
gura ... muestra dos ejemplos de grafos rotulados típicos. Así como un grafo grafo rotulado
(I, J)
G
G
es convenientemente descripto por su matriz de adyacencia
tiene como análogo una
contiene la suma formal de los rótulos de todas las aristas que van de
carácter
∅
AG ,
un
matriz de adyacencia simbólica AG , cuya entrada
si no hay tal arista. Por ejemplo, si
G
y
H
I
a
J,
o un
son los grafos rotulados de la gura ... a
izquierda y derecha respectivamente, entonces
AG =
a b b a
a c b AH = ∅ b a + b a c ∅
Hay un análogo del homomor smo de grafos para grafos rotulados, que añade el requisito de que los rótulos se preserven.
G = (G, LG ) y H = (H, LH ) grafos rotulados. Un homomor smo de grafos rotulados desde G a H es un homomor smo de grafos (∂Φ, Φ) : G → H tal que Definición 3.2. Sean
37
38
3. SHIFTS SÓFICOS
LH (Φ(e)) = LG (e) para toda arista e ∈ Σ(G). En este caso, escribimos (∂Φ, Φ) : G → H. Si ambas ∂Φ y Φ son biyecciones, entonces (∂Φ, Φ) se llama isomor smo de grafos rotulados, denotado mediante (∂Φ, Φ) : G ∼ = H. Dos grafos rotulados son isomorfos como grafos
rotulados (o simplemente isomorfos) si existe un isomor smo de grafos rotulados entre ellos.
Se puede pensar que dos grafos rotulados isomorfos son el mismo para nuestros propósitos. Si
G = (G, L)
es un grafo rotulado, entonces
caminos biin nitos del grafo subyacente de
G
G.
L
puede ser usada para rotular caminos y
De nimos el
rótulo de un camino π = e1 e2 . . . en
mediante
L(π) = L(e1 )L(e2 ) . . . L(en ) n-bloque sobre A, y al cual a veces nos referiremos como un bloque rotulado. Para el camino vacío ε, de nimos L(ε) = ε, la palabra vacía sobre A. Si ξ = . . . e−1 e0 e1 . . . es un camino biin nito en G, de modo que ξ es un punto del shift de aristas XG , de nimos el rótulo del camino xi como L∞ (ξ) = . . . L(e−1 )L(e0 )L(e1 ) . . . ∈ AZ que es un
El conjunto de los rótulos de todos los caminos biin nitos en
G
es denotado por
XG = x ∈ AZ : x = L∞ (ξ) para algún ξ ∈ XG = {L∞ (ξ) : ξ ∈ XG } = L∞ (XG )
A-shift. Por ejemplo, si G es el grafo rotulado de la izquierda XG es el full {a, b}-shift; el grafo rotulado H de la derecha produce un subconjunto propio del full {a, b, c}-shift (¾por qué?). Notar también que si G y H son isomorfos, entonces XG = XH .
Así,
XG
es un subconjunto del full
en la gura ..., entonces
Este capítulo trata los espacios shift que surgen de grafos rotulados. Definición 3.3. Un subconjunto
algún grafo rotulado cual
XG = X .
G.
Una
X
de un full shift es un
presentación de un shift só co X
La transformación shift en
XG
es denotada por
shift só co
si
X = XG para G para el
es un grafo rotulado
σG .
El término só co fue acuñado por Weiss, y se deriva de la palabra hebrea para nito. Es importante darse cuenta de que un shift só co dado tiene muchas presentaciones diferentes. Por ejemplo, la gura ... muestra cuatro presentaciones del full 2-shift, ninguna de las cuales son isomorfas entre sí (aunque los grafos subyacentes de (b) y (c) son grafos isomorfos). Si
X
G = (G, L) y w es un bloque en B(X), decimos que presentación de w si L(π) = w. Un bloque w dado puede tener
es un shift só co presentado por
un camino
π
en
G
es una
varios caminos diferentes que lo presenten. Por ejemplo, en la gura ...(d), el bloque 010001 tiene tres presentaciones, una empezando en cada uno de los tres vértices. Si que un camino biin nito caminos, un punto de
ξ
XG
en
XG
es una
x ∈ XG ,
decimos
presentación de x si L∞ (ξ) = x. Al igual que con los
puede tener varias presentaciones diferentes.
Nuestra de nición de un shift só co no requiere que sea un espacio shift. Sin embargo, siempre lo es. Teorema 3.4.
Los shifts só cos son espacios shift.
X un shift só co sobre A, y G = (G, L) L : Σ → A induce un código monobloque L∞ : XG → XG , X = L∞ (XG ) es un espacio shift por teorema 1.61. Demostración. Sea
Entonces
una presentación de
X.
de modo que su imagen
Nótese que los shifts de aristas son shifts só cos, pues podemos simplemente usar el conjunto de aristas
L(e) = e.
Σ
como alfabeto y, como rotuladora, la función identidad
L : Σ → Σ
dada por
El siguiente resultado extiende esta observación para mostrar que los shifts de tipo
nito son só cos. Teorema 3.5.
Todo shift de tipo nito es un shift só co.
1. PRESENTACIONES DE SHIFTS SÓFICOS
39
M ≥ 0. Sea G el grafo construi[M +1] do según la demostración del teorema 2.28, de modo que X = XG . Recordemos que V (G) = BM (X), Σ(G) = BM +1 (X) y cada arista e1 . . . eM +1 va desde e1 . . . eM hasta e2 . . . eM +1 . Rotulemos la arista e1 . . . eM +1 con el símbolo e1 . Mostraremos que el grafo rotulado G = (G, L) es una presentación de X . [M +1] Sea βM +1 : X → X = XG el código de bloques dado por Demostración. Sea
X
un STF, digamos de memoria
βM +1 (x)[i] = x[i,i+M ]
L x[i,i+M ] = xi , vemos que L∞ (βM +1 (x)) = x para todo x ∈ X , probando que X ⊆ XG . [M +1] Recíprocamente, cada punto ξ ∈ XG = X tiene la forma ξ = βM +1 (x) para algún x ∈ X , así que L∞ (ξ) = L∞ (βM +1 (x)) = x ∈ X . Luego, XG = L∞ (XG ) ⊆ X , y entonces X = XG . Como
Capítulo 4
ASPECTOS TOPOLOGICOS Y DINAMICOS DE LOS ESPACIOS SHIFT El objetivo de este capítulo es analizar a los espacios shift a través de sus características topológicas. Mediante la de nición de una manera adecuada para medir distancias entre tirillas biin nitas, podremos ver a la full shift como un espacio métrico y estudiarla con las herramientas clásicas de la topología y el análisis. De ésto, resultará una caracterización de los espacios shift y de los códigos de ventana deslizante a través de propiedades topológicas. Esto forma parte de investigaciones más o menos recientes (alrededor de 1970) en el área de la Dinámica Simbólica, de modo que se trata de tópicos relativamente nuevos en Matemática, y en franco proceso de expansión. No se pretende dar aquí un estudio detallado de la teoría general de espacios métricos, sino más bien enunciar las de niciones y propiedades básicas de los mismos con el único objetivo de aplicarlos al estudio de los espacios shift. En el presente capítulo, primero de niremos una métrica para la full shift y veremos algunas propiedades básicas importantes de la misma, para luego estudiar la convergencia de sucesiones y arribar a la conclusión de que los espacios shift están caracterizados por ser subconjuntos compactos y shift-invariantes de la full shift. Luego analizaremos la continuidad de acuerdo a la métrica de nida, encontrando que los códigos de ventana deslizante se caracterizan por ser las funciones entre espacios shift que son continuas y conmutan con la función shift.
1. Definición 4.1. Una
d : X × X → R+ 0 1. 2. 3.
métrica
Una métrica para AZ o
función distancia
para un conjunto
d (x, y) = 0 ⇔ x = y ∀x, y ∈ X, d (x, y) = d (y, x) (axioma de simetría) ∀x, y, z ∈ X, d (x, z) ≤ d (x, y) + d (y, z) (desigualdad
El par
(X, d)
X
es una función
con las siguientes propiedades:
se denomina
triangular)
espacio métrico.
Para llevar adelante el objetivo planteado en la introducción, debemos dotar a
AZ
de una
métrica adecuada. Para nuestros propósitos, adecuada va a querer decir que dos puntos x e y de AZ estarán tanto más cerca cuanto más grande sea el bloque central en que coinciden. Así, por ejemplo,
· · · 00010.110101110000 · · ·
y
· · · 10010.110101110010 · · ·
deberán estar entre
sí a una distancia menor que la distancia que haya entre los puntos · · · 00010.1101110000 · · · y · · · 00011.11111111 · · · Para ello, de niremos d : AZ × AZ → R+ 0 mediante
d (x, y) =
0
si
− m´ın{|k|:xk 6=yk }
2
si
x=y x 6= y
En palabras, para encontrar la distancia entre dos puntos distintos coordenada entera −|k| y evaluar 2 .
k
(positiva o negativa) en la que
x
e
y
x e y , hay que detectar la
di eren más cercana a la coordenada
0,
Ejemplo 4.2. Encontremos la distancia entre los puntos
x = · · · 00010.110101110000 · · ·
y = · · · 10010.110101110010 · · · 40
1. UNA MÉTRICA PARA
AZ
41
A n de visualizar mejor, dispongamos ambos puntos uno debajo del otro, y marquemos con
×
las coordenadas en que
xk 6= yk :
−5 −4 −3 −2 −1 0 1 2 3 4 5 6 7 8 9 10 11 x ... 0 0 0 1 0 1 1 0 1 0 1 1 1 0 0 0 0 ... × × × y ... 1 0 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 ... × más = 1/4.
La marca −|−2|
2
cercana a la coordenada
0
corresponde a
k = −2,
de modo que
Notemos que, de acuerdo a esta de nición, el mayor valor que puede tomar
d
d (x, y) = es
1,
que
corresponde al caso en que los dos puntos entre los que se está midiendo la distancia di eren en la coordenada
0.
Justi quemos que la función
d
así de nida es efectivamente una métrica para
AZ :
x e y en AZ , o bien son iguales o bien son distintos. En el primer + caso, es d (x, y) = 0 ∈ R0 . En el caso en que x 6= y , el conjunto {k : xk 6= yk } ⊆ Z es no vacío, de modo que el conjunto {|k| : xk 6= yk } ⊆ N tampoco es vacío, y entonces tiene −t un mínimo elemento N . Ya que la función exponencial 2 es estrictamente positiva + −N para t ∈ R, d (x, y) = 2 ∈ R0 . Esto muestra también que d (x, y) = 0 ⇔ x = y . Dados dos puntos
El cumplimiento del axioma de simetría es directo de ver. Z Para la desigualdad triangular, sean x, y, z ∈ A dos a dos distintos. Llamemos
Nxy = m´ın {|k| : xk 6= yk }
Nyz = m´ın {|k| : yk 6= zk }
Nxz = m´ın {|k| : xk 6= zk }
N = m´ın {Nxy , Nyz }. N = 0, es y0 6= x0 o y0 6= z0 , de modo que d (x, y) = 1 o d (y, z) = 1, y por lo tanto es d (x, y) + d (y, z) ≥ 1 ≥ d (x, z). • Si N > 0, es x[−N +1,N −1] = z[−N +1,N −1] , pues si tomamos i tal que |i| < N , tenemos que |i| < Nxy y |i| < Nyz , de donde xi = yi e yi = zi , por lo que xi = zi . O sea que Nxz ≥ N . Por lo tanto, observando que 2−Nxz ≤ 2−N y que es N = Nxy o N = Nyz ,
Tomemos
•
Si
se tiene
d (x, z) = 2−Nxz ≤ 2−N ≤ 2−Nxy + 2−Nyz = d (x, y) + d (y, z) Es decir, en cualquier caso se veri ca la desigualdad triangular. La función distancia puede restringirse de de la full shift, y el par
(X, d)
AZ × AZ
a
X ×X
para cualquier subconjunto
X
sigue siendo un espacio métrico.
La métrica recientemente de nida recibe el nombre de
métrica usual para los espacios
shift, y es a la que haremos referencia por defecto siempre que hablemos de distancia en espacios shift, a menos que especi quemos lo contrario. Una condición necesaria y su ciente para que dos puntos distintos estén a distancia menor
ε esrictamente positivo es que ambos coincidan en una ventana central de tamaño 2k +1, 1 en donde k = log (a menos que especi quemos otra cosa, log siempre signi cará logaritmo ε en base 2; además, para r ∈ R, brc es la parte entera o piso de r , es decir, el mayor entero que no supera a r ). Para probar la a rmación, notemos que 1 d (x, y) < ε ⇔ 2− m´ın{|k|:xk 6=yk } < ε ⇔ m´ın {|k| : xk 6= yk } > log ε 1 ⇔ m´ın {|k| : xk 6= yk } > log ⇔ x[−blog 1 c,blog 1 c] = y[−blog 1 c,blog 1 c] ε ε ε ε ε Juntando esto con el hecho de que dos puntos de la full shift que están a distancia 0 coinciden en el bloque central de tamaño 2k + 1 cualquiera sea k ∈ N, tenemos el siguiente resultado.
que un
Proposición 4.3.
Sea ε > 0, y x e y dos puntos de AZ . Se tiene que
d (x, y) < ε ⇐⇒ x[−blog 1 c,blog 1 c] = y[−blog 1 c,blog 1 c] ε ε ε ε
42
4. ASPECTOS TOPOLOGICOS Y DINAMICOS DE LOS ESPACIOS SHIFT
En particular, para cualquier K ∈ N, tenemos que d (x, y) < 2−K ⇔ x[−K,K] = y[−K,K] .
(X, d) un espacio métrico, x ∈ X y r ∈ R+ . El entorno de radio r con centro en x, denotado Br (x), es el conjunto de puntos del espacio cuya distancia a x es menor que r . Definición 4.4. Sea
En virtud de la Proposición 4.3, el entorno de radio
ε
con centro en
x ∈ X ⊆ AZ ,
para la
métrica usual, es
Particularmente,
n o Bε (x) = y ∈ X : x[−blog 1 c,blog 1 c] = y[−blog 1 c,blog 1 c] ε ε ε ε para K ∈ N, B2−K (x) = y ∈ X : x[−K,K] = y[−K,K] .
E de un espacio métrico (X, d), se dice que un punto x ∈ E es un punto interior a E si existe r > 0 tal que Br (x) ⊆ E . E es abierto en X si todos sus puntos son puntos interiores a E . Definición 4.5. Dado un subconjunto
Como caso particular, los entornos de cualquier espacio métrico son conjuntos abiertos. Puede demostrarse que cualquier conjunto abierto de un espacio métrico es una unión de entornos, y viceversa. Además, la unión arbitraria de conjuntos abiertos es un conjunto abierto, y la intersección nita de conjuntos abiertos es también un conjunto abierto. En el caso particular de la full shift, a partir de la de nición de conjunto abierto y de la Z caracterización de los entornos, se deduce que un subconjunto X de A es abierto si, y sólo si, Z para cada x ∈ X , existe K ∈ N tal que cualquier punto y ∈ A que satisface y[−K,K] = x[−K,K] pertenece también a
X.
Tal
K
dependerá, en general, de
x.
E de un espacio métrico (X, d), se dice que un punto x ∈ X es un punto de acumulación de E si todo entorno con centro en x tiene un punto de E − {x}. E es cerrado si contiene a todos sus puntos de acumulación. La clausura de E es la unión de E con el conjunto de sus puntos de acumulación. Definición 4.6. Dado un subconjunto
Se tiene que
E
es cerrado si, y sólo si, su complemento es abierto. Además,
y sólo si, la clausura de
E
coincide con
E.
E
es cerrado si,
Puede verse, usando las leyes de De Morgan, que la
intersección arbitraria de conjuntos cerrados es un conjunto cerrado, así como la unión nita de conjuntos cerrados es también un conjunto cerrado.
2.
Sucesiones
(X, d) es una función de N en X . Denotaremos por xn al n-ésimo término de la sucesión, y por {xn }n∈N a la sucesión completa. Cuando el espacio (n) métrico en cuestión sea un espacio shift, denotaremos x al n-ésimo término de la sucesión, pues seguiremos usando xn para referirnos al símbolo que haya en la n-ésima coordenada de la tirilla biin nita x. Una sucesión en un espacio métrico
{xn }n∈N en el espacio (X, d) se dice convergente en X si l´ımn→∞ d (xn , p) = 0. En este caso, escribimos l´ımn→∞ xn = p, o también
Definición 4.7. Una sucesión
p∈X xn −→ p existe
tal que
n→∞
Obsérvese que
l´ımn→∞ xn = p
si, y sólo si,
∀ε > 0, ∃N ∈ N : ∀n ≥ N, d (xn , p) < ε.
Caracterizaremos ahora la convergencia de sucesiones en espacios shift. Básicamente, una (n) Z x en un espacio shift converge a x ∈ A cuando para cualquier K natural, n∈N por grande que sea, el bloque central de tamaño 2K + 1 de x coincide con el bloque central de (n) tamaño 2K + 1 de x , para todo n su cientemente grande.
sucesión
Proposición 4.8.
Sea x(n) n∈N una sucesión en el espacio shift X con la métrica usual, (n)
y x ∈ AZ . Se tiene que l´ımn→∞ x(n) = x si, y sólo si, ∀K ∈ N, ∃N ∈ N : ∀n ≥ N, x[−K,K] = x[−K,K] .
2. SUCESIONES
43
Demostración. Dado que la función exponencial a tasa menor que
mente a
0,
1
tiende asintótica-
por la Proposición 4.3 tenemos que:
l´ım x(n) = x ⇔ ∀ε > 0, ∃N ∈ N : ∀n ≥ N, d x(n) , x < ε ⇔ n→∞ ∀K ∈ N, ∃N ∈ N : ∀n ≥ N, d x(n) , x < 2−K ⇔ (n)
∀K ∈ N, ∃N ∈ N : ∀n ≥ N, x[−K,K] = x[−K,K] Ejemplo 4.9. Estudiar la convergencia de la sucesión
(n)
xi
=
1 0
si si
x
(n)
n∈N
en
{0, 1}
Z
de nida por
|i| = n |i| = 6 n
Veamos el siguiente cuadro:
(0)
x x(1) x(2) x(3)
−4 −3 −2 −1 0 1 2 3 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1
··· ··· ··· ···
4 0 0 0 0
··· ··· ··· ···
. . . Rápidamente nos damos cuenta que la ventana central de tamaño puros
0,
para todo
2K + 1
de
x(n)
consta de
n ≥ K + 1.
Luego, de acuerdo al criterio de convergencia en espacios shift, ∞ el límite de la sucesión es el punto 0 . Ejemplo 4.10. Estudiar la convergencia de la sucesión
x(n) =
(0001)∞ (01)∞
x(n)
n∈N
en
{0, 1}Z
de nida por
n es par n es impar
si si
Dispongamos los términos encolumnados, como antes:
x(0) x(1) x(2) x(3)
−4 −3 −2 −1 0 1 2 3 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1
··· ··· ··· ···
4 0 0 0 0
··· ··· ··· ···
. . .
1,
Aquí vemos que la coordenada tural y
a
en el alfabeto
{0, 1},
por ejemplo, no se estabiliza nunca: para cualquier N na(n) n > N tal que x1 6= a. Entonces, esta sucesión no es
existe
convergente.
{xn }n∈N y {zk }k∈N dos sucesiones en el espacio métrico (X, d). Se {zk }k∈N es subsucesión de {xn }n∈N si existe una sucesión de números naturales estrictamente creciente {nk }k∈N tal que para todo k ∈ N, es zk = xnk . Definición 4.11. Sean
dice que
(X, d) un espacio métrico. Un subconjunto K K posee subsucesión convergente en K .
Definición 4.12. Sea
si toda sucesión en
Es bien sabido que un subconjunto que unidos cubren a
K
K
de
X
se dice
compacto
es compacto si, y sólo si, cualquier familia de abiertos
posee una subfamilia
nita
que también cubre a
K.
Además, todo
subconjunto compacto de un espacio métrico es un conjunto cerrado, y si el espacio métrico es compacto, entonces la familia de los subconjuntos compactos del espacio es precisamente la de los subconjuntos cerrados. El siguiente resultado muestra que cualquier espacio shift (en particular la full shift) es compacto para la métrica usual.
44
4. ASPECTOS TOPOLOGICOS Y DINAMICOS DE LOS ESPACIOS SHIFT
Sea X un espacio shift con la métrica usual. Entonces X es un subconjunto compacto de A . (n) Demostración. Sea x una sucesión en X . Ya que A es un conjunto nito, debe n∈N existir a0 ∈ A y un subconjunto in nito B0 de números naturales tal que para todo n ∈ B0 , (n) x0 = a0 . Elijamos cualquier n0 ∈ B0 . Como A3 es nito, deben existir a−1 y a1 en A, (n) y un subconjunto in nito B1 ⊆ B0 tal que para todo n ∈ B1 , x[−1,1] = a−1 a0 a1 . Elijamos n1 ∈ B1 tal que n1 > n0 (tal elección es posible, pues B1 es un conjunto in nito de números naturales, y por tanto no acotado). Siguiendo de esta manera, para cada k ∈ N, como A2k+1 es nito, deben existir a−k y ak en A, y un subconjunto in nito Bk ⊆ Bk−1 tal que (n) para todo n ∈ Bk , x[−k,k] = a−k · · · a0 · · · ak . Elijamos nk ∈ Bk tal que nk > nk−1 . De este modo, hemos de nido (inductivamente) a−k , ak y nk para todo k ∈ N. Como {nk }k∈N es (n ) (n) creciente, x k es subsucesión de x . de namos x = (ak )k∈Z . Dado que todo blok∈N n∈N (nk ) que de x ocurre en algún x ∈ X , tenemos que x pertenece al espacio shift X . Además, l´ımk→∞ x(nk ) = x, pues dado K ∈ N, tomando N = K , tenemos que para todo k ≥ N es (nk ) = a−K a−K+1 · · · a0 · · · aK−1 aK = x[−K,K] . Entonces X es compacto. x[−K,K] Proposición 4.13.
Z
La sola compacidad no caracteriza completamente a los espacios shift: por ejemplo, el con∞ junto unitario {(01) } es un subconjunto compacto de la full {0, 1}-shift (como cualquier conjunto nito de cualquier espacio métrico) pero no es un espacio shift pues carece de la shift-invariancia. Precisamente, compacidad más shift-invariancia equivalen a tener carácter de espacio shift.
Un subconjunto de AZ es un espacio shift si, y sólo si, es compacto (para la métrica usual de los espacios shift) y shift-invariante. Teorema 4.14.
Demostración. La shift-invariancia de un espacio shift fue demostrada en el primer ca-
pítulo, y la compacidad en la Proposición 4.13.
Z es un subconjunto compacto y shift-invariante de A . c c Por ser compacto, X es cerrado, y entonces X es abierto. De allí que para cada y ∈ X existe c K (y) ∈ N tal que B2−K(y) (y) está contenido en X . Tomemos F = y[−K(y),K(y)] : y ∈ X c , y Recíprocamente, supongamos que
veri quemos que
X
X = XF .
c
x ∈ X , entonces x[−K(x),K(x)] ∈ F , de donde x ∈ / XF . Luego, XF ⊆ X . Si x ∈ / XF , debe existir u ∈ F tal que u v x. Por de nición de F , u debe ser de longitud impar, es decir, |u| = 2n + 1 para algún n ∈ N. Entonces u ocurre en x desde alguna 0 m+n posición m ∈ Z, es decir, x[m,m+2n] = u. Llamando x = σ (x), es x0[−n,n] = u. Como u ∈ F , hay un y ∈ X c tal que y[−K(y),K(y)] = u, debiendo entonces ser K(y) = n. Pero 0 0 c 0 entonces x[−n,n] = y[−n,n] , de donde x ∈ B2−K(y) (y) ⊆ X , o sea, x ∈ / X . Y, por la shift invariancia, x ∈ / X . Luego, X ⊆ XF . Si
3. AZ
Cilindros. Conexidad
puede ser visto como el producto cartesiano in nito
cartesiano, se de ne un
cilindro
como un subconjunto
C
Xi∈Z A. Como en cualquier producto
del producto para el cual un número
nito de coordenadas están jas. En el caso particular de los espacios shift, nos van a interesar los cilindros en que un número nito de coordenadas consecutivas están jas. Formalmente:
A, u ∈ A∗ y k ∈ Z. El cilindro en X asociado al bloque u en la posición k es el conjunto CkX (u) de nido por CkX (u) = x ∈ X : x[k,k+|u|−1] = u Definición 4.15. Sea
A
un alfabeto,
X
un espacio shift sobre
4. CONTINUIDAD
45
X , el cilindro asociado a u en la posición k es el conjunto de puntos del espacio X tales que el bloque u ocurre en la posición k . Obsérvese que para cualquier X n / B (X). (u). Además, CkX (u) = ∅ si, y sólo si, u ∈ n ∈ Z, es σX CkX (u) = Ck−n Si x es un punto del espacio shift X y ε es un real positivo, entonces n o Bε (x) = y ∈ X : x[−blog 1 c,blog 1 c] = y[−blog 1 c,blog 1 c] = C−Xblog 1 c x[−blog 1 c,blog 1 c] En palabras, en el espacio shift
ε
En particular, para
k ∈ N,
ε
ε
ε
ε
ε
ε
se tiene que
X B2−k (x) = y ∈ X : y[−k,k] = x[−k,k] = C−k x[−k,k] Como vemos, los entornos en un espacio shift son cilindros. La recíproca no es cierta en general: no todo cilindro es un entorno. Sin embargo, todo cilindro es un conjunto abierto. En efecto, X sea x ∈ Ck (u). Tomando N = m´ ax {|k| , |k + |u| − 1|}, se tiene que −N ≤ k ≤ k + |u| − 1 ≤ N , de modo que
X B2−N (x) = C−N x[−N,N ] = y ∈ X : y[−N,N ] = x[−N,N ] ⊆ y ∈ X : y[k,k+|u|−1] = x[k,k+|u|−1] = CkX (u) Pero además los cilindros son cerrados, pues
c = x ∈ X : x[k,k+|u|−1] 6= u = CkX (u)
[
x ∈ X : x[k,k+|u|−1] = v
v∈A|u| −{u}
[
=
CkX (v)
v∈A|u| −{u} Es decir, el complemento de un cilindro es una unión de conjuntos abiertos, y por lo tanto es un conjunto abierto; luego, el cilindro es cerrado. Entonces, los cilindros en un espacio shift son conjuntos a la vez abiertos y cerrados. Esto revela otra característica topológica de los espacios shift: son conjuntos
nexos.
totalmente disco-
Recordamos que una forma de caracterizar a los conjuntos disconexos de un espacio
métrico es como aquellos conjuntos que poseen un subconjunto propio no vacío que es a la vez abierto y cerrado. Y un conjunto totalmente disconexo es aquel para el cual todo subconjunto de más de un punto es disconexo. El conjunto clásico de Cantor en la recta real tiene esta misma estructura: se trata de una nube de puntos no aislados en la cual ningún par de puntos distintos pertenece a una misma pieza conexa.
4. Definición 4.16. Sean
se dice
(X, dX )
continua en x ∈ X
e
Continuidad
(Y, dY )
φ:X →Y l´ımn→∞ xn = x, se
dos espacios métricos. Una función
si para toda sucesión
{xn }n∈N
en
X
tal que
l´ımn→∞ φ (xn ) = φ (x). Si A ⊆ X , φ se dice continua en A si φ es continua en cada φ es continua en X , biyectiva y además su función inversa es también continua, φ se denomina un homeomor smo entre X e Y , y los espacios X e Y se dicen homeomorfos. tiene que
x ∈ A.
Si
Una función entre dos espacios métricos es continua en todo su dominio si, y sólo si, la preimagen de cualquier subconjunto abierto del codominio es un subconjunto abierto del dominio. La composición de funciones continuas es también una función continua. La de nición de continuidad que hemos dado corresponde en realidad a la de nición de la
continuidad secuencial o sucesional, y equivale a la clásica de nición ε − δ de continuidad: φ es continua en x si ∀ε > 0, ∃δ > 0 : dX (y, x) < δ ⇒ dY (φ (y) , φ (x)) < ε. Pero la continuidad desde el punto de vista de las sucesiones es más fácil de manejar cuando el espacio métrico es un espacio shift, ya que tenemos completamente caracterizadas a las sucesiones que convergen en un espacio shift.
Todo código de ventana deslizante entre dos espacios shift es una función continua en todo su dominio. Proposición 4.17.
46
4. ASPECTOS TOPOLOGICOS Y DINAMICOS DE LOS ESPACIOS SHIFT
Y dos espacios shift yφ : X → Y un CVD inducido por Φ con memoria y anticipación L ≥ 0. Sean x ∈ X y x(n) n∈N una sucesión en X tal que l´ımn→∞ x(n) = x. Debemos ver que ∀K ∈ N, ∃N ∈ N : ∀n ≥ N, φx(n) [−K,K] = (φx)[−K,K] . (n) Sea K ∈ N. Por la hipótesis de convergencia de x a x, tenemos que existe N ∈ N tal n∈N (n) (n) que ∀n ≥ N, x[−K−L,K+L] = x[−K−L,K+L] . Veamos que para todo n ≥ N es φx = [−K,K] (φx)[−K,K] : si i es un entero tal que −K ≤ i ≤ K , será −K − L ≤ i − L ≤ i + L ≤ K + L, por n lo que x[i−L,i+L] = x[i−L,i+L] , y entonces (n) φx(n) i = Φ x[i−L,i+L] = Φ x[i−L,i+L] = (φx)i Luego, l´ ımn→∞ φ x(n) = φ (x), de donde se deduce que φ es continua en x, y ya que x es arbitrario, φ es continua en X . Demostración. Sean
X
e
La sola continuidad de una función entre dos espacios shift no garantiza que sea un CVD. Hace falta algo más: la conmutabilidad de la función con las shifts de los respectivos espacios. Este resultado se obtuvo por Hedlund y otros en el año 1969. Antes de demostrarlo, enunciemos algunos resultados conocidos de la teoría general de espacios métricos, y cuyas demostraciones quedan de ejercicio. Proposición 4.18. Sean A y B dos subconjuntos compactos disjuntos no vacíos de un espacio métrico. Existe un número real estrictamente positivo δ tal que para todos a ∈ A y b ∈ B , d (a, b) ≥ δ .
Sea {Ak }nk=1 una familia nita de subconjuntos compactos no vacíos de un espacio métrico, dos a dos disjuntos. Existe δ > 0 tal que si x ∈ Ai e y ∈ Aj con i 6= j , entonces d (x, y) ≥ δ . Corolario 4.19.
Sea φ una función continua entre los espacios métricos X e Y , con X compacto, y sea F un subconjunto compacto de Y . Entonces, φ−1 (F ) es un subconjunto compacto de X . Proposición 4.20.
Teorema 4.21.
(Curtis, Lyndon, Hedlund) Sean X e Y dos espacios shift, y φ una
función de X en Y . φ es un código de ventana deslizante si, y sólo si, φ es una función continua tal que φ ◦ σX = σY ◦ φ. Demostración. Sabemos, de los primeros capítulos, que si
las
σ,
y la Proposición 4.17 muestra que
φ
φ
es un CVD, conmuta con
es continua.
φ es un CVD si, y sólo si, x[−N,N ] . El hecho de conmutar con σ lo tenemos por hipótesis, así que sólo resta probar la existencia de un tal N , para lo cual usaremos la hipótesis de la continuidad de φ. Sea U = B1 (φ (X)), el conjunto de símbolos que aparecen en los transformados de los puntos de X . Obviamente, U es un subconjunto Y del alfabeto de Y . Para cada b ∈ U , el cilindro C0 (b) es un subconjunto cerrado de Y , y Y como Y es compacto, C0 (b) es compacto. Además, si b y c son elementos de U con b 6= c, es Y Y C0 (b) ∩ C0 (c) = ∅. Para cada b ∈ U , hagamos Eb = φ−1 C0Y (b) . Por su de nición y por la Proposición 4.20, cada Eb es un subconjunto compacto no vacío de X , y si b 6= c, Eb ∩ Ec = ∅, Y pues si x ∈ Eb , es φ (x) ∈ C0 (b), luego φ (x) ∈ / C0Y (c), y entonces x ∈ / Ec . Además, cada x ∈ X pertenece a un único Eb . Así que la familia {Eb }b∈U es una familia de conjuntos compactos que constituye una partición para X . Luego, por el Corolario 4.19, existe δ > 0 tal que d (x, y) ≥ δ toda vez que x ∈ Eb e y ∈ Ec con b 6= c. Tomemos N ∈ N su cientemente grande como para −N que 2 < δ . Si x e y son puntos de X tales que x[−N,N ] = y[−N,N ] , entonces d (x, y) < 2−N < δ , por lo que x e y deben estar en un mismo Eb . Esto signi ca que existe b ∈ U tal que φ (x) y φ (y) están ambos en C0Y (b), o sea, φ (x)0 = b = φ (y)0 . Pero esto quiere decir que la coordenada 0 del transformado por φ de x ∈ X depende sólo de x[−N,N ] , como queríamos probar. Para la vuelta, recordemos otra caracterización de los CVD:
conmuta con las
σ
y existe un
N ∈ N tal que φ (x)0
es función de
5. SISTEMAS DINÁMICOS
5.
47
Sistemas dinámicos
Los sistemas físicos pueden usualmente describirse a través de una cantidad nita de mediciones. Por ejemplo, un péndulo oscilante constituye un sistema que queda totalmente caracterizado por el ángulo respecto de la vertical y por la velocidad angular. Un gas se describe a través de la posición y momentum de cada molécula. A medida que transcurre el tiempo, esos valores cambian. Si denotamos por
M
al conjunto de todos los valores posibles para un dado sistema,
el estado del mismo en un instante dado corresponde a uno de esos estados. Imaginemos que lmamos el sistema y que luego observamos los cuadros que corresponden al instante luego a
t=1
seg,
t=2
t = 0,
seg, etc. Cada cuadro depende del anterior, de acuerdo a la manera
en que el sistema evolucione durante cada intervalo de un segundo. Si suponemos que las leyes que gobiernan el sistema no cambian con el tiempo, la dependencia de cada cuadro respecto del anterior se traduce en una función estado del sistema en
t = 0, T (x0 )
T :M →M
x0 es el t = 1, T ◦ T (x0 ) en t = 2,
que usualmente es continua. Así, si
describe el estado del sistema en
y así. Por lo tanto, estudiar el comportamiento del sistema en el tiempo se reduce a estudiar las iteraciones de T , es decir, la composición de T consigo misma. Para n ≥ 0, designaremos n 0 por T a la composición de T consigo misma n veces. Es decir, T es la identidad, y, para n > 0, T n = T ◦ T n−1 . Notar que T n es continua si T lo es, pues la continuidad se preserva por composición.
sistema dinámico
Definición 4.22. Un
métrico compacto y
T
(M, T ), en donde M es un espacio M . Si T es un homeomor smo, el
es un par
es una transformación continua en
sistema dinámico se dice
inversible.
Para nosotros, los sistemas dinámicos más interesantes serán aquellos en los que el conjunto
M
X
sea un espacio shift. En particular, si
dinámico que denominamos
(X, φ)
es un espacio shift, el par
sistema dinámico shift.
φ
Si
(X, σX ) es un sistema X en X , el par
es un CVD de
es también un sistema dinámico.
(M, T ),
Definición 4.23. Para un sistema dinámico
sucesión
n
{T x}n∈N .
la
Si el sistema es inversible, la órbita de
x
órbita
de un punto x ∈ n es la sucesión {T x}n∈Z .
M
es la
punto periódico es un punto x ∈ M tal que T x = x para algún n > 0, y tal n se llama un período de x. Si x es un punto n periódico, el menor de los n > 0 tales que T x = x se llama período mínimo de x. Una n órbita {T x} es periódica si x es un punto periódico. Definición 4.24. Para un sistema dinámico
(M, T ),
un
n
Un conjunto de problemas que interesan en relación a estos tópicos involucra el estudio del comportamiento de la órbita de puntos y de conjuntos en un dado sistema dinámico. Por ejemplo, si se tiene un sistema dinámico
(M, T )
en particular, puede interesar saber cómo se
distribuyen las órbitas de los puntos de un dado subconjunto abierto
U
de
M,
o si el conjunto
de puntos periódicos del espacio es denso. Otro conjunto de problemas tiene que ver con problemas de clasi cación de sistemas dinámicos: ¾Cuándo dos sistemas dinámicos aparentemente distintos son el mismo sistema? Definición 4.25. Sean
(M, T )
a
(N, S)
(M, T )
y
(N, S) dos sistemas dinámicos. Un homomor smo θ de θ : M → N tal que θ ◦ T = S ◦ θ. Los homomor smos
es una función continua
de un sistema dinámico a sí mismo se denominan Una simple inducción muestra que si
θ
endomor smos del sistema dinámico.
es un homomor smo de n n para cualquier entero positivo n, se tiene que θ ◦ T = S ◦ θ .
(M, T )
a
(N, S),
entonces,
Notemos que, debido al Teorema de Curtis, Lyndon y Hedlund, los homomor smos entre los sistemas dinámicos shift son precisamente los códigos de ventana deslizante.
inmersión es un homomor smo inyectivo, un factor es un homouna conjugación topológica es un homomor smo biyectivo. Dos
Definición 4.26. Una
mor smo sobreyectivo, y
48
4. ASPECTOS TOPOLOGICOS Y DINAMICOS DE LOS ESPACIOS SHIFT
sistemas dinámicos se dicen
topológicamente conjugados si existe una conjugación topoló-
gica entre ellos. Las nociones de inmersión, factor y conjugación conducen a problemas de clasi cación de sistemas dinámicos. Dos sistemas dinámicos conjugados son esencialmente el mismo, pero la cuestión de si dos dados sistemas dinámicos son conjugados, o uno factor del otro, o uno inmerso en el otro, puede ser muy difícil de resolver. Para detectar si dos sistemas dinámicos
no
son conjugados, una estrategia es la siguiente:
asociemos a cada sistema dinámico con alguna entidad (que puede ser un número, un conjunto, o lo que sea) de manera que dos sistemas conjugados tengan asociados la misma entidad. Luego, dados dos sistemas dinámicos en particular, obtengamos las entidades asociadas respectivas, y si éstas no coinciden sabremos que los sistemas no son conjugados (aunque puede ocurrir que no podamos deducir nada si vemos que ambas entidades coinciden). Dichas entidades reciben el nombre de
invariantes por conjugación.
Una de tales entidades es el conjunto de puntos periódicos de período
n,
donde
n
es un
natural jo. Ya hemos visto, en el capítulo primero, la demostración para el caso en que los sistemas involucrados son sistemas dinámicos shift. Veamos el resultado en general. Proposición 4.27. Sea n un entero positivo. La cantidad de puntos periódicos de período n es un invariante por conjugación.
(M, T ) y (N, S) sistemas dinámicos conjugados, y θ : M → N una conjugación. Denotemos por pn (T ) al cardinal del conjunto de puntos periódicos de período n para T , y pn (S) al de los puntos periódicos para S . Para x ∈ M , se tiene que Demostración. Sean
T n x = x ⇔ θ (T n x) = θ (x) ⇔ S n (θ (x)) = θ (x) θ establece pn (T ) = pn (S). de modo que
una biyección entre los puntos jos de
Tn
y los de
S n.
Por lo tanto,
Un argumento similar al anterior muestra que el número de puntos periódicos de período mínimo
n
es también invariante por conjugación.
Veamos ahora otro invariante por conjugación.
(M, T ) es topológicamente transitivo V , existe n > 0 tal que (T n U ) ∩ V 6= ∅.
Definición 4.28. Un sistema dinámico
cualquier par de abiertos no vacíos
U
y
si para
Es decir, un sistema topológicamente transitivo mueve a cada conjunto abierto lo su ciente como para que llegue a tocar a cualquier otro conjunto abierto, en alguna iteración. La de nición implica que ese toque se producirá una cantidad in nita de veces, según demostraremos a continuación.
Sean (M, T ) un sistema topológicamente transitivo, U y V dos conjuntos abiertos no vacíos y m un natural arbitrario. Existe n > m tal que (T n U ) ∩ V 6= ∅. Lema 4.29.
W = (T m )−1 (V ).
T continua en M , W es k abierto, así que, por hipótesis de transitividad topológica, existe k > 0 tal que T U ∩ W 6= ∅. −1 k m Eso quiere decir que existe z ∈ T U tal que z ∈ (T ) (V ); lo primero signi ca que existe k m x ∈ U tal que T x = z , y lo segundo dice que T z ∈ V . Poniendo n = m + k , tendremos que n > m y que T n x = T m T k x = T m z ∈ V . Es decir, existe x ∈ U tal que T n x ∈ V , de donde (T n U ) ∩ V 6= ∅. Demostración. Sea
Ya que
V
es abierto y
De manera directa, se desprende de allí el siguiente resultado.
Sean (M, T ) un sistema topológicamente transitivo, y U y V dos conjuntos abiertos no vacíos. Existe una sucesión {nk }k∈N de naturales estrictamente creciente tal que para todo k ∈ N, es (T nk U ) ∩ V 6= ∅. Proposición 4.30.
Proposición 4.31.
La transitividad topológica es invariante por conjugación.
5. SISTEMAS DINÁMICOS
49
(M, T ) y (N, S) sistemas dinámicos conjugados, con (M, T ) topológicamente transitivo, y θ : M → N una conjugación. Sean U y V abiertos en N . Denotemos U 0 = θ−1 (U ) y V 0 = θ−1 (V ). Como θ es continua, U 0 y V 0 son abiertos en M , por lo que existe n > 0 tal que (T n U 0 ) ∩ V 0 6= ∅, es decir, (T n (θ−1 (U ))) ∩ θ−1 (V ) 6= ∅. Por lo tanto, siendo θ una Demostración. Sean
biyección, tenemos que
∅= 6 θ Entonces,
(N, S)
T n θ−1 (U ) ∩ θ−1 (V ) = θ T n θ−1 (U ) ∩ θ θ−1 (V ) = S n θ θ−1 (U ) ∩ V = (S n U ) ∩ V
es también topológicamente transitivo.
En el primer capítulo, hemos de nido irreducibilidad: un espacio shift para cualquier par de palabras tal que
uvw ∈ B (X).
u
w
y
en el lenguaje, hay una palabra
v
X
es irreducible si
también en
B (X)
Veremos ahora que en el contexto de los sistemas dinámicos shift, la
irreducibilidad de un espacio shift
X
equivale a la transitividad topológica del sistema dinámico
(X, σX ). Proposición 4.32. Un sistema dinámico shift es topológicamente transitivo si, y sólo si, el espacio shift es irreducible.
(X, σX ) es topológicamente X X transitivo. Sean u y w en B (X). Hagamos U = C0 (u) y V = C0 (w). Ya que U y V son n abiertos y no vacíos, por Lema 4.29, existe n > |u| tal que (σX U ) ∩ V 6= ∅, es decir, hay un n X x ∈ X tal que x ∈ σX C0X (u) = C−n (u) y x ∈ C0X (w). Es decir que x[−n,−n+|u|−1] = u y x[0,|w|−1] = w. Como n > |u|, es −n + |u| − 1 < 0, de modo que podemos tomar v = x[−n+|u|,−1] Demostración. Supongamos que el sistema dinámico shift
uvw ∈ B (X). X es un espacio shift irreducible, y sean U y V dos abiertos no vacíos en el espacio métrico X . Sean x ∈ U , y ∈ V , y tomemos k, l ∈ N tal que B2−k (x) ⊆ U X y B2−l (y) ⊆ V . Hagamos u = x[−k,k] y w = y[−l,l] . Sabemos que B2−k (x) = C−k (u) y que X B2−l (y) = C−l (w). Como X es irreducible, existe v ∈ B (X) tal que uvw ∈ B (X). Tomemos X z ∈ X tal que z[−k,−k+|u|+|v|+|w|−1] = uvw. Tenemos que z ∈ C−k (u) ⊆ U , y además, puesto que |u| = 2k + 1 y |w| = 2l + 1, k−|u|−|v|−l −k−1−|v|−l −k−1−|v|−l X X X z ∈ C−k+|u|+|v| (w) = σX C−l (w) = σX C−l (w) ⊆ σX (V )
para ver que
uvw v x,
es decir,
Recíprocamente, supongamos que
Es decir, z n que (σX U )
k+l+|v|+1
∈ U y σX ∩ V 6= ∅.
(z) ∈ V .
Por lo tanto, tomando
n = k + l + |v| + 1 > 0,
tenemos
De nuestros resultados anteriores, deducimos que, en el universo de los espacios shift, el carácter de irreducible es invariante por conjugación. Teorema 4.33.
o ninguno lo es.
Sean X e Y espacios shift conjugados. Entonces o ambos son irreducibles
(X, σX ) es topológicamente transitivo (prop. 4.32), lo que, por ser e Y conjugados, equivale a que (Y, σY ) es topológicamente transitivo (prop. 4.31), lo que ocurre si, y sólo si, Y es irreducible. Demostración.
X X
es irreducible si, y sólo si,
En el próximo capítulo de niremos e investigaremos un importante invariante por conjugación entre espacios shift: la entropía.
Capítulo 5
ENTROPÍA X es observar la cantidad de los n en el lenguaje de X a medida que n crece; cuanto más grande es el número de n-bloques en B(X), más complejidad tiene el espacio X . Veremos que, conforme n aumenta, |Bn (X)| crece exponencialmente, es decir, se comporta como λn para algún real no negativo λ. Poniendo c = log λ (recordando nuestra convención de que log signi ca logaritmo en base 2), tendremos que, para n su cientemente grande, es |Bn (X)| ∼ = 2cn , de modo que c ∼ = n1 log |Bn (X)|. Esa tasa de crecimiento c, en el límite cuando n → ∞, recibe el nombre de entropía del espacio shift X , y es un invariante por conjugación entre espacios shift. El objetivo de este capítulo es Una manera de medir la complejidad de un espacio shift
bloques de largo
estudiar propiedades de esta entidad, y encontrar métodos para saber calcularla para distintas clases de espacios shift.
1. Definición 5.1. Sea
X
De nición y propiedades básicas un espacio shift. La
entropía de X
se de ne como
1 log |Bn (X)| n→∞ n
h(X) = l´ım con la convención de que
log 0 = −∞.
X = AZ , para todo n ∈ N es Bn (X) = An , así que log |Bn (X)| = log |An| = log |A| = n log |A|. Dividiendo por n y tomando límite cuando n → ∞, vemos que h AZ = log |A|. Es decir, la entropía de un full shift es el logaritmo de la cantidad de letras de su alfabeto. De la de nición, se desprende también directamente que h(∅) = −∞. Por ejemplo, si n
Nuestra primera tarea es ver que la entropía es un número bien de nido, para lo cual debemos garantizar que ese límite que la de ne efectivamente existe. Primero observemos que, siendo
X
no vacío, es
|Bn (X)| ≥ 1
para todo
n ∈ N,
así que el límite, de existir, es un real no
negativo. Sean
m, n ∈ N y sea u ∈ Bm+n (X). Tal u debe ser la concatenación de un bloque v ∈ Bm (X) w ∈ Bn (X). Por lo tanto, Bm+n (X) ⊆ {vw : v ∈ Bm (X), w ∈ Bn (X)} (la contención
y un bloque
puede ser estricta, ya que la concatenación de dos bloques en el lenguaje de un espacio shift no necesariamente produce otro bloque en ese lenguaje). Entonces, por el principio fundamental del conteo, ocurre que
|Bm+n (X)| ≤ |Bm (X)| · |Bn (X)| En consecuencia,
log |Bm+n (X)| ≤ log |Bm (X)| + log |Bn (X)| Poniendo an = log |Bn (X)| para cada n ∈ N, resulta que la sucesión {an }n∈N es una sucesión subaditiva de reales no negativos, es decir, am+n ≤ am + an para todos m, n ∈ N. Una simple + inducción muestra que si an es cualquier sucesión subaditiva en R0 , entonces, para enteros positivos c y k cualesquiera, ack ≤ cak y, en particular, ar ≤ ra1 para cualquier entero positivo r. + Las sucesiones subaditivas en R0 poseen una interesante propiedad que establecemos en el siguiente resultado.
Sea {an }n∈N una sucesión subaditiva de reales no negativos. Entonces l´ımn→∞ existe y vale ´ınf n≥1 ann . Lema 5.2.
50
an n
1. DEFINICIÓN Y PROPIEDADES BÁSICAS
Demostración. Designemos
n ≥ 1.
Debemos ver que
α = ´ınf n≥1
a an , teniéndose entonces que n n n
51
≥ α
para todo
an ∀ε > 0, ∃N : ∀n ≥ N, α − < ε n
k ≥ 1 tal que akk ≤ α + 2ε . Por otro lado, sea m cualquier entero positivo mayor que 2a1 /ε. Hagamos N = mk . Sea n ≥ N . Por el teorema de la división, existen naturales c y r tales que n = ck + r con 0 ≤ r < k . Ya que (c + 1)k > n ≥ N = mk , tenemos que (c + 1) > m, por lo que c ≥ m ≥ 1. Si fuese r = 0, Consideremos entonces
ε>0
tendremos
jo. Por propiedad de ín mo, existe
an ack cak ak ε = ≤ = ≤ α + < α + ε, n ck ck k 2
r > 0, tendremos an ack+r ack + ar cak + ra1 ak a1 ak a1 ε ε = ≤ ≤ < + ≤ + 0) si todos sus coe cientes son positivos; similarmente, diremos que A es no negativa (A ≥ 0) si todos sus coe cientes son reales no negativos. Más generalmente, si A y B son matrices de igual tamaño, escribimos A > B cuando cada coe ciente de A es estrictamente mayor que el respectivo coe ciente de B ; escribimos A ≥ B cuando cada coe ciente de A es mayor o igual que el respectivo coe ciente de B . Toda esta notación se aplica también a los vectores (por ser Diremos que una matriz
A
(no necesariamente cuadrada) es
casos particulares de matrices rectangulares).
G es esencial si desde cualquier vértice sale al menos una arista, y a G no tiene las nulas ni columnas nulas. Por otro lado, un grafo G es irreducible si desde cualquier vértice hay camino en G hasta cualquier otro vértice. Esto equivale a que para cualquier pareja n de vértices I, J , existe n ≥ 0 tal que (A )IJ > 0. Todo esto motiva las siguientes de niciones: Recordemos que un grafo
cualquier vértice llega al menos una arista. Esto se traduce en que la matriz de adyacencia de
Definición 5.7. Sea
nulas ni columnas nulas.
A ≥ 0 una matriz cuadrada. A se dice esencial si A se dice irreducible si ∀I, J, ∃n ≥ 0 : (An )IJ > 0.
no contiene las
Notar que un grafo es esencial si, y sólo si, su matriz de adyacencia es esencial. Similarmente, un grafo es irreducible si, y sólo si, su matriz de adyacencia es irreducible. 0 Convendremos que A = Id|A|×|A| cualquiera sea la matriz cuadrada A. Como caso particu0 lar, [0] = [1]; entonces, [0] es irreducible pero no esencial. Cualquier matriz distinta de [0] que no sea esencial no puede ser irreducible, ya que si A tiene alguna la nula, la correspondiente n la de A (cualquiera sea n ≥ 1) es también nula (y análogamente si A tiene alguna columna nula). Dicho de otro modo, toda matriz irreducible debe necesariamente ser esencial (salvo el caso excepcional de la matriz
[0]).
La matriz de adyacencia es una valiosa herramienta para computar la entropía de shifts G un grafo esencial de r vértices con matriz de adyacencia A. Sabemos que An
de aristas. Sea
contiene la información necesaria para calcular la cantidad de caminos de largo la cantidad de bloques de tamaño
n
en el lenguaje de
|Bn (XG )| =
r X r X
n en G, es decir,
XG : (An )IJ
I=1 J=1 Por lo tanto, para conocer la entropía de XG , debemos averiguar cómo van variando los coe An conforme crece n. Veremos a continuación que, para ello, el conocimiento de los
cientes de
autovalores de
A
es fundamental.
2. CÁLCULO DE LA ENTROPÍA DE SHIFTS SÓFICOS IRREDUCIBLES
53
Sea A ≥ 0 una matriz r × r no nula que posee un autovector v > 0. Entonces, el correspondiente autovalor λ es positivo, y existen constantes positivas c0 y d0 tales que r X r X n c0 λ ≤ (An )IJ ≤ d0 λn Proposición 5.8.
I=1 J=1
En consecuencia, si G es un grafo cuya matriz de adyacencia es A, entonces h (XG ) = log λ. Demostración. Como
Av = λv.
Ya que
A
v
es autovector correspondiente al autovalor
posee al menos un coe ciente
de donde se deduce que
λ
AKL > 0,
es
(Av)K > 0,
se cumple que
es decir,
λvK > 0,
v
tiene todos sus coe cientes positivos. n n Una simple inducción muestra que, ya que Av = λv, se tiene que A v = λ v para cualquier Pr n n n ≥ 1. Entonces, para cualquier índice I , es (A v)I = (λ v)I , de donde J=1 (An )IJ vJ = λn vI . De allí que r X r r X X n n (A )IJ vJ = λ vI I=1 J=1 I=1 Designemos
es positivo pues
λ,
c = m´ın{v1 , . . . , vr }
d = m´ax{v1 , . . . , vr }.
y
Notemos que tanto
c
como
d
son
estrictamente positivos. Por un lado, tendremos que
r X r X
n
(A )IJ vJ ≥
I=1 J=1
r X r X
n
(A )IJ c = c
r X r X
I=1 J=1
(An )IJ
I=1 J=1
y que
n
λ
r X
n
vI ≤ λ
I=1 Entonces
r X
d = λn rd
I=1
r r X X
rd n λ c
(An )IJ ≤
I=1 J=1 Llamemos
d0 = rd/c,
resultando
d0 > 0
r, d
pues
y
c
son positivos.
Por otro lado, tendremos que
r X r X
n
(A )IJ vJ ≤
I=1 J=1
r X r X
n
(A )IJ d = d
I=1 J=1
r X r X
(An )IJ
I=1 J=1
y que
n
λ
r X
vI ≥ λ
n
I=1 Entonces
r X
c = λn rc
I=1
r r X X
(An )IJ ≥
I=1 J=1 Llamemos
c0 = rc/d,
, resultando
c0 > 0
pues
rc n λ d r, d
y
c
son positivos.
Juntando las dos desigualdades de más arriba, tenemos que, para cualquier
c0 λ n ≤
r X r X
n ∈ N,
es
(An )IJ ≤ d0 λn
I=1 J=1 es un PrG P r
Si
I=1
grafo esencial que tiene matriz de adyacencia
n J=1 (A )IJ .
A,
se cumple que
Por nuestro resultado anterior, esto signi ca que
c0 λn ≤ |Bn (XG )| ≤ d0 λn
|Bn (XG )| =
54
5. ENTROPÍA
de donde
Tomando límites
1 1 1 1 1 log c0 + n log λ ≤ log |Bn (XG )| ≤ log d0 + n log λ n n n n n cuando n → ∞, resulta h (XG )) = log λ.
Si una matriz no nula A a coe cientes enteros admite un autovector positivo, todos los autovectores positivos de ella corresponden a un mismo autovalor. Corolario 5.9.
0 el shift de aristas correspondiente a A. Sean v, v autovectores 0 positivos correspondientes a autovalores λ, λ respectivamente. Aplicando la proposición 5.8, 0 0 concluimos que log λ = h (XG ) = log λ , de donde λ = λ . Demostración. Sea
G
Dada una matriz A ≥ 0 que admite un autovector positivo v correspondiente al autovalor λ > 0, cualquier autovalor µ de A cumple que |µ| ≤ λ. Corolario 5.10.
r el tamaño de A. Sean µ un autovalor de A y v0 µ. Como A v = µn v0 y A ≥ 0, es, por un lado, r r r r X X X X n n 0 n 0 n 0 |vI0 | |(A v )I | = |(µ v )I | = |µ vI | = |µ|
Demostración. Sea
asociado a
un autovector
n 0
I=1
I=1
I=1
I=1
y, por otro lado,
r r X r X r r X r X X X n 0 n 0 (A ) v ≤ |(A ) v | = (An )IJ |vJ0 | |(An v0 )I | = IJ J IJ J I=1 I=1 J=1 I=1 J=1 I=1 J=1 ! r r r X XX |vI0 | d0 λn (An )IJ ≤ ≤ m´ax |vI0 |
r X
1≤I≤r
donde
d0 > 0
I=1 J=1
I=1
es el garantizado en la proposición 5.8.
|µ|n ≤ d0 λn ,
Juntando todo esto, resulta que, para todo n ≥ 0, es 1/n Como d0 > 0, es l´ ımn→∞ d0 = 1, y entonces |µ| ≤ λ. Dado un grafo esencial
XG
G
con matriz de adyacencia
A,
Teorema de PerronFrobenius,
1/n
|µ| ≤ d0 λ.
para poder calcular la entropía de
por aplicación de la proposición 5.8, necesitamos saber si
Para ello, contamos con el
es decir,
A
posee un autovector positivo.
que enunciaremos sin demostración
y que es válido para una clase especial de matrices que comprende a las matrices de adyacencia de los grafos irreducibles. Teorema 5.11.
(PerronFrobenius) Sea A ≥ 0 una matriz irreducible no nula. Entonces
A posee un autovector vA positivo con autovalor correspondiente λA positivo que es geométricamente y algebraicamente simple. Cualquier autovalor µ de A tiene módulo menor o igual que λA , y cualquier autovector positivo de A es un múltiplo positivo de vA . El autovalor λA del teorema anterior se denomina autovalor de Perron de A, y vA es autovector de Perron de A. El teorema muestra que vA es único salvo multiplicación por
un un
escalar. Por combinación de la proposición 5.8 con el teorema de PerronFrobenius, obtenemos el siguiente resultado principal. Teorema 5.12.
1. 2.
Si G es un grafo irreducible con matriz de adyacencia A, entonces h(XG ) = log λA . Si X es un shift de tipo nito irreducible de memoria M y G es el grafo esencial con matriz de adyacencia A tal que X [M +1] = XG , entonces h(X) = log λA .
Demostración.
3. LOS PUNTOS PERÍODICOS Y LA ENTROPÍA
1. Como
G
es irreducible,
A
55
es irreducible, por lo que admite un autovector positivo que
λA . Entonces, por proposición 5.8, h(XG ) = log λA . [M +1] X es conjugado a X , siendo la entropía invariante por conjugación, es [M +1] = h(XG ). Como X es irreducible, también lo es X [M ] (teor. 4.33), h(X) = h X de donde G es irreducible, lo que implica que A también lo es. Entonces, por el inciso anterior, h(X) = log λA . corresponde a
2. Ya que
Sea X un shift só co irreducible y G = (G, L) una presentación irreducible resolvente a derecha de X . Entonces h(X) = log λA , siendo A la matriz de adyacencia de G. Corolario 5.13.
Demostración. Por proposición 5.6,
el teorema 5.12,
h(XG ) = log λA
3.
h(X) = h(XG ) = h(XG ), y, siendo G irreducible, por
Los puntos períodicos y la entropía
Queremos ahora investigar cómo crece la cantidad de puntos periódicos de período hay en un espacio shift
X,
a medida que crece
n.
X
un espacio shift y
la cantidad de puntos periódicos (para
σ)
n
que
Veremos que existe una vinculación entre la
tasa de crecimiento de esa cantidad y la entropía de Definición 5.14. Sea
n
X.
un entero positivo. Designamos por
de período
n
que hay en
pn (X)
a
X.
Z Por ejemplo, si X = {0, 1} y n es cualquier entero positivo, tomando cualquier bloque u ∈ An se tiene que u∞ es un punto periódico de X , y bloques diferentes generan puntos periódicos n diferentes, por lo que pn (X) = 2 . Como vemos, al igual que lo que ocurre con |Bn (X)|, pn (X) puede crecer sin cota, por lo que resulta pertinente considerar la tasa de crecimiento de pn (X), 1 log pn (X), y ver qué ocurre con esta sucesión cuando n → ∞. Debe advertirse, desde n un comienzo, que puede no existir el límite de dicha sucesión, ni siquiera restringiendo X a la
es decir,
familia de los shifts de tipo nito. Ejemplo 5.15. Sea
X
un shift de aristas con conjunto de vértices
total de 6 aristas, de las cuales una es un rulo en
I,
2 van de
J
a
K
y
{I, J, K} teniendo un 3 de K a J . Su matriz
de adyacencia es
1 0 0 A= 0 0 2 0 3 0
An y sumamos n/2 en cada paso los coe cientes de su diagonal, obtenemos que, para n par, es pn (X) = 1 + 2 · 6 1 y, para n impar, es pn (X) = 1, así que la subsucesión de log pn (X) correspondiente a los n √ términos pares tiende a log 6, y la correspondiente a los impares tiende a 0. Por lo tanto, 1 log p (X) carece de límite. n n Por la proposición 2.24, sabemos que
pn (X)
es la traza de
An .
Si computamos
1 log pn (X) puede no existir, consideraremos l´ım supn→∞ n1 log pn (X), recorn dando que el límite superior de una sucesión es el mayor de sus puntos de acumulación, y Ya que
l´ımn→∞
siempre existe (y coincide con el límite de la sucesión si éste existe). Proposición 5.16.
Sea X un espacio shift. Entonces, l´ım supn→∞
Demostración. Cada punto
por lo que
x∈X
de período
n
1 n
log pn (X) ≤ h(X).
está determinado por
x[0,n−1] ∈ Bn (X),
pn (X) ≤ |Bn (X)|. En consecuencia, 1 1 1 l´ım sup log pn (X) ≤ l´ım sup log |Bn (X)| = l´ım log |Bn (X)| = h(X) n→∞ n n→∞ n n→∞ n
56
5. ENTROPÍA
La proposición anterior muestra que la tasa de crecimiento de
X
pn (X)
tiene a la entropía de
como cota superior. Sin embargo, para muchos espacios shift esa tasa iguala a Proposición 5.17.
h(X).
Si X es un shift de aristas irreducible, entonces l´ım supn→∞
G = (V, Σ, i, t) J en G cualesquiera
Demostración. Sea
camino desde
I
hasta
N = m´ax {m´ın {|π| : π I,J∈V
un grafo irreducible tal que sean los vértices camino desde
I
I, J , hasta
h(X). 1 n
log pn (X) =
X = XG .
Como hay
sea
J
en
G}}
I, J arbitrarios en G, hay un camino en G desde I hasta J de N. Sea π un bloque en Bn (X) (y, por lo tanto, un camino en G), y sea τ un camino en G desde t(π) hasta i(π) con |τ | ≤ N . Entonces, πτ es ciclo en G, por lo que (πτ )∞ determina un punto periódico en X , con período n + |τ | ≤ n + N . Así vemos cómo construir, para cada bloque en Bn (X), un punto periódico en X cuyo período está entre n y n + N . Notar que dos bloques diferentes en Bn (X) generan diferentes puntos periódicos. Por lo tanto, Por lo tanto, dados vértices longitud menor o igual que
|Bn (X)| ≤ pn (X) + pn+1 (X) + · · · + pn+N (X) n, elijamos kn en el conjunto {0, 1, . . . , N } i ∈ {0, 1, . . . , N }. Tendremos que Para cada
tal que
pn+kn (X) ≥ pn+i (X)
para cada
|Bn (X)| ≤ (N + 1)pn+kn (X) por lo que
1 1 1 log |Bn (X)| ≤ log(N + 1) + log pn+kn (X) n n n En consecuencia,
1 1 log |Bn (X)| = l´ım sup log |Bn (X)| n→∞ n n→∞ n 1 1 n + kn 1 ≤ l´ım sup log(N + 1) + l´ım sup log pn+kn (X) = l´ım sup log pn+kn (X) n n + kn n→∞ n n→∞ n n→∞ n + kn 1 1 = l´ım sup l´ım sup log pn+kn (X) ≤ l´ım sup log pn (X) n n→∞ n→∞ n + kn n→∞ n
h(X) =
Es decir,
l´ım
h(X) ≤ l´ım supn→∞
1 n
log pn (X).
Entonces, aplicando la proposición 5.16, tenemos la
igualdad deseada.
Si X es un shift de tipo nito irreducible, entonces l´ım supn→∞
Corolario 5.18.
h(X).
G
log pn (X) =
X tiene memoria M . Entonces existe un grafo XG = X [M +1] . Siendo X y X [M +1] conjugados, es 1 1 h(X) = h X [M +1] = h(XG ) = l´ım sup log pn (XG ) = l´ım sup log pn (X) n→∞ n n→∞ n
Demostración. Supongamos que
cible
1 n
irredu-
tal que
pues, siendo la cantidad de puntos periódicos invariante por conjugación, es para todo
n.
Corolario 5.19.
h(X).
Si X es un shift só co irreducible, entonces l´ım supn→∞
1 n
log pn (X) =
G = (G, L) una presentación resolvente a derecha para X , con G h(X) = h(XG ) (prop. 5.6). Supongamos que G tiene r vértices. Por resolvente a derecha, cada punto en XG tiene a lo sumo r presentaciones
Demostración. Sea
irreducible. Sabemos que ser una presentación
pn (XG ) = pn (X)
4. CÁLCULO DE LA ENTROPÍA DE SHIFTS SÓFICOS
en
XG .
Como
L
57
es código de ventana deslizante, transforma puntos de período
n
puntos de período
de
XG ,
n
de
XG
en
por lo que
pn (XG ) ≤ r · pn (XG ) Entonces,
1 1 log pn (X) = l´ım sup log pn (XG ) n n→∞ n 1 1 1 1 ≥ l´ım sup log + l´ım sup log pn (XG ) = l´ım sup log pn (XG ) r n→∞ n n→∞ n n→∞ n = h(XG ) = h(X)
l´ım sup n→∞
Es decir,
h(X) ≤ l´ım supn→∞
1 n
log pn (X).
Entonces, aplicando la proposición 5.16, tenemos la
igualdad deseada.
4.
Cálculo de la entropía de shifts só cos
Previamente vimos cómo calcular la entropía de shifts só cos irreducibles: obtener una presentación resolvente a derecha irreducible, y tomar el logaritmo del autovalor de Perron de la matriz de adyacencia del grafo subyacente. Ahora generalizaremos el método de cálculo para el caso de shifts só cos en general (no necesariamente irreducibles). Como siempre, arrancaremos considerando los shifts de aristas, en este caso correspondientes a grafos arbitrarios (no necesariamente irreducibles). Veremos cómo, en este caso, el correspondiente grafo
G
la entropía de
contiene ciertos subgrafos irreducibles cuya identi cación nos permitirá obtener
XG .
La idea es reorganizar las las y columnas de la matriz de adyacencia
A
de
G
de modo de
triangular por bloques, según veremos enseguida, y usar ciertas submatrices cercanas a la diagonal para calcular la entropía de XG .
llevarla a una forma cuadradas
Definición 5.20. Dado un grafo G = (V, Σ, i, t) con matriz de adyacencia A, y estados I, J ∈ V , decimos que I se comunica con J (denotado I J ) si existe camino en G desde I n hasta J ; equivalentemente, si existe n ≥ 0 tal que (A )IJ > 0. Decimos que I se intercomunica con J (denotado I ! J ) si I J y J I .
Es fácil chequear que la intercomunicación establece una relación de equivalencia entre los
clases de intercomunicación. Una clase de éstas consiste en un conjunto maximal de estados tal que desde cualquiera de
vértices del grafo (ejercicio). Sus clases de equivalencia se llaman ellos se puede ir a cualquier otro de la clase por un camino en
G. G es irreducible precisamente
tiene una sola clase de intercomunicación. Una arista de
G
que sale de un estado perteneciente a una clase de intercomunicación
y termina en un estado de una clase de intercomunicación
transición de C1 a C2 . C1 ∪ C2
diferente se llama
Debe notarse que si hay una arista de transición de
puede haber al mismo tiempo arista de transición de estados en
C2
C2
a
C1 ,
C1
arista de
C1
a
C2 ,
no
pues, en ese caso, todos los
estarían intercomunicados, contradiciendo la maximalidad de las clases de
intercomunicación.
G se puede construir otro grafo H cuyos G, y hay una arista (única) desde un vértice Ci en G una arista de transición de Ci a Cj .
Con las clases de intercomunicación de un grafo vértices son las clases de intercomunicación de en
H
si, y sólo si, hay
Ejemplo 5.21. Sea
G
grafo mostrado a continuación, con su correspondiente matriz de
hacia otro vértice
adyacencia
A:
Cj
58
5. ENTROPÍA
1 2 3 4 5 6 7 8 Notar que
5 ! 4
1 0 1 0 0 0 0 0 0
2 1 0 0 0 0 0 1 0
3 0 1 0 0 0 0 0 0
4 0 1 1 0 2 0 0 0
5 0 0 0 1 1 0 0 0
6 0 0 0 0 0 2 0 0
7 1 0 0 0 0 0 0 0
8 0 0 0 1 0 1 1 0
y ningún otro vértice se intercomunica con 5 (ni con 4: por ejemplo,
a pesar de haber camino de 1 a 4, es imposible en el grafo ir de 4 a 1). Luego, una clase de intercomunicación es C1 = {5, 4}. Análogamente se ve que hay otras cuatro clases: C2 = {8}, C3 = {1, 2, 7}, C4 = {6} y C5 = {3}, según puede observarse en la gura que sigue, que es básicamente el mismo grafo G excepto que con los vértices de cada clase agrupados según una línea discontinua.
La arista de G que va de 4 a 8 es de transición de C1 a C2 . Hay también aristas de transición C3 a C1 , de C3 a C5 , de C3 a C2 , de C3 a C4 , de C5 a C1 y de C4 a C2 . Por lo tanto, el grafo H de las clases de intercomunicación tiene cinco vértices (C1 , C2 , C3 , C4 , C5 ) y siete aristas (C1 − C2 , C3 − C1 , C3 − C5 , C3 − C2 , C3 − C4 , C5 − C1 , C4 − C2 ), según se muestra a continuación. de
Notar que el grafo
H
que se construye de esta manera no puede tener rulos (pues por
de nición las aristas de transición vinculan vértices de clases distintas) ni, más generalmente, ciclos, pues, en ese caso, habría nodos de una clase intercomunicados con nodos de otra clase distinta, lo que no puede ser por la maximalidad de las clases. Esto implica que no todo estado de
H
H ). Entonces, anterior, C2 es
puede tener aristas salientes (si fuera ése el caso, se podría generar un ciclo en
debe haber al menos un estado en
H
sin aristas salientes (en nuestro ejemplo
sumideros. Análogamente debe haber al menos un estado en H sin aristas entrantes (C3 es el único del ejemplo anterior) y tales nodos se llaman fuentes. el único). Tales nodos se llaman
4. CÁLCULO DE LA ENTROPÍA DE SHIFTS SÓFICOS
Si quitamos los sumideros de
H
59
(y las aristas conectadas a ellos) de a uno por vez, recursi-
vamente, hasta que no quede ninguno, obtendremos una manera de renombrar los vértices de
H de acuerdo al orden en que se fueron quitando los vértices; así, el primer nodo quitado será C10 , el segundo C20 , y así sucesivamente. De este modo, las clases de intercomunicación quedarán 0 0 ordenadas de manera tal que sólo puede haber camino en H desde Ci hasta Cj cuando i > j . En nuestro ejemplo, el procedimiento anteriormente descripto tiene varias alternativas; una C10 = C2 = {8}, C20 = C1 = {5, 4}, C30 = C4 = {6}, C40 = C5 = {3} y C50 = C3 = {1, 2, 7}. de ellas es
Este orden nos permite reescribir la matriz de adyacencia A de G usando el orden en que 0 0 aparecen los vértices de G en C1 , C2 , etc. Al hacer este reordenamiento, la matriz asume una forma triangular inferior por bloques que puede esquematizarse de la siguiente manera:
C10 C20 C30 . . . Ck0 En ese esquema,
0
C10 C20 C30 A1 0 0 ∗ A2 0 ∗ ∗ A3
··· ··· ··· ···
C 0k 0 0 0 . . .
. . .
. . .
. . .
..
∗
∗
∗
···
.
Ak
representa submatrices rectangulares nulas, y
tangulares posiblemente no nulas. Cada una de las matrices
∗
Ai
representa submatrices reccorresponde a la matriz de
adyacencia del subgrafo irreducible Gi de G que se obtiene de considerar los vértices pertene0 cientes a la clase Ci con las aristas de G que inician y terminan en dichos vértices. Cada Gi se llama una G, y las Ai se llaman las
componente irreducible de
de A. También nos referiremos a los XGi
componentes irreducibles como las componentes irreducibles de XG .
Para el ejemplo 5.21, un posible reordenamiento siguiendo este proceso es el siguiente:
8 5 4 6 3 1 2 7
8 0 0 1 1 0 0 0 1
5 0 1 1 0 0 0 0 0
4 0 2 0 0 1 0 1 0
6 0 0 0 2 0 0 0 0
3 0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 1 0
2 0 0 0 0 0 1 0 1
7 0 0 0 0 0 1 0 0
Ya que el polonomio característico de una matriz no cambia por una permutación simultánea de las y columnas, podemos calcular el polinomio característico
χA (t)
de la matriz
A
original
más fácilmente usando la forma triangular por bloques. Al realizar la expansión (de Laplace) para obtener el determinante, cualquier producto que involucre un término debajo de la diagonal involucrará también un término Por ello, sólo los bloques de
A,
Ai
∗
de la porción por
0 de la porción por encima de la diagonal.
sobre la diagonal importan al calcular el polinomio característico
resultando éste ser el producto de los determinantes de las componentes irreducibles de
A: χA (t) = χA1 (t)χA2 (t) · · · χAk (t) En consecuencia, los autovalores de A son exactamente los autovalores de las Ai . En particular, el mayor de los λAi (en valor absoluto) será también un autovalor de A. Esto sugiere la siguiente de nición. Definición 5.22. Sea
El
A
una matriz no negativa con componentes irreducibles
autovalor de Perron de A es λA = m´ax{λAi : 1 ≤ i ≤ k}. Ya que el conjunto de autovalores de
autovalor de
A
A
es la unión de los autovalores de las
tiene módulo acotado por alguno de los
λAi .
A1 , . . . , A k .
Ai ,
cualquier
Luego, el autovalor de Perron de
60
5. ENTROPÍA
A es el más λA controla
grande (en valor absoluto) de los autovalores de A. Veremos, a continuación, que n la tasa de crecimiento de A (y, en consecuencia, la entropía de XG corresponde
al máximo de las entropías de sus componentes irreducibles
XGi ),
lo que es una extensión del
teorema 5.12 a grafos en general. Teorema 5.23.
Sea G un grafo con matriz de adyacencia A. Entonces, h (XG ) = log λA .
A son A1 , . . . , Ak . Será λA = λAq para algún q ∈ {1, . . . , k}. Como XG ⊇ XGq , es h (XG ) ≥ h XGq = log λAq = log λA . Resta probar la desigualdad en el otro sentido. Si λA = 0, es porque cada λAi es 0, lo que implica que cada Ai es la matriz [0]. En ese caso, G no tiene caminos biin nitos, lo que implica que XG = ∅, quedando en ese caso el resultado establecido. Supongamos entonces que λA > 0. Probaremos la desigualdad deseada acotando el número de caminos de longitud n en G. Cualquiera de tales caminos se puede descomponer en subcaDemostración. Supongamos que las componentes irreducibles de
minos dentro de clases de intercomunicación separados por aristas de transición entre clases. Es decir, cualquier
π ∈ Bn (XG )
es de la forma
π = τ (1) e(1) τ (2) e(2) · · · τ (j−1) e(j−1) τ (j) i ∈ {1, . . . , j}, τ (i) es camino (digamos de largo ni ) en alguno de los subgrafos (i) irreducibles de G (digamos Gqi ), y, para cada i ∈ {1, . . . , j − 1}, e es una arista en G desde algún estado en Gqi hasta algún estado de Gqi+1 . Observar que q1 > q2 > · · · > qj , y entonces j ≤ k . Sea M la cantidad total de aristas de transición entre clases que hay en G. Cada e(i) tiene a lo sumo M posibilidades, y a lo sumo n lugares en los que pueden ocurrir. O sea que k la cantidad total de maneras de acomodar aristas de transición es a lo sumo (M n) . Por cada (i) una de tales maneras, el número de opciones para cada τ es Bni XGq . i m Nótese que, siendo Gi irreducible para cada i entre 1 y k , es |Bm (XGi )| ≤ di λA para i + algún di ∈ R (prop. 5.8). De namos entonces d = m´ ax{di : 1 ≤ i ≤ k}. Tendremos que |Bm (XGi )| ≤ dλm A . Por lo tanto, siendo n1 + · · · + nk ≤ n, la cantidad de formas de elegir los (i) τ es, a lo sumo, Bn1 XGq × · · · × Bn XGq ≤ dj λn1 +···+nj ≤ dk λnA donde, para cada
1
j
i
A
Luego,
Aplicando logaritmos,
|Bn (XG )| ≤ (M n)k dk λnA = (M d)k nk λnA dividiendo por n y tomando límite cuando n → ∞,
log λA .
resulta
h (XG ) ≤
Con el resultado previo, ya estamos en condiciones de calcular la entropía de cualquier espacio shift só co (posiblemente irreducible). Corolario 5.24. Sea X un shift só co, y G = (G, L) una presentación resolvente a derecha para X . Entonces, h(X) = log λA , siendo A la matriz de adyacencia de G. Demostración. Por la proposición 5.6, sabemos que
X = XG ,
se concluye el resultado.
h (XG ) = h (XG ) = log λA .
Como
Capítulo 6
CÓDIGOS DE ESTADOS FINITOS A en X , y hacerlo de tal manera que exista algún modo de recuperar
Por diversos motivos, puede interesar codi car sucesiones arbitrarias sobre un alfabeto sucesiones de algún shift só co
la sucesión original conociendo su imagen. Lo primero que interesa es saber si es posible tal ∞ operación. Por ejemplo, si A = {0, 1} y X = {0 } es evidente que no. En caso de ser posible, de los métodos disponibles investigaremos en este capítulo uno que se denomina
nitos,
código de estados
en el que los símbolos de la sucesión imagen se obtienen de a uno por vez, a medida
que se van leyendo uno por uno los símbolos de la sucesión original, los que son interpretados como una suerte de
instrucciones.
El método usa grafos rotulados con dos clases especiales de
rotulaciones, una resolvente a derecha que además cumple otras condiciones, y una un poco más débil que resolvente a derecha.
1.
Coloreo de rutas y presentaciones cerrantes a derecha
Recordemos que una rotulación
a derecha
L:Σ→A
para un grafo
G = (V, Σ, i, t)
se dice
resolvente L|ΣI es
si desde un mismo nodo no salen dos aristas con un mismo rótulo; es decir,
inyectiva para cada
I ∈ V.
Si imponemos la condición más fuerte de que cada
L|ΣI
sea una
biyección, tendremos un tipo especial de rotulaciones resolventes a derecha.
G un grafo con conjunto de aristas Σ. Un coloreo de rutas de G es L : Σ → A que, para cada I ∈ V , establece una biyección entre las aristas que las letras del alfabeto. G se dice coloreable si admite un coloreo de rutas.
Definición 6.1. Sea
una rotulación salen de
I
y
La gura 1 muestra un ejemplo de grafo coloreable con
A = {0, 1}, y un ejemplo de coloreo.
Figura 1. Ejemplo de coloreo de rutas
Vemos entonces que, en un coloreo de rutas, por cada vértice
I
de
G
y cada letra
a ∈ A,
I cuyo rótulo es a. Esto obliga a que desde cada vértice |A| aristas. Entonces, G es coloreable si, y sólo si, tiene grado de salida
sale exactamente una arista desde deban salir exactamente
constante
desde sus vértices, lo que, en términos de la matriz de adyacencia, signi ca que las
las suman todas lo mismo. Un grafo con r estados y n aristas saliendo desde cada vértice r admite (n!) posibles coloreos de rutas (pues para cada uno de los r vértices hay que elegir una forma de asignar a
n
aristas las
n
letras del alfabeto, que es como ordenar las letras del
alfabeto). Otra consecuencia de la de nición es que si vértices, cada palabra sobre
A
L
tiene exactamente 61
es un coloreo de rutas para
r
G
que tiene
r
presentaciones, una empezando en cada
62
6. CÓDIGOS DE ESTADOS FINITOS
w w = a1 a2 . . . am ,
cuyo rótulo es Si
toma la símbolo
I ∈ V
w ∈ A∗ ,
hay un único camino comenzando en I Z (y, en consecuencia, un coloreo de rutas resulta una presentación para A ).
vértice. Es decir, para cada
y cada
I se toma la única arista e1 ∈ Σ saliente con rótulo a1 , desde t(e1 ) se única arista e2 ∈ Σ saliente con rótulo a2 , y así sucesivamente. En este sentido, cada de A se interpreta como una instrucción de cuál arista tomar si se está en un dado desde
vértice. Ahora veamos otro tipo de rotulaciones especiales para grafos, que satisfacen una condición más débil que la de ser resolventes a derecha.
cerrante a derecha con demora D si cualquier
Definición 6.2. Un grafo rotulado se dice
pareja de caminos de longitud
D+1
arrancando desde un mismo vértice y llevando el mismo
rótulo usan la misma primera arista. Un grafo rotulado se dice cerrante a derecha con alguna demora
cerrante a derecha
si es
D ≥ 0.
Informalmente hablando, un grafo rotulado puede no ser resolvente a derecha (lo cual creará ambigüedad sobre cuál arista rotulada tomar para salir desde algunos estados) pero es cerrante a derecha si esa ambigüedad queda salvada mirando anticipadamente una cierta cantidad
D
de símbolos adicionales que vendrán después. Para los grafos resolventes a derecha, no hay que mirar anticipadamente nada, correspondiendo al caso en que la demora es
D = 0.
Ejemplo 6.3. Consideremos los grados rotulados (a)(d) mostrados en la gura 2.
El grafo (a) tiene demora aristas rotuladas el bucle en
I
a
J
I
a
D = 1.
Para verlo, consideremos el estado
comenzando en
I,
I.
Ya que hay dos
el grafo no es resolvente a derecha. Sin embargo,
a, mientras que la arista de b o c. Luego, el rótulo de un camino
sólo puede ser seguido por una arista rotulada
sólo puede ser seguida por una arista rotulada
de longitud 2 empezando en
I
determina su arista inicial. Un análisis similar permite
concluir lo mismo para el estado
J,
y el estado
K
es más fácil, dado que las aristas que
salen de él llevan rótulos distintos. De manera análoga al inciso anterior, se puede veri car que el grafo rotulado (b) también es cerrante a derecha con demora 1. En el grafo rotulado (c), hay dos caminos con diferentes aristas iniciales rotulados
ab,
por lo que este grafo no tiene demora 1. Sin embargo, el siguiente símbolo determina cuál de los dos caminos debe tomarse, por lo que el grafo es cerrante a derecha con demora
D = 2.
En el grafo rotulado (d), para cualquier m, hay dos caminos comenzando en J que m presentan al bloque ab ; ya que estos caminos tienen distinta arista inicial, el grafo no
es cerrante a derecha.
Una manera equivalente, y a veces cómoda, de visualizar la propiedad de una rotuladora de ser cerrante a derecha con demora
D
es pensar que dos caminos de largo
D+1
arrancando en
un mismo vértice pero usando distinta primera arista no pueden llevar el mismo rótulo. Obviamente, así como el concepto de rotulación resolvente a derecha tiene su dual, que es el
resolvente a izquierda (todas las aristas que llegan a un mismo nodo tienen rótulos diferentes), se puede de nir la noción dual de cerrante a derecha que es la de rotulación cerrante a izquierda: todos los caminos de largo D + 1 que terminan en un mismo nodo y llevan el mismo rótulo de
usan la misma última arista. Pero en el presente capítulo usaremos sólo la noción de cerrante a derecha. La propiedad de ser cerrante a derecha con demora caminos de largo
D + 1:
D
tiene una consecuencia sobre los
todos los caminos de esa longitud que arrancan en un mismo vértice
y llevan igual rótulo, tienen la misma primera arista. La gura 3 ilustra ese hecho. Esto puede generalizarse a caminos más largos diciendo que todos los caminos de largo mayor que
D
arrancando de un mismo nodo y teniendo el mismo rótulo usan las mismas aristas, excepto quizás las últimas
D
de largo mayor que
aristas. Es decir, dos caminos
D)
e0 e1 . . . ek
y
f0 f1 . . . fk
con
k≥D
(o sea,
que arrancan en el mismo vértice y llevan el mismo rótulo cumplen
1. COLOREO DE RUTAS Y PRESENTACIONES CERRANTES A DERECHA
(a)
63
(b)
(c)
(d) Figura 2. Ejemplos de rotulaciones con o sin cierre a derecha
Figura 3. Cierre por la arista inicial de caminos con igual rótulo
ej = fj para cada j ∈ {0, . . . , k − D}: aplicando la de nición a los dos bloques iniciales e0 . . . eD y f0 . . . fD , obtenemos que e0 = f0 , con lo cual e1 . . . ek y f1 . . . fk arrancan en un mismo vértice, y, en caso de tener largo al menos D + 1, aplicamos el mismo razonamiento para ver que e1 = f1 , y así sucesivamente. Visto así, la propiedad de cierre a derecha actúa a que
la manera de un cierre de prenda de vestir, juntando todas las aristas de los caminos de largo mayor que
D
D
que arrancan desde un mismo vértice y llevan un mismo rótulo, salvo las últimas
aristas. Véase la gura 4.
Figura 4. Cierre de todas excepto las últimas
D
aristas de caminos con igual rótulo
64
6. CÓDIGOS DE ESTADOS FINITOS
Usando esta idea para caminos cada vez más largos, vemos que la ambigüedad se traslada cada vez más hacia la derecha; en un caso límite de caminos in nitamente largos hacia la derecha, esa ambigüedad queda entonces
expulsada al in nito (o sea, no subsiste la ambigüedad).
Es decir, veremos que, en un grafo rotulado cerrante a derecha, cualquier pareja de caminos in nitos a derecha que empiezan en el mismo estado y llevan el mismo rótulo corresponden en realidad a un único camino en el grafo. Para formalizar esto, dado un espacio shift X cualquiera X + como el conjunto de todas las sucesiones in nitas a derecha
de nimos su
shift unilateral
que aparecen en
X.
Es decir,
X + = {x0 x1 x2 . . . : (xk )k∈Z ∈ X} En el caso del shift de aristas correspondiente al grafo
G = (V, Σ, i, t), X+ G
corresponde al
conjunto de caminos in nitos a derecha que pueden ser recorridos en el grafo:
X+ G = {e0 e1 e2 . . . : ∀k ∈ N, ek ∈ Σ ∧ t(ek ) = i(ek+1 )} Si
I
es un estado de
G,
designamos por
X+ G,I
como el conjunto de caminos in nitos a derecha
que pueden ser recorridos en el grafo empezando en
I:
+ X+ G,I = e0 e1 e2 . . . ∈ XG : i(e0 ) = I
G = (G, L) es un grafo rotulado, X+ G es la familia de los rótulos de todos los caminos in nitos + derecha en G. Si para cada e0 e1 e2 . . . ∈ XG designamos
Si a
tendremos que
X+ G
L+ (e0 e1 e2 . . .) = L(e0 )L(e1 )L(e2 ) . . . , + + + = L+ (X+ L (x) : x ∈ X+ : X+ G) = G , resultando que L G → XG
es una
función sobreyectiva. Proposición 6.4. Un grafo rotulado (G, L) es cerrante a derecha si, y sólo si, para cada vértice I del grafo, L+ |X+ es inyectiva. G,I
Demostración. Supongamos primero que
es cerrante a derecha, digamos con de-
I un vértice cualquiera del grafo, y sean x = e0 e1 e2 . . . e y = f0 f1 f2 . . . caminos + + X+ G,I tales que L (x) = L (y). Entonces i(e0 ) = I = i(f0 ) y L(e0 )L(e1 ) . . . L(eD ) = L(e0 )L(e1 ) . . . L(eD ). Por ser el grafo rotulado cerrante a derecha con demora D, debe ser e0 = f0 y, en consecuencia, e1 y f1 comienzan en el mismo vértice t(e0 ). Como L(e1 )L(e2 ) . . . L(eD+1 ) = L(f1 )L(f2 ) . . . L(fD+1 ) y el grafo es cerrante a derecha, es e1 = f1 . Aplicando sucesivamente el mismo razonamiento, se cumple que para todo k ∈ N es ek = fk , es decir, x = y , y de este + + modo L es inyectiva si se la restringe a XG,I . Ahora probemos la vuelta por contrarreciprocidad. Supongamos entonces que (G, L) no es cerrante a derecha. Esto signi ca que para cada D ≥ 0, existe una pareja de caminos de largo D + 1, digamos π y τ , que comienzan en un mismo vértice, tienen distinta primera arista y 2 llevan ambos el mismo rótulo. Elijamos tales caminos para el caso en que D = |V | . Será
mora
D.
(G, L)
Sea
in nitos en
π = e0 e1 . . . eD
τ = f0 f1 . . . fD
i(e0 ) = i(f0 ), e0 6= f0 y L(e0 )L(e1 ) . . . L(eD ) = L(f0 )L(f1 ) . . . L(fD ). Como D + 1 > |V |2 , debe haber índices i < j tales que la pareja ei , fi coincide con ej , fj , por lo que ei . . . ej y fi . . . fj son ambos ciclos en G comenzando en un mismo nodo; llamémosles β y γ respectivamente, 0 0 siendo |β| = |γ|. Hagamos α = e0 . . . ei−1 y α = f0 . . . fi−1 , siendo |α| = |α |. Notar que 0 L(α) = L(α ) por ser ambos subcaminos iniciales de π y τ con igual longitud; y, similarmente, L(β) = L(γ). Entonces αβ ∞ y α0 γ ∞ son dos caminos in nitos a derecha arrancando en i(e0 ), + ambos distintos (pues e0 6= f0 ) y con rotulaciones iguales. Luego, L |X+ no es inyectiva. con
G,i(e0 )
Una situación en la que podemos garantizar que un grafo rotulado es cerrante a derecha es aquella en la que la función rotuladora, como código de ventana deslizante que es, resulta ser una conjugación.
1. COLOREO DE RUTAS Y PRESENTACIONES CERRANTES A DERECHA
65
Sea G = (G, L) un grafo rotulado con L∞ : XG → XG conjugación cuya tiene anticipación n. Entonces el grafo rotulado es cerrante a derecha con demora
Proposición 6.5.
inversa n.
L−1 ∞
Demostración. Podemos suponer que
caminos comenzando en el mismo vértice
I
G
es esencial. Sean
e0 e1 . . . en
y
f0 f1 . . . fn
dos
y llevando el mismo rótulo. Debemos probar que
e0 = f0 . m a la memoria de L−1 ∞ y Φ a la respectiva función de bloques, elijamos un camino π en G de largo m que termine en I (tal elección es posible por ser G esencial). Entonces L(πe0 e1 . . . en ) = L(π)L(e0 e1 . . . en ) = L(π)L(f0 f1 . . . fn ) = L(πf0 f1 . . . fn ). Luego, Φ (L(πe0 e1 . . . en )) = Φ (L(πf0 f1 . . . fn )), siendo el primer miembro de esta igualdad precisa−1 mente e0 , y el segundo f0 (por ser Φ la función inductora de L∞ ). Es decir, e0 = f0 . Llamando
Recordemos que el desdoblamiento de salidas de un grafo rotulado corresponde a un desei con el mismo rótulo
doblamiento de salidas del grafo subyacente, rotulando todas las aristas que en el grafo original tiene la arista
e.
Recordemos también que esto produce una nueva
presentación del mismo shift só co. Demostraremos ahora que si se desdobla un grafo rotulado resolvente a derecha con demora con demora
D, el grafo desdoblado es también resolvente a derecha, aunque
D + 1.
Proposición 6.6. Sea G cerrante a derecha con demora D . Cualquier grafo rotulado obtenido por desdoblamiento de salidas de G es cerrante a derecha con demora D + 1.
G = (G, L), y sea (H, L0 ) un grafo obtenido por desdoblamiento de i i i salidas de G . Recordar que H tiene estados I y aristas e , y que el código de amalgama e → e 0 0 i da una conjugación de XH a XG . Además, la rotuladora L en H está dada por L (e ) = L(e). 0 Veremos que (H, L ) es cerrante a derecha con demora D + 1. iD+1 jD+1 j0 j1 i0 i1 Sean e0 e1 . . . eD+1 y f0 f1 . . . fD+1 dos caminos de largo D +2 en H comenzando ambos en I i y teniendo el mismo rótulo (según L0 ). Aplicando el código amalgama, vemos que e0 e1 . . . eD+1 y f0 f1 . . . fD+1 son caminos de largo D + 2 en G comenzando en I y con el mismo rótulo (para L). Así que e0 e1 = f0 f1 . Ya que i0 está determinado por el elemento de la partición al que pertenece e1 , y similarmente j0 está determinado por el elemento de la partición al que j0 i0 0 pertenece f1 , concluimos que e0 = f0 , quedando establecido que L es cerrante a derecha con demora D + 1. Demostración. Sea
Ejemplo 6.7. Consideremos el grafo rotulado (b) de la gura 2, que es cerrante a derecha 1 2 1 con demora 1. Hagamos un desdoblamiento elemental de salidas usando ΣI , ΣI y ΣJ , donde Σ1I consiste en el rulo en I rotulado a y la única arista de I a J rotulada b, Σ2I es el resto de 1 las aristas que salen de I , y ΣJ = ΣJ . El grafo rotulado desdoblado resultante se muestra en la 1 gura 5. En él, hay dos caminos comenzando en I rotulados aa que usan distinta arista inicial,
por lo que el grafo no tiene demora 1. Sin embargo, la proposición muestra que tiene demora 2, como efectivamente puede veri carse.
Figura 5. El desdoblamiento de grafos rotulados incrementa una unidad la demora
66
6. CÓDIGOS DE ESTADOS FINITOS
Recordemos que, en un grafo rotulado, la entropía del shift de aristas del grafo subyacente y la del só co coinciden si la rotulación es resolvente a derecha. Lo mismo es cierto para las rotulaciones cerrantes a derecha. Proposición 6.8.
h (XG ).
Sea G = (G, L) un grafo rotulado cerrante a derecha. Entonces, h (XG ) =
h (XG ) ≤ h (XG ). Para probar la desigualdad en el otro sentido, supongamos que G es cerrante a derecha con demora D . Entonces, cada estado I de G y cada bloque de largo n + D en el lenguaje de XG determinan a lo sumo un camino de largo n en G, y todos los caminos en Bn (XG ) surgen de esta forma. Luego, |Bn (XG )| ≤ |V | × |Bn+D (XG )|. Aplicando logaritmos, dividiendo por n y tomando límite cuando n → ∞, resulta h (XG ) ≤ h (XG ). Demostración. Ya que
XG
es factor de
2.
XG ,
tenemos que
Códigos de estados nitos
Introduciremos ahora una clase de dispositivos para transformar sucesiones arbitrarias (es decir, sin restricciones) sobre un alfabeto en sucesiones sujetas a determinadas restricciones (posiblemente sobre otro alfabeto). Analizaremos también desde el punto de vista teórico la factibilidad del método en lo que resta del capítulo.
código de estados nitos (CEF) grafo codi cador, I es un coloreo de
Definición 6.9. Un
es una terna
(G, I, O),
donde
G
rotulación de entradas y O es una rotulación cerrante a derecha de G llamada rotulación de salidas.
es un grafo llamado
Si todos los vértices de
O∞ (XG ),
G
rutas de
G
llamado
n y si X es un espacio shift que (X, n)-código de estados nitos.
tienen grado de salida
decimos que la terna
(G, I, O)
es un
contiene a
Representaremos grá camente a los CEF mediante el dibujo del correspondiente grafo y una leyenda de la forma
a/b
en cada arista
e,
en donde
a
representa
I(e)
y
b
representa
O(e).
Ejemplo 6.10. El grafo rotulado (b) de la gura 2 tiene grado de salida constante 4, de
modo que proporciona una rotulación de salida para un CEF. La gura 6 muestra una posible elección de rotulación de entradas con alfabeto
{0, 1, 2, 3}.
Figura 6. Un ejemplo de CEF
(G, I, O)
(X, n)-CEF e I0 es un estado jo de G, podemos transformar cualquier + a0 a1 a2 . . . ∈ AZ en otra sucesión de salidas r0 r1 r2 . . . de X + del siguiente modo: identi camos la única arista e0 saliendo de I0 tal que I(e0 ) = a0 y de nimos r0 = O(e0 ). Ahora desde el vértice terminal de e0 sale una única arista e1 tal que I(e1 ) = a1 y de nimos r1 = O(e1 ). Continuando de esta manera, de nimos rk para cualquier k ∈ N. Si
es un
sucesión arbitraria de entradas
Obviamente, queremos ser capaces de recuperar la sucesión original a partir de la sucesión así obtenida. Es precisamente para ello que hemos requerido que proposición 6.4 nos garantiza que
O
O
sea cerrante a derecha: la
es inyectiva cuando se restringe a los caminos in nitos en G que arrancan en I0 , lo que signi ca que hay un único camino in nito e0 e1 e2 . . . en X+ G,I0 tal que O(e0 e1 e2 . . .) = r0 r1 r2 . . .; por lo tanto, cada ak se recupera viendo I(ek ).
3. AUTOVECTORES APROXIMADOS
(G, O)
r0 r1 . . . rD determina e0 , así que a0 = I(e0 ). Luego, r1 r2 . . . rD+1 es un camino rotulado (por O) en G que comienza en t(e0 ), y por lo tanto determina e1 , de donde a1 = I(e1 ). Continuando de este modo, obtenemos todos los ak . Concretamente, si
tiene demora
D,
67
el bloque
En la práctica sólo podemos manejar sucesiones nitas de símbolos. En tal caso, a partir de una sucesión nita arbitraria
a0 a1 . . . ak
podemos generar, por el método arriba descripto,
a0 a1 . . . ak−D (pues O es D). Si bien esto parece alarmante, una solución posible es agregar D símbolos arbitrarios a la derecha de a0 a1 . . . ak y codi car mediante el CEF esta sucesión más grande; obtendremos así una r0 r1 . . . rk . . . rk+D que nos permitirá recuperar a0 a1 . . . ak r0 r1 . . . rk .
Pero el conocimiento de ésta sólo nos permite recuperar
cerrante a derecha con demora
completamente y sin ambigüedades. Ahora bien, dado un alfabeto de
n
símbolos para las sucesiones arbitrarias de entrada y un
X , resta ver bajo qué condiciones existe un (X, n)-CEF. El teorema principal de los X tenga su ciente capacidad de almacenamiento de información, o complejidad, la que es medida por la entropía. shift só co
códigos de estados nitos establece cuál es exactamente esa condición: que
Teorema 6.11.
(Teorema de los Códigos de Estados Finitos) Sean X un shift só co
y n un entero positivo. Entonces, hay un (X, n)-código de estados nitos si, y sólo si, h(X) ≥ log n. La dirección fácil de la demostración es la directa: si
(G, I, O)
es un
(X, n)-CEF,
por
la proposición 6.8, que establece que las rotulaciones cerrantes a derecha preservan entropía, tenemos que shift de
n
h (I∞ (XG )) = h(XG ) = h (O∞ (XG )). Como (G, I) O∞ (XG ) ⊆ X , tenemos que
es una presentación del full
símbolos, y además
log n = h (I∞ (XG )) = h (O∞ (XG )) ≤ h(X) La demostración de la implicación recíproca es mucho más delicada, y requiere de nuevas ideas que desarrollaremos en las secciones posteriores del capítulo.
3. Supongamos que
n
Autovectores aproximados
es un entero positivo y que
una presentación resolvente a derecha
X
es un shift só co. Sabemos que
X
admite
Si tenemos la suerte de que, en esa presentación,
(X, n)-CEF simplemente n aristas salientes desde cada estado (borrando las otras) y restringiendo L a esas aristas elegidas (llamemos O a esa restricción). Obtenemos así un subgrafo G coloreable, al que dotamos de cualquier coloreo de rutas I . Tenemos que (G, I, O) constituye un (X, n)CEF, pues I y O son ambas resolventes a derecha (y entonces O es cerrante a derecha con demora D = 0) y O∞ (XG ) = L∞ (XG ) ⊆ L∞ (XH ) = X . El problema sería que H no tuviese al menos n aristas saliendo desde cada estado. Veremos, sin embargo, que si X satisface la condición h(X) ≥ log n, una cadena de desdoblamientos de estados convenientemente elegidos, aplicados sucesivamente a partir de (H, L), producirá una presentación de X en la que hay al menos n aristas saliendo desde cada vértice. A ella le aplisalen al menos
n
(H, L).
aristas desde cada vértice, podemos diseñar un
eligiendo exactamente
caremos nuestras consideraciones previas, y de esta manera quedará completa la demostración del Teorema de los Códigos de Estados Finitos, que se hará en la sección posterior. Nos dedicaremos ahora a presentar la herramienta precisa que nos servirá de guía para elegir
(H, L), para autovector aproximado,
convenientemente la sucesión de desdoblamientos de estados a realizar, a partir de llegar a la presentación buscada. Esa herramienta recibe el nombre de
y, para motivar su nombre y su de nición, notemos que si un grafo con matriz de adyacencia
A
tiene al menos
n
aristas saliendo desde cada vértice, cada la de
condición equivale a la desigualdad matricial dimensión igual al tamaño de columna
v 6= 0
A
A1 ≥ n1,
1
A
suma al menos
1
n.
Esa
es el vector columna de
y que tiene todos sus coe cientes valiendo
que, reemplazado en cuenta de
recibirá un nombre especial.
en donde
1.
Cualquier vector
en esa desigualdad, la siga satisfaciendo,
68
6. CÓDIGOS DE ESTADOS FINITOS
Definición 6.12. Sea
A
una matriz a coe cientes enteros no negativos, y
n
un entero
(A, n)-autovector aproximado ((A, n)-AA) es un vector v 6= 0 con coe cientes Av ≥ nv. 1 3 Ejemplo 6.13. Sean A = y n = 5. De la de nición de autovector aproximado, 6 1 resulta que cualquier (A, 5)-AA u = (u1 , u2 ) debe satisfacer u1 + 3u2 ≥ 5u1 6u1 + u2 ≥ 5u2
positivo. Un
enteros no negativos que satisface
o, equivalentemente,
−4u1 + 3u2 ≥ 0 6u1 − 4u2 ≥ 0
Este sistema determina un cono en el primer cuadrante; los puntos de ese cono que tienen ambas coordenadas enteras son precisamente los
(A, 5)-autovectores
aproximados. Entre ellos,
tenemos
2 3
3 4 5 6 6 7 , , , , , , ,... 4 6 7 8 9 10
A de tamaño r y un n > 0, el conjunto de los (A, n)-AA es el conjunto de vectores (u1 , . . . , ur ) a coordenadas enteras no negativas que se encuentran en el cono poliédrico de dimensión r (o Pr menor) determinado por el sistema de inecuaciones { J=1 AIJ uJ ≥ nuI : 1 ≤ I ≤ r}. El ejemplo anterior es generalizable de manera directa al hecho de que dada una matriz
Observación 6.14. Podemos caracterizar de diversas maneras a los autovectores aproxi-
mados.
v un (A, n)-autovector aproximado. Siendo A ≥ 0, es A2 v = A(Av) ≥ A(nv) = n(Av) ≥ n(nv) = n2 v. Una sencilla inducción muestra que, más generalmente, para k k todo k ≥ 0 se cumple que A v ≥ n v toda vez que v es un (A, n)-AA. + Por lo tanto, dados n ∈ Z , A y v 6= 0 a coe cientes enteros no negativos,
Sea
v Sea
A
es
(A, n)-AA ⇐⇒ ∀k ∈ N, Ak v ≥ nk v
la matriz de adyacencia de un grafo
G = (V, Σ, i, t),
y
v 6= 0
un vector a coe -
cientes enteros no negativos de dimensión igual al tamaño de A. Consideremos cualquier S J ∈ V . Como ΣJ es la unión disjunta L∈V ΣLJ , se tiene que
X
X
vt(e) =
e∈ΣJ
e∈
S
L∈V
vt(e) =
XX
vt(e) =
L∈V e∈ΣL J
ΣL J
XX
vL =
L∈V e∈ΣL J
X X ΣLJ vL = AJL vL L∈V
Por otra parte, de la de nición de autovector aproximado, se tiene que si, y sólo si,
∀J ∈ V, v
P
es
L∈V
AJL vJ ≥ nvJ .
L∈V
v es un (A, n)-AA
Por lo dicho previamente, resulta que
(A, n)-AA ⇐⇒ ∀J ∈ V,
X
vt(e) ≥ nvJ
e∈ΣJ Cuando irreducible
A es la matriz de adyacencia de un grafo G y posee un (A, n)-AA, hay un subgrafo H de G cuya matriz de adyacencia B admite un (B, n)-autovector aproximado
estrictamente positivo. Lema 6.15. Sean G = (V, Σ, i, t) un grafo con matriz de adyacencia A. Existe un (A, n)-AA si, y sólo si, G posee un subgrafo irreducible H con matriz de adyacencia B tal que existe un (B, n)-AA estrictamente positivo.
3. AUTOVECTORES APROXIMADOS
69
Demostración.
⇒)
v un (A, n)-AA. Designemos por K al subgrafo de G que resulta de quitar todos los I (y, obviamente, sus aristas incidentes) para los cuales vI = 0. Sea H una componente conexa de K que sea un sumidero, es decir, que no contenga aristas que terminen en un estado que no esté en H . Tal H es un subgrafo de G. Llamando VH al conjunto de vértices de H y B a su matriz de adyacencia, sea w la restricción de v a VH . Por su de nición, es w > 0. Sea
vértices
Además, podemos observar que:
J ∈ VH P, es wJ = vJ y AIJ = BIJ , por lo que BIJ wJ = AIJ vJ . De allí B w = IJ J J∈VH J∈VH AIJ vJ . Para cualquier J ∈ V − VH , puede ocurrir una de dos alternativas: 1. O bien J no es un vértice en el subgrafo K , lo que ocurre por ser vJ = 0. 2. O bien J es un vértice de K . En tal caso, todas las aristas de G incidentes con I y con J subsisten en K , y, por de nición de H , no hay arista en K desde I hasta J , de donde se deduce que no hay arista en G desde I hasta J . Entonces, en este caso, AIJ = 0. Cualquiera sea esa alternativa, resulta entonces que AIJ vJ = 0. Siendo J arbitrario en P V − VH , tenemos que J∈V −VH AIJ vJ = 0. Para cualquier que
P
Entonces,
X
X
BIJ wJ =
X
AIJ vJ ≥ nvI = nwI
J∈V
(B, n)-AA estrictamente positivo. ⇐) Sea w un (B, n)-AA para el subgrafo H = (V 0 , Σ0 , i0 , t0 ), y sea v el vector de nido por wJ si J ∈ V 0 vJ = 0 si J ∈ V − V 0 P Sea I un vértice arbitrario de G. Si I ∈ / V 0 , siendo vI = 0, la desigualdad L∈V AIL vL ≥ nvI 0 se cumple trivialmente. Y para cualquier I ∈ V , resulta X X X X X AIL vL = AIL vL + AIL vL = AIL wL ≥ BIL wL ≥ nwI = nvI quedando así demostrado que
L∈V 0
L∈V Ya que
w
AIJ vJ =
J∈V −VH
J∈VH
J∈VH
X
AIJ vJ +
v 6= 0
pues
L∈V −V 0
w > 0,
Dada una matriz
A
es un
resulta que
v
L∈V 0
(A, n)-AA.
es un
n,
y un entro positivo
L∈V 0
¾cuándo existe un
(A, n)-AA?
Teorema 6.16. Sean A ≥ 0 una matriz a coe cientes enteros, y n un entero positivo. Entonces, hay un (A, n)-AA si, y sólo si, λA ≥ n. Si además suponemos que A es irreducible, entonces hay un (A, n)-AA estrictamente positivo. Demostración. Llamemos
sea
r
al tamaño de
A.
Sea
G
un grafo cuya matriz de adyacencia
A.
A es irreducible y que admite un (A, n)-AA v > 0. Sean c = m´ ın{vI : 1 ≤ I ≤ r} y d = m´ax{vI : 1 ≤ I ≤ r}, k k teniéndose que d ≥ c > 0. Para cualquier k ∈ N, es A v ≥ n v (observación 6.14), lo que k implica que para cualquier I ∈ {1, . . . , r} es A v ≥ nk vI , y entonces I Para la implicación directa, por el lema 6.15, podemos suponer que
d
r X r X
k
A
I=1 J=1
Pr
Pr
IJ
≥
r X r X I=1 J=1
k
k
A
IJ
vJ ≥
r X I=1
k
k
n vI = n
r X
vI ≥ nk rc
I=1
A IJ ≥ nk rc/d. Pero además, por la proposición 5.8 y el Teorema de J=1 P Pr r k k Perron-Frobenius, es I=1 J=1 A IJ ≤ d0 λA para alguna constante d0 > 0. Juntando todo rc 1/k esto, y llamando t = , resulta que, para cualquier k ∈ N, es λA ≥ t n. Haciendo tender k dd0 a in nito, y considerando que t > 0, resulta que λA ≥ n. Es decir,
I=1
70
6. CÓDIGOS DE ESTADOS FINITOS
λA ≥ n. Usando una componente irreducible de G de entropía maximal, podemos suponer que A es irreducible. Su autovector de Perron vA es positivo, y satisface AvA = λA vA ≥ nvA . Si vA tuviese todos sus coe cientes racionales, haciendo v = M vA (donde M es el producto de los denominadores de los coe cientes de vA ) obtendríamos que Av = AM vA = M (AvA ) ≥ M nvA = nv, mostrando que v sería el (A, n)-AA que buscamos. Pero no tenemos garantía de que vA vaya a tener todos Para la implicación recíproca, supongamos que se cumple la condición
sus coe cientes racionales, así que debemos trabajar un poco más para asegurar que hay un
(A, n)-AA. Distinguiremos dos casos: 1. λA = n. En este caso, resolvemos
Av = nv
la ecuación vectorial
por eliminación gaus-
siana (siendo el sistema consistente ya que admite al menos la solución
A
v
tiene todos sus coe cientes enteros, la solución
λA
racionales. Por el teorema de Perron-Frobenius, que
v
es múltiplo de
vA .
Multiplicando a
v
vA ),
y, ya que
debe tener todos sus coe cientes
es geométricamente simple, por lo
por el producto de los denominadores de v0 > 0 que cumple
sus coe cientes (y eventualmente por −1), obtenemos un vector Av0 ≥ nv0 . Entonces, v0 es un (A, n)-AA.
λA > n,
2. Si
de modo que
AvA > nvA ,
elijamos
v
con coordenadas racionales su cien-
temente cercanas a las respectivas coordenadas de siga cumpliéndose. Apliquemos a tal
vA
tal que la desigualdad
Av > nv
v
el proceso de multiplicar por el producto de 0 los denominadores (y eventualmente por −1) para obtener un vector v que satisfará 0 0 0 Av ≥ nv . Entonces, v es un (A, n)-AA.
Veremos más adelante que, a la hora de construir necesario obtener explícitamente un vinculada al shift só co
λA ≥ n,
condición
X)
existe un
(A, n)-AA,
y el entero positivo
(A, n)-AA;
(X, n)-códigos
de estados nitos, es
conociendo cierta matriz
n.
A
(estrechamente
El teorema anterior asegura que, bajo la
sin embargo, no proporciona una manera explícita de
encontrar uno. Afortunadamente, existe un algoritmo que permite hacerlo. Antes de presentarlo, 0 de nimos una nueva notación: dados dos vectores v, v de igual tamaño r , designamos por m´ın(v, v0 ) al vector minimal componente a componente, es decir, (m´ın(v, v0 ))I = m´ın{vI , vI0 } para cada I ∈ {1, . . . , r}. Además, designamos por bvc al vector que se obtiene de tomar las partes enteras de las componentes de Teorema 6.17.
v,
es decir,
bvcI = bvI c
para cada
I ∈ {1, . . . , r}.
(Algoritmo del autovector aproximado) Sean A ≥ 0 una matriz a
coe cientes enteros, n un entero positivo y v 6= 0 un vector a coe cientes enteros no negativos. Pongamos 1 0 Av v = m´ın v, n Si v0 = v, contestar v y nalizar. Si no, reemplazar v por v0 y repetir. Este proceso nalmente culmina, y su respuesta es o bien un (A, n)-autovector aproximado o bien el vector nulo.
Demostración. Los sucesivos vectores que se van produciendo tienen coe cientes enteros
no negativos y monótonamente decrecientes componente a componente. Luego, el proceso debe terminar, pues el vector nulo
0
satisface la condición
1 0 = m´ın 0, A0 n si es que ésta no se produce antes. Sea
v
la respuesta. Se tiene que
v
es un vector a coe cientes enteros no negativos. Si
v = 0,
se cumple el enunciado. Si no, notemos que
1 v = m´ın v, Av n por lo que
Av ≥ nv
con
v 6= 0,
es decir,
v
es un
≤
1 Av n
(A, n)-AA.
4. CONSTRUCCIÓN DE CÓDIGOS DE ESTADOS FINITOS
71
Típicamente, el algoritmo anterior se emplea del siguiente modo: comenzar con
v
siendo el
vector cuyas componentes son todas 1 y aplicar el algoritmo; si la respuesta es un vector no nulo, ya tenemos el autovector aproximado que buscamos. En caso contrario, tomar
v
siendo
el vector cuyas componentes son todas 2, y así sucesivamente. El teorema 6.17 asegura que en algún momento terminaremos con este procedimiento, pues existe un
p = m´axI vI ,
(A, n)-AA v.
Si hacemos
aplicando el algoritmo comenzando con el vector cuyas componentes son todas
p,
se obtendrá como respuesta un vector no nulo (ejercicio).
Ejemplo 6.18. Apliquemos el algoritmo anterior a la matriz
ejemplo 6.13. Comenzando con
v=
Comenzando con
v=
Comenzando con
v=
2 2
del
, obtenemos sucesivamente
→
1 2
→
0 1
→
0 0
0 0
0 0
→
1 1
→
0 1
→
→
0 0
, obtenemos sucesivamente
3 3
y hemos obtenido el más pequeño de los
4.
n=5
, obtenemos sucesivamente
→
3 3
y el
1 1
2 2
1 1
A=
1 3 6 1
→
2 3
→
2 3
(A, 5)-autovectores
aproximados.
Construcción de códigos de estados nitos
En esta sección completaremos la demostración del Teorema de los Códigos de Estados Finitos. Lo haremos de manera constructiva, es decir, proporcionando también un método para construir el CEF, conocidos
n
y el shift só co
X
con
h(X) ≥ log n. (G0 , L0 ) para X . Luego, G = (G00 , L) con h (XG ) =
El primer paso es obtener una presentación resolvente a derecha basados en el corolario 5.24, elegimos una componente irreducible
h (XG0 ) = h(X) ≥ log n. A partir de G , y siguiendo una adecuada secuencia de desdoblamientos de estados de grafos rotulados, construimos una presentación de X en la que desde cada vértice salen al menos n aristas, y en esa presentación eliminamos algunas aristas para obtener un grafo G en el que, desde cada vértice, queden saliendo exactamente n aristas. La función rotuladora restringida a esas aristas será nuestra rotuladora de salidas O , y como rotuladora de entradas I elegimos cualquier coloreo de rutas del grafo que resulta. Así obtenemos el CEF (G, I, O) que buscamos. Para ello, necesitamos demostrar una proposición que constituye el corazón de la demostración de que efectivamente existe aquella secuencia de desdoblamientos de estados de grafos rotulados de la que hablamos más arriba. Y dicha proposición usa un sencillo hecho de teoría de números que enunciamos a continuación.
n Sea {mP i }i=1 una sucesión de n enteros positivos. Entonces, existe S ⊆ {1, . . . , n} tal que n es factor de i∈S mi . P N Demostración. Para cada N ∈ {1, . . . , n}, sea pN = m mod n. i i=1 ∗ Si los pN son todos distintos, debe haber algún N tal que pN ∗ = 0 (pues los posibles restos PN ∗ de una división por n son 0, 1, . . . , n − 1) y, en ese caso n es factor de i=1 mi ; luego, basta ∗ tomar S = {1, . . . , N } para ver que el enunciado es cierto. Lema 6.19.
72
6. CÓDIGOS DE ESTADOS FINITOS
N1 < N2 tales que pN1 = pN2 . Eso signi ca que PN2 P 2 mi mod n, es decir, i=N1 +1 mi = 0 mod n. De aquí que N i=1 mi = i=N1 +1 mi es múltiplo de n; luego, basta tomar S = {N1 + 1, . . . , N2 } para ver que el enunciado es cierto. Si no son todos distintos, debe haber
P
PN1
N2 i=1
Sean n un entero positivo, G = (V, Σ, i, t) un grafo irreducible con matriz de adyacencia A, y v > 0 un (A, n)-autovector aproximado. Supongamos que algún estado K ∗ ∈ V tiene menos de n aristas saliendo de él. Entonces, existe I ∈ V y una partición de ΣI en subconjuntos no vacíos Σ1I y Σ2I tal que el grafo G0 que resulta de desdoblar I en I 1 , I 2 usando esa partición posee matriz de adyacencia A0 que admite un (A0 , n)-autovector aproximado v0 > 0 con vI0 1 + vI0 2 = vI y vJ0 = vJ para todo J ∈ V − {I 1 , I 2 }. Proposición 6.20.
p = m´axJ∈V vJ . Notar que debe haber algún P estado K tal que P vK < p, pues, de lo contrario, tendríamos que ∀K ∈ V, vK = p y entonces L AK ∗ L vL = p L AK ∗ L = p |ΣK ∗ |; como v es (A, n)-AA, tendríamos que p |ΣK ∗ | ≥ nvK ∗ = np, es decir, |ΣK ∗ | ≥ n, ∗ contradiciendo la hipótesis de que desde K salen menos de n aristas. 0 Elijamos entonces I , K ∈ V tales que vK < p y vI 0 = p. Como G es irreducible, hay camino 0 en G desde I hasta K . Sea I el último estado en el recorrido de ese camino tal que vI = p, y ∗ e la arista de ese camino que sale del estado I . Observar que vt(e∗ ) < p. P ≥ nvI = np (observación 6.14). Designemos m = |ΣI |. Como v es (A, n)-AA, es e∈ΣI vt(e) P ∗ Además, ∀e ∈ ΣI , vt(e) ≤ p y ∃e ∈ ΣI : vt(e∗ ) < p. Luego, e∈ΣI vt(e) < p |ΣI | = pm. De lo anterior, tenemos que m > n, es decir, hay más de n aristas saliendo de I . Enumeremos ∗ las aristas de G que salen de I como e1 , . . . , en , . . . , em con e1 = e . Aplicando el lema 6.19 a P la sucesión vt(e1 ) , . . . , vt(en ) , vemos que existe S ⊆ {1, . . . , n} tal que i∈S vt(ei ) = qn para 1 1 2 + 1 6 Σ2I algún q ∈ Z . Designemos ΣI = {ei : i ∈ S} y ΣI = ΣI − ΣI . Tendremos que ΣI 6= ∅ = 0 0 0 0 0 1 (pues |ΣI | > |ΣI |). Sea G = (V , Σ , i , t ) el grafo que resulta de hacer un desdoblamiento 1 2 0 elemental de G por el estado I usando la partición ΣI = {ΣI , ΣI }, y llamemos A a su matriz 0 de adyacencia. De namos v mediante: q si J = I 1 0 vI − q si J = I 2 vJ = vJ si J ∈ V − {I 1 , I 2 } Demostración. Sea
0 2 0 Veamos que v así de nido es positivo. Para J 6= I , vJ > 0 pues q > 0 y vJ > 0. Y para Pn P 0 ver que vI 2 > 0, notemos que nq = i=1 vt(ei ) < np, pues vt(e1 ) = vt(e∗ ) < p y e∈Σ1I vt(e) ≤ P n vt(ei ) ≤ p para i ∈ {2, . . . , n} (así que i=1 vt(ei ) < np); de allí que q < p y, en consecuencia, vI0 2 = vI − q = p − q > 0. 0 Tengamos presente que cada arista e de G que no termina en I es también arista en G y 0 cumple que vt0 (e) = vt(e) ; en tanto, cada arista e de G que termina en I (incluidos los rulos en I ) aparece desdoblada en G0 como e1 y e2 , siendo vt0 0 (e1 ) + vt0 0 (e2 ) = vI0 1 + vI0 2 = vI = vt(e) . 0 0 Resta ver que v es (A , n)-AA. Lo haremos por la segunda caracterización dada en la observación 6.14.
1 1 2 1 2 Designemos ∆ a los rulos en I , ∆ a las aristas que van de I a I y ∆ a 1 1 2 1 0 las que salen de I y no terminan ni en I ni en I (siendo ∆ ⊂ ΣI ). Se tiene que ΣI 1 1 2 1 es la unión disjunta ∆ ∪ ∆ ∪ ∆ , y además ΣI es la unión disjunta de ∆ con los rulos 1 1 1 en I que están en ΣI . Por lo dicho más arriba, por cada arista e ∈ ∆ hay una arista e2 ∈ ∆2 y viceversa; y cada pareja e1 , e2 proviene de un rulo e ∈ ΣII ∩ Σ1I . Entonces, Si
X
J = I 1:
vt0 0 (e) =
X
=
X
e∈Σ0 1
vt0 0 (e) +
e∈∆
vt0 0 (e) +
e∈∆1
e∈∆
I
X
vt(e) +
X e∈ΣII ∩Σ1I
X
vt0 0 (e) =
e∈∆2
vt(e) =
X e∈Σ1I
X e∈∆
X
vt(e) +
e∈ΣII ∩Σ1I
vt(e) = nq = nvI0 1
vt0 0 (e) + vt0 0 (e)
4. CONSTRUCCIÓN DE CÓDIGOS DE ESTADOS FINITOS
J = I 2:
Si
P
Por análisis similar al realizado en el caso anterior, resulta
vt(e) ,
e∈Σ2I
73
y, como
Σ2I = ΣI − Σ1I ,
P
e∈Σ0 2 I
vt0 0 (e) =
se tiene que
! X
X
0 vt(e) =
e∈Σ0 2
X
vt(e) =
e∈ΣI −Σ1I
I
vt(e)
− nq ≥ nvI − nq = n(vI − q) = nvI0 2
e∈ΣI
J ∈ / {I 1 , I 2 }: Designemos ∆1 a las aristas que van de J a I 1 , ∆2 a las que van de J a I 2 y ∆ a las que van de J hasta un vértice distinto de I 1 y de I 2 . Se tiene que Σ0J es la unión disjunta ∆ ∪ ∆1 ∪ ∆2 . Como antes, por cada arista e1 ∈ ∆1 hay una 2 2 1 2 arista e ∈ ∆ y viceversa; y cada pareja e , e proviene de una arista e en G desde J P 0 hasta I . Procediendo de manera análoga a lo anterior, se llega a ver que e∈Σ0J vt0 (e) = P 0 e∈ΣJ vt(e) ≥ nvJ = nvJ . Si
0 Es decir, para todos los vértices de G se cumple la desigualdad requerida en la observación 0 0 0 0 6.14 en cuanto a v , A y n, resultando entonces que v es un (A , n)-AA.
Sean n ∈ Z+ y G un grafo irreducible con matriz de adyacencia A. Si λA ≥ n, entonces existe una sucesión de grafos G0 , G1 , . . . , Gm tales que G0 = G, Gm tiene al menos n aristas saliendo desde cada vértice, y para cada i ∈ {1, . . . , m}, Gi resulta de un desdoblamiento elemental de Gi−1 . Teorema 6.21.
v > 0 un (A, n)-AA, cuya existencia está garantizada por el teorema G0 = G. Si desde cada estado de G salen al menos de n aristas, tomamos m = 0 y el enunciado se cumple. En caso contrario, sea G1 el grafo que resulta de aplicar a G0 la (1) proposición 6.20, cuya matriz de adyacencia tendrá un autovector aproximado v > 0 cuya dimensión es una unidad mayor que la de v pero cuya suma de componentes es igual a la suma de las componentes de v. Si G1 tampoco tiene al menos n aristas saliendo desde cada vértice, le aplicamos nuevamente la proposición 6.20 para obtener un grafo G2 cuya matriz de (2) adyacencia tiene autovector aproximado v > 0 con dimensión una unidad mayor que la de (1) v y suma de coe cientes igual a la suma de los coe cientes de v(1) , y así sucesivamente. El (i) proceso debe terminar, pues cada v que se obtiene en cada paso es estrictamente positivo y (i−1) tiene una coordenada más que v , pero sus respectivas sumas de coe cientes son iguales. Entonces, el último Gm obtenido es el buscado. Demostración. Sea
6.16. Hagamos
Ahora podemos completar la demostración del Teorema de los Códigos de Estados Finitos, cuya vuelta nos estaba faltando. Demostración.
(X, n)-CEF.)
(Su ciencia de la condición de entropía para existencia de un
Supongamos que
X
es un shift só co con
sentación resolvente a derecha para
X.
Sea
G0
h(X) ≥ log n,
y sea
(H, L) una H tal
una componente irreducible de
preque
h (XG0 ) = h (XG ), y sea A la matriz de adyacencia de G0 . Designemos L0 a la restricción de L a las aristas de G0 . Como h(X) = log λA ≥ log n, es λA ≥ n. Aplicando entonces a G0 el teorema 6.21, obtenemos la sucesión de grafos rotulados G0 = (G0 , L0 ), . . . , Gm = (Gm , Lm ) donde G1 , . . . , Gm son los que resultan del teorema, y cada grafo rotulado Gi es el correspondiente desdoblamiento (como grafo rotulado) de Gi−1 . Sabemos que X ⊇ XG0 = XGm , y, por proposición 6.6, Gm es cerrante a derecha con demora m. Como Gm tiene al menos n aristas saliendo desde cada vértice, elegimos exactamente n aristas saliendo desde cada vértice (eliminando las otras) para obtener así un subgrafo G coloreable al que dotamos de un coloreo de rutas I . Designando por O a la restricción de Lm a las aristas de G, resulta que la terna (G, I, O) es un (X, n)-CEF, pues O∞ (XG ) = (Lm )∞ (XG ) ⊆ (Lm )∞ (XGm ) = XGm ⊆ X . X el shift só co mostrado en la (X, 3)-CEF, y, en caso a rmativo, veremos
Ejemplo 6.22. Sea
construir un
gura 7. Analizaremos si es posible la aplicación del procedimiento que
está implícito en las demostraciones anteriores para obtener tal código de estados nitos.
74
6. CÓDIGOS DE ESTADOS FINITOS
Figura 7. Shift só co
X
para construir un
(X, 3)-CEF
El grafo subyacente es irreducible y su matriz de adyacencia es
2 1 1 A= 0 1 1 2 1 0 Su autovalor de Perron es
h(X) = log λA ≥ log 3. (X, 3)-CEF.
λA = 3, 1149 . . .,
y como la presentación es resolvente a derecha, es
Entonces, de acuerdo al Teorema de los Códigos de Estados Finitos,
existe un
Como el grafo subyacente ya es irreducible y la presentación es resolvente a derecha, el grafo rotulado de la gura 7 será nuestro
G0
de arranque. Como hay estados con menos de tres aristas
salientes, deberemos seguir el procedimiento dado en la demostración de la proposición 6.20. Por aplicación del algoritmo de búsqueda de autovector aproximado, llegamos a que
[3, 1, 2] es un (A, 3)-AA. De acuerdo a e∗ que arranque en un estado I
v=
la demostración de la proposición 6.20, buscamos una
vI maximal, y termine en un estado J con vJ no ∗ maximal. Hay varias opciones; elegiremos I = 1 y e la arista de 1 a 3 que tiene rótulo a. 1 ∗ De acuerdo a la demostración, elegimos ΣI conteniendo e y la arista de 1 a 2 con rótulo d, 2 y ΣI son todas las otras aristas que salen de I (los dos rulos en 1, en este caso). Notar que P e∈Σ1I vt(e) = 3, así que el q de la demostración vale, en esta etapa, 1. Luego, el autovector aproximado correspondiente al grafo desdoblado G1 tendrá coe cientes 1 y 2, respectivamente, para los dos estados en que se desdoblará I ; los otros estados conservarán el valor que tienen asociado en G0 . arista
con
En la gura 8, mostramos la sucesión de desdoblamientos de grafos rotulados que se produce. En cada paso, mostramos dentro de un hexágono al lado de cada estado el valor del coe ciente del autovector aproximado que le corresponde en esa etapa, e indicamos con I el estado por el ∗ cual se produce el desdoblamiento, con (∗) la arista e , y con línea discontinua las aristas de 1 ΣI . El proceso para en G3 , pues hemos llegado a una presentación en la que desde cada vértice salen al menos tres aristas. Elegimos entonces exactamente tres aristas saliendo de cada vértice, eliminando las otras, y coloreamos el grafo rotulado resultante con el alfabeto de entradas gura 8 muestra, en la parte inferior, uno de los posibles Usando el hecho de que de tamaño
N sin solape),
h X
N
= N h(X)
(donde
A = {0, 1, 2}.
(X, 3)-CEF.
XN
es la presentación de
La misma
X
en bloques
en los ejercicios se verá cómo se puede adaptar el Teorema de los
Códigos de Estados Finitos para construir códigos aún sin cumplirse de manera directa la condición
h(X) ≥ log n.
4. CONSTRUCCIÓN DE CÓDIGOS DE ESTADOS FINITOS
G0
G1
G2
G3
Figura 8. Cadena de desdoblamientos y un
(X, 3)-CEF
resultante
75