×

On Dejean’s conjecture over large alphabets. (English) Zbl 1124.68087

Summary: The (maximal) exponent of a non-empty finite word is the ratio of its length to its period. F. Dejean [J. Comb. Theory, Ser. A 13, 90–99 (1972; Zbl 0245.20052)] conjectured that for any \(n\geq 5\) there exists an infinite word over \(n\) letters with no factor of its exponent larger than \(n/(n - 1)\). We prove that this conjecture is true for \(n\geq 33\).

MSC:

68R15 Combinatorics on words
68Q45 Formal languages and automata

Citations:

Zbl 0245.20052
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] J. Berstel, Axel Thue’s papers on repetition in words: A translation, Publications du LaCIM, Université du Québec á Montréal 20, 1995
[2] Berstel, J.; Karhumäki, J., Combinatorics on words: A tutorial, Bull. eur. assoc. theor. comput. sci., 79, 178-228, (2003) · Zbl 1169.68560
[3] Brandenburg, F.-J., Uniformly growing \(k\)-th power-free homomorphisms, Theoret. comput. sci., 23, 69-82, (1983) · Zbl 0508.68051
[4] Carpi, A., On the repetitive threshold for large alphabets, (), 226-237 · Zbl 1132.68515
[5] Crochemore, M.; Goralcik, P., Mutually avoiding ternary words of small exponent, Internat. J. algebra comput., 1, 407-410, (1991) · Zbl 0762.05011
[6] Dejean, F., Sur un théorème de thue, J. combin. theory ser. A, 13, 90-99, (1972) · Zbl 0245.20052
[7] Ilie, L.; Ochem, P.; Shallit, J., A generalization of repetition threshold, (), 818-826 · Zbl 1097.68110
[8] Karhumäki, J.; Shallit, J., Polynomial versus exponential growth in repetition-free binary words, J. combin. theory ser. A, 105, 335-347, (2004) · Zbl 1065.68080
[9] Lothaire, M., Algebraic combinatorics on words, () · Zbl 1001.68093
[10] Mohammad-Noori, M.; Currie, J.D., Dejean’s conjecture and Sturmian words, European J. combin., 28, 876-890, (2007) · Zbl 1111.68096
[11] 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
[12] 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
[13] Shallit, J., Simultaneous avoidance of large squares and fractional powers in infinite binary words, Internat. J. found. comput. sci., 15, 317-327, (2004) · Zbl 1067.68119
[14] Thue, A., Uber unendliche zeichenreihen, Norske vid. selsk. skr. I. mat. nat. kl., Christiania 7, 1-22, (1906), Reprinted in: T. Nagell (Ed.), Selected Mathematical Papers of Axel Thue, Universitetsforlaget, Oslo, 1977, pp. 139-158 · JFM 39.0283.01
[15] Thue, A., Uber die gegenseitige lage gleicher teile gewisser zeichenreihen, Norske vid. selsk. skr. mat. nat. kl., Christiania 1, 1-67, (1912), Reprinted in: T. Nagell (Ed.), Selected Mathematical Papers of Axel Thue, Universitetsforlaget, Oslo, 1977, pp. 413-478 · JFM 44.0462.01
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.