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