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

Definizione

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

${\displaystyle a_{n}=\textstyle \sum \varepsilon _{i}\varepsilon _{i+1}}$

${\displaystyle 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.^[2][3][4]

Ad esempio a₆ = 1 e b₆ = −1 perché la rappresentazione binaria di 6 è 110, che contiene una occorrenza di 11; invece, a₇ = 2 e b₇ = +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, ...^[5]

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, ...^[6]

Proprietà

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

La definizione ricorsiva è^[3]

${\displaystyle {\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

${\displaystyle 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}}}$

${\displaystyle 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₁₀₈ = a₁₃ + 1 = a₃ + 1 = a₁ + 2 = a₀ + 2 = 2, come si può verificare osservando che la rappresentazione binaria di 108 è 1101100, che contiene due sottostringhe 11; da questo b₁₀₈ = (−1)² = +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

${\displaystyle 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

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