Information-theoretic thresholds from the cavity method

1. INTRODUCTION

• The present framework rigorously handles replica-symmetric cavity predictions, while rigorous justification of the more intricate replica-symmetry-breaking method remains open.The paper states that replica symmetry breaking appears necessary for some k-SAT and q-colorability thresholds, whereas replica symmetry suffices for teacher-student problems and condensation thresholds.Source: §1 · p. 1
• The paper proves that, under easily checked conditions, replica-symmetric cavity predictions reduce random-graph problems to stochastic optimization over bounded-dimensional probability distributions and Belief Propagation on Galton-Watson trees.This supplies a rigorous basis for physics calculations and connects mutual information to information-theoretic thresholds and condensation transitions.Source: §1 · pp. 1–2

1.1. The Potts antiferromagnet.

• For the Potts antiferromagnet, the exact condensation transition is determined by the cavity method’s stochastic optimization problem for all d and q.The transition forms a line in the (d,β)-plane; a phase transition occurs when the relevant critical quantity is finite, including when d > (2q −1)lnq.Source: §1.1 · pp. 2–3

1.2. Random graph coloring.

• For random graph coloring, the paper proves the predicted condensation threshold for every q ≥3, extending earlier second-moment results that required q to exceed an undetermined large constant.The threshold lower-bounds the q-colorability threshold and supports indirect study of coloring geometry through planted models.Source: §1.2 · p. 3

1.3. The stochastic block model.

• In the disassortative stochastic block model, d > d_inf(q,β) permits nontrivial recovery by some algorithm, whereas d < d_inf(q,β) makes nontrivial recovery impossible for every algorithm.The theorem settles the exact information-theoretic threshold for all q ≥3 and β > 0.Source: §1.3 · pp. 4–5

1.4. LDGM codes.

• For LDGM codes, the paper determines the limiting mutual information per bit for all k ≥2, extending prior even-k results to odd k.It proves Montanari’s conjectured formula in the Poisson variable-degree model and extends the related capacity conjecture to all k.Source: §1.4 · p. 5

2. THE CAVITY METHOD, STATISTICAL INFERENCE AND THE INFORMATION-THEORETIC THRESHOLD

• The teacher-student scheme generalizes LDGM to finite spin sets and positive weight functions on random factor graphs, with the student inferring a hidden ground truth from the graph.Strict positivity ensures the introduced quantities are well-defined, while SYM, BAL, and POS can be checked solely from the prior over weight functions.Source: §2.1 · p. 6

2.1. The mutual information.

• Theorems 2.2 and 2.4 give exact mutual-information formulas and identify the relevant optimization with the dominant Belief Propagation fixed point on a Galton-Watson tree.Theorem 2.2 reduces random factor-graph sequences to one stochastic optimization problem; Theorem 2.4 characterizes its optimizer through density evolution.Source: §2.1 · p. 6, §2.2 · p. 7

2.3. The information-theoretic threshold.

• Theorem 2.6 pinpoints dinf as the threshold where the teacher-student and null models change from sublinear to linear Kullback-Leibler divergence.The theorem extends quiet planting across the maximum possible range of d and connects detectability to the mutual-information formula.Source: §2.3 · p. 8

2.4. The condensation phase transition.

• Theorem 2.7 establishes a condensation phase transition at dinf when the limiting normalized expected log-partition function is non-analytic or fails to exist nearby.This verifies a prediction from and derives the paper’s condensation results under the same prior-based assumptions.Source: §2.4 · p. 9

2.5. Discussion and related work.

• The results identify the maximizer of B(d, ·) as the relevant Belief Propagation fixed point, overcoming prior results that did not determine which fixed point governs the free energy.Earlier general validity required strong Gibbs uniqueness, typically only at small d; the present proofs instead conceptually vindicate replica-symmetric cavity predictions.Source: §2.5 · p. 9
• The framework is restricted to Poisson Erdős-Rényi factor graphs and assumptions SYM, BAL, POS, and strict positivity; replica symmetry breaking remains an open issue, though replica symmetry suffices for teacher-student inference and condensation.BAL fails for the assortative block model, and hard constraints require separate limiting arguments; the rigorous 1RSB theory remains largely unresolved.Source: §2.5 · pp. 9–10, §2.4 · p. 9

2.6. Preliminaries and notation.

• For finite Ω, Proposition 2.10 states that independent samples from π admit an empirical-marginal approximation sequence ε_K → 0 as K → ∞.Source: §2.6 · p. 11
• The preliminaries define mutual information between finite-valued random variables and conditional mutual information given a third variable.Source: §2.6 · p. 11
• They also recall entropy, the chain rule H(X,Y) = H(X) + H(Y|X), Kullback–Leibler divergence, and Pinsker’s inequality.Source: §2.6 · p. 11

• The proofs establish a rigorous foundation for replica symmetric calculations previously used non-rigorously in physics.The strategy combines several prior ideas with new arguments, centered on Theorem 2.2.Source: §3.1 · p. 12
• Theorem 2.2 is the central result, from which Theorems 2.6 and 2.7 are subsequently derived.Source: §3.1 · p. 12
• Theorem 2.4 also follows from Theorem 2.2 but requires additional arguments.Source: §3.1 · p. 12

3.1. Overview.

• The proof uses a reweighted teacher-student scheme, pinning, the Aizenman-Sims-Starr scheme, and interpolation to obtain matching mutual-information bounds.The lower bound comes from adding one variable node; the upper bound uses interpolation.Source: §3.1 · p. 12, §3.1.3 · pp. 14–15

3.1.1. The Nishimori property.

• The reweighted teacher-student construction makes the ground truth an exact Gibbs-measure sample, realizing the Nishimori property non-asymptotically.This identity allows posterior and Gibbs-measure calculations to coincide in the reweighted model.Source: §3.1.1 · pp. 12–13

3.1.2. Symmetry and pinning.

• Pinning a typically bounded number of coordinates to sampled spin values makes an arbitrary distribution ε-symmetric with probability at least 1−ε.The perturbation lemma supplies symmetry rather than requiring it to be checked directly.Source: §3.1.2 · p. 14

3.1.3. The free energy.

• The lower free-energy bound tracks the n-to-n+1 change using Gibbs-marginal invariance, while the upper bound interpolates to isolated variables and uses POS to control the derivative.The interpolation preserves the distributional Nishimori identity throughout the path.Source: §3.1.3 · pp. 14–15
• Theorem 2.2 follows from the Nishimori, lower-bound, and upper-bound propositions, with Theorems 2.6 and 2.7 then obtained from it.Source: §3.1.3 · p. 15

• The random factor graph is generated from independently sampled weight functions and uniformly chosen variable neighborhoods, with Gibbs measures defined on its outcomes.Source: §3.2 · p. 15
• Reweighting factor graphs by their partition function produces assignment–graph distributions that match the teacher-student construction.Fact 3.8 gives the corresponding distributional description.Source: §3.2 · p. 15
• For fixed or random pinned sets, the relevant assignment–factor-graph experiments are identical, extending the Nishimori property to pinned models.The construction implements pinning through unary constraints and preserves the assignment distribution.Source: §3.2 · pp. 15–17
• Under BAL, the reweighted assignment distribution is mutually contiguous with the uniform distribution when m=O(n), and Proposition 3.2 follows by setting T=0.Source: §3.2 · pp. 17–18

Free-energy identity

• Lemma 3.14 identifies the expected log partition function of the pinned graph with that of the corresponding planted graph.The proof uses Proposition 3.2, mutual contiguity, and concentration of the log partition functions.Source: §3.3 · p. 18

Approximate symmetry

• For every ε > 0, sufficiently large pinning intensity T makes G*_T ε-symmetric with probability at least 1−ε.This follows from the analogous property for the auxiliary graph and contiguity.Source: §3.3 · p. 19

