1 Introduction↩︎

Spin systems arise from statistical physics to model interactions between neighbors on graphs. In this paper, we consider 2-spin systems. Such a system is defined on a simple finite undirected graph \(G=(V,E)\) and in this way the individual entities comprising the system correspond to the vertices \(V\) and their pairwise interactions correspond to the edges \(E\). The system is associated with three parameters consisting of two edge activities \(\beta\) and \(\gamma\) that model the tendency of vertices to agree and disagree with their neighbors, and a vertex activity \(\lambda\) that models a uniform external field which determines the propensity of a vertex to be the spin \(+\). A partial configuration of this system refers to a mapping \(\sigma: \Lambda\to\{+,-\}\) for some \(\Lambda\subseteq V\) which may be empty. It assigns one of the two spins \(+\) and \(-\) to each vertex in \(\Lambda\). When \(\Lambda=V\), it is a configuration, and its weight denoted by \(w(\sigma)\) is \(\beta^{m_+(\sigma)}\gamma^{m_-(\sigma)}\lambda^{n_+(\sigma)}\), where \(m_+(\sigma),m_-(\sigma)\) and \(n_+(\sigma)\) denote respectively the number of \((+,+)\) edges, \((-,-)\) edges and vertices with the spin \(+\). The partition function of a 2-spin system is defined to be \[Z_G(\beta,\gamma,\lambda):=\sum\limits_{\sigma:V\to\{+,-\}}w(\sigma).\] We also define the partition function conditioning on a pre-described partial configuration \(\sigma_\Lambda\) (i.e., each vertex in \(\Lambda\), called a pinned vertex, is pinned to be the spin \(+\) or \(-\)) denoted by \(Z^{\sigma_\Lambda}_G(\beta,\gamma,\lambda)\) to be \(\sum_{\sigma:V\to\{+,-\}\atop \sigma|_{\Lambda}=\sigma_\Lambda}w(\sigma)\) where \(\sigma|_{\Lambda}\) denotes the restriction of the configuration \(\sigma\) on \(\Lambda\).

Computing the partition function of the 2-spin system given an input graph \(G\) is a very basic counting problem, and it is known to be #P-hard for all complex-valued parameters \((\beta, \gamma, \lambda)\) except for a few very restricted settings such as \(\beta\gamma=1\) or \(\lambda=0\) [2]–[4]. Many natural combinatorial problems can be formulated as computing the partition functions of 2-spin systems. For example, when \(\beta = 0\) and \(\gamma=1\), \(Z_G(0, 1, \lambda)\) is the independence polynomial of the graph \(G\) (also known as the hard-core model in statistical physics); it counts the number of independent sets of the graph \(G\) when \(\lambda =1\). When \(\beta=\gamma\), such a 2-spin system is the famous Ising model.

In classical statistical mechanics, the parameters \((\beta, \gamma, \lambda)\) are usually non-negative real numbers and \((\beta, \gamma)\neq (0, 0)\). Such 2-spin systems are divided into the ferromagnetic case (\(\beta\gamma>1\)) and the antiferromagnetic case (\(\beta\gamma <1\)). For non-negative \((\beta, \gamma, \lambda)\) that are not all zero, the partition function can be viewed as the normalizing factor of the Gibbs distribution, which is the distribution where a configuration \(\sigma\) is drawn with probability \({\rm Pr}_{G; \beta, \gamma, \lambda}(\sigma)=\frac{w(\sigma)}{Z_G(\beta, \gamma, \lambda)}\). However, it is meaningful to consider parameters with complex values. First, complex-valued parameters arise when we consider quantum computation. For instance, the partition functions of 2-spin systems with complex parameters are closely related to the output probability amplitudes of quantum circuits [5]–[7]. Moreover, even in classical theory, the study of the location of complex zeros of the partition function \(Z_G(\beta, \gamma, \lambda)\) connects closely to the analyticity of the free energy \(\log Z_G(\beta, \gamma, \lambda)\), which is a classical notion in statistical physics for defining and understanding the phenomenon of phase transitions. One of the first and also the best-known results regarding the zeros of partition functions is the Lee-Yang theorem [8], [9] for the Ising model. This result was later extended to more general models [10]–[14]. Another standard notion for formalizing (the absence of) phase transitions in 2-spin systems is correlation decay, which means that correlations between spins decay exponentially as a function of the distance between them. More formally, given an infinite graph, such as an infinite regular tree, one can characterize regions in the model’s parameter space where, under the associated Gibbs distribution, correlations between spins decay exponentially with distance.

The two notions for (the absence of) phase transitions can also be exploited directly to devise fully polynomial-time deterministic approximation schemes (FPTASes) for computing the partition functions of 2-spin systems. The method associated with correlation decay, or more precisely, strong spatial mixing (SSM)⁴, was originally developed by Weitz [15], and Bandyopadhyay and Gamarnik [16] for the hard-core model, and was extended to complex parameters harvey2018computing?. It turns out to be a very powerful tool for antiferromagnetic 2-spin systems [17]–[20]. In contrast, for ferromagnetic 2-spin systems, the correlation decay method has yielded only limited results [17], [21]. In these cases, correlation decay is typically established via tree recurrence arguments, which rely on the uniqueness condition on regular trees (also known as the contraction condition [22]) and on the careful design of a suitable potential function.

The method turning complex zero-free regions of partition functions into FPTASes was developed by Barvinok [23] and extended by Patel and Regts [24]. It is usually called the Taylor interpolation method. Motivated by this method, several complex zero-free regions have been obtained for hard-core models [25], [26], Ising models [7], [27]–[30], and general 2-spin systems [22], [31]. Table 1 summarizes the known zero-free regions for 2-spin systems. For a subset \(I\subseteq \mathbb{C}\), we use \(\mathcal{N}(I)\) to denote a complex neighborhood of \(I\). In the table, the fourth column (named “Pinned”) indicates whether the corresponding zero-free regions remain valid for graphs with pinned vertices, while the fifth column (named “Bounded”) indicates whether the result holds only for graphs with maximum degree bounded by some integer \(d\). The result in Row 8 corresponds to the celebrated Lee–Yang theorem [9]. Furthermore, the regions in Rows 2, 4, and 6 are all contained within the region described in Row 7.

