PaperlayerView exact revision on arXiv

Source-linked AI summary

Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models

Andreas Galanis, Daniel Stefankovic, Eric Vigoda

arXiv:1203.2226v4cs.DMmath-phmath.PR

TL;DR

The paper asks whether the computational transition for approximating 2-spin partition functions coincides with the uniqueness transition on the infinite regular tree. It uses second-moment analysis of random regular bipartite graphs linked to tree recursions, and proves inapproximability throughout the non-uniqueness region for hard-core and zero-field antiferromagnetic Ising models, with an extension to some general 2-spin models.

  • Problem

    The paper investigates whether approximation complexity for antiferromagnetic 2-spin partition functions undergoes a transition matching the uniqueness/non-uniqueness phase transition on the infinite tree.

  • Method

    The proof analyzes second moments of the Ising partition function on random Δ-regular bipartite graphs and relates them to tree recursions used to identify critical points.

  • Results

    Unless NP=RP, no FPRAS exists throughout the tree non-uniqueness region for the hard-core model and zero-field antiferromagnetic Ising model for every Δ≥3, with an extension to a region of general 2-spin models.

  • Takeaways & Limitations

    The results establish complementary inapproximability to existing uniqueness-region approximation schemes and settle the hard-core transition across the full non-uniqueness region.

  • Takeaways & Limitations

    For general antiferromagnetic 2-spin models, the results do not reach the uniqueness/non-uniqueness threshold in general.

Abstract

from arXiv · show

Recent inapproximability results of Sly (2010), together with an approximation algorithm presented by Weitz (2006) establish a beautiful picture for the computational complexity of approximating the partition function of the hard-core model. Let $λ_c(T_Δ)$ denote the critical activity for the hard-model on the infinite $Δ$-regular tree. Weitz presented an FPTAS for the partition function when $λ<λ_c(T_Δ)$ for graphs with constant maximum degree $Δ$. In contrast, Sly showed that for all $Δ\geq 3$, there exists $ε_Δ>0$ such that (unless RP=NP) there is no FPRAS for approximating the partition function on graphs of maximum degree $Δ$ for activities $λ$ satisfying $λ_c(T_Δ)<λ<λ_c(T_Δ)+ε_Δ$. We prove that a similar phenomenon holds for the antiferromagnetic Ising model. Recent results of Li et al. and Sinclair et al. extend Weitz's approach to any 2-spin model, which includes the antiferromagnetic Ising model, to yield an FPTAS for the partition function for all graphs of constant maximum degree $Δ$ when the parameters of the model lie in the uniqueness regime of the infinite tree $T_Δ$. We prove the complementary result that for the antiferrogmanetic Ising model without external field that, unless RP=NP, for all $Δ\geq 3$, there is no FPRAS for approximating the partition function on graphs of maximum degree $Δ$ when the inverse temperature lies in the non-uniqueness regime of the infinite tree $T_Δ$. Our results extend to a region of the parameter space for general 2-spin models. Our proof works by relating certain second moment calculations for random $Δ$-regular bipartite graphs to the tree recursions used to establish the critical points on the infinite tree.

1 Introduction

The paper studies whether the computational transition for approximating 2-spin partition functions coincides with the uniqueness transition on the infinite Δ-regular tree. It proves sharp inapproximability results for hard-core and antiferromagnetic Ising models in the tree non-uniqueness region, using second-moment analysis of random regular bipartite graphs.

  • Model framework: 2-spin systems assign configurations on bounded-degree graphs weights determined by edge activities B1, B2 and vertex activity λ, with the partition function normalizing the Gibbs distribution.The hard-core model is obtained from B1=0, B2=1; the Ising model from B1=B2=B, and λ=1 gives the zero-field case.
  • Hard-core model: For the hard-core model, Weitz gave an FPTAS in the tree uniqueness region, while prior work established inapproximability just above the critical activity and this paper settles all λ in the non-uniqueness region.Theorem 1 rules out an FPRAS unless NP=RP for every Δ≥3 and every activity in the non-uniqueness region.
  • Problem setting: The central question is whether approximation complexity changes exactly at the uniqueness/non-uniqueness phase transition of the infinite Δ-regular tree.The paper connects this computational question to the tree phase transition associated with decay of correlations in Gibbs measures.
  • Antiferromagnetic Ising model: For the antiferromagnetic Ising model without external field, no FPRAS exists unless NP=RP throughout the non-uniqueness region for every Δ≥3.The result applies to graphs of maximum degree at most Δ and inverse temperature B in the tree non-uniqueness region.
  • General 2-spin models: The results extend to a region of general antiferromagnetic 2-spin models, although they do not reach the uniqueness/non-uniqueness threshold for all such models.The general-model theorem requires an additional condition beyond tree non-uniqueness.
  • Proof approach: The proof analyzes the second moment on random Δ-regular bipartite graphs and relates it to tree recursions governing the critical points.The analysis estimates the partition function within an arbitrarily small polynomial factor, enabling an approximation-preserving hardness reduction.

