Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

A proof of Dejean's conjecture


Authors: James Currie and Narad Rampersad
Journal: Math. Comp. 80 (2011), 1063-1070
MSC (2010): Primary 68R15
DOI: https://doi.org/10.1090/S0025-5718-2010-02407-X
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. F.-J. Brandenburg, Uniformly growing $ k$th power-free homomorphisms, Theoret. Comput. Sci. 23 (1983) 69-82. MR 693069 (84i:68148)
  • 2. J. Brinkhuis, Nonrepetitive sequences on three symbols, Quart. J. Math. Oxford (2) 34 (1983) 145-149. MR 698202 (84e:05008)
  • 3. A. Carpi, On Dejean's conjecture over large alphabets, Theoret. Comput. Sci. 385 (2007) 137-151. MR 2356248 (2008k:68083)
  • 4. J. D. Currie, N. Rampersad, Dejean's conjecture holds for $ n\ge 30$, Theoret. Comput. Sci. 410 (2009) 2885-2888. MR 2543342
  • 5. J. D. Currie, N. Rampersad, Dejean's conjecture holds for $ n\ge 27$, Theor. Inform. Appl. 43 (2009) 775-778.
  • 6. F. Dejean, Sur un théorème de Thue, J. Combin. Theory Ser. A 13 (1972) 90-99. MR 0300959 (46:119)
  • 7. L. Ilie, P. Ochem, J, Shallit, A generalization of repetition threshold, Theoret. Comput. Sci. 345 (2005) 359-369. MR 2171619 (2006h:68128)
  • 8. D. Krieger, On critical exponents in fixed points of non-erasing morphisms, Theoret. Comput. Sci. 376 (2007) 70-88. MR 2316392 (2008a:68110)
  • 9. M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press, Cambridge, 2002. MR 1905123 (2003i:68115)
  • 10. M. Lothaire, Combinatorics on Words, Encyclopedia of Mathematics and its Applications 17, Addison-Wesley, Reading, MA, 1983. MR 675953 (84g:05002)
  • 11. F. Mignosi, G. Pirillo, Repetitions in the Fibonacci infinite word, RAIRO Inform. Théor. Appl. 26 (1992) 199-204. MR 1170322 (93c:68083)
  • 12. M. Mohammad-Noori, J. D. Currie, Dejean's conjecture and Sturmian words, European J. Combin. 28 (2007) 876-890. MR 2300768 (2007m:68224)
  • 13. J. Moulin Ollagnier, Proof of Dejean's conjecture for alphabets with 5, 6, 7, 8, 9, 10 and 11 letters, Theoret. Comput. Sci. 95 (1992) 187-205. MR 1156042 (93f:68077)
  • 14. J.-J. Pansiot, A propos d'une conjecture de F. Dejean sur les répétitions dans les mots, Discrete Appl. Math. 7 (1984) 297-311. MR 736893 (85g:05010)
  • 15. M. Rao, Last cases of Dejean's conjecture, Proc. WORDS 2009, Salerno (Italy), September 14-18, 2009.
  • 16. J. J. Rotman, An introduction to the theory of groups, 4th ed, Springer-Verlag, Grad. Texts in Math. 148, 1995. MR 1307623 (95m: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.
  • 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
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

DOI: https://doi.org/10.1090/S0025-5718-2010-02407-X
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.

American Mathematical Society