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

Neil Sloane njasloane at gmail.com
Mon May 22 01:44:48 CEST 2017


Maximilian: excellent - will you please update the sequence
with a comment about what you did?

By the way, you said
> 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).
That is exactly why, in my previous email, I said to consider
an arbitrary subword P of the sequence.


Best regards
Neil

Neil J. A. Sloane, President, OEIS Foundation.
11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com


On Sun, May 21, 2017 at 4:18 PM, M. F. Hasler <seqfan at hasler.fr> wrote:

> 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
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>



More information about the SeqFan mailing list