# Calcul de la dynamique de transformations linéaires contractantes mod 1 et arbre de Farey

par

YANN BUGEAUD (Strasbourg) et JEAN-PIERRE CONZE (Rennes)

**Introduction.** L'étude du comportement asymptotique des itérations d'une transformation de l'intervalle dans lui-même a fait l'objet de nombreux travaux, dans un cadre très général. Nous envisageons ici le cas particulier des applications $T_{\gamma,\alpha}$ de l'intervalle $[0, 1[$ dans lui-même définies par

$$T_{\gamma,\alpha} : x \rightarrow \gamma x + \alpha \bmod 1,$$

$\gamma$ et $\alpha$ étant deux paramètres réels vérifiant $0 < \gamma < 1$, et d'applications analogues à "deux pentes". Bien que très simple en raison du caractère localement contractant des applications, l'étude explicite des itérations de $T_{\gamma,\alpha}$ est intéressante d'un point de vue appliqué, car elle intervient dans des algorithmes de quantification en traitement du signal (cf. [3]). D'autre part, d'un point de vue théorique, elle offre un modèle simple pour lequel on peut effectuer une étude complète de la dynamique, par une méthode susceptible d'être étendue à des familles plus générales d'applications localement contractantes.

Cette méthode consiste à prolonger la construction de l'arbre de Farey (cf. [4], [5]), classique pour les rotations (cas $\gamma = 1$), à la région $0 < \gamma < 1$. On obtient ainsi une famille de polynômes qui permet de préciser si l'attracteur de la transformation $T_{\gamma,\alpha}$ est un ensemble fini ou un ensemble de Cantor sur lequel la transformation est semi-conjuguée à une rotation irrationnelle, et d'explicitier analytiquement l'ensemble exceptionnel des valeurs du couple de paramètres $(\alpha, \gamma)$ pour lesquelles la deuxième situation se présente.

Par ailleurs, en utilisant un procédé d'induction, on peut obtenir numériquement les caractéristiques de la dynamique, à l'aide d'un algorithme du type "fractions continues". Ce procédé devrait pouvoir s'étendre à des situations plus générales de transformations localement contractantes semi-conjuguées à un échange d'intervalle.

<footnote n="1991">1991 Mathematics Subject Classification: 11B57, 58F08.</footnote>
Le travail présenté ici prolonge des résultats de Y. Bugeaud [2] et d'autres travaillant dans le cadre du traitement du signal, en particulier sur des problèmes de quantification (voir par exemple les références dans l'article de O. Feely et L. O. Chua [3]). Pour certaines notions utilisées ici telles que nombre de rotation, arbre de Farey, on pourra se référer à l'ouvrage de W. de Melo et S. van Strien [5].

*Plan de l'article.* Une caractérisation des valeurs des paramètres pour lesquels l'application $T_{\gamma,\alpha}$ a une orbite périodique attractive a été donnée dans [2] (théorème 1.1 ci-dessous). Après une première partie consacrée à des rappels, nous présentons dans la partie 2 une démonstration de nature algébrique de ce résultat, basée sur l'étude de fractions rationnelles en une variable généralisant l'arbre de Farey.

Dans la partie 3, nous présentons, sans démonstration, une généralisation du théorème 1.1 au cas des transformations contractantes à deux pentes.

Dans la partie 4, nous décrivons un algorithme, du type de l'algorithme des fractions continues, qui permet de calculer, pour des paramètres $(\gamma, \alpha)$, les caractéristiques de la dynamique des transformations $T_{\gamma,\alpha}$ et plus généralement de la classe des transformations introduite dans la troisième partie.

Nous mentionnons enfin quelques questions prolongeant l'étude présentée ici.

**1. Notations et rappels.** Nous notons $X$ l'intervalle unité $[0, 1[$ et nous désignons respectivement par $[\cdot]$ et $\{\cdot\}$ les fonctions partie entière et partie fractionnaire.

