1
$\begingroup$

We have two positive and increasing integers $a$ and $b$. We assume that $a$ is a function of $b$ and that we have:

$$a \log a \sim b$$

where $\sim$ is the asymptotic equivalence.

I would like to show that $a = \Theta(\frac{b}{\log b})$.

Thank you.

$\endgroup$
  • $\begingroup$ Note that the inverse of $x \log(x)$ is $\frac{x}{W(x)}$ where $W$ is the Lambert W function i.e. the inverse of $x e^x$. So you need asymptotics of $W(x)$ for large argument, specifically you want $W(x)=\Theta(\log(x))$. $\endgroup$ – Ian Jul 20 '17 at 15:43
  • $\begingroup$ That is exactly the relation between the $n$-prime $p_n$ and the number $\pi(n)$ of primes less than or equal to $n$. See WIkipedia. $\endgroup$ – lhf Jul 20 '17 at 16:10
3
$\begingroup$

$$\frac{b}{\log b}\sim\frac{a\log a}{\log a+\log \log a}\sim a.$$

This is even more precise than $\Theta$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Don't we need to assume that $a \to \infty$ as $b \to \infty$ ? $\endgroup$ – lhf Jul 20 '17 at 16:13
  • $\begingroup$ Thank you very much for your answer. @lhf $a$ and $b$ are increasing and $a$ is a function of $b$. $\endgroup$ – Dingo13 Jul 20 '17 at 18:24

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.