Let $\square\_2=\{(x,y): 0\leq x, y\leq1\}$ be the unit square in $\mathbb{R}^2$. Take $n>1$ points $P\_1, \dots, P\_n\in\square\_2$.


Denote the distances $d\_j=\min\{\Vert P\_k-P\_j\Vert: k\neq j\}$, for $j=1,\dots, n$. 



> 
> **QUESTION.** Is it true that $d\_1^2+\cdots+d\_n^2\leq 4$? The bound is tight when $n=2$. 
> 
> 
> 



Sum of squared nearest-neighbor distances between points in a square
We shall prove the more general result: for $n\ge2$ distinct points and any positive real $a,b$, we have $D(R):=d\_1^2+\cdots+d\_n^2\le 2a^2+2b^2$, where the points $P\_j$ are now in an $a\times b$ rectangle $R$ and the distances $d\_j$ are defined as in the OP. Let us use induction on $n$. For $n=2$, the result is obvious. Suppose now that $n>2$. Without loss of generality (wlog), $R=[0,a]\times[0,b]$. "Partition" $R$ into the four $\frac a2\times \frac b2$ rectangles $R\_1:=[0,\frac a2]\times[0,\frac b2],R\_2:=[\frac a2,a]\times[0,\frac b2],
R\_3:=[0,\frac a2]\times[\frac b2,b],R\_4:=[\frac a2,a]\times[\frac b2,b]$ 


Let $n\_1,\dots,n\_4$ be the numbers of the points in the rectangles $R\_1,\dots,R\_4$, respectively. 


*Case 1*: $n\_1,\dots,n\_4\ge2$. Then, by induction, 
\begin{equation}
 d\_1^2+\cdots+d\_n^2=D(R)\le D(R\_1)+\dots+D(R\_4)\le4[2(\tfrac a2)^2+2(\tfrac b2)^2]= 2a^2+2b^2. 
\end{equation}



> 
> **Lemma 1.** Suppose that $n\_1\ge2$ and $n\_2=1$, so that there is exactly one point, say $Q$, in $R\_2$. Then 
>  \begin{equation}
>  D(R\_1)+d(Q,R\_1)^2\le a^2+b^2, 
> \end{equation}
>  where $d(Q,R\_1)$ is the shortest distance from $Q$ to the $n\_1$ points in $R\_1$. 
> 
> 
> 


*Proof:* Let $s$ be the largest abscissa of all the $n\_1$ points in $R\_1$, so that $0\le s\le\tfrac a2$. Let $(u,v):=Q$, so that $\tfrac a2\le u\le a$ and $0\le v\le\tfrac b2$. By symmetry, wlog $0\le v\le\tfrac b4$, and hence $d(Q,R\_1)^2\le(u-s)^2+(\tfrac b2-v)^2$. So, by induction, 
\begin{equation}
 D(R\_1)+d(Q,R\_1)^2\le2s^2+2(\tfrac b2)^2+(u-s)^2+(\tfrac b2-v)^2\le a^2+b^2,
\end{equation}
which proves Lemma 1. $\Box$


*Case 2: One of the $n\_j$'s is $1$, and the other $n\_j$'s are $\ge2$*. Here wlog 
$n\_1,n\_3,n\_4\ge2$ and $n\_2=1$. Then, in view of Lemma 1, 
\begin{equation}
 d\_1^2+\cdots+d\_n^2=D(R)\le D(R\_1)+d(Q,R\_1)^2+D(R\_3)+D(R\_4)\le a^2+b^2+2[2(\tfrac a2)^2+2(\tfrac b2)^2]= 2a^2+2b^2. 
\end{equation}


*Case 3: Two of the $n\_j$'s are $1$'s, and the other $n\_j$'s are $\ge2$*. Here wlog 
$n\_1,n\_3\ge2$ and $n\_2=n\_4=1$ (the "adjacent" subcase) or $n\_1,n\_4\ge2$ and $n\_2=n\_3=1$ (the "non-adjacent" subcase). 
In the "adjacent" subcase, let $Q$ be the only point in $R\_2$, and let $T$ be the only point in $R\_4$. Then, in view of Lemma 1, 
\begin{equation}
 d\_1^2+\cdots+d\_n^2=D(R)\le D(R\_1)+d(Q,R\_1)^2+D(R\_3)+d(T,R\_3)^2\le a^2+b^2+a^2+b^2= 2a^2+2b^2. 
