Complexité de suites
engendrées par des récurrences unipotentes

par

PIERRE ARNOUX et CHRISTIAN MAUDUIT (Marseille)

1. **Introduction et énoncé du résultat.** Si $\mathcal{A}$ est un alphabet fini, et $u = (u_n)_{n \in \mathbb{N}}$ un mot infini sur l'alphabet $\mathcal{A}$, on appelle *facteur de u* tout mot de la forme $u_k u_{k+1} \dots u_{k+n-1}$, pour $k$ entier positif et $n$ entier strictement positif, ainsi que le mot vide. On appelle *langage de u*, noté $L_u$, l'ensemble des facteurs de $u$. La *complexité de u* est la fonction $p$, définie par $p(n) = \text{Card}(L_u \cap \mathcal{A}^n)$, qui compte le nombre de mots de longueur $n$ apparaissant dans $u$.

La complexité mesure le caractère plus ou moins aléatoire du mot infini $u$; les mots les plus simples en ce sens sont les mots périodiques, ou plus généralement ultimement périodiques (c'est-à-dire périodiques à partir d'un certain rang). Un mot périodique de période $p$ à partir du rang $q$ a une complexité bornée par $p+q$, et il est facile de montrer que les mots qui ne sont pas ultimement périodiques ont une complexité strictement croissante, en particulier ils satisfont toujours à $p(n) > n$. Les mots de complexité $p(n) = n + 1$, appelés mots *sturmiens*, sont donc de complexité minimale parmi les mots non ultimement périodiques; ils ont été étudiés par de nombreux auteurs (cf. par exemple [HM], [H], [CH], [P]), et on peut en particulier montrer que ce sont exactement les mots donnés par $u_n = \lfloor (n+1)\alpha + \beta \rfloor - \lfloor n\alpha + \beta \rfloor$, ou $u_n = \lceil (n+1)\alpha + \beta \rceil - \lceil n\alpha + \beta \rceil$, pour $\alpha$ irrationnel (rappelons que $\lfloor x \rfloor$ est la partie entière de $x$, c'est-à-dire le plus grand entier inférieur ou égal à $x$, et $\lceil x \rceil$ est le plus petit entier supérieur ou égal à $x$).

D'autres exemples classiques de mots de faible complexité sont connus : mots engendrés par une substitution (cf. [R], [Mo1], [Mo2]), codages des trajectoires de billards (cf. [AMST], [Hu]), mots de complexité $2n + 1$ (cf. [AR]); voir [A] pour une bibliographie.

Nous nous proposons d'étudier ici un autre type de mots de faible com-
plexité; considérons un polynôme $Q$ à coefficients réels de degré $d$, de coef-

<footnote n="1991">1991 Mathematics Subject Classification: 58F03, 05A15, 05B45.</footnote>
ficient dominant irrationnel, et prenons le mot infini $(\Delta^d[Q(n)])_{n \in \mathbb{N}}$, où $\Delta$ est l'opérateur différence, qui au mot $w$ associe le mot $v = \Delta w$ défini par $v_n = w_{n+1} - w_n$, et où $[x]$ désigne la partie entière de $x$. Le but de cet article est de démontrer le théorème suivant :

**THÉORÈME.** Soit $Q$ un polynôme de degré $d$ à coefficients réels dont le coefficient dominant est irrationnel; la suite $(\Delta^d([Q(n)])_{n \in \mathbb{N}}$ prend comme valeurs $2^d$ entiers consécutifs, et sa complexité, qui ne dépend que de $d$, est donnée par la formule

$$p(n) = \frac{1}{V(0, 1, \dots, d-1)} \sum_{0 \le k_1 < k_2 < \dots < k_d \le n+d-1} V(k_d, \dots, k_1),$$

où $V(k_d, \dots, k_1) = \prod_{1 \le i < j \le d} (k_j - k_i)$ est le déterminant de Vandermonde associé à $(k_d, \dots, k_1)$.

**Remarque.** En particulier, comme pour les suites sturmiennes, la complexité ne dépend pas des coefficients de $Q$, mais seulement de son degré, pourvu que le coefficient dominant soit irrationnel.

Le reste de cet article est organisé de la façon suivante : dans la deuxième section, nous donnons l'idée de la preuve dans un cas particulier simple $(Q(n) = n^2\alpha)$ où il n'y a pas de complications techniques. Dans la troisième section, nous établissons une proposition générale qui permet de ramener le calcul de la complexité des itinéraires d'un système dynamique au stage du nombre d'atomes d'une partition. Dans la quatrième section, nous montrons comment, dans le cas général, passer de la suite $(\Delta^d([Q(n)])_{n \in \mathbb{N}}$ au codage d'une orbite d'une application unipotente de $\mathbb{T}^d$ (c'est-à-dire une application affine dont la partie linéaire admet 1 pour seule valeur propre). Dans la cinquième section, nous montrons que les atomes des partitions considérées sont toujours connexes; ceci nous permet, dans la sixième section, d'utiliser des considérations géométriques pour compter ces atomes. Enfin, dans la septième section, nous étudions quelques suites de type proche : suite $[F_{n+2}\alpha] - [F_{n+1}\alpha] - [F_n\alpha]$, où $F_n$ est la suite de Fibonacci, et suite $[n^2\alpha]$ mod 2; dans ces cas, l'hypothèse de minimalité ou l'hypothèse de connexité des atomes n'est pas satisfaite, et l'on ne peut obtenir par les méthodes ci-dessus la valeur exacte de la complexité.

**2. Principe de la preuve.** Donnons l'idée générale de la preuve dans le cas où $Q(n) = n^2\alpha$ ($\alpha \in \mathbb{R} \setminus \mathbb{Q}$). Tout d'abord, nous allons faire apparaître $u$ comme codage de l'orbite d'un point d'un système dynamique par rapport à une partition. Plus précisément, nous allons donner une transformation $T$ du tore $\mathbb{T}^2$ et une fonction $f$ sur $\mathbb{T}^2$, ne prenant qu'un nombre fini de valeurs, et telles que l'on ait $u_n = f(T^n(0))$.
On trouve $f$ et $T$ en écrivant la suite $n^2\alpha$ comme définie par une récurrence linéaire dans $\mathbb{R}^2$ (plus généralement, si $Q$ est de degré $d$, $Q(n)$ est définie par un système de récurrence dans $\mathbb{R}^d$); 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, 2n\alpha)$. On peut alors écrire $u_n$ en fonction de $x_n$ et $y_n$, puisqu'on a par définition

