Теория сита
![]() | Эта статья включает список литературы , связанную литературу или внешние ссылки , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . ( Июль 2009 г. ) |
Теория сита — это набор общих методов теории чисел , предназначенных для подсчета или, что более реалистично, для оценки размера просеянных наборов целых чисел. Прототипическим примером просеянного набора является набор простых чисел до некоторого заданного X. предела Соответственно, прототипным примером решета является решето Эратосфена , или более общее решето Лежандра . Прямая атака на простые числа с использованием этих методов вскоре достигает, казалось бы, непреодолимых препятствий на пути накопления ошибочных членов. [ нужна ссылка ] В одном из основных направлений теории чисел двадцатого века были найдены способы избежать некоторых трудностей лобовой атаки с наивным представлением о том, каким должно быть просеивание. [ нужна ссылка ]
Одним из успешных подходов является аппроксимация определенного просеянного набора чисел (например, набора простых чисел) другим, более простым набором (например, набором почти простых чисел), который обычно несколько больше исходного набора и его легче анализировать. Более сложные сита также не работают напрямую с множествами как таковыми , а вместо этого подсчитывают их в соответствии с тщательно выбранными весовыми функциями на этих множествах (варианты придания некоторым элементам этих множеств большего «веса», чем другим). Кроме того, в некоторых современных приложениях сита используются не для оценки размера просеянного материала.множества, а для создания функции, которая является большой на множестве и большей частью малой вне его, и при этом ее легче анализировать, чем характеристическую функцию множества.
Термин «сито» впервые использовал норвежский математик Вигго Брун в 1915 году. [1] Однако работа Брюна была вдохновлена работами французского математика Жана Мерлена, погибшего в Первой мировой войне , и сохранились только две его рукописи. [2]
Основная теория сита
Информацию об обозначениях см. в конце.
Начнем с некоторой счетной последовательности неотрицательных чисел. . В самом простом случае эта последовательность представляет собой просто индикаторную функцию. из какого-то набора мы хотим просеять. Однако эта абстракция допускает более общие ситуации. Далее мы вводим общий набор простых чисел, называемый диапазоном отсеивания. и их продукция до как функция .
Цель теории сита - оценить функцию просеивания
В случае это просто подсчитывает мощность подмножества чисел, взаимно простых с простыми делителями .
Принцип включения-исключения [ править ]
Для определять
и для каждого простого числа обозначим множество и пусть быть мощность. Пусть сейчас быть некоторым набором простых чисел.
Если кто-то хочет вычислить мощность , можно применить принцип включения-исключения . Этот алгоритм работает следующим образом: сначала из мощности удаляется мощность и . Теперь, когда мы удалили числа, которые делятся на и дважды, нужно добавить мощность . На следующем этапе удаляется и добавляет и снова. Кроме того, теперь нужно удалить , то есть мощность всех чисел, делящихся на и . Это приводит к принципу включения-исключения.
Личность Лежандра [ править ]
Мы можем переписать функцию просеивания, используя тождество Лежандра.
с помощью функции Мёбиуса и некоторых функций индуцированные элементами
Пример [ править ]
Позволять и . Функция Мёбиуса отрицательна для любого простого числа, поэтому мы получаем
Аппроксимация суммы сравнения [ править ]
Тогда предполагается, что можно записать как
где — плотность , то есть мультипликативная функция такая, что
и является приближением и это некоторый остаточный член. Функция просеивания становится
или короче
Затем пытаются оценить функцию отсеивания, находя верхнюю и нижнюю границы для соответственно и .
Частичная сумма функции просеивания поочередно завышает и занижает, поэтому остаточный член будет огромным. Идея Брюна улучшить это состояла в том, чтобы заменить в функции просеивания с последовательностью весов состоящее из ограниченных функций Мёбиуса. Выбор двух подходящих последовательностей и и обозначив просеивающие функции через и , можно получить нижнюю и верхнюю границы исходных функций отсеивания
С мультипликативен, можно работать и с тождеством
Обозначения: предостережение относительно обозначений: в литературе часто обозначают набор последовательностей. с набором сам. Это значит, что человек пишет определить последовательность . Также в литературе сумма иногда обозначается как мощность из какого-то набора , хотя мы определили быть уже мощностью этого множества. Мы использовали для обозначения множества простых чисел и для наибольшего общего делителя и .
Виды просеивания [ править ]
Современные сита включают сито Бруна , сито Сельберга , сито Турана , большое сито , большее сито и сито Гольдстона-Пинца-Йылдырыма . Одной из первоначальных целей теории решета была попытка доказать гипотезы теории чисел, такие как гипотеза о простых числах-близнецах . Хотя первоначальные широкие цели теории решета все еще по большей части не достигнуты, были достигнуты некоторые частичные успехи, особенно в сочетании с другими инструментами теории чисел. Основные моменты включают в себя:
- Теорема Брюна , показывающая, что сумма обратных чисел простых чисел-близнецов сходится (тогда как сумма обратных чисел всех простых чисел расходится);
- Теорема Чена , показывающая, что существует бесконечно много простых чисел p таких, что p + 2 является либо простым, либо полупростым числом (произведением двух простых чисел); тесно связанная теорема Чэнь Цзинжуня утверждает, что каждое достаточно большое четное число является суммой простого и другого числа, которое является либо простым, либо полупростым. Их можно рассматривать как близкие к гипотезе о простых числах-близнецах и гипотезе Гольдбаха соответственно.
- Фундаментальная лемма теории решета , утверждающая, что если просеять набор из N чисел, то можно точно оценить количество элементов, оставшихся в сите после итераций при условии, что достаточно мала (здесь вполне типичны дроби типа 1/10). Эта лемма обычно слишком слаба, чтобы отсеивать простые числа (что обычно требует чего-то вроде итераций), но этого может быть достаточно для получения результатов, касающихся почти простых чисел.
- Теорема Фридлендера-Иванца , утверждающая, что существует бесконечно много простых чисел вида .
- Чжана Теорема ( Чжан 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), Сита в теории чисел , Результаты математики и ее границы (3), том. 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
Ссылки [ править ]
- ^ Брун, Вигго (1915). «О законе Гольдбаха и числе пар простых чисел». Архив для математики . 34 .
- ^ Кожокару, Алина Кармен; Мурти, М. Рам (2005). Введение в ситовые методы и их применение . Издательство Кембриджского университета. дои : 10.1017/CBO9780511615993 .
- ^ ( Иванец и Фридлендер 2010 )