This month's topics:
Holographic algorithms The JanuaryFebruary 2008 American Scientist features a report by Brian Hayes on holographic (or "accidental") algorithms, a recent phenomenon in computational mathematics. "Their computational power comes from the mutual cancellation of many contributions to a sum, as in the optical interference pattern that creates a hologram," according to their inventor, Leslie Valiant (Harvard); hence the name. The primordial "holographic" algorithm is the determinant of an n by n matrix: in principle it is a sum of n! terms, but in practice, using rowreduction, it can be computed with only about n^{3} operations. In fact, determinants turn out to be at the heart of all the examples Hayes presents. For example, the "perfect matching" problem: on a given graph, is there a set of edges linking each vertex to exactly one other vertex? And the associated counting problem: if so, how many such matchings are there? A graph with one of its perfect matchings. After Hayes, American Scientist 96, No. 1. This question seems to require looking at all possible choices of edges (a number growing factorially with the number of vertices) to see which ones work, but for a planar graph the FisherKasteleynTemperley (FKT) algorithm, dating back to the early 1960s, equates the calculation of the number of perfect matchings on a planar graph with n vertices to the calculation of the determinant of a certain n by n matrix. Valiant's new holographic algorithms go one step further, and relate calculations in one context to the perfect matching problem in an associated graph. One such context, the "Threeice problem," is illustrated below. Hayes explains: "The strategy is to build a new planar graph called a matchgrid, which encodes both the structure of the ice graph and the notallequal constraints that have to be satisfied at each vertex. Then we calculate a weighted sum of the perfect matchings in the matchgrid, using the efficient FKT algorithm. Although there may be no onetoone mapping between individual matchings in the matchgrid and valid assignments of bond directions in the ice graph, the weighted sum of the perfect matchings is equal to the number of valid assignments." The "Threeice problem." For a planar graph where each vertex abuts 1, 2 or 3 edges, how many ways can the edges be oriented (blue arrows) with no ininin or outoutout configurations? The image shows one admissible assignment of orientations. After Hayes. The Gömböc
"The Molecular Architecture of the Nuclear Pore Complex" was the cover story in the November 29 2007 Nature and highlighted there ("News and Views," "Making the Paper") as a substantial achievement by its authors, a RockefellerUCSF team led by Michael Rout, Brian Chait and Andrej Sali. A striking feature of the research was the essential involvement of mathematical methods developed by physicists for handling problems with a very high number of degrees of freedom. Representative configurations at various stages of the optimization process from top (very large scores) to lower right (with a score of 0). Adapted from Nature 450 690; used with permission. Approximately 200,000 different initial configurations were tested, and used to yield "an ensemble of 1000 structures satisfying the input restraints." Then the structures from the ensemble were superposed, and used to generate a single structure for the entire pore. From the end of the abstract: "The present approach should be applicable to many other macromolecular assemblies." "Everything in our world is purely mathematical  including you"This startling quotation occurs about halfway through Dennis Overbye's "Laws of Nature, Source Unknown" in the December 18 2007 New York Times. Overbye attributes it to Max Tegmark, a cosmologist at MIT, whom he considers "The ultimate Platonist ... In talks and papers recently he has speculated that mathematics does not describe the universe  it is the universe. Dr. Tegmark maintains that we are part of a mathematical structure, albeit one gorgeously more complicated than a hexagon, a multiplication table or even the multidimensional symmetries that describe modern particle physics. Other mathematical structures, he predicts, exist as their own universes in a sort of cosmic Pythagorean democracy, although not all of them would necessarily prove to be as rich as our own." Tegmark's thesis is expounded in "Mathematical cosmos: why numbers rule" (New Scientist, September 15, 2007). The main argument is this: "If we assume that reality exists independently of humans, then for a description to be complete, it must also be well defined according to nonhuman entities  aliens or supercomputers, say  that lack any understanding of human concepts. ... This is where mathematics comes in. To a modern logician, a mathematical structure is precisely this: a set of abstract entities with relations between them. ... So ... If you believe in an external reality independent of humans, then you must also believe in what I call the mathematical universe hypothesis: that our physical reality is a mathematical structure." But just as you were thinking that this would make life simpler, you read on. "The hypothesis also makes a much more dramatic prediction: the existence of parallel universes." The explanation: "Most physicists hope for a theory of everything that ... can be specified in few enough bits to fit in a book, if not on a Tshirt. The mathematical universe hypothesis implies that such a simple theory must predict a multiverse. Why? Because this theory is by definition a complete description of reality: if it lacks enough bits to completely specify our universe, then ... the extra bits that describe our universe simply encode which universe we are in, like a multiversal phone number." If you are scratching your head in stunned disbelief, that's perfectly OK: "Evolution endowed us with intuition only for those aspects of physics that had survival value for our distant ancestors, such as the parabolic trajectories of flying rocks. Darwin's theory thus makes the testable prediction that whenever we look beyond the human scale, our evolved intuition should break down. ... To me, an electron colliding with a positron and turning into a Zboson feels about as intuitive as two colliding cars turning into a cruise ship. The point is that if we dismiss seemingly weird theories out of hand, we risk dismissing the correct theory of everything, whatever it may be." Tony Phillips 
Comments: Email Webmaster 
© Copyright
, American Mathematical Society

