Negligible and non-negligible

The Stanford online course, Cryptography I, describes:



What does mean "lambda >= lambda d"?

Because the epsilon is a function, we can write the lambda as x and the epsilon as f(x) for easy understanding. We specify f(x) as below, that is an example,

f(x) = 1 / (2^x)

The f(x) is negligible because,

f(x) = 1 / (2^x) <= 1 / (x^d), 
for all d and large enough x. (statement 1)

Why do we consider the statement 1 is true? I am not a mathematician. I prefer to use enough examples and tools to observe and understand problem. The tool, the iPad App Quick Graph+, is used to draw curves of the below functions.

f(x) = 1 / (2^x)
f(x) = 1 / x
f(x) = 1 / (x^2)
f(x) = 1 / (x^3)
f(x) = 1 / (x^4)



It is hard to verify the statement 1 with the picture because the curves are close to each other when x is large. Therefore we transfer the statement 1 as below.

g(x) = 2^x - x^d >= 0, 
for all d and an enough large x. (statement 2)

We give examples, d = 1, 2, 3, 4. The below picture contains the curves.


If we zoom in the picture, we can find an interesting thing.

The statement 2 is true for an enough large x.



For d = 1, g(x) = 2^x - x >= 0, 
           if x >= x1. x1 is any real number.

For d = 2, g(x) = 2^x - x^2 >= 0, 
           if x >= x2. x2 is 4

For d = 3, g(x) = 2^x - x^3 >= 0, 
           if x >= x3. x3 is about 9.94

For d = 4, g(x) = 2^x - x^4 >= 0, 
           if x >= x4. x4 is 16

Because x is also called lambda, that is what means "lambda >= lambda d".

-Count