$$ 
\begin{aligned}
u_n &= \lfloor x_{n+2} \rfloor - 2\lfloor x_{n+1} \rfloor + \lfloor x_n \rfloor \\
&= \lfloor x_n + 2y_n + 4\alpha \rfloor - 2\lfloor x_n + y_n + \alpha \rfloor + \lfloor x_n \rfloor;
\end{aligned}
$$

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

Or $T$, en tant que produit croisé au-dessus d'une rotation, est minimal (cf. [F]); cela entraîne facilement que toutes les suites $f(T^n(p))$ ont même langage, quel que soit le point $p$ initial, et que l'on peut obtenir ce langage en considérant seulement les mots initiaux (de la forme $u_0u_1...u_n$) de toutes les suites possibles, plutôt que tous les mots d'une seule suite.

L'ensemble $\{(x, y) | 0 \le x < 1, 0 \le x + y + \alpha < 1\}$ est un domaine fondamental pour l'action de $\mathbb{Z}^2$, et sur ce domaine, la quantité $x+2y+4\alpha = 2(x+y+\alpha)-x+2\alpha$ prend toutes les valeurs de l'intervalle $]-1+2\alpha, 2+2\alpha[$. Donc l'application $f$ donnée ci-dessus, qui vaut $f(x, y) = \lfloor x + 2y + 4\alpha \rfloor$ sur le domaine fondamental, prend ses valeurs dans un ensemble fini $\mathcal{A}$ de 4 entiers consécutifs. Elle définit donc une partition $\mathcal{P}$ de $T^2$ en un nombre fini d'ensembles $P_a, a \in \mathcal{A}$, correspondant à chaque valeur possible. Il est clair que $f(T^n(p)) = a$ si et seulement si $p \in T^{-n}(P_a)$. On en déduit facilement qu'il y a autant de mots de longueur $n$ possible qu'il y a d'atomes dans la partition $\mathcal{P} \wedge T^{-1}\mathcal{P} \wedge \dots \wedge T^{n-1}\mathcal{P}$.

