2
$\begingroup$

A follow-up question to this one basically Understanding a simplification in a theorem. If you want to see the original paper, see page 6/24 there.

We are given that $2 < n \leq M \leq n^2$. Then, the following inequality holds

$\log ( 1 + \dfrac{M}{n-2}) \geq \log n + O(1)$.

The paper goes on saying that now $\Omega (n^2)$ lower bound is obtained. How is this so? According to my understanding to actually show that, I would have to find a positive constant $c_1$, so that

$\log n + O(1) \geq c_1n^2$.

If I then divide this by $n^2$, I'll obtain

$\dfrac{\log n}{n^2} + \dfrac{O(1)}{n^2} \geq c_1$.

But as $n \to \infty$, the terms on the left side tend to 0. Therefore it is not bounded by $\Omega (n^2)$. I know I must be misunderstanding or neglecting something, what is it?

  • 2
    Something's very odd here. If $M=n$ then it's certainly not true that $\log\left(1+{M\over n-2}\right)\ge\log n+O(1)$.2011-06-29
  • 0
    The $\Omega(n^2)$ lower bound is on $M$.2011-06-29
  • 0
    @Gerry, @Pele: I think a lot **more** needs to be copied out from page 6 of the paper. In first inequality written down here requires a lot of previous reasoning and, as far as I can see, quite a few implicit assumptions on $M$. Part of the argument requires dividing a previously obtained estimate $\log M + \log\log M + \log B(M) \geq n \log n + O(\log n)$ by $n$, assuming certain conditions to hold. Dividing by $n$ should not introduced the stated factors in the first or second terms on the LHS, so one can only assume that it comes from $B(M)$.2011-06-29
  • 0
    Also, @Pele, you should really register your account so you don't litter Unregistered accounts and therefore unassociated/unloved questions on the site. Registering also helps the software keep track of your reputation, which questions you posted before, and more.2011-06-29
  • 0
    @YuvalFilmus Right, could you still elaborate more please? It's still not totally clear for me where the bound comes from. @WillieWong Will do, thanks.2011-06-29
  • 0
    @Willie: We get $M = \Omega(n^2)$ directly from the inequality that Pele stated.2011-06-29
  • 0
    @Yuval: I was trying to address Gerry's comment. From what OP wrote one may come to the mistaken impression that the inequality *follows* from the condition $2 < n \leq M \leq n^2$. Of course, as you showed, that inequality is not really necessary in the present discussion.2011-06-29

1 Answers 1

3

Note that $\log n + O(1)$ means $\log n + f(n)$ where $|f(n)| \leq C'$ for some constant $C'$ (and large enough $n$), hence it is at least $\log (Cn)$ for $C = \exp(-C') > 0$. Therefore $$\log \left(1 + \frac{M}{n-2}\right) \geq \log (Cn).$$ Exponentiating both sides, $$\frac{M+n-2}{n-2} \geq Cn.$$ In other words, $$ M \geq Cn(n-2)-(n-2). $$ Therefore $M = \Omega(n^2)$.