# Proving that a function is negligible

In mathematics, a negligible function is a function $\mu(x):\mathbb{N}{\rightarrow}\mathbb{R}$ such that for every positive integer $c$ there exists an integer $N_c$ such that for all $x > N_c$, $\mu(x)<\frac{1}{x^c}$. (From wikipedia)

What exactly is $N_c$?

The definition is quite confusing for me, but I think the intuition is that a negligible function is something that shrinks faster than 1 divided by any polynomial function?

Is $2^{-x}$ negligible?

I think so, but don't know how to show this.

Is $x^{-100}$ negligible?

No, not negligible. The condition can be written as $x^{-100} < x^{-c}$ but this will only hold for values of $c$ that are smaller than $100$

Is $2^x$ negligible?

No, this is clear because as $\lim_{x->\infty} 2^x = \infty$, whereas $\lim_{x->\infty}x^{-c} = 0$, thus the inequality will not hold

• Actually, you should have written $N_c$ and not $Nc$. Then $N_c$ is some integer, depending on $c$. for which the estimate holds. For instance, with $\mu(x)=\frac{1}{x^2}$ and $c=2$, you can take $N_2=0$. For $c=1$, you can take $N_1=1$. But for $c=3$, there is no such $N_3$. – Julien Mar 31 '13 at 11:36
• This is equivalent to saying that for every $c$, $\lim_{x\to\infty} \mu(x) x^c = 0$. – Yury Mar 31 '13 at 12:45
• unfortunately i have never learned calculus and have a very basic understanding of limits. for examples both $2^-x$ and $1/x^c$ both seem to $= 0$ when $x->\infty$ – Student Mar 31 '13 at 13:02

Your intuition is right. Fix a real number $a>1$ (in your example with $\mu(x)=2^{-x}$, the base $a$ is $2$), and let $c$ be any positive real number (an integer if you like). We need to find $b\in \Bbb R$ such that $a^{-x}<x^{-c}$ for all $x>b$ (your $N_c$ can then be any integer bigger than $b$). By taking natural logarithms, this inequality may be rewritten$$\frac{x}{\ln x}>\frac{c}{\ln a}.$$The Taylor expansion of the exponential function shows that $\mathrm e^y>1+y+\frac 12y^2$ for all $y>0$, and so $\mathrm e^y/y>1/y+1+\frac 12y$, which implies $\mathrm e^y/y>\frac 12y$. Then writing $y=\ln x$ gives$$\frac{x}{\ln x}>\frac{\ln x}{2}\quad(x>1).$$It is thus sufficient to ensure that $x$ is large enough to make $\frac12 \ln x$ exceed $c/\ln a$; that is, choose $x>b,$ where$$b=\exp\frac{2c}{\ln a}.$$