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

Brendan McKay Brendan.McKay at anu.edu.au
Tue May 2 06:26:40 CEST 2017


Thinking more about this: although I still don't see a full algorithm,
I do see how any number of leading terms might be computed
rigorously.

At each step a[1],...,a[k], you need to either
(1) describe any infinite sequence starting a[1],...,a[k],0
      (in which case the next term is 0), OR
(2) exhaustive search the subtree at a[1],...,a[k],0 showing
     that it is finite (in which case the next term is 1).

If neither (1) or (2) can be achieved the method is stuck.  Since
we know how to construct some infinite cube-free sequences,
I suspect that step (1) can usually be accomplished if the subtree
is infinite.

Brendan.

On 2/5/17 2:12 pm, Brendan McKay wrote:
> 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/
>
>
> -- 
> Seqfan Mailing list - http://list.seqfan.eu/




More information about the SeqFan mailing list