Rudin–Shapiro sequence

From HandWiki

In mathematics, the Rudin–Shapiro sequence, also known as the Golay–Rudin–Shapiro sequence, is an infinite 2-automatic sequence named after Marcel Golay, Walter Rudin, and Harold S. Shapiro, who independently investigated its properties.[1]

Definition

Each term of the Rudin–Shapiro sequence is either [math]\displaystyle{ 1 }[/math] or [math]\displaystyle{ -1 }[/math]. If the binary expansion of [math]\displaystyle{ n }[/math] is given by

[math]\displaystyle{ n = \sum_{k \ge 0} \epsilon_k(n) 2^k, }[/math]

then let

[math]\displaystyle{ u_n = \sum_{k \ge 0} \epsilon_k(n)\epsilon_{k+1}(n). }[/math]

(So [math]\displaystyle{ u_n }[/math] is the number of times the block 11 appears in the binary expansion of [math]\displaystyle{ n }[/math].)

The Rudin–Shapiro sequence [math]\displaystyle{ (r_n)_{n \ge 0} }[/math] is then defined by

[math]\displaystyle{ r_n = (-1)^{u_n}. }[/math]

Thus [math]\displaystyle{ r_n = 1 }[/math] if [math]\displaystyle{ u_n }[/math] is even and [math]\displaystyle{ r_n = -1 }[/math] if [math]\displaystyle{ u_n }[/math] is odd.[2][3][4]

The sequence [math]\displaystyle{ u_n }[/math] is known as the complete Rudin–Shapiro sequence, and starting at [math]\displaystyle{ n = 0 }[/math], 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 [math]\displaystyle{ r_n }[/math] 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, [math]\displaystyle{ u_6 = 1 }[/math] and [math]\displaystyle{ r_6 = -1 }[/math] because the binary representation of 6 is 110, which contains one occurrence of 11; whereas [math]\displaystyle{ u_7 = 2 }[/math] and [math]\displaystyle{ r_7 = 1 }[/math] 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,[5][6] Rudin,[7] and Shapiro.[8] The following is a description of Rudin's motivation. In Fourier analysis, one is often concerned with the [math]\displaystyle{ L^2 }[/math] norm of a measurable function [math]\displaystyle{ f \colon [0,2\pi) \to [0,2\pi) }[/math]. This norm is defined by

[math]\displaystyle{ ||f||_2 = \left(\frac{1}{2\pi} \int_0^{2\pi} |f(t)|^2\,\mathrm{d}t\right)^{1/2}. }[/math]

One can prove that for any sequence [math]\displaystyle{ (a_n)_{n \ge 0} }[/math] with each [math]\displaystyle{ a_n }[/math] in [math]\displaystyle{ \{1,-1\} }[/math],

[math]\displaystyle{ \sup_{x \in \R} \left|\sum_{0 \le n \lt N} a_n e^{inx}\right| \ge \left|\left|\sum_{0 \le n \lt N} a_n e^{inx}\right|\right|_2 = \sqrt{N}. }[/math]

Moreover, for almost every sequence [math]\displaystyle{ (a_n)_{n \ge 0} }[/math] with each [math]\displaystyle{ a_n }[/math] is in [math]\displaystyle{ \{-1,1\} }[/math],

[math]\displaystyle{ \sup_{x \in \R} \left|\sum_{0 \le n \lt N} a_n e^{inx} \right| = O(\sqrt{N \log N}). }[/math][9]

However, the Rudin–Shapiro sequence [math]\displaystyle{ (r_n)_{n \ge 0} }[/math] satisfies a tighter bound:[10] there exists a constant [math]\displaystyle{ C \gt 0 }[/math] such that

[math]\displaystyle{ \sup_{x \in \R} \left|\sum_{0 \le n \lt N} r_n e^{inx} \right| \le C\sqrt{N}. }[/math]

