Rudin–Shapiro-sekvensen

Inom matematik är Rudin –Shapiro-sekvensen , även känd som Golay–Rudin–Shapiro-sekvensen , en oändlig 2- automatisk sekvens uppkallad efter Marcel Golay , Walter Rudin och Harold S. Shapiro , som självständigt undersökte dess egenskaper.

Definition

Varje term i Rudin–Shapiro-sekvensen är antingen $1$ eller $-1$ . Om den binära expansionen av $n$ ges av

$n=\sum _{k\geq 0}\epsilon _{k}(n)2^{k},$

låt sedan

$u_{n}=\sum _{k\geq 0}\epsilon _{k}(n)\epsilon _{k+1}(n).$

(Så $u_{n}$ är antalet gånger blocket 11 visas i den binära expansionen av $n$ .)

Rudin–Shapiro-sekvensen $(r_{n})_{n\geq 0}$ definieras sedan av

$r_{n}=(-1)^{u_{n}}.$

Alltså $r_{n}=1$ om $u_{n}$ är jämn och $r_{n}=-1$ om ${\ displaystyle u_{n}}$ är udda.

Sekvensen $u_{n}$ är känd som den fullständiga Rudin–Shapiro-sekvensen, och med början på $n=0$ är dess första termer:

0, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 1, 1, 1, 2, 3, ... (sekvens A014081 i OEIS )

och motsvarande termer $r_{n}$ i Rudin–Shapiro-sekvensen är:

+1, +1, +1, −1, +1, +1, −1, +1, +1, +1, +1, −1, −1, −1, +1, −1, .. . (sekvens A020985 i OEIS )

Till exempel, $u_{6}=1$ och $r_{6}=-1$ eftersom den binära representationen av 6 är 110, vilket innehåller en förekomst av 11; medan $u_{7}=2$ och $r_{7}=1$ eftersom den binära representationen av 7 är 111, som innehåller två (överlappande) förekomster av 11.

Historisk motivation

Rudin–Shapiro-sekvensen introducerades oberoende av Golay, Rudin och Shapiro. Nedan följer en beskrivning av Rudins motivation. I Fourieranalys är man ofta oroad över $L^{2}$ -normen för en mätbar funktion $f\colon [0,2\ pi )\till [0,2\pi )$ . Denna norm definieras av

$||f||_{2}=\left({\frac {1}{2\pi }}\int _{0}^{2\pi}|f(t)|^{2} \,\mathrm {d} t\right)^{1/2}.$

Man kan bevisa att för vilken sekvens som helst $(a_{n})_{n\geq 0}$ med varje $a_{n}$ i ${ \displaystyle \{1,-1\}}$ ,

$\sup _{x\in \mathbb {R} }\left|\sum _{0\leq n<N}a_{n}e^{inx}\right|\geq \left|\left| \sum _{0\leq n<N}a_{n}e^{inx}\right|\right|_{2}={\sqrt {N}}.$

Dessutom, för nästan varje sekvens $(a_{n})_{n\geq 0}$ med varje $a_{n}$ är i ${ \displaystyle \{-1,1\}}$ ,

$\sup _{x\in \mathbb {R} }\left|\sum _{0\leq n<N}a_{n}e^{inx}\right|=O({\sqrt {N \log N}}).$

Rudin–Shapiro-sekvensen $(r_{n})_{n\geq 0}$ uppfyller dock en snävare gräns: det finns en konstant $C>0$ så att

$\sup _{x\in \mathbb {R} }\left|\sum _{0\leq n<N}r_{n}e^{inx}\right|\leq C{\sqrt {N }}.$

Det förmodas att man kan ta ${\displaystyle C={\sqrt {6}}} ,$ men medan det är känt att $C\geq {\sqrt {6}}$ är det bästa publicerad övre gräns är för närvarande $C\leq (2+{\sqrt {2}}){\sqrt {3/5}}$ . Låt $P_{n}$ vara det n -te Shapiropolynomet . Då, när $N=2^{n}-1$ , ger ovanstående olikhet en gräns på $\sup _{x\in \mathbb {R} }|P_{n}(e^{ix})|$ . På senare tid har gränser också angetts för storleken på koefficienterna för $|P_{n}(z)|^{2}$ där $|z|=1$ .

Shapiro kom fram till sekvensen eftersom polynomen

$P_{n}(z)=\summa _{i=0}^{2^{n}-1}r_{i} z^{i}$

där $(r_{i})_{i\geq 0}$ är Rudin–Shapiro-sekvensen, har ett absolut värde begränsat på den komplexa enhetscirkeln av $2 ^{\frac {n+1}{2}}$ . Detta diskuteras mer i detalj i artikeln om Shapiropolynom . Golays motivation var liknande, även om han var oroad över tillämpningar till spektroskopi och publicerades i en optiktidskrift.

Egenskaper

Rudin–Shapiro-sekvensen kan genereras av en 4-tillståndsautomat som accepterar binära representationer av icke-negativa heltal som indata. Sekvensen är därför 2-automatisk, så enligt Cobhams lilla teorem finns det en 2-uniform morfism $\varphi$ med fixpunkt $w$ och en kodning $\tau$ så att $r=\tau (w)$ , där $r$ är Rudin–Shapiro-sekvensen. Emellertid kan Rudin–Shapiro-sekvensen inte uttryckas enbart som den fasta punkten för någon enhetlig morfism.

Det finns en rekursiv definition

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

Värdena för termerna a _n och b _n i Rudin–Shapiro-sekvensen kan hittas rekursivt enligt följande. Om n = m ·2 ^k där m är udda då

$a_{n}={\begin{ fall}a_{(m-1)/4}&{\text{if }}m\equiv 1{\pmod {4}}\\a_{(m-1)/2}+1&{\text{if }}m\equiv 3{\pmod {4}}\end{cases}}$

$b_{n}={\begin{cases}b_{(m-1)/4}&{\text{if }}m\equiv 1{\pmod {4}} \\-b_{(m-1)/2}&{\text{if }}m\equiv 3{\pmod {4}}\end{cases}}$

₀ Således a ₁₀₈ = a ₁₃ + 1 = a ₃ + 1 = a ₁ + 2 = a + 2 = 2, vilket kan verifieras genom att observera att den binära representationen av 108, vilket är 1101100, innehåller två delsträngar 11. Och så b ₁₀₈ = (−1) ² = +1.

En 2-uniform morfism $\varphi$ som kräver en kodande $\tau$ för att generera Rudin-Shapiro-sekvensen är följande:

$${\begin{aligned}\varphi :a&\to ab\\b&\to ac\\c&\to db\\d&\ till dc\end{aligned}}$$

$${\begin{aligned}\tau :a&\to 1\\b&\to 1\\c&\to -1\\d&\to -1\end{aligned}}$$

Rudin–Shapiro-ordet +1 +1 +1 −1 +1 +1 −1 +1 +1 +1 +1 −1 −1 −1 +1 −1 ..., som skapas genom att sammanfoga termerna i Rudin–Shapiro - sekvensen, är en fast punkt i morfismen eller strängersättningsreglerna

+1 +1 → +1 +1 +1 −1

+1 −1 → +1 +1 −1 +1

−1 +1 → −1 −1 +1 −1

−1 −1 → −1 −1 −1 +1

som följer:

+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 ...

Det kan ses av morfismreglerna att Rudin–Shapiro-strängen innehåller högst fyra på varandra följande +1:or och högst fyra på varandra följande −1:or.

Sekvensen av delsummor av Rudin–Shapiro-sekvensen, definierad av

$s_{n}=\summa _{k=0}^{n}b_{k}\,,$

med värderingar

1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 7, 6, 5, 4, 5, 4, ... (sekvens A020986 i OEIS )

kan visa sig tillfredsställa ojämlikheten

${\sqrt {{\frac {3}{5}}n}}<s_{n}<{\sqrt {6n}}{\text{ för }}n\geq 1\,.$

Om $(s_{n})_{n\geq 0}$ anger Rudin–Shapiro-sekvensen på ${\displaystyle \{0,1\}} ,$ som ges genom ${\displaystyle s_{n}\equiv e_{2;11}(n){\pmod {2}}} ,$ sedan genereringsfunktionen

$S(X)=\summa _{n\geq 0}s_{n}X^{n}$

tillfredsställer

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

vilket gör den algebraisk som en formell potensserie över $\mathbb {F} _{2}(X)$ . Algebraiciteten för $S(X)$ över $\mathbb {F} _{2}(X)$ följer av 2-automatiken för $(s_{n})_{n\geq 0}$ av Christols teorem .

