<p>I am posting this seperately from my earlier special case, because I believe it is a different approach to the problem, and has little relation to my other answer. It may not be exactly what you are looking for, but it is simple, and gets close.</p>

<p>There is a proof which Arthur will always accept whe the proof is correct, but will reject with probability $\frac{1}{(\log \log N)^{2+o(1)}}$. Here's how it works: Merlin sends Arthur the pair $(p_i,c_i = p_i^k\mbox{ mod }m)$ for each prime $p\leq N$. Arthur verifies the sum (taking time $O(N/\log(N)) \times O(\log(N)) = O(N)$). Arthur the checks that the correct number of primes was supplied (by calculating $\pi(N)$) which is sublinear in $N$. Lastly, for $S N$ random pairs, he confirms that $p$ is prime and that $p_i^k \equiv c_i \mbox{ mod }m$. This takes time $SN~O((\log \log N)^{2+o(1)})$. Taking $S = (\log \log N)^{-(2+o(1))}$, we obtain a linear time scaling. Thus, a fraction $S$ of all pairs are verified. If any of these fail, Arthur will of course reject. For Arthur to accept an incorrect proof, there must be at least one pair which fails one of these two tests (or the number of pairs must be less than $\pi(N)$ which was earlier checked). Thus as a fraction $S$ of all pairs are checked, the test will fail for an incorrect proof with probability at least $S$.</p>

<p>Note that for large $N$ this is much much better than random guessing, which succeeds with probability $\frac{1}{m} = \frac{1}{O(N)}$. </p>

CC BY-SA 2.5
2011-03-21T19:24:45.517Z
If posting two answers is bad practice, let me know and I will merge them. I left them seperate as the latter just came to me and is a completely different take compared to the first answer.
Joe Fitzsimons
CC BY-SA 2.5
2011-03-21T19:32:54.957Z
fine with me. especially in CW questions it's common to have multiple answers.
Suresh Venkat
CC BY-SA 2.5
2011-03-21T19:35:37.420Z
@Suresh: Yes, I know, but this isn't CW, and I don't want to come across as a rep-whore.
Joe Fitzsimons
CC BY-SA 2.5
2011-03-21T19:54:59.337Z
@Joe Fitzsimons: Thanks for posting them separately -- please don't merge them.  They are different answers, to be sure.
Charles
CC BY-SA 2.5
2011-03-21T20:04:49.017Z
Very nice answer.  It maxes out both resources -- Merlin's string is $\Theta(N)$ and Arthur uses $\Theta(N)$ time.  Nitpick: verifying primes individually will take too long to get your bound, but of course Arthur can generate them all and compare them to Merlin's list (requiring it to be in order).
Charles
CC BY-SA 2.5
2011-03-21T20:10:06.843Z
@JoeFitzsimons: it's fine :). if both answers deserve rep you'll get double points :)
Suresh Venkat
CC BY-SA 2.5
2011-03-21T20:51:40.630Z
@Charles: Yes, you would need to generate the primes in one go.
Joe Fitzsimons
CC BY-SA 2.5
2011-03-21T20:53:14.080Z
@Joe Fitzsimons: I trust you won't be offended if I wait a day or so before accepting your answer?
Charles
CC BY-SA 2.5
2011-03-21T21:00:53.897Z
@Charles: Of course not. I have no proof that it is optimal. There might actually be a protocol which yields a constant gap between the probabilities for accepting correct and incorrect proofs.
Joe Fitzsimons
CC BY-SA 2.5
2011-03-21T21:08:34.360Z
@Joe Fitzsimons: Heck, for all I know the probability can be improved to 1, the proof string improved to 0, and the time and space reduced to $O(\log N)$.
Charles
CC BY-SA 2.5
2011-03-21T19:23:31.523Z
2011-03-21T19:37:30.493Z
2011-03-21T19:37:30.493Z
Joe Fitzsimons
<p>This is a full answer to the problem which does not use Merlin at all.</p>

<p>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)}).$</p>

<p>Using either algorithm, find the number of primes in all residue classes mod primes until their product is greater than $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.$$</p>

<p>Use the Chinese Remainder Theorem to determine the value of the sum mod $2\cdot3\cdots\log m.$</p>

<p>By the Prime Number Theorem the largest prime needed is $(1+o(1))\log m,$ so this gives the sum in time $O(N^{1/2+o(1)}).$</p>

<h1>References</h1>

