Zero-Freeness Is All You Need: A Weitz-Type FPTAS for the Entire Lee–Yang Zero-Free Region

Our algorithm is a Weitz-type algorithm for two reasons. First, it expresses the partition function as a telescoping product of certain ratios and the key is to approximate each ratio. Secondly, in order to give a good approximation of the ratios, it uses the SAW tree and truncates it at logarithmic depth. However, crucial differences distinguish our algorithm from the standard Weitz algorithm, ensuring that our algorithm does not rely on SSM. First, instead of approximating the marginal probability $P_v=\frac{Z_{G,\sigma (v)=+}}{Z_G}$ of a vertex $v$ being assigned spin $+$, we approximate a carefully designed edge-deletion ratio $P_e=\frac{Z_{G-e}}{Z_G}$ where $G-e$ denotes the graph obtained from $G$ by removing an edge $e$. Second, since SSM is unavailable, we cannot argue that truncating the SAW tree yields a good approximation. Inspired by Barvinok’s algorithm, we show that each edge-deletion ratio viewed as a function on $\lambda$ can be well approximated by truncating its Taylor expansion series at logarithmic degree.

A key difference from Barvinok’s algorithm is that, while in the Barvinok framework the low-order Taylor coefficients are computed via subgraph counting [21, 19], we compute these coefficients still via recursion on the SAW tree. The idea of using SAW-tree recursions to compute low-order coefficients has also been explored by Bencs and Regts [7], who compute low-order Taylor coefficients of $\log Z$. We note that their method remains Barvinok-type, as their goal is to approximate $\log Z$. In contrast, our approach is a genuinely Weitz-style telescoping algorithm that directly approximates each ratio using the SAW tree. Thus, although both approaches use recursive computation of Taylor coefficients, their algorithmic structures and objectives differ substantially.

The replacement of $P_v$ by $P_e$ is crucial for the above method to work. In fact, it is impossible to show that $P_v$ could be approximated by logarithmic-degree Taylor truncation, since this would imply SSM throughout the Lee–Yang region contradicting known impossibility results [3]. The obstruction comes from the fact that, as shown in [28], the ratio $P_v$ viewed as a function on $\lambda$ and its SAW-tree version $P_v^{T_k}$ truncated at depth $k$ share the same first $k$ coefficients, known as local dependence of coefficients (LDC). Hence, if the Taylor expansion series $f_k$ truncated at degree $k$ approximates $P_v$ well, i.e., $|P_v-f_k|\le C{r}^{-k}$ for some positive constants $C$ and $r>1$, then $f_k$ also approximates $P_v^{T_k}$ well. Then, by a triangle inequality, one would have $|P_v-P_v^{T_k}|\le 2C{r}^k$, which is the standard SSM for the Ising model.

The above argument further implies that if LDC can be established for edge-deletion ratios, then together with zero-freeness, which guarantees good approximation by Taylor series of logarithmic degree, we obtain a form of SSM for these ratios. In other words, zero-freeness plus LDC implies SSM. In this paper, we further show that such a LDC property indeed holds for the Ising model with arbitrary parameters $\beta$ and $\lambda$, including regimes beyond the Lee-Yang zero-free region. Thus, together with the Lee-Yang theorem, we establish SSM for edge-deletion ratios¹¹1We actually prove a more general form of SSM; see Theorem 13. across the entire zero-free region. In summary, for Weitz-type FPTASes, zero-freeness alone suffices, while for edge-deletion SSM, one additionally needs LDC, a combinatorial property independent of zero-freeness.

Quite remarkably, the choice of the edge-deletion ratio is not only crucial for a Weitz-type FPTAS for the Ising model, but it also admits a probabilistic interpretation in the Ising related random cluster model. It corresponds exactly to the marginal probability that an edge is included in the random cluster model. Thus, our edge-deletion SSM implies standard SSM for the random cluster model. This is the first SSM result for the random cluster model on general graphs, whereas all previous results were confined to lattices. As brief background, the random cluster model associated the ferromagnetic Ising model is parameterized by edge parameters $p$ and vertex parameters $\lambda$. For an edge $e\in E$ and a partial edge configuration ${\sigma }_{\mathrm{\Lambda }}$ specified on $\mathrm{\Lambda }\subseteq E(G)$, let $P_{G,e}^{\sigma \mathrm{\Lambda }}$ denote the marginal probability under the random cluster distribution that edge $e$ is excluded conditioned on ${\sigma }_{\mathrm{\Lambda }}$.

