Теория решета

Теория решета — это совокупность общих методов в теории чисел, предназначенных для подсчёта, или — что более реалистично — оценки размера просеянных множеств целых чисел. Типичным примером просеянного множества является множество простых чисел до заданного предела ${\displaystyle X}$. Соответственно, типичным примером решета является решето Эратосфена, либо более обобщённое решето Лежандра. Прямой подход к анализу простых чисел с использованием этих методов довольно быстро сталкивается с, казалось бы, непреодолимыми трудностями, связанными с накоплением ошибок. Одним из главных направлений теории чисел в XX веке стало развитие способов обхода этих трудностей и отказ от наивного подхода к просеиванию.

Один из успешных подходов состоит в аппроксимации конкретного просеянного множества (например, множества простых чисел) другим, более простым (например, множеством полупростых), которое обычно немного больше, но легче поддаётся анализу. Более изощрённые решета работают не с самими множествами, а подсчитывают их с помощью тщательно подобранных весовых функций — функций, придающих разным элементам различные веса. Более того, в некоторых современных приложениях решето используют не для оценки размера множества, а для построения функции, которая принимает большие значения на этом множестве и малые — вне его, при этом оставаясь проще для анализа, чем характеристическая функция множества.

Термин решето впервые ввёл норвежский математик Вигго Брун в 1915 году.^[1] Однако работа Бруна была вдохновлена трудами французского математика Жана Мерлина, погибшего в Первой мировой войне, от которого сохранились лишь две рукописи.^[2]

Обозначения см. в конце статьи. Мы следуем Анзац-подходу из книги Opera de Cribro Джона Фридлендера и Генрика Иваньеца.^[3]

Начнём с некоторой счётной последовательности неотрицательных чисел ${\displaystyle {\mathcal {A}}=(a_{n})}$. В базовом случае эта последовательность — просто индикаторная функция ${\displaystyle a_{n}=1_{A}(n)}$ для множества ${\displaystyle A=\{s:s\leq x\}}$, которое мы хотим просеять. Однако это абстрактное представление позволяет рассматривать более общие ситуации.

Далее вводится общее множество простых чисел, называемое областью просеивания, ${\displaystyle {\mathcal {P}}\subseteq \mathbb {P} }$ и их произведение до ${\displaystyle z}$ как функция ${\displaystyle P(z)=\prod \limits _{p\in {\mathcal {P}},p<z}p}$.

Цель теории решёт — оценить функцию просеивания ${\displaystyle S({\mathcal {A}},{\mathcal {P}},z)=\sum \limits _{n\leq x,{\text{gcd}}(n,P(z))=1}a_{n}.}$

В случае ${\displaystyle a_{n}=1_{A}(n)}$ это просто подсчёт мощности подмножества ${\displaystyle A_{\operatorname {sift} }\subseteq A}$, состоящего из чисел, взаимно простых с простыми делителями ${\displaystyle P(z)}$.

Для ${\displaystyle {\mathcal {P}}}$ определим ${\displaystyle A_{\operatorname {sift} }:=\{a\in A|(a,p_{1}\cdots p_{k})=1\},\quad p_{1},\dots ,p_{k}\in {\mathcal {P}}}$ а для каждого простого ${\displaystyle p\in {\mathcal {P}}}$ обозначим подмножество ${\displaystyle E_{p}\subseteq A}$ кратных ${\displaystyle E_{p}:=\{pn:n\in \mathbb {N} \}}$ и ${\displaystyle |E_{p}|}$ — его мощность.

Пусть, например, ${\displaystyle {\mathcal {P}}:=\{2,3,5,7,11,13\dots \}}$. Чтобы посчитать мощность множества ${\displaystyle A_{\operatorname {sift} }}$, можно применить принцип включения–исключения:

1. Вычесть из ${\displaystyle |A|}$ множества ${\displaystyle |E_{2}|}$ и ${\displaystyle |E_{3}|}$, 2. Добавить ${\displaystyle |E_{6}|}$ (чтобы компенсировать двойное вычитание), 3. Вычесть ${\displaystyle |E_{5}|}$, добавить ${\displaystyle |E_{10}|}$ и ${\displaystyle |E_{15}|}$, 4. Затем вычесть ${\displaystyle |E_{30}|}$ — числа, делящиеся на ${\displaystyle 2,3}$ и ${\displaystyle 5}$ одновременно.

Это даёт: ${\displaystyle |A_{\operatorname {sift} }|=|A|-|E_{2}|-|E_{3}|+|E_{6}|-|E_{5}|+|E_{10}|+|E_{15}|-|E_{30}|+\cdots }$

Можно записать это так: ${\displaystyle |A_{\operatorname {sift} }|=\sum \limits _{d|P}\mu (d)|E_{d}|}$

где ${\displaystyle \mu }$ — функция Мёбиуса, ${\displaystyle P:=\prod \limits _{p\in {\mathcal {P}}}p}$, а ${\displaystyle E_{1}:=A}$.

Функцию просеивания можно переписать как тождество Лежандра: ${\displaystyle S({\mathcal {A}},{\mathcal {P}},z)=\sum \limits _{d\mid P(z)}\mu (d)A_{d}(x)}$

с помощью функции Мёбиуса и функций ${\displaystyle A_{d}(x)}$, определённых по элементам ${\displaystyle {\mathcal {P}}}$:

${\displaystyle A_{d}(x)=\sum \limits _{n\leq x,n\equiv 0{\pmod {d}}}a_{n}.}$

Пусть ${\displaystyle z=7}$ и ${\displaystyle {\mathcal {P}}=\mathbb {P} }$. Функция Мёбиуса отрицательна для каждого простого, так что:

${\displaystyle {\begin{aligned}S({\mathcal {A}},\mathbb {P} ,7)&=A_{1}(x)-A_{2}(x)-A_{3}(x)-A_{5}(x)+A_{6}(x)+A_{10}(x)+A_{15}(x)-A_{30}(x).\end{aligned}}}$

Пусть ${\displaystyle A_{d}(x)}$ можно записать как

${\displaystyle A_{d}(x)=g(d)X+r_{d}(x)}$

где ${\displaystyle g(d)}$ — плотность, то есть мультипликативная функция такая, что ${\displaystyle g(1)=1,\qquad 0\leq g(p)<1\qquad p\in \mathbb {P} }$, ${\displaystyle X}$ — аппроксимация ${\displaystyle A_{1}(x)}$, а ${\displaystyle r_{d}(x)}$ — остаточный член.

Функция просеивания становится:

${\displaystyle S({\mathcal {A}},{\mathcal {P}},z)=X\sum \limits _{d\mid P(z)}\mu (d)g(d)+\sum \limits _{d\mid P(z)}\mu (d)r_{d}(x)}$

или кратко: ${\displaystyle S({\mathcal {A}},{\mathcal {P}},z)=XG(x,z)+R(x,z).}$

Оценка функции просеивания сводится к нахождению верхней и нижней грнаницы для ${\displaystyle S}$, ${\displaystyle G}$ и ${\displaystyle R}$.

Сумма по включению–исключению чередует пере- и недоучёт, так что остаточный член может быть очень велик. Брун предложил улучшение — заменить ${\displaystyle \mu (d)}$ в функции просеивания на весовую последовательность ${\displaystyle (\lambda _{d})}$, ограничивающую поведение. Подобрав две последовательности ${\displaystyle (\lambda _{d}^{-})}$ и ${\displaystyle (\lambda _{d}^{+})}$ и обозначив соответствующие функции ${\displaystyle S^{-}}$ и ${\displaystyle S^{+}}$, получаем:

${\displaystyle S^{-}\leq S\leq S^{+}.}$^[3]

Поскольку ${\displaystyle g}$ мультипликативна, также выполняется:

${\displaystyle \sum \limits _{d\mid n}\mu (d)g(d)=\prod \limits _{\begin{array}{c}p|n;\;p\in \mathbb {P} \end{array}}(1-g(p)),\quad \forall \;n\in \mathbb {N} .}$

Примечание по обозначениям: В литературе часто отождествляют последовательность ${\displaystyle {\mathcal {A}}}$ с множеством ${\displaystyle A}$. Это означает, что можно писать ${\displaystyle {\mathcal {A}}={s:s\leq x}}$ для задания последовательности ${\displaystyle {\mathcal {A}}=(a_{n})}$. Также сумма ${\displaystyle A_{d}(x)}$ иногда обозначается как мощность множества ${\displaystyle |A_{d}(x)|}$, хотя здесь ${\displaystyle A_{d}(x)}$ уже обозначает саму эту мощность. Мы используем ${\displaystyle \mathbb {P} }$ для множества простых чисел и ${\displaystyle (a,b)}$ — для наибольшего общего делителя чисел ${\displaystyle a}$ и ${\displaystyle b}$.

Современные решета включают решето Бруна, решето Селберга, решето Турана, большое решето и решето Гольдстона — Пинтца — Йылдырыма.

Первоначальная цель теории решета заключалась в доказательстве гипотез теории чисел, таких как гипотеза о простых близнецах. Хотя широкие цели решетной теории пока не достигнуты, были получены некоторые частичные успехи — особенно в сочетании с другими методами теории чисел. Среди них:

Теорема Бруна — показывает, что сумма обратных к простым-близнецам сходится (в отличие от суммы обратных ко всем простым числам, которая расходится);

Теорема Чена — утверждает, что существует бесконечно много простых чисел ${\displaystyle p}$ таких, что ${\displaystyle p+2}$ — либо простое, либо полупростое (произведение двух простых); тесно связанная теорема Чен Цзинжуна утверждает, что любое достаточно большое чётное число представимо как сумма простого и числа, которое либо простое, либо полупростое. Эти результаты считаются «почти попаданием» в гипотеза о простых близнецах и гипотезу Гольдбаха соответственно;

Фундаментальная лемма теории решета — утверждает, что если просеивается множество из ${\displaystyle N}$ чисел, то можно точно оценить количество оставшихся после ${\displaystyle N^{\varepsilon }}$ итераций, если ${\displaystyle \varepsilon }$ достаточно мало (в типичных случаях — около 1/10). Эта лемма недостаточна для отбора только простых чисел (требуется около ${\displaystyle N^{1/2}}$ итераций), но позволяет получать результаты о полупростых числах;

Теорема Фридландера — Иванца — утверждает, что существует бесконечно много простых чисел вида ${\displaystyle a^{2}+b^{4}}$;

Теорема Чжана (американского математика китайского происхождения Чжана Итана)^[4] доказывает существование бесконечно многих пар простых на ограниченном расстоянии друг от друга.

Теорема Мейнарда—Тао (английского математика Джеймса Мейнарда)^[5] обобщает результат Чжана на произвольно длинные последовательности простых.

Методы решета могут быть весьма мощными, но, как считается, они ограничены препятствием, известным как проблема чётности, которая (в грубом приближении) заключается в том, что методы решета с трудом различают числа с нечётным и чётным числом простых делителей. Эта проблема остаётся малоизученной.

По сравнению с другими методами теории чисел, решетные методы относительно элементарны: они не требуют использования развитых понятий из алгебраической или аналитической теории чисел. Тем не менее, более продвинутые виды решет могут быть весьма сложными, особенно в сочетании с глубокими методами теории чисел. Существуют целые монографии, посвящённые исключительно теории решет — классическая работа: (Halberstam & Richert 1974), современное изложение — (Iwaniec & Friedlander 2010).

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

Решето Эратосфена

Решето Бруна

Полупростое число

Cojocaru, Alina Carmen; Murty, M. Ram. An Introduction to Sieve Methods and Their Applications. Cambridge University Press, 2005.

Halberstam, Heini; Richert, Hans-Egon. Sieve Methods. Academic Press, 1974.

Friedlander, John B.; Iwaniec, Henryk. Opera de Cribro. American Mathematical Society, 2010.

Maynard, James. Small gaps between primes. Annals of Mathematics, 181 (1): 383–413, 2015.

Zhang, Yitang. Bounded gaps between primes. Annals of Mathematics, 179 (3): 1121–1174, 2014.

«Sieve method» в Encyclopedia of Mathematics