# Distance from lattice point to line

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.

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

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

• 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. – Ingix Oct 22 '18 at 21:45
• You are right. Let me fix that. – Andrei Oct 22 '18 at 21:55

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.

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.