Feeds:
Posts
Comments

Posts Tagged ‘symbolic dynamics’

Le 21 novembre dernier Thomas Fernique a défendu son habilitation à diriger des recherches au Laboratoire d’Information de Paris-Nord. Il étudie les pavages et tout particulièrement les pavages ordonnées et apériodiques, modélisant les célèbres quasi-cristaux découverts dans les années 1980. Ses travaux explorent les liens entre différentes classes naturelles de tels systèmes dynamiques multidimensionnels (ie, définis par une action de R^d, d\geq 1): pavages sofiques et substitutifs; pavages planaires vs. sofiques ou de type fini; pavages obtenus par recuit.

L’exposé était suivi d’un pot agrémenté d’un pavage de Penrose (pavage défini par un plan plongé dans R^5) en chocolats blancs et noirs, digne suite d’une autre réalisation à découvrir ici.

Advertisements

Read Full Post »

La fonction de Moebius \mu:\mathbb N^*\to\{-1,0,1\} peut se voir comme un point \mu du décalage (\{-1,0,1\}^{\mathbb N},\sigma). On s’intéresse aux points d’accumulation de l’orbite (et donc au sous-décalage X_M:=\overline{\{\sigma^n(\mu):n\geq0\}}) et des mesures empiriques m^\mu_n:=\frac1n\sum_{k=0}^{n-1} \delta_{\sigma^k(\mu)}. La conjecture de Chowla (1965) est équivalente à la convergence des mesures empiriques vers une mesure pour laquelle les signes des éléments non-nuls sont indépendants.

Thierry de la Rue a exposé au groupe de travail ergodique et dynamique une partie de ses travaux (en collaboration avec El Abdalaoui et Lemanczyk). Il s’agit d’une généralisation du problème où l’interdiction des facteurs carrés p_1^2,p_2^2,\dots est remplacée par celle d’une suite a_1^2,a_2^2,\dots d’entiers deux-à-deux premiers entre eux avec \sum_{k\geq1} a_k^{-2}<\infty.

Une première étape caractérise le sous-décalage et la mesure empirique pour la fonction \eta définie sur \mathbb N^* par \eta(n)=1 ssi aucun a_k^2 ne divise n. Le décalage engendré est décrit par une condition d’admissibilité simple (hérédité; on peut en déduire son entropie topologique et sa mesure d’entropie maximale). La limite des m^\eta_n existe. C’est m^\eta l’image par une application explicite (mais non continue) de la mesure de Haar sur un groupe compact abélien naturel.

Sous la condition (*) \sum_{k\geq1} a_k^{-1}<\infty, la deuxième étape montre la convergence des mesures m^\mu_n vers l’image du produit m^\eta\otimes(\tfrac12,\tfrac12)^{\mathbb N} sur \{0,1\}^{\mathbb N}\times\{-1,1\}^{\mathbb N} par (x,s)\mapsto (x_ns_n).  La condition n’est pas satisfaite dans le cas classique… mais pas de beaucoup!Cette analyse fait intervenir la disjonction au sens de Furstenberg avec différentes classes de systèmes ergodiques d’entropie nulle.

Read Full Post »

La prépublication est enfin sur arxiv!

Voici le lien.

En comparaison avec ma précédente prépublication sur le sujet (également sur arxiv), on parvient dans ce nouveau travail à analyser les mesures maximisant l’entropie relativement à une période. On développe aussi les lemmes boréliens nécessaires au traitement du cas non nécessairement mélangeant. On obtient ainsi un résultat modulo les mesures d’entropie nulle et non pas modulo ces “m.m.e. relatives”.

Read Full Post »

0. Problème du générateur

L’existence d’une partition génératrice finie ou dénombrable est équivalente à la possibilité de plonger un système dans un décalage sur un alphabet fini ou dénombrable, ie, \mathbb N^{\mathbb Z} et donc conditionne la réductibilité de maints problèmes au cas symbolique. Cette problématique est également fortement liée à l’entropie.

