Точное количество простых чисел в интервале

[Yadryara]

\begin{tikzpicture}[x=4.5cm, y=3.5cm, scale=1.0] % Оси координат \draw[->, thick] (-1.3, 0) -- (1.4, 0) node[right] {$x$}; \draw[->, thick] (0, -1.3) -- (0, 1.4) node[above] {$y$}; \node[below left] at (0,0) {0}; % Вертикальные границы интервала [-w, w] \draw[dashed, gray!60] (1.0, -1.1) -- (1.0, 1.1); \draw[dashed, gray!60] (-1.0, -1.1) -- (-1.0, 1.1); % Отметки границ на оси X \node[below, yshift=-2pt] at (1.0, 0) {$w$}; \node[above, yshift=2pt] at (-1.0, 0) {$-w$}; % Пунктирные проекции от правого края (w) к оси Y, чтобы показать значения \draw[dashed, gray!50] (1.0, 0.65) -- (0, 0.65); \draw[dashed, gray!50] (1.0, 1.0) -- (0, 1.0); % Подписи значений на оси Y \node[left, xshift=-2pt, blue] at (0, 1.0) {$a_3w^3$}; \node[left, xshift=-2pt, red] at (0, 0.65) {$aw$}; % Кубическая функция y = a3 * x^3 (синяя) \draw[smooth, blue, ultra thick, domain=-1.1:1.1] plot (\x, {\x*\x*\x}); \node[blue, right] at (1.05, 1.1) {$y = a_3x^3$}; % Аппроксимирующая прямая y = ax (красная) — название над прямой и левее \draw[red, ultra thick, domain=-1.2:1.2] plot (\x, {0.65*\x}); \node[red, above left] at (0.45, 0.30) {$y = ax$}; % Обозначение величины ошибок E1 и E2 стрелками % E1 на краю интервала w \draw[<->, >=stealth, purple, thick] (1.0, 0.65) -- (1.0, 1.0); \node[purple, right] at (1.0, 0.82) {$E_1$}; % E2 в точке экстремума касательной \draw[<->, >=stealth, purple, thick] (0.48, 0.324) -- (0.48, 0.118); \node[purple, right] at (0.47, 0.264) {$E_2$}; \end{tikzpicture}
Рисунок 2. Аппроксимация кубической функции линейной (лемма 5.1)


6. Вычисление $\hat{\Phi}$

Следующие леммы дают нам способ вычисления $\Re\hat{\Phi}(\rho)$.

Лемма 6.1. Для $\Re s_0 \neq 0$ и $h \in \mathbb{R}$:

$$ \hat{\varphi}(s_0 + ih) = \hat{\varphi}(s_0) \exp\left(ih(s_0\lambda^2 + \log(x))\right) \exp\left(-\frac{\lambda^2 h^2}{2}\right) \left(1 + \frac{ih}{s_0}\right)^{-1} $$

Доказательство. Начнём с

$$ \hat{\varphi}(s_0 + ih) = \frac{\exp\left(\frac{\lambda^2(s_0+ih)^2}{2}\right)}{x^{s_0+ih}(s_0 + ih)} $$

и перегруппируем, чтобы получить

$$ \frac{\exp\left(\frac{\lambda^2 s_0^2}{2}\right)}{s_0} x^{s_0} \exp\left(ih(s_0\lambda^2 + \log(x))\right) \exp\left(-\frac{\lambda^2 h^2}{2}\right) \left(1 + \frac{ih}{s_0}\right)^{-1} $$

Лемма 6.2. Пусть $N \in 2\mathbb{Z}_{>0}$, $\lambda, h > 0$ и $\lambda h < 1$. Тогда

$$ \exp\left(-\frac{\lambda^2 h^2}{2}\right) = \sum\limits_{n=0}^{N/2} \frac{(-1)^n}{n!} \left(\frac{\lambda^2 h^2}{2}\right)^n + E_A $$

где

$$ |E_A| \le \frac{1}{\left(\frac{N}{2}\right)!} \left(\frac{\lambda^2 h^2}{2}\right)^{\frac{N}{2}} $$

Доказательство. Эта функция является целой, и ограничение на $\lambda h$ делает члены чередующимися по знаку и убывающими.

Лемма 6.3. Пусть $N \in \mathbb{Z}_{>0}$, $R = \left|\frac{h}{s_0}\right|$ и $|h| < |s_0|$. Тогда

$$ \left(1 + \frac{ih}{s_0}\right)^{-1} = \sum\limits_{n=0}^{N} \left(-\frac{ih}{s_0}\right)^n + E_B $$

with

$$ |E_B| \le \frac{R^{N+1}}{1 - R} $$

Доказательство. Эта функция аналитична на открытом диске $|h| < |s_0|$, и недостающие члены образуют геометрический ряд.

