Quelques propriétés topologiques et ergodiques
des automates cellulaires

Systèmes dynamiques uniformes

Un système dynamique non uniforme (SD) est une suite (Ft)t∈N d’applications continues d’un espace métrique compact X dans lui-mˆeme. Lorsque Ft = Gt , pour tout t ∈ N et une application continue G de X dans lui-mˆeme, le système devient uniforme. Dans le cas uniforme, l’évolution d’un système dynamique est donnée par les itérations successives de la transformation : à partir du point x au temps 0, le point G(x) représente la nouvelle position à l’instant 1 et Gt (x) = G . . . G(x) | {z } t fois est la position à l’instant t ∈ N. Définitions Un système dynamique uniforme (X, G) (ou G sur X) est la donnée d’un espace métrique compact X et d’une application continue G : X → X. Soient (X, G) un SD uniforme, U ⊆ X et x ∈ X. — U est dit G-invariant ou invariant par G (resp. fortement G-invariant) si G(U) ⊆ U (resp. G(U) = U). — (U, G) est un sous-système de (X, G) si U est non vide, fermé et Ginvariant. — (X × Y, G × H) est le système produit de deux SD uniformes (X, G) et (Y, H) tel que ∀(x, y) ∈ X × Y,(G × H)(x, y) = (G(x), H(y)). Orbites. On appelle orbite (positive) d’un point x l’ensemble OG(x) =  G t (x)  t ∈ N = {x, G(x), G2 (x), …}. — Un point x est dit périodique si ∃p ≥ 1, tel que Gp (x) = x. — La période est la petite valeur de p ≥ 1 telle que Gp (x) = x. — Un point x est dit ultimement périodique si son orbite contient un point périodique. Tout point ultimement périodique a une orbite finie. Paires asymptotiques. — Deux points x, y sont dits asymptotiques (ou (x, y) est une paire asymptotique) si lim t→∞ d(G t (x), Gt (y)) = 0. — La classe asymptotique de x ∈ X est AG(x) = n y ∈ X    lim t→∞ d(G t (x), Gt (y)) = 0o . La remarque suivante indique que, dans un espace fini, les paires asymptotiques correspondent à des orbites finalement égales. Remarque 1.1.1. Soient G un SD uniforme sur un espace fini X et x, y ∈ X. Si x et y sont asymptotiques, alors ∃t ∈ N tel que Gt (x) = Gt (y). En particulier, si G est injectif (ou surjectif ), alors x = y. 

Démonstration

Le premier point est clair, parce que X est discret. Le deuxième point est clair, parce que si X est fini, alors l’injectivité ou la surjectivité de G est équivalente à la bijectivité pour tout Gt . Propriété de Baire. — Un sous-ensemble U ⊆ X est dit comaigre dans X s’il contient une intersection dénombrable d’ouverts denses. — Un sous-ensemble U est maigre si X\U est comaigre. D’après le théorème de Baire, dans un espace métrique compact, un ensemble comaigre est dense. — On dit qu’une partie A d’un espace topologique X a la propriété de Baire s’il existe un ouvert U de X tel que la différence symétrique A∆U = (A\U) ∪ (U\A) soit maigre. — Une tribu sur X est un ensemble non vide de parties de X, stable par complémentaires et par unions (ou intersections) dénombrables. — La tribu borélienne (ou tribu de Borel) d’un espace topologique X est la tribu engendrée par les ouverts, ou les fermés, de X. Elle est la plus petite tribu sur X contenant tous les ouverts. Les éléments de la tribu borélienne sont appelés des boréliens. — Les parties de X qui ont la propriété de Baire forment une tribu sur X s’appelle tribu de Baire. Puisque tout ouvert a la propriété de Baire (car l’ensemble vide est maigre), cette tribu contient celle des boréliens ; pour tout borélien A, il existe un ouvert U tel que A∆U soit maigre (pour plus de détails voir [66]). On va utiliser la remarque suivante plusieurs fois. Remarque 1.1.2. Un ensemble W ⊆ X avec la proriété de Baire n’est pas comaigre si et seulement s’il existe un ouvert non vide U dans lequel W ∩ U est maigre. Autrement dit, un ensemble est comaigre si et seulement s’il n’est maigre dans aucun ouvert. Démonstration. WC∆U est maigre pour un certain ouvert U, et W ∩ U ⊆ WC∆U. On remarque que W est comaigre si et seulement si U = ∅. Equicontinuité et sensibilité. — L’ensemble des points d’équicontinuité EG ⊆ X de G est défini par x ∈ EG ⇐⇒ ∀ε > 0, ∃δ > 0, ∀y ∈ Bδ(x), ∀t ≥ 0, d(G t (x), Gt (y)) < ε. Si EG 6= ∅, alors on dit que G est presque-équicontinu.

SYSTEMES DYNAMIQUES UNIFORMES

