Palabras que están de acuerdo en el recuento de todas las subpalabras de longitud $\leq k$

Question

Estoy trabajando con una de dos letras del alfabeto $\{0,1\}$, y estoy hablando generalizada sub-palabra, es decir, las letras no deben ser adyacentes, $|01010|_{00} = 3$

Por ejemplo, las dos palabras $u=1001$ $v=0110$ está de acuerdo en todas las subpalabras de longitud $\leq$ 2 (1, 0, 10, 01, 11 y 00), y ambos son de longitud 4, que pasa a ser el de menor longitud donde esta propiedad será cierto con $k=2$. He encontrado a la mínima longitudes $\{2,4,7,12,16,22\}$$k=\{1,2,3,4,5,6\}$, respectivamente, a través de bruteforcing.

Lo que estoy básicamente buscando es, en dos palabras $|u|=|v|=n$, lo que mantuvo a lo que usted necesita en $k$ que si $u$ $v$ está de acuerdo en todas las subpalabras de longitud $\leq k$,$u=v$.

Estoy buscando una $\mathcal{O}(\log n)$ unido, así que he intentado buscar inductivo para la prueba de k donde la longitud de la palabra se convierte en un múltiplo después de cada iteración.

También, como parte de la prueba, en la medida experimentalmente, he encontrado que si dos palabras están de acuerdo en todas las subpalabras de longitud $k$, también están de acuerdo en toda la longitud de la $\leq k$, pero no puede encontrar una prueba o contra-prueba de ello.

Answer 1

Es un problema de combinatoria de palabras que ya ha sido estudiado.

Realmente no sabemos una buena asintótica equivalente para $k(n)=1,3,6,11,\dots$. Tenemos el límite superior $k(n)=O(\sqrt n)$, o más precisamente: $$k(n)\le 5+\left\lfloor\tfrac{16}{7}\sqrt{n}\right\rfloor\qquad\text{(Krasikov1997)}$$ $$k(n)\le 3+2\left\lfloor\sqrt{n\log 2}\right\rfloor\qquad\text{(Krasikov2000)}$$ (Krasikov2000) no parece estar en línea (que es citado en (Ligeti2007)), y por alguna razón esta mejor límite superior no está citado en (Dudik2002), por lo que caveat emptor.

Hay un fácil $\Omega(\log n)$ límite inferior de considerar por ejemplo, Thue-Morse palabras y su complemento, pero no es nítida. De hecho, $k(n)$ crece más rápido que cualquier polinomio en $\log n$, por lo que el obligado se fueron con la esperanza de que no esté satisfecho: $$\log k(n)=\Omega(\sqrt{\log n})$$ Ver (Dudik2002).

En una forma en que estos dos límites, puede ser reconciliado con dar el ciertamente vaga equivalente $$\log \log k(n)=\Theta(\log \log n)$$ pero esto es todavía lo suficientemente precisa como para rechazar logarítmica de crecimiento, que podría ser $\Theta(\log \log \log n)$.

---

Referencias:

• (Krasikov1997) Krasikov, Roditty, En una Reconstrucción Problema para las Secuencias. J. Combinat. La Teoría De La Ser. Una, 77 (2) (1997), pp 344-348.
• (Krasikov2000) Fomentar, Krasikov, Una mejora de un Borwein-Erdélyi-Kós resultado. Métodos De Appl. Anal., 7(4):605-614, 2000.
• (Dudik2002) Dudık, Schulman, la Reconstrucción de las subsecuencias, J. Combinat. La Teoría De La Ser. Una, 103 (2) (2003), pp 337-348.
• (Ligeti2007) Ligeti, la Combinatoria de las palabras y sus aplicaciones. Tesis Doctoral.