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

Question

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?

---

For a particular polynomial you can test the property by just seeing if it is divisible by $x^k-1$ for some $k$.

Answer 1

This is not meant to be an answer, it's more of a "too big comment", but you can use the following as a lower bound : we have $p(1) = 0$ if and only if $\sum_{i=0}^{n-1} c_i = -1$ (assuming $p(x) = x^n + \sum_{i=0}^{n-1} c_i$), and using a counting argument, you get $$ \mathbb P \ge \frac{ \sum_{d=0}^{\lfloor \frac{n-1}2 \rfloor} \binom{n}{d,d+1,n-2d-1}}{3^n}. $$

(you want $d$ of the $c_i$'s to have value $1$, $d+1$ of them to have the value $-1$ and the other ones $0$, $d$ ranging from $0$ to $\lfloor (n-1)/2 \rfloor$). You can compute this lower bound probably more explicitly if you use techniques from random walks, i.e. you want $\sum_{i=0}^{n-1} c_i = -1$, this is saying that the Markov chain starting at $0$ and doing steps of length $1$ in $\mathbb Z$ ends up at $-1$ after precisely $n$ steps.

This is only a lower bound because I only considered the root of unity $1$. You could get a bigger lower bound using similar techniques with $-1$ and maybe if you push a bit more with $i$ and $\frac{\pm 1 \pm \sqrt{-3}}2$, since these roots of unity generate lattices in $\mathbb C$ over which you can perform random walks. But this is going nowhere close to an answer, so it should be left aside.

I must admit the problem looks tough, I'm looking forward to a great answer.

Answer 2

I don't have an analytical answer, but empirically this can be answered for small $n$ and the probability appears to be decreasing exponentially.

Firstly, you make an incorrect assertion in the question:

For a particular polynomial you can test the property by just seeing if it is divisible by $x^k-1$ for some $k$.

Not so. The probability can be tested by seeing whether the polynomial has a non-trivial greatest common divisor with $x^k - 1$ for some $k$, or equivalently whether it is divisible by $\Phi_k$, the $k$^th cyclotomic polynomial.

Taking care to use a large enough $k$, I have calculated the following table

n    Exact probability   To 3 decimal places
1    2/3                 .667
2    6/9                 .667
3    12/27               .444
4    36/81               .444
5    94/243              .387
6    276/729             .379
7    790/2187            .361
8    2270/6561           .346
9    6412/19683          .326
10   18334/59049         .310
11   52616/177147        .297
12   152914/531441       .288
13   443728/1594323      .278
14   1290680/4782969     .270

The ratio of the probability for $(n+1)$-degree polynomials to the probability for $n$-degree polynomials appears never to exceed $1$; is easily shown to never be less than $\frac13$, and in practice seems to tend to about $0.97$. I would expect small perturbations when $n$ is a member of OEIS A002202, the values of the totient function, because that corresponds to the introduction of new cyclotomic polynomials to take into account.