Can Merlin convince Arthur about a certain sum? 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 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.

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