48
$\begingroup$

You are given positive integers N, m, and k. Is there a way to check if $$\sum_{\stackrel{p\le N}{p\text{ prime}}}p^k\equiv0\pmod m$$ faster than computing the (modular) sum?

For concreteness, you can assume $e^k<m<N.$

I don't know of a way, but it's not obvious to me that no method exists. Fast ways to prove or refute the equivalence would be of interest. You can assume that the particular instance of the problem is 'hard', that is, the modulus is not close enough to N so that Rosser-type bounds on the sum would rule it out.

With $k=0$ this is just asking if $m|\pi(N)$, so it is possible to compute the sum in time $O(N^{1/2+\varepsilon})$ using the Lagarias-Odlyzko method. (Or more practically, one of the combinatorial $\pi(x)$ methods.) For $k>0$ the sum is superlinear and so cannot be stored directly (without, e.g., modular reduction) but it's not clear whether a fast algorithm exists.

You can think of the problem as "Your friend, who has access to great computational resources, makes the claim (N, m, k). If her claim is true, can you prove it? If her claim is false, can you refute it?".

Edit: I posted a related problem on cstheory, asking if there is a short proof or interactive proof that the sum is correct.

$\endgroup$
7
  • $\begingroup$ The title and tags involve primes, but in the question you only use the suggestive notation $p$. Do you mean the sum to be over primes up to $N$? Can you give some motivation for considering this sum? $\endgroup$
    – Douglas Zare
    Mar 21, 2011 at 7:01
  • $\begingroup$ Yes, the sum over primes up to N. The motivation is checking -- or allowing others to check -- sequences such as oeis.org/A125825 . In this example k = 6, m = a(n), and N = prime(a(n)). There are fast methods for finding prime(n) from n, but none that I know of for finding the sum or the sum mod m faster than re-calculating the entire sequence. $\endgroup$
    – Charles
    Mar 21, 2011 at 12:50
  • 1
    $\begingroup$ I would also be interested to know if this can be done for any k greater than 1 - if there is any progress. $\endgroup$
    – davidlowryduda ♦
    May 28, 2011 at 0:09
  • $\begingroup$ let x be the number of primes $\leq N$. Then the sum cannot be 0 if m is even and x is even, or if m is divisible by 3 and x is 1(MOD3) because $p^{2n}$ is 1(mod3) unless p is divisible by 3. $\endgroup$
    – Angela Pretorius
    Sep 11, 2011 at 5:54
  • $\begingroup$ Maybe we can't do fast computer way using this, but is an interesting thing to do: if you create a polinomial wich the roots is the prime numbers and than you expand $\frac{f'(x)}{f(x)}$ you will find the sum of the roots raised in the powers sequentially. $\endgroup$
    – GarouDan
    Nov 2, 2011 at 14:16

1 Answer 1

Reset to default
11
$\begingroup$

Deléglise-Dusart-Roblot [1] give an algorithm which determines the number of primes up to $x$ that are congruent to $l$ modulo $k,$ in time $O(x^{2/3}/\log^2x).$ A modification of the algorithm of Lagarias-Odlyzko [2] allows the same to be computed in time $O(x^{1/2+o(1)}).$

So using either algorithm, find the number of primes in all residue classes mod primes up to $\log m.$ For each prime $q,$ take the total number of primes in each residue class times that residue class to the $k$-th power; this gives the value of $$\sum_{\stackrel{p\le N}{p\text{ prime}}}p^k\pmod q.$$

Use the Chinese Remainder Theorem to determine the value of the sum mod $2\cdot3\cdots\log m.$ The Prime Number Theorem ensure that this, or a little more, is greater than $m$ and hence sufficient to determine the result uniquely. (Note that if $m>N^{k+1}/\log N$ or so, the calculations can be done exactly working mod $k\log N$ or so.)

This gives the sum (mod m or in Z) in time $O(N^{1/2+o(1)})$ since the number of calculations needed is logarithmic.

References

[1] Marc Deléglise, Pierre Dusart, and Xavier-François Roblot, Counting primes in residue classes, Mathematics of Computation 73:247 (2004), pp. 1565-1575. doi 10.1.1.100.779

[2] J. C. Lagarias and A. M. Odlyzko, Computing $\pi(x)$: An analytic method, Journal of Algorithms 8 (1987), pp. 173-191.

[3] Charles, answer on MathOverflow. (Yes, this is the same person. See the other answers there for different approaches.)

$\endgroup$
2
  • $\begingroup$ Does the CRT actually apply here? That is, if I have (for instance) the value of the sum mod $(m+10)$, but the sum itself is substantially greater than $m$ (which can easily happen, e.g. if $N\gg m$) then that doesn't tell me anything at all about the value of the sum mod $m$ itself... $\endgroup$
    – Steven Stadnicki
    Nov 28, 2011 at 22:50
  • $\begingroup$ @StevenStadnicki: Yes, it does. The easiest way is to use the primes up to, say, 2.01 log N, so that the produce of the primes is larger than the total sum. You can then reduce normally. Other approaches are possible for small and/or smooth m. $\endgroup$
    – Charles
    Nov 29, 2011 at 2:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .