Es más probable que la raíz máxima de un polinomio aleatorio con coeficientes reales sea real que compleja

• Los polinomios aleatorios con coeficientes reales, independientes y con distribución uniforme, tienen en total apenas alrededor de 2log n/π raíces reales, pero en experimentos aparece una mayor probabilidad de que la raíz de mayor/menor valor absoluto sea real.
• En 10^5 simulaciones de Monte Carlo por cada grado, esta probabilidad baja hacia alrededor de 1/2 a medida que crece n, y se observa algo similar incluso al escalar coeficientes con distribución normal a (-1,1).
• Una respuesta plantea que el problema de las raíces extremas en grado finito converge al problema de preguntar si la raíz más pequeña de la serie de potencias aleatoria P(x)=a₀+a₁x+a₂x²+… es real.
• Según la distribución, el valor límite puede cambiar: para la uniforme en [-1,1] es cerca de 51%, para la normal estándar cerca de 52%, para una normal con varianza 1/k! es 62%, y para la distribución discreta ±1 parece estar en los bajos 40%.
• El autor de la respuesta duda de la interpretación de que “converge a 1/2” y, con 40 mil experimentos comparando grados 200 y 300, ve muy probable que el límite sea mayor que 50%.

---

Planteamiento del problema: hay pocas raíces reales, pero las extremas se inclinan hacia lo real

• En polinomios aleatorios con coeficientes reales, el número de raíces reales es mucho menor que el de raíces complejas.
  • Si los coeficientes siguen de manera independiente una distribución uniforme en (-1,1), el número de raíces reales de un polinomio de grado n es asintóticamente 2log n/π + o(1).
  • El número de raíces complejas es aproximadamente n - 2log n/π.
  • Según el artículo enlazado, una fórmula asintótica parecida también vale para otras distribuciones de coeficientes.
• Aquí, “raíz más grande” y “raíz más pequeña” se refieren respectivamente a la raíz con mayor valor absoluto y la raíz con menor valor absoluto.
• Si hay muchas menos raíces reales, parecería natural que las raíces extremas también fueran complejas, pero los datos experimentales del autor muestran lo contrario.

Observaciones de Monte Carlo y pregunta abierta

• Los datos observados apuntan a tres ideas principales:
  • La probabilidad de que la raíz más grande o la más pequeña sea real es mayor que la de que sea compleja.
  • Esa probabilidad parece bajar hacia un valor cercano a 1/2 a medida que crece n.
  • Para cada valor de n se hicieron 10^5 simulaciones de Monte Carlo.
• También se indica que, si en vez de usar distribución uniforme se toman coeficientes de una normal de media 0 y desviación estándar 1 y luego se escalan a (-1,1), se mantiene la misma observación y la misma probabilidad límite.
• La pregunta se reduce a dos puntos:
  • Por qué la raíz más grande y la más pequeña se sesgan hacia ser reales.
  • Si para grado n esa probabilidad converge a un valor cercano a 1/2 cuando n→∞.
• El sesgo observado puede expresarse con probabilidades condicionales así:
  • P(L|R)=P(S|R)≈π/(4log n)
  • P(L|C)=P(S|C)≈π/(2nπ-4log n)

Actualización: demostración de una cota inferior y experimento adicional con n=1000

• En la publicación enlazada de Math StackExchange se demuestra que la probabilidad de que la raíz más grande sea real es al menos:
  • (23-16√2)/6 ≈ 6.2%
• Una actualización del 11 de mayo de 2024 agrega el resultado de casi 60,000 experimentos para polinomios de grado n=1000.
  • El resultado es consistente con la gráfica observada para n≤125.
  • Se menciona que, al aumentar el número de ensayos, la probabilidad de que la raíz más grande sea real muestra una tendencia descendente, lo que sugiere una posible convergencia a 1/2.

Respuesta: conexión con la raíz más pequeña de una serie de potencias aleatoria

• Con base en Math StackExchange y en la entrada del blog Thurston, Selberg, and random polynomials Part II, se propone que, para distribuciones de coeficientes adecuadas, el límite de grado finito lleva al problema de la raíz más pequeña de una serie de potencias aleatoria:
  • P(x)=a₀+a₁x+a₂x²+…
  • El límite de la probabilidad de que la raíz más pequeña sea real, en grado finito, sería la probabilidad de que la raíz más pequeña de esta serie de potencias aleatoria sea real.
