Succesiunea Rudin-Shapiro

În matematică succesiunea lui Rudin-Shapiro, cunoscută și ca o succesiune a lui Golay-Rudin-Shapiro, este o secvență automată infinită; este numit după Marcel Golay, Walter Rudin și Harold S. Shapiro, care i-au studiat proprietățile independent unul de celălalt. ^[1]

Definiție

Fiecare termen din secvența Rudin - Shapiro este fie +1, fie -1. Al n-lea termen al secvenței, b _n , este definit de reguli:

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

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

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

b_{n}=(-1)^{a_{n}}

{\ displaystyle b_ {n} = (- 1) ^ {a_ {n}}}

{\ displaystyle b_ {n} = (- 1) ^ {a_ {n}}}

unde ε _i sunt cifrele reprezentării bazei 2 a lui n . Astfel , un _n contorizează numărul de apariții ale subșir 11 (inclusiv șiruri suprapuse) , în reprezentarea binară și b _n este 1 dacă _n este chiar și -1 dacă _n este impar. ^[2] ^[3] ^[4]

De exemplu a ₆ = 1 și b ₆ = −1 deoarece reprezentarea binară a lui 6 este 110, care conține o apariție de 11; în schimb, a ₇ = 2 și b ₇ = +1 deoarece reprezentarea binară a lui 7 este 111, care conține două apariții (suprapuse) de 11.

Începând cu n = 0, primii termeni ai succesiunii la _n sunt:

0, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 1, 1, 1, 2, 3, ... ^[5]

și termenii corespunzători ai secvenței Rudin - Shapiro b _n sunt:

+1, +1, +1, −1, +1, +1, −1, +1, +1, +1, +1, −1, −1, −1, +1, −1, .. . ^[6]

Proprietate

Secvența Rudin - Shapiro poate fi generată de un automat cu patru stări . ^[7]

Definiția recursivă este ^[3]

{\begin{cases}b_{2n}&=b_{n}\\b_{2n+1}&=(-1)^{n}b_{n}\end{cases}}

{\ displaystyle {\ begin {cases} b_ {2n} & = b_ {n} \\ b_ {2n + 1} & = (- 1) ^ {n} b_ {n} \ end {cases}}}

{\ displaystyle {\ begin {cases} b_ {2n} & = b_ {n} \\ b_ {2n + 1} & = (- 1) ^ {n} b_ {n} \ end {cases}}}

Valorile termenilor a _n și b _n din secvența Rudin - Shapiro pot fi găsite recursiv după cum se arată mai jos: dacă n = m 2 ^k , unde m este impar, atunci

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 a_ {n} = {\ begin {cases} a _ {(m-1) / 4} și {\ text {se}} m = 1 \ mod 4 \\ a _ {(m-1) / 2} +1 și {\ text {se}} m = 3 \ mod 4 \ end {cases}}}