Etant donné $\alpha \in [0, 1[$, nous notons $T_\alpha$ la rotation $T_\alpha x = \{x + \alpha\}$, vue comme application de $X$ dans lui-même. On peut coder la rotation $T_\alpha$ en utilisant la partition de l'intervalle $[0, 1[$ en les intervalles $[0, 1 - \alpha[$ et $[1 - \alpha, 1[$. Soit $\varepsilon$ la fonction définie par

$$ \varepsilon(x) = \begin{cases} 0 & \text{si } x \in [0, 1 - \alpha[, \\ 1 & \text{si } x \in [1 - \alpha, 1[. \end{cases} $$

Pour chaque point $x$, la suite $(\varepsilon(T_\alpha^{k-1}x))_{k \in \mathbb{Z}}$ est une suite de “0” et de “1” codant le point $x$. En appliquant la relation $x + \alpha = T_\alpha x + \varepsilon(x)$ au point $T_\alpha^{n-1}x$, nous obtenons par récurrence

$$ x + n\alpha = T_{\alpha}^{n}x + \varepsilon(T_{\alpha}^{n-1}x) + \varepsilon(T_{\alpha}^{n-2}x) + \dots + \varepsilon(x). $$

On notera simplement $(\varepsilon_k)_{k \in \mathbb{Z}}$ la suite correspondant à $x = 0$. On a donc par définition $\varepsilon_k = \varepsilon(T_\alpha^{k-1}0)$, pour tout $k \in \mathbb{Z}$. Pour préciser que cette suite dépend de $\alpha$, on la note également $(\varepsilon_k^\alpha)$. Pour tout $\alpha$, on a $\varepsilon_1^\alpha = 0$ et, pour $k \ge 1$,

$$ (1.1) \qquad \varepsilon_k^\alpha = [k\alpha] - [(k-1)\alpha]. $$
La suite $(\varepsilon_k^\alpha)$ donne la dynamique de l'action de $T_\alpha$ sur l'orbite de 0. Si l'on note $A_0$ (resp. $A_1$) la translation $x \mapsto x + \alpha$ (resp. $x \mapsto x + \alpha - 1$), on a

$$ (1.2) \qquad T_{\alpha}^{n}(0) = A_{\varepsilon_{n}^{\alpha}} \dots A_{\varepsilon_{1}^{\alpha}}(0). $$

Cette suite $(\varepsilon_k^\alpha)$ (dite aussi *suite de Sturm* de $\alpha$) sera appelée *suite de codage* de la rotation $T_\alpha$. Dans le cas où $\alpha$ est rationnel, égal à la fraction irréductible $p/q$, la suite $(\varepsilon_k^{p/q})$ est périodique de période $q$.

Notons que l'on a, pour $n \ge 1$,

$$ [n\alpha] = \sum_{k=1}^{n} \varepsilon_k, \quad n\alpha = \{n\alpha\} + \sum_{k=1}^{n} \varepsilon_k, $$

ce qui fournit une méthode de quantification binaire du réel $\alpha$, puisque $\alpha$ peut s'écrire, si $\alpha = p/q \in [0, 1[$ est rationnel :

$$ \alpha = \frac{1}{q} [\varepsilon(T_{\alpha}^{q-1}0) + \varepsilon(T_{\alpha}^{q-2}0) + \dots + \varepsilon(0)], $$

et si $\alpha$ est irrationnel :

$$ \alpha = \lim_{n} \frac{1}{n} [\varepsilon(T_{\alpha}^{n-1}0) + \varepsilon(T_{\alpha}^{n-2}0) + \dots + \varepsilon(0)]. $$

Nous allons voir que l'ensemble des suites de codage associées aux nombres $\alpha \in [0, 1[$ peut aussi être construit globalement par concatenation selon le procédé de construction de l'arbre de Farey dont nous rappelons brièvement le principe.

Arbre de Farey. L'arbre de Farey est la suite $(G_n)_{n \ge 1}$ d'ensembles de rationnels, ordonnée par inclusion, définie de la façon suivante. On part de $G_1 = \{\frac{0}{1}, \frac{1}{1}\}$. Pour $n \ge 1$, $G_{n+1}$ est l'ensemble, ordonné par ordre croissant, formé des rationnels appartenant à $G_n$ et des rationnels obtenus en prenant le médiant des couples de rationnels consécutifs de $G_n$, le médiant de deux rationnels $p/q$ et $p'/q'$ étant le rationnel

$$ \frac{p''}{q''} = \frac{p + p'}{q + q'}. $$

On obtient ainsi tous les rationnels de l'intervalle $[0, 1]$. On montre par récurrence que deux fractions irréductibles $p/q$ et $p'/q'$ sont deux éléments consécutifs d'un ensemble $G_n$ si, et seulement si, $pq' - p'q = \pm 1$.

Dans la partie 2, nous généralisons ce procédé à des suites de fractions rationnelles en une variable.

Dans ce qui suit, on utilisera, sans le repréciser, le fait que, si $p/q$ est une fraction irréductible appartenant à $]0, 1[$, alors $\varepsilon_0^{p/q} = 1$, $\varepsilon_1^{p/q} = 0$ et la suite $(\varepsilon_k^{p/q})$ est $q$-périodique. Le lemme 1.1 ci-dessous montre que les suites $(\varepsilon_k^{p/q})$ sont symétriques, si l'on exclut les valeurs extrêmes $\varepsilon_0$ et $\varepsilon_{q-1}$ :
LEMME 1.1. *Soit p/q un rationnel irréductible; si l≠0,1 mod q, on a*

$$ \varepsilon_l^{p/q} = \varepsilon_{q-l+1}^{p/q}. $$

Preuve. Il suffit d'observer que, si j ne divise pas q, on a $[-jp/q] = -[jp/q] - 1$. ■

LEMME 1.2. *Soient p/q et p'/q' deux rationnels vérifiant p'q - pq' = 1 et notons r le rationnel (p + p')/(q + q'). Alors εq' = 0 et εq'+1 = 1. De plus, on a*

(i) $\varepsilon_l^r = \varepsilon_l^{p/q}, \quad 1 \le l \le q,$

(ii) $\varepsilon_{q+l}^r = \varepsilon_l^{p'/q'}, \quad 1 \le l \le q'$,

(iii) $\varepsilon_l^r = \varepsilon_l^{p'/q'}, \quad 0 \le l \le q' - 1,$

(iv) $\varepsilon_{q'+l}^r = \varepsilon_{q-l+1}^{p/q}, \quad 0 \le l \le q - 1,$

(v) $\varepsilon_{q'+1-l}^r = \varepsilon_l^{p'/q'}, \quad 0 \le l \le q' - 1,$

(vi) $\varepsilon_{q+q'-l}^r = \varepsilon_{q-l}^{p/q}, \quad 0 \le l \le q - 2.$

Preuve. La preuve est basée sur la relation (1.1). Comme

$$ q' \frac{p+p'}{q+q'} = p' - \frac{1}{q+q'}, $$

on a $[(q' - 1)r] = [q'r] = [(q' + 1)r] - 1$ et donc $\varepsilon_{q'}^r = 0, \varepsilon_{q'+1}^r = 1$.

(i) Pour $0 \le l \le q$, on déduit de $0 \le lr - lp/q \le 1/(q+q')$ et $[lp/q] = [lp/q+1/(q+q')]$ que $[lr] = [lp/q]$. Par conséquent $\varepsilon_l^r = \varepsilon_l^{p/q}$ pour $1 \le l \le q$. On prouve (iii) de manière analogue.

(ii) Soit $0 \le l \le q'$. Comme

$$ \frac{(l+q)(p+p')}{q+q'} = p + \frac{1+l(p+p')}{q+q'}, $$

il suffit de prouver que $[lp'/q'] = [(1+l(p+p'))/(q+q')]$, ce qui découle de

$$ \frac{1+l(p+p')}{q+q'} - \frac{lp'}{q'} \le \frac{1}{q+q'}. $$

(iv) Si $l=0, 1$, (iv) est déjà prouvé. Pour $1 \le l \le q-1$, on a

$$ (q' + l) \frac{p+p'}{q+q'} = p' + \frac{l(p+p') - 1}{q+q'} $$

et l'on déduit de l'inégalité

$$ \frac{lp}{q} - \frac{l(p+p')-1}{q+q'} < \frac{1}{q+q'} $$

que $[lp/q] = [(l(p+p') - 1)/(q+q')]$. On a donc $\varepsilon_{q'+l}^r = \varepsilon_l^{p/q}$ si $2 \le l \le q-1$. Il suffit alors d'appliquer le lemme 1.1.
Enfin, on déduit (v) (resp. (vi)) de (iii) (resp. (iv)) en appliquant le lemme 1.1. ■

### REMARQUE 1.1.
D'après le lemme 1.2, la dynamique de la rotation par $(p+p')/(q+q')$ est d'abord (pour les $q$ premiers itérés) celle de la rotation par $p/q$, puis (pour les $q'$ derniers itérés), celle de la rotation par $p'/q'$. On peut donc construire la dynamique des rotations rationnelles par un procédé de concatenation calqué sur la construction de l'arbre de Farey des rationnels de l'intervalle $[0, 1]$.

### Dynamique des applications $T_{\gamma,\alpha}$.
Considérons maintenant l'application de l'intervalle $[0, 1[$ dans lui-même $T_{\gamma,\alpha}$ définie par

$$ (1.3) \qquad x \xrightarrow{T_{\gamma,\alpha}} \{\gamma x + \alpha\}, $$

où $\gamma$ et $\alpha$ sont deux paramètres réels. On peut supposer $\alpha \in [0, 1[$. Pour $\gamma = 1$, on obtient la rotation $T_\alpha$. Nous nous intéressons ici au cas contractant et nous supposerons donc, dans toute la suite, $0 \le \gamma < 1$.

La dynamique de l'itération de $T_{\gamma,\alpha}$ est donnée, en fonction des valeurs des paramètres, par les résultats suivants de [2] :

### THÉORÈME 1.1.
Soient $q$ et $p, q \ge 1$, $p \le q$, deux entiers premiers entre eux. Définissons l'intervalle $I_q^p(\gamma)$ par

$$ I_q^p(\gamma) = \left[ \frac{P_q^p(\gamma)}{1 + \gamma + \dots + \gamma^{q-1}}, \frac{P_q^p(\gamma) + \gamma^{q-1} - \gamma^q}{1 + \gamma + \dots + \gamma^{q-1}} \right], $$

où $P_q^p$ est le polynôme

$$ P_q^p(\gamma) = \sum_{k=0}^{q-1} \varepsilon_{q-k}^{p/q} \gamma^k. $$

Alors l'application $T_{\gamma,\alpha}$ a une orbite périodique attractive avec la même dynamique que la rotation $T_{1,p/q}$ si, et seulement si, $\alpha \in I_q^p(\gamma)$.

### COROLLAIRE 1.1.
Soit $\gamma < 1$; la mesure de Lebesgue de l'ensemble des paramètres $\alpha \in ]0, 1[$ pour lesquels le nombre de rotation de $T_{\gamma,\alpha}$ est rationnel est égale à 1.

### Preuve.
La somme des longueurs des intervalles $I_q^p(\gamma)$ définis au théorème 1.1 vaut

$$ \mu(\gamma) = \sum_{q=1}^{\infty} \frac{\Phi(q)(\gamma^{q-1} - \gamma^q)}{1 + \gamma + \dots + \gamma^{q-1}}, $$

où $\Phi(q)$, fonction d'Euler, est le nombre d'entiers $p$, $1 \le p \le q$, premiers avec $q$. En utilisant le théorème 308 de [4], on obtient $\mu(\gamma) = 1$. ■

Nous avons représenté sur la Figure 1 les sous-ensembles de $[0, 1[ \times [0, 1[$ formés par les couples $(\gamma, \alpha)$ tels que $\alpha \in I_q^p(\gamma)$, pour $\frac{p}{q} \in \{\frac{0}{1}, \frac{1}{5}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{4}{5}\}$.
<figure><img src="image_1.png" /><figcaption>Figure 1</figcaption></figure>
On comparera ce résultat avec l'étude de perturbations de rotations, telles que la famille classique $x \to x + \alpha + \varepsilon \sin x$ (cf. [1]).

Pour $\gamma \in ]0, 1[$, il existe cependant un ensemble résiduel $C_\gamma$ de valeurs de $\alpha$ pour lesquelles le nombre de rotation est irrationnel. Cet ensemble est défini par

$$C_{\gamma} = X \setminus \bigcup_{q,p} I_{q}^{p}(\gamma).$$

Etant donnés $\alpha$ irrationnel et $\gamma \in ]0, 1[$, posons

$$\tau_{\gamma}(\alpha) = (1 - \gamma) \sum_{k=0}^{\infty} \varepsilon_{-k}^{\alpha} \gamma^{k},$$

($\varepsilon_k^\alpha$)$_{k \in \mathbb{Z}}$ étant la suite fournie par le codage de $\alpha$. On peut montrer (cf. [2]) que, pour chaque $\gamma \in ]0, 1[$, l'application $\tau_\gamma$ est une bijection de $\mathbb{R} \setminus \mathbb{Q} \cap [0, 1]$ sur $C_\gamma$, telle que $\lim_{\gamma \to 1} \tau_\gamma(\alpha) = \alpha$. De plus, la transformation $T_{\gamma, \tau_\gamma(\alpha)}$ est semi-conjuguée à la rotation d'angle $\alpha$.

## 2. Etude des polynômes $P_q^p$

*Extension de la construction de Farey.* Le théorème 1.1 motive l'exten-
sion suivante du procédé de Farey à la région des paramètres $0 \le \gamma < 1$.
On construit un arbre de fractions rationnelles de la forme $P(\gamma)/Q(\gamma)$, où
$Q$ est un polynôme de la forme $Q = 1 + \gamma + \dots + \gamma^{q-1}$ et $P$ un polynôme à
coefficients dans $\{0, 1\}$, de degré au plus $q - 1 = \deg(Q)$.

Le procédé est le suivant. Les fractions de départ, au niveau $n = 0$, sont $0/1$ et $1/1$, qui sont adjacentes. Supposons construite la suite au niveau $n$. Alors les fractions rationnelles au niveau $n+1$ sont les fractions rationnelles au niveau $n$ et les nouvelles fractions obtenues en prenant le “médiant” de deux fractions adjacentes au niveau $n$, construit de la façon suivante :

Si $P/Q$ et $P'/Q'$ sont deux fractions adjacentes au niveau $n$, $P/Q$ étant à “gauche” de $P'/Q'$, on forme $P''/Q''$, qui sera “entre” $P/Q$ et $P'/Q'$ :

$$\frac{P''(\gamma)}{Q''(\gamma)} = \frac{P'(\gamma) + \gamma^{\deg(Q') + 1} P(\gamma)}{Q'(\gamma) + \gamma^{\deg(Q') + 1} Q(\gamma)}.$$

Si $q-1$ et $q'-1$ sont les degrés respectifs de $Q$ et de $Q'$, le polynôme $Q''$ est
donc de la forme $Q''(\gamma) = 1 + \gamma + \dots + \gamma^{q+q'-1}$. Les couples $(P/Q, P''/Q'')$ et $(P''/Q'', P'/Q')$ ainsi construits constituent les nouveaux couples de frac-
tions adjacentes au niveau $n+1$, $P/Q$ étant à “gauche” de $P''/Q''$ et $P''/Q''$
à “droite” de $P'/Q'$.

Les fractions rationnelles $P(\gamma)/Q(\gamma)$ ainsi obtenues seront appelées frac-
tions rationnelles de Farey. En faisant $\gamma = 1$, on retrouve les fractions
irréductibles construites suivant le procédé de Farey. Il est clair que les co-
efficients des numérateurs $P$ obtenus forment les suites de “0” et de “1”
obtenues dans la partie 1, puisque la concaténation de deux telles suites correspond à la construction de la fraction médiant.

Plus précisément, si $(\varepsilon_1 = 0, \dots, \varepsilon_{q-1})$ est la suite construite en procédant aux mêmes concaténations que dans la construction du polynôme $P$, ce polynôme (en fait de degré au plus $q-2$, car $\varepsilon_1 = 0$) est de la forme

$$P(\gamma) = \sum_{k=0}^{q-1} \varepsilon_{q-k}\gamma^k,$$

et $(\varepsilon_k) = (\varepsilon_k^{p/q})$ est la suite associée à la rotation d'angle $p/q = P(1)/Q(1)$.

Si $P/Q$ et $P'/Q'$ sont deux fractions adjacentes, $P'/Q'$ étant la fraction de droite, on a la relation

$$(2.1) \qquad P'Q - PQ' = \gamma^{\deg(Q)}.$$

Elle se démontre par récurrence : supposons que le couple $(P/Q, P'/Q')$ de fractions adjacentes vérifie la relation (2.1). Considérons $P''/Q''$ définie par

$$\frac{P''(\gamma)}{Q''(\gamma)} = \frac{P'(\gamma) + \gamma^{\deg(Q') + 1} P(\gamma)}{Q'(\gamma) + \gamma^{\deg(Q') + 1} Q(\gamma)}.$$

Un calcul immédiat montre que les nouveaux couples adjacents $(P/Q, P''/Q'')$ et $(P''/Q'', P'/Q')$ vérifient (2.1).

*Etude algébrique de la dynamique des transformations $T_{\gamma,\alpha}$.*

Reprenons la remarque 1.1. Dans le cas des entiers $(\gamma = 1)$, étant donnée une fraction irréductible $p/q$, la dynamique de la rotation $x \mapsto x + p/q \bmod 1$ peut être décrite de la façon suivante.

Pour $l = 1, \dots, q$, effectuons la division euclidienne de $lp$ par $q$ :

$$lp = qs_l + r_l, \quad 0 \le r_l < q.$$

Le passage de $l-1$ à $l$ est donné par la suite $(\varepsilon_l)$ correspondant à $p/q$ :

$$s_l = s_{l-1} + \varepsilon_l, \quad r_l = r_{l-1} + p - \varepsilon_l q.$$

Cette assertion peut être démontrée par récurrence en mettant en parallèle le procédé de concaténation (suivant l'ordre correspondant à l'ordre sur l'intervalle entre les fractions adjacentes) et le fait que la dynamique de la rotation par $p''/q''$ est d'abord (pour les $q$ premiers itérés) celle de la rotation par $p/q$, puis (pour les $q'$ derniers itérés), celle de la rotation par $p'/q'$ (ceci peut être montré aisément par un raisonnement dynamique, ou arithmétique (basé sur la relation $q'p - qp' = 1$)). La proposition 2.2 et le corollaire 2.1 qui suivent montrent que cette observation s'étend aux polynômes de Farey et à la dynamique des transformations $T_{\gamma,\alpha}$. Nous en déduisons une preuve algébrique du théorème 1.1 démontré dans [2] au moyen d'un raisonnement dynamique.
Soit $P''/Q'' = (P' + \gamma^{q'} P)/(Q' + \gamma^{q'} Q)$ la fraction médiant de deux fractions adjacentes $P/Q$ et $P'/Q'$. Dans la preuve de la proposition 2.1, nous utiliserons les relations (2.2) suivantes, déduites de (2.1) avec $q = \deg(Q)+1$, $q' = \deg(Q') + 1$ :

$$ (2.2') \qquad \frac{P''}{Q''} = \frac{P}{Q} + \frac{\gamma^{q-1}}{QQ''}, $$

$$ (2.2'') \qquad \frac{P''}{Q''} = \frac{P'}{Q'} - \frac{\gamma^{q+q'-1}}{Q'Q''}. $$

Pour des entiers $l$ et $l'$ vérifiant $1 \le l < q + q'$ et $1 \le l' < q'$, notons $S_l''$ et $R_l''$ le quotient et le reste de la division de $(1+\dots+\gamma^{l-1})P''$ par $Q''$, $S_l$ et $R_l$ (resp. $S_l'$ et $R_l'$) le quotient et le reste de la division de $(1+\dots+\gamma^{l-1})P$ par $Q$ (resp. $(1+\dots+\gamma^{l'-1})P'$ par $Q'$).

**PROPOSITION 2.1.** (1) *Cas* $1 \le l \le q$. Soit $r = l \bmod q$. On a les relations (2.3) :

$$ (2.3') \qquad S_l'' = S_l, $$

$$ (2.3'') \qquad R_l'' = R_l + \gamma^{q-1}(1 - \gamma^r + \gamma T'), \quad \text{pour } r \neq 0, $$

où $T'$ est le reste de la division de $(1 + \gamma + \dots + \gamma^{r-1})P'$ par $Q'$. Dans le cas $r=0$, l'expression de $R_l''$ devient $R_l'' = R_l + \gamma^{q-1}Q'$.

(2) *Cas* $q < l = l' + q < q' + q$. Soit $r = l' \bmod q$. On a les relations (2.4) :

$$ (2.4') \qquad S_l'' = S_{l'} + \gamma^{l'} P, $$

$$ (2.4'') \qquad R_l'' = R_{l'} + \gamma^{l-1} + \gamma^{q'} T, \quad \text{pour } r \neq 0, $$

où $T$ est le reste de la division de $(1 + \gamma + \dots + \gamma^{r-1})P$ par $Q$. Dans le cas $r=0$, l'expression de $R_l''$ devient $R_l'' = R_{l'} + \gamma^{l-1}$.

**Preuve.** (1) Notons, pour simplifier, $S'' = S_l''$, $R'' = R_l''$, $S = S_l$, $R = R_l$. On a

$$ \begin{aligned} S'' + \frac{R''}{Q''} &= (1 + \dots + \gamma^{l-1}) \frac{P''}{Q''} \\ &= (1 + \dots + \gamma^{l-1}) \left[ \frac{P}{Q} + \frac{\gamma^{q-1}}{QQ''} \right] \\ &= S + \frac{R}{Q} + (1 + \dots + \gamma^{l-1}) \frac{\gamma^{q-1}}{QQ''}. \end{aligned} $$

D'où

$$ (S - S'')QQ'' = -(1 + \dots + \gamma^{l-1})\gamma^{q-1} + R''Q - RQ''. $$

Chacun des polynômes dans l'expression à droite est de degré $< 2q + q' - 2$. Comme $QQ''$ est de degré $2q + q' - 2$, on a nécessairement $S = S''$.
Il en résulte

$$
\begin{align*}
R'' &= R \frac{Q''}{Q} + \frac{\gamma^{q-1}}{Q} (1 + \dots + \gamma^{l-1}) \\
    &= R + \frac{\gamma^{q-1}}{Q} (1 + \dots + \gamma^{l-1} + \gamma R Q').
\end{align*}
$$

D'autre part, $R = (1 + \dots + \gamma^{l-1})P - SQ$ et $1 - \gamma^q = (1 - \gamma)Q$; d'où, en
utilisant (2.1),

$$
\begin{align*}
1 + \dots + \gamma^{l-1} + \gamma R Q' &= (1 + \dots + \gamma^{l-1})(1 + \gamma P Q') - \gamma S Q Q' \\
&= (1 + \dots + \gamma^{l-1})(1 - \gamma^q + \gamma P' Q) - \gamma S Q Q',
\end{align*}
$$

et donc

$$
R'' = R + \gamma^{q-1}[(1 + \dots + \gamma^{l-1})(1 - \gamma + \gamma P') - \gamma SQ'].
$$

Soient, comme définis dans l'énoncé, $r$ le reste de la division de $l$ par $q'$ :
$l = uq' + r$ et, pour $r \neq 0$, $T'$ le reste de la division de $(1 + \dots + \gamma^{r-1})P'$
par $Q'$. On a

$$
(2.5) \qquad (1 + \dots + \gamma^{l-1}) P' = \Sigma' Q' + T',
$$

avec $\deg(T') < \deg(Q') = q' - 1$.

Si l'on reporte la relation (2.5) dans le crochet, on obtient donc

$$
\begin{align*}
[ ] &= (1 + \dots + \gamma^{l-1})(1 - \gamma + \gamma P') - \gamma SQ' \\
   &= 1 - \gamma^l + \gamma T' + \gamma (\Sigma' - S) Q' \\
   &= 1 - \gamma^r + \gamma T' + \gamma Q' (\Sigma' - S) + (\gamma^r - \gamma^l).
\end{align*}
$$

Or $\gamma^r - \gamma^l$ est un multiple de $\gamma^r Q'$, donc de $\gamma Q'$, car $r \ge 1$. Comme le polynôme dans le crochet doit être de degré $\le q' - 1$, on a

$$
R'' = R + \gamma^{q-1}(1 - \gamma^r + \gamma T'),
$$

avec $\deg(R) < q - 1$.

Pour $r=0$, le calcul est immédiat.

(2) On a $1 \le l' < q'$. Notons $S' = S_{l'}'$, $R' = R_{l'}'$ et posons $S'' = S_0 + \gamma l' P$.
Le polynôme $S_0$ est de degré au plus $q + q' - 1$. On a

$$
\begin{align*}
S'' + \frac{R''}{Q''} &= (1 + \dots + \gamma^{l-1}) \frac{P''}{Q''} \\
&= (1 + \dots + \gamma^{l'-1}) \left[ \frac{P'}{Q'} - \frac{\gamma^{q+q'-1}}{Q'Q''} \right] + \gamma^{l'} (1 + \dots + \gamma^{q-1}) \frac{P''}{Q''} \\
&= S' + \frac{R'}{Q'} - (1 + \dots + \gamma^{l'-1}) \frac{\gamma^{q+q'-1}}{Q'Q''} + \gamma^{l'} Q \frac{P''}{Q''}.
\end{align*}
$$
Il en résulte

$$
\begin{align*}
Q''Q'(S_0 - S') &= R'Q'' - Q'R'' - (1 + \dots + \gamma^{l'-1})\gamma^{q+q'-1} \\
&\quad + \gamma^{l'}Q'[QP'' - Q''P] \\
&= R'Q'' - Q'R'' - (1 + \dots + \gamma^{l'-1})\gamma^{q+q'-1} + \gamma^{l'+q-1}Q'.
\end{align*}
$$

Comme le polynôme $Q''Q'$ est de degré $q + 2q' - 2$ et que le polynôme à droite est de degré $< q + 2q' - 2$, on a $S' = S_0$ et donc

$$
\begin{gather*}
S'' = S' + \gamma^{l'} P, \\
Q'R'' = R'Q'' - (1 + \dots + \gamma^{l'-1})\gamma^{q+q'-1} + \gamma^{l'+q-1}Q'.
\end{gather*}
$$

Soient, comme définis dans l'énoncé, $r$ le reste de la division de $l'$ par $q$ :
$l' = uq + r$ et, pour $r \neq 0$, $T$ le reste de la division de $(1 + \gamma + \dots + \gamma^{r-1})P$
par $Q$. On a

$$
(2.6) \qquad (1 + \dots + \gamma^{l'-1})P = \Sigma Q + T,
$$

avec $\deg(T) < \deg(Q) = q - 1$.

En utilisant (2.1), $Q'' = Q' + \gamma^{q'}Q$, et le fait que $R'$ est le reste de la division de $(1 + \dots + \gamma^{l'-1})P'$ par $Q'$, on obtient

$$
\begin{align*}
R'' &= R' + \gamma^{l-1} + \frac{\gamma^{q'-1}}{Q'} [-\gamma^q (1 + \dots + \gamma^{l'-1}) + \gamma R'Q] \\
&= R' + \gamma^{l-1} + \gamma^{q'-1} [(1 + \dots + \gamma^{l'-1})\gamma P - \gamma S'Q].
\end{align*}
$$

En réécrivant le crochet à l'aide de (2.6), et comme l'expression dans le
crochet doit être de degré $\le q-1$, on trouve $\Sigma = S'$, et le crochet se réduit
à $T$; d'où

$$
R'' = R' + \gamma^{l-1} + \gamma^{q'} T.
$$

Comme précédemment, pour $r=0$, le calcul est immédiat. $\blacksquare$

On en déduit :

PROPOSITION 2.2. Soit $P(\gamma)/Q(\gamma)$ une fraction rationnelle de Farey, avec $Q(\gamma) = 1 + \dots + \gamma^{q-1}$ de degré $q-1$ et $P(\gamma) = \sum_{k=0}^{q-1} \varepsilon_{q-k} \gamma^k$. Soit $1 \le l \le q$. Le quotient $S_l$ de la division euclidienne de $(1 + \dots + \gamma^{l-1})P(\gamma)$ par $Q(\gamma)$,

$$
(2.7) \quad (1 + \dots + \gamma^{l-1})P(\gamma) = S_l(\gamma)Q(\gamma) + R_l(\gamma), \quad \deg(R_l) < \deg(Q), \\
\text{est donné par}
$$

$$
(2.8) \qquad S_l(\gamma) = \sum_{k=0}^{l-1} \varepsilon_{l-k} \gamma^k.
$$
Preuve. Le résultat est clair pour $l = q$ car $S_q = P$. D'après le procédé de construction des suites $(\varepsilon_k)$ par concaténation, l'assertion résulte, par récurrence, de la proposition 2.1 et du lemme 1.2. ■

COROLLAIRE 2.1. Soit $P(\gamma)/Q(\gamma)$ une fraction rationnelle de Farey. Pour $1 \le l < q$, le reste $R_l$ de la division euclidienne de $(1 + \dots + \gamma^{l-1})P$ par $Q$ est un polynôme à coefficients $0$ ou $1$, de degré $< q - 1$.

Preuve. En développant l'expression (2.7), on voit que le coefficient du terme en $\gamma^{l-1}$ dans le reste $R_l$ est donné par $(\varepsilon_q + \dots + \varepsilon_{q-l+1}) - (\varepsilon_1 + \dots + \varepsilon_l)$. Par application du lemme 1.1, cette différence se réduit à $\varepsilon_q - \varepsilon_1$. Le coefficient du terme en $\gamma^{l-1}$ dans le reste $R_l$ est donc 1.

Raisonnons maintenant par récurrence en utilisant la proposition 2.1 et en considérant deux fractions adjacentes $P/Q$ et $P'/Q'$. Les notations utilisées dans la suite de la preuve sont celles de cette proposition.

(1) Cas $1 \le l \le q$. Dans (2.3), on a $\deg(R_l) < q - 1$ et le deuxième terme est de degré $\ge q - 1$. Par hypothèse de récurrence, $R_l$ est à coefficients 0 ou 1, ainsi que $T'$. Il en est donc de même pour $1 - \gamma^r + \gamma T'$, puisque l'on sait déjà que le coefficient du terme de degré $r - 1$ dans $T'$ est 1. Tous les coefficients de $R_l''$ sont donc 0 ou 1.

(2) Cas $q < l < q + q' - 1$. D'après l'expression de $R_l''$ dans (2.4), où $\deg(R_l'') < q' - 1$, on a comme précédemment le résultat en utilisant l'hypothèse de récurrence et le fait que l'on sait déjà que le coefficient du terme de degré $l - 1$ dans $R_l''$ est 1. ■

Montrons pour finir cette partie comment les résultats précédents permettent algébriquement de retrouver le théorème 1.1 établi dans [2].

La proposition 2.2 et le corollaire 2.1 montrent que l'observation concernant les suites $(\varepsilon_l)$ s'étend aux polynômes de Farey et à la dynamique des transformations $T_{\gamma,\alpha}$. On a en effet, avec les notations de la proposition 2.2, pour $1 \le l \le q$,

$$T_{\gamma, P(\gamma)/Q(\gamma)}^{l}(0) = \frac{R_l(\gamma)}{1 + \dots + \gamma^{q-1}} \in [0, 1].$$

En particulier, $T_{\gamma,P(\gamma)/Q(\gamma)}^q(0) = 0$. Ainsi, d'après (2.8), la dynamique de la transformation $T_{\gamma,P(\gamma)/Q(\gamma)}$ sur l'orbite de 0 est celle de $T_{1,p/q}$ sur l'orbite de 0. En notant $A_0$ et $A_1$ les transformations $A_0 : x \mapsto \gamma x + \alpha$ et $A_1 : x \mapsto \gamma x + \alpha - 1$, on obtient comme dans (1.2)

$$(2.9) \qquad T_{\gamma, P(\gamma)/Q(\gamma)}^{n}(0) = A_{\varepsilon_n^{p/q}} \dots A_{\varepsilon_1^{p/q}}(0) \quad \text{pour tout } n \ge 1.$$

D'autre part, avec les notations du théorème 1.1, on a, pour $1 \le l \le q$,

$$T_{\gamma, (P_q^p(\gamma) + \gamma^{q-1} - \gamma^q)/(1 + \dots + \gamma^{q-1})}^l(0) = \frac{R_l(\gamma) + \gamma^{q-1} - \gamma^{q+l-1}}{1 + \dots + \gamma^{q-1}} \in [0, 1].$$
et, plus généralement, pour tout entier $n \ge 1$ :

$$T_{\gamma, (P_q^p(\gamma) + \gamma^{q-1} - \gamma^q)/(1+\dots+\gamma^{q-1})}^n(0) = \frac{R_{n \bmod q}(\gamma) + \gamma^{q-1} - \gamma^{q+n-1}}{1 + \dots + \gamma^{q-1}} \in [0, 1].$$

L'assertion (2.9) s'étend donc à toutes les valeurs du paramètre $\alpha$ dans l'intervalle $I_q^p(\gamma)$. Notons par ailleurs que, pour tout $x \in [0, 1[$, on a

$$\mathrm{dist}(T_{\gamma, \alpha}^n(x), \{0, T_{\gamma, \alpha}, \dots, T_{\gamma, \alpha}^n(0)\}) \le \gamma^n.$$

**3. Généralisation au cas de deux pentes distinctes.** Après avoir donné, dans la partie précédente, une preuve purement algébrique du théorème 1.1, nous en présentons une généralisation au cas de deux pentes distinctes.

Soient $\theta \in [0, 1]$, $u, v$, avec $0 < u < 1 - \theta < v < 1$, trois paramètres. Notons $\gamma_0, \alpha_0, \gamma_1, \alpha_1$ les quatre paramètres définis par

$$\gamma_0 = (1 - v)/\theta, \quad \alpha_0 = v, \quad \gamma_1 = u/(1 - \theta), \quad \alpha_1 = -u\theta/(1 - \theta).$$

Ils vérifient $-1 < \alpha_1 < 0 < \alpha_0, \gamma_0, \gamma_1 < 1$ et $\alpha_0 > \alpha_1 + \gamma_1$, ainsi que la relation

$$(3.1) \qquad \alpha_1 \gamma_0 = (\alpha_0 - 1) \gamma_1.$$

On considère les applications

$$[0, \theta] \xrightarrow{A_{\gamma_0, \alpha_0}} [v, 1], \quad \text{où } A_{\gamma_0, \alpha_0}(x) = \gamma_0 x + \alpha_0,$$

$$[\theta, 1] \xrightarrow{A_{\gamma_1, \alpha_1}} [0, u], \quad \text{où } A_{\gamma_1, \alpha_1}(x) = \gamma_1 x + \alpha_1.$$

Nous noterons plus simplement $A_0$ et $A_1$ ces deux affinités.

La transformation $T_{\gamma_0, \gamma_1, \alpha_0} : X \to X$, que l'on note simplement $T$ quand il n'y a pas d'ambiguïté, est définie comme l'unique application qui coïncide avec $A_0$ sur $[0, \theta[$ et avec $A_1$ sur $[\theta, 1[$.

On note $S$ la famille de ces transformations $T_{\gamma_0, \gamma_1, \alpha_0}$ contractantes, linéaires par morceaux, de l'intervalle $[0, 1[$ dans lui-même. Les transformations $T_{\gamma, \alpha}$ introduites plus haut appartiennent à cette classe (égalité des deux pentes).

Le comportement asymptotique de l'itération de $T_{\gamma_0, \gamma_1, \alpha_0}$ est relié à la position du point critique $\theta = (1 - \alpha_0)/\gamma_0$. Plus précisément, on a le résultat suivant.

**PROPOSITION 3.1.** Soit $n_0 = \inf\{n \ge 0 \mid \theta \notin T^n(X)\} + 1$. Pour tout $n < n_0$, $T^n(X)$ est composé d'exactement $n + 1$ intervalles disjoints. Si $n_0$ est fini, pour tout $n \ge n_0$, $T^n(X)$ est composé d'exactement $n_0$ intervalles disjoints.
Preuve. Soit $n \ge 0$. Supposons que $T^n(X)$ soit la réunion disjointe de $l$ intervalles $I_1, \dots, I_l$. Alors, si $\theta \in I_l$, on a

$$T^{n+1}(X) = \bigcup_{i=1}^{l-1} T(I_i) \cup J_1 \cup J_2,$$

où les $T(I_i)$ sont des intervalles et où $J_1$ et $J_2$ sont des intervalles respectivement de la forme $[0, \cdot[$ et $[\cdot, 1[$. Ces $l+1$ intervalles sont disjoints par injectivité de $T$; dans ce cas, une itération supplémentaire a donné naissance à un intervalle supplémentaire. Si $\theta \notin T^n(X)$, alors $T^{n+1}(X)$ est la réunion disjointe des $l$ intervalles $T(I_i)$. On conclut en notant que $T^0(X) = X$ se compose d'un unique intervalle. ■

Nous ne présentons pas de preuve de l'énoncé suivant, qui généralise le théorème 1.1. Notons simplement que l'on peut le démontrer soit à l'aide d'un raisonnement dynamique (il s'agit de la méthode esquissée dans [2]), soit à partir d'une étude algébrique semblable à celle détaillée dans la partie 2.

### THÉORÈME 3.1. Soient $\gamma_0$ et $\gamma_1$ vérifiant $0 < \gamma_0, \gamma_1 \le 1$. A tout rationnel $p/q$ irréductible, $0 < p \le q$, correspond un intervalle compact $I_q^p(\gamma_0, \gamma_1)$ tel que, si $\alpha_0 \in I_q^p(\gamma_0, \gamma_1)$, l'application $T_{\gamma_0, \gamma_1, \alpha_0}$ est semi-conjuguée à la rotation d'angle $p/q$. De plus, si l'on note $\varepsilon_l = \varepsilon_l^{p/q}$, on a

$$I_q^p(\gamma_0, \gamma_1) = \left[ \frac{A_q^p(\gamma_0, \gamma_1)}{B_q^p(\gamma_0, \gamma_1)}, \frac{C_q^p(\gamma_0, \gamma_1)}{D_q^p(\gamma_0, \gamma_1)} \right],$$

où

$$A_q^p(\gamma_0, \gamma_1) = 1 + \sum_{k=1}^{q-1} \varepsilon_k \gamma_{\varepsilon_{q-1}} \dots \gamma_{\varepsilon_k},$$

$$B_q^p(\gamma_0, \gamma_1) = 1 + \sum_{k=1}^{q-1} \gamma_{\varepsilon_{q-1}} \dots \gamma_{\varepsilon_k},$$

$$C_q^p(\gamma_0, \gamma_1) = 1 + \sum_{k=2}^{q} \varepsilon_k \gamma_{\varepsilon_2} \dots \gamma_{\varepsilon_k} - \gamma_{\varepsilon_1} \dots \gamma_{\varepsilon_q},$$

$$D_q^p(\gamma_0, \gamma_1) = 1 + \sum_{k=2}^{q} \gamma_{\varepsilon_2} \dots \gamma_{\varepsilon_k}.$$

### REMARQUES. On observe que l'intervalle $I_q^p(1, 1)$ est réduit au rationnel $p/q$.

Il n'est pas difficile de montrer que l'on peut construire les intervalles $I_q^p(\gamma_0, \gamma_1)$ par récurrence, en utilisant une généralisation du procédé de Farey. Plus précisément, si $p/q$ et $p'/q'$ sont deux rationnels de $]0, 1[$ vérifiant
$p'q - pq' = 1$, alors on détermine $I_{q+q'}^{p+p'}$ à partir de $\text{Min}(I_q^p) =: P/Q$ et $\text{Min}(I_{q'}^{p'}) =: P'/Q'$ de la manière suivante :

$$I_{q+q'}^{p+p'} = \left[ \frac{P' + \gamma_1^{p'} \gamma_0^{q'-p'} P}{Q' + \gamma_1^{p'} \gamma_0^{q'-p'} Q}, \frac{P + \gamma_1^p \gamma_0^{q-p} P'}{Q + \gamma_1^p \gamma_0^{q-p} Q'} \right],$$

sauf si $P/Q = 0/1$ ou $P'/Q' = 1/1$, auxquels cas on a, respectivement,

$$\text{Min}(I_{q+q'}^{p+p'}) = 1/(1 + \gamma_0 + \dots + \gamma_0^{q'}),$$

$$\text{Max}(I_{q+q'}^{p+p'}) = (1 + \gamma_1 P)/(1 + \gamma_1 Q).$$

En utilisant cette construction et en suivant le raisonnement détaillé dans la partie 4 de [2], on peut faire correspondre à tout irrationnel $\alpha \in [0, 1]$ et à tout couple $(\gamma_0, \gamma_1) \in ]0, 1]^2$ un unique réel $\tau_{\gamma_0, \gamma_1}(\alpha)$ tel que l'application $T_{\gamma_0, \gamma_1, \tau_{\gamma_0, \gamma_1}(\alpha)}$ soit semi-conjuguée à la rotation d'angle $\alpha$.

**4. Un algorithme de type “fractions continues”.** Contrairement à la classe des transformations $T_{\gamma, \alpha}$, la classe $S$ des transformations “à deux pentes” $T_{\gamma_0, \gamma_1, \alpha_0}$ introduite dans la partie 2 est stable par induction sur l'intervalle $[\theta, 1]$, $\theta$ étant le point critique. En notant $T$ la transformation $T_{\gamma_0, \gamma_1, \alpha_0}$, on observe en effet que la transformation induite par $T$ sur l'intervalle $[\theta, 1]$ est de la même forme. Comme dans le cas des rotations, en utilisant l'induction sur $[\theta, 1]$, on peut définir un algorithme, analogue à celui des fractions continues, permettant d'étudier la structure des transformations $T$.

S'il n'existe pas de point critique dans l'intervalle $[0, 1]$, la transformation $T$ contracte l'intervalle $[0, 1]$ et les itérés de $T$ convergent vers son unique point fixe. La condition d'existence d'un point critique $\theta$ dans l'intervalle $[0, 1]$ est $\gamma_0 + \alpha_0 > 1$. On itère le procédé d'induction tant que la transformation induite possède un point critique.

*Calcul de la transformation induite.* La transformation induite sur $[\theta, 1]$ est de la forme :

$$[\theta_1, 1] \xrightarrow{A_0^{n-1} A_1} [\theta, u_1], \quad [\theta, \theta_1] \xrightarrow{A_0^n A_1} [v_1, 1].$$

Les valeurs de $u_1, v_1, \theta_1$ sont données par

$$u_1 = \alpha_0(1 + \gamma_0 + \dots + \gamma_0^{n-2}) + \gamma_0^{n-1}(\alpha_1 + \gamma_1),$$

$$v_1 = \gamma_0^n \gamma_1 \theta + \alpha_0(1 + \gamma_0 + \dots + \gamma_0^{n-1}) + \gamma_0^n \alpha_1 \\ = \alpha_0(1 + \gamma_0 + \dots + \gamma_0^{n-1}),$$

$$\theta_1 = \gamma_0^{-n} \gamma_1^{-1} (1 - (\alpha_0(1 + \gamma_0 + \dots + \gamma_0^{n-1}) + \alpha_1 \gamma_0^n)).$$
Après normalisation de l'intervalle $[\theta, 1]$ en $[0, 1]$, on obtient la paramétrisation de la transformation $T'$ déduite de $T$ par induction :

$$ \theta' = \frac{\theta_1 - \theta}{1 - \theta}, \quad u' = \frac{u_1 - \theta}{1 - \theta}, \quad v' = \frac{v_1 - \theta}{1 - \theta}. $$

Les deux nouvelles affinités définissant la transformation induite sont donc $A'_0 = A_{\gamma'_0, \alpha'_0}$ et $A'_1 = A_{\gamma'_1, \alpha'_1}$ avec

$$ \gamma'_0 = \gamma_0^n \gamma_1, \quad \alpha'_0 = \frac{\alpha_0(1 + \gamma_0 + \dots + \gamma_0^n) - 1}{\gamma_0 + \alpha_0 - 1}, $$

$$ \gamma'_1 = \gamma_0^{n-1} \gamma_1, \quad \alpha'_1 = \frac{\alpha_0(1 + \gamma_0 + \dots + \gamma_0^{n-1}) - 1}{\gamma_0 + \alpha_0 - 1}. $$

Dans ces relations, l'entier $n$ est défini par la condition $A_0^{n-1}(0) \le \theta < A_0^n(0)$, soit

$$ \alpha_0(1 + \gamma_0 + \dots + \gamma_0^{n-2}) \le \frac{1 - \alpha}{\gamma_0} < \alpha_0(1 + \gamma_0 + \dots + \gamma_0^{n-1}), $$

ou encore

$$ \alpha_0(1 + \gamma_0 + \dots + \gamma_0^{n-1}) \le 1 < \alpha_0(1 + \gamma_0 + \dots + \gamma_0^n). $$

On a bien la relation (3.1) : $\alpha'_0\gamma'_1 - \alpha'_1\gamma'_0 = \gamma'_1$.

Le nouveau point critique est

$$ \theta' = \frac{1 - \alpha_0(1 + \gamma_0 + \dots + \gamma_0^{n-1})}{\gamma_0^{n-1}\gamma_1(\gamma_0 + \alpha_0 - 1)}. $$

Le rapport

$$ \frac{\gamma_0 \alpha_0}{\gamma_1 (\alpha_0 + \gamma_0 - 1)} $$

reste invariant par passage aux nouveaux paramètres.

On utilise un développement du type “fraction continue” avec signe, c'est-à-dire un développement de la forme

$$ p_n/q_n = \frac{1}{b_1 - \frac{1}{b_2 - \frac{1}{\ddots}}} $$

Ce développement correspond à la rotation induite par $\alpha$ sur l'intervalle $[\theta, 1]$, avec $\theta = 1 - \alpha$.

Les paramètres $\alpha, \gamma$ étant fixés, l'algorithme suivant donne le développement du nombre de rotation de la transformation (les termes de la fraction continue sont les valeurs successivement prises par la variable $b$). Si $\gamma < 1$ est fixé, la somme des longueurs des intervalles $I_q^p(\gamma)$ définis dans le théorème 1.1 est égale à 1; par conséquent, pour tout $\gamma < 1$, l'algorithme s'arrête
pour presque tout $\alpha$ après un nombre fini de pas (cas d'une orbite périodique
attractive).

(* $\alpha$ et $\gamma$ sont les paramètres de la transformation $T_{\gamma,\alpha}$ *)

$\gamma_1 := \gamma;$

tant que $\alpha + \gamma > 1$ faire

début

$u := 1;$

$r := 1;$

$z := \gamma;$

$\beta := 1/\alpha;$

$b := 1;$

tant que $u < \beta$ faire

début

$b := b + 1;$

$u := 1 + \gamma * u;$

$r := r * \gamma;$

fin;

$a := (a * u - 1)/(\gamma + \alpha - 1);$

$\gamma := r * \gamma_1;$

$\gamma_1 := \gamma/z;$

afficher(b);

fin;

**5. Questions.** Différentes généralisations du problème traité peuvent être envisagées.

(1) Le système récursif suivant est étudié en traitement du signal et en particulier dans des algorithmes de quantification :

$$
u_n = \{ \gamma u_{n-1} + \epsilon_n \},
$$

où $\gamma$ est un paramètre dépendant du dispositif matériel, $\epsilon_n$ est l'entrée. Pour des raisons physiques, la constante $\gamma$ vérifie $0 < \gamma < 1$.

Dans ce qui précède, nous avons considéré le cas d'une entrée constante
(le paramètre $\alpha$). On peut se placer dans le cas où l'entrée n'est plus con-
stante, mais est un processus stationnaire. Cela revient à se donner un
système dynamique $(X, T, \mu)$, $T$ étant une transformation sur un espace
$X$ laissant invariante une mesure de probabilité $\mu$, une fonction $\phi$ sur $X$ et
une constante $\gamma \in [0, 1[$. Le processus stationnaire en entrée est alors la suite
$(\phi(T^n x))_{n \ge 0}, x \in X$. Le cas $\gamma = 1$ est celui d'une extension isométrique de
systèmes dynamiques. Une question posée en traitement du signal est la
nature spectrale du processus de sortie $(u_n)$, ce qui conduit à l'étude du
comportement asymptotique de l'itération de la transformation :

$$ (x, y) \to S(x, y) = (Tx, \{\gamma y + \phi(x)\}), $$

pour $\gamma < 1$.

On pourra prendre, par exemple, $\phi(x) = x$, $\phi(x) = \sin 2\pi x$, ou encore une entrée localement constante (par exemple $\phi$ à deux valeurs).

(2) Une autre généralisation consiste à étudier la dynamique d'une transformation localement linéaire et contractante. Le cas isométrique serait celui des échanges d'intervalle s.

Le problème posé est de déterminer, de façon algorithmique, les valeurs des paramètres pour lesquelles la dynamique est non dégénérée et semi-conjuguée à celle d'un échange d'intervalle s.

(3) Cas de la dimension $d > 1$. On se donne une matrice $\Gamma$ contractante de dimension $d \times d$ et un vecteur $v$ de dimension $d$. Le problème consiste à étudier la dynamique de l'application :

$$ x \in [0, 1]^d \to \Gamma x + v \bmod 1. $$

## Références bibliographiques

[1] V. I. Arnold, *Chapitres supplémentaires de la théorie des équations différentielles ordinaires*, Mir, Moscou, 1980.

[2] Y. Bugeaud, *Dynamique de certaines applications contractantes linéaires par morceaux sur $[0, 1[$*, C. R. Acad. Sci. Paris Sér. I 317 (1993), 575-578.

[3] O. Feely and L. O. Chua, *The effect of integrator leak in $\Sigma - \Delta$ modulation*, IEEE Trans. Circuits Systems 38 (1991), 1293-1305.

[4] G. H. Hardy and E. M. Wright, *An Introduction to the Theory of Numbers*, Clarendon Press, 1979.

[5] W. de Melo and S. van Strien, *One-Dimensional Dynamics*, Ergeb. Math. Grenzgeb. (3) 25, Springer, 1993.

Université Louis Pasteur
7 rue René Descartes
67084 Strasbourg Cedex, France
E-mail: bugeaud@irma.u-strasbourg.fr

Université de Rennes I
Campus de Beaulieu
35042 Rennes Cedex, France
E-mail: Jean-Pierre.Conze@univ-rennes1.fr

Reçu le 7.4.1997
et révisé le 15.4.1998

(3161)