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