Problem #231: Let $S$ be a string of length $2^k-1$ formed from an...

---

Progress

Erdős initially conjectured that the answer is yes for all $k\geq 2$, but for $k=4$ this was disproved by de Bruijn and Erdős. At least, this is what Erdős writes, but gives no construction or reference, and a simple computer search produces no such counterexamples for $k=4$. Perhaps Erdős meant $2^k$, where indeed there is an example for $k=4$:\[1213121412132124.\]Erdős then asked if there is in fact an infinite string formed from $\{1,2,3,4\}$ which contains no abelian squares? This is equivalent to [192], and such a string was constructed by Keränen [Ke92]. The existence of this infinite string gives a negative answer to the problem for all $k\geq 4$.

Containing no abelian squares is a stronger property than being squarefree (the existence of infinitely long squarefree strings over alphabets with $k\geq 3$ characters was established by Thue).

We refer to a recent survey by Fici and Puzynina [FiPu23] for more background and related results.