Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 http://math.stackexchange.com/questions/798082/probability-a-polynomial-has-a-root-which-is-a-root-of-unity

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

2 Answers 2

up vote 14 down vote accepted

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

share|improve this answer
    
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. –  Jon Peterson May 29 at 16:35
1  
@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$. –  Ben Crowell May 29 at 20:42
add comment

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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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