# how to solve the following inequality?

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?

Thanks.

-
Have you tried solving the corresponding equation numerically by Newton's Method? –  Gerry Myerson May 29 '11 at 0:18
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$) –  Ross Millikan May 29 '11 at 0:41
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? –  t.b. May 29 '11 at 0:43
@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. –  inequaler May 29 '11 at 1:16
@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. –  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}.

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