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 à ou à . Le e terme est défini comme suit: Soit

le développement binaire de et soit

.

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

Ainsi, si le nombre de facteurs dans l'écriture binaire de est pair, et sinon[2].

Par exemple, pour , le développement binaire de est , donc et . Pour , le développement binaire est , il y a deux occurrences (chevauchantes) de , donc et .

Les premiers termes de la suite 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 , 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: pour un nombre pair d'occurrences de , et pour un nombre impair; cette lettre est suivie du dernier bit lu. Par exemple, pour l'entier , dont l'écriture binaire est , la suite des états parcourus est

.

La valeur calculée est +1.

2.- La suite de Rudin-Shapiro est (uniformément) morphique, comme toute suite automatique. Soit un alphabet à quatre lettre. Le morphisme -uniforme de dans lui-même défini par :

engendre, à partir de , le mot infini :

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

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

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 et vérifient des relations de récurrence qui permettent de les calculer facilement. Posons en effet , avec impair. Alors on a :

Par exemple, on a . En effet, l’écriture binaire de l'entier est , et ce mot contient deux occurrence de . On obtient .

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 le nombre de facteurs de longueur de la suite de Rudin–Shapiro, vue comme mot infini. On a , et pour .

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 :

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é :

pour [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, (ISBN 0-521-82332-3)

Article connexe[modifier | modifier le code]