Secuencia de Rudin-Shapiro

En matemáticas , la secuencia de Rudin-Shapiro , también conocida como secuencia de Golay-Rudin-Shapiro , es una secuencia automática infinita de 2 bits que lleva el nombre de Marcel Golay , Harold S. Shapiro y Walter Rudin , quienes investigaron sus propiedades. ^[1]

Definición

Cada término de la sucesión de Rudin–Shapiro es o . Si la expansión binaria de está dada por ${\displaystyle 1}$ ${\displaystyle -1}$ ${\displaystyle n}$

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

entonces deja

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

(También lo es el número de veces que aparece el bloque 11 en la expansión binaria de .) ${\displaystyle u_{n}}$ ${\displaystyle n}$

La secuencia de Rudin-Shapiro queda entonces definida por ${\displaystyle (r_{n})_{n\geq 0}}$

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

Por lo tanto, si es par y si es impar. ^{[2] [3] [4]} ${\displaystyle r_{n}=1}$ ${\displaystyle u_{n}}$ ${\displaystyle r_{n}=-1}$ ${\displaystyle u_{n}}$

La secuencia se conoce como secuencia completa de Rudin-Shapiro y, a partir de , sus primeros términos son: ${\displaystyle u_{n}}$ ${\displaystyle n=0}$

0, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 1, 1, 1, 2, 3, ... (secuencia A014081 en la OEIS )

y los términos correspondientes de la secuencia de Rudin-Shapiro son: ${\displaystyle r_{n}}$

+1, +1, +1, −1, +1, +1, −1, +1, +1, +1, −1, −1, −1, +1, −1, ... (secuencia A020985 en la OEIS )

Por ejemplo, y porque la representación binaria de 6 es 110, que contiene una ocurrencia de 11; mientras que y porque la representación binaria de 7 es 111, que contiene dos ocurrencias (superpuestas) de 11. ${\displaystyle u_{6}=1}$ ${\displaystyle r_{6}=-1}$ ${\displaystyle u_{7}=2}$ ${\displaystyle r_{7}=1}$

Motivación histórica

La secuencia de Rudin-Shapiro fue introducida independientemente por Golay, ^{[5] [6]} Rudin, ^[7] y Shapiro. ^[8] A continuación se describe la motivación de Rudin. En el análisis de Fourier , a menudo nos preocupamos por la norma de una función medible . Esta norma se define por ${\displaystyle L^{2}}$ ${\displaystyle f\colon [0,2\pi )\to [0,2\pi )}$

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

Se puede demostrar que para cualquier secuencia con cada uno en , ${\displaystyle (a_{n})_{n\geq 0}}$ ${\displaystyle a_{n}}$ ${\displaystyle \{1,-1\}}$

${\displaystyle \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}}.}$

Además, para casi todas las secuencias con cada uno está en , ${\displaystyle (a_{n})_{n\geq 0}}$ ${\displaystyle a_{n}}$ ${\displaystyle \{-1,1\}}$

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

Sin embargo, la secuencia de Rudin-Shapiro satisface un límite más estricto: ^[10] existe una constante tal que ${\displaystyle (r_{n})_{n\geq 0}}$ ${\displaystyle C>0}$

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

Se conjetura que se puede tomar , ^[11] pero mientras se sabe que , ^[12] el mejor límite superior publicado actualmente es . ^[13] Sea el n -ésimo polinomio de Shapiro . Entonces, cuando , la desigualdad anterior da un límite en . Más recientemente, también se han dado límites para la magnitud de los coeficientes de donde . ^[14] ${\displaystyle C={\sqrt {6}}}$ ${\displaystyle C\geq {\sqrt {6}}}$ ${\displaystyle C\leq (2+{\sqrt {2}}){\sqrt {3/5}}}$ ${\displaystyle P_{n}}$ ${\displaystyle N=2^{n}-1}$ ${\displaystyle \sup _{x\in \mathbb {R} }|P_{n}(e^{ix})|}$ ${\displaystyle |P_{n}(z)|^{2}}$ ${\displaystyle |z|=1}$

Shapiro llegó a la secuencia porque los polinomios

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

donde es la secuencia de Rudin–Shapiro, tiene valor absoluto acotado en el círculo unitario complejo por . Esto se analiza con más detalle en el artículo sobre polinomios de Shapiro . La motivación de Golay era similar, aunque estaba preocupado por las aplicaciones a la espectroscopia y publicó en una revista de óptica. ${\displaystyle (r_{i})_{i\geq 0}}$ ${\displaystyle 2^{\frac {n+1}{2}}}$

Propiedades

La secuencia de Rudin-Shapiro puede ser generada por un autómata de 4 estados que acepte representaciones binarias de números enteros no negativos como entrada. ^[15] Por lo tanto, la secuencia es 2-automática, por lo que por el pequeño teorema de Cobham existe un morfismo 2-uniforme con punto fijo y una codificación tal que , donde es la secuencia de Rudin-Shapiro. Sin embargo, la secuencia de Rudin-Shapiro no puede expresarse como el punto fijo de algún morfismo uniforme solo. ^[16] ${\displaystyle \varphi }$ ${\displaystyle w}$ ${\displaystyle \tau }$ ${\displaystyle r=\tau (w)}$ ${\displaystyle r}$

