# What are not non-negligible functions?

I had a brief look at "On Defining Proofs of Knowledge" by Bellare and Goldreich and I am a little confused by their definitions.

I was under the impression a negligible function $$f$$ was defined as something like $$\forall\ polynomials\ p\ \exists k\ s.t.\ \forall x > k: f(x) < \frac{1}{p(x)}$$

And that non-negligible meant simply that it was not negligible. The paper however states: "Put in other words negligible is not the negation of non-negligible!" (p. 5) And this seems to be based on the definition "a non-negligible function in $$n$$ is a function which is asymptotically bounded from below by a function of the form $$n^{-c}$$ for some constant $$c$$" (p. 4) which I am losely translating as $$\exists\ polynomial\ p\ and\ k\ s.t.\ \forall x > k: f(x) > \frac{1}{p(x)}$$ With the difference being functions which are somehow alternating.

This is a bit of a weird question because the mathematics seem to be clear but I am confused by what the common usage is. And is this something that is generally important? I've never seen it discussed elsewhere.

• What they seem to be calling "non-negligible" (I can't check the ps file on mobile) is usually called "noticable" and the standard caution is that "non-negligible" (in the sense you used it) is not equivalent to "noticable". May 17 at 13:14
• See e.g. these lecture notes May 17 at 13:24
• May 17 at 13:30
• Yes, that is the problem with the negation of complex sentences. May 17 at 14:29

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

• Based on the comments, I've given a shot that our site has this written around... May 17 at 19:31
• This answer does not address the fact that the cited paper defines non-negligible differently. May 17 at 19:53
• @Maeher I'm aware of this. These definitions are the same as in Oded Goldreich's Foundations of Cryptography Volume I. So, I can say this is common usage as OP asked. If we consider the date of the article as '92 and the book as '01-03 we can say that this is common then ( Oded co-auther of the article and the sole author of the book) May 17 at 20:03