Negligibility

Negligibility describes the property of a quantity being so small that it can be ignored in analysis or decision-making. The term is used across mathematics, science, and engineering to justify simplifying assumptions, truncating series, or omitting tiny contributions in models.

In asymptotic analysis, a function f is negligible if for every positive integer c, f(n) = o(n^{-c}) as n tends to infinity. Equivalently, f(n) n^c → 0 for all c. Such functions decay faster than the reciprocal of any polynomial. This contrasts with terms like 1/n^k, which are not negligible because they do not decay faster than every inverse polynomial.

In cryptography and computer science, negligibility is defined with respect to a security parameter. A function ε: N → [0,1] is negligible if for every polynomial p, there exists N such that ε(n) ≤ 1/p(n) for all n ≥ N. In practice, this means the success probability of an adversary vanishes faster than any inverse polynomial as the security parameter grows.

Examples: ε(n) = 2^{-n} or ε(n) = e^{-n^2} are negligible. Non-examples include ε(n) = 1/n or ε(n) = 1/log n, which do not decay faster than every inverse polynomial.

Negligibility is related to, but stronger than, the basic idea of tending to zero. It provides a uniform way to bound small terms across all polynomial rates and is a standard tool for justifying the omission of tiny effects in theoretical analyses and practical designs.