# Prove - In $\frac{1}{{2}^{\lambda }}\leq \frac{1}{{\lambda }^{d}}$, there exists a large value of $\lambda$, so that the equation holds for any $d$.

This problem appears in some material about cryptography related to negligible and non-negligible functions.

In the material says :

epsilon is negligible if

For all $d$, there exists some $\lambda_d$ such that $$\lambda \geq \lambda_d:\epsilon \left(\lambda \right)\leq \frac{1}{{\lambda }^{d}}$$

Then, how I can prove formally that in the following equation:

$$\frac{1}{{2}^{\lambda }}\leq \frac{1}{{\lambda }^{d}}$$

there will exist a large value of $\lambda$, such that for any value of $d$ the equation will hold? So that means that this function is negligible

Note: $\lambda$ and $d$ are positive reals

Thanks

-
Use the dollar sign or a pair of them on both sides of the equation. – Juris Jan 20 '13 at 1:30
Do you mean, "there will exist a value of $d$, such that for any value of $\lambda$ it will hold it?" – Herng Yi Jan 20 '13 at 1:31
Please also clarify the domain of $d$ and $\lambda$ - I assume that both are positive reals? – Herng Yi Jan 20 '13 at 1:32
Did you mean, $\lambda \geq \lambda^d : \cdots$? – Herng Yi Jan 20 '13 at 2:06
yes, that is what I meant – Manolo Jan 20 '13 at 2:10

What you can show is that for every $d$ there is a $L(d)$ such that $\frac{1}{{2}^{\lambda }}\leq \frac{1}{{\lambda }^{d}}$ for $\lambda > L(d)$.

$\frac{1}{{2}^{\lambda }}\leq \frac{1}{{\lambda }^{d}}$ is equivalent to ${2}^{\lambda }\geq {\lambda }^{d}$ or $\lambda \ln 2 \geq d \ln \lambda$ or ${\lambda \ln 2 \over \ln \lambda}\geq d$.

Since ${\lambda \over \ln \lambda}$ is unbounded and increasing for $\lambda > e$, once we find a solution to ${\lambda \over \ln \lambda}\geq {d \over \ln 2}$, we have found the desired $L(d)$.

Note: The solution to ${x \over \ln x} = y$ is about $x = y \ln y$. You can readily find more exact results - one place I know of is de Bruijn's "Asymptotic Methods in Analysis".

-
thanks @marty cohen, I have been thinking in the first part of the solution that I mentioned, but I was missing the rest of it. It was very helpful your post – Manolo Jan 20 '13 at 2:22

This is false. No matter what $\lambda$ is, the value of $1/\lambda^d$ can be made arbitrarily small by choosing ever larger values of $d$. This is because the function $f(d) = 1/\lambda^d$ is decreasing and $\lim_{x \to \infty}f(x) = 0$.

Since $1/2^\lambda$ is a constant, there is bound to be some critical value of $d_0$ such that $1/\lambda^d \leq 1/2^\lambda$ for all $d \geq d_0$.

Explicitly, we may solve $1/2^\lambda = 1/\lambda^{d_0}$ to get $d_0 = \log_{\lambda}2^\lambda$.

-
I found this in a book about negligible and non-negligible functions so that is why I needed that proof – Manolo Jan 20 '13 at 1:49
You may have copied the question wrongly, for the way you stated it, the assertion is false. – Herng Yi Jan 20 '13 at 1:52
The new information you added doesn't make my argument any less applicable - I guess the function $\epsilon(\lambda) = 1/2^\lambda$ is not negligible then? – Herng Yi Jan 20 '13 at 2:04