Algorithmic Pirogov–Sinai theory at the phase boundary: efficient counting and sampling in the phase-coexistence regime for lattice models

Helmuth, Perkins and Regts combined Pirogov–Sinai contour representations with Barvinok's interpolation method to build the first deterministic fully polynomial-time approximation schemes (FPTAS) and efficient samplers for the ferromagnetic Potts and hard-core models on regions of $\mathbb{Z}^d$ and on tori, valid at sufficiently low temperature or high fugacity, and stated a concrete list of open problems marking the limits of the method: pushing the hard-core fugacity threshold to $\lambda_{\mathrm{coex}}(d)=\tilde{\Theta}(d^{-1/3})$ and to the proven coexistence region $\lambda>5.3506$ on the $\mathbb{Z}^2$ torus, obtaining genuine torus FPTAS for exponentially small tolerances, proving that ground-state-seeded Glauber dynamics mixes rapidly, finding algorithms for the hard-hexagon (triangular-lattice) model at all non-critical fugacities, and handling ground-state collections such as proper $q$-colorings. Later work resolved sub-ranges of these targets — Borgs–Chayes–Helmuth–Perkins–Tetali gave efficient sampling and an FPRAS for Potts on $\mathbb{Z}^d$ tori at all temperatures for large $q$, de Boer–Buys–Peters–Regts gave a genuine FPTAS for the hard-core model on balanced tori at large $|\lambda|$, and Cannon–Helmuth–Perkins extended Pirogov–Sinai theory beyond $\mathbb{Z}^d$ to bipartite graphs — but the central open core survives: whether efficient approximate counting and sampling exist throughout the coexistence regime down to the physical phase boundaries, in particular for the hard-hexagon model above its exactly known critical fugacity. The stated problems remain open in their surviving generality.

Background

Two families of lattice models drive the question. The hard-core model at fugacity $\lambda>0$ on a finite graph $G=(V,E)$ is the probability distribution on independent sets $I$ (vertex sets with no edge inside) with $\mu(I)\propto\lambda^{|I|}$; its normalizing constant $Z_G(\lambda)=\sum_I\lambda^{|I|}$ is the independence polynomial, the object to be approximated. The ferromagnetic $q$-state Potts model at inverse temperature $\beta\ge0$ puts mass $\mu(\sigma)\propto e^{-\beta H(\sigma)}$ on colorings $\sigma$ of the vertices, where $H(\sigma)$ counts edges with differing endpoint colors; large $\beta$ favors monochromatic configurations. We take $G$ to be a finite region of the cubic lattice $\mathbb{Z}^d$ with suitable boundary conditions, or the torus $\mathbb{T}^d_n=(\mathbb{Z}/n\mathbb{Z})^d$.

An FPTAS (fully polynomial-time approximation scheme) is a deterministic algorithm that outputs an $\varepsilon$-relative-error estimate of $Z$ in time polynomial in the instance size $n$ and $1/\varepsilon$; an FPRAS is its randomized analogue, and an efficient sampler outputs a draw within total variation distance $\varepsilon$ of $\mu$ in such time. Glauber dynamics is the single-site heat-bath Markov chain for $\mu$ (at each step, a uniformly random vertex is resampled from its conditional distribution given its neighbors); it is known to mix exponentially slowly at low temperature from worst-case starts, because the chain must tunnel between competing ordered phases.

In the uniqueness regime (weak correlations) these computational tasks are classical: Weitz's correlation-decay algorithm gives an FPTAS on all graphs of maximum degree $\Delta$ for $\lambda<\lambda_c(T_\Delta)=(\Delta-1)^{\Delta-1}/(\Delta-2)^{\Delta-2}$, the threshold for weak mixing on the infinite $\Delta$-regular tree. The hard regime is the phase-coexistence (non-uniqueness) regime: several infinite-volume Gibbs states coexist. For the hard-core model on $\mathbb{Z}^d$, coexistence of an even-rich and an odd-rich phase is proven for $\lambda\ge C\,\log^2 d/d^{1/3}$ (Galvin–Kahn; Peled–Samotij), and for $\lambda>5.3506$ on $\mathbb{Z}^2$ (Blanca–Chen–Galanis–Randall–Tetali). For the hard-core model on the triangular lattice — Baxter's exactly solved hard-hexagon model, with critical fugacity $\lambda_c=(11+5\sqrt5)/2\approx11.09$ — the free energy is analytic for every real $\lambda\neq\lambda_c$.