For each zero-free region in Table 1, an FPTAS exists via Barvinok’s algorithm. In contrast, Weitz-style FPTASes are currently known only for the regions in Rows 1, 2, 4, 6, and 7, where SSM can be established via tree recurrence arguments using contraction properties. For other regions, particularly those corresponding to the ferromagnetic regime (\(\beta\gamma > 1\)), it remains unclear whether SSM can be proved using such methods. This raises a natural and intriguing question: For those zero-free regions of 2-spin systems where FPTASes exist via Barvinok’s algorithm, can Weitz’s algorithm also be applied? In particular, is it possible to establish SSM for these zero-free regions even when the standard tree recurrence method is not known to work?

New SSM results and Weitz’s FPTASes beyond tree recurrences↩︎

In this paper, we answer this question in the affirmative. We show that for any zero-free region of 2-spin systems on graphs with pinned vertices, SSM holds throughout the same region. This immediately implies new SSM results including the regions in Rows 3 and 5 of Table 1. We also obtain new SSM results for parts of the Lee-Yang zero-free region. Consequently, Weitz’s FPTASes exist for these regions. Notably, these SSM results are not known to be provable via the standard tree recurrence method.

Related work↩︎

Our work generalizes a recent line of work establishing that zero-freeness implies SSM for the hard-core model and other graph homomorphism models [33]–[35]. This implication reflects a deeper connection between the two key paradigms for designing FPTASes for 2-spin systems: zero-freeness (from complex analysis) and correlation decay (from probabilistic arguments). In seminal works [36], [37], Dobrushin and Shlosman proved that for lattice models, the correlation decay property is equivalent to the zero-freeness of the partition function. Recently, further formal connections have been established beyond lattice models. Such results have been obtained for the hard-core model [25], the Ising model [27], [28], lsscorrelation?, and general 2-spin systems [22] on graphs with bounded degree. In these works, for real parameters where correlation decay can be established via the tree recurrence method using the contraction property, this property can often be analytically extended to complex neighborhoods of the parameters, thereby ensuring zero-freeness of the partition function. However, it remains unclear whether correlation decay or SSM directly implies zero-freeness of the partition function. On the other hand, harvey2018computing? proved correlation decay result for hard-core model based on multivariate zero-freeness condition on polydisc region, establishing Weitz’s type FPTAS. Gamarnik [34] first showed that zero-freeness of the partition function directly implies a weak form of SSM for the hard-core model and other graph homomorphism models. Later, Regts [35] strengthened this result by proving that zero-freeness implies SSM for the hard-core model near \(\lambda = 0\), as well as for other graph homomorphism models on all graphs of bounded degree. When restricted to 2-spin systems, the graph homomorphism model is the 2-spin system without external field, i.e., \(\lambda=1\), and the implication from zero-freeness to SSM holds for a complex neighborhood of \((\beta, \gamma)=(1, 1)\).

A novel and unified approach beyond cluster expansions↩︎

In this paper, we significantly extend the known implication from zero-freeness to the most general settings of 2-spin systems, comprehensively covering all currently known zero-free regions (Rows 1 to 7 of Table 1, to the best of our knowledge) of the partition functions of 2-spin systems with pinned vertices. The prior approach [35] relies on an analytic tool, namely cluster expansions, which are model-specific and known only for a few cases such as the hard-core model (i.e., \(\beta=0, \gamma=1\)) near \(\lambda=1\), or the 2-spin system without external field (i.e., \(\lambda=1\)) near \(\beta=1\) and \(\gamma=1\). A crucial limitation of this approach is that beyond these model-specific settings, general cluster expansions are not known for 2-spin systems with arbitrary complex parameters \((\beta, \gamma, \lambda)\) on general graphs.⁵

We circumvent this obstacle and establish SSM for general 2-spin systems via a purely combinatorial approach based on a Christoffel–Darboux-type identity (Theorem 4 below), which holds universally for arbitrary complex \((\beta, \gamma, \lambda)\). This enables a unified analysis of various zero-free regions across all three parameters. Unlike the previous result [35], which treats the partition function as a univariate function restricted to strip-like zero-free regions, we are able to handle the partition function \(Z_G(\beta, \gamma, \lambda)\) with arbitrary multivariate complex parameters \((\beta, \gamma, \lambda)\) and zero-free regions of arbitrary shape. In summary, we present a unified and broadly applicable framework for deriving SSM from zero-freeness based on a combinatorial identity, bypassing the need for model-specific cluster expansions which may be inapplicable to general 2-spin systems. In Appendix 8, we review the cluster expansion approach in more detail, discuss its limitations in extending to general 2-spin systems, and compare it with our approach.

Below, we formally describe the implication from zero-freeness to SSM for general 2-spin systems. A region refers to a standard complex region, i.e., a simply connected open set in \(\mathbb{C}\), and a neighborhood of some \(z\in \mathbb{C}\) refers to a region containing \(z\). For \(z\in \mathbb{C}\), we say \(U\subseteq \mathbb{C}\) is a quasi-neighborhood of \(z\) if either \(U\) is a neighborhood of \(z\) or \(U=\{z\}\). For a region \(U\) where \(0\notin U\), we define \(1/U\) to be the set \(\{z\in \mathbb{C}\mid 1/z \in U\}\), which is a region. A family \(\mathcal{G}\) of graphs is closed under constructions of self-avoiding walk trees (see Subsection 2.2) if for any graph \(G\in \mathcal{G}\) and any vertex \(v\) of \(G\), the SAW tree of \(G\) rooted at \(v\) is in \(\mathcal{G}\).

Roughly speaking, the first condition of Theorem 2 requires that the partition function viewed as a function of \(\lambda\) is zero-free in a complex neighborhood of \(\lambda=0\), and the second and third conditions of Theorem 2 together require that the partition function viewed as a function of \(\beta\) or \(\gamma\) is zero-free in a neighborhood of \(\beta\gamma =1\). We use Figure 1 (a) to illustrate Theorem 2. The first row and the second row are examples of conditions 1 and 2 respectively, where the underlying graphs are arbitrary and a non-negative point \((\beta_0, \gamma_0, \lambda_0)\) is required. The third row illustrates condition 3, where the underlying graphs are required to have bounded degree, but no non-negative point is required.

In addition, for the Ising model, we have the following SSM result from zero-free regions of \(\beta\).

