Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
8  
The first part has to do with zero-knowledge proofs (en.wikipedia.org/wiki/Zero-knowledge_proof). The second part is the PCP theorem (en.wikipedia.org/wiki/PCP_theorem). I'm not sufficiently well-versed to give a complete answer though. –  Akhil Mathew Jul 28 '10 at 11:58
6  
A slightly facetious remark: In practice, if you are on the receiving end of such a claim, you also have to decide what a priori probability you attach to the person in question having proved RH (as opposed to being a crank, say, or the proof-check coming out okay just by chance). (In my case it would be very low, less than 1 in a million or so.) Thus the write-up they present you would likely have to be very convincing to actually be convincing. So, unless you are already have a mathematician with a very strong reputation, you are probably best of presenting your entire proof ... –  Matt E Aug 3 '10 at 6:08
5  
... because peoples' a priori skepticism may be much greater than the probability of a proof-check of a 10 or 20 bit fragment of an incorrect proof coming out okay. –  Matt E Aug 3 '10 at 6:13

3 Answers 3

up vote 11 down vote accepted

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.

share|improve this answer
    
How do we know that the Riemann Hypothesis can be proven by an interactive proof system? Is there some general theorem? –  Casebash Jul 28 '10 at 12:34
    
You are right, there is a missing link. I edited my answer. –  MRA Jul 28 '10 at 12:52

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.