×

A proof of Dejean’s conjecture. (English) Zbl 1215.68192

Summary: We prove Dejean’s conjecture. Specifically, we show that Dejean’s conjecture holds for the last remaining open values of \( n\), namely \( 15 \leq n \leq 26\).

MSC:

68R15 Combinatorics on words
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Franz-Josef Brandenburg, Uniformly growing \?th power-free homomorphisms, Theoret. Comput. Sci. 23 (1983), no. 1, 69 – 82. · Zbl 0508.68051
[2] Jan Brinkhuis, Nonrepetitive sequences on three symbols, Quart. J. Math. Oxford Ser. (2) 34 (1983), no. 134, 145 – 149. · Zbl 0528.05004
[3] Arturo Carpi, On Dejean’s conjecture over large alphabets, Theoret. Comput. Sci. 385 (2007), no. 1-3, 137 – 151. · Zbl 1124.68087
[4] James Currie and Narad Rampersad, Dejean’s conjecture holds for \?\ge 30, Theoret. Comput. Sci. 410 (2009), no. 30-32, 2885 – 2888. · Zbl 1173.68050
[5] J. D. Currie, N. Rampersad, Dejean’s conjecture holds for \( n\geq 27\), Theor. Inform. Appl. 43 (2009) 775-778. · Zbl 1192.68497
[6] Françoise Dejean, Sur un théorème de Thue, J. Combinatorial Theory Ser. A 13 (1972), 90 – 99 (French). · Zbl 0245.20052
[7] Lucian Ilie, Pascal Ochem, and Jeffrey Shallit, A generalization of repetition threshold, Theoret. Comput. Sci. 345 (2005), no. 2-3, 359 – 369. · Zbl 1079.68082
[8] Dalia Krieger, On critical exponents in fixed points of non-erasing morphisms, Theoret. Comput. Sci. 376 (2007), no. 1-2, 70 – 88. · Zbl 1111.68058
[9] M. Lothaire, Algebraic combinatorics on words, Encyclopedia of Mathematics and its Applications, vol. 90, Cambridge University Press, Cambridge, 2002. A collective work by Jean Berstel, Dominique Perrin, Patrice Seebold, Julien Cassaigne, Aldo De Luca, Steffano Varricchio, Alain Lascoux, Bernard Leclerc, Jean-Yves Thibon, Veronique Bruyere, Christiane Frougny, Filippo Mignosi, Antonio Restivo, Christophe Reutenauer, Dominique Foata, Guo-Niu Han, Jacques Desarmenien, Volker Diekert, Tero Harju, Juhani Karhumaki and Wojciech Plandowski; With a preface by Berstel and Perrin. · Zbl 1001.68093
[10] M. Lothaire, Combinatorics on words, Encyclopedia of Mathematics and its Applications, vol. 17, Addison-Wesley Publishing Co., Reading, Mass., 1983. A collective work by Dominique Perrin, Jean Berstel, Christian Choffrut, Robert Cori, Dominique Foata, Jean Eric Pin, Guiseppe Pirillo, Christophe Reutenauer, Marcel-P. Schützenberger, Jacques Sakarovitch and Imre Simon; With a foreword by Roger Lyndon; Edited and with a preface by Perrin. · Zbl 0514.20045
[11] F. Mignosi and G. Pirillo, Repetitions in the Fibonacci infinite word, RAIRO Inform. Théor. Appl. 26 (1992), no. 3, 199 – 204 (English, with French summary). · Zbl 0761.68078
[12] M. Mohammad-Noori and James D. Currie, Dejean’s conjecture and Sturmian words, European J. Combin. 28 (2007), no. 3, 876 – 890. · Zbl 1111.68096
[13] 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). · Zbl 0745.68085
[14] 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). · Zbl 0536.68072
[15] M. Rao, Last cases of Dejean’s conjecture, Proc. WORDS 2009, Salerno (Italy), September 14-18, 2009. · Zbl 1230.68163
[16] Joseph J. Rotman, An introduction to the theory of groups, 4th ed., Graduate Texts in Mathematics, vol. 148, Springer-Verlag, New York, 1995. · Zbl 0810.20001
[17] A. M. Shur, I. A. Gorbunova, On the growth rates of complexity of threshold languages. In the local proceedings of the 12th Mons Theoretical Computer Science Days, 2008. · Zbl 1184.68341
[18] A. Thue, Über unendliche Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiana 7 (1906) 1-22.
[19] A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiana 1 (1912) 1-67. · 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.