Pirogov–Sinai (PS) theory is the classical machinery for the coexistence regime: configurations are organized as a ground state (a periodic maximizer, e.g. one monochromatic phase of the Potts model or one parity class of $\mathbb{Z}^d$ for the hard-core model) plus contours, the boundaries of connected regions deviating from it; a Peierls-type condition makes long contours exponentially costly, and a convergent cluster expansion (in the Kotecký–Preiss sense) then controls the partition function and the phase diagram. Helmuth, Perkins and Regts (PTRF 176, 2019) made PS theory algorithmic: truncating the cluster expansion and combining it with Barvinok's interpolation method, they gave, for all $d\ge2$, an FPTAS and efficient sampler for the hard-core model at all fugacities $\lambda>\lambda^\star(d)$ on regions of $\mathbb{Z}^d$ with parity boundary conditions (Theorem 1.4), and — on even tori, for all error tolerances $\varepsilon\ge e^{-cn}$ — counting and sampling algorithms for both models at sufficiently low temperature / high fugacity, running in time $(n/\varepsilon)^{O(\log d)}$ (Theorems 1.2–1.5). The restriction $\varepsilon\ge e^{-cn}$ on the torus arises because contributions from winding contours — contours that wrap around a periodic direction of the torus and so cannot be shrunk away — can only be shown exponentially (not super-exponentially) small. Helmuth–Perkins–Regts sketch (Section 7.2) that the Borgs–Chayes–Tetali bound of order $\exp(-\Theta(n^{d-1}))$ on interfaces of non-zero winding number, together with Glauber dynamics at the smallest tolerances, can yield a genuine torus FPTAS, and note that the topological details are left for future work; Borgs–Chayes–Helmuth–Perkins–Tetali later list a deterministic torus FPTAS for exponentially small tolerances as an explicit open problem (item 2 of their Section 7). Their concluding Section 7 formulates the open problems that define this record: the parameter thresholds $\beta^\star(d,q)$ and $\lambda^\star(d)$ are far from the physical phase boundaries, the torus algorithm is not a genuine FPTAS, Markov-chain alternatives are unproven, and whole model classes (the non-bipartite triangular lattice; models whose ground states form collections, such as proper $q$-colorings) lie outside the contour formalism. The complexity class #BIS (counting independent sets on bipartite graphs), believed of intermediate difficulty, motivates the bipartite-graph direction.

Problem Statement

Resolve the open problems raised in Section 7 of Helmuth–Perkins–Regts's algorithmic Pirogov–Sinai theory, together with the open problems listed in Section 7 of Borgs–Chayes–Helmuth–Perkins–Tetali that extend them, understood as one question: does phase coexistence in the canonical lattice models form an algorithmic barrier to approximate counting and sampling at the physical phase boundaries? Each of the six settings below is an independent open problem that can be settled on its own, but the question as a whole is resolved only when all six are settled; settling a proper subset is a partial resolution. The common objective is to determine, for each of the following settings, whether an efficient algorithm exists — and to settle it constructively (an FPTAS/FPRAS and an efficient sampler, i.e. time polynomial in the instance size $n$ and $1/\varepsilon$):

(i) Hard-core threshold in high dimension. Extend Theorems 1.4 and 1.5 of the source from all sufficiently large $\lambda$ down to $\lambda_{\mathrm{coex}}(d)=\tilde{\Theta}(d^{-1/3})$, matching the best known probabilistic phase-coexistence bounds (up to polylogarithmic factors) for the hard-core model on $\mathbb{Z}^d$ and its even tori.

(ii) Hard-core coexistence window on the square-lattice torus. Find an FPTAS and an efficient sampling algorithm for the hard-core model on the two-dimensional torus $\mathbb{T}^2_n$ for all fugacities $\lambda>5.3506$, the proven coexistence region on $\mathbb{Z}^2$ — closing the gap between this threshold and the large constant $\Lambda$ currently achievable by zero-freeness methods.

(iii) Genuine torus FPTAS and small-$q$ Potts. Obtain a deterministic FPTAS for the torus partition functions valid for all tolerances $\varepsilon>0$, including exponentially small $\varepsilon=\exp(-\Omega(n^{d-1}))$ — an item left as an explicit open problem (item 2) in Section 7 of Borgs–Chayes–Helmuth–Perkins–Tetali; and, following Section 7 (item 1) of Borgs–Chayes–Helmuth–Perkins–Tetali, extend the all-temperatures ($\beta\ge0$) sampling/counting results for the Potts model on regions of $\mathbb{Z}^d$ and on tori $\mathbb{T}^d_n$ beyond the super-exponential constraint $q\ge q_0(d)$ — in particular to each fixed $q\ge3$, the regime in which the underlying physical phenomena are believed to hold when $d\ge3$.

