Recentemente, Gil Kalai e Dick Lipton escreveram um belo artigo sobre uma conjectura interessante proposta por Peter Sarnak, especialista em teoria dos números e na hipótese de Riemann.
Conjetura. Seja a função de Möbius . Suponha que seja uma função com entrada na forma de representação binária de , então f : N → { - 1 , 1 } A C 0 k k ∑ k ≤ n μ ( k ) ⋅ f ( k ) = o ( n ) .
Observe que se , temos uma forma equivalente do teorema do número primo .
ATUALIZAÇÃO : Ben Green, no MathOverflow, fornece um pequeno artigo que afirma provar a conjectura. Dê uma olhada no jornal .
Por outro lado, sabemos que, definindo (com uma pequena modificação para que o intervalo esteja em ), a soma resultante tem a estimativa Existe um limite superior que pode ser calculado em , portanto, a restrição proposta em na conjectura não pode ser relaxada para uma função . Minha pergunta é:μ(k)LP∩coLP⊆NP∩CONPF(k)NP
Qual é a classe de menor complexidade que conhecemos atualmente, de modo que uma função em satisfaz a estimativa Em particular, como alguns teóricos acreditavam que a computação não está em , podemos fornecer outras funções que implica um crescimento linear na soma? Podem ser obtidos limites ainda melhores? f ( k ) C ∑ k ≤ n μ ( k ) ⋅ f ( k ) =μ ( k ) P P f ( k )
fonte
Respostas:
fonte