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:

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

{\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₁₀₈ = 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, ... (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\,.

^[1]

Note

^ ^a ^b John Brillhart, Patrick Morton, A Case Study in Mathematical Research: The Golay-Rudin-Shapiro Sequence, in The American Mathematical Monthly, vol. 103, 1996, p. 854, DOI:10.2307/2974610.
^ (EN) Eric W. Weisstein, Successione di Rudin-Shapiro, in MathWorld, Wolfram Research.
^ ^a ^b Pytheas Fogg (2002) p.42
^ Everest et al (2003) p.234
^ (EN) Sequenza A014081, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
^ (EN) Sequenza A020985, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
^ Finite automata and arithmetic, Jean-Paul Allouche

Bibliografia

Jean-Paul Allouche e Jeffrey Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003, ISBN 978-0-521-82332-6, Zbl 1086.11015.
Graham Everest, Alf van der Poorten, Igor Shparlinski e Thomas Ward, Recurrence sequences, Mathematical Surveys and Monographs, vol. 104, Providence, American Mathematical Society, 2003, ISBN 0-8218-3387-1, Zbl 1033.11006.
N. Pytheas Fogg, Substitutions in dynamics, arithmetics and combinatorics, a cura di Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A., Lecture Notes in Mathematics, vol. 1794, Berlin, Springer-Verlag, 2002, ISBN 3-540-44141-7, Zbl 1014.11015.
Michel Mendès France, The Rudin-Shapiro sequence, Ising chain, and paperfolding, in Bruce C. Berndt, Harold G. Diamond, Heini Halberstam, Adolf Hildebrand (a cura di), Analytic number theory. Proceedings of a conference in honor of Paul T. Bateman, held on April 25–27, 1989, at the University of Illinois, Urbana, IL (USA), Progress in Mathematics, vol. 85, Boston, Birkhäuser, 1990, pp. 367–390, ISBN 0-8176-3481-9, Zbl 0724.11010.