Why, in Superbowl of statistical mechanics, famous players could never cross goal line

When a lake freezes over, how do trillions of randomly oriented water molecules know at almost the same time to align themselves into crystalline form? Similarly, when iron becomes magnetized, how do trillions of atoms know to align their spins almost instantly?

The best-studied model in science to discuss these phase changes and, indeed, a wide variety of changes in state (neural networking, protein folding, flocking birds, beating heart cells, questions of economics, and more) is the Ising model, developed by Ernst Ising in 1926 as part of his PhD dissertation.

Ising conceived of a linear chain, composed of particles that have magnetic moments called ‘spins’ able to take an up or down position. Each particle’s spin influences the spins of the moments bordering it. The conception was expanded almost 20 years later into a two-dimensional grid of upward or downward spins, each spin influencing the behavior of spins around it, with a wider application in the material world.

The model can be expanded to any three-dimensional lattice model, and its properties figured out numerically with a high degree of accuracy. But not exactly. Not for the general case. As opposed to the known mathematical solutions for one or two dimensions, no one has been able to find an exact solution to any three-dimensional lattice problem in terms of elementary equations you could look up in a math book.

The continued application of Ising’s model, more than 8,000 papers published between 1969 to 1997, has tempted many scientists to extend the grid’s usefulness into three dimensions, the realm in which most real-world problems take place.

Now Sandia computational biologist Sorin Istrail has shown that the solution of Ising’s model cannot be extended into three dimensions for any lattice, and so exact solutions can never be found.

Sorin, who has just taken entrepreneurial leave from Sandia to accept the position of Senior Director of Informatics Research with Celera Genomics Corporation, says his paper will be published in May in the Proceedings of the Association for Computing Machinery’s (ACM) 2000 Symposium on the Theory of Computing.

Says Sorin, “Naturally, it’s not as useful as finding the Holy Grail. We all wanna be like Lars [Onsager, the Nobel-Prize chemist who, in a mathematical tour-de-force, extended the Ising model solution from one dimension to two]. But at least no one now needs to spend time trying to solve the unsolvable.”

To prove that the solution could not be extended, Sorin resorted to a method called computational intractability, which identifies problems that cannot be solved in humanly feasible time. There are approximately 6,000 such problems known in all areas of science. They are all mathematically equivalent to each other. A solution to one would be a solution to all. Says Sorin, “I showed that the Ising problem, for any lattice, is one of those problems. Therefore, it is computationally intractable.”

Nobel laureate Richard Feynman wrote in 1972 of the three-dimensional Ising model that “the exact solution for three dimensions has not yet been found.”

Other researchers who have tried read like a roll call of famous names in science and mathematics: Onsager, Kac, Feynman, Fisher, Kasteleyn, Temperley, Green, Hurst, and more recently Barahona.

Says Sorin, “What these brilliant mathematicians and physicists failed to do, indeed cannot be done.”

As for Ising, whom Sorin describes as “a genius,” the young German-Jewish scientist was barred from teaching when Hitler came to power. The modeler worked menial jobs and, though he survived World War II and taught afterwards in the United States, never published again.

Last modified: April 20, 2000