# On the zeros of partition functions with multi-spin interactions

Alexander Barvinok  Department of Mathematics, University of Michigan, Ann
Arbor, MI 48109-1043, USA  barvinokumich.edu

(June 27, 2024)

Let $X_{1},\ldots,X_{n}$ be probability spaces, let $X$ be their direct
product, let $\phi_{1},\ldots,\phi_{m}:X\longrightarrow{\mathbb{C}}$ be random
variables, each depending only on a few coordinates of a point
$x=(x_{1},\ldots,x_{n})$, and let $f=\phi_{1}+\ldots+\phi_{m}$. The
expectation $\mathbb{E}\thinspace e^{\lambda f}$, where
$\lambda\in{\mathbb{C}}$, appears in statistical physics as the partition
function of a system with multi-spin interactions, and also in combinatorics
and computer science, where it is known as the partition function of edge-
coloring models, tensor network contractions or a Holant polynomial. Assuming
that each $\phi_{i}$ is 1-Lipschitz in the Hamming metric of $X$, that each
$\phi_{i}(x)$ depends on at most $r\geq 2$ coordinates $x_{1},\ldots,x_{n}$ of
$x\in X$, and that for each $j$ there are at most $c\geq 1$ functions
$\phi_{i}$ that depend on the coordinate $x_{j}$, we prove that
$\mathbb{E}\thinspace e^{\lambda f}\neq 0$ provided $|\lambda|\leq\
(3c\sqrt{r-1})^{-1}$ and that the bound is sharp up to a constant factor.
Taking a scaling limit, we prove a similar result for functions
$\phi_{1},\ldots,\phi_{m}:{\mathbb{R}}^{n}\longrightarrow{\mathbb{C}}$ that
are 1-Lipschitz in the $\ell^{1}$ metric of ${\mathbb{R}}^{n}$ and where the
expectation is taken with respect to the standard Gaussian measure in
${\mathbb{R}}^{n}$. As a corollary, the value of the expectation can be
efficiently approximated, provided $\lambda$ lies in a slightly smaller disc.

partition function, spin systems, hypergraphs, edge-coloring models, zeros,
algorithm, interpolation method, numerical integration, Lee-Yang stability

###### :

82B20, 30C15, 68R05, 68W25

††support: This research was partially supported by NSF Grant DMS 1855428.

## 1\. Introduction and the main results

We investigate the complex zeros and computational complexity of functionals
of a particular type, which appear under different names in statistical
physics, computer science, and combinatorics. The functionals can be viewed as
the partition function of a spin system with multiple spin interactions
(statistical physics) or as the partition function of a hypergraph edge-
coloring model, also known as a tensor network contraction, or as a Holant
polynomial (combinatorics and computer science).

In what follows, we consider functions on the direct product
$X_{1}\times\ldots\times X_{n}$ of probability spaces. For a point $x\in X$,
$x=\left(x_{1},\ldots,x_{n}\right)$, we refer to $x_{j}\in X_{j}$ as the
$j$-th coordinate of $x$. The Hamming distance between two points $x,y\in X$
is the number of the coordinates where they differ:

$\operatorname{dist}(x,y)=\left|j:\ x_{j}\neq
y_{j}\right|,\quad\text{where}\quad
x=\left(x_{1},\ldots,x_{n}\right)\quad\text{and}\quad
y=\left(y_{1},\ldots,y_{n}\right).$

We prove the following main result.

###### (1.1) Theorem

Let $X_{1},\ldots,X_{n}$ be probability spaces, let $X=X_{1}\times\ldots\times
X_{n}$ be the product space and let
$\phi_{1},\ldots,\phi_{m}:X\longrightarrow{\mathbb{C}}$ be measurable
functions. Assume that

Let

$f=\sum_{i=1}^{m}\phi_{i}$

and suppose that $\lambda$ is a complex number such that

$|\lambda|\ \leq\ {1\over 3c\sqrt{r-1}}.$

Then

$\mathbb{E}\thinspace e^{\lambda f}\neq 0.$

Moreover, if, additionally,

$\left|\phi_{i}(x)\right|\ \leq\ L\quad\text{for all}\quad x\in
X\quad\text{and}\quad i=1,\ldots,m$ $None$

and some $L>0$, then

$e^{|\lambda|mL}\ \geq\ \left|\mathbb{E}\thinspace e^{\lambda f}\right|\ \geq\
e^{-|\lambda|mL}\left(\cos{\pi\over 4\sqrt{r-1}}\right)^{n}.$ $None$

We prove Theorem 1.1 in Section 2, and in Section 4 we show that the bound for
$|\lambda|$ is optimal, up to a constant factor. The method of proof extends
those of [Ba17] and [BR19]. The dependence on $r$ is worth noting. One
approach frequently used for problems of this type is the cluster expansion
method, see [Je24] for a recent survey. In the situation of Theorem 1.1 it
apparently gives only $|\lambda|=\Omega(1/rc)$ as a bound for the zero-free
region, while also requiring $|\phi_{i}|$ to remain uniformly bounded [Ca+22].

The dependence on $r$ allows us to obtain a zero-free region for a partition
function which can be considered as a scaling limit of that of Theorem 1.1. We
consider the standard Gaussian probability measure in ${\mathbb{R}}^{n}$ with
density

${1\over(2\pi)^{n/2}}\exp\left\\{-{1\over
2}\left(x_{1}^{2}+\ldots+x_{n}^{2}\right)\right\\}\quad\text{for}\quad
x=\left(x_{1},\ldots,x_{n}\right)$

and prove the following result.

###### (1.2) Theorem

Let $\phi_{1},\ldots,\phi_{m}:{\mathbb{R}}^{n}\longrightarrow{\mathbb{C}}$ be
functions on Euclidean space ${\mathbb{R}}^{n}$, endowed with the standard
Gaussian probability measure. Assume that

Let

$f=\sum_{i=1}^{m}\phi_{i}$

and suppose that $\lambda$ is a complex number such that

$|\lambda|\ <\ {1\over 6c\sqrt{r-1}}.$

Then

$\mathbb{E}\thinspace e^{\lambda f}\neq 0.$

Moreover, if, additionally,

$\left|\phi_{i}(x)\right|\ \leq\ L\quad\text{for all}\quad
x\in{\mathbb{R}}^{n}\quad\text{and}\quad i=1,\ldots,m$ $None$

and some $L>0$, then

$e^{|\lambda|mL}\ \geq\ \left|\mathbb{E}\thinspace e^{\lambda f}\right|\ \geq\
e^{-|\lambda|mL}e^{-\pi^{2}n/32r}.$ $None$

We prove Theorem 1.2 in Section 3.

Suppose we want to approximate the value of $\mathbb{E}\thinspace e^{\lambda
f}$ efficiently. As we are dealing with complex numbers, it is convenient to
adopt the following definition: we say that a complex number $z_{1}\neq 0$
approximates another complex number $z_{2}\neq 0$ within relative error
$\epsilon$ if $z_{1}=e^{w_{1}}$ and $z_{2}=e^{w_{2}}$ for some $w_{1}$ and
$w_{2}$ such that $|w_{1}-w_{2}|\leq\epsilon$.

Let us fix some $0<\delta<1$. From by now standard method of polynomial
interpolation [Ba16], [PR17], it follows that for any $\lambda$ such that

$|\lambda|\ \leq\ {1-\delta\over 3c\sqrt{r-1}}\quad\text{(in Theorem
1.1)}\quad\text{or}\quad|\lambda|\ \leq\ {1-\delta\over
6c\sqrt{r-1}}\quad\text{(in Theorem 1.2)}$

approximating the value of $\mathbb{E}\thinspace e^{\lambda f}$ within
relative error $0<\epsilon<1$ reduces to the computation of the $m^{k}$
expectations

$\mathbb{E}\left(\phi_{i_{1}}\cdots\phi_{i_{k}}\right)\quad\text{for all}\quad
1\leq i_{1},i_{2},\ldots,i_{k}\leq m.$

where

$k=O_{\delta}\left(\ln(m+n)-\ln\epsilon\right).$

