Линник: большое решето

Что такое решето

Решето — общее название методов, оценивающих количество чисел, не делящихся на набор данных простых.

Идея восходит к Эратосфену: вычёркиваем кратные $2$, потом кратные $3$ и так далее. Формула включений-исключений даёт точный ответ, но с $2^{k}$ слагаемыми, и погрешности накапливаются быстрее, чем главный член.

Вигго Брун в 1919 году придумал, как обрезать это чередование так, чтобы ошибка оставалась под контролем, и получил первые нетривиальные результаты о простых-близнецах: их сумма обратных величин сходится (константа Бруна $\approx1{,}9022$), а всякое достаточно большое чётное число есть сумма двух чисел не более чем с девятью простыми множителями каждое. Сельберг в 1940-е придал решету оптимальную квадратичную форму.

Все эти решёта — «малые»: они просеивают по небольшим простым модулям.

Большое решето

Юрий Владимирович Линник (1915–1972) в 1941 году предложил принципиально другую конструкцию, назвав её большим решетом: просеивать сразу по всем классам вычетов по всем модулям до некоторой границы $Q$, причём $Q$ может быть велико — сравнимо с корнем из длины интервала.

Обычное решето убирает по одному остатку на каждый модуль, большое — сразу многоMathLocus · построено для этого сайта

Современная форма его неравенства такова. Пусть $a_n$ — произвольные комплексные числа, $S(\alpha)=\sum_{n\leqslant N}a_n e^{2\pi i n\alpha}$. Тогда

$$\boxed{\;\sum_{q\leqslant Q}\ \sum_{\substack{a=1\\ \gcd(a,q)=1}}^{q}\left|S\!\left(\frac aq\right)\right|^{2}\;\leqslant\;\left(N+Q^{2}\right)\sum_{n\leqslant N}|a_n|^{2}\;}$$

Читается так: сумма квадратов значений тригонометрической суммы во всех рациональных точках с малыми знаменателями не превосходит того, что дал бы «случайный» набор коэффициентов. Это утверждение о том, что экспоненты $e^{2\pi i n a/q}$ ведут себя почти как ортогональная система, и по существу является аналитическим фактом — доказательства проходят через неравенство двойственности или через оценки Гальярдо и Монтгомери. Число $N+Q^{2}$ оптимально по порядку.

Название «решето» здесь историческое: неравенство само по себе просеиванием не является, но именно из него получаются решётные оценки, и притом с гораздо большим числом модулей, чем допускали методы Бруна и Сельберга.

Куда это привело

Теорема Бомбьери — Виноградова (1965), важнейшее прямое следствие. Обозначим через $\pi(x;q,a)$ число простых до $x$ в прогрессии $a\bmod q$. Тогда

$$\sum_{q\leqslant\sqrt{x}/(\ln x)^{B}}\ \max_{\gcd(a,q)=1}\left|\pi(x;q,a)-\frac{\mathrm{li}(x)}{\varphi(q)}\right|\;\ll\;\frac{x}{(\ln x)^{A}} .$$

Смысл: в среднем по модулям простые распределяются по прогрессиям так же хорошо, как это предсказывала бы обобщённая гипотеза Римана. Гипотезу не доказали — но её следствие «в среднем» получили безусловно, и для большинства приложений этого достаточно. Теорему так и называют: «ГРГ для бедных».

Дальше из неё выходит почти всё современное:

теорема Чэня (1966): всякое достаточно большое чётное число есть $p+m$, где $m$ имеет не более двух простых множителей — сильнейшее продвижение в бинарной проблеме Гольдбаха;
теорема Чжана (2013): существует бесконечно много пар простых, отличающихся не более чем на 70 миллионов, — первое в истории безусловное продвижение к гипотезе о близнецах; после работы Мейнарда, Тао и проекта Polymath разрыв снижен до 246;
оценки в теореме Грина — Тао о прогрессиях в простых.

Отдельно Линнику принадлежит теорема о наименьшем простом в прогрессии (1944): если $\gcd(a,q)=1$, то в прогрессии $a\bmod q$ есть простое, не превосходящее $q^{L}$, где $L$ — абсолютная постоянная. Он не вычислил её; сегодня известно, что $L\leqslant5$ (Ксилурис, 2011), а гипотетически $L=2$ с точностью до логарифмов.

Год и город

Заметка вышла в «Докладах Академии наук СССР» в 1941 году — в Ленинграде, в год начала блокады. Линнику было 26 лет. Он ушёл в ополчение, был отозван, работал в эвакуации в Казани, вернулся в Ленинград и создал там школу, из которой вышли, среди прочих, Матиясевич и Малышев.

Ему же принадлежит дисперсионный метод (1958–61) — ещё один общий приём, которым он доказал, что всякое достаточно большое число есть сумма простого и двух квадратов, и решил проблему Харди — Литлвуда о представлении чисел суммой простого и двух квадратов. И эргодический метод в теории чисел: связь распределения целых точек на сферах с теорией динамических систем, направление, которое расцвело только в 1980-е.

Задача. Проверьте на простом примере, что неравенство большого решета не улучшить: положите $a_n=1$ для всех $n\leqslant N$ и $Q=1$. Что даёт левая часть, что правая?
(Ответ: слева единственное слагаемое $|S(1)|^{2}=N^{2}$; справа $(N+1)\cdot N$. Неравенство верно и почти точно — множитель $N+Q^{2}$ нельзя заменить на существенно меньший.)

Следующая точка: Принстон — где теорему о распределении простых докажут заново, без анализа, и поссорятся из-за этого навсегда.