ALBUQUERQUE, N.M. — 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 themselves 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 Ph.D. dissertation.
Now computational biologist Sorin Istrail at the Department of Energy’s Sandia National Laboratories 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.
Ising conceived of a linear chain, composed of particles like little magnets able to take an up or down position. The position of each magnet influences the positions of the magnets bordering it. The conception was expanded almost 20 years later into two-dimensional lattices of upward or downward magnets (actually magnetic moments or spins), each magnet influencing the behavior of magnets near it. The lattice had a wider application in the material world than the simpler chain.
The model also can be expanded into three dimensions 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.
Yet 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 by developing a proof in three dimensions, the realm in which most real-world problems take place.
“Very fundamental problems in physics hinge on whether these things are fully understood or not,” says Bill Camp, director of Sandia’s Computation, Computers and Math Center. “We don’t want something that might as well be right; scientists want the real answer.”
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 Istrail, “What these brilliant mathematicians and physicists failed to do, indeed cannot be done.” Istrail, 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 Istrail, “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, Istrail 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. Because they are all mathematically equivalent to each other, a solution to one would be a solution to all — an infeasible result.
Says Istrail, “I showed the Ising problem, for any lattice, is one of these problems. Therefore, it is computationally intractable.”
As for Ising, whom Istrail describes as “a genius,” the young German-Jewish scientist was barred from teaching when Hitler came to power. The modeler was restricted to menial jobs and, though he survived World War II and taught afterwards in the United States, never published again.