Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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? –  Douglas Zare Mar 21 '11 at 7:01
    
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. –  Charles Mar 21 '11 at 12:50
1  
I would also be interested to know if this can be done for any k greater than 1 - if there is any progress. –  mixedmath May 28 '11 at 0:09
    
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. –  Angela Richardson Sep 11 '11 at 5:54
    
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. –  GarouDan Nov 2 '11 at 14:16

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
    
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... –  Steven Stadnicki Nov 28 '11 at 22:50
    
@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. –  Charles Nov 29 '11 at 2:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.