[seqfan] Re: The lex. earliest binary cube-free sequence

[jean-paul allouche]

Hi

I remember that Jeff Shallit asked me the same question
some years ago. He had the same proof as F. A-W. for
the existence of the sequence. The difficulty about being
sure of the first terms is of course the risk of necessary backtracking
(it may well happen that at some point you get a dead end and have
to backtrack without being even sure that the length of the
backtracking is uniformly bounded).

jean-paul

Le 01/05/17 à 07:11, Frank Adams-Watters via SeqFan a écrit :
> This is not sufficient to show that there is a minimal element.
>
> Let S be the set of all sequences of zeros and ones that
> includes both 0 and 1. This is non-empty and totally
> ordered by the lexicographic ordering. But there is no
> minimal element: for every n, there is a sequence that
> starts with n zeros, and then has a 1:
> 0, 0, ..., 0, 1, 0, 0 ...
>
> Clearly each of these is in S. But equally obvious is that
> the greatest lower bound is the all zeros sequence -
> which is not in S.
>
> In order to show that S has a minimal element, you
> must show that, there is some property P, such
> that if every finite initial substring of S has the
> property P, then the sequence has the defining
> property of S. (You also need to have only finitely
> many choices for each next term, but that is
> trivially true here.)
>
> This does work here; if every initial substring is
> cube-free, then the sequence is cube-free.
> So there is a minimal cube-free sequence.
>
> Franklin T. Adams-Watters
>
>
> -----Original Message-----
> From: Neil Sloane <njasloane at gmail.com>
> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
> Sent: Sun, Apr 30, 2017 11:14 pm
> Subject: [seqfan] The lex. earliest binary cube-free sequence
>
> Consider the set S of all (0,1}-sequences that do not contain
> any cubes (no substring XXX).
> S is non-empty since it contains
> Thue-Morse A010060 and also A285196.
> S is totally ordered
> by lexicographic ordering.
> So by the Axiom of Choice there is a minimal element.
> David Wilson's A282317 is defined to be this minimal element.
> But there is no proof, as far as I know, that the terms
> that he has computed are correct (although they probably are correct.
> )His sequence begins0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0,1, ..
> and he gives a b-file with 10000 terms.  One way that one might prove that
> his terms are correct would be to guess some kind of recurrence
> that matches his terms, and then to use this
> characterization to prove that the infinite extension is
> indeed cube-free and minimal.
> This is the kind of question that we all deal with every day:
> givena sequence, find a rule that generates it. Here is a case when it would ber
> eally nice to find a rule!
> Of course it could be that there is no rule, other than the definition.
> But that is unlikely, given that  “God does not play dice with the
> universe”.--Seqfan Mailing list - http://list.seqfan.eu/
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/