2 Proof Outline

The proof analyzes phase separation in random regular bipartite graphs through second-moment estimates, then uses this bimodality in reductions to establish hardness and slow Glauber dynamics. Tree recursions control the crucial optimization, extending the argument across antiferromagnetic 2-spin models and selected hard-core cases.

  • Phase structure: The proof studies random Δ-regular bipartite graphs to show that Gibbs configurations are concentrated near unbalanced phases in the tree non-uniqueness region.The two phases correspond to densities (p±, p∓) on the bipartition sides.
  • Phase structure: In the non-uniqueness region, the first-moment contribution is maximized at the asymmetric density pairs (p±, p∓), whereas uniqueness favors (p*, p*).This identifies the dominant phase configurations used in the later second-moment analysis.
  • Consequences: The resulting bimodality makes the random bipartite graph function as a Boolean gadget in the hardness reduction, while balanced configurations have exponentially small Gibbs measure and Glauber dynamics is torpidly mixing.The proof first obtains a polynomial-factor estimate for the partition function and then applies the reduction framework.
  • Second moment: The second-moment argument requires uncorrelated configuration pairs to dominate, formalized by Condition 1 and verified for general 2-spin systems and specified Ising and hard-core regimes.The stated cases include the hypotheses of Theorem 3, antiferromagnetic Ising with Δ=3, and hard-core models with Δ=3, 4, 5.
  • Second moment: Tree recursions reduce the general soft-constraint second-moment optimization, which otherwise involves nine extra variables, to a short inequality argument.For the hard-core model, hard constraints reduce the optimization to two variables.

3 Extremal Measures on the Infinite Tree for 2-Spin Models

The infinite tree has free and parity-conditioned Gibbs measures whose fixed points distinguish uniqueness from non-uniqueness. These measures supply the occupation densities that determine the dominant phases in the random-graph moment calculations.

  • Tree measures: The infinite (Δ−1)-ary tree has the same uniqueness and non-uniqueness regions as the infinite Δ-regular tree, although root occupation probabilities differ.The rooted tree is used because its recursion has a convenient root degree.
  • Tree measures: The free measure μ* is translation invariant, while μ+ and μ− are semi-translation invariant measures induced by even and odd boundary conditions.Their root probabilities are denoted p*, p+ and p−, respectively.
  • Fixed points: The recursion has one fixed point (Q*, Q*) in the uniqueness region and exactly three solutions, (Q±, Q∓) and (Q*, Q*), in the non-uniqueness region.In the latter case, Q− < Q* < Q+.
  • Fixed points: The corresponding two-step tree recursion has q+ and q− as attractors in the non-uniqueness region, linking the extremal measures to the inequalities used in the moment analysis.The quantities ω and ω* are introduced to express these recursion-based optimality conditions.
  • Ising symmetry: For the zero-field Ising model, symmetry gives p+ + p− = 1, q+ + q− = 1, and p* = q* = 1/2.These identities follow from the transformation exchanging the two spin states.

4 Moment Analysis

