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?

Previously asked at https://math.stackexchange.com/questions/798082/probability-a-polynomial-has-a-root-which-is-a-root-of-unity

  • 1
    $\begingroup$ A somewhat related question: mathoverflow.net/questions/166068/… $\endgroup$ – Marco Golla May 28 '14 at 8:32
  • 6
    $\begingroup$ 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$. $\endgroup$ – fedja May 28 '14 at 13:52
  • 2
    $\begingroup$ Are you interested in an asymptotic estimate? In lower/upper bounds? Exact values? $\endgroup$ – Marco Golla May 28 '14 at 14:36
  • $\begingroup$ @MarcoGolla An asymptotic estimate would be great. Thank you. $\endgroup$ – dorothy May 28 '14 at 16:13
  • 1
    $\begingroup$ 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. $\endgroup$ – Ben Crowell May 28 '14 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$$

  • $\begingroup$ 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. $\endgroup$ – Jon Peterson May 29 '14 at 16:35
  • 1
    $\begingroup$ @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$. $\endgroup$ – Ben Crowell May 29 '14 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.

  • $\begingroup$ Multiply by $3^n$ and check on OEIS! $\endgroup$ – Per Alexandersson May 28 '14 at 19:10
  • 1
    $\begingroup$ Nothing comes on OEIS. $\endgroup$ – Mayank Pandey May 28 '14 at 19:34
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson May 29 '14 at 0:13
  • $\begingroup$ 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. $\endgroup$ – dorothy Jun 2 '14 at 19:05
  • 1
    $\begingroup$ The numerators should be $2,6,12,36,94,276,790,2270$ and not $2,6,12,35,94,275,789, 2267$. $\endgroup$ – dorothy Jun 3 '14 at 9:14

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.