16
$\begingroup$

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

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ A somewhat related question: mathoverflow.net/questions/166068/… $\endgroup$
    – Marco Golla
    May 28, 2014 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, 2014 at 13:52
  • 2
    $\begingroup$ Are you interested in an asymptotic estimate? In lower/upper bounds? Exact values? $\endgroup$
    – Marco Golla
    May 28, 2014 at 14:36
  • $\begingroup$ @MarcoGolla An asymptotic estimate would be great. Thank you. $\endgroup$
    – Simd
    May 28, 2014 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$
    – user21349
    May 28, 2014 at 18:33

2 Answers 2

Reset to default
16
$\begingroup$

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$$

Improve this answer
$\endgroup$
2
  • $\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, 2014 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$
    – user21349
    May 29, 2014 at 20:42
13
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Multiply by $3^n$ and check on OEIS! $\endgroup$
    – Per Alexandersson
    May 28, 2014 at 19:10
  • 1
    $\begingroup$ Nothing comes on OEIS. $\endgroup$
    – Mayank Pandey
    May 28, 2014 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, 2014 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$
    – Simd
    Jun 2, 2014 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$
    – Simd
    Jun 3, 2014 at 9:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.