11
$\begingroup$

When I tried to construct a counterexample in my research, I encountered the following result, which should be true.

Let $m=m(n)$ be a function that grows faster than $\sqrt n$, so $m(n) = \omega(\sqrt n)$. Choose $m$ integers $a_1,...,a_m$ randomly from $[1,n]$. Then

$$\lim\limits_{n\to \infty} \mathbb{E}\left[ \frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n}\right] =1.$$ Any references to this result would be greatly helpful. Direct proof would also be very welcome.

Crossposted on cstheory

Improve this question
$\endgroup$
9
  • $\begingroup$ MO is not the right place for this question, since it is not research-level mathematics. It might be research-level computer science (I still doubt that. That seems to suggest that computer scientists only do trivial math) but it certainly isn't research-level mathematics. Furthermore: The claim is obviously wrong, because the maximal number of different distances is $\frac{1}{2}m(m-1)$ since $|a_i-a_j|=|a_j-a_i|$ so that the quotient is bounded from above by $\frac{1}{2}$ if $m\approx \sqrt{n}$. $\endgroup$
    – Johannes Hahn
    Commented Jun 21, 2015 at 13:11
  • 5
    $\begingroup$ @Hahn: sorry for using a computer science term $\omega(\sqrt{n})$ without explanation. It actually means some function that grows more quickly than any constant times $\sqrt{n}$, which excludes $m=\sqrt{n}$ in particular. $\endgroup$
    – Zhu Cao
    Commented Jun 21, 2015 at 13:17
  • 3
    $\begingroup$ I posted an answer at cstheory.stackexchange. $\endgroup$
    – James Martin
    Commented Jun 21, 2015 at 18:42
  • 12
    $\begingroup$ I'd like to push back against the "off-topic" votes. 11 upvotes over two days at cstheory with no answers is very unusual if it's trivial. If so, it would be great to get a quick sketch for the benefit of the cs crowd. ... e.g. I don't see how to proceed with just tail bounds and union bounds, since the ${m\choose 2}$ variables $|a_i-a_j|$ are non-uniform and non-independent. Seems to need a bigger hammer to me -- I'm far from an expert, but I doubt I'm the only one who tried.... $\endgroup$
    – usul
    Commented Jun 21, 2015 at 19:49
  • 1
    $\begingroup$ @usul, simultaneous cross-posting is frowned upon on Stack Exchange sites (and violates the rules on CSTheory.SE), so it seems pretty clear that one of the two copies needed to be closed. $\endgroup$
    – D.W.
    Commented Jun 22, 2015 at 0:51

0

Reset to default