×

Dejean’s conjecture and Sturmian words. (English) Zbl 1111.68096

Summary: Dejean conjectured that the repetition threshold of a \(k\)-letter alphabet is \(k/(k - 1)\), \(k\not= 3,4\). Values of the repetition threshold for \(k\) were found by Thue, Dejean and Pansiot. Moulin-Ollagnier attacked Dejean’s conjecture for \(5\leq k\leq\) 11. Building on the work of Moulin-Ollagnier, we propose a method for deciding whether a given Sturmian word with quadratic slope confirms the conjecture for a given \(k\). Elaborating this method in terms of directive words, we develop a search algorithm for verifying the conjecture for a given \(k\). An implementation of our algorithm gives suitable Sturmian words for \(7\leq k\leq 14\). We prove that for \(k=5\), no suitable Sturmian word exists.

MSC:

68R15 Combinatorics on words
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adjan, S.; Novikov, P. S., Infinite periodic groups I-III, Izv. Akad. Nauk SSSR Ser. Mat., 32 (1968), (in Russian)
[2] Beck, J., An application of Lovász local lemma: there exists an infinite 01-sequence containing no near identical intervals, (Finite and Infinite Sets, Vol. I, II (Eger, 1981). Finite and Infinite Sets, Vol. I, II (Eger, 1981), Colloq. Math. Soc. Jnos Bolyai, vol. 37 (1984), North-Holland: North-Holland Amsterdam), 103-107 · Zbl 0567.05010
[3] Berstel, J., Axel Thue’s papers on repetitions in words: a translation, (Publications du LCIM, vol. 20 (1994), Université du Quebec à Montréal)
[4] Brandenburg, F. J., Uniformly growing k-th powerfree homomorphisms, Theoret. Comput. Sci., 23, 69-82 (1983) · Zbl 0508.68051
[5] Main, M. G.; Bucher, W.; Haussler, D., Applications of an Infinite Squarefree CO-CFL, Inf. Process Lett., 20, 105-107 (1985) · Zbl 0602.68060
[6] Carpi, A., Multidimensional unrepetitive configurations, Theoret. Comput. Sci., 56, 2, 233-241 (1988) · Zbl 0649.68073
[7] Cassaigne, J.; Currie, J. D., Words strongly avoiding fractional powers, European J. Combin., 20, 8, 725-737 (1999) · Zbl 0948.68140
[8] Currie, J. D.; Shelton, R. O., Cantor sets and Dejean’s conjecture, J. Autom. Lang. Comb., 1, 2, 113-127 (1996) · Zbl 0867.68068
[9] Dejean, F., Sur un théorème de Thue, J. Combin. Theory Ser. A, 13, 90-99 (1972) · Zbl 0245.20052
[10] Jezek, J., Intervals in the lattice of varieties, Algebra Universalis, 6, 147-158 (1976) · Zbl 0354.08007
[11] Justin, J., Characterization of the repetitive commutative semigroups, J. Algebra, 21, 87-90 (1972) · Zbl 0248.05004
[12] Justin, J.; Vuillon, L., Return words in Sturmian and episturmian words, Theor. Inform. Appl., 34, 343-356 (2000) · Zbl 0987.68055
[13] M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press, London, pp. 45-110; M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press, London, pp. 45-110 · Zbl 1001.68093
[14] Morse, M., Recurrent geodesics on a surface of negative curvature, Trans. Amer. Math. Soc., 22, 84-100 (1921) · JFM 48.0786.06
[15] Moulin-Ollagnier, J., Proof of Dejean’s conjecture for alphabets with 5,6,7,8,9,10 and 11 letters, Theoret. Comput. Sci., 95, 187-205 (1992) · Zbl 0745.68085
[16] Pansiot, J.-J., A propos d’une conjecture de F. Dejean sur les répétitions dans les mots, Discrete Appl. Math., 7, 297-311 (1984) · Zbl 0536.68072
[17] Thue, A., Über unendliche Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiana, 7 (1906) · JFM 39.0283.01
[18] Thue, A., Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiana, 10 (1912) · JFM 44.0462.01
[19] Trotter, W. T.; Winkler, P., Arithmetic progressions in partially ordered sets, ORDER, 4, 37-42 (1987) · Zbl 0629.06005
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.