Je répète ici la présentation de Benjamin WEISS, Countable generators in dynamics” (1989) qui a donné une version borélienne (ou si l’on veut mesurable) du théorème de Rokhlin.

1. Théorème de Rokhlin (1963)

Enoncé: Soit (X,\mathcal X,\mu,T) un système dynamique probabiliste inversible défini sur un espace de Rokhlin. Si ce système est ergodique, alors il existe une partition dénombrable \mathcal P dite génératrice unilatérale: \bigvee_{k\leq0} T^{-k}\mathcal P= \mathcal X modulo \mu.

Lemme. Pour toute partition finie \mathcal P et tout mesurable C de mesure non-nulle, il existe une partition dénombrable \mathcal Q de C, telle que \bigvee_{n\leq0} T^{-n}(\mathcal Q\cup\{X\setminus C\})\geq \mathcal P.

Preuve du lemme: On subdivise C selon le temps de premier retour, puis chaque morceau correspondant au temps de retour n selon \bigvee_{k=0}^{n-1} T^{-k}\mathcal P. La partition \mathcal Q ainsi obtenue est mesurable et dénombrable. Par ergodicité, l’orbite de presque tout point x visite C en un temps -n avec n\geq0 minimal. L’élément de \bigvee_{n\leq0} T^{-n}(\mathcal Q\cup\{X\setminus C\}) contenant x est donc contenu dans un élément de \mathcal P. Dans un espace de Rokhlin, ceci permet de conclure.

Preuve du théorème: On peut  supposer (\mu,T) apériodique, le théorème étant sinon trivial. Il existe donc une suite de mesurables disjoints C_0,C_1,C_2,\dots de mesures non-nulles. Dans un espace de Rokhlin, il existe une suite de partitions mesurables finies telles que \bigvee_{n\geq0} \mathcal P_n=\mathcal X modulo \mu. Le lemme fournit pour chaque entier n\geq0, une partition dénombrable \mathcal Q_n de C_n. On pose \mathcal Q:=\bigcup_{n\geq0} \mathcal Q_n\cup\{X\setminus\bigcup_{n\geq0}C_n\}. C’est bien une partition dénombrable vu la disjonction des C_n et \bigvee_{n\in\mathbb Z} T^{-n}\mathcal Q\geq\bigvee_{n\geq0} P_n=\mathcal X modulo \mu.

2. Version borélienne

Contexte: (X,\mathcal X,T) est un automorphisme d’un espace de Borel standard. On le muni de l’idéal errant \mathcal W. Un borélien est dit complètement positif si le complémentaire de son orbite positive \bigcup_{n\geq1} T^nB appartient à \mathcal W. Autrement dit, l’ensemble des points qui ne visite pas B une infinité de fois dans le passé et dans le futur appartient à \mathcal W.

Lemme: Si T est apériodique (sans points périodiques), alors il existe un borélien complètement positif satisfaisant A\cap TA=\emptyset.

Remarque: Si A est complètement positif, alors TA l’est aussi: X\setminus\bigcup_{n\geq1} T^n(TA)=(X\setminus\bigcup_{n\geq1}T^nA) \cup \{x\in A:\forall n\geq2 T^nx\notin A\}, l’union de deux éléments de \mathcal W (utilise le théorème de récurrence de Poincaré).

On itère ce lemme en posant A_0:=A et en considérant le système (A_n,\mathcal X\mid A_n,T_{A_n}), ce qui fournit A_{n+1},TA_{n+1}\subset A_n, donc disjoints de TA_n et de A_0,\dots,A_{n-1}.

Corollaire: il existe une suite de boréliens disjoints C_n,n\geq0, complètement positifs.

Un espace de Borel standard admet une suite de partitions finies dont l’union est génératrice. A partir de là, il suffit de reproduire la preuve du théorème de Rokhlin.

3. Commentaires

En général il n’existe pas de générateur fini – l’existence d’une mesure de probabilité invariante d’entropie infinie suffit à l’interdire. Dans le cadre mesuré, c’est la seule objection. Dans le cadre borélien,

