{\huge Is This A Proof?}

Seeking the limits of mathematical proofs

\vspace{.3in} Ivan Vinogradov was a famous mathematician who created a whole method, named after him, that allowed him to make major advances on many open number theoretic problems. These included his theorem on the Weak Goldbach Conjecture and many others. Today Ken and I wish to talk about a new type of ``mathematical proof,'' illustrating it for the Weak Goldbach Conjecture.

It is strange, pushes the limits of what we usually call a proof, but still might be considered a proof. Our plan is to present it first abstractly, then give a concrete example of the new style ``proof.'' The central questions today are: Is this new type of proof really a proof, and is it new?

What Is A Proof?

We know what a mathematical proof is. It is a convincing argument that some mathematical statement is correct. The rigor of proofs has changed slowly over the years, yet today we would all agree what constitutes a proof and what does not. Of course some are short and straightforward, some are short and complex, some are long and complex, few are long and straightforward.

The acid test is: can a proof be checked? If it cannot then most would argue it is not a proof. A poorly written proof may fail this test, even if the writer of the proof is convinced of its correctness. Some proofs over the years have been rejected because they failed this checking test, and some that failed were later judged to be correct. Many ``correct'' proofs still have typos or minor errors that are easy for a checker to fix. A typo of $latex {x}&fg=000000$ for $latex {x+1}&fg=000000$ may be easy to spot, and thus a proof that is technically incorrect is really fine.

Computer Proofs

Let $latex {S}&fg=000000$ be some statement we wish to prove. A standard proof would be a written argument that convinces you and others that $latex {S}&fg=000000$ is true. If the proof uses computation then what usually happens is:

For some statement $latex {T}&fg=000000$ you prove that $latex {T \rightarrow S}&fg=000000$.
Then you use your computer to check that $latex {T}&fg=000000$ is correct.

This of course then shows that $latex {S}&fg=000000$ is proved. Well, this is the issue with computer-based proofs. The fear is that the checking of $latex {T}&fg=000000$ may be faulty due to a program error or even a hardware error. This can be reduced by having people review the programs, or even better having them independently write their own programs to check $latex {T}&fg=000000$. But there remains some feeling---for many---that such proofs could be wrong. We now have many proofs that no human can check, including proofs of the Four-Color Theorem (until recently) and this year's advance on Paul Erd\H{o}s's Discrepancy problem (EDP). Many are uncomfortable with proofs of this kind, proofs that rely on massive computation. In any case we will consider human proofs and machine proofs as ``standard'' types of proofs. For thoughtful comments on machine proofs see this by Robert Pollack.

We think we have discovered a new type of proof---it fits into neither of these categories.

Monte Carlo Proofs

We will now describe our new type of proof. It is a type of computer-based proof, but one that ups the ante and is even more problematic. We still think it is quite interesting and should be studied.

So let look at a new way to prove $latex {S}&fg=000000$. Let $latex {A_{i}}&fg=000000$ and $latex {B_{i}}&fg=000000$ be additional statements for $latex {i=1,\dots,N}&fg=000000$. The keys are the following:

We can prove that for each $latex {i}&fg=000000$ that $latex {A_{i} \wedge B_{i} \rightarrow S}&fg=000000$.
We can also prove that $latex {A_{i}}&fg=000000$ is true for at least $latex {1/2}&fg=000000$ of the $latex {N}&fg=000000$ indices $latex {i}&fg=000000$.
The statement $latex {B_{i}}&fg=000000$ is easy to check for any index $latex {i}&fg=000000$ by computation.

Then we can proceed as follows. Pick a set $latex {I \subset [N]}&fg=000000$ of $latex {m}&fg=000000$ random indices. For each $latex {i}&fg=000000$ in this set, check that $latex {B_{i}}&fg=000000$ is true. We claim that if all check correctly, then the probability that $latex {S}&fg=000000$ is true is at least $latex {1-2^{-m}}&fg=000000$.

The point is that each time we select an index $latex {i}&fg=000000$ there is a probability at least $latex {1/2}&fg=000000$ that $latex {A_{i}}&fg=000000$ is true. Since we check that $latex {B_{i}}&fg=000000$ is true, $latex {S}&fg=000000$ follows. But we may have selected an index $latex {i}&fg=000000$ so that $latex {A_{i}}&fg=000000$ is not true. The chance that this happens $latex {m}&fg=000000$ times is clearly at most $latex {2^{-m}}&fg=000000$, and so we have the claimed probability.

An Example

We return to the Weak Goldbach Conjecture. Vinogradov, in the 1930's, famously proved that every sufficiently large odd number is the sum of at most three primes. His ``sufficiently large'' was not effective at first: he proved there was a constant $latex {C}&fg=000000$ so that all odd numbers larger than it were the sums of three primes. In 1956 it was shown that $latex {C}&fg=000000$ was upper-bounded by $latex {3^{14,348,907}}&fg=000000$---a pretty large number. This was reduced in 2002 by Liu Ming-Chit and Wang Tian-Ze to approximately $latex {e^{3,100}}&fg=000000$---still pretty large. Computer searches still cannot even get near such a bound.