It is conjectured that one can take [math]\displaystyle{ C = \sqrt{6} }[/math],[11] but while it is known that [math]\displaystyle{ C \ge \sqrt{6} }[/math],[12] the best published upper bound is currently [math]\displaystyle{ C \le (2+\sqrt{2})\sqrt{3/5} }[/math].[13] Let [math]\displaystyle{ P_n }[/math] be the n-th Shapiro polynomial. Then, when [math]\displaystyle{ N = 2^n-1 }[/math], the above inequality gives a bound on [math]\displaystyle{ \sup_{x \in \R} |P_n(e^{ix})| }[/math]. More recently, bounds have also been given for the magnitude of the coefficients of [math]\displaystyle{ |P_n(z)|^2 }[/math] where [math]\displaystyle{ |z| = 1 }[/math].[14]

Shapiro arrived at the sequence because the polynomials

[math]\displaystyle{ P_n(z) = \sum_{i=0}^{2^n-1} r_i z^i }[/math]

where [math]\displaystyle{ (r_i)_{i \ge 0} }[/math] is the Rudin–Shapiro sequence, have absolute value bounded on the complex unit circle by [math]\displaystyle{ 2^{\frac{n+1}{2}} }[/math]. 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.[15] The sequence is therefore 2-automatic, so by Cobham's little theorem there exists a 2-uniform morphism [math]\displaystyle{ \varphi }[/math] with fixed point [math]\displaystyle{ w }[/math] and a coding [math]\displaystyle{ \tau }[/math] such that [math]\displaystyle{ r = \tau(w) }[/math], where [math]\displaystyle{ r }[/math] is the Rudin–Shapiro sequence. However, the Rudin–Shapiro sequence cannot be expressed as the fixed point of some uniform morphism alone.[16]

There is a recursive definition[3]

[math]\displaystyle{ \begin{cases} r_{2n} & = r_n \\ r_{2n+1} & = (-1)^n r_n \end{cases} }[/math]

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

[math]\displaystyle{ 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} }[/math]
[math]\displaystyle{ 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} }[/math]

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 [math]\displaystyle{ \varphi }[/math] that requires a coding [math]\displaystyle{ \tau }[/math] to generate the Rudin-Shapiro sequence is the following:[math]\displaystyle{ \begin{align} \varphi: a&\to ab\\ b&\to ac\\ c&\to db\\ d&\to dc \end{align} }[/math] [math]\displaystyle{ \begin{align} \tau: a&\to 1\\ b&\to 1\\ c&\to -1\\ d&\to -1 \end{align} }[/math]

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

[math]\displaystyle{ s_n = \sum_{k=0}^n r_k \, , }[/math]

with values

1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 7, 6, 5, 4, 5, 4, ... (sequence A020986 in the OEIS)

can be shown to satisfy the inequality

[math]\displaystyle{ \sqrt{\frac{3}{5} n} \lt s_n \lt \sqrt{6n} \text{ for } n \ge 1 \, . }[/math][1]

Let [math]\displaystyle{ (s_n)_{n \ge 0} }[/math] denote the Rudin–Shapiro sequence on [math]\displaystyle{ \{0,1\} }[/math], in which case [math]\displaystyle{ s_n }[/math] is the number, modulo 2, of occurrences (possibly overlapping) of the block [math]\displaystyle{ 11 }[/math] in the base-2 expansion of [math]\displaystyle{ n }[/math]. Then the generating function

[math]\displaystyle{ S(X) = \sum_{n \ge 0} s_n X^n }[/math]

satisfies

[math]\displaystyle{ (1+X)^5 S(X)^2 + (1+X)^4 S(X) + X^3 = 0, }[/math]

making it algebraic as a formal power series over [math]\displaystyle{ \mathbb{F}_2(X) }[/math].[17] The algebraicity of [math]\displaystyle{ S(X) }[/math] over [math]\displaystyle{ \mathbb{F}_2(X) }[/math] follows from the 2-automaticity of [math]\displaystyle{ (s_n)_{n \ge 0} }[/math] by Christol's theorem.

The Rudin–Shapiro sequence along squares [math]\displaystyle{ (r_{n^2})_{n \ge 0} }[/math] is normal.[18]

The complete Rudin–Shapiro sequence satisfies the following uniform distribution result. If [math]\displaystyle{ x \in \mathbb{R} \setminus \mathbb{Z} }[/math], then there exists [math]\displaystyle{ \alpha = \alpha(x) \in (0,1) }[/math] such that

[math]\displaystyle{ \sum_{n \lt N} \exp(2\pi ixu_n) = O(N^{\alpha}) }[/math]

