Math in the Media 0502 May 2002 "Computers, Paradoxes and the Foundations of Mathematics''
is the title of an article by Gregory Chaitin (IBM Watson Research Center) in the March-April 2002 American Scientist
. This excerpt from his recent book "Conversations with a Mathematician'' (Springer) is subtitled "Some great thinkers of the 20th century have shown that even in the austere world of mathematics, incompleteness and randomness are rife.'' The great thinkers in question seem to be Russell, Gödel, Turing, Kolmogorov and ... Chaitin. In this non-technical but very illuminating piece, Chaitin shows us first how the fundamental mechanism of Russell's Paradox (the barber who shaves all the men who do not shave themselves; who shaves him?) reappears in Gödel's proof of his Incompleteness Theorem ("Any formal system that tries to contain the whole truth and nothing but the truth about addition, multiplication and the numbers 0, 1, 2, 3,... will have to be ... either inconsistent or incomplete.'') and in Turing's negative solution to the Halting Problem ("No formal axiomatic system can enable you to deduce whether a program will eventually halt.'') The connection to randomness comes through Chaitin's algorithmic information theory. There is a bound on the complexity of a data set that can be explained (in a precise sense that he describes) by a finite set of axioms. A completely random sequence of numbers, to take an extreme case, could not be generated by any shorter program. The conclusion for mathematics: "In practice, there's this vast world of mathematical truth out there --an infinite amount of information-- but any given set of axioms only captures a tiny, finite amount of this information. That, in a nutshell, is why Gödel incompleteness is natural and inevitable rather than mysterious and complicated.'' Links for further exploration available online
. Flies, weeds and statistical mechanics.
The flies are two species of fruit flies of the genus Drosophila
; the weeds are two species of mustards of the genus Arabidopsis
; the statistical-mechanical techniques are applied by a six-person Harvard-Cornell-Washington University-North Carolina State team (Bustamante, Nielsen, Sawyer, Olsen, Purugganan, Hartl) and the results are reported in the April 4 2002 Nature
. The goal is to tease out the pressure of natural selection on individual genes; they use a sophisticated "analytical method that borrows information from all the genes to make inferences about the magnitude of selection for any individual gene.'' The method, a "hierarchical bayesian analysis,'' leads to analytically intractable calculations. The authors handle them with Monte Carlo Markov Chain computation scheme borrowed from thermodynamics. The title of the work is "The cost of inbreeding in Arabidopsis
'' The Erdös Prizes.
In the April 5 2002 Science
Charles Seife has a News Focus piece entitled "Erdös's Hard-to-win Prizes Still Draw Bounty Hunters.'' Paul Erdös died in 1996, but his personal, quirky influence lives on through the prizes he offered for solutions to problems he found intriguing. The prize would be proportional to the difficulty of the problem. There are $10 problems, $25 problems, and a couple worth over $1000. Since his death the prizes have been administered by his long-time friend and associate Ronald Graham (U. C. San Diego), who will send a winner an Erdös-signed check ("suitable for framing'') and another of his own, suitable for cashing. Graham "estimates that the outstanding bounties on unsolved problems total about $25,000'' but does not seem to be worried about a run on the bank. A special case of a $1000 problem was worth a Fields Medal for Klaus Roth (University College, London) in 1958. Nash sightings
Sixty Minutes, CBS, March 14 2002. "Nash: Film No Whitewash'' is the headline on the website for the Mike Wallace interview. "Dr. John Nash, the Nobel Prize winning mathematician whose life is portrayed in the Oscar-nominated film `A Beautiful Mind,' denies being anti-Semitic. His wife denies he's homosexual. And a son denies he's a bad father.'' As Mike Wallace says: "It's been suggested that some of competing producers from other films that have been nominated have been spreading this stuff to the press'' in the heat of the campaign for the Oscars. The site features excerpts from the interview and two short streaming video segments. No math.
New York Times Business section, April 11 2002. "Economic Scene; You've seen the movie. Now just exactly what was it that John Nash had on his beautiful mind?'' by Hal R. Varian. A business-oriented analysis of Nash's game-theoretic contributions, including a worked-outexample of a Nash equilibrium. The article, available online, ends as follows: "Back to picking up girls. In the movie, the fictional John Nash described a strategy for his male drinking buddies, but didn't look at the game from the woman's perspective, a mistake no game theorist would ever make. A female economist I know once told me that when men tried to pick her up, the first question she asked was: "Are you a turkey?" She usually got one of three answers: "Yes," "No," and "Gobble-gobble." She said the last group was the most interesting by far. Go figure.''
Public Television, April 28 2002. "A Brilliant Madness.'' A one-hour documentary, presumably giving the reality behind the movie. The good part is substantial interviews with real people who were there: mathematicians (Mel Hausner, Felix Browder, Harold Kuhn, D. J. Newman), the economist Paul Samuelson, family and friends (Martha Nash Legg, John Stier, Alicia Nash, Donald Reynolds, Herta Newman, Zepporah Levinson) and quite a bit of the present-day John Nash himself. The bad part is many tedious minutes of generic video footage. The missing part is any look at Nash's mathematics beyond the title pages of his great papers, and any hint of the darker sides of his pre-breakdown personality. Public Television could have done better. Much ancillary material, including Nash interviews that were not part of the show and a primer on game theory by Avinash Dixit (Princeton, Economics) is available online. DNA Computer solves a hard problem.
Here's the problem: assign values 0
(False) or 1
(True) to the 20 variables A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T
so that the following 24-fold product gives the value 1
(c+p+R)(E+L+i)(m+b+T)(L+h+e)(S+d+F)(I+L+e)(a+D+k)(M+b+s)(E+Q+I)(O+I+q) (e+i+l)(F+K+D)(o+q+G)(f+S+M)(l+i+E)(L+A+N)(T+C+B)(J+g+h)(e+I+l)(R+t+C) (j+r+p)(A+k+n)(H+g+o)(H+P+j) = 1
| where a = 1-A , b = 1-B etc., and + stands for the logical "or'': || ||. |
The (unique) solution (A=0, B=1, C=0, D=0, E=0, F=0, G=1, H=1, I=0, J=1, K=1, L=1, M=0, N=0, O=1, P=1, Q=1, R=0, S=0, T=0
) was found by a DNA computer in Pasadena, programmed by a Cal Tech - USC team (R. S. Braich, N. Chelyapov, C. Johnson, P. W. K. Rothemund, L. Adelman). "The DNA computation ... exhaustively searched all 230
(1,048,576) possible truth assignments in the process of finding the unique satisfying assignment.'' The work, described in a Research Article in the April 19 2002 Science
, was picked up in the March 19 2002 New York Times
, in a piece by George Johnson: "In Classic Math Riddle, DNA Gives a Satisfying Answer'' available online
. After joking about Mick Jagger and "Can't get no satisfaction,'' Johnson gives an apt real-world interpretation, corresponding to (a+C+b)(c+E+F)(e+a+B) ...
| "Suppose Alice will attend a party only if Caroline does and Bobby doesn't, while Caroline insists that Eric and Francesca be there. Eric, though, refuses to be in the same room with Alice unless Bobby is there to distract her attention. Try to accommodate 20 such prima donnas and there are more than a million (2 to the 20th power) possible combinations to consider.''|
He notes that "The computation, which took four days of lab work to carry out, would have gone much faster with a regular old computer.'' In fact the team's report ends by saying "Despite our successes, and those of others, in the absence of technical breakthroughs, optimism regarding the creation of a molecular computer capable of competing with electronic computers on classical computational problems is not warranted.'' The team goes on to suggest specialized contexts in which molecular computation, as we know it today, might nevertheless be valuable. Johnson's take on the experiment: "What was remarkable was that a swarm of DNA molecules could be coaxed into solving a problem that would flummox an unaided human brain.'' Poincaré conjecture on NPR, and in the Times.
On Tuesday morning April 16 2002, listeners to National Public Radio's Morning Edition would have heard Bob Edwards say: "A British mathematician says he's found a way to solve a 100-year-old math mystery. Martin Dunwoody at Southampton University has been working on something called `the Poincaré conjecture;' it suggests a kind of universal quality of multidimensional space. For example, mathematicians inspired by the conjecture already have proven that in two dimensions the surface of objects like a sphere and a tabletop are similar, but no one has proved the conjecture true in 3-dimensional space. If Dunwoody has solved it, he'll win a million dollars, but not until people such as Arthur Jaffe say it's correct. Jaffe is Professor of Math at Harvard and President of the Clay Mathematics Institute. The Institute will award the million-dollar prize for solving of one of seven math mysteries.'' Their minds befogged with images of tabletops and spheres, they would have heard Arthur Jaffe explain that the Poincaré conjecture "is regarded as one of the major outstanding problems of the field.'' Edwards questions him on the status of Dunwoody's claim. Jaffee: "There's a little skepticism.'' Edwards asks about the other six mysteries, and then "Shouldn't these great minds be working on cancer, or something?'' Jaffe answers: "We feel that mathematics is really at the basis of all of science. Cancer of course is important. But these fundamental questions in mathematics have a way of coming up in every field of life.'' And he ends with: "We think it's very important that the brightest young people in the country, some of them, think about these questions which don't get quite as much publicity as cancer or other medical research at the moment.'' The segment is available online
NPR scooped the New York Times on this story. The best the Times could do was to run an AP dispatch ("UK Math Whiz May Have Solved Problem'') on April 25. This piece, however, does a little better on the mathematical background: "Before Poincare, mathematicians ... could list all the possible shapes of two-dimensional surfaces and use mathematical calculations to distinguish between them. His question, or conjecture, was whether the two-dimensional calculations could be easily modified to answer similar questions about three-dimensional spaces. He was pretty sure the answer was yes but couldn't prove it mathematically. Nearly 100 years later, math whizzes remain stuck. Even more frustrating, ... dimensions of four or higher were proven mathematically by American and British experts in the last 40 years. That leaves three dimensions as the remaining problem.'' The AP was also more explicit about the skepticism. They quoted Ian Stewart (Warwick; "This looks like a competent attempt'') and Colin Rourke (Warwick; "He's acknowledged the gap in his solution that I pointed out. ... He doesn't have cast-iron proof.'' The article is available online Sidewalk math on NPR.
The very next segment on the April 16 Morning Edition began like this. Bob Edwards again: "Unsolved math mysteries are for the experts, but what about the rest of us? New York math teacher George Nobl is taking the subject to the streets. He's on a mission to transform the subject from something to avoid to something that is fun.'' This is the same George Nobl who appeared in the New York Times
on February 7 and was picked up
in this column. NPR correspondent Madeleine Brand was sent out to do the interview. She described the problem of the day: You have 20 lbs. of cashews selling at $3.55 a pound. Peanuts sell for $2.50 a pound. How much peanuts should you add to the cashews to get a mixture selling at $3.20? Brand: "So this is a real-life question?'' Nobl: "They all are.'' The segment is also available online
, where you will find "expanded coverage'' and therein a link to the answer.
Stony Brook Math in the Media Archive