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

[Brendan McKay]

Each node in the tree has a 0-subtree and a 1-subtree, each of
which can be finite or infinite.

Now suppose we have the first k elements of the leftmost infinite
sequence  a[1],...,a[k].  We can do that for k=0 easily enough.
Then take a[k+1]=0 if the 0-subtree of this node is infinite and
a[k+1]=1 otherwise.  This never gets stuck because the property
that the current subtree is infinite is preserved by each step.

To prove this gives the leftmost infinite path, assume there is a
path even more to the left and find a contradiction at the place
where they first diverge.

None of this provides an algorithm in the strict Turing-machine
sense since it doesn't say how we can determine whether a subtree
is finite.  It would suffice if there is a Turing-computable function
B(k) which bounds the size of a finite subtree of a node at depth k.
Turing-computable functions can be stupendously large, but I don't
see any bound at all at the moment.

Brendan.


On 2/5/17 1:46 am, Neil Sloane wrote:
> 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/
>>
> --
> Seqfan Mailing list - http://list.seqfan.eu/