Rigorous organization of Bethe states and effective evaluation of the Bethe variational formula for spin systems on the Bethe lattice

Coja-Oghlan and Perkins (2019) proved, for a very general class of spin systems on the Bethe lattice (the random d-regular graph) satisfying a convexity condition, that the Gibbs measure decomposes into Bethe states - pure states free of long-range correlations whose marginals satisfy Belief Propagation - and that the free energy density is given exactly by a variational formula: the infimum of a Bethe functional over cavity-invariant distributions on a space of kernels. The physics predictions about the organization of these Bethe states and of the minimizers, however, remain unproven: statistical equivalence of the unboundedly many pure states with weights governed by the one-step replica-symmetry-breaking (1RSB) equations in the 1RSB regime; hierarchical (ultrametric) organization of pure states in the full-RSB regime; identification of which scenario occurs for a given model and parameters; and, on this basis, effective evaluation of the variational formula through explicit minimizers or convergent numerical schemes. Since 2019, rigorous results have been confined to the replica-symmetric regime, to specific models, or to one-sided interpolation bounds; this core remains open, and the full-RSB variational functional for the Bethe-lattice spin glass remains ansatz-level, its equality with the true free energy being explicitly conjectural (refs 11, 12, 13). The problem asks for a rigorous replica-symmetry-breaking structure theory of the Bethe lattice and a computable free energy.

Background

Setting. In the terminology of Mézard and Parisi, the Bethe lattice of degree $d$ is the random $d$-regular graph on $n$ vertices (not the infinite $d$-regular tree): locally it looks like a tree, so each spin interacts with only a bounded number of neighbors, yet globally it is an expansive random graph. A spin system on such a graph is specified by a finite spin set $\Omega$ (for instance $\{+1,-1\}$) and a distribution over weight functions $\psi:\Omega^k\to(0,\infty)$ encoding the interactions; the Gibbs (Boltzmann) distribution $\mu_G$ assigns to a spin configuration a probability proportional to the product of the weights of its local assignments, and the central observable is the free energy density $\lim_{n\to\infty}\frac{1}{n}\mathbb{E}[\log Z(G)]$, whose singularities in the temperature parameter are the phase transitions of the model. This class covers diluted spin glasses (random signed couplings, which cause frustration - some couplings favor alignment of neighboring spins and others oppose it, so not all local preferences can be satisfied simultaneously), ferromagnets, the Potts antiferromagnet, and random constraint satisfaction problems such as $k$-SAT and hypergraph coloring.

The cavity method and Bethe states. The cavity method of Mézard and Parisi predicts the structure of $\mu_G$ through messages: for adjacent vertices $u,v$, the Belief Propagation (BP) message $\nu_{u\to v}$, a probability distribution on $\Omega$, is the would-be marginal of the spin at $u$ in the graph with $v$ deleted, and BP is the recurrence that these messages satisfy whenever correlations decay with distance. Because disordered systems develop long-range correlations - a phenomenon called replica symmetry breaking (RSB) - Mézard and Parisi hypothesized that the phase space always decomposes into pure states (ergodic components of the Gibbs measure, generalizing the two magnetized phases of the Ising ferromagnet), called Bethe states, such that inside each state correlations decay and the messages satisfy BP. Coja-Oghlan and Perkins proved this hypothesis rigorously for very general models on the random $d$-regular graph subject to a convexity condition called POS: with high probability there is a decomposition into at most $L(n)$ Bethe states, where $L(n)$ grows arbitrarily slowly, and the free energy equals $\inf_{\pi\in\mathfrak{D}^\star}\mathscr{B}(\pi)$, an infimum over distributions $\pi$ on strong kernels - measurable maps $[0,1]^2\to\mathcal{P}(\Omega)$, i.e. kernel-representable message ensembles akin to graphons (a graphon is a symmetric measurable function $[0,1]^2\to[0,1]$ used to describe limits of dense graph sequences), metrized by the cut distance (a metric on kernels that generalizes the cut metric on graphs: it measures the smallest possible discrepancy of weight densities, over all measurable bipartitions of the coordinates) - that are invariant under the cavity perturbation (adding or deleting a few random vertices and edges). Their Theorem 2.6 further expresses the free energy directly in terms of the Bethe state decomposition and its BP messages, so evaluating the formula requires actually determining the decomposition, its states, and their weights.

