What are not non-negligible functions?

• Negligible Function: A function $\mu$ is negligible iff $\forall c \in N \;\; \exists n_0 \in N$ such that $\forall n \geq n_0, \mu(n) < n^{−c}.$

  As we generally now, a negligible function is smaller than any polynomial. We have also an equivalent limit definition;

  $f(n)$ is negligible than for every polynomial $q(n)$ we have;

  $$\lim_{n \rightarrow \infty} q(n) f(n) =0$$

  The easy examples are the $2^{-n},2^{-\sqrt{n}}, \text{ and } n^{- \log n}$.

• Non-Negligible Function:^* a function $\mu(n)$ is non-negligible iff $\exists c \in N$ such that $\forall n_0 \in N, \exists n \geq n_0$ such that $\mu(n) \geq n^{-c}.$

  To be non-negligible, only one candidate is enough to show that $n \geq n_0$ for which $\mu(n) \geq n^{-c}$.

• Noticeable Function: A function $\mu$ is noticeable iff $\exists c \in N, n_0 \in N$ such that $\forall n \geq n_0, \mu(n) \geq n^{-c}.$

  As we can see, the difference from non-negligibility is; for all $n \geq n_0$

  An example is $n^{-3}$ which is only polynomially slow ( like any polynomial)

  Weak One-Way Functions are defined on noticeable functions.

Interleaving is the key to generating distinguishing examples. Take any noticeable and negligible function and interleave them;

$$\mu(n) = \cases{ 2^{-n} & : $x$ is even \\ n^{-3} & : $x$ is odd}$$

$\mu$ is a non-negligible and non-noticeable function!.

_{^*Quantifiers negation: In the negation $\neg\forall = \exists$ and $\neg \exists = \forall$}