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

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

Заявление

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

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

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

Пример

Этот пример принадлежит Сельбергу и приведен в качестве упражнения с подсказками Кожокару и Мурти.

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

Сита,

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

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

Карацубы

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

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

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

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

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

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

$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.$

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

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

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

Дальше,

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

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

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

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

$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.$

Карацуба доказал, что $x\to +\infty$, асимптотическая формула

$n_{1}^{*}(x)-n_{0}^{*}(x)\sim Cn^{*}(x)(\ln x)^{2\left({\frac {r}{\varphi (k)}}-1\right)},$

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

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

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

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

$n_{1}^{*}(x)-n_{0}^{*}(x)\sim {\frac {\pi }{8{\sqrt {3}}}}{\frac {n^{*}(x)}{\ln x}},\qquad x\to +\infty .$