106
правок
Изменения
→Граф Рамануджана
===Граф Рамануджана===
<tex>d</tex>-регулярный граф называется графом Рамануджана, если его второе по модулю собственное число не превосходит <tex>2{\sqrt {d-1}}</tex>. Любоцкий, Сарнак, Филлипс и Маргулис указали явную конструкцию графов Кэли, являющихся графами Рамануджана. Опишем эту конструкцию.
Пусть <tex>p</tex> и <tex>q</tex> простые числа, <tex>p = 1</tex> <tex>mod</tex> <tex>\bmod 4</tex> и <tex>q = 1</tex> <tex>mod</tex> <tex>\bmod 4</tex>. В качестве группы <tex>G</tex> возьмём <tex>PGL(2, \mathbb Z/q{\mathbb Z})</tex>, т.е. невырожденные матрицы 2 × 2 над полем вычетов по модулю <tex>q</tex>, профакторизованные по отношению пропорциональности (с обычной операцией матричного умножения).Далее мы зададим в этой группе симметричное множество <tex>S</tex>. Выберем такое целое <tex>i</tex>, что <tex>i^2 = −1</tex> <tex>mod</tex> <tex>\bmod q</tex>. Можно доказать, что тогда имеется ровно <tex>(p + 1)</tex> целочисленное решение уравнения
<tex>a_0^2 + a_1^2 + a_3^2 = p</tex>
