Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 


A proof of Dejean's conjecture

Authors: James Currie and Narad Rampersad
Journal: Math. Comp. 80 (2011), 1063-1070
MSC (2010): Primary 68R15
Published electronically: August 30, 2010
MathSciNet review: 2772111
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. Franz-Josef Brandenburg, Uniformly growing 𝑘th power-free homomorphisms, Theoret. Comput. Sci. 23 (1983), no. 1, 69–82. MR 693069, 10.1016/0304-3975(88)90009-6
  • 2. Jan Brinkhuis, Nonrepetitive sequences on three symbols, Quart. J. Math. Oxford Ser. (2) 34 (1983), no. 134, 145–149. MR 698202, 10.1093/qmath/34.2.145
  • 3. Arturo Carpi, On Dejean’s conjecture over large alphabets, Theoret. Comput. Sci. 385 (2007), no. 1-3, 137–151. MR 2356248, 10.1016/j.tcs.2007.06.001
  • 4. James Currie and Narad Rampersad, Dejean’s conjecture holds for 𝑛≥30, Theoret. Comput. Sci. 410 (2009), no. 30-32, 2885–2888. MR 2543342, 10.1016/j.tcs.2009.01.026
  • 5. J. D. Currie, N. Rampersad, Dejean's conjecture holds for $ n\ge 27$, Theor. Inform. Appl. 43 (2009) 775-778.
  • 6. Françoise Dejean, Sur un théorème de Thue, J. Combinatorial Theory Ser. A 13 (1972), 90–99 (French). MR 0300959
  • 7. Lucian Ilie, Pascal Ochem, and Jeffrey Shallit, A generalization of repetition threshold, Theoret. Comput. Sci. 345 (2005), no. 2-3, 359–369. MR 2171619, 10.1016/j.tcs.2005.07.016
  • 8. Dalia Krieger, On critical exponents in fixed points of non-erasing morphisms, Theoret. Comput. Sci. 376 (2007), no. 1-2, 70–88. MR 2316392, 10.1016/j.tcs.2007.01.020
  • 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. MR 1905123
  • 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. MR 675953
  • 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). MR 1170322
  • 12. M. Mohammad-Noori and James D. Currie, Dejean’s conjecture and Sturmian words, European J. Combin. 28 (2007), no. 3, 876–890. MR 2300768, 10.1016/j.ejc.2005.11.005
  • 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). MR 1156042, 10.1016/0304-3975(92)90264-G
  • 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). MR 736893, 10.1016/0166-218X(84)90006-4
  • 15. M. Rao, Last cases of Dejean's conjecture, Proc. WORDS 2009, Salerno (Italy), September 14-18, 2009.
  • 16. 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
  • 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.
  • 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.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 68R15

Retrieve articles in all journals with MSC (2010): 68R15

Additional Information

James Currie
Affiliation: Department of Mathematics and Statistics, University of Winnipeg, 515 Portage Avenue, Winnipeg, Manitoba R3B 2E9, Canada

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

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.
Article copyright: © Copyright 2010 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.