What are not non-negligible functions?

vn flag

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.

cn flag
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".
cn flag
[See e.g. these lecture notes](
cn flag
Or [page 9 of these](
kelalaka avatar
in flag
Yes, that is the problem with the negation of complex sentences.
in flag
  • 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$

kelalaka avatar
in flag
Based on the comments, I've given a shot that our site has this written around...
cn flag
This answer does not address the fact that the cited paper defines non-negligible differently.
kelalaka avatar
in flag
@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)

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.