# Exercise 3.1

### Problem

Prove Proposition 3.6.

> **PROPOSITION 3.6** Let $$negl\_1$$ and $$negl\_2$$ be negligible functions. Then, 
>
> 1. The function $$negl\_3$$ defined by $$negl\_3(n) = negl\_1(n)+negl\_2(n)$$ is negligible. 
> 2. For any positive polynomial $$p$$, the function $$negl\_4$$ defined by $$negl\_4(n) = p(n) · negl\_1(n)$$ is negligible.

### Solution

#### Part 1

Since $$negl\_1$$ is a negligible function, for any positive polynomial $$p$$, there exists an $$N\_1$$ such that 

$$
\forall n > N\_1, negl\_1(n) < \frac{1}{p(n)}
$$

Similarly, there exists an $$N\_2$$ such that

$$
\forall n > N\_2, negl\_2(n) < \frac{1}{p(n)}
$$

Thus for any positive polynomial $$p$$, there exists $$N > \max(N\_1, N\_2)$$ such that&#x20;

$$
\forall n > N, negl\_1(n) < \frac{1}{2p(n)}, negl\_2(n) < \frac{1}{2p(n)}
$$

Hence,&#x20;

$$
\forall n>N, negl\_3(n) = negl\_1(n)+negl\_2(n) < \frac{2}{2p(n)} = \frac{1}{p(n)}
$$

Therefore $$negl\_3$$ is also negligible.

#### Part 2

Assuming that $$negl\_4$$ is not negligible. That is, exists a integer $$c > 0$$ such that&#x20;

$$
\forall n > 0, negl\_4(n) = p(n)\cdot negl\_1(n) \geq \frac{1}{n^c} \Rightarrow negl\_1(n) \geq \frac{1}{p(n)\cdot n^c}
$$

Since $$p$$ is a polynomial, $$p'(n) = p(n)\cdot n^c$$ is also polynomial. That is there exists a positive polynomial $$p'(n)$$ such that&#x20;

$$
\forall n > 0, negl\_1(n) \geq \frac{1}{p'(n)}
$$

Which is converse to $$negl\_1$$ is negligible.

Therefore $$negl\_4$$ is negligible.