[seqfan] Re: More about lex earliest cubefree 0,1 sequence

[M. F. Hasler]

On Sat, May 20, 2017 at 5:47 PM, Neil Sloane wrote:
> Dear Seqfans,
> I claim that the first 6 terms are correct, because the sequence S = 0010T
> = 001001101001...  = PT is cubefree(...)
> The starting point is the fact (Allouche and Shallit, Automatic Seqs., pp.
> 14-15) that T is not only cubefree, it is overlap-free, meaning there is no
> substring of the form ABABA, where B is a binary string and A is 0 or 1.

Indeed, this generalizes to an initial segment W of S of arbitrary length:
Suppose WT = XXX... with length(X) > length(W), specifically X=WY.
Then T=YXX... = YWYWY... = ABABA... with AB = YW, length(A)=1:
T not overlap free, contradiction.

To cover the case where XXX would start later in WT, re-do the
previous lines with W truncated by some of its first digit(s).

So it appears to me that the "such-and-such property" you mentioned earlier is:
"WT does not start with a cube XXX with length(X) <= length(W),
and the same for any left-truncation of W."

That way we can prove (quite easily) that arbitrarily long initial
segments W of S are correct (because they can be extended to an
infinite cubefree sequence).
(Of course not all initial segments will work, e.g., if W ends in
...00 then WT does contain a cube. We need to find a suitable W
containing at least the segment we want to prove correct.)

I have done this for the displayed 130 terms. (To do so it is
sufficient to check that the concatenation of these 130 terms with the
initial 260 initial terms of the Thue-Morse sequence A010060 is
cubefree, which happens to be the case.)

- Maximilian