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.


How far away must forced letters be so that squares are still avoidable?
HTML articles powered by AMS MathViewer

by Matthieu Rosenfeld HTML | PDF
Math. Comp. 89 (2020), 3057-3071 Request permission


We describe a new nonconstructive technique to show that squares are avoidable by an infinite word even if we force some letters from the alphabet to appear at certain occurrences. We show that as long as forced positions are at a distance at least 19 (resp., 3, resp., 2) from each other, then we can avoid squares over 3 letters (resp., 4 letters, resp., 6 or more letters). We can also deduce exponential lower bounds on the number of solutions. For our main theorem to be applicable, we need to check the existence of some languages and we explain how to verify that they exist with a computer. We hope that this technique could be applied to other avoidability questions where the good approach seems to be nonconstructive (e.g., the Thue-list coloring number of the infinite path).
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC (2010): 68R15
  • Retrieve articles in all journals with MSC (2010): 68R15
Additional Information
  • Matthieu Rosenfeld
  • Affiliation: Department Mathématique, Université de Liège, Ailée de la Découverte 12, 4000 Liège, Belgium
  • MR Author ID: 1169147
  • Email:
  • Received by editor(s): May 31, 2019
  • Received by editor(s) in revised form: October 22, 2019, January 7, 2020, and January 30, 2020
  • Published electronically: April 28, 2020
  • Additional Notes: Computational resources were provided by the Consortium des Équipements de Calcul Intensif (CÉCI), funded by the Fonds de la Recherche Scientifique de Belgique (F.R.S.-FNRS) under Grant No. 2.5020.11 and by the Walloon Region
  • © Copyright 2020 American Mathematical Society
  • Journal: Math. Comp. 89 (2020), 3057-3071
  • MSC (2010): Primary 68R15
  • DOI:
  • MathSciNet review: 4136557