<p>[1] Marc Deléglise, Pierre Dusart, and Xavier-François Roblot, <a href="http://www.ams.org/journals/mcom/2004-73-247/S0025-5718-04-01649-7/S0025-5718-04-01649-7.pdf" rel="nofollow noreferrer">Counting primes in residue classes</a>, <em>Mathematics of Computation</em> <strong>73</strong>:247 (2004), pp. 1565-1575. <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.100.779" rel="nofollow noreferrer">doi 10.1.1.100.779</a></p>

<p>[2] J. C. Lagarias and A. M. Odlyzko, <a href="http://www.dtc.umn.edu/~odlyzko/doc/arch/analytic.pi.of.x.pdf" rel="nofollow noreferrer">Computing $\pi(x)$: An analytic method</a>, <em>Journal of Algorithms</em> <strong>8</strong> (1987), pp. 173-191.</p>

<p>[3] Charles, <a href="https://mathoverflow.net/questions/81443/fastest-algorithm-to-compute-the-sum-of-primes/81533#81533">answer on MathOverflow</a>. (Yes, this is the same person. See the other answers there for different approaches.)</p>

CC BY-SA 3.0
2011-11-28T22:39:05.040Z
2011-11-28T22:39:05.040Z
2017-04-13T12:57:54.777Z
Charles
<p>This is not a full answer, but rather a special case (for a larger value of $k$ than you consider), which I had originally posted as a comment. In the case that $k=x \phi(m)$ (for some integer $x$) there is a simple proof and Merlin's string can be of zero length. </p>

<p>To do this, Arthur simply calculates $\phi(m)$. This can be done by factorising $m$ (which can be done in time sublinear in $N$ even using trial division). Since $p^{x \phi(m)} \equiv 0 \mbox{ mod } m$ for all $p|m$, and $p^{x \phi(m)} \equiv 1 \mbox{ mod } m$ otherwise, if $k=x \phi(m)$ then we have $\sum_{p \leq N, p~prime} p^{k} \equiv \pi(N) - y \mbox{ mod } m$, where $y$ is the number of distinct prime divisors of $m$. As pointed out in the comment section $\pi(N)$ can be calculated in time sublinear in $N$, and hence this sum can be directly calculated by Arthur.</p>

<p>Further, for the special case that $1&lt;N&lt;m$ then the sum cannot equal $m\alpha$, as $1&lt;\pi(N)&lt;m$.</p>

CC BY-SA 2.5
2011-03-21T18:27:38.317Z
2011-03-21T18:34:56.310Z
2011-03-21T18:34:56.310Z
Joe Fitzsimons
<p>Merlin, who has unbounded computational resources, wants to convince Arthur that
$$m|\sum_{p\le N,\ p\text{ prime}}p^k$$
for $(N,m,k)$ with $k=O(\log N)$ and $m=O(N).$  Computing this sum in the straightforward way (modular exponentiation and addition) takes time $N(\log\log N)^{2+o(1)}$ with FFT-based multiplication.*  But Arthur can only perform $O(N)$ operations.</p>

<p>(Notation, for compatibility with earlier versions of this question: Let the sum equal $m\alpha$; then the question is whether $\alpha$ is an integer.)</p>

<p>Can Merlin convince Arthur with a string of length $O(N)$?  If not, can he convince Arthur with an interactive proof (total communication, of course, must be $O(N)$)?  If so, could Merlin use a string of length $o(N)$? Could Arthur use $o(N)$ time?</p>

<p>Arthur has no access to nondeterminism or other special tools (quantum methods, oracles other than Merlin, etc.) but has $O(N)$ space if needed.  Of course Arthur need not compute the sum directly, he merely needs to be convinced that a given triple (N, m, k) makes the equation true or false.</p>

<p>Note that with $k=0$ it is possible to compute the sum in time $O(N^{1/2+\varepsilon})$ using the <a href="http://www.dtc.umn.edu/~odlyzko/doc/arch/analytic.pi.of.x.pdf" rel="nofollow">Lagarias-Odlyzko</a> method.  For $k&gt;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.</p>

<p>I would also be interested in any algorithm to calculate the sum (modular or otherwise) other than by direct powering and addition.</p>

<p><em>*</em> $N/\log N$ numbers to calculate, time $\lg k\log N(\log\log N)^{1+o(1)}=\log N(\log\log N)^{2+o(1)}$ for each calculation.</p>

