The Ising Partition Function: Zeros and Deterministic Approximation

We study the problem of approximating the partition function of the ferromagnetic Ising model in graphs and hypergraphs. Our first result is a deterministic approximation scheme (an FPTAS) for the partition function in bounded degree graphs that is valid over the entire range of parameters β (the interaction) and λ (the external field), except for the case |λ| = 1 (the “zero-field” case). A randomized algorithm (FPRAS) for all graphs, and all β, λ, has long been known. Unlike most other deterministic approximation algorithms for problems in statistical physics and counting, our algorithm does not rely on the “decay of correlations” property. Rather, we exploit and extend machinery developed recently by Barvinok, and Patel and Regts, based on the location of the complex zeros of the partition function, which can be seen as an algorithmic realization of the classical Lee-Yang approach to phase transitions. Our approach extends to the more general setting of the Ising model on hypergraphs of bounded degree and edge size, where no previous algorithms (even randomized) were known for a wide range of parameters. In order to achieve this extension, we establish a tight version of the Lee-Yang theorem for the Ising model on hypergraphs, improving a classical result of Suzuki and Fisher.

Authors

• Jingcheng Liu 0001
• Alistair Sinclair
• Piyush Srivastava 0001

Keywords

• Approximation algorithms
• Partitioning algorithms
• Correlation
• Computational modeling
• Taylor series
• Physics
• Electronic mail
• Partition Function
• Deterministic Approximation
• Phase Transition
• Estimation Algorithm
• Ising Model
• Statistical Physics
• Poles And Zeros
• Decay Of Correlations
• Final Results
• Loss Of Generality
• Markov Chain Monte Carlo
• Proof Of Theorem
• Taylor Expansion
• Term In Eq
• Maximum Degree
• Lexicographic
• Unit Circle
• Graph Properties
• Sum Of Power
• Induced Subgraph
• Multigraph
• Extension Of Theorem
• Special Case Of Theorem
• Approximate counting
• Zeros of polynomials
• Stability theory
• Lee-Yang theorem