Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.78.

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