Теория сита

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

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

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

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

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

Начнем с некоторой счетной последовательности неотрицательных чисел . В самом простом случае эта последовательность является просто индикаторной функцией некоторого множества, которое мы хотим просеять. Однако эта абстракция допускает более общие ситуации. Далее мы вводим общий набор простых чисел, называемый диапазоном отсеивания , и их произведение с точностью до функции . ${\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 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^{+}.}$^[1]

Поскольку мультипликативно, можно работать и с тождеством ${\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. Теорема Чжана (Чжан 2014), показывающая, что на ограниченном расстоянии существует бесконечно много пар простых чисел . Теорема Мейнарда – Тао (Maynard 2015) обобщает теорему Чжана на последовательности простых чисел произвольной длины.

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

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

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

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

Литература

• Кожокару, Алина Кармен ; Мурти, М. Рам (2006), Введение в ситовые методы и их приложения , Тексты для студентов Лондонского математического общества, том. 66, Издательство Кембриджского университета , 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
• Харман, Глин (2007). Первичные сита . Монографии Лондонского математического общества. Том. 33. Принстон, Нью-Джерси: Издательство Принстонского университета. ISBN 978-0-691-12437-7. МР  2331072. Збл  1220.11118.
• Хальберштам, Хейни ; Рихерт, Ханс-Эгон (1974). Ситовые методы . Монографии Лондонского математического общества. Том. 4. Лондон-Нью-Йорк: Академик Пресс . ISBN 0-12-318250-6. МР  0424730.
• Иванец, Хенрик ; Фридлендер, Джон (2010), Opera de cribro , Публикации коллоквиума Американского математического общества, том. 57, Провиденс, Род-Айленд: Американское математическое общество , ISBN. 978-0-8218-4970-5, МР  2647984
• Хули, Кристофер (1976), Приложения ситовых методов к теории чисел , Cambridge Tracts in Mathematics, vol. 70, Кембридж-Нью-Йорк-Мельбурн: Издательство Кембриджского университета , ISBN 0-521-20915-3, МР  0404173
• Мейнард, Джеймс (2015). «Малые промежутки между простыми числами». Анналы математики . 181 (1): 383–413. arXiv : 1311.4600 . дои : 10.4007/анналы.2015.181.1.7. МР  3272929.
• Тененбаум, Джеральд (1995), Введение в аналитическую и вероятностную теорию чисел , Кембриджские исследования по высшей математике, том. 46, Перевод второго французского издания (1995 г.) CB Thomas, Cambridge University Press , стр. 56–79, ISBN. 0-521-41261-7, МР  1342300
• Чжан, Итан (2014). «Ограниченные промежутки между простыми числами». Анналы математики . 179 (3): 1121–1174. дои : 10.4007/анналы.2014.179.3.7 . МР  3171761.

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

• Бредихин, Б.М. (2001) [1994], «Метод сита», Энциклопедия Математики , EMS Press

Рекомендации

1. (Иванец и Фридлендер, 2010)