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?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
5
This is false, take $f(x) = 2^{-2x}$ and $g(x) = 2^{-x}$.
-
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
