secuencia k-regular

En matemáticas y en informática teórica , una secuencia k -regular es una secuencia que satisface ecuaciones de recurrencia lineal que reflejan las representaciones de base k de los números enteros. La clase de secuencias k -regulares generaliza la clase de secuencias k -automáticas a alfabetos de tamaño infinito.

Existen varias caracterizaciones de las sucesiones k -regulares, todas ellas equivalentes. Algunas caracterizaciones comunes son las siguientes. Para cada una, consideramos que R ′ es un anillo noetheriano conmutativo y consideramos que R es un anillo que contiene a R ′.

Sea k  ≥ 2. El k-núcleo de la secuencia es el conjunto de subsecuencias ${\displaystyle s(n)_{n\geq 0}}$

${\displaystyle K_{k}(s)=\{s(k^{e}n+r)_{n\geq 0}:e\geq 0{\text{ y }}0\leq r\leq k ^{e}-1\}.}$

La secuencia es ( R ′, k )-regular (a menudo abreviada simplemente como " k -regular") si el módulo generado por K _k ( s ) es un módulo R ′ finitamente generado . ^[1]${\displaystyle s(n)_{n\geq 0}}$${\estilo de visualización R'}$

En el caso especial cuando , la secuencia es -regular si está contenida en un espacio vectorial de dimensión finita sobre . ${\displaystyle R'=R=\mathbb {Q}}$${\displaystyle s(n)_{n\geq 0}}$${\estilo de visualización k}$$Estilo de visualización K(s)$${\displaystyle \mathbb {Q}}$

Una secuencia s ( n ) es k -regular si existe un entero E tal que, para todo e _j > E y 0 ≤ r _j ≤ k ^{e _j}  − 1, cada subsecuencia de s de la forma s ( k ^{e _j} n  +  r _j ) es expresable como una combinación lineal R ′ , donde c _ij es un entero, f _ij ≤ E y 0 ≤ b _ij ≤ k ^{f _ij}  − 1. ^[2] ${\displaystyle \sum _{i}c_{ij}s(k^{f_{ij}}n+b_{ij})}$

Alternativamente, una secuencia s ( n ) es k -regular si existen un entero r y subsecuencias s ₁ ( n ), ..., s _r ( n ) tales que, para todo 1 ≤ i ≤ r y 0 ≤ a ≤ k  − 1, cada secuencia s _i ( kn  +  a ) en el k -núcleo K _k ( s ) es una combinación R ′-lineal de las subsecuencias s _i ( n ). ^[2]

Sea x ₀ , ..., x _{k  − 1} un conjunto de k variables no conmutativas y sea τ una función que envía un número natural n a la cadena x _{a 0} ... x _{a e  − 1} , donde la representación base- k de x es la cadena a _{e  − 1} ... a ₀ . Entonces una secuencia s ( n ) es k -regular si y solo si la serie formal es - racional . ^[3]${\displaystyle \sum_{n\geq 0}s(n)\tau (n)}$${\displaystyle \mathbb {Z}}$

La definición formal de serie de una secuencia k -regular conduce a una caracterización del autómata similar a la máquina matricial de Schützenberger . ^{[4] [5]}

La noción de secuencias k -regulares fue investigada por primera vez en un par de artículos de Allouche y Shallit. ^[6] Antes de esto, Berstel y Reutenauer estudiaron la teoría de series racionales , que está estrechamente relacionada con las secuencias k -regulares. ^[7]

Sea la valoración -ádica de . La secuencia de la regla ( OEIS : A007814 ) es -regular y la -kernel ${\displaystyle s(n)=\nu _ {2}(n+1)}$ ${\estilo de visualización 2}$${\estilo de visualización n+1}$${\displaystyle s(n)_{n\geq 0}=0,1,0,2,0,1,0,3,\dots }$${\displaystyle 2}$${\displaystyle 2}$

${\displaystyle \{s(2^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq 2^{e}-1\}}$

está contenido en el espacio vectorial bidimensional generado por y la secuencia constante . Estos elementos básicos conducen a las relaciones de recurrencia ${\displaystyle s(n)_{n\geq 0}}$${\displaystyle 1,1,1,\dots }$

${\displaystyle {\begin{aligned}s(2n)&=0,\\s(4n+1)&=s(2n+1)-s(n),\\s(4n+3)&=2s(2n+1)-s(n),\end{aligned}}}$

que, junto con las condiciones iniciales y , determinan de forma única la secuencia. ^[8]${\displaystyle s(0)=0}$${\displaystyle s(1)=1}$

La secuencia de Thue-Morse t ( n ) ( OEIS : A010060 ) es el punto fijo del morfismo 0 → 01, 1 → 10. Se sabe que la secuencia de Thue-Morse es 2-automática. Por lo tanto, también es 2-regular y su núcleo 2

${\displaystyle \{t(2^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq 2^{e}-1\}}$

consta de las subsecuencias y . ${\displaystyle t(n)_{n\geq 0}}$${\displaystyle t(2n+1)_{n\geq 0}}$

La sucesión de números de Cantor c ( n ) ( OEIS : A005823 ) consta de números cuyas expansiones ternarias no contienen 1. Es sencillo demostrar que

${\displaystyle {\begin{aligned}c(2n)&=3c(n),\\c(2n+1)&=3c(n)+2,\end{aligned}}}$

y por lo tanto la secuencia de números de Cantor es 2-regular. De manera similar, la secuencia de Stanley

0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, ... (secuencia A005836 en la OEIS )

de números cuyas expansiones ternarias no contienen 2 también es 2-regular. ^[9]

Una aplicación algo interesante de la noción de k -regularidad al estudio más amplio de algoritmos se encuentra en el análisis del algoritmo de ordenación por fusión . Dada una lista de n valores, el número de comparaciones realizadas por el algoritmo de ordenación por fusión son los números de ordenación , regidos por la relación de recurrencia

${\displaystyle {\begin{aligned}T(1)&=0,\\T(n)&=T(\lfloor n/2\rfloor )+T(\lceil n/2\rceil )+n-1,\ n\geq 2.\end{aligned}}}$

Como resultado, la secuencia definida por la relación de recurrencia para la ordenación por fusión, T ( n ), constituye una secuencia 2-regular. ^[10]

Si es un polinomio de valor entero , entonces es k -regular para cada . ${\displaystyle f(x)}$${\displaystyle f(n)_{n\geq 0}}$${\displaystyle k\geq 2}$

La secuencia de Glaisher-Gould es 2-regular. La secuencia de Stern-Brocot es 2-regular.

Allouche y Shallit dan varios ejemplos adicionales de secuencias k -regulares en sus artículos. ^[6]

Las secuencias k -regulares exhiben una serie de propiedades interesantes.

• Toda secuencia k -automática es k -regular. ^[11]
• Toda secuencia k -sincronizada es k -regular.
• Una secuencia k -regular toma un número finito de valores si y sólo si es k -automática. ^[12] Esta es una consecuencia inmediata de que la clase de secuencias k -regulares sea una generalización de la clase de secuencias k -automáticas.
• La clase de secuencias k -regulares está cerrada bajo la adición término por término, la multiplicación término por término y la convolución . La clase de secuencias k -regulares también está cerrada bajo la escala de cada término de la secuencia por un entero λ. ^{[12] [13] [14] [15]} En particular, el conjunto de series de potencias k -regulares forma un anillo. ^[16]
• Si es k -regular, entonces para todos los números enteros , es k -automático. Sin embargo, la recíproca no se cumple. ^[17]${\displaystyle s(n)_{n\geq 0}}$${\displaystyle m\geq 1}$${\displaystyle (s(n){\bmod {m}})_{n\geq 0}}$
• Para k ,  l ≥ 2 multiplicativamente independiente  , si una secuencia es tanto k -regular como l -regular, entonces la secuencia satisface una recurrencia lineal. ^[18] Esta es una generalización de un resultado debido a Cobham con respecto a secuencias que son tanto k -automáticas como l -automáticas. ^[19]
• El término n- ésimo de una secuencia k -regular de números enteros crece como máximo de forma polinomial en n . ^[20]
• Si es un cuerpo y , entonces la secuencia de potencias es k -regular si y sólo si o es una raíz de la unidad. ^[21]${\displaystyle F}$${\displaystyle x\in F}$${\displaystyle (x^{n})_{n\geq 0}}$${\displaystyle x=0}$${\displaystyle x}$

Dada una secuencia candidata que no se sabe si es k -regular, la k -regularidad se puede demostrar normalmente directamente a partir de la definición calculando elementos del núcleo de y demostrando que todos los elementos de la forma con y suficientemente grandes se pueden escribir como combinaciones lineales de elementos del núcleo con exponentes más pequeños en lugar de . Esto suele ser computacionalmente sencillo. ${\displaystyle s=s(n)_{n\geq 0}}$${\displaystyle s}$${\displaystyle (s(k^{r}n+e))_{n\geq 0}}$${\displaystyle r}$${\displaystyle 0\leq e<2^{r}}$${\displaystyle r}$

Por otra parte, para refutar la k -regularidad de la secuencia candidata, normalmente es necesario producir un subconjunto linealmente independiente en el núcleo de , lo que suele ser más complicado. A continuación se muestra un ejemplo de una prueba de este tipo. ${\displaystyle s}$${\displaystyle \mathbb {Z} }$${\displaystyle s}$

Sea el número de en la expansión binaria de . Sea el número de en la expansión binaria de . Se puede demostrar que la secuencia es 2-regular. Sin embargo, la secuencia no es 2-regular, mediante el siguiente argumento. Supongamos que es 2-regular. Afirmamos que los elementos para y del 2-núcleo de son linealmente independientes sobre . La función es sobreyectiva sobre los enteros, por lo que sea el menor entero tal que . Por 2-regularidad de , existen y constantes tales que para cada , ${\displaystyle e_{0}(n)}$${\displaystyle 0}$${\displaystyle n}$${\displaystyle e_{1}(n)}$${\displaystyle 1}$${\displaystyle n}$${\displaystyle f(n):=e_{0}(n)-e_{1}(n)}$${\displaystyle g=g(n):=|f(n)|}$${\displaystyle (g(n))_{n\geq 0}}$${\displaystyle g(2^{k}n)}$${\displaystyle n\geq 1}$${\displaystyle k\geq 0}$${\displaystyle g}$${\displaystyle \mathbb {Z} }$${\displaystyle n\mapsto e_{0}(n)-e_{1}(n)}$${\displaystyle x_{m}}$${\displaystyle e_{0}(x_{m})-e_{1}(x_{m})=m}$${\displaystyle (g(n))_{n\geq 0}}$${\displaystyle b\geq 0}$${\displaystyle c_{i}}$${\displaystyle n\geq 0}$

${\displaystyle \sum _{0\leq i\leq b}c_{i}g(2^{i}n)=0.}$

Sea el valor mínimo para el cual . Entonces para cada , ${\displaystyle a}$${\displaystyle c_{a}\neq 0}$${\displaystyle n\geq 0}$

${\displaystyle g(2^{a}n)=\sum _{a+1\leq i\leq b}-(c_{i}/c_{a})g(2^{i}n).}$

Evaluando esta expresión en , donde y así sucesivamente, obtenemos, en el lado izquierdo ${\displaystyle n=x_{m}}$${\displaystyle m=0,-1,1,2,-2}$

${\displaystyle g(2^{a}x_{m})=|e_{0}(x_{m})-e_{1}(x_{m})+a|=|m+a|,}$

y en el lado derecho,

${\displaystyle \sum _{a+1\leq i\leq b}-(c_{i}/c_{a})|m+i|.}$

De ello se deduce que para cada entero , ${\displaystyle m}$

${\displaystyle |m+a|=\sum _{a+1\leq i\leq b}-(c_{i}/c_{a})|m+i|.}$

Pero para , el lado derecho de la ecuación es monótono porque tiene la forma para algunas constantes , mientras que el lado izquierdo no lo es, como se puede comprobar al sustituir sucesivamente , , y . Por lo tanto, no es 2-regular. ^[22]${\displaystyle m\geq -a-1}$${\displaystyle Am+B}$${\displaystyle A,B}$${\displaystyle m=-a-1}$${\displaystyle m=-a}$${\displaystyle m=-a+1}$${\displaystyle (g(n))_{n\geq 0}}$

• Allouche, Jean-Paul; Shallit, Jeffrey (1992), "El anillo de secuencias k -regulares", Theoret. Comput. Sci. , 98 (2): 163–197, doi : 10.1016/0304-3975(92)90001-v.
• Allouche, Jean-Paul; Shallit, Jeffrey (2003), "El anillo de secuencias k -regulares, II", Theoret. Comput. Sci. , 307 : 3–29, doi : 10.1016/s0304-3975(03)00090-2.
• 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  .