\documentclass[XUPS,XML,SOM,Unicode,francais, NoFloatCountersInSection, NoEqCountersInSection, ThmDefs]{cedram}
\setcounter{tocdepth}{2}
%\XUPScorrections
\def\theequation{$*$}
\graphicspath{{xups94-02_figures}}

\def\0{\bf 0}
\def\1{\bf 1}
\def\2{\bf 2}
\def\aa{\boldsymbol{a}}
\def\suba{\sigma_{\bf 0}}
\def\subb{\sigma_{\bf 1}}
\def\ra{R_{\alpha}}
\let\cal\mathcal
\def\Smaller{\smaller\smaller}

\begin{document}
\frontmatter

\title[Complexité de suites]{Complexité de suites à valeurs dans un ensemble fini: quelques exemples}

\author[\initial{P.} \lastname{Arnoux}]{\firstname{Pierre} \lastname{Arnoux}}

\address{Laboratoire de Mathématiques discrètes, Faculté des Sciences de Luminy,
163 avenue de Luminy, 13288 Marseille Cedex 9}

\email{pierre@pierrearnoux.fr}

\thanks{Journées X-UPS 1994. Aspects des systèmes dynamiques (des équations différentielles aux itérations de fonctions). Prépublication du Centre de mathématique de l'École polytechnique, 1994, et Éditions de l'École polytechnique, 2009}

\maketitle
\vspace*{-\baselineskip}
\tableofcontents
\mainmatter


\section{Qu'est-ce que la complexité d'une suite?}

Nous considérons ici des suites à valeurs dans un ensemble fini~$\cal
A$, appelé alphabet. On en rencontre dans des situations diverses:
bien entendu, dans tout ce qui relève du codage de
l'information (texte, son...), mais aussi en biologie (génome), et
en physique (étude de l'évolution d'un système au cours du temps,
quand on ne peut faire que des mesures discrètes). Une méthode assez
générale pour obtenir de telles suites est de prendre un système
dynamique $T:X\to X$, et une fonction de codage $f:X\to \cal A$ (ou,
ce qui revient au même, une partition finie de $X$ indexée par~$\cal
A$); on considère alors les suites de terme général $f(T^n(x))$,
codage symbolique de l'orbite du point~$x$ sous l'action de $T$. On
peut considérer suivant les cas des suites \hbox{infinies} (indexées par
$\NN$) ou bi-infinies (indexées par $\ZZ$); nous nous restreindrons ici
au cas des suites infinies.

On s'intéresse particulièrement à évaluer le caractère plus ou moins
aléatoire d'une telle suite; si l'on connaît $n$ symboles de la
suite, que peut-on dire des suivants? Une méthode possible consiste à
compter le nombres de combinaisons possibles de~$n$ symboles
consécutifs. C'est ce que l'on appelle la \emph{complexité} de la
suite; donnons d'abord quelques définitions:\enlargethispage{\baselineskip}

On appelle \emph{mot} sur l'alphabet $\cal A$ une suite finie $W=w_1\ldots
w_n$ à valeurs dans~$\cal A$; on notera $|W|=n$ la longueur du mot, et
$|W|_{\aa}$ le nombre d'occurrences de la lettre~$\aa$ dans
$W$. On dit qu'un mot~$W$ est \emph{facteur} de la suite
$u=(u_n)_{n\in\NN}$ s'il existe un entier $k$ tel que $W=u_k\ldots
u_{k+n-1}$.

\begin{enonce*}[remark]{Définition} On appelle \emph{complexité} de la suite $u$ la
fonction $p$ qui, à tout entier $n$, associe le nombre de facteurs de
longueur~$n$ de~$u$.
\end{enonce*}