Although we give three different conditions involving three parameters \(\lambda, \beta\), and \(\gamma\) for 2-spin systems (Theorem 2) and a condition for Ising models (Theorem 3) under which zero-freeness implies SSM, they are all proved by a unifying approach in which a Christoffel-Darboux type identity plays a key role. A Christoffel-Darboux type identity was originally established for the independence polynomial on trees [39] and was later extended to general graphs [40]. Our main technical contribution lies in establishing a Christoffel-Darboux type identity for the 2-spin system⁶ on trees. Such an identity provides a relation for the partition functions of 2-spin systems with different pinned vertices, and may be of independent interest. Given a graph \(G\), a partial configuration \(\sigma_{\Lambda}\), and \(u,v\in V(G),\) we define \[Z^{\sigma_\Lambda,+}_{G,v}(\beta,\gamma,\lambda)=\sum\limits_{\sigma:V\to\{+,-\} \atop \sigma|_{\Lambda}=\sigma_\Lambda, \sigma(v)=+}w(\sigma), \text{ and } Z^{\sigma_\Lambda,+,+}_{G,v,u}(\beta,\gamma,\lambda)=\sum\limits_{\sigma:V\to\{+,-\} \atop \sigma|_{\Lambda}=\sigma_\Lambda, \sigma(v)=\sigma(u)=+}w(\sigma),\] and similarly we can define \(Z^{\sigma_\Lambda,-}_{G,v}(\beta,\gamma,\lambda),Z^{\sigma_\Lambda,+,-}_{G,v,u}(\beta,\gamma,\lambda),Z^{\sigma_\Lambda,-,+}_{G,v,u}(\beta,\gamma,\lambda)\) and \(Z^{\sigma_\Lambda,-,-}_{G,v,u}(\beta,\gamma,\lambda).\)

Although Theorem 4 is established for trees only, the implication from zero-freeness to SSM applies to 2-spin systems on all graphs by using SAW trees (Lemma 4). Thus, for our purposes, it suffices to prove the identity for trees only. It remains an interesting and challenging question whether this identity can be extended to 2-spin systems on general graphs.

We briefly explain why Theorem 4 provides a unifying approach to turn all existing zero-free regions of 2-spin systems to SSM. A key step in deriving SSM from zero-freeness is to show that the coefficients of the first \(k\) terms in the Taylor series of the rational function \(P_{G,v}^{\sigma_\Lambda}(\beta,\gamma,\lambda)=\frac{Z^{\sigma_\Lambda,+}_{G,v}(\beta,\gamma,\lambda)}{Z^{\sigma_\Lambda}_{G}(\beta,\gamma,\lambda)}\) around a specific point (for example \(\lambda=0\), or \(\beta=1\) after a variable replacement) depend only on the \(k\)-neighborhood of \(v\) in \(G\), defined as LDC (Definition 5). By Theorem 4, one can factor out \(\lambda^{d(u,v)}\) and \((\beta\gamma-1)^{d(u,v)}\) from \(P_{G,v}^{\sigma_\Lambda}(\beta,\gamma,\lambda)-P_{G,v}^{\sigma_\Lambda, u^+}(\beta,\gamma,\lambda)\) where \(P_{G,v}^{\sigma_\Lambda, u^+}(\beta,\gamma,\lambda)=\frac{Z^{\sigma_\Lambda,+,+}_{G,v,u}(\beta,\gamma,\lambda)}{Z^{\sigma_\Lambda,+}_{G,u}(\beta,\gamma,\lambda)}\). Then, by pinning vertices pointwise, we can eventually prove LDC for 2-spin systems both near \(\lambda=0\) and \(\beta\gamma=1\) in a unified way, eliminating the need to establish cluster expansions for various special cases of 2-spin systems to prove LDC. Thus, the use of Theorem 4 is not only novel but also circumvents the need for cluster expansion, which may be inapplicable to general 2-spin systems.

Furthermore, the application of Theorem 4 reveals another potential advantage. It may answer a natural and intriguing question: if the partition function is zero-free on a complex neighborhood of some points other than \(\lambda=0\) and \(\beta\gamma=1\), can we still derive SSM from such zero-free regions? The answer would be yes if one could factor out some \((\lambda-\lambda_0)^{d(u,v)}\) or \((\beta\gamma-z_0)^{d(u,v)}\) from \(P_{G,v}^{\sigma_\Lambda}(\beta,\gamma,\lambda)-P_{G,v}^{\sigma_\Lambda, u^+}(\beta,\gamma,\lambda)\). However, such a factorization is ruled out by Theorem 4. Otherwise, there would exist some \(\lambda_0\neq 0\) or \(\beta_0\gamma_0=z_0\neq 1\) such that \(P_{G,v}^{\sigma_\Lambda}(\beta,\gamma,\lambda_0) \equiv P_{G,v}^{\sigma_\Lambda, u^+}(\beta,\gamma,\lambda_0)\) or \(P_{G,v}^{\sigma_\Lambda}(\beta_0,\gamma_0,\lambda) \equiv P_{G,v}^{\sigma_\Lambda, u^+}(\beta_0,\gamma_0,\lambda)\) for all graphs \(G\), which is impossible. Thus, it is highly possible that by using Theorem 4, we have indeed characterized all zero-free regions from which SSM can be derived (at least via the approach based on establishing LDC). In addition, we utilize the Riemann mapping theorem to handle zero-free regions of arbitrary shape, rather than restricting to strip-shaped neighborhoods of real intervals.⁷

Organization↩︎

The paper is organized as follows. In Section 2, we present some definitions and notations, and introduce certain results from complex analysis. In Section 3, we prove a Christoffel-Darboux type identity for 2-spin systems on trees, and use it to prove the key LDC property for \(\beta, \gamma\) and \(\lambda\) in a unified way. In Section 4, we combine all these ingredients together and show that zero-freeness implies SSM for regions of arbitrary shapes. In Section 5, we extend our approach to deal with 2-spin systems with non-uniform external fields, and establish novel (strong/plus/minus) spatial mixing results for the non-uniform ferromagnetic Ising model from the Lee-Yang circle theorem. We conclude the paper and introduce some open questions in Section 6. An extension of the Christoffel-Darboux type identity to \(q\)-spin systems on trees will be given in Appendix 7. In Appendix 8, we compare our approach with the cluster expansion approach in more detail.

2 Preliminaries↩︎

2.1 Notations and definitions↩︎

