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

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!

• @Vidit: Thanks for accepting my answer. I would also like to direct everyone's attention to Will Sawin's answer below which gives very sharp asymptotic bounds for $\chi(n)$. – Ricardo Andrade Jun 19 '13 at 11:52

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. • Thanks for this, Ricardo. I am still parsing your answer, I'll get back to you once I understand this. – Vidit Nanda Jun 17 '13 at 15:36 • @Vidit: You are welcome. Please let me know if there are any problems. – Ricardo Andrade Jun 18 '13 at 23:33 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} )} • PS: this is a really pretty argument, I hope more people +1 it. – Vidit Nanda Jun 19 '13 at 12:51 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.