I suspect this didn't get posted (since I believe that Jeff is not a member of math-fun and that non-members of math-fun can't post), so I'm forwarding it. Jim ---------- Forwarded message ---------- From: Jeffrey Shallit <shallit@uwaterloo.ca> Date: Wed, Jan 18, 2017 at 10:25 AM Subject: Re: Fwd: [math-fun] Thue-Morse and cubefree firs seq To: James Propp <jamespropp@gmail.com>, jean-paul allouche < jean-paul.allouche@imj-prg.fr>, Eric.Angelini@kntv.be, gef@iap.fr, Nicolas.Graner@u-psud.fr, math-fun <math-fun@mailman.xmission.com> The status of the lexicographically least cubefree sequence v over {0,1} is the same as the status of the lexicographically least squarefree sequence over {0,1,2}: namely, although it is possible to write down with certainty the first few terms of this sequence, almost nothing is known about it, for example: - does every finite cubefree word eventually appear in v? - do the letters 0 and 1 (and more generally any subword) have a limiting frequency in v, and if so, what is it? - is the word v generated by a finite automaton (in the way Thue-Morse is), or as the iteration of a morphism or image of such a word (in the way Thue-Morse is)? James Currie, in a series of papers with Shelton ("fixing blocks") developed a method to test, given a squarefree prefix p, whether p infinitely extendable to the right while maintaining the squarefree property. His method gives, in principle, a bound B on how many bits you need to extend such a prefix p before you know it is infinitely extendable, but I am not sure anyone has explicitly estimated how big B is in terms of |p|. Currie once told me it is o(|p|). This method should, in principle, apply to cubefree words, also. In contrast, the situation for overlap-free words is much better. The lexicographically least overlap-free word over {0,1} is known, and it is 001001 t', where t' is obtained from the Thue-Morse word t by interchanging 0 and 1. This was proved in this paper: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v5i1r27