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

[Neil Sloane]

Frank, thanks for pointing out the error in my argument.
Can you give a reference for your proof?

I have been trying to write out a formal version of your argument.
Consider a tree T whose nodes are all the finite and infinite
binary cube-free strings,
with the empty string as the root,
where strings of length n are at level n,
string s at level n is joined by an edge to a string t at level n+1 if t=s0
or s1.
and strings at the same level are ordered left to right lexicographically.
Then we want to show that there is a left-most infinite path starting at
the root.

Konig's Lemma tells us that there ARE infinite paths (such as Thue-Morse).
But what is the argument that proves there is a left-most (or earliest)
infinite path?
It is tempting to say, prune the tree by dropping edges that
cannot be continued indefinitely. What's left is a non-empty tree.
But that doesn't seem enough show there is a left-most infinite path?





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 Mon, May 1, 2017 at 1:11 AM, Frank Adams-Watters via SeqFan <
seqfan at list.seqfan.eu> wrote:

> 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/
>