formal proof about inequality in numbers

Question

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

Answer 1

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".

Answer 2

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$.