Negligible function

In mathematics, a negligible function is a function

μ

:

N

→

R

{\displaystyle \mu :\mathbb {N} \to \mathbb {R} }

such that for every positive integer c there exists an integer Nc such that for all n > Nc,

|

μ

(

n

)

|

<

1

n

c

.

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

Equivalently, the following definition may be used.

A function

μ

:

N

→

R

{\displaystyle \mu :\mathbb {N} \to \mathbb {R} }

is negligible, if for every positive polynomial poly(·) there exists an integer Npoly > 0 such that for all n > Npoly

|

μ

(

n

)

|

<

1

poly

⁡

(

n

)

.

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

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 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

R

{\displaystyle \mathbb {R} }

):

(Continuous function) A function

f

:

R

→

R

{\displaystyle f:\mathbb {R} {\rightarrow }\mathbb {R} }

is continuous at

x

=

x

0

{\displaystyle x=x_{0}}

if for every

ε

>

0

{\displaystyle \varepsilon >0}

, there exists a positive number

δ

>

0

{\displaystyle \delta >0}

such that

|

x

−

x

0

|

<

δ

{\displaystyle |x-x_{0}|<\delta }

implies

|

f

(

x

)

−

f

(

x

0

)

|

<

ε

.

{\displaystyle |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

=

∞

{\displaystyle x_{0}=\infty }

with

f

(

x

0

)

=

0

{\displaystyle f(x_{0})=0}

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

(Infinitesimal) A continuous function

μ

:

R

→

R

{\displaystyle \mu :\mathbb {R} \to \mathbb {R} }

is infinitesimal (as

x

{\displaystyle x}

goes to infinity) if for every

ε

>

0

{\displaystyle \varepsilon >0}

there exists

N

ε

{\displaystyle N_{\varepsilon }}

such that for all

x

>

N

ε

{\displaystyle x>N_{\varepsilon }}

|

μ

(

x

)

|

<

ε

.

{\displaystyle |\mu (x)|<\varepsilon \,.}

Next, in the discrete setting where the domain is restricted to natural numbers

n

∈

N

{\displaystyle n\in \mathbb {N} }

, we replace

ε

>

0

{\displaystyle \varepsilon >0}

by the functions

1

/

n

c

{\displaystyle 1/n^{c}}

where

c

>

0

{\displaystyle c>0}

or by

1

/

poly

⁡

(

n

)

{\displaystyle 1/\operatorname {poly} (n)}

where

poly

⁡

(

n

)

{\displaystyle \operatorname {poly} (n)}

is a positive polynomial.