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

DOI10.1090/MCOM/3535zbMATH Open1477.68257arXiv1903.04214OpenAlexW3005756005MaRDI QIDQ5118863FDOQ5118863

Authors: Matthieu Rosenfeld 

Publication date: 27 August 2020

Published in: Mathematics of Computation (Search for Journal in Brave)

Abstract: We describe a new non-constructive 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 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 non-constructive (e.g., the Thue-list coloring number of the infinite path).

Full work available at URL: https://arxiv.org/abs/1903.04214

Recommendations

• Avoiding squares over words with lists of size three amongst four symbols
• scientific article; zbMATH DE number 2051164
• Avoiding Approximate Squares
• Infinite words containing squares at every position
• Avoiding Abelian squares in partial words

zbMATH Keywords

avoidabilitysquaressquare-free wordsquare-free language

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Combinatorics on words (68R15) Computer assisted proofs of proofs-by-exhaustion type (68V05)

Cites Work

• New approach to nonrepetitive sequences
• Nonrepetitive colorings of graphs
• Exponential lower bounds for the number of words of uniform length avoiding a pattern
• Doubled patterns are 3-avoidable
• On square-free arithmetic progressions in infinite words
• Some further results on squarefree arithmetic progressions in infinite words

Cited In (1)

• AVOIDING APPROXIMATE SQUARES

This page was built for publication: How far away must forced letters be so that squares are still avoidable?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5118863)