4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$ – Julien Mar 31 '13 at 11:36
  • $\begingroup$ This is equivalent to saying that for every $c$, $\lim_{x\to\infty} \mu(x) x^c = 0$. $\endgroup$ – Yury Mar 31 '13 at 12:45
  • $\begingroup$ 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$ $\endgroup$ – Student Mar 31 '13 at 13:02
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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