FOM: Long Walks #4 (corrected version)

Harvey Friedman friedman at
Wed Oct 28 04:45:07 EST 1998

PATIENT AUDIENCE: I correctly renumbered the title from #3 to #4. I also
replaced n-4 by n-3 in Theorem 3. You should delete the previous posting of
this morning.

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) >

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

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

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.

More information about the FOM mailing list