Эффективно вычислимая функция как контрпример к гипотезе Сарнака Мёбиуса

35

Недавно Гил Калай и Дик Липтон написали хорошую статью на интересную гипотезу, предложенную Питером Сарнаком, экспертом по теории чисел и гипотезе Римана.

Гипотеза. Пусть - функция Мёбиуса . Предположим, что является функцией с входом в виде двоичного представления , тогда f : N{ - 1 , 1 }μ(К)е:N{-1,1} kkk n μ(k)f(k)=o(n).AС0КК

ΣКNμ(К)е(К)знак равноо(N),

Отметим, что если то мы имеем эквивалентную форму теоремы о простых числах .е(К)знак равно1

ОБНОВЛЕНИЕ : Бен Грин на MathOverflow предоставляет небольшую статью, в которой утверждается, чтобы доказать гипотезу. Посмотрите на бумагу .

С другой стороны, мы знаем, что, установив (с небольшой модификацией, чтобы диапазон находился в ), полученная сумма имеет оценку Существует верхняя граница, что может быть вычислена в , поэтому предложенное ограничение на в предположении не может быть смягчена до функции . Мой вопрос:е(К)знак равноμ(К)-1,1

ΣКNμ(К)2знак равноΩ(N),
μ(К)UпсоUпNпсоNпе(К)Nп

Какой класс наименьшей сложности мы знаем в настоящее время, так что функция в удовлетворяет оценке в частности, так как некоторые из теоретиков полагают , что вычислительные не находится в , мы можем обеспечить другие функции что подразумевает линейный рост суммирования? Можно ли получить еще лучшие оценки? f ( k ) C k n μ ( k ) f ( k ) = Ω ( n ) ? μ ( k ) P P f ( k )Се(К)С

ΣКNμ(К)е(К)знак равноΩ(N)?
μ(К)ппе(К)
Сянь-Чжи Чан 張顯 之
источник
3
Некоторый квантовый класс, такой как P ^ {BQNC}, также должен работать, так как факторинг лежит в этом классе.
Робин Котари
5
е(К)знак равноКяя
2
@ Эмануэле, хороший вопрос. Индикаторная функция i-го бита в двоичном представлении k является линейным «скобочным полиномом», но имеет очень высокие коэффициенты, поэтому она не может следовать из теоремы Грин-Тао о корреляции функции Мёбиуса с ограниченной нильпоследовательности Нильпоследовательности с ограниченным шагом имеют в качестве особых случаев полиномы с ограниченными степенями скобок, но их результат может иметь некоторые ограничения на величины коэффициентов
Лука Тревизан
1
еNС0
е{-1,0,1}{-1,1}

Ответы: