Consider we have four points like this: There are 6 distinct pairs of points on this grid, but I am only interested in the pairs of points that are separated by a minimum distance. Therefore I want 4 pairs, since distance between $A,D$ and $C,B$ is $2\sqrt2$, and the remaining distances are 2.
Now consider this:
The actual distances are not important but the smallest distance is a horizontal or vertical distance between two adjacent points, i.e.: $$d(A,B)=d(B,E)=d(E,F)=d(A,C) $$ etc. All the points are symmetrically put onto the grid ( figure obviously not in scale). This time the number of pairs that are at the smallest distance from each other is 24.
Last example (There are 52 such distinct pairs here).
Question: Given $n=2^k$ points distributed symmetrically where the horizontal and vertical distances between adjacent points are the same, is there a closed formula for finding a total number of distinct pairs of points which are at the minimum distance from each other.
Edit:
Case of 8 points is ambiguous as it takes totally different shape. For 32 points as shown in last example we take 1 by 1 squares off the outer-most edges. For $2^7=128$ we would take 2×2 such squares i.e.:
Then for $2^9=512$ we would take of 4×4 such square etc.
Best Answer
It is easiest to consider the general case, of not just a power of $2$, but of a square of $l^2$ points. We are basically counting how many horizontal and vertical lines we can draw between points. Looking only at vertical lines, we see there are $l-1$ lines for each column of $l$ points, of which there are $l$. The same argument is true for the horizontal lines. So we have $l(l-1)+l(l-1)=2l(l-1)$ lines, and therefore 'minimum distance' point pairs.
So in the particular case of even $k=2m$, we have $2^{2m}=(2^m)^2$ points, so that our formula gives $2*2^m(2^m-1)=2^{m+1}(2^m-1)$ pairs
For odd $k=2m+1$, note that there are $2^{2m+1}$ points already laid down, and $4(2^{m-2})^2$ points that would be in the corners. Then we form a square by putting the corner points back, with $2^{2m+1}+4(2^{m-2})^2=(3*2^{m-1})^2$ points. This square has, by our formula, $2*3*2^{m-1}(3*2^{m-1}-1)=9*2^{2m-1}-3*2^m$ pairs. Two things left to consider: how many of those pairs were inside our corner squares, and how many of those pairs are connecting our corner squares to 'actual' points. The corner squares have, by our formula, $2*2^{m-2}(2^{m-2}-1)=2^{2m-3}-2^{m-1}$ pairs inside each of them. And finally, for each corner square, we have one row and one column of $2^{m-2}$ connecting lines / point pairs.
So, for $k=2m+1$, we have $9*2^{2m-1}-3*2^m-4(2^{2m-3}-2^{m-1})-2*4(2^{m-2})=2^m(2^{m+2}-3)$ minimum distance point pairs!
(I have included the below as a special proof of the even case, because I liked the recursiony-ness and couldn't bring myself to delete it haha)
For the square case, i.e. even $k=2m$, $n=2^{2m}$, we have the following recursive formula, where $f(m)$ is the number of minimum distance point pairs in a square of $2^{2m}$ points:
$f(m)=2^{m+1}+4f(m-1), \quad f(1)=4$
To see this, note that the number of points is $2^{2m}=4^m$, which is a power of 4. Given the symmetry of the set up, the square of $n$ points is comprised of 4 squares of $4^{m-1}=2^{2m-2}$ points, in each quadrant of the plane. Certainly these squares have $f(m-1)$ minimum distance point pairs each, and there are 4 of them. Finally, the 4 smaller squares each have their sides made up of $2^{m-1}=\sqrt{4^{m-1}}$ points. To connect the 4 small squares to each other, we will have to connect $2^{m-1}$ points to each other 4 times (once for top left small square to bottom left, once for top left to top right, once as bottom left to bottom right, and once for top right to bottom right). So that's $4*2^{m-1}=2^{m+1}$
Then, we get from this recursive formula, the closed form:
$f(m) = \sum\limits_{i=1}^{m} 2^{m+i} = 2^{m+1}(2^m-1)$
This can be seen by expanding out $f(m)$ with the recursive formula, and keeping track of things:
$f(m)=2^{m+1}+2^2f(m-1)=2^{m+1}+2^2(2^m+2^2f(m-2))=2^{m+1}+2^{m+2}+2^4f(m-2)=\ldots=2^{m+1}+\ldots+2^{m+m-1}+2^{2(m-1)}f(1)=2^{m+1}+\ldots+2^{2m} = 2^{m+1}(2^m-1)$
(last step using geometric series formula)