What fraction of n-point sets in the unit ball have diameter smaller than 1?

Question

This question is inspired by a recent talk by Matt Kahle on random geometric complexes.

Some simple notation: let $\mathcal{B} \subset \mathbb{R}^d$ be the unit ball in $d$-dimensional Euclidean space with the usual norm $\|\cdot\|$ and let $\mathcal{B}^k$ denote the $k$-fold product of this ball with itself for any positive integer $k$. For each $n \in \mathbb{N}$, define $K_n \subset \mathcal{B}^n$ as follows:

$$ K_n = \lbrace(p_1,\ldots,p_n) \in \mathcal{B}^n \text{ so that } \|p_i - p_j\| < 1 \text{ for all } 1 \leq i,j \leq n\rbrace.$$

Thus, $K_n$ consists of those $n$-tuples of points in the unit ball whose diameter is bounded above by $1$. I would like to know what fraction of $\mathcal{B}^n$ lies in $K_n$ asymptotically as $n$ increases. More precisely, let $\mu$ be the usual $d$-dimensional Lebesgue measure, and define $$\chi(n) = \frac{\mu(K_n)}{\mu(\mathcal{B})^n}.$$

How does $\chi(n)$ behave for fixed dimension $d$ as $n \to \infty$?

While an answer to this specific question would be great, I would be much more interested in some insight regarding how one should tackle such problems. The Calculus approach of setting up some integral fails horribly -- at least, I should confess that I tried $n = 2 = d$ and got hopelessly stuck with what appears to be an elliptic integral of the murderous kind -- so I expect that there is no closed formula for $\chi(n)$. But surely someone has worked out asymptotic envelopes for such a basic quantity!

Answer 1

