Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
show 1 more comment

2 Answers

up vote 1 down vote accepted

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

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
    
I have added more information to this problem –  Manolo Jan 20 '13 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 '13 at 2:04
    
no, according to the material is negligible –  Manolo Jan 20 '13 at 2:06
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.