Considera un polinomio de grado $n$, $P(x)$, con coeficientes $c_i \in \{-1,0,1\}$ elegidos de forma uniforme e independiente.
¿Cuál es la probabilidad de que $P(x)$ tenga una raíz que sea una raíz de la unidad?
Pregunta previamente realizada en https://math.stackexchange.com/questions/798082/probability-a-polynomial-has-a-root-which-is-a-root-of-unity
Como se discutió en los comentarios, creo que para grandes $n$ la probabilidad de que tenga una raíz que sea una raíz de la unidad es el doble de la probabilidad de que 1 sea una raíz. Para grandes $n$, $P(1)$ es una variable aleatoria cuya distribución es aproximadamente normal y cuya varianza es $\sigma^2=2n/3$. La probabilidad de que $P(1)=0$ es entonces aproximadamente $1/\sigma\sqrt{2\pi}$. Duplicar esto da una probabilidad $\sqrt{3/\pi n}\approx 0.98 n^{-1/2}$. Esto parece coincidir bastante bien con los dos últimos valores en la lista de Matt F.:
$$\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$$
Ten en cuenta que la probabilidad de que 1 sea una raíz es igual a la probabilidad de que -1 sea una raíz. Esto se ve fácilmente por el hecho de que $P(1)$ y $P(-1)$ tienen la misma distribución ya que los coeficientes aleatorios $c_i$ son tales que $-c_i$ tiene la misma distribución que $c_i$. Esto explica por qué duplicarías la probabilidad de que 1 sea una raíz en tus cálculos anteriores.
@JonPeterson: El hecho de que estas dos probabilidades sean iguales no es lo mismo que decir que el duplicar sea correcto. Algunos polinomios tienen tanto $1$ como $-1$ como raíces, por lo que la probabilidad de que una u otra sea raíz es menor que el doble de la probabilidad de que una sea raíz. Sin embargo, como argumenté en un comentario, la probabilidad de que ambos sean raíces es pequeña para un gran $n$.
Obtengo $$\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\}$$
para los polinomios mónicos de grado 1 a 8, usando 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}]He enumerado los polinomios de grado $n$, y he enumerado los polinomios característicos de raíces de la unidad de hasta grado $2n+2$. Luego solo se trata de probar cuáles son divisibles por cuáles.
Creo que el número de polinomios mónicos con 1 como cero puede ser oeis.org/A005717, aunque las descripciones proporcionadas allí no coinciden con esto.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
1 votos
Una pregunta algo relacionada: mathoverflow.net/questions/166068/…
6 votos
No tengo tiempo para la computación completa ahora, pero aún así debo señalar que la probabilidad de que $1$ sea raíz ya es del orden de $n^{-1/2}$ y que el número de polinomios ciclotómicos de grado $d$ es a lo sumo $e^{Clog d\log\log d}$, por lo que la probabilidad de que tengamos una raíz de algún polinomio ciclotómico de grado $d$ es a lo sumo $e^{Clog d\log\log d}(1+c\frac nd)^{-d/2}$), lo que muestra que realmente no necesitamos preocuparnos mucho por nada excepto $\pm 1$ para $n$ grande.
2 votos
¿Estás interesado en una estimación asintótica? ¿En límites inferiores/superiores? ¿Valores exactos?
0 votos
@MarcoGolla Un estimado asintótico sería genial. Gracias.
1 votos
La pregunta de si $-1$ es una raíz de $P$ puede estar relacionada con la pregunta de si $1$ es una raíz del polinomio $P^*$ cuyos coeficientes de $i$ impar han tenido sus signos cambiados. Para valores grandes de $n$, la probabilidad de que estos dos polinomios sean distintos se acerca exponencialmente a 1. Para valores grandes de $n$, la probabilidad de que tanto 1 como $-1$ sean raíces es pequeña, por lo que la probabilidad de que $\pm 1$ sea una raíz es el doble de la probabilidad de que 1 sea una raíz. Teniendo en cuenta el comentario de fedja, solo necesitamos estimar la probabilidad de que 1 sea una raíz.
0 votos
@Fedja, ¿de dónde proviene la estimación $(1+c/n)^{-d/2}$? ¿Se cumple para $d=d(n)$?
0 votos
@ofer zeitouni Cada $d$ potencia consecutiva de la raíz son linealmente independientes sobre $\mathbb Q$ y para variables aleatorias simétricas independientes (vectoriales), tenemos $P(X+Y=0)\le\sqrt{P(X+X'=0)P(Y+Y'=0)}$, etc. ($Z'$ es una copia independiente de $Z$, y asumo que la diferencia entre la fórmula en tu comentario y la mía es solo un error tipográfico de tu parte).
0 votos
@fedja sí, fue un error tipográfico de mi parte. Y gracias por el argumento.