Il est clair que, si l'alphabet $\cal A$ est de cardinal $k$, $p(n)$
est borné par $k^n$; il est facile de montrer que, puisqu'un mot de
longueur $n+m$ peut se décomposer en deux mots de longueur respective
$n$ et $m$, on a $p(n+m)\le p(n)p(m)$. On en déduit que $\log(p(n))/n$
admet une limite finie quand $n$ tend vers l'infini; c'est ce qu'on
appelle \emph{l'entropie } de la suite. Une suite d'entropie $\log k$
contient tous les mots possibles; une suite d'entropie strictement
positive peut être considérée comme très aléatoire.

Dans cet exposé, nous allons montrer comment, dans certains cas,
on peut calculer explicitement la complexité d'une suite en
considérant un système dynamique. Nous nous intéresserons à des
suites peu aléatoires, d'entropie nulle.

Si la complexité d'une suite est majorée par une exponentielle,
peut-on donner des minorations? On a un lemme évident:

\begin{enonce*}{Lemme} La complexité est une fonction croissante.
\end{enonce*}

En effet, tout facteur de longueur $n$ de $u$ est le début d'au
moins un facteur de longueur $n+1$, et deux facteurs distincts
sont les débuts de deux facteurs distincts, il y a donc au moins
autant de facteurs de longueur $n+1$ que de facteurs de longueur~$n$.

On ne peut pas faire mieux en général: les suites les moins aléatoires
sont les suites périodiques, et pour une telle suite, le nombre de mots
de longueur $n$ est borné par la période de la suite; la complexité
est alors constante à partir d'un certain rang. Plus généralement,
rappelons qu'une suite est dite \emph{ultimement périodique} si elle
est périodique à partir d'un certain rang. On a en fait une
caractérisation complète des suites de complexité bornée:

\begin{enonce*}{Lemme} Les trois propriétés suivantes sont équivalentes:
\begin{enumeratei}
\item\label{enum:i}
la suite $u$ est ultimement périodique;

\item\label{enum:ii}
la complexité est bornée;

\item\label{enum:iii}
il existe un entier $n$ tel que $p(n)=p(n+1)$.
\end{enumeratei}
\end{enonce*}

\begin{proof}
Si la suite est périodique de période $t$ à partir du
rang $n_0$, on a toujours $p(n)\le
n_0+t$, donc \eqref{enum:i} implique \eqref{enum:ii}; il est clair que \eqref{enum:ii} implique
\eqref{enum:iii}, il suffit donc de montrer que \eqref{enum:iii} implique~\eqref{enum:i}.

Mais s'il y a autant de facteurs de longueur $n$ et $n+1$, chaque
facteur de longueur~$n$ est le début d'un et d'un seul facteur
de longueur $n+1$; autrement dit, quand on connaît $n$ lettres, on
connaît la suivante. De plus, comme il n'y a qu'un nombre fini de
facteurs, on retrouve en au plus $p(n)$ fois un facteur déjà vu, et
la suite est alors périodique à partir de l'apparition de ce facteur.
\end{proof}

On en déduit qu'\emph{a contrario},
la complexité d'une suite non ultimement périodique est strictement
croissante; comme $p(1)$ vaut au moins 2, sinon il n'y aurait qu'un
symbole et la suite serait constante, la complexité d'une suite non
ultimement pério\-di\-que vérifie $p(n)\ge n+1$.

\begin{enonce*}[remark]{Définition}
On dit qu'une suite est sturmienne si elle est non
ultimement périodique et de complexité minimale $p(n)=n+1$.
\end{enonce*}

Remarquons que, puisque $p(1)=2$, une suite sturmienne est définie
sur un alphabet à 2 lettres, que l'on peut nommer $\0$ et $\1$. Les
suites sturmiennes sont en quelque sorte les plus ordonnées des
suites non périodiques; elles ont été étudiées par de nombreux
auteurs, nous citerons \cite{HM}, \cite{He}, \cite{CH}.

\section{L'exemple le plus simple: les suites sturmiennes}

Les suites sturmiennes possèdent de nombreuses caractérisations,
combinatoires, dynamiques, arithmétiques, voire géométriques, que
l'on peut résumer dans le théo\-rè\-me suivant:

\begin{enonce*}{Théorème}
Pour une suite non ultimement périodique sur l'alphabet à deux lettres
$\{\bf 0,\bf 1\}$, les propriétés suivantes sont équivalentes:
\begin{enumeratei}
\item\label{th:i}
(complexité) La suite est de complexité minimale: $p(n)=n+1$.

\item\label{th:ii}
(équilibre) Les nombres de $0$ contenus dans deux facteurs de même
longueur diffèrent au plus de $1$: si $U$ et $V$ sont deux facteurs de
$u$ tels que $|U|=|V|$, alors $|U|_{\0}-|V|_{\0}\le 1$.

\item\label{th:iii}
(engendrement par substitutions) Il existe deux suites~$a_n$
et~$b_n$ d'entiers strictement positifs, vérifiant $a_n\ge b_n$, et
une lettre $\aa=\0$ ou $\1$ telles que, pour tout $n$, la suite $u$
débute par le mot
\[
S^{b_1}\subb^{a_1-1}S^{b_2}\suba^{a_2}
S^{b_3}\subb^{a_3}\ldots S^{b_{2n}}\suba^{a_{2n}}(\aa), 
\]
où $S$ est
l'application qui, à un mot, associe ce mot privé de sa première
lettre et $\suba$ (\resp $\subb$) est l'application (substitution, ou
encore morphisme du monoïde libre) qui à un mot associe le mot obtenu
en remplaçant $\0$ par $\0$ et $\1$ par $\1\0$ (\resp $\0$ par $\0\1$
et $\1$ par $\1$)

\item\label{th:iv}
(arithmétique) Il existe deux nombres $\alpha, \beta$ dans
l'intervalle $[0,1[$, avec $\alpha$ irrationnel, tels que la suite
$u_n$ soit définie par $u_n=[(n+1)\alpha+\beta]-[n\alpha+\beta]$ ou
$u_n=\lceil(n+1)\alpha+\beta\rceil-\lceil n\alpha+\beta\rceil$, où~$[x]$ désigne le plus grand entier inférieur ou égal à $x$ (partie
entière de~$x$), et $\lceil x\rceil$ le plus petit entier supérieur
ou égal à $x$.

\item\label{th:v}
(rotation) Il existe deux réels $\alpha$ et $\beta$ dans
$[0,1[$, avec $\alpha$ irrationnel, tels que la suite $u$ soit donnée
par le codage de l'orbite de $\beta$ pour le système dynamique
$$R_{\alpha}: [0,1[{}\to [0,1[\quad x\mto x+\alpha \mod 1$$
par rapport à la partition $[0,1-\alpha[, [1-\alpha 1[$ (ou par le
codage obtenu en prenant les intervalles ouverts à gauche et fermés à
droite).
\end{enumeratei}
\end{enonce*}

\subsubsection*{Remarque}
Les propriétés \eqref{th:iv} et \eqref{th:v} sont susceptibles d'une
interprétation simple: si l'on trace dans le plan, quadrillé par les
horizontales et les verticales à coordonnées entières, la droite
$y=\alpha x+\beta$, et que l'on compte le nombre d'horizontales que
cette droite coupe entre deux verticales successives (ce nombre vaut $0$
ou $1$ si $\alpha<1$), on obtient la suite
$u$ (\cf figure \ref{arnouxfig1}); sous cette forme, le sens de la propriété
d'équilibre est assez clair.

\begin{figure}[htb]
\setlength{\unitlength}{.75cm}
\begin{center}
\begin{picture}(11,7)
\put(0,.66){\line(2,1){11}}
\put(1,0){\line(0,1){7}}
\put(2,0){\line(0,1){7}}
\put(3,0){\line(0,1){7}}
\put(4,0){\line(0,1){7}}
\put(5,0){\line(0,1){7}}
\put(6,0){\line(0,1){7}}
\put(7,0){\line(0,1){7}}
\put(8,0){\line(0,1){7}}
\put(9,0){\line(0,1){7}}
\put(10,0){\line(0,1){7}}
\put(0,1){\line(1,0){11}}
\put(0,2){\line(1,0){11}}
\put(0,3){\line(1,0){11}}
\put(0,4){\line(1,0){11}}
\put(0,5){\line(1,0){11}}
\put(0,6){\line(1,0){11}}
\put(.3,.2){1}
\put(1.3,.2){0}
\put(2.3,.2){1}
\put(3.3,.2){0}
\put(4.3,.2){1}
\put(5.3,.2){0}
\end{picture}
\end{center}
\caption{\label{arnouxfig1}}
\end{figure}

Il peut être plus naturel de regarder le codage obtenu
en notant~$\HH$ chaque fois que la droite considérée coupe une
horizontale, et $\VV$ à chaque fois qu'elle coupe une verticale. Ce
codage s'obtient à partir du précédent en remplaçant $\0$ par $\VV$
et $\1$ par $\HH\VV$; on peut montrer que la suite obtenue est encore
sturmienne, comme image d'une suite sturmienne par une \og bonne\fg
substitution.

On peut aussi montrer que cette suite est directement associée à la
rotation d'angle $\alpha/(1+\alpha)$; le raisonnement qui suit peut
paraître peu naturel, mais il fait jouer le même rôle aux deux
coordonnées et il est donc plus facile à généraliser, comme nous le
verrons plus loin.

Notons $L_n$ la ligne brisée (\og escalier\fg) qui joint les points de
la forme $(k,n-k)$ et les points de la forme $(k,n+1-k)$, pour
$k\in\ZZ$, par des segments horizontaux et verticaux; une droite de
pente $\alpha$ coupe une fois et une seule chaque ligne brisée $L_n$,
et le codage est déterminé par le fait qu'elle coupe $L_n$ en un
segment horizontal ou vertical. Notons $D$ la droite $x+y=0$, et
cherchons le codage associé à la droite issue d'un point $p$ de $D$;
pour trouver le $n$-ième terme de la suite, on projette
$L_n$ sur $D$ parallèlement à la direction $(1,\alpha)$, ce qui donne
un pavage périodique de $D$ en deux types d'intervalles, de longueurs
respectives $1/(1+\alpha)$ et $\alpha/(1+\alpha)$ (si l'on prend le
vecteur $(-1,1)$ comme base); le type d'intervalle auquel appartient~$p$ donne le terme cherché de la suite. Si l'on décale le point $p$
de $(-1,1)$, on retrouve le même codage; on peut donc quotienter $D$
par un groupe de translations pour se ramener à un cercle partitionné
en deux intervalles, et le dessin montre que la partition obtenue
à partir de $L_{n+1}$ se déduit de la partition obtenue de $L_n$
par une rotation de $\alpha/(1+\alpha)$, d'où le résultat cherché
(voir la figure \ref{arnouxfig2}).

\begin{figure}[htb]
\setlength{\unitlength}{.5cm}
\begin{center}\Smaller
\begin{picture}(15,7)
\includegraphics[height=7\unitlength]{arnouxfig2}\put(.2,0){$L_3$}
\put(-1.7,0){$L_2$}
\put(-3.6,0){$L_1$}
\put(-5.4,0){$L_0$}
\put(-8.1,.2){$D$}
\put(-12.8,4){$\displaystyle\frac{\alpha}{1+\alpha}$}
\put(-11.6,2.8){$\displaystyle\frac{1}{1+\alpha}$}
\end{picture}
\end{center}
\caption{\label{arnouxfig2}}
\end{figure}

Une autre façon d'obtenir cette suite est de jouer au billard sur le
carré, en partant dans la direction $(1,\alpha)$ et en notant $\HH$
(\resp $\VV$) chaque fois que l'on touche un côté horizontal (\resp vertical). \qed

\begin{proof}[Preuve du théorème]
La preuve complète est assez longue; nous ne pouvons ici donner que des
indications. On trouvera une preuve complète, sous forme de
problème, dans l'épreuve optionnelle d'informatique de l'agrégation
de mathéma\-ti\-ques 1994.

Les propriétés \eqref{th:i} et \eqref{th:ii} sont combinatoires, et la
preuve de leur équivalence est aussi purement combinatoire (et non
triviale!).

Les propriétés \eqref{th:iv} et \eqref{th:v} sont évidemment équivalentes: \eqref{th:iv} n'est
rien d'autre que l'écriture explicite du codage donné par \eqref{th:v}. On
peut remarquer en particulier qu'utiliser la fonction $[x]$ (\resp $\lceil x\rceil$) pour~\eqref{th:iv} revient à prendre les intervalles fermés à gauche (\resp à
droite)
dans \eqref{th:v} en fait, les suites obtenues par l'un ou l'autre codage
sont les mêmes sauf pour un nombre dénombrables de valeurs de $\beta$
(de la forme $p-n\alpha$) où elles diffèrent en deux positions.

Il est facile de montrer que toute suite obtenue par codage
d'une rotation est de complexité minimale, et nous le prouverons à la
fin de cette section. C'est la réciproque qui est difficile, et
c'est ici qu'intervient la propriété \eqref{th:iii}, qui est la plus compliquée
à interpréter.

Ce qui est simple à montrer, c'est que toute suite sturmienne peut
se réécrire par $\suba$ ou $\subb$; en effet, puisque $p(2)=3$, il
n'y a que trois facteurs de longueur 2; or, puisque la suite n'est
pas périodique, elle n'est pas constante, donc les deux lettres $\0$
et $\1$ apparaissent une infinité de fois, donc les deux mots $\0\1$
et $\1\0$ aussi; donc l'un des deux facteurs $\0\0$ et $\1\1$
n'apparaît pas. Supposons que ce soit $\1\1$; alors, tout $\1$ est
suivi par $\0$, et l'on peut recoder la suite en utilisant $\0$
et $\1\0$; autrement dit, il existe une unique suite $v$ telle que
$u=\suba(v)$. Il~suffirait alors que $v$ soit sturmienne pour
pouvoir itérer, et obtenir~$u$ comme issue d'une suite infinie de
recodage.

Il y a malheureusement un problème technique: en général, ce n'est
pas la suite~$v$ qui est sturmienne, mais la suite $Sv$, c'est-à-dire~$v$ privée de son premier terme; en effet, si $u$ commence par un~$\0$, on ne peut savoir directement si celui ci doit être considéré,
pour le recodage, comme le mot $\0$ ou comme la deuxième lettre du
mot $\1\0$. On peut cependant montrer que l'on peut toujours écrire
$u$ sous la forme $\suba(v)$ ou $S\suba(v)$, où $v$ est une suite
sturmienne; c'est ici qu'intervient l'application $S$ de décalage.\enlargethispage{\baselineskip}

Puisque toute suite de codage pour une rotation est sturmienne, elle
peut se recoder de cette façon, et on peut alors interpréter la suite
$(a_n)$: ce n'est autre que le développement en fraction continue du
nombre $\alpha$; la suite $b_n$ est associée, de façon plus complexe,
au nombre~$\beta$. Il est alors assez simple de prouver que toute
suite sturmienne est une suite de rotation, puisqu'il suffit alors de
prendre les suites $(a_n)$ et $(b_n)$ données par la propriété \eqref{th:iii},
de construire les réels~$\alpha$ et~$\beta$, et de montrer que le
codage associé donne bien la suite cherchée. La propriété \eqref{th:iii} donne
en fait une interprétation combinatoire du développement en fraction
continue du nombre~$\alpha$; dans la cas où ce développement est
périodique, la suite peut prendre une forme très simple.

En particulier, si l'on pose $a_n=1$, $b_n=0$, $\aa=\0$ ou $\1$, on
obtient les deux codages possibles pour l'orbite, par la
rotation d'angle $(\sqrt 5-1)/2$, du point $(3-\sqrt 5)/2$. On les
trouve donc en partant d'une des deux lettres, en remplaçant $\0$
(\resp $\1$) par $\0\1$ (\resp $\1\0\1$) et en itérant. On peut
montrer que l'orbite de $(\sqrt 5-1)/2$ pour la même rotation est,
elle, donnée en itérant la substitution dite de \emph{Fibonacci},
$\1\mto \1\0$, $\0\mto \1$; le mot infini obtenu, dit \emph{mot
de Fibonacci}, est la suite sturmienne la plus facile à exhiber.
\end{proof}

Il reste à montrer que la suite donnée par le codage de l'orbite
d'une rotation est sturmienne; nous allons en donner deux preuves. Pour
montrer que la suite
\hbox{$[(n+1)\alpha+\beta]-[n\alpha+\beta]$} est sturmienne, on peut utiliser
la propriété d'équilibre: le nombre de $\1$ compris entre $u_{k}$ et
$u_{k+n-1}$ est égal par construction à
\hbox{$[(k+n)\alpha+\beta]-[k\alpha+\beta]$}, et il est clair que, pour $n$
fixé, ce nombre ne peut prendre au plus que deux valeurs distinctes
suivant $n$. On peut aussi étudier directement la complexité, et la
preuve qui suit est plus susceptible de généralisation.

Fixons quelques notations. Pour $\alpha$ irrationnel fixé, on note
$R_{\alpha}$ la rotation d'angle~$\alpha$ sur le cercle identifié
à l'intervalle $[0,1[$; on note ${\cal P}$ la partition en les deux
intervalles $I_{\0}=[0,1-\alpha[$ et $I_{\1}=[1-\alpha,1[$.
L'application $f$ de codage est donnée par $f(x)=\0$ (\resp $\1$) si
$x\in I_{\0}$ (\resp $I_{\1}$), et on cherche la complexité de la
suite $u(\beta)=(f(R_{\alpha}^n\beta))_{n\in\NN}$.

Mais un facteur de
$u(\beta)$ qui apparaît en position $k$ est un facteur initial de
$u(b+k\alpha)$: plutôt que de chercher tous les facteurs de $\beta$
de longueur $n$, avec $\beta$ fixé, on peut chercher le facteur
initial de toutes les suites $u(x)$.

La première lettre de $u(x)$ est déterminée par la position de $x$
par rapport à le partition ${\cal P}$; la deuxième lettre est
déterminée par la position de $\ra x$ par rapport à ${\cal P}$, ou
encore par la position de~$x$ par rapport à $\ra^{-1}{\cal P}$. En
effet on a $u_1(x)=\nobreak\0$ si et seulement si $\ra x\in I_{\0}$, ou
$x\in \ra^{-1}I_{\0}$. Pour connaître le facteur initial de $u(x)$,
il~faut placer $x$ par rapport aux partition ${\cal P}, \ra^{-1} {\cal
P},\ldots, \ra^{-n+1} {\cal P}$, et il y a donc autant de facteurs
initiaux possibles que d'ensembles dans l'intersection ${\cal P}\wedge
\ra^{-1} {\cal P}\wedge\cdots\wedge \ra^{-n+1} {\cal P}$ de ces
partitions.

\begin{figure}[htb]
\setlength{\unitlength}{1cm}
\begin{center}
\begin{picture}(5,5)
\includegraphics[height=5\unitlength]{arnouxfig3}
\put(.1,2){0}
\put(-.4,.5){$1-\alpha$}
\put(-2,-.3){$1-2\alpha$}
\put(-4.5,-.3){$1-3\alpha$}
\put(-.1,1.2){$I_1$}
\put(-2,1.4){$R_{\alpha}^{-1}(I_1)$}
\put(-3.5,.9){$R_{\alpha}^{-2}(I_1)$}
\put(-1.4,1.2){\vector(0,-1){.7}}
\put(-2.8,.7){\vector(0,-1){.5}}
\end{picture}
\end{center}
\caption{\label{arnouxfig3}}
\end{figure}

Un calcul immédiat montre que la partition $\ra^{-k}{\cal P}$ est
constituée des deux intervalles $[-k\alpha, 1-(k+1)\alpha[$ et
$[1-(k+1)\alpha[,1-k\alpha[$ (attention, tous ces calculs se font
modulo 1! voir figure \ref{arnouxfig3}); l'intersection des $n$ premiers itérés
inverses de la partition ${\cal P}$ est donc donnée par $n+1$ points,
et la partition obtenue a donc $n+1$ éléments. On a bien prouvé qu'il
y a $n+1$ facteurs initiaux de longueur $n$ possibles, donc au plus
$n+1$ facteurs possibles pour $u(\beta)$. Compte tenu du fait
que la suite $u(\beta)$ n'est pas ultimement périodique, elle est de
complexité $n+1$. On pourrait, en utilisant le fait que
l'orbite d'un point pour une rotation irrationnelle sur le cercle est
dense, montrer directement que tous les facteurs initiaux possibles
sont des facteurs de $u(\beta)$.

\section{Suites engendrées par des systèmes dynamiques}

On peut généraliser la démonstration précédente. Considérons,
comme dans l'introduction, un système dynamique $T:X\to X$, une
partition ${\cal P}$ indexée par~$\cal A$, et la fonction $f$ de codage
associée. Notons $u(x)= (f(T^nx))_{n\in\NN}$ la suite donnée par le
codage de l'orbite de $x$; comme ci-dessus, il est clair qu'un
facteur de $u(x)$ qui apparaît en position $k$ est facteur initial
de $u(T^k(x)$.

Par ailleurs, la lettre d'ordre $k$ de $u(x)$ donne la position de
$x$ par rapport à la partition $T^{-k}{\cal P}$, et comme ci-dessus, il
y a donc autant de facteurs initiaux de longueur $n$ que d'atomes
dans l'intersection $ \cP\wedge T^{-1}\cP\wedge\cdots\wedge
T^{-n+1}\cP$; on a donc:

\begin{enonce*}{Proposition} Soit $u(x)$ la suite donnée par le codage de
l'orbite de~$x$ pour le système $T:X\to X$ par rapport à la partition
${\cal P}$; la complexité d'ordre $n$ de $u$ est majorée par le nombre
d'atomes de la partition $ \cP\wedge T^{-1}\cP\wedge\cdots\wedge
T^{-n+1}\cP$.
\end{enonce*}

Il est en général impossible d'aller plus loin, pour deux raisons:
d'une part, l'orbite de $x$ peut éviter de larges régions de $X$
(par exemple, si l'orbite de $x$ est périodique), et les mots
initiaux correspondants n'apparaîtront pas comme facteurs de $u(x)$;
d'autre part, la région associée à un mot initial peut être très
petite, voire réduite à un nombre fini de points, et dans ce cas le
mot correspondant n'apparaîtra pas dans la plupart des orbites.

Dans la cas d'un système dynamique topologique, on peut donner des
conditions qui évitent ces phénomènes, et l'on a:

\begin{enonce*}{Proposition} Soit $X$ un espace métrique compact, et $T$
un homéo\-mor\-phisme de $X$. Soit ${\cal P}=\{P_{\aa},\,\aa\in \cal A\}$ une
partition de X qui vérifie la condition suivante:

\refstepcounter{equation}\label{eq:*}\noindent \eqref{eq:*} Pour toute suite finie $\aa_0,\aa_1,\ldots,\aa_{n-1}$, l'ensemble
$P_{\aa_0}\cap T^{-1}P_{\aa_1}\cap \cdots\cap T^{-n+1}P_{\aa_{n-1}}$ est
vide ou d'intérieur non vide.

Alors, si $x$ est un point d'orbite dense pour $T$, la complexité de
la suite $u(x)$ est égale au nombre d'atomes des partitions $ \cP\wedge
T^{-1}\cP\wedge\cdots\wedge T^{-n+1}\cP$
\end{enonce*}

\begin{proof}
En effet, tout mot initial
correspond à un ensemble qui contient un ouvert; par densité de
l'orbite de $x$, ce mot initial est un facteur de $u(x)$.
\end{proof}

Il y a un cas où l'on vérifie facilement la condition sur $x$: on dit
qu'un système dynamique topologique est \emph{minimal} s'il n'admet
pas de sous-ensemble fermé invariant, ou, de manière équivalente, si
toute orbite est dense; dans ce cas, on a le théorème suivant:

\begin{enonce*}{Théorème} Soit $T: X\to X$ un système dynamique minimal, et
soit~${\cal P}$ une partition de $X$ vérifiant la condition \eqref{eq:*} de la
proposition précédente; alors, pour tout point $x$, la complexité de
la suite $u(x)$ est égale au nombre d'atomes des partitions $ \cP\wedge
T^{-1}\cP\wedge\cdots\wedge T^{-n+1}\cP$; en particulier, toutes les
suites de codages ont la même complexité (et les mêmes
facteurs).
\end{enonce*}

La suite de l'exposé est consacrée à quelques applications de ce
lemme. On va, pour quelques types de suites, exhiber un système
dynamique associé, montrer qu'il est minimal, et calculer, par des
méthodes géométriques, le nombre d'atomes de la partition associée.

\section{Un exemple: les différences secondes de la suite \texorpdfstring{$[n^2\alpha]$}{na}}

On a vu qu'une suite sturmienne peut être obtenue comme suite des
différences de termes consécutifs de la suite à valeurs entières
$[n\alpha+\beta]$. On peut essayer de généraliser en considérant la
suite $w$ définie par $w_n= [n^2\alpha]$, avec $\alpha$ irrationnel.
Pour obtenir une suite à valeurs dans un alphabet fini, il faut cette
fois prendre la suite~$u$ des différences secondes, donnée par
$u_n=w_{n+2}-2w_{n+1}+w_n$.

Cette suite n'est bien sûr plus associée à une rotation, mais on peut
aussi l'obtenir comme suite de codage d'un système dynamique.
Plus précisément, nous allons
donner une transformation $T$ du tore~$\TT^2$ et une fonction $f$ sur
$\TT^2$, ne prenant qu'un nombre fini de valeurs, et telles que l'on
ait $u_n=f(T^n(0,0))$.

Il est facile de trouver $f$ et $T$ en écrivant $n^2\alpha$ comme une
suite récurrente; en effet, si l'on considère l'application affine $A$
définie par $A(x,y)=(x+y+\alpha,y+2\alpha)$, on vérifie immédiatement
que $A^n(0,0)=(x_n,y_n)=(n^2\alpha,n\alpha)$. On peut alors écrire
$u_n$ en fonction de $x_n$ et $y_n$, puisqu'on a par définition:
\begin{align*}
u_n&=w_{n+2}-2w_{n+1}+w_n\\
&=[x_{n+2}]-2[x_{n+1}]+[x_n]\\
&=[x_n+2y_n+4\alpha]-2[x_n+y_n+\alpha]+[x_n]
\end{align*}

On peut donc écrire $u_n=f(x_n,y_n)$, avec
\[
f(x,y)=[x+2y+4\alpha]-2[x+y+\alpha]+[x];
\]
on vérifie immédiatement
que $f$ est $\ZZ^2$-périodique, donc peut être considéré comme une
application définie sur le tore $\TT^2=\RR^2/\ZZ^2$, et~que de même $A$,
étant associée à une matrice de
$SL(2,\ZZ)$, passe au quotient en une transformation affine $T$ de
$\TT^2$.

On sait que $T$, qui est ce qu'on appelle un produit
croisé au-dessus d'une rotation, est minimal dès que $\alpha$ est
irrationnel; cela découle de travaux de Furstenberg. En fait, on ne
montre pas que toute orbite est dense, mais une propriété bien plus
forte: toute orbite est équirépartie sur le tore
$\TT^2$ (cf \cite{F}, ou \cite{CFS}, p.~100-104).

On est donc en position d'appliquer le théorème précédent; il reste à
montrer que ${\cal P}$ satisfait la propriété \eqref{eq:*}, et à calculer le
nombre d'atomes.

Mais d'après l'écriture de $f$, les intérieurs des atomes de la
partition~${\cal P}$ sont les cellules de la décomposition cellulaire de
$\TT^2$ engendrée par les trois cercles $x=0$,
$x+y+\alpha=0$ et $x+2y+4\alpha=0$ (\cf figure~\ref{arnouxfig4}); un calcul simple
montre que la partition $T^{-n}{\cal P}$ est engendrée de même par les
cercles
$H_k=T^{-k}H_0$ d'équation $x+ky+k^2\alpha=0$, pour $n\le k\le n+2$.

\begin{figure}[htb]
\setlength{\unitlength}{.6cm}
\begin{center}\Smaller
\begin{picture}(7,7)
\includegraphics[height=7\unitlength]{arnouxfig4}
\put(-1,0){$x+y+\alpha=0$}
\put(0,1){$x+2y+4\alpha=0$}
\put(0,2.9){$x+2y+4\alpha=1$}
\put(0,4.7){$x+2y+4\alpha=2$}
\put(-1.6,7){$x=1$}
\put(-4.2,7){$x=0$}
\end{picture}
\end{center}
\caption{: Les $4$ atomes de $\cP$\label{arnouxfig4}}
\end{figure}

Ces cellules sont des polygones avec un nombre fini de côté; pour que
la condition \eqref{eq:*} ne soit pas satisfaite, il faudrait qu'il y ait une
coïncidence de sommets entre certaines de ces cellules, et qu'au
moins trois des cercles $H_K$ aient une intersection non vide, ce qui est
impossible par irrationalité de $\alpha$.

On peut alors calculer effectivement la complexité; nous avons une
décomposition cellulaire du tore, donnée par un nombre fini de
cercles, dont nous voulons connaître le nombre $F_n$ de faces.
Puisque toute arête a deux sommets, et que tout sommet, appartenant
à deux cercles, délimite quatre arêtes, les nombres $S_n$ de sommets et
$A_n$ d'arêtes vérifient $A_n=2 S_n$. Compte tenu de la relation
d'Euler sur le tore, $S-A+F=0$, on en déduit qu'il y a autant de
faces que de sommets. On se
ramène donc à calculer le nombre de points d'intersections de $H_j$ et
$H_k$, ou encore, en faisant agir $T^j$, de $H_0$ et $H_{k-j}$, qui
vaut $|k-j|$. En faisant la somme sur tous les couples d'hyperplans,
on obtient:
$$p(n)=\sum_{0\le j<k\le n+1} (k-j)=\frac {(n+1)(n+2)(n+3)}{6}.$$

D'où le résultat:

\begin{enonce*}{Théorème} la complexité de la suite $u$ des différences
secondes de $[n^2\alpha]$ est donnée par:
$$p(n)=\frac{(n+1)(n+2)(n+3)}{6}$$
\end{enonce*}

En particulier, comme pour les suites sturmiennes, la complexité ne
dépend pas de la valeur de
$\alpha$.

\subsubsection*{Remarque}
En toute rigueur, nous avons compté, non pas le nombre
d'ato\-mes de l'intersection $ \cP\wedge T^{-1}\cP\wedge\cdots\wedge
T^{-n+1}\cP$, mais le nombre de composantes connexes de ces atomes; il
faudrait donc, ce qui peut être fait moyennant un peu de travail
supplémentaire, montrer que ces atomes sont connexes; voir \cite{AM} pour
plus de détails.

Ces arguments se généralisent à des suites obtenues à partir de
polynômes de degré quelconque; rappelons que, si $w$ est une suite à
valeurs réelles, la suite $v=\Delta w$ des différences est définie
par: $v_n=w_{n+1}-w_n$. Le résultat énoncé ci-dessus est un cas
particulier du théorème suivant:

\begin{enonce*}{Théorème} Soit $Q$ un polynôme de degré $d$ à coefficients
réels dont le coef\-fi\-cient dominant est irrationnel; la suite
$\left(\Delta^d([Q(n)])\right)_{n\in\NN}$ ne prend qu'un nombre fini de
valeurs, et sa complexité, qui ne dépend que de $d$, est donnée par la
formule:
$$p(n)=\frac 1{V(0,1,\ldots,d-1)}\sum_{0\le k_1<k_2<\cdots<k_d\le
n+d-1}V(k_d,\ldots,k_1)$$ où
$V(k_d,\ldots,k_1)=\prod_{1\le i<j\le d}(k_j-k_i)$ est le déterminant
de Vandermonde associé à
$(k_d,\ldots,k_1)$.
\end{enonce*}

Il est remarquable que la complexité trouvée ne dépende que du degré
du poly\-nô\-me.

\section{Un autre exemple: les suites de billard cubique}

Au lieu de généraliser la définition arithmétique des suites
sturmiennes, on peut regarder la définition géométrique: billard
carré, ou droite dans le plan; nous considérerons donc le billard
cubique, c'est-à-dire le système formé par un point mobile dans un
cube, sans forces extérieures, avec réflexions élastiques sur les
parois.

On code chacune des trajectoires par la suite des faces du cube
qu'elle rencontre (on note $\0$, $\1$ et $\2$ les trois types de faces,
on ne fait pas de différence entre les faces parallèles). A toute
trajectoire est ainsi associée un mot infini sur l'alphabet
$\{\0,\1,\2\}$. On a le résultat suivant:

\begin{enonce*}{Théorème} La complexité d'une trajectoire de pente
$(\alpha,\beta,\gamma)$, où $\alpha,\beta$ et $\gamma$ sont
rationnellement indépendants, est égale à $n^2+n+1$.
\end{enonce*}

On trouvera une démonstration détaillée dans \cite{AMST}; nous donnons
ci-dessous les grandes lignes de la preuve. On supposera, pour
simplifier les calculs, que
$\alpha,\beta,\gamma$ sont trois réels rationnellement indépendants
dans leur ensemble qui satisfont: \hbox{$\alpha+\beta+\gamma=1$}.\enlargethispage{1.5\baselineskip}

La première étape est de remarquer que, de façon analogue aux suites
sturmien\-nes, il est équivalent d'étudier le billard cubique ou
d'étudier une droite de pente irrationnelle dans $\RR^3$ et ses
intersections avec les plans $x=n$, $y=n$, $z=n$ pour tout entier $n$.

On procède alors de façon analogue à l'étude faite pour la droite de
pente irrationnelle dans le plan: Si l'on appelle hauteur du point
$(a,b,c)$ le nombre $a+b+c$, on appelle $\Sigma_n$ la \og surface plissée\fg
qui joint les sommets de hauteur $n,n+1,n+2$ (voir figure 5). La
droite considérée coupe chaque surface plissée une fois et une seule,
dans un de ses trois types de faces. Si l'on projette la surface
plissée sur le plan diagonal $x+y+z=0$, on obtient un pavage
périodique de ce plan; un calcul simple montre que l'on passe du
pavage projeté de $\Sigma_n$ au pavage projeté de $\Sigma_{n+1}$ par une
translation de vecteur $(1-\alpha,-\beta,-\gamma)$, projection sur le
plan diagonal du vecteur $(1,0,0)$ (on pourrait projeter un autre des
trois vecteurs de base, car les différences entre ces trois
projections appartiennent au groupe de translation du pavage); en
quotientant par le groupe du pavage, on se ramène donc à étudier une
translation du tore
$\TT^2$, codée par rapport à une partition en trois quadrilatères. Il
est bien connu (théorème de Kronecker) qu'une translation
irrationnelle du tore est minimale.

\smallskip
\begin{figure}[htb]
\setlength{\unitlength}{.8cm}\centerline{\includegraphics[height=6\unitlength]{arnouxfig5}}
\caption{}
\end{figure}

Il faut alors, comme précédemment, montrer que la partition considérée
satisfait à la condition \eqref{eq:*}, ce qui vient de l'hypothèse
d'irrationalité, puis montrer que les atomes de l'intersection des
partitions itérées sont connexes, et on se ramène à un problème de
comptage.

La partition intersectée d'ordre $n$ vient d'une triangulation du tore
avec $S_n$ sommets, $A_n$ arêtes et $F_n$ faces, qui satisfait
la formule d'Euler $S_n-A_n+F_n=0$. La partition d'ordre 1, qui est
la projection d'un cube en perspective, a 3 sommets, 6 arêtes et 3
faces, qui correspondent aux trois lettres du codage. On passe de la
partition d'ordre~$n$ à la partition d'ordre $n+1$ en rajoutant 3
segments et un point (projection d'un cube de hauteur plus grande que
les précédents); mais ces trois segments recoupent les arêtes déjà
existantes. On montre que les segments ajoutés à l'étape $n$
recoupent les segments ajoutés à l'étape~$i$ en 2 points si $i<n-1$,
et en 0 points si $i=n-1$ (plus exactement, dans ce cas ils recoupent
ces segments en leur extrémité, ce qui ne rajoute pas de nouveau
sommet). On a donc $S_{n+1}=S_n+2n+1$, et donc $S_n=n^2+2$. On montre
de même que $A_{n+1}=A_n+4n+3$, donc $A_n=2n^2+n+3$, d'où l'on déduit
le résultat cherché.

\section{Suites de billard: la conjecture de Tamura}

Une fois que l'on a réussi à calculer la complexité du billard carré
et du billard cubique, il est bien sûr tentant, comme on l'a fait
pour les parties entières de polynômes, de généraliser en dimension
quelconque.

\begin{enonce*}[remark]{Définition} Nous noterons $p(n,s)$ le nombre de facteurs de longueur~$n$ dans une suite engendrée par le billard dans le cube de dimension $s+1$
\end{enonce*}

Le cas $s=1$ correspond au billard carré, c'est-à-dire
aux suites sturmiennes, $s=2$ est le billard cubique de la section
précédente,
$s=0$ est un cas dégénéré, billard sur un segment, correspondant à
une suite constante de complexité 1.

Il est à noter que nous ne savons pas si $P(n,s)$ est bien défini
dans le cas général: la définition que nous avons donnée suppose
implicitement que la complexité d'une suite de billard cubique
irrationnel ne dépend que de la dimension, et pas de la direction
initiale, ce qui n'a pas de raison d'être vrai \emph{a priori}.

Cependant, il est facile de vérifier que $p(n,s)$ est bien défini
pour $n<3$, et que l'on a $p(0,s)=1$ (cas du mot vide), $p(1,s)=s+1$
(nombre de lettres, c'est-à-dire d'hyperfaces du cube de dimension
$s+1$), et $p(2,s)=s^2+s+1$ (car tous les mots~$\bf i j$,
avec ${\bf i}\ne{\bf j}$, sont possibles, mais un seul des mots
$\bf i i$ est possible. D'autre part, J.I.~Tamura a calculé
numériquement la complexité pour un certain nombre d'exemples de
dimension supérieure à 3.

Si l'on résume les résultats connus, on
trouve le tableau de la page suivante, où les chiffres en
italique résultent de simulations numériques
$$\arraycolsep4pt
\begin{array}{ccccccccc}
n\backslash
s &0 &1 &2 &3 &4 &5 &\cdots&s\\
0 &1 &1 &1 &1 &1 &1 &&1\\
1 &1 &2 &3 &4 &5 &6 &&s+1\\
2 &1 &3 &7 &13&21&31&&s^2+s+1\\
3 &1 &4 &13&\emph{34}&\emph{73}&\emph{136}& \\
4 &1 &5 &21&\emph{73}&\emph{209}&\\
5 &1 &6 &31&\emph{136}&\\
\cdots &\\
n &1 &n+1&n^2+n+1&
\end{array}
$$

Au vu de ces résultats, J.I. Tamura a conjecturé que la fonction
$p(n,s)$ est définie et symétrique: $p(n,s)=p(s,n)$.

On peut pousser la conjecture plus loin: il est clair que l'on a
$p(n,s)<(s+1)^n$, car c'est le nombre de mots de longueur $n$ que
l'on peut former avec $s+1$ lettres; au vu des résultats obtenus, il
est donc naturel de supposer que, pour $n$ fixé, $p(n,s)$ est un
polynôme unitaire de degré $n$ en $s$.

Mais on peut alors calculer de proche en proche chaque ligne,
puisque, par symétrie, les $n$ premières lignes déterminent les $n$
premières colonnes, et que l'on connaît donc $n$ valeurs du polynôme
unitaire de degré $n+1$ associé à la ligne suivante, ce qui le
détermine complètement; le calcul peut être fait explicitement,et
conduit à la conjecture suivante:

\begin{enonce*}{Conjecture} La fonction $p(n,s)$ est donnée par:
$$p(n,s)=\sum_{i=0}^{\inf (n,s)}\frac {n!s!}{(n-i)!i!(s-i)!}$$
\end{enonce*}

Cette conjecture est en parfait accord avec les simulations
numériques, et a été vérifiée dans un grand nombre de cas
particuliers; elle n'est cependant pas démontrée dès que $n$ et $s$
sont plus grands que 2: les calculs de comptage qui généralisent ceux
de la section précédente deviennent alors inextricable. On n'a par
ailleurs à l'heure actuelle aucune preuve que cette fonction soit
définie dans le cas général; en fait, même dans les cas $n=1$ ou
$n=2$, la démonstration la plus simple consiste à calculer
explicitement $p(n,s)$ et à montrer que le résultat ne dépend pas de
la direction. Il existe dans ce cas des preuves directes, sans calculer
la valeur mais en montrant directement que le nombre de mots ne
varie pas quand on change la direction, mais elles sont plus
compliquées.

On n'a également aucune idée, même heuristique, de la raison pour
laquelle cette fonction serait symétrique en $n$ et $s$.

\section{Quelques autres résultats}

Citons pour terminer quelques autres cas où l'on sait calculer
explicitement la complexité:

Une autre généralisation du billard carré est le billard dans un
polygone rationnel (c'est-à-dire dont les angles sont des multiples
rationnels de $\pi $); dans ce cas, P.~Hubert a montré (\cf \cite{Hu}) que,
si, dans un polygone à $q$ côtés, les angles sont de la forme
$k_1\pi /r, k_2\pi /r, \ldots,k_q\pi /r$, où les entiers $k_1,k_2,\ldots,k_q,r$
sont premiers entre eux dans leur ensemble, alors la suite obtenue en
codant une trajectoire non pério\-dique par les côtés qu'elle rencontre
est de complexité $p(n)=n(q-\nobreak2)r+2r$; si l'on veut appliquer la
formule au carré, il faut faire attention que ce codage distingue les
côtés parallèles, contrairement à celui que nous avons étudié plus
haut, d'où le résultat $4n+4$ qu'on obtient ici. On ne sait pas par
contre quelle est la complexité du billard dans un polygone
irrationnel, et encore moins ce qui se passe pour un polyèdre autre
que le cube ou un cylindre sur un polygone rationnel.

On peut également s'intéresser aux généralisations de la propriété~\eqref{th:iii}, c'est-à-dire aux suites engendrées par substitution; dans ce
cas, B. Mossé (\cf \cite{Mo}) a montré que la suite $p(n+1)-p(n)$ est
bornée, donc que $p(n)$ est sous-linéaire, et a donné un algorithme
effectif de calcul de $p(n)$; mais la complexité n'a pas en général
de forme simple, même pour une suite substitutive très simple telle
que la suite de Morse, obtenue en partant de $\1$, en remplaçant $\1$
par $\1\0$ et $\0$ par $\0\1$ et en itérant. Pour d'autres résultats
sur ce sujet, on peut aussi consulter \cite{Al}.

\section{Note de 2008}
La conjecture de Tamura a été démontrée en 1995 par Baryshnikov
\cite{B}, en prouvant que la complexité ne dépend pas de la direction
(pourvu qu'elle soit irrationnelle), et en la calculant dans le cas
particulier où la direction est proche de l'un des axes. On ne
connaît toujours pas de preuve directe de la symétrie $P(n,s)=P(s,n)$.

L'étude de la complexité a fait des progrès depuis 1995, citons
deux résultats frappants:\enlargethispage{\baselineskip}

Le premier est dû à Julien Cassaigne \cite{C}: si la complexité $P(n)$
est sous-affine, la suite de ses différences $P(n+1)-P(n)$ est
bornée (la réciproque est triviale).

Le second est dû à Alex Heinis \cite{Hei}. On a vu plus haut les suites
sturmiennes, qui vérifient $\lim_{n\to\infty} {P(n)}/n=1$, et il est
facile de construire des suites dont la complexité satisfait $\lim_{n
\to\infty} {P(n)}/n=2$. Le résultat de Heinis affirme qu'il n'existe
pas de suite dont la complexité satisfait $\lim_{n\to\infty} {P(n)}/
n=\alpha$, avec $1<\alpha<2$. Plus précisément, il existe des suites
pour lesquelles $1<\liminf_{n\to\infty}P(n)/n\le \limsup_{n\to\infty}P
(n)/n<2$, mais alors $P(n)/n$ n'admet pas de limite, et on peut même
minorer explicitement la différence entre la limite supérieure et la
limite inférieure.

On ne connaît d'ailleurs aucun exemple de suite pour laquelle la
limite $\lim_{n\to\infty} P(n)/n$ existe, mais n'est pas
entière, et c'est une question intéressante de savoir s'il en existe.


\backmatter
\bibliographystyle{jepplain+eid}
\bibliography{xups94-02}
\end{document}

