I have the following inequality: $$n \ge \frac{K_n^2}{\epsilon^2} \frac{\log K_n}{\epsilon},\text{ where }K_n = (\log n)^3.$$

I would like to solve it, even numerically.

I thought that numerically it can be solved by iteratively setting $K_n$ using a current value for $n$ and then $n$ using a current value for $K_n$.

However, I get a weird behavior. For different $\epsilon$ (more specifically for $\epsilon = 3.3409202$) I get that the answer for $n$ is 2.0127e+06. If I increase $\epsilon$ by a bit, I get a complex number. For other similar inequalities, I would get a different, but similar interesting "boundary" behavior: there would be a certain epsilon under which the value of solved $n$ will be very large, and over which the $n$ will suddenly jump to a really small value.

Is there any explanation for what's going on here? Is there a better way to solve this inequality?


  • $\begingroup$ Have you tried solving the corresponding equation numerically by Newton's Method? $\endgroup$ – Gerry Myerson May 29 '11 at 0:18
  • $\begingroup$ I tried it in Excel with no problem. At $\epsilon=5, n=197031$ and it seems well behaved. Starting with $n=1000$, it converges in about 20-25 steps (more for higher $\epsilon$) $\endgroup$ – Ross Millikan May 29 '11 at 0:41
  • $\begingroup$ I'm really puzzled how a complex number can come up in that problem. What software did you use and how exactly did you implement the iteration? Did you use a computer algebra system that used the Lambert $W$-function and messed up branches? $\endgroup$ – t.b. May 29 '11 at 0:43
  • $\begingroup$ @Ross - that's strange. @Theo - I am using Matlab. I think what happens is that at some point n becomes smaller than 1, then the log becomes negative, and then disaster starts. $\endgroup$ – inequaler May 29 '11 at 1:16
  • $\begingroup$ @Ross I just tried running it with $\epsilon = 5$ and I get 1.9703e+05 + 2.7281e-50i... So the imaginary part is very close to 0. Perhaps it is some numeric overflow. $\endgroup$ – inequaler May 29 '11 at 1:17

I assume that solving the inequality means replacing the inequality sign by an equality sign and solving for $n$. From your post, I understand that you run into problems for "large" $\epsilon$ ($\epsilon >3.6$). The equation written explicitly reads $$\epsilon^3 n = 3 \log^6 n \,\log \log n.$$

It turns out that the equation has two solutions for $\epsilon< \epsilon^*$: one in the region $(e,n^*)$ and the other in the interval $(n^*,\infty)$. For $\epsilon=\epsilon^*$, the only solution is at $n^*$ and for $\epsilon> \epsilon^*$ there is no (real) solution. The values for $\epsilon^*$ and $n^*$ and some explanation you find below:

Let us assume $n\geq 1$ as the right hand side for $n \leq 1$ is in general complex (and also $\epsilon>0$). The right hand side is negative in the region $[1,e]$. As the left hand side is positive, the solution to the equation has to be for $n\geq e$.

The right hand side grows slower than the left hand side (for $n \to \infty$). Furthermore, the left hand side at $n=e$ is $\epsilon^3 e$ whereas the right hand side is 0. Therefore, it is clear that there will be a maximal $\epsilon= \epsilon^*$ for which the equation has a solution (and for $\epsilon < \epsilon^*$ there will be two solutions).

The condition for $\epsilon^*$ is that the left hand side is a tangent (at $n^*$) to the right hand side. In formulas $$ \begin{align} \text{LHS}(n^*) &= \text{RHS}(n^*)\\ \text{LHS}'(n^*) &= \text{RHS}'(n^*) \end{align} $$ with $\text{LHS}(n)= \epsilon^* n$ and $\text{RHS}(n) = 3 \log^6 n \,\log \log n$. The solution is $$ \begin{align} \epsilon^* &= 8.60323 &n^* &= 687.328 \end{align}. $$

  • 3
    $\begingroup$ And the interpretation of no solution for large $\epsilon$ is that the original inequality is satisfied for all $n\gt0$. $\endgroup$ – Gerry Myerson May 29 '11 at 11:58
  • $\begingroup$ @Gerry: +1, this is an important comment (I was so busy with the equality that I forgot about the inequality ;-)) $\endgroup$ – Fabian May 29 '11 at 14:21

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.