I am certainly not the best person to answer this question, as I do not have much insight to share regarding how to approach this kind of problems. My only (fairly obvious) suggestion is to estimate the relevant quantities in any way possible. In this process, it can be very helpful to reduce the calculations to lower dimensions, and the Fubini theorem will be our friend here.$\newcommand{\norm}[1]{\lVert #1 \rVert}$$\newcommand{\abs}[1]{\lvert #1 \rvert}$$\newcommand{\suchthat}{\ : \ }$$\newcommand{\set}[1]{\left\lbrace #1 \right\rbrace}$$\newcommand{\NN}{\mathbb{N}}$$\newcommand{\RR}{\mathbb{R}}$$\newcommand{\ball}[2][0]{{B_{#2}(#1)}}$$\newcommand{\unitball}{\ball{1}}$$\newcommand{\dd}{\:\mathrm{d}}$$\newcommand{\label}[1]{\rlap{\qquad\qquad \text{#1}}}$

For this problem, my single intuition is that when one of the points $p_i$ drifts away from the centre of the unit ball, then every other point $p_j$ for $j\neq i$ cannot access a certain portion of the unit ball which sits close to $-p_i \: /\norm{p_i}$. By adding sufficiently many points, this should make the ratio $\chi(n)$ go to zero as $n$ goes to infinity. I will try to make this intuition precise in the remainder of this answer.

---

Notation and preliminaries

Fix the dimension $d$ of the ambient Euclidean space. Let $\norm{\cdot}$ denote the Euclidean norm on $\RR^d$, and $\ball[x]{r} = \set{ p\in\RR^d \suchthat \norm{p - x} \lt r }$ the open ball in $\RR^d$ with radius $r$ and centre $x$. Further, let $\mu$ be the Lebesgue measure on $\RR^d$, and $\mu_n = \mu^{\times n}$ the product measure on $\bigl(\RR^d \bigr)^{\times n}$ (i.e. Lebesgue measure on $\RR^{d n}$).

As in the statement of the question, $K_n$ will denote the following subset of $\unitball^{\times n}$: $$ K_n = \set{ (p_1, \ldots, p_n) \in \unitball^{\times n} \suchthat \forall_{i,j} \ \norm{p_i - p_j} \lt 1 } $$ We shall prove that $$ \chi(n) = \frac{\mu_n(K_n)}{\mu_n \bigl( \unitball^{\times n} \bigr)} = \frac{\mu_n(K_n)}{\mu\bigl(\unitball\bigr)^n} $$ converges to $0$ as $n\to\infty$. In fact, I will give (fairly coarse) upper and lower bounds for $\chi(n)$. Nevertheless, I am sure one can give much stricter bounds for $\chi(n)$ and perhaps even describe its asymptotic behaviour.

---

Upper bound for $\chi(n)$

Fix a positive integer $n$. Define $$ X_n = \set{ (p_1, \ldots, p_n)\in K_n \suchthat \forall_i \ \norm{p_i} \lt 1/2 } $$ (the choice of the number $1/2$ here is mostly arbitrary) and $Y_n = K_n\setminus X_n$ to be the complement of $X_n$ in $K_n$. The set $X_n$ is contained in $\ball{1/2}^{\times n}$ and thus $$ \mu_n(X_n) \leq \mu_n\bigl(\ball{1/2}^{\times n}\bigr) = \mu\bigl(\ball{1/2}\bigr)^n $$ Now define for each $i\in\set{1, \ldots, n}$ the set $$ Z_{n,i} = \set{ (p_1, \ldots, p_n)\in K_n \suchthat \norm{p_i} \geq 1/2 } $$ It is easy to check that $$ Y_n = \bigcup_{i=1}^n Z_{n,i} $$ Moreover, by permuting the first and $i$-th points (which gives a measure preserving self-bijection of $K_n$), we see that $\mu_n(Z_{n,i}) = \mu_n(Z_{n,1})$ for all $i\in\set{1, \ldots, n}$. It follows that $$ \mu_n(Y_n) \leq n \cdot \mu_n(Z_{n,1}) $$ and therefore $$ \mu_n(K_n) = \mu_n(X_n) + \mu_n(Y_n) \leq \mu\bigl(\ball{1/2}\bigr)^n + n\cdot \mu_n(Z_{n,1}) \label{(A)} $$

Now we perform a crude estimation of the volume of $Z_{n,1}$. The Fubini theorem entails $$ \mu_n(Z_{n,1}) = \int_{\unitball\setminus\ball{1/2}} \mu_{n-1}(P_x) \dd \mu(x) $$ where $P_x \subset K_{n-1}$ is the following cross-section of $Z_{n,1}$, for each $x\in\unitball\setminus\ball{1/2}$: $$ P_x = \set{ (p_1, \ldots, p_{n-1}) \in \bigl(\RR^d \bigr)^{\times (n-1)} \suchthat (x, p_1, \ldots, p_{n-1}) \in K_n } $$

Lemma: For each $x\in\unitball\setminus\ball{1/2}$, the inequality $\mu_{n-1}(P_x) \leq \mu\bigl(\unitball\cap\ball[1/2,0,\ldots,0]{1}\bigr)^{n-1}$ holds.

I will present a proof of the lemma at the end of this answer. We now apply the estimate in the lemma to the preceding integral expression for $\mu_n(Z_{n,1})$ to obtain: $$ \mu(Z_{n,1}) \leq \mu\bigl( \unitball \bigr) \cdot \mu\bigl( \unitball\cap\ball[1/2,0,\ldots,0]{1} \bigr)^{n-1} $$ Putting this together with estimate (A): $$ \mu_n(K_n) \leq \mu\bigl(\ball{1/2}\bigr)^n + n\cdot \mu\bigl( \unitball \bigr) \cdot \mu\bigl(\unitball\cap\ball[1/2,0,\ldots,0]{1}\bigr)^{n-1} $$ and further using the fact that $\ball{1/2} \subset \unitball\cap\ball[1/2,0,\ldots,0]{1}$, we simplify $$ \mu_n(K_n) \leq (n+1) \cdot \mu\bigl( \unitball \bigr) \cdot \mu\bigl(\unitball\cap\ball[1/2,0,\ldots,0]{1}\bigr)^{n-1} $$ Consequently, we obtain an upper bound for $\chi(n)$:

$$ \chi(n) \leq (n+1) \left( \frac{\mu\bigl(\unitball\cap\ball[1/2,0,\ldots,0]{1}\bigr)}{\mu\bigl(\unitball\bigr)} \right)^{n-1} = (n+1) \rho^{n-1} $$

where $0 \lt \rho \lt 1$. Note that $\rho$ depends only on $d$. In particular, $\chi(n)$ converges to zero as $n\to\infty$.

---

Lower bound for $\chi(n)$

It is very easy to give a crude lower bound for $\chi(n)$. Simply observe that $X_n \subset K_n$, and that $X_n = \ball{1/2}^{\times n}$ (here we do require the choice of $1/2$ in the definition of $X_n$). Therefore, $$ \mu_n(K_n) \geq \mu_n(X_n) = \mu\bigl(\ball{1/2}\bigr)^n $$ and so

$$ \chi(n) \geq \left( \frac{\mu\bigl(\ball{1/2}\bigr)}{\mu\bigl(\ball{1}\bigr)} \right)^n = 2^{-dn} $$

---

Proof of the lemma

We make use of the rotational symmetry of $Z_{n,1}$. Choose a rotation on $\RR^d$ which takes the point $x$ to the point $(\norm{x},0,\ldots,0)$ on the first axis. Applying that rotation componentwise gives a measure preserving bijection between $P_x$ and $P_{(\norm{x},0,\ldots,0)}$, and we see that $$ \mu_{n-1}(P_x) = \mu_{n-1}\bigl( P_{(\norm{x},0,\ldots,0)} \bigr) \label{(1)} $$

On the other hand, it is straightforward to check that $$ P_x = \set{ (p_1, \ldots, p_{n-1}) \in K_{n-1} \suchthat \forall_i \ \norm{p_i - x} \lt 1 } $$ and it follows that $$ P_x \subset \bigl(\unitball\cap\ball[x]{1}\bigr)^{\times (n-1)} \label{(2)} $$

Claim: For $0\leq s\leq t$, the following inclusion holds: $$ \unitball\cap\ball[t,0,\ldots,0]{1} \subset \unitball\cap\ball[s,0,\ldots,0]{1} \label{(3)} $$

Proof of claim:

• For $a\in\RR$, we have $\abs{a-s} \leq \max\set{ \abs{a-t}, \abs{a} }$: either $a \lt s$ which implies $\abs{a-s} \leq \abs{a-t}$, or $a\geq s$ which implies $\abs{a-s}\leq \abs{a}$.
• Thus, for any $y\in\RR^d$ we have $\abs{y_1-s} \leq \max\set{ \abs{y_1-t}, \abs{y_1} }$ which by a simple calculation implies $\norm{y-(s,0,\ldots,0)} \leq \max\set{ \norm{y-(t,0,\ldots,0)}, \norm{y} }$.

End of proof.

The inclusions (2) and (3) prove $$ P_{(t,0,\ldots,0)} \subset \bigl(\unitball\cap\ball[t,0,\ldots,0]{1}\bigr)^{\times (n-1)} \subset \bigl(\unitball\cap\ball[1/2,0,\ldots,0]{1}\bigr)^{\times (n-1)} $$ for $1/2 \leq t \lt 1$. Using (1), we conclude that for each $x\in\unitball\setminus\ball{1/2}$ $$ \mu_{n-1}(P_x) = \mu_{n-1}\bigl( P_{(\norm{x},0,\ldots,0)} \bigr) \leq \mu_{n-1}\Bigl(\bigl(\unitball\cap\ball[1/2,0,\ldots,0]{1}\bigr)^{\times (n-1)}\Bigr) $$ and so $\mu_{n-1}(P_x) \leq \mu\bigl(\unitball\cap\ball[1/2,0,\ldots,0]{1}\bigr)^{n-1}$ as desired.

Answer 2

I'm going to show that, for any $x>2^{-d}$, this is $O(x^{n})$. By Ricardo's lower bound, this is tight.

Given a set of $n$ points of diameter at most $1$, take all the points you get from those points by rounding the coordinates up or down to multiples of $\epsilon$. This new set of points will contain the old set of points in its convex hull, and since the new set of points will be of a distance no more than $\sqrt{d}\epsilon$ from the old set of points, will have a diameter at most $1+2\sqrt{d}\epsilon$. Thus each configuration of points of diameter at most $1$ in a sphere of radius $1$ is contained in the convex hull of some configuration of $\epsilon$-lattice points of diameter at most $1+2\sqrt{d}\epsilon$ in a sphere of radius $1+\sqrt{d}\epsilon$. Let $N$ be the (finite) number of such configurations of lattice points. Then since the sphere has the greatest volume of any convex body with a given diameter, the convex hulls each take up at most $(1+2\sqrt{d} \epsilon)^d/2^d$ of the volume of the sphere, so landing in any hull has probability

\[ N \left(\frac{ 1 + 2 \sqrt{d} \epsilon}{2}\right)^{dn} \]

If we let $\epsilon$ go to $0$ we have the desired result.

To be more specific, we can set $\epsilon = n^{-1/(d+1)}$, and get the upper bound

\[\ln \left(2^{nd} \chi(n)\right) = O\left( n^{d/(d+1)} \right) \]

using the trivial upper bound $N < 2^{O(\epsilon^{-d} )}$

Answer 3

A quick proof sketch that the ratio goes to 0: Let $a$ and $b$ be points in the unit ball of distance 2. (The existence of such does not hold in an arbitrary metric space!) As we add more and more points to our set in an i.i.d. manner, we will with probability 1 eventually find points $x$ and $y$ with $d(x,a)< 1/2$ and $d(y,b)< 1/2$. Then $d(x,y)>1$ or else $$ d(a,b)\le d(a,x)+d(x,y)+d(y,b) < 1/2 + 1 + 1/2 = 2 $$ Finally, similarly to how the Strong Law of Large Numbers implies the Weak Law of Large Numbers, this gives that our ratio goes to 0.