FOM: Long Walks

[Harvey Friedman]

Want to take a very long walk without going forward very much? You can.

We use N for the set of all nonnegative integers. Let k >= 1. We say that
x,y in N^k are adjacent if and only if for all 1 <= i <= k, |x[i]-y[i]| <=
1. I.e., in going from x to y, each coordinate must change at most 1 unit.
A walk in N^k is a (finite or infinite) sequence from N^k, starting at the
origin, such that each term is adjacent to the next term. A forward path in
N^k is a sequence y[1],...,y[n] from N^k such that for all 1 <= i <= k and
1 <= p <= q <= n, y[p][i] <= y[q][i]. Note that a forward path is not
required to be a walk. We say that a forward path is contained in a walk if
and only if the forward path is a subsequence of that walk. E.g., in two
dimensions, (0,0),(1,1),(1,1) is a forward path in the walk
(0,0),(1,1),(1,0),(0,1),(1,1),(0,2). So is (0,0),(0,1),(0,2).

THEOREM 1. For all k,p >= 1, there is a longest walk in N^k with no forward
path of length p.

Let W(k,p) be the length of the longest walk in N^k with no forward path of
length p.

THEOREM 2. W(3,12) > 10^318. W(4,5) > 2^2^10^78. For k,p >= 3, W(k,p+1) >
A_k-1(p+1).

Here A_k is the k-th level of the Ackerman hierearchy, starting with A_1 =
doubling, A_2 = exponentiation, A_3 = superexponentiation, etcetera.Upper
bounds indicate that W(k,p) <= A_k(cp), k >= 2. Also W(k,3) grows faster
than any primitive recursive function. These estimates are very crude, and
will be revisited.