Теперь мы можем зафиксировать некоторое $N \in 2\mathbb{Z}_{>0}$ и умножить эти два многочлена (степени $N$), чтобы получить один многочлен (степени $2N$) от $h$, который мы можем аналитически проинтегрировать по $\exp\left(ih(s_0\lambda^2 + \log(x))\right)$.

Теперь мы начинаем с $\hat{\Phi}\left(\frac{1}{2}\right)$ и движемся вверх по линии $\Re s = \frac{1}{2}$ малыми шагами. Мы принимаем вклад от наиболее удаленных $\rho$ равным нулю и ограничиваем ошибку, которую вносит это приближение.

[Yadryara]

7. Вычисления

Для получения временной сложности $O(x^{1/2+\varepsilon})$ алгоритма Лагариаса — Одлыжко мы должны выбрать свободный параметр $\lambda$, чтобы уравнять время выполнения суммы по нулям и элементов просеивания вычислений. Фактически, мы сместили время выполнения в сторону вычисления нулей, как для подтверждения того, что RH выполняется на высоте, достаточной для этих вычислений, так и потому, что эти данные могут быть применены в будущих исследованиях. Мы изолировали все нули $\zeta$ на высоте $30\,610\,046\,000$ (всего $103\,800\,788\,359$ нулей). Метод, используемый для определения местоположения этих нулей, описан в [15], но по сути является специфической для $\zeta$ оконной версией алгоритма Букера из [4].

Мы установили $\lambda = 6273445730170391 \times 2^{-84}$ (обратите внимание, что это число точно представимо в формате с плавающей запятой двойной точности IEEE 754). Мы использовали первые $69\,778\,732\,700$ нулей для вычисления суммы (те, что находятся до высоты $20\,950\,046\,000$), что, в свою очередь, потребовало просеивания области шириной около $6 \times 10^{15}$. В результате ошибка усечения от суммирования по нулям и от просеивания в совокупности составила $< 0.989$.

При таком выборе $\lambda$ мы получаем:

$$ \hat{\Phi}\left(\frac{1}{2}\right) < 3 \times 10^{13} $$

поэтому нам необходимо, чтобы наши нули были локализованы с абсолютной точностью не менее 25 знаков после запятой. Таким образом, мы вынуждены использовать арифметику с многозначными числами, несмотря на снижение производительности, которое это подразумевает (до 100 раз по сравнению с аппаратной арифметикой с плавающей запятой).

Как обсуждалось ранее, мы используем интервальную арифметику для управления накоплением ошибок округления во время вычислений, и с этой целью мы расширили пакеты Revol и Rouillier MPFI [16] очевидным образом для обработки комплексной арифметики. Применение интервальной арифметики влечет за собой еще одно снижение производительности (нынче примерно в 3 или 4 раза).

Просеивание (полностью с использованием целочисленной арифметики) было выполнено на $352\,800$ сегментах, каждый шириной $2^{34}$, как это было продиктовано ограничениями памяти, и дополнительно подразделено для контроля ошибки при аппроксимации $\varphi$ рядом Тейлора. Фактическое вычисление этой аппроксимации Тейлора снова требует интервальной арифметики с многозначной точностью.

Суммирование по нулям и простое решето тривиально распараллеливаются, и мы использовали кластер Bluecrystal Phase II Бристольского университета для выполнения всех вычислений, потребовав приблизительно $63\,000$ процессорных часов. В личном сообщении Tomas Oliveira e Silva указал, что вычисление $\pi(10^{23})$ с использованием комбинаторного метода занимало около месяца на одном компьютере. Предполагая, что время выполнения асимптотически приближается к $O(x^{2/3})$ и $O(x^{1/2})$ для комбинаторного и аналитического алгоритмов соответственно, точка пересечения, при которой эта реализация аналитического алгоритма начнет превосходить комбинаторный метод, будет находиться в области $x = 4 \times 10^{31}$.

Результатом вычислений, после добавления различных членов ошибки, стал интервал, охватывающий ровно одно целое число, поэтому мы имеем:

Теорема 7.1.

$$ \pi(10^{24}) = 18\,435\,599\,767\,349\,200\,867\,866. $$

Отметим, что это согласуется с условным результатом Бюте, Франке, Йоста и Кляйнюнга (Büche, Franke, Jost, Kleinjung).

¹ С этой целью Джонатан Бобер (Jonathan Bober) предоставил около первых 36 миллиардов нулей в [3].
² Наши нули расположены с абсолютной точностью $\pm 2^{-102}$, чего более чем достаточно.



Приложение А. Усечение суммы по нулям

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

Для $t > 0$, где $t$ не является мнимой частью нуля $\rho$, определим $N(t)$ как число нулей $\zeta(s)$ в критической полосе с $\Im s \in [0, t]$.

Лемма А.1. Пусть $t \ge 2$. Тогда

$$ \left| N(t) - \frac{t}{2\pi} \log\left(\frac{t}{2\pi e}\right) - \frac{7}{8} \right| < 0.137 \log(t) + 0.443 \log \log(t) + 1.588. $$

Доказательство. См. [17] Теорема 19.

Лемма А.2. Для $x > 1$, $T, \lambda > 0$ и $\sigma \in [0, 1]$ определим

$$ B(\sigma, T) := \exp \left[ \frac{\lambda^2(1 - T^2)}{2} \right] \left[ \frac{x^{\sigma}}{T \log x} + \frac{1}{\lambda^2 T^2 x} \right]. $$

Тогда

$$ |\Re \Phi(\sigma + iT)| \le B(\sigma, T). $$

Доказательство. Интегрируем вдоль контура, идущего вертикально вниз от $-1 + i\infty$ до $-1 + iT$, затем вправо до $\sigma + iT$. Для горизонтального контура имеем:

$$ \left| \int_{-1}^{\sigma} \frac{\exp\left(\frac{\lambda^2(u+iT)^2}{2}\right)}{u + iT} x^{u+iT} \, du \right| \le \frac{\exp\left(\frac{\lambda^2(1-T^2)}{2}\right)}{T} \int_{-1}^{\sigma} x^u \, du < \frac{\exp\left(\frac{\lambda^2(1-T^2)}{2}\right)}{T \log x} x^{\sigma}. $$

Для вертикального контура имеем:

$$ \left| \int_{T}^{\infty} \frac{\exp\left(\frac{\lambda^2(-1+it)^2}{2}\right)}{-1 + it} x^{-1+it} \, dt \right| \le x^{-1} \exp\left(\frac{\lambda^2}{2}\right) \int_{T}^{\infty} \frac{\exp\left(-\frac{\lambda^2 t^2}{2}\right)}{t} \, dt $$

$$ < \frac{\exp\left(\frac{\lambda^2}{2}\right)}{x T^2} \int_{T}^{\infty} t \exp\left(-\frac{\lambda^2 t^2}{2}\right) \, dt = \frac{\exp\left(\frac{\lambda^2(1-T^2)}{2}\right)}{\lambda^2 T^2 x}. $$

[Yadryara]

Лемма А.3. Пусть $T > 0$, $\sigma \in [0, 1]$ и $\alpha_T$ таковы, что $t^{\alpha_T} \ge N(t)$ для всех $t \ge T$. Тогда

$$ \sum\limits_{\Im\rho \ge T} B(\sigma, \Im\rho) \le \exp\left[\frac{\lambda^2(1 - T^2)}{2}\right] \left[ \frac{x^{\sigma}}{T \log x} + \frac{1}{\lambda^2 T^2 x} \right] \left[ \lambda^2 T^2 + 2 + \lambda^2 T^{2 - \alpha_T} - N(T) \right]. $$

Доказательство. Обращаясь к лемме А.2 и записывая

$$ k_{\sigma} := \exp\left(\frac{\lambda^2}{2}\right) \left[ \frac{x^{\sigma}}{T \log x} + \frac{1}{\lambda^2 T^2 x} \right], $$

мы можем мажорировать сумму по нулям с помощью интеграла Стилтьеса:

$$ \int_{T}^{\infty} k_{\sigma} \exp\left(-\frac{\lambda^2 t^2}{2}\right) \, dN(t). $$

Теперь мы интегрируем по частям и мажорируем $N(t)$ с помощью $t^{\alpha_T}$, чтобы получить:

$$ \sum\limits_{\Im\rho > T} B(\sigma, \Im\rho) \le -k_{\sigma} \exp\left(-\frac{\lambda^2 T^2}{2}\right) N(T) + k_{\sigma} \lambda^2 \int_{T}^{\infty} t^{\alpha_T + 1} \exp\left(-\frac{\lambda^2 t^2}{2}\right) \, dt $$

$$ \le k_{\sigma} \exp\left(-\frac{\lambda^2 T^2}{2}\right) \left[ \lambda^2 T^2 + 2 + \lambda^2 T^{2 - \alpha_T} - N(T) \right]. $$

Отметим, что упомянутое выше $\alpha_T$ можно вычислить, используя лемму А.1.

Теперь рассмотрим ошибку, вносимую усечением нашей суммы по нулям $\zeta(s)$. Пусть $T_1$ — высота, ниже которой мы находим и используем все нули, а $T_2$ — высота, до которой, как нам известно, выполняется гипотеза Римана (RH).


Лемма А.4. Пусть $E_1$ — действительная часть ошибки, вносимой игнорированием нулей с мнимой частью абсолютного значения $\in [T_1, T_2]$ (действительные части которых, как известно, равны $\frac{1}{2}$). Тогда:

