Mail to a friend · Print this article · Previous Columns

Tony Phillips' Take on Math in the Media A monthly survey of math news

This month's topics:

• Holographic algorithms
• The Gömböc
• Math and macromolecular architecture
• "Everything in our world is purely mathematical - including you"

The January-February 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 row-reduction, it can be computed with only about n³ 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 Fisher-Kasteleyn-Temperley (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 "Three-ice 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 not-all-equal 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 one-to-one 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 "Three-ice 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 in-in-in or out-out-out configurations? The image shows one admissible assignment of orientations. After Hayes.

The Gömböc looks something like this. It has back-front symmetry as well as symmetry in the plane shown. The prototype given to Arnol'd was about 4 inches wide.

"The Self-Righting Object" was among the items chosen for the New York Times Magazine's 7th Annual Year in Ideas (December 9, 2007). Named "the Gömböc" by its inventors --Gábor Domokos and Péter Várkonyi of Budapest-- it is the result, according to the Magazine, of "a long mathematical quest," starting with a problem posed to Domokos in 1995 by the celebrated Russian mathematician V. I. Arnol'd: to construct a "mono-monostatic" object. This would be a convex, homogeneous object with such a geometry that it would have exactly one stable position when placed on a flat surface. "Homogeneous" rules out toys of the "Comeback Kid" class which rely on a weighted bottom to keep them coming back up. The Gömböc also got play in a piece by Julie Rehmeyer in Science News Outline for April 7, 2007. Neither of these accounts gives any hint of the mathematics involved in Domokos and Várkonyi's solution, although Rehmeyer reminds us that "flat toys cut from a piece of plywood" always have at least two stable positions (see the Gömböc website for details). And she's funnier. It turns out that the Gömböc looks a bit like a turtle, and the question arises whether turtles might have evolved mono-monostaticity to avoid getting stranded on their backs. "So far, they've tested 30 turtles and found quite a few that are nearly self-righting. Várkonyi admits that most biology experiments study many more animals than that but, he says, 'it's much work, measuring turtles.'"

"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 Rockefeller-UCSF 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.
    The Nuclear Pore Complex is a large (molecular mass around 50 million) assembly of 456 proteins (in yeast) that spans the nuclear envelope and controls movement of material into and out of the nucleus. It was known that about 30 different proteins are involved, and the general shape was understood: "a doughnut-shaped structure, consisting of eight spokes arranged radially around a central channel." But the exact way the pieces fit together was a mystery. The article spells it out completely. An accompanying article, "Determining the architectures of macromolecular assemblies," explains how the puzzle was solved. The phrase the authors use to describe their method is "integrating spatial restraints." The spatial restraints are all the available data about the shapes and affinities of the constituent proteins, encoded into a set of functions that give 0 when "the restraint is satisfied" and higher values if it is violated. "In essence, restraints can be thought of as generating a 'force' on each component in the assembly, to mould them into a configuration that satisfies the data used to define the restraints." This "force" is essentially (minus) the gradient of a scoring function cooked up from the restraints. The "integration" is an optimization process: "The optimization starts with a random configuration of the constituent proteins' beads, and then iteratively moves them so as to minimize violations of the restraints." (The beads are points representing the location of each protein). The configuration is periodically shaken up by "simulated annealing" to "minimize the likelihood of getting caught in local scoring function minima."

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."

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 non-human 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 T-shirt. 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 Z-boson 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
Stony Brook University
tony at math.sunysb.edu

Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement