FOM: 21:Long Sequences/Update

Mon Oct 12 22:18:00 EDT 1998

This is the 21st in a series of self contained postings to fom
covering a wide range of topics in f.o.m. Previous ones are:

1:Foundational Completeness   11/3/97, 10:13AM, 10:26AM.
2:Axioms  11/6/97.
3:Simplicity  11/14/97 10:10AM.
4:Simplicity  11/14/97  4:25PM
5:Constructions  11/15/97  5:24PM
6:Undefinability/Nonstandard Models   11/16/97  12:04AM
7.Undefinability/Nonstandard Models   11/17/97  12:31AM
8.Schemes 11/17/97    12:30AM
9:Nonstandard Arithmetic 11/18/97  11:53AM
10:Pathology   12/8/97   12:37AM
11:F.O.M. & Math Logic  12/14/97 5:47AM
12:Finite trees/large cardinals  3/11/98  11:36AM
13:Min recursion/Provably recursive functions  3/20/98  4:45AM
14:New characterizations of the provable ordinals  4/8/98  2:09AM
14':Errata  4/8/98  9:48AM
15:Structural Independence results and provable ordinals  4/16/98
10:53PM
16:Logical Equations, etc.  4/17/98  1:25PM
16':Errata  4/28/98  10:28AM
17:Very Strong Borel statements  4/26/98  8:06PM
18:Binary Functions and Large Cardinals  4/30/98  12:03PM
19:Long Sequences  7/31/98  9:42AM
20:Proof Theoretic Degrees  8/2/98  9:37PM

A complete archiving of fom, message by message, is available at
http://www.math.psu.edu/simpson/fom/
Also, my series of self contained postings (only) is archived at
http://www.math.ohio-state.edu/foundations/manuscripts.html

This is an update to posting 19:Long Sequences.

Recall that for k >=3D 1, n(k) is the length of the longest sequence x
from {1,...,k} such that no block x_i,...,x_2i is a subsequence of any
other block x_j,...,x_2j. Recall that n(1) = 3, n(2) = 11, and n(3) is
incomprehensibly large. I gave the lower bound n(3) > A_7(184), where
A_7 is the seventh level of the Ackerman hierarchy of functions from Z+
into Z+, where it starts with A_1 = doubling.

We now introduce functions M_k:Z+ into Z+ as follows. Let k >= 1. M_k(n)
is the length of the longest sequence
x[1],...,x[p] from {1,...,k} such that for no n <= i < j <= p/2, is
x[i],...,x[2i] a subsequence of x[j],...,x[2j].

THEOREM 1. Let k >= 1. M_k+1 is an omega^omega^k recursive function. M_k+3
eventually domiantes every
< omega^omega^k recursive function. M_k+4 eventually dominates every
omega^omega^k recursive function. M_k+3 eventually dominates all
H_beta, beta < omega^k, in the fast growing hierarchy. M_k+1 is eventually
dominated by
H_(omega^k)+1. The binary function M_k(n) is strictly increasing in each
argument.

The function M_2, involving two letters 1,2, assumes special
importance. In fact, we write m(k) = M_2(k). By Theorem 1, the
function m is strictly increasing.

Note that m(1) = n(2) = 11.

THEOREM 2. For all k >= 2, m(13k+5) > A_k-1(22k+8). m(83) > A_5(118). The
function m eventually dominates any given primitive recursive
function.

Recently, Randy Dougherty has written and implemented software to
investigate the function m. He uses 0,1 instead of 1,2, and has found:

m(1) = 11:  01110000000

m(2) = 31:

0001101111110100000000000000000,

0001101111111100000000000000000

m(3) = 199:

0001011100011000000000010000000000000000000000011111111111111111111111111111
1111111111111111111100000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000110000,

0001011110011000000000010000000000000000000000011111111111111111111111111111
1111111111111111111100000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000110000

m(4) >= 187205.

Dougherty has found that the above displayed sequences for m(1),m(2),m(3),
are all of the
longest sequences of the required kind, except for reversing the bits,
and then changing the first k = 0,1,2 bits, respectively, and the last
bit. Thus there are 4 longest sequences for m(1), 16 longest sequences
for m(2), and 32 longest sequences for m(3).

OPEN PROBLEMS: What is the least k such that m(k) is incomprehensibly
large? E.g., m(k) >= A_5(5)? How large is m(4)? How many longest
sequences for m(k) are there? For m(4)? For n(k)? For n(3)? Give upper
and lower bounds for m(k+1) in terms of m(k). Give an upper bound for
m(k) in terms of the Ackerman hierarchy and k.

Dougherty's m(4) >= 187205 uses some man machine interaction. The far
smaller sequences that were generated by the computer for m(4) by brute
force, were examined. The observed patterns were used to obtain an
appropriate sequence of length 187205.

Dougherty also considered the lengths of special sequences, a very
special kind of finite sequence from {1,2,3}, which we used to obtain
our lower bound for n(3).

The longest special sequence we were able to obtain by hand was of
length 216. Then I developed a theory to lengthen this sequence of
length 216 to length A_7(184)+1 for the n(3) problem to obtain the upper
bound for n(3). Let
L be the longest length of a special sequence. L < n(3) is obvious.

Dougherty claims that L <= m(4), with the help of output from the
computer implementation. In addition, he reports that certain sequences
for m(4) can be easily modified to yield a special sequence of slightly
smaller length.

In this way, Dougherty claims that L >= 187196, using the particular
sequence constructed for the result m(4) >= 187205. This is beter than my L
>= 216 obtained by hand.

Now 187188 = 26(7199)+14. Using this lower bound of Dougherty, we have the
following improved lower bound for n(3):

THEOREM 3. n(3) > A_7198(158386).

I have a lower bound for n(4). Write A(t) = A_t(t).

THEOREM 4. n(4) is greater than AA...A(1), where there are A(L) A's.
Recall that L >= 187196.

Now that's a pretty big number.

All of 19: Long Sequences, and this posting except for Theorem 4, is in
Long Finite Sequences, October 10, 1998. Wait for this most recent
version to appear on my website

http://www.math.ohio-state.edu/foundations/manuscripts=

within a week.