Diviser pour régner. Suites 2-rationnelles.

Diviser pour régner
Suites 2-rationnelles

Page de Philippe Dumas
Diviser pour régner | Maple | Livres
Publications | Adresse | English version

Introduction
Une idée fondamentale
Complexité et récurrences
Suites 2-rationnelles
Comportement asymptotique
Références

Parmi les suites mahlériennes, nous allons distinguer une classe particulière, la classe des suites rationnelle en base 2 ou encore 2-rationnelles. On peut définir une suite 2-rationnelle (u_n) par la donnée d'une représentation linéaire. Une telle représentation consiste en une matrice ligne $\lambda$ , une matrice colonne $\gamma$ et deux matrices carrées A₀ et A₁ dont les tailles sont respectivement $1\times N$ , $N\times 1$ et $N\times N$ pour un certain entier N. Si l'entier n a pour écriture binaire

$\begin{displaymath} n=(n_{\ell}\ldots n_0)_2,\end{displaymath}$

la valeur de la suite pour l'entier n est

$\begin{displaymath} u_n=\lambda A_{n_{\ell}}\dotsb A_{n_0}\gamma.\end{displaymath}$

La notion de suite 2-rationnelle ou plus généralement de suite B-rationnelle (on imagine la définition) est une extension directe de la notion de suite rationnelle, c'est-à-dire de suite dont la série génératrice est une fraction rationnelle (n'admettant pas le pôle 0). Cette notion apparaît dans [4] où l'on parle de suite 2-régulière, mais cette terminologie nous paraît trop floue, le mot régulier ayant de multiples sens. On trouve dans [4] de nombreux exemples de suites 2-rationnelles. Indiquons la suite $(\nu_n)$ qui donne le nombre de 1 dans l'écriture binaire de n. Cette suite admet la représentation linéaire

$\begin{displaymath} \lambda=\left(\begin{array} {cc} 0&1 \end{array}\right),\qquad \gamma=\left(\begin{array} {c} 1\\ 0 \end{array}\right),\end{displaymath}$

$\begin{displaymath} A_0=\left(\begin{array} {cc} 1&0\\ 0&1 \end{array}\right),... ...d A_1=\left(\begin{array} {cc} 0&-1\\ 1&2 \end{array}\right).\end{displaymath}$

Caractérisation des suites rationnelles en base 2. Nous avons défini les suites 2-rationnelles par la donnée d'une représentation linéaire; dans la nature les exemples ne sont pas donnés de cette façon et on doit donc prouver la 2-régularité. Souvent on dispose d'une récurrence diviser pour régner et on peut alors appliquer le résultat suivant [12]. Si la série formelle f(z) satisfait l'équation

$\begin{displaymath} z^af(z)+\sum_{k=1}^Nc_k(z)f(z^{2^k})=b(z),\end{displaymath}$

dans laquelle a est un entier et b(z) est une série 2-rationnelle, alors f(z) est 2-rationnelle. En terme de suites, les récurrences de la forme

$\begin{displaymath} f_{n-a}+\sum_{k=1}^N\sum_{\ell}c_{k,\ell}f_{(n-\ell)/2^k}=b_n\end{displaymath}$

fournissent des suites 2-rationnelles si (b_n) est 2-rationnelle. On notera que dans cette récurrence l'unique terme en n, f_n-a, est déterminé par les termes en n/2, n/4, etc. Il convient de donner un résultat un peu plus général car on rencontre fréquemment des récurrences définies suivant le résidu modulo une puissance de 2. Par exemple dans [35] l'étude d'un algorithme d'appariement euclidien amène à considérer une suite (c_n) qui vérifie

$\begin{displaymath} \left\{ \begin{array} {lcl} c_{4n} & = & a(c_{2n+1}+c_{2n-1}... ...+1})+1 \\ c_{4n+3} & = & a(c_{2n+2}+c_{2n+1})\end{array}\right.\end{displaymath}$

$\begin{displaymath} \left\{ \begin{array} {lcl} C_{4n} & = & a(C_{2n+1}+C_{2n-1}... ...+1})+1 \\ C_{4n+3} & = & a(C_{2n+2}+C_{2n+1})\end{array}\right.\end{displaymath}$

En passant aux séries génératrices f₀₀(z), f₀₁(z), f₁₀(z), f₁₁(z) respectivement associées aux suites (c_4n), (c_4n+1), (c_4n+2), (c_4n+3) puis au vecteur de séries formelles

$\begin{displaymath} F(z)=\left(\begin{array} {c} f_{00}(z)\\ f_{01}(z) \\ f_{10}(z) \\ f_{11}(z) \end{array}\right)\end{displaymath}$

on obtient l'équation

$\begin{displaymath} z\,F(z)=a\,C_1(z)F(z^2)+E(z)\end{displaymath}$

avec

$\begin{displaymath} C_1(z)=\left(\begin{array} {cccc} 0 & z(1+z) & 0 & z^2(1+z) ... ...in{array} {c} z/(1-z) \\ 0 \\ z/(1-z) \\ 0 \end{array}\right).\end{displaymath}$

On peut montrer qu'un vecteur de séries formelles F(z) vérifiant une équation de la forme

$\begin{displaymath} z^aF(z)+\sum_{k=1}^NC_k(z)F(z^{2^k})=B(z),\end{displaymath}$

