В рамках академического курса MIT OpenCourseWare профессор Лоуренс Гат представляет лекцию, посвященную теории решет и методу большого решета. Этот математический аппарат, зародившийся в недрах аналитической теории чисел, демонстрирует, как случайные проекции сложных числовых множеств приводят к неожиданному статистическому сглаживанию данных. Исследуя фундаментальную теорему Линника, Гат раскрывает глубокие связи между распределением простых чисел и многомерным вещественным анализом, предлагая слушателям интуитивный геометрический взгляд на сложные алгебраические структуры.
🧮 Постановка задачи и концепция большого решета 0:12
Контекст метода большого решета (the large sieve) исторически связан с аналитической теорией чисел. По определению, предложенному профессором Лоуренсом Гатом, в качестве отправной точки рассматривается функция $f$, заданная на множестве целых чисел от $1$ до $N$. Основная идея заключается в том, чтобы проанализировать, что происходит с этой функцией при редукции чисел по модулю простого числа $p$.
Для этого вводится оператор проекции $\pi_p(f)$, который отображает кольцо вычетов $\mathbb{Z}/p\mathbb{Z}$ в комплексные числа $\mathbb{C}$. Значение этой проекции в точке $a$ задается формулой:
$$\pi_p f(a) = \sum_{n \equiv a \pmod p} f(n)$$
Как подчеркивает лектор, суть большого решета заключается в одновременном рассмотрении множества таких проекций для большого количества различных простых чисел $p$, чтобы выявить их типичное поведение и взаимосвязь.
Для удобства анализа функцию целесообразно разделить на две составляющие:
- Постоянную часть (среднее значение);
- Осциллирующую часть с нулевым средним значением.
Постоянная часть $f_0$ представляет собой константу, равную среднему значению функции на исходном интервале:
$$f_0 = \frac{1}{N} \sum_{n=1}^N f(n)$$
Вычитая ее из исходной функции, мы получаем осциллирующую («высокую») часть $f_H = f - f_0$, сумма значений которой равна нулю. В процессе записи формул на доске Гат делает шутливую ремарку о том, что выбранное им обозначение может быть опасным, и во избежание путаницы явно переписывает его в виде заглавной буквы $H$. Аналогичное разделение применяется и к проекциям функций.
Один из слушателей в аудитории просит уточнить, что именно означают квадратные скобки в определении постоянной части $f_0$. Лоуренс Гат поясняет, что в данном контексте это обычные круглые скобки, внутри которых находится число, задающее среднее значение функции.
Главная тема и интуитивная идея большого решета, по словам Гата, заключается в следующем: если взять практически произвольную функцию и построить множество ее различных модулярных проекций, то осциллирующая, высокочастотная часть этих проекций в среднем окажется очень мала. В то же время постоянная часть, зависящая исключительно от $f_0$, может оставаться существенно большей.
📜 Теорема Линника и геометрическая жесткость квадратов 5:17
Фундаментальным результатом в этой области является теорема, впервые доказанная советским математиком Юрием Линником. Пусть $P_M$ — множество простых чисел $p$, лежащих в диапазоне:
$$\frac{M}{2} < p < M$$
Теорема Линника утверждает, что если функция $f$ отображает целые числа в $\mathbb{C}$, а параметр $M$ не превышает $\sqrt{N}$, то сумма $L^2$-норм высокочастотных компонентов проекций по всем $p \in P_M$ ограничена:
$$\sum_{p \in P_M} |\pi_p f_H|{L^2}^2 \le \frac{N}{M} \sum{n=1}^N |f_H(n)|^2$$
Чтобы осмыслить эту оценку, профессор предлагает обратиться к базовым фактам аналитической теории чисел. Согласно теореме о распределении простых чисел, количество элементов в множестве $P_M$ примерно равно $M / \log M$, что для грубых оценок можно принять за величину порядка $M$. Из этого вытекает важное следствие: если заменить сумму в левой части теоремы на среднее значение по всем простым числам диапазона, то средняя $L^2$-норма осциллирующей части проекции будет ограничена величиной порядка $N/M^2$, умноженной на исходную энергию функции.
Для демонстрации силы этого метода лектор приводит пример с квадратами целых чисел, который кратко упоминался на прошлой лекции. Квадраты обладают уникальным свойством: при их редукции по модулю $p$ они могут давать только квадратичные вычеты, количество которых ограничено величиной $(p+1)/2$. Таким образом, они заполняют лишь около половины всех возможных классов вычетов.
Задавшись вопросом о том, что можно сказать о произвольном множестве $A \subset {1, \dots, N}$, чьи проекции по модулю $p$ существенно меньше самого числа $p$, Гат формулирует геометрическое следствие. Если для всех простых чисел $p$ порядка $\sqrt{N}$ размер поддержки проекции $\pi_p(A)$ строго ограничен (например, меньше $0.99p$), то размер самого множества $A$ не может превышать величину порядка $\sqrt{N}$. Этот результат является точным и достигается как раз на множестве идеальных квадратов.
Для доказательства этого утверждения функция $f$ выбирается как характеристическая функция множества $A$. Если бы все значения проекции $\pi_p f(a)$ были равны между собой, то их величина составляла бы $|A|/p$, а сумма их квадратов была бы равна $|A|^2/p$. В случае неравномерного распределения, в силу неравенства Коши — Буняковского — Шварца, эта сумма будет только больше. С учетом того, что $p \sim \sqrt{N}$, данная величина оценивается снизу как $|A|^2 N^{-1/2}$.
Поскольку поддержка проекции ограничена долей $0.99p$, функция гарантированно далека от константы. Профессор Гат строго доказывает сопутствующую лемму: если поддержка функции $g$ на конечном множестве вычетов значительно меньше $p$, то $L^2$-норма ее высокочастотной части $g_H$ сопоставима с $L^2$-нормой всей функции $g$.
Доказательство строится на ортогональности константной и осциллирующей частей:
$$|g|{L^2}^2 = |g_0|{L^2}^2 + |g_H|_{L^2}^2$$
Если константная часть мала, утверждение очевидно. В противном случае мы рассматриваем дополнение к поддержке функции (множество $S$, где $g = 0$), на котором $g_H = -g_0$. Поскольку размер $S$ составляет фиксированную долю от $p$, сумма квадратов $g_H$ на этом множестве дает оценку снизу, пропорциональную общей норме функции.
Объединяя этот результат с ограничением из теоремы Линника, Гат демонстрирует, что среднее значение нормы высокочастотной части, с одной стороны, оценивается снизу через $|A|^2 N^{-1/2}$, а с другой стороны, ограничено сверху размером множества $|A|$. Из цепочки неравенств напрямую следует искомый верхний предел:
$$|A| \le \sqrt{N}$$
🎲 Вероятностный взгляд: сравнение со случайными множествами 18:16
Чтобы развить математическую интуицию и лучше прочувствовать «нумерологию» уравнений, профессор предлагает сопоставить полученный результат с поведением абсолютно случайного множества. В качестве мысленного эксперимента рассматривается подмножество $A \subset {1, \dots, N}$, в которое каждое число включается независимо с вероятностью $1/2$.
При проецировании такого случайного множества по модулю $p$ математическое ожидание количества элементов в конкретном классе вычетов $a$ будет в точности равно половине от общего числа кандидатов, то есть:
$$\mathbb{E}[\pi_p \mathbb{1}_A(a)] \approx \frac{N}{2p}$$
Естественно, в силу случайности выбора, реальное значение будет испытывать флуктуации. Стандартное отклонение для этой схемы Бернулли пропорционально квадратному корню из числа испытаний. С высокой вероятностью разница между реальным размером проекции и его ожидаемым значением будет ограничена корнем из $N/p$. Для простых чисел из диапазона $p \sim \sqrt{N}$ эта погрешность составит величину порядка $N^{1/4}$.
Большое решето приводит к удивительному выводу: абсолютно любое, даже самое сложное, сконструированное злонамеренным образом детерминированное множество («худший случай») при анализе через случайный модуль $p$ и случайный вычет $a$ ведет себя практически так же, как случайное множество.
Это утверждение кристаллизуется в третьем следствии лекции: для любого подмножества $A$ средний квадрат отклонения реальной проекции от ее математического ожидания по всем модулям и вычетам строго ограничен сверху величиной $N^{1/2}$. Извлекая квадратный корень с помощью неравенства Коши — Буняковского — Шварца, мы получаем среднее отклонение порядка $N^{1/4}$, что идеально совпадает с вероятностной оценкой для случайного множества.
Красивым и глубоким применением этой концепции является задача распределения простых чисел в арифметических прогрессиях. Математиков давно интересует вопрос: насколько равномерно распределены простые числа по различным направлениям $a \pmod p$? Граничная гипотеза утверждает, что такое равномерное распределение должно соблюдаться для всех без исключения ненулевых вычетов и модулей.
Доказанное следствие из большого решета делает фундаментальный шаг в этом направлении: оно гарантирует, что это свойство выполняется если не для всех, то для подавляющего большинства простых чисел и вычетов. Любопытно, как замечает Гат, что данное утверждение изначально вообще не использует никаких специфических свойств простых чисел — они рассматриваются просто как абстрактное подмножество целых чисел.
Тем не менее, этот подход лежит в основе одного из центральных результатов современной теории чисел — теоремы Бомбьери — Виноградова, которая долгие годы оставалась вершиной научной мысли в этой области и которую Гат обещает подробно разобрать на следующем занятии.
В завершение этого раздела профессор Гат предлагает концептуальное резюме: если взять достаточно плотное множество $A$, составляющее заметную долю от всего интервала $[1, N]$, то подавляющее большинство его модулярных проекций будут выглядеть почти как константы. Этот процесс проецирования детерминированной структуры без явных закономерностей уничтожает высокочастотные колебания. Математики называют этот эффект сглаживанием проекций (projections getting smoother).
В этот момент лектор отвечает на вопрос из зала касательно обозначений под знаком усреднения: символ $p \in P_{N^{1/2}}$ означает, что мы берем среднее по всем простым числам, чьи размеры близки к квадратному корню из $N$.
🔍 Анализ Фурье: мост между целыми числами и модулярными мирами 31:39
Строгое доказательство теоремы Линника базируется на переходе в спектральную область с помощью преобразования Фурье. Профессор напоминает слушателям математический инвентарь для двух параллельных миров: бесконечных целых чисел и конечных колец вычетов $\mathbb{Z}/p\mathbb{Z}$.
Для функции $f$, заданной на целых числах и имеющей конечную поддержку на отрезке $[1, N]$, преобразование Фурье определяет непрерывную функцию на окружности $\mathbb{R}/\mathbb{Z}$:
$$\hat{f}(\xi) = \sum_{n} f(n) e^{-2\pi i n \xi}$$
Для этого преобразования справедливы классическая формула обращения Фурье и теорема Планшереля (сохранение энергии):
$$\sum_{n} |f(n)|^2 = \int_{0}^{1} |\hat{f}(\xi)|^2 d\xi$$
Лектор обращает внимание на то, что это привычная теория рядов Фурье для периодических функций, где просто для удобства исходная функция и ее Фурье-образ поменялись местами в обозначениях.
[Image of Fourier transform of a function]
В то же время для дискретной функции $g$, заданной на конечном множестве $\mathbb{Z}/p\mathbb{Z}$, преобразование Фурье дает также дискретную функцию. Значение Фурье-коэффициента в спектральной точке $\alpha$ определяется как:
$$\hat{g}(\alpha) = \sum_{a \in \mathbb{Z}/p\mathbb{Z}} g(a) e^{-2\pi i a \alpha / p}$$
Соответственно, дискретная теорема Планшереля содержит нормировочный множитель:
$$\sum_{a} |g(a)|^2 = \frac{1}{p} \sum_{\alpha} |\hat{g}(\alpha)|^2$$
Связующим звеном между этими двумя пространствами выступает ключевая лемма-словарь (dictionary lemma). Она утверждает, что преобразование Фурье от модулярной проекции функции совпадает со значениями непрерывного преобразования Фурье исходной функции, вычисленными в рациональных точках вида $\alpha/p$:
$$\widehat{\pi_p(f)}(\alpha) = \hat{f}\left(\frac{\alpha}{p}\right)$$
Доказательство леммы элементарно и заключается в раскрытии двойной суммы. Разворачивая определение проекции, мы получаем сумму по всем $n$, сопоставимым с $a \pmod p$. Поскольку добавление к аргументу экспоненты целых кратных исходного модуля $p$ не меняет значения комплексного экспоненциального распределения, исходная дискретная структура шага редукции бесшовно преобразуется в непрерывный Фурье-образ целых чисел.
Используя этот «словарь», левую часть теоремы Линника можно переписать через Фурье-коэффициенты. Исключение нулевой частоты (что эквивалентно переходу к высокочастотной части $f_H$) означает, что мы суммируем значения спектра по всем ненулевым индексам $\alpha$.
Таким образом, задача сводится к оценке суммы квадратов модулей Фурье-образа функции в специфическом дискретном наборе точек на вещественной прямой. Этот набор точек обозначается как $Q_M$:
$$Q_M = \left{ \frac{\alpha}{p} \;\middle|\; \frac{M}{2} < p < M, \; 0 < \alpha \le p-1 \right}$$
Размер этого множества составляет величину порядка $M^2$. Важнейшим топологическим свойством этих рациональных дробей является то, что они распределены по вещественной оси очень равномерно.
Гат формулирует и доказывает лемму о расстоянии: любые две несовпадающие дроби из множества $Q_M$ отстоят друг от друга как минимум на величину $1/M^2$. Доказательство тривиально: разность двух дробей $\alpha_1/p_1 - \alpha_2/p_2$ приводится к общему знаменателю $p_1 p_2$. Так как числитель является ненулевым целым числом, его модуль не меньше единицы, а знаменатель не превышает $M^2$.
Выбор именно простых чисел в качестве модулей гарантирует, что одна и та же дробь не может быть записана двумя разными способами, что исключает нежелательные наложения точек в пространстве частот.
🎨 Гармонический баланс: эвристика узких пиков и строгое сглаживание 45:31
Для демонстрации физического смысла происходящего профессор чертит на доске график: отрезок от $0$ до $1$, на котором нанесены точки множества $Q_M$. На вертикальной оси откладывается квадрат модуля Фурье-преобразования функции $f_H$. Наша искомая сумма — это просто значения функции в этих дискретных точках. Ситуация напоминает интегральную сумму Римана, и естественным шагом является сравнение этой дискретной суммы с непрерывным интегралом Планшереля.
Однако возникает математическое препятствие: функция могла бы гипотетически иметь огромные, но экстремально узкие пики, сосредоточенные в точности в точках нашей сетки $Q_M$. Такой пик внес бы ничтожный вклад в интеграл, но сильно увеличил бы дискретную сумму.
Здесь на сцену выходит фундаментальный физический принцип локальной константности (locally constant heuristic): поскольку исходная функция $f$ сосредоточена на конечном пространственном интервале длины $N$, ее Фурье-образ не может меняться мгновенно — он обязан быть примерно постоянным на частотных интервалах длины $1/N$.
По условию теоремы Линника, верхняя граница диапазона $M$ не превышает $\sqrt{N}$. Это жестко гарантирует, что минимальное расстояние между точками нашей сетки ($1/M^2$) заведомо больше или равно ширине спектрального пика ($1/N$). Пики, локализованные в точках сетки, физически не могут быть изолированы друг от друга, они неизбежно перекрываются и размазываются по пространству.
Следовательно, значение в точке, умноженное на шаг, оценивается через интеграл по окрестности. Дальнейшие выкладки сводятся к аккуратной алгебре.
Профессор Гат с улыбкой признается аудитории в своей давней слабости:
«Когда вы переходите к теореме Планшереля по модулю $p$, там возникает нормировочный множитель $1/p$, который я постоянно забываю».
Учитывая, что $p \sim M$, этот множитель компенсирует избыточность суммирования, переводя общую оценку дискретной суммы в искомый вид теоремы Линника: $\frac{N}{M} \sum |f_H(n)|^2$.
В этот момент лектор предлагает глубокую физическую интерпретацию того, почему нулевая частота (константная часть) является выделенной в теории решет. Если представить каждую модулярную проекцию своим цветом радуги, то при нанесении их спектров на общую ось частот обнаружится удивительная картина.
Все ненулевые частоты различных модулей практически никогда не пересекаются между собой. Любая спектральная масса, помещенная в ненулевую точку, вносит вклад в проекцию только одного конкретного простого числа. Но нулевая частота (среднее значение) присутствует абсолютно во всех цветах спектра, в проекциях по каждому из простых чисел.
Поэтому при усреднении по семейству модулей все индивидуальные частотные колебания взаимно уничтожаются и подавляются, а константная составляющая непоколебимо сохраняется, доминируя в финальном сигнале.
Один из студентов интересуется, насколько мы свободны в выборе функции $f$, ведь в классических методах решета обычно исследуются строго характеристические функции подмножеств. Профессор поясняет, что аппарат большого решета универсален: функция может быть абсолютно любой, и ее математическая структура никак не привязана к свойству индикаторности, хотя в ряде теорем разреженность множеств накладывает свои интересные эффекты.
Для строгого доказательства эвристики локальной константности Гат вводит вспомогательную гладкую функцию среза $\psi_N$, которая равна единице на интервале $[1, N]$ и стремится к нулю за его пределами. Ее преобразование Фурье представляет собой пик высоты $N$ и ширины $1/N$.
Отвечая на вопрос с места о том, как можно говорить о «гладкости» для функции, заданной на дискретном множестве целых чисел, лектор предлагает изящное обобщение: мы конструируем гладкую функцию на всей вещественной прямой, а затем просто вычисляем ее значения в целочисленных точках.
Поскольку исходная функция $f$ не меняется при умножении на этот срез ($f = f \cdot \psi_N$), в частотной области это превращается в операцию свертки их Фурье-образов. Применяя неравенство Коши — Буняковского — Шварца, мы строго ограничиваем квадрат модуля исходной функции через интеграл свертки.
Слушатели просят уточнить, в каком именно смысле понимается Фурье-образ функции среза — как для дискретного или как для непрерывного случая. Профессор Гат разворачивает на доске формулы связи через формулу суммирования Пуассона. Периодический дискретный Фурье-образ получается путем периодического зацикливания (периодизации) непрерывного образа. Поскольку исходный непрерывный пик затухает колоссально быстро, влияние соседних хвостов периодизации в рабочей области от $-1/2$ до $1/2$ пренебрежимо мало.
Внося операцию суммирования по сетке $Q_M$ внутрь интеграла свертки, мы замечаем, что из-за отсутствия перекрытий между смещенными гладкими пиками вся сумма оперативно оценивается величиной порядка $N$, что полностью завершает строгое доказательство теоремы Линника. Попутно Гат напоминает студентам, что аналогичная эвристика содержится в их домашнем задании, которое необходимо сдать сегодня вечером, и приглашает всех на свои консультационные часы сразу после окончания лекции.
🌐 Аналогия в вещественном анализе: сглаживание в многомерных пространствах 1:10:26
В финальной части лекции профессор Гат перекидывает концептуальный мост из теории чисел в область многомерного вещественного анализа. Оказывается, феномен модулярного сглаживания имеет практически безупречный геометрический аналог в пространстве $\mathbb{R}^d$. Если рассмотреть функцию, заданную в многомерном пространстве, и начать строить ее проекции на подпространства меньшей размерности, то почти все полученные проекции будут обладать радикально лучшими свойствами гладкости, нежели исходная функция.
Профессор приводит поразительный пример: если мы работаем в пространстве достаточно большой размерности $d$, то даже если исходная функция принадлежит лишь классу $L^2$ и является разрывной абсолютно в каждой точке пространства, ее проекция на типичную случайную прямую линию гарантированно окажется не просто непрерывной, но и будет принадлежать классам дифференцируемости $C^1$, $C^2$ и выше.
Математический аппарат этой схемы полностью изоморфен нашему дискретному «словарю». Пусть $\pi_V(f)$ — оператор проекции функции на подпространство $V$. Лемма-словарь для вещественного анализа постулирует: преобразование Фурье от проекции функции на подпространство $V$ представляет собой не что иное, как ограничение (сужение) общего многомерного преобразования Фурье исходной функции на это подпространство:
$$\widehat{\pi_V(f)} = \hat{f}\big|_V$$
Геометрическая картина в спектральном пространстве выглядит следующим образом. Мы имеем исходную функцию из $L^2$, чья спектральная энергия распределена по многомерному пространству. Мы начинаем проводить через начало координат различные подпространства (например, прямые линии $V_1, V_2$). Все эти направления пересекаются в одной единственной критической точке — в начале координат (на нулевой частоте).
Любая спектральная масса, расположенная в области низких частот (вблизи нуля), автоматически улавливается и учитывается проекциями по всем без исключения направлениям $V$. Но если у функции есть огромный энергетический всплеск на далекой высокой частоте, он пересечется лишь с крайне узким, изолированным подмножеством направлений, практически не оказывая влияния на подавляющее большинство остальных случайных проекций.
В результате в случайно выбранной проекции низкие частоты искусственно гиперболизируются и доминируют, а высокие частоты радикально подавляются. Спектр проекции оказывается сосредоточен в узкой окрестности нуля, что на языке анализа означает фундаментальное сглаживание функции.
Этот феномен формализуется в виде финальной теоремы, анонсированной профессором: если функция $f \in L^2$ имеет поддержку в единичном многомерном шаре пространства $\mathbb{R}^d$, и размерность $d$ достаточно велика, то интеграл по сфере направлений от $C^k$-нормы одномерных проекций будет строго ограничен исходной $L^2$-энергией функции.
Завершая занятие, Лоуренс Гат призывает студентов еще раз вглядеться в поразительное изящество и гармонию этой математической аналогии. Радуга пересекающихся модулярных частот в большом решете теории чисел работает по абсолютно тем же законам, что и веер пересекающихся подпространств в многомерном вещественном анализе. Оба этих механизма, несмотря на разную природу, одинаково фильтруют хаос, выдвигая на передний план константную гармонию низких частот.
