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

Frank Adams-Watters franktaw at netscape.net
Mon May 1 07:11:04 CEST 2017

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/

More information about the SeqFan mailing list