Pairs of square-free arithmetic progressions in infinite words

Abstract

We study a question of Harju from 2019 regarding the existence of infinite ternary square-free words whose subsequences modulo $p$ and $q$ are also square-free for relatively prime integers $p$ and $q$. Among such pairs $(p,q)$ with $p,q\ge 3$, the only two pairs with this property known prior to this work were $(3,11)$ and $(5,6)$. We prove that there are finitely many pairs $(p,q)$ of relatively prime integers with $p,q\ge 3$ for which there is no infinite ternary square-free word whose subsequences modulo $p$ and $q$ are square-free. To prove our result, we combine different techniques, including the construction of words from multi-valued square-free morphisms and circular square-free morphisms. We also introduce the notion of square-free transducers, a generalization of square-free morphisms that may be of independent interest.