Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 3 down vote accepted

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

share|cite|improve this answer
Note that $\log n + O(1)$ means $\log n + C'$ for some constant $C'$ (and large enough $n$): Sorry but no, $\log n + O(1)$ does not mean that. – Did Jun 29 '11 at 18:43
Indeed, thanks! – Pele Jun 29 '11 at 19:28
But it "almost" means that! Corrected now. – Yuval Filmus Jun 29 '11 at 23:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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