The Ising partition function: zeros and deterministic approximation. (English) Zbl 1412.82012
Summary: We study the problem of approximating the partition function of the ferromagnetic Ising model with both pairwise as well as higher order interactions (equivalently, in graphs as well as hypergraphs). Our approach is based on the classical Lee-Yang theory of phase transitions, along with a new Lee-Yang theorem for the Ising model with higher order interactions, and on an extension of ideas developed recently by Barvinok, and Patel and Regts that can be seen as an algorithmic realization of the Lee-Yang theory. Our first result is a deterministic polynomial time approximation scheme (an FPTAS) for the partition function in bounded degree graphs that is valid over the entire range of parameters \(\beta \) (the interaction) and \(\lambda \) (the external field), except for the case \(\left| \lambda \right| =1\) (the “zero-field” case). A polynomial time randomized approximation scheme (FPRAS) for all graphs and all \(\beta,\lambda \), based on Markov chain Monte Carlo simulation, 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, but, as pointed out above, on Lee-Yang theory. This 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 latter 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.
MSC:
| 82B20 | Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics |
| 82D40 | Statistical mechanics of magnetic materials |
| 82B26 | Phase transitions (general) in equilibrium statistical mechanics |
| 82B80 | Numerical methods in equilibrium statistical mechanics (MSC2010) |
| 65C05 | Monte Carlo methods |
| 65C40 | Numerical analysis or methods applied to Markov chains |
| 05C65 | Hypergraphs |
References:
| [1] | Anari, N., Gharan, S.O.: The Kadison-Singer problem for strongly Rayleigh measures and applications to Asymmetric TSP. In: Proceedings of the 56th IEEE Symposium on Foundations of Computer Science (FOCS) (2015) |
| [2] | Anari, N., Gharan, S.O.: A generalization of permanent inequalities and applications in counting and optimization. In: Proceedings of the 49th ACM Symposium on Theory and Computation (STOC), pp. 384-396. arXiv:1702.02937 (2017) · Zbl 1370.26031 |
| [3] | Asano, T.: Lee-Yang theorem and the Griffiths inequality for the anisotropic Heisenberg ferromagnet. Phys. Rev. Let. 24(25), 1409-1411 (1970). https://doi.org/10.1103/PhysRevLett.24.1409 · doi:10.1103/PhysRevLett.24.1409 |
| [4] | Barata, J.C.A., Goldbaum, P.S.: On the distribution and gap structure of Lee-Yang zeros for the Ising model: periodic and aperiodic couplings. J. Stat. Phys. 103(5-6), 857-891 (2001). https://doi.org/10.1023/A:1010332500031 · Zbl 0989.82015 · doi:10.1023/A:1010332500031 |
| [5] | Barata, J.C.A., Marchetti, D.H.U.: Griffiths’ singularities in diluted Ising models on the Cayley tree. J. Stat. Phys. 88(1-2), 231-268 (1997). https://doi.org/10.1007/BF02508471 · Zbl 0945.82510 · doi:10.1007/BF02508471 |
| [6] | Barvinok, A.: Computing the partition function for cliques in a graph. Theory Comput. 11(13), 339-355 (2015) · Zbl 1351.05212 |
| [7] | Barvinok, A.: Computing the permanent of (some) complex matrices. Found. Comput. Math. 16(2), 329-342 (2015). https://doi.org/10.1007/s10208-014-9243-7 · Zbl 1347.65082 · doi:10.1007/s10208-014-9243-7 |
| [8] | Barvinok, A.: Combinatorics and Complexity of Partition Functions. Springer, New York (2016) · Zbl 1367.05002 |
| [9] | Barvinok, A., Soberón, P.: Computing the partition function for graph homomorphisms with multiplicities. J. Combin. Theory Ser. A 137, 1-26 (2016) · Zbl 1325.05114 |
| [10] | Barvinok, A., Soberón, P.: Computing the partition function for graph homomorphisms. Combinatorica 37(4), 633-650 (2017) · Zbl 1399.05209 |
| [11] | Berger, N., Kenyon, C., Mossel, E., Peres, Y.: Glauber dynamics on trees and hyperbolic graphs. Probab. Theory Relat. Fields 131(3), 311-340 (2005). https://doi.org/10.1007/s00440-004-0369-4 · Zbl 1075.60003 · doi:10.1007/s00440-004-0369-4 |
| [12] | Borcea, J., Brändén, P.: The Lee-Yang and Pólya-Schur programs. I. Linear operators preserving stability. Invent. Math. 177(3), 541-569 (2009) · Zbl 1175.47032 |
| [13] | Borcea, J., Brändén, P.: The Lee-Yang and Pólya-Schur programs. II. Theory of stable polynomials and applications. Commun. Pure Appl. Math. 62(12), 1595-1631 (2009) · Zbl 1177.47041 |
| [14] | Borcea, J., Brändén, P., Liggett, T.: Negative dependence and the geometry of polynomials. J. AMS 22(2), 521-567 (2009) · Zbl 1206.62096 |
| [15] | Borgs, C., Chayes, J., Kahn, J., Lovász, L.: Left and right convergence of graphs with bounded degree. Random Struct. Algorithms 42(1), 1-28 (2013). https://doi.org/10.1002/rsa.20414 · Zbl 1257.05172 · doi:10.1002/rsa.20414 |
| [16] | Cai, J.Y., Chen, X., Lu, P.: Graph homomorphisms with complex values: a dichotomy theorem. In: Proceedings of the ICALP, Lecture Notes in Computer Science, vol. 6198, pp. 275-286. Springer. http://www.springerlink.com/content/46275700132p5250/abstract/ (2010) · Zbl 1288.05178 |
| [17] | Csikvári, P., Frenkel, P.E.: Benjamini-Schramm continuity of root moments of graph polynomials. Eur. J. Combin. 52, 302-320 (2016) · Zbl 1327.05159 |
| [18] | Efthymiou, C., Hayes, T.P., Štefankovic, D., Vigoda, E., Yin, Y.: Convergence of MCMC and loopy BP in the tree uniqueness region for the hard-core model. In: Proceedings of the 57th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 704-713 (2016) · Zbl 1422.68272 |
| [19] | Galanis, A., Goldberg, L.A.: The complexity of approximately counting in 2-spin systems on \[k\] k-uniform bounded-degree hypergraphs. Inf. Comput. 251, 36-66 (2016). https://doi.org/10.1016/j.ic.2016.07.003. http://www.sciencedirect.com/science/article/pii/S0890540116300426 · Zbl 1353.68128 |
| [20] | Galanis, A., Ge, Q., Štefankovič, D., Vigoda, E., Yang, L.: Improved inapproximability results for counting independent sets in the hard-core model. Random Struct. Algorithms 45(1), 78-110 (2014). https://doi.org/10.1002/rsa.20479 · Zbl 1297.05177 · doi:10.1002/rsa.20479 |
| [21] | Goldberg, L.A., Jerrum, M.: Inapproximability of the Tutte polynomial. Inf. Comput. 206(7), 908-929 (2008). https://doi.org/10.1016/j.ic.2008.04.003. http://www.sciencedirect.com/science/article/pii/S089054010800031X · Zbl 1153.68039 |
| [22] | Goldberg, L.A., Grohe, M., Jerrum, M., Thurley, M.: A complexity dichotomy for partition functions with mixed signs. SIAM J. Comput. 39(7), 3336-3402 (2010). https://doi.org/10.1137/090757496 · Zbl 1298.68099 · doi:10.1137/090757496 |
| [23] | Goldberg, L.A., Jerrum, M., Paterson, M.: The computational complexity of two-state spin systems. Random Struct. Algorithms 23(2), 133-154 (2003) · Zbl 1030.82001 |
| [24] | Guo, H., Jerrum, M.: Random cluster dynamics for the Ising model is rapidly mixing. In: Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1818-1827 (2017) · Zbl 1419.82013 |
| [25] | Guo, H., Lu, P.: Uniqueness, spatial mixing, and approximation for ferromagnetic 2-spin systems. In: Proceedings of the APPROX/RANDOM (2016) · Zbl 1398.68241 |
| [26] | Ising, E.: Beitrag zur Theorie des Ferromagnetismus. Z. Phys. 31, 253-258 (1925). https://doi.org/10.1007/BF02980577 · Zbl 1439.82056 · doi:10.1007/BF02980577 |
| [27] | Jerrum, M., Sinclair, A.: Approximating the permanent. SIAM J. Comput. 18(6), 1149-1178 (1989). https://doi.org/10.1137/0218077 · Zbl 0723.05107 · doi:10.1137/0218077 |
| [28] | Jerrum, M., Sinclair, A.: Polynomial-time approximation algorithms for the Ising model. SIAM J. Comput. 22(5), 1087-1116 (1993) · Zbl 0782.05076 |
| [29] | Jerrum, M., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution. Theor. Comput. Sci. 43, 169-188 (1986) · Zbl 0597.68056 |
| [30] | Lee, T.D., Yang, C.N.: Statistical theory of equations of state and phase transitions. II. Lattice gas and Ising model. Phys. Rev. 87(3), 410-419 (1952). https://doi.org/10.1103/PhysRev.87.410 · Zbl 0048.43401 · doi:10.1103/PhysRev.87.410 |
| [31] | Li, L., Lu, P., Yin, Y.: Correlation decay up to uniqueness in spin systems. In: Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 67-84 (2013) · Zbl 1422.68302 |
| [32] | Long, Y., Nachmias, A., Ning, W., Peres, Y.: A power law of order 1/4 for critical mean-field Swendsen-Wang dynamics. AMS MEMO/232/1092 (2014) · Zbl 1304.60078 |
| [33] | Lu, P., Yang, K., Zhang, C.: FPTAS for hardcore and Ising models on hypergraphs. In: Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS), pp. 51:1-51:14 (2016) · Zbl 1388.68309 |
| [34] | Lubetzky, E., Sly, A.: Critical Ising on the square lattice mixes in polynomial time. Commun. Math. Phys. 313(3), 815-836 (2012). https://doi.org/10.1007/s00220-012-1460-9 · Zbl 1250.82008 · doi:10.1007/s00220-012-1460-9 |
| [35] | Luby, M., Vigoda, E.: Approximately counting up to four. In: Proceedings of the 29th ACM Symposium on Theory of Computing, pp. 682-687. https://doi.org/10.1145/258533.258663 (1997) · Zbl 0963.68150 |
| [36] | Marcus, A., Spielman, D., Srivastava, N.: Interlacing families I: Bipartite Ramanujan graphs of all degrees. Ann. Math. (2015) https://doi.org/10.4007/annals.2015.182.1.7. http://annals.math.princeton.edu/2015/182-1/p07 · Zbl 1316.05066 |
| [37] | Marcus, A.W., Spielman, D.A., Srivastava, N.: Interlacing families II: Mixed characteristic polynomials and the Kadison-Singer problem. Ann. Math. 182, 327-350 (2015) · Zbl 1332.46056 |
| [38] | Martinelli, F., Olivieri, E.: Approach to equilibrium of Glauber dynamics in the one phase region. I. The attractive case. Commun. Math. Phys. 161(3), 447-486 (1994) · Zbl 0793.60110 |
| [39] | Martinelli, F., Olivieri, E.: Approach to equilibrium of Glauber dynamics in the one phase region: II. The general case. Commun. Math. Phys. 161, 487-514 (1994) · Zbl 0793.60111 |
| [40] | Martinelli, F., Sinclair, A., Weitz, D.: Glauber dynamics on trees: Boundary conditions and mixing time. Commun. Math. Phys. 250(2), 301-334 (2004). https://doi.org/10.1007/s00220-004-1147-y · Zbl 1076.82010 · doi:10.1007/s00220-004-1147-y |
| [41] | Mossel, E., Sly, A.: Exact thresholds for Ising-Gibbs samplers on general graphs. Ann. Probab. 41(1), 294-328 (2013) · Zbl 1270.60113 |
| [42] | Patel, V., Regts, G.: Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials. SIAM J. Comput. 46(6), 1893-1919 (2017). arXiv:1607.01167 · Zbl 1383.68099 |
| [43] | Randall, D., Wilson, D.: Sampling spin configurations of an Ising system. In: Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 959-960 (1999) · Zbl 1052.82525 |
| [44] | Ruelle, D.: Characterization of Lee-Yang polynomials. Ann. Math. 171(1), 589-603 (2010). https://doi.org/10.4007/annals.2010.171.589. http://annals.math.princeton.edu/2010/171-1/p16 · Zbl 1251.30005 |
| [45] | Scott, A., Sokal, A.: The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma. J. Stat. Phys. 118(5-6), 1151-1261 (2004) · Zbl 1107.82013 |
| [46] | Shearer, J.B.: On a problem of Spencer. Combinatorica 5(3), 241-245 (1985) · Zbl 0587.60012 |
| [47] | Sinclair, A., Srivastava, P.: Lee-Yang theorems and the complexity of computing averages. Commun. Math. Phys. 329(3), 827-858 (2014) · Zbl 1294.82009 |
| [48] | Sinclair, A., Srivastava, P., Thurley, M.: Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs. J. Stat. Phys. 155(4), 666-686 (2014) · Zbl 1297.82009 |
| [49] | Sinclair, A., Srivastava, P., Štefankovič, D., Yin, Y.: Spatial mixing and the connective constant: optimal bounds. Probab. Theory Relat. Fields 168, 153-197 (2016) · Zbl 1373.82026 |
| [50] | Sly, A., Sun, N.: Counting in two-spin models on \[d\] d-regular graphs. Ann. Probab. 42(6), 2383-2416 (2014). https://doi.org/10.1214/13-AOP888. http://projecteuclid.org/euclid.aop/1412083628 · Zbl 1311.60117 |
| [51] | Song, R., Yin, Y., Zhao, J.: Counting hypergraph matchings up to uniqueness threshold. In: Proceedings of the APPROX/RANDOM, pp. 46:1-46:29 (2016) · Zbl 1398.05113 |
| [52] | Stanley, R., Fomin, S.: Enumerative Combinatorics. Cambridge University Press, Cambridge (1999) · Zbl 0928.05001 |
| [53] | Straszak, D., Vishnoi, N.K.: Real stable polynomials and matroids: optimization and counting. In: Proceedings of the 49th ACM Symposium on Theory of Computing (STOC), pp. 370-383. arXiv:1611.04548 (2017) · Zbl 1370.90180 |
| [54] | Suzuki, M., Fisher, M.E.: Zeros of the partition function for the Heisenberg, Ferroelectric, and general Ising models. J. Math. Phys. 12(2), 235-246 (1971). https://doi.org/10.1063/1.1665583. http://scitation.aip.org/content/aip/journal/jmp/12/2/10.1063/1.1665583;jsessionid=tsaFQsrLOe4npdBWQR-8iADE.x-aip-live-06 |
| [55] | Weitz, D.: Counting independent sets up to the tree threshold. In: Proceedings of the 38th ACM Symposium on Theory of Computing (STOC), pp. 140-149 (2006) · Zbl 1301.68276 |
| [56] | Yang, C.N., Lee, T.D.: Statistical theory of equations of state and phase transitions. I. Theory of condensation. Phys. Rev. 87(3), 404-409 (1952). https://doi.org/10.1103/PhysRev.87.404 · Zbl 0048.43305 · doi:10.1103/PhysRev.87.404 |
| [57] | Zhang, J., Liang, H., Bai, F.: Approximating partition functions of the two-state spin system. Inf. Process. Lett. 111(14), 702-710 (2011). https://doi.org/10.1016/j.ipl.2011.04.012 · Zbl 1260.68469 · doi:10.1016/j.ipl.2011.04.012 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
