1
$\begingroup$

I can use an example: the case where we have $x$ such that $f(x)=g(x)$. The quotient is $1$, a non-negligible function. However, we can't conclude that all functions $f(x)/g(x)$ are also negligible.

How can I formally prove this?

Improve this question
$\endgroup$
12
$\begingroup$

This is false, take $f(x) = 2^{-2x}$ and $g(x) = 2^{-x}$.

Improve this answer
$\endgroup$
5
  • 6
    $\begingroup$ This answer just appeared in the "low quality" review, probably because it's just one line. It is a perfectly viable counter example, but some extra information would be nice. $\endgroup$
    – tylo
    Nov 2 '16 at 13:46
  • 3
    $\begingroup$ @tylo I think the answer is fine as it is, thank you very much. $\endgroup$
    – fkraiem
    Nov 2 '16 at 14:28
  • 3
    $\begingroup$ @tylo: I agree with fraiem; he could use more words, but it is an effective counterexample $\endgroup$
    – poncho
    Nov 2 '16 at 14:45
  • 1
    $\begingroup$ Just to add: this counterexample actually comes up in real situations. In particular, when simulating constant-round zero-knowledge proofs (as in the Goldreich Kahan proof system). $\endgroup$
    – Yehuda Lindell
    Nov 2 '16 at 20:25
  • $\begingroup$ If two quantities go to zero at different rates their ratio can be made to diverge, just divide by the one going to zero faster. $\endgroup$
    – kodlu
    Nov 2 '16 at 22:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.