The moment analysis expresses contributions of fixed-density configurations and configuration pairs on random regular bipartite graphs, then applies asymptotic maximization to identify dominant phases and overlaps. Stirling’s approximation converts the combinatorial sums into first- and second-moment optimization problems.

  • First moment: For a configuration with −1 densities α and β on the two bipartition sides, the first moment sums matching contributions according to their −1-to−1 edge count δn.The matching contribution depends on δn, while independent matchings produce the Δ-power and the external field contributes the λ term.
  • First moment: The first-moment formulation partitions each side by spin and uses edge-count variables xij constrained by the side densities.These variables encode how a perfect matching connects the four spin-defined parts.
  • Second moment: The second moment tracks overlaps γ and δ between two configurations and refines the matching counts with variables yij across their four induced parts on each side.The row and column sums of yij are determined by the overlap-induced quantities Li and Rj.
  • Asymptotics: Stirling’s approximation reduces the first- and second-moment sums to maxima of Φ1(α, β, X) and Φ2(γ, δ, Y), combining field, entropy, and interaction terms.The functions f1 and f2 provide the entropy terms, while g1 and g2 encode matching interaction contributions.
  • Asymptotics: For the second moment, Φ2 includes the doubled external-field contribution and an entropy term determined by the overlap densities γ and δ.Its interaction term depends on the yij variables and the model parameters.

5 Finding the Maxima

The section reduces the relevant moment calculations to constrained maximization problems and classifies their critical points and local maxima across uniqueness regimes. Strict concavity, symmetry, and Hessian analysis identify the maximizers used in the later lemmas.

  • General maximization framework: The functions φ1 and φ2 are written as maxima of Φ(u,v,Z)=f(u,v)+g(Z) over nonnegative variables with prescribed marginals.This abstraction unifies the first- and second-moment optimization problems.
  • General maximization framework: Strict concavity makes g(Z) attain its maximum at a unique point, characterized by Lagrange-multiplier conditions.The positive variables R_i and C_j satisfy the displayed marginal equations, with uniqueness modulo reciprocal scaling.
  • First-moment optimization: In the non-uniqueness region, φ1 has critical points (p±,p∓) and (p∗,p∗), whereas the uniqueness region has only (p∗,p∗).The boundary contributes no local maximum.
  • First-moment optimization: In the non-uniqueness region, Φ1 has a local maximum at (p+,p−,X∗) and a saddle point at (p∗,p∗,Xo); in the uniqueness region, (p∗,p∗,Xo) is a local maximum.These classifications follow from Hessian analysis and distinguish the relevant asymmetric and symmetric points.
  • Second-moment optimization: For the second-moment objective at (α,β)=(p±,p∓), symmetry forces R2=R3 and C2=C3, and the only critical point satisfies γ=α2 and δ=β2.The corresponding point is a local maximum, with no local maximum on the boundary.
  • Proof remarks: The antiferromagnetic Ising analysis requires tighter treatment where the AM-GM inequalities become weak, specifically when the relevant ratios greatly exceed B2/B1.The proof exploits this weakness in the antiferromagnetic, zero-field regime rather than treating it as a generic bound.

6 NP-Hardness Results

The paper extends Sly’s reduction to general 2-spin models, proving inapproximability throughout the non-uniqueness region under Condition 1. The construction uses a random bipartite gadget whose phases and conditioned root spins exhibit the concentration properties needed for the reduction.

  • Theorem 5 rules out an FPRAS for 2-spin models in the tree’s non-uniqueness region when Condition 1 holds, unless NP = RP.
  • Consequences: The hard-core theorem follows for every ∆≥3, while the cases ∆=4,5 are obtained by combining Theorem 5 with Lemma 4.
  • Consequences: For the antiferromagnetic Ising model without external field, Theorem 2 rules out an FPRAS throughout the non-uniqueness region for all ∆≥3.
  • Gadget construction: The gadget uses random bipartite matchings, appended even-depth trees, and a phase determined by which side has more −1 spins.The appended trees make concentration easier to establish for the roots corresponding to degree-∆−1 vertices.
  • Gadget properties: Lemma 19 states that the two phases occur with roughly equal probability and that root spins are approximately independent when conditioned on a phase.The root-spin probabilities are tied to extremal measures on the infinite (∆−1)-ary tree.
  • Proof strategy: The proof first establishes asymptotic product behavior for the auxiliary vertices, then transfers it to tree roots using the gadget’s appended trees and extremality.

7 Calculating Moments

