Skutecznie obliczalna funkcja jako przeciw-przykład do przypuszczenia Mobiusa Sarnaka

35

Ostatnio Gil Kalai i Dick Lipton napisali fajny artykuł na temat ciekawej hipotezy zaproponowanej przez Petera Sarnaka, eksperta w dziedzinie teorii liczb i hipotezy Riemanna.

Przypuszczenie. Niech będzie funkcją Möbiusa . Załóżmy, że f : N{ - 1 , 1 } jest funkcją A C 0 z wejściem k w postaci binarnej reprezentacji k , a następnie k n μ ( k ) f ( k ) = o ( n ) .μ(k)f:N{1,1}AC0kk

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

Zauważ, że jeśli to mamy równoważną postać twierdzenia na temat liczby pierwszej .f(k)=1

AKTUALIZACJA : Ben Green w MathOverflow zapewnia krótki artykuł, który ma udowodnić przypuszczenie. Spójrz na papier .

Z drugiej strony wiemy, że ustawiając (z niewielką modyfikacją, aby zakres był w zakresief(k)=μ(k)1,1), otrzymana suma ma oszacowanie Nie ma górnej granicy że μ ( k ) może być obliczona w U PC O U PN PC O N P , więc ograniczeniem zaproponowała F ( k ), w hipotezie, nie mogą być złagodzone do N P funkcji . Moje pytanie brzmi:

knμ(k)2=Ω(n).
μ(k)UPcoUPNPcoNPf(k)NP

Jaka jest obecnie najniższa znana nam klasa złożoności , tak że funkcja f ( k ) w C spełnia oszacowanie k n μ ( k ) f ( k ) = Ω ( n ) ? W szczególności, ponieważ niektórzy teoretycy uważali, że obliczania μ ( k ) nie ma w P , czy możemy zapewnić inne funkcje P f ( k )Cf(k)C

knμ(k)f(k)=Ω(n)?
μ(k)PPf(k)co oznacza liniowy wzrost sumy? Czy można uzyskać jeszcze lepsze granice?
Hsien-Chih Chang 張顯 之
źródło
3
Niektóre klasy kwantowe, takie jak P ^ {BQNC}, również powinny działać, ponieważ faktoring leży w tej klasie.
Robin Kothari,
5
f(k)=kii
2
@Emanuele, dobre pytanie. Funkcja wskaźnika i-tego bitu w binarnej reprezentacji k jest liniowym „wielomianem nawiasowym”, ale ma bardzo wysokie współczynniki, więc może nie wynikać z twierdzenia Greena-Tao o korelacji funkcji Mobiusa z ograniczeniem -step nie ma konsekwencji. Brak ciągów ograniczonych wielomianów w ograniczonych stopniach jako przypadki szczególne, ale ich wynik może mieć pewne ograniczenia co do wielkości współczynników
Luca Trevisan
1
fNC0
f{1,0,1}{1,1}

Odpowiedzi: