3D Ising Model
Research Summary
Statistical Mechanics, Three-Dimensionality and NP-Completeness: I. Universality of Intractability of the Partition Functions of the Ising Model Across Non-Planar Lattices
This work provides an exact characterization, across crystal lattices, of the computational tractability frontier for the partition functions of several Ising models. Our results show that beyond planarity computing partition functions is NP-complete. We provide rigorous solutions to several working conjectures in the statistical mechanics literature, such as the Crossed-Bonds conjecture, and the impossibility to compute effectively the partition functions for any three-dimensional lattice Ising model; these conjectures apply to the Onsager algebraic method, the Fermion operators method, and the combinatorial method based on Pfaffians. The fundamental results of the area, including those of Onsager, Kac, Feynman, Fisher, Kasteleyn, Temperley, Green, Hurst and more recently Barahona:This work provides an exact characterization, across crystal lattices, of the computational tractability frontier for the partition functions of several Ising models. Our results show that beyond planarity computing partition functions is NP-complete. We provide rigorous solutions to several working conjectures in the statistical mechanics literature, such as the Crossed-Bonds conjecture, and the impossibility to compute effectively the partition functions for any three-dimensional lattice Ising model; these conjectures apply to the Onsager algebraic method, the Fermion operators method, and the combinatorial method based on Pfaffians. The fundamental results of the area, including those of Onsager, Kac, Feynman, Fisher, Kasteleyn, Temperley, Green, Hurst and more recently Barahona:
- for every Planar crystal lattice the partition functions for the finite sublattices can be computed in polynomial-time, paired with the results of this paper:
- for every Non-Planar crystal lattice computing the partition functions for the finite sublattices is NP-complete, provide an exact characterization for several of the most studied Ising models. Our results settle at once, for several models, (1) the 2D non-planar vs. 2D planar, (2) the next-nearest neighbour interactions vs. 2D, and (3) the general 3D Ising, intensively studied open problems of the area.
Our results axe obtained by establishing a Kuratowski-like characterization theorem for the class of (infinite) crystal lattices called Bravais lattices, that can also be extended to general crystal structures. The "forbidden subgraph," called Kuratowskian, plays the central role, being contained in every non-planar crystal lattice. This universality phenomenon (existence independent of lattice structure), captured in the "equation": Translational Invariance + NonPlanarity = Universality of Subgraphs, provides a unified understanding of non-planarity as a root of computational intractability. The important structural property of the Kuratowskians is that they are "embedding-universal" for 3- regular graphs, in the sense that every such graph has a subdivision included in the Kuratowskian. Several NP-hardness results are obtained in this paper, by using different types of Kuratowskians, which in turn witness NP-hardness of various counting coefficients of the partition functions.
The exceedingly complex mathematical methods that solved the planar cases of the Ising model, could be interpreted as an explanation of why no 3D solvable cases have been found. Richard Feynman in 1972 commented " The exact solution for three dimensions has not yet been found". Our results, for the Ising models that we consider in this paper, provide evidence of a paradigm-shift: the "has not yet been found" needs now be replaced with "it may be computationally intractable across lattices."
SorinFest
Lars Onsager, Brown University Professor of Chemistry from 1928-1933 and winner of the Nobel Prize for Chemistry in 1968. In 1944, Onsager obtained the phase transition and exact solution for the 2D planar Ising Model (Ising ferromagnetic 2D plane grid). His seminal exact mathematical proof of the 2D planar Ising model partition function formula is considered one of the most extraordinary mathematical tour de force proofs in statistical physics. Answering the call to “make [the proof] human”, a dream team of mathematicians and physicists, including Kac, Ward, Feynman, Hurst, Kasteleyn, and Temperley attempted until 1975 to generalize Onsager’s proof to three dimensions, but without success. Kac and Ward, with contributions from Feynman, obtained a combinatorial proof of the Onsager theorem. In 2000, Sorin published the paper "Statistical Mechanics, Three-Dimensionality and NP-completeness. I. Universality of Intractability for the Partition Function of the Ising Model Across Non-Planar Lattices" at the Symposium on the Theory of Computing (STOC). His paper showed, for several Ising spin glass models, that for every non-planar (and therefore every 3D) model, computing the partition function is NP-complete. The proofs were axiomatic: Non-planarity plus Translational Invariance implies NP-completeness.
The dimer problem and the Ising problem were finally solved for planar lattice graphs only. It was found that a generalization to nonplanar lattice graphs, including all three-dimensional lattice graphs, is impossible unless the number of Pfaans involved is allowed to increase to intractably large numbers.
P. W. Kasteleyn
The Statistics of Dimers on a Lattice. (Physica 1961)
How famous physicists and mathematicians commented in the 1950-1960s on an NP-complete problem before the concept of NP-completeness was discovered in 1971 by Stephen Cook and Leonid Levin.
Sorin Istrail
No physically interesting nonplanar lattice has been solved completely as yet. The simplest such lattice is the plane square lattice with interactions along the diagonals as well as the sides of the squares, sometimes called the union jack lattice. It is somewhat melancholy thought that nearly twenty-four years of work has added relatively little to our knowledge of analytical properties of the Onsager Ising model itself, though we now have a great deal more information deduced from series expansions.
With monotonous regularity, each method has reproduced virtually the same results as those listed above and has added virtually no new ones on the analytical side. This information may be summarized as knowledge for planar lattices but not for any interesting nonplanar lattice of the partition function and correlations as a function of temperature in zero magnetic field, together with the spontaneous magnetization and various boundary and impurity effects. It relates either the trace of vacuum to vacuum expectation of a product of linear sums of operators known as Cliord or Fermi operators to what is known mathematically as a Pfaan.
This experience is almost unique in mathematical physics. Nearly always a valid new treatment of a problem produces new results as well as reproducing old ones.
H. N. V. Temperley
Two-dimensional Ising Models (Phase transitions and critical phenomena 1974)
Conspicuously missing from the table of open problems are the calculation of the free energy of the two-dimensional Ising model when H is non-zero, and the calculation of the free energy of the three-dimensional Ising model. This omission is intentional. These two problems are both extremely difficult. Indeed, they have existed for a quarter of a century, and absolutely no progress has been made. By no progress, we mean no progress toward an explicit solution.
B. M. McCoy and T. T. Wu
The Two-Dimensional Ising Model (Harvard University Press 1973)
The three-dimensional case does exhibit a phase transition, but exact calculation of its properties has proved hopelessly difficult. The two-dimensional case for so-called nearest-neighbor interactions was solved by Lars Onsager. In Onsager's solution, a veritable tour de force of mathematical ingenuity and inventiveness, he uncovered a number of surprising features and started a series of investigations which continue to this day.
The solution was difficult to understand, and George Uhlenbeck urged me to try to simplify it. "Make it human," was the way he put it. At the Institute for Advanced Studies at Princeton, I met John C. Ward, and we succeeded in rederiving Onsager's result. Our success was in large measure due to knowing the answer; we were, in fact, guided by this knowledge. But our solution turned out to be incomplete. It took several years and the effort of several people before the gap in the derivation was filled. Even Feynman got into the act. He attended two lectures I gave at CalTech and came up with the clearest and sharpest formulation of what was needed to fill the gap. The only time I have ever seen Feynman taking notes was during the two lectures. Usually, he is miles ahead of the speaker, but following combinatorial arguments is difficult for all mortals.
Mark Kac
Enigmas of Chance (Harper and Row 1985)
The exact solution for three dimensions has not yet been found.
Richard Feynman
Lectures on Statistical Mechanics (Addison-Wesley 1972)
It has been rather puzzling that the two methods at present known for finding exact solutions for the Ising problem, namely the algebraic method of Onsager and the combinatorial method employing Pfaans, have exactly the same range of application, although they appear so different in approach. Problems which yield to one method yield to the other, whilst problems which are not tractable by one approach also fail to be exactly solved by the other, although the reasons for this failure appear to have completely different mathematical origins.
On the one hand, Ising problems which cannot be solved by the Pfaan method are characterized by the appearance of crossed bonds, which produce unwanted negative signs in the combinatorial generating functions, and such crossed bonds are usually manifestations of the topological structure of the lattice being investigated, i.e., the three-dimensional cubic lattice.
On the other hand, the Onsager approach breaks down because the Lie algebra encountered in the process of solution cannot be decomposed into sufficiently simple algebra. It is usually stated that such more complicated algebras occur only when the corresponding lattice has crossed bonds, although an explicit proof of this fact does not appear to be published. It is difficult to see why the two methods have exactly the same limitations.
C. A. Hurst
Relation between the Onsager and Pfaffian methods for Solving the Ising Problem (Journal of Mathematical Physics 1965)