Generating square-free words efficiently

Abstract

We study a simple algorithm generating square-free words from a random source. The source produces uniformly distributed random letters from a k-ary alphabet, and the algorithm outputs a (k+1)-ary square-free word. We are interested in the "conversion ratio" between the lengths of the input random word and the output square-free word. For any k≥3 we prove the expected value of this ratio to be a constant and calculate it up to an O(1/k5) term. For the extremal case of ternary square-free words, we suggest this ratio to have a constant expectation as well and conjecture its actual value from computer experiments. © 2015 Elsevier B.V..