Suite de Rudin-Shapiro

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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, Walter Rudin et Harold Shapiro, qui ont étudié indépendamment ses propriétés[1].

Définition[modifier | modifier le code]

Chaque terme de la suite de Rudin-Shapiro est égal à 1 ou à -1. Le ne terme b_n est défini comme suit: Soit

n=\sum_{i=0}^k\varepsilon_i2^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[2].

Par exemple, pour n=6, le développement binaire de 6 est 110, donc a_6=1 et b_6=-1. Pour n=7, le développement binaire est 111, il y a deux occurrences (chevauchantes) de 11, donc a_7=2 et b_7=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[modifier | modifier le code]

Automate de la suite de Rudin-Shapiro.

1.- 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.

2.- La suite de Rudin-Shapiro est (uniformément) morphique, comme toute suite automatique. Soit A=\{a,b,c,d\} un alphabet à quatre lettre. 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 :

abac abdb adac dcac\cdots

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

3.- 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.

4.- 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 occurrence de 11. On obtient b_{108}=1.

5.- 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[3]

6.- 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\ge8.

7.- 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.

8.- 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 \ge 1[1].


Notes et références[modifier | modifier le code]

  1. a et b A Case Study in Mathematical Research: The Golay–Rudin–Shapiro Sequence, par John Brillhart et Patrick Morton
  2. (en) Eric W. Weisstein, « Suite de Rudin-Shapiro », MathWorld
  3. Allouche & Shallit (2003)

(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[modifier | modifier le code]

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

Article connexe[modifier | modifier le code]