Is this statement $\operatorname{negl}_1(n)-\operatorname{negl}_2(n)\leq \operatorname{negl}_3(n)$ true for some negligible function $\operatorname{negl}_3$ and security parameter $n$?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
$\newcommand{\negl}{\operatorname{negl}}$ \begin{align} \negl_1(n)-\negl_2(n)&\leq \left|\negl_1(n)-\negl_2(n)\right|\\ &\leq\left|\negl_1(n)+\negl_2(n)\right|\\ &=\negl_1(n)+\negl_2(n)\\ &\leq \negl_3(n) \end{align}
where the last statement uses the fact that the sum of two negligible functions is negligible and the rest uses the fact that $\negl_1(n)\geq0$ and $\negl_2(n)\geq0$. For a proof of the last inequality, see this lecture on one-way functions and negligble functions (PDF).