# Are a uniformly random polynomial's roots are distributed uniformly in the field?

Assume we have a $\mathbb{F}_p$, where $p$ is a large prime (e.g. 128-bit value).

We define all polynomials over the field, and pick a polynomial,$P(x)$, of degree $d$, where the polynomials' coefficients are drawn uniformly random from the field.

Question: Are the roots of the polynomial, $P(x)$, distributed uniformly over the field?

or can we say that the polynomial's roots (if it has any) are uniformly random elements of the field?

• No, because some of the polynomials might be irreducible in $\Bbb{F}_p$ – Qwerty Jun 28 '16 at 11:17
• @Qwerty You mean they may not have any root at all? – user153465 Jun 28 '16 at 11:24
• Yes I mean that – Qwerty Jun 28 '16 at 11:30
• @Qwerty ok, I meant if it has any root, would the root be uniformly random element of the field. – user153465 Jun 28 '16 at 11:33

Think it in the reverse way; Say your field contains $n$ elements. Choose uniformly any number of value from the field, say $p_1,p_2,\cdots , p_k|k\le n$

It is sure that $P(x)=\prod\limits_{i=1}^k(x-p_i)\in\Bbb{F}[x]$

• Thanks, it raises two questions: (1) is $P(x)$ in your answer a uniformly random polynomial in the field? (2) is $P(x)$ in my question a uniformly random polynomial of the field. Or are they equivalent? – user153465 Jun 28 '16 at 11:44
• @user153465 As I said If you choose $P(x)$ first it can be either irreducible or may have roots. However for those that have roots, definitely they are uniformly distributed.And please upvote and accept if you liked my answer – Qwerty Jun 28 '16 at 11:49
• @Qwerty Your $P(x)$ is not distributed uniformly over all polynomials with $k$ roots. For instance, consider the polynomials $x^2$ and $x(x-1)$. Both polynomials should have the same probability of occurring. But there is only one way to get $x^2$ ($p_1=0, p_2=0$), while there are two ways of getting $x(x-1)$. ($p_1=0, p_2=1$ or $p_1=1, p_2=0$). – D Poole Jun 28 '16 at 12:42
• @DPoole I meant to say that the probability that 1 is a root= the probaility that 0 is a root= probability that any elemnt of $\Bbb{F}$ is a root – Qwerty Jun 28 '16 at 12:45
• @Qwerty Your random polynomial does have that property, but the random polynomial described in the comments to the OP is different than yours. In user153465's case, it is a polynomial whose coefficients are uniformly distributed conditioned on having at least one root. – D Poole Jun 28 '16 at 12:50

Conditioned on the number of roots being $k$, the roots are uniformly distributed over all multi-sets of $\mathbb{F}_p$ of size $k$.

Let $P(x)$ be a uniformly chosen polynomial chosen from $$\mathbb{P} := \{f(x) = x^d + a_1x^{d-1}+\ldots + a_{p-1} x + a_p: a_i \in \mathbb{F}_p, f(x)\text{ has at least one root in }\mathbb{F}_p\}.$$ Each polynomial of $\mathbb{P}$ can be uniquely decomposed into polynomials $$P(x) = R(x) \times Q(x),$$ where $R(x)$ is a monic polynomial which factors completely and $Q(x)$ is irreducible monic polynomial.

Let us condition on $Q(x) = Q_0(x)$ for some irreducible polynomial $Q_0(x)$ with degree $d', 0 \leq d' \leq d-1$. Now $R(x)$ is uniformly distributed over all polynomials of the form $$\prod_{i=1}^{d-d'} (x-\beta_i),$$ where $\beta_i \in \mathbb{F}_p$. Note that the $\beta_i$'s are not (necessarily) uniformly distributed here. For instance, if $d-d' = 2$ and $p=3$, then $R(x)$ is uniform over the 6 polynomials $\{x^2, x(x-1), x(x-2), (x-1)^2, (x-1)(x-2), (x-2)^2\}$. In general, there is a bijection between possible polynomials $R(x)$ and all multi-sets of $\mathbb{F}_p$ of $d-d'$ elements. There are ${p-1+d-d' \choose p-1}$ possible multisets here. Since $R(x)$ is uniform over these possible polynomials, we have that for all admissible $R_0(x)$ with corresponding solutions $A_0$ (with multiplicity) $$P(\text{roots of }P(x)=A_0 | Q = Q_0)=P(R(x) = R_0(x) | Q = Q_0) = \frac{1}{{p-1 + d-d' \choose p-1}}.$$ This implies that \begin{align*} P(\text{roots of }P(x)=A_0 | \text{deg}Q = d') &= \sum_{Q_0(x) \atop \text{deg}(Q_0)=d'} P(R(x) = R_0(x) | Q = Q_0) P(Q = Q_0| \text{deg}Q = d') \\&= \sum_{Q_0(x) \atop \text{deg}(Q_0)=d'} \frac{1}{{p-1 + d-d' \choose p-1}} P(Q = Q_0| \text{deg}Q = d') \\&= \frac{1}{{p-1 + d-d' \choose p-1}}. \end{align*} Therefore, conditioned on the number of roots, the multiset of roots is uniformly distributed over all multisets of $\mathbb{F}_p$ of the right size.

I would imagine that it would be harder to get the distribution of the number of roots of $P(x)$ though.