# Probability a polynomial has a root which is a root of unity

Consider a degree $n$ polynomial $P(x)$ with coefficients $c_i \in \{-1,0,1\}$ chosen uniformly and independently.

What is the probability that $P(x)$ has a root which is a root of unity?

-
A somewhat related question: mathoverflow.net/questions/166068/… –  Marco Golla May 28 at 8:32
I do not have time for the full computation now, but let me still note that the probability that $1$ is a root is already of order $n^{-1/2}$ and that the number of cyclotomic polynomials of degree $d$ is at most $e^{Clog d\log\log d}$, so the probability that we have a root of some cyclotomic polynomial of degree $d$ is at most $e^{Clog d\log\log d}(1+c\frac nd)^{-d/2}$), which shows that we do not really need to bother much about anything except $\pm 1$ for large $n$. –  fedja May 28 at 13:52
Are you interested in an asymptotic estimate? In lower/upper bounds? Exact values? –  Marco Golla May 28 at 14:36
@MarcoGolla An asymptotic estimate would be great. Thank you. –  dorothy May 28 at 16:13
The question of whether $-1$ is a root of $P$ can be related to the question of whether $1$ is a root of the polynomial $P^*$ whose odd-$i$ coefficients have had their signs flipped. For large $n$, the probability that these two polynomials are distinct gets exponentially close to 1. For large $n$, the probability that both 1 and $-1$ are roots is small, so the probability that $\pm 1$ is a root is double the probability that 1 is a root. So taking into account fedja's comment, we just need to estimate the probability that 1 is a root. –  Ben Crowell May 28 at 18:33

As discussed in comments, I think for large $n$ the probability that it has a root which is a root of unity is double the probability that 1 is a root. For large $n$, $P(1)$ is a random variable whose distribution is approximately normal and whose variance is $\sigma^2=2n/3$. The probability that $P(1)=0$ is then approximately $1/\sigma\sqrt{2\pi}$. Doubling this gives a probability $\sqrt{3/\pi n}\approx 0.98 n^{-1/2}$. This seems to agree quite well with the final two values in Matt F.'s list:

$$\frac{263}{729}=0.361 \qquad \sqrt{\frac{3}{7\pi}}=0.369$$

$$\frac{2267}{6561}=0.346 \qquad \sqrt{\frac{3}{8\pi}}=0.345$$

-
Note that the probability that 1 is a root is equal to the probability that -1 is a root. This is easily seen by the fact that $P(1)$ and $P(-1)$ have the same distribution since the random coefficients $c_i$ are such that $-c_i$ has the same distribution as $c_i$. This explains why you would double the probability that 1 is a root in your above calculations. –  Jon Peterson May 29 at 16:35
@JonPeterson: The fact that these two probabilities are equal is not the same as saying doubling is correct. Some polynomials have both $1$ and $-1$ as roots, so the probability that one or the other is a root is less than double the probability that one is a root. However, as I argued in a comment, the probability that both are roots is small for large $n$. –  Ben Crowell May 29 at 20:42

I get $$\left\{\frac{2}{3},\frac{2}{3},\frac{4}{9},\frac{35}{81},\frac{94}{243},\frac{275}{729} ,\frac{263}{729},\frac{2267}{6561}\right\}$$

for the monic polynomials of degree 1 to 8, using Mathematica:

f[a_, b_] := a x^(b - 1)

PolysOfDegree[n_] := First /@ Table[ x^n + Plus @@
MapIndexed[f, IntegerDigits[i, 3, n] - 1], {i, 0, 3^n - 1}]

TestFactors[n_] := Table[FactorList[x^i - 1], {i, 1, 2 n + 2}]
// Flatten // Union // Rest

HasRootOfUnityAsRoot[poly_] := Or @@ Map[ PolynomialMod[poly , #] === 0 &,
TestFactors[Exponent[poly, x]]]

Prob[n_] := Count[Map[HasRootOfUnityAsRoot, PolysOfDegree[n]], True]/3^n

Table[Prob[n], {n,1,8}]


I've enumerated the polynomials of degree $n$, and enumerated the characteristic polynomials of roots of unity of degree up to $2n+2$. Then it's just a matter of testing which are divisible by which.

-
Multiply by $3^n$ and check on OEIS! –  Per Alexandersson May 28 at 19:10
Nothing comes on OEIS. –  Mayank Pandey May 28 at 19:34
I think the number of monic polynomials with 1 as a zero may be oeis.org/A005717 although the descriptions given there don't match this. –  Gerry Myerson May 29 at 0:13
I think HasRootOfUnityAsRoot has a bug. If we set $n=4$ then $x^4-x^2+1$ is the 12th cyclotomic polynomial but HasRootOfUnityAsRoot[x^4-x^2+1] returns False. –  dorothy Jun 2 at 19:05
The numerators should be $2,6,12,36,94,276,790,2270$ and not $2,6,12,35,94,275,789, 2267$. –  dorothy Jun 3 at 9:14