AMS :: Mathematics of Computation

Asymptotic repetitive threshold of balanced sequences
HTML articles powered by AMS MathViewer

by L’ubomíra Dvořáková, Daniela Opočenská and Edita Pelantová;

Math. Comp. 92 (2023), 1403-1429

DOI: https://doi.org/10.1090/mcom/3816

Published electronically: January 11, 2023

HTML | PDF | Request permission

Abstract:

The critical exponent $E(\mathbf u)$ of an infinite sequence $\mathbf u$ over a finite alphabet expresses the maximal repetition of a factor in $\mathbf u$. By the famous Dejean’s theorem, $E(\mathbf u) \geq 1+\frac 1{d-1}$ for every $d$-ary sequence $\mathbf u$. We define the asymptotic critical exponent $E^*(\mathbf u)$ as the upper limit of the maximal repetition of factors of length $n$. We show that for any $d>1$ there exists a $d$-ary sequence $\mathbf u$ having $E^*(\mathbf u)$ arbitrarily close to $1$. Then we focus on the class of $d$-ary balanced sequences. In this class, the values $E^*(\mathbf u)$ are bounded from below by a threshold strictly bigger than 1. We provide a method which enables us to find a $d$-ary balanced sequence with the least asymptotic critical exponent for $2\leq d\leq 10$.

References

