Recientemente enseñé expansores e introduje la noción de gráficos Ramanujan. Michael Forbes preguntó por qué se les llama así, y tuve que admitir que no lo sé. ¿Nadie?
fuente
Recientemente enseñé expansores e introduje la noción de gráficos Ramanujan. Michael Forbes preguntó por qué se les llama así, y tuve que admitir que no lo sé. ¿Nadie?
Para agregar contenido a las respuestas aquí, explicaré brevemente cuál es la conjetura de Ramanujan.
En primer lugar, la conjetura de Ramanujan es en realidad un teorema, probado por Eichler e Igusa. Aquí hay una forma de decirlo. Sea el número de soluciones integrales para la ecuación cuadrática . Si , ese fue, por supuesto, probado por Legendre, pero Jacobi dio el recuento exacto: . No se sabe nada exactamente igual para m más grande, pero Ramanujan conjeturó el límite: r_m (n) = c_m \ sum_ {d \ mid n} d + O (n ^ {1/2 + \ epsilon}) para cada \ epsilon> 0 , donde c_m es una constante dependiente solo de m.
Lubtozky, Phillips y Sarnak construyeron sus expansores basados en este resultado. No estoy familiarizado con los detalles de su análisis, pero creo que la idea básica es construir un gráfico Cayley de para un primo que , utilizando generadores determinados por cada suma de descomposición de cuatro cuadrados de , donde es un residuo cuadrático módulo . Luego, relacionan los valores propios de este gráfico de Cayley con para las potencias enteras .
Una referencia, que no sea el documento de Lubotzky-Phillips-Sarnak en sí, es la breve descripción de Noga Alon en Tools from Higher Algebra .
Wikipedia ofrece esta respuesta con bastante rapidez. Citando
El documento al que se hace referencia son los gráficos de Ramanujan A. Lubotzky, R. Phillips y P. Sarnak, COMBINATORICA Volumen 8, Número 3 (1988), 261-277, DOI: 10.1007 / BF02126799.
fuente