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 On 1/18/17 10:14 AM, James Propp wrote:
I seem to recall that this question is addressed in one of articles Jeff sent me last week, but I don't remember which.
Thanks,
Jim ---------- Forwarded message ---------- From: *Eric Angelini* <Eric.Angelini@kntv.be <mailto:Eric.Angelini@kntv.be>> Date: Wed, Jan 18, 2017 at 8:30 AM Subject: [math-fun] Thue-Morse and cubefree firs seq To: math-fun <math-fun@mailman.xmission.com <mailto:math-fun@mailman.xmission.com>> Cc: Gilles Esposito-Farese <gef@iap.fr <mailto:gef@iap.fr>>, Nicolas Graner <Nicolas.Graner@u-psud.fr <mailto:Nicolas.Graner@u-psud.fr>>
Hello Math-Fun, [copy to Gilles and Nicolas]
The late post about Thue-Morse raises (perhaps) this question: - what is the lexicographically first binary cubefree seq? Certainly not the Thue-Morse sequence [which starts with 0110 -- as this could be bettered by the start 00100101]. I find nothing about this putative seq I'm looking for in the OEIS, but I might be shortsighted or wrong (wrong in the sense that this lexicographically first seq is perhaps impossible to build). My friend Gilles Esposito-Farèse, for instance, has built a 3000-term seq which is cubefree (checked by computer) -- but is it the first one? And will the cubefree constraint hold in the seq he found if the said seq is extended, say, to 1 million terms? Could the million-and-one term affect the 1234-th one (for example), via a kind of backtracking? Best, É.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <mailto:math-fun@mailman.xmission.com> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun <https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>