Question (B. Weiss 1989): Un système dynamique borélien standard n’admettant pas de mesure finie invariante possède-t-il toujours un générateur à deux éléments?

 

 

Read Full Post »

Les difféomorphismes d’Anosov f:M\to M admettent des partitions de Markov, i.e., des recouvrements finis \{R_1,\dots,R_N\} de M satisfaisant pour un certain \epsilon>0 et tout i=1,\dots,N:

  • diam(R_i)<\epsilon et [x,y]:=W^s_\epsilon(x)\cap W^u_\epsilon(y) est bien défini R_i\times R_i\to R_i;
  • Pour j\ne i, int(R_i)\cap int(R_j)=\emptyset;
  • R_i=\overline{int(R_i)};
  • f(R_i\cap W^s_\epsilon(x))\subset R_j\cap W^s_\epsilon(f(x)) si x\in int(R_i)\cap f^{-1}(int(R_j)) et de même pour W^u_\epsilon, f^{-1}.

Dans le cas des surfaces, on peut construire des partitions de Markov simplement en considérant les variétés stables et instables issues d’un point fixe ou périodique.  Les bords des partitions ainsi obtenues sont inclus dans une union finie de variétés stables ou instables et sont donc négligeables pour toute mesure invariante apériodique. En dimension supérieure, les bords ne peuvent être de cette forme pour de simples raisons de dimension.

Le bord d’une partition de Markov peut porter une dynamique assez riche comme le montre un exemple de R.W. Williams dans le cas dilatant et la construction plus générale étudiée par J. Ashley, B. Kitchens, M. Stafford dans un article des Trans. AMS de 1992 que m’a signalé Vincent PIT.

1. Exemple de Williams dans le cas de f(x)=2x \mod 1 sur le cercle (exemple 3.5 de l’article cité). On pose A_0:=[3/4,1],\; A_{n+1}:=f^{-1}(A_n)\setminus\bigcup_{k\leq n} A_k et P_i:=\overline{\{E(2x)=E(i/2)\}\cap\bigcup_{n\equiv i\mod 2}A_k}. \mathcal P:=\{P_0,P_1,P_2,P_3\} vérifie: R_i=\overline{int R_i},\; int(R_i)\cap int (R_j)=\emptyset, \; f(int(R_i))\cap R_j\ne\emptyset\implies f(R_i)\supset R_j (partition de Markov au sens des endomorphismes). Mais l’ensemble des points non-errant de (\partial\mathcal R:=\bigcup_i \partial R_i,f) est topologiquement conjugué au décalage défini en interdisant 11 (observons que A_n est l’ensemble des nombres dont le développement binaire fait apparaître 11 pour la première fois à la position n).

2. Construction générale dans le cas d’un automorphisme hyperbolique f:T\to T du tore bidimensionel (lemme 3.9). Soit X\subset T  invariant et conjugué à un  système sofique irréductible quelconque, d’entropie strictement inférieure à celle de f.  Une partition de Markov géométrique fournit  une première extension topologique \gamma:Y\to T, de degré 1 (presque tout point de T a exactement 1 préimage). Les auteurs construisent (théorème 2.10, raffinant le lemme 2.6 – voici un exemple) une deuxième extension topologique \pi:Z\to Y de degré 1 avec Z un autre décalage irréductible de type fini et qui réalise \gamma^{-1}(X) comme son cœur, i.e., l’ensemble des points de Y admettant au moins 2 préimages x^1,x^2 complètement séparées: \forall n\in\mathbb Z\;x^1_n\ne x^2_n.  La partition standard de Z se projette par \gamma\circ\pi en une partition de Markov P de f:T\to T. Les auteurs montrent que l’ensemble non-errant de f|\bigcap_{n\in\mathbb Z}f^{-n}\partial P est bien égal à X. Remarquons que cet ensemble non-errant est égal à l’ensemble des points admettant des itinéraires complétement séparés (théorème 1.5).

Read Full Post »

