Re: [math-fun] Fwd: Thue-Morse and cubefree firs seq
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>
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
On January 18th 2017 at 14:30, <Eric.Angelini@kntv.be> wrote:
- what is the lexicographically first binary cubefree seq?
Dear cube-free sequence fans (I am impressed to see some great names in the list!) Many thanks for your already deep answers. The construction of the first elements of the sequence is indeed straightforward, and one finds: AAB AAB AB AAB AAB B AAB AAB AB AAB AAB B AAB AAB AB AAB AB B AAB AAB AB AAB AAB B AAB AAB AB AAB AAB B AAB AAB AB AAB B AAB AAB AB AAB AAB B AAB AAB AB AAB AAB B AAB AAB AB B AAB AAB AB AAB AAB B AAB AAB AB AAB AAB B AAB AAB AB AAB B ... (where I used A and B instead of your 0 and 1). A kind of chaotic pattern appears, and one may thus define a more compact notation: 1 = AAB AAB AB AAB AAB B 2 = AAB AAB AB AAB AB B 3 = AAB AAB AB AAB B 4 = AAB AAB AB B 5 = AAB AB AAB AAB B 6 = AB AAB AAB B 7 = AB AAB B which allows me to give you now more than 15000 terms : 112 113 114 113 114 113 12 113 114 113 114 113 12 113 114 113 114 115 116 115 116 115 117 114 113 114 113 114 115 116 115 116 115 117 114 113 114 113 114 115 116 115 116 115 117 12 113 114 113 114 113 12 113 114 113 114 113 12 113 114 113 114 115 116 115 116 115 117 114 113 114 113 114 115 116 115 116 115 117 114 113 114 113 114 115 116 115 116 115 117 12 113 114 113 114 113 12 113 114 113 114 113 12 113 114 113 114 115 116 115 116 115 117 114 113 114 113 114 115 116 115 116 115 117 114 113 114 113 114 115 116 115 116 115 12 113 114 113 114 113 12 113 114 113 114 113 12 113 114 113 114 115 116 115 116 115 117 114 113 114 113 114 115 116 115 116 115 117 114 113 114 113 114 115 116 115 116 115 117 12 113 114 113 114 113 12 113 114 113 114 113 12 113 114 113 114 115 116 115 116 115 117 114 113 114 113 114 115 116 115 116 115 117 114 113 114 113 114 115 116 115 116 115 117 12 113 114 113 114 113 12 113 114 113 114 113 12 113 114 113 114 115 116 115 116 115 117 114 113 114 113 114 115 116 115 116 115 117 114 113 114 113 114 115 116 115 116 115 12 113 114 113 114 113 12 113 114 113 114 113 12 113 114 113 114 115 116 115 116 115 117 114 113 114 113 114 115 116 115 116 115 117 114 113 114 113 114 115 116 115 116 115 117 12 113 114 113 114 113 12 113 114 113 114 113 12 113 114 113 114 115 116 115 116 115 117 114 113 114 113 114 115 116 115 116 115 117 114 113 114 113 114 115 116 115 116 115 117 12 113 114 113 114 113 12 113 114 113 114 113 12 113 114 113 114 115 116 115 116 115 117 114 113 114 113 114 115 116 115 ... There again appears a clear structure, but it is obviously non periodic (cube-free), and the property of being the lexicographically first sequence seems to generate more chaos than for Prouhet-Thue-Morse. It can be shown that these first terms are correct, i.e., that they will never be modified by some subsequent term inducing a very long cube. [My naive way of proving so was to note that the substring BBAABB never appears, therefore that one may glue the infinite Prouhet-Thue-Morse sequence (starting from its 22nd term, i.e., precisely BBAABB) at a point, and this proves that the backtracking cannot spoil what we already computed.]
Can Esposito-Farèse report the maximum amount of backtracking that he needed
Well, I needed to program a specific routine to answer this question, as my method of construction did not work letter by letter (to increase its speed, and I therefore needed to backtrack more sometimes). When I work letter by letter, it seems that the backtracking never exceeds 3. It simply happens when one tries to add an extra A at the end of a string of the form ...ABB, and that this generates a cube (sometimes very long!). One should then a priori try to add a B instead, but ...ABBB is also forbidden. Therefore one has to go back to the previous ...A and replace it by ...B. [I checked that only on the first thousand of terms, and not on the full result above.] Many questions may be asked. One of the most immediate would be: Can it be proven that this sequence will never become equivalent to another known cube-free sequence (Prouhet-Thue-Morse, Kolakoski, Stewart's choral, ...) after a given term? A probably more difficult question: Does this sequence have any mathematical interest? (besides the fact that it also gives the lexicographically last cube-free sequence by replacing A <--> B ;-) Looking forward to your insights; sincerely, G.E-F
participants (3)
-
Gilles Esposito-Farese -
James Propp -
Jeffrey Shallit