What is the probability of a polynomial with integer coefficients has rational roots?

346 Views Asked by At

What is the probability of a polynomial with integer coefficients has rational roots? For some reason I feel like the probability of having rational roots assuming the coefficients are random integers would get smaller as the degree goes up.

Degree 1: $ax+b=0$ always has 1 rational root

Degree 2: $ax^2+bc+c=0$ has rational root(s) if $b^2-4ac$ is a perfect square (side question: do we consider $0$ to be a perfect square since $0^2=0$)?

Degree 3: $ax^3+bx^2+cx+d=0$ I can't say much for this case but I know Cardano's formula has a lot of radicals (and nested radicals!)

Anyone know any results/theorems in this direction?

1

There are 1 best solutions below

2
On BEST ANSWER

This is not an answer to the question as stated, just a very long comment. There are issues with making this question rigorous over $\mathbb{Z}$ but it is completely rigorous if we work $\bmod p$ for a prime $p$ and I thought it would be interesting to describe what the answer is in this setting. After that I'll try to say some things about the integer case.

For simplicity I'll work with monic polynomials only but this doesn't affect the answer. There are $p^n$ monic polynomials of degree $n$ over $\mathbb{F}_p$. We can ask: what is the probability that a random such polynomial has no roots in $\mathbb{F}_p$? This is equivalent to not being divisible by any $x - a, a \in \mathbb{F}_p$. It turns out that the events of being divisible by $x - a$ and $x - b, a \neq b$ are all independent as long as $n \ge p$, which gives that if $n \ge p$ then the probability that a polynomial has no roots in $\mathbb{F}_p$ is $\boxed{ \left( \frac{p-1}{p} \right)^p }$. As $p \to \infty$ this converges to $\boxed{ e^{-1} }$, so we get that for large primes $p$ and polynomials of large degree $n \ge p$ about $36.7\%$ of monic polynomials have no roots $\bmod p$.

(This should be compared to a standard result for permutations: for large $n$ the probability that a random permutation in $S_n$ has no fixed points also converges to $\frac{1}{e}$, so is also about 36.7%. The relationship between these two comes from thinking about the Frobenius map acting on the roots of a random polynomial as a random permutation.)

However, this requires that we take the degree to be $n \ge p$. What we'd like to be able to do is fix the degree $n$ while taking $p$ to be arbitrary. This makes the calculations more complicated, but skipping over the details either inclusion-exclusion or a generating function argument using the cyclotomic identity can be used to show that if $a_n$ is the number of monic polynomials of degree $n$ with no roots in $\mathbb{F}_p$ then

$$a_{p, n} = \sum_{i=0}^{\text{max}(p, n)} (-1)^i {p \choose i} p^{n-i}$$

so the probability that a random monic polynomial of degree $n$ has no roots in $\mathbb{F}_p$ is given by dividing this by $p^n$. For example, for $n = 2$ the probability is

$$\frac{a_{p, 2}}{p^2} = {p \choose 2} p^{-2}$$

which as $p \to \infty$ converges to $\boxed{ \frac{1}{2} }$; that is, about 50% of monic quadratic polynomials $\bmod p$ don't have a root $\bmod p$. This can be motivated heuristically as follows: we want to know the probability that the discriminant is not quadratic residue, and if the discriminant behaves randomly then about half of $\mathbb{F}_p$ consists of quadratic residues, so it's not a quadratic residue about half the time.

For $n = 3$ the probability (for $p \ge 3$) is

$$\frac{a_{p, 3}}{p^3} = {p \choose 2} p^{-2} - {p \choose 3} p^{-3}$$

which as $p \to \infty$ converges to $\frac{1}{2} - \frac{1}{6} = \boxed{ \frac{1}{3} }$; that is, about 33.3% of monic cubic polynomials $\bmod p$ don't have a root $\bmod p$. If someone has a nice idea for how to motivate this I'd like to hear it.

In general, as $p \to \infty$, the probability $\frac{a_{p, n}}{p^n}$ converges to $\boxed{ \sum_{i=0}^n \frac{(-1)^i}{i!} }$, which itself as $n \to \infty$ converges to $e^{-1}$ as above. But note that this time we know what happens when $n$ is fixed, and in particular we do not need to take $n \ge p$ as above. (This is also exactly the probability that a random permutation in $S_n$ has no fixed points!)


The difficulty with trying to even state this question precisely over $\mathbb{Z}$ is that it's not at all clear how one ought to construct a "random" polynomial over $\mathbb{Z}$. Setting aside the formal issue that countable sets don't admit uniform probability distributions, you might try to choose each coefficient randomly in some interval $[-N, N]$, then ask for the asymptotic probability that a random such polynomial does or doesn't have roots as $N \to \infty$.

But there's an issue here: why insist that each coefficient go to infinity at the same rate? There are some fascinating things known about the complex roots of polynomials chosen randomly as above for small values of $N$ (maybe for large $N$ too, who knows), but choosing the coefficients to all be similar size forces the complex roots to exist in a fairly narrow range; I think they end up near the unit circle with high probability although I don't know how to make this precise. Other ways of choosing a random polynomial, e.g. taking the characteristic polynomial of a random matrix, produce different distributions on the coefficients and on the roots. For example, for a large positive integer $N$ you could choose the $k^{th}$ coefficient uniformly in the interval $\left[ - N^k {n \choose k}, N^k {n \choose k} \right]$; the motivation for this is that this is the bound implied by requiring all the roots to have absolute value $\le N$. With this distribution the coefficients go to infinity at quite different rates and the distribution over roots, including integer roots, is likely to be different as a result.

Anyway, I expect the probability that a polynomial of degree $n \ge 2$ has a rational root to go to $0$ as $N \to \infty$ regardless of what choices you make, but the rate at which the probability goes to $0$ may depend a lot on the choices. This can be numerically investigated and if anyone wants to do so I'd be quite interested to see the results!

Edit: For some background on the distribution of the complex zeroes of random polynomials you can see, for example, this post by Terence Tao. The answer depends on how you choose to scale the coefficients relative to each other as expected and there are three scalings typically investigated in the literature; you can look at the post for details.

I think the classical results quoted there imply that if we choose the coefficients uniformly in $[-N, N]$ then the roots end up close to uniformly distributed around the unit circle, at least as $n \to \infty$, and also that very few of the roots are even real, let alone rational. But the classical results seem to concern the $n \to \infty$ limit while the coefficient distribution is fixed, so I don't know how much they tell us about the situation where $n$ is fixed but the coefficient distribution varies.