Rudin–Shapiro sequence

In mathematics the Rudin–Shapiro sequence, also known as the Golay–Rudin–Shapiro sequence is an infinite automatic sequence named after Marcel Golay, Walter Rudin and Harold S. Shapiro, who independently investigated its properties.^[1]

Definition

Each term of the Rudin–Shapiro sequence is either +1 or −1. The n^th term of the sequence, b_n, is defined by the rules:

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

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

where the ε_i are the digits in the binary expansion of n. Thus a_n counts the number of (possibly overlapping) occurrences of the sub-string 11 in the binary expansion of n, and b_n is +1 if a_n is even and −1 if a_n is odd.^[2][3][4]

For example, a₆ = 1 and b₆ = −1 because the binary representation of 6 is 110, which contains one occurrence of 11; whereas a₇ = 2 and b₇ = +1 because the binary representation of 7 is 111, which contains two (overlapping) occurrences of 11.

Starting at n = 0, the first few terms of the a_n sequence are:

0, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 1, 1, 1, 2, 3, ... (sequence A014081 in the OEIS)

and the corresponding terms b_n of the Rudin–Shapiro sequence are:

+1, +1, +1, −1, +1, +1, −1, +1, +1, +1, +1, −1, −1, −1, +1, −1, ... (sequence A020985 in the OEIS)

Properties

The Rudin–Shapiro sequence can be generated by a four state automaton.^[5]

There is a recursive definition^[3]

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

The values of the terms a_n and b_n in the Rudin–Shapiro sequence can be found recursively as follows. If n = m·2^k where m is odd then

$a_{n}={\begin{cases}a_{{(m-1)/4}}&{\text{if }}m=1\mod 4\\a_{{(m-1)/2}}+1&{\text{if }}m=3\mod 4\end{cases}}$

$b_{n}={\begin{cases}b_{{(m-1)/4}}&{\text{if }}m=1\mod 4\\-b_{{(m-1)/2}}&{\text{if }}m=3\mod 4\end{cases}}$

Thus a₁₀₈ = a₁₃ + 1 = a₃ + 1 = a₁ + 2 = a₀ + 2 = 2, which can be verified by observing that the binary representation of 108, which is 1101100, contains two sub-strings 11. And so b₁₀₈ = (−1)² = +1.

The Rudin–Shapiro word +1 +1 +1 −1 +1 +1 −1 +1 +1 +1 +1 −1 −1 −1 +1 −1 ..., which is created by concatenating the terms of the Rudin–Shapiro sequence, is a fixed point of the morphism or string substitution rules

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

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

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

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

as follows:

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

It can be seen from the morphism rules that the Rudin–Shapiro string contains at most four consecutive +1s and at most four consecutive −1s.

The sequence of partial sums of the Rudin–Shapiro sequence, defined by

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

with values

1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 7, 6, 5, 4, 5, 4, ... (sequence A020986 in the OEIS)

can be shown to satisfy the inequality

${\sqrt {{\frac {3n}{5}}}}<s_{n}<{\sqrt {6n}}{\text{ for }}n\geq 1\,.$^[1]

See also

• Shapiro polynomials

Notes

1. John Brillhart and Patrick Morton, winners of a 1997 Lester R. Ford Award (1996). "A Case Study in Mathematical Research: The Golay–Rudin–Shapiro Sequence". Amer. Math. Monthly. 103: 854–869. doi:10.2307/2974610.
2. Weisstein, Eric W. "Rudin–Shapiro Sequence". MathWorld.
3. Pytheas Fogg (2002) p.42
4. Everest et al (2003) p.234
5. Finite automata and arithmetic, Jean-Paul Allouche

References

• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. ISBN 978-0-521-82332-6. Zbl 1086.11015.
• Everest, Graham; van der Poorten, Alf; Shparlinski, Igor; Ward, Thomas (2003). Recurrence sequences. Mathematical Surveys and Monographs. 104. Providence, RI: American Mathematical Society. ISBN 0-8218-3387-1. Zbl 1033.11006.
• Pytheas Fogg, N. (2002). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. 1794. Editors Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. Berlin: Springer-Verlag. ISBN 3-540-44141-7. Zbl 1014.11015.
• Mendès France, Michel (1990). "The Rudin-Shapiro sequence, Ising chain, and paperfolding". In Berndt, Bruce C.; Diamond, Harold G.; Halberstam, Heini; et al. 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. 85. Boston: Birkhäuser. pp. 367–390. ISBN 0-8176-3481-9. Zbl 0724.11010.