View PDF HTML (experimental)

Abstract:We study the algorithmic implications of zero-free regions for the partition functions of 2-spin systems. While Barvinok's algorithm yields FPTASes in such regions, the applicability of Weitz's algorithm is limited to parameter regimes where strong spatial mixing (SSM) can be established. It remains open whether Weitz's algorithm can be applied to general zero-free regions, particularly in settings where no standard tree-recurrence-based proof of SSM is known. We establish new SSM results and thereby extend the applicability of Weitz's FPTAS to all currently known zero-free regions of 2-spin systems with pinned vertices. We achieve this through a unified approach to deriving SSM from zero-freeness in the most general settings of 2-spin systems. Our work features two key innovations.
this http URL SSM results cover parts of the celebrated Lee-Yang zero-free region for the ferromagnetic Ising model, where no tree-recurrence-based proof of SSM is currently known or considered feasible. The tree recurrence method typically relies on carefully designed potential functions, the construction and analysis of which can be highly challenging. For ferromagnetic 2-spin systems, it remains an open challenge whether such potential functions can be constructed. We circumvent this difficulty by deriving SSM directly from zero-freeness.
this http URL prior approach to deriving SSM from zero-freeness relies on cluster expansions, which are model-specific and known only for a few restricted parameter settings such as the hard-core model near vertex activity $\lambda=1$. We overcome this obstacle by introducing a purely combinatorial approach based on a novel Christoffel-Darboux-type identity that holds universally for 2-spin systems. This provides a broadly applicable framework for handling general 2-spin systems with arbitrary multivariate parameters and zero-free regions of arbitrary shape in a unified manner.

Submission history

From: Xiaowei Ye [view email]
[v1] Wed, 17 Jan 2024 16:41:57 UTC (561 KB)
[v2] Wed, 10 Apr 2024 15:00:11 UTC (561 KB)
[v3] Sat, 8 Feb 2025 12:06:16 UTC (757 KB)
[v4] Thu, 16 Jul 2026 15:46:41 UTC (306 KB)