Given a partial configuration \(\sigma_\Lambda\), for any \(\Lambda'\subset\Lambda,\) we denote by \(\sigma_{\Lambda'}\) the restriction of \(\sigma_{\Lambda}\) on \(\Lambda'\), called a sub-partial configuration of \(\sigma_{\Lambda}\). Consider the rational function \(P_{G,v}^{\sigma_\Lambda}(\beta,\gamma,\lambda)=\frac{Z^{\sigma_\Lambda,+}_{G,v}(\beta,\gamma,\lambda)}{Z^{\sigma_\Lambda}_{G}(\beta,\gamma,\lambda)}.\) Note that when \(\beta, \gamma, \lambda{>0}\), \(P_{G,v}^{\sigma_\Lambda}\) denotes the marginal probability of \(v\) being assigned to the spin \(+\) in the Gibbs distribution. However, when \(\beta, \gamma, \lambda\in \mathbb{C}\), \(P_{G,v}^{\sigma_\Lambda}(\beta,\gamma,\lambda)\) has no probabilistic meaning and \(P_{G,v}^{\sigma_\Lambda}(\beta,\gamma,\lambda)\in \mathbb{C}\) if \(Z^{\sigma_\Lambda}_{G}(\beta,\gamma,\lambda)\neq 0\). For the setting \(\beta =0\) or \(\gamma =0\), there are trivial partial configurations such that \(Z^{\sigma_\Lambda}_{G, v}(\beta,\gamma,\lambda)=0\). We rule these cases out as they are infeasible.

When the parameters \(\beta\) and \(\gamma\) of a 2-spin system are fixed, we may write the partition function \(Z^{\sigma_\Lambda}_{G}(\beta,\gamma,\lambda)\) as \(Z^{\sigma_\Lambda}_{G,\beta,\gamma}(\lambda)\) and the rational function \(P_{G,v}^{\sigma_\Lambda}(\beta,\gamma,\lambda)\) as \(P_{G, \beta,\gamma,v}^{\sigma_\Lambda}(\lambda)\), which are both univariate functions on \(\lambda\). Sometimes we may omit the fixed parameters \(\beta\) and \(\gamma\) at the subscript for simplicity. The definition of zero-freeness can be easily adapted to the partition function \(Z^{\sigma_\Lambda}_{G,\beta,\gamma}(\lambda)\) with fixed \(\beta\) and \(\gamma\), and similarly to \(Z^{\sigma_\Lambda}_{G,\gamma,\lambda}(\beta)\) with fixed \(\gamma\) and \(\lambda\), as well as \(Z^{\sigma_\Lambda}_{G,\beta,\lambda}(\gamma)\) with fixed \(\beta\) and \(\lambda\). When the three parameters are all fixed, we may write the value \(Z^{\sigma_\Lambda}_{G}(\beta,\gamma,\lambda)\) as \(Z^{\sigma_\Lambda}_{G}\) and the value \(P_{G,v}^{\sigma_\Lambda}(\beta,\gamma,\lambda)\) as \(P_{G,v}^{\sigma_\Lambda}\) for simplicity.

Suppose that the partition function \(Z^{\sigma_\Lambda}_{G,\beta,\gamma}(\lambda)\) is zero-free on some \(U\subseteq \mathbb{C}\). Then, the rational function \(P_{G, \beta,\gamma,v}^{\sigma_\Lambda}(\lambda)\) is analytic on \(U\) for any graph \(G\) and any feasible partial configuration \(\sigma_\Lambda\). Moreover, if the vertex \(v\) is proper to \(\sigma_\Lambda\), then \(P_{G, \beta,\gamma,v}^{\sigma_\Lambda}(\lambda) \neq 0\) and \(P_{G, \beta,\gamma,v}^{\sigma_\Lambda}(\lambda) \neq 1\) on \(U\) since \(Z_{G, \beta,\gamma,v}^{\sigma_\Lambda, +}(\lambda)\neq 0\) and \(Z_{G, \beta,\gamma,v}^{\sigma_\Lambda, -}(\lambda)\neq 0\). Notice that \(\lim_{\lambda\rightarrow 0}P_{G, \beta,\gamma,v}^{\sigma_\Lambda}(\lambda)=0\). We agree that \(P_{G, \beta,\gamma,v}^{\sigma_\Lambda}(\lambda)=0\) when \(\lambda=0\). If the zero-free region \(U\) is of the form \(\mathcal{N}(0)\backslash\{0\}\) for some complex neighborhood \(\mathcal{N}(0)\) of \(0\), then the rational function \(P_{G, \beta,\gamma,v}^{\sigma_\Lambda}(\lambda)\) is analytic on the entire \(\mathcal{N}(0)\).

Note that the SSM property guarantees that the partition function \(Z_{G}^{\sigma_\Lambda}\) is zero-free on the fixed point \((\beta, \gamma, \lambda)\), as \(|P_{G,v}^{\sigma_{\Lambda}}|<\infty\) for any graph \(G\) and any feasible partial configuration \(\sigma_{\Lambda}\). The above SSM definition for complex parameters is stronger than the usual definition for real parameters (see Definition 5 of [19] for example). For real values, by monotonicity one need only consider the case that \(\Lambda_1=\Lambda_2\) (the two configurations are on the same set of vertices). However when defining SSM for complex parameters, it is necessary to consider the case that \(\Lambda_1\neq \Lambda_2\) in order to ensure that the SSM-based Weitz’s algorithm works for complex parameters (see Lemma 3.4 of [22]).

2.2 Weitz’s algorithm and self-avoiding walk tree↩︎

Given a graph \(G=(V,E)\) and a vertex \(v\in V\), the SAW tree of \(G\) at \(v\), denoted by \(T_{\text{SAW}}(G,v)\), is a tree with the root \(v\) that enumerates all self-avoiding paths beginning from \(v\) in. Supplementary vertices closing cycles of \(G\) are added as leaves of the tree. Each vertex in \(V\) of \(G\) is mapped to corresponding vertices of \(T_{\text{SAW}}(G,v)\). A vertex set \(\Lambda\subseteq V\) is mapped to some \(\Lambda_{\text{SAW}}\subseteq V_{\text{SAW}}\), and a partial configuration \(\sigma_\Lambda:\Lambda\to\{\pm\}\) is mapped to a partial configuration \(\sigma'_{\Lambda_{\text{SAW}}}\) on \(\Lambda_{\text{SAW}}\). Let \(L_{\Lambda_{\text{SAW}}}\) denote the set of leaf vertices \(u\) in \(V_{\text{SAW}}\) such that \(u\) closes a cycle and no vertices in the path between the root \(v\) and the leaf \(u\) are pinned by \(\sigma'_{\Lambda_{\text{SAW}}}\). For every vertex in \(L_{\Lambda_{\text{SAW}}}\), a configuration is imposed to it depending on the orientation of the cycle, where the order of indices of vertices is arbitrarily chosen (see Figure 2 for an example). We denote by \(\sigma_{\Lambda_{\text{SAW}}}\) the partial configuration \(\sigma'_{\Lambda_{\text{SAW}}}\) on \(\Lambda_{\text{SAW}}\) together with the imposed configuration on \(L_{\Lambda_{\text{SAW}}}\). One can easily check that if \(\sigma_\Lambda\) is feasible in \(G\) and \(v\) is proper to \(\sigma_\Lambda\), then \(\sigma_{\Lambda_{\text{SAW}}}\) is feasible in \(T_{\text{SAW}}(G,v)\) and \(v\) is proper to \(\sigma_{\Lambda_{\text{SAW}}}\). Here is the key result for the SAW tree construction.

2.3 Tools from complex analysis↩︎

For some \(\rho>0\) and \(z_0\in \mathbb{C}\), we denote the open disk \(\{z\in\mathbb{C}: |z-z_0|<\rho\}\) centered at \(z_0\) of radius \(\rho\) by \(\mathbb{D}_{\rho}(z_0)\), its boundary by \(\partial\mathbb{D}_{\rho}(z_0)\), and its closure by \(\overline{\mathbb{D}_{\rho}}(z_0)\). For simplicity, we write \(\mathbb{D}_{\rho}(0)\) as \(\mathbb{D}_{\rho}\). For a holomorphic (or analytic) function \(f\) on a complex neighborhood \(U\subseteq \mathbb{C}\) of \(z_0\), \(f\) can be expanded as a convergent series \(f(z)=\sum_{k\geq 0}a_k (z-z_0)^k\) near \(z_0\), called the Taylor expansion series of \(f\) at \(z_0\).

A sequence of functions converges locally uniformly to \(f\) or \(\infty\) on \(U\) if for every \(z\in U\) there exists an open disk \(\mathbb{D}_\rho(z)\subseteq U\) centered at \(z\) for some \(\rho>0\) such that the sequence converges uniformly to \(f\) or \(\infty\) on \(\mathbb{D}_\rho(z)\).

The next important tool is Montel’s theorem. For more details and a proof, please refer to [42] for the version of univariate functions and [43], [44] for multivariate functions.

The following Riemann mapping theorem is the key tool to map any bounded complex region to the unit open disk.

The following lemma is used in [35] to derive SSM from zero-freeness.

With the lemma in hand, in order to obtain SSM, it suffices to establish the following two properties, namely a uniform bound on a circle and local dependence of coefficients (LDC). The first property says that there exists a circle \(\partial \mathbb{D}_\rho\) around \(0\) such that the rational functions \(P^{\sigma_{\Lambda}}_{G,v}(\lambda)\) have a uniform bound on \(\partial \mathbb{D}_\rho\) for any graph \(G\), any feasible partial configuration \(\sigma_\Lambda\), and any \(v\) proper to it. The second property states that if partial configurations \(\sigma_{\Lambda_1}\) and \(\tau_{\Lambda_2}\) share the same local structure around a vertex \(v\) in \(G\) which is proper to both configurations, then the leading Taylor expansion coefficients of the two rational functions \(P^{\sigma_{\Lambda_1}}_{G,v}(\lambda)\) and \(P^{\tau_{\Lambda_2}}_{G,v}(\lambda)\) near \(0\) coincide.

In [35], a uniform bound was obtained by applying Montel’s theorem (Theorem 7). In this paper, we use the same idea and extend it to the multivariate version since we need to handle three complex parameters \(\beta, \gamma\) and \(\lambda\). Also in [35], LDC was proved by using the cluster expansion formula for polymer models, since explicit expressions were given for the Taylor series of the rational function \(P^{\sigma_\Lambda}_{G,v}(\lambda)\) near \(\lambda=0\) where \(\beta=0, \gamma=1\), and the rational function \(P^{\sigma_\Lambda}_{G,v}(\beta)\) near \(\beta=1\) (after a variable replacement) where \(\beta=\gamma, \lambda=1\). However, besides these particular parameters, to the best of our knowledge, explicit cluster expansions are not known for 2-spin systems on general graphs with arbitrary complex parameters \((\beta, \gamma, \lambda)\). In this paper, we overcome this obstacle and prove LDC for general 2-spin systems with arbitrary \((\beta, \gamma, \lambda)\) by establishing a Christoffel-Darboux type identity. It turns out that an explicit expression for the Taylor series of the rational function is unnecessary for proving LDC for 2-spin systems.

3 Christoffel-Darboux type identity gives LDC↩︎

In this section, we prove our main technical result, a Christoffel-Darboux type identity for 2-spin systems on trees and use it to prove local dependence of coefficients (LDC) for \(\lambda, \beta\) and \(\gamma\) in a unified way. We first formally define LDC.

As an illustration, we will focus on the proof of LDC for \(\lambda\) near \(0\). The proofs of LDC for \(\beta\) and \(\gamma\) are quite similar. Below, without other specifications, we use LDC to stand for LDC for \(\lambda\) near \(0\). We first introduce a special form of LDC, called point-to-point LDC and we show it implies LDC.

Thus, it suffices to prove that point-to-point LDC derives from zero-freeness for trees. We prove this by establishing a Christoffel-Darboux type identity for 2-spin systems on trees.

Before we delve into the general 2-spin system, we first consider a simple case, the hard-core model, the partition function of which is the independence polynomial. This model is the 2-spin system where \(\beta=0\) and \(\gamma=1.\) For the hard-core model, [35] proved that LDC holds by using a tool called cluster expansion from statistical physics. Here, we show that it can also be proved by the following Christoffel-Darboux type identity by Gutman [39]. For a graph \(G=(V, E)\) and a subset \(U\subseteq V\), we use \(G\backslash U\) to denote the graph obtained from \(G\) by deleting all vertices in \(U\) and their adjacent edges (i.e., the subgraph of \(G\) induced by the vertex set \(V\backslash U\)).

This identity was extended to general graphs in [40] (Theorem 1.3). By Lemma 4, the identity for trees is already enough for our proof.

Now, we extend the above Christoffel-Darboux type identity to general 2-spin systems on trees. Actually, we can extend it to the more general \(q\)-spins system on trees (see Appendix 7).

Combining Lemmas 3, 4 and 6, we have the following result.

Notice that in the Christoffel-Darboux type identity for the 2-spin system, besides the “factor” \(\lambda^{d(u,v)+1}\), one can also take a “factor” \((\beta\gamma-1)^{d(u,v)}\) out of \(Z_{T,u,v}^{\sigma_{\Lambda},+,+}Z_{T,u,v}^{\sigma_{\Lambda}, -,-} -Z_{T,u,v}^{\sigma_{\Lambda}, +,-}Z_{T,u,v}^{\sigma_{\Lambda}, -,+}\). Thus, we can prove LDC for \(\beta\) near \(1/\gamma\) similarly. The proof of LDC for \(\gamma\) near \(1/\beta\) is symmetric.

In addition, for the Ising model, \(\beta=\gamma\), \(\beta\gamma=1\) implies \(\beta=\gamma=1\) or \(-1\). Thus, similarly, we can define and prove LDC for \(\beta\) near \(1\) or \(-1\) for the Ising model.

4 Zero-freeness implies SSM↩︎

Now, we are ready to show that zero-freeness implies SSM. We first apply Montel’s theorem (Theorem 7) to get a uniform bound for the multivariate function \(P^{\sigma_\Lambda}_{G,v}(\beta, \gamma, \lambda)\), which extends Lemma 5 of [35].

Then, combining LDC and the above uniform bound, we can prove SSM on a disk region. Still, we give the proof of SSM for \(\lambda\) as an illustration. The proof of SSM for \(\beta\) or \(\gamma\) is similar.

By Lemma 11, when the zero-free region of \(\lambda\) is a disk, the 2-spin system exhibits SSM for any \(\lambda\) in the disk. Using Riemann mapping theorem, we are able to map any region \(U\) containing \(0\) to the unit disk \(\mathbb{D}_1\) with \(0\) as a fixed point. Finally, we can drop the restriction of \(\lambda \in \mathbb{D}_\rho \subseteq U_3\) for some disk \(\mathbb{D}_\rho\) as in the statement of Lemma 11, and get the following result: zero-freeness implies SSM for any complex neighborhood of \(\lambda=0\).

Similarly, we have the following SSM results for \(\beta\) and \(\gamma\).

Combining Theorems 11, 12 and 13, we get our main Theorem 2.

In addition, for the Ising model, we have the following SSM result from zero-free regions of \(\beta\).

5 The implication for non-uniform external fields↩︎

In this section, we extend our result to handle 2-spin systems with non-uniform external fields, and apply it to get new spatial mixing results for the non-uniform ferromagnetic Ising model from corollaries of Lee-Yang circle theorem on graphs with pinned vertices.

The notations and definitions for 2-spin systems with a uniform external field can be extended to the setting with non-uniform external fields as above. In particular, the Christoffel-Darboux type identity (Theorem 10) is also valid for 2-spin systems with non-uniform external fields by replacing \(\lambda^{d(u,v)+1}\) with \(\prod_{w\in p_{uv}}\lambda_w\) where \(p_{uv}\) is the unique path connecting \(u\) and \(v\) in a tree. The SAW tree construction also works where all vertices in \(V_{\text{SAW}}\) mapped from a single vertex \(v\in V\) have the same external field as the external field \(\lambda_v\) of the original \(v\), and Theorem 5 still holds for the multivariate rational functions \(P_{G, v}^{\sigma_\Lambda}(\beta, \gamma, \pmb \lambda)\). For non-uniform external fields \(\pmb \lambda=(\lambda_v)_{v\in V}\), we say they have the same argument \(\theta\) if \(\arg(\lambda_v)=\theta\) for all \(v\in V\).

The following is the celebrated Lee-Yang circle theorem.

Note that Lee-Yang circle theorem gives zero-freeness for the partition function of the Ising model regarding the external fields \(\pmb\lambda\). Thus, we need to apply Theorem 15, instead of Theorem 14 which requires zero-freeness regarding the edge activity \(\beta\)⁸. However, Theorem 15 requires the zero-freeness condition holds for 2-spin systems on graphs even conditioning on some partial configurations. Thus, Lee-Yang circle theorem cannot be directly adapted to our setting since it holds only for graphs with no pinned vertices. In order to obtain SSM from zero-freeness, we first give the following corollary of Lee-Yang circle theorem.

Combining Theorem 15 and Corollary 1, we get a new SSM result for the ferromagnetic Ising model with non-uniform external fields.

If we restrict the partial configuration \(\sigma_\Lambda\) to include at most one vertex with the \(+\) spin (or at most one vertex with the \(-\) spin), then similar to Corollary 1, we have the following zero-free results as a corollary of Lee-Yang Theorem.

We say a partial configuration \(\sigma_\Lambda\) is all-plus if \(\sigma(v)=+\) for every \(v\in \Lambda\), and all-minus if \(\sigma(v)=-\) for every \(v\in \Lambda\). We define the following forms of spatial mixing.

6 Concluding remarks and questions↩︎

We prove that if the partition function of a 2-spin system is zero-free in a complex neighborhood of \(\lambda=0\) or \(\beta\gamma=1\) containing a positive point, then the corresponding 2-spin system exhibits SSM. By a Christoffel-Darboux type identity, it seems that the implication from zero-free regions to SSM only works for complex neighborhoods of \(\lambda=0\) or \(\beta\gamma=1\). A natural question is: what is the magic of these two special settings of parameters \(\lambda=0\) and \(\beta\gamma=1\) for which the exact computation of the partition function is polynomial-time solvable? In fact, so far all currently known zero-free regions (and even all SSM results and all FPTAS results) for 2-spin systems lie in some complex neighborhoods of \(\lambda=0\) (up to a switch of the spins \(+\) and \(-\)) or \(\beta\gamma =1\). We are curious whether this is always true and we make the following conjectures.

For the Ising model, a complex zero-free neighborhood of \(\beta=1\) is known [27]. Also, one can check that the point \(\beta=-1\) (with a fixed \(\lambda\)) satisfies the real contraction property introduced in [22] which implies that there exists a complex neighborhood of \(-1\) such that the partition function of the Ising model is zero-free on it. Thus, for Conjecture 3, at least there exists a complex neighborhood of \(\beta=1\) and a complex neighborhood of \(\beta=-1\) respectively such that the partition function of the Ising model is zero-free on them.

7 Christoffel-Darboux identity for \(q\)-spin systems on trees↩︎

In this section, we extend Christoffel-Darboux type identity to \(q\)-spin systems.

Such a system is defined on a simple undirected graph \(G=(V,E)\) and in this way the individual entities comprising the system correspond to the vertices \(V\) and their pairwise interactions correspond to the edges \(E\).

The system is associated with some parameters consisting of a \(q\times q\) symmetric matrix of edge activities \(A=(a_{i,j})_{1\le i,j\le q}\in\mathcal{M}_q(\mathbb{C})\) that models the tendency of vertices to agree and disagree with their neighbors, and a uniform vertex activity vector \(\boldsymbol{\lambda}=(\lambda_1,\cdots,\lambda_q)\in\mathbb{C}^q\) that models an external field which determines the propensities of a vertex.

A partial configuration of this system refers to a mapping \(\sigma: \Lambda\to[q]=\{1,2,\cdots,q\}\) for some \(\Lambda\subseteq V\) which may be empty. It assigns one of the \(q\) spins to each vertex in \(\Lambda\). When \(\Lambda=V\), it is called a configuration and its weight is \[\omega(\sigma)=\prod_{v\in V}\lambda_{\sigma(v)}\prod_{(u,v)\in E}a_{\sigma(u),\sigma(v)}.\] The partition function of a 2-spin system is defined to be \[Z_G(A,\boldsymbol{\lambda}):=\sum\limits_{\sigma:V\to[q]}w(\sigma).\] We also define the partition function conditioning on a pre-described partial configuration \(\sigma_\Lambda\) by \[Z^{\sigma_\Lambda}_G(A,\boldsymbol{\lambda})\sum_{\tau:V\to[q],\tau|_{\Lambda}=\sigma_\Lambda}w(\sigma)\] where \(\tau|_{\Lambda}\) denotes the restriction of the configuration \(\tau\) on \(\Lambda\). For \(u,v\in V(G),\) we define \[Z^{\sigma_\Lambda,i}_{G,v}(A,\boldsymbol{\lambda})=\sum\limits_{\sigma|_{\Lambda}=\sigma_\Lambda,\sigma(v)=i}w(\sigma) \text{ and } Z^{\sigma_\Lambda,i,j}_{G,v,u}(A,\boldsymbol{\lambda})=\sum\limits_{\sigma|_{\Lambda}=\sigma_\Lambda,\sigma(v)=i,\sigma(u)=j}w(\sigma).\] If \(v\in\Lambda\) is already pinned to some \(j\in[q]\), then automatically \(Z^{\sigma_\Lambda,i}_{G,v}=0\) for all \(i\neq j\) and \(Z^{\sigma_\Lambda,j}_{G,v}=Z^{\sigma_\Lambda}_{G}.\) Given a partial configuration \(\sigma_\Lambda\), for any \(\Lambda'\subset\Lambda,\) we denote \(\sigma_{\Lambda'}\) the restriction of \(\sigma_{\Lambda}\) on \(\Lambda'\), called a sub-partial configuration of \(\sigma_{\Lambda}\). In the rest of this paper, we omit the argument \((A,\lambda)\) of the partition functions for simplicity.

Now we generalize Theorem 4 to \(q\)-spin systems as the following:

8 Comparison with the cluster expansion approach↩︎

In [35], the local dependence of coefficients (LDC) property is proved using cluster expansions for the hard-core model. We first review the cluster expansion formulation. Then, we discuss its limitations in extending to general 2-spin systems, and explain why the Christoffel-Darboux type identity introduced in the present paper can circumvent the obstacle.

8.1 Review of the cluster expansion approach↩︎

For the hard-core model on a graph \(G=(V,E)\) with fugacity \(\lambda\), the ratio \[P_{G,v}(\lambda)=\frac{\lambda Z_{G\setminus N[v]}(\lambda)}{Z_G(\lambda)}\] (which for positive \(\lambda\) equals the marginal probability that vertex \(v\) is occupied) admits a series expansion around \(\lambda=0\) derived from the cluster expansion of the multivariate independence polynomial. Concretely, viewing \(Z_G(\lambda)\) as the specialization of the multivariate polynomial \(Z_G(\mathbf{w})=\sum_{I\subseteq V\atop I\text{ indep.}}\prod_{u\in I} w_u\) at \(w_u\equiv \lambda\), one obtains near \(\lambda=0\) \[\label{eq:cluster-expansion} P_{G,v}(\lambda)=\sum_{k\geq 1}\frac{1}{k!}\sum_{v_1,\dots,v_k\in V} \phi\bigl(G(v_1,\dots,v_k)\bigr)\,m_v(v_1,\dots,v_k)\,\lambda^k,\tag{3}\] where \(G(v_1,\dots,v_k)\) is the cluster induced by the (not necessarily distinct) vertices \(v_1,\dots,v_k\), \(\phi(H)\) is the Ursell function of a graph \(H\), and \(m_v(v_1,\dots,v_k)\) counts the occurrences of \(v\) among \(v_1,\dots,v_k\). Because \(\phi(H)=0\) unless \(H\) is connected, the coefficient of \(\lambda^k\) depends only on the \((k-1)\)-neighborhood of \(v\) in \(G\). This immediately yields the LDC property for the hard-core model.

For graph homomorphism measures, a similar cluster expansion is obtained by realizing the partition function as the independence polynomial of an auxiliary graph \(\Gamma\) whose vertices correspond to connected subgraphs of the original graph.

Let \(G=(V,E)\) be a graph and let \(A\) be a symmetric \(q\times q\) matrix. We consider the partition function with an external field \(\xi\in\mathbb{C}^{V\times[q]}\): \[Z_G(A,\xi)=\sum_{\phi:V\to[q]}\prod_{v\in V}\xi_{v,\phi(v)}\prod_{uv\in E}A_{\phi(u),\phi(v)}.\] Fix a boundary condition \(\sigma:\Lambda\to[q]\) on some \(\Lambda\subseteq V\setminus\{v\}\). The goal is to expand the ratio \[P_{G,v,i;A}^{\sigma}(z)=\frac{Z_{G,v,i}^{\sigma_{v,i}}(J+z(A-J))}{Z_G^{\sigma}(J+z(A-J))}\] around \(z=0\), where \(J\) is the all-ones matrix.

8.1.0.1 Auxiliary graph \(\Gamma\).

The vertex set of \(\Gamma\) consists of all connected subgraphs \(H=(S,F)\) of \(G\) with at least one edge (\(|F|\geq 1\)). Two vertices \(H_1=(S_1,F_1)\) and \(H_2=(S_2,F_2)\) are adjacent in \(\Gamma\) if and only if \(S_1\cap S_2\neq\emptyset\). Thus an independent set in \(\Gamma\) corresponds to a collection of pairwise vertex-disjoint connected subgraphs of \(G\).

8.1.0.2 Weights.

For a vertex \(H=(S,F)\) of \(\Gamma\), its weight \(w^{\sigma}(H)\) is defined as \[w^{\sigma}(H):= \frac{z^{|F|}\,Z_H^{\sigma}(A-J,\xi)}{\Bigl(\prod_{v\in S\setminus\Lambda}\sum_{i=1}^q\xi_{v,i}\Bigr)\cdot\prod_{v\in\Lambda\cap S}\xi_{v,\sigma(v)}},\] where \(Z_H^{\sigma}(A-J,\xi)\) is the partition function on \(H\) with edge matrix \(A-J\) and external field \(\xi\), under the boundary condition \(\sigma\) restricted to \(\Lambda\cap S\). Define also the prefactor \[p^{\sigma}(\xi):= \Bigl(\prod_{v\in V\setminus\Lambda}\sum_{i=1}^q\xi_{v,i}\Bigr)\cdot\prod_{v\in\Lambda}\xi_{v,\sigma(v)}.\]

8.1.0.3 Polymer representation.

Lemma 8 of [35] states that \[p^{\sigma}(\xi)\,Z_{\Gamma}(w^{\sigma}) = Z_G^{\sigma}(J+z(A-J),\xi),\] where \(Z_{\Gamma}(w^{\sigma})\) is the multivariate independence polynomial of \(\Gamma\) evaluated at the weights \(w^{\sigma}(H)\): \[Z_{\Gamma}(w^{\sigma}) = \sum_{\substack{\mathcal{I}\subseteq V(\Gamma)\\\mathcal{I}\text{ independent}}} \;\prod_{H\in\mathcal{I}} w^{\sigma}(H).\]

8.1.0.4 Cluster expansion of the ratio.

Applying the formal cluster expansion (7) to \(\log Z_{\Gamma}(w^{\sigma})\) and differentiating with respect to \(\xi_{v,i}\), one obtains the following series expansion for the ratio (see [35]): \[P_{G,v,i;A}^{\sigma}(z) = \frac{1}{q} + \sum_{\ell\geq 1} z^{\ell} \sum_{k\geq 1} \frac{1}{k!} \sum_{(H_1,\dots,H_k)\in \mathcal{C}_{v,\ell,k}(G)} \phi\bigl(\Gamma(H_1,\dots,H_k)\bigr)\, \frac{\partial}{\partial\xi_{v,i}} \prod_{j=1}^{k} \widehat{w}^{\sigma}(H_j)\Big|_{\xi=1},\] where

• \(\mathcal{C}_{v,\ell,k}(G)\) is the collection of sequences \((H_1,\dots,H_k)\) of connected subgraphs of \(G\) with at least two vertices satisfying \(\sum_{j=1}^{k}|E(H_j)|=\ell\), \(v\in\bigcup_{j=1}^{k}V(H_j)\), and the graph \(\Gamma(H_1,\dots,H_k)\) (the subgraph of \(\Gamma\) induced by \(\{H_1,\dots,H_k\}\)) is connected;

• \(\phi\) is the Ursell function;

• \(\widehat{w}^{\sigma}(H)=w^{\sigma}(H)\,z^{-|E(H)|}\) are the scaled weights.

The crucial observation is that the \(\ell\)-th coefficient of this series depends only on the subgraphs \(H_j\) whose vertex sets lie within distance \(\ell\) of \(v\) in \(G\). Consequently, the coefficients of \(z^{0},z^{1},\dots,z^{d-1}\) are identical for two boundary conditions that agree on the \(d\)-neighborhood of \(v\), yielding the LDC property.

8.2 Limitations of the cluster expansion approach for general 2‑spin systems↩︎

Despite its effectiveness for the restricted setting considered in [35], the cluster expansion formulation for graph homomorphisms suffers from two fundamental limitations that prevent its application to general 2‑spin systems.

1. Restricted parameter path. The expansion is derived for a partition function whose edge matrix varies along the specific one‑parameter trajectory \(A(z)=J+z(A-J)\). In other words, the zero‑freeness assumption must hold for a whole family of matrices that interpolate linearly between the all‑ones matrix \(J\) and the target matrix \(A\). For a general 2‑spin system with edge activities \(\beta\) and \(\gamma\), the analogous statement would require zero‑freeness for all parameters lying on a line segment connecting \((\beta,\gamma)=(1,1)\) to the desired values. This is far more restrictive than the univariate zero‑free regions (e.g., in \(\lambda\) alone or in \(\beta\) alone).

2. Absence of expansion in the external field variables. The cluster expansion used above treats the auxiliary vertex weights \(w^{\sigma}(H)\) as power series in the single variable \(z\), while the external field parameters \(\xi_{v,i}\) are merely spectators. No expansion is performed in the \(\xi\) variables themselves. Consequently, the method does not yield a multivariate series expansion of the ratios as functions of several independent complex parameters. In a general 2‑spin system, one may need to expand simultaneously in \(\lambda\), \(\beta\), and \(\gamma\) to obtain LDC around different points (e.g., \(\lambda=0\) for arbitrary \(\beta,\gamma\), or \(\beta\gamma=1\) for arbitrary \(\lambda\)). The cluster expansion approach, being inherently univariate in its current form, cannot yield such a unified multi‑parameter LDC statement.

In contrast, the Christoffel–Darboux type identity established in this paper makes no reference to any specific parameter trajectory and does not require a convergent series expansion in any of the variables. It directly factors the algebraic difference of partition functions with different pinned vertices, revealing powers of \(\lambda\) and \(\beta\gamma-1\) that depend only on the graph distance. This purely combinatorial identity therefore yields LDC uniformly for all three parameters and applies to zero‑free regions of arbitrary shape, overcoming the restrictions of the cluster expansion framework.

References↩︎

---

1. In a recent follow-up work [1], this framework has been further extended to more general settings, including hypergraph independence polynomials, random cluster models, Potts models, and Holant problems, thereby yielding new SSM results in these settings.↩︎

2. School of Computer Science and Technology & Hefei National Laboratory, University of Science and Technology of China. Supported by the Innovation Program for Quantum Science and Technology, 2021ZD0302901.↩︎

3. École Polytechnique. This work was done while Xiaowei Ye was an undergraduate student at the School of the Gifted Young, University of Science and Technology of China.↩︎

4. There are weak spatial mixing and strong spatial mixing. Weak spatial mixing just refers to the correlation decay property; strong spatial mixing requires that correlations between spins decay exponentially with distance even when conditioning on a pre-described partial configuration.↩︎

5. While there are cluster expansion results for lattice structures [38], it is unknown whether these results can be extended to general graphs.↩︎

6. In fact, we establish an identity for the more general \(q\)-spin system in the appendix, see Theorem [thm:CD-q-spin].↩︎

7. In order to obtain an FPTAS for non-disk zero-free regions via Barvinok’s algorithm, such regions must be mapped to a disk by polynomials [23]. While by using Riemann mapping theorem, one can establish SSM and obtain an FPTAS via Weitz’s algorithm for zero-free regions of arbitrary shapes.↩︎

8. Zeros of the partition function of the Ising model regarding \(\beta\) are known as Fisher zeros [45].↩︎