Empirical Gibbs marginals

• The empirical distribution of Gibbs marginals is analyzed through Wasserstein convergence and spin-conditioned reweighted marginal distributions.The argument partitions the space of marginals, controls spin counts using approximate symmetry and concentration, and derives the stated convergence lemmas.Source: §3.3 · p. 19

Coupling construction

• For sufficiently large n, the construction couples random factor graphs by generating ˜m = Po(˜λ) independent random constraint nodes and applying unary or variable-node pinning operations.It chooses θ uniformly from [0,T] and pins variable nodes to σ∗.Source: §3.3 · pp. 20–21

Distributional comparison

• For sufficiently large n, the coupled graphs G′ and G′′ have the distributions of the corresponding planted graphs, while the common graph ˜G and G*_T have total variation distance o(1).Poisson additivity and the calibrated expected degrees establish the distributional identities; comparing pinning sets and constraint counts yields the total-variation bound.Source: §3.3 · pp. 21–22

Contiguity and approximation

• For any fixed γ∗, the distribution of Y and the uniform distribution are mutually contiguous, with ε_T=o_T(1) under the bounded-mean condition D=d+o(1).The argument invokes (3.52), (3.53), Lemma 2.8, Fact 3.16, and Claim 3.21 to obtain the vanishing error term.Source: §3.3 · p. 24

Completion of the proof

• The lower-bound assertion follows by applying the weak continuity of B(d, ·) to the preceding distributional identities and mixture bounds.The proof uses the independent-sample construction, the normalization of the denominator in (3.26), and the resulting equations (3.55)–(3.58).Source: §3.3 · p. 24

Mixture representation

• With high probability, ρ_˜G admits a decomposition (1−α(˜G))ρ_˜G+α(˜G)δ_ν(˜G)∈P^2, where α(˜G)≥0 and E[α(˜G)]=o(1).This follows from the total-variation estimate TV=o(1), expressing ρ_˜G as an asymptotically near-uniform component plus a small exceptional mass.Source: §3.3 · p. 24

3.4. The upper bound.

• The interpolation compares a model with free energy −nB(d,π)+o(n) to the original factor graph, with a non-positive free-energy derivative under BAL, SYM, and POS.The interpolating family is parameterized by t ∈ [0,1], with t = 1 identical to the original model.Source: §3.4 · p. 25

3.4.1. The interpolation scheme. ∗(Ω).

• At t = 1 the interpolated model is the original factor graph, while at t = 0 every connected component contains only one variable node.The model has Po(dn(1−(1−1/k)t)) constraint nodes, with unary constraints at t = 0.Source: §3.4.1 · p. 25
• For every ε > 0, a t-independent T makes the perturbed interpolating Gibbs measure ε-symmetric with probability at least 1−ε uniformly over t ∈ [0,1].The perturbation uses planted assignments and additional unary constraints to obtain the replica-symmetric models required by the argument.Source: §3.4.1 · p. 26

3.4.2. Coupling assignments.

• For m = O(n), the reweighted assignment distribution is mutually contiguous with the uniform distribution, is independent of γ in law, and admits couplings for neighboring m values.The coupling argument uses BAL and strict entropy concavity to control deviations from the uniform empirical distribution.Source: §3.4.2 · pp. 26–27

3.4.3. Proof of Proposition 3.25.

• The proof of Proposition 3.25 couples neighboring interpolating graphs by controlling assignment changes and shows that approximate symmetry, together with POS, yields the required interpolation estimates.The construction gives high-probability control of the number of differing constraint neighborhoods or weight functions, while the Gibbs marginals become asymptotically uniform in total variation.Source: §3.4.3 · pp. 28, 31

3.4.4. Proof of Proposition 3.7.

• Adding {0,1}-valued constraint nodes gives E[ln Z(ĜT,1)] ≤ E[ln Z(Ĝ)], while E[ln Z(ĜT,0)] = E[ln Z(Ĝ0,0)] + o(n) because only finitely many unary constraints are added.The number of added constraints is bounded by fixed T, and each component of ĜT,0 contains one variable node with Po(d) unary constraints.Source: §3.4.4 · pp. 31–32
• E[ln Z(Ĝ0,0)] is computed directly because every connected component contains a single variable node, allowing symmetry to reduce the expectation to the component of x1.The degree of x1 is Poisson distributed, and its incident weight functions follow the construction specified at t = 0.Source: §3.4.4 · p. 32
• Proposition 3.7 follows immediately from Lemmas 3.35 and 3.36 after the preceding partition-function comparison and component calculation.Source: §3.4.4 · p. 32
• Theorem 2.2 is then used to derive Theorems 2.6 and 2.7, with the Kullback–Leibler divergence recalled as preparatory background.Source: §3.5 · p. 32

Auxiliary lemma

• The proof of Lemma 3.38 uses a planting-style argument to transfer high-probability events between graph/assignment distributions when the quenched and annealed values coincide.The argument begins from concentration of ln Z and controls the relevant event through the planted measure.Source: §3.5 · pp. 32–33

Proof strategy

• The key equivalence is E[ln Z( ˆG)] = ln E[Z(G)] + o(n) if and only if E[ln Z(G)] = ln E[Z(G)] + o(n).The forward direction uses concentration, truncation, and Paley–Zygmund; the converse derives an extensive deficit under the alternative.Source: §3.5 · p. 33

Corollary 3.40

• Corollary 3.40 converts the failure of the planted equality into an extensive gap between the quenched and annealed log-partition functions.This gap is then used to identify the relevant threshold regime.Source: §3.5 · p. 34

Theorem 2.7

• For d < d_inf, E[ln Z(G(n,m,p))] = ln E[Z(G(n,m,p))] + o(n), whereas for d > d_cond, E[ln Z(G(n,m,p))] ≤ E[ln Z(Ĝ(n,m,p))] − Ω(n).The below-threshold relation follows from Corollary 3.39 and Lemma 3.3, while the above-threshold bound follows from Lemma 3.38, Corollary 3.39, and (3.77).Source: §3.5 · pp. 34–35

Theorem 2.6

• Lemma 3.41 relates the relevant planted and unplanted quantities under SYM and BAL, using asymptotic balance and non-negativity of Kullback–Leibler divergence.Theorem 2.6 is then immediate from Theorem 2.7 and Lemma 3.41.Source: §3.5 · pp. 32, 35

Theorem 2.4

• The empirical marginal distribution ρ(G*) satisfies an approximate distributional Belief Propagation fixed-point property for sufficiently large n.Lemma 3.42 establishes the required convergence, and the result is obtained by combining the coupling and perturbation estimates.Source: §3.6 · pp. 35, 36, 39

Perturbation stability

• Adding a bounded number of variables and constraints changes the empirical marginal distribution by at most an arbitrarily small Wasserstein-1 error when the original graph is sufficiently symmetric.The proof couples a uniformly sampled old variable with a corresponding variable in the enlarged graph and controls expected total variation distance.Source: §3.6 · pp. 36–38

Regularity argument

• Regularity partitions supplied by Theorem 3.44 control conditional measures on most cells and transfer regularity from the enlarged graph back to the original graph.The argument uses REG1–REG4, total variation bounds, and state estimates to obtain the needed local stability.Source: §3.6 · p. 37

Coupling construction

• The construction couples a planted graph with an enlarged graph containing L additional variables, whose empirical marginals approximate those of the original graph.The distinguished variables are shown to be representative up to total variation error, enabling the later perturbation argument.Source: §3.6 · pp. 38–39

Fixed-point identification

• The approximate fixed-point relation is derived by sampling neighboring factor nodes and using SYM, independent uniform positions, weak continuity of T_d, and contiguity.The neighboring variables contribute independent samples from the corresponding empirical distributions under the teacher-student construction.Source: §3.6 · p. 39