Rudin–Shapiro-sekvensen längs kvadrater $(r_{n^{2}})_{n\geq 0}$ är normal.

Den kompletta Rudin–Shapiro-sekvensen uppfyller följande enhetliga fördelningsresultat. Om ${\displaystyle x\in \mathbb {R} \setminus \mathbb {Z} } ,$ så finns det $\alpha =\alpha (x )\in (0,1)$ så att

$\sum _{n<N}\exp(2\pi ixu_{n})=O(N^{\alpha })$

vilket innebär att $(xu_{n})_{n\geq 0}$ är enhetligt fördelad modulo $1$ för alla irrationaler $x$ .

Samband med endimensionell Ising-modell

Låt den binära expansionen av n ges av

$n=\summa _{k\geq 0}\epsilon _{k}(n)2^{k}$

där $\epsilon _{k}(n)\in \{0,1\}$ . Kom ihåg att den fullständiga Rudin–Shapiro-sekvensen definieras av

$u(n)=\sum _{k\geq 0}\epsilon _{k}(n)\epsilon _{k+1}(n).$

Låta

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

Låt sedan

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

Slutligen, låt

$S(N,x)=\summa _{0\leq n<2^{N}}\exp(2\pi ixu(n,N)).$

Kom ihåg att partitionsfunktionen för den endimensionella Ising-modellen kan definieras enligt följande. Fix $N\geq 1$ som representerar antalet platser, och fixkonstanter $J>0$ och $H>0$ som representerar kopplingskonstanten och extern fältstyrka, respektive . Välj en sekvens av vikter $\eta =(\eta _{0},\dots ,\eta _{N-1})$ med varje $\eta _{i}\in \{-1,1\}$ . För alla snurrsekvenser $\sigma =(\sigma _{0},\dots ,\sigma _{N-1})$ med varje $\sigma _{i}\in \{-1,1\}$ , definiera dess Hamiltonian med

$H_{\eta }(\sigma )=-J\summa _{0\leq k<N}\eta _{k}\sigma _{k}\sigma _{k+1}-H\summa _{0\leq k<N}\sigma _{k}.$

Låt $T$ vara en konstant som representerar temperaturen, som tillåts vara ett godtyckligt icke-noll komplext tal, och sätt $\beta =1/(kT)$ där $k$ är Boltzmanns konstant . Partitionsfunktionen definieras av

$Z_{N}(\eta ,J,H,\beta )=\summa _{\sigma \in \{-1,1\}^{N}}\exp(-\beta H_{\eta }(\sigma )).$

Då har vi

$S(N,x)=\exp \left({\frac { \pi iNx}{2}}\right)Z_{N}\left(1,{\frac {1}{2}},-1,\pi ix\right)$

där viktsekvensen $\eta =(\eta _{0},\dots ,\eta _{N-1})$ uppfyller ${\ displaystyle \eta _{i}=1}$ för alla $i$ .

Se även

• Shapiro polynom

Anteckningar

•    Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatiska sekvenser: teori, tillämpningar, generaliseringar . Cambridge University Press . ISBN 978-0-521-82332-6 . Zbl 1086.11015 .
•    Everest, Graham; van der Poorten, Alf; Shparlinski, Igor; Ward, Thomas (2003). Återkommande sekvenser . Matematiska undersökningar och monografier. Vol. 104. Providence, RI : American Mathematical Society . ISBN 0-8218-3387-1 . Zbl 1033.11006 .
•    Pytheas Fogg, N. (2002). Berthé, Valérie ; Ferenczi, Sébastien; Mauduit, Christian; Siegel, Anne (red.). Substitutioner i dynamik, aritmetik och kombinatorik . Föreläsningsanteckningar i matematik. Vol. 1794. Berlin: Springer-Verlag . ISBN 3-540-44141-7 . Zbl 1014.11015 .
•    Mendès Frankrike, Michel (1990). "Rudin-Shapiro-sekvensen, Ising-kedjan och pappersvikning". I Berndt, Bruce C .; Diamond, Harold G.; Halberstam, Heini ; et al. (red.). Analytisk talteori. Handlingar från en konferens till Paul T. Batemans ära, som hölls den 25–27 april 1989, vid University of Illinois, Urbana, IL (USA) . Framsteg i matematik. Vol. 85. Boston: Birkhäuser. s. 367–390. ISBN 0-8176-3481-9 . Zbl 0724.11010 .