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

  • $\begingroup$ Where does this problem come from? Could you give a bit of context? $\endgroup$ – Dietrich Burde Mar 11 '18 at 19:53
  • 2
    $\begingroup$ 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. $\endgroup$ – krirkrirk Mar 11 '18 at 19:53
  • 1
    $\begingroup$ Good question. I'll favorite it, hope to have a nice answer $\endgroup$ – Tal-Botvinnik Mar 11 '18 at 19:53
  • $\begingroup$ I would say that the second question is true, because $P(x)$ and $P(x-x_0)$ for some $x_0$ should be indistinguishable. $\endgroup$ – Tal-Botvinnik Mar 11 '18 at 19:55
  • $\begingroup$ @DietrichBurde The reason why I avoided giving more context was to keep it simple. Please see my following comments. In [1], 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. $\endgroup$ – Ay. Mar 11 '18 at 20:03

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

  • $\begingroup$ Could you please elaborate on why this probability is $\frac 1p$ ? $\endgroup$ – krirkrirk Mar 11 '18 at 20:22
  • 1
    $\begingroup$ 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$. $\endgroup$ – Robert Israel Mar 11 '18 at 20:25
  • $\begingroup$ Of course! Thanks. $\endgroup$ – krirkrirk Mar 11 '18 at 20:27
  • $\begingroup$ thanks for the answer. Could you please clarify which part of your answer is related to which part of my question. Thanks again! $\endgroup$ – Ay. Mar 18 '18 at 16:45
  • 1
    $\begingroup$ 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). $\endgroup$ – GMB Apr 8 '19 at 20:34

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.