The replica-symmetry-breaking scenarios. Physics predicts three organizations of the Bethe states and of the minimizing distributions $\pi$, depending on the model and its parameters. First, replica symmetry: a single, or boundedly many, Bethe state(s). Second, one-step RSB (1RSB): an unbounded number of Bethe states that are statistically equivalent in the cavity sense - the empirical distribution of BP messages within each pure state converges to one common limit, while the states themselves differ, their weights and overlaps being described by the 1RSB survey equations (distributional fixed-point equations for the law of a BP message under a random choice of pure state); within this scenario one further distinguishes the dynamically broken regime, where exponentially many tiny clusters still carry replica-symmetric total mass, from the condensed regime, where a sublinear number of states dominate the Gibbs weights. Third, full RSB: the Bethe states form a hierarchical structure in which, as in the Parisi solution of the fully connected Sherrington-Kirkpatrick model, triples of states are organized ultrametrically (pairwise distances satisfy $d(x,z)\le\max(d(x,y),d(y,z))$). For the fully connected model the analogue is a theorem - the Parisi formula and ultrametricity are proven there (see Panchenko's monograph). For diluted, locally tree-like models no such structure theory exists even for graphs of Erdos-Renyi type: Panchenko characterized finite-RSB asymptotic Gibbs measures only conditionally on the RSB ansatz and proved the corresponding variational formula, and the replica-symmetric solution of general diluted models is rigorous only in high-temperature and subcritical regimes (Biswas, Chen and Sen). On the Bethe lattice itself, rigorous RSB-level results exist only for specific models - for example the 1RSB formula for the independence ratio of random $d$-regular graphs at large degree, or the RSB transition of the Ising antiferromagnet - while for the canonical Bethe-lattice spin glass, physics predicts a marginally stable full-RSB phase (Parisi), and the full-RSB variational functional proposed for it (Concetti) remains conjectural. This is the gap the present problem addresses.

Problem Statement

For general spin systems on the Bethe lattice - the random $d$-regular graph - with a finite spin set and weight functions satisfying the convexity condition POS of Coja-Oghlan and Perkins, the free energy density is known to satisfy $\lim_{n\to\infty}\frac{1}{n}\,\mathbb{E}[\log Z(G_n)] \;=\; \inf_{\pi\in\mathfrak{D}^\star}\,\mathscr{B}(\pi),$ where $\mathfrak{D}^\star$ is the space of cavity-invariant distributions on strong kernels and $\mathscr{B}$ is the Bethe functional, and the Gibbs measure admits a decomposition into Bethe states whose conditional measures are free of long-range correlations and approximately satisfy Belief Propagation. Establish rigorously the physics-predicted organization of these Bethe states and of the (near-)minimizing distributions $\pi$:

1. (1RSB structure) In parameter regimes governed by one-step replica symmetry breaking, prove that the number of Bethe states is unbounded while the states are statistically equivalent in the cavity sense - the empirical distribution of Belief Propagation messages within each pure state converges to one common limit - and characterize the state weights and overlaps by the 1RSB distributional (survey) equations, including the condensation transition at which a sublinear number of states come to dominate the Gibbs weights.

2. (Full-RSB structure) In regimes governed by full replica symmetry breaking, prove that the pure states are hierarchically (ultrametrically) organized - the diluted, locally tree-like analogue of the Parisi hierarchy of the Sherrington-Kirkpatrick model.

3. (Scenario identification) For general models and parameters, give an explicit criterion valid across the class of POS spin systems that determines which scenario (replica symmetric, 1RSB, full RSB; dynamically broken versus condensed) actually occurs, including the location of the phase boundaries; the criterion must cover, in particular, the diluted spin glass of Mézard and Parisi as a function of the degree $d$ and inverse temperature $\beta$ and the hard-core model (in which each vertex is either occupied or empty, adjacent vertices cannot both be occupied, and each occupied vertex receives a weight $\lambda$ called the fugacity) as a function of the fugacity $\lambda$.

4. (Effective evaluation) Building on the structural characterization, make the variational formula effectively evaluable: derive explicit descriptions of minimizers or closed-form reductions in the tractable regimes, and practicable, convergent schemes with controlled error for the free energy and for the Bethe state decomposition and its weights, on which the functional $\mathscr{B}(G)$ depends.

Deliverables (1)-(4) jointly serve one objective: converting the exact but abstract variational formula into a rigorous, computable replica-symmetry-breaking theory of the Bethe lattice. The completion boundary is a proven characterization of the low-temperature organization of the Gibbs measure together with a provably correct way to evaluate the free energy, replacing the current ansatz-level cavity predictions.

References

1. Amin Coja-Oghlan and Will Perkins, 'Spin Systems on Bethe Lattices', Communications in Mathematical Physics 372, 441-523 (2019). DOI: 10.1007/s00220-019-03544-y; arXiv:1808.03440. https://doi.org/10.1007/s00220-019-03544-y
2. Marc Mézard and Giorgio Parisi, 'The Bethe lattice spin glass revisited', The European Physical Journal B 20, 217-233 (2001). DOI: 10.1007/PL00011099. https://doi.org/10.1007/PL00011099
3. Marc Mézard and Andrea Montanari, 'Information, Physics, and Computation', Oxford University Press (2009). ISBN 978-0-19-857083-7; DOI: 10.1093/acprof:oso/9780198570837.001.0001. https://doi.org/10.1093/acprof:oso/9780198570837.001.0001
4. Dmitry Panchenko, 'Spin glass models from the point of view of spin distributions', The Annals of Probability 41, 1315-1361 (2013). DOI: 10.1214/11-AOP696. https://doi.org/10.1214/11-AOP696
5. Dmitry Panchenko, 'Structure of Finite-RSB Asymptotic Gibbs Measures in the Diluted Spin Glass Models', Journal of Statistical Physics 162, 1-42 (2016). DOI: 10.1007/s10955-015-1385-8. https://doi.org/10.1007/s10955-015-1385-8
6. Dmitry Panchenko, 'The Sherrington-Kirkpatrick Model', Springer, New York (2013). DOI: 10.1007/978-1-4614-6289-7; ISBN 978-1-4614-6288-0. https://doi.org/10.1007/978-1-4614-6289-7
7. Ratul Biswas, Wei-Kuo Chen and Arnab Sen, 'On the Replica Symmetric Solution in General Diluted Spin Glasses', Random Structures & Algorithms 66, e70013 (2025). DOI: 10.1002/rsa.70013; arXiv:2410.15599. https://doi.org/10.1002/rsa.70013
8. Jian Ding, Allan Sly and Nike Sun, 'Maximum independent sets on random regular graphs', Acta Mathematica 217, 263-340 (2016). DOI: 10.1007/s11511-017-0145-9. https://doi.org/10.1007/s11511-017-0145-9
9. Amin Coja-Oghlan, Philipp Loick, Balázs F. Mezei and Gregory B. Sorkin, 'The Ising Antiferromagnet and Max Cut on Random Regular Graphs', SIAM Journal on Discrete Mathematics 36, 1306-1342 (2022). DOI: 10.1137/20M137999X; arXiv:2009.10483. https://doi.org/10.1137/20M137999X
10. Evan Chang, Neel Kolhe and Youngtak Sohn, 'Upper bounds on the 2-colorability threshold of random d-regular k-uniform hypergraphs for k >= 3', preprint (2023). arXiv:2308.02075. https://arxiv.org/abs/2308.02075
11. Francesco Concetti, 'The Full Replica Symmetry Breaking in the Ising Spin Glass on Random Regular Graph', Journal of Statistical Physics 173, 1459-1483 (2018). DOI: 10.1007/s10955-018-2142-6; arXiv:1712.00367. https://doi.org/10.1007/s10955-018-2142-6
12. Francesco Concetti, 'Properties of the full replica symmetry breaking free energy functional of the Ising spin glass on random regular graph', preprint (2025). arXiv:2508.17049. https://arxiv.org/abs/2508.17049
13. Giorgio Parisi, 'The Marginally Stable Bethe Lattice Spin Glass Revisited', Journal of Statistical Physics 167, 515-542 (2017). DOI: 10.1007/s10955-017-1724-z. https://doi.org/10.1007/s10955-017-1724-z
14. Francesco De Santis and Giorgio Parisi, 'Computation of the Zero Temperature RSB parameter in Bethe Lattice Spin Glasses', preprint (2018). arXiv:1805.01228. https://arxiv.org/abs/1805.01228
15. Marc Lelarge and Mendes Oulamara, 'Replica Bounds by Combinatorial Interpolation for Diluted Spin Systems', Journal of Statistical Physics 173, 917-940 (2018). DOI: 10.1007/s10955-018-1964-6. https://doi.org/10.1007/s10955-018-1964-6
16. Viktor Harangi, 'Improved Replica Bounds for the Independence Ratio of Random Regular Graphs', Journal of Statistical Physics 190, Article 60 (2023). DOI: 10.1007/s10955-022-03062-7; arXiv:2204.01353. https://doi.org/10.1007/s10955-022-03062-7
17. Kuikui Liu, Sidhanth Mohanty, Prasad Raghavendra, Amit Rajaraman and David X. Wu, 'Locally Stationary Distributions: A Framework for Analyzing Slow-Mixing Markov Chains', Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2024), 203-215. DOI: 10.1109/FOCS61266.2024.00022; arXiv:2405.20849. https://doi.org/10.1109/FOCS61266.2024.00022
18. Ágnes Backhausz, Charles Bordenave and Balázs Szegedy, 'Typicality and entropy of processes on infinite trees', Annales de l'Institut Henri Poincare, Probabilites et Statistiques 58 (2022). DOI: 10.1214/21-AIHP1233; arXiv:2102.02653. https://doi.org/10.1214/21-aihp1233