[seqfan] Re: More about lex earliest cubefree 0,1 sequence

[L. Edson Jeffery]

Hello,

Assuming that the listed terms in A282317 are correct, we can prove that
the initial segment

X=
{0, 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, 0, 0, 1, 1,
 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1}

(comprising the first forty-four entries of the sequence) does not appear
later in the sequence.

Let B = {1,1}. First, the following is easy to prove:

(i) Any subsequence of A282317, not containing B, when extended far enough
to the right (in A282317) must eventually contain B.

A computer calculation shows that the longest possible subsequence of
A282317 not containing B can have length at most 15 (cf. table below). Let
L be a cubefree word over {0,1} of the form

(1) L = {U,B},

in which the word U is minimal (i.e., not maximal), starts and ends with 0
and does not contain B. Then we can partition A282317 into blocks of the
form (1). It turns out that there are precisely (and coincidentally)
twenty-six such possible distinct blocks. We can arrange the blocks in
lexicographical order, earliest to latest, and assign each to the
corresponding letter of the alphabet, as follows:

a = {0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1}
b = {0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1}
c = {0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1}
d = {0, 0, 1, 0, 0, 1, 0, 1, 1}
e = {0, 0, 1, 0, 0, 1, 1}
f = {0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1}
g = {0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1}
h = {0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1}
i = {0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1}
j = {0, 0, 1, 0, 1, 0, 0, 1, 1}
k = {0, 0, 1, 0, 1, 1}
l = {0, 0, 1, 1}
m = {0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1}
n = {0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1}
o = {0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1}
p = {0, 1, 0, 0, 1, 0, 0, 1, 1}
q = {0, 1, 0, 0, 1, 0, 1, 1}
r = {0, 1, 0, 0, 1, 1}
s = {0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1}
t = {0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1}
u = {0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1}
v = {0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1}
w = {0, 1, 0, 1, 0, 0, 1, 0, 1, 1}
x = {0, 1, 0, 1, 0, 0, 1, 1}
y = {0, 1, 0, 1, 1}
z = {0, 1, 1}

So, A282317 can be represented by a sequence of the above letters starting
as

{a, a, b, a, a, c, a, a, d, a, a, c, a, a, d, a, a, c, a, b, ...}.


Now, to prove the initial claim, assume that X = {a,a,b} does appear later
in A282317. Then A282317 = {a, a, b, ..., Y, a, a, b, ...}, say, where Y is
one of the above blocks. By hypothesis, the subsequence {Y,a,a,b} is
cubefree. However, for each possible Y, {Y,a,a,b} does contain a cube
(because each block ends with {0,1,1}), which is impossible. Therefore X
does not appear after Y, which is a contradiction. QED

By the way, A010060 uses a small subset of the above blocks, namely {k, l,
q, r, z}, all of the overlap-free ones. I wonder if (but doubt) there is a
substitution rule or morphism on these blocks that produces A010060.

Ed Jeffery