Erdős Problem #231

Let \(S\) be a string of length \(2^k-1\) formed from an alphabet of \(k\) characters. Must \(S\) contain an abelian square: two consecutive blocks \(x\) and \(y\) such that \(y\) is a permutation of \(x\)? 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. 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](https://www.erdosproblems.com/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. As stated, the answer is negative for every \(k \geq 2\): the strings \(121\) and \(1213121\) of length \(2^k - 1\) for \(k = 2, 3\) contain no abelian square. See `erdos_231.variants.two_pow` for strings of length \(2^k\).