Zigzags and Collinear Lattice Points

Question

A "zigzag" is an infinite planar path formed by starting at $(0,0)$ and then repeatedly moving $1$ unit up or $1$ unit right. A lattice point is a point with integral coordinates. Given a zigzag $Z$ and a positive integer $n$, must $Z$ contain (at least) $n$ collinear lattice points?

Answer 1

In two dimensions it is fairly cheap. First observe (as it has been done already) that the bad path (if it exists) can cross any line with rational slope only finitely many times, which implies that eventually it is contained in an arbitrarily small angle $A_\varepsilon$ around some direction $\theta$ (i.e., $|y-\theta x|\le\varepsilon x$; WLOG the escape slope $\theta\le 1$, otherwise just swap $x$ and $y$). Now pick up a big $P$ and choose some $p\in\{1,\dots,P\},q\ge 0$ such that $|q-\theta p|\le 1/P$ (Dirichlet approximation theorem). Then for large $N$, the path has $\ge N/2$ points in the sector $A_{1/(pP)}\cap B(0,N)$ but for any point $(x,y)$ in this sector, we have $$|py-qx|\le p|y-\theta x|+|q-\theta p|x\le pN/(pP)+N/P\le 2N/P,$$ so there are at least $P/8$ points with the same value of $py-qx$, which are on the same line.

Answer 2

This paper shows that the answer to your question is yes. Specifically, look to lemma $(1)$ and lemma $(2)$, which are:

Let $m>1, \{p_i\}$ be a sequence in $\mathbb{Z}^m$ and $S$ be a finite subset of $\mathbb{Z}^m$ such that $p_{i+1}-p_i \in S$ for all $i$. Then for each positive integer $N$, there are $N$ integers $j$ and a rational hyperplane $H$ such that $p_j \in H$.

Let $m>1$ and $S$ be a finite subset of $\mathbb{Z}^m$. Let $N \in \mathbb{Z}^+$ be given. Then there is an $N' \in \mathbb{Z}^+$ such that if $\{p_i\}$ is a finite sequence in $\mathbb{Z}^m$ of length $N'$ and $p_{i+1}-p_i \in S$ for all $i < N'$, then there are $N$ distinct integers $j$ and a hyperplane $H$ such that $p_j \in H$.

For your question, $m = 2$, $S = \{(0, 1), (1, 0) \}$, and the hyperplane $H$ is a line. Let the $i$th point in the zigzag be given by $p_i$. Assume that $\theta = (\theta_x, \theta_y)$ is a cluster point of $\frac{p_i}{||p_i||}$, which will be a point on the unit circle in the first quadrant for our specific case.

The author defines $H$ to be the line through the origin and $\theta$. Then $H'$ and $H''$ are lines going through the origin with rational slopes forming angles with $H$ that are less than a specified angle, on opposite sides of $H$. Since a subsequence of points have $\frac{p_i}{||p_i||}$ converging to $\theta$, there are infinitely many choices for $p_J$ between $H'$ and $H''$. For each such $p_J$, there is a $p_j$ on the opposite side of $H'$ or $H''$, which means that the path traced by $p_i$ crosses $H'$ and $H''$ infinitely often. Since $H'$ and $H''$ have rational slopes, a finite number of translates of them cover all the points in $\mathbb{Z}^2$ within a distance of $1$. Then, one of these translates contains $p_i$ for infinitely many $i$.

There are more details in the paper, but what they basically show first is that there are all but a finite number of points within a region bounded by two lines which are a small angle (explicitly defined in the paper) from $H$. Then there must be a line going through $n$ points in this region. In this picture, $H$ is the middle line, and all the points in the path but a finite number of lattice points will be within the green and purple lines. Then they show that there must also be at least $n$ collinear points within this region.