1
$\begingroup$

Consider the string $s = a_{1}..a_{n}$.

Let's say that $p$ is a period when $a_{i} = a_{i + p}$ for all $i \in [1..n-p]$

Suppose there are two periods : $q$ and $p$, such that $q + p \le n$ then $\gcd(p,q)$ is also a period.

I tried to represent it : $\gcd(p,q) = \gcd(p,p+q)$ , but it doesn't help me. Give any hint, please.

$\endgroup$
1
$\begingroup$

The result you mention is due to Fine and Wilf [1]. As indicated on the Wikipedia page Théorème de périodicité de Fine et Wilf (which unfortunately does not seem to exist in English), the theorem of Fine and Wilf can be stated in (at least) three different ways. Version $1$ is a slightly stronger version of your question. Version 3 is the original statement of [1].

Version 1. Suppose that $s$ has two periods $p$ and $q$. If $p+q-\operatorname{gcd}(p,q) \leqslant |s|$, then $\operatorname{gcd}(p,q)$ is a period of $s$.

Version 2. Let $u$ and $v$ be two words, and suppose that for some positive integers $h$ and $k$, $u^h$ and $v^k$ have a common prefix of length $\geqslant |u|+|v|-\operatorname{gcd}(|u|,|v|)$. Then $u$ and $v$ are powers of a word of length $\operatorname{gcd}(|u|,|v|)$.

Version 3. Let $(a_n)_{n\geqslant 0}$ and $(b_n)_{n\geqslant 0}$ be two periodic sequences, of period $p$ and $q$, respectively. If $a_n=b_n$ for $p+q-\operatorname{gcd}(p,q)$ consecutive integers, then $a_n=b_n$ for all $n$.

A proof of Version 2 is given in [2, Prop.1.3.5, page 10]. If you just want a hint, first try the case where $d = \operatorname{gcd}(|u|,|v|) = 1$, and then argue on the alphabet $A^d$ for the general case.

[1] N. J. Fine and H. S. Wilf, Uniqueness theorems for periodic functions, Proc. of the AMS 16, (1965), 109-114 (ISSN 0002-9939, DOI 10.1090/s0002-9939-1965-0174934-9).

[2] M. Lothaire, Combinatorics on words, Addison-Wesley Publishing Co., Reading, Mass., coll. Encyclopedia of Mathematics and its Applications 17,‎ (1983) (ISBN 978-0-201-13516-9), Revised version Cambridge University Press, (1997), ISBN 978-0521599245

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.