Merlin, der über unbegrenzte Rechenressourcen verfügt, möchte Arthur davon überzeugen, dass

$$m|\sum_{p\le N,\ p\text{ prime}}p^k$$ für $(N,m,k)$ mit $k=O(\log N)$ und $m=O(N).$ Die einfache Berechnung dieser Summe (modulare Exponentiation und Addition) benötigt Zeit $N(\log\log N)^{2+o(1)}$ mit FFT-basierter Multiplikation. * Arthur kann jedoch nur$O(N)$-Operationen ausführen.

(Notation zur Kompatibilität mit früheren Versionen dieser Frage: Lassen Sie die Summe gleich $m\alpha$ ; dann ist die Frage, ob $\alpha$ eine ganze Zahl ist.)

Kann Merlin Arthur mit einer Schnur der Länge überzeugen $O(N)$? Wenn nicht, kann er Arthur mit einem interaktiven Beweis überzeugen (die totale Kommunikation muss natürlich $O(N)$ )? Wenn ja, könnte Merlin eine Zeichenfolge mit der Länge $o(N)$ ? Könnte Arthur $o(N)$ Zeit verwenden?

Arthur hat keinen Zugang zu Nichtdeterminismus oder anderen Spezialwerkzeugen (Quantenmethoden, Orakel außer Merlin usw.), hat aber bei Bedarf $O(N)$ -Raum. Natürlich muss Arthur die Summe nicht direkt berechnen, er muss lediglich davon überzeugt sein, dass ein gegebenes Tripel (N, m, k) die Gleichung wahr oder falsch macht.

Beachten Sie, dass mit $k=0$ ist es möglich , die Summe der Zeit zu berechnen , $O(N^{1/2+\varepsilon})$ unter Verwendung der Lagarias Odlyzko- Methode. Für $k>0$ die Summe superlinear und kann daher nicht direkt gespeichert werden (ohne z. B. modulare Reduktion), es ist jedoch nicht klar, ob ein schneller Algorithmus existiert.

Ich würde mich auch für einen Algorithmus interessieren, mit dem die Summe (modular oder anderweitig) berechnet werden kann, außer durch direkte Stromversorgung und Addition.

* zu berechnende Zahlen, Zeit lg k log N ( log log N ) 1 + o ( 1 ) = log N ( log log N ) 2 + o ( 1 ) für jede Berechnung.$N/\log N$$\lg k\log N(\log\log N)^{1+o(1)}=\log N(\log\log N)^{2+o(1)}$

Ich poste dies getrennt von meinem früheren Sonderfall, weil ich glaube, dass es eine andere Herangehensweise an das Problem ist und wenig mit meiner anderen Antwort zu tun hat. Es ist vielleicht nicht genau das, wonach Sie suchen, aber es ist einfach und kommt näher.

Es gibt einen Beweis, den Arthur immer akzeptiert, wenn der Beweis korrekt ist, der jedoch mit Wahrscheinlichkeit abgelehnt wird$\frac{1}{(\log \log N)^{2+o(1)}}$$(p_i,c_i = p_i^k\mbox{ mod }m)$$p\leq N$$O(N/\log(N)) \times O(\log(N)) = O(N)$$\pi(N)$$N$$S N$$p$$p_i^k \equiv c_i \mbox{ mod }m$$SN~O((\log \log N)^{2+o(1)})$$S = (\log \log N)^{-(2+o(1))}$$S$$\pi(N)$$S$$S$

$N$$\frac{1}{m} = \frac{1}{O(N)}$

Dies ist eine vollständige Antwort auf das Problem, bei dem Merlin überhaupt nicht verwendet wird.

$x$$l$$k,$$O(x^{2/3}/\log^2x).$$O(x^{1/2+o(1)}).$

$m.$$q,$$k$

$$\sum_{\stackrel{p\le N}{p\text{ prime}}}p^k\pmod q.$$

$2\cdot3\cdots\log m.$

$(1+o(1))\log m,$$O(N^{1/2+o(1)}).$

Verweise

[1] Marc Deléglise, Pierre Dusart und Xavier-François Roblot, Zählen von Primzahlen in Restklassen , Mathematics of Computation 73 : 247 (2004), S. 1565-1575. doi 10.1.1.100.779

$\pi(x)$

[3] Charles, antworte auf MathOverflow . (Ja, dies ist dieselbe Person. In den anderen Antworten finden Sie unterschiedliche Ansätze.)

$k$$k=x \phi(m)$$x$

$\phi(m)$$m$$N$$p^{x \phi(m)} \equiv 0 \mbox{ mod } m$$p|m$$p^{x \phi(m)} \equiv 1 \mbox{ mod } m$$k=x \phi(m)$$\sum_{p \leq N, p~prime} p^{k} \equiv \pi(N) - y \mbox{ mod } m$$y$$m$$\pi(N)$$N$

$1<N<m$$m\alpha$$1<\pi(N)<m$