Merlín, que tiene recursos computacionales ilimitados, quiere convencer a Arthur de que

$$m|\sum_{p\le N,\ p\text{ prime}}p^k$$ para $(N,m,k)$ con $k=O(\log N)$ y $m=O(N).$ Calcular esta suma de forma directa (exponenciación modular y suma) lleva tiempo $N(\log\log N)^{2+o(1)}$ con multiplicación basada en FFT. * Pero Arthur solo puede realizaroperaciones$O(N)$.

(Notación, para compatibilidad con versiones anteriores de esta pregunta: dejemos que la suma sea igual a $m\alpha$ ; entonces la pregunta es si $\alpha$ es un número entero).

¿Puede Merlín convencer a Arthur con una cuerda de longitud $O(N)$ ? Si no, ¿puede convencer a Arthur con una prueba interactiva (la comunicación total, por supuesto, debe ser $O(N)$ )? Si es así, ¿podría Merlín usar una cadena de longitud $o(N)$ ? ¿Podría Arthur usar el tiempo $o(N)$ ?

Arthur no tiene acceso al no determinismo ni a otras herramientas especiales (métodos cuánticos, oráculos que no sean Merlín, etc.) pero tiene espacio $O(N)$ si es necesario. Por supuesto, Arthur no necesita calcular la suma directamente, simplemente necesita estar convencido de que un triple dado (N, m, k) hace que la ecuación sea verdadera o falsa.

Tenga en cuenta que con $k=0$ , es posible calcular la suma en el tiempo $O(N^{1/2+\varepsilon})$ usando el Lagarias-Odlyzko método. Para $k>0$ la suma es superlineal y, por lo tanto, no se puede almacenar directamente (sin, por ejemplo, reducción modular), pero no está claro si existe un algoritmo rápido.

También estaría interesado en cualquier algoritmo para calcular la suma (modular o de otro tipo) que no sea mediante alimentación directa y adición.

* números para calcular, tiempo lg k log N ( log log N ) 1 + o ( 1 ) = log N ( log log N ) 2 + o ( 1 ) para cada cálculo.$N/\log N$$\lg k\log N(\log\log N)^{1+o(1)}=\log N(\log\log N)^{2+o(1)}$

Estoy publicando esto por separado de mi caso especial anterior, porque creo que es un enfoque diferente del problema y tiene poca relación con mi otra respuesta. Puede que no sea exactamente lo que está buscando, pero es simple y se acerca.

$\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)}$

Esta es una respuesta completa al problema que no usa Merlín en absoluto.

$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.$$

Use el Teorema del resto chino para determinar el valor de la suma mod$2\cdot3\cdots\log m.$

Por el teorema del número primo, el primo más grande necesario es por lo que esto da la suma en el tiempo$(1+o(1))\log m,$$O(N^{1/2+o(1)}).$

Referencias

[1] Marc Deléglise, Pierre Dusart y Xavier-François Roblot, Cuenta primos en clases de residuos , Matemáticas de la computación 73 : 247 (2004), págs. 1565-1575. doi 10.1.1.100.779

[2] JC Lagarias y AM Odlyzko, Computing : An analytic method$\pi(x)$ , Journal of Algorithms 8 (1987), págs. 173-191.

[3] Charles, responde en MathOverflow . (Sí, esta es la misma persona. Vea las otras respuestas allí para conocer diferentes enfoques).

Esta no es una respuesta completa, sino más bien un caso especial (para un valor mayor de de lo que consideras), que originalmente había publicado como un comentario. En el caso de que (para algún entero ) hay una prueba simple y la cadena de Merlín puede ser de longitud cero.$k$$k=x \phi(m)$$x$

Para hacer esto, Arthur simplemente calcula . Esto se puede hacer factorizando (que se puede hacer en tiempo sublineal en incluso usando la división de prueba). Dado que para todos los , y contrario, si entonces tenemos , donde es el número de divisores primos de . Como se señaló en la sección de comentarios, se puede calcular en tiempo sublineal en$\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$, y por lo tanto, Arthur puede calcular esta suma directamente.

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