FOM: Long Walks #3

[Harvey Friedman]

This version supercedes all earlier versions that were posted on the FOM.
The last posting on this topic was 10:18AM 10/26/98. These results
represent considerable improvement.

***You can take a long centered walk with rests without going outward.***

[This slogan is given a clear meaning below].

We use Z for the set of all integers. Let k >= 1. A walk in Z^k is a finite
or infinite sequence x[1],x[2],... from Z^k such that for all i, the
Euclidean distance from x[i] to x[i+1] is 1. A centered walk is a walk
where x[1] is the origin.

We use the geometrically significant partial ordering on Z^k given by x <=*
y if and only if for all 1 <= i <= k, 0 <= x[i] <= y[i] or 0 >= x[i] >=
y[i]. Conceptually, this means that the vector from x to y points
outward from the origin.

Let p >= 1. We can consider the subsequence x[p],x[2p],x[3p],... of the
walk x[1],x[2],... . This can be interpreted in terms of "resting" after
every p steps. Thus we walk x[1],...,x[p], then rest. Then walk
x[p+1],...,x[2p], then rest. And so on.

THEOREM 1. For all k,p >= 1, in every infinite walk x[1],x[2],... in Z^k,
there exists i < j such that x[pi] <=* x[pj].

THEOREM 2. For all k,p >= 1, there is a longest centered walk x[1],...,x[n]
in Z^k such that for no i < j is x[pi] <=* x[pj].

Let CW(k,p) be the length of the longest centered walk in Z^k for which
there is no i < j such that x[pi] <=* x[pj].

THEOREM 3. CW(3,4) > 2^2^2^2^2^2^2. For all n >= 5, CW(3,n) >
2^2^2^2^2^2^2^(n-4).

These results are crude, with no attempt at optimization.

The Ackerman hierarchy of functions is defined as follows. For each k >= 1,
we define A_k:Z+ into Z+. Let A_1 be doubling: i.e., A_1(n) = 2n. Suppose
A_k has been defined. Define A_k+1(n) = A_kA_k...A_k(1), where there are n
A_k's. It is easy to show that for all k >= 1, A_k(1) = 2 and A_k(2) = 4.
However, the function of k, A_k(3), is strictly increading in k, and in
fact eventually dominates each function in the Ackerman hierarchy. The
Ackerman function (of one variable) is defined as A(k) = A_k(k). Note that
A_2 is exponentiation, and A_3 is iterated exponentiation, or the tower
function.

THEOREM 4. Let k >= 2. A_k-1(p) < CW(k,p) < A_k(p+c). Here c is a universal
constant.

Again, this result is very crude, with no attempt at optimization. The plan
is to improve the basic setup and crude results as much as possible before
making a fully detailed study of this.