We sketch the algorithm in Section 5. In many applications of Theorem 1.1 the
probability spaces $X_{j}$ are finite. Assuming that each $X_{j}$ contains at
most $q$ elements, computing each expectation
$\mathbb{E}\left(\phi_{i_{1}}\cdots\phi_{i_{k}}\right)$ by the direct
enumeration takes $O\left(q^{rk}\right)$ time, provided we have an access to
the values of $\phi_{i}(x)$ for a given $x\in X$. If the parameter $r$ is
fixed in advance, we obtain a quasi-polynomial algorithm of
$(q(m+n))^{O(\ln(m+n)-\ln\epsilon)}$ complexity to approximate
$\mathbb{E}\thinspace e^{\lambda f}$ within relative error $0<\epsilon<1$.
Moreover, the general technique of Patel and Regts [PR17] allows one to speed
it up to a genuinely polynomial time algorithm of
$\bigl{(}q(m+n)\epsilon^{-1}\bigr{)}^{O(1)}$ complexity, provided the
parameter $c$ is also fixed in advance. In the context of Theorem 1.2, the
expectations $\mathbb{E}\left(\phi_{i_{1}}\cdots\phi_{i_{k}}\right)$ are
represented by integrals in the space of dimension at most $kr$ and often can
be efficiently computed or approximated with high accuracy, assuming again
that $r$ is fixed in advance. In that case, we also obtain an algorithm of
quasi-polynomial complexity to approximate $\mathbb{E}\thinspace e^{\lambda
f}$.

As we mentioned, the expectation $\mathbb{E}\thinspace e^{\lambda f}$ appears
in several different, though closely related contexts.

### (1.3) Statistical physics: partition functions of systems with multi-spin
interactions

Here we describe the statistical physics context of Theorem 1.1. Suppose that
we have a system of $n$ particles, where the $j$-th particle can be in a state
described by a point $x_{j}\in X_{j}$, also called the spin of the particle.
The vector $x=\left(x_{1},\ldots,x_{n}\right)$ of all spins is called a spin
configuration. The particles interact in various ways, and the energy of a
spin configuration is given by a function $-f(x_{1},\ldots,x_{n})$. Then for a
real $\lambda>0$, interpreted as the inverse temperature, the value of
$\mathbb{E}\thinspace e^{\lambda f}$ is the partition function of the system,
see, for example, [FV18] for the general setup. If the function $f$ is written
as a sum of $\phi_{i}$, as in Theorem 1.1, then the energy of the system is a
sum over subsystems, each containing at most $r$ particles, and each particle
participating in at most $c$ subsystems.

The idea to relate complex zeros of the partition function
$\lambda\longmapsto\mathbb{E}\thinspace e^{\lambda f}$ to the physical
phenomenon of phase transition apparently goes back to Mayer [Ma37], when it
became known as “Mayer’s conjecture”, see Section 4.12.3 of [FV18] for a
discussion. It then took off with the classical works of Lee and Yang [YL52],
[LY52], who showed that zero-free regions like the one described by Theorem
1.1 correspond to regimes with no phase transition.

In terms of Theorem 1.1, the most studied case is that of $r=2$, which
includes the classical Ising, Potts and Heisenberg models, see [FV18]. In that
case, we have a (finite) graph $G=(V,E)$ with set $V$ of vertices and set $E$
of edges. The particles are identified with the vertices of $G$, the spins are
$\pm 1$ in the case of the Ising model, elements of some finite set in the
case of the Potts model, or vectors in Euclidean space, in the case of the
Heisenberg model. The interactions are pairwise and described by the functions
attached to the edges of $E$. Hence, in the context of Theorem 1.1, we have
$r=2$ and $c$ is the largest degree of a vertex of $G$. Starting with [LY52],
the complex zeros of the partition function of systems with pairwise
interactions were actively studied in great many papers. We refer to [FV18]
for earlier, and to [B+21], [G+22], [PR20], [P+23] for more recent works.

Zero-free regions for systems with multiple spin interactions were considered
by Suzuki and Fisher [SF71], again in connection with phase transition, see
also [L+19] and [L+16] for recent developments. In this case, the particles
are identified with the vertices of a hypergraph, while functions attached to
the edges (sometimes called hyperedges) of the hypergraph describe
interactions. In terms of Theorem 1.1, the maximum number of vertices of an
edge of the hypergraph is $r$, while $c$ is the largest degree of vertex. The
papers [SF71] and [L+19], respectively [L+16], consider rather special
ferromagnetic, respectively antiferromagnetic, types of interaction, so their
results are not directly comparable to ours. While [SF71], [L+19] and [L+16]
say more about those specific models, our Theorem 1.1 allows one to handle a
wider class of interactions.

### (1.4) Statistical physics: partition functions of interacting particles
with an external field

Here we give an example of how Theorem 1.2 applies to systems of pairwise
interacting particles, cf. [FV18]. For an integer $N>1$, let us consider $N$
particles represented as vectors $x^{(1)},\ldots,x^{(N)}$ in
${\mathbb{R}}^{d}$, chosen independently at random from the standard Gaussian
distribution in ${\mathbb{R}}^{d}$. Suppose that there are pairwise repulsive
constant forces, so that the total energy of the system is

$-f\left(x^{(1)},\ldots,x^{(N)}\right)=-\sum_{i\neq j}\|x^{(i)}-x^{(j)}\|,$

where $\|\cdot\|$ is the standard Euclidean norm in ${\mathbb{R}}^{d}$. The
energy is minimized when the particles are far away from each other. However,
the probability of a configuration with large pairwise distances is small, so
that the Gaussian density can be interpreted as an external force pushing the
particles towards the origin, In terms of Theorem 1.2, we have $n=dN$,
$m={N\choose 2}$, $r=2d$ and $c=N$. Theorem 1.2 establishes a zero-free region
of the order

$|\lambda|=\Omega\left({1\over N\sqrt{d}}\right)$

for the partition function $\mathbb{E}\thinspace e^{\lambda f}$. This model is
related to the old problem of finding a configuration of points on the unit
sphere in ${\mathbb{R}}^{d}$ that maximizes the sum of pairwise distances
between points, see [B+23] (we note that for large $d$ the standard Gaussian
measure in ${\mathbb{R}}^{d}$ is concentrated around the sphere
$\|x\|=\sqrt{d}$).

Essentially identical models described by Theorem 1.1 are studied in
connection with questions in combinatorics and theoretical computer science.

### (1.5) Combinatorics and computer science: edge-coloring models and tensor
network contractions

Let $G=(V,E)$ be a graph. Suppose now that every edge of $G$ can be in one of
the $k$ states $\\{1,\ldots,k\\}$, typically called “colors”. In terms of
Theorem 1.1, we have $n=|E|$ and $X_{1}=\ldots=X_{n}=\\{1,\ldots,k\\}$, so
that $X=\\{1,\ldots,k\\}^{E}$. Suppose further, that to each vertex $v$ of $G$
a function $\psi_{v}:X_{1}\times\ldots\times X_{n}\longrightarrow{\mathbb{C}}$
is attached, that depends only on the colors of the edges of $G$ that contain
$v$. The expression

$\sum_{x\in X}\prod_{v\in V}\psi_{v}(x)$ $None$

is known as the tensor network contraction, or the partition function of the
edge coloring model, or as a Holant polynomial, see [Re18] for relations
between different models, and references. For relations with spin systems in
statistical physics and also knot invariants, see [HJ93]. Assuming that
$\psi_{v}(x)\neq 0$ for all $x$ and $v$, we can write
$\psi_{v}(x)=\exp\left\\{\phi_{v}(x)\right\\}$ and (1.5.1) can be written as
the scaled expectation $\mathbb{E}\thinspace e^{\lambda f}$ of Theorem 1.1,
assuming the uniform probability measure in each space $X_{j}$. In the context
of Theorem 1.1, we have $c=2$, while $r$ is equal to the largest degree of a
vertex of $G$. Note that compared to the graph interpretation of the Ising and
Potts models from Section 1.3, the parameters $r$ and $c$ switch places.

A similar to (1.5.1) expression can be built for hypergraphs, in which case
$r$ is still the maximum degree of vertex, while $c$ becomes the maximum size
of an edge, see for example, Chapter 6 of [Ta11] for the discussion of the
partition function of a $k$-satisfiability problem.

In combinatorics and computer science, there is a lot of interest in efficient
approximation of (1.5.1), also in connection with zero-free regions [GG16],
[B+22], [Ca+22], [G+21], [Re18], since many interesting counting problems on
graphs and hypergraphs can be stated as a problem of computing (1.5.1). To
illustrate, we consider just one example of perfect matchings in a hypergraph,
see [Ta11] for further motivation.

