WorksPhysics and Astronomy
Computing Classical Partition Functions via Cycle-Space Sampling
Abstract
We present a method for computing thermodynamic properties of classical spin systems by reformulating the partition function as a sum over even subgraphs of the interaction graph. Starting from the high-temperature expansion, we show that the expansion coefficients are determined by the weight distribution of the null space of the binary incidence matrix over , and that this statement holds verbatim for multi-spin interactions once the graph is replaced by a hypergraph. We introduce a Monte Carlo scheme based on the Wang-Landau algorithm that performs a random walk directly in this null space. Because the weight distribution is temperature independent, a single estimate yields the zero-field partition function, and the thermodynamic quantities obtained from its temperature derivatives, at arbitrary temperature. We validate the approach against exact finite-size results on the two-dimensional triangular-lattice Ising model, apply it to the three- and four-dimensional hypercubic Ising models where no exact solution is available, and to the two- and three-dimensional Baxter-Wu models, whose three-spin interactions place them outside the reach of Pfaffian methods. For the two-body models we compare against conventional Wang-Landau sampling in energy space; for the Baxter-Wu models we validate against exact enumeration at the smallest size in each dimension.
Introduction
Partition functions play a central role in statistical mechanics, encoding the complete thermodynamic content of a system. For an interacting spin model with Hamiltonian defined on a set of spins, the canonical partition function at inverse temperature is
where the sum runs over all microscopic spin configurations.
Direct evaluation of is generically intractable because the configuration space grows exponentially with system size. Analytical solutions exist only for a handful of special cases, most notably Onsager’s solution of the two-dimensional Ising model [1, 2, 3], its combinatorial reformulation by Kac and Ward [4], and the triangular-lattice result of Houtappel [5]; a broad survey of the solvable cases is given by Baxter [6]. The scarcity of such cases is not an accident of technique. Computing the Ising partition function is #P-hard in general [7, 8], and Barahona showed that the associated decision problems are NP-hard already for the three-dimensional lattice and for the two-dimensional lattice in a field [9]; Istrail later identified non-planarity as the essential obstruction [10]. In the absence of exact solutions, one typically resorts to approximate methods: Markov-chain Monte Carlo (MCMC) sampling [11, 12], series expansions [13], transfer-matrix methods [14], or renormalization-group approaches [15].
While MCMC methods can efficiently estimate thermal expectation values, they face well-known challenges. First, the estimation of the partition function itself, as opposed to ratios of partition functions or thermal averages, is notoriously difficult in the canonical framework [16]. Second, near critical points or in the presence of frustration, standard local-update algorithms suffer from critical slowing down, requiring increasingly long simulations to decorrelate successive configurations [17, 18]. Extended-ensemble methods address the first difficulty by flattening the sampled distribution—umbrella sampling [19], multicanonical sampling [20], histogram reweighting [21], and replica exchange [22]—and it is to this family that the present work belongs. Cluster algorithms such as Swendsen–Wang [12] and Wolff [23] alleviate this problem for certain unfrustrated models but do not extend straightforwardly to frustrated systems or models with complex interactions, though specialized cluster moves exist for some disordered cases [24] and for particular multi-spin models such as the Baxter–Wu model [25, 26].
A complementary approach is provided by high-temperature series expansions, in which the partition function is expressed as a polynomial whose coefficients count certain subgraphs of the interaction graph [13, 27, 28]. The high-temperature expansion of the Ising model expresses as a polynomial in weighted by the number of even subgraphs of each size; the representation goes back to van der Waerden [29]. The central challenge then shifts from sampling spin configurations to counting combinatorial objects, a task amenable to a different set of algorithmic tools.
In this work we develop this idea into a practical computational framework. The key observation is that the even subgraphs of a graph are in exact bijection with the elements of the null space of the binary incidence matrix of over the field . The high-temperature expansion coefficients are therefore determined by the weight distribution of this null space, that is, the number of null vectors of each Hamming weight. We then introduce a Monte Carlo algorithm that performs a random walk directly in the null space, employing the Wang–Landau scheme [30, 31, 32] to estimate the weight distribution.
Sampling in subgraph space rather than spin space is not a new idea, and the distinctions bear stating precisely. The closest antecedent is the worm algorithm of Prokof’ev and Svistunov [33], which samples the same high-temperature even-subgraph representation by local moves that introduce and displace a pair of odd-degree defects, at a temperature fixed in advance. Jerrum and Sinclair’s fully polynomial randomized approximation scheme for the ferromagnetic Ising partition function runs a Markov chain whose states are subgraphs of the interaction graph rather than spin configurations [34], and deterministic polynomial-time approximations have since been developed for bounded-degree graphs at parameters lying in a zero-free region of the partition function [35]. Independently, the loop calculus of Chertkov and Chernyak writes the exact partition function as a belief-propagation term corrected by a series indexed by generalized loops, subgraphs without dangling ends in which every participating vertex has degree at least two, odd degrees included [36, 37]. For the zero-field pairwise Ising model expanded about the spin-symmetric belief-propagation fixed point, the terms containing odd-degree vertices vanish and the surviving generalized loops are precisely the even subgraphs above. In that case the loop series is indexed by the same combinatorial data whose weight distribution we set out to compute; we gather that data by Hamming weight rather than evaluate it term by term. What distinguishes the present approach from all three is that the walk is performed in the null space itself, using its -linear structure, and that what it returns is the entire temperature-independent weight distribution rather than a quantity tied to one temperature.
Our construction has three motivating features. The weight distribution is temperature independent, so once determined it yields the partition function, and the thermodynamic quantities obtained from its temperature derivatives, at any temperature without further simulation; in this respect it is equivalent to a complete energy-space density of states, from which it can be computed exactly (Sec. IV E). The random walk takes place in a vector space over : the moves are XORs with basis vectors, they preserve the null-space constraint exactly, and they connect any two elements in at most steps, where is the dimension of the null space. Finally, nothing in the derivation refers to the topology or the uniformity of the interaction structure. As we show in Sec. III D, the same identity holds when two-body couplings are replaced by -body couplings, with the incidence matrix of a graph replaced by that of a -uniform hypergraph. This last point carries the method beyond the reach of
Pfaffian techniques, and does so generically rather than through a construction tailored to a particular model; it is the setting of a substantial part of our numerical work. The remainder of this paper is organized as follows. Section II reviews the high-temperature expansion, establishes notation, and derives the multi-spin generalization. Section III sets out the method: the null-space formulation, the bijection with even subgraphs, and the connection to the weight enumerator of the cycle code (Sec. III A); the sampling algorithm (Sec. III B); the thermodynamic observables and the numerical precision required to evaluate them (Sec. III C); complexity and scaling (Sec. III D); and extensions, together with the limitations of the approach (Sec. III E). Section IV presents numerical results for five lattice families. Section V concludes.
High-temperature expansion
The Ising model
We consider the zero-field Ising model on a graph with vertex set () and edge set ():
where . Throughout the main development we take uniform ferromagnetic couplings, ; the inhomogeneous case is discussed in Sec. III E.
Derivation of the expansion
The partition function reads
Using the identity
valid for , the partition function becomes
where .
Expanding the product over edges, each edge contributes either a factor of or a factor of . A given term in the expansion corresponds to a subset :
Spin summation and even subgraphs
To evaluate the inner sum over spins, note that for each vertex the spin appears exactly times in the product, where is the degree of vertex in the subgraph induced by . The spin sum factorizes:
Since
the spin sum is nonzero if and only if every vertex has even degree in . Subgraphs satisfying this condition are the even subgraphs of , equivalently the elements of its cycle space. When the condition is met the spin sum equals .
Denoting by the number of even subgraphs with exactly edges, the partition function becomes
where and (the empty subgraph). The problem of computing is thus reduced to determining the coefficients , a purely combinatorial and temperature-independent task.
Multi-spin interactions
Equation (9) is usually presented as a statement about graphs, but the derivation never uses the fact that an interaction involves exactly two spins. Consider
where is a collection of subsets of , each of arbitrary size. Writing and noting that and hence , the identity (4) applies unchanged,
and expanding the product over gives
where is the number of interaction terms in containing site . The spin sum is again nonzero precisely when every is even, in which case it equals . Equation (9) therefore holds verbatim, with now counting subsets of interaction terms in which every site appears an even number of times.
It follows that the entire apparatus developed below, including the null-space bijection and the sampling algorithm, transfers to multi-spin models with no modification other than the replacement of the graph incidence matrix by the incidence matrix of the corresponding hypergraph. The Baxter–Wu model [38], defined by three-spin interactions on the elementary triangles of the triangular lattice, is the case we treat numerically in Sec. IV D. Pfaffian methods do not apply to it. Transfer matrices do, as for any finite-range model, at a cost exponential in the transverse size, and cluster algorithms have been devised for the Baxter–Wu model specifically, either by freezing one sublattice so that the remaining spins interact through effective two-spin couplings [25] or by building clusters from triangles [26]; these rely on the particular structure of that model.
Equation (9), together with its multi-spin extension, converts the evaluation of into a counting problem that is exact, finite, and independent of temperature: the zero-field partition function, and with it the zero-field thermodynamics of the model, is carried by the integer sequence . This is a reformulation rather than a solution. The objects being counted are exponentially numerous, so direct enumeration is confined to the smallest instances and the coefficients must instead be estimated. How to do so is the problem addressed in the next section.
Method
Our method rests on two ideas. The first is structural: the coefficients of the high-temperature expansion are exactly the weight distribution of the null space of a binary incidence matrix, so counting even subgraphs becomes a question about a linear code. The second is algorithmic: that null space can be explored directly by a random walk whose moves are additions of basis vectors, and its weight distribution estimated by flat-histogram sampling. We take these in turn, then show how the resulting coefficients yield the partition function and its temperature derivatives at every temperature, and what numerical precision that step demands. The section closes with the cost of the scheme, the way its accuracy degrades as systems grow, and the classes of model it does and does not reach.
Null-space formulation
The binary incidence matrix
Let be the incidence matrix over of the interaction structure. Each column corresponds to an interaction term and has nonzero entries in the rows of the sites it couples:
with all arithmetic modulo 2. For two-body models every column has exactly two nonzero entries and is the ordinary incidence matrix of a graph; for -body models every column has nonzero entries and is the incidence matrix of a -uniform hypergraph. Nothing in what follows depends on which of the two cases applies.
Bijection with null vectors
We represent a subset by its characteristic vector . The number of terms of incident on site is
over the integers, so the requirement that every site be covered an even number of times is
i.e., . For a graph, is the cycle space of [39].
The number of terms in equals the Hamming weight , whence
Dimension of the null space
By rank–nullity over ,
and the null space contains exactly elements. For a connected graph , so , the circuit rank of ; with connected components, .
For hypergraphs the rank is not fixed by connectivity alone and must be computed. We record the instance that arises below. For the Baxter–Wu interaction structure on an open triangular patch, and , and
for every , in agreement with direct computation for all . The left null space of is spanned by the two sublattice-parity vectors: each elementary triangle contains one site of each of the three sublattices of the triangular lattice, so the indicator vector of any pair of sublattices annihilates every column, and a propagation argument along the rows of the patch shows that there are no further left null vectors. The nullity equals the number of interior sites, and the null space has a natural geometric basis: the six triangles surrounding an interior site cover that site six times and each of its neighbors twice, so their characteristic vector lies in , and these “hexagon” vectors are linearly independent.
On a torus the counting is different—every site then belongs to six triangles, and the rank deficiency depends on whether the three-sublattice structure is compatible with the boundary identifications, which requires .
Parity of the weight distribution
For multi-spin models of odd interaction order the weight distribution obeys a constraint that, among two-body models, holds only for bipartite graphs.
Lemma. If every interaction term has odd cardinality, then every element of has even Hamming weight; equivalently, for all odd .
Proof. Sum all rows of over . The entry in column of the sum is , so the sum is the all-ones vector . Hence lies in the row space of , which is the dual code of , and therefore for every . □
The hypothesis fails for two-body models, where the row sum vanishes identically and no constraint follows in general. Bipartite graphs are the exception, since all their cycles are even and their cycle spaces contain only even-weight vectors; the cycle code of the triangular lattice, by contrast, does contain odd-weight words, the shortest being the weight-three triangles. For the Baxter–Wu model, by contrast, half of the histogram bins are empty by construction. We use this in two ways: the sampler bins only even weights, halving the number of bins and hence the work required for the histogram to flatten, and the vanishing of the odd- coefficients serves as a check that the basis and the walk have been implemented correctly.
A related observation concerns the top of the support. The all-ones vector lies in precisely when every site is covered an even number of times. On a periodic Baxter–Wu lattice every site belongs to six elementary triangles and the support therefore extends to exactly. On the open patches simulated below this fails: boundary sites belong to one, two, or three triangles, the all-ones vector is not a null vector, and the maximum Hamming weight in the null space falls short of .
The shortfall can be computed exactly. Writing a null vector as a combination of the hexagon generators, a triangle carries a one precisely when an odd number of its corners is an interior site selected by that combination, so is the maximum, over subsets of the interior sites, of the number of triangles with an odd number of corners in . We solve this optimization exactly for every , writing it as a maximization over the binary generator coefficients with one parity constraint per triangle and using the constraint-programming solver CP-SAT of OR-Tools [40], which terminates only once the objective value is matched by a proven upper bound. The result is
for and ; is exceptional, with rather than 22, in agreement with complete enumeration of its null vectors. We have no proof that Eq. (19) holds for all . Over the certified range the shortfall is a boundary term, so approaches unity from below. We compare Eq. (19) with the observed support edges in Sec. IV D.
Computing a basis for the null space
A basis for can be computed by Gaussian elimination in operations, and the sparsity of (two nonzero entries per column for graphs, for -uniform hypergraphs) reduces this substantially in practice; for very large instances the sparse methods of Wiedemann [41] are preferable.
For graphs one may instead avoid elimination entirely: given a spanning tree , each non-tree edge defines a unique fundamental cycle consisting of together with the tree path joining its endpoints, and the characteristic vectors of these cycles form a basis for [39]. We use this construction for all two-body models reported below and Gaussian elimination for the Baxter–Wu models.
Connection to coding theory
The null space is a binary linear code of length and dimension ; for a graph it is the cycle code of [42], and its dual (the row space of ) is the cut-space code. Such graphical codes were introduced and studied in the 1960s by Bredeson and Hakimi [43, 44] and revisited later by Jungnickel and Vanstone [45]; for a connected graph the cycle code has parameters , where the minimum distance is the girth of [46]. The girth therefore fixes the smallest with , which is three for the triangular lattice and four for the square lattice, and supplies a further exactly known coefficient against which an estimate can be checked. In this language the are the coefficients of the weight enumerator polynomial,
and the reduced partition function is a section of it, .
Three consequences follow. The MacWilliams identity [42] relates the weight enumerator of the cycle code to that of the cut-space code, which is a duality relation for the partition function and a nontrivial constraint on any estimate of the . Coding-theoretic bounds of Plotkin and linear-programming type constrain the support and shape of the weight distribution. And the literature on weight-enumerator computation for structured codes is a source of specialized algorithms for graphs with symmetry.
The identification also sets expectations about worst-case difficulty. Computing the weight distribution of a general binary linear code is intractable: the associated decoding and minimum-weight problems are NP-hard [47], computing the minimum distance is NP-hard [48], and the wider complexity landscape is surveyed by Barg [49]. Cycle codes of lattice graphs are highly structured rather than generic, so these results do not preclude efficient treatment of the cases of interest, but they do rule out any general-purpose polynomial-time algorithm, consistently with the hardness results for the Ising partition function noted in § 1.
Monte Carlo sampling of the null space
Random walk on the null space
Let be a basis for . Every null vector has the unique representation
where is addition modulo 2. The elementary move selects a basis vector uniformly at random and applies
flipping the coefficient and preserving the null-space constraint exactly. The chain is irreducible, since any null vector is reachable from any other in at most moves. Because every move flips exactly one coefficient of the basis expansion, the bare walk is periodic with period two; the acceptance step of Sec. III B 2 introduces rejections that remove the periodicity (equivalently, a lazy step may be added). Under uniform selection the uniform distribution over the null vectors is stationary.
The 1/t Wang–Landau estimator
Flat-histogram sampling of the Hamming weight is achieved with the Wang–Landau algorithm [30, 50]. We use the variant [31, 32], which eliminates the saturation of the error that afflicts the original protocol [51], together with a discovery-and-restart rule adapted to the fact that the support of the weight distribution is not known in advance. The symbol in the established name of that variant refers to simulation time; to avoid a collision with we write the simulation clock as throughout.
We maintain , an estimate of the logarithm of the weight distribution, a visited flag , and a global discovery flag , all indexed by . A proposed move from weight to weight is accepted with probability
Since the proposal is symmetric, for a frozen estimate this rule satisfies detailed balance with respect to the distribution , which becomes the flat-histogram target as . The adaptive process itself, in which changes after every move, is not a reversible chain with a fixed target; its convergence rests on the vanishing of the modification factor [31, 32]. The estimate at the resulting weight is incremented by the modification factor , and the visited flag is set.
The protocol rules are as follows; Algorithm 1 states them in full. The walk starts from the empty subgraph, , so that the weight used for normalization is discovered from the outset. If the proposed move reaches a weight that has never been seen ( false), the support of the distribution has just been extended and every accumulated is biased relative to it; we therefore set true, move the walker to , and restart the estimate: and are reinitialized, is reset to unity, the move counter is reset, and the run returns to its first phase. In the first phase, whenever every discovered weight has been visited since the last reset, is cleared and . Writing for the number of trial moves divided by the number of discovered weights, once the run enters its second phase, in which is set to after every move and the visited flags are no longer used. A weight first encountered in the second phase triggers the same restart. The run terminates only once it is in the second phase and , so the first phase may run beyond the nominal budget (Sec. III D). On termination is normalized by and weights never discovered are assigned . Discovery is not completeness: the condition that every discovered weight has been visited does not certify that every accessible weight has been found, and the exactly known support edges and the identity serve as a posteriori checks of that. In the second phase the statistical error decreases as without saturating [32]. Flat-histogram methods nonetheless carry an intrinsic limitation independent of the update schedule. For walks that change the sampled variable by a bounded amount per step, the round-trip time grows at least as the square of the number of bins, and faster when the walk meets bottlenecks [52]. Basis moves can change the weight by as much as , so that bound does not carry over verbatim, but bottlenecks in the weight coordinate slow the null-space walk in the same way. Diagnostics based on the spectral gap of the transition matrix in the sampled variable [53] and massively parallel implementations [54] apply directly to the null-space walk, and we return to both in § 2.1.
The estimate is determined only up to an additive constant in , which is fixed by the exactly known value . Where additional coefficients are known analytically, for instance the smallest nonzero weight and its multiplicity on a regular lattice, they provide an independent check; we use for this purpose in Sec. IV.
Efficient weight-change computation
The cost per step is dominated by evaluating the Hamming-weight change. From
where is the bitwise AND, we have . Since is precomputed, the cost is that of the inner product , evaluated in time with word-level operations ( the machine word size, typically 64). For sparse basis vectors one may instead iterate over the support of , at cost , which is the better choice for fundamental-cycle bases on large lattices.
Basis preprocessing
Mixing depends on the structure of the basis. If many basis vectors have overlapping supports the induced weight changes are correlated and the walk decorrelates slowly. The fundamental-cycle basis is a natural default, since fundamental cycles of a breadth-first spanning tree have localized support and small weight. Alternatively one may apply random row operations to a given basis to decorrelate supports, at the cost of increasing and hence the per-step cost.
Thermodynamic observables
Once is known, the zero-field partition function and the thermodynamic quantities obtained from its temperature derivatives follow analytically as functions of temperature.
Partition function and free energy
Defining the reduced partition function
so that , the Helmholtz free energy is
Internal energy and specific heat
From , using and ,
Algorithm 1 1/ Wang–Landau sampling in the null space. The clock is the number of trial moves per discovered weight.
Require: Null-space basis ; move budget
; {empty subgraph}
;
; ; ; phase
while phase or do
Choose uniformly at random
;
if is false then
; ;
; ; ; ; phase {restart}
else
if then
;
end if
;
end if
; {moves per discovered weight}
if phase then
if true for all discovered then
clear ;
end if
if then
phase
end if
end if
if phase then
end if
end while
Normalize: for discovered
return if , else , for
with . The specific heat, , is
The entropy follows from .
Numerical evaluation
Equations (26)–(28) are innocuous as written but demand care in practice. The dynamic range of the is enormous: for the three-dimensional lattices of Sec. IV C the weight distribution spans some five hundred orders of magnitude, far outside double precision. All sums over the are therefore evaluated in arbitrary-precision arithmetic and converted to log-space only at the end.
Two features make the evaluation benign despite the dynamic range. All are nonnegative and, for ferromagnetic couplings, , so every term in , , and is positive and no cancellation occurs; the sums are as well conditioned as their magnitudes allow. And because the enter only through the ratios and , an error in the overall normalization of cancels identically in and . What propagates into the observables is not the normalization but the error in the shape of the distribution, which is why we report relative errors bin by bin rather than only for the total. The specific heat is more exposed to such errors than the energy. Its second and third terms in Eq. (28) combine to , a difference of moments of the thermal weight distribution , and where is small compared with the individual moments, as at low temperature, relative errors in the shape of are amplified. This statistical amplification persists even when the sums are evaluated with sufficient numerical precision.
The situation for antiferromagnetic couplings is addressed separately in Sec. III E 3.
Magnetization and susceptibility
In an external field, the partition function acquires additional structure. The zero-field susceptibility follows from with . For the two-body models in zero field, and for the two-dimensional Baxter–Wu patches, whose sublattice-pair reversals Eq. (18) leave invariant and together flip every site, on any finite lattice. This does not carry over to the three-dimensional Baxter–Wu system, whose incidence matrix has full row rank (Appendix B) and which therefore has no nontrivial spin-reversal symmetry. There products of interaction terms can reduce to a single spin; for the three faces of a tetrahedron that share a vertex , , so acquires a nonzero value at every finite temperature. In either case, incorporating or requires tracking subsets in which one or two designated sites have odd incidence, that is, a coset of rather than the null space itself. We defer this to future work.
Computational complexity and scaling
Null-space dimension and graph structure
The dimension controls both the size of the sampling space () and, through , the number of histogram bins (). For a regular lattice of coordination number with two-body couplings and periodic boundaries, and
TABLE I. Null-space dimension for the lattice families considered. is the coordination number for two-body models and the number of interaction terms per site for Baxter–Wu. The last column is the ratio of sampling-space dimension to spin-space dimension in the thermodynamic limit.
| Lattice | |||
| Square (2D) | 4 | 1 | |
| Triangular (2D) | 6 | 2 | |
| Simple cubic (3D) | 6 | 2 | |
| Hypercubic (4D) | 8 | 3 | |
| Baxter–Wu (2D) | 6 | 1 | |
| Baxter–Wu (3D) | 24 | 7 |
Table 1.
For the open lattices simulated in Sec. IV the missing boundary bonds reduce both counts,
leaving the leading behavior unchanged. Table I collects the relevant cases; the ratios quoted there are thermodynamic-limit ratios. The entry that matters for interpreting our results is the comparison in the last column: is the asymptotic ratio of the dimension of the sampling space to that of the space of spin configurations. It equals unity for the two-dimensional square lattice and for the two-dimensional Baxter–Wu model, and exceeds it in every other case listed, reaching for the three-dimensional Baxter–Wu system. A method that samples the null space therefore operates in a space of higher dimension than conventional energy-space Wang–Landau in most of the geometries treated here, and a corresponding cost is to be expected.
Cost per Monte Carlo step
Each proposed null-space update costs when implemented with word-level operations, or when the support of is traversed sparsely. By comparison, a single-spin update in the energy-space implementation costs , where is the number of interaction terms incident on spin , and hence for the bounded-degree lattices considered here. A null-space update may alter interaction variables simultaneously, so the two types of updates are not directly comparable on a move-for-move basis. Their relative efficiency must instead be assessed using a common computational budget together with autocorrelation or histogram round-trip measurements.
The numerical comparisons reported in Sec. IV were performed as follows. The null-space simulations used the nominal stopping parameter and were run on USC’s high-performance computing cluster, whereas the energy-space simulations used and were run on a workstation. Moreover, in our implementation the adaptive first stage of the Wang–Landau procedure is allowed to continue until its discovery and histogram conditions are satisfied before the stopping condition becomes operative. Consequently, several energy-space runs performed more than trial moves during this first stage, and the actual number of moves varied with the model and system size. The comparisons below should therefore be interpreted as checks of consistency and convergence under the computational budgets used, rather than as controlled measurements of the relative computational efficiency of the two methods. A cost-normalized comparison at matched wall-clock time remains necessary before any efficiency advantage can be claimed.
Convergence
Convergence depends on the number of histogram bins, , and on the dynamic range of across them. For models of odd interaction order the lemma of Sec. III A 4 halves the effective bin count at no cost. In the phase the statistical error falls as without the saturation of the original protocol [32]. The practical difficulty at large system size is not the asymptotic rate but the tails. The extreme weights and , at the two ends of the support, have very small . In a converged flat-histogram ensemble they are visited as often as any other bin, but the walk reaches them only through long excursions from the bulk, and the resulting round-trip times leave their relative error orders of magnitude worse than that at the mode. This is visible in every relative-error panel in Sec. IV. How these errors reach the observables depends on temperature through . At high temperature, , the small- coefficients dominate; as the temperature is lowered the weight moves toward the combinatorial bulk of the distribution, since , and the high-weight tail is suppressed by at every temperature. At low temperature the errors in are therefore those of the bulk coefficients, amplified as described in Sec. III C 3, rather than those of the small- tail.
Comparison with other methods
Exact enumeration of all null vectors is feasible only for . Transfer-matrix methods compute exactly for quasi-one-dimensional systems at cost exponential in the width. Pfaffian methods of Fisher–Kasteleyn–Temperley type [55, 56, 57] give polynomial-time exact answers for planar graphs and do not extend beyond them [9, 10].
Approximation schemes with guarantees exist in the ferromagnetic case: the Jerrum–Sinclair chain is an FPRAS for any ferromagnetic Ising system [34], and for bounded-degree graphs deterministic approximations follow from zero-freeness arguments at parameters in side a zero-free region [35]. These carry rigorous error bounds that our scheme does not, but they estimate at a fixed temperature rather than producing the temperature-independent , and they are formulated for two-body couplings. Multicanonical and simulated tempering [58] methods, and conventional Wang–Landau sampling in energy space, operate in spin-configuration space and estimate the density of states rather than . For uniform couplings the two sequences are related by an exact linear transform [Eq. (37) and its inverse], so the distinction lies in the space that is sampled, not in the information obtained. Energy-space Wang–Landau sampling is our baseline for the two-body models of Sec. IV.
Extensions and limitations
Inhomogeneous couplings
For edge-dependent couplings , defining ,
Binning by Hamming weight no longer suffices, since null vectors of equal weight carry different products. One remedy is to introduce the continuous variable and perform Wang–Landau sampling with respect to , in direct analogy with energy-space Wang–Landau. This sacrifices the temperature independence that motivates the method, since depends on through the , and we have not implemented it.
Potts and clock models
The -state Potts model admits a high-temperature expansion in which the even-subgraph condition is replaced by a divisibility condition [59]. This suggests replacing with , but a complete extension requires more than the substitution: oriented edges carrying -valued currents, a conservation constraint at every site given by the kernel of the oriented incidence matrix, and weights given by the character-expansion coefficients of the interaction, which for clock models depend on the current and not only on whether it vanishes. For composite the kernel is a module rather than a vector space. We have not developed this extension and regard it as prospective.
Sign of the couplings
For two-body models the restriction to is not a matter of convenience. For one has , and whenever the cycle code contains odd-weight words, becomes an alternating sum over coefficients that span hundreds of orders of magnitude. The result is catastrophic cancellation: the value of can be smaller than its largest term by a factor comparable to , so extracting it requires the to a relative precision that no sampling scheme can supply at large . This is structurally the same obstruction that afflicts fermionic and frustrated quantum Monte Carlo [60], where the cost of resolving a small average sign likewise grows exponentially. Deciding whether such a problem can be evaded by a change of basis is itself computationally hard [61], though useful easing is sometimes possible [62, 63].
On bipartite lattices the difficulty is removable, since the gauge transformation on one sublattice maps the antiferromagnet onto the ferromagnet; equivalently, the cycle code then contains only even weights and no negative term survives. For uniform antiferromagnetic two-body couplings on non-bipartite lattices, which is to say precisely the geometrically frustrated cases, it is not.
Models in which every interaction has odd order are free of the difficulty for either sign of a uniform coupling. Since for odd (Sec. III A4), and every surviving term is nonnegative. Physically, global spin reversal changes the sign of every odd-order interaction and maps uniform onto uniform ; both Baxter–Wu models are therefore sign free for either sign of . More generally, for couplings of uniform magnitude and signs , a spin-sign gauge removes every negative coupling precisely when
is solvable, that is, when lies in the row space of , or equivalently when for every . Uniform antiferromagnetic couplings correspond to , and the bipartite and odd-order cases above are instances in which lies in the row space. We make no claim that the present method addresses frustration, and all results below are ferromagnetic. Whether a resummation of that exploits the structure of the cycle code can control the cancellation is an open question that we regard as worth pursuing.
Numerical results
We report results for five lattice families, chosen to separate three distinct questions: whether the sampler reproduces exactly known answers, how it behaves where no exact answer exists, and whether it functions at all for interactions beyond two-body. For the two-body models the baseline for comparison is conventional Wang–Landau sampling of the density of states in spin-configuration space, run with the same protocol and implemented in the same code base. We refer to the two schemes as null-space and energy-space sampling.
| System | ||||
| Triangular 2D | 4 | 16 | 33 | 18 |
| 8 | 64 | 161 | 98 | |
| 12 | 144 | 385 | 242 | |
| 16 | 256 | 705 | 450 | |
| Cubic 3D | 4 | 64 | 144 | 81 |
| 6 | 216 | 540 | 325 | |
| 8 | 512 | 1344 | 833 | |
| 10 | 1000 | 2700 | 1701 | |
| Hypercubic 4D | 2 | 16 | 32 | 17 |
| 3 | 81 | 216 | 136 | |
| 4 | 256 | 768 | 513 | |
| 5 | 625 | 2000 | 1376 | |
| Baxter–Wu 2D | 5 | 25 | 32 | 9 |
| 10 | 100 | 162 | 64 | |
| 15 | 225 | 392 | 169 | |
| 20 | 400 | 722 | 324 | |
| Baxter–Wu 3D | 3 | 27 | 88 | 61 |
| 4 | 64 | 270 | 206 | |
| 5 | 125 | 608 | 483 | |
| 6 | 216 | 1150 | 934 |
Table 2. Systems studied. All lattices carry open boundary conditions. is the number of sites, the number of interaction terms, and the null-space dimension: for the connected two-body graphs, for the two-dimensional Baxter–Wu patches Eq. (18), and for the three-dimensional Baxter–Wu systems, whose incidence matrices have full row rank at every size simulated Appendix B.
Setup
Table Table II lists the systems, their sizes, and the resulting null-space dimensions. All simulations reported in this work—null-space and energy-space alike—use open (free) boundary conditions; couplings are uniform and ferromagnetic, . Bases are constructed from breadth-first fundamental cycles for the two-body models and by Gaussian elimination for Baxter–Wu. Each data point is the mean of 20 independent runs with distinct seeds. The number of moves performed by the algorithm depends on both and the number of states discovered for that model and size; the relative standard error (RSE) plotted in the lower panels of the figures is the standard error over these runs divided by the mean, expressed as a percentage. Where an exact result is available we additionally plot the relative deviation of the mean from it.
The largest null spaces here, for the three-dimensional lattice and in four dimensions, correspond to and configurations respectively. For the two-dimensional Baxter–Wu patches , the number of interior sites Eq. (18). The three-dimensional Baxter–Wu geometry is defined in Sec. IV D and Appendix B; there and, because the site–face incidence matrix has full row rank at these sizes, . The entries of Table II for that system are obtained from the lattice generator and confirmed by direct row reduction of , independently of the sampled histograms.
Validation against exact results
The two-dimensional triangular lattice is planar, so its finite-size partition function is available exactly, and it provides an exact reference at every simulated size.
The reference coefficients are obtained, at every , from a Kac–Ward-type directed-walk determinant [4, 64] evaluated in exact arithmetic. One builds the transfer matrix on directed edge states of the open patch, whose nonzero entries are turning-angle phases and hence twelfth roots of unity, and uses
so that the generating polynomial of the is recovered as the exact polynomial square root of a characteristic polynomial. The construction and its exact evaluation are given in Appendix A.
Two features render this reference reliable for the present purpose. First, is constructed on precisely the same finite graph—the open patch with bonds and no periodic identification—from which the sampled null-space bases are built, so the comparison is not confounded by a boundary mismatch. Second, the resulting coefficients satisfy the two independent identities , the number of elementary triangles of the patch, and , which is the order of for a connected graph. The second identity is sensitive to the boundary condition—evaluated against the nullity of the corresponding periodic lattice it would fail by many orders of magnitude—and therefore guards against a boundary mismatch as well as an arithmetic error. Neither identity determines the graph uniquely, since distinct graphs can share these invariants, so they are consistency checks rather than a certificate of the geometry. For the same coefficients were checked against complete enumeration of .
Figure 1 shows the estimated weight distribution. The agreement with the exact values is visually complete on the logarithmic scale of the top panel, which spans some 135 decades at . The informative panels are the lower two. At the relative standard error is of order or below across the whole support. At it rises from about at the mode to at the lower edge of the support and a few tenths of a percent at the upper edge. At and 16 it is about at the mode, a few percent at the lower edge, and reaches tens of percent near the upper edge. The relative deviation from the exact result tracks the standard error closely, as is expected of an estimator dominated by variance rather than by a systematic bias that would persist across seeds. The degradation into the tails is the effect discussed in Sec. III D. Through the low-weight tail enters the observables most strongly at high temperature, while the high-weight tail, where the errors are largest, is suppressed by at every temperature.
Figure 1. Weight distribution of the cycle code of the triangular lattice. Top: mean estimated against normalized Hamming weight , with the exact enumeration shown as a dotted black curve. Middle: relative standard error over independent runs. Bottom: relative deviation of the mean from the exact value. The horizontal axis of all three panels is . The error is smallest at the mode and grows by several orders of magnitude into both tails, where the coefficients are smallest and the walk reaches them only through long excursions from the bulk.
Figure 2 propagates the weight distribution into the specific heat through Eq. (28) and compares against energy-space Wang–Landau on the same lattices. Both reproduce the exact finite-size curves, including the growth and shift of the peak with . The deviation panels show cycle-space errors below 1% over most of the temperature range, exceeding it at and 16 only near the ends of the range shown, where they reach a few percent, with the characteristic downward spikes where the deviation changes sign. The energy-space estimator is somewhat better behaved, holding below about 0.5% throughout. We regard this as establishing correctness rather than superiority: on a lattice where both methods apply and (for the open patch ), no accuracy argument favors the null space, and we advance none. The corresponding mean-energy comparison is deferred to Figure 6 in the Appendix, as is the energy-space density of states, Figure 9.
Figure 2. Specific heat per site of the triangular-lattice Ising model from cycle-space sampling (left) and from conventional Wang–Landau sampling in energy space (right), each against the exact finite-size result. Lower panels show the relative deviation from exact. The two schemes agree with the exact answer at comparable accuracy, with the energy-space estimator somewhat more uniform across temperature.
Figure 6. Mean energy per site of the triangular-lattice Ising model from cycle-space sampling (left) and energy-space sampling (right), each against the exact finite-size result, with relative deviations below.
Figure 9. Energy-space densities of states obtained by conventional Wang–Landau sampling, for the triangular (top left), simple cubic (top right), and four-dimensional hypercubic (bottom) lattices. These are the baselines used in Figure 2, Figure 3, Figure 6, and Figure 7.
Three and four dimensions
Neither the three- nor the four-dimensional Ising model is exactly solvable, and we did not compute exact finite-size references (which would be feasible at the smallest sizes, e.g. the configurations of the four-dimensional system), so here the two estimators check each other rather than an external reference. Figure 3 shows the specific heat.
Figure 3. Specific heat per site of the Ising model on the simple cubic lattice (left) and the four-dimensional hypercubic lattice (right). Solid curves are cycle-space estimates, dashed curves energy-space estimates; lower panels give the relative standard error of each. No exact finite-size reference was computed for either case. The cycle-space curve in the left panel has not converged: its shoulder near and the two spurious maxima near 4.2 and 4.9, absent from the energy-space result, are convergence artifacts and carry no physical content. It is shown to document the failure mode and is excluded from the discussion of the physics.
At the smaller sizes the two schemes agree closely: the , 6, and 8 cubic-lattice curves lie on top of one another, and the peak position and height evolve as expected toward the bulk critical temperature; with open boundaries the finite-size corrections include a surface term, so the approach to the bulk values is slower than for periodic lattices. The most precise Monte Carlo determination gives , that is [65, 66]. The four-dimensional curves behave similarly at , 3, 4; there the specific-heat singularity is marginal and its precise character remains the subject of large-scale numerical work [67, 68], so we make no claim about the peak shape beyond its size dependence.
The relative standard errors in the lower panels of Figure 3 are substantial for both estimators: roughly 10–30% above , rising to and beyond toward , with the cycle-space values the larger. The agreement of the mean curves at , 6, and 8 described above should be read with uncertainties of this size in mind.
At the largest size in each case the cycle-space estimate degrades visibly, and in three dimensions it fails. The cubic curve develops a shoulder near , a spurious secondary maximum near 4.2, and a further bump near 4.9, none of which the energy-space result reproduces; the corresponding relative standard error panel shows sharp excursions to – at and 2.8. These are convergence artifacts, not physical features: they appear only at the size where is largest, and they are not stable across seeds. We therefore do not regard the cycle-space curve as a result, and it should not be read as one; the converged cycle-space data in three dimensions are those at , 6, and 8. We retain the curve in Figure 3 only to make the failure mode visible, since suppressing it would misrepresent the present state of the method. At nullities of order the protocol has not converged at the budget used, and establishing convergence at these sizes requires either a longer budget or the improvements sketched in § 2.1. In four dimensions the mean curve agrees with the energy-space result, but its error panel shows the same pattern of sharp excursions, near and 2.7.
Across the range where both converge, the relative standard error of the energy-space estimator is consistently below that of the cycle-space estimator, typically by a factor of about two. This is the expected consequence of Table I: at and the null space is asymptotically two and three times the dimension of the spin space ( and 2.20 at the sizes simulated), and the sampler incurs the corresponding cost. Temperature independence does not distinguish the two methods here. A complete is equally temperature independent, , and for the uniform discrete models studied here its energy discretization is exact, so neither estimate needs to be recomputed to change the temperature. What distinguishes cycle-space sampling is the representation itself: the moves, the geometry of the space explored, and the resulting numerical behavior. In these geometries, at the budgets used, that representation offers no accuracy advantage, and we have not attempted a cost-normalized comparison.
The corresponding mean-energy and weight-distribution figures are collected in the Appendix as Figure 7 and Figure 8.
Figure 7. Mean energy per site for the simple cubic (left) and four-dimensional hypercubic (right) Ising models. Solid curves are cycle-space estimates, dashed curves energy-space estimates, with relative standard errors below.
Figure 8. Weight distributions of the cycle codes of the simple cubic (left) and four-dimensional hypercubic (right) lattices, with relative standard errors below, plotted against the normalized Hamming weight . The distributions span roughly 500 and 400 decades respectively at the largest sizes.
Multi-spin interactions: the Baxter–Wu models
The Baxter–Wu model, introduced by Wood and Griffiths [69] and solved exactly by Baxter and Wu [38, 70], places a three-spin coupling on every elementary triangle of the triangular lattice. It is self-dual, with the same critical temperature as the square-lattice Ising model, , and belongs to the universality class of the four-state Potts model, with and ; unusually for that class, its leading singularities carry no logarithmic factors [38, 71]. Its ordered phase is fourfold degenerate, reflecting the three-sublattice structure of the triangular lattice, the same structure that underlies the rank result of Eq. (18).
The Pfaffian methods that solve planar two-body models have no analogue here. Cluster algorithms do exist, but they are built on the particular structure of this model: Novotny and Evertz freeze one sublattice, leaving effective two-spin couplings on the other two [25], and Velonakis and Martinos construct clusters from triangles [26]. Energy-space Wang–Landau sampling applies to multi-spin models as well, and has been used for the three-dimensional model [72]. By Sec. II D the cycle-space construction applies without modification and without model-specific input.
a. The three-dimensional system. “Baxter–Wu 3D” is not a standard model and admits more than one natural definition, so we state ours explicitly. We use an open finite patch of the three-dimensional Baxter–Wu geometry of Jorge, Ferreira and Caparica [72], in which each bulk spin has twelve nearest neighbors and belongs to twenty-four triangular faces, and one three-spin interaction is placed on every elementary triangular face of the nearest-neighbor graph. Sites are labeled with , so , and the twelve nearest neighbor displacements of an interior site are
with . A neighbor is retained only when all of its coordinates remain in ; no wraparound is applied. Because the layer offsets above and below a given plane are negatives of one another, the stacking is , that is, face-centered cubic; the lattice is described as close packed in Ref. [72], and a translation-invariant twelve-vector neighbor set of this kind is necessarily the face-centered variant. The bulk geometry is thus the same as theirs, while our finite systems differ by the use of free rather than periodic boundaries. Writing for the resulting nearest-neighbor graph, the interaction set is , the three-cycles of , which are exactly its elementary triangular faces, and .
by plane family (Appendix B) gives
and direct row reduction shows that the site–face incidence matrix has full row rank for , so , the values listed in Table II. The two-body edges of serve only to define the faces; they are not themselves interaction terms. The count that enters the partition function, and hence the prefactor in Eqs. (27) and (28), is the number of faces, Eq. (35). The same caution applies in two dimensions, where is the number of triangles and not the number of bonds of the underlying triangular patch. No exact result is available for the three-dimensional model in the thermodynamic limit; for periodic lattices with , Ref. [72] reports a first-order transition at , with a specific-heat maximum scaling as .
b. Specific heat. Figure 4 shows the specific heat for the two-dimensional model at and for its three-dimensional counterpart at . The two-dimensional peaks sharpen with system size and drift upward. At , where the weight distribution is known exactly (Sec. IV E), the maximum is at ; at the larger sizes the maxima are , , and , at , , and , for , , and respectively. The drift is toward the exact from below, as expected of a finite-size specific-heat maximum in a model with , although the approach is slow—open boundaries contribute a surface correction to the finite-size shift—and we have not attempted a finite-size scaling extrapolation. The three-dimensional model shows a markedly larger and narrower peak. At , again exactly known, the maximum is at ; it moves to , , and , at , , and , for , , and . The growth of the maximum is far steeper than in two dimensions, and the peak is accompanied by a correspondingly steep rise in the mean energy (Figure 10), which would be consistent with the first-order transition reported for the periodic system [72]. Figure 4 shows means over the 20 runs without uncertainty bands, and we have not yet quantified the run-to-run scatter of these maxima. This matters most at , whose nullity lies between those at which the cubic-lattice runs converged () and failed (); the peak height should accordingly be regarded as provisional. The direction of the drift is consistent with the periodic-lattice value of Ref. [72], but the sizes accessible here are far too small, and the boundaries too influential, to support an extrapolation or to resolve the order of the transition.
Figure 4. Specific heat per site of the two-dimensional (left) and three-dimensional (right) Baxter–Wu models from cycle-space sampling. These models have three-spin interactions, so the sampling space is the null space of a hypergraph incidence matrix. No energy-space baseline was run for these systems.
Figure 10. Mean energy per site for the two-dimensional (left) and three-dimensional (right) Baxter–Wu models from cycle-space sampling. Both are monotonically increasing in temperature and approach the ground-state value at the low-temperature end, as required. The steep rise of the curve near in the right panel coincides with the specific-heat maximum of Figure 4.
Figure 5 shows the underlying weight distributions, plotted over even weights only in accordance with the lemma of Sec. III A 4. The curves terminate at , , , and for , , , respectively, below . This is a property of the open-boundary code, not a shortcoming of the sampler. As discussed in Sec. III A 4, boundary sites belong to fewer than six triangles, so the all-ones vector is not a null vector and the support does not extend to . Exact enumeration at (, ) gives the support : the minimum nonzero weight is six—the hexagon of any interior site—and the maximum is with . At the larger sizes Eq. (19) gives , , and for , , , that is , , and , each certified optimal as described in Sec. III A 4. The observed terminations coincide with these values at every size, so the sampler reaches the true top of the support, and the shortfall relative to is the boundary effect of Eq. (19) rather than a failure to explore the tail.
Figure 5. Weight distributions for the two-dimensional (left) and three-dimensional (right) Baxter–Wu models, with relative standard errors below, plotted against the normalized Hamming weight . Only even weights are shown, since vanishes identically for odd in a model of odd interaction order (Sec. III A 4). The curves terminate below ; for the open-boundary codes the support itself ends below (exact enumeration at gives ), as discussed in the text.
The largest-weight coefficients remain the smallest and the least well resolved, but their influence on the thermodynamics is mild: they enter multiplied by with , so the observables are controlled by the well-sampled bulk of the distribution.
No energy-space baseline was run for either Baxter–Wu system, so the mutual comparison between representations that anchors Secs. IV B and IV C is not available here. In its place we validate the smallest system in each dimension directly against complete enumeration, in Sec. IV E. The corresponding mean-energy curves appear as Figure 10 in the Appendix.
Direct validation against exact enumeration
Both Baxter–Wu systems admit an exact reference at their smallest simulated size, which we use to test the sampler in the multi-spin setting as the triangular lattice does in the two-body setting.
In two dimensions, has , so the entire null space can be enumerated: all elements of give
all other coefficients vanishing. The multiplicity is the number of interior-site hexagons, consistent with the geometric basis of Sec. III A.
In three dimensions the null space at is far too large to enumerate (), but the space of spin configurations is not: , so all configurations can be swept directly to give the exact density of states . The weight distribution then follows from the inverse of the high-temperature transform,
where is the number of configurations with of the interaction terms satisfied, so that . The transform is invertible: setting ,
so for uniform couplings the density of states and the weight distribution carry the same information. Expanding the right-hand side of Eq. (37) in exact integer arithmetic yields the complete sequence for the system. It reproduces every structural prediction of Secs. III A and III A 4 independently of any simulation: all are nonnegative integers, for every odd as required by the lemma of Sec. III A 4, and exactly, confirming the nullity entered in Table II. The support runs from to , with and .
| System | ||||
| Triangular 2D | 16 | 450 | 311.9162 | 311.9 |
| Cubic 3D | 10 | 1701 | 1179.0434 | 1179.0 |
| Hypercubic 4D | 5 | 1376 | 953.7705 | 953.8 |
| Baxter–Wu 2D | 20 | 324 | 224.5797 | 224.6 |
| Baxter–Wu 3D | 6 | 934 | 647.3995 | 647.4 |
Table 3. Consistency check of the estimated weight distributions against the exact identity . The estimated logarithmic totals are quoted to the precision available in the run summaries.
Propagating Eqs. (36) and (37) through Eqs. (27) and (28) gives exact finite-size thermodynamics for both systems. In two dimensions at the specific heat peaks at at ; in three dimensions at it peaks at at . The sampled estimates reproduce both references to better than 0.01% in and in across the whole temperature range shown.
Two features of the exact reference are worth recording, since both are readily mistaken in a multi-spin model. The ground-state energy is with the number of interaction terms, so at every temperature: for two-dimensional and for three-dimensional . And , so the mean energy is nondecreasing in temperature and the specific heat is nonnegative. Both are violated if the prefactor in Eqs. (27) and (28) is taken to be the number of two-body bonds of the underlying nearest-neighbor graph rather than the number of three-spin terms, which is why we state the distinction explicitly in Sec. IV D. Both inequalities are inexpensive to evaluate and worth imposing on any output of the method.
Consistency checks
Independent of any reference solution, the total must equal with given by Table II. Because the total is dominated by the coefficients near the mode, this is a one-parameter check on the overall normalization and shape of the distribution. Table III collects the results: in every case agrees with to the precision displayed. At one decimal place in the logarithm this constrains the total only to within about 5%, and it is blind to errors in the shape that leave the total unchanged, so it is a coarse normalization check rather than a precise accuracy certificate. The check is nonetheless unforgiving of any gross mismatch between the interaction structure assumed in the analysis and the one actually simulated—evaluated against the nullities of the corresponding periodic lattices, for example, the same totals would appear to fall short by factors of to —so it doubles as a check on the lattice geometry, though not a unique certificate of it, since distinct structures can share the same nullity.
Summary and conclusions
We have presented a framework that reformulates the computation of the Ising partition function as a sampling problem in the null space of the binary incidence matrix, and shown that the reformulation survives the passage from two-body to multi-spin interactions unchanged. Like a complete energy-space density of states, the weight distribution is temperature independent, so a single estimate yields the zero-field partition function, and the thermodynamic quantities obtained from its temperature derivatives, at any temperature. For the uniform models treated here the two coefficient sequences carry equivalent information, each being an exact linear transform of the other (Eqs. (37) and (38)); what differs is the sampling problem. The cycle-space walk moves through a linear code by additions of basis vectors rather than through spin configurations, it applies without structural modification to arbitrary multi-spin interaction hypergraphs, and its output is directly the weight distribution of that code, which makes coding-theoretic tools available and admits extensions to multivariate weight enumerators for models with several interaction classes. Its numerical conditioning and convergence behavior differ from those of energy-space sampling, as the results above show. Sparse interaction structures whose nullity is well below the spin-space dimension constitute a further promising setting that we have not yet explored.
The numerical results delineate the regimes in which each representation is effective. Whenever conventional energy-space Wang–Landau sampling is also applicable and both calculations have converged, cycle-space and energy-space sampling produce mutually consistent thermodynamic observables with broadly comparable accuracy. On the triangular lattice the energy-space estimates are somewhat more uniform, while in three and four dimensions the larger null-space dimension leads to visible convergence loss at the largest sizes studied. For the multi-spin models, where no energy-space baseline was run, the estimator was instead checked directly against complete enumeration at the smallest size in each dimension. Because the simulations were not performed at matched computational cost, these results do not establish an efficiency ordering between the two methods.
Several directions follow naturally from the present results. The most immediate concerns are convergence diagnostics, parallelization, and cost-normalized benchmarking. The spectral-gap diagnostic of Barash et al. [53] could replace the fixed move budget with a principled convergence criterion for the null-space walk. In parallel, the Wang–Landau framework of Vogel et al. [54], which distributes the sampled weight range across multiple replicas, could directly address the slow exploration of the tails observed for our largest lattices. A controlled comparison with energy-space sampling should additionally match wall-clock time or another common computational budget, record the actual number of trial moves and histogram round trips, and include the one-time cost of constructing the null-space basis. Such measurements are needed to determine the crossover between the two representations.
The tail problem may also be reduced by changing the sampling objective. Rather than estimating the entire weight distribution uniformly, one could sample null vectors with probability proportional to and combine the resulting ensemble with an appropriate normalization estimator for . This would concentrate computational effort near the weights that dominate at the temperature of interest, although it would sacrifice the temperature-independent character of the full calculation. Complementary information is available through the MacWilliams identity, which imposes an exact relation between the cycle- and cut-space weight enumerators. Incorporating this constraint, or sampling the dual enumerator when it is more favorable, may improve the reconstruction of poorly resolved tails.
The coding-theoretic formulation also points toward deterministic and hybrid alternatives to flat-histogram sampling. The weight distribution can be obtained as a marginal of a graphical model on the Tanner graph of , suggesting generalized belief propagation [73] and tensor-network contraction [74, 75] for interaction graphs with suitable structure. This connection is particularly natural because, for the zero-field pairwise model at the spin-symmetric belief-propagation fixed point, the surviving terms of the loop series are the same even subgraphs counted by the coefficients [36, 37]. A hybrid scheme could therefore use belief propagation to capture the leading contribution and cycle-space sampling to estimate the weight-resolved corrections.
The principal conceptual obstacle remains the cancellation problem for frustrated systems, those whose coupling signs cannot be removed by the gauge condition of Eq. (32), described in Sec. III E 3. Overcoming this obstruction, whether through a change of representation, a partial resummation, or a structure-dependent decomposition of the cycle code, is the most important open question raised by the present work. A more speculative direction is to seek a corresponding construction for quantum spin models, where the partition function involves a trace over noncommuting operators. A Suzuki–Trotter expansion or a permutation-matrix representation may provide an enlarged configuration space in which an analogous null-space structure can be identified.
By shifting the computational effort from spin configurations to the combinatorics of the interaction hypergraph, and by identifying the high-temperature coefficients with the weight enumerator of a linear code, the present formulation makes tools from coding theory available for computing classical partition functions. The results establish the soundness of this reformulation and demonstrate its applicability to interaction structures beyond the reach of graph-specific methods. Improved convergence control, dual-space algorithms, and cost-normalized benchmarks will determine the regimes in which this structural flexibility also translates into a computational advantage.
Acknowledgments
The authors acknowledge the Center for Advanced Research Computing (CARC) at the University of Southern California for providing the computing resources used in this work.
References
@page 17/22 starts_mid=1 ends_mid=0 of the tails observed for our largest lattices. A controlled comparison with energy-space sampling should additionally match wall-clock time or another common computational budget, record the actual number of trial moves and histogram round trips, and include the one-time cost of constructing the null-space basis. Such measurements are needed to determine the crossover between the two representations.
The tail problem may also be reduced by changing the sampling objective. Rather than estimating the entire weight distribution uniformly, one could sample null vectors with probability proportional to and combine the resulting ensemble with an appropriate normalization estimator for . This would concentrate computational effort near the weights that dominate at the temperature of interest, although it would sacrifice the temperature-independent character of the full calculation. Complementary information is available through the MacWilliams identity, which imposes an exact relation between the cycle- and cut-space weight enumerators. Incorporating this constraint, or sampling the dual enumerator when it is more favorable, may improve the reconstruction of poorly resolved tails.
The coding-theoretic formulation also points toward deterministic and hybrid alternatives to flat-histogram sampling. The weight distribution can be obtained as a marginal of a graphical model on the Tanner graph of , suggesting generalized belief propagation [73] and tensor-network contraction [74, 75] for interaction graphs with suitable structure. This connection is particularly natural because, for the zero-field pairwise model at the spin-symmetric belief-propagation fixed point, the surviving terms of the loop series are the same even subgraphs counted by the coefficients [36, 37]. A hybrid scheme could therefore use belief propagation to capture the leading contribution and cycle-space sampling to estimate the weight-resolved corrections.
The principal conceptual obstacle remains the cancellation problem for frustrated systems, those whose coupling signs cannot be removed by the gauge condition of Eq. (32), described in Sec. III E 3. Overcoming this obstruction, whether through a change of representation, a partial resummation, or a structure-dependent decomposition of the cycle code, is the most important open question raised by the present work. A more speculative direction is to seek a corresponding construction for quantum spin models, where the partition function involves a trace over noncommuting operators. A Suzuki–Trotter expansion or a permutation-matrix representation may provide an enlarged configuration space in which an analogous null-space structure can be identified.
By shifting the computational effort from spin configurations to the combinatorics of the interaction hypergraph, and by identifying the high-temperature coefficients with the weight enumerator of a linear code, the present formulation makes tools from coding theory available for computing classical partition functions. The results establish the soundness of this reformulation and demonstrate its applicability to interaction structures beyond the reach of graph-specific methods. Improved convergence control, dual-space algorithms, and cost-normalized benchmarks will determine the regimes in which this structural flexibility also translates into a computational advantage.
Acknowledgments
The authors acknowledge the Center for Advanced Research Computing (CARC) at the University of Southern California for providing the computing resources used in this work.
References
Exact coefficients for the open triangular lattice
This appendix records the construction used to obtain the reference coefficients of Sec. IV B.
a. Lattice. The reference graphs are open patches of the triangular lattice: vertices with , and bonds , , and whenever both endpoints lie in the domain, with no periodic identification. Hence and
that is for , matching Table II. This is the same finite graph on which the sampled null-space bases are built.
The three-dimensional Baxter–Wu system
b. Directed-walk determinant. Introduce the six directed steps
which, in the equilateral embedding with the unit vector at angle , point along the directions . A directed state is a pair of a site and an attempted outgoing direction, so the turning matrix has dimension , with entries
where the walk turns through the angle and taken on the branch
the zero at forbidding immediate backtracking. States whose step leaves the domain are inactive and contribute trivial factors. For this construction the Kac–Ward formula for finite planar graphs [4, 64] gives Eq. (33), . Appendix B of Stanley [76] presents the corresponding directed-walk construction for the square lattice; here the same construction is applied to the six directed edge orientations of the triangular lattice, with the appropriate turning-angle phases.
c. Evaluation. Let and write the characteristic polynomial of as . Its coefficients are computed exactly by the Faddeev–LeVerrier recursion [77]: set , and, for , , . The same coefficients give . Every nonzero entry of is a twelfth root of unity, and in our implementation every intermediate matrix element remains a single phase monomial with , and , a property checked at run time. Exact arithmetic therefore reduces to arbitrary-precision integer magnitudes together with a phase index modulo 12.
Finally is factorized exactly. Every irreducible factor occurs with even multiplicity, as guaranteed by Eq. (33), so the polynomial square root is obtained by halving these multiplicities and fixing . Its coefficients are the nonnegative integers . As stated in Sec. IV B, they satisfy and ; the latter follows because and the vertex–edge incidence matrix of a connected graph has .
The three-dimensional Baxter–Wu system
This appendix records the counting behind Eq. (35) and the null-space dimensions of Table II for the geometry defined in Sec. IV D.
a. Counting the faces. In cubic coordinates the triangular faces of fall into three Cartesian plane families , each consisting of planes carrying triangles apiece, together with one oblique family of triangles; this decomposition is exhaustive and disjoint, and we have verified it face by face for . Hence , giving for . The auxiliary nearest-neighbor graph has two-body edges, that is, 90, 252, 540, 990; these define the faces and are not interaction terms.
b. Null-space dimensions. Let be the site–triangle incidence matrix. For each simulated size direct row reduction over gives , i.e. full row rank, so
which evaluates to 61, 206, 483, 934. At this gives , matching the exported basis of 934 vectors of length 1150.
Supplementary figures
This appendix collects the mean-energy comparisons for all five systems, the weight distributions for the three- and four-dimensional lattices, and the energy-space densities of states used as the baseline in Sec. IV.
References
- [1]E. Ising, Z. Phys. 31, 253 (1925).
- [2]L. Onsager, Phys. Rev. 65, 117 (1944).
- [3]B. Kaufman, Phys. Rev. 76, 1232 (1949).
- [4]M. Kac and J. C. Ward, Phys. Rev. 88, 1332 (1952).
- [5]R. M. F. Houtappel, Physica 16, 425 (1950).
- [6]R. J. Baxter, Exactly Solved Models in Statistical Mechanics (Academic Press, London, 1982).
- [7]L. G. Valiant, Theor. Comput. Sci. 8, 189 (1979).
- [8]F. Jaeger, D. L. Vertigan, and D. J. A. Welsh, Math. Proc. Cambridge Philos. Soc. 108, 35 (1990).
- [9]F. Barahona, J. Phys. A: Math. Gen. 15, 3241 (1982).
- [10]S. Istrail, in Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC ’00) (ACM, 2000) pp. 87–96.
- [11]N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller, J. Chem. Phys. 21, 1087 (1953).
- [12]R. H. Swendsen and J.-S. Wang, Phys. Rev. Lett. 58, 86 (1987).
- [13]C. Domb and M. S. Green, eds., Phase Transitions and Critical Phenomena, Vol. 3 (Academic Press, London, 1974).
- [14]H. A. Kramers and G. H. Wannier, Phys. Rev. 60, 252 (1941).
- [15]K. G. Wilson, Rev. Mod. Phys. 47, 773 (1975).
- [16]D. Frenkel and B. Smit, Understanding Molecular Simulation: From Algorithms to Applications, 2nd ed. (Academic Press, San Diego, 2002).DOI
- [17]A. D. Sokal, in Functional Integration: Basics and Applications, NATO ASI Series, Vol. 361 (Springer, Boston, 1997) pp. 131–192.
- [18]D. P. Landau and K. Binder, A Guide to Monte Carlo Simulations in Statistical Physics, 4th ed. (Cambridge University Press, Cambridge, 2014).
- [19]G. M. Torrie and J. P. Valleau, J. Comput. Phys. 23, 187 (1977).
- [20]B. A. Berg and T. Neuhaus, Phys. Rev. Lett. 68, 9 (1992).
- [21]A. M. Ferrenberg and R. H. Swendsen, Phys. Rev. Lett. 61, 2635 (1988).
- [22]K. Hukushima and K. Nemoto, J. Phys. Soc. Jpn. 65, 1604 (1996).
- [23]U. Wolff, Phys. Rev. Lett. 62, 361 (1989).
- [24]J. Houdayer, Eur. Phys. J. B 22, 479 (2001).
- [25]M. A. Novotny and H. G. Everts, in Computer Simulation Studies in Condensed-Matter Physics VI, edited by D. P. Landau, K. K. Mon, and H.-B. Schüttler (Springer, Berlin, 1993) p. 188.
- [26]I. N. Velonakis and S. S. Martinos, Physica A 390, 24 (2011).
- [27]J. Oitmaa, C. Hamer, and W. Zheng, Series Expansion Methods for Strongly Interacting Lattice Models (Cambridge University Press, Cambridge, 2006).DOI
- [28]P. Butera and M. Comi, Phys. Rev. B 65, 144431 (2002).
- [29]B. L. van der Waerden, Z. Phys. 118, 473 (1941).
- [30]F. Wang and D. P. Landau, Phys. Rev. Lett. 86, 2050 (2001).
- [31]R. E. Belardinelli and V. D. Pereyra, Phys. Rev. E 75, 046701 (2007).
- [32]R. E. Belardinelli and V. D. Pereyra, J. Chem. Phys. 127, 184105 (2007).
- [33]N. Prokof’ev and B. Svistunov, Phys. Rev. Lett. 87, 160601 (2001).
- [34]M. Jerrum and A. Sinclair, SIAM J. Comput. 22, 1087 (1993).
- [35]V. Patel and G. Regts, SIAM J. Comput. 46, 1893 (2017).
- [36]M. Chertkov and V. Y. Chernyak, Phys. Rev. E 73, 065102(R) (2006).
- [37]M. Chertkov and V. Y. Chernyak, J. Stat. Mech., P06009 (2006).
- [38]R. J. Baxter and F. Y. Wu, Phys. Rev. Lett. 31, 1294 (1973).
- [39]R. Diestel, Graph Theory, 5th ed. (Springer, Berlin, 2017).
- [40]L. Perron and F. Didier, “CP-SAT,” Google OR-Tools, version 9.15 (2026).
- [41]D. H. Wiedemann, IEEE Trans. Inf. Theory 32, 54 (1986).
- [42]F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes (North-Holland, Amsterdam, 1977).
- [43]J. G. Bredeson and S. L. Hakimi, IEEE Trans. Inf. Theory 13, 348 (1967).
- [44]S. L. Hakimi and J. G. Bredeson, IEEE Trans. Inf. Theory 14, 584 (1968).
- [45]D. Jungnickel and S. A. Vanstone, IEEE Trans. Inf. Theory 43, 136 (1997).
- [46]B. Bollobás, Modern Graph Theory (Springer, New York, 1998).
- [47]E. R. Berlekamp, R. J. McEliece, and H. C. A. van Tilborg, IEEE Trans. Inf. Theory 24, 384 (1978).
- [48]A. Vardy, IEEE Trans. Inf. Theory 43, 1757 (1997).
- [49]A. Barg, in Handbook of Coding Theory, Vol. 1, edited by V. S. Pless and W. C. Huffman (North-Holland, Amsterdam, 1998) pp. 649–754.
- [50]F. Wang and D. P. Landau, Phys. Rev. E 64, 056101 (2001).
- [51]C. Zhou and R. N. Bhatt, Phys. Rev. E 72, 025701 (2005).
- [52]P. Dayal, S. Trebst, S. Wessel, D. Würtz, M. Troyer, S. Sabhapandit, and S. N. Coppersmith, Phys. Rev. Lett. 92, 097201 (2004).
- [53]L. Y. Barash, M. A. Fadeeva, and L. N. Shchur, Phys. Rev. E 96, 043307 (2017).
- [54]T. Vogel, Y. W. Li, T. Wüst, and D. P. Landau, Phys. Rev. Lett. 110, 210603 (2013).
- [55]M. E. Fisher, Phys. Rev. 124, 1664 (1961).
- [56]P. W. Kasteleyn, Physica 27, 1209 (1961).
- [57]H. N. V. Temperley and M. E. Fisher, Philos. Mag. 6, 1061 (1961).
- [58]E. Marinari and G. Parisi, Europhys. Lett. 19, 451 (1992).
- [59]F. Y. Wu, Rev. Mod. Phys. 54, 235 (1982).
- [60]M. Troyer and U.-J. Wiese, Phys. Rev. Lett. 94, 170201 (2005).
- [61]M. Marvian, D. A. Lidar, and I. Hen, Nat. Commun. 10, 1571 (2019).
- [62]D. Hangleiter, I. Roth, D. Nagaj, and J. Eisert, Sci. Adv. 6, eabb8341 (2020).
- [63]I. Hen, Phys. Rev. E 99, 033306 (2019).
- [64]D. Cimasoni, J. Stat. Mech.: Theory Exp. 2010, P07023 (2010).
- [65]A. M. Ferrenberg and D. P. Landau, Phys. Rev. B 44, 5081 (1991).
- [66]A. M. Ferrenberg, J. Xu, and D. P. Landau, Phys. Rev. E 97, 043301 (2018).
- [67]H. P. Lundow and K. Markström, Phys. Rev. E 80, 031104 (2009).
- [68]P. H. Lundow and K. Markström, Nucl. Phys. B 993, 116256 (2023).
- [69]D. W. Wood and H. P. Griffiths, J. Phys. C: Solid State Phys. 5, L253 (1972).
- [70]R. J. Baxter and F. Y. Wu, Aust. J. Phys. 27, 357 (1974).
- [71]A. R. S. Macêdo, A. Vasilopoulos, M. A. Akriditis, J. A. Placlak, N. G. Fytas, and M. Weigel, Phys. Rev. E 108, 024140 (2023).
- [72]L. N. Jorge, L. S. Ferreira, and A. A. Caparica, Phys. Rev. E 100, 032141 (2019).
- [73]J. S. Yeadidia, W. T. Freeman, and Y. Weiss, IEEE Trans. Inf. Theory 51, 2282 (2005).
- [74]M. Levin and C. P. Nave, Phys. Rev. Lett. 99, 120601 (2007).
- [75]T. Nishino and K. Okunishi, J. Phys. Soc. Jpn. 65, 891 (1996).
- [76]H. E. Stanley, Introduction to Phase Transitions and Critical Phenomena (Clarendon Press, Oxford, 1971) see Appendix B.
- [77]F. R. Gantmacher, The Theory of Matrices, Vol. 1 (Chelsea, New York, 1959).









