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$
  • 2
    $\begingroup$ Stars and Bars lets you compute the number of combinations with repetition. $\endgroup$ – lulu May 26 '16 at 11:57
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$

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.