FOM: Long Walks #2 (corrected; please ignore previous version)

[Harvey Friedman]

***You can take a long walk from anywhere without going outward very
much.***  ***You can even take a long walk from anywhere off center without
going outward at all.***

[These slogans are given a clear meaning below].

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

I have talked to an expert in walks in lattices here (Peter March), and
this posting makes use of his feedback.

I think it is now best to conform to the most standard setups in this well
studied field of walks. The results will be more or less the same. I will
give some precise numbers in a later posting, as I am pressed with some
other matters right now.

So with this in mind, we restate the setup.

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,p >= 1, there is a longest walk in Z^k starting at the
origin with no outward subsequence of length p. 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 p.

Let W(k,p,x) be the length of the longest walk in Z^k starting at x with no
outward subsequence of
length p.

THEOREM 3. W(3,p,0) grows at least double exponentially. W(k,p,0) grows at
least like the k-1-st level of the Ackerman hierarchy, where the first
level is doubling, the second level is exponentiation, and the third level
is iterated exponentiation. Each W(k,_,_) is primitive recursive. Each
W(k,_,_) grows at most like the k-th level of the Ackerman hierarchy.

In 4:12AM 10/19/98, I gave some lower bounds for the earlier version of W
which would here read:

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

These have to be reexamined and probably will have to be modified, which I
will report on later. But the basic character of the results should be the
same. Also the claim at the end would read: W(k,3,0) grows faster than any
primitive recursive function. This needs to be modified to W(k,ck,0), where
c is a very small constant.

An important class of walks are the self avoiding walks. These are the
walks where no term repeats. So it is natural to define W'(k,p,x) to be the
length of the longest self avoiding walk in Z^k starting at x with no
outward subsequence of length p. It appears that the results should be of
the same kind.

It makes sense to require more of outward sequences. E.g., a substantially
outward sequence is an outward sequence where some coordinate moves at
least two units. Of course, sufficiently long walks may not have outward
subsequences of length even 2. But walks with sufficiently many distinct
terms do have substantially outward subsequences of prescribed length.
Obviously sufficiently long self avoiding walks have sufficiently many
distinct terms. Thus we can consider the associated W''(k,p,x). Here
W''(k,2,x) is interesting even for unit basis vectors x. This should also
behave wildly already at dimension k = 3. NOTE: This is the second slogan.