4
$\begingroup$

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 ?

2 Answers 2

5

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.

  • 0
    Note that this theorem also works if $p_1$ and $p_2$ do not divide $|w|$.2011-02-17
2

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$.

  • 0
    $(n,m)$ is shorthand for the GCD. The infinite string $S$ is indexed by the integers (it's infinite on both ends).2011-02-18