Il reste à montrer (en utilisant le fait que les atomes de $\mathcal{P}$ sont connexes) que tous ces atomes sont connexes, ce que nous ferons dans la partie 5. On peut alors utiliser des arguments géométriques simples pour calculer effectivement la complexité; en effet, il est clair d'après l'écriture de $f$ que les intérieurs des atomes de la partition $f$ sont les cellules de la décomposition cellulaire de $T^2$ engendrée par les trois cercles $x = 0, x + y + \alpha = 0$ et $x + 2y + 4\alpha = 0$; un calcul simple montre que la partition itérée $\mathcal{P} \wedge T^{-1}\mathcal{P} \wedge \dots \wedge T^{n-1}\mathcal{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 $0 \le k \le n+1$. Mais il est facile de montrer qu'une telle décomposition cellulaire a autant de cellules que de sommets, et comme, par irrationalité de $\alpha$, chaque sommet ne peut appartenir qu'à deux cercles, on se ramène à 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 l'expression de la complexité de la suite $u$ :

$$p(n) = \sum_{0 \le j < k \le n+1} (k-j) = \frac{(n+1)(n+2)(n+3)}{6},$$

ce qui est bien le cas $d = 2$ du théorème énoncé dans la première partie.

Nous allons voir que ces arguments se généralisent à des suites obtenues à partir de polynômes de degré quelconque, à l'exception d'une complication technique : quand $d$ est plus grand que 2, la fonction $f$ est invariante par un groupe plus grand que $\mathbb{Z}^d$, et si l'on se contente de passer au quotient par $\mathbb{Z}^d$, les atomes de la partition définie par $f$ ne sont plus connexes.

**3. Complexité des itinéraires d'un système dynamique par rapport à une partition.** Un exemple classique de mots infinis sur l'alphabet $\mathcal{A}$ est donné par les itinéraires d'un système dynamique. On considère un système dynamique $T : X \to X$, une partition $\mathcal{P}$ indicée par l'alphabet $\mathcal{A}$, et la fonction $f$ de codage associée, qui à $x$ associe $a$ si $x \in \mathcal{P}_a$. On note $u(x) = (f(T^n x))_{n \in \mathbb{N}}$ le mot infini (itinéraire) donné par le codage de l'orbite de $x$ (en fait, tout mot infini peut être obtenu de cette façon pour un système bien choisi : il suffit de prendre le décalage à gauche sur $\mathcal{A}^\mathbb{Z}$ et la partition canonique).

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}\mathcal{P}$, et comme ci-dessus, il y a donc autant de facteurs initiaux de longueur $n$ que d'atomes dans l'intersection $\mathcal{P} \wedge T^{-1}\mathcal{P} \wedge \dots \wedge T^{-n+1}\mathcal{P}$; on a donc :

**LEMME 1.** *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 $\mathcal{P}$; la complexité d'ordre $n$ de $u$ est majorée par le nombre d'atomes de la partition $\mathcal{P} \wedge T^{-1}\mathcal{P} \wedge \dots \wedge T^{-n+1}\mathcal{P}$.*

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 le cas d'un système dynamique topologique, on peut donner des conditions qui évitent ces phénomènes :
LEMME 2. Soit $X$ un espace métrique compact, et $T$ un homéomorphisme de $X$. Soit $\mathcal{P} = \{P_a, a \in \mathcal{A}\}$ une partition de $X$ qui vérifie la condition suivante :

(*) Pour toute suite finie $a_0, a_1, \dots, a_{n-1}$, l'ensemble $P_{a_0} \cap T^{-1}P_{a_1} \cap \dots \cap T^{-n+1}P_{a_{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 $\mathcal{P} \wedge T^{-1}\mathcal{P} \wedge \dots \wedge T^{-n+1}\mathcal{P}$.

Preuve. 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)$. ■

Il y a un cas où l'on vérifie facilement la condition sur $x$: on dit qu'un système dynamique topologique est 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 la proposition suivante :

PROPOSITION. Soit $T: X \to X$ un système dynamique minimal, et soit $\mathcal{P}$ une partition de $X$ vérifiant la condition (*) du lemme précédent; alors, pour tout point $x$, la complexité de la suite $u(x)$ est égale au nombre d'atomes des partitions $\mathcal{P} \wedge T^{-1}\mathcal{P} \wedge \dots \wedge T^{-n+1}\mathcal{P}$; en particulier, toutes les suites de codages ont la même complexité (et en fait, les mêmes facteurs).

4. Réduction à l'étude d'un automorphisme unipotent du tore $\mathbb{T}^d$. On considère un polynôme $Q(X) = \sum_{i=0}^d q_i X^i$ de degré $d$ et de coefficient dominant $q_d = \alpha \in \mathbb{R} \setminus \mathbb{Q}$, et la suite $u_n = \Delta^n(|Q(n)|)$. Le but de cette section est de construire une transformation $T: \mathbb{T}^d \to \mathbb{T}^d$, ne dépendant que de $\alpha$, et une fonction $f: \mathbb{T}^d \to \mathbb{N}$ telles que $u_n = f(T^n(q_0, \dots, q_{d-1}))$.

La construction repose sur le lemme suivant :

LEMME 3. Soit $A$ la matrice triangulaire supérieure infinie, indicée par $i, j \ge 0$, donnée par $a_{i,j} = C_j^i$ si $0 \le i \le j$, et $a_{i,j} = 0$ sinon

$$A = \begin{pmatrix} 1 & 1 & 1 & 1 & \dots \\ & 1 & 2 & 3 & \dots \\ & & 1 & 3 & \dots \\ & & & 1 & \dots \\ & & & & 1 & \dots \\ & & & & & \dots \\ & & & & & & \dots \end{pmatrix}.$$

Pour tout entier $n$ positif, les coefficients $a_{i,j}^{(n)}$ de $A^n$ sont donnés par $a_{i,j}^{(n)} = C_j^n n^{j-i}$ si $i \le j$ :
$$A^n = \begin{pmatrix}
1 & n & n^2 & n^3 & n^4 & \dots \\
1 & 2n & 3n^2 & 4n^3 & \dots \\
& 1 & 3n & 6n^2 & \dots \\
& & 1 & 4n & \dots \\
& 0 & & 1 & \dots \\
& & & & \dots & \dots
\end{pmatrix}$$

