6
$\begingroup$

I'm reading this paper which says

Let $d=d(n)$ be the positive real number for which

$$ \binom n d p^{\binom d 2} = 1 $$

where $ 0 < p \le 1$, then

$$ d(n) = 2 \log_bn - 2 \log_b (\log_b n) + 2 \log_b\left(\frac 1 2 e\right) + 1 + O(1) \\= 2\log_bn+ O( \log_b \log_b n) $$

where $b = \frac 1 p$.

As the authors skimmed the proof, I've completely no idea how they reached the conclusion.

$\endgroup$
  • 1
    $\begingroup$ I suppose you could try to use stirling and then just plug in $d$ and see what happens? $\endgroup$ – Maximilian Janisch Jun 30 at 22:07
  • $\begingroup$ @MaximilianJanisch what you said probably works, but I think OP might want a motivated proof. $\endgroup$ – mathworker21 Jul 1 at 0:34
3
+50
$\begingroup$

Setting $b=1/p$, the equation can be written as

$$\frac{n!}{d!(n-d)!}=b^{d(d-1)/2}$$

or

$$\log_b\left[\frac{n!}{d!(n-d)!}\right]=\frac{d(d-1)}{2}$$

Applying the Stirling approximation, the LHS becomes

$$\log_b \left(\sqrt{\frac{n}{2\pi d(n-d)}} \frac{ n^n}{d^d(n-d)^{n-d}}\right)\\ =\left(n+\frac{1}{2}\right)\log_b n- \left(d+\frac{1}{2}\right)\log_b d-\left(n-d+\frac{1}{2}\right)\log_b(n-d)+O(1) $$

We can consider the expansion for $n=\infty$ of the term $\log_b(n-d)$, which is

$$\log_b n-\frac{d}{n\log b}+O(n^{-2})$$

Substituting we get

$${ d}\,{\log_b n} +\frac{d}{\log b} -\frac{d^2}{n \log b} -\left(d+\frac{1}{2}\right)\log_b d +O(1) $$

Since this quantity has to be equal to $d(d-1)/2$, grouping the terms according to $d$ we have

$$d^2\left(\frac{1}{2}+\frac{1}{n\log b }\right)-d\left(\log_b n+\frac{1}{2}+\frac{1}{\log b} \right) +\left(d+\frac{1}{2}\right)\log_b d =O(1)$$

From this equation, we get that, as $n \rightarrow \infty$, the main term of the asymptotic expansion of $d$ is $ 2\log_b n$.


To determine the successive term of the expansion, we can set $d=2\log_b n +f(n)$. Taking the last equation, dividing by $d$, and making the substitution we get

$$\bigg[2\log_b n+f(n)\bigg]\left(\frac{1}{2}+\frac{1}{n\log b }\right)- \left(\log_b n+\frac{1}{2}+\frac{1}{\log b } \right) +\left(1+\frac{1}{2[2\log_b n +f(n)]}\right) \\ \log_b \bigg[2\log_b n+f(n)\bigg] =O(1)$$

Taking into account that the order of $f(n)$ is lower than $\log n$, incorporating some terms into the $O(1)$ error, the last equation becomes

$$\frac{1}{2}\left[2\log_b n+{f(n)}\right]- \log_b n + \log_b [2\log_b n+f(n)] =O(1)$$

from which

$$f(n)=-2\log_b (\log_b n) +O(1)$$


To further go into the expansion, we can set

$$d=2\log_b n -2\log_b (\log_b n ) +g(n)$$

Proceding as above by making the substitution, taking into account that the order of $g(n)$ is $O(1)$, and incorporating some terms into a residual $O(1)$ term, we get

$$\frac{1}{2}\left[2\log_b n -2\log_b (\log_b n)+{g(n)}\right]\\- \log_b n - \frac{1}{2} -\frac{1}{\log b}+\log_b 2\\+ \log_b [\log_b n+2\log_b(\log_b n) +f(n)] =O(1)$$

from which

$$g(n)=1+ \frac{2}{\log b}-2 \left(\log_b 2 \right) +O(1)\\ = 1+ 2\log_b e +2 \left(\log_b \frac{1}{2}\right) +O(1) \\ =1+ 2\log_b \left(\frac{1}{2}e \right) +O(1)$$

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Nice answer. But the exponent in the OP's question is $d\choose2$, not $n\choose2$, which changes your starting equation. Maybe it's just a typo in your answer, though. $\endgroup$ – cjferes Jul 3 at 22:27
  • 2
    $\begingroup$ Thank you for your note. I just edited my answer. $\endgroup$ – Anatoly Jul 3 at 22:32
  • $\begingroup$ Thank you for the clear and understandable answer! $\endgroup$ – UmbQbify -Key20- Jul 4 at 10:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.