Dejean’s conjecture and letter frequency. (English) Zbl 1147.68612

Summary: We prove two cases of a strong version of Dejean’s conjecture involving extremal letter frequencies. The results are that there exist an infinite \((\frac54^+)\)-free word over a 5 letter alphabet with letter frequency \(\frac16\) and an infinite \((\frac65^+)\)-free word over a 6 letter alphabet with letter frequency \(\frac15\).


68R15 Combinatorics on words
Full Text: DOI EuDML HAL


[1] A. Carpi, On Dejeans conjecture over large alphabets. Theoret. Comput. Sci.385 (2007) 137-151. · Zbl 1124.68087
[2] C. Choffrut and J. Karhumäki, Combinatorics of words, in Handbook of Formal Languages, edited by G. Rozenberg and A. Salomaa, Springer-Verlag (1997) 329-438.
[3] M. Mohammad-Noori and J.D. Currie, Dejean’s conjecture and Sturmian words. Eur. J. Combin.28(3) (2007) 876-890. · Zbl 1111.68096
[4] F. Dejean, Sur un théorème de Thue. J. Combin. Theor. Ser. A13 (1972) 90-99. · Zbl 0245.20052
[5] A. Khalyavin. The minimal density of a letter in an infinite ternary square-free word is 883/3215. J. Integer Sequences10 (2007) 07.6.5. · Zbl 1140.11304
[6] R. Kolpakov, G. Kucherov and Y. Tarannikov, On repetition-free binary words of minimal density. Theoret. Comput. Sci.218 (1999) 161-175. · Zbl 0916.68118
[7] J. Moulin-Ollagnier, Proof of Dejean’s conjecture for alphabets with 5,6,7,8,9,10 and 11 letters. Theoret. Comput. Sci.95 (1992) 187-205. · Zbl 0745.68085
[8] P. Ochem, Letter frequency in infinite repetition-free words. Theoret. Comput. Sci.380 (2007) 388-392. · Zbl 1115.68124
[9] P. Ochem and T. Reix, Upper bound on the number of ternary square-free words, in Workshop on Words and Automata (WOWA’06). St. Petersburg, Russia, June 7 (2006).
[10] J.-J. Pansiot, À propos d’une conjecture de F. Dejean sur les répétitions dans les mots. Discrete Appl. Math.7 (1984) 297-311. · Zbl 0536.68072
[11] C. Richard and U. Grimm, On the entropy and letter frequencies of ternary square-free words. Electron. J. Comb.11 (2004) #R14. · Zbl 1104.68090
[12] Y. Tarannikov, The minimal density of a letter in an infinite ternary square-free word is 0.2746... J. Integer Sequences5 (2002) 02.2.2. · Zbl 1121.11303
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.