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 n^e terme b_n est défini comme suit : soit

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

le développement binaire de n et soit

$a_{n}=\sum _{i=0}^{k-1}\varepsilon _{i+1}\varepsilon _{i}$.

Le nombre a_n est le nombre d’occurrences du facteur 11 dans l'écriture binaire de n. Alors b_n est défini par :

$b_{n}=(-1)^{a_{n}}$

Ainsi, b_n = 1 si le nombre de facteurs 11 dans l'écriture binaire de n est pair, et b_n = -1 sinon.

Par exemple, pour n = 6, le développement binaire de 6 est 110, donc a₆ = 1 et b₆ = -1. Pour n = 7, le développement binaire est 111, il y a deux occurrences (chevauchantes) de 11, donc a₇ = 2 et b₇ = 1.

Les premiers termes de la suite (a_n) sont (on commence à 0) :

0, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 1, 1, 1, 2, 3, ... (c'est la suite A014081 de l'OEIS)

et les termes correspondants de la suite (b_n), 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 suite A020985 de l'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 : p pour un nombre pair d'occurrences de 11, et i 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 A* dans lui-même défini par :

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

engendre, à partir de a, le mot infini :

$abacabdbabacdcac\cdots$

La suite de Rudin-Shapiro est obtenue en envoyant a et b sur +1, et c et d sur -1.

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

${\begin{array}{lcl}{+}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 n = 2^km, avec m impair. Alors on a :

$a_{n}={\begin{cases}a_{(m-1)/4}&{\text{si }}m\equiv 1{\bmod {4}}\\a_{(m-1)/2}+1&{\text{si }}m\equiv 3{\bmod {4}}\end{cases}}$

$b_{n}={\begin{cases}b_{(m-1)/4}&{\text{si }}m\equiv 1{\bmod {4}}\\-b_{(m-1)/2}&{\text{si }}m\equiv 3{\bmod {4}}\end{cases}}$

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 c(n) le nombre de facteurs de longueur n 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\geq 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 suite A020986 de l'OEIS)

Elle vérifie l'inégalité :

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

pour $n\geq 1$.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Rudin-Shapiro sequence » (voir la liste des auteurs).

Références

• (en) Jean-Paul Allouche et Jeffrey O. Shallit, Automatic sequences : Theory, applications, generalizations, Cambridge, Cambridge University Press, 2003, 571 p. (ISBN 0-521-82332-3, MR 1997038)

Article connexe

• polynôme de Shapiro