\end{equation}
The "non-adjacent" subcase is considered quite similarly, by using an appropriate flip/symmetry. 


*Case 4: Three of the $n\_j$'s are $1$'s, and the other $n\_j$ is $\ge2$*. Here wlog 
$n\_1\ge2$ and $n\_2=n\_3=n\_4=1$. Let $Q\_2=(p,q),Q\_3=(u,v),Q\_4=(x,y)$ be the unique points in $R\_2,R\_3,R\_4$, respectively, so that $p,x\in[\tfrac a2,a]$, $v,y\in[\tfrac b2,b]$, $u\in[0,\tfrac a2]$, $q\in[0,\tfrac b2]$. 


Let $s$ and $t$ be, respectively, the largest abscissa and ordinate of all the $n\_1$ points in $R\_1$. Then  

\begin{multline}
 D(R)\le B:=D(R\_1)+d(Q\_2,S)^2+d(Q\_3,T)^2+\frac{\|Q\_4-Q\_2\|^2+\|Q\_4-Q\_3\|^2}2,
\end{multline}
where $S$ is a point (among the $n\_1$ points in $R\_1$) with the largest abscissa $s$, and $T$ is a point (among the $n\_1$ points in $R\_1$) with the largest ordinate $t$, so that $S=(s,\eta)$ for some $\eta\in[0,t]$, and $T=(\xi,t)$ for some $\xi\in[0,s]$. Of course, $d(Q\_2,S)$ is a convex function of $\eta\in[0,t]$, and so, 
\begin{equation}
 d(Q\_2,S)^2\le\max(d(Q\_2,(s,0))^2,d(Q\_2,(s,t))^2)
 =(p - s)^2 + \max(q^2, (q-t)^2). 
\end{equation}
Similarly, 
\begin{equation}
 d(Q\_3,T)^2\le
\max(u^2, (u-s)^2) + (v - t)^2. 
\end{equation}
Next,
\begin{equation}
 \|Q\_4-Q\_2\|^2+\|Q\_4-Q\_3\|^2=(x - p)^2 + (y - q)^2 + (x - u)^2 + (y - v)^2, 
\end{equation}
which is convex in $x,y$, with the maximum in $x\in[\tfrac a2,a]$ and $y\in[\tfrac b2,b]$ attained at $x=a$ and $y=b$, for any given $p\in[\tfrac a2,a]$, $v\in[\tfrac b2,b]$, $u\in[0,\tfrac a2]$, $q\in[0,\tfrac b2]$. 
Further, by induction, $D(R\_1)\le2s^2+2t^2$. Thus, 
\begin{multline}
 D(R)\le B\le B\_1:=
 2 s^2+2t^2+\max \left(q^2,(q-t)^2\right)+\max \left((u-s)^2,u^2\right) \\ 
 +(p-s)^2+(v-t)^2 \\ 
 +\tfrac{1}{2} \left((a-p)^2+(b-q)^2\right)+\tfrac{1}{2} \left((a-u)^2+(b-v)^2\right). 
\end{multline}
Clearly, $B\_1$ is convex in $p,v$, and one can see that the maximum of $B\_1$ in $p\in[\tfrac a2,a]$ and $v\in[\tfrac b2,b]$ is attained at $p=a$ and $v=b$, for any given $s\in[0,\tfrac a2]$, $t\in[0,\tfrac b2]$, $u\in[0,\tfrac a2]$, $q\in[0,\tfrac b2]$. So,
\begin{equation}
 B\_1\le B\_{21}+B\_{22}+B\_{23}, 
