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