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 jest funkcją z wejściem w postaci binarnej reprezentacji , a następnie $\mu(k)$ $f: \mathbb{N} \to \{-1,1\}$ $\mathsf{AC}^0$ $k$ $k$
$\sum_{k \leq n} μ (k) \cdot f (k) = o (n) .$ $\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 może być obliczona w , więc ograniczeniem zaproponowała w hipotezie, nie mogą być złagodzone do funkcji . Moje pytanie brzmi:

\sum_{k \leq n} μ (k)^{2} = Ω (n) .

$\sum_{k \leq n} \mu(k)^2 = \Omega(n) \text.$

μ (k)

$\mu(k)$

U P \cap c o U P \subseteq N P \cap c o N P

$\mathsf{UP} \cap \mathsf{coUP} \subseteq \mathsf{NP} \cap \mathsf{coNP}$

f (k)

$f(k)$

N P

$\mathsf{NP}$

Jaka jest obecnie najniższa znana nam klasa złożoności , tak że funkcja w spełnia oszacowanie W szczególności, ponieważ niektórzy teoretycy uważali, że obliczania nie ma w , czy możemy zapewnić inne funkcje $\mathsf{C}$ $f(k)$ $\mathsf{C}$
$\sum_{k \leq n} μ (k) \cdot f (k) = Ω (n) ?$ $\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?

— Hsien-Chih Chang 張顯之
źródło

Niektóre klasy kwantowe, takie jak P ^ {BQNC}, również powinny działać, ponieważ faktoring leży w tej klasie.

— Robin Kothari,

f (k) = k_{i}

$f(k) = k_i$

i

$i$

@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

f \in N C^{0}

$f \in NC^0$

f

$f$

{- 1, 0, 1}

$\{-1,0,1\}$

{- 1, 1}

$\{-1,1\}$