Warum werden Ramanujan-Graphen nach Ramanujan benannt?

25

Ich habe kürzlich Expander unterrichtet und den Begriff der Ramanujan-Graphen eingeführt. Michael Forbes fragte, warum sie so heißen und ich musste zugeben, dass ich es nicht weiß. Jemand?

Dana Moshkovitz
quelle

Antworten:

36

Um den Antworten hier etwas Inhalt hinzuzufügen, erkläre ich kurz, was Ramanujans Vermutung ist.

Zunächst ist Ramanujans Vermutung tatsächlich ein Satz, der von Eichler und Igusa bewiesen wurde. Hier ist eine Möglichkeit, es auszudrücken. Sei rm(n) die Anzahl der Integrallösungen der quadratischen Gleichung x12+m2x22+m2x32+m2x42=n . Wenn m=1 ist, ist rm(n)>0m r m ( n ) = c m Σ d | n D + O ( n 1 / 2 + ε ) ε > 0 c m mr1(n)=8dn,4ddmrm(n)=cmdnd+O(n1/2+ϵ)ϵ>0cmm

Basierend auf diesem Ergebnis haben Lubtozky, Phillips und Sarnak ihre Expander konstruiert. Ich kenne die Details ihrer Analyse nicht, aber ich glaube, die Grundidee besteht darin, einen Cayley-Graphen von für eine Primzahl zu konstruieren , die , wobei Generatoren verwendet werden, die durch jede Summe von bestimmt werden -vier-Quadrate-Zerlegung von p , wobei p ein quadratischer Rest modulo q ist . Dann beziehen sie die Eigenwerte dieses Cayley-Graphen auf r_ {2q} (p ^ k) für ganzzahlige Potenzen k . q 1 mod 4PSL(2,Zq)q1mod4p q r 2 q ( p k ) kppqr2q(pk)k

Eine andere Referenz als das Lubotzky-Phillips-Sarnak-Papier selbst ist Noga Alons kurze Beschreibung in Tools from Higher Algebra .

Arnab
quelle
2
nett ! gute Antwort.
Suresh Venkat
21

Wikipedia liefert diese Antwort ziemlich schnell. Zitieren

Konstruktionen von Ramanujan-Graphen sind oft algebraisch. Lubotzky, Phillips und Sarnak zeigen, wie eine unendliche Familie von regulären Ramanujan-Graphen konstruiert wird , wenn eine Primzahl ist. Ihr Beweis verwendet die Ramanujan-Vermutung , die zum Namen der Ramanujan-Graphen führte.p = 1p+1p=1mod4

Das erwähnte Papier sind Ramanujan-Diagramme A. Lubotzky, R. Phillips und P. Sarnak, COMBINATORICA, Band 8, Nummer 3 (1988), 261-277, DOI: 10.1007 / BF02126799.

Dave Clarke
quelle
Die Frage ist: Was ist die Ramanujan-Vermutung
Suresh Venkat
Es ist manchmal viel besser, Links beim Zitieren beizubehalten.
Tsuyoshi Ito
Tatsächlich. Ich habe den Ernst der Frage unterschätzt.
Dave Clarke