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.
is the number of times the block 11 appears in the binary expansion of
is known as the complete Rudin–Shapiro sequence, and starting at
because the binary representation of 7 is 111, which contains two (overlapping) occurrences of 11.
The Rudin–Shapiro sequence was introduced independently by Golay,[5][6] Rudin,[7] and Shapiro.
This norm is defined by One can prove that for any sequence
satisfies a tighter bound:[10] there exists a constant
be the n-th Shapiro polynomial.
More recently, bounds have also been given for the magnitude of the coefficients of
[14] Shapiro arrived at the sequence because the polynomials where
is the Rudin–Shapiro sequence, have absolute value bounded on the complex unit circle by
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.
The Rudin–Shapiro sequence can be generated by a 4-state automaton accepting binary representations of non-negative integers as input.
[15] The sequence is therefore 2-automatic, so by Cobham's little theorem there exists a 2-uniform morphism
However, the Rudin–Shapiro sequence cannot be expressed as the fixed point of some uniform morphism alone.
[16] There is a recursive definition[3] 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 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.
to generate the Rudin-Shapiro sequence is the following:
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 as follows: 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 with values can be shown to satisfy the inequality Let
is the number, modulo 2, of occurrences (possibly overlapping) of the block
Then the generating function satisfies making it algebraic as a formal power series over
[18] The complete Rudin–Shapiro sequence satisfies the following uniform distribution result.
Recall that the complete Rudin–Shapiro sequence is defined by Let Then let Finally, let Recall that the partition function of the one-dimensional Ising model can be defined as follows.
representing the number of sites, and fix constants
representing the coupling constant and external field strength, respectively.
Choose a sequence of weights
be a constant representing the temperature, which is allowed to be an arbitrary non-zero complex number, and set
The partition function is defined by Then we have where the weight sequence