2
$\begingroup$

I am reading Dan Boneh's book and I am stuck on Theorem 2.11, whose proof is left as an exercise.

The question is: prove that if $\lim_{n \rightarrow \infty} f(n)n^c = 0$ for all $c > 0$, then $f$ is negligible.

Here, negligible function is defined to be a function $f : \mathbb{Z}_{\geq 1} \rightarrow \mathbb{R}$ such that for any real $c > 0$, there exists an integer $n_0 \geq 1$ such that $f(n) < \frac{1}{n^c}$ for al $n \geq n_0$.

What I've done so far is the following: assume that, for any real $c > 0$, we have $\lim_{n \rightarrow \infty} f(n)n^c = 0$. See that this means that $\lim_{n \rightarrow \infty} f(n)n^{c+1} = 0$ as well. Note that $\frac{1}{n} = \frac{1}{n^{c+1}}n^c$, so $\lim_{n \rightarrow \infty} \frac{1}{n^{c+1}}n^c = \lim_{n \rightarrow \infty} f(n)n^c = 0$, so $f(n)n^c < \frac{1}{n^{c+1}}n^c$ and finally $f(n) < \frac{1}{n^{c+1}}$, as we wanted.

Is this correct? If so, how to justify the part that says $f(n)n^c < \frac{1}{n^{c+1}}n^c$?

$\endgroup$

1 Answer 1

1
$\begingroup$

Assume that for any $c>0,$ we have $$\lim_{n \rightarrow \infty} f(n)n^{c} = 0.$$ This means that for any $\epsilon>0$ however small, there exists some finite $N$ so that for all $n>N,$ we have $f(n) n^c \leq \epsilon.$ This is the standard $\epsilon$ definition of a limit in analysis (if you go far enough, you are arbitrarily close, i.e., $\epsilon$-close to the limit point, which is here equal to zero).

Note that this directly implies by division that $$ f(n) \leq \frac{\epsilon}{n^c}, \quad \forall n>N $$ as well. Since $\epsilon>0$ was arbitrary we can take it to be in $(0,1)$ and we are done.

Note:

Your assumption was too strong, one need not have $f(n)<1/n,$ for convergence, one can have $f(n)<1/g(n)$ for any growing function $g(n)$ however slowly it may grow. Also, here we can typically assume that $f(n)$ is a positive function, otherwise one may need to use absolute values, but in cryptography the functions are normally positive.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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