Roots of a random polynomial!

Let $Z_k$ be a random variable which is equal to $1$ if $k$ is a root of the polynomial $P(x)$ , and $0$ otherwise. Hence the number of roots ( $N$ ) of a random polynomial $P(x)$ may be conveniently expressed as $N=\sum_{k=0}^{p-1}Z_k$ . Taking expectation of both sides and using the linearity property of the expectation, we have $\mathbb{E}N=\sum_{k=0}^{p-1}\mathbb{E}Z_k=\sum_{k=0}^{p-1}\mathbb{P}(Z_k=1)$ . Now we will evaluate each of the above probabilities.

Note that $k \in \mathbb{Z}_p$ is a root of the polynomial (i.e. $Z_k=1$ ), if and only if $c_0=-(c_1k+c_2k^2+ \ldots +c_d k^d) \mod(p)$ . Let us now fix a realization of the coefficients $\{c_1,c_2, \ldots, c_d\}$ . Hence the right hand side of the above equation is a fixed number in the set $\mathbb{F}_p$ . Since $c_0$ is chosen independently and uniformly at random from the set $\mathbb{F}_p$ , probability that $Z_k=1$ conditional on that realization of $\{c_1,c_2, \ldots, c_d\}$ is the same as the probability that the random variable $c_0$ is equal to the right hand side. Since $c_0$ is independent of every other coefficients, this conditional probability is simply $\frac{1}{p}$ . Since this probability is independent of the particular realization of $\{c_1,c_2, \ldots, c_d\}$ , we have $\mathbb{P}(Z_k=1)=\frac{1}{p}$ , for all $k\in \mathbb{Z}_p$ . Thus we have $\mathbb{E}N=p \times \frac{1}{p}=1\hspace{10pt} \blacksquare$ .

An elementary way to rewrite Abhishek's proof is to write out the sample space with $p^d$ points (all possible co-efficient vectors). And then we observe that $P(x+a) (mod p)$ is another polynomial in the sample space for every 'a' in the field. Further, the map $P(x) \to P(x+a)$ is a bijection. It is simple to see that $0$ is a root for $p^{d-1}$ points in the sample space. Using the bijection, we infer that every element of the field is a root for $p^{d-1}$ points in the sample space. Therefore, we totally have $p^d$ roots for $p^d$ polynomials. This means on an average we have 1 root per polynomial.