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, bn, è definito dalle regole:

dove εi sono le cifre della rappresentazione in base 2 di n. In questo modo an conta il numero di occorrenze della sottostringa 11 (comprese le stringe sovrapposte) nella rappresentazione binaria, e bn vale +1 se an è pari e −1 se an è dispari.Pytheas Fogg (2002) p.42Everest et al (2003) p.234

Ad esempio a6 = 1 e b6 = −1 perché la rappresentazione binaria di 6 è 110, che contiene una occorrenza di 11; invece, a7 = 2 e b7 = +1 perché la rappresentazione binaria di 7 è 111, che contiene due occorrenze (sovrapposte) di 11.

Cominciando con n = 0, i primi termini della successione an sono: 0, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 1, 1, 1, 2, 3, ... e i corrispondenti termini della successione bn 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.Finite automata and arithmetic, Jean-Paul Allouche

La definizione ricorsiva è

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

Quindi a108 = a13 + 1 = a3 + 1 = a1 + 2 = a0 + 2 = 2, come si può verificare osservando che la rappresentazione binaria di 108 è 1101100, che contiene due sottostringhe 11; da questo b108 = (−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

con valori 1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 7, 6, 5, 4, 5, 4, ... si può dimostrare che soddisfa la diseguaglianza

Note

Bibliografia

Voci correlate Successione di Thue-Morse

Categoria:Successioni di interi