From Whence...?

"The more the universe seems comprehensible the more it also seems pointless."
-- physicist Steven Weinberg as famously quoted in Jim Holt's "Why Does the World Exist?"


I'm currently finishing Jim Holt's bestseller (and one of the NY Times' Top 10 nonfiction picks for 2012), "Why Does the World Exist?" (now out in paperback). Won't write a full review since it's more philosophy than math or science, but will recommend it to those with a philosophical bent, or who have enjoyed any of the other recent books on that most fundamental of questions, 'why is there something instead of nothing?"

The first half of Holt's book, while good, takes a little bit of time to gain traction, and the second half is especially good and invigorating. Holt keeps the sometimes deep philosophical and theoretical discussion not only accessible, but also moving along at a pace which doesn't get too bogged down with any one set of arguments or thinker. If you are someone who scoffs at the very idea of reading an entire book on a question that essentially can't be answered, then you'll want to pass on this volume, but if you enjoy seeing the wide variety of cerebral exercises major thinkers have employed to approach this basic conundrum than Holt takes you on a good ride, tossing in personal anecdotes along the way.

My favorite chapter (not too surprisingly) is chapter 10 on Platonism, where, in addition to Plato, the likes of Kurt Gödel, Roger Penrose, Max Tegmark, Bertrand Russell, and Hartry Field are among those making appearances in the debate over whether there is an independent platonic realm of mathematics (apart from human consciousness), or is mathematics merely a human construction. Both sides have very astute and brilliant proponents.

The mini-portraits of the many fascinating individuals Holt discusses or holds court with in this book are just as interesting as the ideas they put forth. John Updike fans will find a chapter toward the end (#13) with their literary hero. Heidegger, Quine, Wittgenstein, Leibniz, Richard Swinburne, David Deutsch, Adolf Grunbaum, Derek Parfit, John Leslie, Thomas Nagel, Robert Nozick, are among the intriguing panoply of players (living and dead) who are aired in these pages (many individuals who I was not previously familiar with at all).  Some of the book's philosophical discussion is a bit muddied in semantics (as could be expected), and I prefer the discussions with scientists, but Holt deftly works his way through all of it, be it religion, cosmology, or quantum mechanics. And at the end comes a moving chapter on the death of his own mother.

For some extended reviews of the book here are two (of several) from the Web:

http://bnreview.barnesandnoble.com/t5/Reviews-Essays/Why-Does-the-World-Exist/ba-p/8475

http://articles.washingtonpost.com/2013-02-08/opinions/36990295_1_wrong-question-answer-universe

Of course the volume reaches no final resolution and there is a bit of predictability in so much as certain issues keep recurring as sticking points, yet the intellectual exercise remains entertaining. Holt notes early on in the volume that the question of why the world exists is "so simple that it would occur only to a child." Maybe that explains why, despite its intractability,  we find it such an irresistible inquiry... it makes us all feel like children again in this great big farfetched universe of ours (...or, multiverse).

One last thing:
The quotation I've long-used from Bertrand Russell heading my Math-Frolic blog comes from early in his career when his optimism about mathematics and empiricism was strong. Holt's book (again the chapter on Platonism) introduced me to another quote, I was unfamiliar with, from much later in Russell's storied life. I love the quote, and change-of-heart it expresses, so much so that I've added it to the Math-Frolic blog heading, and will leave you with it here:

"I have come to believe, though very reluctantly, that it [mathematics] consists of tautologies. I fear that, to a mind of sufficient intellectual power, the whole of mathematics would appear trivial, as trivial as the statement that a four-legged animal is an animal."

[NOTE: I've actually since moved the paired quotes over to the MathTango heading.]

[...This all reminds me of yet another brand new book now showing up in bookstores: not meaning to stray too far from mathematics, but computer scientist/keen-thinker Douglas Hofstadter's latest tome is, "Surfaces and Essences" (about the role of 'analogy' in human cognition), and I suspect it is must-reading for anyone interested in cognition. (Hofstadter was author of "Gödel, Escher, Bach," one of the most acclaimed works of nonfiction of the last half-century, and several works since. He also took over Martin Gardner's column at Scientific American for a few years back when Gardner retired.)]

Beholding Mathematics...

“Beauty is the first test: there is no permanent place in this world for ugly mathematics.” -- G.H. Hardy


Just a little Sunday rumination on mathematical beauty today….

Math bloggers come in a variety of flavors, sometimes with few specific overlapping interests, but what they often hold in common is an overarching desire to share math's beauty and wonder with others.
"The beauty of mathematics" is a phrase most math bloggers have probably used at some point… it rolls off our tongue (or keyboard), so obvious is the "beauty" of mathematical thought and application we see, despite its frequent lack of resonance with other lay folks.

This article about young Princeton University professor Manjul Bhargava well captures his enthrallment with the "beauty" of math:

http://www.livescience.com/28508-numbers-manjul-bhargava-nsf-bts.html

In it Bhargava says: "When you discover things about numbers, it's very beautiful. When mathematicians are thinking about their problems, we're not thinking about their various applications, but rather are pursuing beauty. That's how pure mathematicians think."

Bhargava is of Indian origin... same as the remarkable Ramanujan who also found incredible, and uncanny, beauty in mathematics, which he felt was communicated to him directly in visions from an Indian goddess. 

And most anyone who reads science on the Web has probably seen this Richard Feynman clip which goes semi-viral from time to time. In it he describes, touchingly, how he, as a scientist, is capable of perceiving beauty, just as much as one of his artist friends can do… perhaps even more-so. As he essentially says toward the end, 'How does science detract from the ability to perceive beauty… it only adds, it only ADDS!!' …and so too mathematics, one could say:



So why do people universally comprehend the notion of "beauty" when applied to art or music or fashion or even food, but not when it comes to mathematics?
Usually beauty is beheld directly through the senses, vision, hearing, taste, touch… but math is more abstract, beheld at a different cerebral level where we discern patterns or connections mentally, whether or not they are physically evident.
Certainly not all math is beautiful, and it is indeed interesting how some theorems or proofs can be viewed as elegant or beautiful, while others simply are not (EVEN though they may be equally true or valid). As Paul Erdös was fond of saying some proofs are "from the Book" (God's creation manual).

An article from Smithsonian Magazine notes "...two of the essential requirements for mathematical beauty. First, it is surprising... Second, it is simple."

Read more:
 http://www.smithsonianmag.com/science-nature/the-natural-beauty-of-math-174842751.html#ixzz2KS3JBicz

Meanwhile S.Lang, in "The Beauty of Doing Mathematics," addressing those who view mathematics as dry and dull, writes "Last time, I asked: 'What does mathematics mean to you?' And some people answered: 'The manipulation of numbers, the manipulation of structures.' And if I had asked what music means to you, would you have answered: 'The manipulation of notes?' "

Robert Krulwich, Marcus du Sautoy, and Simon Singh explore the topic in this short clip from the World Science Festival:



And below a longer piece from the same Festival (including, at the 76-minute point, comments on Platonism vs. non-Platonism in math):

http://worldsciencefestival.com/videos/mysteries_of_the_mathematical_universe

There the debate continues over whether mathematics is discovered or invented; whether it exists in some outer 'real' world or only within the processes of the human brain.
And one may reflect on and on and on about mathematical 'beauty,' but surely it at least (like all beauty), ultimately exists in the… mind… of the beholder (be that beholder Man or God).

Of P and NP

"The Golden Ticket" by Lance Fortnow


Who'd a thunk it!? …that somebody could write an engaging, fascinating account of the P vs. NP Millennium Problem for a mass audience? Moreover to have done so without ever too-technically defining either P or NP, nor introduced much of the jargon or mathematics one might expect such a treatise to require! Hats off to Scott Fortnow (a blogger at "Computational Complexity") for doing it!

P vs. NP is one of the seven famous Clay Institute Millennium Problems for which one earns a cool $1 million for simply finding a solution (… but of course "simply" is NOT the operative word! -- thus far only one of the problems, the Poincare Conjecture, has been solved… and, ironically, the solver, Grigori Perelman, refused the prize money!).

Fortnow's book has been well-praised by reviewers, and oddly it reminds me a bit of Jason Rosenhouse's "The Monty Hall Problem." Both books are uncannily the same size and shape (and about the same number of pages), but more importantly, just as Rosenhouse did a wonderful, meticulous, intricate job of explaining the Monty Hall Problem (and its many nuances) to a lay audience, Fortnow does a similar job for P vs. NP, with a book that is, surprisingly, a bit of a page-turner.

I suspect I could read Fortnow's work 3-4 more times and each time take away a little more knowledge and understanding of the depth of P vs. NP, such is the richness of the volume. The content and implications of the book crosses boundaries of computer science, philosophy, math, logic, complexity, and number theory.

For any who don't know, P problems are those that can essentially be solved relatively quickly; i.e. "efficiently" (via a computer at least), while NP problems cannot be solved in any reasonable amount of time, even with the aid of computers, even though proposed answers CAN BE checked quite quickly. And the conundrum is to discover if these two classes of problems are in fact one-and-the-same, i.e. P = NP… or, as MOST researchers believe, do P and NP problems represent distinctly separate categories. To the uninitiated it may seem like a question of hugely abstract or narrow interest, but as Fortnow notes, "Determining whether P = NP is the most important question in computer science and perhaps in all mathematics." [bold added] Again, most believe P ≠ NP, but this too is exceedingly difficult to PROVE.

The so-called "Travelling Salesman Problem" is likely the most well-known of the NP problems… given say a few hundred cities to visit, find the shortest, most efficient route for visiting them all (…might seem to some like a straightforward problem for a modern-day computer to solve… but, it ISN'T! there simply is no algorithm, nor brute force technique, to solve it in a human time-frame.
The initial chapters of the book employ made-up examples to communicate the nature of P vs. NP. Often I prefer the use of 'real-life' type examples over invented ones to get across mathematical or scientific ideas, but Fortnow's concocted versions are so good and entertaining that they serve his purposes well. Chapters 4 and 5 go into some of the history of P vs. NP… normally, a book might start off with the historical part, but I think Fortnow succeeds in drawing you into the whole subject with the introductory chapters, and only then putting forth the history which may be a little dry or tedious and not the best lead-in to the topic.

Chapter 7 touches on Gödelian thought as well as the "halting problem." Most folks are familiar with the paradoxical, self-referential sentence, "This sentence is not true." Fortnow introduces a variation, "There is no proof that this sentence is true," to help explain how Gödelian self-reference demonstrates that there exist sentences which may be known to be true, yet are unprovable (if the prior sentence is false, then there IS a proof of the sentence, but if there IS a proof that the sentence is true, then it CANNOT be false! And vice-versa IF the sentence IS true, then, by its own admission, there is NO PROOF of its truth). In the end though, Fortnow notes that "this paradoxical approach to P versus NP seems doomed to fail, at least as a direct attempt at showing P ≠ NP."

Chapter 8 is on cryptography, one of the most significant real-life areas that would be affected if P were ever shown to be equal to NP (in which case code breaking, including breaking RSA encryption, could be done with ease).

In Chapter 10 we learn about NC, 'Nick's Class' of problems, another category within complexity theory, that may or may not be equal to the NP category of problems. Such ideas may be old-hat for those well-steeped in computer science, but are a new arena for the rest of us.

One update I learned from the book is that Vinay Deolalikar's claimed 2010 proof that P ≠ NP is apparently no longer in play. Last I'd heard (but I haven't followed the story that closely) Deolalikar was still trying/hoping to patch the various objections that critics voiced concerning his 'proof.' Apparently, though there were (not surprisingly) fatal flaws he could not overcome.
In fact, according to Fortnow, "We are further away from proving P ≠ NP then we ever were. Not literally, but in the sense that there is no longer any obvious path, no known line of reasoning that could lead to a proof in the near future."
Fortnow does mention that the field of "algebraic geometry" is currently the best candidate for possibly making progress on the problem. And he does indicate toward the end that he believes eventually P will be shown to not equal NP "…but it might take twenty or two hundred or two thousand years."
This is yet another splendid book from Princeton University Press, on a topic rarely treated in book-length form for the layperson, and for most of us a valuable, mind-stretching offering.

(Princeton Univ. Press has a transcribed interview with Fortnow about his book here: http://press.princeton.edu/releases/m9937.html )

ADDENDUM: Scott Aaronson, who is far more expert than I to review the Fortnow book, now has his own very positive review up over at his blog here:

http://www.scottaaronson.com/blog/?p=1293