• Se afirma que usando el teorema de Rouché puede verse fácilmente que esta probabilidad es mayor que 0 y menor que 1.
• El valor límite puede depender de la distribución de los coeficientes aᵢ:
  • Si aᵢ sigue la uniforme en [-1,1], es alrededor de 51%.
  • Si sigue una Gaussian de media 0 y varianza 1, es alrededor de 52%.
  • Si es Gaussian pero con varianza 1/k!, es alrededor de 62%.
  • Si sigue la distribución discreta en 1 y -1, parece quedar en los bajos 40%.
• Por tanto, más que decir que “en todos los casos razonables es mayor que 50%”, lo correcto sería que según el modelo puede ser mayor o menor que 50%.

Por qué las raíces extremas pueden ser reales aunque haya pocas raíces reales

• En muchos modelos, las raíces tienden a concentrarse alrededor del disco unitario y su distribución angular tiende a ser uniforme; además, en escalas muy locales aparece repulsión entre raíces.
• Las raíces complejas pueden repartirse alrededor del borde del disco unitario, pero la repulsión entre raíces reales tendería a “forzarlas” a ser más pequeñas o más grandes.
• Desde esta perspectiva, aunque el número total de raíces reales sea solo logarítmico, todavía podría haber suficientes raíces reales para ocupar la raíz más pequeña o la más grande.
• La tarea pendiente es convertir estos valores, fáciles de estimar por Monte Carlo, en estimaciones numéricas rigurosas.

Idea para construir una estimación rigurosa con el teorema de Rouché

• Suponiendo coeficientes uniformes aᵢ∈[-1,1], se propone dividir el espacio de coeficientes de polinomios de bajo grado en pequeñas cajas.
  • Como ejemplo, se menciona dividir cada aᵢ en 1000 intervalos del mismo tamaño para polinomios de grado menor que 100.
  • En la respuesta se indica que eso produce en total 100^1000 polinomios.
• Desde la perspectiva de Monte Carlo, se esperaría poder clasificar la mayoría de los polinomios en dos conjuntos:
  • Aquellos cuya raíz más pequeña es real y tiene valor absoluto menor que 9/10.
  • Aquellos cuyas dos raíces más pequeñas forman un par complejo conjugado y tienen valor absoluto menor que 9/10.
• En ambos casos, si sobre la frontera de un disco que contenga solo esas raíces se prueba que |P| > (9/10)^100, el teorema de Rouché garantiza que se conserva la naturaleza de la raíz más pequeña.
• El enfoque no tendría obstáculos teóricos, pero la carga computacional puede ser demasiado grande, así que quizá haría falta trabajar con grados menores que 10 y alrededor de 10^10 polinomios, o encontrar una partición más eficiente.

Objeción a la interpretación de convergencia a 1/2 y cálculos adicionales

• El autor de la respuesta considera poco convincente la interpretación del autor de la pregunta de que “probablemente converge a 1/2”, y usa como contraargumento que otros modelos naturales y simétricos no convergen a 1/2.
• Al generar 1000 polinomios aleatorios de grado 500 y revisar el valor absoluto de la raíz más pequeña, en todos los casos fue menor que 0.91.
  • Al extender esto a una serie de potencias aleatoria, se indica que la variación de la función dentro del disco |z|<0.91 es del orden de 10^-20 o menor.
  • Para que no aplique el teorema de Rouché, haría falta que la raíz más pequeña, o el par complejo conjugado correspondiente, estuviera extremadamente cerca de la siguiente raíz en términos de valor absoluto.
• Para estimar mejor la tasa de convergencia se propone el siguiente experimento:
  • Calcular 50,000 polinomios aleatorios de grado 500.
  • Calcular 50,000 polinomios extendidos a grado 1000 manteniendo los mismos términos iniciales.
  • Verificar en ambos grados si la raíz más pequeña es real y con qué frecuencia cambia su naturaleza al aumentar el grado.
• La intuición del autor es que al pasar de grado 500 a 1000 los cambios deberían ser muy raros.
  • Si ambos valores están cerca de 51% y la tasa de cambio es mucho menor que 1%, eso sería una señal de que el límite es estrictamente mayor que 50%.

Experimento comparativo real: grados 200 y 300

• Como los cálculos para grados mayores tardaban demasiado, la comparación real se hizo con grados 200 y 300.
• Resultado de ejecutar 40,000 polinomios:
  • En 20,287 de los polinomios de grado 200, la raíz más pequeña era real.
  • Al extender esos mismos polinomios a grado 300, en todos los casos se conservó esa misma propiedad.
• Este resultado sugiere que los valores esperados para grados 200, 300 y 1000 podrían ya estar muy cerca del valor esperado en grado infinito.
• El valor calculado es aproximadamente 50.7%, y como el cálculo del autor de la pregunta también ronda 50.7%, se presenta como evidencia de que el límite es mayor que 1/2.
• El autor de la respuesta añade que está “seguro de que el límite es mayor que 50%” y ofrece 100 dólares a quien demuestre que está equivocado.

Estabilización rápida en series de potencias truncadas

• Como evidencia adicional, se revisa para una serie de potencias aleatoria P(x)=Σaᵢxᶦ en qué momento se estabiliza si la raíz más pequeña de sus polinomios truncados Pₖ(x)=Σᵢ₌₀ᵏaᵢxᶦ es real o compleja, para k de 1 a 1000.
• En 200 polinomios aleatorios, el punto de estabilización fue en la mayoría de los casos muy pequeño:
  • En muchos casos ya se estabilizaba en k=1 o k=2.
  • El valor máximo entre los listados fue 22.
• Esto también respalda la idea de que los experimentos en grado finito pueden acercarse muy rápido al límite de grado infinito.

[GN⁺]

Opiniones de Hacker News

• Es realmente curioso que esté entre el nivel del azar y 1/φ.
  En la publicación de MSE enlazada ya se demostró que la probabilidad de que la raíz máxima sea real es de al menos 6.2%, e incluso más de 1/10 de 1/φ. Me parece natural la conexión entre los números primos y φ. Los primos no son aleatorios, como suele malinterpretarse, sino que surgen recursivamente a partir de los primos anteriores, porque son los “huecos” que no ocupan los múltiplos de los primos previos. Por eso es razonable esperar que aparezca algún patrón natural de crecimiento como e o φ. Es un patrón de magnitudes muy fundamentales, como la verdad y la belleza.

  • La forma en que e aparece en los primos puede verse en el promedio del tamaño de conjuntos que reúnen solo brechas crecientes, por ejemplo (2,3,5)(7,11)(13,17)..., o solo brechas que no disminuyen, como (2,3,5,7,11)(13,17)(19,23,29)...
    Más que una propiedad de los primos en sí, es una propiedad del crecimiento, y encaja mejor en conjuntos de números aleatorios.
  • Hermoso. φ siempre parece aparecer cuando algo se amontona densamente.

• Se me ocurren de inmediato dos preguntas:

  1. ¿Qué significa “aleatorio” aquí? Parece que hicieron experimentos numéricos; se ve parecido a usar coeficientes enteros uniformes en un conjunto acotado, y entonces el resultado puede cambiar mucho.
  2. Me pregunto si analizaron grados impares, donde siempre se garantiza una raíz real, grados pares, o ambos.
     No intento menospreciar este artículo tan interesante.
  • Tal como se usa en la definición, la distribución es de coeficientes uniformes independientes en (-1,1).
  • Correcto. El planteamiento original del problema es paradójico. No se puede muestrear uniformemente de un conjunto infinito. Supongo que el artículo original usó números de punto flotante aleatorios acotados.
    Pero la parte importante de la pregunta puede plantearse para cualquier distribución posible sobre los reales.

• Si quieres hacer un experimento numérico con esto, R tiene soporte integrado para este tipo de cosas:
  plot(polyroot(runif(101,-1,1)))
  Con eso puedes ver una visualización de las raíces de un polinomio de grado 100.

• “Supongamos que los coeficientes son independientes y uniformemente aleatorios en (−1,1). Si no, se puede escalar cada coeficiente a (−1,1) dividiéndolo por el coeficiente con mayor valor absoluto.”
  No sé si mi intuición es correcta, pero al dividir y escalar así, ¿la distribución de los demás coeficientes, excepto el mayor, no se vuelve una distribución no uniforme?

  • Lo importante es que multiplicar un polinomio por una constante no cambia sus raíces.
  • Cierto, pero no se puede elegir aleatoriamente un número real con distribución uniforme. En algún punto hay que ceder.