{\ displaystyle a_ {n} = {\ begin {cases} a _ {(m-1) / 4} și {\ text {se}} m = 1 \ mod 4 \\ a _ {(m-1) / 2} +1 și {\ 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}}

{\ displaystyle b_ {n} = {\ begin {cases} b _ {(m-1) / 4} și {\ text {se}} m = 1 \ mod 4 \\ - b _ {(m-1) / 2} & {\ text {se}} m = 3 \ mod 4 \ end {cases}}}

{\ displaystyle b_ {n} = {\ begin {cases} b _ {(m-1) / 4} și {\ text {se}} m = 1 \ mod 4 \\ - b _ {(m-1) / 2} & {\ text {se}} m = 3 \ mod 4 \ end {cases}}}

Deci a ₁₀₈ = a ₁₃ + 1 = a ₃ + 1 = a ₁ + 2 = a ₀ + 2 = 2, după cum se poate verifica observând că reprezentarea binară a lui 108 este 1101100, care conține două șiruri de caractere 11; din acest b ₁₀₈ = (−1) ² = +1.

Cuvântul lui Rudin-Shapiro +1 +1 +1 −1 +1 +1 −1 +1 +1 +1 +1 +1 −1 −1 −1 +1 −1 ..., care este creat prin concatenarea termenilor de secvența, este un punct fix de morfism (set de reguli de substituție a șirurilor)

+1 +1 → +1 +1 +1 −1

+1 −1 → +1 +1 −1 +1

−1 +1 → −1 −1 +1 −1

−1 −1 → −1 −1 −1 +1

după cum urmează:

+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 −1 ...

Din aceste reguli se poate observa că șirul Rudin - Shapiro conține cel mult patru simboluri +1 consecutive și cel mult patru simboluri -1 consecutive.

Din succesiunea sumelor parțiale ale succesiunii Rudin - Shapiro, definită de

s_{n}=\sum _{k=0}^{n}b_{k}\,,

{\ displaystyle s_ {n} = \ sum _ {k = 0} ^ {n} b_ {k} \ ,,}

{\ displaystyle s_ {n} = \ sum _ {k = 0} ^ {n} b_ {k} \ ,,}

cu valori

1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 7, 6, 5, 4, 5, 4, ... (EN) Secvența A020986 , pe Enciclopedia on-line a secvențelor întregi , Fundația OEIS.

se poate demonstra că satisface inegalitatea

{\sqrt {\frac {3n}{5}}}<s_{n}<{\sqrt {6n}}{\text{ per }}n\geq 1\,.

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

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

^[1]

Notă

^ ^a ^b John Brillhart, Patrick Morton, Un studiu de caz în cercetarea matematică: secvența Golay-Rudin-Shapiro , în The American Mathematical Monthly , vol. 103, 1996, p. 854, DOI : 10.2307 / 2974610 .
^ (EN) Eric W. Weisstein, Succesiunea lui Rudin-Shapiro, în MathWorld , Wolfram Research.
^ ^a ^b Pytheas Fogg (2002) p.42
^ Everest și colab. (2003) p.234
^ (EN) secvența A014081 , on -line Encyclopedia of Integer Sequences , Fundația OEIS.
^ (EN) secvența A020985 , on -line Encyclopedia of Integer Sequences , Fundația OEIS.
^ Automate finite și aritmetică , Jean-Paul Allouche

Bibliografie

Jean-Paul Allouche și Jeffrey Shallit , Secvențe automate: teorie, aplicații, generalizări , Cambridge University Press, 2003, ISBN 978-0-521-82332-6 , Zbl 1086.11015 .
Graham Everest, Alf van der Poorten, Igor Shparlinski și Thomas Ward, secvențe de recurență , sondaje și monografii matematice, vol. 104, Providence, American Mathematical Society, 2003, ISBN 0-8218-3387-1 , Zbl 1033.11006 .
N. Pytheas Fogg, Substituții în dinamică, aritmetică și combinatorică , editat de Berthé, Valérie; Ferenczi, Sébastien; Mauduit, creștin; Siegel, A., Note de curs în matematică, vol. 1794, Berlin, Springer-Verlag, 2002, ISBN 3-540-44141-7 , Zbl 1014.11015 .
Michel Mendès Franța, secvența Rudin-Shapiro, lanțul Ising și hârtie , în Bruce C. Berndt , Harold G. Diamond, Heini Halberstam , Adolf Hildebrand (ed.), Teoria analitică a numerelor. Lucrările unei conferințe în onoarea lui Paul T. Bateman, desfășurată în perioada 25-27 aprilie 1989, la Universitatea din Illinois, Urbana, IL (SUA) , Progresul în matematică, vol. 85, Boston, Birkhäuser, 1990, pp. 367-390, ISBN 0-8176-3481-9 , Zbl 0724.11010 .

Elemente conexe

Succesiunea Thue-Morse

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[bm-1] John Brillhart, Patrick Morton, Un studiu de caz în cercetarea matematică: secvența Golay-Rudin-Shapiro , în The American Mathematical Monthly , vol. 103, 1996, p. 854, DOI : 10.2307 / 2974610 .

[2] (EN) Eric W. Weisstein, Succesiunea lui Rudin-Shapiro, în MathWorld , Wolfram Research.

[PF42-3] Pytheas Fogg (2002) p.42

[4] Everest și colab. (2003) p.234

[5] (EN) secvența A014081 , on -line Encyclopedia of Integer Sequences , Fundația OEIS.

[6] (EN) secvența A020985 , on -line Encyclopedia of Integer Sequences , Fundația OEIS.

[7] Automate finite și aritmetică , Jean-Paul Allouche

[1]

[2]

[3]

[4]

[5]

[6]

[7]