Successione di Rudin-Shapiro
# Successione di Rudin-Shapiro

In matematica la successione di Rudin–Shapiro, nota anche come successione di Golay–Rudin–Shapiro è una sequenza automatica infinita; prende il nome da Marcel Golay, Walter Rudin e Harold S. Shapiro, che hanno studiato le sue proprietà indipendentemente uno dall'altro.

## Definizione

Ogni termine della successione di Rudin–Shapiro è o +1 o −1. Il termine n-esimo della successione, $b_n,$ è definito dalle regole:

    $a_{n}=\textstyle \sum \varepsilon _{i}\varepsilon _{i+1}$
    $b_{n}=(-1)^{a_{n}}$

dove $ε_i$ sono le cifre della rappresentazione in base 2 di n. In questo modo $a_n$ conta il numero di occorrenze della sottostringa 11 (comprese le stringe sovrapposte) nella rappresentazione binaria, e $b_n$ vale +1 se $a_n$ è pari e −1 se $a_n$ è dispari.

Ad esempio $a_6$ = 1 e $b_6$ = −1 perché la rappresentazione binaria di 6 è 110, che contiene una occorrenza di 11; invece, $a_7$ = 2 e $b_7$ = +1 perché la rappresentazione binaria di 7 è 111, che contiene due occorrenze (sovrapposte) di 11.

Cominciando con n = 0, i primi termini della successione $a_n$ sono:

    0, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 1, 1, 1, 2, 3, ...

e i corrispondenti termini della successione $b_n$ di Rudin–Shapiro sono:

    +1, +1, +1, −1, +1, +1, −1, +1, +1, +1, +1, −1, −1, −1, +1, −1, ...

## Proprietà

La successione di Rudin–Shapiro può essere generata da un automa a quattro stati.

La definizione ricorsiva è

    ${\begin{cases}b_{2n}&=b_{n}\\b_{2n+1}&=(-1)^{n}b_{n}\end{cases}}$

I valori dei termini $a_n$ e $b_n$ nella successione di Rudin–Shapiro si può trovare riscorsivamente come illustrato di seguito: se n = $m·2^k,$ dove m è dispari allora

    $a_{n}={\begin{cases}a_{(m-1)/4}&{\text{se }}m=1\mod 4\\a_{(m-1)/2}+1&{\text{se }}m=3\mod 4\end{cases}}$
    $b_{n}={\begin{cases}b_{(m-1)/4}&{\text{se }}m=1\mod 4\\-b_{(m-1)/2}&{\text{se }}m=3\mod 4\end{cases}}$

Quindi $a_{108}$ = $a_{13}$ + 1 = $a_3$ + 1 = $a_1$ + 2 = $a_0$ + 2 = 2, come si può verificare osservando che la rappresentazione binaria di 108 è 1101100, che contiene due sottostringhe 11; da questo $b_{108}$ = $(−1)^2$ = +1.

La parola di Rudin–Shapiro +1 +1 +1 −1 +1 +1 −1 +1 +1 +1 +1 −1 −1 −1 +1 −1 ..., che si crea concatenando i termini della successione, è un punto fisso del morfismo (insieme di regole di sostituzione delle stringhe)

    +1 +1 → +1 +1 +1 −1
    +1 −1 → +1 +1 −1 +1
    −1 +1 → −1 −1 +1 −1
    −1 −1 → −1 −1 −1 +1

come segue:

    +1 +1 → +1 +1 +1 −1 → +1 +1 +1 −1 +1 +1 −1 +1 → +1 +1 +1 −1 +1 +1 −1 +1 +1 +1 +1 −1 −1 −1 +1 −1 ...

Si può vedere che da queste regole che la stringa di Rudin–Shapiro contiene al più quattro simboli +1 consecutivi e al più quattro simboli -1 consecutivi.

Della successione delle somme parziali della successione di Rudin–Shapiro, definita da

    $s_{n}=\sum _{k=0}^{n}b_{k}\,,$

con valori

    1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 7, 6, 5, 4, 5, 4, ... (EN) Sequenza A020986, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.

si può dimostrare che soddisfa la diseguaglianza

    ${\sqrt {\frac {3n}{5}}}<s_{n}<{\sqrt {6n}}{\text{ per }}n\geq 1\,.$