G. Badkobeh and M. Crochemore, Finite-repetition threshold for infinite ternary words, Electron. Proc. Theor. Comput. Sci. (EPTCS) 63 (2011), 37–43., DOI 10.4204/EPTCS.63.7
A. R. Baranwal, Decision algorithms for Ostrowski-automatic sequences. Master Thesis, University of Waterloo, 2020.
Aseem R. Baranwal and Jeffrey Shallit, Critical exponent of infinite balanced words via the Pell number system, Combinatorics on words, Lecture Notes in Comput. Sci., vol. 11682, Springer, Cham, 2019, pp. 80–92. MR 4009062, DOI 10.1007/978-3-030-28796-2
J. Berstel and P. Séébold, Sturmian words, Algebraic combinatorics on words, 2002, pp. 45–110.
Arturo Carpi, On Dejean’s conjecture over large alphabets, Theoret. Comput. Sci. 385 (2007), no. 1-3, 137–151. MR 2356248, DOI 10.1016/j.tcs.2007.06.001
Arturo Carpi and Aldo de Luca, Special factors, periodicity, and an application to Sturmian words, Acta Inform. 36 (2000), no. 12, 983–1006. MR 1776146, DOI 10.1007/PL00013299
James Currie and Narad Rampersad, A proof of Dejean’s conjecture, Math. Comp. 80 (2011), no. 274, 1063–1070. MR 2772111, DOI 10.1090/S0025-5718-2010-02407-X
David Damanik and Daniel Lenz, The index of Sturmian sequences, European J. Combin. 23 (2002), no. 1, 23–29. MR 1878771, DOI 10.1006/eujc.2000.0496
Françoise Dejean, Sur un théorème de Thue, J. Combinatorial Theory Ser. A 13 (1972), 90–99 (French). MR 300959, DOI 10.1016/0097-3165(72)90011-8
F. M. Dekking, On repetitions of blocks in binary sequences, J. Combinatorial Theory Ser. A 20 (1976), no. 3, 292–299. MR 429728, DOI 10.1016/0097-3165(76)90023-6
Francesco Dolce, L’ubomíra Dvořáková, and Edita Pelantová, On balanced sequences and their critical exponent, Theoret. Comput. Sci. 939 (2023), 18–47. MR 4509497, DOI 10.1016/j.tcs.2022.10.014
Fabien Durand, A characterization of substitutive sequences using return words, Discrete Math. 179 (1998), no. 1-3, 89–101. MR 1489074, DOI 10.1016/S0012-365X(97)00029-0
L’ubomíra Dvořáková, Kateřina Medková, and Edita Pelantová, Complementary symmetric Rote sequences: the critical exponent and the recurrence function, Discrete Math. Theor. Comput. Sci. 22 ([2020–2021]), no. 1, Paper No. 20, 33. MR 4115748
L’ubomíra Dvořáková, Edita Pelantová, Daniela Opočenská, and Arseny M. Shur, On minimal critical exponent of balanced sequences, Theoret. Comput. Sci. 922 (2022), 158–169. MR 4436532, DOI 10.1016/j.tcs.2022.04.021
L’. Dvořáková and E. Pelantová, An upper bound on asymptotic repetitive threshold of balanced sequences via colouring of the Fibonacci sequence, arXiv:2211.11877 (2022).
I. P. Goulden, Andrew Granville, L. Bruce Richmond, and Jeffrey Shallit, Natural exact covering systems and the reversion of the Möbius series, Ramanujan J. 50 (2019), no. 1, 211–235. MR 4008106, DOI 10.1007/s11139-018-0030-y
J. W. Hoffman, W. R. Livingston, and J. Ruiz, A note on disjoint covering systems–variations on a 2002 AIME problem, Math. Mag. 84 (2011), no. 3, 211–215., DOI 10.4169/math.mag.84.3.211
P. Hubert, Suites équilibrées, Theoret. Comput. Sci. 242 (2000), no. 1-2, 91–108 (French, with English and French summaries). MR 1769142, DOI 10.1016/S0304-3975(98)00202-3
Jacques Justin and Giuseppe Pirillo, Episturmian words and episturmian morphisms, Theoret. Comput. Sci. 276 (2002), no. 1-2, 281–313. MR 1896357, DOI 10.1016/S0304-3975(01)00207-9
Dalia Krieger and Jeffrey Shallit, Every real number greater than 1 is a critical exponent, Theoret. Comput. Sci. 381 (2007), no. 1-3, 177–182. MR 2347401, DOI 10.1016/j.tcs.2007.04.037
M. Mohammad-Noori and James D. Currie, Dejean’s conjecture and Sturmian words, European J. Combin. 28 (2007), no. 3, 876–890. MR 2300768, DOI 10.1016/j.ejc.2005.11.005
Marston Morse and Gustav A. Hedlund, Symbolic dynamics II. Sturmian trajectories, Amer. J. Math. 62 (1940), 1–42. MR 745, DOI 10.2307/2371431
Jean Moulin Ollagnier, Proof of Dejean’s conjecture for alphabets with $5,6,7,8,9,10$ and $11$ letters, Theoret. Comput. Sci. 95 (1992), no. 2, 187–205 (English, with French summary). MR 1156042, DOI 10.1016/0304-3975(92)90264-G
Jean-Jacques Pansiot, À propos d’une conjecture de F. Dejean sur les répétitions dans les mots, Discrete Appl. Math. 7 (1984), no. 3, 297–311 (French, with English summary). MR 736893, DOI 10.1016/0166-218X(84)90006-4
Š. Porubský and J. Schönheim, Covering systems of Paul Erdős. Past, present and future, Paul Erdős and his mathematics, I (Budapest, 1999) Bolyai Soc. Math. Stud., vol. 11, János Bolyai Math. Soc., Budapest, 2002, pp. 581–627. MR 1954716
Narad Rampersad, Jeffrey Shallit, and Élise Vandomme, Critical exponents of infinite balanced words, Theoret. Comput. Sci. 777 (2019), 454–463. MR 3961908, DOI 10.1016/j.tcs.2018.10.017
Michaël Rao, Last cases of Dejean’s conjecture, Theoret. Comput. Sci. 412 (2011), no. 27, 3010–3018. MR 2830264, DOI 10.1016/j.tcs.2010.06.020
Ofir Schnabel, On the reducibility of exact covering systems, Integers 15 (2015), Paper No. A34, 8. MR 3372478
Jeffrey Shallit, Simultaneous avoidance of large squares and fractional powers in infinite binary words, Internat. J. Found. Comput. Sci. 15 (2004), no. 2, 317–327. MR 2071461, DOI 10.1142/S0129054104002443
R. J. Simpson, Regular coverings of the integers by arithmetic progressions, Acta Arith. 45 (1985), no. 2, 145–152. MR 797258, DOI 10.4064/aa-45-2-145-152
Igor N. Tunev and Arseny M. Shur, On two stronger versions of Dejean’s conjecture, Mathematical foundations of computer science 2012, Lecture Notes in Comput. Sci., vol. 7464, Springer, Heidelberg, 2012, pp. 800–812. MR 3030481, DOI 10.1007/978-3-642-32589-2_{6}9
Laurent Vuillon, A characterization of Sturmian words by return words, European J. Combin. 22 (2001), no. 2, 263–275 (English, with English and French summaries). MR 1808196, DOI 10.1006/eujc.2000.0444
E. Zeckendorf, A generalized Fibonacci numeration, Fibonacci Quart. 10 (1972), no. 4, 365–372. MR 309854
Štefan Znám, On exactly covering systems of arithmetic sequences, Math. Ann. 180 (1969), 227–232. MR 242760, DOI 10.1007/BF01350740