Rudin–Shapiro sequence explained

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.^[1]

Definition

Each term of the Rudin–Shapiro sequence is either

1 or -1 . If the binary expansion of n is given byn = \sum _{k} \epsilon _{k(n)} 2 ^{k,}

then let

u _{n} = \sum _{k} \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} is then defined byr _{n} = ( -1 ) ^{u _{n}} .

Thus

r _{n} = 1 if u _{n} is even and r _{n} = -1 if u _{n} is odd.^[2]

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

f \colon [ 0 , 2 \pi) \to [ 0 , 2 \pi) . This norm is defined by||f|| _{2} = \left( (1)/(2 \pi) \int ^{2 \pi} _{0} |f(t)| ^{2dt\right)} ^{1/2} .

One can prove that for any sequence

(a _{n)} _{n} with each a _{n} in \{ 1 , -1 \} ,\sup _{x} \left|\sum _{0} a _{n} e ^{inx} \right| \ge \left|\left|\sum _{0} a _{n} e ^{inx} \right|\right| _{2} = \sqrt{N}.

Moreover, for almost every sequence

(a _{n)} _{n} with each a _{n} is in \{ -1 , 1 \} ,\sup _{x} \left|\sum _{0} a _{n} e ^{inx} \right| = O(\sqrt{N log N}). ^[7]

However, the Rudin–Shapiro sequence

(r _{n)} _{n} satisfies a tighter bound:^[8] there exists a constant C > 0 such that\sup _{x} \left|\sum _{0} r _{n} e ^{inx} \right| \le C\sqrt{N}.

It is conjectured that one can take

C = \sqrt{ 6 } ,^[9] but while it is known that C \ge \sqrt{ 6 } ,^[10] the best published upper bound is currently C \le ( 2+ \sqrt{ 2 })\sqrt{ 3 / 5 } .^[11] Let P _{n} be the n-th Shapiro polynomial. Then, when N = 2 ^{n-1} , the above inequality gives a bound on \sup _{x} |P ^{ix} _{n(e} )| . More recently, bounds have also been given for the magnitude of the coefficients of |P ^{2} _{n(z)|} where |z| = 1 .^[12]

Shapiro arrived at the sequence because the polynomials

