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

Définition

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

n = ∑ i = 0 k ε i 2 i {\displaystyle n=\sum _{i=0}^{k}\varepsilon _{i}2^{i}}

le développement binaire de n et soit

a n = ∑ i = 0 k − 1 ε i + 1 ε i {\displaystyle a_{n}=\sum _{i=0}^{k-1}\varepsilon _{i+1}\varepsilon _{i}} .

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

b n = ( − 1 ) a n {\displaystyle b_{n}=(-1)^{a_{n}}}

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

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

Les premiers termes de la suite (an) 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 (bn), 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
p 0 , p 1 , i 1 , i 0 , i 1 , p 1 , p 0 , p 0 , p 0 {\displaystyle 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 } {\displaystyle A=\{a,b,c,d\}} un alphabet à quatre lettres. Le morphisme 2-uniforme de A* dans lui-même défini par :
a ↦ a b b ↦ a c c ↦ d b d ↦ d c {\displaystyle {\begin{array}{lcl}a&\mapsto &ab\\b&\mapsto &ac\\c&\mapsto &db\\d&\mapsto &dc\end{array}}}

engendre, à partir de a, le mot infini :

a b a c a b d b a b a c d c a c ⋯ {\displaystyle 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 :
+ 1 + 1 ↦ + 1 + 1 + 1 − 1 + 1 − 1 ↦ + 1 + 1 − 1 + 1 − 1 + 1 ↦ − 1 − 1 + 1 − 1 − 1 − 1 ↦ − 1 − 1 − 1 + 1 {\displaystyle {\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 ) {\displaystyle (a_{n})} et ( b n ) {\displaystyle (b_{n})} vérifient des relations de récurrence qui permettent de les calculer facilement. Posons en effet n = 2km, avec m impair. Alors on a :
a n = { a ( m − 1 ) / 4 si  m ≡ 1 mod 4 a ( m − 1 ) / 2 + 1 si  m ≡ 3 mod 4 {\displaystyle 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 = { b ( m − 1 ) / 4 si  m ≡ 1 mod 4 − b ( m − 1 ) / 2 si  m ≡ 3 mod 4 {\displaystyle 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 {\displaystyle 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 {\displaystyle 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[3]
  • 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 {\displaystyle 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 ) {\displaystyle c(n)=8(n-1)} pour n ≥ 8 {\displaystyle 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 = ∑ k = 0 n b k , {\displaystyle 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é :

3 n 5 < s n < 6 n {\displaystyle {\sqrt {\frac {3n}{5}}}<s_{n}<{\sqrt {6n}}}

pour n ≥ 1 {\displaystyle n\geq 1} [1].

Notes et références

  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 », sur 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

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

Article connexe

  • icône décorative Portail des mathématiques
  • icône décorative Portail de l'informatique théorique