Existe una definición recursiva ^[3]

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

Los valores de los términos r _n y u _n en la sucesión de Rudin–Shapiro se pueden hallar recursivamente de la siguiente manera. Si n = m ·2 ^k donde m es impar entonces

${\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}}}$

${\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}}}$

Por lo tanto, u ₁₀₈ = u ₁₃ + 1 = u ₃ + 1 = u ₁ + 2 = u ₀ + 2 = 2, lo que se puede verificar observando que la representación binaria de 108, que es 1101100, contiene dos subcadenas 11. Y entonces r ₁₀₈ = (−1) ² = +1.

Un morfismo 2-uniforme que requiere una codificación para generar la secuencia de Rudin-Shapiro es el siguiente: ${\displaystyle \varphi }$ ${\displaystyle \tau }$ $${\displaystyle {\begin{aligned}\varphi :a&\to ab\\b&\to ac\\c&\to db\\d&\to dc\end{aligned}}}$$ $${\displaystyle {\begin{aligned}\tau :a&\to 1\\b&\to 1\\c&\to -1\\d&\to -1\end{aligned}}}$$

La palabra de Rudin–Shapiro +1 +1 +1 −1 +1 +1 −1 +1 +1 +1 −1 −1 −1 −1 +1 −1 ..., que se crea concatenando los términos de la secuencia de Rudin–Shapiro, es un punto fijo de las reglas de morfismo o sustitución de cadenas .

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

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

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

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

como sigue:

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

Se puede ver a partir de las reglas de morfismo que la cadena Rudin-Shapiro contiene como máximo cuatro +1 consecutivos y como máximo cuatro −1 consecutivos.

La secuencia de sumas parciales de la secuencia de Rudin-Shapiro, definida por

${\displaystyle s_{n}=\sum _{k=0}^{n}r_{k}\,,}$

con valores

1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 7, 6, 5, 4, 5, 4, ... (secuencia A020986 en la OEIS )

se puede demostrar que satisface la desigualdad

${\displaystyle {\sqrt {{\frac {3}{5}}n}}<s_{n}<{\sqrt {6n}}{\text{ for }}n\geq 1\,.}$^[1]

Sea la sucesión de Rudin–Shapiro en , en cuyo caso es el número, módulo 2, de ocurrencias (posiblemente superpuestas) del bloque en la expansión en base 2 de . Entonces la función generadora ${\displaystyle (s_{n})_{n\geq 0}}$ ${\displaystyle \{0,1\}}$ ${\displaystyle s_{n}}$ ${\displaystyle 11}$ ${\displaystyle n}$

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

satisface

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

haciéndolo algebraico como una serie de potencias formales sobre . ^[17] La ​​algebraicidad de sobre se sigue de la 2-automaticidad de por el teorema de Christol . ${\displaystyle \mathbb {F} _{2}(X)}$ ${\displaystyle S(X)}$ ${\displaystyle \mathbb {F} _{2}(X)}$ ${\displaystyle (s_{n})_{n\geq 0}}$

La secuencia de Rudin-Shapiro a lo largo de los cuadrados es normal. ^[18] ${\displaystyle (r_{n^{2}})_{n\geq 0}}$

La secuencia completa de Rudin–Shapiro satisface el siguiente resultado de distribución uniforme. Si , entonces existe tal que ${\displaystyle x\in \mathbb {R} \setminus \mathbb {Z} }$ ${\displaystyle \alpha =\alpha (x)\in (0,1)}$

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

lo que implica que se distribuye uniformemente módulo para todos los irracionales . ^[19] ${\displaystyle (xu_{n})_{n\geq 0}}$ ${\displaystyle 1}$ ${\displaystyle x}$

Relación con el modelo unidimensional de Ising

Sea la expansión binaria de n dada por

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

donde . Recordemos que la secuencia completa de Rudin-Shapiro está definida por ${\displaystyle \epsilon _{k}(n)\in \{0,1\}}$

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

Dejar

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

Entonces dejalo

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

Por último, dejemos que

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

Recuerde que la función de partición del modelo unidimensional de Ising se puede definir de la siguiente manera. Fix representa el número de sitios y fix constantes y representa la constante de acoplamiento y la intensidad del campo externo, respectivamente. Elija una secuencia de pesos con cada . Para cualquier secuencia de espines con cada , defina su hamiltoniano mediante ${\displaystyle N\geq 1}$ ${\displaystyle J>0}$ ${\displaystyle H>0}$ ${\displaystyle \eta =(\eta _{0},\dots ,\eta _{N-1})}$ ${\displaystyle \eta _{i}\in \{-1,1\}}$ ${\displaystyle \sigma =(\sigma _{0},\dots ,\sigma _{N-1})}$ ${\displaystyle \sigma _{i}\in \{-1,1\}}$

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

