Введение

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

Теория просеивания — это набор общих методов в теории чисел, предназначенных для подсчёта или, более реалистично, для оценки размера отсеянных множеств целых чисел. Прототипическим примером отсеянного множества является множество простых чисел до некоторого заданного предела X. Соответственно, прототипическим примером сита является сито Эратосфена или более общее сито Лежандра. Прямая атака на простые числа с использованием этих методов вскоре наталкивается на, казалось бы, непреодолимые препятствия из-за накопления членов погрешности. В одном из основных направлений теории чисел в двадцатом веке были найдены способы избежать некоторых трудностей прямого подхода, основанного на наивном представлении о том, каким должно быть просеивание. Один из успешных подходов заключается в приближении конкретного отсеянного множества чисел (например, множества простых чисел) другим, более простым множеством (например, множеством почти простых чисел), которое обычно несколько больше исходного множества и легче поддаётся анализу. Более сложные сита также не работают непосредственно с самими множествами, а вместо этого подсчитывают их элементы, используя тщательно подобранные весовые функции, позволяющие придавать некоторым элементам этих множеств больший «вес», чем другим. Кроме того, в некоторых современных приложениях сита используются не для оценки размера отсеянного множества, а для построения функции, которая велика на этом множестве и в основном мала вне его, при этом её проще анализировать, чем характеристическую функцию множества. Термин «сито» впервые был использован норвежским математиком Вигго Бруном в 1915 году. Однако работа Бруна была вдохновлена трудами французского математика Жана Мерлена, который погиб в Первой мировой войне, и сохранилось всего две его рукописи.

Пример

Пусть и функция Мёбиуса отрицательна для каждого простого числа, поэтому мы получаем

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

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