(iv) Seeded Glauber dynamics. Prove the source's conjecture (Section 7.3 Open Problem) that the following is an efficient sampling algorithm for $q$-state ferromagnetic Potts on $\mathbb{T}^d_n$ below the critical temperature $\beta_c(d,q)$, and for the hard-core model on $\mathbb{T}^d_n$ at sufficiently high fugacity: choose one of the ground states uniformly at random (a monochromatic configuration, respectively the even or odd occupied configuration) and run Glauber dynamics from it; the source's conjectured bound is $O(n\log n)$ steps to within total variation $\varepsilon$, despite exponentially slow mixing from worst-case starts.

(v) Hard hexagon. Find efficient counting and sampling algorithms for the hard-hexagon model (the hard-core model on the triangular lattice) for all real $\lambda\neq\lambda_c$, $\lambda_c=(11+5\sqrt5)/2$; the unresolved core is the ordered (coexistence) phase $\lambda>\lambda_c$, since the uniqueness region is covered by Weitz's correlation-decay FPTAS.

(vi) Colorings. Find an FPTAS and an efficient sampler for proper $q$-colorings of the torus $\mathbb{T}^d_n$ when $d=d(q)$ is sufficiently large.

The problem is fully resolved when each of the targets (i)–(vi) is discharged by a rigorous constructive result at the stated parameter ranges (no weakening of a threshold, e.g. no replacement of $\lambda_{\mathrm{coex}}(d)=\tilde{\Theta}(d^{-1/3})$ by a power of $d$, and no replacement of 'all $\lambda>\lambda_c$' by 'all $\lambda$ above an unspecified large constant'). The related free-energy-approximation direction from the source (Section 7.5) is context, not a target, as the source states no completion boundary for it.

References

