[seqfan] Re: The lex. earliest binary cube-free sequence
njasloane at gmail.com
Mon May 1 17:46:37 CEST 2017
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
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
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)
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?
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/
More information about the SeqFan