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

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

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

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

Проблема четности . Если A - это множество, все элементы которого являются произведениями нечетного числа простых чисел (или все являются произведениями четного числа простых чисел), то (без введения дополнительных ингредиентов) теория решет не может предоставить нетривиальные нижние оценки для размер 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 ² + b ⁴ .

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

Феномен Карацубы [ править ]

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

Позвольте быть набор натуральных чисел (положительных целых чисел), то есть чисел . Множество простых чисел, то есть такие целые числа , , которые имеют только два различных делителей (а именно, а ), обозначается , . Каждое натуральное число ,, может быть представлено как произведение простых чисел (не обязательно различных), то есть где , и такое представление уникально с точностью до порядка множителей.${\ Displaystyle \ mathbb {N}}$${\ Displaystyle 1,2,3, \ точки}$${\ Displaystyle п \ в \ mathbb {N}}$${\ displaystyle n> 1}$${\ displaystyle n}$${\ displaystyle 1}$${\ Displaystyle \ mathbb {P}}$${\ Displaystyle \ mathbb {P} = \ {2,3,5,7,11, \ точки \} \ подмножество \ mathbb {N}}$${\ Displaystyle п \ в \ mathbb {N}}$${\ displaystyle n> 1}$${\ displaystyle n = p_ {1} p_ {2} \ dots p_ {k},}$${\ displaystyle p_ {1} \ in \ mathbb {P}, \ p_ {2} \ in \ mathbb {P}, \ \ dots, \ p_ {k} \ in \ mathbb {P}}$

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

Если, однако, мы ограничиваем наши два набора для тех натуральных чисел, каноническое представление не содержит простых чисел в арифметической прогрессии , например , или прогрессия , , , , то из этих положительных целых чисел, с четным числом простых факторов , как правило, быть меньше, чем с нечетным числом простых множителей. Карацуба обнаружил это свойство. Он также нашел формулу для этого явления, формулу для различия мощностей.${\ displaystyle 6m + 1}$${\ Displaystyle м = 1,2, \ точки}$${\ displaystyle км + l}$${\ Displaystyle 1 \ Leq L <к}$${\ Displaystyle (л, к) = 1}$${\ Displaystyle м = 0,1,2, \ точки}$наборов натуральных чисел с нечетным и четным количеством простых множителей, когда эти множители подчиняются определенным ограничениям. Во всех случаях, поскольку задействованные множества бесконечны, под «большим» и «меньшим» мы подразумеваем предел отношения множеств, поскольку верхняя граница простых чисел стремится к бесконечности. В случае простых чисел, содержащих арифметическую прогрессию, Карацуба доказал, что этот предел бесконечен.

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

Позвольте и быть подмножества , такие, что , если содержит четное количество простых факторов, и , если содержит нечетное количество простых факторов. Интуитивно понятно, что размеры двух наборов и примерно одинаковы. Точнее, для всех мы определяем и , где мощность множества всех чисел из таких, что , и мощность множества всех чисел из таких, что . Асимптотика и была выведена Э. Ландау : ^[8]${\ displaystyle \ mathbb {N} _ {0}}$${\ Displaystyle \ mathbb {N} _ {1}}$${\ Displaystyle \ mathbb {N}}$${\ Displaystyle п \ в \ mathbb {N} _ {0}}$${\ displaystyle n}$${\displaystyle n\in \mathbb {N} _{1}}$${\displaystyle n}$${\displaystyle \mathbb {N} _{0}}$${\displaystyle \mathbb {N} _{1}}$${\displaystyle x\geq 1}$${\displaystyle n_{0}(x)}$${\displaystyle n_{1}(x)}$${\displaystyle n_{0}(x)}$${\displaystyle n}$${\displaystyle \mathbb {N} _{0}}$${\displaystyle n\leq x}$${\displaystyle n_{1}(x)}$${\displaystyle n}$${\displaystyle \mathbb {N} _{1}}$${\displaystyle n\leq x}$${\displaystyle n_{0}(x)}$${\displaystyle n_{1}(x)}$

${\displaystyle n_{0}(x)={\frac {1}{2}}x+O\left(xe^{-c{\sqrt {\ln x}}}\right),n_{1}(x)={\frac {1}{2}}x+O\left(xe^{-c{\sqrt {\ln x}}}\right);c>0.}$

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

${\displaystyle n_{0}(x)\sim n_{1}(x)\sim {\frac {1}{2}}x,}$

что и асимптотически равны.${\displaystyle n_{0}(x)}$${\displaystyle n_{1}(x)}$

Способствовать,

${\displaystyle n_{1}(x)-n_{0}(x)=O\left(xe^{-c{\sqrt {\ln x}}}\right),}$

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

С другой стороны, если мы позволим быть натуральным числом и быть последовательностью натуральных чисел,, такие, что ; ; все разные по модулю ; Позвольте быть набор простых чисел, принадлежащих прогрессиям ; . ( это множество всех простых чисел, не делящихся ).${\displaystyle k\geq 2}$${\displaystyle l_{1},l_{2},\dots l_{r}}$${\displaystyle 1\leq r<\varphi (k)}$${\displaystyle 1\leq l_{j}<k}$${\displaystyle (l_{j},k)=1}$${\displaystyle l_{j}}$${\displaystyle k}$${\displaystyle j=1,2,\dots r.}$${\displaystyle \mathbb {A} }$${\displaystyle kn+l_{j}}$${\displaystyle j\leq r}$${\displaystyle \mathbb {A} }$${\displaystyle k}$

Мы обозначаем как набор натуральных чисел, которые не содержат простых множителей из , и как подмножество чисел из с четным числом простых множителей, как подмножество чисел из с нечетным числом простых множителей. Определим функции${\displaystyle \mathbb {N} ^{*}}$${\displaystyle \mathbb {A} }$${\displaystyle \mathbb {N} _{0}^{*}}$${\displaystyle \mathbb {N} ^{*}}$${\displaystyle \mathbb {N} _{1}^{*}}$${\displaystyle \mathbb {N} ^{*}}$

${\displaystyle n^{*}(x)=\displaystyle \sum _{\begin{array}{c}n\leq x\\n\in \mathbb {N} ^{*}\end{array}}1;n_{0}^{*}(x)=\displaystyle \sum _{\begin{array}{c}n\leq x\\n\in \mathbb {N} _{0}^{*}\end{array}}1;n_{1}^{*}(x)=\displaystyle \sum _{\begin{array}{c}n\leq x\\n\in \mathbb {N} _{1}^{*}\end{array}}1.}$

Карацуба доказал, что,

для асимптотической формулы${\displaystyle x\to +\infty }$

${\displaystyle n_{1}^{*}(x)-n_{0}^{*}(x)\sim Cn^{*}(x)(\ln x)^{2\left({\frac {r}{\varphi (k)}}-1\right)},}$действительно, где - положительная постоянная.${\displaystyle C}$

Он также показал, что аналогичные теоремы можно доказать для других наборов натуральных чисел, например, для чисел, которые можно представить в виде суммы двух квадратов, и для наборов натуральных чисел, все множители которых принадлежат to , будет отображать аналогичное асимптотическое поведение.${\displaystyle \mathbb {A} }$

Теорема Карацубы была обобщена на случай, когда - некоторый неограниченный набор простых чисел.${\displaystyle \mathbf {A} }$

Феномен Карацубы иллюстрируется следующим примером. Мы считаем , натуральные числа которых каноническое представление не включает в себя простые числа , принадлежащие к прогрессированию , . Тогда это явление выражается формулой: ${\displaystyle 6m+1}$${\displaystyle m=1,2,\dots }$${\displaystyle n_{1}^{*}(x)-n_{0}^{*}(x)\sim {\frac {\pi }{8{\sqrt {3}}}}{\frac {n^{*}(x)}{\ln x}},x\to +\infty .}$

Заметки [ править ]