FOM: Long Binary Sequences

Harvey Friedman friedman at math.ohio-state.edu
Thu Oct 15 11:52:03 EDT 1998


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.





More information about the FOM mailing list