Beyond introducing the notion of edge-deletion SSM, a main technical contribution of this paper is a broadly applicable method for establishing LDC. The LDC property was first shown implicitly in [25] using cluster expansion, an analytic method applicable to the hard-core model, and was later formally introduced and extended to general 2-spin systems [28] using a combinatorial approach based on a Christoffel-Darboux type identity. In this paper, we substantially generalize the combinatorial framework by circumventing the need of explicit identities: a more applicable division relation proved via a delicate one-to-one correspondence already suffices for LDC. We show that such division relations hold broadly across diverse models including the Potts model, the hypergraph independence polynomial, and binary symmetric Holant problems. For each model, combining division relations with existing zero-free regions yields new SSM results, thereby broadening the applicability of correlation-decay techniques.

As an example, we prove the following LDC and SSM properties for the hypergraph independence polynomial. We define $P_{H,v}^{{\sigma }_{\mathrm{\Lambda }}}(\lambda )$ as the standard marginal probability of the vertex $v$ being occupied in hypergraph $H$ under the partial configuration ${\sigma }_{\mathrm{\Lambda }}$ on $\mathrm{\Lambda }\subseteq V(H)$.

Combining this LDC property with the optimal zero-free region of [5], where ${\lambda }_c(\mathrm{\Delta })=\frac{{(\mathrm{\Delta }-1)}^{\mathrm{\Delta }-1}}{{(\mathrm{\Delta }-2)}^{\mathrm{\Delta }}}$ and ${\lambda }_s(\mathrm{\Delta })=\frac{{(\mathrm{\Delta }-1)}^{\mathrm{\Delta }-1}}{{\mathrm{\Delta }}^{\mathrm{\Delta }}}$, we obtain the following new SSM result.

The paper is organized as follows. In Section 3, to derive the Weitz-type algorithm, we show that the truncated series provides a good approximation of the edge-deletion ratio using zero-freeness, and then analyze the truncated series through the self-avoiding walk tree and operations on formal power series. This yields the FPTAS. In Section 4, we introduce the framework in which zero-freeness implies SSM via LDC, and establish the SSM property in terms of edge activities for the ferromagnetic Ising model, using the Lee–Yang theorem and the divisibility relation. This edge-based SSM property further implies the standard SSM of the corresponding random-cluster model. In Section 5, we extend the divisibility relation to various models and derive their SSM properties. Omitted proofs can be found in the full paper [26].

For a graph $G=(V,E)$, with edge activities $𝜷={({\beta }_e)}_{e\in E}$ and vertex activities $𝝀={({\lambda }_v)}_{v\in V}$, the weight of a configuration $\sigma :V\to \{+,-\}$ is given by

where $m(\sigma )=\{e=(u,v)\in E\mid {\sigma }_u={\sigma }_v\}$ is the set of edges whose endpoints have the same spin, and $n(\sigma )=\{v\in V\mid {\sigma }_v=+\}$ is the set of vertices assigned spin +. The patition function of the Ising model is defined by $Z_G(𝜷,𝝀)={\sum }_{\sigma :V\to \{+,-\}}w(\sigma )$. The celebrated Lee–Yang theorem states the zero-free region of the Ising model.

A partial configuration of the Ising model is a mapping $\sigma :\mathrm{\Lambda }\to \{+,-\}$ for some $\mathrm{\Lambda }\subseteq V$, which may be empty. The conditional partition function is defined as $Z_G^{{\sigma }_{\mathrm{\Lambda }}}(𝜷,𝝀)={\sum }_{\begin{array}{c}\sigma :V\to \{+,-\}\\ {\sigma |}_{\mathrm{\Lambda }}={\sigma }_{\mathrm{\Lambda }}\end{array}}$ where ${\sigma |}_{\mathrm{\Lambda }}$ denotes the restriction of the configuration $\sigma$ on $\mathrm{\Lambda }$. Let $u,v\in V$, then define

