13
$\begingroup$

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}$.

$\endgroup$
9
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Brilliant - thanks a lot. It was not immediately obvious to me how the key observation (the emptyness of ORP) followed from symmetry. I've flushed this part out a bit and am now convinced. I'm going to write that flushed out version into a answer to my own question, since I cannot include things like carriage returns inside a comment. $\endgroup$ – Rob Nov 22 '14 at 19:44
  • $\begingroup$ Sorry for the previous comment. I'm now OK with your proof. $\endgroup$ – Hao Chen Nov 22 '14 at 22:50
  • $\begingroup$ Nah, I'm not. Please see my answer. $\endgroup$ – Hao Chen Nov 22 '14 at 23:36
  • $\begingroup$ I finally got my own proof complete, and propose a fix to your proof, see my revised answer. $\endgroup$ – Hao Chen Nov 23 '14 at 0:58
9
$\begingroup$

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:

Triangle $OPQ$ contains no interior lattice points when $P$ is the lattice point making the shallowest angle with $\ell$ from below.  By symmetry, in this case triangle $ORP$ also contains no interior lattice points.

$\endgroup$
  • $\begingroup$ What about the area between the parallel lines OQ and PR, with m<0 ? $\endgroup$ – Hao Chen Nov 22 '14 at 21:11
  • $\begingroup$ You mean in the lower half plane? By symmetry, $(n,m) \in \mathbb{Z}^2$ is a minimizer of the orthogonal distance to $\ell$ iff $(-n,-m)$ is. Therefore it suffices to consider the upper half plane. $\endgroup$ – Rob Nov 22 '14 at 21:16
  • $\begingroup$ In your picture, P is not the closest to l. There are closer points on the other side, for example (1, 1). By symmetry, (-1, -1) is a closer point below l with larger angle (or not depending on your meaning by angle). $\endgroup$ – Hao Chen Nov 22 '14 at 21:22
  • $\begingroup$ I'm not saying that the proof is wrong. But this is a detail that bothers me. $\endgroup$ – Hao Chen Nov 22 '14 at 21:36
  • 2
    $\begingroup$ You mean "fleshed out," not "flushed out." $\endgroup$ – KConrad Nov 23 '14 at 3:24
2
$\begingroup$

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.

enter image description here

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.

$\endgroup$
  • $\begingroup$ You are right - the correct statement should not be that the minimizer $n+im$ obeys $Arg(n+im) \in \{\theta_i,\theta_{i+1}\}$, but rather $Arg(n+im) \in \{\theta_i,\theta_{i+1},\theta_i+\pi,\theta_{i+1}+\pi\}$. But perhaps a nicer way of saying things is that the above result gives you the solution with $Arg(n+im) \in [0,\pi)$, from which a second solution $-n-im$ in $[\pi,2\pi)$ is constructed. $\endgroup$ – Rob Nov 23 '14 at 1:26
  • $\begingroup$ @Rob, indeed, but that's not my concern, I understand what you mean. $\endgroup$ – Hao Chen Nov 23 '14 at 1:29
  • $\begingroup$ @Rob, my concern is, in your argument, there might be a closer point in lower half space, whose angle is not any of the four candidates. $\endgroup$ – Hao Chen Nov 23 '14 at 1:31
  • $\begingroup$ If such a point exists, it has to have a twin in the upper half plane, where we know the proof works. The difference in angle between the point and its twin is $\pi$. $\endgroup$ – Rob Nov 23 '14 at 1:38
  • $\begingroup$ The last sentence of my proof is supposed to cover such cases, as that of the blue point. Any integer point in another quadrant has distance $>1$ from the line, so larger than, say, $(1,1)$. $\endgroup$ – domotorp Nov 23 '14 at 6:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.