# formal proof about inequality in numbers

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 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 at 1:31 Please also clarify the domain of $d$ and $\lambda$ - I assume that both are positive reals? – Herng Yi Jan 20 at 1:32 Did you mean, $\lambda \geq \lambda^d : \cdots$? – Herng Yi Jan 20 at 2:06 yes, that is what I meant – Manolo Jan 20 at 2:10
show 1 more comment

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 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 at 1:49 You may have copied the question wrongly, for the way you stated it, the assertion is false. – Herng Yi Jan 20 at 1:52 I have added more information to this problem – Manolo Jan 20 at 2:01 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 at 2:04 no, according to the material is negligible – Manolo Jan 20 at 2:06