Preuve. Le produit est bien défini, puisque A est triangulaire supérieure, donc les calculs ne font intervenir que des sommes finies; la démonstration du lemme est immédiate par récurrence. On a

$$\begin{align*}
a_{i,j}^{(n+1)} &= \sum_{k=0}^{\infty} a_{i,k}^{(n)} a_{k,j} \\
&= \sum_{k=i}^{j} C_k^i n^{k-i} C_j^k \quad \text{(les autres termes sont nuls)} \\
&= \sum_{k=0}^{j-i} C_j^i C_{j-i}^k n^k \quad \text{(par l'identité } C_{k+i}^i C_{j-k+i}^k = C_k^i C_{j-k}^k \text{)} \\
&= C_j^i (n+1)^{j-i}. \quad \blacksquare
\end{align*}$$

La restriction de A à l'espace $\mathbb{R}^{d+1}$ (muni de coordonnées $(x_0, \dots, x_d)$) est une application unipotente qui laisse fixe les hyperplans $x_d = \text{const}$; on appelle T la restriction de cette application au plan $x_d = \alpha$. C'est une application affine, et le lemme précédent montre que la première coordonnée de $T^n(q_0, \dots, q_{d-1})$ n'est autre que $Q(n)$.

Il est commode pour la suite de rappeler les principales propriétés de l'opérateur $\Delta$ (voir [GKP], pp. 187–191).

LEMME 4. *L'opérateur $\Delta$ vérifie*

$$(\Delta^d w)_n = \sum_{i=0}^{d} (-1)^i C_d^i w_{n+d-i}.$$

Si P est un polynôme de degré d et de coefficient dominant $\alpha$, on a $\Delta^d P = d!\alpha$; si P est un polynôme de degré inférieur à d, on a $\Delta^d P = 0$.

On en déduit l'expression de la suite $u_n$ en fonction de l'orbite du point $(q_0, \dots, q_{d-1})$ :

LEMME 5. Si l'on pose $T^n(q_0, \dots, q_{d-1}) = (x_0^{(n)}, \dots, x_{d-1}^{(n)})$, on a

$$u_n = \sum_{i=0}^{d} (-1)^{d-i} C_d^i \left[ i^d \alpha + \sum_{k=0}^{d-1} i^k x_k^{(n)} \right].$$
Preuve. On applique le lemme 4 à $u = \Delta^d w$. Ici, $w_n = \lfloor Q(n) \rfloor = \lfloor x_0^{(n)} \rfloor$; or un calcul simple montre que $x_0^{(n+i)} = i^d \alpha + \sum_{k=0}^{d-1} i^k x_k^{(n)}$, d'où l'expression de $u$. ■

On peut donc écrire $u_n = f(x_0^{(n)}, \dots, x_{d-1}^{(n)})$, si l'on pose

$$f(x_0, \dots, x_{d-1}) = \sum_{i=0}^{d} (-1)^{d-i} C_d^i \left[ i^d \alpha + \sum_{k=0}^{d-1} i^k x_k \right]$$

mais l'application $f$, qui est définie sur le plan $x_d = \alpha$, passe en fait au quotient sur le tore $\mathbb{T}^d$.

LEMME 6. La fonction $f$ est $\mathbb{Z}^d$-périodique.

Preuve. On calcule directement que l'on a

$$f(x_0, \dots, x_k+1, \dots, x_{d-1}) - f(x_0, \dots, x_k, \dots, x_{d-1}) = \sum_{i=0}^{d} (-1)^i C_d^i i^k = \Delta^d i^k$$

car le terme entier qu'on ajoute peut sortir de la partie entière; mais cette somme est nulle pour $k < d$, d'après le lemme 4. ■

D'autre part, l'application $T$ passe évidemment elle aussi au quotient, puisque sa partie linéaire est un élément de $\text{SL}(d, \mathbb{Z})$; on trouve donc le résultat annoncé.

Remarque 1. L'application $T$ est un produit croisé au-dessus d'une rotation irrationnelle, elle est donc minimale (c'est-à-dire que l'orbite de tout point est dense) d'après un théorème de Furstenberg ([F]).

Remarque 2. Ces formules sont commodes pour les calculs, mais elles présentent un inconvénient : les atomes de la partition du tore $\mathbb{R}^d/\mathbb{Z}^d$ associée à la fonction $f$ ne sont pas connexes dès que $d > 2$; en fait, dans ce cas, $f$ et $T$ sont invariantes par un groupe $\Gamma$ plus grand que $\mathbb{Z}^n$. On peut en effet écrire de façon différente le système dynamique, en utilisant le lemme 4 : le polynôme $Q$ satisfait l'équation de récurrence $\Delta^d Q = d! \alpha$, c'est-à-dire,

$$Q(n+d) = d!\alpha + \sum_{i=0}^{d-1} (-1)^{d-1-i} C_d^i Q(n+i).$$

On peut donc obtenir $Q(n)$ comme première coordonnée de $S^n(Q(0), \dots, Q(d-1))$, où $S$ est définie par

$$S(y_0, y_1, \dots, y_{d-1}) = (y_1, \dots, y_{d-1}, d!\alpha + \sum_{i=0}^{d-1} (-1)^{d-1-i} C_d^i y_i).$$
Dans ces coordonnées, on obtient la suite $u$ au moyen de la fonction $g$ de codage définie par

$$g(y_0, y_1, \dots, y_{d-1}) = \left\lfloor d!\alpha + \sum_{i=0}^{d-1} (-1)^{d-1-i} C_d^i y_i \right\rfloor + \sum_{i=0}^{d-1} (-1)^{d-i} C_d^i \lfloor y_i \rfloor.$$

Par construction, $g$ et $S$ passent au quotient par $\mathbb{Z}^d$, puisque toutes les formules sont à coefficients entiers, et que les deux coefficients de $y_i$ se compensent exactement dans l'expression de $g$.

En comparant avec les expressions précédentes, on voit que $g$ et $S$ sont en fait les applications $f$ et $T$, avec le changement de variable affine

$$y_i = i^d \alpha + \sum_{k=0}^{d-1} i^k x_k$$

dont la partie linéaire est de matrice $A = (a_{i,j})$, $a_{i,j} = i^j$ (transposée d'une matrice de Vandermonde); donc $f$ et $T$ passent en fait au quotient par un réseau $\Gamma = A^{-1}\mathbb{Z}^d$ qui contient $\mathbb{Z}^d$ comme sous-réseau d'indice $V(0, 1, \dots, d-1)$.

Remarquons que les atomes de la partition définie par $g$ sur $\mathbb{R}^d/\mathbb{Z}^d$ sont connexes; en effet, on peut prendre comme domaine fondamental le cube unité; or sur ce cube, la fonction $g$ est donnée par $g(y_0, y_1, \dots, y_{d-1}) = \lfloor d!\alpha + \phi(y_0, \dots, y_{d-1}) \rfloor$, où $\phi$ est une forme linéaire, et les atomes sont les intersections du cube unité et des tranches comprises entre deux hyperplans $\phi + d!\alpha = n$, d'où le résultat. On vérifie aussi que $\phi$ prend, sur le cube unité, toutes les valeurs d'un intervalle ouvert de longueur $2^d - 1$ dont les extrémités sont irrationnelles; donc la fonction $g$ prend pour valeurs $2^d$ entiers consécutifs.

C'est ce système dynamique que nous allons considérer dans la prochaine section, pour appliquer la proposition de la section 3; en effet, pour ce système, les atomes des partitions que nous considérons sont connexes, et des considérations géométriques permettent de les dénombrer. Cependant, le calcul effectif n'est pas facile dans ces coordonnées, et nous reviendrons dans la section 6 aux expressions des lemmes 3 et 5, avec lesquelles le calcul est plus commode; il suffit ensuite de quotienter par le groupe fini $\Gamma/\mathbb{Z}^d$.

**5. Connexité des composantes des partitions itérées associées au système.** Dans les sections précédentes, nous n'avons pas distingué entre l'application $T: \mathbb{R}^d \to \mathbb{R}^d$ et l'application obtenue par passage au quotient; mais il est important, pour les questions de connexité, de bien faire la différence entre $\mathbb{R}^d$ et $\mathbb{T}^d = \mathbb{R}^d/\Gamma$. Nous noterons donc $T$ l'application affine sur $\mathbb{R}^d$, et $\bar{T}$ la transformation de $\mathbb{T}^d$ obtenue par passage au quotient
par le réseau $\Gamma$. Nous noterons de même $f$ l'application de $\mathbb{R}^d$ dans $\mathbb{N}$, et $\bar{f}$ l'application obtenue par passage au quotient.

Nous allons commencer par expliciter la partition associée à $f$; en utilisant la formule donnée à la fin de la section 2, on voit que les lieux de discontinuité de $f$ sont les plans $H_{i,n}$ d'équation $\sum_{k=0}^{d-1} i^k x_k + i^d \alpha = n$, avec $n$ entier. Un calcul simple montre que ces plans sont images les uns des autres par $T$, plus précisément on a $H_{i,n} = T^{-i} H_{0,n}$ (il suffit de remarquer que, dans les coordonnées $y_i$ définies à la fin de la section 4, l'équation de $H_{i,n}$ est $y_i = n$, et d'utiliser l'expression donnée pour $T$ dans ces coordonnées).

Puisque les vecteurs $(1, i, i^2, \dots, i^{d-1})$, pour $i \in \mathbb{N}$, sont linéairement indépendants, les plans $H_{i,n}$ le sont aussi, et l'intersection de $d$ plans non parallèles est réduite à un point. De plus, si $\alpha$ est irrationnel, l'intersection de $d+1$ plans est toujours vide, car sinon, en résolvant le système à $d+1$ inconnues $(x_0, \dots, x_{d-1}, \alpha)$ donné par les équations des $d+1$ plans, les équations étant à coefficients entiers, on obtiendrait une valeur rationnelle pour $\alpha$.

La projection canonique envoie tous les $H_{i,n}$, pour $i$ fixé, sur un même hyperplan $\bar{H}_i$ de $\mathbb{T}^d$; l'équation étant rationnelle, cet hyperplan est en fait un tore de dimension $d-1$ plongé dans $\mathbb{T}^d$. On peut ainsi expliciter complètement la partition $\mathcal{P}$ associée à $f$ :

**LEMME 7.** *Les intérieurs des atomes de la partition $\mathcal{P}$ sont les cellules de la partition déterminée par les $d+1$ hyperplans $\bar{H}_0, \dots, \bar{H}_d$.*

**Préuve.** Il est clair, d'après la définition de $f$, que les bords des éléments de la partition $\mathcal{P}$ sont contenus dans les hyperplans; de plus, comme $f$ varie au voisinage de chaque hyperplan, les hyperplans $\bar{H}_i$ ne peuvent être contenus dans l'intérieur d'un atome de la partition; on en déduit donc que chaque atome de $\mathcal{P}$ est réunion d'un nombre fini de cellules qui n'ont pas de face (de dimension $d-1$) en commun. De plus, on a vu ci-dessus qu'un domaine fondamental pour l'action de $\Gamma$ est encadré par les hyperplans $H_{i,0}$ et $H_{i,1}$, pour $0 \le i < d$; sur ce domaine fondamental, les atomes de $\mathcal{P}$ sont séparés par les hyperplans $H_{d,n}$, et $f$ ne peut prendre la même valeur sur deux cellules distinctes. $\blacksquare$

On peut alors prouver que chaque atome de la partition itérée $\mathcal{P} \wedge T^{-1} \mathcal{P} \wedge \dots \wedge T^{1-n} \mathcal{P}$ est connexe; nous allons en fait démontrer une propriété plus forte :

**DÉFINITION.** On dit qu'un sous-ensemble $E$ du tore $\mathbb{T}^d$ muni de sa structure affine est *convexe* si deux points de $E$ peuvent être joints par un unique segment.
Remarquons que la propriété de convexité sur le tore n’est pas facile à manier; en particulier, il est faux que l’intersection de deux ensembles convexes soit convexe (cf. Figure 1); on a cependant la propriété suivante :

<figure><img src="image_1.png" /><figcaption>Fig. 1</figcaption></figure>

**LEMME 8.** *Soient $E$ et $F$ deux ensembles convexes de $\mathbb{T}^d$; si ces deux ensembles sont contenus dans un même convexe $D$, alors l'intersection $E \cap F$ est convexe. C'est en particulier le cas s'ils sont contenus dans la projection de l'intérieur $\bar{D}$ d'un domaine fondamental convexe pour l'action de $\Gamma$ sur $\mathbb{R}^d$.*

**Préuve.** Soient $x$ et $y$ deux points de l'intersection; par définition, ils sont joints par un segment $\gamma$ dans $E$ et un segment $\gamma'$ dans $F$; ces deux segments, étant contenus dans $D$, sont égaux, donc contenus dans l'intersection. ■

**LEMME 9.** *Chaque atome de la partition $\mathcal{P} \wedge T^{-1}\mathcal{P} \wedge \dots \wedge T^{1-n}\mathcal{P}$ est d'intérieur convexe.*

**Préuve.** C'est vrai pour $n=1$, puisqu'on a vu que les atomes de $\mathcal{P}$ sont convexes. Supposons le résultat vrai à l'ordre $n$, et soit $P$ un atome de $\mathcal{P} \wedge T^{-1}\mathcal{P} \wedge \dots \wedge T^{-n}\mathcal{P}$; c'est l'intersection d'un atome $P_1$ de $\mathcal{P} \wedge T^{-1}\mathcal{P} \wedge \dots \wedge T^{1-n}\mathcal{P}$, qui est convexe par hypothèse, et d'un atome $P_2$ de $T^{-n}\mathcal{P}$, qui est convexe comme image d'un convexe par un automorphisme linéaire. Mais les intérieurs de $P_1$ et $P_2$ sont tous deux contenus dans la même cellule de la partition engendrée par $\overline{H}_n, \dots, \overline{H}_{n-1+d}$; donc leur intersection est convexe d'après le lemme précédent. ■

**6. Calcul effectif de la complexité.** Pour calculer la complexité, il suffit donc de calculer le nombre de composantes connexes de la partition $\mathcal{P} \wedge T^{-1}\mathcal{P} \wedge \dots \wedge T^{1-n}\mathcal{P}$ de $\mathbb{R}^d/\Gamma$; ou encore, il suffit de calculer le nombre de composantes connexes de la partition sur $\mathbb{R}^d/\mathbb{Z}^d$, et de diviser par l'indice
$V(0, 1, \dots, d-1)$ de $\mathbb{Z}^d$ dans $\Gamma$. Dans tout ce qui suit, on se placera dans $\mathbb{R}^d/\mathbb{Z}^d$.

LEMME 10. Soit $0 \le i_1 < \dots < i_d$ une suite finie d'entiers; l'intersection des tores $\bar{H}_{i_1}, \dots, \bar{H}_{i_d}$ correspondant est un ensemble fini, de cardinal $V(i_1, \dots, i_d)$, où le nombre $V(i_1, \dots, i_d) = \prod_{1 \le k < j \le d} (i_j - i_k)$ est le déterminant de Vandermonde associé à $(i_1, \dots, i_d)$.

Preuve. On se place dans $\mathbb{R}^d$, et on considère les plans $H_{i_k,n}$, pour tout $n$ entier; on considère l'ensemble des points d'intersection de $d$ plans non parallèles de cette famille, il est clair que c'est un réseau $\Gamma_{i_1, \dots, i_d}$, et que ce réseau contient un translaté de $\mathbb{Z}^d$, car, les équations étant à coefficients entiers, chaque famille de plans $H_{i,n}$, pour $i$ fixé, est invariante par translation de $\mathbb{Z}^d$. Par passage au quotient, le réseau $\mathbb{Z}^d$ se projette sur un point, et le réseau que nous considérons sur un nombre fini de points; pour calculer ce nombre, il suffit de connaître le volume d'un domaine fondamental de $\Gamma_{i_1, \dots, i_d}$. Pour cela, prenons comme coordonnées les équations des plans, c'est-à-dire les sommes $\sum i^k x_k$. Les $H_{i,n}$ deviennent des hyperplans parallèles aux hyperplans de coordonnées, et le cube unité un domaine fondamental de $\Gamma_{i_1, \dots, i_d}$; il suffit de calculer le déterminant de ce changement de coordonnées, qui est évidemment le déterminant de Vandermonde. $\blacksquare$

De la démonstration du lemme 10, découle immédiatement le corollaire suivant :

COROLLAIRE. Les $d$ tores plongés $\bar{H}_{i_1}, \dots, \bar{H}_{i_d}$ déterminent une décomposition cellulaire du tore $\mathbb{T}^d$ qui a $V(i_1, \dots, i_d)$ cellules de dimension $d$ et le même nombre de sommets.

On va maintenant donner la formule explicite; on aura besoin pour cela du lemme suivant, dont la démonstration nous a été communiquée par Gaël Meigniez ([M]) :

LEMME 11. On considère une décomposition cellulaire du tore $\mathbb{T}^d$ par des hyperplans en position générale; on suppose que toutes les cellules de cette décomposition sont convexes. Alors le nombre de cellules est égal au nombre de sommets de la partition.

Preuve. On va démontrer le lemme par récurrence sur la dimension. En dimension 1, il s'agit d'un cercle partitionné par des points, et le lemme dit simplement que, s'il y a au moins un point, le nombre d'intervalles de la partition est égal au nombre de points, ce qui est évident.

Supposons le résultat vrai en dimension $d-1$; si les hyperplans découpent le tore en cellules convexes, il doit y avoir au moins $d$ hyperplans, sinon les
cellules ne seraient pas simplement connexes. S'il y a exactement *d* hyperplans, le corollaire du lemme 10 nous dit qu'il y a autant de cellules que de sommets. Supposons le résultat vrai pour $k \ge d$ hyperplans; rajoutons un nouvel hyperplan $H$. La trace des $k$ autres hyperplans détermine un décomposition cellulaire de $H$, et il est clair que chaque cellule de cette décomposition de $H$ sépare 2 cellules de dimension $d$; on a donc rajouté autant de cellules de dimension $d$ qu'il y a de cellules sur $H$; d'autre part, il est clair que tous les sommets rajoutés sont sur $H$, et sont des sommets pour sa décomposition. Mais $H$ étant de dimension $d-1$ satisfait à l'hypothèse, et l'on voit que l'on a rajouté autant de cellules que de sommets, l'égalité est encore vraie pour $k+1$ hyperplans, d'où le résultat. ■

Il suffit donc, pour compter le nombre de cellules, de compter le nombre de sommets; or, la partition étudiée est engendrée par les hyperplans $\overline{H}_0, \overline{H}_1, \dots, \overline{H}_{n-1+d}$; chaque sommet est obtenu par l'intersection de $d$ de ces hyperplans, et le nombre de telles intersection, d'après le lemme 10, est donné par le déterminant de Vandermonde correspondant, d'où le théorème.

**7. Remarques.** On peut essayer de généraliser ce résultat à d'autres suites récurrentes; l'automorphisme du tore et l'application de codage se déduisent facilement de la formule de récurrence, mais on ne peut en général donner que des majorations, parce que la condition de minimalité ou celle de connexité des atomes ne sont en général pas satisfaites. Les deux exemples qui suivent illustrent ces difficultés.

**EXEMPLE 1.** On note $F_n$ la suite de Fibonacci, définie par $F_0 = 0$, $F_1 = 1$, $F_{n+2} = F_n + F_{n+1}$; pour un réel irrationnel $\alpha$, on considère le mot infini donné par $u_n = [F_{n+2}\alpha] - [F_{n+1}\alpha] - [F_n\alpha]$.

Si l'on pose $T(x, y) = (y, x+y)$ et $f(x, y) = [x+y] - [x] - [y]$, on a $u_n = f(T^n(0, \alpha))$. Il est alors possible, en utilisant les même techniques que ci-dessus, de donner une borne à la complexité, mais on ne peut obtenir de formules exactes, puisque l'on ne connaît pas de point d'orbite dense pour $T$; on sait seulement, par ergodicité de $T$, que la formule obtenue sera valable pour presque tout point de départ. La complexité obtenue est exponentielle, ce qui montre que la suite est très aléatoire : il y a peu de corrélations entre les valeurs successives de $[F_n\alpha]$.

**EXEMPLE 2.** Mendès-France s'est intéressé dans [MF] aux mots définis par $u_n = [Q(n)] \bmod g$, où $Q$ est un polynôme de degré $d$ et de coefficient dominant irrationnel; il a montré que pour ces mots infinis, $p(n) \in O(n^{2(d+1)^2})$. On peut ici reprendre le même automorphisme $T$ que dans la section 3, et l'application $f$ donnée par $f(x_0, \dots, x_{d-1}) = [x_0] \bmod g$, qui est invariante modulo $(g\mathbb{Z})^d$. Dans ce cas, l'automorphisme est bien minimal, mais il est faux que les atomes des partitions itérées soient connexes;
on sait donc que la complexité ne peut dépendre que de $d$ et $\alpha$, et on a une majoration pour cette complexité :

$$p(n) \le g^d \sum_{0 \le k_1 < k_2 < \dots < k_d \le n-1} V(k_d, \dots, k_1) \quad \text{si } n \ge d$$

ce qui montre que $p(n) \in O(n^{d(d+1)/2})$.

References

[A] J.-P. Allouche, *Sur la complexité des suites infinies*, Bull. Belg. Math. Soc. 1 (1994), 133-143.

[AMST] P. Arnoux, C. Mauduit, I. Shiokawa and J. I. Tamura, *Complexity of sequences defined by billiards in the cube*, Bull. Soc. Math. France 122 (1994), 1-12.

[AR] P. Arnoux et G. Rauzy, *Représentation géométrique de suites de complexité* $2n + 1$, ibid. 119 (1991), 199-215.

[CH] E. M. Coven and G. A. Hedlund, *Sequences with minimal block growth*, Math. Systems Theory 7 (1973), 138-153.

[F] H. Furstenberg, *Strict ergodicity and transformation of the torus*, Amer. J. Math. 83 (1961), 573-601.

[GKP] R. L. Graham, D. E. Knuth and O. Patashnik, *Concrete Mathematics*, Addison-Wesley, 1988.

[H] G. A. Hedlund, *Sturmian minimal sets*, Amer. J. Math. 66 (1944), 605-620.

[HM] G. A. Hedlund and M. Morse, *Symbolic dynamics II. Sturmian trajectories*, ibid. 62 (1940), 1-42.

[Hu] P. Hubert, *Complexité de suites définies par des billards rationnels*, Bull. Soc. Math. France 123 (1995), 257-270.

[M] G. Meigniez, communication personnelle.

[MF] M. Mendès-France, *Nombres normaux. Applications aux fonctions pseudo-aléatoires*, J. Anal. Math. 20 (1967), 1-56.

[Mo1] B. Mossé, *Reconnaissabilité des substitutions et complexité des suites automatiques*, Bull. Soc. Math. France 124 (1996), 101-118.

[Mo2] —, *On the complexity of fixed points of substitutions*, Institut de Mathématiques de Luminy, prétirage 96-06, 1996.

[P] M. Paul, *Minimal symbolic flows having minimal block growth*, Math. Systems Theory 8 (1974), 309-315.

[R] G. Rauzy, *Suites à termes dans un alphabet fini*, Séminaire Théorie des Nombres de Bordeaux, t. 25, 1982-1983, 2501-2516.

Laboratoire de Mathématiques Discrètes
UPR 9016
163, Avenue de Luminy
Case 930
13288 Marseille Cedex 9, France
E-mail: arnoux@lmd.univ-mrs.fr
mauduit@lmd.univ-mrs.fr

Reçu le 27.5.1995 (2799)