CC BY-SA 2.5
2011-03-21T05:15:48.527Z
[Related post on Math.SE](http://math.stackexchange.com/q/28238/2767).
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-03-21T05:37:42.180Z
Yes, related.  The key difference is that the math.SE question assumes that Merlin has zero computational resources and this one assumes he has unbounded resources.
Charles
CC BY-SA 2.5
2011-03-21T11:31:19.050Z
What about the time needed for primality testing?
Peter Shor 
CC BY-SA 2.5
2011-03-21T16:05:47.240Z
@Peter Shor: The primes up to N can be generated in sublinear time thanks to the algorithm of Atkin & Bernstein.
Charles
CC BY-SA 2.5
2011-03-21T16:14:49.520Z
@Charles: There are $N/\log N$ of them.
Joe Fitzsimons
CC BY-SA 2.5
2011-03-21T16:17:40.257Z
But it's not obvious to me that one need compute all the primes up to N.  If k = 0 the sum can be computed in less time than listing the primes up to N with an oracle.
Charles
CC BY-SA 2.5
2011-03-21T16:18:50.083Z
@Joe Fitzsimons: Yes, and N/log N is sublinear.  The Atkin-Bernstein algorithm takes time O(N/log log N), or O(log N/log log N) per prime.
Charles
CC BY-SA 2.5
2011-03-21T16:21:16.103Z
@Joe Fitzsimons: Arthur has time O(N), not time O(log N).
Charles
CC BY-SA 2.5
2011-03-21T16:24:31.957Z
@Charles: I realise that. My point was in relation to Peter's comments about primality testing, which would be in addition to the modular exponentiation. $N/\log(N) \times O(\log N) = O(N)$.
Joe Fitzsimons
CC BY-SA 2.5
2011-03-21T16:27:17.033Z
@Joe Fitzsimons: Yes, so as I said in the original question computing the sum in the straightforward way is not possible.  But it's not clear that there isn't a faster way to compute the answer.  For k = 0 the answer can be computed very quickly, soft-O of sqrt(N) I believe (this is nontrivial); can it be computed more quickly for higher k?
Charles
CC BY-SA 2.5
2011-03-21T16:32:52.383Z
@Charles: I don't see that $\sqrt{N}$ scaling for counting primes. Can you expain it? I would have thought it required superlinear scaling. The Sieve of Eratosthenes gives an $O(N^2)$ algorithm.
Joe Fitzsimons
CC BY-SA 2.5
2011-03-21T16:34:46.297Z
The algorithm is due to Lagarias & Odlyzko.  It is described, e.g., http://www.dtc.umn.edu/~odlyzko/doc/arch/analytic.pi.of.x.pdf  (And it's not $O(\sqrt N)$ but $\tilde{O}(\sqrt N).$)
Charles
CC BY-SA 2.5
2011-03-21T16:45:57.847Z
Also, the naive Sieve of Eratosthenes gives O(N log log N).  There are O(n) versions, and using the Atkin-Berrnstein sieve as mentioned earlier gives O(N/log log N).  But there are much faster methods starting with Meissel's method that do not enumerate primes at all.  (Lagarias-Odlyzko is a different sort of calculation entirely.)
Charles
CC BY-SA 2.5
2011-03-21T18:03:05.300Z
@Charles so as per the discussion with Joe, you merely want to check divisibility by m right ? I think that should be clarified rather than using the confusing $\alpha$ parameter
Suresh Venkat
<cc.complexity-theory><ds.algorithms><time-complexity><interactive-proofs><nt.number-theory>
Can Merlin convince Arthur about a certain sum?
Charles
# Can Merlin convince Arthur about a certain sum?

(Asked by: username_0 on 2011-03-21)

Merlin, who has unbounded computational resources, wants to convince Arthur that
$$m|\sum\_{p\le N,\ p\text{ prime}}p^k$$
for $(N,m,k)$ with $k=O(\log N)$ and $m=O(N).$ Computing this sum in the straightforward way (modular exponentiation and addition) takes time $N(\log\log N)^{2+o(1)}$ with FFT-based multiplication.\* But Arthur can only perform $O(N)$ operations.

(Notation, for compatibility with earlier versions of this question: Let the sum equal $m\alpha$; then the question is whether $\alpha$ is an integer.)

Can Merlin convince Arthur with a string of length $O(N)$? If not, can he convince Arthur with an interactive proof (total communication, of course, must be $O(N)$)? If so, could Merlin use a string of length $o(N)$? Could Arthur use $o(N)$ time?

Arthur has no access to nondeterminism or other special tools (quantum methods, oracles other than Merlin, etc.) but has $O(N)$ space if needed. Of course Arthur need not compute the sum directly, he merely needs to be convinced that a given triple (N, m, k) makes the equation true or false.

Note that with $k=0$ it is possible to compute the sum in time $O(N^{1/2+\varepsilon})$ using the [Lagarias-Odlyzko](http://www.dtc.umn.edu/~odlyzko/doc/arch/analytic.pi.of.x.pdf) method. 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.

I would also be interested in any algorithm to calculate the sum (modular or otherwise) other than by direct powering and addition.

*\** $N/\log N$ numbers to calculate, time $\lg k\log N(\log\log N)^{1+o(1)}=\log N(\log\log N)^{2+o(1)}$ for each calculation.

**Tags:** cc.complexity-theory, ds.algorithms, time-complexity, interactive-proofs, nt.number-theory

> **Comments:**
> **username_1**: [Related post on Math.SE](http://math.stackexchange.com/q/28238/2767).  
> **username_0**: Yes, related.  The key difference is that the math.SE question assumes that Merlin has zero computational resources and this one assumes he has unbounded resources.  
> **username_2**: What about the time needed for primality testing?  
> **username_0**: @Peter Shor: The primes up to N can be generated in sublinear time thanks to the algorithm of Atkin & Bernstein.  
> **username_3**: @username_0: There are $N/\log N$ of them.  
> **username_0**: But it's not obvious to me that one need compute all the primes up to N.  If k = 0 the sum can be computed in less time than listing the primes up to N with an oracle.  
> **username_0**: @username_3: Yes, and N/log N is sublinear.  The Atkin-Bernstein algorithm takes time O(N/log log N), or O(log N/log log N) per prime.  
> **username_0**: @username_3: Arthur has time O(N), not time O(log N).  
> **username_3**: @username_0: I realise that. My point was in relation to Peter's comments about primality testing, which would be in addition to the modular exponentiation. $N/\log(N) \times O(\log N) = O(N)$.  
> **username_0**: @username_3: Yes, so as I said in the original question computing the sum in the straightforward way is not possible.  But it's not clear that there isn't a faster way to compute the answer.  For k = 0 the answer can be computed very quickly, soft-O of sqrt(N) I believe (this is nontrivial); can it be computed more quickly for higher k?  
> **username_3**: @username_0: I don't see that $\sqrt{N}$ scaling for counting primes. Can you expain it? I would have thought it required superlinear scaling. The Sieve of Eratosthenes gives an $O(N^2)$ algorithm.  
> **username_0**: The algorithm is due to Lagarias & Odlyzko.  It is described, e.g., http://www.dtc.umn.edu/~odlyzko/doc/arch/analytic.pi.of.x.pdf  (And it's not $O(\sqrt N)$ but $\tilde{O}(\sqrt N).$)  
> **username_0**: Also, the naive Sieve of Eratosthenes gives O(N log log N).  There are O(n) versions, and using the Atkin-Berrnstein sieve as mentioned earlier gives O(N/log log N).  But there are much faster methods starting with Meissel's method that do not enumerate primes at all.  (Lagarias-Odlyzko is a different sort of calculation entirely.)  
> **username_4**: @username_0 so as per the discussion with Joe, you merely want to check divisibility by m right ? I think that should be clarified rather than using the confusing $\alpha$ parameter  

---

## 3 answers

### Answer by username_3 on 2011-03-21. Score: 7 | Accepted answer

I am posting this seperately from my earlier special case, because I believe it is a different approach to the problem, and has little relation to my other answer. It may not be exactly what you are looking for, but it is simple, and gets close.

There is a proof which Arthur will always accept whe the proof is correct, but will reject with probability $\frac{1}{(\log \log N)^{2+o(1)}}$. Here's how it works: Merlin sends Arthur the pair $(p\_i,c\_i = p\_i^k\mbox{ mod }m)$ for each prime $p\leq N$. Arthur verifies the sum (taking time $O(N/\log(N)) \times O(\log(N)) = O(N)$). Arthur the checks that the correct number of primes was supplied (by calculating $\pi(N)$) which is sublinear in $N$. Lastly, for $S N$ random pairs, he confirms that $p$ is prime and that $p\_i^k \equiv c\_i \mbox{ mod }m$. This takes time $SN~O((\log \log N)^{2+o(1)})$. Taking $S = (\log \log N)^{-(2+o(1))}$, we obtain a linear time scaling. Thus, a fraction $S$ of all pairs are verified. If any of these fail, Arthur will of course reject. For Arthur to accept an incorrect proof, there must be at least one pair which fails one of these two tests (or the number of pairs must be less than $\pi(N)$ which was earlier checked). Thus as a fraction $S$ of all pairs are checked, the test will fail for an incorrect proof with probability at least $S$.

Note that for large $N$ this is much much better than random guessing, which succeeds with probability $\frac{1}{m} = \frac{1}{O(N)}$.

> **Comments:**
> **username_3**: If posting two answers is bad practice, let me know and I will merge them. I left them seperate as the latter just came to me and is a completely different take compared to the first answer.  
> **username_4**: fine with me. especially in CW questions it's common to have multiple answers.  
> **username_3**: @Suresh: Yes, I know, but this isn't CW, and I don't want to come across as a rep-whore.  
> **username_0**: @username_3: Thanks for posting them separately -- please don't merge them.  They are different answers, to be sure.  
> **username_0**: Very nice answer.  It maxes out both resources -- Merlin's string is $\Theta(N)$ and Arthur uses $\Theta(N)$ time.  Nitpick: verifying primes individually will take too long to get your bound, but of course Arthur can generate them all and compare them to Merlin's list (requiring it to be in order).  
> **username_4**: @JoeFitzsimons: it's fine :). if both answers deserve rep you'll get double points :)  
> **username_3**: @username_0: Yes, you would need to generate the primes in one go.  
> **username_0**: @username_3: I trust you won't be offended if I wait a day or so before accepting your answer?  
> **username_3**: @username_0: Of course not. I have no proof that it is optimal. There might actually be a protocol which yields a constant gap between the probabilities for accepting correct and incorrect proofs.  
> **username_0**: @username_3: Heck, for all I know the probability can be improved to 1, the proof string improved to 0, and the time and space reduced to $O(\log N)$.  

---

### Answer by username_0 on 2011-11-28. Score: 6

This is a full answer to the problem which does not use Merlin at all.

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

Using either algorithm, find the number of primes in all residue classes mod primes until their product is greater than $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.$

By the Prime Number Theorem the largest prime needed is $(1+o(1))\log m,$ so this gives the sum in time $O(N^{1/2+o(1)}).$

# References

[1] Marc Deléglise, Pierre Dusart, and Xavier-François Roblot, [Counting primes in residue classes](http://www.ams.org/journals/mcom/2004-73-247/S0025-5718-04-01649-7/S0025-5718-04-01649-7.pdf), *Mathematics of Computation* **73**:247 (2004), pp. 1565-1575. [doi 10.1.1.100.779](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.100.779)

[2] J. C. Lagarias and A. M. Odlyzko, [Computing $\pi(x)$: An analytic method](http://www.dtc.umn.edu/~odlyzko/doc/arch/analytic.pi.of.x.pdf), *Journal of Algorithms* **8** (1987), pp. 173-191.

[3] username_0, [answer on MathOverflow](https://mathoverflow.net/questions/81443/fastest-algorithm-to-compute-the-sum-of-primes/81533#81533). (Yes, this is the same person. See the other answers there for different approaches.)


---

### Answer by username_3 on 2011-03-21. Score: 5

This is not a full answer, but rather a special case (for a larger value of $k$ than you consider), which I had originally posted as a comment. In the case that $k=x \phi(m)$ (for some integer $x$) there is a simple proof and Merlin's string can be of zero length.

To do this, Arthur simply calculates $\phi(m)$. This can be done by factorising $m$ (which can be done in time sublinear in $N$ even using trial division). Since $p^{x \phi(m)} \equiv 0 \mbox{ mod } m$ for all $p|m$, and $p^{x \phi(m)} \equiv 1 \mbox{ mod } m$ otherwise, if $k=x \phi(m)$ then we have $\sum\_{p \leq N, p~prime} p^{k} \equiv \pi(N) - y \mbox{ mod } m$, where $y$ is the number of distinct prime divisors of $m$. As pointed out in the comment section $\pi(N)$ can be calculated in time sublinear in $N$, and hence this sum can be directly calculated by Arthur.

Further, for the special case that $1


---

