FOM: Long Walks #3
Harvey Friedman
friedman at math.ohio-state.edu
Mon Oct 26 04:18:48 EST 1998
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.
More information about the FOM
mailing list