# Obtaining an asymptotic lower bound on a function

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?

• 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)$. – Gerry Myerson Jun 29 '11 at 12:54
• The $\Omega(n^2)$ lower bound is on $M$. – Yuval Filmus Jun 29 '11 at 13:58
• @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)$. – Willie Wong Jun 29 '11 at 14:12
• 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. – Willie Wong Jun 29 '11 at 14:15
• @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. – Pele Jun 29 '11 at 14:27

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)$.