Periodicidad en cuerdas.

Question

Se sabe que una cadena de $s$ es en realidad hecha de repeticiones de otra cadena de $s_1$ de la longitud de la $L_1$.

También se $s$ puede considerarse como compuesto de repeticiones de otra cadena de $s_2$ de la longitud de la $L_2$.

Por ejemplo, la cadena de $s = abababab$ se realiza mediante la repetición de la subcadena $s_1$ "$ab$" de longitud $L_1= 2$ o por la repetición de la subcadena $s_2$ "$abab$" de longitud $L_2=4$.

Creo que en este caso, $s$ puede ser hecha por la repetición de una subcadena de longitud $\gcd(L_1,L_2)$. Por ejemplo, si $L_1=6$ $L_2=10$ $s$ debe ser repetitiva en una subcadena de longitud $2$ (= $\gcd(6,10)$) demasiado. Esto parece evidente, pero ¿cómo puedo mostrar esta formalmente ?

Answer 1

Esto se deduce del siguiente teorema:

Teorema. Deje que$w \in \Gamma^{*}$ sea una palabra con periodicidades$p_1$ y$p_2$. Si$|w| \geq p_1+p_2- \gcd(p_1,p_2)$, entonces$w$ tiene periodicidad$\gcd(p_1, p_2)$.

Esto se conoce como el teorema de Fine y Wilf .

Answer 2

Reemplace su cadena original$s$ por infinitas copias de$s$, yendo en ambas direcciones:$$S = ... sss ... $ $ Ahora$s$ tiene un período$n$ iff$S(x) = S(x+n)$.

Si$S$ tiene períodos$n,m$ entonces$S$ también tiene un período$(n,m)$ desde$(n,m) = an + bm$ para algunos enteros$a,b$.