Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

A proof of Dejean’s conjecture
HTML articles powered by AMS MathViewer

by James Currie and Narad Rampersad PDF
Math. Comp. 80 (2011), 1063-1070 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, 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
  • 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.
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
  • 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