Conjecture regarding closest point inside a discrete ball to a line

Question

I'm a PhD student in image processing, where I've stumbled into a problem that seems to be essentially number theory. I've hunted around online and while I've found many results on similar problems, this particular problem I cannot seem to find a solution to:

Given a line in the plane passing through the origin making angle $\theta$ with the $x$-axis, I am trying to determine the closest nonzero Gaussian integer $n+im$ to the line obeying $|n+im| \le r$.

I have a conjecture which is backed up by numerous computer tests, but no proof. The conjecture is as follows:

Let $\Theta(r) = \{\theta_1,\theta_2,...,\theta_N\}$ denote the set of angles representable using Gaussian integers of this form. That is, each $\theta_k=Arg(n+im)$ for some non-zero Gaussian integer $n+im$ of norm at most $r$.

Find $\theta_k, \theta_{k+1}$ straddling $\theta$, i.e. $\theta_k \le \theta < \theta_{k+1}$. Let $n+im$ be a Gaussian integer that solves our minimization problem. Then either $Arg(n+im)=\theta_k$ or $Arg(n+im)=\theta_{k+1}$.

Answer 1

This is true and I would be grateful if someone could make a figure to the argument below. Your conjecture follows from the following statement.

Let $\ell$ pass through the origin, $O$. For simplicity, suppose $\ell$ has a positive slope and let $P=(n,m)$ for some $m,n>0$ such that $P$ lies under $\ell$. Denote by $Q$ the point on $\ell$ whose $y$ coordinate is $m$ and by $R$ the point on the $x$-axis such that $ORPQ$ forms a parallelogram. Using symmetry, we get that if $OPQ$ is an empty triangle, then so if $ORP$.

Thus if $P$ minimizes the angle, there can be no closer points to the line in the lower part of the same quadrant. Notice also that all points in the quadrants that are not intersected by $\ell$ are farther than $P$.

Answer 2

Thanks very much to domotorp for resolving this with an elegant symmetry based argument. Since I could not immediately see how the crucial step - the emptyness of ORP - follows from symmetry, I've fleshed that portion out here:

We need the following result, which is simple enough that I do not include a proof:

Let $A \subseteq \mathbb{R}^2$ and suppose $T : \mathbb{R}^2 \rightarrow \mathbb{R}^2$ is a 1-1 and onto transformation that preserves $\mathbb{Z}^2$, that is $T(\mathbb{Z}^2)=\mathbb{Z}^2$. Then $A$ contains a ``lattice point'' (by which we mean an element of $\mathbb{Z}^2$) if and only if $T(A)$ does.

Let us apply the above with $A=OPQ$ and $T$ denoting a reflection about the horizontal line whose $y$-coordinate is the average of the $y$-coordinates of $O$ and $P$ followed by a reflection about the vertical line whose $x$-coordinate is the average of the $x$-coordinates of $O$ and $P$. Since both reflections are lattice preserving operations and since $T(OPQ) = ORP$, it follows that $OPR$ is empty if $OPQ$ is, as claimed.

And here's a Figure:

Answer 3

I think the proof of @domotrop is not complete.

I will first present my own proof. After several revisions, it is now complete. Then I will express my concern for the proof of @domotrop, and propose a fix.

In the following picture, $O$ is the origin. Let $P$ and $Q$ be the closest points with angle $\theta_k$ and $\theta_{k+1}$. The point $-Q$ is the opposite of $Q$. Without loss of generality, we assume that $P$ is closer to $\ell$ than $Q$.

Up to a change of sign, any closer lattice point with larger angle from $\ell$ will be in the grey area, for example the blue point. Then with the help of a parallelogram, we can find the red lattice point in either of the green areas with smaller angle from $\ell$. This red point is definitely inside the circle, so it contradicts our assumption.

I think the proof of @domotrop is not complete. My concern for @domotrop's proof was the following: For example, in the picture of @Rob, $P$ minimize the angle with $\ell$ from below, but the point $(-1,-1)$ is closer with a larger angle from $\ell$. Therefore, if $\arg(n+im)$ takes value in $(-\pi,\pi]$, the points like $(-1,-1)$, which are in the lower half-space, is something that we should be careful with. That is, either there is no such point, or the opposite of the closest is indeed the next angle.

The fix consists of considering the opposite of the $\theta_{k+1}$ as in my proof. Then, in the above picture, since the green parts are empty, so is the grey part, and Q.E.D. @domotrop explained that we only needs to consider the two quadrants containing $\ell$. Then his proof is complete after repeating the same argument above $\ell$ in the first quadrant, and replacing $y$ with $x$ when constructing the parallelogram.