Let $H=(V,E)$ be a hypergraph with set $V$ of vertices and set $E$ of edges.
We choose $X=\\{1,2\\}^{E}$ so that every edge of $H$ can be colored into one
of the two colors, which we interpret as the edge being selected or not
selected. We define $\psi_{v}(x)=1$ if exactly one edge containing $v$ is
selected, and $\psi_{v}(x)=0$ otherwise. Then (1.5.1) is exactly the number of
perfect matchings is $H$. Since deciding whether a hypergraph contains a
perfect matching is a well-known NP-complete problem, there is little hope to
approximate (1.5.1) efficiently. One can try to come up with a more
approachable version of the problem by modifying the definition of $\psi_{v}$
so that $\psi_{v}(x)=1$ if exactly one edge containing $v$ is selected, and
$\psi_{v}(x)=1-\delta$ otherwise, for some $0<\delta<1$. In this case, the sum
(1.5.1), while taken over all collections of edges of $H$, is “exponentially
tilted” towards perfect matchings. Thus every perfect matching is counted with
weight 1, and an arbitrary collection of edges is discounted exponentially in
the number of vertices where the perfect matching condition is violated. In
other words, the weight of a collection of edges is exponentially small in the
number of vertices that belong to any number of edges in the collection other
than 1.

The larger $\delta$ we are able to choose, the more (1.5.1) is tilted towards
perfect matchings. It follows from Theorem 1.1 via the interpolation method
that for a fixed $r$, there is a quasi-polynomial algorithm approximating
(1.5.1) for some $\delta=\Omega\left(1/c\sqrt{r}\right)$, where $c$ is the
maximum number of vertices in an edge of $H$ and $r$ is the largest degree of
vertex. The results [Ca+22] and [Re18] appear to allow only for
$\delta=\Omega\left(1/cr\right)$. We note that Theorem 1.1 allows us to choose

$\psi_{v}=\exp\left\\{-\Omega\left(|k-1|\over c\sqrt{r}\right)\right\\},$

where $k$ is the number of selected edges containing $v$, so as to assign
smaller weights to the vertices $v$ with bigger violation of the perfect
matching condition, up to the smallest weight of
$\psi_{v}=\exp\left\\{-\Omega(\sqrt{r}/c)\right\\}$, when all edges containing
$v$ are selected.

We note also that Theorem 1.1 allows us to select edges with a non-uniform
probability, and hence to zoom in the perfect matchings even more: if the
hypergraph $H$ is $r$-regular, that is, if each vertex is contained in exactly
$r$ edges, it makes sense to select each edge independently with probability
$1/r$, so that for each vertex $v$ the expected number of selected edges
containing $v$ is exactly 1. If $H$ is not regular, one can choose instead the
maximum entropy distribution, which also ensures that the expected number of
selected edges containing any given vertex is exactly 1, while the weights of
all perfect matchings remain equal. The maximum entropy distribution exists if
an only if there exists a positive fractional perfect matching, that is, an
assignment of positive real weights to the edges of $H$ such that for every
vertex of $H$ the sum of weights of the edges containing it is exactly 1, see
[Ba23] for details.

### (1.6) Numerical integration in higher dimensions

Computationally efficient numerical integration of multivariate functions is
an old problem that is often associated with “the curse of dimensionality”.
The most spectacular success is achieved for integration of log-concave
functions on ${\mathbb{R}}^{n}$ via the Monte Carlo Markov Chain method, see
[LV07] for a survey. Deterministic methods enjoyed much less success. In
[GS24], the authors, using the deterministic decay of correlations approach,
considered integration of functions over the unit cube $[0,1]^{n}$. The model
of [GS24] fits the setup of our Theorem 1.1, if we choose
$X_{1}=\ldots=X_{n}=[0,1]$ endowed with the Lebesgue probability measure. The
results of [GS24] appear to be weaker than our Theorem 1.1, in the dependence
on both parameters $r$ and $c$, as well as in the class of allowed functions
$\phi_{i}$.

Theorem 1.2 allows us to integrate efficiently some functions that are
decidedly not log-concave (or log-convex), for example if we choose
$\phi_{i}(x)=\bigl{|}|x_{i}|-1\bigr{|}$ for some $i$, thus reaching beyond the
realm of functions efficiently integrated by randomized methods.

### (1.7) Other applications

Zero-free regions of partition functions of the type covered by Theorem 1.1
turn out to be relevant to the decay of correlations [Ga23], [Re23], to the
mixing time of Markov Chains [Ch+22], to the validity of the Central Limit
Theorem for combinatorial structures [MS19], as well as to other related
algorithmic applications [J+22].

## 2\. Proof of Theorem 1.1

We start with a lemma.

###### (2.1) Lemma

Let $X$ be a probability space and let $f:X\longrightarrow{\mathbb{C}}$ be an
integrable function. Suppose that $f(x)\neq 0$ for all $x\in X$ and, moreover,
for any two points $x,y\in X$, the angle between $f(x)$ and $f(y)$, considered
as non-zero vectors in ${\mathbb{R}}^{2}={\mathbb{C}}$ does not exceed
$\theta$ for some $0\leq\theta<2\pi/3$. Then

$\left|\mathbb{E}\thinspace f\right|\ \geq\ \left(\cos{\theta\over
2}\right)\mathbb{E}\thinspace|f|.$

###### Demonstration Proof

This is Lemma 3.3 from [BR19], see also Lemma 3.6.3 of [Ba16]. The idea of the
proof is to compare both sides of the inequality to the expected length of the
orthogonal projection of $f(x)$ onto the bisector of the angle enclosing the
range of $f$. ∎

We will need some technical inequalities.

###### (2.2) Lemma

The following inequalities hold

###### Demonstration Proof

The inequality of Part (1) is proved, for example, in [Ba23], see Lemma 6.1
there. To prove the inequality of Part (2), let

$f(\alpha)=\sin(\tau\alpha)\quad\text{and}\quad g(\alpha)=\tau\sin\alpha.$

Then $f(0)=g(0)=0$ and

$f^{\prime}(\alpha)=\tau\cos(\tau\alpha)\ \geq\
\tau\cos\alpha=g^{\prime}(\alpha),$

from which the proof follows. To prove the inequality of Part (3), we note
that

$\left|e^{z}-1\right|=\left|\sum_{k=1}^{\infty}{z^{k}\over k!}\right|\ \leq\
\sum_{k=1}^{\infty}{|z|^{k}\over k!},$

and hence it suffices to check the inequality assuming that $z$ is non-
negative real. Since the function

${e^{z}-1\over z}=\sum_{k=0}^{\infty}{z^{k}\over(k+1)!}$

is increasing for $z\geq 0$, it suffices to check the inequality at $z=1$,
where it states that $|e-1|\leq 2$. ∎

Let $X_{1},\ldots,X_{n}$ be probability spaces and let
$f:X_{1}\times\ldots\times X_{n}\longrightarrow{\mathbb{C}}$ be an integrable
function. For a subset $S\subset\\{1,\ldots,n\\}$, by $\mathbb{E}_{S}f$ we
denote the conditional expectation obtained by integrating $f$ over the
coordinates $x_{j}\in X_{j}$ with $j\in S$. Thus $\mathbb{E}_{S}f$ is a
function of the coordinates $x_{j}$ with $j\notin S$. In particular, for
$S=\emptyset$, we have $\mathbb{E}_{S}f=f$ and for $S=\\{1,\ldots,n\\}$, we
have $\mathbb{E}_{S}=\mathbb{E}\thinspace f$.

Now we are ready to prove Theorem 1.1.

### (2.3) Proof of Theorem 1.1

Let

$\theta={\pi\over 2\sqrt{r-1}}.$ $None$

For a subset $S\subset\\{1,\ldots,n\\}$, we prove by induction on $|S|$ the
following

