Number of distinct differences of $\omega(\sqrt{n})$ integers chosen from $[n]$ I encountered the following result during my research. 


  $$\lim\limits_{n\to \infty} \mathbb{E}\left[ 
\frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n}
\right] = 1$$
  where $m=\omega(\sqrt n)$ and $a_1,\cdots,a_m$ are chosen at random from $[n]$.


I am looking for a reference/a direct proof.



Crossposted on MO
Assume as given that $m=\omega(\sqrt{n})$.

Fix any $\epsilon&gt;0$. We will consider $r\in[1,n]$ with $r&lt;(1-\epsilon)n$. The aim is to show that with high probability as $n\to\infty$, $r$ is included in the set of differences.

First consider the set $A=\{a_i:i&lt;m/2\}\cap[1,\epsilon n]$. The number of $i$ with $i&lt;m/2$ such that $a_i&lt;\epsilon n$ is binomial with expectation around $\epsilon m/2$. So with high probability as $n\to\infty$, the number of such $i$ will be at least $\epsilon m/4$, which is $\omega(\sqrt{n})$. Then (claim, "left as exercise", not hard to show) with high probability as $n\to\infty$, the set $A$ has size at least $\sqrt{n}$. Let us write $G$ for this "good event", that $|A|\geq\sqrt{n}$.

Suppose that indeed $G$ holds, i.e. there are at least $\sqrt{n}$ distinct values of $a_i$ less than $\epsilon n$, for $i&lt;m/2$. Note that for each such value, there is a value $k\in [1,n]$ which is precisely $r$ larger. Now consider the values of $a_i$ for $i\geq m/2$. These are independent and each one has probability at least $\sqrt{n}/n=1/\sqrt{n}$ of being at distance $r$ from an element of the set $A$. The probability that no difference $r$ is produced is then at most $(1-1/\sqrt{n})^{m/2}$ which goes to 0 as $n\to\infty$ since $m=\omega(\sqrt{n})$. So indeed, the probability that $G$ holds but no difference of size $r$ exists tends to 0 as $n\to\infty$. 

So (uniformly in $r&lt;(1-\epsilon)n$) the probability that $r$ is included in the set of differences tends to 1 as $n\to\infty$. 
Hence using linearity of expectation,
$$
\liminf
\limits_{n\to \infty} \mathbb{E}\left[ \frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n}\right] \geq 1-\epsilon.$$
Since $\epsilon$ is arbitrary, the limit is 1 as desired.