56

The Ising model is a well-known and well-studied model of magnetism. Ising solved the model in one dimension in 1925. In 1944, Onsager obtained the exact free energy of the two-dimensional (2D) model in zero field and, in 1952, Yang presented a computation of the spontaneous magnetization. But, the three-dimensional (3D) model has withstood challenges and remains, to this date, an outstanding unsolved problem.

Marton Trencseni
  • 3,095
  • 1
  • 20
  • 30
  • 8
    First of all, I like the question. The problem so far with the answers (by Gerben and Lubos) is that they fail to grapple with the fact that in $d \ge 4$ the thermodynamics is trivial. Those are certainly non-integrable and amenable to embedding of NP-hard/complete problems, but the very act of taking the infinite limit solves/side-steps those problems. I can understand, separately, why $d \le 2$ and $d \ge 4$ can be solved, but is there any definite negative reason for $d=3$, rather than a lack of positive reason? – genneth Apr 30 '11 at 19:25
  • 2
    @genneth: I had an idea concerning that, but I'm not absolutely sure about it. The Ising model is the 'infinite coupling limit' of the lattice phi^4 model, in all dimensions. For D = 2 and 3, it has been shown that phi^4 is non-trivial, meaning there is a UV fixed point. D = 3 is thus the only case in which the calculation is non-trivial ánd the thermodynamics isn't. – Gerben May 01 '11 at 08:52
  • 1
    @Gerben: but I think that's simply what I thought --- the default position is that nothing is solvable. At high dimensions, universality/mean-field theory saves you, and at low dimensions, the completely separate reason of integrability does. I'm happy enough with that, but I do wonder if there isn't a more "continuous" reason... – genneth May 01 '11 at 13:22
  • @genneth: I am not sure what kind of reason you are looking for. Basically you stated it yourself: at low dimensions there are too few neighbors and therefore simpler interactions (or weaker correlations, if you will), at high dimensions there are too many neighbors and the theory becomes mean-field. There isn't much more to it than this. Of course, these statements hold pretty much for any model. The only difference between Ising and those other models is that it is integrable in 2d. But in 3d it is the same complete mess. – Marek May 01 '11 at 13:31
  • 5
    @genneth: and therefore, I'd add as an answer to this question: it is hard to solve because basically everything is hard to solve and 3d Ising is no exception. 2d Ising was such an exception but one shouldn't be blinded by one special case (of course, there are a lot more integrable models, but still few and far between generic models). – Marek May 01 '11 at 13:34
  • 2
    @Marek: I gave you comment an upvote. But I wouldn't rule out that one day we will have a unified theory of how things work. – genneth May 01 '11 at 19:20

5 Answers5

17

There is a result I only heard about recently: it has been proven that computing partition functions for the Ising-model in dimensions > 2 is NP-complete. (The paper can be found at http://www.cs.brown.edu/people/sorin/pdfs/Ising-paper.pdf; a more readable one is here http://www.siam.org/pdf/news/654.pdf - both can be found on the Wikipedia on the Ising model). I'm far from an expert on this, but the main idea is that a certain NP-complete graph theory problem on finding maximal sets of edges can be mapped to ground states of Ising-3D. Roughly, this means that you can't find ground states in polynomial time, and as most physicists know, if the difficulty of your problem scales exponentially, solving something exactly for large systems quickly becomes impossible.

Gerben
  • 840
  • 1
    I checked out the original proof by Ising for the 1D case. It is basically a simple mathematical trick to get rid of the N spin variables in the expression for the partition function. What's a good intuitive way to connect this to NP-completeness? Also, I had one of those PDFs open so I went ahead and read it, it concludes with "Finally, Ising’s original, ferromagnetic model, in which all coupling constants are equal (and positive), is a special case, so it too might yet fall within polynomial time." So the ferromagnetic case is not proven to be NP-complete, but it's also unsolved? – Marton Trencseni Apr 30 '11 at 20:13
  • 1
    There are multiple ways to go about solving the Ising model, and I'm not sure which method you used, and all become worse at high dimensions. If it's the transfer matrix method, in 2D you need to link all rows by transfer matrices - in a way, you're building transfer matrices out of simpler transfer matrices. The 2x2-matrix you had to diagonalize in the 1D-case thus becomes much worse. Finally, the ferromagnetic case (assuming they mean the isotropic one) isn't solved, as far as I'm aware. It should be slightly easier, but I can't judge how intractable the problem is. – Gerben Apr 30 '11 at 20:42
  • Sorry, it wasn't one of the PDFs you mentioned. It was http://physics.neiu.edu/~papiewski/ising.pdf page 10. – Marton Trencseni May 01 '11 at 16:40
  • @mtrencseni: do you want me to go into details on that particular derivation, or is everything clear to you? – Gerben May 02 '11 at 15:47
  • It's perfectly clear, the question is, from my original comment, "What's a good intuitive way to connect this to NP-completeness?", where [this] means being or not being able to perform such a trick on the partition function. – Marton Trencseni May 02 '11 at 19:45
  • 8
    This answer is incomplete-- the result you mention is simply noting that the configurations of 3d Ising model are hard to compute for a general configuration of external spatially varying magnetic field. This doesn't make the two point correlation function hard to compute, since the same proof works in 4d or 5d, where the model has trivial exponents. – Ron Maimon Mar 30 '12 at 15:07
10

The 3d Ising model can be "solved" in a certain sense, it can be recast as the problem of a discrete lattice Fermionic string. This method is explained in detail in the last chapter of Polyakov's "Gauge Fields and Strings", and it is the natural generalization of Onsager's method to 3d.

This method does not produce analytical computable critical exponents in 3d as yet, but not because the 3d model is intractable. The proofs that you have intractability in calculating the free energy for an arbitrary sublattice of the 3d model is interesting, but it also works in 5d or 6d, where the critical exponents are mean field, and so exactly computable. This proof only shows that the general solution, in the sense of computing all correlation functions in the presence of arbitrary external fields, is going to be difficult. But it does not mean that the 2 point function is uncomputable in the long-distance limit.

The only precise meaning I can see to the statement that a statistical model is solvable is saying that the computation of the correlation functions can be reduced in complexity from doing a full Monte-Carlo simulation. In this regard, knowing that the configurations of the 3d model are described by Polyakov lattice Fermionic strings does help, because you can simulate noninteracting strings enclosing volumes instead of spins on each site. The issue is that the strings are Fermionic, so it might not be possible to actually simulate a typical configuration using Polyakov's transformation any more simply than the usual way, because of the Fermion sign problem.

This is all investigated by Polyakov from time to time, and there is still a reasonable hope for a new idea which will lead to progress, the computational intractability results nonwithstanding.

Ron Maimon
  • 1
  • 1
    Onsager's solution for the 2D Ising model (like solutions to integrable problems in general) does much more than calculate the critical exponents. – Arnold Neumaier Mar 30 '12 at 07:56
  • 1
    @ArnoldNeumaier: Polyakov's quasi-solution also solves everything--- it's an exact reformulation in terms of a superficially different problem of free fermionic world-sheets, and it should allow any not-too-complicated quantity to be computable by world-sheet summing methods. The only problem is that these have a sign problem, so they don't Monte-Carlo sum, but they might have a continuum path-integral limit which can be related to a real world-sheet sum which we can do analytically. – Ron Maimon Mar 30 '12 at 15:33
1

Exaxt solvability has nothing to do with NP-completeness.

For equations on a lattice or a continuum, exact solvability happens to be equivalent with having enough symmetries to allow the solution to be determined by exploiting these. (To a large extent, this even holds for ordinary differential equations in more than a few variables.)

The reason that a few (classical or quantum) systems are integrable therefore comes from the fact that they have a much larger (infinite-dimensional) symmetry group, and hence infinitely many conservation laws, while a typical system has only a small, low-dimensional symmetry group. This is the (modern) explanation why Onsager's solution works, while there is no analogous solution in the next dimension.

If one looks at lists of integrable systems (e.g., the one at http://en.wikipedia.org/wiki/Integrable_system#Exactly_solvable_models which for the classical case seems fairly complete) one sees that they get very scarce in higher dimensions. There are just not enough possible large symmetry groups around....

Arnold Neumaier
  • 44,880
  • 2
    This is not a good answer either. There is a good 3d simplification of the Ising model into a model of noninteracting lattice strings, due to Polyakov. – Ron Maimon Mar 30 '12 at 07:25
  • In general, a simplification of the Ising model is not the Ising model. Is the simplification you talk about 9ref please) equivalent to the Ising model? If not, your remark has no bearing on the question. – Arnold Neumaier Mar 30 '12 at 07:38
  • ... on the question, which I take to be about exact solvability. For numerically, all such problems are solvable in some approximation. – Arnold Neumaier Mar 30 '12 at 07:51
  • 1
    The 3d Ising model has an exact lattice reformulation as a Fermionic lattice "world sheet" sum exactly analogous to Onsager's Fermionic lattice world-line sum in 2d. The method is clever, and it is the extension of Onsager to 3d, and it is explained by Polyakov in "Gauge Fields and Strings", and it led to hopes that the continuum limit of the 3d Ising model would have an insightful limit. So far, this hasn't happened, but the formulation itself is a sort-of exact solution in a sense, except it requires a world-sheet numerical sum to evaluate. – Ron Maimon Mar 30 '12 at 15:06
1

Two-dimensional theories simply have much more mathematical structure that makes many such models mathematically solvable - integrable.

In particular, in the long-distance limit, one obtains a scale-invariant theory that is typically conformally invariant as well. Two-dimensional conformal symmetry is - unlikely any higher-dimensional symmetry - infinite-dimensional. This fact plays a very important role in string theory which has 2-dimensional world sheets. In some sense, the 2D systems lead to "infinitely many conserved quantities" which often makes their physics solvable.

Perturbative string theory reflects much of the special mathematics that makes problems tractable in two dimensions. Needless to say, 1D systems may be as solvable as 2D systems or more so. Integrable - analytically solvable - systems have also included spin chains. All these things are parts of string theory in one way or another. On the other hand, problems in three or more dimensions are qualitatively harder and most of the questions about the Ising model in 3D and similar models are not analytically solvable.

Another question is whether one may understand a model qualitatively. Of course, an analytic understanding gives one a superior tool to answer this question as well. When it doesn't, it's still possible to gain some qualitative understanding - numerically or by various approximation schemes - and the fact that as of 2011, it hasn't been done, is just a historical accident that is more likely because it's a difficult problem.

Luboš Motl
  • 179,018
  • 14
    -1 because of three reasons: conformal symmetry is only relevant at critical point while Ising model is integrable (in fact superintegrable) for any temperature. The reason it is integrable has nothing to do with being two-dimensional (there are lots of non-integrable 2d models) and also nothing to do with long-distance limit. Second reason: too much stringy propaganda which is completely irrelevant here (there's just the accidental relation through CFT). Third, last paragraph is completely wrong, 3d Ising model of course is qualitatively understood, both numerically and pertubatively. – Marek Apr 30 '11 at 20:53
  • 2
    @Marek, You are (and at least 2 other deeply misguided people on this server are) wrong about the key point, Marek. All these integrabilities in 1D and 2D are linked to conformal symmetry - they're really extensions of it. This is true outside the scaling limit, too. ... I never claimed that a model wasn't understood qualitatively. What you call "stringy propaganda" is the set of most important insights about these physics questions. If you deny that string theory is the key to shed light on nearly all of these conceptual issues, it doesn't make them any less true, profound, and important. – Luboš Motl May 01 '11 at 10:33
  • 2
    @Luboš: I can't believe how you can make such ridiculous claims. Once again, whether the model is integrable has nothing to do with conformal symmetry. These are completely independent statements. They can (and in important cases do) occur together but this certainly doesn't imply any consequence one way or the other. Additionaly, that string theory sheds some light on these models is very misguided view as well. You don't need string theory to solve (or indeed work on) 2d lattice models. Feel free to provide references for such an illuminating application of string theory to lattice models ;) – Marek May 01 '11 at 11:06
  • 1
    Dear @Marek, you have no clue what you're talking about. Non-conformal versions of theories such as the Ising model, when they're integrable, may be shown to be integrable by their being deformations of the conformal theories whose integrability is guaranteed by the conformal symmetry, and the integrability survives after the deformation. See e.g. http://arxiv.org/abs/hep-th/9312169 and especially its reference 1 by Zamoldchikov and hundreds of other papers about similar issues e.g. http://scholar.google.com/scholar?q=integrable+away-from-criticality+conformal&hl=en&lr=&btnG=Search – Luboš Motl May 16 '11 at 06:38
  • 1
    One may work on something without knowing some essential insights about those matters that were found in the last 25 years but that doesn't mean that his work may be a world quality work as of 2011. It can't. – Luboš Motl May 16 '11 at 06:39
  • 2
    @Luboš: unfortunately it's you who doesn't know what he's talking about :) Zamolodchikov's construction was an ad-hoc deformation of conformal field theory to obtain an E8 Toda theory (which he didn't know at the time, of course) but it's still not settled whether this is the only possible deformation, or indeed whether the complete theory is a deformation at all. The observed $m_2/m_1$ ratio certainly doesn't exclude other theories. – Marek May 16 '11 at 09:40
  • 3
    @Luboš: by the way, where is that paper about string theory you promised us? Neither conformal theory, nor its deformations are string theory. I hope you do not wish to claim that just because some theory is found also in string theory, it's only because of string theory we have it... Although there is relation to string theory, surely work of Zamolodchikov, Cardy and others followed rather mundane goals of understanding this particular field theory and its applications to condensed matter and statistical physics systems. – Marek May 16 '11 at 09:47
  • 7
    @LubošMotl: didn't downvote, but Marek is right, I don't see any connection between relativistic style 2d conformal symmetry and integrability in the sense of Bethe-Ansatz, Lax pairs, or Yang-Baxter relations. There are models like the nonlinear Schrodinger equation which are not relativistically conformal in any limit, nor deformations of such, but are Bethe-Ansatz and Lax-pair integrable, there are infinitely many such examples because Lax-pair is so general. Also integrable Potts models in Yang-Baxter sense only link up to 2d CFT's, only if you have a unitary 2nd order phase transition. – Ron Maimon Mar 30 '12 at 15:39
-5

I solved the Ising model:

I. A. Stepanov. Exact Solutions of the One-Dimensional, Two-Dimensional, and Three-Dimensional Ising Models. – Nano Science and Nano Technology: An Indian Journal. 2012. Vol. 6. No 3. 118 - 122. (The paper is on the Journal site with a free access)

Igor Stepanov
  • 1
  • 1
    Please write your answer of the 3D magnetization, transition temperature or partition function, etc. here, otherwise, it is not helpful. – unsym Jan 20 '13 at 23:03
  • The magnetization is given by Eq. (32), partition function is given by Eq. (30), and there is no transition temperature – it possesses magnetization at all temperatures. There is a misprint in Eq. (32): all J must be multiplied by beta = 1/kT. – Igor Stepanov Jan 20 '13 at 23:23
  • It is not for inifite system – unsym Jan 21 '13 at 01:09
  • It is for infinitive ones - read attentively. – Igor Stepanov Feb 02 '13 at 23:23