Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

I have following conditions and want to show that $\frac {p(n)} n \xrightarrow {n \to \infty} 0$.

\begin{align} (1)&\tilde{\gamma}(n) \xrightarrow {n \to \infty} 0, \\ (2)&\lim_{n \to \infty} n \tilde{\gamma}(n) > 0 ,\\ (3)&p(n):= \min\{q \in \mathbb{N} : q \geq \sqrt{n} \left|\log \tilde{\gamma}(q)\right|\}. \end{align}

My conclusions:

\begin{align} (1),(2) \Rightarrow \exists c,N \quad \forall n>N: 1>\tilde{\gamma}(n) > \frac{c}{n}, \\ (3) \Rightarrow p(n) < \sqrt{n} |\log \tilde{\gamma}(p(n))| + 1. \end{align}

The short proof in my book is "for large $n, p<\sqrt{n}(\log n)^2$, so that $p=o(n)$."

Clearly $ p<\sqrt{n}(\log n)^2 \Rightarrow p=o(n)$. But i couldn't proof that $ p<\sqrt{n}(\log n)^2$.

Do you have any ideas how to proof it?

Note that for $1>\tilde{\gamma}(p)> \frac c p$ it is $|\log \tilde{\gamma}(p) |< |\log \frac c p| $.

Trying to proof: $\sqrt{n} \ge \frac p {a + \log p}$ for some constant $a$.

I know from (1),(2),(3) that \begin{align} \sqrt{n} \geq \frac{p-1}{|\log c| + |\log p|} = \frac{p}{|\log c| + |\log p|} - \frac{1}{|\log c| + |\log p|}. \end{align}

And since $\frac{1}{|\log c| + |\log p|} \xrightarrow {p \to \infty} 0$, it is proofed.

Is this proof correct?

share|cite|improve this question

Considering $t=\sqrt{n}$ and $x(t)=p(n)$, the hypothesis is that $x(t)\leqslant t\cdot(a+\log x(t))$ for some constant $a$ and every $t\geqslant t_0$ and the conclusion to reach is that $x(t)\leqslant t\cdot(\log t)^2$ for every $t$ large enough.

The function $u:\xi\mapsto\xi/(a+\log\xi)$ being increasing on $\xi\geqslant\mathrm e^{1-a}$, if $x(t)\geqslant t\cdot(\log t)^2$, then $$ t\geqslant u(x(t))\geqslant u(t\cdot(\log t)^2)=t\cdot(\log t)^2/(a+\log t+2\log\log t)\sim t\cdot\log t, $$ which is absurd for $t$ large enough. Hence $x(t)\leqslant t\cdot(\log t)^2$ for every $t$ large enough (and in fact $x(t)\leqslant t\cdot(\log t)^{1+\varepsilon}$ for every $t$ large enough, for every $\varepsilon\gt0$).

share|cite|improve this answer
Tank you for your answer. So now i have only to proof that $x(t) \le t(a+\log x(t))$ for some constant $a$. – Runje Nov 23 '12 at 14:09
I tried to proof this hypothesis in my edit. – Runje Nov 23 '12 at 14:23
About your edit, you should first modify the incorrect definition in (3), replacing $\geqslant$ by $\leqslant$ and adding the mention "size of" before the set defining $p(n)$. Then, as I indicate clearly in my post, $p(n)\leqslant\sqrt{n}(\log p(n)-\log c)$ by hypothesis, hence I fail to see what should be proved here. – Did Nov 24 '12 at 9:32
I am sorry, i forgot an important part of the definition of $p(n)$. I hope it makes now more senses what i did there, because i want to proof it with these conditions. – Runje Nov 26 '12 at 9:43

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.