Conditional partition functions for the remaining pinning choices $Z_{G,v}^{{\sigma }_{\mathrm{\Lambda }},-}(𝜷,𝝀)$, $Z_{G,v,u}^{{\sigma }_{\mathrm{\Lambda }},+,-}(𝜷,𝝀)$, $Z_{G,v,u}^{{\sigma }_{\mathrm{\Lambda }},-,+}(𝜷,𝝀)$ and $Z_{G,v,u}^{{\sigma }_{\mathrm{\Lambda }},-,-}(𝜷,𝝀)$ are defined analogously. Then the conditional marginal probability that $v$ is pinned to $+$ given the partial configuration ${\sigma }_{\mathrm{\Lambda }}$ and the corresponding marginal ratio are defined as

In the seminal work of Weitz [31], the self-avoiding walk (SAW) tree reduces the computation of marginal probabilities for 2-spin models on general graphs to the corresponding computation on trees. If the graph $G=(V,E)$ has maximum degree $\mathrm{\Delta }$, then the SAW tree $T_{\text{SAW}}(G,v)$ rooted at $v\in V$ also has maximum degree $\mathrm{\Delta }$. Moreover, the marginal probability and marginal ratio at $v$ in $G$ coincide with those at the root of $T_{\text{SAW}}(G,v)$ (with some leaves possibly pinned).

Consider a rooted tree $T=(V,E)$ with root $r\in V$. Suppose $r$ has $d$ children $v_1,\mathrm{\dots },v_d$. Removing $r$ yields $d$ subtrees $T_1,\mathrm{\dots },T_d$, where $T_i$ is rooted at $v_i$. Let $R_{T_i,v_i}$ denote the marginal ratio at $v_i$ in $T_i$ (e.g., $R_{T_i,v_i}=Z_{T_i,v_i}^{+}/Z_{T_i,v_i}^{-}$), and let $R_{T,r}$ be the marginal ratio at $r$ in $T$. Then the tree recursion expressing $R_{T,r}$ in terms of the $R_{T_i,v_i}$ is given by a multivariate map $F_d:{\widehat{ℂ}}^d\to \widehat{ℂ}$:

where $\widehat{ℂ}=ℂ\cup \{\mathrm{\infty }\}$ is the extended complex plane, $\beta ,\gamma$ are the edge-interaction parameters, and $\lambda$ is the external field. For the ferromagnetic Ising model, we have $\beta =\gamma >1$.

A region is a connected open set in $ℂ$. In particular, an open disk with one interior point removed is also a region. We denote by ${𝔻}_{\rho }(z_0)$ the open disk centered at $z_0$ with radius $\rho$, and by $\partial {𝔻}_{\rho }(z_0)$ its boundary circle. If $z_0=0$, we simply write ${𝔻}_{\rho }$ and $\partial {𝔻}_{\rho }$; if $\rho =1$, we omit the subscript $\rho$. Let $f(z)={\sum }_{k\ge 0}{a}_k{z}^k$ be a (formal) power series, and write its truncation to degree $m$ as

The following lemma is a standard result of complex analysis textbook.

Applying Lemma 7 requires a uniform bound on a circle for a family of analytic functions. In [25], Regts employed Montel’s theorem to obtain such bounds, leading to the following result.

Next, assume the first $m+1$ coefficients of $f$ and $g$ are given. We can compute ${(kf)}^{[m]}$ and ${(f+g)}^{[m]}$ in $O(m)$ arithmetic operations, and ${(fg)}^{[m]}$ as well as ${(f/g)}^{[m]}$ (assuming $g(0)\ne 0$) in $O(m\log m)$ operations using FFT-based multiplication and Newton iteration; see, e.g., [30, Secs. 8.2 and 9.1].

To show the truncation series gives a good approximation via Lemma 7, we apply Lemma 8 to obtain a uniform bound of $P_{G,e}(\lambda )$ for all graph $G$ and edge $e\in G$. This requires that $P_{G,e}(\lambda )$ avoid $0$ and $1$ for all graph $G$ and edge $e\in G$.

