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\; =\; \backslash sum\_\{k\; \backslash ge\; 0\}\; \backslash epsilon\_k(n)\; 2^k,$

then let

: $u\_n\; =\; \backslash sum\_\{k\; \backslash ge\; 0\}\; \backslash epsilon\_k(n)\backslash 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\; \backslash 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.{{MathWorld|urlname=Rudin-ShapiroSequence|title=Rudin–Shapiro Sequence}}Everest et al (2003) p.234

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, ... {{OEIS|A014081}}

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, ... {{OEIS|A020985}}

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.

The Rudin–Shapiro sequence was introduced independently by Golay,{{cite journal |last1=Golay |first1=M.J.E. |title=Multi-slit spectrometry |journal= Journal of the Optical Society of America|date=1949 |volume=39 |issue=437–444|pages=437–444 |doi=10.1364/JOSA.39.000437 |pmid=18152021 }}{{cite journal |last1=Golay |first1=M.J.E. |title=Static multislit spectrometry and its application to the panoramic display of infrared spectra. |journal= Journal of the Optical Society of America|date=1951 |volume=41 |issue=7 |pages=468–472|doi=10.1364/JOSA.41.000468 |pmid=14851129 }} Rudin,{{cite journal |last1=Rudin |first1=W. |title=Some theorems on Fourier coefficients. |journal=Proceedings of the American Mathematical Society |date=1959 |volume=10 |issue=6 |pages=855–859|doi=10.1090/S0002-9939-1959-0116184-5 |doi-access=free }} and Shapiro.{{cite journal |last1=Shapiro |first1=H.S. |title=Extremal problems for polynomials and power series. |journal=Master's Thesis, MIT. |date=1952}} 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\; \backslash colon\; [0,2\backslash pi)\; \backslash to\; [0,2\backslash pi)$. This norm is defined by

: $$

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

One can prove that for any sequence $(a\_n)\_\{n\; \backslash ge\; 0\}$ with each $a\_n$ in $\backslash \{1,-1\backslash \}$,

:

Moreover, for almost every sequence $(a\_n)\_\{n\; \backslash ge\; 0\}$ with each $a\_n$ is in $\backslash \{-1,1\backslash \}$,

: $$

\sup_{x \in \R} \left|\sum_{0 \le n < N} a_n e^{inx} \right| = O(\sqrt{N \log N}).{{cite journal |last1=Salem |first1=R. |last2=Zygmund |first2=A. |title=Some properties of trigonometric series whose terms have random signs. |journal=Acta Mathematica |date=1954 |volume=91 |pages=245–301|doi=10.1007/BF02393433 |s2cid=122999383 |doi-access=free }}

However, the Rudin–Shapiro sequence $(r\_n)\_\{n\; \backslash ge\; 0\}$ satisfies a tighter bound:Allouche and Shallit (2003) p. 78–79 there exists a constant $C\; >\; 0$ such that

: $$

\sup_{x \in \R} \left|\sum_{0 \le n < N} r_n e^{inx} \right| \le C\sqrt{N}.

It is conjectured that one can take $C\; =\; \backslash sqrt\{6\}$,Allouche and Shallit (2003) p. 122 but while it is known that $C\; \backslash ge\; \backslash sqrt\{6\}$,{{cite journal |last1=Brillhart |first1=J. |last2=Morton |first2=P. |title=Über Summen von Rudin–Shapiroschen Koeffizienten. |journal=Illinois Journal of Mathematics |date=1978 |volume=22 |pages=126–148|doi=10.1215/ijm/1256048841 |doi-access=free }} the best published upper bound is currently $C\; \backslash le\; (2+\backslash sqrt\{2\})\backslash sqrt\{3/5\}$.{{cite journal |last1=Saffari |first1=B. |title=Une fonction extrémale liée à la suite de Rudin–Shapiro. |journal=C. R. Acad. Sci. Paris |date=1986 |volume=303 |pages=97–100}} Let $P\_n$ be the n-th Shapiro polynomial. Then, when $N\; =\; 2^n-1$, the above inequality gives a bound on $\backslash sup\_\{x\; \backslash in\; \backslash 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$.{{cite journal |last1=Allouche |first1=J.-P. |last2=Choi |first2=S. |last3=Denise |first3=A. |last4=Erdélyi |first4=T. |last5=Saffari |first5=B. |title=Bounds on Autocorrelation Coefficients of Rudin-Shapiro Polynomials |journal=Analysis Mathematica |date=2019 |volume=45 |issue=4 |pages=705–726|doi=10.1007/s10476-019-0003-4 |arxiv=1901.06832 |s2cid=119168430 }}

Shapiro arrived at the sequence because the polynomials

: $P\_n(z)\; =\; \backslash sum\_\{i=0\}^\{2^n-1\}\; r\_i\; z^i$

where $(r\_i)\_\{i\; \backslash ge\; 0\}$ is the Rudin–Shapiro sequence, have absolute value bounded on the complex unit circle by $2^\{\backslash 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.

The Rudin–Shapiro sequence can be generated by a 4-state automaton accepting binary representations of non-negative integers as input.[http://www.emis.de/journals/SLC/opapers/s30allouche.pdf Finite automata and arithmetic], Jean-Paul Allouche The sequence is therefore 2-automatic, so by Cobham's little theorem there exists a 2-uniform morphism $\backslash varphi$ with fixed point $w$ and a coding $\backslash tau$ such that $r\; =\; \backslash 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.Allouche and Shallit (2003) p. 192

There is a recursive definitionPytheas Fogg (2002) p.42

: $$

\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} & \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 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 $\backslash varphi$ that requires a coding $\backslash tau$ to generate the Rudin-Shapiro sequence is the following:$$\backslash begin\{align\}$$

\varphi: a&\to ab\\

b&\to ac\\

c&\to db\\

d&\to dc

\end{align} $$\backslash 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\; =\; \backslash sum\_\{k=0\}^n\; r\_k\; \backslash ,\; ,$

with values

: 1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 7, 6, 5, 4, 5, 4, ... {{OEIS|A020986}}

can be shown to satisfy the inequality

:

Let $(s\_n)\_\{n\; \backslash ge\; 0\}$ denote the Rudin–Shapiro sequence on $\backslash \{0,1\backslash \}$, 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 function

: $S(X)\; =\; \backslash sum\_\{n\; \backslash ge\; 0\}\; 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 $\backslash mathbb\{F\}\_2(X)$.Allouche and Shallit (2003) p. 352 The algebraicity of $S(X)$ over $\backslash mathbb\{F\}\_2(X)$ follows from the 2-automaticity of $(s\_n)\_\{n\; \backslash ge\; 0\}$ by Christol's theorem.

The Rudin–Shapiro sequence along squares $(r\_\{n^2\})\_\{n\; \backslash ge\; 0\}$ is normal.{{cite journal |last1=Müllner |first1=C. |title=The Rudin–Shapiro sequence and similar sequences are normal along squares. |journal=Canadian Journal of Mathematics |year=2018 |volume=70 |issue=5 |pages=1096–1129|doi=10.4153/CJM-2017-053-1 |arxiv=1704.06472 |s2cid=125493369 }}

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

:

which implies that $(xu\_n)\_\{n\; \backslash ge\; 0\}$ is uniformly distributed modulo $1$ for all irrationals $x$.Allouche and Shallit p. 462–464

Let the binary expansion of n be given by

: $n\; =\; \backslash sum\_\{k\; \backslash ge\; 0\}\; \backslash epsilon\_k(n)\; 2^k$

where $\backslash epsilon\_k(n)\; \backslash in\; \backslash \{0,1\backslash \}$. Recall that the complete Rudin–Shapiro sequence is defined by

: $u(n)\; =\; \backslash sum\_\{k\; \backslash ge\; 0\}\; \backslash epsilon\_k(n)\backslash epsilon\_\{k+1\}(n).$

Let

: $\backslash tilde\{\backslash epsilon\}\_k(n)\; =\; \backslash begin\{cases\}$

\epsilon_k(n) & \text{if } k \le N-1, \\

\epsilon_0(n)& \text{if } k = N.

\end{cases}

Then let

:

Finally, let

:

Recall that the partition function of the one-dimensional Ising model can be defined as follows. Fix $N\; \backslash 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 $\backslash eta\; =\; (\backslash eta\_0,\backslash dots,\backslash eta\_\{N-1\})$ with each $\backslash eta\_i\; \backslash in\; \backslash \{-1,1\backslash \}$. For any sequence of spins $\backslash sigma\; =\; (\backslash sigma\_0,\backslash dots,\backslash sigma\_\{N-1\})$ with each $\backslash sigma\_i\; \backslash in\; \backslash \{-1,1\backslash \}$, define its Hamiltonian by

:

Let $T$ be a constant representing the temperature, which is allowed to be an arbitrary non-zero complex number, and set $\backslash beta\; =\; 1/(kT)$ where $k$ is the Boltzmann constant. The partition function is defined by

: $Z\_N(\backslash eta,J,H,\backslash beta)\; =\; \backslash sum\_\{\backslash sigma\; \backslash in\; \backslash \{-1,1\backslash \}^N\}\; \backslash exp(-\backslash beta\; H\_\{\backslash eta\}(\backslash sigma)).$

Then we have

: $S(N,x)\; =\; \backslash exp\backslash left(\backslash frac\{\backslash pi\; iNx\}\{2\}\backslash right)Z\_N\backslash left(1,\backslash frac\{1\}\{2\},-1,\backslash pi\; ix\backslash right)$

where the weight sequence $\backslash eta\; =\; (\backslash eta\_0,\backslash dots,\backslash eta\_\{N-1\})$ satisfies $\backslash eta\_i\; =\; 1$ for all $i$.Allouche and Shallit (2003) p. 457–461

• Shapiro polynomials

{{reflist}}

{{refbegin}}

{{refend}}

• {{cite book | last1 = Allouche | first1 = Jean-Paul | last2 = Shallit | first2 = Jeffrey | author2-link = Jeffrey Shallit | isbn = 978-0-521-82332-6 | publisher = Cambridge University Press | title = Automatic Sequences: Theory, Applications, Generalizations | year = 2003 | zbl=1086.11015 }}
• {{cite book | last1=Everest | first1=Graham | last2=van der Poorten | first2=Alf | last3=Shparlinski | first3=Igor | last4=Ward | first4=Thomas | title=Recurrence sequences | series=Mathematical Surveys and Monographs | volume=104 | location=Providence, RI | publisher=American Mathematical Society | year=2003 | isbn=0-8218-3387-1 | zbl=1033.11006 }}
• {{cite book | last=Pytheas Fogg | first=N. | editor1=Berthé, Valérie|editor1-link=Valérie Berthé|editor2=Ferenczi, Sébastien|editor3=Mauduit, Christian|editor4=Siegel, Anne | title=Substitutions in dynamics, arithmetics and combinatorics | series=Lecture Notes in Mathematics | volume=1794 | location=Berlin | publisher=Springer-Verlag | year=2002 | isbn=3-540-44141-7 | zbl=1014.11015 }}
• {{cite book | zbl=0724.11010 | last=Mendès France | first=Michel | chapter=The Rudin-Shapiro sequence, Ising chain, and paperfolding | pages=367–390 | editor1-last=Berndt | editor1-first=Bruce C. | editor1-link=Bruce C. Berndt | editor2-last=Diamond | editor2-first=Harold G. | editor3-last=Halberstam | editor3-first=Heini | editor3-link=Heini Halberstam |display-editors = 3 | editor4-last=Hildebrand | editor4-first=Adolf | title=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) | series=Progress in Mathematics | volume=85 | location=Boston | publisher=Birkhäuser | year=1990 | isbn=0-8176-3481-9 }}

{{DEFAULTSORT:Rudin-Shapiro sequence}}

Category:Binary sequences