The replica symmetric solution for Potts models on d-regular graphs

Amir Dembo, Andrea Montanari, Allan Sly, Nike SunarXiv 2012 · DOI · arXiv

Abstract

In the study of statistical mechanics on sparse networks, the Bethe approximation provides a powerful heuristic for calculating the free energy of a system. However, rigorously establishing its validity for the Potts model—a generalization of the Ising model—has remained a significant challenge. This paper provides an explicit formula for the limiting free energy density of ferromagnetic Potts models on graph sequences that converge locally to $d$-regular trees. By demonstrating that the free energy coincides with the replica symmetric solution derived from Belief Propagation fixed points, the authors settle long-standing questions regarding the variational principle in these systems.

Introduction

Calculating the free energy density—defined as the log-partition function normalized by the number of vertices—is a central objective in statistical mechanics. For systems with complex interactions, this calculation is often intractable. Physicists frequently turn to the Bethe approximation, which assumes that the underlying graph structure is locally tree-like. While this approximation is well-validated for the Ising model (where spins are binary), the Potts model (where spins can occupy $q > 2$ states) introduces complexities such as multiple stable states and potential replica symmetry breaking (RSB).

This research addresses whether the standard Bethe formula correctly predicts the limiting free energy for ferromagnetic Potts models on $d$-regular graphs across all temperature regimes, particularly when multiple fixed points exist in the underlying message-passing equations.

Mathematical Context: The Potts Model and Bethe Functional

The Potts model describes a system of interacting spins where each vertex in a graph can take one of $q$ possible values. In the ferromagnetic regime, neighboring vertices are encouraged to share the same state. As the number of vertices $n$ tends to infinity, the goal is to determine the limit of the free energy density.

The Bethe prediction suggests that this limit can be found by evaluating a specific functional—the Bethe free energy—at the fixed points of the Belief Propagation (BP) equations. In the "replica symmetric" (RS) framework, it is assumed that the local tree-like structure of the graph is sufficient to describe the global state, avoiding the fragmentation into unrelated states seen in spin glasses.

Methodological Approach

The authors utilize several sophisticated mathematical tools to bridge the gap between local structure and global energy:

  • Local Weak Convergence: The study focuses on graph sequences that "look like" an infinite $d$-regular tree ($T_d$) in any finite neighborhood, even if the global structure contains large loops.
  • Random-Cluster (FK) Representation: By mapping the Potts model onto a bond-percolation model (the Fortuin-Kasteleyn representation), the authors analyze the system's phase transitions. This tool is crucial for proving that the global maximum of the free energy functional is achieved at specific, stable BP fixed points.
  • Operation R (Recursive Decomposition): To establish a rigorous upper bound for the free energy on random $d$-regular graphs, the authors introduce "Operation R." This randomized operation modifies a $d$-regular graph while preserving its local tree-like properties, allowing for a recursive analysis of the partition function.

Main Results

The paper provides three primary contributions to the field:

1. Convergence to the Bethe Prediction

The central result (Theorem 3) states that for any sequence of graphs converging locally to a $d$-regular tree (where $d$ is even), the free energy density of the ferromagnetic Potts model converges exactly to the Bethe prediction. This holds for all temperatures and external magnetic fields, confirming that the replica symmetric solution is exact in this regime.

2. Universal Upper Bound

For uniformly random $d$-regular graphs, the authors show that the replica symmetric Bethe formula serves as a rigorous upper bound for the asymptotic free energy. Notably, this result extends beyond the Potts model to any model with "permissive" interactions, providing a broad tool for future research.

3. Classification of Stationary Points

The research provides a complete classification of the stationary points of the Potts-Bethe functional. By identifying which fixed points act as local or global maximizers, the authors clarify the variational principle that governs the system's macroscopic behavior.

Discussion and Limitations

While this work provides a rigorous foundation for the replica symmetric solution, several avenues for future research remain:

  • The Parity of $d$: The proof for general graph sequences currently requires $d$ to be even to facilitate specific graph decompositions where edges are paired perfectly. Extending these results to odd $d$ remains a technical challenge.
  • Anti-ferromagnetic Models: In anti-ferromagnetic systems, where neighbors prefer different states, global properties (such as bipartiteness) significantly influence the free energy. Consequently, local tree-like convergence is insufficient to determine the limit.
  • Replica Symmetry Breaking: The current study focuses on the ferromagnetic regime where replica symmetry holds. Investigating regimes where RSB occurs—such as in spin glasses or the Potts model with very large $q$—remains a major frontier in mathematical physics.

Conclusion

By rigorously proving the validity of the Bethe prediction for ferromagnetic Potts models on $d$-regular graphs, this paper bridges the gap between heuristic physics predictions and mathematical certainty. The results confirm that for these systems, the complex global free energy is indeed governed by the local, tree-like interactions described by Belief Propagation.

Summary updated

Abstract

We provide an explicit formula for the limiting free energy density (log-partition function divided by the number of vertices) for ferromagnetic Potts models on uniformly sparse graph sequences converging locally to the d-regular tree for d even, covering all temperature regimes. This formula coincides with the Bethe free energy functional evaluated at a suitable fixed point of the belief propagation recursion on the d-regular tree, the so-called replica symmetric solution. For uniformly random d-regular graphs we further show that the replica symmetric Bethe formula is an upper bound for the asymptotic free energy for any model with permissive interactions.
BibTeX
@misc{dembo2012replica,
  author = {Amir Dembo and Andrea Montanari and Allan Sly and Nike Sun},
  title = {{The replica symmetric solution for Potts models on d-regular graphs}},
  year = {2012},
  eprint = {1207.5500},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1207.5500},
}
Figure