Arithmetic progressions in space?

Here is a neat question that I stumbled upon during my academic random walk.

A sequence of k+1 vectors x_1, \ldots, x_{k+1} \in \mathbb{Z} ^ n is called an arithmetic progression of length k if there exists a vector d \in \mathbb{Z}^n such that x_{i+1} = x_i + d . In other words, an arithmetic progression in \mathbb{Z}^n is exactly the generalization you would expect of your good ol’ high-school arithmetic progression in \mathbb{Z} . For example, in \mathbb{Z}^2 , the sequence (11,12), (15,17), (19,22), (23,27) is an arithmetic progression of length 3, with difference vector (4,5) .

An infinite path in \mathbb{Z}^n is a sequence of distinct points x_1, x_2, \ldots \in \mathbb{Z}^n such that || x_i - x_{i+1}|| = 1 . In other words, you start at some x_0 , and then progress by going one step up or down or left or right or forward or backward or whatever it is they call it in general n dimensions, while making sure not to intersect yourself. For example, here is the beginning of an infinite path in \mathbb{Z}^2 , which also just happens to contain as a subset the arithmetic progression given above (shown in red):

Question: Does every infinite path in \mathbb{Z}^n contain arbitrarily long arithmetic progressions? That is, given a path x_1, x_2, \ldots \in \mathbb{Z}^n , is it true that it contains a subsequence x_{i_1}, \ldots, x_{i_{k+1}} which is an arithmetic progression, for every k ?

I really liked this question, since at first I had no clue as to what the answer was; while working on it I kept changing my mind, at one time certain that arithmetic progressions are unavoidable, and at the next imagining that an example of a progressionless path is nearly within my grasp.

You too, O’ faithful invisible readers, can tell me what you think, in the form of a non-binding referendum! Post your thoughts and ideas in the comments; I will post the answer in the not-too-distant future.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s