# Product of polynomial with negligible function is negligible

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) With $$z(n)=p(n)k(n)$$ $$\Rightarrow p(n)negl(n)

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

• What is "negligible" in your context? Nov 14 '21 at 16:35
• 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)$.
– 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) 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.