A proof of Dejean’s conjecture
HTML articles powered by AMS MathViewer
- by James Currie and Narad Rampersad;
- Math. Comp. 80 (2011), 1063-1070
- DOI: https://doi.org/10.1090/S0025-5718-2010-02407-X
- Published electronically: August 30, 2010
- PDF | Request permission
Abstract:
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$.References
- Franz-Josef Brandenburg, Uniformly growing $k$th power-free homomorphisms, Theoret. Comput. Sci. 23 (1983), no. 1, 69–82. MR 693069, DOI 10.1016/0304-3975(88)90009-6
- Jan Brinkhuis, Nonrepetitive sequences on three symbols, Quart. J. Math. Oxford Ser. (2) 34 (1983), no. 134, 145–149. MR 698202, DOI 10.1093/qmath/34.2.145
- Arturo Carpi, On Dejean’s conjecture over large alphabets, Theoret. Comput. Sci. 385 (2007), no. 1-3, 137–151. MR 2356248, DOI 10.1016/j.tcs.2007.06.001
- James Currie and Narad Rampersad, Dejean’s conjecture holds for $n\geq 30$, Theoret. Comput. Sci. 410 (2009), no. 30-32, 2885–2888. MR 2543342, DOI 10.1016/j.tcs.2009.01.026
- J. D. Currie, N. Rampersad, Dejean’s conjecture holds for $n\ge 27$, Theor. Inform. Appl. 43 (2009) 775–778.
- Françoise Dejean, Sur un théorème de Thue, J. Combinatorial Theory Ser. A 13 (1972), 90–99 (French). MR 300959, DOI 10.1016/0097-3165(72)90011-8
- Lucian Ilie, Pascal Ochem, and Jeffrey Shallit, A generalization of repetition threshold, Theoret. Comput. Sci. 345 (2005), no. 2-3, 359–369. MR 2171619, DOI 10.1016/j.tcs.2005.07.016
- Dalia Krieger, On critical exponents in fixed points of non-erasing morphisms, Theoret. Comput. Sci. 376 (2007), no. 1-2, 70–88. MR 2316392, DOI 10.1016/j.tcs.2007.01.020
- 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. MR 1905123, DOI 10.1017/CBO9781107326019
- M. Lothaire, Combinatorics on words, Encyclopedia of Mathematics and its Applications, vol. 17, Addison-Wesley Publishing Co., Reading, MA, 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. MR 675953
- 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). MR 1170322, DOI 10.1051/ita/1992260301991
- M. Mohammad-Noori and James D. Currie, Dejean’s conjecture and Sturmian words, European J. Combin. 28 (2007), no. 3, 876–890. MR 2300768, DOI 10.1016/j.ejc.2005.11.005
- 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). MR 1156042, DOI 10.1016/0304-3975(92)90264-G
- 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). MR 736893, DOI 10.1016/0166-218X(84)90006-4
- M. Rao, Last cases of Dejean’s conjecture, Proc. WORDS 2009, Salerno (Italy), September 14–18, 2009.
- Joseph J. Rotman, An introduction to the theory of groups, 4th ed., Graduate Texts in Mathematics, vol. 148, Springer-Verlag, New York, 1995. MR 1307623, DOI 10.1007/978-1-4612-4176-8
- 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.
- A. Thue, Über unendliche Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiana 7 (1906) 1–22.
- A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiana 1 (1912) 1–67.
Bibliographic Information
- James Currie
- Affiliation: Department of Mathematics and Statistics, University of Winnipeg, 515 Portage Avenue, Winnipeg, Manitoba R3B 2E9, Canada
- Email: j.currie@uwinnipeg.ca
- Narad Rampersad
- Affiliation: Department of Mathematics and Statistics, University of Winnipeg, 515 Portage Avenue, Winnipeg, Manitoba R3B 2E9, Canada
- Address at time of publication: Department of Mathematics, University of Liège, Grand Traverse, 12 (Bat. B37), 4000 Liège, Belgium
- Email: narad.rampersad@gmail.com
- Received by editor(s): June 2, 2009
- Received by editor(s) in revised form: December 19, 2009
- Published electronically: August 30, 2010
- Additional Notes: The first author was supported by an NSERC Discovery Grant.
The second author was supported by an NSERC Postdoctoral Fellowship. - © Copyright 2010
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 80 (2011), 1063-1070
- MSC (2010): Primary 68R15
- DOI: https://doi.org/10.1090/S0025-5718-2010-02407-X
- MathSciNet review: 2772111