Recientemente, Gil Kalai y Dick Lipton escribieron un buen artículo sobre una conjetura interesante propuesta por Peter Sarnak, un experto en teoría de números e hipótesis de Riemann.
Conjetura. Sea la función de Möbius . Suponga que es una función con la entrada en forma de representación binaria de , luego f : N → { - 1 , 1 } A C 0 k k ∑ k ≤ n μ ( k ) ⋅ f ( k ) = o ( n ) .
Tenga en cuenta que si entonces tenemos una forma equivalente del teorema del número primo .
ACTUALIZACIÓN : Ben Green en MathOverflow proporciona un breve documento que pretende probar la conjetura. Echa un vistazo al papel .
Por otro lado, sabemos que al establecer (con una ligera modificación para que el rango esté en ), la suma resultante tiene la estimación Hay un límite superior que se puede calcular en , por lo que la restricción propuesta en en la conjetura no se puede relajar a una función . Mi pregunta es:μ(k)UP∩coUP⊆NP∩coNPf(k)NP
¿Cuál es la clase de complejidad más baja que conocemos actualmente, de modo que una función en satisfaga la estimación En particular, dado que algunos de los teóricos creían que calcular μ ( k ) no está en P , ¿podemos proporcionar otras funciones P f ( k ), lo que implica un crecimiento lineal en la sumatoria? ? ¿Se pueden obtener límites aún mejores? f ( k ) C ∑ k ≤ n μ ( k ) ⋅ f ( k ) = Ω ( n ) ?
fuente
Respuestas:
fuente