Then a uniform bound of $P_{G,e}(\lambda )$ for all graph $G$ and edge $e\in G$ follows from Lemma 8, where the upper bound (for a circle) is used to establish the additive error in Lemma 7, and the lower bound (for a single point) is used to turn the additive error into a multiplicative error.

Write $e_i=(u,v)$. By the definition of the Ising model, we have

It holds because if $u$ and $v$ have the same spin, the only extra contribution in $Z_{G_i}$ (compared with $Z_{G_{i-1}}$) is the edge $e_i=(u,v)$, which contributes a factor of $\beta$. Dividing numerator and denominator by $Z_{G_i,u,v}^{-,-}$ and substituting the ratio identities

we have

To calculate $P_{G_i,e_i}{(\lambda )}^{[k]}$, it suffices to calculate the ratios $R_{G_i,v}^{u^{+}}{(\lambda )}^{[k]}$, $R_{G_i,u}^{v^{-}}{(\lambda )}^{[k]}$ and $R_{G_i,v}^{u^{-}}{(\lambda )}^{[k]}$. This can be done by the tree recursion on the self-avoiding walk tree $T_{\text{SAW}}(G_i^{u^{+}},v)$, $T_{\text{SAW}}(G_i^{v^{-}},u)$ and $T_{\text{SAW}}(G_i^{u^{-}},v)$ respectively. Recall the tree recursion formula $R_{T,r}(\lambda )=\lambda {\prod }_{i=1}^d\frac{\beta R_{T_i,v_i}(\lambda )+1}{R_{T_i,v_i}(\lambda )+\beta }.$ To compute $R_{T,r}{(\lambda )}^{[k]}$, it suffices to compute the truncated series of ${\prod }_{i=1}^d\frac{\beta R_{T_i,v_i}(\lambda )+1}{R_{T_i,v_i}(\lambda )+\beta }$ up to degree $k-1$; hence, for each child $v_i$ we require $R_{T_i,v_i}{(\lambda )}^{[k-1]}$. Therefore $R_{T,r}{(\lambda )}^{[k]}$ can be obtained by traversing the truncated self-avoiding walk tree to depth $k$ and, for every node at depth $i\in [0,k]$, computing the truncated series of its ratio to degree $k-i$. Suppose $T$ has maximum degree $\mathrm{\Delta }$. At each node, we multiply at most $\mathrm{\Delta }$ series and perform one division, which costs $O(\mathrm{\Delta }k\log k)$ using FFT-based series arithmetic. The truncated SAW tree to depth $k$ has $O({\mathrm{\Delta }}^k)$ nodes. Hence the total running time is $O({\mathrm{\Delta }}^k\cdot \mathrm{\Delta }k\log k)=O({\mathrm{\Delta }}^{k+1}k\log k)$.

If $G$ has maximum degree $\mathrm{\Delta }$, then the self-avoiding walk tree $T_{\text{SAW}}(G_i^{u^{+}},v)$, $T_{\text{SAW}}(G_i^{v^{-}},u)$ and $T_{\text{SAW}}(G_i^{u^{-}},v)$ also have maximum degree $\mathrm{\Delta }$. Thus, the time complexity for computing $P_{G_i,e_i}{(\lambda )}^{[k]}$ is $O(k\log k{\mathrm{\Delta }}^{k+1})$.

Our algorithm shows that SSM is unnecessary for a Weitz-type FPTAS, as we do not rely on SSM for the marginal probability of a vertex being assigned a particular spin. Instead, it is crucial for our algorithm to replace marginal probabilities of vertices by edge-deletion ratios, which eliminates the need for SSM. In the next section, we show that, even though the standard notion of SSM does not hold, by further proving the local dependence of coefficients (LDC), a combinatorial property independent of zero-freeness, we can indeed establish a new form of SSM for edge deletion ratios. Thus, zero-freeness alone gives Weitz-type FPTASes, while zero-freeness plus LDC gives new forms of SSM.

By [28], a key ingredient in establishing SSM from zero-freeness is the local dependence of coefficients (LDC). For further details, we refer to the full version. In this section, we focus on proving LDC by proving a division relation using a combinatorial bijection.

We establish a divisibility relation that implies the LDC.