5
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ Are you looking for a hint or an answer? How far have you gotten on this question? $\endgroup$
    – Brian Tung
    Commented Aug 26, 2020 at 17:38
  • $\begingroup$ I will take whatever I am offered, with thanks. I have not gotten far, but I have experimented with small values of n, seeking to find, for a given n, the furthest one can walk without meeting the condition. That is, I am looking to see whether this leads to a shape or convex hull of a possible maximal region that FAILS to have n collinear points. Of course, two sides of this are parts of the positive x and y axes. $\endgroup$ Commented Aug 27, 2020 at 21:53
  • $\begingroup$ For example, for the easiest case with n = 2, the region is just the point (0, 0), as a step either left or right from any point yields two collinear points. For n = 3, the maximal region is the unit square. $\endgroup$ Commented Aug 27, 2020 at 22:17
  • 1
    $\begingroup$ What do you mean by "integral coordinates"? I'm not super familiar with how lattices work, but I'd like to try to help! $\endgroup$ Commented Aug 28, 2020 at 15:14
  • $\begingroup$ Integer = "whole number" but positive, negative, or zero; integral is adjective form. $\endgroup$ Commented Aug 28, 2020 at 19:43

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
4
+25
$\begingroup$

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.

enter image description here

$\endgroup$
6
  • $\begingroup$ The claim about $H'$ and $H''$ is false. Just take a sequence where all the angles converge to $\theta$, not just a subsequence, (which is possible). Then the points are eventually all between $H'$ and $H''$ and so the path can only cross the lines finitely many times. (Nonetheless, it is true that a path with no n collinear points can only cross any line with rational slope finitely many times.) It is also easy to construct a path which does not have infinitely many points between any two parallel lines (just follow closely a curve with positive second derivative). $\endgroup$ Commented Sep 3, 2020 at 14:04
  • $\begingroup$ @DavidHartley Hmm, I see your points. To be honest, I glossed over a lot of the details in the paper because of the length and complexity. The paper obviously explains it better than I could, so I will take another look at the paper and try to improve my answer. $\endgroup$ Commented Sep 3, 2020 at 16:22
  • $\begingroup$ Also, I think if a curve with positive second derivatives is followed, it would look nearly like a line at some section of points, so it would be even easier to show that there are $n$ collinear points. $\endgroup$ Commented Sep 3, 2020 at 16:27
  • $\begingroup$ @VarunVejalla You do not need two parallel lines, just an arbitrarily small angle around the limiting direction. I posted the details as an answer (too long for a comment box), but the credit and bounty should really be yours (though I cannot control that) :-) $\endgroup$
    – fedja
    Commented Sep 6, 2020 at 6:09
  • $\begingroup$ @fedja Yes, it seems I have misunderstood the paper. I have editted my answer to showcase that. $\endgroup$ Commented Sep 6, 2020 at 6:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .