Почему графы Рамануджана названы в честь Рамануджана?

25

Недавно я преподавал расширители и ввел понятие рамануджановских графов. Майкл Форбс спросил, почему их так называют, и я должен был признать, что не знаю. Кто угодно?

Дана Мошковиц
источник

Ответы:

36

Чтобы добавить некоторое содержание к ответам здесь, я кратко объясню, какова гипотеза Рамануджана.

Прежде всего, гипотеза Рамануджана на самом деле является теоремой, доказанной Эйхлером и Игузой. Вот один из способов заявить это. Обозначим через rm(n) число интегральных решений квадратного уравнения x12+m2x22+m2x32+m2x42=n . Если m=1 , то rm(n)>0м г м ( п ) = с т Σ д | п д + О ( п 1 / 2 + ε ) ε > 0 с м мr1(n)=8dn,4ddmrm(n)=cmdnd+O(n1/2+ϵ)ϵ>0cmm

Lubtozky, Phillips и Sarnak построили свои расширители на основе этого результата. Я не знаком с деталями их анализа, но я считаю, что основная идея состоит в том, чтобы построить граф Кэли из для простого , , с использованием генераторов, определяемых каждой суммой разложение по четырем квадратам p , где p - квадратичный вычет по модулю q . Затем они связывают собственные значения этого графа Кэли с r_ {2q} (p ^ k) для целых степеней k . q 1 mod 4 p p q r 2 q ( p k ) kPSL(2,Zq)q1mod4ppqr2q(pk)k

Ссылкой, помимо самой статьи Любоцкого-Филлипса-Сарнака, является краткое описание Ноги Алона в « Инструментах из высшей алгебры» .

Арнаб
источник
2
хороший ! отличный ответ.
Суреш Венкат
21

Википедия дает этот ответ довольно быстро. квотирование

Конструкции рамануджановских графов часто алгебраичны. Любоцкий, Филлипс и Сарнак показывают, как построить бесконечное семейство -регулярных рамануджановых графов, когда - простое число. Их доказательство использует гипотезу Рамануджана , которая привела к названию графов Рамануджана.р = 1p+1p=1mod4

Упомянутый документ представляет собой графы Рамануджана A. Lubotzky, R. Phillips и P. Sarnak, COMBINATORICA, том 8, номер 3 (1988), 261-277, DOI: 10.1007 / BF02126799.

Дэйв Кларк
источник
вопрос в том, какова гипотеза Рамануджана
Суреш Венкат
Иногда гораздо лучше сохранить ссылки, когда вы цитируете.
Цуёси Ито
Верно. Я недооценил серьезность вопроса.
Дэйв Кларк