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


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.