Jump to content

Проблема четности (теория решета)

В теории чисел относится проблема четности к ограничению теории сит , которое не позволяет ситам давать хорошие оценки во многих видах задач подсчета простых чисел. Проблема была выявлена ​​и названа Атле Сельбергом в 1949 году. Примерно с 1996 года Джон Фридлендер и Хенрик Иванец разработали несколько сит, чувствительных к четности, которые делают проблему четности менее препятствием.

Заявление [ править ]

Теренс Тао дал такую ​​«грубую» формулировку проблемы: [1]

Проблема паритета . Если A — множество, все элементы которого являются произведениями нечетного числа простых чисел (или все произведения четного числа простых чисел), то (без введения дополнительных ингредиентов) теория решета не может предоставить нетривиальные нижние оценки для размер А. ​Кроме того, любые верхние границы должны отличаться от истины в 2 или более раз.

Эта проблема важна, поскольку она может объяснить, почему ситам трудно «обнаружить простые числа», другими словами, дать нетривиальную нижнюю оценку числа простых чисел с некоторым свойством. Например, в некотором смысле теорема Чена очень близка к решению гипотезы о простых числах-близнецах , поскольку она говорит, что существует бесконечно много простых чисел p таких, что p + 2 является либо простым, либо произведением двух простых чисел. Проблема четности предполагает, что, поскольку интересующий случай имеет нечетное количество простых делителей (а именно 1), невозможно разделить два случая с помощью сита.

Пример [ править ]

Этот пример принадлежит Сельбергу и приведен в качестве упражнения с подсказками Кожокару и Мурти. [2] : 133–134 

Задача состоит в том, чтобы оценить отдельно количество чисел ≤ x , у которых нет простых делителей ≤ x. 1/2 , которые имеют четное (или нечетное) количество простых делителей . Можно показать, что независимо от выбора весов в сите типа Брюна или Сельберга полученная верхняя оценка будет не менее (2 + o (1)) x / ln x для обеих задач. Но на самом деле набор с четным числом факторов пуст и поэтому имеет размер 0. Набор с нечетным количеством факторов — это просто простые числа между x 1/2 и x, поэтому по теореме о простых числах его размер равен (1 + o (1)) x / ln x . Таким образом, эти ситовые методы не могут дать полезную верхнюю границу для первого набора и переоценивают верхнюю границу второго набора в 2 раза.

Сита, четности к чувствительные

Примерно начиная с 1996 года Джон Фридлендер и Хенрик Иванец разработали несколько новых методов сита, позволяющих «решить» проблему четности. [3] [4] Одним из триумфов этих новых методов является теорема Фридлендера-Иванца , которая утверждает, что существует бесконечно много простых чисел вида a. 2 + б 4 .

Глин Харман связывает проблему четности с различием между информацией типа I и типа II в сите. [5]

Карацубы Феномен

В 2007 году Анатолий Алексеевич Карацуба обнаружил дисбаланс между числами в арифметической прогрессии при заданных соотношениях числа простых множителей. Его документы [6] [7] были опубликованы после его смерти.

Позволять быть набором натуральных чисел (положительных целых чисел), то есть чисел . Множество простых чисел, то есть таких целых чисел , , которые имеют всего два различных делителя (а именно, и ), обозначается , . Каждое натуральное число , , можно представить в виде произведения простых чисел (не обязательно различных), то есть где ,и такое представление уникально с точностью до порядка факторов.

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

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

Мы переформулируем феномен Карацубы, используя математическую терминологию.

Позволять и быть подмножествами , такой, что , если содержит четное число простых делителей, и , если содержит нечетное число простых делителей. Интуитивно понятно, что размеры двух наборов и примерно одинаковы. Точнее, для всех , мы определяем и , где - мощность множества всех чисел от такой, что , и - мощность множества всех чисел от такой, что . Асимптотическое поведение и был выведен Э. Ландау : [8]

Это показывает, что

то есть и асимптотически равны.

Дальше,

так что разница между мощностями двух множеств невелика.

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

Обозначим как набор натуральных чисел, не содержащий простых множителей из , и как подмножество чисел из с четным числом простых делителей, так как подмножество чисел из с нечетным числом простых делителей.Определим функции

Карацуба доказал, что , асимптотическая формула

допустимо, где является положительной константой.

Он также показал, что аналогичные теоремы можно доказать и для других наборов натуральных чисел, например, для чисел, представимых в виде суммы двух квадратов, и что множества натуральных чисел, все делители которых принадлежат к , будет демонстрировать аналогичное асимптотическое поведение.

Теорема Карацубы была обобщена на случай, когда — некоторое неограниченное множество простых чисел.

Феномен Карацубы иллюстрируется следующим примером. Мы рассматриваем натуральные числа, в каноническое представление которых не входят простые числа, принадлежащие прогрессии , . Тогда это явление выражается формулой:

Примечания [ править ]

  1. ^ Тао, Теренс (5 июня 2007 г.). «Открытый вопрос: проблема четности в теории решета» . Проверено 11 августа 2008 г.
  2. ^ Кожокару, Алина Кармен ; М. Рам Мурти (2005). Введение в ситовые методы и их применение . Тексты студентов Лондонского математического общества. Том. 66. Издательство Кембриджского университета. ISBN  0-521-61275-6 .
  3. ^ Фридлендер, Джон ; Хенрик Иванец (18 февраля 1997 г.). «Использование сита, чувствительного к четности, для подсчета простых значений многочлена» . Труды Национальной академии наук . 94 (4): 1054–1058. Бибкод : 1997PNAS...94.1054F . дои : 10.1073/pnas.94.4.1054 . ЧВК   19742 . ПМИД   11038598 . 1054–1058.
  4. ^ Фридлендер, Джон ; Генрик Иванец (1998). «Асимптотическое решето для простых чисел». Анналы математики . 148 (3): 1041–1065. arXiv : math/9811186 . Бибкод : 1998math.....11186F . дои : 10.2307/121035 . JSTOR   121035 . S2CID   11574656 .
  5. ^ Харман, Глин (2007). Первичные сита . Монографии Лондонского математического общества. Том. 33. Издательство Принстонского университета. стр. 45, 335. ISBN.  978-0-691-12437-7 . Збл   1220.11118 .
  6. ^ Карацуба, А.А. (2011). «Свойство множества простых чисел». Российские математические обзоры . 66 (2): 209–220. Бибкод : 2011РуМаС..66..209К . дои : 10.1070/RM2011v066n02ABEH004739 .
  7. ^ Карацуба, А.А. (2011). «Свойство множества простых чисел как мультипликативный базис натуральных чисел». Доклады математики (84:1): 1–4.
  8. ^ Ландау, Э. (1912). «О количестве узлов сетки на отдельных участках». Бог. Новости. : 687–771.
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: abde4387a12fb22bf29b1c5c9c914908__1641317340
URL1:https://arc.ask3.ru/arc/aa/ab/08/abde4387a12fb22bf29b1c5c9c914908.html
Заголовок, (Title) документа по адресу, URL1:
Parity problem (sieve theory) - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)