In mathematics, the Rudin–Shapiro sequence, also known as the Golay–Rudin–Shapiro sequence, is an infinite 2-automatic sequence named after Marcel Golay, Harold S. Shapiro, and Walter Rudin, who investigated its properties.
Definition Each term of the Rudin–Shapiro sequence is either 1 {\displaystyle 1} or − 1 {\displaystyle -1} . If the binary expansion of n {\displaystyle n} is given by
n = ∑ k ≥ 0 ϵ k ( n ) 2 k , {\displaystyle n=\sum _{k\geq 0}\epsilon _{k}(n)2^{k},}
then let
u n = ∑ k ≥ 0 ϵ k ( n ) ϵ k + 1 ( n ) . {\displaystyle u_{n}=\sum _{k\geq 0}\epsilon _{k}(n)\epsilon _{k+1}(n).}
(So u n {\displaystyle u_{n}} is the number of times the block 11 appears in the binary expansion of n {\displaystyle n} .) The Rudin–Shapiro sequence ( r n ) n ≥ 0 {\displaystyle (r_{n})_{n\geq 0}} is then defined by
r n = ( − 1 ) u n . {\displaystyle r_{n}=(-1)^{u_{n}}.}
Thus r n = 1 {\displaystyle r_{n}=1} if u n {\displaystyle u_{n}} is even and r n = − 1 {\displaystyle r_{n}=-1} if u n {\displaystyle u_{n}} is odd. The sequence u n {\displaystyle u_{n}} is known as the complete Rudin–Shapiro sequence, and starting at n = 0 {\displaystyle n=0} , its first few terms 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 r n {\displaystyle r_{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) For example, u 6 = 1 {\displaystyle u_{6}=1} and r 6 = − 1 {\displaystyle r_{6}=-1} because the binary representation of 6 is 110, which contains one occurrence of 11; whereas u 7 = 2 {\displaystyle u_{7}=2} and r 7 = 1 {\displaystyle r_{7}=1} because the binary representation of 7 is 111, which contains two (overlapping) occurrences of 11.
Historical motivation The Rudin–Shapiro sequence was introduced independently by Golay, Rudin, and Shapiro. The following is a description of Rudin's motivation. In Fourier analysis, one is often concerned with the L 2 {\displaystyle L^{2}} norm of a measurable function f : [ 0 , 2 π ) → [ 0 , 2 π ) {\displaystyle f\colon [0,2\pi )\to [0,2\pi )} . This norm is defined by
| | f | | 2 = ( 1 2 π ∫ 0 2 π | f ( t ) | 2 d t ) 1 / 2 . {\displaystyle ||f||_{2}=\left({\frac {1}{2\pi }}\int _{0}^{2\pi }|f(t)|^{2}\,\mathrm {d} t\right)^{1/2}.}
… excerpt ends here. Continue reading the full article.
