I want to prove that for every positive polynomial $p(n)$ and any negligible function $negl(n)$ the product $negl(n)p(n)$ is also negligible.

This is what I tried so far:

$\forall n>n_0:negl(n)<1/k(n),k=$any positive polynomial. $\Rightarrow p(n)negl(n)<p(n)1/z(n) $ With $z(n)=p(n)k(n)$ $\Rightarrow p(n)negl(n)<p(n)1/z(n)=p(n)\frac{1}{p(n)k(n)}=1/k(n)$

Question : I am not sure if I am allowed to substitute $z(n)$ with the product of $p(n)$ and $k(n)$.

  • $\begingroup$ What is "negligible" in your context? $\endgroup$
    – nir shahar
    Nov 14 '21 at 16:35
  • $\begingroup$ A function $f(n)$ is negligible if for any $n>n_0 \in N$ $f(n)$ is smaller then $1/p(n)$ for any positive polynomial $p(n)$. $\endgroup$
    – UniX
    Nov 14 '21 at 16:39

You are allowed, but you have to make sure to keep it formal.

The property of $negl$ guarantees you that $\exists n_0 : \forall n>n_0: negl(n)<\frac{1}{p(n)k(n)}$ for some polynomial $k(n)$.

Now, for any $n>n_0$, you know that this holds and thus $p(n)negl(n)<p(n)\frac{1}{p(n)k(n)}=\frac{1}{k(n)}$ if $p(n)$ is positive (it will be for all $n>n_1$ for some $n_1$).

Thus, for all $n>\max\{n_0,n_1\}$, we know that $p(n)negl(n)<\frac{1}{k(n)}$ and by definition we get that $p(n)negl(n)$ is also negligible.


We have $negl(n)$ as a negligible function, then by definition, it is smaller than the inverse of any polynomial, for all sufficiently large $n$. In particular, given any polynomial $q(n)$, $negl(n)$ is smaller than $1/(p(n) \cdot q(n))$

$$negl(n) <1/(p(n) \cdot q(n)) $$ Now, we have

$$negl(n)p(n) < q(n).$$

Limit definition also easy to use;

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

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

Now, we need to show that for every $q(n)$, $negl(n)p(n)$ is negligible;

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

This is true; since $negl(n)$ is negligible implies for every polynomial;

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


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.