The long-term goal of course has been to reduce this constant $latex {C}&fg=000000$ and prove eventually the following theorem:

Theorem 1 Every odd integer greater than $latex {5}&fg=000000$ can be expressed as the sum of three primes.

Recently this has been achieved by Harald Helfgott, who technically proved that the theorem is true for all odd numbers greater than $latex {10^{27}}&fg=000000$. Computer searches had already verified the theorem up to $latex {10^{30}}&fg=000000$. But let us cycle back to the situation before last year where $latex {C}&fg=000000$ was still on the order of $latex {\exp(3,100)}&fg=000000$. Let $latex {S}&fg=000000$ be the statement that all odd numbers below $latex {C}&fg=000000$ are the sum of at most three odd primes. The set $latex {P}&fg=000000$ of prime numbers below $latex {C}&fg=000000$ has density order-of $latex {C/\ln(C)}&fg=000000$. The key concept is:

Definition 2 A subset $latex {Q}&fg=000000$ of the even numbers below $latex {C}&fg=000000$ is complementary to $latex {P}&fg=000000$ if every odd number below $latex {C}&fg=000000$ can be written as $latex {p+q}&fg=000000$ where $latex {p \in P}&fg=000000$ and $latex {q \in Q}&fg=000000$.

By a probabilistic argument, most subsets $latex {Q}&fg=000000$ of size $latex {c\ln(C)^2}&fg=000000$ are complementary, where $latex {c}&fg=000000$ is a small known constant. (Indeed some finer results are now known.) The size $latex {c\ln(C)^2}&fg=000000$ is not too large, and the numbers themselves have only order-$latex {\ln(C)}&fg=000000$ size. The final ingredient comes from the known heuristic bounds on Goldbachs' Conjecture itself. For most\/ even numbers $latex {k}&fg=000000$, one is highly likely to find primes $latex {q}&fg=000000$ and $latex {r}&fg=000000$ summing to $latex {k}&fg=000000$ within $latex {(\ln k)^{O(1)}}&fg=000000$ trials.

Executing the Proof

Given the above facts, the following procedure is feasible to execute. It is a computer procedure, but the work involved is orders of magnitude smaller than the EDP proof, and the predicates needing to be checked are simpler than for the Four-Color Theorem.

Generate $latex {m}&fg=000000$-many sets $latex {Q_{i}}&fg=000000$ of $latex {c\ln(C)^2}&fg=000000$-many even numbers below $latex {C}&fg=000000$..
For each $latex {i}&fg=000000$, for each $latex {k \in Q_{i}}&fg=000000$, search for primes $latex {q_{i,k},r_{i,k}}&fg=000000$ summing to $latex {k}&fg=000000$.
If each $latex {i,k}&fg=000000$-case succeeds, accept and output the entire table $latex {V}&fg=000000$ of $latex {[k,q_{i,k},r_{i,k}]}&fg=000000$ as the proof.

We could weaken the last step to accept if for a two-thirds majority of $latex {i}&fg=000000$, every $latex {i,k}&fg=000000$-case succeeds, but let us grant that the heuristic bounds on Goldbach's Conjecture are good enough that this stricter and simpler policy has a high chance of success.

So granting that it succeeds and we get the output table---note that it is easy to verify afterward that the $latex {q_{i,k}}&fg=000000$ and $latex {r_{i,k}}&fg=000000$ are prime and sum to $latex {k}&fg=000000$---as the ``proof,'' what do we really have? Define the statements as follows:

$latex {\bullet }&fg=000000$ The statement $latex {A_{i}}&fg=000000$ says: ``the set $latex {Q_{i}}&fg=000000$ is indeed complementary for $latex {\cal P}&fg=000000$ up to $latex {C}&fg=000000$.''

$latex {\bullet }&fg=000000$ The statement $latex {B_{i}}&fg=000000$ says: ``the set $latex {Q_{i}}&fg=000000$ has all its even numbers the sum of two primes.'' We claim that this fits our framework; let's check. At least half the time $latex {A_{i} \wedge B_{i} \rightarrow S}&fg=000000$. We suppose that some $latex {Q_{i}}&fg=000000$ is a complement---we only need one. Let $latex {n \le C}&fg=000000$ that is odd. Then $latex {n = p + k}&fg=000000$ where $latex {p}&fg=000000$ is a prime and $latex {k}&fg=000000$ is in $latex {Q_{i}}&fg=000000$. But we checked that $latex {B_{i}}&fg=000000$ is true, so all the $latex {k \in Q_{i}}&fg=000000$ are sums of two primes. This means that $latex {S}&fg=000000$ is proved.

