2
$\begingroup$

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?

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

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]$

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user153465 Jun 28 '16 at 11:44
  • $\begingroup$ @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 $\endgroup$ – Qwerty Jun 28 '16 at 11:49
  • $\begingroup$ @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$). $\endgroup$ – D Poole Jun 28 '16 at 12:42
  • $\begingroup$ @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 $\endgroup$ – Qwerty Jun 28 '16 at 12:45
  • $\begingroup$ @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. $\endgroup$ – D Poole Jun 28 '16 at 12:50
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.