Thue (1906) showed that there exist arbitrarily long
square-free strings over an alphabet of three symbols (not true for
two symbols). An open problem was posed
in Grytczuk et al. (2010), which is a generalization of Thue's original
result: given an alphabet list L=L1, . . ., Ln$, where |Li|=3$, is
it always possible to find a square-free string,
w=w1w2 ⸳ ⸳ ⸳ wn, where wi ∈ Li? In this paper we show that squares can be forced on square-free strings over alphabet lists iff a suffix of the square-free string conforms to a pattern which we term as an offending suffix. We also prove properties of offending suffixes. However, the problem remains tantalizingly open.
|