(2.3.2) Statement: Let functions $\phi_{i}$, $f$ and a complex number
$\lambda$ be as in Theorem 1.1. For every $S\subset\\{1,\ldots,n\\}$, we have
$\mathbb{E}_{S}\thinspace e^{\lambda f}\neq 0$, by which we mean that
$\mathbb{E}_{S}e^{\lambda f}\neq 0$ for any choice of the coordinates
$x_{j}\in X_{j}$ with $j\notin S$. Moreover, for every $j\notin S$, the value
of $\mathbb{E}_{S}\thinspace e^{\lambda f}\neq 0$, considered as a vector in
${\mathbb{R}}^{2}={\mathbb{C}}$, rotates by not more than an angle of $\theta$
when only the $x_{j}$ coordinate of $x=\left(x_{1},\ldots,x_{n}\right)$
changes, while all other coordinates stay the same.

Once we have (2.3.2) for $S=\\{1,\ldots,n\\}$, we conclude that
$\mathbb{E}\thinspace e^{\lambda f}\neq 0$, which is what we want to prove.

Suppose that $|S|=0$, so that $S=\emptyset$ and

$\mathbb{E}_{S}\thinspace e^{\lambda f}=e^{\lambda
f}=\exp\left\\{\lambda\sum_{i=1}^{m}\phi_{i}\right\\}.$

Let $x^{\prime},x^{\prime\prime}\in X$ be two points that differ only in the
$x_{j}$ coordinate. Since at most $c$ of the functions $\phi_{i}$ depend on
the coordinate $x_{j}$ and each function $\phi_{i}$ is 1-Lipschitz, we have

$|\lambda f(x^{\prime})-\lambda
f(x^{\prime\prime})|=|\lambda||f(x^{\prime})-f(x^{\prime\prime})|\ \leq\
|\lambda|c\ \leq\ {1\over 3\sqrt{r-1}}\ <\ \theta,$

which establishes the base of the induction.

Suppose now that Statement 2.3.2 holds for every $S$ with $|S|\leq k$, where
$0\leq k<n$. Let us choose an arbitrary $S\subset\\{1,\ldots,n\\}$ such that
$|S|=k+1$ and an index $j\in S$. Applying Lemma 2.1 and the induction
hypothesis, we conclude that

$\left|\mathbb{E}_{S}\thinspace e^{\lambda
f}\right|=\left|\mathbb{E}_{\\{j\\}}\mathbb{E}_{S\setminus\\{j\\}}e^{\lambda
f}\right|\ \geq\ \left(\cos{\theta\over
2}\right)\mathbb{E}_{\\{j\\}}\left|\mathbb{E}_{S\setminus\\{j\\}}e^{\lambda
f}\right|.$ $None$

It follows that

$\mathbb{E}_{S}\thinspace e^{\lambda f}\neq 0.$

Assuming that $k+1<n$, let us pick some index not in $S$, without loss of
generality index $n$. We need to prove that as the coordinate $x_{n}$ changes
from some value $x_{n}^{\prime}$ to some value $x_{n}^{\prime\prime}$, while
other coordinates remain the same, the value of $\mathbb{E}_{S}\thinspace
e^{\lambda f}$ rotates through an angle of at most $\theta$. Let

$I=\left\\{i:\ \phi_{i}\quad\text{depends on}\quad
x_{n}\right\\},\quad\text{so}\quad|I|\leq c.$

Without loss of generality, $I\neq\emptyset$. For each $i\in I$, we define two
functions $\phi_{i}^{\prime}$ and $\phi_{i}^{\prime\prime}$, obtained from
$\phi_{i}$ by fixing the coordinate $x_{n}$ to $x_{n}^{\prime}$ and
$x_{n}^{\prime\prime}$ respectively. Although $\phi_{i}^{\prime}$ and
$\phi_{i}^{\prime\prime}$ are functions of the first $n-1$ coordinates
$x_{1},\ldots,x_{n-1}$ of $x\in X$, we formally consider them as functions on
$X$, by ignoring the last coordinate $x_{n}$.

Since each function $\phi_{i}$ is 1-Lipschitz in the Hamming metric, we have

$\left|\phi_{i}^{\prime}(x)-\phi_{i}^{\prime\prime}(x)\right|\ \leq\
1\quad\text{for all}\quad x\in X\quad\text{and}\quad i\in I.$ $None$

Thus the value of $\mathbb{E}_{S}\thinspace e^{\lambda f}$, where we fix
$x_{n}=x_{n}^{\prime}$, is

$\mathbb{E}_{S}\exp\left\\{\lambda\sum_{i\in
I}\phi_{i}^{\prime}+\lambda\sum_{i\notin I}\phi_{i}\right\\},$ $None$

while the value of $\mathbb{E}_{S}e^{\lambda f}$, where we fix
$x_{n}=x_{n}^{\prime\prime}$, is

$\mathbb{E}_{S}\exp\left\\{\lambda\sum_{i\in
I}\phi_{i}^{\prime\prime}+\lambda\sum_{i\notin I}\phi_{i}\right\\}.$ $None$

We pass from (2.3.5) to (2.3.6) step by step, replacing one
$\phi_{i}^{\prime}$ by $\phi_{i}^{\prime\prime}$ at each step. Our goal is to
prove that at each step, the expectation rotates by at most $\theta/c$. Once
we prove that, it would follow that the expectation $\mathbb{E}_{S}\thinspace
e^{\lambda f}$ rotates by at most $\theta$, when we replace the value of
$x_{n}=x_{n}^{\prime}$ by $x_{n}=x_{n}^{\prime\prime}$.

Let us pick an index in $I$, without loss of generality index $m$. We define

$f^{\prime}=\phi_{m}^{\prime}+\psi\quad\text{and}\quad
f^{\prime\prime}=\phi_{m}^{\prime\prime}+\psi,$ $None$

where $\psi$ is the sum of some functions $\phi_{i}^{\prime}$,
$\phi_{i}^{\prime\prime}$ and $\phi_{i}$, where for each $i\neq m$ we select
exactly one of the three functions $\phi_{i}^{\prime}$,
$\phi_{i}^{\prime\prime}$ or $\phi_{i}$ into the sum for $\psi$. Hence our
goal is to show that the angle between $\mathbb{E}_{S}\thinspace e^{\lambda
f^{\prime}}$ and $\mathbb{E}_{S}\thinspace e^{\lambda f^{\prime\prime}}$ does
not exceed $\theta/c$.

Since each of the functions $\phi_{i}^{\prime}$ and $\phi_{i}^{\prime\prime}$
is obtained from $\phi_{i}$ by specifying some value of $x_{n}$, we can apply
the induction hypothesis both to $f^{\prime}$ and to $f^{\prime\prime}$. Let
$S_{0}\subset S$ be the set of indices $j\in S$ such that $\phi_{m}^{\prime}$
and $\phi_{m}^{\prime\prime}$ depend on $x_{j}$. In particular, $|S_{0}|\leq
r-1$.

If $S_{0}=\emptyset$, then

$\mathbb{E}_{S}\thinspace e^{\lambda
f^{\prime}}=e^{\lambda\phi_{m}^{\prime}}\mathbb{E}_{S}\thinspace
e^{\lambda\psi}\quad\text{and}\quad\mathbb{E}_{S}\thinspace e^{\lambda
f^{\prime\prime}}=e^{\lambda\phi_{m}^{\prime\prime}}\mathbb{E}_{S}\thinspace
e^{\lambda\psi}.$

Using (2.3.4), we conclude the angle between $\mathbb{E}_{S}\thinspace
e^{\lambda f^{\prime}}\neq 0$ and $\mathbb{E}_{S}\thinspace e^{\lambda
f^{\prime\prime}}\neq 0$ does not exceed

$|\lambda\phi_{m}^{\prime\prime}(x)-\lambda\phi_{m}^{\prime}(x)|\ \leq\
|\lambda|\ \leq\ {1\over 3c\sqrt{r-1}}\ <\ {\theta\over c}.$

Suppose now that $S_{0}\neq\emptyset$. Since $\phi_{m}^{\prime}$ and
$\phi_{m}^{\prime\prime}$ do not depend on the coordinates $x_{j}$ with
$j\notin S_{0}$, from (2.3.7) we have

$\begin{split}\mathbb{E}_{S}\thinspace e^{\lambda
f^{\prime\prime}}=&\mathbb{E}_{S}\left(e^{\lambda\phi_{m}^{\prime\prime}}e^{\lambda\psi}\right)=\mathbb{E}_{S}\left(e^{\lambda\phi_{m}^{\prime\prime}-\lambda\phi_{m}^{\prime}}e^{\lambda\phi_{m}^{\prime}+\lambda\psi}\right)=\mathbb{E}\left(e^{\lambda\phi_{m}^{\prime\prime}-\lambda\phi_{m}^{\prime}}e^{\lambda
f^{\prime}}\right)\\\
=&\mathbb{E}_{S_{0}}\left(\left(e^{\lambda\phi_{m}^{\prime\prime}-\lambda\phi_{m}^{\prime}}\right)\mathbb{E}_{S\setminus
S_{0}}e^{\lambda f^{\prime}}\right)\end{split}$

and hence

$\begin{split}\mathbb{E}_{S}\thinspace e^{\lambda
f^{\prime\prime}}-\mathbb{E}_{S}\thinspace e^{\lambda
f^{\prime}}=&\mathbb{E}_{S_{0}}\left(\left(e^{\lambda\phi_{m}^{\prime\prime}-\lambda\phi_{m}^{\prime}}\right)\mathbb{E}_{S\setminus
S_{0}}e^{\lambda
f^{\prime}}\right)-\mathbb{E}_{S_{0}}\left(\mathbb{E}_{S\setminus
S_{0}}e^{\lambda f^{\prime}}\right)\\\
=&\mathbb{E}_{S_{0}}\left(\left(e^{\lambda\phi_{m}^{\prime\prime}-\lambda\phi_{m}^{\prime}}-1\right)\mathbb{E}_{S\setminus
S_{0}}\thinspace e^{\lambda f^{\prime}}\right).\end{split}$

By (2.3.4) and by Part (3) of Lemma 2.2, we have

$\left|e^{\lambda\phi_{m}^{\prime\prime}-\lambda\phi_{m}^{\prime}}-1\right|\
\leq\ 2|\lambda|.$

Therefore,

$\left|\mathbb{E}_{S}\thinspace e^{\lambda
f^{\prime\prime}}-\mathbb{E}_{S}\thinspace e^{\lambda f^{\prime}}\right|\
\leq\ 2|\lambda|\mathbb{E}_{S_{0}}\left|\mathbb{E}_{S\setminus
S_{0}}\thinspace e^{\lambda f^{\prime}}\right|.$ $None$

Iterating (2.3.3) with $f$ replaced by $f^{\prime}$, we obtain that

$\displaystyle\left|\mathbb{E}_{S}e^{\lambda f^{\prime}}\right|=$
$\displaystyle\left|\mathbb{E}_{S_{0}}\mathbb{E}_{S\setminus S_{0}}\thinspace
e^{\lambda f^{\prime}}\right|\ \geq\ \left(\cos{\theta\over
2}\right)^{|S_{0}|}\mathbb{E}_{S_{0}}\left|\mathbb{E}_{S\setminus
S_{0}}e^{\lambda f^{\prime}}\right|$ $None$ $\displaystyle\geq\
\left(\cos{\theta\over
2}\right)^{r-1}\mathbb{E}_{S_{0}}\left|\mathbb{E}_{S\setminus S_{0}}e^{\lambda
f^{\prime}}\right|.$

Combining (2.3.8) and (2.3.9), we conclude that

${\left|\mathbb{E}_{S}\thinspace e^{\lambda
f^{\prime\prime}}-\mathbb{E}_{S}\thinspace e^{\lambda
f^{\prime}}\right|\over\left|\mathbb{E}_{S}\thinspace e^{\lambda
f^{\prime}}\right|}\ \leq\ {2|\lambda|\over\cos^{r-1}\left(\theta/2\right)}.$

Recalling the bound for $|\lambda|$, formula (2.3.1) for $\theta$ and using
Part (1) of Lemma 2.2, we obtain

$\displaystyle{\left|\mathbb{E}_{S}\thinspace e^{\lambda
f^{\prime\prime}}-\mathbb{E}_{S}\thinspace e^{\lambda
f^{\prime}}\right|\over\left|\mathbb{E}_{S}\thinspace e^{\lambda
f^{\prime}}\right|}\ \leq$ $\displaystyle{2\over
3c\sqrt{r-1}}\left(\cos{\pi\over 4\sqrt{r-1}}\right)^{-(r-1)}$
$\displaystyle\leq$ $\displaystyle{2\over
3c\sqrt{r-1}}{1\over\cos(\pi/4)}={2\sqrt{2}\over 3c\sqrt{(r-1)}}.$

It follows now that the angle, call it $\alpha$, between
$\mathbb{E}_{S}\thinspace e^{\lambda f^{\prime}}$ and
$\mathbb{E}_{S}\thinspace e^{\lambda f^{\prime\prime}}$ is acute and that

$\sin\alpha\ \leq\ {2\sqrt{2}\over 3c\sqrt{(r-1)}}.$

From (2.3.1) and Part (2) of Lemma 2.2, we have

$\sin{\theta\over c}\ =\ \sin{\pi\over 2c\sqrt{r-1}}\ \geq\ {1\over
c\sqrt{r-1}}\sin{\pi\over 2}={1\over c\sqrt{r-1}}\ \geq\ \sin\alpha.$

Hence the angle between $\mathbb{E}_{S}\thinspace e^{\lambda f^{\prime}}$ and
$\mathbb{E}_{S}\thinspace e^{\lambda f^{\prime\prime}}$ indeed does not exceed
$\theta/c$ and $\mathbb{E}_{S}\thinspace e^{\lambda f}$ rotates by not more
than an angle of $\theta$ when the value of one of the coordinates $x_{j}$
with $j\notin S$ changes, while the others remain the same. This completes the
induction step in proving Statement 2.3.2.

It remains to prove (1.1.2) assuming (1.1.1). Clearly, we have

$|f(x)|\ \leq\ mL\quad\text{for all}\quad x\in X$

and the upper bound in (1.1.2) follows. To prove the lower bound, iterating
(2.3.3), we get

$\left|\mathbb{E}\thinspace e^{\lambda f}\right|\ \geq\ \left(\cos{\theta\over
2}\right)^{n}\mathbb{E}\thinspace\left|e^{\lambda f}\right|\ \geq\
e^{-|\lambda|mL}\left(\cos{\pi\over 4\sqrt{r-1}}\right)^{n},$

as required. ∎

## 3\. Proof of Theorem 1.2

We obtain Theorem 1.2 as a scaling limit of Theorem 1.1.

### (3.1) Proof of Theorem 1.2

First, we consider the case of bounded functions $\phi_{i}$, so that the
condition (1.2.1) is satisfied.

We are going to use Theorem 1.1. For an integer $N\geq 1$, we consider $nN$
probability spaces $X_{1}=\ldots=X_{nN}=\\{-1,1\\}$ and their direct product
$X=\\{-1,1\\}^{nN}$, all endowed with the uniform probability measure. We
write a point $x\in X$ as $x=\left(x_{jk}\right)$, where $j=1,\ldots,n$ and
$k=1,\ldots,N$. For $i=1,\ldots,m$, we define functions
$\psi_{i}:\\{-1,1\\}^{nN}\longrightarrow{\mathbb{C}}$ by

$\psi_{i}(x)={\sqrt{N}\over
2}\phi_{i}\left({x_{11}+\ldots+x_{1N}\over\sqrt{N}},\ldots,{x_{j1}+\ldots+x_{jN}\over\sqrt{N}},\ldots,{x_{n1}+\ldots+x_{nN}\over\sqrt{N}}\right)$

and

$g_{N}=\sum_{i=1}^{m}\psi_{i}.$

Since the functions $\phi_{i}$ are 1-Lipschitz in the $\ell^{1}$ metric of
${\mathbb{R}}^{n}$, the functions $\psi_{i}$ are 1-Lipschitz in the Hamming
metric of $X$. Moreover, each function $\psi_{i}$ depends on not more than
$r_{N}=rN$ coordinates and at most $c$ functions $\psi_{i}$ depend on any
particular coordinate $x_{jk}$. Finally, from (1.2.1), we conclude that

$\left|\psi_{i}(x)\right|\ \leq\ {\sqrt{N}\over 2}L\quad\text{for}\quad
i=1,\ldots,m.$

Therefore, from formula (1.1.2) of Theorem 1.1, we conclude that

$\left|\mathbb{E}\thinspace e^{\lambda_{N}g_{N}}\right|\ \geq\
\exp\left\\{-{1\over 2}|\lambda_{N}|m\sqrt{N}L\right\\}\left(\cos{\pi\over
4\sqrt{rN-1}}\right)^{nN}.$

provided

$|\lambda_{N}|\ \leq\ {1\over 3c\sqrt{rN}}.$

Therefore,

$\left|\mathbb{E}\thinspace\exp\left\\{\lambda{2\over\sqrt{N}}g_{N}\right\\}\right|\
\geq\ \exp\left\\{-|\lambda|mL\right\\}\left(\cos{\pi\over
4\sqrt{rN-1}}\right)^{nN}$ $None$

provided

$|\lambda|\ \leq\ {1\over 6c\sqrt{r}}.$

By the Central Limit Theorem, as $N\longrightarrow\infty$, the random vector

$\left({x_{11}+\ldots+x_{1N}\over\sqrt{N}},\ldots,{x_{j1}+\ldots+x_{jN}\over\sqrt{N}},\ldots,{x_{n1}+\ldots+x_{nN}\over\sqrt{N}}\right)$

converges in distribution to the standard Gaussian measure in
${\mathbb{R}}^{n}$. Since the functions $\phi_{i}$ are continuous and bounded,
we have

$\lim_{N\longrightarrow\infty}\mathbb{E}\thinspace\exp\left\\{\lambda{2\over\sqrt{N}}g_{N}\right\\}=\mathbb{E}\thinspace
e^{\lambda f},$

where the expectation in the right hand side is taken with respect to the
standard Gaussian measure in ${\mathbb{R}}^{n}$, see, for example, Section 7.2
of [GS20]. Since

$\lim_{N\longrightarrow\infty}\left(\cos{\pi\over
4\sqrt{rN-1}}\right)^{nN}=\lim_{N\longrightarrow\infty}\left(1-{\pi^{2}\over
32(rN-1)}\right)^{nN}=\exp\left\\{-{\pi^{2}n\over 32r}\right\\},$

from (3.1.1) we obtain the lower bound in the inequality (1.2.2). The upper
bound in (1.2.2) is trivial.

It remains to consider the general case of not necessarily bounded functions
$\phi_{i}$. Shifting, if necessary,

$\phi_{i}:=\phi_{i}-\phi_{i}(0)\quad\text{for}\quad i=1,\ldots,m,$

without loss of generality we assume that

$\phi_{i}(0)=0\quad\text{for}\quad i=1,\ldots,m.$

Then

$\left|\phi_{i}\left(x_{1},\ldots,x_{n}\right)\right|\ \leq\
\sum_{j=1}^{n}|x_{j}|\quad\text{for}\quad i=1,\ldots,m.$ $None$

For $L>0$, we define the truncation of $\phi_{i}$ by

$\phi_{i,L}(x)=\begin{cases}\phi_{i}(x)&\text{if}\quad|\phi_{i}(x)|\leq L\\\
L\phi_{i}(x)/|\phi_{i}(x)|&\text{if}\quad|\phi(x)|>L.\end{cases}$

Then

$\left|\phi_{i,L}(x)-\phi_{i,L}(y)\right|\ \leq\
\left|\phi_{i}(x)-\phi_{i}(y)\right|,$

so $\phi_{i,L}$ satisfy the conditions of Theorem 1.2, and are bounded. Hence
for

$f_{L}=\sum_{i=1}^{m}\phi_{L}$

we have

$\mathbb{E}\thinspace e^{\lambda f_{L}}\neq
0\quad\text{provided}\quad|\lambda|\ \leq\ {1\over 6c\sqrt{r-1}}.$

From (3.1.2) it follows that

$\lim_{L\longrightarrow+\infty}\mathbb{E}\thinspace e^{\lambda
f_{L}}=\mathbb{E}\thinspace e^{\lambda f}$

and that the convergence is uniform on any compact set of $\lambda$ in
${\mathbb{C}}$. Then by the Hurwitz Theorem, see, for example, Section 1 of
[Kr01], we have two options: either $\mathbb{E}\thinspace e^{\lambda f}=0$ for
all $\lambda\in{\mathbb{C}}$ or $\mathbb{E}\thinspace e^{\lambda f}\neq 0$ for
all $\lambda$ in the open disc $|\lambda|<1/6c\sqrt{r-1}$. Since for
$\lambda=0$ we clearly have $\mathbb{E}\thinspace e^{\lambda f}=1$, the first
option is not realized. ∎

## 4\. Optimality

Our goal is to show that the bound

$|\lambda|\ \leq\ {1\over 3c\sqrt{r-1}}$

in Theorem 1.1 is optimal, up to a constant factor, replacing $1/3$. We do it
in two steps. First, we show that for $c=1$ the dependence on $r$ is optimal,
up to a constant factor, and then that the dependence on both $c$ and $r$ is
optimal.

### (4.1) Dependence on $r$

Let $X_{1}=\ldots=X_{n}=\\{-1,1\\}$ and let $X=\\{-1,1\\}^{n}$, all endowed
with the uniform probability measure. We intend to show that for all
sufficiently large $n$ there is a function $\phi:X\longrightarrow{\mathbb{C}}$
which is 1-Lipschitz in the Hamming metric of $X$ and such that
$\mathbb{E}\thinspace e^{\lambda\phi}=0$ for some $\lambda$ satisfying

$|\lambda|\ \leq\ {\gamma\over\sqrt{n}},$

where $\gamma>0$ is an absolute constant.

We reverse engineer an example from our proof of Theorem 1.2 in Section 3.

The functions

$z\longmapsto\int_{0}^{+\infty}e^{zx}e^{-x^{2}/2}\ dx\quad\text{and}\quad
z\longmapsto\int_{-\infty}^{0}e^{zx}e^{-x^{2}/2}\ dx,$

where we integrate over a real variable $x$, are non-constant entire functions
of $z\in{\mathbb{C}}$ and hence the range of each, by the Picard Theorem, is
the whole plane ${\mathbb{C}}$, except perhaps one point. Therefore, there are
two points $u,v\in{\mathbb{C}}$ such that

$\int_{-\infty}^{0}e^{ux}e^{-x^{2}/2}\
dx+\int_{0}^{+\infty}e^{vx}e^{-x^{2}/2}\ dx=0.$

Let us define $\psi:{\mathbb{R}}\longrightarrow{\mathbb{C}}$

$\psi(x)=\begin{cases}vx&\text{if\ }x\geq 0\\\ ux&\text{if \ }x<0.\end{cases}$

Then

$\int_{-\infty}^{+\infty}e^{\psi(x)}e^{-x^{2}/2}\ dx=0.$ $None$

It is easy to check that $\psi$ is Lipschitz, more precisely,

$|\psi(x)-\psi(y)|\ \leq\
\tau|x-y|\quad\text{where}\quad\tau=\max\left\\{|u|,|v|\right\\}.$

For an $L>0$, we consider the truncation

$\psi_{L}(x)=\begin{cases}\psi(x)&\text{if}\quad|\psi(x)|\leq L\\\
L\psi(x)/|\psi(x)|&\text{if}\quad|\psi(x)|>L.\end{cases}$

Then

$\left|\psi_{L}(x)-\psi_{L}(y)\right|\ \leq\ |\psi(x)-\psi(y)|\ \leq\
\tau|x-y|,$ $None$

so $\psi_{L}$ is also Lipschitz and, in addition, bounded.

Let us fix some $\rho>1$. We have

$\lim_{L\longrightarrow\infty}\int_{-\infty}^{+\infty}e^{z\psi_{L}(x)}e^{-x^{2}/2}\
dx=\int_{-\infty}^{+\infty}e^{z\psi(x)}e^{-x^{2}/2}\ dx$ $None$

and from (4.1.2) it follows that the convergence is uniform in $z$ on all
compact sets in ${\mathbb{C}}$. Since the right hand side of (4.1.3) for $z=0$
is equal to 1, while for $z=1$ is equal to 0 by (4.1.1), by the Hurwitz
Theorem, see, for example, Section 1 of [Kr01], we conclude that for all
sufficiently large $L$ we must have

$\int_{-\infty}^{+\infty}e^{z\psi_{L}(x)}e^{-x^{2}/2}\ dx=0\quad\text{for
some}\quad z\quad\text{with}\quad|z|<\rho.$ $None$

Let us pick some $L$ such that (4.1.4) holds. For an integer $n$, we consider
$n$ probability spaces $X_{1}=\ldots=X_{n}=\\{-1,1\\}^{n}$ and their product
$X=\\{-1,1\\}^{n}$, all endowed with the uniform probability measure. We
define $\phi:X\longrightarrow{\mathbb{C}}$ by

$\phi(x)={\sqrt{n}\over
2\tau}\psi_{L}\left({1\over\sqrt{n}}\sum_{i=1}^{n}x_{i}\right)\quad\text{where}\quad
x=\left(x_{1},\ldots,x_{n}\right).$ $None$

It follows from (4.1.2) that $\phi$ is 1-Lipschitz in the Hamming metric of
$\\{-1,1\\}^{n}$. Hence $\phi$ satisfies the conditions of Theorem 1.1 with
$c=1$ and $r=n$.

Since by the CentraL Limit Theorem the normalized sum

${1\over\sqrt{n}}\sum_{i=1}^{n}x_{i}$

converges in distribution to the standard Gaussian measure as $n$ grows, and
the function $\psi_{L}$ is continuous and bounded, we have

$\mathbb{E}\thinspace\exp\left\\{z\psi_{L}\left({1\over\sqrt{n}}\sum_{i=1}^{n}x_{i}\right)\right\\}\longrightarrow{1\over\sqrt{2\pi}}\int_{-\infty}^{+\infty}e^{z\psi_{L}(x)}e^{-x^{2}/2}\
dx$ $None$

and that the convergence in (4.1.6) is uniform in $z$ on all compact subsets
of ${\mathbb{C}}$, see, for example, Section 7.2 of [GS20]. The right hand
side of (4.1.6) is equal to 1 for $z=0$. Then by (4.1.4) and the Hurwitz
Theorem, for all sufficiently large $n$ we must have

$\mathbb{E}\thinspace\exp\left\\{z\psi_{L}\left({1\over\sqrt{n}}\sum_{i=1}^{n}x_{i}\right)\right\\}=0\quad\text{for
some}\quad z\quad\text{with}\quad|z|<\rho.$

Therefore, from (4.1.5) we conclude that for all sufficiently large $n$, there
is $\lambda$ satisfying

$|\lambda|<{2\tau\rho\over\sqrt{n}}\quad\text{and}\quad\mathbb{E}\thinspace
e^{\lambda\phi}=0,$

which proves that the bound in Theorem 1.1 is indeed optimal in terms of $r$,
up to an absolute constant factor.

### (4.2) Dependence on $r$ and $c$

To prove that the dependence on both $r$ and $c$ is optimal, for an integer
$k\geq 1$, we introduce

$f_{k}(x)=\underbrace{\phi(x)+\ldots+\phi(x)}_{\text{$k$ times}},$ $None$

where $\phi$ is defined by (4.1.5). While the parameter $r$ remains the same
for all $f_{k}$ defined by (4.2.1), the parameter $c$ changes, $c=k$.
Furthermore,

$\mathbb{E}\thinspace e^{\lambda f_{k}}=\mathbb{E}\thinspace e^{(k\lambda)f},$

and hence the zero-free region for $\lambda$ scales

$|\lambda|=O\left({1\over k\sqrt{r}}\right)=O\left({1\over c\sqrt{r}}\right).$

### (4.3) Question: computational complexity

It would be interesting to find out whether the dependence on $r$ is optimal
from the computational complexity point of view, that is, whether for real-
valued $f$ and $\lambda\gg 1/c\sqrt{r}$, the approximation of
$\mathbb{E}\thinspace e^{\lambda f}$ becomes computationally difficult,
possibly conditioned on P $\neq$ NP or other commonly believed hypothesis. The
argument with the “cloning” of $f$ as in (4.2.1) shows that the dependence on
$c$ is indeed optimal.

## 5\. Approximations

### (5.1) The goal

Here we sketch how Theorems 1.1, respectively Theorem 1.2, allow us to
approximate $\mathbb{E}\thinspace e^{\lambda f}$ provided

$|\lambda|\ \leq\ {1-\delta\over
3c\sqrt{r-1}},\quad\text{respectively,}\quad|\lambda|\ \leq\ {1-\delta\over
6c\sqrt{r-1}}$ $None$

for some $0<\delta<1$, fixed in advance. The approach was used many times
before, in particular in [Ba17] in the context closest to ours.

The algorithm is based on the following result.

###### (5.2) Lemma

Let $p(z)$ be a univariate polynomial of degree $N$ in a complex variable $z$.
Suppose that for some $\beta>1$, we have $p(z)\neq 0$ for all $z$ satisfying
$|z|<\beta$ and let us choose a branch of $g(z)=\ln p(z)$ in the disc
$|z|<\beta$. For an integer $k\geq 1$, let $T_{k}(z)$ be the Taylor polynomial
of $g(z)$ degree $k$ computed at $z=0$, that is,

$T_{k}(z)=g(0)+\sum_{s=1}^{k}{g^{(s)}(0)\over s!}z^{s}.$

Then

$\left|g(z)-T_{k}(z)\right|\ \leq\
{N\over(k+1)(\beta-1)\beta^{k}}\quad\text{for all}\quad|z|\leq 1.$

###### Demonstration Proof

This is Lemma 2.2.1 from [Ba16]. ∎

As follows from Lemma 5.2, to approximate $g(1)$ by $T_{k}(1)$ within an
additive error $0<\epsilon<1$ and hence to approximate $p(1)$ by
$\exp\\{T_{k}(1)\\}$ within a relative error $0<\epsilon<1$, it suffices to
choose $k=O_{\beta}\left(\ln N-\ln\epsilon\right)$. Moreover, the derivatives
$g^{(s)}(0)$ can be computed from $p(0)$ and the derivatives $p^{(s)}(0)$ for
$s=1,\ldots,k$ in $O(k^{2})$ time, see Section 2.2.2 of [Ba16].

### (5.3) Bounds

In the context of Theorem 1.1, let us pick an arbitrary $x_{0}\in X$ and let
$\gamma=f(x_{0})$. In the context of Theorem 1.2, let $\gamma=f(0)$. Since

$\mathbb{E}\thinspace
e^{\lambda(f-\gamma)}=e^{-\lambda\gamma}\mathbb{E}\thinspace e^{\lambda f},$

without loss of generality, we assume that $f(x_{0})=0$ (Theorem 1.1) or
$f(0)=0$ (Theorem 1.2).

Then in the context of Theorem 1.1, respectively Theorem 1.2, we have

$\displaystyle|f(x)|\ \leq\ nm\quad\text{for all}\quad x\in
X,\quad\text{respectively,}$ $None$ $\displaystyle|f(x_{1},\ldots,x_{n})|\
\leq\ m\sum_{j=1}^{n}|x_{j}|\quad\text{for
all}\quad(x_{1},\ldots,x_{n})\in{\mathbb{R}}^{n}.$

Given a complex $\lambda$ satisfying (5.1.1), we consider a function

$z\longmapsto\mathbb{E}\thinspace e^{\lambda
zf}=\mathbb{E}\thinspace\exp\left\\{\lambda z\sum_{i=1}^{m}\phi_{i}\right\\}.$
$None$

While (5.3.2) is not a polynomial, we can approximate it close enough by its
Taylor polynomial $p_{N}(z)$ and then use Lemma 5.2 to approximate $\ln
p_{N}(z)$ by a polynomial of a low degree. To accomplish the first step, one
can use, for example, the following standard estimate.

###### (5.4) Lemma

Let $\rho>0$ be a real number and let $N\geq 5\rho$ be an integer. Then

$\left|e^{z}-\sum_{k=0}^{N}{z^{k}\over k!}\right|\ \leq\ e^{-2\rho}$

for all $z\in{\mathbb{C}}$ such that $|z|\leq\rho$.

###### Demonstration Proof

This is Lemma 3.2 in [Ba17]. The proof is a standard estimate of the
truncation error. ∎

Using (5.3.1), Lemma 5.4 and the bounds (1.1.2) and (1.2.2), for a given
$0<\epsilon<1$, one can compute

$N=\left((m+n)\ln{1\over\epsilon}\right)^{O(1)},$

such that the Taylor polynomial of (5.3.2),

$p_{N}(z)=\sum_{s=0}^{N}{\lambda^{s}z^{s}\over
s!}\mathbb{E}f^{s}=\sum_{s=0}^{N}{\lambda^{s}z^{s}\over
s!}\left(\sum_{i=1}^{m}\phi_{i}\right)^{s}$

satisfies

$p_{N}(z)\neq 0\quad\text{provided}\quad|z|\ \leq\ {1\over 1-\delta}$

and $p_{N}(1)$ approximates $\mathbb{E}\thinspace e^{\lambda f}$ within a
relative error of $\epsilon/3$ (in the context of Theorem 1.2, we replace
$\phi_{i}$ by their appropriate truncations).

Using Lemma 5.2 with $\beta=(1-\delta)^{-1}$, we further approximate
$p_{N}(1)$ within a relative error of $\epsilon/3$ using only
$k=O_{\delta}\left(\ln(m+n)-\ln\epsilon)\right)$ first derivatives,

$p_{N}^{(s)}(0)=\lambda^{s}\mathbb{E}\left(\sum_{i=1}^{m}\phi_{i}\right)^{s}\quad\text{for}\quad
s=1,\ldots,k,$

which in turn reduces to computing
$m^{O_{\delta}\left(\ln(m+n)-\ln\epsilon\right)}$ different expectations

$\mathbb{E}\left(\phi_{i_{1}}\cdots\phi_{i_{k}}\right),$

see, for example, [Ba17] for a similar computation.

This results in a quasi-polynomial algorithm for approximating
$\mathbb{E}\thinspace e^{\lambda f}$. As we remarked, Patel and Regts [PR17],
see also [L+19], developed methods for faster computation of the relevant
derivatives of $g(z)=\ln p(z)$, which in some cases allows one to obtain a
genuinely polynomial algorithm of $\bigl{(}m+n)/\epsilon\bigr{)}^{O(1)}$
complexity, provided the parameters $r$ and $c$ are fixed in advance.

## References

  * B+22 Z. Bai, Y. Cao, and H. Wang, Zero-freeness and approximation of real Boolean Holant problems, Theoretical Computer Science 917 (2022), 12–30.
  * B+23 A. Barg, P. Boyvalenkov, and M. Stoyanova, Bounds for the sum of distances of spherical sets of small size, Discrete Mathematics 346 (2023), no. 5, Paper No. 113346, 19 pp.
  * Ba16 A. Barvinok, Combinatorics and Complexity of Partition Functions, Algorithms and Combinatorics 30, Springer, 2016.
  * Ba17 A. Barvinok, Computing the partition function of a polynomial on the Boolean cube, A Journey through Discrete Mathematics, Springer, 2017, pp. 135–164.
  * BR19 A. Barvinok and G. Regts, Weighted counting of solutions to sparse systems of equations, Combinatorics, Probability $\&$ Computing 28 (2019), no. 5, 696–719.
  * Ba23 A. Barvinok, Smoothed counting of 0-1 points in polyhedra, Random Structures $\&$ Algorithms 63 (2023), no. 1, 27–60.
  * B+21 F. Bencs, E. Davies, V. Patel, G. Regts, On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs, Annales de l’Institut Henri Poincaré D 8 (2021), no.3, 459–489.
  * Ca+22 K. Casel, P. Fischbeck, T. Friedrich, A. Göbel, and J.A. Gregor Lagodzinski, Zeros and approximations of Holant polynomials on the complex plane, Computational Complexity 31 (2022), no. 2, Paper No. 11, 52 pp.
  * Ch+22 Z. Chen, K. Liu and E. Vigoda, Spectral independence via stability and applications to Holant-type problems, 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science–FOCS 2021, IEEE Computer Society, 2022, pp. 149–160.
  * FV18 S. Friedli and Y. Velenik, Statistical Mechanics of Lattice Systems. A concrete mathematical introduction, Cambridge University Press, 2018.
  * GG16 A. Galanis and L.A. Goldberg, The complexity of approximately counting in 2-spin systems on $k$-uniform bounded-degree hypergraphs, Information and Computation 251 (2016), 36–66.
  * Ga23 D. Gamarnik, Correlation decay and the absence of zeros property of partition functions, Random Structures $\&$ Algorithms 62 (2023), no. 1, 155–180.
  * GS24 D. Gamarnik and D. Smedira, Integrating high-dimensional functions deterministically, preprint arXiv:2402.08232 (2024).
  * G+22 A. Galanis, L.A. Goldberg, A. Herrera-Poyatos, The complexity of approximating the complex-valued Ising model on bounded degree graphs, SIAM Journal on Discrete Mathematics 36 (2022), no.3, 2159–2204.
  * GS20 G.R. Grimmett and D.R. Stirzaker, Probability and Random Processes. Fourth edition, Oxford University Press, 2020.
  * G+21 H. Guo, C. Liao, P. Lu and C. Zhang, Zeros of Holant problems: locations and algorithms, ACM Transactions on Algorithms 17 (2021), no. 1, Art. 4, 25 pp.
  * HJ93 P. de la Harpe and V.F.R. Jones, Graph invariants related to statistical mechanical models: examples and problems, Journal of Combinatorial Theory. Series B 57 (1993), no. 2, 207–227.
  * J+22 V. Jain, W. Perkins, A. Sah, and M. Sawhney, Approximate counting and sampling via local central limit theorems, STOC ’22–Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, Association for Computing Machinery (ACM), 2022, pp. 1473–1486.
  * Je24 M. Jenssen, The cluster expansion in combinatorics, Surveys in Combinatorics 2024 (F. Fischer and R. Johnson, ed.), London Math. Soc. Lecture Note Ser., vol. 493, Cambridge University Press, 2024, pp. 55–88.
  * Kr04 S.G. Krantz, Complex Analysis: the Geometric Viewpoint. Second edition, Carus Mathematical Monographs, 23, Mathematical Association of America, 2004.
  * LY52 T.D. Lee and C.N. Yang, Statistical theory of equations of state and phase transitions. II. Lattice gas and Ising model, Physical Review (2) 87 (1952), 410–419.
  * L+19 J. Liu, A. Sinclair and P. Srivastava, The Ising partition function: zeros and deterministic approximation, Journal of Statistical Physics 174 (2019), no.2, 287–315.
  * LV07 L. Lovász and S. Vempala, The geometry of logconcave functions and sampling algorithms, Random Structures $\&$ Algorithms 30 (2007), no. 3, 307–358.
  * L+16 P. Lu, K. Yang and C. Zhang, FPTAS for hardcore and Ising models on hypergraphs, Art. No. 51, 14 pp., 33rd Symposium on Theoretical Aspects of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., 47, Schloss Dagstuhl. Leibniz-Zentrum für Informatik, 2016, also preprint arXiv:1509.05494.
  * Ma37 J.E. Mayer, The statistical mechanics of condensing systems. I, The Journal of Chemical Physics 5 (1) (1937), 67–73.
  * MS19 M. Michelen and J. Sahasrabudhe, Central limit theorems from the roots of probability generating functions, Advances in Mathematics 358 (2019), 106840, 27 pp.
  * PR17 V. Patel and G. Regts, Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials, SIAM Journal on Computing 46 (2017), no. 6, 1893–1919.
  * PR20 H. Peters and G. Regts, Location of zeros for the partition function of the Ising model on bounded degree graphs, Journal of the London Mathematical Society (2) 101 (2020), no.2, 765–785.
  * P+23 V. Patel, G. Regts and A. Stam, A near-optimal zero-free disk for the Ising model, preprint arXiv:2311.05574 (2023).
  * Re18 G. Regts, Zero-free regions of partition functions with applications to algorithms and graph limits, Combinatorica 38 (2018), no. 4, 987–1015.
  * Re23 G. Regts, Absence of zeros implies strong spatial mixing, Probability Theory and Related Fields 186 (2023), no. 1–2, 621–641.
  * SF71 M. Suzuki and M.E. Fisher, Zeros of the partition function for the Heisenberg, Ferroelectric, and general Ising models, Journal of Mathematical Physics 12(2) (1971), 235–246.
  * Ta11 M. Talagrand, Mean Field Models for Spin Glasses. Volume I. Basic examples, Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics, vol. 54, Springer-Verlag, 2011.
  * YL52 C.N. Yang and T.D. Lee, Statistical theory of equations of state and phase transitions. I. Theory of condensation, Physical Review (2) 87 (1952), 404–409.