• Para polinomios de grado 5 o más no hay fórmula; entonces, ¿cómo distinguen una raíz real de real + epsilon*i?

  • Con el teorema de Budan https://en.wikipedia.org/wiki/Budan%27s_theorem se puede certificar si en el intervalo (r - ɛ, r + ɛ] hay exactamente una raíz real, o exactamente cero.
    Si la estimación r está a menos de ɛ de alguna raíz, se puede distinguir entre una raíz real y una compleja sin conocer el valor exacto. Claro que también hay casos en los que el teorema de Budan no da respuesta. Por ejemplo, falla de la forma más obvia si hay dos o más raíces en ese intervalo.
  • Que no exista una fórmula exacta para las raíces de polinomios de grado alto no impide que pueda determinarse la distribución de las raíces de esos polinomios. La pregunta trata sobre una distribución, no sobre un polinomio específico, así que el teorema de Abel no es una barrera.
    Por ejemplo, si consideramos el polinomio a_n x^n + ... + a_0, donde los coeficientes a_i son variables aleatorias Bernoulli independientes e idénticamente distribuidas, podemos decir con confianza que, aunque el grado n sea grande (>4), ese polinomio tiene una raíz real en x = 0 con probabilidad 1/2. En la pregunta enlazada funciona una lógica parecida, aunque más sofisticada.
  • Si es un polinomio con coeficientes enteros, se puede acotar la raíz más grande y la más pequeña mediante alguna potencia del máximo de los valores absolutos de los coeficientes. Supongo que debe haber una cota similar para la parte imaginaria más pequeña que puede tener una raíz.
    Si los coeficientes son reales, una fórmula tampoco ayuda. Está el mismo problema de no poder determinar si un número es igual a 0. Por ejemplo, en la fórmula cuadrática el discriminante podría ser -epsilon: si epsilon es 0, no hay raíces imaginarias; si no es 0, sí las hay.
  • Aquí parece que podría usarse la derivada. Si x+iy y x-iy son raíces complejas y y es muy pequeño, entonces la derivada en x también debería ser pequeña. Si y=0, es una raíz doble, así que p'(x)=0.
    Por lo tanto, si p'(x) está lo suficientemente lejos de 0, puede considerarse una raíz real simple. Y con coeficientes aleatorios, una raíz doble prácticamente no debería ocurrir.
  • La estimación se basa en razonamiento, no en cálculo numérico. Por ejemplo, los polinomios de valores reales son estables bajo conjugación compleja, así que si tienen una raíz compleja, su conjugada también debe ser raíz. Por lo tanto, en un polinomio con tres raíces distintas, una de ellas necesariamente debe ser real. Con razonamientos así se puede determinar si una raíz es puramente real o compleja.
    En cuanto a las fórmulas, no existe una fórmula general para grados 5 o superiores. Las fórmulas generales solo existen para polinomios de grado 4 o menor.
    Por supuesto, puede haber fórmulas específicas para ciertos tipos de polinomios de grado alto. Pero no existen para el caso general de grado 5 o más, y eso ya fue demostrado clásicamente.

• Me salgo un poco del tema, pero siempre disfruto leer textos de matemática como este.
  En la universidad me encantaba la matemática y, aunque estudié Ciencias de la Computación, el entusiasmo de mis profesores siempre me sirvió de estímulo. Me gustaría aprender más y meterme un poco en resolver problemas con matemática. Tal vez podría inclinarme hacia el análisis numérico.
  Eso sí, me gradué hace 2 años y desde entonces no he practicado mucho, así que probablemente tenga que reaprender bastante. Me pregunto por dónde sería bueno empezar y si habrá lugares donde encontrar temas interesantes. No es análisis numérico, pero durante la carrera resolví bastantes problemas de Project Euler; ¿habrá algo parecido? Cualquier idea es bienvenida.
  ¿O debería primero volver a resolver todos los problemas de los libros de texto? ;-)

  • Para alguien que conoce hasta cierto punto la matemática de nivel universitario y tiene curiosidad, Mathematics and Its History (https://link.springer.com/book/10.1007/978-1-4419-6053-5) es un libro realmente entretenido.
    Creo que también podrías disfrutar Proofs from THE BOOK (https://link.springer.com/book/10.1007/978-3-662-57265-8).
  • Es un poco distinto de lo que preguntas, pero si te gusta la matemática, The Math Sorcerer vale mucho la pena: https://www.youtube.com/@TheMathSorcerer
  • Fui a la universidad a estudiar matemática 6 o 7 años después de dejar la escuela; en su momento me iba bien en matemática, pero ya casi lo había olvidado todo. No encontré mejor método que volver a resolver todos los ejercicios que había hecho antes, y descubrí que en realidad no lo había olvidado por completo. Suerte.

• No sé si será porque no conozco este tipo de matemática.
  En mi cabeza, tomo un polinomio “aleatorio” y miro solo sus dos raíces más grandes. Luego pienso en dos reflexiones: una respecto de la parte inferior/superior de la curva y otra respecto del eje x. Si esas dos raíces superiores no están degeneradas, me parece que, entre las cuatro combinaciones de curvas obtenidas por reflexión, dos tienen una raíz real máxima y dos tienen una raíz imaginaria máxima. Si están degeneradas, la raíz máxima es real.
  Entonces concluiría que (1) hay más casos en los que la raíz máxima es real que casos en los que es imaginaria, y (2) como hay infinitamente más curvas con una raíz máxima no degenerada que casos degenerados, esa “ventaja” es tan pequeña que desaparece.
  Se nota que casi no conozco la terminología. Probablemente se me esté escapando que la uniformidad de los coeficientes aleatorios no implica una distribución uniforme en el espacio. O tal vez mis reflexiones rompen alguna de las condiciones, por ejemplo la de tener coeficientes reales. O quizá simplemente esté equivocado.

  • No estoy seguro de qué quieres decir con reflexión. Reflejar la gráfica de un polinomio p(x) respecto del eje x significa cambiar p(x) por p(-x). ¿Qué significa “reflejar respecto de la parte inferior/superior de la curva”? ¿Es una reflexión respecto del eje y? Entonces significaría cambiar p(x) por -p(x).
  • ¿Qué significa una reflexión respecto de la parte inferior/superior de la curva?
    Con combinaciones, ¿quizá te refieres a tomar (polinomio + polinomio reflejado)/2?

• No entiendo muy bien por qué parece contraintuitivo que los reales sean más probables.
  Si, en vez de coeficientes reales uniformemente aleatorios dentro de un intervalo, eliges raíces uniformemente aleatorias en un disco centrado en el origen del plano complejo y formas un polinomio, casi nunca obtendrás un polinomio con coeficientes reales. En cambio, si las raíces aleatorias son reales, el polinomio necesariamente tendrá coeficientes reales. Así que, a priori, ninguna respuesta me sorprende, y que los reales parezcan más plausibles me resulta un poco más intuitivo. Por supuesto, no es algo inevitable.

  • Un polinomio de grado n tiene n raíces, incluyendo tanto raíces reales como complejas. En un polinomio aleatorio, aproximadamente log(n) de ellas son reales y n - log(n) son no reales.
    Cuando n crece, log(n) es muy pequeño comparado con n, así que es muy sorprendente que en más de la mitad de los casos la raíz máxima sea una de ese pequeñísimo número de raíces reales.

• Siguiendo los enlaces de aquí, parece que una de las respuestas de Boris Hanin resolvió una pregunta que tenía desde hace tiempo.

• Pero me pregunto si, al hablar de polinomios aleatorios, se trata de coeficientes reales o de coeficientes complejos.

  • Si se permiten coeficientes complejos, la distribución se vuelve rotacionalmente simétrica en el plano complejo. Por eso, la probabilidad de que una raíz esté sobre el eje real no es mayor que la probabilidad de que esté sobre cualquier otra recta que pase por el origen. Los polinomios cuya raíz máxima sea real prácticamente desaparecerían.
  • La pregunta planteada especifica que son coeficientes reales. Experimentalmente, parece que eligieron coeficientes aleatorios en el rango [-1, 1] con distribución uniforme y también probaron algún tipo de distribución normal escalada.
  • En la primera línea de la pregunta dice “real”.