Função eficientemente computável como um contra-exemplo da conjectura Mobius de Sarnak

35

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 ) .μ(k)f:N{1,1}AC0kk

knμ(k)f(k)=o(n).

Observe que se , temos uma forma equivalente do teorema do número primo .f(k)=1

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 é:f(k)=μ(k)1,1μ(k)LPcoLPNPCONPF(k)NP

knμ(k)2=Ω(n).
μ(k)UPcoUPNPcoNPf(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 ) =Cf(k)Cμ ( k ) P P f ( k )

knμ(k)f(k)=Ω(n)?
μ(k)PPf(k)
Hsien-Chih Chang 張顯 之
fonte
3
Alguma classe quântica como P ^ {BQNC} também deve funcionar, uma vez que o fatoramento está nessa classe.
Robin Kothari
5
f(k)=kii
2
@ Emanuele, boa pergunta. A função indicadora do i-ésimo bit na representação binária de k é um "polinômio de colchete" linear, mas possui coeficientes muito altos, portanto, pode não seguir o teorema de Green-Tao sobre a correlação da função Mobius com a função limitada. n-sequências passo a passo. Nilsequences limitada passos têm limitado grau polinômios suporte como casos especiais, mas seu resultado pode ter algumas restrições sobre as magnitudes dos coeficientes
Luca Trevisan
11
fNC0
f{1,0,1}{1,1}

Respostas:

4

AC0f

Gil Kalai
fonte