Can Merlin convince Arthur about a certain sum?

Question

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

Answer 1

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

Answer 2

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

Answer 3

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<N<m$ then the sum cannot equal $m\alpha$, as $1<\pi(N)<m$.