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? 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})$.
 A: $\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.