Renaud Leplaideur a exposé au groupe de travail de théorie ergodique ses tout derniers travaux avec H. Bruin, A.T. Baraviera et A.O. Lopes. Ils ont en particulier construit, pour tout 0<a<1, une application f_a:S^1\to S^1 de classe C^1 présentant une transition de phase et un compact K, invariant, uniquement ergodique et indifférent: (i) f_a'\geq 1; (ii) (f_a')^{-1}(1)=K; (iii) le potentiel - \log f_a' possède plusieurs mesures d’équilibre.

Ceci généralise l’exemple bien connu de Manneville-Pomeau. Plusieurs autres résultats suggèrent des liens entre cette non-unicité et une certaine invariance par renormalisation du potentiel, sans qu’il soit clair qu’il s’agisse là d’un phénomène général ou encore d’un analogue mathématique du lien entre phénomène critique et invariance par renormalisation établi et exploité par les physiciens théoriciens depuis Wilson et les années 1970.

Read Full Post »

It is often interesting to study the properties of objects picked at random in some class. This may shed some light on whether some observed system has is typical in some probabilistic model or may even turn out to be an efficient way of  obtaining an interesting behavior. This idea was put to spectacular use by Erdös in combinatorics (see Random graphs, Bollobas?), and closer to us, by Gromov (and later Yann Ollivier) for finitely presented groups.

In a very recent preprint, K. McGoff has considered random subshift of finite type (see An introduction to symbolic dynamics by Marcus and Lind). A subshift of finite type is a compact set of the form

X:=\{x\in\{1,\dots,N\}^{\mathbb N}: \forall p\in\mathbb Z\; x_px_{p+1}\dots x_{p+L-1}\in\mathcal A\}

where N\in\mathbb N^* and \mathcal A\subset\{1,\dots,N\}^L for some L, the finite sequences being considered up to translation of the indices. The self-map \sigma: (x_p)_{p\in\mathbb Z}\mapsto (x_{p+1})_{p\in\mathbb Z} (called the shift) turns X into a dynamical system.

Note that the following inclusion is usually strict: \mathcal B(X,L):=\{x_p\dots x_{p+L-1}:x\in X,\; p\in\mathbb Z\} \subset \mathcal F.

Given \mathcal F, some of the most natural questions are:

  1. Is X empty?
  2. What is the entropy of X? This quantifies how big X is. It is the positive number h(X):=\lim_{n\to\infty}\frac1n\log \#X(n) where X(n) is the set of all the finite sequences of length $n$ which occurs as a subsequence of any x\in X and \#X(n) is the cardinality of that set.
  3. How many irreducible components does X have? An irreducible component  is the closure of an orbit, i.e., \{\sigma^n(x):n\in\mathbb Z\}, which is not included in a larger one.

Let us stress that these questions are well-known to have an algorithmic answer. If the maximal length of sequences appearing in \mathcal F is L, one defines a N^{L-1}\times N^{L-1}-matrix with 0,1-entries. The largest positive eigenvalue is the exponential of the entropy (or zero if and only if X=\emptyset) and its multiplicity is the number of irreducible components. But of course N^{L-1} is very large if L is large.

K. McGoff considers the following random model with parameter 0\leq \alpha\leq 1 and a subshift of finite type X. Given L a very large integer, \mathcal F\subset\mathcal B(X,L) is defined by declaring that each sequence of length belongs to \mathcal F independently and with probability 1-\alpha. He then considers the limit of the probabilities when L\to\infty. Let us quote his main results in a somewhat weakened form and specialized to X=\{1,\dots,N\}^{\mathbb Z} for simplicity.

There is a dichotomy between small \alpha (empty shift with positive limit probability,  zero entropy with full limit probability, non-trivial distribution of the number of components) and large \alpha (non-empty, entropy close to \log(\alpha\lambda) and a single, aperiodic irreducible component with full limit probability).

The above results for small \alpha are shown for all \alpha<1/N. For large \alpha, the non-emptyness holds for \alpha\geq 1/N, the convergence of the entropy for \alpha>1/N and the irreducibility and aperiodicity for \alpha close enough to 1.

Read Full Post »

Older Posts »