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

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

• You know that the cyclotomic polynomials can have arbitrarily large coefficients, right? I thought this would be an interesting fact, even though it doesn't really help. May 18, 2014 at 20:21
• The number of polynomials with these coefficients is $2\cdot 3^n$. I calculated how many of these have roots of unity for $n = 0, \dots, 9$ and the result is 0, 2, 6, 12, 58, 90, 420, 714, 3826, 5814 with probabilities 0, 1/3, 1/3, 2/9, 29/81, 5/27, 70/243, 119/729, 1913/6561, 323/2187 May 18, 2014 at 20:45
• @AleksVlasev You probably want to remove the sign of $x^n$ because it is kind of annoying in the computation, inducing factors of $2$ anywhere and not changing the probabilities. It also doubles uselessly the number of computer operations you have to do ;) May 18, 2014 at 20:46
• That's a good point. I just hacked something together haha. May 18, 2014 at 20:49
• I was just mentioning. May 18, 2014 at 20:50

## 2 Answers

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.

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.

• I think this looks more like $1/\sqrt{n}$.
– user138491
Jun 3, 2014 at 15:18