Abstract
Given an infinite word with values in a finite alphabet that admit frequencies for all its factors, the smallest frequency function associates with a given positive integer the smallest frequency for factors of this length, and the recurrence function measures the gaps between successive occurrences of factors. We develop in this paper the relations between the growth orders of the smallest frequency and of the recurrence functions. As proved by M. Boshernitzan, linearly recurrent words are characterized in terms of the smallest frequency function. In this paper, we see how to extend this result beyond the case of linearly recurrent words. We first establish a general relation between the smallest frequency and the recurrence functions. Given a lower bound for the smallest frequency function, this relation provides an upper bound for the recurrence function which involves the primitive of this lower bound. We then see how to improve this relation in the case of Sturmian words where the product of the smallest frequency and the recurrence function is bounded for most of the lengths of factors. We also indicate how to construct Sturmian words having a prescribed behaviour for the smallest frequency function, and for the product of the smallest frequency and the recurrence function.
This work was supported by the Agence Nationale de la Recherche through the project “Codys” (ANR-18-CE40-0007).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Aliste-Prieto, J., Coronel, D., Cortez, M.I., Durand, F., Petite, S.: Linearly repetitive Delone sets. In: Kellendonk, J., Lenz, D., Savinien, J. (eds.) Mathematics of Aperiodic Order. PM, vol. 309, pp. 195–222. Springer, Basel (2015). https://doi.org/10.1007/978-3-0348-0903-0_6
Berthé, V.: Fréquences des facteurs des suites sturmiennes. Theor. Comput. Sci. 165(2), 295–309 (1996)
Berthé, V., Vuillon, L.: Tilings and rotations on the torus: a two-dimensional generalization of Sturmian sequences. Disc. Math. 223(2000), 27–53 (2000)
Berthé, V., Cesaratto, E., Rotondo, P., Vallée, B., Viola, A.: Recurrence function on Sturmian words: a probabilistic study. In: Italiano, G.F., Pighizzini, G., Sannella, D.T. (eds.) MFCS 2015. LNCS, vol. 9234, pp. 116–128. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48057-1_9
Émile Borel, M.: Les probabilités dénombrables et leurs applications arithmétiques. Rendiconti del Circolo Matematico di Palermo (1884–1940) 27(1), 247–271 (1909). https://doi.org/10.1007/BF03019651
Boshernitzan, M.: A condition for unique ergodicity of minimal symbolic flows. Ergod. Theor. Dyn. Syst. 12(3), 425–428 (1992)
Cassaigne, J.: Limit values of the recurrence quotient of Sturmian sequences. Theor. Comput. Sci. 218(1), 3–12 (1999)
Berthé, V., Rigo, M. (eds.): Combinatorics, Automata and Number Theory. Encyclopedia of Mathematics and its Applications, vol. 135. Cambridge University Press, Cambridge (2010)
Durand, F., Host, B., Skau, C.: Substitutions, Bratteli diagrams and dimension groups. Ergod. Theor. Dyn. Syst. 19, 952–993 (1999)
Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers. Oxford Science Publications, Published by Oxford University Press, Oxford (1980)
Haynes, A., Koivusalo, H., Walton, J.: A characterization of linearly repetitive cut and project sets. Nonlinearity 31(2), 515–539 (2018)
Haynes, A., Marklof, J.: Higher dimensional Steinhaus and Slater problems via homogeneous dynamics. Ann. Sci. Éc. Norm. Supér. 4(53), 537–557 (2020)
Haynes, A., Marklof, J.: A five distance theorem for Kronecker sequences. Int. Math. Res. Not. IMRN 24, 19747–19789 (2022)
Keane, M.: Non-ergodic interval exchange transformations. Israel J. Math. 26, 188–196 (1977)
Lagarias, J.C., Pleasants, P.A.B.: Local complexity of Delone sets and crystallinity. Can. Math. Bull. 45(4), 634–652 (2002)
Lagarias, J.C., Pleasants, P.A.B.: Repetitive Delone sets and quasicrystals. Ergod. Theor. Dyn. Syst. 23, 831–867 (2003)
Lothaire, M.: Algebraic Combinatorics on Words. Encyclopedia of Mathematics and its Applications, vol. 90. Cambridge University Press, Cambridge (2002)
Morse, M., Hedlund, G.A.: Symbolic dynamics. Am. J. Math. 60, 815–866 (1938)
Morse, M., Hedlund, G.A.: Symbolic dynamics II. Sturmian trajectories. Am. J. Math. 62, 1–42 (1940)
Fogg, N.P.: Substitutions in Dynamics, Arithmetics and Combinatorics. Lecture Notes in Mathematics, vol. 1794. Springer, Heidelberg (2002). https://doi.org/10.1007/b13861
Rotondo, P., Vallée, B: The recurrence function of a random Sturmian word. In: 2017 Proceedings of the Fourteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), pp. 100–114. SIAM, Philadelphia (2017)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Berthé, V., Mimouni, A. (2023). Recurrence and Frequencies. In: Frid, A., Mercaş, R. (eds) Combinatorics on Words. WORDS 2023. Lecture Notes in Computer Science, vol 13899. Springer, Cham. https://doi.org/10.1007/978-3-031-33180-0_7
Download citation
DOI: https://doi.org/10.1007/978-3-031-33180-0_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-33179-4
Online ISBN: 978-3-031-33180-0
eBook Packages: Computer ScienceComputer Science (R0)