Suite de Rudin-Shapiro

En mathématiques, et notamment en combinatoire des mots, la suite de Rudin-Shapiro, aussi connue sous le nom suite de Golay–Rudin–Shapiro est une suite automatique, nommée ainsi d'après Marcel Golay, Harold Shapiro, et Walter Rudin, qui ont étudié ses propriétés.

Définition

Chaque terme de la suite de Rudin-Shapiro est égal à 1 ou à -1. Le nModèle:E terme Modèle:Mvar est défini comme suit : soit

$n=\sum _{i=0}^k{\epsilon }_i{2}^i$

le développement binaire de Modèle:Mvar et soit

$a_n=\sum _{i=0}^{k-1}{\epsilon }_{i+1}{\epsilon }_i$.

Le nombre Modèle:Mvar est le nombre d’occurrences du facteur 11 dans l'écriture binaire de Modèle:Mvar. Alors Modèle:Mvar est défini par :

$b_n=(-1{)}^{a_n}$

Ainsi, Modèle:Math si le nombre de facteurs 11 dans l'écriture binaire de Modèle:Mvar est pair, et Modèle:Math sinon.

Par exemple, pour Modèle:Math, le développement binaire de 6 est 110, donc Modèle:Math et Modèle:Math. Pour Modèle:Math, le développement binaire est 111, il y a deux occurrences (chevauchantes) de 11, donc Modèle:Math et Modèle:Math.

Les premiers termes de la suite Modèle:Math sont (on commence à 0) :

0, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 1, 1, 1, 2, 3, ... (c'est la Modèle:OEIS)

et les termes correspondants de la suite Modèle:Math, qui constituent le début de la suite de Rudin-Shapiro, sont :

+1, +1, +1, -1, +1, +1, -1, +1, +1, +1, +1, -1, -1, -1, +1, -1, ... (c'est la Modèle:OEIS)

Propriétés

Automate de la suite de Rudin-Shapiro.

• La suite de Rudin–Shapiro est engendrée par un automate fini à quatre états. Dans l'automate, les états coloriés en jaune produisent un terme +1, et les états coloriés en rouge un terme -1. Les noms des états mémorisent la situation : Modèle:Mvar pour un nombre pair d'occurrences de 11, et Modèle:Mvar pour un nombre impair; cette lettre est suivie du dernier bit lu. Par exemple, pour l'entier 108, dont l'écriture binaire est 11011000, la suite des états parcourus est

$p0,p1,i1,i0,i1,p1,p0,p0,p0$.

La valeur calculée est +1.

• La suite de Rudin-Shapiro est (uniformément) morphique, comme toute suite automatique. Soit $A=\{a,b,c,d\}$ un alphabet à quatre lettres. Le morphisme 2-uniforme de Modèle:Math dans lui-même défini par :

$\begin{array}{ccc}a& \mapsto & ab\\ b& \mapsto & ac\\ c& \mapsto & db\\ d& \mapsto & dc\end{array}$

engendre, à partir de Modèle:Mvar, le mot infini :

$abacabdbabacdcac\cdots$

La suite de Rudin-Shapiro est obtenue en envoyant Modèle:Mvar et Modèle:Mvar sur +1, et Modèle:Mvar et Modèle:Mvar sur -1.

• La suite de Rudin-Shapiro est invariante par la substitution :

$\begin{array}{ccc}+1+1& \mapsto & +1+1+1-1\\ +1-1& \mapsto & +1+1-1+1\\ -1+1& \mapsto & -1-1+1-1\\ -1-1& \mapsto & -1-1-1+1\end{array}$

appliquée en groupant les termes deux par deux. Ces règles montrent qu'il n'y a pas plus que quatre symboles consécutifs égaux.

• Les valeurs des suites $(a_n)$ et $(b_n)$ vérifient des relations de récurrence qui permettent de les calculer facilement. Posons en effet Modèle:Math, avec Modèle:Mvar impair. Alors on a :

$a_n=\{\begin{array}{cc}{a}_{(m-1)/4}& \text{si }m\equiv 1mod4\\ a_{(m-1)/2}+1& \text{si }m\equiv 3mod4\end{array}$

$b_n=\{\begin{array}{cc}{b}_{(m-1)/4}& \text{si }m\equiv 1mod4\\ -b_{(m-1)/2}& \text{si }m\equiv 3mod4\end{array}$

Par exemple, on a $a_{108}=a_{13}+1=a_3+1=a_1+2=a_0+2=2$. En effet, l’écriture binaire de l'entier 108 est 11011000, et ce mot contient deux occurrences de 11. On obtient $b_{108}=1$.

• La suite contient des palindromes : par exemple, le préfixe de longueur 10, à savoir +1, +1, +1, -1, +1, +1, -1, +1, +1, +1, est un palindrome. La suite ne contient que des palindromes de longueur 1, 2, 3, 4, 5, 6, 7, 8, 10, 12 et 14

• Soit Modèle:Math le nombre de facteurs de longueur Modèle:Mvar de la suite de Rudin–Shapiro, vue comme mot infini. On a $c(0)=1,c(1)=2,c(2)=4,c(3)=8,c(4)=16,c(5)=24,c(6)=36,c(7)=46$, et $c(n)=8(n-1)$ pour $n\ge 8$.

• La suite de Rudin-Shapiro est liée à une suite de pliage de papier, à savoir la suite régulière définie par les instructions de pliage alternant 0 et 1. Cette suite de pliage est :

0 0 1 1 0 1 1 0 0 0 1 0 0 1 1. . .

La suite déduite de celle-ci « par intégration », à savoir la suite de ses sommes partielles modulo 2, est suite :

0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 . . .

C'est la suite de Rudin-Shapiro si on écrit 0 à la place de +1, et 1 à la place de -1.

• La suite des sommes partielles de la suite de Rudin–Shapiro, définie par :

$s_n=\sum _{k=0}^n{b}_k,$

a les valeurs :

1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 7, 6, 5, 4, 5, 4, ... (C'est la Modèle:OEIS)

Elle vérifie l'inégalité :

$\sqrt{\frac{3n}{5}}<s_n<\sqrt{6n}$

pour $n\ge 1$.

Notes et références

Références

• Modèle:Ouvrage

Article connexe

• polynôme de Shapiro