$$ |E_1| \le 2 \exp\left[\frac{\lambda^2(1 - T_1^2)}{2}\right] \left[ \frac{\sqrt{x}}{T_1 \log x} + \frac{1}{\lambda^2 T_1^2 x} \right] \left[ \lambda^2 T_1^2 + 2 + \lambda^2 T_1^{2 - \alpha_{T_1}} - N(T_1) \right]. $$

Доказательство. Применим лемму A.3 с $\sigma = \frac{1}{2}$ и введем множитель $2$ для учета нулей с отрицательной мнимой частью.

Заметим, что эта оценка включает в себя вообще все нули с мнимой частью $> T_2$, однако на таких высотах их вклад будет пренебрежимо мал.


Лемма A.5. Пусть $E_2$ — действительная часть ошибки, вносимой путем исключения нулей с мнимой частью $\notin [-T_2, T_2]$ из основной суммы (которые не обязательно имеют действительную часть $= \frac{1}{2}$). Тогда:

$$ |E_2| \le \exp\left[\frac{\lambda^2(1 - T_2^2)}{2}\right] \left[ \frac{x + 1}{T_2 \log x} + \frac{2}{\lambda^2 T_2^2 x} \right] \left[ \lambda^2 T_2^2 + 2 + \lambda^2 T_2^{2 - \alpha_{T_2}} - N(T_2) \right]. $$

Доказательство. Мы сопоставляем каждое $\rho$ с $1 - \overline{\rho}$ и берем наихудший случай, когда один из нулей имеет действительную часть, очень близкую к $1$. Результат следует из леммы A.3.

__________________________________________________________________________________________

Ссылки

1. Том М. Апостол, Введение в аналитическую теорию чисел, Учебники по математике для студентов, Springer, 1976.
   
2. А. О. Л. Аткин и Д. Дж. Бернштейн, Простые решета с использованием бинарных квадратичных форм, Math. Comp. 73 (2004), № 246, 1023–1030.
   
3. Джонатан Бобер, База данных нулей дзета-функции, 2012, sage.math.washington.edu
   
4. Эндрю Р. Букер, Гипотеза Артина, метод Тьюринга и гипотеза Римана, Experiment. Math. 15 (2006), № 4, 385–407.
   
5. Дж. Бют, Дж. Франке, А. Йост и Т. Кляйнюнг, Практический аналитический метод вычисления $\pi(x)$, в печати.
   
6. Х. Дэвенпорт, Теория мультипликативных чисел, третье изд., Учебники по математике для аспирантов, № 74, Springer, 2000.
   
7. М. Делеглиз и Дж. Риват, Вычисление $\pi(x)$: метод Мейсселя, Лемера, Лагариаса, Миллера, Одлыжко, Math. Comp. 65 (1996), № 213, 235–246.
   
8. У. Ф. Галвей, Аналитическое вычисление функции подсчета простых чисел, Ph.D. диссертация, Университет Иллинойса в Урбана-Шампейн, 2004.
   
9. Дж. К. Лагариас и А. М. Одлыжко, Вычисление $\pi(x)$: аналитический метод, J. Algorithms 8 (1987), № 2, 173–191.
   
10. Дж. К. Лагариас, В. С. Миллер и А. М. Одлыжко, Вычисление $\pi(x)$: метод Мейсселя — Лемера, Math. Comp. 44 (1985), № 170, 537–560.
    
11. Д. Х. Лемер, О точном числе простых чисел меньше заданного предела, Illinois J. Math. 3 (1959), № 3, 381–388.
    
12. Д. Ф. Э. Мейсель, Ueber die Bestimmung der Primzahlenmenge innerhalb gegebener Grenzen, Math. Ann. 2 (1870), вып. 4, 636–642.
    
13. Д. Ф. Э. Мейсель, Berechnung der Menge von Primzahlen, welche innerhalb der ersten Milliarde natürlicher Zahlen vorkommen, Math. Ann. 25 (1885), вып. 2, 251–257.
    
14. Р. Э. Мур, Интервальный анализ, т. 60, Прентис-Холл Энглвуд Клиффс, Нью-Джерси, 1966.
    
15. Дэвид Дж. Платт, Вычисление $\zeta$ на критической прямой, В стадии подготовки.
    
16. Н. Револь и Ф. Руйе, Библиотека для интервальной арифметики произвольной точности, 10-й Международный симпозиум GAMM/IMACS по научным вычислениям, компьютерной арифметике и проверенным численным методам, 2002.
    
17. Б. Россер, Явные границы для некоторых функций простых чисел, Amer. J. Math. 63 (1941), № 1, 211–232.
    
18. Команда курса, Справочник по комплексному анализу, Открытый университет, 1994.

Институт математических исследований Хайльбронна, Бристольский университет
Адрес электронной почты: [e-mail]