The new issue of American Scientist is on the Web and will soon be in the mail. My “Computing Science” column begins disarmingly enough, “I was a teenage angle trisector,” but shortly descends into the usual boring pedantry. On the other hand, I do answer the question that has been on every lip these past few weeks: Who was Pierre Laurent Wantzel?
An amateur’s outlook on computation and mathematics
- Home
-
About
-
Featured
- My God, It’s Full of Dots!
- Counting Your Chickens Before They’re Pecked
- The short arm of coincidence
- Prime After Prime
- Traffic Jams in Javascript
- Sunshine In = Earthshine Out
- Dancing with the Spheres
- The abc game
- Statistical mechanics of magnet balls
- World3, the public beta
- The n-ball game
- A slight discrepancy
- Googling the lexicon
- Kenken-friendly numbers
- Swapping Lies
-
Recent
-
Topics
-
Extras
-
Books
“David Bressoud’s book Proofs and Confirmations gives what I believe is the best-ever insider’s account of what it’s like to do mathematics.”
You do yourself a disservice. Your article is the best exposition of what proofs are all about that I have read in a while (and I will read Bressoud’s book).
A related comment: you quote Philip J. Davis as saying, “The authenticity of a mathematical proof is not absolute but only probabilistic”. Have you heard of probabilistic proof checking ? A major revolution in theoretical computer science from the mid 80s (culminating in a new way of characterizing the complexity class NP), it developed the idea of a “proof” as something that you can verify almost certainly by examining it in a few places, chosen randomly.
Such proofs were called Probabilistically Checkable Proofs (yes, PCP, I know :)). and led both to a characterization of NP (as the class of problems for which membership proofs can be so verified) as well as the foundation for proving impossibility results about even getting close to the optimal solution to an NP-complete problem (like the Travelling Salesman Problem, for example). These ideas were arguably the most stunning achievement in classical complexity theory over the last 20 years.
Thanks, Suresh, for your kind words. But whatever the merits or otherwise of my column, I can’t compete with Bressoud when it comes to “insider accounts” for the simple reason that I’m not an insider.
As for probabilistically checkable proofs, I totally agree that the notion is fascinating and the theory is a great achievement. And yet…. Correct me if I’m wrong, but I have the impression that PCP has had little or no effect on the working practices of ordinary mathematicians. It’s just not an appealing way to prove the kinds of theorems that most mathematicians consider interesting. And I wonder if that’s not further evidence that the main point of proof is not to determine whether or not a statement is true but rather to understand why it’s true.
Yes, you are right. PCP (the proof; I can’t say for the drug ;)) doesn’t directly affect the work of mathematicians: it’s something that came up in a different context, but has interesting implications for the process of checking a proof (mechanically).
I couldn’t agree more with your last statement. Now if only one could get undergraduates to understand this as well :).
In his Introduction to Differential Equations With Applications and Historical Notes, George Simmons describes his view of proofs. I highly recommend reading this piece. It is amusing as well as insightful. I’m writing from a place where I do not have access to the book, so I cannot quote some of its best lines, but I do remember he likens a (good) proof as a way of persuading the reader with a compelling argument as opposed to trying to beat him or her into submission with the bludgeon of formal and arcane logical reasoning.
Also, in the context of the text as a teaching volume, I remember he creates a metaphor for proof in terms of clothing. Sometimes the occasion calls for something formal, tight fitting, and uncomfortable (think suits, ties, tuxedos, and stiff shoes), but more often than not something a bit more casual and loose fitting (khakis and a polo shirt) is more appropriate and more appealing. The proof might even be more understandable.
Actually, it’s quite easy to trisect angles with the right tools for the job (not just compass and straight edge, of course). One of the simplest is called a tomahawk, from a fancied resemblance, and it can actually be constructed with a ruler and straight edge.
The tomahawk is basically a modified set square. Imagine a set square placed as a capital L, with the vertical extending arbitrarily far and the horizontal of unit length. Then to the left of the vertical, tangent to it just where it joins the horizontal, provide a circle of unit radius. You can fill in a little of the material to make it solid, and trim off the lower part of the circle.
Then to trisect an angle, align the tomahawk so that the vertical passes through the vertex, the circle touches one side, and the end of the horizontal touches the other. Then the vertical markes off one of the trisecting lines; flop the tomahawk over to get the other.
I have heard that you can use two tomahawks to quintisect (is that a word?) angles, but I know nothing further of this.
Well, I still can’t see how vos Savant’s solution to the Monty Hall problem could be right. I see that the odds become 50-50 when door 3 is false, but why one door has a higher likelihood than the other escapes me. Please post the answer!
Dear Michael,
If I write something down and say “This is the answer,” why should you believe me? How do we persuade ourselves and others that something is true? For Erdos it apparently took a computer simulation, although I’m sure that once he’d seen the computational evidence, he constructed an argument he found convincing. (Alexander Bogomolny has a Monty Hall applet at http://www.cut-the-knot.org/Curriculum/Probability/MontyHall.shtml, and I’m sure there are others out there as well.)
Having said all that, here’s my favorite version of the story. Suppose you initially choose Door 1. Monty then offers you an opportunity either to keep Door 1 or to trade it for both Door 2 and Door 3 — that is, you get the prize it it’s behind either of those doors. If the prize was hidden at random, so that each door has probability 1/3, the trade should have a payoff of 2/3. Agreed?
I submit that the situation where Monty opens a door and then allows you to switch to the remaining third door is equivalent to this trade. You still get the prize if it was hidden behind either 2 or 3. If you decline to switch, you win only if the prize was put behind 1.