[math-fun] Question on cubefree sequences
This follows on a recent discussion of the lexically first cubefree sequence. I have computed what I believe to be a(0..10000) of the lexically first infinite cubefree word over alphabet {0,1} (treating 0 < 1). I started to submit this sequence, however, when I got to the comments section, I began to write Since an infinite cubefree word over {0,1} exists, a lexically first such word must exist, so this sequence is well-defined. Then I caught myself, because I realized the reasoning was unsound. For example, there is an infinite word over {0, 1} that includes the digit 1, but no lexically first such word. So, do we actually know that there is a lexically first cubefree word over {0, 1}?
On 1/18/17, Jeffrey Shallit <shallit@uwaterloo.ca> wrote:
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
You could start by looking here! WFL On 2/4/17, David Wilson <davidwwilson@comcast.net> wrote:
This follows on a recent discussion of the lexically first cubefree sequence.
I have computed what I believe to be a(0..10000) of the lexically first infinite cubefree word over alphabet {0,1} (treating 0 < 1). I started to submit this sequence, however, when I got to the comments section, I began to write
Since an infinite cubefree word over {0,1} exists, a lexically first such word must exist, so this sequence is well-defined.
Then I caught myself, because I realized the reasoning was unsound. For example, there is an infinite word over {0, 1} that includes the digit 1, but no lexically first such word. So, do we actually know that there is a lexically first cubefree word over {0, 1}?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The space of all sequences is a complete metric space, with the following metric: if two sequences agree on the first n positions, then they are at distance <= 2^(-n). It is easy to see that the set of all sequences avoiding cubes is closed, so there is a unique lexicographically least element. On 2/4/17 5:12 PM, David Wilson wrote:
This follows on a recent discussion of the lexically first cubefree sequence.
I have computed what I believe to be a(0..10000) of the lexically first infinite cubefree word over alphabet {0,1} (treating 0 < 1). I started to submit this sequence, however, when I got to the comments section, I began to write
Since an infinite cubefree word over {0,1} exists, a lexically first such word must exist, so this sequence is well-defined.
Then I caught myself, because I realized the reasoning was unsound. For example, there is an infinite word over {0, 1} that includes the digit 1, but no lexically first such word. So, do we actually know that there is a lexically first cubefree word over {0, 1}?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
David Wilson -
Fred Lunnon -
Jeffrey Shallit