Proof ingredients

• The argument generalizes an earlier lemma and relies on entropy identities, the chain rule, and Kullback–Leibler divergence calculations.The cited prior work is described as the basis for similar calculations, while the proof here supplies the generalized statement.Source: §3.7 · pp. 40–41

Mutual-information bound

• Uniform random pinning yields an integrated bound on conditional mutual information, with 0 ≤ ∫ E_U[I(σ_i,σ_j | (σ_u)_{u∈U})] dθ ≤ n ln|Ω|.The bound follows from a chain-rule calculation and the fact that conditional mutual information vanishes when either indexed variable is pinned.Source: §3.7 · p. 41

Final conversion

• Applying Markov’s inequality to the mutual-information estimate and then Pinsker’s inequality yields the claimed total-variation conclusion for sufficiently large T.The final step converts the information bound into distributional closeness.Source: §3.7 · p. 42

4.1. Proof of Theorem 1.1.

• The Potts antiferromagnet satisfies BAL, SYM, and POS, allowing the general theorem to yield the expression BPotts(q,d,1−exp(−β)) from (1.2).The proof uses the random factor graph representation and Corollary 4.2.Source: §4.1 · p. 43
• n E[ln Zβ(G(n,d))] = −lnq −d ln(1−(1−exp(−β))/q)/2 iff d ≤dq,cond(β).The condensation threshold matches the information-theoretic threshold defined for the Potts model.Source: §4.1 · p. 43

4.2. Proof of Theorem 1.3.

• The disassortative stochastic block model and the planted Potts antiferromagnet are mutually contiguous for all q ≥2, d > 0, and β > 0.Conditioning away multiple edges has negligible effect because their number is asymptotically Poisson with constant mean.Source: §4.2 · pp. 43–44
• For dinf(q,β) < d≤((q −cβ)/cβ)2, the proof establishes nontrivial overlap behavior and connects it to algorithms producing nearly balanced partitions with positive agreement.The argument uses continuity in d, overlap stability, and the fact that two samples from the relevant measure have non-trivial expected overlap.Source: §4.2 · pp. 45–47
• Above d_inf(q,β), an algorithm achieves positive expected overlap, whereas below it every assignment has vanishing expected overlap.For larger d, the proof reduces to d ≤((q−cβ)/cβ)^2 because the algorithm of Abbe and Sandon [2] succeeds with high probability beyond that range.Source: §4.2 · p. 49

4.3. Proof of Theorem 1.2.

• The random graph coloring condensation threshold satisfies dq,cond ≤(q−1)^2 for every q≥3.The argument transfers balanced coloring results to finite-temperature Potts models and then takes β large enough to obtain the bound.Source: §4.3 · p. 52

4.4. Proof of Theorem 1.4.

• The LDGM application is formulated as a factor model with binary alphabet Ω={±1}, uniformly distributed planted constraint types, and ξ=E[ψ(1)]=1.The passage identifies the conditional constraint distribution with the LDGM-code description before computing the remaining model parameters.Source: §4.4 · p. 54
• The proof of Theorem 1.4 checks SYM, BAL, and POS and concludes the theorem.SYM and BAL follow from constancy of the relevant function, while POS is established through the displayed nonnegativity argument.Source: §4.4 · pp. 54–55

4.5. Further examples.

• The hypergraph Potts antiferromagnet example satisfies BAL, SYM, and POS.The argument uses color symmetry for SYM, convexity for BAL, and a nonnegative polynomial expression for POS.Source: §4.5 · pp. 55–56
• The random k-SAT and k-NAESAT models at inverse temperature β > 0 satisfy BAL, SYM, and POS under uniform literal-sign distributions.Both verifications use Boolean values and literal signs represented by ±1, with POS following from the same nonnegativity inequality.Source: §4.5 · pp. 56–57