×

Proof of Dejean’s conjecture for alphabets with \(5, 6, 7, 8, 9, 10\) and \(11\) letters. (English) Zbl 0745.68085

Summary: Axel Thue proved that overlapping factors could be avoided in arbitrarily long words on a two-letter alphabet while, on the same alphabet, square factors always occur in words longer than 3. F. Dejean [J. Comb. Theory, Ser. A 13, 90–99 (1972; Zbl 0245.20052)] stated an analogous result for three-letter alphabets: every long enough word has a factor, which is a fractional power with an exponent at least 7/4 and there exist arbitrary long words in which no factor is a fractional power with an exponent strictly greater than 7/4. The number 7/4 is called the repetition threshold of the three-letter alphabets.
Thereafter, she proposed the following conjecture: the repetition threshold of the \(k\)-letter alphabets is equal to \(k/(k-1)\) except in the particular cases \(k=3\), where this threshold is 7/4, and \(k=4\), where it is 7/5.
For \(k=4\), this conjecture was proved by J. J. Pansiot [Discrete Appl. Math. 7, 297–311 (1984; Zbl 0536.68072)].
We give a computer-aided proof of Dejean’s conjecture for several other values: \(5, 6, 7, 8, 9, 10\) and \(11\).

MSC:

68R15 Combinatorics on words
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Dejean, F., Sur un théorème de Thue, J. Combin. Theory Ser. A, 13, 90-99 (1972) · Zbl 0245.20052
[2] Lothaire, M., Encyclopedia of Mathematics and its Applications, (Combinatorics on Words, 17 (1983), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 1221.68183
[3] Martin, J. C., Minimal Flows Arising from Substitutions of Nonconstant Length, Math. Systems Theory, 7, 1, 73-82 (1973) · Zbl 0256.54026
[4] 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
[5] Thue, A., Über unendliche Zeichenreihen, Norske Vid. Selsk. Skr. I Mat-Nat Kl. Christiana, 7, 1-22 (1906) · JFM 39.0283.01
[6] Thue, A., Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Selsk. Skr. I Mat-Nat Kl. Christiana, 1, 1-67 (1912) · 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. 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.