# Roots of random polynomials.

Assume $P(x)$ is a random polynomial of degree $d$, where its coefficients are picked uniformly at random from $\mathbb{F}_p$, and $p$ is a large prime number. So the polynomial is defined over $\mathbb{F}_p$.

Question 1: What is the probability that polynomial $P(x)$ has at least one root?

Question 2: Are roots of $P(x)$ random values in $\mathbb{F}_p$?

• Where does this problem come from? Could you give a bit of context? – Dietrich Burde Mar 11 '18 at 19:53
• Useful(?) fact : there are $\frac 1n \sum_{d|n} p^d\mu(\frac nd)$ irreducible polynomials of degree $n$ over $F_p$. Here $\mu$ is the Möbius function. – krirkrirk Mar 11 '18 at 19:53
• Good question. I'll favorite it, hope to have a nice answer – Tal-Botvinnik Mar 11 '18 at 19:53
• I would say that the second question is true, because $P(x)$ and $P(x-x_0)$ for some $x_0$ should be indistinguishable. – Tal-Botvinnik Mar 11 '18 at 19:55
• @DietrichBurde The reason why I avoided giving more context was to keep it simple. Please see my following comments. In , it is said that $P(x)=R_1.f_1+R_2+f_2$ is a random polynomial where $R_i$ are random polynomials of degree $d$ and $f_i$ are arbitrary polynomials of degree $d$ too. The above approach is used to compute the intersection of two sets (each encoded as polynomial $f_i$). However, this approach introduces some error roots to the result (i.e. elements that are not encoded in $f_i$ but appear in the root of P(x)) . The reason is the use of random polynomials. – A researcher Mar 11 '18 at 20:03

## 1 Answer

Given $x \in \mathbb F_p$, the probability that a random polynomial of degree $d$ has $x$ as a root is $1/p$. Thus the expected number of roots of a random polynomial is $1$. Unfortunately these events are not independent, but we may speculate that for large $d$ and $p$ the number of roots is not too badly approximated by a Poisson distribution, which would say the probability of no roots is approximately $1/e$.

• Could you please elaborate on why this probability is $\frac 1p$ ? – krirkrirk Mar 11 '18 at 20:22
• Write the polynomial as $P(x) = \sum_{j=0}^d a_j x^j$. For any $x$ and any $a_1,\ldots,a_d$, there is exactly one value of $a_0$ that makes $P(x) = 0$. – Robert Israel Mar 11 '18 at 20:25
• Of course! Thanks. – krirkrirk Mar 11 '18 at 20:27
• thanks for the answer. Could you please clarify which part of your answer is related to which part of my question. Thanks again! – A researcher Mar 18 '18 at 16:45
• For what it's worth, this speculation is right: the distribution limits to Poisson (link.springer.com/content/pdf/10.1007/s11006-006-0139-y.pdf). – GMB Apr 8 '19 at 20:34