Элементарная теория чисел, теория групп и графы Рамануджана

«Элементарная теория чисел, теория групп и графы Рамануджана» — это книга по математике, цель которой — сделать построение графов Рамануджана доступным для студентов-математик бакалавриата. Для этого он охватывает несколько других важных тем теории графов , теории чисел и теории групп . Она была написана Джулианой Давидофф , Питером Сарнаком и Аленом Валеттом и опубликована в 2003 году издательством Кембриджского университета как 55-й том серии книг для студентов Лондонского математического общества.

Предыстория

Основная статья: граф Рамануджана

В теории графов графы -расширители представляют собой неориентированные графы с высокой связностью: каждое достаточно маленькое подмножество вершин имеет множество ребер, соединяющих его с остальными частями графа. Разреженные графы-расширители имеют множество важных приложений в информатике, включая разработку кодов исправления ошибок , проектирование сортировочных сетей и дерандомизацию рандомизированных алгоритмов . Для этих приложений граф должен быть построен явно, а не просто доказано его существование.

Один из способов показать, что граф является расширителем, — изучить собственные значения его матрицы смежности . Для $r$- обычный график , это действительные числа в интервале $[-r,r]$, а наибольшее собственное значение (соответствующее всех единиц собственному вектору ) точно равно $r$. Спектральное расширение графа определяется разницей между наибольшим и вторым по величине собственными значениями, спектральным разрывом , который контролирует, насколько быстро случайное блуждание по графу приходит к своему стабильному распределению ; этот разрыв может быть максимум $2{\sqrt {r-1}}$. Графы Рамануджана определяются как графы, оптимальные с точки зрения спектрального разложения: они $r$-регулярные графы, спектральная щель которых в точности равна $2{\sqrt {r-1}}$.

Хотя графы Рамануджана с высокой степенью , такие как полные графы , легко построить, для приложений этих графов необходимы графы-расширители низкой степени. В настоящее время известно несколько конструкций графов Рамануджана низкой степени, первые из которых были предложены Любоцким, Филлипсом и Сарнаком (1988) и Маргулисом (1988) . Рецензент Юрген Эльстрод пишет, что «хотя описание этих графов элементарно, доказательства того, что они обладают желаемыми свойствами, нет». Цель «Элементарной теории чисел, теории групп и графов Рамануджана» сделать как большую часть этой теории доступной на элементарном уровне . можно

Темы

Ее авторы разделили «Элементарную теорию чисел», «Теорию групп» и «Графы Рамануджана» на четыре главы. В первом из них представлены основы теории графов , включая материалы об обхвате графов (длине кратчайшего цикла), о раскраске графов и об использовании вероятностного метода для доказательства существования графов, для которых как обхват, так и количество необходимых цветов велико. Это обеспечивает дополнительную мотивацию для построения графов Рамануджана, поскольку построенные в книге графы дают явные примеры того же явления. В этой главе также представлен ожидаемый материал по теории спектральных графов , необходимый для определения графов Рамануджана.

Глава 2, посвященная теории чисел , включает в себя теорему о сумме двух квадратов, характеризующую целые положительные числа, которые можно представить в виде сумм двух квадратов целых чисел (тесно связанных с нормами гауссовских целых чисел ), теорему Лагранжа о четырех квадратах , согласно которой все положительные целые числа целые числа могут быть представлены как суммы четырех квадратов (доказано с использованием норм кватернионов Гурвица ) и квадратичной взаимности . Глава 3 посвящена теории групп и, в частности, теории проективных специальных линейных групп. $PSL(2,\mathbb {F} _{q})$ и проективные линейные группы $PGL(2,\mathbb {F} _{q})$ над конечными полями, порядок которых является простым числом $q$и теория представлений конечных групп .

В последней главе строится граф Рамануджана. $X^{p,q}$ для двух простых чисел $p$ и $q$ как граф Кэли группы $PSL(2,\mathbb {F} _{q})$ или $PGL(2,\mathbb {F} _{q})$ (в зависимости от квадратичной взаимности) с генераторами, определяемыми по модулю $q$ набор $p+1$ кватернионы, происходящие из представлений $p$ как сумма четырех квадратов. Эти графики автоматически $(p+1)$-обычный. В главе приведены формулы для определения количества вершин и оценки их обхвата. Хотя это и не доказывает полностью, что эти графы являются графами Рамануджана, в этой главе доказывается, что они являются расширителями спектра, и описывается, как утверждение о том, что они являются графами Рамануджана, вытекает из Пьера Делиня доказательства гипотезы Рамануджана (связь с Рамануджаном, из которой произошло название этих графиков было получено).

и

Эта книга предназначена для студентов продвинутого уровня, которые уже познакомились с абстрактной алгеброй и реальным анализом . Рецензент Томас Шеманске предлагает использовать его в качестве основы семинара для пожилых людей, как быстрый путь ко многим важным темам и интересный пример того, как эти, казалось бы, отдельные темы объединяют усилия в этом приложении. С другой стороны, Томас Пфафф считает, что это будет сложно даже для большинства студентов старших курсов, но может стать хорошим выбором для самостоятельного обучения или факультативного курса магистратуры.