Periodicity, morphisms, and matrices

✍ Scribed by Sabin Cautis; Filippo Mignosi; Jeffrey Shallit; Ming-wei Wang; Soroosh Yazdani

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 173 KB
• Volume: 295
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00398-5

✦ Synopsis

In 1965, Fine and Wilf proved the following theorem: if (fn)n¿0 and (gn)n¿0 are periodic sequences of real numbers, of period lengths h and k, respectively, and fn = gn for 0 6 n ¡ h + k -gcd(h; k), then fn = gn for all n ¿ 0. Furthermore, the constant h + k -gcd(h; k) is best possible. In this paper, we consider some variations on this theorem. In particular, we study the case where fn 6 gn instead of fn = gn. We also obtain generalizations to more than two periods.

We apply our methods to a previously unsolved conjecture on iterated morphisms, the decreasing length conjecture: if h : * → * is a morphism with | | = n, and w is a word with |w| ¿ |h(w)| ¿ |h 2 (w)| ¿ • • • ¿ |h k (w)|, then k 6 n.