= Solution
Apply part a to each of the at most $n(n-1)/2$ nonzero differences $u_i-u_j$. For $w_i=Au_i/\sqrt d$, the <union bound> makes the probability of any failure at most
$$
\frac{n(n-1)}2\,2e^{-dt^2/136}
<n^2e^{-dt^2/136}.
$$
The assumed inequality $d>272\log(n/\sqrt\varepsilon)/t^2$ makes this smaller than $\varepsilon$. Hence, simultaneously for every distinct pair,
$$
1-t\leq\frac{\lVert w_i-w_j\rVert_2^2}{\lVert u_i-u_j\rVert_2^2}\leq1+t
$$
with probability at least $1-\varepsilon$, which is the finite-set <Johnson–Lindenstrauss lemma>.
Back to article page
