Proofs, Proofs, and Proofs
Your proof is not my proof
Jennifer Chayes is theorist who has made fundamental contributions in two different ways, some directly as a researcher and some indirectly as a manager. She is the director and co-founder of the Microsoft research lab in Cambridge—the one in New England—not England. Her main research contributions are in the area that spans theory and physics, including phase transitions in discrete systems such as networks. Her main administrative contributions have been in the creation of world class teams. Each of these types of contributions is impressive and each is hard—I think it takes a unique person to be able to do both so well.
Today I want to talk about the notion of proof, with all its various meanings.
Jennifer and Dana Randall helped create the area that now joins theorists and physicists who work on various Markov type systems. They started with a lone workshop, and now the area is a thriving part of both disciplines. When they started what was a proof in one area was not necessarily one in the other. This, Dana tells me, often led to comments like this being made during one of her presentations:
But Dana that is not an open problem, X “proved” it years ago in
One of the great achievements of Jennifer and Dana, with help from many others, is to reduce this dissonance about what proof means. Those from theory and those from physics, who work on Markov systems, may still not completely agree on what is a proof, but the differences are at least now acknowledged.
Types of Proofs—Silly?
Proof Reading: Ken and I try hard to proof-read these pieces for typos, math errors, and general examples of poor communication. We try very hard, but we know that we often fail short. One type of activity that has “proof” in it is the art of proof reading. Or is it proofreading? I have noticed that the New York Times almost never has spelling errors these days—thanks to spellcheckers—but grammar errors are another story. Oh well, I guess that’s progress.
Proof of Vodka
In the spirit of the holiday season we thought we would mention the notion of “proof” as used in the US to measure the content of alcohol in a beverage. I no longer drink—long story—but still appreciate that many do enjoy wine, beer, or even more adult type beverages. According to our friends at Wikipedia: Alcohol proof in the United States is defined as twice the percentage of alcohol by volume. Consequently, 100-proof whiskey contains 50% alcohol by volume (abv); 86-proof whiskey contains 43% alcohol. The terminology used in the United States is “n” proof, where “n” is a number—not “n” degrees proof.
Why “proof”? The proof that alcohol wasn’t overly watered down was that gunpowder would burn in it rather than be doused by the water. For rum this threshold was measured at 57.15% abv, so that became “100% proof.” The accurate British multiplied abv by 7/4 to get proof for any abv, but the rough Americans multiplied by 2. Now both countries require abv to be stated on bottles, proof being optional.
Perhaps it is best to skip this one, since it is so unclear. What is “proof” in the legal sense seems to be dependent on obvious stuff like country—legal rules differ from place to place. But even within the same country with the same rules, the notion of legal proof seems to depend on time, and perhaps on some hidden random variables. The definition linked to by Wikipedia is a 190-page PDF file with an awkward space in its URL. It defines legal proof as what the laws that define the status quo require in order to change the status quo. So let’s skip it.
Proof of Pudding
This is also the season for various treats that are called puddings. I especially like bread puddings of various kinds. The phrase “the proof is in the pudding” is a misquote of a misquixote—something mis-attributed to Miguel de Cervantes, Don Quixote (1615). The form credited to Cervantes is correct but is said by this site to date to the 1300’s and first appear in print in a 1605 work by William Camden: “The proof of the pudding is in the eating.” Here “proof” has its root meaning from Latin proba as “test.”
There also is the Yale University “Proof of the Pudding,” an all-female a cappella group specializing in jazz and swing. As an ex-professor of that great institution I agree that this is another fun use of the notion of proof of the pudding.
Math and Physics—Serious?
Math Proof: We could go on for days about what is a math proof. In many of our posts we discuss specific proofs, or we discuss general issues about proof. So I will not spend much time on it now. I do note that there still is a long trail of comments on whether or not the reals are countable or uncountable. So the notion of mathematical proof is not as clear-cut as some would like to believe.
Physics Proof The real point today is to return back to Jennifer and Dana examples of the disconnect between mathematical types of proofs and physics type proofs.
The simple point is this: physics accepts as a “proof” things that we would not and do not. Some examples to make the point are in order.
An Old Old Example: The Dirichlet Principle, named of course for Lejeune Dirchlet, is the “obvious” notion that certain functions exist that obtain a minimum value. Note we are talking about functions that have some minimum value, not points.
There is a book that is out of print that whose title summaries the issue nicely:
Dirichlet’s principle: A mathematical comedy of errors and its influence on the development of analysis, by Antonie Monna.
The great Bernhard Riemann named the principle after Dirchlet and believed it was obvious, from a physics argument, that there had to always be a solution. Karl Weierstrass later showed that there were reasonable problems of this type without any minimizer—that the principle was false in full generality.
The reason it was thought to be “obvious” was the analogy to calculus. We are probably familiar with the idea of finding the real number so that some given function is minimized for in , for example. A typical calculus problem might be: Find the value so that
is smallest for in . This is the one of the prime applications of calculus.
Things get more difficult when we replace by a function and by a functional and ask for the that makes
the smallest possible. An ancient example is to ask for the curve that has length and encloses the most area in the plane: the functional determines the area of the curve . This is the famous isoperimetric problem, whose answer is well known to be the circle with circumference .
The problem is that it is not hard to guess that the circle is the solution, proving that it is the solution is much harder. Jakob Steiner in 1838, showed that if there was a minimum, then it was the circle. He did this by a very clever argument based on taking any non-circle and making it more symmetric, and making the area not decrease. The difficulty with this argument is the proof that there is a minimum. That is the hard part of the proof—see this for a discussion.
Finally see the following for a silly solution in the spirit of the holidays:
Consider the large class of animals capable of changing their ratio of surface area to volume. (And note that these animals live — approximately — in Euclidean 3-space.) What do these animals do when it’s cold? They curl up into a ball! More precisely, they assume the closest approximation to a ball that they can manage. This is because any exposed surface area is a place where heat is lost, and curling up into a ball minimizes that surface area. So a spherical or “ball” shape keeps animals warmer. Now, here’s how these ideas can be turned into a 4-line “biological proof” of the above proposition.
Proof by Physical Impossibility?
Suppose one can prove that the feasible ability to travel back in time and kill one’s grandfather. Is this a proof of ? A similar and more plausible case is when the ability to transmit information at faster than light speed. A controversial example of such an is discussed here.
Are there theorems in quantum information theory for which it is felt that the “nicest” proof is by “reduction to Einstein” rather than from axioms? We note that this paper by Ulvi Yurtsever implies that the ability to maintain a prediction advantage over quantum sources that are adduced to be genuinely random implies the ability to communicate faster than light. We invite readers to comment on other examples and the formal status of this kind of proof.
What is a proof? Must a proof be checkable by a human being unaided by a computer? Note that we could be talking about a checker for the proof, not the proof itself.