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

Способы оценки размера просеянных наборов целых чисел

Теория решета — это набор общих методов в теории чисел , предназначенных для подсчета или, что более реалистично, оценки размера просеянных наборов целых чисел. Прототипическим примером просеянного набора является набор простых чисел до некоторого заданного предела X. Соответственно, прототипическим примером решета является решето Эратосфена или более общее решето Лежандра . Прямая атака на простые числа с использованием этих методов вскоре достигает, по-видимому, непреодолимых препятствий в виде накопления ошибок. ^{[ необходима цитата ]} В одном из основных направлений теории чисел в двадцатом веке были найдены способы избежать некоторых трудностей лобовой атаки с наивным представлением о том, каким должно быть просеивание. ^{[ необходима цитата ]}

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

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

Основная теория решета

Информацию об обозначениях см. в конце.

Начнем с некоторой счетной последовательности неотрицательных чисел . В самом простом случае эта последовательность — просто индикаторная функция некоторого множества, которое мы хотим просеять. Однако эта абстракция допускает более общие ситуации. Далее мы вводим общий набор простых чисел, называемый диапазоном просеивания , и их произведение вплоть до как функцию . ${\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}=\{pn:n\in \mathbb {N} \}}$ ${\displaystyle |E_{p}|}$

Теперь мы представим способ вычисления мощности . Для этого диапазон просеивания будет конкретным примером простых чисел . ${\displaystyle A_{\operatorname {sift} }}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {P}}:=\{2,3,5,7,11,13\dots \}}$

Если кто-то хочет вычислить мощность , можно применить принцип включения-исключения . Этот алгоритм работает следующим образом: сначала из мощности удаляется мощность и . Теперь, поскольку были удалены числа, которые делятся на и дважды, нужно добавить мощность . На следующем шаге нужно удалить и снова добавить и . Кроме того, теперь нужно удалить , т. е. мощность всех чисел, делящихся на и . Это приводит к принципу включения-исключения ${\displaystyle A_{\operatorname {sift} }}$ ${\displaystyle |A|}$ ${\displaystyle |E_{2}|}$ ${\displaystyle |E_{3}|}$ ${\displaystyle 2}$ ${\displaystyle 3}$ ${\displaystyle |E_{6}|}$ ${\displaystyle |E_{5}|}$ ${\displaystyle |E_{10}|}$ ${\displaystyle |E_{15}|}$ ${\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 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 A_{d}(x)}$ ${\displaystyle \mathbb {P} }$ ${\displaystyle (a,b)}$ ${\displaystyle a}$ ${\displaystyle b}$

Виды просеивания

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

1. Теорема Бруна , которая показывает, что сумма обратных величин простых чисел-близнецов сходится (тогда как сумма обратных величин всех простых чисел расходится);
2. Теорема Чена , которая показывает, что существует бесконечно много простых чисел p, таких, что p + 2 является либо простым, либо полупростым числом (произведением двух простых чисел); тесно связанная теорема Чена Цзинжуня утверждает, что каждое достаточно большое четное число является суммой простого числа и другого числа, которое является либо простым, либо полупростым. Их можно считать близкими к гипотезе о простых числах-близнецах и гипотезе Гольдбаха соответственно.
3. Основная лемма теории решета , которая утверждает, что если просеивать набор из N чисел, то можно точно оценить количество элементов, оставшихся в решете после итераций, при условии, что оно достаточно мало (такие дроби, как 1/10, здесь весьма типичны). Эта лемма обычно слишком слаба, чтобы отсеять простые числа (что обычно требует чего-то вроде итераций), но может быть достаточной для получения результатов относительно почти простых чисел. ${\displaystyle N^{\varepsilon }}$ ${\displaystyle \varepsilon }$ ${\displaystyle N^{1/2}}$
4. Теорема Фридлендера–Иванца , утверждающая, что существует бесконечно много простых чисел вида . ${\displaystyle a^{2}+b^{4}}$
5. Теорема Чжана (Zhang 2014), которая показывает, что существует бесконечно много пар простых чисел в пределах ограниченного расстояния . Теорема Мейнарда–Тао (Maynard 2015) обобщает теорему Чжана на произвольно длинные последовательности простых чисел.

Методы теории решета

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

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

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

Литература

• Кожокару, Алина Кармен ; Мурти, М. Рам (2006), Введение в методы решета и их применение , Лондонское математическое общество, студенческие тексты, т. 66, Cambridge University Press , ISBN 0-521-84816-4, МР  2200366
• Мотохаси, Ёити (1983), Лекции по методам решета и теории простых чисел , Лекции по математике и физике Института фундаментальных исследований Тата, т. 72, Берлин: Springer-Verlag , ISBN 3-540-12281-8, МР  0735437
• Гривз, Джордж (2001), Сита в теории чисел , Ergebnisse der Mathematik und ihrer Grenzgebiete (3), vol. 43, Берлин: Springer-Verlag , номер документа : 10.1007/978-3-662-04658-6, ISBN. 3-540-41647-1, г-н  1836967
• Harman, Glyn (2007). Решета для обнаружения простых чисел . Монографии Лондонского математического общества. Том 33. Принстон, Нью-Джерси: Princeton University Press. ISBN 978-0-691-12437-7. MR  2331072. Zbl  1220.11118.
• Halberstam, Heini ; Richert, Hans-Egon (1974). Методы решета . Монографии Лондонского математического общества. Том 4. Лондон-Нью-Йорк: Academic Press . ISBN 0-12-318250-6. МР  0424730.
• Iwaniec, Henryk ; Friedlander, John (2010), Opera de cribro , American Mathematical Society Colloquium Publications, т. 57, Providence, RI: American Mathematical Society , ISBN 978-0-8218-4970-5, г-н  2647984
• Хули, Кристофер (1976), Применение методов решета к теории чисел , Cambridge Tracts in Mathematics, т. 70, Кембридж-Нью-Йорк-Мельбурн: Cambridge University Press , ISBN 0-521-20915-3, МР  0404173
• Мейнард, Джеймс (2015). «Маленькие промежутки между простыми числами». Annals of Mathematics . 181 (1): 383–413. arXiv : 1311.4600 . doi : 10.4007/annals.2015.181.1.7. MR  3272929.
• Тененбаум, Жеральд (1995), Введение в аналитическую и вероятностную теорию чисел , Кембриджские исследования по высшей математике, т. 46, Перевод со второго французского издания (1995) К. Б. Томаса, Cambridge University Press , стр. 56–79, ISBN 0-521-41261-7, МР  1342300
• Чжан, Итан (2014). «Ограниченные промежутки между простыми числами». Annals of Mathematics . 179 (3): 1121–1174. doi : 10.4007/annals.2014.179.3.7 . MR  3171761.

Внешние ссылки

• Бредихин, Б.М. (2001) [1994], «Метод решета», Энциклопедия математики , Издательство ЭМС

Ссылки

1. Брун, Вигго (1915). «Über das Goldbachsche Gesetz und die Anzahl der Primzahlpaare». Архив по математике. Натурвиденскаб . 34 .
2. Кожокару, Алина Кармен; Мурти, М. Рам (2005). Введение в методы решета и их применение . Cambridge University Press. doi : 10.1017/CBO9780511615993. ISBN 978-0-521-84816-9.
3. (Иванец и Фридлендер, 2010)