×

Periodicity, morphisms, and matrices. (English) Zbl 1046.68084

Summary: In 1965, Fine and Wilf proved the following theorem. if \((f_n)_{n\geq 0}\) and \((g_n)_{n\geq 0}\) are periodic sequences of real numbers, of period lengths \(h\) and \(k\), respectively, and \(f_n=g_n\) for \(0\leq n<h+k-\text{gcd} (h,k)\), then \(f_n=g_n\) for all \(n\geq 0\). Furthermore, the constant \(h+k-\text{gcd}(h,k)\) is best possible. In this paper, we consider some variations on this theorem. In particular, we study the case where \(f_n\leq g_n\) instead of \(f_n= g_n\). 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:\Sigma^*\to\Sigma^*\) is a morphism with \(| \Sigma |=n\), and \(w\) is a word with \(| w|>| h(w) | >| h^2(w) |>\cdots>| h^k(w)|\), then \(k\leq n\).

MSC:

68R15 Combinatorics on words
Full Text: DOI

References:

[1] J. Berstel, P. Séébold, Sturmian words. in: M. Lothaire (Ed.), Algebraic Combinatorics on Words. Cambridge University Press, Cambridge, 2002, pp. 45-110.; J. Berstel, P. Séébold, Sturmian words. in: M. Lothaire (Ed.), Algebraic Combinatorics on Words. Cambridge University Press, Cambridge, 2002, pp. 45-110. · Zbl 1001.68093
[2] Bo, Z., Improvements on inequalities for non-negative matrices, Austral. J. Combin., 21, 251-255 (2000) · Zbl 0956.15011
[3] Castelli, M. G.; Mignosi, F.; Restivo, A., Fine and Wilf’s theorem for three periods and a generalization of Sturmian words, Theoret. Comput. Sci., 218, 83-94 (1999) · Zbl 0916.68114
[4] Choffrut, C.; Karhumäki, J., Combinatorics of words, (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages (1997), Springer: Springer Berlin), 329-438 · Zbl 0866.68057
[5] Crochemore, M.; Rytter, W., Text Algorithms (1994), Oxford University Press: Oxford University Press Oxford · Zbl 0844.68101
[6] Fejér, L., Sur les polynomes harmoniques quelconques, C. R. Acad. Sci. Paris, 157, 506-509 (1913) · JFM 44.0304.02
[7] Fine, N. J.; Wilf, H. S., Uniqueness theorems for periodic functions, Proc. Amer. Math. Soc., 16, 109-114 (1965) · Zbl 0131.30203
[8] Gilbert, A. D.; Smyth, C. J., Zero-mean cosine polynomials which are non-negative for as long as possible, J. London Math. Soc., 62, 489-504 (2000) · Zbl 1032.42002
[9] Hardy, G. H.; Wright, E. M., An Introduction to the Theory of Numbers (1985), Oxford University Press: Oxford University Press Oxford · Zbl 0020.29201
[10] Justin, J., On a paper by Castelli, Mignosi, Restivo, Theoret. Inform. Appl., 34, 373-377 (2000) · Zbl 0987.68056
[11] Knuth, D. E.; Morris, J.; Pratt, V., Fast pattern matching in strings, SIAM J. Comput., 6, 323-350 (1977) · Zbl 0372.68005
[12] Mignosi, F.; Shallit, J.; Wang, M.-w., Variations on a theorem of Fine & Wilf, (Sgall, J.; Pultr, A.; Kolman, P., Proc. MFCS 2001, Lecture Notes in Computer Science, vol. 2136 (2001), Springer: Springer Berlin), 512-523 · Zbl 0999.68166
[13] Pólya, G.; Szegö, G., Problems and Theorems in Analysis II (1976), Springer: Springer Berlin · Zbl 0311.00002
[14] Salomaa, A., Formal Languages (1973), Academic Press: Academic Press New York · Zbl 0262.68025
[15] J. Shallit, Ten problems I can’t solve, Talk for University of Waterloo Pure Mathematics Club, July 11, 2000. Slides available at; J. Shallit, Ten problems I can’t solve, Talk for University of Waterloo Pure Mathematics Club, July 11, 2000. Slides available at
[16] Shallit, J.; Wang, M.-w., On two-sided infinite fixed points of morphisms, (Ciobanu, G.; Păun, G., Proc. 12th Internat. Symp. on Fundamentals of Computation Theory (FCT ’99), Lecture Notes in Computer Science, vol. 1684 (1999), Springer: Springer Berlin), 488-499 · Zbl 0945.68115
[17] Wang, M.-w., An inequality for non-negative matrices II, Linear Algebra Appl., 348, 259-264 (2002) · Zbl 1003.15018
[18] Wang, M.-w.; Shallit, J., An inequality for non-negative matrices, Linear Algebra Appl., 290, 135-144 (1999) · Zbl 0930.15020
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.