Rudin–Shapiro sequence

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 or . If the binary expansion of is given by

then let

(So is the number of times the block 11 appears in the binary expansion of .)

The Rudin–Shapiro sequence is then defined by

Thus if is even and if is odd.

The sequence is known as the complete Rudin–Shapiro sequence, and starting at , 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 of the Rudin–Shapiro sequence are:

+1, +1, +1, −1, +1, +1, −1, +1, +1, +1, +1, −1, −1, −1, +1, −1, ...

For example, and because the binary representation of 6 is 110, which contains one occurrence of 11; whereas and 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 norm of a measurable function . This norm is defined by

One can prove that for any sequence with each in ,

Moreover, for almost every sequence with each is in ,

However, the Rudin–Shapiro sequence satisfies a tighter bound: there exists a constant such that

It is conjectured that one can take , but while it is known that , the best published upper bound is currently . Let be the n-th Shapiro polynomial. Then, when , the above inequality gives a bound on . More recently, bounds have also been given for the magnitude of the coefficients of where .

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.

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 with fixed point and a coding such that , where 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

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

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

A 2-uniform morphism that requires a coding 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

+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

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

Let denote the Rudin–Shapiro sequence on , in which case is the number, modulo 2, of occurrences (possibly overlapping) of the block in the base-2 expansion of . Then the generating function

satisfies

making it algebraic as a formal power series over . The algebraicity of over follows from the 2-automaticity of by Christol's theorem.

The Rudin–Shapiro sequence along squares is normal.

The complete Rudin–Shapiro sequence satisfies the following uniform distribution result. If , then there exists such that

which implies that is uniformly distributed modulo for all irrationals .

Relationship with one-dimensional Ising model

Let the binary expansion of n be given by

where . 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. Fix representing the number of sites, and fix constants and representing the coupling constant and external field strength, respectively. Choose a sequence of weights with each . For any sequence of spins with each , define its Hamiltonian by

Let be a constant representing the temperature, which is allowed to be an arbitrary non-zero complex number, and set where is the Boltzmann constant. The partition function is defined by

Then we have

where the weight sequence satisfies for all .

See also

• Shapiro polynomials

Notes

References