Generalised fine and Wilf's theorem for arbitrary number of periods (Q557915)

The notion of period of a word is central in combinatorics on words. There are many fundamental results on periods of words. Among them is the well known and basic periodicity result of Fine and Wilf which intuitively determines how far two periodic events have to match in order to guarantee a common period. More precisely, any word with length at least \(p+q-\gcd(p,q)\) having periods \(p\) and \(q\) has also period the greatest common divisor of \(p\) and \(q\), \(\gcd(p,q)\). Moreover, the bound \(p+q-\gcd(p,q)\) is optimal since counterexamples can be provided for words of smaller length. Fine and Wilf's result was generalized for more than two periods but the problem of finding the optimal bounds had not been settled. In this very interesting paper, the authors give an extension of Fine and Wilf's theorem for an arbitrary number of periods and prove that their bounds are optimal. More precisely, they show that any word having periods \(p_1, \ldots, p_n\) and length at least the so-denoted \({f_w}_n (p_1, \ldots, p_n)\), has also the greatest common divisor of \(p_1, \ldots, p_n\) as period, and they prove that their bound \({f_w}_n (p_1, \ldots, p_n)\) is optimal. The optimality proof is based on results of graphs associated with bounds and tuples of periods. They obtain a uniqueness result concerning extremal words for the optimal bounds (a word \(w\) of length \({f_w}_n ({\mathbf p})-1\) is extremal for the bound \({f_w}_n ({\mathbf p})\) if all integers in \({\mathbf p} = (p_1, \ldots, p_n)\) are periods of \(w\) but \(\gcd({\mathbf p})\) is not a period of \(w\)). Moreover, they give an algorithm which given an \(n\)-tuple of periods \({\mathbf p}\), computes the optimal bound \({f_w}_n ({\mathbf p})\) and an extremal word for that bound.