Euclidean distance bound with geometric constraints

Question

Let $S_n$ be a set of $n$ points belonging to $\mathcal{B}_d:=\{\mathbf{x}\in\mathbb{R}^d:\|\mathbf{x}\|_2\le 1\}$, where $d\ll \log(n)$. Let $s_n$ and $\ell_n$ be respectively defined as follows:

$$s_n:={n\choose 3}^{-1}\cdot\!\!\!\!\sum_{1\le i<j<k\le n}\min\left(\|\mathbf{x}_i-\mathbf{x}_j\|_2, \|\mathbf{x}_j-\mathbf{x}_k\|_2, \|\mathbf{x}_k-\mathbf{x}_i\|_2\right)~,$$

$$\ell_n:={n\choose 3}^{-1}\cdot\!\!\!\!\sum_{1\le i<j<k\le n}\max\left(\|\mathbf{x}_i-\mathbf{x}_j\|_2, \|\mathbf{x}_j-\mathbf{x}_k\|_2, \|\mathbf{x}_k-\mathbf{x}_i\|_2\right)~.$$

---

Question: How can we find a (tight if possible) lower and upper bound for the ratio $\rho_n=\frac{\ell_n}{s_n}$?

Answer 1

For the upper bound:

Take $n/2$ points arbitrarily close to $0$ and $n/2$ points arbitrarily close to 1.

Then, in $3/4$ths of the triangles, there will be a point close to $0$ and a point close to $1$, and therefore the longest edge will be close to 1. Otherwise, all 3 vertices will be at 0 (or at 1) and the longest edge is 0. Thus, $l_n \approx 3/4$.

Furthermore, in any triangle, there will be two points close to $0$ or two points close to $1$, and therefore the smallest edge will be close to $0$. Thus, $s_n \approx 0$.

Consequently, $l_n/s_n \approx \infty$.

$\\ $

For the lower bound:

Evenly divide the $n$ points among the $d$ unit vectors, $e_1,\ldots,e_d$. The distance between any two unit vectors is $\sqrt{2}$. Approximately $\left(1-\frac{1}{d^2}\right)$ of the triangles contain at least two different $e_i$'s, so $l_n \approx \sqrt{2} \left(1-\frac{1}{d^2}\right)$.

Approximately $\left(1-\frac{1}{d}\right)\left(1 - \frac{2}{d}\right)$ of the triangles contain three different $e_i$'s, and so $s_n \approx \sqrt{2}\left(1-\frac{1}{d}\right)\left(1 - \frac{2}{d}\right)$. Taking the ratio, $l_n/s_n \approx \frac{d+1}{d-2}$. This ratio heads to $1$ as $d \rightarrow \infty$.

$\\ $

PS. This can be tightened a little by noting that in the $d$-dimensional sphere, you can actually take $d+1$ equidistant points, and therefore $l_n/s_n \approx \frac{d+2}{d-1}$.

PPS. As an example, suppose that $d=20$ and $n=200$. Then, we put $200/20=10$ points at each of $e_1,\ldots,e_{20}$. Draw the first vertex at random. Draw two more vertices at random. The odds that they are at the same $e_i$ is $\approx 1/d^2=1/400$. Therefore, approximately $399/400$ of triangles will have vertices at at least two different $e_i$, and so $l_n \approx \sqrt{2} (399/400)$. When we draw three vertices at random, the odds that they are all different $e_i$ is $19/20 \cdot 18/20$ (because the second draw has to avoid the first and the third draw has to avoid the first two). Therefore, $s_n \approx \sqrt{2} (342/400)$ and $l_n / s_n \approx 399/342 = 21/18 = 7/6 = 1.1\overline{6}$. The approximations come in when we estimate the probability that a randomly drawn triangle has vertices at different $e_i$'s because once a single vertex is draw at $e_i$, there are now less vertices available there, and so the odds of repetition are slightly smaller.