This section analyzes first and second moments of constrained partition functions using entropy-based optimization and Gaussian approximations around unique maxima. The key comparison identifies matching exponential rates for the relevant first- and second-moment quantities.

  • Optimization identities: Lemma 27 establishes the matching relation 2Φ1(α, β, X*) = Φ2(α2, β2, Y*).
  • Optimization identities: Entropy identities relate the one-copy and two-copy optimization problems through f2(α2, β2) = 2f1(α, β) and g2(Y*) = 2g1(X*).
  • First moment: The first-moment asymptotics are obtained by restricting to a neighborhood of the maximizer and applying standard integration arguments to the quadratic decay.
  • The first and second moments are analyzed through optimization functions whose dominant terms lie near unique maximizers and exhibit quadratic decay.Strict concavity and local quadratic decay justify Gaussian integration around the maximizers.
  • Second moment: The second-moment asymptotics use successive Gaussian integrations after decomposing the Hessian into principal minors and verifying the required definiteness condition.The calculation is completed after checking 4DF − E2 > 0.
  • Concentration: The analysis also bounds contributions outside the dominant neighborhoods by exp(−Ω(n1/2)), allowing those terms to be omitted asymptotically.

8 Asymptotically Almost Surely results

The section uses small subgraph conditioning to establish asymptotically almost sure moment and partition-function properties on random regular bipartite graphs. Cycle counts are handled through Poisson limits and transition-matrix calculations.

  • Small subgraph conditioning extends earlier hard-core analyses to account for the additional parameters B1 and B2 in general 2-spin models.
  • Conditioning framework: The conditioning theorem yields Y > r(n)E[Y] asymptotically almost surely when cycle variables satisfy asymptotic Poisson independence and the required conditional-moment relations.
  • Cycle analysis: For random ∆-regular bipartite graphs, odd cycle counts vanish and even cycle counts satisfy the required Poisson conditions.
  • Consequences: The resulting lemmas provide the ingredients needed for the later hardness proof, with the relevant bounds selected using r(n) = 1/n and r(n) = 1/√n.
  • Cycle analysis: Cycle contributions are encoded by red, blue, and white vertex assignments, with red-red and blue-blue adjacent assignments prohibited.
  • Cycle analysis: A transition matrix counts weighted closed walks corresponding to rooted oriented cycles, enabling the calculation of cycle-dependent moment ratios.

9 Remaining Proofs

The remaining proofs establish inequalities and Hessian properties needed for the moment analysis and non-uniqueness arguments. They use algebraic identities, AM-GM bounds, concavity, and Sylvester’s criterion.

  • Lemma 34 supplies an inequality involving B1, B2, x, y, and d that is used in proving the non-uniqueness-related Lemma 8.
  • Algebraic inequalities: The proof of Lemma 34 derives the inequality from two representations of W and the AM-GM inequality, with equality characterized by x = y.
  • Concavity and maximizers: Strict concavity and Taylor expansion yield the quadratic decay of g near its maximizer, including cases where some matrix entries are zero.
  • Boundary cases: The boundary analyses control derivatives as α, β, γ, or δ approach the feasible-region boundary, completing the proofs of the auxiliary lemmas.
  • Hessian analysis: The Hessian analysis for Φ1 uses Sylvester’s criterion, with positivity of a principal minor supplied by Lemma 8 and a saddle-point sign change in the critical case.
  • Hessian analysis: The analogous Φ2 analysis checks positive definiteness of −H2, relying on convexity for the first principal minors and Lemma 8 for the remaining condition.

9.5 Proof of Lemma 3

The proof establishes the required inequalities for the Ising model without external field in the case B1 = B2 = B, λ = 1, and ∆ = 3. It splits the analysis according to whether r1r4 is below or above 1, then concludes the lemma from the resulting bounds.

  • The proof specializes to the Ising model without external field with B1 = B2 = B, λ = 1, and ∆ = 3.The proof is identified as establishing Condition 1 in this parameter setting.
  • The parameter region 0 < B < 1 yields values of α and β heavily biased toward 1 and 0, respectively.The proof uses this bias to derive corresponding bounds on r1, r4, c1, and c4.
  • The analysis of inequality (73) splits into the cases r1r4 < 1 and r1r4 > 1, with the latter described as considerably harder.Claims 40 and 41 address the two cases separately.
  • The proof concludes by showing that the only critical points satisfy γ = α2 and δ = β2, then applying Lemmas 15 and 16.This yields the stated conclusion of Lemma 3.

