Maximum number of points you can put on grid $ n\times m$ with no equidistant?

Question

Assume we have a grid of $n\times m$ points. and the distance between two rows or two columns is 1 ( unit ). I have a couple of questions related to this grid:-

1. What is the list of possible length between points?

2. What is the maximum number of points that they have no equidistant between any pairs?

   • For question number one , I know if we have we have $n \times m$ so we have length of size $1,2 \dots \mbox{max}\{m,n\}$ in addiction of this we have $\sqrt{2},\sqrt{5}$ and some others. but I am interested in all of these distance.
   • For question number 2 intuitionally it look like for $n\times n$ case we the maximum point with no equidistant is n.

I have feeling this has been studied in some books but I am not sure where or how to answer the general case of this problem. any hints and/or answers would be appreciated.

There are solution of $5 \times 4$ for example this is two of the solution of it ( there is 5 non-equidistant points):-

Reference:- I found this problem from the twitter and you can find it here.

Answer 1

The squared lengths are of the form $i^2 + j^2$ for $i \in [0,n]$ and $j \in [0,m]$; assuming (with no loss of generality) that $n \ge m$, we can consider only the cases where $i \ge j$, of which there are $$(m+1)(n-m)+\frac{1}{2}(m+1)(m+2)=\frac{1}{2}(m+1)\left(m+2(n-m+1)\right).$$ On the other hand, placing $k$ points creates $k(k+1)/2$ pairs, so if all of these pairs must have distinct distances, $$ k(k+1) \le (m+1)\left(m + 2(n-m+1)\right). $$ So for $n=m$ this implies $k \le m+1$, and more generally $$ k \le \sqrt{(m+1)\left(m + 2(n-m+1)\right)}. $$

A tighter bound, at least in the limit of large $n$, will come from improving the estimate of the number of distinct distances on the grid. We know that the number of positive integers less than $2n^2+1$ that are the sum of two squares is $O\left(n^2 / \sqrt{\log n}\right)$ (cf. the Landau-Ramanujan constant); i.e., it grows more slowly than $n^2$. For $n=m$, then, the growth rate of $k$ is necessarily in $O\left(n / \sqrt[4]{\log n}\right)$. So $k=n$ is not correct: in fact, $k/n \rightarrow 0$ for large $n$.