1
$\begingroup$

Let $0 < p < 1$ be a constant, and set $b = 1/p$. Let $0 < \epsilon < 1/2$. Given a natural number $r \ge 2$, let $n_r$ be the maximal natural number for which

$\binom{n_r}{r} p^{\binom{r}{2}} \le r^{-(1+\epsilon)}$

Also, let $n_{r}^{\prime}$ be the minimal natural number for which

$\binom{n_{r}^{\prime}}{r} p^{\binom{r}{2}} \ge r^{1+\epsilon}$

It is clear that $n_r < n_{r}^{\prime}$. After some computations, one get that

$ n_r = \frac{r}{e} b^{(r-1)/2} + o(rb^{r/2})$ and similarly $ n_{r}^{\prime} = \frac{r}{e} b^{(r-1)/2} + o(rb^{r/2})$

My question is, how do we get the following:

$ n_{r}^{\prime}-n_r < \frac{5 \log{r}}{2r} n_r $

I don't know how can we obtain that inequality. Equivalently, we want

$ \frac{n_{r}^{\prime}}{n_r} < 1 + \log{r^{5/2r}} $

As $n_r$ is maximal, it follows that $\binom{n_r+1}{r} p^{\binom{r}{2}} > r^{-(1+\epsilon)}$ As well, as $n_{r}^{\prime}$ is minimal, we see that $\binom{n_{r}^{\prime} - 1}{r} p^{\binom{r}{2}} < r^{1+\epsilon}$

Then, the quotient of these inequalities gives $ \frac{\frac{(n_r^{\prime}-1)^r}{r^r}}{\frac{(n_r+1)^r}{r!}} \le \frac{\binom{n_{r}^{\prime} - 1}{r}}{\binom{n_r+1}{r}} < r^{2(1+\epsilon)} \le r^{3}$

So, by Stirling's approx.

$ \left(\frac{n_r^{\prime}-1}{n_r+1}\right)^r < \frac{r^r}{r!} r^{3} \sim \frac{e^r r^{5/2}}{\sqrt{2 \pi}} < e^r r^{5/2} $

Then $ \left(\frac{n_r^{\prime}-1}{n_r+1}\right) < e r^{5/2r} $, now taking logarithms:

$ \log{\left(\frac{n_r^{\prime}-1}{n_r+1}\right)} < 1 + \log{r^{5/2r}}$

The RHS is the one we desire, however, I don't know how to fix the LHS to get what we need: $\frac{n_r^{\prime}}{n_r}$.

Thanks for your help!

0 Answers 0