On square-free arithmetic progressions in infinite words
type: Item
instance of: scholarly article
title: On square-free arithmetic progressions in infinite words
zbMATH Open document ID: 1423.68372
published in: Theoretical Computer Science
publication date: 2019-05-02T00:00:00Z
review text: Let \(w\) be a word, and let \(w(i)\) stand for the \(i\)th letter of \(w\). The author shows that for each \(p\ge3\) there are infinite square-free ternary words \(w=w(1)w(2)w(3)\cdots\) such that the word \([w]_p=w(p)w(2p)w(3p)\cdots\) is square-free (Theorem 3). This result is tight since any square-free ternary word \(w\) with \([w]_2\) square-free has length at most 15. The construction in Theorem 3 relies on square-free cyclic shift morphisms found by \textit{J. Currie} [Theor. Comput. Sci. 482, 1--8 (2013; Zbl 1291.68302)] for \(p\ge23\) and on some cleverly selected square-free morphisms for each \(p=3,\dots,22\). The author concludes with three interesting open problems.
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 7050150
zbMATH Keywords: square-free word
zbMATH Keywords: square-free morphism
zbMATH Keywords: arithmetic progression
zbMATH Keywords: Thue word
zbMATH Keywords: Hall-Thue word
author: Tero Harju
MaRDI profile type: Publication
full work available at URL: j.tcs.2018.09.032
OpenAlex ID: W2895192162
cites work: Multidimensional unrepetitive configurations
cites work: Sharp characterizations of squarefree morphisms
cites work: Infinite ternary square-free words concatenated from permutations of a single word
cites work: A Sequence Without Repeats on x, x -1 , y, y -1
cites work: Q5735246
cites work: A Note on Square-Free Shuffles of Words
cites work: Q4151737
cites work: Words avoiding repetitions in arithmetic progressions
cites work: Q3659988
cites work: Unending chess, symbolic dynamics and a problem in semi-groups
cites work: Q5203929
Wikidata QID: Q129139887
DOI: 10.1016/J.TCS.2018.09.032
description: scientific article; zbMATH DE number 7050150