Distribución de números de Perron

Question

Un Perron número es un verdadero algebraicas entero $\lambda$ que es mayor que el valor absoluto de cualquiera de sus Galois conjugados. El Perron-Frobenius teorema dice que cualquier entero no negativo de la matriz $M$ tal de que algún poder de $M$ es estrictamente positivo tiene un único positivo autovector cuyo autovalor es un Perron número. Doug Lind demostrado lo contrario: dado un Perron número $\lambda$, existe una matriz, tal vez en la dimensión mucho mayor que el grado de $\lambda$. Perron números surgen con frecuencia en muchos lugares, especialmente en los sistemas dinámicos.

Mi pregunta:

¿Cuál es la limitación de la distribución de Galois de los conjugados de la Escalinata números de $\lambda$ en algunos intervalo acotado, como el grado tiende a infinito?

Estoy particularmente interesado en buscar en el límite de la longitud del intervalo va a 0. Una manera de normalizar este es mirar la relación $\lambda^g/\lambda$, como $\lambda^g$ rangos de la Galois conjugados. Vamos a llamar a estos números de \emph{Perron proporciones}.

Tenga en cuenta que para cualquier fija $C > 1$ e integer $d > 0$, sólo hay un número finito de Perron números de $\lambda < C$ grado $< d$, ya que es evidente que hay un límite en el discriminante del polinomio mínimo de $\lambda$, así que la pregunta sólo es interesante cuando una va al infinito.

En ningún campo en particular, el conjunto de expresiones algebraicas los números que se Perron se encuentran en un cono convexo en el producto de Arquímedes lugares del campo. Para cualquier red, entre celosía puntos con $x_1 < C$ que están dentro de este cono, la proyección a lo largo de las líneas a través del origen al plano $x_1 = 1$ tiende hacia el uniforme de distribución, así como la $C \rightarrow \infty$, la distribución de la Escalinata ratios converge a una distribución uniforme en la unidad de disco (con una contribución de cada lugar complejo del campo), además de una distribución uniforme en el intervalo de $[-1,1]$ (con una contribución por cada lugar del campo).

Pero ¿qué sucede cuando $C$ está en manos de delimitada y el grado tiende a infinito? Esta pregunta parece relacionados con la teoría de matrices aleatorias, pero no veo ninguna traducción directa del cosas que he escuchado. La elección de un azar Perron número parece muy diferente de la elección de aleatorio entero no negativo de la matriz.

He probado algunos crudo experimentos, mirando al azar elegido polinomios, de un determinado grado cuyos coeficientes son números enteros en algunas rango fijo, excepto para el coeficiente de $x^d$ que es $1$, la selección de aquellas que el polinomios irreducibles cuyo mayor raíz real es Escalera. Este no es el mismo que al seleccionar al azar Perron número de un determinado grado en un intervalo. Yo no conozco ninguna forma razonable de hacer el último excepto para lo suficientemente pequeño $d$ e $C$ que uno podría presumiblemente encontrar por búsqueda exhaustiva. De todos modos, aquí están algunas muestras de lo intenté. En primer lugar, de entre los 16,807 quinto grado de los polinomios con coeficientes en el rango de -3 a 3, $3,361$ que definir una Escalinata número. Aquí es la trama de el Perron relaciones:

texto alt http://dl.dropbox.com/u/5390048/PerronPoints5%2C3.jpg

Aquí están los resultados de una muestra de 20.000 grado 21 de polinomios con coeficientes de entre -5 y 5. De esta muestra, 5,932 definido Perron números:

texto alt http://dl.dropbox.com/u/5390048/PerronPoints21.jpg

La distribución decididamente no parece que va a converger hacia una distribución uniforme en el disco, además de una distribución uniforme en el intervalo. Tal vez los artificiales límites en los coeficientes de la causa de la mayor densidad del anillo.

Hay buena, distribuciones naturales para la selección entero aleatorio polinomios? Hay un la manera de hacerlo sin perjudicar indebidamente la distribución de las raíces?

A ver si iba a ayudar a separar lo que está pasando, Traté de que el trazado de la Escalera de ratios restringidos a $\lambda$ en subintervalos. Para el grado 21 de ejemplo, aquí es la trama de $\lambda$ por orden:

texto alt http://dl.dropbox.com/u/5390048/CDF21.jpg

(Si desea cambiar la escala de la $x$ eje rango de $0$ a $1$ y de intercambio de $x$ e $y$ ejes, esto se convierte en la trama de la muestra la función de distribución acumulativa de $\lambda$.) Aquí están las parcelas de el Perron ratios restringidos a los intervalos de $1.5 < \lambda < 2$ y $3 < \lambda < 4$:

