Последствия вариантов гипотезы Римана в TCS

Более чем 1,5-летняя гипотеза Римана имеет глубокие следствия в математике, и большое доказательство математической теории в настоящее время доказано условно и многочисленными вариантами. Недавно я наткнулся на ссылку на условный результат в TCS, основанный на гипотезе Римана. Поэтому мне интересно,

Каковы основные последствия гипотезы Римана в TCS?

В качестве начала приведем пример из недавней статьи « Полиномы гомоморфизма», завершенные для VP Дюраном, Махаджаном, Малодом, де Руджи-Альтерром и Саурабом. Из введения статьи:

Один из наиболее важных открытых вопросов в теории алгебраической сложности - решить, различны ли классы VP и VNP. Эти классы, впервые определенные Валиантом в [13, 12], являются алгебраическими аналогами классов булевой сложности P и NP, и их разделение необходимо для отделения P от NP (по крайней мере, неравномерно и предполагая обобщенную гипотезу Римана, над полем , [3]). $\mathbb{C}$

cc.complexity-theory algebraic-complexity arithmetic-circuits ВЗН
источник

Хорошо известно, что обобщенная RH подразумевает, что мы можем дерандомизировать критерий примитивности Миллера-Рабина. Но я не знаю, есть ли что-нибудь более глубокое или более широкое, связанное с этим.

Усул

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

в двоичном виде, найти простое число больше

). Надеюсь, кто-то знающий может прокомментировать.

n

$n$

n

$n$

Усул

@usul RH подразумевает, что для всех больших

есть простое число , которое дает несколько нетривиальный детерминистический алгоритм, но очень далеко от того, что мы хотим. Более того, мы знаем, как достичь того же времени работы без RH, см. Документ проекта polymath arxiv.org/abs/1009.3956 . Я полагаю, что лучший детерминистический алгоритм для поиска простых чисел, предполагая, что RH будет значительным результатом.

n

$n$

[n, n + n^{0.5 + o (1)}]

$[n, n + n^{0.5 + o(1)}]$

Сашо Николов

Кроме того, расширение RH дает хорошую верхнюю границу наименьшего простого числа в арифметических прогрессиях (см., Например, раздел 5.5.4 в shoup.net/ntb/ntb-v2.pdf ).

Алексей Головнев

Ответы:

Во-первых, я не знаю ни о каком применении CS гипотезы Римана как таковой. Существуют различные применения обобщений RH.

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

Результат, упомянутый в ОП, основан на результате Койрана о том, что экзистенциальная теория (которая обычно идет под запутанным названием «Nullstellensatz Гильберта») находится в AM, и, следовательно, в полиномиальной иерархии. Он принимает RH для Дедекинда -функции; в частности, он опирается на эффективный вариант теоремы плотности Чеботарева. $\mathbb C$ $\zeta$

Другой класс приложений CS использует тот факт, что каждый нетривиальный квадратичный символ Дирихле по модулю принимает для некоторого , первоначально из-за Ankeny, часто утверждается со ссылкой на Баха, который улучшена константа в нотации. Он основан на RH для -функций квадратичных характеров Дирихле, который слабее, чем у Дедекинда $m$ $\chi(x)=-1$ $x=O((\log m)^2)$ $O$ $L$ $\zeta$ -функции. (Результат на самом деле имеет место в более общем случае для символов Гекке конечного порядка, и в полной общности ему требуется RH для функций упомянутых символов Гекке, что фактически эквивалентно RH для функций Дедекинда . Однако приложения CS Я знаю, что в этом нет необходимости.) В результате можно дерандомизировать несколько алгоритмов, таких как алгоритм тестирования примитивности Миллера-Рабина или алгоритм Шенкса-Тонелли для вычисления квадратных корней по модулю простых чисел. $L$ $\zeta$

Насколько я знаю, RH является не полезно детерминировано найти простые числа в заданном интервале, как упомянуто в комментарии выше. Это следовало бы из гипотезы Крамера или аналогичной оценки простых промежутков, но RH слишком слаба, чтобы доказать такие оценки (ошибочный член в теореме о простых числах, по крайней мере, порядка примерно ни на что). $\sqrt x$

Эмиль Йержабек
источник

L

$L$

ζ

$\zeta$

@ Франсуа: Я также лично привык к этой терминологии. Но, например, довольно известная книга Баха и Шаллита определяет ее совершенно противоположным образом (что, кстати, противоречит использованию самого Баха в его статье «Явные границы ...»).

Эмиль Йержабек

Разве FACTORING в PPA не является интересным следствием? arxiv.org/abs/1207.5220

domotorp

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

Эмиль Йержабек

Предполагая расширенную гипотезу Римана, Л. М. Адлеман и Х. В. Ленстра дали алгоритм полиномиального времени, чтобы найти неприводимый полином требуемой степени над конечным полем: http://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1986a/art .pdf

Лин Бинкай
источник