Let $n$ be a large positive integer. Sample $N \ge 2$ points $x_1,\ldots,x_N$ iid from the uniform distribution on $\{0,1\}^n$. Define the gap $\delta_{N,n} := \min_{i \ne j} d_H(x_i,x_j)$, where $d_H$ is Hamming distance. Note that $\delta_{N,n}$ is a random variable with values in $\{0,\ldots,n\}$. I'm interested in good tail bounds for $\delta_{N,n}$. To this end, given $\gamma \in (0,1)$, define $p_{N,n,\gamma} \in [0,1]$ by 

\begin{eqnarray}
p_{N,n,\gamma} := \mathbb P(\delta_{N,n} \ge \gamma n).
\end{eqnarray}

**Question 1.** What are good upper and lower-bounds for $p_{N,n,\gamma}$ ?

I'm particularly interested in the following case:

- $N = N(n) \asymp n$, i.e $cn \le N \le Cn$ for some constants $c,C \gt 0$.
- $N = N(n) \asymp 2^{c n^\alpha}$ for some constants $\alpha \in (0,1]$ and $c \gt 0$
- ...

Phase transition
----

Now, let $N = N(n) = 2^{cn^\alpha}$ for some constants $\alpha \in (0,1]$ and $c \gt 0$.

**Question 2.** For what values of $(c,\alpha)$ do we have $\liminf_{n \to \infty} p_{N(n),n,\gamma} = 0$ ?

**Question 3.** For what values of $(c,\alpha)$ do we have $\limsup_{n \to \infty} p_{N(n),n,\gamma} = 1$ ?