which implies that [math]\displaystyle{ (xu_n)_{n \ge 0} }[/math] is uniformly distributed modulo [math]\displaystyle{ 1 }[/math] for all irrationals [math]\displaystyle{ x }[/math].[19]

Relationship with one-dimensional Ising model

Let the binary expansion of n be given by

[math]\displaystyle{ n = \sum_{k \ge 0} \epsilon_k(n) 2^k }[/math]

where [math]\displaystyle{ \epsilon_k(n) \in \{0,1\} }[/math]. Recall that the complete Rudin–Shapiro sequence is defined by

[math]\displaystyle{ u(n) = \sum_{k \ge 0} \epsilon_k(n)\epsilon_{k+1}(n). }[/math]

Let

[math]\displaystyle{ \tilde{\epsilon}_k(n) = \begin{cases} \epsilon_k(n) & \text{if } k \le N-1, \\ \epsilon_0(n)& \text{if } k = N. \end{cases} }[/math]

Then let

[math]\displaystyle{ u(n,N) = \sum_{0 \le k \lt N} \tilde{\epsilon}_k(n)\tilde{\epsilon}_{k+1}(n). }[/math]

Finally, let

[math]\displaystyle{ S(N,x) = \sum_{0 \le n \lt 2^N} \exp(2\pi ixu(n,N)). }[/math]

Recall that the partition function of the one-dimensional Ising model can be defined as follows. Fix [math]\displaystyle{ N \ge 1 }[/math] representing the number of sites, and fix constants [math]\displaystyle{ J \gt 0 }[/math] and [math]\displaystyle{ H \gt 0 }[/math] representing the coupling constant and external field strength, respectively. Choose a sequence of weights [math]\displaystyle{ \eta = (\eta_0,\dots,\eta_{N-1}) }[/math] with each [math]\displaystyle{ \eta_i \in \{-1,1\} }[/math]. For any sequence of spins [math]\displaystyle{ \sigma = (\sigma_0,\dots,\sigma_{N-1}) }[/math] with each [math]\displaystyle{ \sigma_i \in \{-1,1\} }[/math], define its Hamiltonian by

[math]\displaystyle{ H_{\eta}(\sigma) = -J\sum_{0 \le k \lt N} \eta_k \sigma_k \sigma_{k+1} - H \sum_{0 \le k \lt N} \sigma_k. }[/math]

Let [math]\displaystyle{ T }[/math] be a constant representing the temperature, which is allowed to be an arbitrary non-zero complex number, and set [math]\displaystyle{ \beta = 1/(kT) }[/math] where [math]\displaystyle{ k }[/math] is Boltzmann's constant. The partition function is defined by

[math]\displaystyle{ Z_N(\eta,J,H,\beta) = \sum_{\sigma \in \{-1,1\}^N} \exp(-\beta H_{\eta}(\sigma)). }[/math]

Then we have

[math]\displaystyle{ S(N,x) = \exp\left(\frac{\pi iNx}{2}\right)Z_N\left(1,\frac{1}{2},-1,\pi ix\right) }[/math]

where the weight sequence [math]\displaystyle{ \eta = (\eta_0,\dots,\eta_{N-1}) }[/math] satisfies [math]\displaystyle{ \eta_i = 1 }[/math] for all [math]\displaystyle{ i }[/math].[20]

See also

Notes

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

References

  • Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. ISBN 978-0-521-82332-6. 
  • Everest, Graham; van der Poorten, Alf; Shparlinski, Igor; Ward, Thomas (2003). Recurrence sequences. Mathematical Surveys and Monographs. 104. Providence, RI: American Mathematical Society. ISBN 0-8218-3387-1. 
  • Pytheas Fogg, N. (2002). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. 1794. Berlin: Springer-Verlag. ISBN 3-540-44141-7. 
  • Mendès France, Michel (1990). "The Rudin-Shapiro sequence, Ising chain, and paperfolding". in Berndt, Bruce C.; Diamond, Harold G.; Halberstam, Heini et al.. 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. pp. 367–390. ISBN 0-8176-3481-9. 



Retrieved from "https://handwiki.org/wiki/index.php?title=Rudin–Shapiro_sequence&oldid=3366814"