\end{equation}
where 
\begin{align}
 B\_{21}&:=\max \left(q^2,(q-t)^2\right)- b q+q^2/2, \\ 
 B\_{22}&:=\max \left(u^2,(u-s)^2\right)- a u+u^2/2, \\ 
 B\_{23}&:=\tfrac{1}{2} \left(3 a^2+3 b^2-4 a s-4 b t+6 \left(s^2+t^2\right)\right). 
\end{align}
Next,
\begin{equation}
 B\_{21}\le t^2,\quad B\_{22}\le s^2
\end{equation}
for $q,t\in[0,\tfrac b2]$ and $u,s\in[0,\tfrac a2]$. So, 
\begin{equation}
 D(R)\le B\le B\_1\le B\_{21}+B\_{22}+B\_{23}
 \le\tfrac{1}{2} (3 a^2 + 3 b^2) -4 (\tfrac a2 - s) s - 4 (\tfrac b2 - t) t
 \le\tfrac{1}{2} (3 a^2 + 3 b^2)\le2 a^2 + 2 b^2. 
\end{equation}


*Case 5: This case obtains from Cases 2, 3, 4 by replacing there some of the conditions of the form $n\_j=1$ by $n\_j=0$*. This case immediately follows from Cases 2, 3, 4, because now the nonnegative contributions of the single points will be replaced by $0$ --- with the only exception occurring when three of the $n\_j$'s are $0$ and hence the remaining one of the $n\_j$'s (say $n\_1$) equals $n$. Indeed, in the latter exceptional subcase, we cannot use the induction, since $n\_1=n\not<n$. The remedy in this case is to continue the "partitioning" of the smaller rectangles containing all the $n$ points until we no longer have such an exceptional situation. This process will stop. Indeed, if it never stops, then all the $n$ distinct points will get eventually contained in a singleton set, which is a contradiction. 


So far, we have consider all the cases when at least one of the $n\_j$'s is $\ge2$. Otherwise, we have $n\_j\le1$ for all $j=1,\dots,4$ and hence $n\le4$. Since $n>2$, it remains to consider the following two cases. 


*Case 6: $n=3$*. By shrinking the rectangle $R$, wlog we may assume that each side of $R$ contains at least one of the three points $P\_1,P\_2,P\_3$. By the pigeonhole principle, at least two sides of the rectangle must share one of the three points. Also, wlog none of the points $P\_1,P\_2,P\_3$ is in the interior of $R$. Indeed, if e.g. $P\_3$ is in the interior of $R$, then we can move $P\_3$ away from the line $\ell(P\_1,P\_2)$ (through $P\_1,P\_2$) in the direction perpendicular to $\ell(P\_1,P\_2)$ (till we hit the boundary of $R$), so that all the pairwise distances between the points $P\_1,P\_2,P\_3$ may only increase, and then $D(R)$ may only increase. 


So, wlog $P\_1=(0,0),P\_2=(u,b),P\_3=(a,v)$ for some $u\in[0,a]$ and $v\in[0,b]$. So, 
\begin{equation}
 D(R)\le B\_3:=\frac{P\_1P\_2^2+P\_1P\_3^2}2+\frac{P\_2P\_1^2+P\_2P\_3^2}2+\frac{P\_3P\_2^2+P\_3P\_1^2}2=
 P\_1P\_2^2+P\_1P\_3^2+P\_2P\_3^2,
\end{equation}
where $AB:=\|A-B\|$. Since $B\_3$ is convex in $u,v$, its maximum in $u\in[0,a]$ and $v\in[0,b]$ is attained when $u\in\{0,a\}$ and $v\in\{0,b\}$, and this maximum is $2a^2+2b^2$, which proves Case 6. 


*Case 7: $n=4$*. Again, by shrinking the rectangle $R$, wlog we may assume that each side of $R$ contains at least one of the four points $P\_1,P\_2,P\_3,P\_4$. Also, each of the four points is either (i) in the convex hull of the other three points or (ii) on the boundary of $R$. Indeed, otherwise wlog $P\_4$ is in the interior of $R$, but not in the convex hull of $P\_1,P\_2,P\_3$; more specifically, we may assume that the points $P\_4$ and $P\_3$ are to the opposite sides of the line $\ell(P\_1,P\_2)$. 
Then we can move $P\_4$ away from the triangle $P\_1P\_2P\_3$ in the direction perpendicular to the line $\ell(P\_1,P\_2)$ (till we hit the boundary of $R$), so that all the pairwise distances between the points $P\_1,P\_2,P\_3,P\_4$ may only increase, and then $D(R)$ may only increase. Therefore, wlog we have one the following subcases. 


*Subcase 7.1: $P\_4$ is in the convex hull of $P\_1,P\_2,P\_3$,* so that $P\_4=(1-s-t)P\_1+sP\_2+tP\_3$ for some $s,t$ such that $s,t\ge0$ and $s+t\le1$. 
Also, here, as in Case 6, wlog $P\_1=(0,0),P\_2=(u,b),P\_3=(a,v)$ for some $u\in[0,a]$ and $v\in[0,b]$. Hence
\begin{equation}
 D(R)\le B\_{71}:=P\_1P\_4^2+P\_2P\_4^2+P\_3P\_4^2+[(1-s-t)P\_4P\_1^2+s\,P\_4P\_2^2+t\,P\_4P\_3^2]\le2a^2+2b^2;
\end{equation}
the latter inequality follows easily by the convexity of $B\_{71}$ in each of the variables $u,v,(s,t)$. Thus, Subcase 7.1 is done. 


*Subcase 7.2: All the four points $P\_1,P\_2,P\_3,P\_4$ are on the boundary of $R$.* 


*Subsubcase 7.2.1: There is a bijection $\beta$ from the set of the points $\{P\_1,P\_2,P\_3,P\_4\}$ to the set of the sides of $R$ such that $P\_j\in\beta(P\_j)$ for all $j$.* So, wlog $P\_1=(s,0),P\_2=(0,t),P\_3=(u,b),P\_4=(a,v)$ for some $s,u\in[0,a]$ and $t,v\in[0,b]$. Then, similarly to the case $n=3$,  

\begin{equation}
 D(R)\le\frac{P\_1P\_2^2+P\_1P\_4^2}2+\frac{P\_2P\_1^2+P\_2P\_3^2}2
 +\frac{P\_3P\_2^2+P\_3P\_4^2}2+\frac{P\_4P\_1^2+P\_4P\_3^2}2\le2a^2+2b^2, 
\end{equation}
by convexity. 
Subcase 7.2.1 is done. 


*Subsubcase 7.2.2: One of the points $P\_1,P\_2,P\_3,P\_4$ (say $P\_1$) is shared by two sides of the rectangle $R$.* So, wlog $P\_1=(0,0)$. Suppose that one of the two sides of $R$ (say $S\_1$ and $S\_2$) sharing the point $P\_1$ contains one of the points $P\_2,P\_3,P\_4$; let us say this side is $S\_1$. Then we can move $P\_1$ slightly along the side $S\_2$ out of its position at $(0,0)$. In view of the continuity of $D(R)$ in $P\_1$, we can thus get rid of the sharing -- provided that at least one of the two sides of $R$ sharing the point $P\_1$ contains one of the points $P\_2,P\_3,P\_4$. So, wlog $P\_1=(0,0)$ and none of the two sides of $R$ sharing the point $P\_1$ contains any of the points $P\_2,P\_3,P\_4$. So, one of the sides of $R$ not sharing the point $P\_1$ contains two of the points $P\_2,P\_3,P\_4$. Therefore and by the interchangeability of the horizontal and vertical directions, wlog $P\_1=(0,0),P\_2=(u,b),P\_3=(a,v),P\_4=(a,w)$ for some $u\in[0,a]$ and $v,w\in[0,b]$ such that $v>w$. So,  

\begin{equation}
 D(R)\le P\_1P\_2^2+P\_2P\_3^2+P\_3P\_4^2+P\_4P\_1^2\le2a^2+2b^2, 
\end{equation}
again by convexity. 
Subcase 7.2.2 is done, as well as the entire proof of the bound $2a^2+2b^2$. 


