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

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 ) $\mu(k)$$f: \mathbb{N} \to \{-1,1\}$$\mathsf{AC}^0$$k$$k$

$$\sum_{k \leq n} \mu(k) \cdot f(k) = o(n) \text.$$

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 zakresie$f(k) = \mu(k)$$\\{-1,1\\}$), otrzymana suma ma oszacowanie Nie ma górnej granicy że μ ( k ) może być obliczona w U P ∩ C O U P ⊆ N P ∩ C O N P , więc ograniczeniem zaproponowała F ( k ), w hipotezie, nie mogą być złagodzone do N P funkcji . Moje pytanie brzmi:

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 $\mathsf{C}$$f(k)$$\mathsf{C}$

$$\sum_{k \leq n} \mu(k) \cdot f(k) = \Omega(n) \text{?}$$ $\mu(k)$$\mathsf{P}$$\mathsf{P}$$f(k)$co oznacza liniowy wzrost sumy? Czy można uzyskać jeszcze lepsze granice?

$AC^0$$f$