2
$\begingroup$

What is the smallest $d> 0$ such that for any line in the plane not parallel to the $x$- or $y$-axis, the distance of some lattice point to the line does not exceed $d$?

If the line has slope $1$ and passes through point $(1/2,0)$, it has distance at least $\frac{1}{2\sqrt{2}}$ from any lattice point. This might also be the minimum $d$. There's of course an explicit formula for the distance from a line to any point, but here we have infinitely many points, which can generate infinitely many distances, for example if the slope is irrational.

$\endgroup$
  • 1
    $\begingroup$ Isn't it rather $\frac{\sqrt 2}2$? $\endgroup$ – Berci Oct 22 '18 at 21:39
  • $\begingroup$ $\sqrt{(1/4)^2+(1/4)^2}=\sqrt{2}/4=\frac{1}{2\sqrt{2}}$ $\endgroup$ – Andrei Oct 22 '18 at 22:04
  • $\begingroup$ Ah, ok. I took the wrong line.. : ) $\endgroup$ – Berci Oct 22 '18 at 22:36
2
$\begingroup$

The minimum $d$ is $\frac{1}{2\sqrt2}$, in the case you showed. The way to prove it is relatively easy. Choose four neighboring lattice points $(x_0,y_0)$, $(x_0+1,y_0)$, $(x_0,y_0+1)$, $(x_0+1,y_0+1)$ such as the line $y=ax+b$ goes in between. The distance from such a lattice point to the line can be written in terms of Pythagoras' theorem. We know the $x$ and $y$ components in the triangles formed by the lattice points, and the line. Along $x$ you have either $\{x\}$ or $\{1-x\}$ and along $y$ you have either $\{ax+b\}$ or $1-\{ax+b\}$ . Here the $\{\}$ notation means the fractional part.

We can write the areas of one of these triangles as either $0.5\{x\}\{ax+b\}$ or $0.5d\sqrt{\{x\}^2+\{y\}^2}$. From here $$d=\frac{\{x\}\{ax+b\}}{\sqrt{\{x\}^2+\{y\}^2}}$$ and similar combinations, with $\{x\}$ replaced with $1-\{x\}$ and/or $\{ax+b\}$ replaced with $1-\{ax+b\}$

Since we want to find the maximum distance for any line, it means that the $x$ and $y$ component are independent. The maximum value is reached when $\{x\}=1/2$ and $\{ax+b\}=1/2$. The minimum distance is then $$d=\frac{\frac{1}{2}\frac12}{\sqrt{\left(\frac{1}{2}\right)^2+\left(\frac{1}{2}\right)^2}}=\frac{1}{2\sqrt2}$$

$\endgroup$
  • $\begingroup$ That does not conform with the OP's conjecture $\frac1{2\sqrt{2}}$, which is smaller (so contradicts your claim to minimalness). I assume just a calculation problem. $\endgroup$ – Ingix Oct 22 '18 at 21:45
  • $\begingroup$ You are right. Let me fix that. $\endgroup$ – Andrei Oct 22 '18 at 21:55
0
$\begingroup$

I'm giving an additional solution that ultimately uses the same kind of idea, but is to me a little clearer on all the min/maxing of distances.

So we have a line $y=ax+b$ with $a \neq 0$. If the slope $a$ is negative, we can replace it with $y=-ax+b$, which corresponds to mirroring on the $y$-axis, which is a bijection between lattice points, so if we can prove it for positive $a$, it follows for all $a$.

Similiarly, if $a > 1$, we can replace it with $y=\frac1a x-\frac{b}a$, which corresponds to mirroring on the $y=x$ axis, which is also a bijection between lattice points.

So, for symmetry reasons, we need to consider $0 < a \le 1 $ only. Since $a>0$, our line is intersecting any parallel to the $x$-axis.

line intersects y=integer line

The line $y=ax+b$ is red, the lattice of integer points in the plane is partially shown. The distance of 2 such lattice points to the line is shown in blue, the angle under which the line hits the parallel to the $x$-axis is $\alpha$. Since $0 < a = \tan(\alpha) \le 1$ we have $0 < \alpha \le 45°$.

The intersection point of the red line with the parallel to the $x$-axis is somewhere between the 2 lattice points, the $x$ distances are $l_1$ and $l_2$ with $l_1+l_2=1$ (this corresponds to $\{x\}$ and $\{1-x\}$ in Andrei's solution).

For the distance $d_1$ of the left lattice point to the line we get $d_1=l_1\sin(\alpha)$ and similiarly $d_2=l_2\sin(\alpha)$.

Now we know that at least one of $l_1,l_2$ is $\le \frac12$ and from $0 < \alpha \le 45°$ it follows that $\sin(\alpha) \le \frac1{\sqrt{2}}$, so

$$\min(d_1,d_2) \le \frac12 \frac1{\sqrt{2}} = \frac1{2\sqrt{2}}$$

which shows that $\frac1{2\sqrt{2}}$ is indeeded the highest possible value for the minimal distance.

$\endgroup$

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.