Source-linked AI summary
Approximate Counting for Mixed $p$-Spin Glasses in Weak External Fields via Cluster Expansion
Qiang Wu
TL;DR
The paper formulates approximation of eZ_N from disorder and accuracy/failure inputs. It computes retained small-vertex hypergraph contributions using local spin averages and inclusion–exclusion, with a polynomial operation bound.
Problem
The task is to return an approximation eZ_N from N, disorder J, β, h, relative accuracy η, and failure allowance δ.
Source: §1.2 · p. 3Method
For each retained vertex set, local spin averages and inclusion–exclusion compute hypergraph weights without expanding them into individual terms.
Source: §1.5 · p. 5, §3.2 · p. 15Results
Algorithm 1 has an operation bound C N^C ε^-C δ^-C for every finite real input J and every internal-randomness realization.
Source: §1.3 · p. 3Takeaways & Limitations
In SK, fixed-length cycles and paths contribute order one in L2 under the stated regimes, making the o(1) estimate unavailable.
Source: §4 · p. 17For fixed parameter values, success is not claimed simultaneously over the full parameter range; failure is bounded by δ+τ_N, and the cost exponent grows as β0 approaches βf.
Source: §1.3 · p. 3
Abstract
from arXiv · showhide
We give algorithms for approximating the partition function $Z_N$ of the Sherrington--Kirkpatrick (SK) model and finite mixed Ising $p$-spin models with $p\ge 3$. The algorithms apply at a fixed margin below the second-moment threshold $\beta_{\mathrm f}$ with homogeneous weak external fields $|h|\leq\rho_0N^{-1/4}$, for fixed $\rho_0>0$. For any accuracy $\varepsilon\in(0,1)$ and failure parameter $\delta\in(0,1)$, they approximate $\log Z_N$ to additive error $\varepsilon$. The number of exact operations is polynomial jointly in $N$, $\varepsilon^{-1}$, and $\delta^{-1}$. The disorder variables have i.i.d symmetric distribution with unit variance. The failure probability is at most $\delta$ plus an explicit disorder tail bound. This tail bound tends to zero under a finite fourth moment condition. Our approach builds on the cluster expansions of Aizenman--Lebowitz--Ruelle~\cite{ALR87} and Dey--Wu~\cites{DW23,DW26}. For higher-order mixtures, we retain hypergraphs using few vertices and evaluate their total weight deterministically through local spin averages and inclusion--exclusion. For SK, we impose cutoffs on the number of vertices of degree at least three and on the total number of edges. We estimate the retained sum using randomized color coding~\cite{AYZ95}. A lower tail control based on reverse hypercontractivity~\cite{MOS13} converts the mean-square approximation of the normalized partition function into logarithmic accuracy.
1. Introduction and main results
The introduction distinguishes the long-standing limiting-free-energy problem from the algorithmic task of approximating finite-system partition functions. For spin glasses, that algorithmic task has been studied only recently, and this work takes a cluster-expansion approach.
Introduction and main results
- Talagrand and Panchenko proved the Parisi formula, giving a variational characterization of the limiting free energy for the SK model and its p-spin variants.Source: §1 · p. 1
- The algorithmic counterpart asks how to compute a finite system’s partition function approximately or exactly in polynomial time.Source: §1 · p. 1
- For spin glasses, algorithmic study is recent: prior work established average-case hardness for exact SK evaluation and (quasi)-polynomial approximation algorithms in high-temperature regimes [6] [17] [20] [31].Source: §1 · p. 2
- This work develops an alternative approach based on cluster expansion.Source: §1 · p. 2
1.1. Definitions.
The definitions specify the interaction orders and disorder law for the models, and identify the second-moment threshold through an entropy comparison. The SK model is the order-two case, while the higher-order mixtures use orders at least three.
Definitions
- A finite mixed model is specified by interaction orders P with positive coefficients a_p; SK has P = {2}, while higher-order mixtures use P ⊆ {3, 4, . . .}.Source: §1.1 · p. 2
- The disorder variables are independent with a common law that is symmetric about zero and has unit variance.Source: §1.1 · p. 2
- For β < β_f, the entropy comparison β^2ξ(x) < I(x) holds for every x in (0, 1]; for SK, β_f = 1.Source: §1.1 · p. 2
1.2. Approximate counting problem.
The approximate-counting problem asks for an accurate estimate of a finite system’s partition function, with success assessed over disorder and, for SK, algorithmic randomness. The requested control is finer than an asymptotic free-energy approximation, and the operation-count model excludes numerical precision costs.
Approximate counting problem
- The algorithm takes the system size, disorder realization, parameters, relative accuracy η, and failure allowance δ as input, and seeks an approximate partition function.Source: §1.2 · p. 3
- Accuracy is assessed over disorder and, for SK, independent algorithmic randomness.Source: §1.2 · p. 3
- A log-partition estimate within ε = log(1 + η) suffices for relative accuracy η, whereas o(1) error in N^-1 log Z_N leaves Z_N known only within a factor e^o(N).Source: §1.2 · p. 3
- The operation-count bounds exclude bit complexity and the numerical precision needed to control roundoff errors.Source: §1.2 · p. 3
1.3. Main result.
Theorem 1.1 gives Algorithm 1 a polynomial-operation guarantee for specified parameters, with its error controlled under condition (1). Its failure bound includes a disorder-tail term whose decay depends on moment assumptions.
1.3. Main result.
- C N^C ε^-C δ^-C operations suffice for Algorithm 1 on every finite real disorder input and every realization of its internal randomness.The constants depend only on the fixed model parameters stated in the theorem.Source: §1.3 · p. 3
- For fixed parameter values, the success probability is at least 1 − δ − τN, and the guarantee is not simultaneous across the parameter range.The cost exponent grows as β0 approaches βf.Source: §1.3 · p. 3
- If E|J0|^4 is finite, the disorder tail satisfies t^4 P(|J0| > t) → 0 as t → ∞.The paper notes that a second-moment condition alone need not make the tail bound small.Source: §1.3 · p. 4
- For m ≥ 2(pm + b)/(pm − 1) with E|J0|^m finite, the logarithmic error is at most ε with failure probability at most N^-b for sufficiently large N.The operation cost is at most C_b N^C_b ε^-C_b.Source: §1.3 · p. 4
1.4. The algorithm.
The algorithm factors out a computable term from the partition function and approximates the logarithm of the normalized remainder. A mean-square approximation and lower-tail control yield logarithmic accuracy with polynomial operation cost.
1.4. The algorithm.
- The algorithm computes N log(2 cosh h) + log Z_N exactly and approximates the logarithm of the normalized partition function.The explicitly computable factor is separated as an initial cluster-expansion step.Source: §1.4 · p. 4
- GraphApprox returns an estimate of the normalized partition function with mean-square error at most u using C N C u^-C operations.This guarantee holds for target mean-square error u in (0, 1).Source: §1.4 · p. 4
- With probability at least 1 − δ − τ_N, the normalized partition function is at least z and its estimate differs by at most εz/2, yielding logarithmic error at most ε and polynomial cost.The stated cost is polynomial jointly in N, ε^-1, and δ^-1.Source: §1.4 · p. 4
- The procedure sets a base term from N log(2 cosh h) and the interaction factors, then adds log T when the GraphApprox output T is positive.If T is not positive, it returns the base term alone.Source: §1.4 · p. 5
1.5. Ideas of the proof.
The proof controls the discarded cluster weight, computes retained graph or hypergraph contributions efficiently, and converts mean-square approximation into logarithmic accuracy using lower-tail control.
1.5. Ideas of the proof.
- The proof combines variance bounds for discarded clusters, efficient summation of retained graphs, and lower-tail control to obtain logarithmic accuracy.The lower-tail bound is obtained via reverse hypercontractivity.Source: §1.5 · pp. 5–6
- In the graph expansion, ∂Γ denotes the vertices of odd degree, and the spin mean is tanh h.These quantities enter the expansion and its expected error analysis.Source: §1.5 · p. 5
- Independence and disorder symmetry make cross terms vanish when the expansion error is squared and averaged, enabling a second-moment bound for a fixed retained graph family.The retained family is chosen to keep the resulting error sum small while remaining computable.Source: §1.5 · p. 5
- For higher-order mixtures, retaining hypergraphs on at most k vertices bounds the omitted weight, while local spin averages and inclusion–exclusion sum retained weights without over-counting.Each average G(S) is evaluated using 2^|S| spin configurations, with polynomial work per configuration.Source: §1.5 · p. 5
- For SK, the second-moment contribution from graphs with b branching vertices is bounded by C(Cb/N)^b, motivating cutoffs on branching vertices and total edges.Branching vertices have degree at least three; color coding sums the resulting paths and cycles.Source: §1.5 · pp. 5–6
- Balancing truncation error against the number of candidate vertex sets yields cutoffs with polynomial cost, and for SK the edge cutoff need only be O(1 + log(1/u)).Independent colorings estimate the retained SK graph sum with mean-square error at most u/8 when R ≥ 8C+e^2L/u.Source: §1.5 · p. 6
1.6. Related work.
Related approximate-counting approaches use zero-freeness or sampling and annealing; their model classes and guarantees differ from the cluster-expansion approach discussed here.
1.6. Related work.
- Bencs, Huang, Lee, Liu and Regts [6] give deterministic quasi-polynomial-time zero-freeness algorithms for finite Gaussian mixed Ising and spherical models at zero field, below the second-moment threshold.Their Ising threshold agrees with β_f after matching interaction normalizations.Source: §1.6 · p. 6
- For Gaussian SK at zero field, sampling-based methods yield efficient sampling below β = 1, and annealing-based counting achieves polynomial time for sufficiently large N.The counting guarantee in Hou, Liu, and Yu [20] has polynomial exponents that may depend on accuracy and confidence powers.Source: §1.6 · pp. 6–7
- Sampling-based counting obtains partition-function estimates from Gibbs samples, while the paper’s approach directly sums retained graph weights.The counting-to-sampling reduction requires counts after fixing spins, which can introduce site-dependent fields and lower-order interactions outside the theorem’s model class.Source: §1.6 · p. 7
- Other cited algorithmic results address the random-field Ising model and the continuous random energy model [24].Source: §1.6 · p. 7
1.7. Concurrent work.
Concurrent work also gives approximate-counting algorithms, with differences in disorder, fields, model coverage, and complexity guarantees. The approaches share some SK graph-summing structure but use distinct methods in other settings.
1.7. Concurrent work.
- Concurrent works give deterministic polynomial-time algorithms for Gaussian SK at zero field throughout β < 1, whereas this work allows symmetric disorder and homogeneous weak fields with an explicit disorder tail bound.For higher-order mixtures, the comparison works cover some models excluded here, while [31] reaches the static phase transition for mixtures with all orders at least three.Source: §1.7 · p. 7
- The operation bound is polynomial jointly in system size, inverse accuracy, and inverse failure allowance, but it does not account for numerical precision.The cited guarantees in [31] establish polynomial bit complexity; failure bounds also differ in their vanishing tail terms.Source: §1.7 · p. 7
- For SK at zero field, the approaches separate branching vertices from degree-two paths and cycles and use color coding, while this work adds an auxiliary vertex for weak-field effects.For mixtures of orders at least three, this work uses local spin averages and inclusion–exclusion; the cited alternatives use extended color coding or Hermite expansion with cavity calculations.Source: §1.7 · p. 7
1.8. AI disclosure.
The author describes AI assistance in developing the cluster-expansion algorithms, particularly the higher-order and SK approaches. The author states that they checked all proofs and take responsibility for the mathematical claims.
1.8. AI disclosure.
- The initial cluster-truncation idea was motivated by Dey–Wu, and GPT-5.6 Pro proposed a higher-order algorithm with a hyperedge cutoff.That initial approach yielded only a quasi-polynomial-time algorithm for SK.Source: §1.8 · p. 8
- GPT-6 Pro contributed to the SK approach, including color coding, truncation schemes, key arguments, and reverse-hypercontractivity lower-tail control.Codex also assisted with literature searches, figure generation, and a companion Lean formalization.Source: §1.8 · p. 8
- The author checked all proofs, revised the manuscript, and takes responsibility for its mathematical claims.Source: §1.8 · p. 8
2. Cluster expansion and second moment estimates
The section expands the normalized partition function into graph weights and uses orthogonality to express truncation error through discarded weights. Below the second-moment threshold, edge-count tails decay exponentially, supporting efficient truncation.
2.2. Second moments and the edge tail.
- Below βf, the second-moment bound controls the graph-weight sum and yields exponential decay in the number of edges.The assumptions include |h| ≤ ρ0N^-1/4 and β ≤ β0 < βf.Source: §2 · p. 8, §2.2 · p. 11
2.1. Expansion and orthogonality.
- Expanding each interaction and averaging independent spins expresses the normalized partition function as a sum of graph weights.Selecting interactions in Γ contributes their weight product and a spin average determined by the odd-degree vertices.Source: §2.1 · p. 8
- Distinct graph clusters are orthogonal, so the mean-square truncation error is the sum of expected squared weights of discarded graphs.For distinct clusters, an edge in their symmetric difference appears once and has centered weight, making the expectation vanish.Source: §2.1 · p. 9
2.2. Second moments and the edge tail.
- Retaining at most L edges gives mean-square error at most u for L = O(1 + log(1/u)), but direct listing costs N^O(L).This cost does not establish polynomial dependence jointly on N and u^-1, motivating more efficient graph-family summation.Source: §2.2 · p. 12
3. Mixed p-spin models with p ⩾3
For mixed p-spin models with interaction orders at least three, the method truncates hypergraphs by their used vertices and evaluates the retained sum through local spin averages and inclusion–exclusion. Second-moment bounds control the discarded contribution.
3. Mixed p-spin models with p ⩾3
- For a pure three-spin model, a fixed shape on v vertices with all degrees two contributes O(N^-v/3).The analysis sums over shapes and labels, accounting for edge second moments and external-field factors.Source: §3 · p. 12
3.1. Restricting the number of vertices.
- At fixed vertex count, low total degree yields decay through odd-degree vertices and small field factors, while higher degree yields decay through edge second moments.The proof bounds this trade-off for fixed edge counts, then sums over the counts.Source: §3.1 · pp. 12–13
- The vertex truncation bounds the discarded contribution geometrically up to γN vertices and uses the edge-tail bound beyond that range.Every hypergraph with more than γN vertices has more than γN/P edges.Source: §3.1 · p. 14
3.2. Exact summation on small vertex sets.
- Inclusion–exclusion coefficients cancel repeated counts so each hypergraph using at most k vertices is counted exactly once.The retained sum is formed from the local averages G(S) over sets S with |S| ≤ k.Source: §3.2 · p. 15
- Each G(S) is evaluated by averaging products over spin assignments on S, avoiding expansion into individual hypergraph terms.The procedure enumerates the 2^|S| spin assignments and scans the interaction list.Source: §3.2 · pp. 15–16
4. The SK model
The section develops an approximation for the retained SK graph sum, truncating by branching vertices and edges and evaluating the retained graphs through path-and-cycle decompositions and color coding. It establishes unbiased estimation and bounds the approximation error and operation count.
4.1. Branching vertices truncation.
- Fixed-length cycles and paths can contribute order one, motivating cutoffs on branching vertices and edges; the discarded sum is bounded using branching and edge-tail estimates.The truncation retains graphs with at most D branching vertices and at most L original edges, for D < floor(γN).Source: §4 · p. 17, §4.1 · pp. 19–20
4.2. Augmented graphs.
- Augmenting graphs with vertex 0 turns field factors into edges and gives every vertex even degree; each graph then has a unique path-and-cycle-piece decomposition, with pieces meeting only in A+.The converse characterization requires even degrees throughout and degree at least four at each branching vertex in the augmented graph.Source: §4.2 · pp. 20, 22
4.3. Color-coded summation.
- For a fixed coloring, color coding computes colorful retained graph sums exactly and deterministically, using at most C_alg (N + 2L + 1)^6 16^L 3^(6|A|) operations.It uses 2L colors for vertices outside A, combines pieces only when their colors do not overlap, and averages corrected estimates over independent colorings for the full retained sum.Source: §4.3 · pp. 23–24
- Polynomial multiplication combines colorful path and cycle pieces, enforcing disjoint outside colors, at most L original edges, and the required final degree states.Color and edge-count reductions are applied during multiplication; coefficient selection requires even degree at 0 and even degree at least four at every vertex in A.Source: §4.3 · pp. 26, 28
4.4. Unbiased estimation and cost.
- Each colorful graph contribution is divided by its coloring inclusion probability, correcting its weight even when weights are signed.A graph with m outside vertices is colorful with probability π_{m,2L}; graphs with at most L edges have at most 2L outside vertices, so these probabilities are positive.Source: §4.4 · pp. 29–30
- Averaging R independently corrected color sums for each candidate branching set and summing over candidates gives an unbiased estimate for every fixed disorder realization.The colorings are independent of the disorder and of one another.Source: §4.4 · p. 30
- The estimator’s operation count is at most Calg R (N + 2L + 1)^6 16^L on every finite input and color outcome.Calg is an absolute constant.Source: §4.4 · p. 31
- Averaging over disorder removes covariance terms between different graph weights, even when graphs sharing a candidate branching set have dependent coloring coefficients.The coefficient array is independent of the disorder, enabling the orthogonality argument.Source: §4.4 · p. 31
- The total approximation error separates into truncation errors and random-coloring error, with their cross term vanishing because the retained-sum error has conditional color mean zero.The bound combines Propositions 4.2 and 4.5.Source: §4.4 · pp. 31–32
- The operation count sums the fixed-coloring computation over candidate sets and trials, including the work to compute inclusion probabilities, draw colors, and accumulate corrected entries.Candidate sets are generated using the procedure of Proposition 3.3; the resulting count is given in equation (57).Source: §4.4 · p. 32
5. Proof of the main results
The proof selects truncation parameters to keep the retained-sum computation polynomial, controls the normalized partition function’s lower tail, and combines both bounds to obtain logarithmic accuracy.
5.1. Choosing the cutoffs.
- Cutoffs are chosen to control truncation error while keeping the retained-sum computation polynomial in N and u^-1; the higher-order algorithm is deterministic and the SK algorithm randomized.If truncation is not used, the algorithm evaluates the sum exactly.Source: §5.1 · pp. 33–34
5.2. Lower tail bound for ˆZN.
- Reverse hypercontractivity yields P(bZ_N < z) ≤ C+ z^s + τ_N, controlling the chance that the normalized partition function is too small for logarithmic approximation.On a suitable event determined by coupling magnitudes, the normalized partition function is expressed as a noise average over independent coupling signs.Source: §5.2 · pp. 35–36
5.3. Proof of the main theorem.
- The algorithm approximates log Z_N within ε with failure probability bounded by δ plus the disorder-tail term, using polynomially many operations in N, ε^-1, and δ^-1.The proof bounds the probability of failure using the normalized partition function’s lower tail and the approximation error, then substitutes the chosen parameters into the cost bound.Source: §5.3 · p. 37