Frequencies of letters in infinite k-balanced sequences
DOI:
https://doi.org/10.14311/AP.2025.65.0534Keywords:
letter frequency , balanced sequences, balancedness threshold, factor complexityAbstract
The frequency of letters in a symbolic sequence u over a finite alphabet is one of the basic characteristics of u. The notion of k-balancedness captures the property that the number of any letter occurring in two arbitrary factors of u of equal length differs at most by k. For a fixed integer k and alphabet size d ∈ N, we discuss possible frequencies of letters in k-balanced d-ary sequences. For the size d of the alphabet, we introduce the notion of balancedness threshold BT(d) and provide an upper bound on it, where BT(d) is the minimum k such that there exists a k-balanced sequence over a d-letter alphabet for all possible letter frequencies.
Downloads
References
M. Morse, G. A. Hedlund. Symbolic dynamics II. Sturmian trajectories. American Journal of Mathematics 62(1):1–42, 1940. https://doi.org/10.2307/2371431
L’. Balková, E. Pelantová, Š. Starosta. Sturmian jungle (or garden?) on multiliteral alphabets. RAIRO – Theoretical Informatics and Applications 44(4):443–470, 2010. https://doi.org/10.1051/ita/2011002
G. Richomme, K. Saari, L. Q. Zamboni. Abelian complexity of minimal subshifts. Journal of the London Mathematical Society 83(1):79–95, 2011. https://doi.org/10.1112/jlms/jdq063
L. Vuillon. A characterization of Sturmian words by return words. European Journal of Combinatorics 22(2):263–275, 2001. https://doi.org/10.1006/eujc.2000.0444
P. Arnoux, Š. Starosta. The Rauzy gasket. In B. Boston (ed.), Further Developments in Fractals and Related Fields, Trends in Mathematics, pp. 1–23. Birkhäuser, Boston, 2013. https://doi.org/10.1007/978-0-8176-8400-6_1
A. Zorich. Deviation for interval exchange transformations. Ergodic Theory and Dynamical Systems 17(6):1477–1499, 1997. https://doi.org/10.1017/S0143385797086215
P. Hubert. Suites équilibrées. Theoretical Computer Science 242(1–2):91–108, 2000. https://doi.org/10.1016/S0304-3975(98)00202-3
L. Dvořáková, Z. Masáková, E. Pelantová. 2-balanced sequences coding rectangle exchange transformation. Theoretical Computer Science 68(6):1537–1555, 2024. https://doi.org/10.1007/s00224-024-10188-6
M. Andrieu, L. Vivion. Imbalances in hypercubic billiard words. In 18th Mons Theoretical Computer Science Days. Prague, 2022.
P. Arnoux, C. Mauduit, I. Shiokawa, J.-I. Tamura. Complexity of sequences defined by billiard in the cube. Bulletin de la Société Mathématique de France 122(1):1– 12, 1994. https://doi.org/10.24033/bsmf.2220
P. Arnoux, C. Mauduit, I. Shiokawa, J.-I. Tamura. Rauzy’s conjecture on billiards in the cube. Tokyo Journal of Mathematics 17(1):211–218, 1994. https://doi.org/10.3836/tjm/1270128200
N. Bedaride, P. Hubert. Billiard complexity in the hypercube. Annales de l’Institut Fourier 57(3):719–738, 2007. https://doi.org/10.5802/aif.2274
M. Queffélec. Substitution dynamical systems – spectral analysis. Lecture notes in mathematics. Springer-Verlag, Heidelberg, 2nd edn., 2010. https://doi.org/10.1007/978-3-642-11212-6
V. Berthé, V. Delecroix. Beyond substitutive dynamical systems: S-adic expansions. RIMS Kôkyûroku Bessatsu B46:81–123, 2014.
B. Adamczewski. Balances for fixed points of primitive substitutions. Theoretical Computer Science 307(1):47–75, 2003. https://doi.org/10.1016/S0304-3975(03)00092-6
J. Cassaigne. Un algorithme de fractions continues de complexité linéaire, 2015. DynA3S meeting, LIAFA, Paris.
J. Cassaigne, S. Labbé, J. Leroy. Almost everywhere balanced sequences of complexity 2n + 1. Combinatorics and Number Theory 11(4):287–333, 2022. https://doi.org/10.2140/moscow.2022.11.287
M. Newman. Roots of unity and covering sets. Mathematische Annalen 191(4):279–282, 1971. https://doi.org/10.1007/BF01350330
M. Lothaire. Algebraic combinatorics on words. Encyclopedia of Mathematics and Its Applications. Cambridge University Press, Cambridge, 2002. https://doi.org/10.1017/CBO9781107326019
N. Bedaride. Directional complexity of the hypercubic billiard. Discrete Mathematics 309(8):2053–2066, 2009. https://doi.org/10.1016/j.disc.2008.04.018
L. Vuillon. Balanced words. Bulletin of the Belgian Mathematical Society – Simon Stevin 10(5):787–805, 2003. https://doi.org/10.36045/bbms/1074791332
Downloads
Published
Issue
Section
License
Copyright (c) 2025 L’ubomíra Dvořáková, Edita Pelantová
This work is licensed under a Creative Commons Attribution 4.0 International License.
