# Periodicity in strings

It is known that a string $s$ is actually made up of repetitions of another string $s_1$ of length $L_1$.

Also $s$ can be thought of as made up of repetitions of another string $s_2$ of length $L_2$.

For example the string $s = abababab$ is made by repeating the substring $s_1$ "$ab$" of length $L_1= 2$ or by repeating the substring $s_2$ "$abab$" of length $L_2=4$.

I believe that in such a case $s$ can be made by repeating substring of length $\gcd(L_1,L_2)$. For example if $L_1=6$ and $L_2=10$ then $s$ should be repetitive in a substring of length $2$ (= $\gcd(6,10)$) too. This seems intuitive but how do I show this formally ?

-

This follows from the following Theorem:

Theorem. Let $w \in \Gamma^{*}$ be a word with periodicities $p_1$ and $p_2$. If $|w| \geq p_1+p_2- \gcd(p_1,p_2)$, then $w$ has periodicity $\gcd(p_1, p_2)$.

This is known as Fine and Wilf's Theorem.

-
Note that this theorem also works if $p_1$ and $p_2$ do not divide $|w|$. – Yuval Filmus Feb 17 '11 at 16:47

Replace your original string $s$ by infinitely many copies of $s$, going both ways: $$S = ... sss ...$$ Now $s$ has period $n$ iff $S(x) = S(x+n)$.

If $S$ has periods $n,m$ then $S$ also has period $(n,m)$ since $(n,m) = an + bm$ for some integers $a,b$.

-
(n,m) means the gcd of (n,m) ? what is the indexing for this new infinite string S ? – AnkurVijay Feb 17 '11 at 16:51
$(n,m)$ is shorthand for the GCD. The infinite string $S$ is indexed by the integers (it's infinite on both ends). – Yuval Filmus Feb 18 '11 at 2:35