FOM: More Long Binary Sequences

[Harvey Friedman]

This is an addendum to my posting of 4:52PM 10/15/98. I include this whole
previous posting for your convenience. The new stuff is at the end.
*****

Recall from my postings of 7/31/98 9:42AM, anbd 10/13/98 3:18AM, that

1. n(k) is defined to be the length of the longest sequence from {1,...,k}
such that there are no two distinct blocks of the form x[i],...,x[2i], i >=
k, such that the first is a subsequence of the second.

2. m(k) is defined to be the length of the longest binary sequence such
that there are no two distinct blocks of the form x[i],...,x[2i], i >= k,
such that the first is a subsequence of the second.

For each p >= 2, let B(p) be the length of the longest binary sequence such
that there are no p distinct blocks of the form x[i],...,x[2i], where each
block is a  subsequence of the later blocks. Each B(p) exists.

As indicated in earlier postings, the results are:

m(1) = 11, m(2) = 31, m(3) = 100, m(4) >= 187205.
n(3) > A_7198(158386).

What about B?

B(2) = m(1) = n(2) = 11. B(3) > A_7198(158386).

Here A_7198 is the 7198-th level of the Ackerman hierarchy, where the first
level is doubling, the second level is exponentiation, and the third level
is iterated exponentiation.

Added 10/16/98: Let A(k) be the unary Ackerman function, A(k) = A_k(k).

There are constants c,d such that m(k) <= A([ck+d]). Some detailed work
needs to be done to get really small c,d.

This is false for B. In fact, for k >= 2, B(2k-1) > AA...A(7198), where
there are k A's. In particular, B(3) > A(A(7198)).