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=\sum {\epsilon }_i{\epsilon }_{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₆ = 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, ...

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{array}{cc}{b}_{2n}& =b_n\\ b_{2n+1}& =(-1{)}^n{b}_n\end{array}$

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{array}{cc}{a}_{(m-1)/4}& \text{se }m=1mod4\\ a_{(m-1)/2}+1& \text{se }m=3mod4\end{array}$

$b_n=\{\begin{array}{cc}{b}_{(m-1)/4}& \text{se }m=1mod4\\ -b_{(m-1)/2}& \text{se }m=3mod4\end{array}$

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

$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, ... Template:OEIS

si può dimostrare che soddisfa la diseguaglianza

$\sqrt{\frac{3n}{5}}<s_n<\sqrt{6n}\text{ per }n\ge 1.$

Bibliografia

• Template:Cita libro
• Template:Cita libro
• Template:Cita libro
• Template:Cita libro

Voci correlate

• Successione di Thue-Morse