I have that $$ Y \geq n e^{- 1- t \log t + o(1)}$$

and $$Y \leq n e^{\log n +t - t \log t}.$$

Now I would like to find values $t_0(n)$ and $t_1(n)$ such that $$Y \rightarrow 0 \text{ for all } t \geq t_0(n)$$ and $$Y \rightarrow \infty \text{ for all }t \leq t_1(n).$$

I know that $$t_0(n)=(1+\epsilon)\frac{\log n}{\log \log n}$$

and $$t_1(n)=\frac{\log n}{\log \log n}$$

are such values. But how does one derive this in general?

What I have done (illustrated with $t_1(n)$):

I want $Y \rightarrow \infty$, thus I want to show that $ne^{-1 -t \log t+ o(1)}=e^{\log n - 1 - t \log t + o(1)}$ goes to $\infty$. This is the case iff $\log n-t \log t \rightarrow \infty$, which is the case if $t \log t = o(\log n)$. In order to find such a boundary case, I wanted to solve $t \log t = \Theta(\log n)$, but I have no idea how to do this. Thank you for your help!!


1 Answer 1


I remember doing something similar in the past, and I reasoned very similarly. Just when you reach the point of $\log n - t\log t \to \infty$, instead of jumping to $t\log t = o(\log n)$ (which is not the same thing), think what is it that you really want.

Because you can proceed like this: denote $f(x) = x \log x$, and conclude that your $t$ has to satisfy $t > f^{-1}(\log n) + \kappa(n)$ where $\kappa(n)$ tends to $\infty$ as slowly as you wish.

But likely you don't need this much of precision, and $f^{-1}$ can't be expressed via standard functions. In this case, go for the first approximation of $f^{-1}$, namely, if $t\log t \sim \log n$, then $t \sim \log n /\log \log n$.

If you are wondering how to come up with that first approximation, you can either look at Lambert W function (esp. example 2 and second asymptotic expansion), or try guesstimating: If you take $t = \log n$ (which is a very natural first guess), then $t \log t = \log n \log \log n$, which is a factor of $\log \log n$ too much. So let's divide by it! Try $t = \log n/\log\log n$ and get $$ t\log t = \frac{\log n}{\log \log n} (\log \log n - \log \log \log n) = (1 - \frac{\log\log n}{\log \log \log n})\log n. $$

Nice, this value works for your condition $\log n - t \log t \to \infty$, and it will no longer work, if you, say, divide it by constant. If such accuracy is enough you stop here, if not, you can continue to multiply $t$ by various things and increase precision.

The story with $t_0$ is the same, so I will not go there.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .