¿Cuál es la subword la complejidad de la función de este infinito palabra?

Question

Deje $w_{0}$ denotar el finito palabra $01$ en el libre monoid $\{ 0, 1 \}^{\ast}$, y para $i \in \mathbb{N}$ definir $w_{i}$ como la palabra obtenidos por contigua a la primera $\left\lfloor \frac{\ell(w_{i-1})}{2} \right\rfloor$ entradas $w_{i-1}$ a la derecha de $w_{i-1}$. Por lo tanto tenemos que:

\begin{align*} w_{0} & = 01 \\ w_{1} & = 010 \\ w_{2} & = 0100 \\ w_{3} & = 010001 \\ w_{4} & = 010001010 \\ & \text{etc.} \end{align*}

Deje $$ w = 0100010100100010001010001010010001010010000100010100100010001010100 \ldots$$ indicar el infinito palabra binaria obtenida en el límite, con respecto a la secuencia de $(w_{i} : i \in \mathbb{N}_{0})$. Desde la construcción de este infinito palabra es muy simple y natural, es sorprendente que la secuencia de enteros $$(0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, \ldots)$$ given by the consecutive entries in $w$ no está actualmente en el On-Line de la Enciclopedia de Secuencias de Enteros (OEIS).

Recordemos que el subword la complejidad de la función de $\sigma_{v} = \sigma : \mathbb{N} \to \mathbb{N}$ de un infinito palabra $v$ es la función en $\mathbb{N}$ que se asigna a $n \in \mathbb{N}$ para el número de los distintos factores de $v$ de la longitud de la $n$. Dada la simple definición de la palabra binaria de $w$, es natural preguntarse: ¿qué es $\sigma_{w}$? No es obvio para mí cómo encontrar una forma cerrada de la evaluación de la secuencia $$(\sigma_{w}(n) )_{n \in \mathbb{N}} = (2, 3, 5, 8, 12, \ldots),$$ since proving a statement of the form $\sigma_{w}(n) = m$ for fixed $n \in \mathbb{N}$ (where $m \in \mathbb{N}$) appears to be nontrivial in general. However, for certain 'small' values of $n \in \mathbb{N}$, the evaluation of $\sigma_{w}(n)$ is relatively trivial. For example, using induction, it is easily seen that $\sigma_{w}(2)=3$.

También es natural preguntarse: ¿Cuál es el abelian la complejidad de la función de $w$?

Answer 1

Reivindicación 1. Para cualquier palabra $x\in\{0,1\}^*$, ($x$ es no un subword de $w$) fib ($11$ es un subword de $x$); es decir, las únicas palabras que no son subpalabras de $w$ son aquellos que contienen la subword $11$.

Prueba:

1. $x$ no es un subword de $w$ si $11$ es un subword de $x$

   Deje $suffix(w_i)$ $prefix(w_i)$ denotar cualquier sufijo y prefijo, respectivamente, de cualquiera de las $w_i$. Ahora, una palabra $x$ se produce como un subword de $w$ fib se forma en la unión de algunos de concatenación $(+)$ $suffix(w_i) + prefix(w_i)$ durante algunos iteración de la regla de reescritura en la definición recursiva de $w$. E. g., toda la longitud-$2$ palabras ocurren, excepto para $11$ - el último nunca se produce debido a $..1+1..$ no puede ocurrir, como $1..$ no es nunca un $prefix(w_i)$. Desde $11$ no se producen como subword en $w$, ninguna palabra, en que $11$ se produce como un subword.

2. $x$ no es un subword de $w$ sólo si $11$ es un subword de $x$

   (- para ser completado--)

Reivindicación 2. El número de palabras en $\{0,1\}^n$ que no contienen la subword $11$ es igual al número Fibonacci $F_{n+2}=F_{n+1} + F_n$,$F_0=0, F_1=1$.

Prueba: Ver cuántas $N$ dígitos de los números binarios puede ser formado en $0$ no se repite. El mismo argumento se aplica al $1$ (en lugar de $0$) no se repite.

Reivindicación 3. $\sigma_w(n) = F_{n+2}.$

Prueba: Inmediata a partir de la Reivindicación 1 Y Demanda 2.

Reivindicación 4. $\sigma_w^\mathrm{abelian}(n) = \left\lfloor\frac{n+3}{2}\right\rfloor.$

Prueba: Esto se desprende de la Reivindicación 1 Y la Reivindicación 2, junto con la observación de que para cada una de las $k$$\{0,1,2,...\left\lfloor\frac{n}{2}\right\rfloor\}$, hay una palabra en $\{0,1\}^n$ que contiene exactamente $k$ $1$s y no $11$-subword, pero que para cualquier grande $k$ esa palabra no existe.

Los cálculos con Sage confirmar estas afirmaciones para las pequeñas $n$, pero la primera ocurrencia de los tiempos de algunos relativamente corto de palabras son infeasibly grande, como lo sugiere la siguiente tabla de resultados:

\begin{array}{|c|c||c|} n & \sigma_w(n) & \sigma_w^\mathrm{abelian}(n) & \mathrm{index\ of\ the\ 1st\ occurrence\ of\ }0^n \\ \hline 1&2&2&0 \\ 2&3&2&2 \\ 3&5&3&2 \\ 4&8&3&39 \\ 5&13&4&40360461 \\ 6&21^*&4^*&> 7854933623 \end{array}

$(^*)$ El prefijo más largo que el sistema puede calcular directamente es $w_{55}$, que tiene una longitud de $7854933628$. A excepción de $0^6$, contiene todos los de $21$ de la longitud-$6$ subpalabras que no contengan $11$.

Answer 2

No es una respuesta completa, pero probablemente una referencia útil.

Usted menciona que la secuencia de enteros $$(0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, \ldots)$$ given by the consecutive entries in $w$ is not currently in OEIS. However, the sequence of positions of $1$ en esta secuencia, a saber: $$ 1, 5, 7, 10, 14, 18, 20, 24, 26, 29, 33, 35, \dotsm $$ aparece como A020942, Primera columna de 3er orden Zeckendorf matriz, en OEIS. Citando OEIS

Cualquier número de $n$ tiene representación única como suma de los términos de $\{1, 2, 3, 4, 6, 9, 13, 19, ...\}^{*}$ tal que no hay dos términos adyacentes o pen-adyacente; por ejemplo, $7=6+1$. Secuencia da a todos los $n$ donde la representación implica la $1$.

$^{(*)}\scriptsize\text{ These terms obey the recurrence equation $a(n) = a(n-1) + a(n-3)$.}$

Dos referencias

[1] Larry Ericksen y Pedro G. Anderson, los Patrones en las diferencias entre las filas de k-Zeckendorf matrices, La de Fibonacci Quarterly 50, febrero de 2012.

[2] C. Kimberling, El Zeckendorf matriz es igual a la Wythoff matriz, Fibonacci Quarterly 33 (1995) 3-8.

Referencia [1] da interesantes conexiones con la secuencia de palabras $w_k$ $k$letras del alfabeto definido de la siguiente manera: \begin{align} w_0 &= a_0,\\ w_1 &= a_0a_1,\\ &\ \vdots\\ w_{k-1} &= a_0a_1 \dotsm a_{k-1} \end{align} y $w_i = w_{i-1}w_{i-k}$$i \geqslant k$. Esto hace que este artículo una aproximación razonable con miras a la solución de su problema.