Let $n$ and $d$ be large positive integers with $n \le d^\gamma$, for some absolute constant $\gamma>0$; i.e., $n$ is at most polynomial in $d$. Let $x\_1,\ldots,x\_n,x\_{n+1}$ be drawn iid from the uniform distribution on the sphere $S\_{d-1}(\sqrt{d})$ of radius $\sqrt{d}$ in $\mathbb R^d$, and consider the random variable $\Delta(n,d) := \min\_{1 \le i \le n}\|x\_{n+1}-x\_i\|$. Let $\alpha \in (0,1)$.



> 
> **Question.** *What is a good upper-bound for $\Delta(n,d)$, perhaps valid with probability at least $\alpha$ ?*
> 
> 
> 


One would expect $\Delta(n,d)=o(\sqrt{d})$, i.e., $\Delta(n,d)/\sqrt{d} \to 0$ in the limit $d \to \infty$ w.h.p.


A crude (and possibly very bad) estimate
----------------------------------------


Because the sphere $S\_{d-1}(\sqrt{d})$ can be covered with $N\_d(\varepsilon) \le (\sqrt{d}/\varepsilon)^d$ (euclidean) balls of radius $\varepsilon$, it is clear that $\Delta(n,d) \le \sqrt{d}/n^{1/d} \asymp \sqrt{d}$ with probability tending to $1$ with $d$. However, this bound is very far from my target, namely $o(\sqrt{d})$.



For $x_1,...,x_n$ iid random on sphere of radius $\sqrt{d}$ in $R^d$, what is a good upper-bound on min distance of $x_{n}$ from the other $x_i$'s?
$\newcommand{\De}{\Delta}\newcommand{\R}{\mathbb R}\newcommand{\ga}{\gamma}\newcommand{\Ga}{\Gamma}$This is to provide a detalization on Will Sawin's comment. Specifically, let us show that the best upper bound on $\De:=\De(n,d)$ is $\sim\sqrt{2d}$ (as $d\to\infty$ and $d^\ga\ge n\to\infty$).


Indeed, for real $m>0$, let
\begin{equation\*}
 p:=P(\De>m)=P(\min\_{1\le i\le n}\|x\_{n+1}-x\_i\|>m). \tag{1}\label{1}
\end{equation\*}
We want to choose $m$ so that $p$ be bounded away from $0$. In other words, writing
\begin{equation\*}
 p=e^{-u},
\end{equation\*}
we want to choose $m$ so that
$$u=O(1).$$


Let $e\_1:=(1,0,\dots,0)\in\R^d$. Note that $x\_1/\sqrt d$ equals $G/\|G\|$ in distribution, where $G=(G\_1,\dots,G\_n)$ is a standard Gaussian random vector in $\R^d$.
So, by spherical symmetry,
\begin{equation\*}
\begin{aligned}
 e^{-u}=p&=P(\min\_{1\le i\le n}\|\sqrt d\, e\_1-x\_i\|>m) \\ 
 &=P(\|\sqrt d\, e\_1-x\_1\|>m)^n \\ 
 &=P\Big(1-\frac{e\_1\cdot x\_1}{\sqrt d}>\frac{m^2}{2d}\Big)^n \\ 
 &=P\Big(1-\frac{G\_1}{\|G\|}>\frac{m^2}{2d}\Big)^n \\ 
\end{aligned}
\end{equation\*}
where $e\_1:=(1,0,\dots,0)\in\R^d$ and $\cdot$ is the dot product. So,
\begin{equation\*}
 P\Big(1-\frac{G\_1}{\|G\|}>\frac{m^2}{2d}\Big)=e^{-u/n}=1-(1+o(1))\frac un. \tag{2}\label{2}
\end{equation\*}
If $m\ge\sqrt{2d}$, then $P\big(1-\frac{G\_1}{\|G\|}>\frac{m^2}{2d}\big)\le P(G\_1<0)=1/2$, which contradicts \eqref{2} for all large enough $n$. So, without loss of generality,
\begin{equation\*}
0< m<\sqrt{2d} \tag{3}\label{3}
\end{equation\*}
and hence
\begin{equation\*}
\begin{aligned}
 &P\Big(1-\frac{G\_1}{\|G\|}>\frac{m^2}{2d}\Big) \\ 
 &=P\Big(G\_1<0,1-\frac{G\_1}{\|G\|}>\frac{m^2}{2d}\Big) \\ &+P\Big(G\_1>0,1-\frac{G\_1}{\|G\|}>\frac{m^2}{2d}\Big) \\ 
 &=P(G\_1<0)+P\Big(G\_1>0,1-\frac{|G\_1|}{\|G\|}>\frac{m^2}{2d}\Big) \\ 
 & =\frac12+\frac12\,P\Big(1-\frac{|G\_1|}{\|G\|}>\frac{m^2}{2d}\Big). 
\end{aligned}
\end{equation\*}
So,
\begin{equation\*}
 P\Big(1-\frac{G\_1}{\|G\|}>\frac{m^2}{2d}\Big)=\frac12+\frac12\,P(Y>z), 
\end{equation\*}
where
\begin{equation\*}
 Y:=1-\frac{G\_1^2}{\|G\|^2},\quad z:=1-\Big(1-\frac{m^2}{2d}\Big)^2. \tag{4}\label{4}
\end{equation\*}
So, in view of \eqref{2}, $P(Y>z)=1-(2+o(1))\frac un$, that is,  

\begin{equation\*}
 P(Y\le z)\sim\frac{2u}n\ge\frac{2u}{d^\ga}. \tag{5}\label{5}
\end{equation\*}
Next, $Y$ has the beta distribution with parameters $\frac{d-1}2,\frac12$. So, for
\begin{equation\*}
 c\_d:=\frac{\Ga(d/2)}{\Ga(1/2)\Ga((d-1)/2)}\sim\sqrt{\frac{d}{2\pi}}, \tag{6}\label{6}
\end{equation\*}
we have
\begin{equation\*}
\begin{aligned}
 P(Y\le z)&=c\_d \int\_0^z y^{(d-3)/2}(1-y)^{-1/2}\,dy \\ 
&\le c\_d z^{(d-3)/2}\int\_0^z (1-y)^{-1/2}\,dy \\ 
&\le 2c\_d z^{(d-1)/2}. 
\end{aligned}
\tag{7}\label{7}
\end{equation\*}
By \eqref{4}, \eqref{3}, \eqref{7}, \eqref{5}, and \eqref{6},
\begin{equation\*}
 1\ge z^{(d-1)/2}\gtrsim\frac{u\sqrt{2\pi}}{d^{\ga+1/2}},
\end{equation\*}
which implies $z\to1$.


Thus, by \eqref{4}, $m\sim\sqrt{2d}$, as claimed.


