FOM: More Long Binary Sequences
Harvey Friedman
friedman at math.ohio-state.edu
Fri Oct 16 06:57:34 EDT 1998
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)).
More information about the FOM
mailing list