Consider $m$ vectors $v\_1,\dots,v\_m$ in $\mathbb R^n$, drawn uniformly and independetly from unit sphere. It is pretty straightforward from Chebyshev inequality that 
$$
\mathrm P (\forall i\ne j \ |v\_i \cdot v\_j|\leq \varepsilon) \to 1\ \text{as} \ n \to \infty.
$$ 


But what about quantitative version of this limit, i.e. if we define 
$$
f(m, \varepsilon, \delta) = \min\{n : \mathrm P(\forall i\ne j\ |v\_i \cdot v\_j| \leq \varepsilon)\geq 1 - \delta\} 
$$


what can we say about asymptotic behavior of $f$?



Precise probability that $m$ random vectors in $n$ dimensional space are nearly-orthogonal
$\newcommand{\ep}{\varepsilon}
\newcommand{\Ga}{\Gamma}
\newcommand{\de}{\delta}$
For $\ep\in(0,1)$, let  

\begin{equation\*}
 P\_{m,n}:=P\Big(\bigcap\_{1\le i<j\le m}\{|v\_i\cdot v\_j|\le\ep\}\Big)
 =1-Q\_{m,n},
\end{equation\*}
where 
\begin{equation\*}
 Q\_{m,n}:=P\Big(\bigcup\_{1\le i<j\le m}\{|v\_i\cdot v\_j|>\ep\}\Big). 
\end{equation\*}
By [Bonferroni inequalities](https://en.wikipedia.org/wiki/Boole%27s_inequality#Bonferroni_inequalities),
\begin{equation\*}
 Mp\ge Q\_{m,n}\ge Mp-R/2,
\end{equation\*}
where 
\begin{equation\*}
 p:=P(|v\_1\cdot v\_2|>\ep), 
\end{equation\*}
\begin{equation\*}
 M:=m(m-1)/2,
\end{equation\*}
\begin{equation\*}
 R:=\sum\_{1\le i<j\le m}\;\sum\_{1\le k<l\le m,\,(k,l)\ne(i,j)}
 P(|v\_i\cdot v\_j|>\ep,|v\_k\cdot v\_l|>\ep). 
\end{equation\*}
If $\{i,j\}\cap\{k,l\}=\emptyset$, then $P(|v\_i\cdot v\_j|>\ep,|v\_k\cdot v\_l|>\ep)=P(|v\_i\cdot v\_j|>\ep)\,P(|v\_k\cdot v\_l|>\ep)=p^2$. 
If $\{i,j\}\cap\{k,l\}\ne\emptyset$ but $\{i,j\}\ne\{k,l\}$, then, using the iid condition on the $u\_i$'s and the spherical symmetry, for (say) the unit vector $e\_1$ of the standard orthonormal basis of $\mathbb R^n$, we have 
\begin{multline}
 P(|v\_i\cdot v\_j|>\ep,|v\_k\cdot v\_l|>\ep)
 =P(|v\_1\cdot v\_2|>\ep,|v\_1\cdot v\_3|>\ep) \\ 
 =P(|e\_1\cdot v\_2|>\ep,|e\_1\cdot v\_3|>\ep)
 =P(|e\_1\cdot v\_2|>\ep)\,P(|e\_1\cdot v\_3|>\ep)=p^2. 
\end{multline}
So, $P(|v\_i\cdot v\_j|>\ep,|v\_k\cdot v\_l|>\ep)=p^2$ for any $i,j,k,l$ such that $1\le i<j\le m,\,1\le k<l\le m,\,(k,l)\ne(i,j)$. So, 
\begin{equation\*}
R=M(M-1)p^2. 
\end{equation\*}


Next, 
\begin{equation\*}
 p=P(|e\_1\cdot v\_1|>\ep)=K\_nI\_n,
\end{equation\*}
where, with $n\to\infty$, 
\begin{equation\*}
 K\_n:=\frac{\Ga(n/2)}{\Ga(1/2)\Ga((n-1)/2)(n-1)^{1/2}}\to1/\sqrt\pi, 
\end{equation\*}
\begin{equation\*}
 I\_n:=(n-1)^{1/2}\int\_{\sqrt c}^\infty(1+t^2)^{-n/2}\,dt=e^{-nc/(2+o(1))}, 
\end{equation\*}
\begin{equation\*}
 c:=\frac{\ep^2}{1-\ep^2}. 
\end{equation\*}


Collecting the pieces, we see that 
\begin{equation}
 Q\_{m,n}=Me^{-nc/(2+o(1))}. 
\end{equation}
Setting now $\de=Q\_{m,n}\to0$, we find the asymptotics of the needed $n$:
\begin{equation}
 n\sim2\frac{1-\ep^2}{\ep^2}\,\ln\frac{m(m-1)}{2\de}. 
\end{equation}


