Effizient berechenbare Funktion als Gegenbeispiel zu Sarnaks Mobius-Vermutung

35

Kürzlich haben Gil Kalai und Dick Lipton einen schönen Artikel über eine interessante Vermutung geschrieben, die von Peter Sarnak, einem Experten für Zahlentheorie und Riemannsche Hypothese, vorgeschlagen wurde.

Vermutung. Sei die Möbius-Funktion . Angenommen, ist eine Funktion mit Eingabe in Form einer binären Darstellung vonμ(k)f:N{1,1}AC0kk, then

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

Note that if f(k)=1 then we have an equivalent form of the Prime number theorem.

UPDATE: Ben Green on MathOverflow provide a short paper which claims to prove the conjecture. Take a look at the paper.

On the other hand, we know that by setting f(k)=μ(k) (with slightly modification so the range is in 1,1), the resulting sum has the estimation

knμ(k)2=Ω(n).
There is an upper bound that μ(k) can be computed in UPcoUPNPcoNP, so the constrain proposed on f(k) in the conjecture cannot be relaxed to an NP function. My question is:

What is the lowest complexity class C we currently know, such that a function f(k) in C satisfies the estimation

knμ(k)f(k)=Ω(n)?
In particular, since some of the theorists believed that computing μ(k) is not in P, can we provide other P functions f(k) which implies a linear growth in the summation? Can even better bounds be obtained?
Hsien-Chih Chang 張顯之
quelle
3
Some quantum class like P^{BQNC} should also work, since factoring lies in that class.
Robin Kothari
5
Is this even known if f(k)=ki for a fixed i?
Manu
2
@Emanuele, good question. The indicator function of the i-th bit in the binary representation of k is a linear "bracket polynomial", but it has very high coefficients, so it might not follow from the Green-Tao theorem on the correlation of the Mobius function with bounded-step nilsequences. Bounded-step nilsequences have bounded-degree bracket polynomials as special cases, but their result might have some restrictions on the magnitudes of the coefficients
Luca Trevisan
1
And is it known for fNC0?
domotorp
Do you want a function f with the range {1,0,1} or {1,1} or something else?
Jukka Suomela

Antworten:

4

There have been interesting developments on this problem, however Replacing AC0 with ACC(2) (Namely allowing mod 2 gates as well) is still well out-of-reach. Some progress beyond Ben Green's theorem can be found in this MO question https://mathoverflow.net/questions/57543/walsh-fourier-transform-of-the-mobius-function as well as this one https://mathoverflow.net/questions/97261/mobius-randomness-of-the-rudin-shapiro-sequence . In addition, Jean Bourgain proved Mobius randomness for every monotone function f (in terms of the binary-digit expansion).

Gil Kalai
quelle