Encyclopedia

Negligible function

Mathematical function

Wikipedia contributorsAdapted for Fathomly · View authors

4 min read
Source updated August 24, 2026

In mathematics, a negligible function is a function $\mu :\mathbb {N} \to \mathbb {R}$ such that for every positive integer c there exists an integer N_c such that for all n > N_c,

$|\mu (n)|<{\frac {1}{n^{c}}}.$

Equivalently, the following definition may be used. A function $\mu :\mathbb {N} \to \mathbb {R}$ is negligible, if for every positive polynomial poly(·) there exists an integer N_poly > 0 such that for all n > N_poly

$|\mu (n)|<{\frac {1}{\operatorname {poly} (n)}}.$

01History

The concept of negligibility can find its trace back to sound models of analysis. Though the concepts of "continuity" and "infinitesimal" became important in mathematics during Newton and Leibniz's time (1680s), they were not well-defined until the late 1810s. The first reasonably rigorous definition of continuity in mathematical analysis was due to Bernard Bolzano, who wrote in 1817 the modern definition of continuity. Later Cauchy, Weierstrass and Heine also defined as follows (with all numbers in the real number domain $\mathbb {R}$ ):

(Continuous function) A function $f:\mathbb {R} {\rightarrow }\mathbb {R}$ is continuous at $x=x_{0}$ if for every $\varepsilon >0$ , there exists a positive number $\delta >0$ such that $|x-x_{0}|<\delta$ implies $|f(x)-f(x_{0})|<\varepsilon .$

This classic definition of continuity can be transformed into the definition of negligibility in a few steps by changing parameters used in the definition. First, in the case $x_{0}=\infty$ with $f(x_{0})=0$ , we must define the concept of "infinitesimal function":

(Infinitesimal) A continuous function $\mu :\mathbb {R} \to \mathbb {R}$ is infinitesimal (as $x$ goes to infinity) if for every $\varepsilon >0$ there exists $N_{\varepsilon }$ such that for all $x>N_{\varepsilon }$

$|\mu (x)|<\varepsilon \,.$

Next, in the discrete setting where the domain is restricted to natural numbers $n\in \mathbb {N}$ , we replace $\varepsilon >0$ by the functions $1/n^{c}$ where $c>0$ or by $1/\operatorname {poly} (n)$ where $\operatorname {poly} (n)$ is a positive polynomial. This leads to the definitions of negligible functions given at the top of this article. Since the constants $\varepsilon >0$ can be expressed as $1/\operatorname {poly} (n)$ with a constant polynomial, this shows that infinitesimal functions (restricted to $\mathbb {N}$ ) are a superset of negligible functions.

02Use in cryptography

In complexity-based modern cryptography, a security scheme is provably secure if the probability of security failure (e.g., inverting a one-way function, distinguishing cryptographically strong pseudorandom bits from truly random bits) is negligible in terms of the input security parameter or cryptographic key length $n$ . Hence comes the definition at the top of the page because key length $n$ must be a natural number.

Nevertheless, the general notion of negligibility doesn't require that the input parameter $n$ is strictly the key length. Indeed, $n$ can be any predetermined discrete system metric and corresponding mathematical analysis would illustrate some hidden analytical behaviors of the system.

The reciprocal-of-polynomial formulation is used for the same reason that computational boundedness is defined as polynomial running time: it has mathematical closure properties that make it tractable in the asymptotic setting (see #Closure properties). For example, if an attack succeeds in violating a security condition only with negligible probability, and the attack is repeated a polynomial number of times, the success probability of the overall attack still remains negligible.

In practice one might want to have more concrete functions bounding the adversary's success probability and to choose the security parameter large enough that this probability is smaller than some threshold, say 2⁻¹²⁸.

03Closure properties

One of the reasons that negligible functions are used in foundations of complexity-theoretic cryptography is that they obey closure properties. Specifically,

If $f,g:\mathbb {N} \to \mathbb {R}$ are negligible, then the function $n\mapsto f(n)+g(n)$ is negligible.
If $f:\mathbb {N} \to \mathbb {R}$ is negligible and $p$ is any real polynomial, then the function $n\mapsto p(n)\cdot f(n)$ is negligible.

Conversely, if $f:\mathbb {N} \to \mathbb {R}$ is not negligible, then neither is $n\mapsto f(n)/p(n)$ for any real polynomial $p$ .

04Examples

is negligible for any constant :
- Step: This is an exponential decay function where $a$ is a constant greater than or equal to 2. As $n\to \infty$ , $a^{-n}\to 0$ very quickly, making it negligible.
is negligible:
- Step: This function has exponential decay with a base of 3, but the exponent grows slower than $n$ (only at ${\sqrt {n}}$ ). As $n\to \infty$ , $3^{-{\sqrt {n}}}\to 0$ , so it’s still negligible but decays slower than $3^{-n}$ .
is negligible:
- Step: In this case, $n^{-\log n}$ represents a superpolynomial decay, with the exponent growing negatively due to $\log n$ . Since the decay rate increases with $n$ , the function goes to 0 faster than polynomial functions like $n^{-k}$ for any constant $k$ , making it negligible.
is negligible:
- Step: This function decays as the logarithm of $n$ raised to a negative exponent $-\log n$ , which leads to a fast approach to 0 as $n\to \infty$ . The decay here is faster than inverse logarithmic or polynomial rates, making it negligible.
is not negligible, for positive :
- Step: We can rewrite this as $f(n)=n^{-c}$ , which is a polynomial decay rather than an exponential one. Since $c$ is positive, $f(n)\to 0$ as $n\to \infty$ , but it doesn’t decay as quickly as true exponential functions with respect to $n$ , making it non-negligible.

Assuming $n>0$ and a fixed real constant $a>1$ , we take the limit as $n\to \infty$ :

Negligible:

:
- Step: This function decays exponentially with base $a$ raised to the power of $-{\frac {n}{2}}$ . As $n\to \infty$ , $a^{-{\frac {n}{2}}}\to 0$ quickly, making it negligible.
for :
- Step: We can simplify $a^{-\log(n^{k})}$ as $n^{-k\log a}$ , which decays faster than any polynomial. As $n\to \infty$ , the function approaches zero and is considered negligible for any $k\geq 1$ and $a>1$ .
for :
- Step: The decay is determined by the base $a$ raised to the power of $-(\log n)^{k}$ . Since $(\log n)^{k}$ grows with $n$ , this function approaches zero faster than polynomial decay, making it negligible.
:
- Step: Here, $f(n)$ decays exponentially with a base of $a$ raised to $-{\sqrt {n}}$ . As $n\to \infty$ , $f(n)\to 0$ quickly, so it’s considered negligible.
:
- Step: With an exponential base and exponent $n(\log n)$ , this function would approach zero very rapidly, suggesting negligibility.

Non-negligible:

:
- Step: Since $n^{1/n}\to 1$ as $n\to \infty$ , this function decays very slowly, failing to approach zero quickly enough to be considered negligible.

Watch videos about Negligible functionExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Negligible function”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Negligible function

01History

02Use in cryptography

03Closure properties

04Examples

Sources and credits

Related topics

Negligible set

Colombeau algebra

Nonstandard analysis