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, 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.[2][3][4]
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, ...[5]
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, ...[6]
Proprietà
La successione di Rudin–Shapiro può essere generata da un automa a quattro stati.[7]
La definizione ricorsiva è[3]
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, ... (EN) Sequenza A020986, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
si può dimostrare che soddisfa la diseguaglianza
- [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.
Voci correlate
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)