What is the minimum distance between vertices on an integer grid with the form $(m(m+2), 0)p + (m, 1)q$?

Question

Suppose, for given $m > 0$, we have a set of points of the form $v = (m(m+2), 0)p + (m, 1)q$, with $p, q, m$ integers. What is the minimum distance between two (distinct ones) of them?

Here is the square distance between any point and the origin: $|v|^2 = (pm^2 + 2pm + qm)^2 + q^2,$

we need to find the $p, q$ that minimizes this distance given $m > 0$.

In practice it is easy enough to check a few points, and find the optimum by trial and error, but I am wondering if there is a closed form solution.

Background: this came up while working on this question: How many colors is necessary so that a rectangle always covers no color more than once?. See the second last conjecture.

(Note: I am not sure if there are more appropriate tags.)

Answer 1

Instead of minimizing the distance (which would involve a square root), we can minimize its square and deal just with integers. Let $v(p,q)$ be the squared distance:

$$v(p,q)=(pm^2 + 2pm + qm)^2 + q^2$$

Since the sum of two squares values cannot be smaller than either of them and we have $v(0,1)=m^2+1$, any smaller distance would need to satisfy two necessary conditions (remembering that we are dealing with integers and $(m+1)^2>m^2+1$):

• $|pm^2 + 2pm + qm| \leq m$, which can also be simplified as $|pm+2p+q|\leq 1$
• $|q| \leq m$ (the same reasoning applied to the second term)

Using the general inequality $|A-B|\leq |A| + |B|$ allows us to combine these two inequalities into ones: $$|p(m+2)|\leq |pm+2p+q)| + |q| \leq (m+1)$$ which immediately implies $p=0$. This simplifies our expression for the distance into $v(0,q)=q^2(m^2+1)$ and the it is clear that the smallest non-zero value occurs for $q=\pm 1$.

Thus, the smallest non-zero value of $v(p,q)$ is indeed $(m^2+1)$.

Answer 2

Since $v^2$ is a sum of squares of integers, and it's not $0$, then it must be $1$ (if we can find such a solution). There are two choices:

Case 1: $q=0$ and $pm^2+2pm+qm=\pm1$. I can easily guess a solution for $pm^2+2pm=-1$: $p=1$ and $m=-1$

Case 2: $q=\pm 1$ and $pm^2+2pm+qm=0$. Same $p$ and $m$ as above also verify this case.

Answer 3

A sample plot below for $m=3$.

It turns out to be the same final grid as $(p',q) \to (mq,(m+2)p'+q)$

It then turns out that the closest two points (tied with many others) are:

• $(0,0) \to (0,0)$
• $(0,1) \to (m,1)$

So the minimum distance is $\sqrt{m^2+1}$