Теория сита - Sieve theory

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

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

Виды рассева

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

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

Приемы теории сита

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

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

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

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

внешняя ссылка