9.6 Proof of Lemma 4

The proof of Lemma 4 reduces the critical-point analysis to the hard-core model and verifies that the only critical points satisfy γ = α2 and δ = β2. The argument uses case-based sign analysis after reparameterizing the relevant expressions.

  • Lemma 43 states that for the hard-core model with ∆ = 3, 4, 5, the solution satisfies γ = α2 and δ = β2.The lemma applies when B1 = 0, B2 = 1, and (α, β) = (p+, p−).
  • Lemma 4 follows because the only critical points of φ2(γ, δ) satisfy γ = α2 and δ = β2, after which Lemmas 15 and 16 complete the argument.The proof explicitly parallels the proof of Lemma 2.
  • The proof parameterizes the variables using d := ∆−1, x = (r1r4)1/d, y = (c1c4)1/d, a = 1/r4, and b = 1/c4.This transforms the equations used to analyze the critical points.
  • Symmetry between x and y reduces the analysis to two cases, while the case x = y = 1 directly gives γ = α2 and δ = β2.The two nontrivial cases are distinguished by the ordering of x, y, and yd.
  • After reparameterization, the coefficient signs differ by case: all four are positive in Case 1, while c00 and c11 are positive and c01 and c10 are negative in Case 2.The resulting sign patterns prevent the target expression from being zero.

A.1 Case ∆= 3

The ∆ = 3 appendix case uses symbolic algebra to transform the target expression, reduce powers, and factor its coefficients after a reparameterization. The resulting factor structure exposes the required sign pattern.

  • The computation substitutes expressions for a and b into the target expression and reduces powers of qa and qb.The reduced expression has the form c00 + c10qa + c01qb + c11qaqb.
  • The computation checks that the transformed expressions represent the target left-hand side up to nonzero factors introduced during substitution and reduction.The comments identify the denominator factors and the factor retained as H.
  • The reparameterization x = (ty + yd)/(t + 1) is used to reveal the signs of c00, c01, c10, and c11.The transformed coefficients are denoted u00, u01, u10, and u11.
  • The symbolic expressions for the four coefficients are expanded into polynomials in t and y for the ∆ = 3 case.The displayed expansions provide the coefficient-level verification used in the appendix.

A.2 Case ∆= 4

The ∆ = 4 appendix case repeats the symbolic factorization strategy and checks positivity of the remaining coefficient factors. The computation is organized around transformed coefficients c00, c01, c10, and c11.

  • For ∆ = 4, the computation constructs the target polynomial F and extracts a factor after substituting the expressions for a and b.The substitution uses a = (−1 + y + Qa)/(x^d − y) and b = (−1 + x + Qb)/(yd − x).
  • The powers of Qa and Qb are reduced recursively using identities involving 1 − xd − y + xdy and 1 − yd − x + ydx.This leaves an expression suitable for coefficient extraction.
  • The coefficients c00, c01, c10, and c11 are extracted from the reduced polynomial H and then reparameterized through x = (ty + yd)/(t + 1).The transformed objects are u00, u01, u10, and u11.
  • The appendix checks positivity of the coefficients of the last factor for each transformed coefficient.The symbolic test sets T and y to 1 when checking whether any coefficient is negative.

A.3 Case ∆= 5

The Δ=5 case factors a polynomial, substitutes auxiliary expressions, reduces higher powers, extracts coefficient terms, and checks resulting factors for negativity.

  • A.3 Case ∆= 5: The computation factors an expression with d = 4 and extracts a selected factor after expansion.The factorization is built from two polynomial products involving x, y, a, and b.
  • A.3 Case ∆= 5: The calculation substitutes a and b in terms of x, y, Qa, and Qb before reducing powers of Qa and Qb.Higher powers are replaced using the relations 1 - x^d - y + x^d*y and 1 - y^d - x + y^d*x.
  • A.3 Case ∆= 5: Each coefficient term is expanded after substituting x = (t*y + y^d)/(t + 1), and the resulting factor lists are measured by their lengths.The same substitution is applied to all four coefficient terms.
  • A.3 Case ∆= 5: For Δ=5, the code tests factors from u00, u01, u10, and u11 at T = 1 and y = 1, marking BAD if any evaluated factor is negative.The final output is the Boolean value BAD.
Loading 1203.2226v4…