Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



How far away must forced letters be so that squares are still avoidable?

Author: Matthieu Rosenfeld
Journal: Math. Comp. 89 (2020), 3057-3071
MSC (2010): Primary 68R15
Published electronically: April 28, 2020
MathSciNet review: 4136557
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

Abstract: 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).

References [Enhancements On Off] (What's this?)


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

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
Article copyright: © Copyright 2020 American Mathematical Society