Negligible function

A function Failed to parse (Missing texvc executable; please see math/README to configure.): \mu(x):\mathbb{N}{\rightarrow}\mathbb{R}

is negligible, if for every positive integer Failed to parse (Missing texvc executable; please see math/README to configure.): c
there exists an Failed to parse (Missing texvc executable; please see math/README to configure.): N_c>0
such that for all Failed to parse (Missing texvc executable; please see math/README to configure.): x>N_c

Failed to parse (Missing texvc executable; please see math/README to configure.): |\mu(x)|<\frac{1}{x^c}.

Equivalently, we may also use the following definition. A function Failed to parse (Missing texvc executable; please see math/README to configure.): \mu(x):\mathbb{N}{\rightarrow}\mathbb{R}

is negligible, if for every positive polynomial Failed to parse (Missing texvc executable; please see math/README to configure.): poly(.)
there exists an Failed to parse (Missing texvc executable; please see math/README to configure.): N_{poly}>0
such that for all Failed to parse (Missing texvc executable; please see math/README to configure.): x>N_{poly}

Failed to parse (Missing texvc executable; please see math/README to configure.): |\mu(x)|<\frac{1}{poly(x)}.

History

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 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. Lately Cauchy, Weierstrass and Heine also defined as follows (with all numbers in the real number domain Failed to parse (Missing texvc executable; please see math/README to configure.): \mathbb{R} ):

(Continuous function) A function Failed to parse (Missing texvc executable; please see math/README to configure.): f(x):\mathbb{R}{\rightarrow}\mathbb{R}

is continuous at Failed to parse (Missing texvc executable; please see math/README to configure.): x=x_0
if for every Failed to parse (Missing texvc executable; please see math/README to configure.): \epsilon>0

, there exists a positive number Failed to parse (Missing texvc executable; please see math/README to configure.): \delta>0

such that Failed to parse (Missing texvc executable; please see math/README to configure.): |x-x_0|<\delta
implies Failed to parse (Missing texvc executable; please see math/README to configure.): |f(x)-f(x_0)|<\epsilon.

This classic definition of continuity can be transformed into the definition of negligibility in a few steps by changing a parameter used in the definition per step. First, in case Failed to parse (Missing texvc executable; please see math/README to configure.): x_0=\infty

with Failed to parse (Missing texvc executable; please see math/README to configure.): f(x_0)=0

, we must define the concept of "infinitesimal function":

(Infinitesimal) A continuous function Failed to parse (Missing texvc executable; please see math/README to configure.): \mu(x):\mathbb{R}{\rightarrow}\mathbb{R}

is infinitesimal (as Failed to parse (Missing texvc executable; please see math/README to configure.): x
goes to infinity) if for every Failed to parse (Missing texvc executable; please see math/README to configure.): \epsilon>0
there exists Failed to parse (Missing texvc executable; please see math/README to configure.): N_{\epsilon}
such that for all Failed to parse (Missing texvc executable; please see math/README to configure.): x>N_{\epsilon}

Failed to parse (Missing texvc executable; please see math/README to configure.): |\mu(x)|<\epsilon\,.

^{[citation needed]}

Next, we replace Failed to parse (Missing texvc executable; please see math/README to configure.): \epsilon>0

by the functions Failed to parse (Missing texvc executable; please see math/README to configure.): 1/x^c
where Failed to parse (Missing texvc executable; please see math/README to configure.): c>0
or by Failed to parse (Missing texvc executable; please see math/README to configure.): 1/poly(x)
where Failed to parse (Missing texvc executable; please see math/README to configure.): poly(x)
is a positive polynomial. This leads to the definitions of negligible functions given at the top of this article. Since the constants Failed to parse (Missing texvc executable; please see math/README to configure.): epsilon>0
can be expressed as Failed to parse (Missing texvc executable; please see math/README to configure.): 1/poly(x)
with a constant polynomial this shows that negligible functions are a subset of the infinitesimal functions.

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 Failed to parse (Missing texvc executable; please see math/README to configure.): x

= cryptographic key length Failed to parse (Missing texvc executable; please see math/README to configure.): n

. Hence comes the definition at the top of the page because key length Failed to parse (Missing texvc executable; please see math/README to configure.): n

must be a natural number.

Nevertheless, the general notion of negligibility has never said that the system input parameter Failed to parse (Missing texvc executable; please see math/README to configure.): x

must be the key length Failed to parse (Missing texvc executable; please see math/README to configure.): n

. Indeed, Failed to parse (Missing texvc executable; please see math/README to configure.): x

can be any predetermined system metric and corresponding mathematic analysis would illustrate some hidden analytical behaviors of the system.

Footnote

References

• Goldreich, Oded (2001). Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press. ISBN 0-521-79172-3. Fragments available at the author's web site.
• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  Section 10.6.3: One-way functions, pp.374–376.
• Christos Papadimitriou (1993). Computational Complexity, 1st edition, Addison Wesley. ISBN 0-201-53082-1.  Section 12.1: One-way functions, pp.279–298.
• Jean François Colombeau (1984). New Generalized Functions and Multiplication of Distributions. Mathematics Studies 84, North Holland. ISBN 0-444-86830-5. 

See also

• Negligible function (cryptography)
• Negligible set
• Colombeau algebra
• Nonstandard numbers
• Gromov's theorem on groups of polynomial growth
• Non-standard calculus