Récemment, Gil Kalai et Dick Lipton ont tous deux écrit un bel article sur une hypothèse intéressante proposée par Peter Sarnak, expert en théorie des nombres et Hypothèse de Riemann.
Conjecture. Soit la fonction de Möbius . Supposons que soit une fonction avec entrée sous la forme d'une représentation binaire de , puis A C 0 k k Σ k ≤ n μ ( k ) ⋅ f ( k ) = o ( n ) .
Notez que si alors nous avons une forme équivalente du théorʻeme des nombres premiers .
MISE À JOUR : Ben Green de MathOverflow fournit un court article qui prétend prouver la conjecture. Regardez le papier .
D'autre part, nous savons qu'en définissant (avec une légère modification pour que la plage soit dans ), la somme résultante a l'estimation
Quelle est la classe de complexité la plus basse nous connaissons actuellement, telle qu'une fonction dans vérifie l'estimation
en particulier, étant donné que certains des théoriciens croyait que l' informatique ne sont pas dans , pouvons - nous fournir d' autres fonctions qui implique une croissance linéaire de la somme? Peut-on encore obtenir de meilleures limites?
la source
Réponses:
Des développements intéressants ont eu lieu sur ce problème, mais le remplacement de par ACC (2) (autorisant notamment les portes du mod 2) est toujours hors de portée. Certains progrès au-delà du théorème de Ben Green peuvent être trouvés dans cette question MO https://mathoverflow.net/questions/57543/walsh-fourier-transform-of-the-mobius-function ainsi que celle-ci https://mathoverflow.net / questions / 97261 / mobius-randomness-of-the-rudin-shapiro-sequence . De plus, Jean Bourgain a prouvé le caractère aléatoire de Mobius pour chaque fonction monotone (en termes de développement à deux chiffres). fUn c0 F
la source