Document Open Access Logo

Fisher Zeros and Correlation Decay in the Ising Model

Authors Jingcheng Liu, Alistair Sinclair, Piyush Srivastava

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2019.55.pdf
  • Filesize: 410 kB
  • 8 pages

Document Identifiers

Author Details

Jingcheng Liu
  • Computer Science Division, UC Berkeley, USA
Alistair Sinclair
  • Computer Science Division, UC Berkeley, USA
Piyush Srivastava
  • Tata Institute of Fundamental Research, Mumbai, India

Funding

  • Liu, Jingcheng: Supported by US NSF grant CCF-1815328.
  • Sinclair, Alistair: Supported by US NSF grant CCF-1815328.
  • Srivastava, Piyush: Supported by a Ramanujan Fellowship of the Indian Department of Science and Technology.

Cite As Get BibTex

Jingcheng Liu, Alistair Sinclair, and Piyush Srivastava. Fisher Zeros and Correlation Decay in the Ising Model. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 55:1-55:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ITCS.2019.55

Abstract

The Ising model originated in statistical physics as a means of studying phase transitions in magnets, and has been the object of intensive study for almost a century. Combinatorially, it can be viewed as a natural distribution over cuts in a graph, and it has also been widely studied in computer science, especially in the context of approximate counting and sampling. In this paper, we study the complex zeros of the partition function of the Ising model, viewed as a polynomial in the "interaction parameter"; these are known as Fisher zeros in light of their introduction by Fisher in 1965. While the zeros of the partition function as a polynomial in the "field" parameter have been extensively studied since the classical work of Lee and Yang, comparatively little is known about Fisher zeros. Our main result shows that the zero-field Ising model has no Fisher zeros in a complex neighborhood of the entire region of parameters where the model exhibits correlation decay. In addition to shedding light on Fisher zeros themselves, this result also establishes a formal connection between two distinct notions of phase transition for the Ising model: the absence of complex zeros (analyticity of the free energy, or the logarithm of the partition function) and decay of correlations with distance. We also discuss the consequences of our result for efficient deterministic approximation of the partition function. Our proof relies heavily on algorithmic techniques, notably Weitz's self-avoiding walk tree, and as such belongs to a growing body of work that uses algorithmic methods to resolve classical questions in statistical physics.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Discrete mathematics
Keywords
  • Ising model
  • zeros of polynomials
  • partition functions
  • approximate counting
  • phase transitions

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Nima Anari and Shayan Oveis Gharan. The Kadison-Singer problem for strongly Rayleigh measures and applications to Asymmetric TSP. In Proc. 56th IEEE Symp. Found. Comp. Sci. (FOCS), October 2015. Google Scholar
  2. Nima Anari and Shayan Oveis Gharan. A Generalization of Permanent Inequalities and Applications in Counting and Optimization. In Proc. 49th ACM Symp. Theory Comput. (STOC), pages 384-396. ACM, June 2017. URL: https://arxiv.org/abs/1702.02937.
  3. A. Barvinok. Combinatorics and Complexity of Partition Functions. Algorithms and Combinatorics. Springer, 2017. Google Scholar
  4. Alexander Barvinok. Computing the permanent of (some) complex matrices. Found. Comput. Math., 16(2):329-342, 2015. URL: http://dx.doi.org/10.1007/s10208-014-9243-7.
  5. Alexander Barvinok and Pablo Soberón. Computing the partition function for graph homomorphisms with multiplicities. J. Combin. Theory, Ser. A, 137:1-26, 2016. Google Scholar
  6. Alexander Barvinok and Pablo Soberón. Computing the partition function for graph homomorphisms. Combinatorica, 37(4):633-650, August 2017. Google Scholar
  7. Ferenc Bencs and Péter Csikvári. Note on the zero-free region of the hard-core model, July 2018. URL: https://arxiv.org/abs/1807.08963.
  8. M. E. Fisher. The nature of critical points. In W. E. Brittin, editor, Lecture notes in Theoretical Physics, volume 7c, pages 1-159. University of Colorado Press, 1965. Google Scholar
  9. Hans-Otto Georgii. Gibbs Measures and Phase Transitions. De Gruyter Studies in Mathematics. Walter de Gruyter Inc., October 1988. Google Scholar
  10. Nicholas J. A. Harvey, Piyush Srivastava, and Jan Vondrák. Computing the independence polynomial: from the tree threshold down to the roots. In Proc. 29th ACM-SIAM Symp. Discrete Algorithms (SODA), pages 1557-1576, 2018. URL: https://arxiv.org/abs/1608.02282.
  11. E. Ising. Beitrag zur Theorie des Ferromagnetismus. Z. Phys., 31:253-258, February 1925. URL: http://dx.doi.org/10.1007/BF02980577.
  12. T. D. Lee and C. N. Yang. Statistical Theory of Equations of State and Phase Transitions. II. Lattice Gas and Ising Model. Phys. Rev., 87(3):410-419, 1952. URL: http://dx.doi.org/10.1103/PhysRev.87.410.
  13. Liang Li, Pinyan Lu, and Yitong Yin. Correlation Decay up to Uniqueness in Spin Systems. In Proc. 24th ACM-SIAM Symp. Discrete Algorithms (SODA), pages 67-84, 2013. Google Scholar
  14. Jingcheng Liu, Alistair Sinclair, and Piyush Srivastava. The Ising Partition Function: Zeros and Deterministic Approximation. In Proc. 58th Annual IEEE Symp. Found. Comp. Sci. (FOCS), pages 986-997, 2017. URL: https://arxiv.org/abs/1704.06493.
  15. Jingcheng Liu, Alistair Sinclair, and Piyush Srivastava. Fisher zeros and correlation decay in the Ising model, 2018. URL: https://arxiv.org/abs/1807.06577.
  16. Ryan L. Mann and Michael J. Bremner. Approximation algorithms for complex-valued Ising models on bounded degree graphs, June 2018. URL: https://arxiv.org/abs/1806.11282.
  17. Adam Marcus, Daniel Spielman, and Nikhil Srivastava. Interlacing families I: Bipartite Ramanujan graphs of all degrees. Ann. Math., pages 307-325, July 2015. URL: http://dx.doi.org/10.4007/annals.2015.182.1.7.
  18. Adam W Marcus, Daniel A Spielman, and Nikhil Srivastava. Interlacing families II: Mixed characteristic polynomials and the Kadison-Singer problem. Ann. Math., 182:327-350, 2015. Google Scholar
  19. Viresh Patel and Guus Regts. Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials. SIAM J. Comput., 46(6):1893-1919, December 2017. URL: https://arxiv.org/abs/1607.01167.
  20. Han Peters and Guus Regts. On a conjecture of Sokal concerning roots of the independence polynomial, January 2017. URL: https://arxiv.org/abs/1701.08049.
  21. Alex Scott and Alan Sokal. The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma. J. Stat. Phys., 118(5-6):1151-1261, 2004. Google Scholar
  22. James B. Shearer. On a problem of Spencer. Combinatorica, 5(3), 1985. Google Scholar
  23. Barry Simon. The Statistical Mechanics of Lattice Gases, volume 1. Princeton University Press, 1993. Google Scholar
  24. Alistair Sinclair, Piyush Srivastava, and Marc Thurley. Approximation Algorithms for Two-State Anti-Ferromagnetic Spin Systems on Bounded Degree Graphs. J. Stat. Phys., 155(4):666-686, 2014. Google Scholar
  25. Allan Sly and Nike Sun. Counting in two-spin models on d-regular graphs. Ann. Probab., 42(6):2383-2416, November 2014. URL: http://dx.doi.org/10.1214/13-AOP888.
  26. Damian Straszak and Nisheeth K. Vishnoi. Real Stable Polynomials and Matroids: Optimization and Counting. In Proc. 49th ACM Symp. Theory Comput. (STOC), pages 370-383. ACM, June 2017. URL: https://arxiv.org/abs/1611.04548.
  27. Dror Weitz. Counting Independent Sets up to the Tree Threshold. In Proc. 38th ACM Symp. Theory Comput. (STOC), pages 140-149, 2006. Google Scholar
  28. C. N. Yang and T. D. Lee. Statistical Theory of Equations of State and Phase Transitions. I. Theory of Condensation. Phys. Rev., 87(3):404-409, August 1952. URL: http://dx.doi.org/10.1103/PhysRev.87.404.
  29. Jinshan Zhang, Heng Liang, and Fengshan Bai. Approximating partition functions of the two-state spin system. Inf. Process. Lett., 111(14):702-710, 2011. URL: http://dx.doi.org/10.1016/j.ipl.2011.04.012.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact