Upper bounding the minimum distance between points (in high dimensional space)

98 Views Asked by At

Given $m>n$ points $p_i\in\mathbb{R}^n$, how to upper-bound $\min_{i,j}|p_i-p_j|$ across all possible sets of points, where $|\cdot|$ denotes Euclidean distance?

I think we can make two simplifying assumptions (reducing to point distributions that maximize the distance between points). First, all points have the same distance from the origin, i.e. $\rho=|p_i|=\max_j|p_j|$ for all $i\in[m]$. Furthermore, the points are equally spaced out on the $n$-sphere of radius $\rho$.

For the case of small $n$ and large $m$, research has been done from the perspective of spherical codes. I'm instead interested in high dimensional cases with large $n$ and any special $m>n$.

Given the two simplifications, for the case of $m=2n$, we may assume two points $p_{k_1},p_{k_2}$ lie on the axis of each dimension $k$, pointing in opposite directions, i.e. $p_{k_1}=\rho\cdot\textbf{e}_{k},p_{k_2}=-\rho\cdot\textbf{e}_{k}$ for $k\in[n]$. That is, $p_{2k}=\rho\cdot\textbf{e}_{k}$ and $p_{2k-1}=-\rho\cdot\textbf{e}_{k}$ for $k\in[n]$. In this case, $\min_{i,j}|p_i-p_j| = |\rho\cdot\textbf{e}_{k}-\rho\cdot\textbf{e}_{k'}| = \sqrt{\rho^2+(-\rho)^2} = \rho\sqrt{2}$, for any distinct $k,k'\in[n]$. If the general case has no simple formula, how about extending to $m=tn$ for some integers $t>2$?