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
    Commented 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
    Commented May 28, 2014 at 13:52
  • 2
    $\begingroup$ Are you interested in an asymptotic estimate? In lower/upper bounds? Exact values? $\endgroup$
    – Marco Golla
    Commented May 28, 2014 at 14:36
  • $\begingroup$ @MarcoGolla An asymptotic estimate would be great. Thank you. $\endgroup$
    – Simd
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented May 28, 2014 at 19:10
  • 1
    $\begingroup$ Nothing comes on OEIS. $\endgroup$
    – Mayank Pandey
    Commented 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
    Commented 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
    Commented 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
    Commented Jun 3, 2014 at 9:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .