FOM: Long Walks #5

Harvey Friedman friedman at math.ohio-state.edu
Tue Nov 10 10:55:13 EST 1998


Overall, my favorite formulation of the walk stuff is to depart slightly
from the usual notion of walk:

THEOREM 1. There is a longest sequence from the lattice set Z^3, starting
at (1,1,1), such that the Euclidean distance between any two consecutive
terms is at most 3, and no term points outward to any later term.

How long is such a sequence?

[We say that (a_1,a_2,a_3) points outward to (b_1,b_2,b_3) if and only if
for each 1 <= i <= 3, either 0 <= a_i <= b_i or 0 >= a_i >= b_i.]

Answer: Greater than 2^2^2^2^2^2^2.

As the dimension goes up (which is 3 above), you climb the Ackerman
hierarchy of functions.

If one wishes to use the usual definition of walk - which is Euclidean
distance exactly 1 between consecutive terms - then one introduces a slight
complication:

THEOREM 2. There is a longest sequence x_1,...,x_n from the lattice set
Z^3, starting at the origin, such that the Euclidean distance between any
two consecutive terms is 1, and no x_4i points outward to any x_4j, i < j.
Such a sequence is of length greater than 2^2^2^2^2^2^2.

Again, as the dimension goes up, you climb the Ackerman hierarchy of
functions.

A fuller statement of results will be given in the special posting series
after I have optimized these results some more. But I like this setup.








More information about the FOM mailing list