Rudin–Shapiro sequence

Each term of the Rudin–Shapiro sequence is either 1 or -1. If the binary expansion of n is given by : n = \sum_{k \ge 0} \epsilon_k(n) 2^k, then let : u_n = \sum_{k \ge 0} \epsilon_k(n)\epsilon_{k+1}(n). (So u_n is the number of times the block 11 appears in the binary expansion of n.) The Rudin–Shapiro sequence (r_n)_{n \ge 0} is then defined by : r_n = (-1)^{u_n}. Thus r_n = 1 if u_n is even and r_n = -1 if u_n is odd. The sequence u_n is known as the complete Rudin–Shapiro sequence, and starting at n = 0, its first few terms are: : 0, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 1, 1, 1, 2, 3, ... and the corresponding terms r_n of the Rudin–Shapiro sequence are: : +1, +1, +1, −1, +1, +1, −1, +1, +1, +1, +1, −1, −1, −1, +1, −1, ... For example, u_6 = 1 and r_6 = -1 because the binary representation of 6 is 110, which contains one occurrence of 11; whereas u_7 = 2 and 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 norm of a measurable function f \colon [0,2\pi) \to [0,2\pi) . This norm is defined by : One can prove that for any sequence (a_n)_{n \ge 0} with each a_n in \{1,-1\}, : \sup_{x \in \R} \left|\sum_{0 \le n Moreover, for almost every sequence (a_n)_{n \ge 0} with each a_n is in \{-1,1\}, : \sup_{x \in \R} \left|\sum_{0 \le n However, the Rudin–Shapiro sequence (r_n)_{n \ge 0} satisfies a tighter bound: there exists a constant C > 0 such that : \sup_{x \in \R} \left|\sum_{0 \le n It is conjectured that one can take C = \sqrt{6}, but while it is known that C \ge \sqrt{6}, the best published upper bound is currently C \le (2+\sqrt{2})\sqrt{3/5}. Let P_n be the n-th Shapiro polynomial. Then, when N = 2^n-1, the above inequality gives a bound on \sup_{x \in \R} |P_n(e^{ix})|. More recently, bounds have also been given for the magnitude of the coefficients of |P_n(z)|^2 where |z| = 1. Shapiro arrived at the sequence because the polynomials : P_n(z) = \sum_{i=0}^{2^n-1} r_i z^i where (r_i)_{i \ge 0} is the Rudin–Shapiro sequence, have absolute value bounded on the complex unit circle by 2^{\frac{n+1}{2}}. This is discussed in more detail in the article on Shapiro polynomials. Golay's motivation was similar, although he was concerned with applications to spectroscopy and published in an optics journal. == Properties ==

The Rudin–Shapiro sequence can be generated by a 4-state automaton accepting binary representations of non-negative integers as input. The sequence is therefore 2-automatic, so by Cobham's little theorem there exists a 2-uniform morphism \varphi with fixed point w and a coding \tau such that r = \tau(w), where r is the Rudin–Shapiro sequence. However, the Rudin–Shapiro sequence cannot be expressed as the fixed point of some uniform morphism alone. There is a recursive definition : \begin{cases} r_{2n} & = r_n \\ r_{2n+1} & = (-1)^n r_n \end{cases} The values of the terms rn and un in the Rudin–Shapiro sequence can be found recursively as follows. If n = m·2k where m is odd then : u_n = \begin{cases} u_{(m-1)/4} & \text{if } m \equiv 1 \pmod 4 \\ u_{(m-1)/2} + 1 & \text{if } m \equiv 3 \pmod 4 \end{cases} : r_n = \begin{cases} r_{(m-1)/4} & \text{if } m \equiv 1 \pmod 4 \\ -r_{(m-1)/2} & \text{if } m \equiv 3 \pmod 4 \end{cases} Thus u108 = u13 + 1 = u3 + 1 = u1 + 2 = u0 + 2 = 2, which can be verified by observing that the binary representation of 108, which is 1101100, contains two sub-strings 11. And so r108 = (−1)2 = +1. A 2-uniform morphism \varphi that requires a coding \tau to generate the Rudin-Shapiro sequence is the following:\begin{align} \varphi: a&\to ab\\ b&\to ac\\ c&\to db\\ d&\to dc \end{align} \begin{align} \tau: a&\to 1\\ b&\to 1\\ c&\to -1\\ d&\to -1 \end{align} 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 r_k \, , with values : 1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 7, 6, 5, 4, 5, 4, ... can be shown to satisfy the inequality : \sqrt{\frac{3}{5} n} The algebraicity of S(X) over \mathbb{F}_2(X) follows from the 2-automaticity of (s_n)_{n \ge 0} by Christol's theorem. The Rudin–Shapiro sequence along squares (r_{n^2})_{n \ge 0} is normal. The complete Rudin–Shapiro sequence satisfies the following uniform distribution result. If x \in \mathbb{R} \setminus \mathbb{Z}, then there exists \alpha = \alpha(x) \in (0,1) such that : \sum_{n which implies that (xu_n)_{n \ge 0} is uniformly distributed modulo 1 for all irrationals x. == Relationship with one-dimensional Ising model ==

Let the binary expansion of n be given by : n = \sum_{k \ge 0} \epsilon_k(n) 2^k where \epsilon_k(n) \in \{0,1\}. Recall that the complete Rudin–Shapiro sequence is defined by : u(n) = \sum_{k \ge 0} \epsilon_k(n)\epsilon_{k+1}(n). Let : \tilde{\epsilon}_k(n) = \begin{cases} \epsilon_k(n) & \text{if } k \le N-1, \\ \epsilon_0(n)& \text{if } k = N. \end{cases} Then let : u(n,N) = \sum_{0 \le k Finally, let : S(N,x) = \sum_{0 \le n Recall that the partition function of the one-dimensional Ising model can be defined as follows. Fix N \ge 1 representing the number of sites, and fix constants J > 0 and H > 0 representing the coupling constant and external field strength, respectively. Choose a sequence of weights \eta = (\eta_0,\dots,\eta_{N-1}) with each \eta_i \in \{-1,1\}. For any sequence of spins \sigma = (\sigma_0,\dots,\sigma_{N-1}) with each \sigma_i \in \{-1,1\}, define its Hamiltonian by : H_{\eta}(\sigma) = -J\sum_{0 \le k Let T be a constant representing the temperature, which is allowed to be an arbitrary non-zero complex number, and set \beta = 1/(kT) where k is the Boltzmann constant. The partition function is defined by : Z_N(\eta,J,H,\beta) = \sum_{\sigma \in \{-1,1\}^N} \exp(-\beta H_{\eta}(\sigma)). Then we have : S(N,x) = \exp\left(\frac{\pi iNx}{2}\right)Z_N\left(1,\frac{1}{2},-1,\pi ix\right) where the weight sequence \eta = (\eta_0,\dots,\eta_{N-1}) satisfies \eta_i = 1 for all i. == See also ==