В рамках открытого курса MIT OpenCourseWare представлена лекция, посвященная теории случайных блужданий на конечных группах и ее неожиданным связям с геометрией. На примере матричной группы $SL_2(\mathbb{F}_p)$ лектор демонстрирует, как сложные комбинаторные задачи сводятся к анализу линейных операторов. Центральной темой повествования становится элегантный метод Сарнака — Сю, объединяющий теорию представлений и свойства графов-экспандеров.
🎲 От теории проекций к случайным блужданиям 0:10
Переходя к заключительной части учебного курса, лектор размышляет о практическом применении ранее изученного материала. Предыдущие занятия были посвящены технически насыщенным темам, таким как теоремы Бургейна и Каца о проекциях в конечных полях. Чтобы показать реальную ценность этих небольших математических улучшений, дальнейший план занятий разделен на три этапа: одна неделя отводится на случайные блуждания на группах, еще одна — на однородную динамику, а завершится курс доказательством точной теоремы о проекциях. Текущее занятие призвано послужить доступным введением в предмет.
Математическая модель случайного блужания строится на конечной группе $G$ с заданной на ней вероятностной мерой $\mu$. Данная мера представляет собой неотрицательную функцию, сумма значений которой равна единице. Процесс блуждания выглядит следующим образом:
- Движение начинается из некоторой стартовой точки $g_0$.
- На каждом шаге из распределения $\mu$ случайно выбирается элемент $h$.
- Новое положение системы $g_1$ определяется как произведение $g_0 \cdot h$.
Главный аналитический вопрос, который ставит перед собой математик, заключается в том, насколько равномерно распределено это вероятностное распределение после выполнения $k$ шагов.
🔄 Свертка и линейные операторы: математический аппарат 4:32
Для точного описания динамики блуждания применяется операция дискретной свертки функций на группе. Если заданы две функции $F_1$ и $F_2$, то их свертка, вычисленная для элемента $g$, представляет собой сумму по всем парам элементов, произведение которых дает $g$:
$$(F_1 * F_2)(g) = \sum_{g_1 g_2 = g} F_1(g_1) F_2(g_2)$$
На основе меры $\mu$ конструируется линейный оператор $T_\mu$, действие которого на функцию $F$ эквивалентно ее свертке с этой мерой: $T_\mu(F) = F * \mu$. Если применить данный оператор $k$ раз к дельта-функции $\delta_{g_0}$ (описывающей гарантированное нахождение в начальной точке $g_0$), мы получим точное распределение вероятностей нахождения в элементе $g$ после $k$ шагов случайного блуждания.
Чтобы строго оценить степень равномерности распределения, ученые измеряют норму разности между текущим распределением и гипотетическим идеально равномерным состоянием, где вероятность для любого элемента равна $1/|G|$. Чаще всего для этого используется норма $L^2$, хотя выбор может падать и на $L^\infty$.
Изучение линейного оператора $T_\mu$ сводится к анализу его сингулярных чисел и сингулярных векторов. Геометрически действие любой матрицы можно представить как трансформацию единичного шара в эллипсоид, где главные полуоси соответствуют сингулярным числам $\sigma_i$, а их прообразы — ортонормированным сингулярным векторам $v_i$.
Сингулярные числа являются квадратными корнями из собственных значений матрицы $M^* M$, а наибольшее сингулярное число $\sigma_1$ определяет операторную норму матрицы. Поскольку оператор $T_\mu$ выполняет усреднение, для константной функции единица он всегда возвращает единицу: $T_\mu(1) = 1$.
📊 Нормы операторов и сохранение ортогональности 13:46
Базовая лемма, предложенная лектором, гласит, что норма $L^2$ функции после применения оператора блужания не превышает ее исходной нормы:
$$|T_\mu(F)|{L^2} \le |F|{L^2}$$
Для доказательства этого факта свертка переписывается как линейная комбинация сдвинутых версий функции $F$, где оператор правого сдвига определяется как $R_{g_2}(F)(g) = F(g \cdot g_2^{-1})$. Так как сдвиг просто переставляет значения функции местами, он не меняет ее $L^2$-норму. Применяя неравенство треугольника к линейной комбинации сдвигов, веса которых определяются вероятностями $\mu(g_2)$, сумма которых равна единице, мы получаем искомое ограничение.
Для понимания перемешивающих свойств блуждания критически важно изучить поведение оператора на подпространстве, ортогональном константам. Лектор обозначает его как $L^2(G_0)$ — пространство функций с нулевым средним значением:
$$L^2(G_0) = \left{ F \in L^2(G) \;\middle|\; \sum_{g \in G} F(g) = 0 \right}$$
Вторая лемма подтверждает, что оператор $T_\mu$ переводит это пространство само в себя. Сумма значений функции $T_\mu(F)$ после несложных алгебраических преобразований распадается на произведение двух сумм — значений самой функции $F$ и значений меры $\mu$. Поскольку первая сумма равна нулю по определению пространства $L^2(G_0)$, результат применения оператора также сохраняет нулевое среднее. Это означает, что константная функция отделяется от остальной части спектра оператора.
📈 Скорость перемешивания и теорема Сельберга 20:30
Наибольшее сингулярное значение оператора на пространстве функций с нулевым средним обозначается как $\sigma_1(T_\mu)$. Лектор выводит ключевое утверждение, связывающее это число со скоростью перемешивания случайного блуждания: норма разности между распределением после $k$ шагов и равномерным распределением ограничена величиной $\sigma_1(T_\mu)^k$.
При разбиении дельта-функции на константную и «высокочастотную» (с нулевым средним) составляющие, константная часть при вычитании равномерного распределения взаимно уничтожается. Оставшаяся часть оценивается через сингулярное число оператора. Если математикам удается подобрать такое количество шагов $k$, при котором величина $\sigma_1(T_\mu)^k$ становится меньше, чем $1/(100|G|)$, то отклонение распределения в любой точке (норма $L^\infty$) гарантированно составит менее 1% от эталона. В таком случае блуждание считается полностью перемешанным.
В качестве фундаментального примера рассматривается специальная матричная группа $SL_2(\mathbb{F}_p)$ над конечным полем. Агнер Сельберг в конце 1950-х годов исследовал естественную равномерную меру на симметричном наборе из четырех образующих матриц данной группы. Современная формулировка следствия из его классической теоремы утверждает: существует универсальная константа $c > 0$ (например, порядка $1/100$), такая что для любого простого числа $p$ старшее сингулярное число оператора блуждания строго ограничено:
$$\sigma_1(T_A) \le 1 - c$$
Это означает, что такое блуждание перемешивается чрезвычайно быстро вне зависимости от размера поля. Отвечая на вопрос из аудитории, лектор отмечает, что ему неизвестно точное поведение спектра при изменении $p$ — колеблется ли оно или сходится к фиксированному пределу. Сам Сельберг формулировал теорему для первого собственного значения оператора Лапласа на гиперболической поверхности, выдвинув гипотезу о том, что оно должно стремиться к $1/4$ при росте $p$, однако при переходе от геометрии поверхностей к дискретным графам точные константы неизбежно искажаются.
🕸️ Графы-экспандеры и геометрическое расширение 31:08
Любой симметричный набор образующих $A$ в конечной группе позволяет построить граф Кэли $\mathcal{C}(G, A)$. Вершинами графа выступают элементы группы, а ребро между $g_1$ и $g_2$ проводится тогда и только тогда, когда $g_2 = g_1 \cdot a$ для некоторого $a \in A$. Случайное блуждание на группе в такой интерпретации превращается в классическое случайное блуждание по ребрам графа.
Лектор доказывает важное геометрическое свойство таких графов через спектральные характеристики оператора. Количество ребер между произвольным подмножеством вершин $S$ и его дополнением $S^c$ подчиняется строгому неравенству:
$$|E(S, S^c)| \ge (1 - \sigma_1(T_A)) \cdot |A| \cdot \frac{|S||S^c|}{|G|}$$
Если бы граф был абсолютно случайным, доля ребер, ведущих из $S$ наружу, в среднем составляла бы $|S^c|/|G|$. Теорема показывает, что реальное количество ребер составляет фиксированную значительную долю от этого идеального случайного значения, если $\sigma_1$ строго меньше единицы.
В случае, если размер множества $S$ не превышает половины всего графа, из формулы вытекает, что число выходящих ребер пропорционально размеру самого множества. Графы с таким свойством называют экспандерами (или расширяющимися графами). В качестве контрпримера лектор приводит обычную двумерную сетку размером $n \times n$ с общим числом вершин $n^2$. Сетку можно легко разрезать пополам вертикальной линией, удалив всего $n$ ребер, что несопоставимо мало по сравнению с объемами половин множества.
[Image comparing the expansion properties of an expander graph versus a 2D grid graph]
Экспандеры же разрезать подобным образом невозможно — для разделения графа пополам всегда требуется удалить колоссальное количество связей. То, что образующие группы Сельберга порождают экспандеры, стало исторически первым доказательством существования таких объектов. Сами экспандеры были формально описаны Пинскером лишь в 1970 году, а также близко к этому Колмогоровым и Барздиным в 1960-х.
Отвечая на вопрос, зачем требовать, чтобы множество $A$ именно генерировало группу, лектор поясняет: если образующие порождают лишь собственную подгруппу $H$, граф распадается на несвязанные компоненты. Блуждание никогда не сможет покинуть пределы $H$, перемешивание станет невозможным, а спектральный зазор закроется ($\sigma_1 = 1$).
🧬 Метод Сарнака — Сю: сила теории представлений 46:57
Оригинальное доказательство Сельберга базировалось на глубоком анализе гиперболической геометрии и опиралось на гипотезу Римана для кривых над конечными полями. Из-за колоссального объема сопутствующей алгебраической геометрии полное развернутое доказательство занимало несколько сотен страниц. Однако в начале 1990-х годов математики Питер Сарнак и Кристиан Сю предложили принципиально более простое и изящное доказательство, изучению которого посвящена оставшаяся часть лекции.
Первый ключевой элемент этого метода опирается на теорию представлений группы $SL_2(\mathbb{F}_p)$. Унитарное представление представляет собой гомоморфизм группы в группу унитарных матриц размерности $D$. Лектор формулирует фундаментальное утверждение: размерность любого нетривиального унитарного представления этой группы жестко ограничена снизу величиной:
$$D \ge \frac{p+1}{2}$$
Для контекста: любая группа действует на пространстве функций $L^2(G)$ путем сдвигов. Для $SL_2(\mathbb{F}_p)$ размерность этого пространства огромна и составляет порядка $p^3$. Если рассмотреть действие группы на смежных классах по ее подгруппам, например, по диагональной подгруппе (размер порядка $p$) или унипотентной подгруппе (размер $p$), то максимальной подгруппой оказывается верхнетреугольная подгруппа Бореля $B$ размером порядка $p^2$. Пространство $L^2(G/B)$ имеет размерность порядка $p^3/p^2 = p$, что задает правильный порядок величины. В отличие от абелевых групп, где все неприводимые представления строго одномерны, в $SL_2(\mathbb{F}_p)$ все нетривиальные представления обязаны обладать огромной размерностью.
Для доказательства этого факта рассматриваются две базовые матрицы, генерирующие всю группу:
$$U = \begin{pmatrix} 1 & 1 \ 0 & 1 \end{pmatrix}, \quad V = \begin{pmatrix} 1 & 0 \ 1 & 1 \end{pmatrix}$$
В любом нетривиальном представлении $\rho$ хотя бы одна из этих матриц (пусть это будет $U$) не переходит в единичную матрицу. Специфическое свойство матрицы $U$ заключается в том, что при сопряжении с помощью диагональной матрицы она оказывается сопряжена своим собственным степеням вида $U^{a^2}$ для любого скаляра $a$. Следовательно, в представлении матрица $\rho(U)$ сопряжена матрице $\rho(U)^{a^2}$. Поскольку сопряженные матрицы обладают идентичными наборами собственных значений, спектр матрицы $\rho(U)$ должен быть инвариантен относительно возведения собственных значений в степень $a^2$.
С другой стороны, очевидно, что $U^p = I$, а значит, и $\rho(U)^p = I$. Это означает, что все собственные значения матрицы $\rho(U)$ являются комплексными корнями $p$-й степени из единицы. Если у матрицы есть хотя бы одно собственное значение $\lambda \neq 1$, то все его степени $\lambda^{a^2} \pmod p$ также обязаны быть ее собственными значениями. В поле $\mathbb{F}_p$ существует ровно $\frac{p-1}{2}$ различных квадратичных вычетов, и все соответствующие корни из единицы будут уникальными. Наличие такого огромного количества различных собственных значений у одной матрицы физически возможно только в том случае, если размерность пространства $D$ не меньше, чем $\frac{p+1}{2}$.
🧮 Кратность собственных значений и финальная оценка 1:02:15
Второе предложение метода Сарнака — Сю связывает размерность представлений со спектральным радиусом оператора блужания $\sigma_1(T_\mu)$ для произвольной вероятностной меры:
$$\sigma_1(T_\mu)^2 \cdot \frac{D+1}{2} \le |SL_2(\mathbb{F}p)| \cdot |\mu|{L^2}^2$$
Применяя алгебраические упрощения, лектор сводит это выражение к красивой оценке: квадрат старшего сингулярного числа не превышает величину порядка $\frac{1}{p^2} |\mu|_{L^2}^2$.
Ключевое линейно-алгебраическое наблюдение состоит в том, что на собственных подпространствах симметричной матрицы $T_\mu T_\mu^*$ естественным образом определено действие группы $G$. Поскольку оператор правой свертки коммутирует с оператором левого сдвига функций на группе, группа переводит собственные векторы оператора в собственные векторы с тем же самым собственным значением. За исключением тривиального одномерного пространства константных функций, это действие на собственных подпространствах является нетривиальным. А так как любое нетривиальное представление этой группы имеет огромную размерность, каждое из старших собственных значений обязано обладать колоссальной кратностью — как минимум $\frac{p+1}{2}$.
Согласно матричной алгебре, сумма квадратов всех сингулярных чисел оператора с учетом их кратности в точности равна его норме Гильберта — Шмидта (сумме квадратов всех элементов матрицы). Для оператора свертки эта сумма легко вычисляется и оказывается равной произведению размера группы на $L^2$-норму исходной меры: $|G| \cdot |\mu|_{L^2}^2$. С другой стороны, поскольку максимальное сингулярное значение $\sigma_1$ повторяется в спектре огромное число раз, общая сумма спектра мажорируется снизу величиной $\frac{p+1}{2} \sigma_1^2$. Это дает искомое неравенство.
В качестве прямого следствия лектор выводит универсальное правило для блужания по любому подмножеству $A \subset SL_2(\mathbb{F}p)$ с равномерным распределением, где $|\mu_A|{L^2}^2 = 1/|A|$. Оценка принимает вид:
$$\sigma_1(T_A)^2 \le \frac{p^2}{|A|}$$
Из этой формулы напрямую следует математический закон перемешивания на конечных группах:
- Если размер подмножества $A$ существенно превосходит $p^2$ (например, составляет $10p^2$ или $p^{2+\epsilon}$), то блуждание гарантированно и крайне быстро перемешивается до равномерного состояния.
- Если подмножество $A$ меньше, чем $p^2$, оно рискует целиком оказаться внутри какой-либо подгруппы (например, подгруппы Бореля размером порядка $p^2$), и тогда перемешивания не произойдет вовсе.
Этот результат дает исчерпывающий и точный ответ на вопрос о связи размера множества образующих и скорости перемешивания, демонстрируя фундаментальное отличие некоммутативных матричных групп от классических коммутативных систем. Однако парадокс заключается в том, что в теореме Сельберга размер множества $A$ равен всего четырем, что намного меньше барьера $p^2$. Разрешению этого противоречия и будет посвящена следующая лекция.
