Why, in Superbowl of statistical mechanics, famous players
could never cross goal line
Threedimensional proof for Ising Model impossible,
Sandia researcher claims
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 beststudied 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 twodimensional
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 threedimensional 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 realworld 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
threedimensional 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 NobelPrize
chemist who, in a mathematical tourdeforce, 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
GermanJewish 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.
Sandia is a multiprogram laboratory operated by Sandia
Corporation, a Lockheed Martin Company, for the United States
Department of Energy under contract DEAC0494AL85000. With main
facilities in Albuquerque, N.M., and Livermore, Calif., Sandia has
major research and development responsibilities in national security,
energy and environmental technologies, and economic competitiveness.
Media contact:
Neal Singer, nsinger@sandia.gov, (505) 8457078
Technical contact:
Sorin Istrail, scistra@sandia.gov, (505) 8457612