1. Tyler Helmuth, Will Perkins, Guus Regts, 'Algorithmic Pirogov–Sinai theory', Probability Theory and Related Fields 176 (2019) 851–895. DOI: 10.1007/s00440-019-00928-y, https://doi.org/10.1007/s00440-019-00928-y (arXiv:1806.11548, https://arxiv.org/abs/1806.11548)
2. Christian Borgs, Jennifer Chayes, Tyler Helmuth, Will Perkins, Prasad Tetali, 'Efficient sampling and counting algorithms for the Potts model on Z^d at all temperatures', Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020), 738–751. DOI: 10.1145/3357713.3384271, https://doi.org/10.1145/3357713.3384271 (arXiv:1909.09298, https://arxiv.org/abs/1909.09298)
3. David de Boer, Pjotr Buys, Han Peters, Guus Regts, 'On boundedness of zeros of the independence polynomial of tori', 2023. arXiv:2306.12934, https://arxiv.org/abs/2306.12934
4. Sarah Cannon, Tyler Helmuth, Will Perkins, 'Pirogov–Sinai theory for the hard-core model beyond lattices', Communications in Mathematical Physics 407 (2026). DOI: 10.1007/s00220-026-05623-3, https://doi.org/10.1007/s00220-026-05623-3 (arXiv:2411.07809, https://arxiv.org/abs/2411.07809)
5. Dror Weitz, 'Counting independent sets up to the tree threshold', Proceedings of the 38th ACM STOC (2006). DOI: 10.1145/1132516.1132538, https://doi.org/10.1145/1132516.1132538
6. R. J. Baxter, 'Hard hexagons: exact solution', Journal of Physics A: Mathematical and General 13 (1980) L61–L70. DOI: 10.1088/0305-4470/13/3/007, https://doi.org/10.1088/0305-4470/13/3/007
7. David Galvin, Jeff Kahn, 'On phase transition in the hard-core model on Z^d', Combinatorics, Probability and Computing 13 (2004) 137–164. DOI: 10.1017/S0963548303006035, https://doi.org/10.1017/S0963548303006035
8. Ron Peled, Wojciech Samotij, 'Odd cutsets and the hard-core model on Z^d', Annales de l'Institut Henri Poincaré, Probabilités et Statistiques 50 (2014). DOI: 10.1214/12-AIHP535, https://doi.org/10.1214/12-aihp535
9. Antonio Blanca, Yuxuan Chen, David Galvin, Dana Randall, Prasad Tetali, 'Phase coexistence for the hard-core model on Z^2', Combinatorics, Probability and Computing 28 (2019) 1–22. DOI: 10.1017/S0963548318000238, https://doi.org/10.1017/s0963548318000238
10. Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg, Will Perkins, James Stewart, Eric Vigoda, 'Fast algorithms at low temperatures via Markov chains', Random Structures & Algorithms 58 (2021) 294–321. DOI: 10.1002/rsa.20968, https://doi.org/10.1002/rsa.20968 (arXiv:1901.06653, https://arxiv.org/abs/1901.06653)
11. Jeroen Huijben, Viresh Patel, Guus Regts, 'Sampling from the low temperature Potts model through a Markov chain on flows', Random Structures & Algorithms 62 (2022) 219–239. DOI: 10.1002/rsa.21089, https://doi.org/10.1002/rsa.21089
12. Antonio Blanca, Reza Gheissari, 'Sampling from the Potts model at low temperatures via Swendsen–Wang dynamics', Proceedings of FOCS 2023. DOI: 10.1109/FOCS57990.2023.00122, https://doi.org/10.1109/focs57990.2023.00122
13. Antonio Blanca, Reza Gheissari, Xusheng Zhang, 'Mean-field Potts and random-cluster dynamics from high-entropy initializations', Annals of Applied Probability 36 (2026). DOI: 10.1214/25-AAP2235, https://doi.org/10.1214/25-aap2235
14. Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg, Xandru Mifsud, Paulina Smolarova, Xusheng Zhang, 'Fast mixing for low-temperature Potts models via Poisson trees', 2026. arXiv:2607.29495, https://arxiv.org/abs/2607.29495
15. Ijay Narang, Will Perkins, 'The hard-core model on bipartite spectral expanders: counting and sampling at all fugacities', 2026. arXiv:2608.03848, https://arxiv.org/abs/2608.03848
16. Andreas Galanis, Leslie Ann Goldberg, Paulina Smolarova, 'Low-temperature sampling on sparse random graphs', Electronic Journal of Probability 31 (2026) 1–40. DOI: 10.1214/26-EJP1576, https://doi.org/10.1214/26-ejp1576 (arXiv:2502.08328, https://arxiv.org/abs/2502.08328)
17. Eyal Lubetzky, Fabio Martinelli, Allan Sly, Fabio Lucio Toninelli, 'Quasi-polynomial mixing of the 2D stochastic Ising model with plus boundary up to criticality', Journal of the European Mathematical Society 15 (2013) 339–386. DOI: 10.4171/JEMS/363, https://doi.org/10.4171/jems/363
18. A. Mazel, I. Stuhl, Y. Suhov, 'High-density hard-core model on triangular and hexagonal lattices', Annales Henri Poincaré 26 (2025) 3321–3381. DOI: 10.1007/s00023-025-01567-x, https://doi.org/10.1007/s00023-025-01567-x
19. Qidong He, Ian Jauslin, 'High-fugacity expansion and crystallization in non-sliding hard-core lattice particle models without a tiling constraint', Journal of Statistical Physics 191 (2024). DOI: 10.1007/s10955-024-03349-x, https://doi.org/10.1007/s10955-024-03349-x
20. Qidong He, 'Unified criteria for crystallization in hard-core lattice systems with applications to polyomino fluids and multi-component mixtures', 2026. arXiv:2602.05294, https://arxiv.org/abs/2602.05294
21. Ron Peled, Yinon Spinka, 'Rigidity of proper colorings of Z^d', Inventiones mathematicae 232 (2023) 79–162. DOI: 10.1007/s00222-022-01164-3, https://doi.org/10.1007/s00222-022-01164-3
22. Jingcheng Liu, Alistair Sinclair, Piyush Srivastava, 'A deterministic algorithm for counting colorings with 2Δ colors', Proceedings of FOCS 2019. DOI: 10.1109/FOCS.2019.00085, https://doi.org/10.1109/focs.2019.00085
23. Stefan Adams, Raimundo Briceño, Brian Marcus, Ronnie Pavlov, 'Representation and poly-time approximation for pressure of Z^2 lattice models in the non-uniqueness region', Journal of Statistical Physics 162 (2016) 1031–1067. DOI: 10.1007/s10955-015-1433-4, https://doi.org/10.1007/s10955-015-1433-4
24. Patrick Arras, Felix Joos, 'Independent sets in discrete tori of odd sidelength', SIAM Journal on Discrete Mathematics 39 (2025) 1953–1973. DOI: 10.1137/24M1703288, https://doi.org/10.1137/24m1703288