dans laquelle a est un entier, les C_k(z) sont des matrices carrées à coefficients des polynômes et B(z) est un vecteur de séries formelles 2-rationnelles, a des composantes 2-rationnelles. À nouveau il faut remarquer que les suites associées satisfont une récurrence qui fournit le terme en n en fonction des termes en n/2, n/4, etc. On conclut ainsi que la suite (c_n) est 2-rationnelle.

De la même façon la suite définie par [21, p. 25]

$\begin{displaymath} f(n)=\max_k\left\{f(k)+f(n-k)+\min(k,n-k)\right\},\end{displaymath}$

qui intervient dans un algorithme sur les permutations, satisfait

$\begin{displaymath} f(2m)=2f(m)+m,\qquad f(2m+1)=f(m)+f(m+1)+m\,;\end{displaymath}$

elle est donc 2-rationnelle. En fait elle vaut

$\begin{displaymath} f(n)=\sum_{0\leq k<n}\nu_k,\end{displaymath}$

où $\nu_k$ est toujours le nombre de 1 dans l'écriture binaire de l'entier k.

Représentation linéaire. Sachant qu'une suite est 2-rationnelle, il est naturel d'en chercher une représentation linéaire. La 2-régularité d'une suite (u_n) exprime le fait que les suites (u_n), (u_2n), (u_2n+1), (u_4n), (u_4n+1), (u_4n+2), (u_4n+3), etc restent toutes dans un espace de dimension fini. Pour mettre ceci en valeur on associe à la suite un arbre binaire dans lequel la racine est étiqueté par la suite (u_n), plus généralement les noeuds sont étiquetés par les suites (u_2^kn+r), avec $0\leq r<2^k$ , et les fils du n $\oe$ ud étiqueté par (u_2^kn+r) sont étiquetés par (u_2^k+1n+r) et (u_2^k+1n+2^k+r). De plus les suites qui étiquettent les n $\oe$ uds internes de l'arbre sont linéairement indépendantes et les suites qui étiquettent les feuilles de l'arbres s'expriment linéairement en fonction des précédentes.

Appliquant cet algorithme on obtient pour la suite (T_n) qui donne le coût du tri-fusion dans le cas le pire l'arbre et le système de relations de récurrences suivants.

$\begin{displaymath} \begin{array} {rcl} T_{4n+1} & = & 4T_n-5 T_{2n}+ T_{2n+1}+2... ...& -36T_n +48T_{2n} -16T_{2n+1} -16T_{4n} +11T_{4n+2}\end{array}\end{displaymath}$

Ces relations de récurrence se traduisent en une représentation linéaire de dimension N=5.

Les séries 2-rationnelles sont en fait la traduction via la numération binaire des séries rationnelles sur l'alphabet $\{0,1\}$ de la théorie des langages formels[7]; à la série 2-rationnelle

$\begin{displaymath} f(z)=\sum_{n\geq0}f_nz^n\qquad\text{est associ\'ee la s\'erie}\qquad S=\sum_{n\geq0}f_n(n_{\ell}\ldots n_0)_2\end{displaymath}$

à support dans le langage rationnel des écritures binaires d'entiers $\varepsilon+1\{0,1\}^*$ . Une conséquence en est que pour une série 2-rationnelle f(z) la condensée

$\begin{displaymath} Kf(t)=\sum_{\ell\geq0}\sum_{2^{\ell}\leq n<2^{\ell+1}}f_nt^{\ell}\end{displaymath}$

est une série rationnelle au sens ordinaire.

Suite 2-automatique. Une autre manifestation de ce lien avec la théorie des langages est la notion de suite 2-automatique, qui est antérieure à la notion de suite 2-rationnelle [8]. Les suites 2-automatiques sont les suites 2-rationnelles qui ne prennent qu'un nombre fini de valeurs. Un exemple fera comprendre de quelle sorte d'automate il est question. La suite du pliage de papier est définie comme suit [10]. On plie une bande de papier une infinité de fois et toujours dans le même sens. Ensuite on déplie la bande et l'on observe les plis. Ils peuvent être entrants ou sortants et en codant convenablement ces plis par 0 ou 1, on obtient une suite qui commence par 1101100. Cette suite est 2-rationnelle car elle satisfait la récurrence

$\begin{displaymath} \left\{ \begin{array} {rcl} u_{4k} & = & 1, \\ u_{4k+2} & = & 0, \\ u_{2k+1} & = & u_k.\end{array}\right.\end{displaymath}$

Cette récurrence donne tout de suite le 2-automate du pliage de papier, représenté ci-dessous.

$\begin{picture} (400,200) \put(100,150){\circle{20}} \put(200,150){\circle{20}} ... ... \put(170,70){$1$} \put(255,55){\vector(1,1){15}} \put(270,70){$0$}\end{picture}$

On peut calculer la valeur de la suite sur un entier donné en utilisant le 2-automate. On part de l'état initial i indiqué par une flèche entrante et on suit les flèches selon les bits de l'entier en commençant par les bits de poids faibles; on regarde alors la valeur associée à l'état sur lequel on a terminé; c'est la valeur cherchée. Si l'on cherche la valeur de la suite pour l'entier treize, d'écriture binaire 1101, on passe successivement par les états i, i, a, c et c en suivant les flèches étiquetées 1, 0, 1 et enfin 1. La fonction de sortie donne alors la valeur . On trouvera dans [1] une présentation des différents problèmes liés aux suites automatiques.

Page précédente : Complexité et récurrences
Page suivante : Comportement asymptotique

Page précédente :	Complexité et récurrences
Page suivante :	Comportement asymptotique