Proving the Riemann Hypothesis without revealing anything other than you proved it

Consider the following assertion from Scott Aaronson's blog:

Supposing you do prove the Riemann Hypothesis, it’s possible to convince someone of that fact, without revealing anything other than the fact that you proved it. It’s also possible to write the proof down in such a way that someone else could verify it, with very high confidence, having only seen 10 or 20 bits of the proof.

Can anyone explain where this result comes from?

Solution 1:

The correct answer has already been given by Akhil Mathew in the comments above.

The topic belongs to the field of complexity theory in computer science. In complexity theory, there exists an intriguing concept for the problem of deciding whether a given word belongs to a given formal language or not: interactive proof systems. These systems model the interaction between resource-limited verifier (say, you or me) and an almighty prover (say, your much, much smarter older sister). The goal of the interaction is that the prover convinces the verifier from the fact that the given word is or is not an element of the language such that:

• almost surely, the verfier can only be convinced from the true answer and
• the verifier can only be fooled to believe the opposite within a very small margin of error.

There are a large number of theoretical results with respect to these interactive systems. These resuts include the follwoing two statements (given informally):

• everything that can be proven by such an interactive protocoll can also be proven using an interactive protocoll that convinces the verifier (within small margin of error) but it does not reveal any information about the proof itself. (Zero-Knowledge-Proof, "Everything provable is provable in zero-knowledge" by Ben-Or et al, 1988)
• every proof can be rewritten such that inspection of just a constant number of bits from this proof convinces the verifier within only a small margin of error (PCP-Theorem, "Proof verification and the hardness of approximation problems" by Arora et al, 1992, and a number of other papers)

Both of these concepts and results are highly non-trivial and beyond the scope of this forum.

Of course, in the quote above Scott Aaronson is just using some everyday's problem to illustrate these concepts. To use these results formally, would have to convert the task of "proving the Riemann Hypothesis" to a decision problem of formal languages, as is standard in complexity theory.

EDIT: There is in fact a small modification in the model between both results stated above which I omitted. First, the interaction between one prover and the verifier can be generalized to multiple provers and a verifier. Next, there is a result that finds that the case of multiple provers can be equivalently reformulated as follows: The provers are removed from the protocol, rather there is a single (possibly very long) string which acts as a written proof for the word problem. Interaction is now looking at an arbitrarily chosen bit of this proof, and the verifier may choose the location of these bits randomly. This is called a Probabilistic Checkable Proof (hence, PCP). So ,in this scenario, the "written proof" of the Riemann Hypothesis would be interpreted as the proof string.

Solution 2:

The point is that SHORTPROOF is an NP-complete problem: given a sentence of length $n$ in the language of some formal proof system (ZFC, Peano arithmetic, etc), does it have a proof of length at most some fixed polynomial in $n$, such as $(2n)^{100}$? It's in NP because for a reasonable formal system you can check a given proof fairly quickly. This problem was considered in Goedel's letter to von Neumann that implicitly stated what we now call the $P \neq NP$ question (the heart of the problem, the universality of concrete NP-complete problems, wasn't known until much later).

Any NP-complete problem has a zero-knowledge proof protocol for demonstrating solutions of instances, e.g. that we have a SHORTPROOF of the Riemann hypothesis. These are "proofs that reveal nothing other than their own validity".

The role of the PCP theorem is to show that the proof protocols (interactive challenge/response games) can be very efficient for any stipulated level of confidence. The probability that the prover really does have a SHORTPROOF of Riemann, given that we follow the protocol and the prover wins, is at least 99 percent, or whatever specified degree of certainty.

Solution 3:

The concept behind it is Zero knowledge proof. Wikipedia has a good article about it.

The similar question was asked in paper "How to Prove a Theorem So No One Else Can Claim It" by M. Blum. Also this article discusses the question.