1
$\begingroup$

Suppose that $f\in\mathbb{F}_p[x]$ is a degree $d$ random univariate polynomial with coefficients from a finite field $\mathbb{F}_p$. What is the probability that $f$ can be written as: $$f(x)=\prod_{j=1}^d(x-\alpha_j),$$ for $\alpha_j\in\mathbb{F}_p$?


My heuristic guess: we have got $p^d$ different polynomials. I have also got $p$ options to choose $\alpha_1$, $p-1$ options for $\alpha_2$,..., and $p-d+1$ options for $\alpha_d$. Considering all possible rotations of $\alpha_j$, the probability is equal to: $\frac{p(p-1)\cdots(p-d+1)}{p^dd!}$. However it seems that I am missing roots with multiplicity larger than $1$. Any idea?

$\endgroup$
1
  • 2
    $\begingroup$ Stars and Bars lets you compute the number of combinations with repetition. $\endgroup$
    – lulu
    May 26, 2016 at 11:57

1 Answer 1

1
$\begingroup$

As lulu indicated in a comment, you need to count the number of combinations of roots with repetition. You have $d$ roots to distribute over $p$ bins; the number of ways to do this is $\binom{d+p-1}d$, so the probability is

$$ \frac{\binom{d+p-1}d}{p^d}\;. $$

For $d\ll p$ this is roughly $\frac1{d!}\frac1p$, so about a fraction $\frac1{d!}$ of all monic polynomials can be fully factored.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .