论文标题
有关零分区函数的零和近似的更多信息
More on zeros and approximation of the Ising partition function
论文作者
论文摘要
我们考虑计算分区函数$ \ sum_x e^{f（x）} $的问题，其中$ f：\ { - 1，1，1，1 \}^n \ longrightArrow {\ bbb r} $是boolean cube $ \ \ \ { - 1，1，1，1，1 \}^n $的Quadratic或cubtic多项式。在二次多项式$ f $的情况下，我们表明可以在quasi-polynomial $ n^{o（\ ln n n-\ ln n- \ ln-\ ln-\ ln-\ ln-\ lnε）} $ time中近似$ 0 <ε<1 $ $ 0 <ε<1美元$ 1-δ$，对于任何$δ> 0 $，提前修复。对于立方多项式$ f $，我们在较强的情况下获得了相同的结果。 我们应用了多项式插值的方法，为此，我们证明了$ \ sum_x e^{\ tilde {f}（x）} \ ne 0 $对于复杂价值的多项式$ \ tilde {f} $在满足上述情况下的真实价值$ f $的社区中。边界在渐近上是最佳的。无零区域的结果被解释为在相应的ISING模型中的Lee -Yang Sense中没有相变。边界的新特征是，它们控制每个顶点的总相互作用，但并非每一个相互作用的顶点相互作用。
We consider the problem of computing the partition function $\sum_x e^{f(x)}$, where $f: \{-1, 1\}^n \longrightarrow {\Bbb R}$ is a quadratic or cubic polynomial on the Boolean cube $\{-1, 1\}^n$. In the case of a quadratic polynomial $f$, we show that the partition function can be approximated within relative error $0 < ε< 1$ in quasi-polynomial $n^{O(\ln n - \ln ε)}$ time if the Lipschitz constant of the non-linear part of $f$ with respect to the $\ell^1$ metric on the Boolean cube does not exceed $1-δ$, for any $δ>0$, fixed in advance. For a cubic polynomial $f$, we get the same result under a somewhat stronger condition. We apply the method of polynomial interpolation, for which we prove that $\sum_x e^{\tilde{f}(x)} \ne 0$ for complex-valued polynomials $\tilde{f}$ in a neighborhood of a real-valued $f$ satisfying the above mentioned conditions. The bounds are asymptotically optimal. Results on the zero-free region are interpreted as the absence of a phase transition in the Lee - Yang sense in the corresponding Ising model. The novel feature of the bounds is that they control the total interaction of each vertex but not every single interaction of sets of vertices.
