# Precise estimate for probability an $n$-point set has diameter smaller than $1$

This question was inspired by an earlier question that I answered but would like a more precise bound for.

Consider random points $$x_1, \dots, x_n$$ in the unit ball in $$\mathbb R^d$$, uniformly and independently distributed. What is the probability that they form a set of diameter at most $$1$$?

A lower bound, noted by Ricardo Andrade, comes from observing that $$x_1,\dots,x_n$$ will always form a set of diameter at most $$1$$ if they all lie in the ball of radius $$1/2$$ centered at the origin, so the probability is at least $$1/2^{nd}$$. I showed this was correct up to a subexponential factor. What is that factor?

In other words, let

$$f(n) = \frac{ \left| \left\{ (x_1,\dots,x_n) \in (\mathbb R^d)^n \mid |x_i|<1, |x_i-x_j| <1 \right\} \right|}{ \left(\left| \left\{ x \in \mathbb R^d \mid |x|<1/2 \right\}\right|\right)^n }$$

What are the asymptotics of $$f(n)$$? I gave an upper bound of $$e^{ O (n^{d/(d+1)})}$$, and I know how to give a lower bound proportional to $$n^d$$, but these are obviously quite far apart.

It should be possible to replace ball of radius $$1$$ with any other reasonably large set and change the asymptotics by only a constant.

• You have two variables, $n$ and $d$. Are you interested in knowing what happens if you fix $d$ and let $n$ increase? If you want both $n$ and $d$ to increase, how quickly relative to each other? – Douglas Zare Apr 5 '16 at 22:51
• @DouglasZare I'm primarily interested in the case when $d$ is fixed and $n$ is increasing. I also expect this to be the easiest case. – Will Sawin Apr 6 '16 at 0:24
• @WillSawin: Should $<1$ in the denominator be $<1/2$? – D_809 Dec 24 '19 at 13:01
• @D_809 Yes, sounds right. – Will Sawin Dec 24 '19 at 16:59

• Igor, I don't see how this result applies here. Will is asking about the probability in Theorem 1.1 with $t=n^{\frac{4}{d+3}}$ while $t$ is fixed there as $n\to\infty$. – D_809 Dec 24 '19 at 20:18