Sumas de potencias primos

Question

Se le dan números enteros positivos N, m y k. ¿Hay alguna forma de comprobar si $$\sum_{\stackrel{p\le N}{p\text{ prime}}}p^k\equiv0\pmod m$$ más rápido que calcular la suma (modular)?

Para concretar, se puede suponer $e^k<m<N.$

No conozco la manera, pero no me parece obvio que no exista ningún método. Sería interesante encontrar formas rápidas de demostrar o refutar la equivalencia. Se puede suponer que el caso particular del problema es "difícil", es decir, el módulo no es lo suficientemente cercano a N como para que los límites de tipo Rosser en la suma lo descarten.

Con $k=0$ esto es solo preguntar si $m|\pi(N)$ por lo que es posible calcular la suma en tiempo $O(N^{1/2+\varepsilon})$ utilizando el Lagarias-Odlyzko método. (O, de forma más práctica, una de las combinatorias $\pi(x)$ métodos). En $k>0$ la suma es superlineal y, por tanto, no puede almacenarse directamente (sin, por ejemplo, reducción modular), pero no está claro si existe un algoritmo rápido.

Puedes plantearte el problema como "Tu amiga, que tiene acceso a grandes recursos computacionales, hace la afirmación (N, m, k). Si es cierta, ¿puedes demostrarlo? Si es falsa, ¿puedes refutarla?".

Editar: He publicado un problema relacionado en cstheory, preguntando si hay una prueba corta o una prueba interactiva de que la suma es correcta.

Answer 1

Deléglise-Dusart-Roblot [1] dan un algoritmo que determina el número de primos hasta $x$ que son congruentes con $l$ modulo $k,$ a tiempo $O(x^{2/3}/\log^2x).$ Una modificación del algoritmo de Lagarias-Odlyzko [2] permite calcular el mismo en tiempo $O(x^{1/2+o(1)}).$

Entonces, usando cualquiera de los dos algoritmos, encuentra el número de primos en todas las clases de residuos mod primos hasta $\log m.$ Para cada primo $q,$ tomar el número total de primos en cada clase de residuo multiplicado por esa clase de residuo por el $k$ -ésima potencia; esto da el valor de $$\sum_{\stackrel{p\le N}{p\text{ prime}}}p^k\pmod q.$$

Utiliza el Teorema del Resto Chino para determinar el valor de la suma mod $2\cdot3\cdots\log m.$ El teorema de los números primos asegura que esto, o un poco más, es mayor que $m$ y, por tanto, suficiente para determinar el resultado de forma única. (Obsérvese que si $m>N^{k+1}/\log N$ más o menos, los cálculos se pueden hacer exactamente trabajando mod $k\log N$ más o menos).

Esto da la suma (mod m o en Z) en el tiempo $O(N^{1/2+o(1)})$ ya que el número de cálculos necesarios es logarítmico.

Referencias

[1] Marc Deléglise, Pierre Dusart y Xavier-François Roblot, Contar primos en clases de residuos , Matemáticas del cálculo 73 :247 (2004), pp. 1565-1575. doi 10.1.1.100.779

[2] J. C. Lagarias y A. M. Odlyzko, Informática $\pi(x)$ : Un método analítico , Revista de algoritmos 8 (1987), pp. 173-191.

[Charles, respuesta en MathOverflow . (Sí, se trata de la misma persona. Ver las otras respuestas allí para diferentes enfoques).