texto alt http://dl.dropbox.com/u/5390048/PerronPoints21%281.5%2C2%29.jpg

texto alt http://dl.dropbox.com/u/5390048/PerronPoints21%283%2C4%29.jpg

La restricción a un intervalo parece concentrado de los valores absolutos de la Escalinata proporciones, incluso más. La distribución angular parece que converge con el uniforme la distribución en un círculo más punto de masas en $0$ e $\pi$.

Hay una explicación para la distribución de los radios? Las conjeturas de lo que es?

Answer 1

He adquirido una nueva perspectiva sobre esta cuestión, basándose en los comentarios y en Hitachi Peach respuesta. Lugar de edición de la pregunta original, voy a escribir más pensamientos (parcial) de respuesta en la esperanza de que inspire a alguien con conocimientos diferentes a decir más.

En primer lugar, después de Hitachi Peach comentario después de su respuesta, he intentado trazar una imagen de todas las respuestas para una pareja de dos de las situaciones más sencillas: cuadráticas y cúbicas con un pequeño valor de $C$.

A continuación se muestra un diagrama en el coeficiente de espacio para polinomios cuadráticos. El eje horizontal es el coeficiente de $x$ y el eje vertical es la constante.

texto alt http://dl.dropbox.com/u/5390048/QuadraticSmallPerron.jpg

Las partes no sombreadas en el medio son polinomios cuyas raíces son reales con la máxima absoluta valor 5 y el mínimo valor absoluto 1; la mitad izquierda de esta zona se compone de Perron polinomios. Las líneas rojas son las curvas de nivel de la máxima de la raíz.

Aquí es similar complot para polinomios cúbicos, esta vez mostrando la región en el coeficiente de espacio donde todas las raíces tienen valor absoluto menor que 2.

texto alt http://dl.dropbox.com/u/5390048/CubicRootsSmaller2.jpg