Si EG est comaigre, alors on dit que G est quasi-équicontinu. Si EG = X, alors on dit que G est équicontinu. De manière équivalente par compacité, pour tout ε > 0, il existe δ > 0 uniforme tel que ∀x ∈ X, ∀y ∈ Bδ(x), ∀t ∈ N, d(G t (x), Gt (y)) < ε. Quand le contexte sera évident, on pourra omettre l’indice G. — G est sensible si ∃ε > 0, ∀x ∈ X, ∀δ > 0, ∃y ∈ Bδ(x), ∃t ∈ N, d(G t (x), Gt (y)) ≥ ε. — G est positivement expansif si ∃ε > 0, ∀x, y ∈ X, x 6= y, ∃t ∈ N, d(G t (x), Gt (y)) ≥ ε. 1.1.2 Dynamique asymptotique — L’ensemble limite de U est ΩG(U) = \ t∈N OG(Gt (U)) . Soit y ∈ X, y ∈ ΩG(U) si et seulement s’il existe une suite des points xk ∈ U et une suite croissante (tk)k∈N telles que lim k→∞ G tk (xk) = y. Tout ensemble limite est G-invariant. Si U est fermé et G-invariant, alors ΩG(U) = \ t∈N G t (U). On dit que ΩG = ΩG(X) est l’ensemble limite de G. — G a un ensemble limite stable s’il existe T ∈ N tel que G T (X) = ΩG. — L’ensemble asymptotique de U est ωG(U) = [ x∈U ΩG(x). Tout ensemble asymptotique est G-invariant. On dit que ωG = ωG(X) est l’ensemble asymptotique de G.— L’ensemble asymptotique d’un point x est exactement son ensemble limite. ωG(x) = ωG({x}) = [ x∈{x} ΩG(x) = ΩG(x). Quand le contexte sera évident, on pourra omettre l’indice G. Un ensemble limite est une intersection décroissante d’ensembles fermés. Par compacité, tout ensemble limite est un fermé non vide. En revanche, tout ensemble asymptotique n’est pas fermé. La proposition suivante contient certaines propriétés des ensembles asymptotiques. Proposition 1.1.3. Soit (X, G) un SD uniforme, x ∈ X et U ⊆ X. 1. Si x est un point périodique, alors ω(x) = OG(x). En particulier, x ∈ ω(x). 2. ω(Gt (x)) = ω(x) pour tout t ∈ N. 3. Si y ∈ ω(x), alors ω(y) ⊆ ω(x). 4. Si U 6= ∅, alors Ω(U) 6= ∅ et ω(U) 6= ∅. Nilpotence. — On dit que G est nilpotent s’il existe un point z ∈ X tel que ∃T ∈ N, ∀x ∈ X, ∀t > T, Gt (x) = z. — On dit que G est asymptotiquement nilpotent si ωG est un singleton. Pour savoir plus sur l’ensemble asymptotique des systèmes dynamiques, on peut consulter [32]. On note qu’il a été appelé ensemble accessible dans [24], et ensemble ultime dans [31].

Attracteurs

Soit (X, G) un SD uniforme. V ⊆ X est un attracteur s’il est non vide, fermé, G(V ) = V et si pour tout ε > 0, il existe δ > 0 tels que pour tout x ∈ X, d(x, V ) < δ =⇒ ∀t ≥ 0, d(G t (x), V ) < ε et lim t→∞ d(G t (x), V ) = 0. — V est un attracteur minimal, si aucun ensemble V 0 ⊆ V n’est un attracteur. — V est un quasi-attracteur, s’il est une intersection dénombrable d’attracteurs. — Le domaine (ou bassin) d’un attracteur V est DG(V ) = n x ∈ X    lim t→∞ d(G t (x), V ) = 0o .

SYSTEMES DYNAMIQUES UNIFORMES 

Définition 1.1.4. Soit (X, G) un SD uniforme. Un ensemble U ⊆ X est entrant si G(U) ⊆ ◦ U. On va voir dans la proposition suivante que l’ensemble limite de tout ensemble entrant est un attracteur, l’ensemble limite est un attracteur qui contient tous les attracteurs et l’union et l’intersection de deux attracteurs est un attracteur. De plus, le domaine d’attraction de tout attracteur est ouvert (voir la preuve dans le livre de K˚urka [43]). Proposition 1.1.5. Soit (X, G) un SD uniforme. 1. Si G(U) ⊆ ◦ U, alors V = ΩG(U) est un attracteur. 2. ΩG est l’attracteur maximal. 3. Si V0, V1 sont des attracteurs, alors V0 ∪ V1 est un attracteur. 4. Si V0, V1 sont des attracteurs tels que V0 ∩ V1 6= ∅, alors V0 ∩ V1 est le plus grand attracteur contenu dans les deux. 5. L’ensemble des attracteurs de (X, G) est au plus dénombrable. 6. Le domaine d’un attracteur est ouvert. La proposition suivante a été prouvée dans [43]. Elle veut dire que, dans un SD uniforme, le domaine d’un attracteur équicontinu est équicontinu. Proposition 1.1.6. [43] Si V est un attracteur dans (X, G) et si V ⊆ E, alors DG(V ) ⊆ E. 1.1.4 Récurrence Points récurrents. Soit (X, G) un SD uniforme. Un point x ∈ X est un point récurrent si pour tout voisinage U de x, ∃t ∈ N, Gt (x) ∈ U. Un point récurrent ne revient pas forcément exactement à lui-mˆeme, mais il retourne à n’importe quel voisinage (arbitrairement petit) de lui-mˆeme. Voici quelques propriétés des points récurrents (voir la preuve dans le livre de Vries [19]). Proposition 1.1.7. Soit (X, G) un SD uniforme. 1. Un point x ∈ X est récurrent si et seulement si x ∈ OG(x). 2. L’ensemble de tous les points récurrents, noté RG, est G-invariant. 3. Tout point périodique est un point récurrent. 4. Un point ultimement périodique mais non périodique n’est pas un point récurrent. 5. Si A ⊆ X est G-invariant et x ∈ A, alors x est un point récurrent dans (X, G) si et seulement s’il est récurrent dans le sous-système (A, G|A ). 6. si x ∈ RG, alors pour tout voisinage U de x, l’ensemble D(x, U) est infini, o`u D(x, U) =  t ∈ N   G t (x) ∈ U . Il est bien connu qu’un point est récurrent si et seulement s’il appartient à son ensemble asymptotique (voir par exemple le livre de Vries [19]). Proposition 1.1.8. Soit (X, G) un SD uniforme. Les conditions suivantes sont équivalentes : 1. x ∈ X est un point récurrent ; 2. x ∈ ω(x); 3. ω(x) = OG(x). Points non-errants. Soit (X, G) un SD uniforme. — Un point x ∈ X est un point non-errant si pour tout voisinage U de x, ∃t ≥ 1, U ∩ G −t (U) 6= ∅. — L’ensemble des points non-errants est noté NG, on dit que G est non-errant si NG = X, ou, de manière équivalente, si pour tout ouvert U ⊆ X, ∃t ≥ 1, U ∩ G −t (U) 6= ∅. Voici quelques propriétés des points non-errants (voir par exemple le livre de Vries [19]). Proposition 1.1.9. Soit (X, G) un SD uniforme. 1. Pour tout point x ∈ X on a ω(x) ⊆ NG. 2. L’ensemble des points non-errants est compact non vide et G-invariant. 3. Si un point est non-errant dans un sous-système (A, G) de (X, G), alors il est non-errant dans le système (X, G). 4. Tout point récurrent est un point non-errant. 5. Si X a un sous-ensemble dense des points récurrents, alors NG = X. En particulier, c’est le cas si X a un ensemble dense des points périodiques. 6. Si x ∈ NG, alors pour tout voisinage U de x, l’ensemble D(U, U) est infini, o`u D(U, U) =  t ∈ N   G t (U) ∩ U 6= ∅ . 7. Si G est non-errant, alors l’ensemble des points récurrents est comaigre.

Transitivité 

Soit G un SD uniforme sur X. — Un point est transitif si son orbite est dense. — Si l’orbite de tout point x ∈ X est dense dans X, ou bien, de manière équivalente, si G n’a pas d’ensemble G-invariant fermé sauf l’ensemble vide et X, on dit que G est minimal. — G est transitif si pour tous ouverts U, V ⊆ X, il existe t ≥ 1 tel que Gt (U) ∩ V 6= ∅, ou de manière équivalente, U ∩ G−t (V ) 6= ∅. — G est semi-transitif si pour tous ouverts non vides U, V ⊆ X tel que V ∩ ΩG 6= ∅, il existe t ≥ 1 tel que U ∩ G−t (V ) 6= ∅. Tout SD uniforme transitif est semi-transitif. La réciproque est vraie si le SD est surjectif. D’après la proposition suivante, tout système dynamique uniforme transitif est surjectif et non-errant mais n’est pas sensible. Proposition 1.1.10. [13, 2] 1. Tout SD uniforme transitif est surjectif. 2. Un SD uniforme transitif est soit sensible, soit quasi-équicontinu. 3. Tout SD uniforme transitif est non-errant. Pour la transitivité, il existe de nombreuses équivalences dans la littérature, par exemple [18, 3]. Dans la proposition suivante, l’espace est parfait [4] ou bien le système est surjectif [5]. Proposition 1.1.11. [4, 5] Soit (X, G) un SD uniforme tel que X est un espace parfait ou G est surjectif. Les conditions suivantes sont équivalentes. 1. (X, G) est transitif. 2. Pour tout ouvert non vide U ⊆ X, S∞ t=1 G−t (U) est dense. 3. L’ensemble des points transitifs est non vide. 4. Il existe x ∈ X tel que ωG(x) = X. 5. Pour tous ouverts U, V ⊆ X, l’ensemble D(U, V ) est infini, o`u D(U, V ) =  t ∈ N   G t (U) ∩ V 6= ∅ . Mélange. — Un SD uniforme (X, G) est faiblement mélangeant si (X × X, G × G) est transitif. — Un SD uniforme (X, G) est faiblement semi-mélangeant si pour tous ouverts non vides U, V, U0 , V 0 ⊆ X tels que V et V 0 intersectent ΩG, il existe t ≥ 1 tel que U ∩ G −t (V ) 6= ∅ et U 0 ∩ G −t (V 0 ) 6= ∅.