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$
1
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$
6
  • $\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$
-1
$\begingroup$

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.

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