City Research Online

Avoiding square-free words on free groups

Badkobeh, G. ORCID: 0000-0001-5550-7149, Harju, T. ORCID: 0000-0002-9640-6309, Ochem, P. ORCID: 0000-0001-5504-4586 & Rosenfeld, M. (2022). Avoiding square-free words on free groups. Theoretical Computer Science, 922, pp. 206-217. doi: 10.1016/j.tcs.2022.04.025


We consider sets of factors that can be avoided in square-free words on two-generator free groups. The elements of the group are presented in terms of {0, 1, 2, 3} such that 0 and 2 (resp., 1 and 3) are inverses of each other so that 02, 20, 13 and 31 do not occur in a reduced word. A Dean word is a reduced word that does not contain occurrences of uu for any nonempty . Dean showed in 1965 that there exist infinite square-free reduced words. We show that if w is a Dean word of length at least 59 then there are at most six reduced words of length 3 avoided by w. We construct an infinite Dean word avoiding six reduced words of length 3. We also construct infinite Dean words with low critical exponent and avoiding fewer reduced words of length 3. Finally, we show that the minimal frequency of a letter in a Dean word is 8/59 and the growth rate is close to 1.45818.

Publication Type: Article
Additional Information: © 2024. This manuscript version is made available under the CC-BY-NC-ND 4.0 license
Publisher Keywords: Combinatorics on wordsSquare-free words
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments: School of Science & Technology
School of Science & Technology > Computer Science
SWORD Depositor:
[thumbnail of Dean.pdf]
Text - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (443kB) | Preview


Add to AnyAdd to TwitterAdd to FacebookAdd to LinkedinAdd to PinterestAdd to Email


Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login