P _{n(z)} = \sum ^{2 ^{n-1}} _{i =0} r _{i} z ^{i} where (r _{i)} _{i} is the Rudin–Shapiro sequence, have absolute value bounded on the complex unit circle by 2 ^{(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

\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.^[14]

There is a recursive definition^[15]

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

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

u _{n} = \begin{cases} u _{(m-1)/4} & if m \equiv 1 \pmod 4 \\ u _{(m-1)/2} + 1 & if m \equiv 3 \pmod 4 \end{cases} r _{n} = \begin{cases} r _{(m-1)/4} & if m \equiv 1 \pmod 4 \\ - r _{(m-1)/2} & if m \equiv 3 \pmod 4 \end{cases}

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

\varphi that requires a coding \tau 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

s _{n} = \sum ^{n} _{k =0} 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{ (3)/(5) n} < s _{n} < \sqrt{ 6 n} for n \ge 1 .

Let

(s _{n)} _{n} denote the Rudin–Shapiro sequence on \{ 0 , 1 \} , in which case s _{n} is the number, modulo 2, of occurrences (possibly overlapping) of the block 11 in the base-2 expansion of n . Then the generating functionS(X) = \sum _{n} s _{n} X ^{n}

satisfies

( 1+ X) ^{5} S(X) ^{2} + ( 1+ X) ^{4} S(X) + X ^{3} = 0 ,

making it algebraic as a formal power series over

F _{2(X)} .^[16] The algebraicity of S(X) over F _{2(X)} follows from the 2-automaticity of (s _{n)} _{n} by Christol's theorem.

The Rudin–Shapiro sequence along squares

(r _{n ^{2}} ) _{n} is normal.^[17]

The complete Rudin–Shapiro sequence satisfies the following uniform distribution result. If

x \in R \setminus Z , then there exists \alpha = \alpha(x) \in ( 0 , 1 ) such that\sum _{n} \exp( 2 \pi ixu _{n)} = O(N ^{\alpha} )

which implies that

(xu _{n)} _{n} is uniformly distributed modulo 1 for all irrationals x .^[18]

Relationship with one-dimensional Ising model

Let the binary expansion of n be given by

n = \sum _{k} \epsilon _{k(n)} 2 ^{k}

where

\epsilon _{k(n)} \in \{ 0 , 1 \} . Recall that the complete Rudin–Shapiro sequence is defined byu(n) = \sum _{k} \epsilon _{k(n)\epsilon} _{k+1} (n).

Let

\tilde{\epsilon} _{k(n)} = \begin{cases} \epsilon _{k(n)} & if k \le N -1 , \\ \epsilon _{0(n)&} if k = N. \end{cases}

Then let

u(n,N) = \sum _{0} \tilde{\epsilon} _{k(n)\tilde{\epsilon}} _{k+1} (n).

Finally, let

S(N,x) = \sum _{0 \le n < 2 ^{N}} \exp( 2 \pi ixu(n,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 η = ( η _{0,...,η} _{N-1} ) with each η _{i} \in \{ -1 , 1 \} . For any sequence of spins \sigma = (\sigma _{0,...,\sigma} _{N-1} ) with each \sigma _{i} \in \{ -1 , 1 \} , define its Hamiltonian byH _{η} (\sigma) = - J\sum _{0} η _{k} \sigma _{k} \sigma _{k+1} - H \sum _{0} \sigma _{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 Boltzmann's constant. The partition function is defined byZ _{N(η,J,H,\beta)} = \sum ^{N}} _{\sigma \in \{ -1 , 1 \} \exp( - \beta H _{η} (\sigma)).

Then we have

S(N,x) = \exp\left( (\pi iNx)/(2) \right)Z _{N\left( 1 , (1)/(2)} , -1 ,\pi ix\right)

where the weight sequence

η = ( η _{0,...,η} _{N-1} ) satisfies η _{i} = 1 for all i .^[19]

See also

• Shapiro polynomials

References

• Book: Allouche . Jean-Paul . Shallit . Jeffrey . Jeffrey Shallit . 978-0-521-82332-6 . . Automatic Sequences: Theory, Applications, Generalizations . 2003 . 1086.11015 .
• Book: Everest . Graham . van der Poorten . Alf . Shparlinski . Igor . Ward . Thomas . Recurrence sequences . Mathematical Surveys and Monographs . 104 . . . 2003 . 0-8218-3387-1 . 1033.11006 .
• Book: Pytheas Fogg, N. . Berthé, Valérie. Valérie Berthé. Ferenczi, Sébastien. Mauduit, Christian. Siegel, Anne . Substitutions in dynamics, arithmetics and combinatorics . Lecture Notes in Mathematics . 1794 . Berlin . . 2002 . 3-540-44141-7 . 1014.11015 .
• Book: Mendès France, Michel . 0724.11010 . The Rudin-Shapiro sequence, Ising chain, and paperfolding . 367–390 . Berndt . Bruce C. . Bruce C. Berndt . Diamond . Harold G. . Halberstam . Heini . Heini Halberstam . 3 . Hildebrand . Adolf . 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 . 1990 . 0-8176-3481-9 .

Notes and References

1. A Case Study in Mathematical Research: The Golay–Rudin–Shapiro Sequence. John Brillhart and Patrick Morton, winners of a 1997 Lester R. Ford Award. Amer. Math. Monthly. 1996. 103. 10 . 854–869. 10.2307/2974610. 2974610 .
2. Everest et al (2003) p.234
3. Golay . M.J.E. . Multi-slit spectrometry . Journal of the Optical Society of America. 1949 . 39 . 437–444. 437–444 . 10.1364/JOSA.39.000437 . 18152021 .
4. Golay . M.J.E. . Static multislit spectrometry and its application to the panoramic display of infrared spectra. . Journal of the Optical Society of America. 1951 . 41 . 7 . 468–472. 10.1364/JOSA.41.000468 . 14851129 .
5. Rudin . W. . Some theorems on Fourier coefficients. . . 1959 . 10 . 6 . 855–859. 10.1090/S0002-9939-1959-0116184-5 . free .
6. Shapiro . H.S. . Extremal problems for polynomials and power series. . Master's Thesis, MIT. . 1952.
7. Salem . R. . Zygmund . A. . Some properties of trigonometric series whose terms have random signs. . . 1954 . 91 . 245–301. 10.1007/BF02393433 . 122999383 . free .
8. Allouche and Shallit (2003) p. 78–79
9. Allouche and Shallit (2003) p. 122
10. Brillhart . J. . Morton . P. . Über Summen von Rudin–Shapiroschen Koeffizienten. . . 1978 . 22 . 126–148. 10.1215/ijm/1256048841 . free .
11. Saffari . B. . Une fonction extrémale liée à la suite de Rudin–Shapiro. . . 1986 . 303 . 97–100.
12. Allouche . J.-P. . Choi . S. . Denise . A. . Erdélyi . T. . Saffari . B. . Bounds on Autocorrelation Coefficients of Rudin-Shapiro Polynomials . Analysis Mathematica . 2019 . 45 . 4 . 705–726. 10.1007/s10476-019-0003-4 . 1901.06832 . 119168430 .
13. http://www.emis.de/journals/SLC/opapers/s30allouche.pdf Finite automata and arithmetic
14. Allouche and Shallit (2003) p. 192
15. Pytheas Fogg (2002) p.42
16. Allouche and Shallit (2003) p. 352
17. Müllner . C. . The Rudin–Shapiro sequence and similar sequences are normal along squares. . Canadian Journal of Mathematics . 2018 . 70 . 5 . 1096–1129. 10.4153/CJM-2017-053-1 . 1704.06472 . 125493369 .
18. Allouche and Shallit p. 462–464
19. Allouche and Shallit (2003) p. 457–461