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 terme est défini comme suit : soit
le développement binaire de et soit . Le nombre est le nombre d’occurrences du facteur 11 dans l'écriture binaire de . Alors est défini par :
Ainsi, si le nombre de facteurs 11 dans l'écriture binaire de est pair, et sinon.
Par exemple, pour , le développement binaire de 6 est 110, donc et . Pour , le développement binaire est 111, il y a deux occurrences (chevauchantes) de 11, 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 )
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 )
Propriétés
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 11, et 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 . La valeur calculée est +1.
La suite de Rudin-Shapiro est (uniformément) morphique, comme toute suite automatique. Soit un alphabet à quatre lettres. Le morphisme 2-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.
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.
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 108 est 11011000, et ce mot contient deux occurrences de 11. On obtient .
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 le nombre de facteurs de longueur de la suite de Rudin–Shapiro, vue comme mot infini. On a , et pour .
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 :
a les valeurs : 1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 7, 6, 5, 4, 5, 4, ... (C'est la ) Elle vérifie l'inégalité :
pour .
Notes et références
Références
Articles connexes polynôme de Shapiro
Rudin-Shapiro Catégorie:Combinatoire Catégorie:Informatique théorique Rudin-Shapiro