Sea una constante que represente la temperatura, que puede ser un número complejo arbitrario distinto de cero, y establezca donde es la constante de Boltzmann . La función de partición se define por ${\displaystyle T}$ ${\displaystyle \beta =1/(kT)}$ ${\displaystyle k}$

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

Entonces tenemos

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

donde la secuencia de pesos satisface para todos . ^[20] ${\displaystyle \eta =(\eta _{0},\dots ,\eta _{N-1})}$ ${\displaystyle \eta _{i}=1}$ ${\displaystyle i}$

Véase también

• Polinomios de Shapiro

Notas

1. John Brillhart y Patrick Morton, ganadores del premio Lester R. Ford en 1997 (1996). "Un estudio de caso en investigación matemática: la secuencia Golay-Rudin-Shapiro". Amer. Math. Monthly . 103 (10): 854–869. doi :10.2307/2974610. JSTOR  2974610.{{cite journal}}: CS1 maint: numeric names: authors list (link)
2. Weisstein, Eric W. "Secuencia de Rudin-Shapiro". MathWorld .
3. Pytheas Fogg (2002) pág. 42
4. Everest y otros (2003) pág. 234
5. Golay, MJE (1949). "Espectrometría de rendijas múltiples". Revista de la Sociedad Óptica de América . 39 (437–444): 437–444. doi :10.1364/JOSA.39.000437. PMID  18152021.
6. Golay, MJE (1951). "Espectrometría estática multirranura y su aplicación a la visualización panorámica de espectros infrarrojos". Revista de la Sociedad Óptica de América . 41 (7): 468–472. doi :10.1364/JOSA.41.000468. PMID  14851129.
7. Rudin, W. (1959). "Algunos teoremas sobre los coeficientes de Fourier". Actas de la American Mathematical Society . 10 (6): 855–859. doi : 10.1090/S0002-9939-1959-0116184-5 .
8. Shapiro, HS (1952). "Problemas extremos para polinomios y series de potencias". Tesis de maestría, MIT .
9. Salem, R.; Zygmund, A. (1954). "Algunas propiedades de series trigonométricas cuyos términos tienen signos aleatorios". Acta Mathematica . 91 : 245–301. doi : 10.1007/BF02393433 . S2CID  122999383.
10. Allouche y Shallit (2003) págs. 78-79
11. Allouche y Shallit (2003) pág. 122
12. Brillhart, J.; Morton, P. (1978). "Über Summen von Rudin – Shapiroschen Koeffizienten". Revista de Matemáticas de Illinois . 22 : 126-148. doi : 10.1215/ijm/1256048841 .
13. Saffari, B. (1986). "Una función extrema ligada a la suite de Rudin-Shapiro". CR Acad. Ciencia. París . 303 : 97-100.
14. Allouche, J.-P.; Choi, S.; Denise, A.; Erdélyi, T.; Saffari, B. (2019). "Límites de los coeficientes de autocorrelación de polinomios de Rudin-Shapiro". Análisis Mathematica . 45 (4): 705–726. arXiv : 1901.06832 . doi :10.1007/s10476-019-0003-4. S2CID  119168430.
15. Autómatas finitos y aritmética, Jean-Paul Allouche
16. Allouche y Shallit (2003) pág. 192
17. Allouche y Shallit (2003) pág. 352
18. Müllner, C. (2018). "La secuencia de Rudin–Shapiro y secuencias similares son normales a lo largo de los cuadrados". Revista Canadiense de Matemáticas . 70 (5): 1096–1129. arXiv : 1704.06472 . doi :10.4153/CJM-2017-053-1. S2CID  125493369.
19. Allouche y Shallit, págs. 462-464
20. Allouche y Shallit (2003) págs. 457–461

Referencias

• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Secuencias automáticas: teoría, aplicaciones, generalizaciones . Cambridge University Press . ISBN 978-0-521-82332-6.Zbl 1086.11015  .
• Everest, Graham; van der Poorten, Alf; Shparlinski, Igor; Ward, Thomas (2003). Secuencias de recurrencia . Encuestas y monografías matemáticas. 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, cristiano; Siegel, Anne (eds.). Sustituciones en dinámica, aritmética y combinatoria . Apuntes de conferencias de matemáticas. vol. 1794. Berlín: Springer-Verlag . ISBN 3-540-44141-7.Zbl 1014.11015  .
• Mendès France, Michel (1990). "La sucesión de Rudin-Shapiro, la cadena de Ising y el plegado de papel". En Berndt, Bruce C .; Diamond, Harold G.; Halberstam, Heini ; et al. (eds.). Teoría analítica de números. Actas de una conferencia en honor de Paul T. Bateman, celebrada del 25 al 27 de abril de 1989 en la Universidad de Illinois, Urbana, IL (EE. UU.) . Progress in Mathematics. Vol. 85. Boston: Birkhäuser. págs. 367–390. ISBN. 0-8176-3481-9.Zbl 0724.11010  .