One aspect is that if our routine failed, then we would have a significant ``probabilistic'' result of a completely different kind. It would indicate that the heuristic bounds on Goldbach's Conjecture are incorrect. But once the routine succeeds, all that is water under the bridge. We have already proved each $latex {B_{i}}&fg=000000$, and our routine has bypassed the need to prove $latex {A_{i}}&fg=000000$, which would ostensibly be computationally prohibitive.

Note also that we are of course not assuming Goldbach is true overall---we are only needing to verify it for the tiny sample of numbers that go into each $latex {Q_{i}}&fg=000000$. That is, call $latex {Q_{i}}&fg=000000$ ``good'' if $latex {A_{i}}&fg=000000$ is true, and ``hyper-good'' if every $latex {k \in Q_{i}}&fg=000000$ obeys the heuristic bounds on Goldbach. We don't actually need to argue that with probability at least $latex {\frac{1}{2}}&fg=000000$ a random $latex {Q_{i}}&fg=000000$ is hyper-good---once $latex {V}&fg=000000$ is checked the ``hyper'' part is dispensed with. Hence we only need that a random $latex {Q_{i}}&fg=000000$ is good with probability at least $latex {\frac{1}{2}}&fg=000000$. Then the confidence in $latex {V}&fg=000000$ being a proof is $latex {1 - \frac{1}{2^m}}&fg=000000$. Is that enough?

Comparing Other Probabilistic Proofs

Consider the problem of proving that a given arithmetic formula $latex {g(x_1,\dots,x_n)}&fg=000000$ computes the zero polynomial over some finite field $latex {\mathbb{F}}&fg=000000$. Whenever $latex {g}&fg=000000$ does not compute the zero polynomial, a random subset $latex {Q \subset \mathbb{F}^n}&fg=000000$ of known small size $latex {c}&fg=000000$ will, with probability at least $latex {\frac{1}{2}}&fg=000000$, include an argument $latex {x}&fg=000000$ giving $latex {g(x) \neq 0}&fg=000000$. Now choose $latex {m}&fg=000000$-many such subsets $latex {Q_{i}}&fg=000000$, and run a routine exhibiting that $latex {g(x) = 0}&fg=000000$ for every $latex {i}&fg=000000$ and $latex {x \in Q_{i}}&fg=000000$. Let $latex {V}&fg=000000$ be the resulting table of zero values. (Of course, we could have just picked one random $latex {Q}&fg=000000$ of size $latex {mc}&fg=000000$, but we are comparing with the above.) Is this $latex {V}&fg=000000$ exactly the same kind of ``proof''?

We argue no. The main reason is that the statement corresponding to $latex {A_{i}}&fg=000000$, namely that $latex {Q_{i}}&fg=000000$ is ``good,'' is counterfactual. It is saying that if $latex {g}&fg=000000$ were a non-zero polynomial, then $latex {A_{i}}&fg=000000$ would have had a counter-example. The only way to avoid the problem of ``which $latex {g}&fg=000000$?'' seems to be for $latex {Q_{i}}&fg=000000$ to be a universal hitting set for all non-zero $latex {n}&fg=000000$-variable polynomials over $latex {\mathbb{F}}&fg=000000$. The size bounds on universal hitting sets, especially in arithmetical not Boolean complexity, are murkier to argue.

The cases of randomized algorithms for deciding primality and other problems in $latex {\mathsf{BPP}}&fg=000000$ or $latex {\mathsf{RP}}&fg=000000$ (etc.) look similar. For a language $latex {L}&fg=000000$ in the Arthur-Merlin class $latex {\mathsf{AM}}&fg=000000$, there is a predicate $latex {R(x,y,z)}&fg=000000$ decidable in time $latex {|x|^{O(1)}}&fg=000000$ such that for all $latex {x}&fg=000000$:

$latex \displaystyle \begin{array}{rcl} x \in L &\implies& (\text{for most } y) (\exists z)R(x,y,z)\\ x \notin L &\implies& (\text{for most } y)(\forall z)\neg R(x,y,z). \end{array} &fg=000000$

Here we would want a bunch of pairs $latex {(y,z_y)}&fg=000000$ to be the proof of the theorem ``$latex {x \in L}&fg=000000$.'' By the perfect completeness theorem for $latex {\mathsf{AM}}&fg=000000$, we can replace $latex {R}&fg=000000$ by $latex {R'}&fg=000000$ such that the first line holds for all $latex {y}&fg=000000$, which is analogous to the idea of our routine always succeeding and outputting a set $latex {V}&fg=000000$ of such pairs.

The problem again, however, is that the goodness of the pairs is still defined with respect to counterfactual $latex {x \notin L}&fg=000000$ cases. Whereas in our proof, goodness is a positive statement, namely that the randomly-chosen set really is complementary to the set of primes.

Open Problems

Is this a new type of proof? What should we call it? Are there novel applications of the method?