The probabilistic proof that 2^400-593 is a prime: a revolutionary new type of mathematical proof, or not a proof at all?

Avi Wigderson gave a great CS colloquium talk at HUJI on Monday (a real auditorium talk with an audience of about 200 people). The title of the talk was

The Value of Errors in Proofs – a fascinating journey from Turing’s 1936 seminal R ≠ RE to the 2020 breakthrough of MIP* = RE

A large part of the talk was devoted to the series of conceptually new forms of proofs compared to the ordinary notion of proofs in mathematics. Starting from the 1980s, these new notions of proofs came from theoretical computer science. They include Zero-knowledge proof (ZKP), interactive proofs (IP), multi-prover interactive proofs (MIP), probabilistically checkable proofs (PCP),  and the very recent quantum multi prover interactive proofs. Of course, all these proofs are probabilistic; the prover convinces the verifier(s) that a mathematical statement is correct only with very high probability.

One little disagreement Avi and I have is whether the probabilistic proofs of mathematical statements (from the 70s) could be regarded as a major new type of mathematical proof coming from TCS.  For example, in connection with the efficient primality testing of Solovay-Strassen and Rabin-Miller, Rabin’s paper stated the following theorem:

2^{400}-593 is a prime!

At that time, this theorem had only a probabilistic proof: you can be convinced that the statement is correct with very high probability depending on some internal randomization. I remember hearing a lecture by Rabin about it in the mid 70s where he was happy about this new notion of a proof (2000 years after Euclid) for a mathematical theorem. (And I was also happy about it.)

OK, now for the disagreement: in my view, Rabin’s proof that 2^{400}-593 is a prime (and similar results), is indeed a new startling notion of mathematical proof coming from TCS that belongs to this series of later discoveries and could even be regarded as one of its starting points.

According to Avi, Rabin’s proof that 2^{400}-593 is a prime is, in fact, not a proof at all! The ordinary notion of mathematical proof is captured by the class NP, and proofs are not relevant at all for statements that can be verified by efficient algorithms (whether deterministic or randomized).

This debate is 30% semantic, and 10% a matter of historical assessment and giving proper credits, but I think it is 50% a serious question about the interface of insights from theoretical computer science and practical reality, and of interpretation of results from TCS. In this case, it is about the meaning of proofs in mathematics and the practice of proving mathematical theorems.

Update: Here is the video of the HUJI talk Avi Wigderson – The Value of Errors in Proofs. Our little discussion starts here (37.30 roughly untill 43:00).

What do you think?

(Of course, of an even greater importance is the interface between insights from TCS and the practical reality of computation.)

Update: Interesting Facebook discussion; and another one;

593

This entry was posted in Computer Science and Optimization, Controversies, Philosophy, What is Mathematics and tagged , , . Bookmark the permalink.

15 Responses to The probabilistic proof that 2^400-593 is a prime: a revolutionary new type of mathematical proof, or not a proof at all?

  1. Geoffrey Irving says:

    I asked a while ago on cstheory whether there were natural “non-parameterized” statements where this kind of the proof was the only one known. I’d be curious if you know of any! Here by “non-parameterized” I mean the statement isn’t just an instance of a language where the only efficient algorithm known is randomized, so 2^{400} - 593 \in PRIMES wouldn’t count.

    https://cstheory.stackexchange.com/questions/21394/natural-theorems-proven-only-to-high-probability

    • Gil Kalai says:

      This is a good question, but do you have a way to say what “natural” is?

      • Geoffrey Irving says:

        Not really, which is definitely a flaw. I don’t have a clean definition of natural (beyond “I know it when I see it”), but I think the requirement to not be a member of an existing parameterized family of questions (a language) is a reasonable constraint.

      • Gil Kalai says:

        Geoffrey, one thing that I am not sure about is the extent of using randomized algorithms for identity testing in various algebra packages. There are various mathematical proofs that relies on heavy use of computers for algebraic manipulations but I am not sure to what extent randomization is used.

  2. hectorpal says:

    Is there any recording of that talk? I tried to find it but didn’t find it.

  3. This reminds me of how the US dollar came off the gold standards back in the 70s. Is math also going rogue?

  4. One can iterate to make the probability of error exponentially small in these algorithms, far smaller than the chance that a human-created proof of some theorem would have an error. So small that the chance of the algorithm ever getting it wrong in all the future history of mankind would be negligible. So I don’t see the value of worrying about this, vs. worrying whether some typical math paper is correct. Attention should be focused on those claims that are more likely to be wrong.

  5. Schlafly says:

    If there were really probabilistic proofs, then they would be applied to the big problems, like the Riemann Hypothesis and P=NP. There are many empirical reasons for believing in them. And yet no amount of such evidence ever adds up to a proof.

  6. Shai says:

    Another important aspect of traditional mathematical proofs is that they provide some insights as to why a statment is correct. While, of course, notions like “insigts” or “explantion” or “udnerstanding” are not formalizable, they do play an important role in our view of and respect for mathematical arguments. I guess that this aspect is more relevant when talking about “non-parameterized” statements (if I undersatnd correctly what Geoffrey Irving meant by it).

  7. Carl-Fredrik Nyberg Brodda says:

    “This debate is 30% semantic, and 10% a matter of historical assessment and giving proper credits, but I think it is 50% a serious question…” Is this a probabilistic proof that 10+30+50 = 100? 🙂

    • Gil Kalai says:

      The remaining 10% are related questions on proofs in mathematics. For example, if we have a machinery for proving a certain class of theorems, how do we value these theorems and proofs? There is also the meta-meta question about the value of such meta discussions.

  8. Yousif Mohammed says:

    Gil, you said that, “Rabin’s proof that 2^{400}-593 is a prime is, in fact, not a proof at all! The ordinary notion of mathematical proof is captured by the class NP, and proofs are not relevant at all for statements that can be verified by efficient algorithms” Do you mean that Avi is not convinced that 2^400-593 is a proof because we don’t have a witness to check whether it is a prime or not?

    • Yousif Mohammed says:

      Another issue: If Rabin’s proof is not captured by NP, then what class is that capture Rabin’s proof?

    • Gil Kalai says:

      Hi Yousif, no this is not the issue. What Avi says is that if the verification is via a polynomial time algorithm (that can be deterministic or random) this is not considered a “proof”. The notion of proof kicks in only when there is no efficient algorithm. What I say is that this is a nice formal setting but of little direct relevance to proofs in mathematics. (It can be used as an analogy or as a metaphor.)

      (Rabin proofs falls within BPP which reflects efficient algorithms.)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s