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 5:03AM 10/21/98. These results are more
focused.

***You can take a long walk from the origin without going outward very
much.***

[This slogan is given a clear meaning below].

This is a self contained sequel to 4:12AM 10/19/98.

We use Z for the set of all integers. Let k >= 1. We say that
x,y in Z^k are adjacent if and only if the Euclidean distance between x and
y is exactly 1. This is equivalent to saying that there exists 1 <= i <= k
such that

	i) x_i - y_i is 1 or -1;
	ii) for 1 <= j <= k, j not= i, we have x_j = y_j.

Thus, only one coordinate is altered, and that coordinate is altered by
exactly one unit.

A walk in Z^k is a (finite or infinite) sequence from Z^k such that
consecutive terms are adjacent.

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

We say that a (finite or infinite) sequence x_1,x_2,... from Z^k is outward
if and only if each term is <=* the next term.

Since walks are sequences, the concept of subsequence of walks is clear. We
are particularly interested in the outward subsequences of walks.

THEOREM 1. For all k >= 1, every infinite walk in Z^k has an infinite
outward subsequence.

THEOREM 2. For all k,n >= 1, there is a longest walk in Z^k starting at the
origin with no outward subsequence of length n. In fact, if x in Z^k then
there is a longest walk in Z^k starting at x with no outward subsequence of
length n.

Let W(k,n) be the length of the longest walk in Z^k starting at the origin
with no
outward subsequence of length n. More generally, let W(k,n,x) be the length
of the longest walk in Z^k starting at x with no outward subsequence of
length n.

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 3. For all n >= 1, W(2,3n+2) > 16^n. For all n,k >= 1, W(k,3n+2) >
A_k(n). There is a constant c such that for all n,k >= 1, W(k,n,x) <
A_k(ckn|x|). W(3,6) > 2^2^2^2^44. W(3,4,(1,1,1)) > 2^2^2^2^44.

Here |x| is the maximum of the absolute values of the coordinates of x. The
information is rather crude, and there is ample room for much improvement.