# Does $\Delta \geq \max\{2em, \lg P + \lg \frac{1}{\epsilon} \}$ guarantees that $(\frac{em}{\Delta})^\Delta \leq \frac{\epsilon}{P}$?

I saw this in a technical paper which made a leap I can't follow, it tries to solve an inequality $(cx)^{-x} \leq y$, which it then says it is satisfied when $x \geq -\ln {y}$. I can't make the leap, any ideas? I can also provide the link to the paper if needed. Thanks!

EDIT: Hi, thanks for the replies! Here is the paper http://supertech.csail.mit.edu/papers/steal.pdf It's the last a bit of math on Page 16. It says that: $(\frac{em}{\Delta})^\Delta \leq \frac{\epsilon}{P}$ holds as long as $\Delta \geq \max\{2em, \lg P + \lg \frac{1}{\epsilon} \}$ holds. Here e is the base of natural logarithm, m is a non-negative integer, P is a positive integer, $\Delta$ is a positive integer, and $\epsilon$ is a positive real number.

Frankly speaking, I'm confused about all of these I just described, I can't figure out why the solution to this inequality is a max of two terms, and why the first term does not depend on $\epsilon$ at all. I guess the second term is probably the important part so I asked it in the first place.

Thanks so much!

Resoulution: $\lg$ means logarithm with base 2 in the paper. So $\Delta \geq \max\{2em, \lg P + \lg \frac{1}{\epsilon} \}$ means that $(\frac{em}{\Delta})^\Delta \leq (\frac12)^\Delta \leq (\frac12)^{\lg P + \lg \frac{1}{\epsilon}} = \frac{\epsilon}{P}$. Also thanks Tim for the explanation.

• Please provide the link to the paper. – user230734 Jun 17 '15 at 1:50
• There is additionnal information needed, because for $x>0$ fixed, $cx^{−x}$ can take any value in $]0,+\infty[$ (depending on the value of $c$). But $x \geq −\ln(y)$ doesn't depend of $c$ : there will probably be a problem – Tryss Jun 17 '15 at 2:39
• Hi BolzWeir and Tryss, thanks for the reply! I've added the link to the paper and pointed out the location. I apologize if my original description was a little off from the paper. Thanks! – ios learner Jun 17 '15 at 6:10
• What does lg mean? – Gerry Myerson Jun 17 '15 at 7:00
• Hi @GerryMyerson, you are right, apparently lg means logarithm with base 2 in the original literature and I understand it now, thanks! – ios learner Jun 17 '15 at 21:44

## 1 Answer

Suppose $\Delta=2em$, $P=e^{em}$, $1/\epsilon=e^{em}$. Then $\log P+\log(1/\epsilon)=2em$, so the condition on $\Delta$ is met. We have $$\left({em\over\Delta}\right)^{\Delta}=2^{-2em}>e^{-2em}={\epsilon\over P}$$ so the conclusion is false.

EDIT: I'm assuming "lg" is an abbreviation for natural logarithm. If I'm wrong about that, then all bets are off.

• Shouldn't the left hand side have base $\frac{1}{2}$? – Linus S. Jun 17 '15 at 7:28
• The left side of what? $em/\Delta=1/2$, $(1/2)^Q=2^{-Q}$. – Gerry Myerson Jun 17 '15 at 7:30
• You are correct, my bad. – Linus S. Jun 17 '15 at 7:32
• Hi, thanks for the observation, that's so weird. – ios learner Jun 17 '15 at 18:23