I've been thinking about proving some bounds for the OEIS sequence A319476:

$a(n)$ is the minimum number of distinct distances between $n$ non-attacking rooks on an $n \times n$ chessboard.

I'd like to find references to the minimum number of distinct distances between $n$ points in $\mathbb Z^2$. Call this minimum number of distances $a(n)$.

The minimum number of distinct distances in $\mathbb R^2$ is given by OEIS sequence A186704.


For example, $a(3) = 2$ because if there were only one distinct distance, this would mean there's a way to place the vertices of an equilateral triangle on $\mathbb Z^2$. We can, however, place an isosceles triangle like $(0, 0), (0, 1),$ and $(1, 0)$ on the grid, which has two distinct pairwise distances, namely $1$ and $\sqrt 2$.

Similarly, $a(4) = 2$ with vertices $(0, 0), (0, 1), (1, 0)$ and $(1, 1)$ and pairwise distances of $1$ and $\sqrt 2$.

  • $\begingroup$ $r(5)=2$ as can be seen in a regular pentagon. $\endgroup$ – Gerry Myerson Nov 2 '18 at 21:54
  • $\begingroup$ Thanks, Gerry! I found that the number of distinct distances in the plane is given by $A186704(n)$, so I rephrased the question to ask just about points on $\mathbb Z^2$. $\endgroup$ – Peter Kagey Nov 2 '18 at 21:55
  • 2
    $\begingroup$ You might be interested in the book by Garibaldi, Iosevich, and Senger, The Erdos Distance Problem, in the Student Mathematical Library series of the American Math Society. Although on skimming it I didn't see any mention of the ${\bf Z}^2$ question, and it's mainly concerned with asymptotics rather than exact numbers. $\endgroup$ – Gerry Myerson Nov 2 '18 at 22:16
  • $\begingroup$ Have you determined the values of $a(n)$ for small $n$, say up to 10? $\endgroup$ – Servaes Nov 2 '18 at 23:35
  • $\begingroup$ @Servaes, I haven't. I have bounds for them based on some brute-force computations, but I can't prove that those bounds are correct. $\endgroup$ – Peter Kagey Jan 16 at 1:34

Your Answer

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

Browse other questions tagged or ask your own question.