Entre estos están el 31 de Perron polinomios (donde el máximo es alcanzado por un real positivo de la raíz. Aquí están sus raíces, y la normalizado de las raíces (dividido por el Perron número):

texto alt http://dl.dropbox.com/u/5390048/PerronPoints3%282%29.jpg

texto alt http://dl.dropbox.com/u/5390048/PerronPoints3%282%29normalized.jpg

Después de ver y pensar acerca de estas imágenes, se hizo claro que para polinomios con raíces delimitada por $C > 1$, como el grado crece grande, el volumen en el coeficiente de reparto space crezca muy rápidamente con el grado, y parece de alto volumen/(zona de frontera) de relación. El típico coeficientes de llegar a ser grande, y la mayoría de las raíces se parecen a cambiar lentamente como los coeficientes de cambio, por lo que no golpe en la frontera con demasiada facilidad. Si es así, entonces para obtener un azar de celosía punto dentro de este volumen, se debe trabajar bastante bien a la primera encontrar un punto aleatorio elegido de manera uniforme en el coeficiente de espacio y, a continuación, pasar a la más cercano celosía punto.

Con eso en mente, traté de adivinar la distribución de las raíces (invariante por el complejo de conjugación), elegir una muestra aleatoria de $d$ elementos escogidos de forma independiente a partir de esta distribución, se genera el polinomio con coeficientes reales que esas raíces, ronda fuera de los coeficientes para el entero más próximo, y mirando a la resultante de las raíces. Para mi sorpresa, muchas de las raíces no eran muy estables: el más cercano de la integral del polinomio generalmente terminaron con raíces bastante lejos fuera de los límites, para los valores de los parámetros de varias distribuciones que he probado. (Nota: una restricción en la distribución es que la la media geométrica de los valores absolutos debe ser un entero $\ge 1$. Esto descarta la distribución uniforme, al menos para valores pequeños de $C$).

Después de pensar más acerca de la estabilidad de la cuestión de las raíces (como los coeficientes son perturbado), me di cuenta de la importancia de las interacciones de las raíces cercanas. Siempre hay una doble raíz, las raíces se mueven rápidamente cuando los coeficientes son cambiados --- es decir, la relación de volumen en el coeficiente de espacio para el volumen en la raíz del espacio es relativamente pequeño. Es como si las raíces cercanas en efecto, tienen una fuerza de repulsión. La distribución conjunta de las raíces es importante: usted obtener respuestas incorrectas si los tratas como independiente.

Con esto en mente, he intentado un experimento en el que se hace clic en un diagrama para poner en las raíces para un control real polinomio con la mano, mientras el equipo encontró que las raíces del polinomio más cercano con coeficientes enteros. Con un poco de práctica, esto funcionó bien. Nuevas raíces "prefiere" a se inserta donde la polinomio es alta, así que me sombreada en el diagrama por el valor absoluto del polinomio, para indicar buenos lugares para una nueva raíz. A veces, las raíces de la controladora polinomio se desvincule de las raíces de al entero más cercano polinomio, y el resultado es a menudo un fuera de los límites de la raíz no está cerca de ningún control de raíz. En ese caso, la eliminación del control de las raíces que se desasocian la trae de regreso a la línea. Como el control de las raíces se mueven, la algebraica de los números enteros saltar en pasos discretos, y estos pasos son mucho más pequeñas cuando el control de la distribución de la raíz está en un buen región del espacio de parámetros.

Aquí está una captura de pantalla en el experimento (que es divertido!):

texto alt http://dl.dropbox.com/u/5390048/ControlRoots.jpg

Aquí, la convención es que cada punto de control sobre el eje real se duplica con su complejo conjugado. Cada punto de control por debajo del eje real se proyecta que el eje real, y da una verdadera raíz para el control del polinomio. Todo el control de las raíces se muestran en negro, y las raíces del entero más cercano polinomio se muestran en rojo. Para estas posiciones, el rojo raíces están bien asociados con raíces negras. Es un Perron polinomio, porque un real de la raíz ha sido arrastrado por lo que tiene la máxima módulo.

En la siguiente captura de pantalla, he arrastrado de control de varios raíces en un clúster de alrededor de 11 de la mañana. El rojo raíces no eran felices allí, así que desligarse del control de las raíces y dispersos en direcciones diferentes, uno de ellos a una mucho más grande de radio. Esta es una buena indicación de que la relación del coeficiente de espacio de volumen a la raíz del volumen de espacio es pequeño. Este polinomio no es Perron.

texto alt http://dl.dropbox.com/u/5390048/RootPerturb-disassociated.jpg

Este experimento es mucho más difícil para $C$ cerca de $1$: los coeficientes son mucho más pequeñas para un determinado grado, lo que hace que las raíces mucho menos estable. Ellos se vuelven más estables cuando no son un montón de raíces se extienden bastante uniforme, sobre todo cerca de la frontera exterior.

Aquí es un método que en principio debería dar un casi uniformemente al azar la elección de un polinomio con raíces delimitada por $C$, y creo que, por la aproximación más cercana el polinomio de tener coeficientes enteros, dar un casi uniforme elección de la algebraicas entero cuya conjugados están delimitadas por $C$: a partir de cualquier polinomio cuyas raíces están delimitadas por $C$, por ejemplo, un cyclotomic polinomio. Elegir un vector aleatorio en el coeficiente de espacio, y seguir un $C^1$ curva cuyo vector tangente evoluciona por el movimiento Browniano en la unidad de la esfera. Cuando una raíz golpea el círculo de radio $C$, elegir al azar una nueva dirección en la que la raíz disminuye en valor absoluto (i.e, uso de dispersión difusa en las superficies). La distribución de los puestos deben converger a la distribución uniforme en el región dada en el coeficiente de espacio.

Este método también es probable que el trabajo de encontrar al azar polinomio cuyas raíces están en el interior de cualquier conectados conjunto abierto y sujeto a ciertas limitaciones geométricas (por ejemplo, no puede ser en el interior del círculo unitario) casi uniformemente al azar algebraicas entero de alto grado cuya Galois conjugados están dentro de un determinado conectado conjunto abierto.

Por supuesto, aún más interesante que un empírica de simulación sería un buen análisis teórico.

Answer 2

Hay muchos contextos en los que se puede establecer que una familia de polinomios, o incluso un único polinomio, tiene raíces que se distribuyen de acuerdo a alguna medida que se aproxima el uniforme de la medida sobre el círculo unidad.

Deje $f(x) = a_N x^N + \ldots + a_1 x + a_0$ ser un polinomio con coeficientes reales, y asumir que $a_N \ne 0$. Considerar la cantidad:

$$L_N(f) = \log \left( \sum |a_k| \right) - \frac{1}{2} \log |a_N| - \frac{1}{2} \log |a_0|.$$

Un teorema de Hughes y Nikeghbali (Los ceros de polinomios aleatorios clúster de manera uniforme cerca del círculo unidad, de Naturaleza 144 (1998)), dice (de manera informal) que si $L_N(f)$ es pequeña en comparación a $N$, entonces las raíces se distribuyen de manera uniforme a lo largo del círculo unidad. Un ingrediente de su resultado es un teorema de Erdos-Turan (En la distribución de las raíces de polinomios, Ann. de Matemáticas. (2) 51 (1950)) que (bajo la misma hipótesis) muestra que los argumentos de las raíces se distribuyen de manera uniforme. Con esto, podemos responder:

Hay una explicación para la distribución de los radios? Las conjeturas de lo que es?

Si uno toma los coeficientes de mentir en algún limitada gama, decir $[-5,5]$,, a continuación, $L_N(f)$ tiene orden de $O(\log(N))$, que sin duda es $o(N)$. Por tanto, los polinomios aleatorios generados de esta manera tienen raíces que se están distribuyendo en el círculo unidad. Por otro lado, los polinomios de ser elegido son las que tienen un único más grande de la raíz del tamaño en la mayoría de los cinco y por lo general alrededor de $5$, y por lo tanto el normaliza las raíces se parecen a agruparse alrededor de la circunferencia de radio $1/5$. La agrupación se hace más pronunciada cuando se restringe a los polinomios donde el más grande de la raíz se encuentra en $[5,5-\lambda]$ para las más $\lambda$ (por lo tanto, Thurston del gráfico con más restringido intervalos son más "en forma de anillo." (No hay ningún punto de masa a lo largo del eje real por el teorema de Erdos-Turan.)

Hay buena, distribuciones naturales para la selección entero aleatorio polinomios? Hay una manera de hacerlo sin perjudicar indebidamente la distribución de las raíces?

Dado un gran dimensional probabilidad de espacio, de una manera natural, para generar al azar de los elementos según la distribución es el uso de un paseo aleatorio de Metropolis-Hastings algoritmo. Concretamente, se puede empezar con una muestra aleatoria de Perron polinomio con mayor root $< 5$, y, a continuación, perturbar los coeficientes de acuerdo a algunos de distribución (es decir, una distribución normal, con una pequeña desviación). Si el nuevo polinomio es también Perron con mayor root $< 5$, elija este polinomio, o bien mantenga el mismo polinomio. Este proceso de Markov debería --- bajo las condiciones adecuadas --- generar al azar polinomios (en total) de acuerdo a la distribución requerida. Por ejemplo, vamos a ejecutar este algoritmo y compararlo con las raíces de azar monic polinomios con coeficientes en $[-5,5]$ que tienen una única más grande de la raíz. Las raíces de polinomios con coeficientes en $[-5,5]$ se ilustra en el primer gráfico, y el resultado de la Metropolis-Hastings algoritmo para todos los Perron polinomios con mayor raíz de menos de $5$ se da en el segundo gráfico:

Observe que las raíces de la primera gráfica se concentran alrededor del círculo unitario, como se explicó anteriormente. Sin embargo, las raíces de la segunda gráfica se clústeres alrededor de la frontera. De hecho, esto resulta para reflejar la realidad (ver el teorema de abajo).

¿Cuál es la limitación de la distribución de Galois de los conjugados de la Escalinata números de $\lambda$ en algunos intervalo acotado, como el grado tiende a infinito?

Vamos a considerar en primer lugar el problema más fácil de describir "real Perron polinomios" --- que es, monic polinomios con coeficientes reales que tienen una única más grande de la raíz de $\le r$ (necesariamente real). El real Perron números de forma integral celosía puntos en este espacio (aunque no todo el entramado de puntos, sólo los correspondientes a los polinomios irreducibles; sin embargo, la reducible entramado de puntos forma una fina subconjunto). Si uno corrige el grado de $N$ y aumenta el radio de $r$, entonces (debido a que las regiones que participan son adecuados agradable) el entramado de puntos se distribuyen más o menos uniformemente en el interior del espacio (Davenport Lema). Sin embargo, si uno corrige $r$ y permite a $N \rightarrow \infty$, no es tan claro si la distribución de celosía de puntos se puede aproximar por el correspondiente de la real de la región. El estudio de celosía puntos en la no-convexo regiones (o incluso convexa) y a menudo conduce a bastante espinoso número teórico de los problemas, pero uno puede al menos la esperanza (y comparar con el experimento) que la geometría real da un indicio de la verdad de la cuestión. Para este fin, se tiene la siguiente:

Teorema: Fijar un real entero positivo $r > 0$. Deje $\Omega_N$ denotar el espacio de monic polinomios con coeficientes reales que tienen una raíz real $\alpha$ tal que $r > \alpha > |\sigma \alpha|$ para todos los conjugados $\sigma \alpha \ne \alpha$. Entonces, como $N \rightarrow \infty$, las raíces de un azar del polinomio en $\Omega_N$ se distribuyen de manera uniforme a lo largo del círculo $|z| = r$.

La prueba de este teorema se utiliza el teorema de Hughes y Nikeghbali mencionados anteriormente. El punto es que uno tiene que obtener estimaciones de cómo las cantidades $|a_i|$ varían en el espacio de $\Omega_N$, que se reduce, en último término, a la evaluación y/o la estimación de los diversos integrales sobre $\Omega_N$. Por ejemplo, considere el ejemplo anterior de grado $21$ polinomios con una mayor root $< 5$. El modelo dado por el OP elija $a_{21} \in [-5,5]$. Resulta, sin embargo, que el valor esperado del término constante $a_{21}$ sobre $\Omega_{21}$ (con $r = 5$) es

$$ \frac{3^2 \cdot 5^{21} \cdot 7 \cdot 13 \cdot 17 \cdot 19}{2^{17} \cdot 11} \sim 8.748 \times 10^{13}.$$

Esto es bastante grande en comparación con $[-5,5]$!

Otras estadísticas

Hay algunas otras interesantes las probabilidades de que uno puede calcular utilizando integrales sobre espacios como $\Omega_N$ y espacios relacionados. Por ejemplo, se puede considerar que todos los monic polinomios de grado $2N$ con la propiedad de que sus raíces tienen valor absoluto en la mayoría de uno. Esto define una región compacta de (el coeficiente de espacio) $\mathbf{R}^N$, por lo que tiene una natural uniforme medida. Entonces la probabilidad de que un azar de tal polinomio no tiene raíces reales en el intervalo de $[-1,1]$ (lo que es equivalente, es positivo en $[-1,1]$, lo que es equivalente, no tiene raíces en todos los de $\mathbf{R}$) es igual a

$$\sim \frac{2C}{\sqrt{2\pi} \cdot (2N)^{3/8}},$$

donde la constante $C$ es igual a

$$C = 2^{-1/24} e^{- 3/2 \cdot \zeta'(-1)} = 1.24514 \ldots.$$

Curiosamente, hay un teorema de Dembo, Poonen, Shao, y Zeitouni que un azar del polinomio (en el más sentido usual de la palabra) cuyos coeficientes son los elegidos con (digamos) idénticas a las distribuciones normales con cero significa que hay de positivo en $[-\infty,\infty]$ con una probabilidad de $N^{-b + o(1)}$ y positivo en $[-1,1]$ con una probabilidad de $N^{-b/2 + o(1)}$ para algunas constante universal de~$b/2$, lo que ellos estiman que ser $0.38 \pm 0.015$. Por otro lado, el exponente que ocurren por encima de es $3/8 = 0.375$. ¿Hay alguna relación directa entre estos teoremas? Por ejemplo, ¿indica esto que $b = 3/4$? (El resultado de DPSZ en realidad es para una muy amplia gama de distribuciones con la misma indeterminado $b$, pero no se aplica a nuestro muy rígido contexto).

Comentarios Adicionales

Hay algunos análisis que uno puede hacer del espacio de $\Omega_{N}$, o más en general, el espacio de todos los monic polinomios con coeficientes reales, cuyas raíces tienen valor absoluto en la mayoría de los $r$. Por ejemplo, uno puede mostrar que un "azar" polinomio de grado $N$, sujeto a la restricción de que todas sus raíces tienen valor absoluto en la mayoría de los $r$, será una Escalinata polinomio (es decir, tienen un único más grande de la raíz) con una probabilidad de exactamente $1/N$ si $N$ es impar y $1/(N+1)$ si $N$ es incluso. Algunos de este análisis aparecen en mi tesis (voy a añadir un enlace aquí, cuando se escribe!). Como mi asesor, dijo, "Cualquier pregunta que Thurston pregunta es probablemente vale la pena pensar."

Answer 3

Usted puede pedir a una pregunta similar sobre Pisot y Salem números. El año pasado junto con mi proyecto de estudiante Charlie Scarr estábamos buscando, en particular, en una posible conexión entre la distribución de las raíces en el interior del círculo unidad y la Mahler medida de un polinomio. Nosotros no avances demasiado pero Charlie hizo algunas observaciones interesantes que se pueden encontrar en su informe http://www.maths.dur.ac.uk/~dma0mb/proyectos/C_Scarr.pdf

Más cerca a tu pregunta, creo que sería muy interesante para comprobar qué tipo de foto que sale si se restringe a los polinomios con pequeñas Mahler medida. Una gran lista de tales polinomios está disponible en Michael Mossinghoff de la página en Lehmer del problema. No es de ninguna manera una muestra aleatoria pero el orden por Mahler medida se ve muy natural en este contexto.