1
$\begingroup$

How do I prove that a function $f_2$, defined as the product of a negligible function $f_1$ and a polynomial $p$, is itself negligible?

$$f_2(n)= p_1(n)f_1(n)$$

I see $f_2$ as negligible simply because I know that if you have something that has a negligible probability of happening $(f_1)$ then if you try a polynomial number of times $(p)$ we are still left with a negligible result. But I do not know how to prove this. I would appreciate if someone could point me in the right direction.

I have had a look here in particular the proof for the second Lemma, I think my question is related to the necessity part of the proof, but it seems to have confused me more than it helped.

$\endgroup$
2
$\begingroup$

Since $f_1$ is negligible, it is smaller than the inverse of any polynomial, for all sufficiently large $n$. In particular, given any polynomial $q$, it is smaller than $1/p_1q$.

$\endgroup$
  • $\begingroup$ You have stated the definition of a negligible function which I understand, would you mind expanding on the second part of your answer? Why exactly are you modifying $p$ with a second polynomial $q$, and therefore coming up with the inverse you show. I know $f_1$ is still negligible (smaller than the inverse) but how is that showing that so is $f_2$? $\endgroup$ – Nooby Dec 26 '17 at 20:02
  • $\begingroup$ Well, if $f_(n) \le 1/p_1(n)q(n)$, what does that say about $f_2(n)$? $\endgroup$ – fkraiem Dec 26 '17 at 23:35
  • $\begingroup$ And I introduce the second polynomial $q$ because what we want to show is that $f_2$ is smaller than the inverse of any polynomial; I call this polynomial $q$, you can call it however you want. $\endgroup$ – fkraiem Dec 27 '17 at 3:09
  • $\begingroup$ Yes so $f_2(n) < 1/p_1(n)q(n)$, I saw this and it seems to confirm it somehow (second part of question "b"). Similar to what you did here, this person adds $p(n)$ to $q(n)$, but is left only with $1/q(n)$. Why is $f_2(n) < 1/p_1(n)q(n)$ not a sufficient answer? $\endgroup$ – Nooby Dec 27 '17 at 19:38
  • $\begingroup$ It is $f_1$ that is smaller than $1/p_1q$, not $f_2$. It seems you are also a newbie in mathematics in general... $\endgroup$ – fkraiem Dec 28 '17 at 1:24
0
$\begingroup$

Based on limit definition;

$f_1(n)$ is negligible than for every polynomial $q(n)$ we have;

$$\lim_{n \rightarrow \infty} q(n) f_1(n) =0$$

We need to show that for every $q(n)$, $f_2(n)$ is negligible;

$$\lim_{n \rightarrow \infty} q(n) f_2(n) = \lim_{n \rightarrow \infty} q(n) [p_1(n) f_1(n)] =0$$

This is true; since $f_1(n)$ is negligible implies for any polynomial;

$$\lim_{n \rightarrow \infty} [q(n) p_1(n)] f_1(n) =0,$$ where $q(n) p_1(n)$ is a polynomial.

$\endgroup$

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.