Недавно Гил Калай и Дик Липтон написали хорошую статью на интересную гипотезу, предложенную Питером Сарнаком, экспертом по теории чисел и гипотезе Римана.
Гипотеза. Пусть - функция Мёбиуса . Предположим, что является функцией с входом в виде двоичного представления , тогда f : N → { - 1 , 1 } kk ∑ k ≤ n μ(k)⋅f(k)=o(n).
Отметим, что если то мы имеем эквивалентную форму теоремы о простых числах .
ОБНОВЛЕНИЕ : Бен Грин на MathOverflow предоставляет небольшую статью, в которой утверждается, чтобы доказать гипотезу. Посмотрите на бумагу .
С другой стороны, мы знаем, что, установив (с небольшой модификацией, чтобы диапазон находился в ), полученная сумма имеет оценку Существует верхняя граница, что может быть вычислена в , поэтому предложенное ограничение на в предположении не может быть смягчена до функции . Мой вопрос:
Какой класс наименьшей сложности мы знаем в настоящее время, так что функция в удовлетворяет оценке в частности, так как некоторые из теоретиков полагают , что вычислительные не находится в , мы можем обеспечить другие функции что подразумевает линейный рост суммирования? Можно ли получить еще лучшие оценки? f ( k ) C ∑ k ≤ n μ ( k ) ⋅ f ( k ) = Ω ( n ) ? μ ( k ) P P f ( k )
источник
Ответы:
источник