# Negligible function defined as product of polynomial and a negligible function

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.

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$.

• 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$? Dec 26, 2017 at 20:02
• Well, if $f_(n) \le 1/p_1(n)q(n)$, what does that say about $f_2(n)$? Dec 26, 2017 at 23:35
• 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. Dec 27, 2017 at 3:09
• 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? Dec 27, 2017 at 19:38
• 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... Dec 28, 2017 at 1:24

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.

if we define f(n)*p(n) as a negligible function, that means that, lim(f(n) * p(n) * p(n)) = 0. This simplifies to lim(f(n) * 2p(n)) = 0, where we gain the constant of 2 to the original equation that we already know is negligible. Then, we can prove that a negligible function multiplied by a constant is still negligible: we can pull out the constant such that we have 2 * lim(f(n) * p(n)) = 0, then we divide both sides by 2 to get the original equation which we know is negligible.