Approximating the Permanent of a Random Matrix with Polynomially Small Mean: Zeros and Universality Frederic Koehler, Pui Kuen Leung Abstract We study algorithms for approximating the permanent of a random matrix when the entries are slightly biased away from zero. This question is motivated by the goal of understanding the classical complexity of linear optics and boson sampling (Aaronson and Arkhipov ’11; Eldar and Mehraban ’17). Barvinok’s interpolation method enables efficient approximation of the permanent, provided one can establish a sufficiently large zero-free region for the polynomial per ⁡ ( z ​ J + W ) \per(zJ+W) , where J J is the all-ones matrix and W W is a random matrix with independent mean-zero entries. We show that when the entries of W W are standard complex Gaussians, all zeros of the random polynomial per ⁡ ( z ​ J + W ) \per(zJ+W) lie within a disk of radius O ~ ( n − 1 / 3 ) \tilde{O}(n^{-1/3}) , which yields an approximation algorithm when the bias of the entries is Ω ~ ( n − 1 / 3 ) \tilde{\Omega}(n^{-1/3}) . Previously, there were no efficient algorithms at biases smaller than 1 / polylog ⁡ ( n ) 1/\mathrm{polylog}(n) , and it was unknown whether there typically exist zeros z z with | z | ≥ 1 |z|\geq 1 . As a complementary result, we show that the bulk of the zeros, namely ( 1 − ϵ ) ​ n (1-\epsilon)n of them, have magnitude Θ ( n − 1 / 2 ) \Theta(n^{-1/2}) . This prevents our interpolation method from contradicting the conjectured average-case hardness of approximating the permanent. We also establish analogous zero-free regions for the hardcore model on general graphs with complex vertex fugacities. In addition, we prove universality results establishing zero-free regions for random matrices W W with i.i.d. subexponential entries. 1 Introduction The permanent of a matrix A , \per(A)=\sum_{\sigma}\prod_{i}A_{i\sigma(i)}, is a central object in theoretical computer science, combinatorics, and other areas. Despite its simple definition, computing the permanent of an n\times n matrix is \#P -hard in the worst case [ 64 ] , and this hardness is widely believed to persist even for approximate computation in broad regimes. At the same time, there are also natural classes of matrices for which the permanent can be efficiently approximated — notably, including matrices A with nonnegative entries [ 37 , 38 , 36 ] . A particularly compelling motivation for studying the permanent comes from the study of linear optics and the boson sampling problem [ 1 ] . In this setting, output probabilities of a quantum experiment are expressed in terms of permanents of random matrices, and the conjectured classical hardness of approximating these quantities is one of the main pieces of evidence for quantum computational advantage. Understanding when such permanents can nevertheless be approximated classically is therefore closely tied to the limits of classical simulation of quantum systems. See, e.g., [ 4 , 26 , 39 , 15 ] for some relevant work and further discussion. There is a natural analogy with cryptography here. To understand the security of a cryptographic primitive, one develops attacks and then tries to understand why those attacks fail beyond a certain point. The “primitive” is the conjectured average-case hardness of approximating the permanent of a random matrix, and the “attacks” are efficient approximation algorithms. So far, the most powerful line of attack has been based on algorithmic Taylor expansions, as we discuss next. Previous work. Barvinok [ 9 , 10 ] showed that it is possible to approximate the permanent of some matrices with positive and negative entries — those which are sufficiently diagonally dominant. In general, Barvinok’s interpolation method reduces approximate counting to proving that a suitable partition function has no zeros in a region connecting a trivial point to the point of interest. Random matrices are very far from diagonally dominant, but Eldar and Mehraban [ 26 ] gave a new analysis of the zeros which shows that interpolation can be used to approximate the permanent of a random matrix with a mean of order 1/\mathrm{polyloglog}(n) . Using a different approach (not based on complex analysis), Ji, Jin, and Lu [ 39 ] gave an improved approximation algorithm which estimates the permanent of a matrix with a mean of order 1/\mathrm{polylog}(n) in quasipolynomial time. However, the limit of 1/\mathrm{polylog}(n) seems fundamental to their approach: “with our technique only, it is rather hard to go beyond the 1/\mathrm{polylog}(n) barrier and essential new ideas seem necessary if this is ever possible.” [ 39 ] Our results. In this paper, we revisit the interpolation approach to approximating the permanent, and show how to obtain dramatically stronger results. The core mathematical problem is to understand the complex zeros of the random polynomial \per(zJ+W), where J is the all-ones matrix and W is an n\times n random matrix with independent mean-zero entries. This polynomial interpolates between the easily understood matrix J (at the point z=\infty ) and the random matrix W (at z=0 ). If one can show that \per(zJ+W) is zero-free along a path from large |z| down to the desired scale, then Barvinok’s method yields an efficient approximation algorithm for the permanent of a random matrix whose entries have a small nonzero bias. Our first main result concerns the complex Gaussian setting. When the entries of W are standard complex Gaussians, we prove that with high probability all zeros of \per(zJ+W) lie within a disk of radius \tilde{O}(n^{-1/3}) . Prior to this work, it was not even known whether zeros of constant magnitude typically occur. As a consequence, we obtain a polynomial time approximation algorithm when the bias of the entries is \Omega(n^{-1/3+\beta}) for any \beta>0 . We include a concrete theorem statement below for clarity. Theorem 1 (Short version of Theorem 27 ) . Let \gamma,\beta>0 and \delta>0 . There exists a deterministic algorithm such that for all sufficiently large n\geq n_{0}(\gamma,\beta,\delta) , the algorithm outputs an n^{-\gamma} -approximation to \log\per(Jz+W) for any |z|\geq n^{-1/3+\beta} with probability at least 1-\delta (uniformly over z ) and with runtime n^{O(\gamma)}. The algorithm is based on Taylor expansion to degree O(\gamma) ; note that \gamma>0 is chosen by the user, so our algorithm can achieve arbitrarily small inverse polynomial accuracy. This substantially improves on the state of the art, where such an approximation guarantee was only known for biases on the order of 1/\mathrm{polylog}(n) , and with quasipolynomial runtime [ 39 ] . We also prove a complementary result showing that the bulk of the zeros, namely (1-\epsilon)n of them, have magnitude \Theta(n^{-1/2}) . Thus, while all zeros lie in a disk of radius about n^{-1/3} , most zeros are in fact concentrated at the smaller scale n^{-1/2} . This gives a conceptual check on the scope of our algorithmic result: the zero-free region we prove is genuinely nontrivial, but it remains outside the regime where one might expect to contradict the conjectured average-case hardness of approximating the permanent. Beyond the Gaussian case, we establish universality by showing that zero-free regions at scale n^{-1/4} continue to exist for much more general random matrices with i.i.d. subexponential entries. Our methods also extend beyond permanents — in particular, we establish analogous zero-free regions for the hardcore model on general graphs with complex vertex fugacities. As we shall see later, the permanent morally corresponds to hardcore model on the line graph of K_{n,n} , also known as the monomer-dimer model on K_{n,n} . 1.1 Further related work The study of complex zeros of partition functions has a long history in statistical physics and combinatorics, beginning with seminal work of Lee and Yang [ 43 ] which established a zero-free region for the Ising model and established connections between zeros and phase transitions. In the case of monomer–dimer systems, the classical theorem of Heilmann and Lieb [ 32 ] plays an analogous role. More broadly, a large literature has developed around zero-free regions for independence, matching, and related polynomials, together with their algorithmic consequences; see for example [ 16 , 55 , 54 , 20 , 14 , 47 , 50 , 45 ] . There is a substantial literature on approximation algorithms for the permanent outside the random small-bias setting. For nonnegative matrices, we previously mentioned the breakthrough FPRAS of Jerrum, Sinclair, and Vigoda [ 37 , 38 , 36 ] . Deterministic approximation via Bethe-type variational methods and related ideas has also been studied extensively, see for example [ 44 , 19 , 30 , 8 , 66 ] . Other recent work has considered structured matrix classes, such as positive semidefinite matrices [ 24 ] , as well as exponential time algorithms [ 21 ] . On the probabilistic side, several works study the size and anticoncentration of the permanent of random matrices [ 61 , 62 , 41 , 35 , 1 ] . More broadly, our results fit into a growing body of work connecting the geometry of complex zeros to computational tractability and hardness in counting problems. In particular, for spin systems and graph polynomials, recent works have related the presence of zeros or zero-dense regions to phase transitions, failure of correlation decay, and hardness of approximation — see, e.g., [ 56 , 17 , 22 , 28 , 13 , 12 ] . Our result fits into a line of recent works concerning algorithms for disordered systems. Perhaps most closely relevant, Bencs, Huang, Lee, Liu, and Regts [ 11 ] studied zero-free regions and quasipolynomial-time approximation in mean-field spin glasses using Barvinok’s approach combined with a reweighted second moment calculation. In their context the reweighting plays a less critical role: it is used to improve a O(1) bound on the number of zeros, which already gives useful algorithmic consequences, to a zero-freeness result. Another technically relevant work is due to Mohanty and Rajaraman [ 46 ] , where they analyzed eigenvalues of random matrices by viewing the corresponding determinant as a random polynomial and analyzing its zeros. These works fit into a broader literature rigorously analyzing how algorithmic thresholds shift (compared to worst-case/uniqueness thresholds) when there are random weights in the model — see, e.g., [ 29 , 25 , 2 , 7 , 6 , 18 , 5 , 40 ] . Finally, our motivation is tied to the literature on boson sampling and quantum advantage, where permanents of random matrices appear as output amplitudes or probabilities. This has led to sustained interest in the average-case complexity of the permanent, in the power and limits of classical simulation, and in identifying regimes where structured instances admit efficient classical algorithms — see, e.g., [ 1 , 31 , 21 , 4 ] . 2 Overview 2.1 Riemann sphere perspective The following perspective formalizes the point z=\infty and is helpful for keeping track of the scale of different quantities in the analysis. We are interested in locating the zero set of the degree n polynomial z\mapsto\per(zJ+W), which is a zero-dimensional affine variety. It is natural to homogenize and rephrase the question in terms of the corresponding zero-dimensional projective variety \mathcal{V}=\{[z_{1}:z_{2}]:\per(z_{1}J+z_{2}W)=0\}\subset\mathbb{P}^{1} which lives inside the Riemann sphere \mathbb{P}^{1}=\{[z:1]:z\in\mathbb{C}\}\cup\{[1:0]\} . This gives us two symmetrical ways to think about the zero set: 1. The zeros of the projective version are in one-to-one correspondence to the original affine version under the map [z_{1}:z_{2}]\to z_{1}/z_{2} , because at the new point at \infty , i.e. at [1:0] , we have that \per(J)=n!\neq 0 . 2. On the other hand, for generic W we have that \per(W)\neq 0 , so the zero set is also in one-to-one correspondence with the zero-dimensional affine variety \{z:\per(J+zW)=0\} under the map [z_{1}:z_{2}]\to z_{2}/z_{1} . We will almost always use the latter “inverted” coordinate system in what follows. The reason is our original goal, which is to prove there are no zeros of the original polynomial of, e.g., scale 1/n^{1/4} or larger, is more naturally rephrased by centering about the point at infinity: we will show there are no solutions of \per(J+zW)=0 such that |z|\ll n^{1/4} . 2.2 Previous approaches The best zero-freeness results known so far came from the original work of Eldar and Mehraban [ 26 ] . By using Jensen’s formula from complex analysis, combined with an upper bound on the sensitivity of the permanent [ 52 ] , they proved (Equation (28) of [ 26 ] ) that for any r>0 , \mathbb{E}\#\{|z|1 , with probability at least 1-1/r there are at most 4r^{3} roots within distance r of the origin. This result is used to obtain their main algorithmic result, by arguing they can pick a path likely to avoid these roots and then iteratively Taylor expand along this path. • Region with o(n) zeros. For any r=o(\sqrt{n}) , with probability 1-o(1) there are at most o(n) roots within distance r of the origin. This can also be deduced by combining coefficient bounds in [ 26 ] with results from the theory of random polynomials (see Theorem 4 of [ 34 ] ). It turns out that the last estimate for o(n) zeros is qualitatively sharp (see Section 9 ). However, the former two estimates are the ones which are relevant to algorithms; To apply Barvinok’s method [ 9 ] , we need to have a guarantee for a region that there are no zeros (or very few, so that we may hopefully pick a further subregion which is truly zero-free, as done in [ 26 ] ). Algorithm of Ji, Jin, and Lu [ 39 ] . Interestingly, the best current algorithm for this problem does not use the zero-free machinery at all. Instead, they use the more direct interpretation of \per(J+zW) as a generating function for subpermanents of W : \frac{1}{n!}\per(J+zW)=\frac{1}{n!}\sum_{\sigma}\prod_{i=1}^{n}(J+zW)_{i\sigma(i)}=\sum_{k=0}^{n}\frac{(n-k)!}{n!}z^{k}\sum_{B\subset_{k}W}\per(B) where B ranges over k\times k submatrices of W . The number of such submatrices B is {n\choose k}^{2}=\left(\frac{(n!)}{(n-k)!k!}\right)^{2} , so the standard deviation of the k th coefficient is \sqrt{\operatorname{Var}\left(\frac{(n-k)!}{n!}\sum_{B\subset_{k}W}\per(B)\right)}=\frac{1}{k!}. (2) Because this decays as 1/k!\leq(e/k)^{k} , we can hope that if z=O(\mathrm{polylog}(n)) , then truncating the expansion after O(\mathrm{polylog}(n)) terms will achieve small error; this is rigorously justified in [ 39 ] and gives a quasipolynomial time algorithm in this regime. 2.3 New approach We show the zero-free region is actually much larger than previously known, and thereby obtain stronger algorithmic consequences. Our analysis is inspired by an ansatz which suggests that a large cancellation may occur (Equation ( 5 ) below). The following analogy is helpful for understanding where this guess comes from. Analogy between permanent and hardcore model. By definition, \per(J+zW)=\sum_{\sigma}\prod_{i}(J+zW)_{i\sigma(i)} Consider expanding out the terms on the right hand side. For each row i , each term encodes a choice of: • A potential column \sigma(i) to match row i with. • Whether to include this edge or not ( zW_{i\sigma(i)} if yes, or 1 if not). This means that every term in the sum can be mapped to a corresponding matching of the complete n\times n bipartite graph. Now, observe that for every matching M in the bipartite graph, there are (n-|M|)! permutations in the sum each generating the matching one time. So we can rewrite \displaystyle\frac{1}{n!}\per(J+zW) \displaystyle=\sum_{M}\frac{(n-|M|)!}{n!}\prod_{(i,j)\in M}(zW_{ij}) (3) Pretend that we can replace (n-|M|!)/n! in the expression for per(J+zW)/n! in ( 3 ) by 1/n^{|M|} — then we get the partition function of a hardcore model on the line graph of the complete bipartite graph K_{n,n} with complex fugacities: Z(z)=\sum_{M}\prod_{(i,j)\in M}(zW_{ij}/n) This model is also known as a monomer-dimer model . The hardcore constraint encodes that each vertex in the original graph will be adjacent to at most one edge from the matching M . We call this hardcore model the idealized model of the permanent; it makes the next step much more transparent. Remark 2 (Comparison with Heilmann-Lieb theorem [ 32 ] ) . Suppose W_{ij}=1 for all i,j , then this is the matching polynomial of the complete bipartite graph. By the Heilmann-Lieb theorem [ 32 ] , all of the zeros of Z(z) would be along the negative real axis. More generally, the Heilmann-Lieb theorem applies when W_{ij}\geq 0 . However, we are interested in weights with mean zero so the behavior will be quite different. Cluster expansion of idealized hardcore model. Note that Z(0)=1 because the empty set is the only size 0 matching. Using the identity \log(1+x)=x-x^{2}/2+x^{3}/3-\cdots we can expand the partition function as a formal power series 1 1 1 The Taylor series \log(1+x) does converge when |x|<1 , but we will be considering the resulting series expansion in situations far outside this regime — where, e.g., |Z(z)|=\Omega(e^{n^{1/10}})\gg 1 . in z and obtain \log Z(z)=(z/n)\sum_{ij}W_{ij}-(z/n)^{2}\left(\sum_{v}W_{ij}^{2}/2+\sum_{ijk:i\neq k}W_{ij}W_{kj}+\sum_{ijk:j\neq k}W_{ij}W_{ik}\right)+O_{n}(z^{3}). For the hardcore model, there is a systematic way to compute any of the formal power series coefficients in terms of a sum over connected diagrams, which leads this series to be called the cluster expansion [ 27 ] . See Figure 1 . We can compute that the first term in the expansion of \log Z has variance O(z^{2}) and the second term has variance O(z^{4}/n) . More generally, from the explicit cluster expansion formula (see Section 3 ) we know that the k th term has variance O_{k}(z^{2k}/n^{k-1}) . If |z|^{4}\ll n , the contribution of the second term in the expansion is o(1) , which suggests we might be able to make the approximations \log\frac{\per(J+zW)}{n!}\approx\log Z(z)\approx(z/n)\sum_{ij}W_{ij}\,? (4) order 1 order 2 single edge same edge twice share a row share a column order 3 same edge three times double edge + row-adjacent double edge + column-adjacent K_{2,2} – one edge left 3-star right 3-star Figure 1: Connected diagrams contributing to the first three orders of the formal expansion of \log Z(z) for the idealized monomer–dimer model on K_{n,n} . We emphasize that the validity of neglecting all of the high-degree terms is not obvious, though it will ultimately be justified by our proof. Many important perturbative expansions do not converge 2 2 2 For example, the Dyson series in QED (Quantum Electrodynamics, the fundamental theory governing the behavior of light) is known to have a radius of convergence equal to zero based on physical considerations [ 23 ] . , and are at best asymptotic series expansions (see, e.g., the discussion in Chapter 13.1 of [ 60 ] ). The basic reason these types of perturbative expansions can fail to converge is the dependence of the coefficient a_{k} on k . Usually there is a combinatorial explosion in the number of terms contributing to the k th coefficient, so that the magnitude of |a_{k}| can grow like k! or worse. The dependence on k can be neglected for k small and n large, but the power series for the cluster expansion ranges from k=1 to \infty for any finite n . Remark 3 (Cancellations in cluster expansion) . As stated above, the variance of the k th coefficient in the Taylor series for \log Z decays rapidly with n for fixed k . However, in the polynomial expansion of Z they do not — they are \Theta_{k}(1) by a calculation analogous to ( 2 ). This discrepancy indicates that massive cancellations occurred when we expanded the formal series for \log(1+x) , and gives some indication why we can dramatically improve over the approach of [ 39 ] . Convergence and zero-free region. The mathematical heart of this work is to prove that for the log-permanent, the series expansion does have a large (polynomial in n ) radius of convergence. Unfortunately, standard methods for analyzing the convergence of the cluster expansion such as the Kotecký-Preiss (KP) condition completely fail at this task; they can show at best that our power series converges at some radius of the order of O(1) , which is already known [ 26 ] . The KP condition and similar methods aim to directly show that the power series is absolutely convergent by comparing the magnitude of various terms in the expansion — this will not work well in our situation, where we want to take advantage of large cancellations caused by the random sign/phase of the weights. Since the permanent itself is analytic, for the log-permanent to have a convergent expansion we need to show that there are no small complex zeros z such that \per(J+zW)=0 . Note that because the permanent is a degree n polynomial, we are guaranteed to have n zeros somewhere, but we want to show that they are far away from the origin (or, in the original coordinate system, the point at infinity). A natural way to prove such a zero-free region exists is by applying Jensen’s formula from complex analysis, which is an explicit relation between the location of the zeros of a holomorphic function to its averaged rate of growth. In particular, if we consider any R>r and count the number of zeros z_{1},\ldots,z_{m} of \per(J+zW) inside the smaller disc of radius r , we find \#\{|z|0 , then we would be able to approximate the permanent of a random matrix better than expected, which would break the complexity-theoretic assumptions used to argue for the hardness of boson sampling in [ 1 ] . Interestingly, we are able to prove that (1-\epsilon)n of the zeros of \per(J+zW) are at scale \Theta(\sqrt{n}) , forming a direct obstruction to convergence of the Taylor series expansion. So if it is possible to break the conjectured hardness of approximating the permanent, new algorithmic ideas would have to be required. At a technical level, this result would be much easier to prove if we knew the conjectured anticoncentration of the permanent to be true. However, existing results fall far short of proving this conjecture (see [ 1 , 61 , 62 ] ) and, in particular, seem to be too weak for our present application. In the end, we are able to recover the result unconditionally by deriving an inductive lower bound on \mathbb{E}\log|\per(W)|^{2} (Lemma 49 ). 2.4 Organization After going through some mathematical preliminaries (Section 3 ), we go on to develop our main results for the permanent. In Section 4 , to introduce our method we go through the proof that for complex Gaussians, the radius of convergence is at least O(n^{1/4}) . This initial result is subsumed by the more sophisticated arguments in the next two sections: in Section 5 , we show that for the complex Gaussian case we can improve the radius of convergence to O(n^{1/3}) , and in Section 6 , we show that the O(n^{1/4}) -radius zero-free result is true for arbitrary subexponential distributions. We then proceed to establish analogous results in the setting of the hardcore model on a general graph. We prove that analogous zero-free results hold for the hardcore model on any graph of maximum degree \Delta with subexponential weights — first in Section 7 for the case of complex Gaussian weights, and then in Section 8 for general subexponential weights. Conceptually, these developments are parallel to the analysis of the permanent, although the technical details differ significantly. In Section 9 we analyze the relationship between our findings with the conjectured average-case hardness permanent: we show that if the radius of convergence can be improved to \omega(\sqrt{n}) , then we can estimate the permanent on a classical computer better than is predicted possible by [ 1 ] , and we show that under the anticoncentration conjecture about Gaussian permanents, the radius of convergence cannot be improved beyond \Theta(\sqrt{n}) . In Appendix A , we give the results of numerical experiments for small values of n . In Appendix B , we discuss a connection between the formulas we establish and the Bethe approximation used in variational inference. In Appendix C , we include estimates on the size of the low-degree terms in the cluster expansion, and its permanent analogue. 3 Preliminaries 3.1 Complex analysis See the textbook [ 59 ] for a more comprehensive reference. Jensen’s formula. We make extensive use of Jensen’s formula from complex analysis, which says that if f is an analytic function, r>0 , and a_{1},\ldots,a_{N} are the complex zeros of f inside of the disc of radius r about the origin, repeated according to their multiplicities, then \log|f(0)|=-\sum_{k=1}^{N}\log\frac{r}{|a_{k}|}+\frac{1}{2\pi}\int_{0}^{2\pi}\log|f(re^{i\theta})|d\theta. So \log|f(0)| is determined by the locations of the singularities within the disc, and by its average value on the boundary. A commonly used consequence of this result is that if we consider any R>r and apply the formula at radius R while still considering zeros a_{1},\ldots,a_{N} inside the smaller disc of radius r , we find m\log(R/r)\leq\sum_{k=1}^{N}\log\frac{R}{|a_{k}|}\leq\frac{1}{2\pi}\int_{0}^{2\pi}\log|f(Re^{i\theta})|d\theta-\log|f(0)| (6) which is a convenient way to upper bound the number of zeros N . The precise way we will use Jensen’s formula is stated in the following lemma. Let D(0,r)=\{z:|z|r>0 and let f and h be random functions which are almost surely holomorphic on an open set containing D(0,R) and such that f(0)\neq 0 almost surely. Let g=e^{h}f , then \mathbb{E}\,N_{f}(r)\leq\frac{1}{4\pi\log(R/r)}\int_{0}^{2\pi}\log\mathbb{E}|g(Re^{i\theta})|^{2}d\theta-\mathbb{E}\log|g(0)|. Proof. By construction, f and g have the same zeros, so it is equivalent to bound \mathbb{E}N_{g}(r) . Also, \log|g(z)|=\frac{1}{2}\log|g(z)|^{2} . So the expected number of zeros can be bounded by Jensen’s formula ( 6 ), using that \mathbb{E}_{\theta}\mathbb{E}\log|g(Re^{i\theta})|^{2}\leq\mathbb{E}_{\theta}\log\mathbb{E}|g(Re^{i\theta})|^{2} by Jensen’s inequality. Here the expectation over \theta is just the uniform measure from 0 to 2\pi . This proves the result. For an alternative proof, we can apply Jensen’s formula directly to f , and use that \frac{1}{2\pi}\int\log|e^{h}(Re^{i\theta})|d\theta=\log|e^{h(0)}| since \log|e^{h}| is a harmonic function. Therefore, the net contribution of h to the right hand side of Jensen’s formula is zero, so we can add zero to both sides and then the conclusion follows by Jensen’s inequality as above. ∎ Integrating the logarithmic derivative. We will also use the standard fact that a nowhere-vanishing analytic function admits a holomorphic logarithm on any simply connected domain (Theorem 6.2 of [ 59 ] ). Explicitly, if \Omega\subset\mathbb{C} is simply connected and f is holomorphic on \Omega with f(z)\neq 0 for all z\in\Omega , then there exists a holomorphic function g on \Omega such that f(z)=e^{g(z)}\qquad(z\in\Omega). Equivalently, g^{\prime}(z)=f^{\prime}(z)/f(z) . In particular, fixing a base point z_{0}\in\Omega and a choice of logarithm g(z_{0})=\log f(z_{0}) , one has g(z)=\log f(z_{0})+\int_{\gamma}\frac{f^{\prime}(w)}{f(w)}\,dw, (7) where \gamma is any piecewise C^{1} path in \Omega from z_{0} to z . Because \Omega is simply connected and f^{\prime}/f is holomorphic, the integral is path-independent. 3.2 Hardcore model and cluster expansion Let G=(V,E) be a finite graph and let \lambda=(\lambda_{v})_{v\in V}\in\mathbb{C}^{V} be a collection of complex fugacities assigned to its vertices. The hardcore model is a statistical mechanics model defined on the collection of all independent sets \mathcal{I}(G) of the graph. As a reminder, an independent set I is a subset of vertices such that no two elements of I are adjacent in the graph. We can think of the hardcore model as a “gas” of particles: each vertex can be occupied by at most one particle, and two particles cannot be at the same or at adjacent vertices. Each particle can be thought of as a hard sphere of radius 1 , and the adjacency constraint is to prevent spheres from overlapping. See [ 49 , 27 ] for more background and context. The partition function Z(\lambda) of the hardcore model is the sum of the weights of all valid independent sets: Z(\lambda)=\sum_{I\in\mathcal{I}(G)}\prod_{v\in I}\lambda_{v}. (8) Observe from the definition that Z(0)=1 , since the product is taken over the empty set. Cluster Expansion The cluster expansion provides a formal power series for \log Z(\lambda) . To formulate it, we define a cluster as a multiset of vertices, which we can represent as a tuple of multiplicities \mathbf{m}=(m_{v})_{v\in V}\in(\mathbb{Z}_{\geq 0})^{V} . For any given multiset \mathbf{m} , we construct an incompatibility graph H[\mathbf{m}] by taking m_{v} distinguishable copies of each vertex v\in V , and drawing an edge between two copies if they correspond to the exact same vertex or to adjacent vertices in G . The cluster expansion of the log partition function is given by: \log Z(\lambda)=\sum_{\mathbf{m}\neq\mathbf{0}}\frac{1}{\mathbf{m}!}\phi(H[\mathbf{m}])\prod_{v\in V}\lambda_{v}^{m_{v}} (9) where \mathbf{m}!=\prod_{v\in V}m_{v}! , and \phi(H) is the Ursell function. For any graph H=(W,E_{H}) , the Ursell function evaluates the sum over all its connected spanning subgraphs: \phi(H)=\sum_{\begin{subarray}{c}A\subseteq E_{H}\\ (W,A)\text{ is connected}\end{subarray}}(-1)^{|A|} (10) Note that if the incompatibility graph H[\mathbf{m}] is disconnected, \phi(H[\mathbf{m}])=0 , which ensures the expansion only sums over “connected” clusters . We can think of the cluster expansion as essentially a generalized version of the identity \log(1+z)=z-z^{2}/2+z^{3}/3+\cdots which is convergent when |z|<1 . In fact, this is exactly the cluster expansion of the hardcore model on a single-vertex graph, because the corresponding Ursell function is (-1)^{m-1}(m-1)! . First few terms of cluster expansion. Let \lambda_{v}=\lambda W_{v} . The first couple of terms of the cluster expansion are \log Z(\lambda)=\lambda\sum_{v}W_{v}-\lambda^{2}(\sum_{v}W_{v}^{2}/2+\sum_{u\sim v}W_{u}W_{v})+O(\lambda^{3}). Here for the formal power series, when we write O(\lambda^{3}) it only means that all remaining terms in the formal expansion have degree 3 or higher. Kotecký–Preiss condition. A standard sufficient condition for absolute convergence of the cluster expansion is the Kotecký–Preiss (KP) criterion [ 27 , 49 ] . As emphasized earlier, this condition will not give very impressive results if directly applied to a hardcore model with random fugacities, since it does not take advantage of phase cancellations. However, the KP condition will end up to be useful to handle auxiliary models which show up in our mathematical analysis. Proposition 5 (Kotecký–Preiss criterion) . Assume there exists a collection of numbers (a_{v})_{v\in V} with a_{v}\geq 0 such that for every v\in V , \sum_{u\in\{v\}\cup N(v)}|\lambda_{u}|e^{a_{u}}\leq a_{v}, (11) where N(v) denotes the set of neighbors of v in G . Then the cluster expansion for \log Z(\lambda) converges absolutely. More precisely, for every v\in V , \sum_{\mathbf{m}:\,m_{v}\geq 1}\frac{1}{\mathbf{m}!}\,\bigl|\phi(H[\mathbf{m}])\bigr|\prod_{u\in V}|\lambda_{u}|^{m_{u}}\leq a_{v}. (12) In particular, Z(\lambda)\neq 0 , and hence \log Z(\lambda) is well-defined and analytic in this region. Note that by summing ( 12 ) over vertices v , we have in particular that |\log Z(\lambda)|\leq\sum_{v}a_{v}, so the KP condition is very useful for bounding partition functions. Spanning tree bound. The following lemma provides a useful upper bound on the magnitude of the Ursell function. Lemma 6 (Lemma 3.4 of [ 51 ] ) . Let H=(V,E) be a finite connected graph. Then |\phi(H)|\leq\tau(H), where \tau(H) denotes the number of spanning trees of H . In particular, if |V|=k , then |\phi(H)|\leq k^{k-2}. This estimate can be recovered as a corollary of the fact that Ursell coefficients admit a representation in terms of spanning trees [ 48 , 51 ] . 3.3 Wick’s formula Wick’s formula gives a combinatorial expression for Gaussian moments in terms of sums over pairings. This is a clean example in which moments reduce to partition functions of an auxiliary system, and it plays an important role in the second-order analysis of the permanent (Section 5 ). Real case. Let (G_{u})_{u\in I} be a centered real Gaussian process. Then all odd moments vanish. Moreover, for any even collection u_{1},\dots,u_{2m} , \mathbb{E}\!\left[\prod_{j=1}^{2m}G_{u_{j}}\right]=\sum_{P\in\mathcal{P}_{2m}}\prod_{\{a,b\}\in P}\mathbb{E}[G_{u_{a}}G_{u_{b}}], where \mathcal{P}_{2m} denotes the set of pairings of \{1,\dots,2m\} . Complex case. Let (G_{u})_{u\in I} be a centered circularly symmetric complex Gaussian process. Then \mathbb{E}\!\left[\prod_{i=1}^{m}G_{u_{i}}\prod_{j=1}^{n}\overline{G_{v_{j}}}\right]=0\qquad\text{if }m\neq n, and when m=n , \mathbb{E}\!\left[\prod_{i=1}^{m}G_{u_{i}}\prod_{j=1}^{m}\overline{G_{v_{j}}}\right]=\sum_{\sigma\in S_{m}}\prod_{i=1}^{m}\mathbb{E}[G_{u_{i}}\overline{G_{v_{\sigma(i)}}}]. 3.4 Combinatorial identities We will use a standard generating function identity for permutations — see Chapter 2 of [ 57 ] . It follows from the formula for the number of derangements D_{m} of [m] , D_{m}=m!\sum_{j=0}^{m}\frac{(-1)^{j}}{j!}, which is Example 2.2.1 of [ 57 ] . As a reminder, a derangement is a permutation with no fixed points. Lemma 7 . Let \pi\sim\mathsf{Unif}(S_{n}) and let \fix(\pi):=\#\{i\in[n]:\pi(i)=i\} be the number of fixed points of \pi . Then for every t\in\mathbb{C} , \mathbb{E}_{\pi}[t^{\fix(\pi)}]=\sum_{k=0}^{n}\frac{(t-1)^{k}}{k!}. As a consequence, if t>1 then \mathbb{E}_{\pi}[t^{\fix(\pi)}]\leq e^{t-1} . Proof. By decomposing a permutation into its fixed points and a derangement of the remaining points, we find \mathbb{E}_{\pi}[t^{\fix(\pi)}]=\frac{1}{n!}\sum_{k=0}^{n}\binom{n}{k}D_{n-k}t^{k}. Using the derangement identity above gives \displaystyle\mathbb{E}_{\pi}[t^{\fix(\pi)}] \displaystyle=\sum_{k=0}^{n}\frac{t^{k}}{k!}\sum_{j=0}^{n-k}\frac{(-1)^{j}}{j!}=\sum_{m=0}^{n}\sum_{k=0}^{m}\frac{t^{k}}{k!}\frac{(-1)^{m-k}}{(m-k)!}=\sum_{m=0}^{n}\frac{1}{m!}\sum_{k=0}^{m}\binom{m}{k}t^{k}(-1)^{m-k} \displaystyle=\sum_{m=0}^{n}\frac{(t-1)^{m}}{m!}, and the inequality when t>1 follows by Taylor series expansion of the exponential. ∎ Remark 8 . This generating function identity is one example illustrating how the combinatorics of summing over permutations has nice algebraic properties. Because the general hardcore model (which instead sums over matchings on a general graph) does not have this nice permutation structure, we will see that our analysis changes significantly. Stirling’s formula. Since we will be working with permutations, it is helpful to remember Stirling’s approximation: \log(n!)=n\log(n/e)+\log(2\pi n)/2+o(1) as n\to\infty . 4 First-order permanent analysis In this section, we show how to analyze the zero-free region for matrices with complex Gaussian entries up to |z|=\tilde{O}(n^{1/4}) . This result will be improved in later sections using more sophisticated arguments, so it is helpful to go through this simpler result first. Setup. Let W\in\mathbb{C}^{n\times n} be a random matrix with i.i.d. entries W_{ij}\sim\mathcal{N}_{\mathbb{C}}(0,1) , where by \mathcal{N}_{\mathbb{C}}(0,1) we mean the standard complex Gaussian with density \frac{1}{\pi}e^{-|w|^{2}} for w\in\mathbb{C} . Let J denote the n\times n all-ones matrix, and define P_{n}(z):=\frac{1}{n!}\per(J+zW)=\mathbb{E}_{\sigma\sim S_{n}}\Big[\prod_{i=1}^{n}\bigl(1+zW_{i,\sigma(i)}\bigr)\Big]. We also define the global linear statistic D_{1}(W):=\frac{1}{n}\sum_{i,j=1}^{n}W_{ij}, and the first-order reweighted permanent X^{(1)}(z):=P_{n}(z)\exp\bigl(-zD_{1}(W)\bigr). First moment. Observe that \mathbb{E}X^{(1)}(z)=1 due to the circular symmetry of the complex Gaussian. Explicitly, if we Taylor expand X^{(1)}(z)=\sum_{k\geq 0}c_{k}(W)\,z^{k}, then each c_{k} is a homogeneous polynomial of degree k in the entries of W , so c_{k}(e^{i\theta}W)=e^{ik\theta}c_{k}(W) . Since e^{i\theta}W\stackrel{{\scriptstyle d}}{{=}}W for every \theta\in\mathbb{R} , we obtain \mathbb{E}[c_{k}(W)]=\mathbb{E}[c_{k}(e^{i\theta}W)]=e^{ik\theta}\mathbb{E}[c_{k}(W)]. Hence \mathbb{E}[c_{k}(W)]=0 for all k\geq 1 , while c_{0}(W)=1 . 4.1 Tilted measure and exact moment formula We define the tilted expectation \widehat{\mathbb{E}} by \widehat{\mathbb{E}}[f(W)]:=\frac{\mathbb{E}\!\left[f(W)\exp\!\bigl(-2\Re(zD_{1}(W))\bigr)\right]}{\mathbb{E}\!\left[\exp\!\bigl(-2\Re(zD_{1}(W))\bigr)\right]}. Lemma 9 (Linear tilt of a complex Gaussian product measure) . Under the tilted law \widehat{\mathbb{E}} , the entries W_{ij} remain independent complex Gaussians, each with variance 1 , vanishing pseudo-variance, and common mean \widehat{\mathbb{E}}[W_{ij}]=-\frac{\overline{z}}{n}. In other words, under \widehat{\mathbb{E}} we have W_{ij}\sim\mathcal{N}_{\mathbb{C}}\!\left(-\frac{\overline{z}}{n},\,1\right) i.i.d. Moreover, M(z):=\mathbb{E}\!\left[\exp\!\bigl(-2\Re(zD_{1}(W))\bigr)\right]=e^{|z|^{2}}. Proof. Since the entries are independent, it suffices to work entrywise. Write u:=z/n , so 2\Re(zD_{1}(W))=2\Re\!\left(\frac{z}{n}\sum_{i,j}W_{ij}\right)=\sum_{i,j}2\Re(uW_{ij}). Hence \exp\!\bigl(-2\Re(zD_{1}(W))\bigr)=\prod_{i,j}\exp\!\bigl(-2\Re(uW_{ij})\bigr). Therefore the tilt factorizes over entries, so under the tilted law the entries remain independent. Now fix one entry W\sim\mathcal{N}_{\mathbb{C}}(0,1) , with density \pi^{-1}e^{-|w|^{2}} . Under the tilt by e^{-2\Re(uw)} , its density becomes proportional to e^{-|w|^{2}}e^{-2\Re(uw)}=e^{-(|w|^{2}+2\Re(uw))}=e^{-|w+\overline{u}|^{2}+|u|^{2}}. Thus, after normalization, the tilted law is exactly \mathcal{N}_{\mathbb{C}}(-\overline{u},1) . Since u=z/n , this gives \widehat{\mathbb{E}}[W_{ij}]=-\frac{\overline{z}}{n}. The variance and pseudo-variance are unchanged because only the mean is shifted. Finally, the normalizing constant is M(z)=\prod_{i,j}\mathbb{E}\bigl[e^{-2\Re(uW_{ij})}\bigr]. For one standard complex Gaussian W , \mathbb{E}[e^{-2\Re(uW)}]=e^{|u|^{2}} , by the same completion-of-squares calculation. Therefore M(z)=\bigl(e^{|u|^{2}}\bigr)^{n^{2}}=e^{n^{2}|z|^{2}/n^{2}}=e^{|z|^{2}} . ∎ Lemma 10 (Exact second moment) . Let \alpha:=\frac{|z|^{2}}{n},\qquad\kappa=1-\alpha. Then \mathbb{E}\bigl[|X^{(1)}(z)|^{2}\bigr]=e^{|z|^{2}}\,\kappa^{2n}\sum_{k=0}^{n}\frac{1}{k!}\left(\frac{|z|^{2}}{\kappa^{2}}\right)^{k}. Proof. By definition of the tilted expectation, \mathbb{E}\bigl[|X^{(1)}(z)|^{2}\bigr]=\mathbb{E}\!\left[|P_{n}(z)|^{2}e^{-2\Re(zD_{1}(W))}\right]=M(z)\,\widehat{\mathbb{E}}\bigl[|P_{n}(z)|^{2}\bigr]. By Lemma 9 , M(z)=e^{|z|^{2}} , so it remains to compute \widehat{\mathbb{E}}[|P_{n}(z)|^{2}] . Under \widehat{\mathbb{E}} , write W_{ij}=-\frac{\overline{z}}{n}+\eta_{ij}, where \eta_{ij} are i.i.d. \mathcal{N}_{\mathbb{C}}(0,1) . Then 1+zW_{ij}=1-\frac{|z|^{2}}{n}+z\eta_{ij}=\kappa+z\eta_{ij}. Hence P_{n}(z)=\mathbb{E}_{\sigma\sim S_{n}}\Big[\prod_{i=1}^{n}(\kappa+z\eta_{i,\sigma(i)})\Big] and so \widehat{\mathbb{E}}[|P_{n}(z)|^{2}]=\mathbb{E}_{\sigma,\tau\sim S_{n}}\widehat{\mathbb{E}}\Bigg[\prod_{i=1}^{n}(\kappa+z\eta_{i,\sigma(i)})\prod_{j=1}^{n}(\kappa+\overline{z}\,\overline{\eta_{j,\tau(j)}})\Bigg]. Fix \sigma,\tau\in S_{n} . Let F(\sigma,\tau):=\{i\in[n]:\sigma(i)=\tau(i)\} and m:=|F(\sigma,\tau)| . Since \sigma and \tau are permutations, the edge sets \{(i,\sigma(i)):1\leq i\leq n\},\qquad\{(j,\tau(j)):1\leq j\leq n\} intersect exactly on the m common edges indexed by F(\sigma,\tau) . Because the \eta_{ab} are independent, centered, and satisfy \widehat{\mathbb{E}}[\eta_{ab}\overline{\eta_{cd}}]=\delta_{ac}\delta_{bd},\qquad\widehat{\mathbb{E}}[\eta_{ab}\eta_{cd}]=0, the expectation factors edge-by-edge. For an edge appearing in only one of the two products, the only surviving contribution comes from taking the constant term \kappa . For a common edge, the contribution is \widehat{\mathbb{E}}\bigl[(\kappa+z\eta)(\kappa+\overline{z}\,\overline{\eta})\bigr]=\kappa^{2}+|z|^{2}. Thus \widehat{\mathbb{E}}\Bigg[\prod_{i=1}^{n}(\kappa+z\eta_{i,\sigma(i)})\prod_{j=1}^{n}(\kappa+\overline{z}\,\overline{\eta_{j,\tau(j)}})\Bigg]=(\kappa^{2}+|z|^{2})^{m}\,\kappa^{2(n-m)}. Equivalently, \widehat{\mathbb{E}}[\cdots]=\kappa^{2n}\left(1+\frac{|z|^{2}}{\kappa^{2}}\right)^{m}. Therefore \widehat{\mathbb{E}}[|P_{n}(z)|^{2}]=\kappa^{2n}\,\mathbb{E}_{\sigma,\tau}\!\left[\left(1+\frac{|z|^{2}}{\kappa^{2}}\right)^{m}\right]. Now if \sigma,\tau are independent uniform permutations, then \pi:=\sigma\tau^{-1} is a uniform permutation, and m=\#\{i:\sigma(i)=\tau(i)\}=\#\{i:\pi(i)=i\} is the number of fixed points of a uniform permutation. Applying Lemma 7 with t=1+\frac{|z|^{2}}{\kappa^{2}} gives \widehat{\mathbb{E}}[|P_{n}(z)|^{2}]=\kappa^{2n}\sum_{k=0}^{n}\frac{1}{k!}\left(\frac{|z|^{2}}{\kappa^{2}}\right)^{k}. Multiplying by M(z)=e^{|z|^{2}} completes the proof. ∎ 4.2 Variance asymptotics Theorem 11 . If |z|=o(n^{1/4}) , then \mathbb{E}\bigl[|X^{(1)}(z)|^{2}\bigr]=1+o(1). Proof. Since |z|=o(n^{1/4}) , we have \frac{|z|^{4}}{n}\to 0 and \alpha=|z|^{2}/n\to 0 . By Lemma 10 , \mathbb{E}\bigl[|X^{(1)}(z)|^{2}\bigr]=e^{|z|^{2}}\kappa^{2n}\sum_{k=0}^{n}\frac{y^{k}}{k!},\qquad y:=\frac{|z|^{2}}{\kappa^{2}}. We first expand the prefactor. Since \alpha\to 0 , \log(1-\alpha)=-\alpha-\frac{\alpha^{2}}{2}+O(\alpha^{3}) , so \displaystyle|z|^{2}+2n\log(1-\alpha)=|z|^{2}-2n\alpha-n\alpha^{2}+O(n\alpha^{3})=-|z|^{2}-\frac{|z|^{4}}{n}+O\!\left(\frac{|z|^{6}}{n^{2}}\right). Hence e^{|z|^{2}}\kappa^{2n}=\exp\!\left(-|z|^{2}-\frac{|z|^{4}}{n}+O\!\left(\frac{|z|^{6}}{n^{2}}\right)\right). Next, y=\frac{|z|^{2}}{(1-\alpha)^{2}}=|z|^{2}(1+2\alpha+O(\alpha^{2}))=|z|^{2}+\frac{2|z|^{4}}{n}+O\!\left(\frac{|z|^{6}}{n^{2}}\right). Also y=o(n) , because |z|^{2}=o(n^{1/2}) . Therefore the truncated exponential sum satisfies \sum_{k=0}^{n}\frac{y^{k}}{k!}=e^{y}(1-o(1)). Indeed, the omitted tail e^{-y}\sum_{k=n+1}^{\infty}y^{k}/k! is the probability that a Poisson (y) random variable exceeds n , which is o(1) when y=o(n) — e.g., by Chebyshev or Chernoff bounds. Thus \sum_{k=0}^{n}\frac{y^{k}}{k!}=\exp\!\left(|z|^{2}+\frac{2|z|^{4}}{n}+O\!\left(\frac{|z|^{6}}{n^{2}}\right)\right)(1-o(1)). Combining the two estimates, \displaystyle\mathbb{E}\bigl[|X^{(1)}(z)|^{2}\bigr] \displaystyle=\exp\!\left(-|z|^{2}-\frac{|z|^{4}}{n}+O\!\left(\frac{|z|^{6}}{n^{2}}\right)\right)\cdot\exp\!\left(|z|^{2}+\frac{2|z|^{4}}{n}+O\!\left(\frac{|z|^{6}}{n^{2}}\right)\right)(1-o(1)) \displaystyle=\exp\!\left(\frac{|z|^{4}}{n}+O\!\left(\frac{|z|^{6}}{n^{2}}\right)\right)(1-o(1)). Since |z|^{4}/n\to 0 , the exponent tends to 0 . Therefore \mathbb{E}\bigl[|X^{(1)}(z)|^{2}\bigr]=1+o(1) as claimed. ∎ From the above result, we can immediately conclude the corresponding zero-free region by applying Jensen’s formula (more precisely, Lemma 4 ), which in turn yields an algorithm via Barvinok interpolation. Since we are about to improve on the above result, we leave further details to the next section. 5 Second-order permanent analysis We now proceed to strengthen the result in the previous section by taking into account the quadratic term in the expansion of the log-permanent. In order to make the calculations clearer, it is helpful to write the second-order reweighting in a geometric way. Second-order reweighting in terms of subspaces. Let W\in\mathbb{C}^{n\times n} have i.i.d. entries W_{ij}\sim\mathcal{N}_{\mathbb{C}}(0,\nu) . Let \mathbb{C}^{n\times n}=\mathcal{H}_{0}\oplus\mathcal{H}_{r}\oplus\mathcal{H}_{c}\oplus\mathcal{H}_{m} where \displaystyle\mathcal{H}_{0} \displaystyle:=\operatorname{span}\{J\}, \displaystyle\mathcal{H}_{r} \displaystyle:=\operatorname{span}\{x\mathbf{1}^{T}:x\in\mathbb{C}^{n},\mathbf{1}^{T}x=0\}, \displaystyle\mathcal{H}_{c} \displaystyle:=\operatorname{span}\{\mathbf{1}y^{T}:y\in\mathbb{C}^{n},\mathbf{1}^{T}y=0\}, \displaystyle\mathcal{H}_{m} \displaystyle:=\operatorname{span}\{M\in\mathbb{C}^{n\times n}:M\mathbf{1}=0,\mathbf{1}^{T}M=0\}, and P_{0},P_{r},P_{c},P_{m} are the corresponding orthogonal projections. Define P_{\parallel}:=P_{0}+P_{r}+P_{c} , so that P_{m}+P_{\parallel}=I . Let w=\operatorname{vec}(W)\in\mathbb{C}^{n^{2}} and a:=\frac{1}{n}\mathbf{1} , and write D_{1}(W):=a^{T}w,\quad D_{2}(W):=w^{T}Bw, where B:=-\frac{1}{n}P_{\parallel}+\frac{1}{n(n-1)}P_{m} . These two terms are exactly what one gets by Taylor expanding the log-permanent: explicitly, D_{1}(W)=(\log G_{W}(z))^{\prime}(0) and D_{2}(W)=(\log G_{W}(z))^{\prime\prime}(0) , where G_{W}(z)=\frac{1}{n!}\per(J+zW). Given these definitions, the second-order reweighted permanent is given by X_{W}^{(2)}(z):=\exp\left(-zD_{1}(W)-\frac{z^{2}}{2}D_{2}(W)\right)G_{W}(z). First moment. Note that by circular symmetry of the complex Gaussian law, \mathbb{E}X_{W}^{(2)}(z)=1 . Indeed, if X_{W}^{(2)}(z)=\sum_{k\geq 0}c_{k}(W)\,z^{k}, then each c_{k} is a homogeneous polynomial of degree k in the entries of W , so c_{k}(e^{i\theta}W)=e^{ik\theta}c_{k}(W) . Since e^{i\theta}W\stackrel{{\scriptstyle d}}{{=}}W for every \theta\in\mathbb{R} , we obtain \mathbb{E}[c_{k}(W)]=\mathbb{E}[c_{k}(e^{i\theta}W)]=e^{ik\theta}\mathbb{E}[c_{k}(W)]. Hence \mathbb{E}[c_{k}(W)]=0 for all k\geq 1 , while c_{0}(W)=1 . Therefore \mathbb{E}X_{W}^{(2)}(z)=1 . 5.1 Reweighted second moment analysis 5.1.1 Exact formulas In this section, we show how to give a nice formula for the reweighted second moment by reinterpreting it in terms of a “tilted” Gaussian distribution and applying Wick’s formula. Tilted expectation. Define the tilted expectation \widehat{\mathbb{E}}[f(W)]:=\frac{\mathbb{E}[e^{-2\operatorname{Re}(zD_{1})-\operatorname{Re}(z^{2}D_{2})}f(W)]}{\mathbb{E}[e^{-2\operatorname{Re}(zD_{1})-\operatorname{Re}(z^{2}D_{2})}]}. Also, for t,s\in\mathbb{C}^{n^{2}} , define M(t,s):=\mathbb{E}\exp\left(t^{T}w+s^{T}\overline{w}-\operatorname{Re}(z^{2}w^{T}Bw)\right). Proposition 12 . We have \mathbb{E}|X_{W}^{(2)}(z)|^{2}=M(-za,-\overline{z}a)\mathbb{E}_{\sigma,\tau\sim\mathsf{Unif}(S_{n})}\left[\widehat{\mathbb{E}}\left[\prod_{i=1}^{n}(1+zw_{e_{i}})(1+\overline{z}\overline{w_{f_{i}}})\right]\right] where e_{i}=(i,\sigma(i)) , f_{i}=(i,\tau(i)) . Proof. Note that \mathbb{E}|X_{W}^{(2)}(z)|^{2}=\frac{1}{(n!)^{2}}\sum_{\sigma,\tau\in S_{n}}T_{\sigma,\tau}(z)=\mathbb{E}_{\sigma,\tau\sim\mathsf{Unif}(S_{n})}[T_{\sigma,\tau}(z)], where \displaystyle T_{\sigma,\tau}(z) \displaystyle:=\mathbb{E}\left[\exp\left(-2\operatorname{Re}(za^{T}w)-\operatorname{Re}(z^{2}w^{T}Bw)\right)\prod_{i=1}^{n}(1+zw_{e_{i}})(1+\overline{z}\overline{w_{f_{i}}})\right] \displaystyle=M(-za,-\overline{z}a)\widehat{\mathbb{E}}\left[\prod_{i=1}^{n}(1+zw_{e_{i}})(1+\overline{z}\overline{w_{f_{i}}})\right]. ∎ Lemma 13 . Let S:=I-\nu^{2}|z|^{4}B^{2} , K:=BS^{-1} . If S\succ 0 , then M(t,s)=\det(S)^{-1/2}\exp\left(\nu t^{T}S^{-1}s-\frac{\nu^{2}}{2}\overline{z}^{2}t^{T}Kt-\frac{\nu^{2}}{2}z^{2}s^{T}Ks\right). Proof. Diagonalize B=U\Lambda U^{T} with real orthogonal U . Set g:=U^{T}w , t^{\prime}:=U^{T}t , s^{\prime}:=U^{T}s . Since w\sim\mathcal{N}_{\mathbb{C}}(0,\nu I) and U is orthogonal, g_{k} are independent \mathcal{N}_{\mathbb{C}}(0,\nu) . The integral factorizes into one-dimensional complex Gaussian integrals: M(t,s)=\prod_{k=1}^{N}I_{\lambda_{k}}(t_{k}^{\prime},s_{k}^{\prime}) with N=n^{2} and \displaystyle I_{\lambda}(t,s) \displaystyle:=\mathbb{E}\exp\left(tg+s\overline{g}-\frac{1}{2}z^{2}\lambda g^{2}-\frac{1}{2}\overline{z}^{2}\lambda\overline{g}^{2}\right) \displaystyle=\frac{1}{\sqrt{1-\nu^{2}|z|^{4}\lambda^{2}}}\exp\left(\frac{\nu ts}{1-\nu^{2}|z|^{4}\lambda^{2}}-\frac{\nu^{2}}{2}\frac{\overline{z}^{2}\lambda t^{2}}{1-\nu^{2}|z|^{4}\lambda^{2}}-\frac{\nu^{2}}{2}\frac{z^{2}\lambda s^{2}}{1-\nu^{2}|z|^{4}\lambda^{2}}\right). Then \sum_{k=1}^{N}\frac{\nu t_{k}^{\prime}s_{k}^{\prime}}{1-\nu^{2}|z|^{4}\lambda_{k}^{2}}=\nu t^{T}U(I-\nu^{2}|z|^{4}\Lambda^{2})^{-1}U^{T}s=\nu t^{T}S^{-1}s, \sum_{k=1}^{N}-\frac{\nu^{2}}{2}\frac{\overline{z}^{2}\lambda_{k}t_{k}^{2}}{1-\nu^{2}|z|^{4}\lambda_{k}^{2}}=-\frac{\nu^{2}}{2}\overline{z}^{2}t^{T}U\Lambda(I-\nu^{2}|z|^{4}\Lambda^{2})^{-1}U^{T}t=-\frac{\nu^{2}}{2}\overline{z}^{2}t^{T}Kt, \sum_{k=1}^{N}-\frac{\nu^{2}}{2}\frac{z^{2}\lambda_{k}s_{k}^{2}}{1-\nu^{2}|z|^{4}\lambda_{k}^{2}}=-\frac{\nu^{2}}{2}z^{2}s^{T}Ks, so multiplying over k yields the desired matrix form. ∎ Let \alpha:=\nu|z|^{2}/n be a parameter which will ultimately be required to be smaller than some absolute constant. Since S=(1-\alpha^{2})P_{\parallel}+\left(1-\frac{\alpha^{2}}{(n-1)^{2}}\right)P_{m} , we know that S\succ 0 provided we require \alpha<1 . Lemma 14 . Let \beta:=\alpha/(1-\alpha)\quad\text{and}\quad\kappa:=1-\beta=\frac{1-2\alpha}{1-\alpha}. (13) For \alpha<1/2 , we have M(-za,-\overline{z}a)=\det(S)^{-1/2}e^{n\beta} , \widehat{\mathbb{E}}[w]=-\frac{\overline{z}\nu}{1-\alpha}a,\quad\Gamma:=\widehat{\mathbb{E}}[(w-\widehat{\mathbb{E}}w)(\overline{w-\widehat{\mathbb{E}}w})^{T}]=\nu S^{-1},\quad\Delta:=\widehat{\mathbb{E}}[(w-\widehat{\mathbb{E}}w)(w-\widehat{\mathbb{E}}w)^{T}]=-\nu^{2}\overline{z}^{2}K. Consequently, with \eta:=w-\widehat{\mathbb{E}}w , for every coordinate e , 1+zw_{e}=\kappa+z\eta_{e},\quad 1+\overline{z}\overline{w_{e}}=\kappa+\overline{z}\overline{\eta_{e}}. Proof. We apply the previous lemma with (t,s)=(-za,-\overline{z}a) . Note that S^{-1}=\frac{1}{1-\alpha^{2}}P_{\parallel}+\frac{1}{1-\alpha^{2}/(n-1)^{2}}P_{m} from which it follows that S^{-1}a=(1-\alpha^{2})^{-1}a . Also, Ba=-\frac{1}{n}a and a^{T}a=1 , so we get M(-za,-\overline{z}a)=\det(S)^{-1/2}\exp\left(\frac{\nu|z|^{2}}{1-\alpha^{2}}+\frac{\nu^{2}|z|^{4}}{n(1-\alpha^{2})}\right)=\det(S)^{-1/2}e^{n\beta}. The mean and covariances are the first/second derivatives of \log M(t-za,s-\overline{z}a) at (0,0) . The identity for \kappa follows from z\widehat{\mathbb{E}}[w_{e}]=-\nu|z|^{2}/(n(1-\alpha))=-\beta . ∎ Fix (\sigma,\tau) and set X_{i}:=\eta_{e_{i}}\quad\text{and}\quad Y_{j}:=\overline{\eta_{f_{j}}}. Then under the tilted law, (X_{1},\ldots,X_{n},Y_{1},\ldots,Y_{n}) is centered Gaussian with covariances \widehat{\mathbb{E}}[X_{i}Y_{j}]=\Gamma_{e_{i},f_{j}},\quad\widehat{\mathbb{E}}[X_{i}X_{i^{\prime}}]=\Delta_{e_{i},e_{i^{\prime}}}\quad\widehat{\mathbb{E}}[Y_{j}Y_{j^{\prime}}]=\overline{\Delta_{f_{j},f_{j^{\prime}}}}. From Wick’s formula, we get the following. Lemma 15 . \widehat{\mathbb{E}}\left[\prod_{i=1}^{n}(\kappa+zX_{i})\prod_{j=1}^{n}(\kappa+\overline{z}Y_{j})\right]=\kappa^{2n}\sum_{M\in\mathcal{M}}\prod_{e\in M}w_{e}, where \mathcal{M} is the set of partial matchings on \{1_{t},\ldots,n_{t},1_{s},\ldots,n_{s}\} , and edge weights are w_{(i_{t},j_{s})}=\frac{|z|^{2}\Gamma_{e_{i},f_{j}}}{\kappa^{2}},\quad w_{(i_{t},i^{\prime}_{t})}=\frac{z^{2}\Delta_{e_{i},e_{i^{\prime}}}}{\kappa^{2}},\quad w_{(j_{s},j^{\prime}_{s})}=\frac{\overline{z}^{2}\overline{\Delta_{f_{j},f_{j^{\prime}}}}}{\kappa^{2}}. Here, i_{t} corresponds to the i th term in \prod_{i=1}^{n}(\kappa+zX_{i}) while j_{s} corresponds to the j th term in \prod_{j=1}^{n}(\kappa+\overline{z}Y_{j}) . Proof. Let V_{i_{t}}:=X_{i},\quad V_{j_{s}}:=Y_{j},\quad\xi_{i_{t}}:=\frac{z}{\kappa},\quad\xi_{j_{s}}:=\frac{\overline{z}}{\kappa}. Then \prod_{i=1}^{n}(\kappa+zX_{i})\prod_{j=1}^{n}(\kappa+\overline{z}Y_{j})=\kappa^{2n}\prod_{u\in U}(1+\xi_{u}V_{u}), where U=\{1_{t},\ldots,n_{t},1_{s},\ldots,n_{s}\} . Expanding, \widehat{\mathbb{E}}\left[\prod_{u\in U}(1+\xi_{u}V_{u})\right]=\sum_{A\subset U}\left(\prod_{u\in A}\xi_{u}\right)\widehat{\mathbb{E}}\left[\prod_{u\in A}V_{u}\right]. Since V is centered jointly Gaussian, Wick’s formula gives that the expectation vanishes for |A| odd, and for |A|=2m , \widehat{\mathbb{E}}\left[\prod_{u\in A}V_{u}\right]=\sum_{P\in\mathcal{P}(A)}\prod_{\{u,v\}\in P}\widehat{\mathbb{E}}[V_{u}V_{v}], with \mathcal{P}(A) the matchings/pairings of A . Summing over all A and pairings is equivalent to summing over all partial matchings M on U ; each unmatched vertex contributes 1, and each matched edge contributes \xi_{u}\xi_{v}\widehat{\mathbb{E}}[V_{u}V_{v}]. For (i_{t},j_{s}) this is \frac{|z|^{2}}{\kappa^{2}}\widehat{\mathbb{E}}[X_{i}Y_{j}]=\frac{|z|^{2}\Gamma_{e_{i},f_{j}}}{\kappa^{2}} ; similarly for (i_{t},i^{\prime}_{t}) and (j_{s},j_{s}^{\prime}) one gets the stated tt and ss weights. Hence \widehat{\mathbb{E}}\left[\prod_{i=1}^{n}(\kappa+zX_{i})\prod_{j=1}^{n}(\kappa+\overline{z}Y_{j})\right]=\kappa^{2n}\sum_{M\in\mathcal{M}}\prod_{e\in M}w_{e}, ∎ Remark 16 (Edge weights are real) . Since \Gamma=\nu S^{-1} and \Delta=-\nu^{2}\overline{z}^{\,2}K , with S^{-1} and K real symmetric matrices, all of these edge weights are in fact real. More explicitly, w_{(i_{t},j_{s})}=\frac{\nu|z|^{2}}{\kappa^{2}}(S^{-1})_{e_{i},f_{j}}\in\mathbb{R},\qquad w_{(i_{t},i^{\prime}_{t})}=w_{(j_{s},j^{\prime}_{s})}=-\frac{\nu^{2}|z|^{4}}{\kappa^{2}}K_{e_{i},e_{i^{\prime}}}\in\mathbb{R}. 5.1.2 Variance asymptotics From the above application of Wick’s formula, we have reduced the problem of computing the second moment to combinatorial sums over matchings. These sums are suitable for analysis via the cluster expansion and KP condition. Lemma 17 (cluster expansion for matching partition function) . Let G=(V,E) be a finite simple graph with complex activities w=(w_{e})_{e\in E} and matching partition function Z_{G}(w):=\sum_{M\text{ is a matching in }G}\prod_{e\in M}w_{e}. Define \delta:=\max_{v\in V}\sum_{e\ni v}|w_{e}|. If \delta\leq 1/(4e) , then Z_{G}(w)\neq 0 and the branch of \log Z_{G} with \log Z_{G}(0)=0 satisfies \left|\log Z_{G}(w)-\sum_{e\in E}w_{e}\right|\leq\frac{|V|}{4}\cdot\frac{(2e\delta)^{2}}{1-2e\delta}\leq 2e^{2}|V|\delta^{2}. Proof. A matching in G is exactly an independent set in the line graph L(G) (vertices of L(G) are edges of G , and adjacency means sharing an endpoint). In particular, we can rewrite Z_{G} as a multivariate independence polynomial Z_{G}(w)=Z_{L(G)}(\lambda),\quad\lambda_{e}:=w_{e}, where Z_{L(G)} is the multivariate independence polynomial. A standard consequence of the KP condition (explicitly, Theorem 3.3 in [ 49 ] ) gives that if for some b\geq 0 and every vertex v we have \sum_{u\in N_{L(G)}(v)\cup\{v\}}|\lambda_{u}|e^{1+b}\leq 1, then the cluster expansion for \log Z_{L(G)}(\lambda) converges absolutely and, in particular, Z_{L(G)}(\lambda)\neq 0 . For an edge e=xy\in E(G) (a vertex in L(G) ), its closed neighborhood in L(G) corresponds to edges of G incident to x or y . Hence \sum_{u\in N_{L(G)}(e)\cup\{e\}}|\lambda_{u}|\leq\sum_{f\ni x}|w_{f}|+\sum_{f\ni y}|w_{f}|\leq 2\delta. So the KP condition holds (with b=0 ) whenever 2\delta e\leq 1 , i.e. \delta\leq 1/(2e) . When this holds, Z_{G}(w)\neq 0 . Define Z(t):=Z_{G}(tw) . By the KP condition (with b=0 ) applied to tw , we have Z(t)\neq 0 for all |t|\leq 1/(2e\delta) . Z(t) is a polynomial of degree at most the maximum matching size, so \deg Z(t)\leq|V|/2 . Factor Z(t)=\prod_{j=1}^{N}(1-t/r_{j}) with N\leq|V|/2 . Zero-freeness on |t|\leq 1/(2e\delta) implies |r_{j}|\geq 1/(2e\delta) , i.e. |1/r_{j}|\leq 2e\delta=:\eta . Then \log Z(1)-\sum_{e\in E}w_{e}=\sum_{j=1}^{N}\left(\log\left(1-\frac{1}{r_{j}}\right)+\frac{1}{r_{j}}\right)=-\sum_{j=1}^{N}\sum_{k\geq 2}\frac{1}{kr_{j}^{k}}. Taking absolute values and using \sum_{k\geq 2}\eta^{k}/k\leq\eta^{2}/(2(1-\eta)) gives \left|\log Z_{G}(w)-\sum_{e\in E}w_{e}\right|\leq N\cdot\frac{\eta^{2}}{2(1-\eta)}\leq\frac{|V|}{2}\cdot\frac{(2e\delta)^{2}}{2(1-2e\delta)}=\frac{|V|}{4}\cdot\frac{(2e\delta)^{2}}{1-2e\delta}. Under the assumption that \delta\leq 1/(4e) , this is bounded above by 2e^{2}|V|\delta^{2} . ∎ Write F(\sigma,\tau):=\{i\in[n]:\sigma(i)=\tau(i)\} , and let m:=|F(\sigma,\tau)| . For i\in F(\sigma,\tau) , e_{i}=f_{i} , and the diagonal ts -edge weight is w_{\text{diag}}:=\frac{|z|^{2}\Gamma_{e,e}}{\kappa^{2}}. Note that this is independent of e , and positive provided that \alpha<1 , because \Gamma_{e,e}=\nu(S^{-1})_{ee} and S is positive definite. Lemma 18 . Fix (\sigma,\tau) and define Z_{\sigma,\tau}:=\sum_{M\in\mathcal{M}}\prod_{e\in M}w_{e}. Then Z_{\sigma,\tau}=\sum_{S\subset F(\sigma,\tau)}w_{\mathrm{diag}}^{|S|}Z_{\sigma,\tau}^{(S)} where Z_{\sigma,\tau}^{(S)} is the matching partition function on the reduced graph obtained by starting from the complete graph on \{1_{t},\ldots,n_{t},1_{s},\ldots,n_{s}\} then deleting \{i_{t},i_{s}:i\in S\} and deleting the remaining edges \{(i_{t},i_{s}):i\in F(\sigma,\tau)\backslash S\} . Proof. The diagonal edges (i_{t},i_{s}) for i\in F(\sigma,\tau) are pairwise disjoint. Partition matchings by S(M):=\{i\in F(\sigma,\tau):(i_{t},i_{s})\in M\}. If S(M)=S , then the matching contributes w_{\mathrm{diag}}^{|S|} from these chosen edges, and the remaining edges form a matching on the stated reduced graph. Summing over all such matchings gives Z_{\sigma,\tau}^{(S)} . ∎ Lemma 19 (Reduced-graph bound) . Assume \alpha\leq 1/4 and write \lambda:=\frac{1}{1-\alpha^{2}},\quad\mu:=\frac{1}{1-\alpha^{2}/(n-1)^{2}},\quad K:=BS^{-1}. Define u:=\frac{\nu^{2}|z|^{4}}{\kappa^{2}}\left(\frac{\lambda}{n^{3}}+\frac{\mu}{n^{3}(n-1)}\right). Then the total sum of the weights of all internal tt edges and internal ss edges in the unreduced graph is given by \Sigma_{tt+ss}(n)=-n(n-1)u=-\frac{\alpha^{2}}{\kappa^{2}}\left((n-1)\lambda+\mu\right). Moreover, for every (\sigma,\tau) and S\subset F(\sigma,\tau) , \delta_{(S)}:=\max_{v\in V^{(S)}}\sum_{e\in E^{(S)}:e\ni v}|w_{e}|\leq C\alpha^{2}, \sum_{e\in E^{(S)}}w_{e}\leq\Sigma_{tt+ss}(n)+C\alpha^{2}|S|+C\alpha^{3}n, where (V^{(S)},E^{(S)}) is the reduced graph from the previous lemma. Proof. Step 1: exact formula for \Sigma_{tt+ss}(n) . For i\neq j , permutation edges e_{i},e_{j} have distinct row and distinct column, hence (P_{\parallel})_{e_{i},e_{j}}=-\frac{1}{n^{2}},\quad(P_{m})_{e_{i},e_{j}}=+\frac{1}{n^{2}}. Since K=\Big(-\frac{\lambda}{n}\Big)P_{\parallel}+\Big(\frac{\mu}{n(n-1)}\Big)P_{m}, we get K_{e_{i},e_{j}}=\frac{\lambda}{n^{3}}+\frac{\mu}{n^{3}(n-1)}. Substituting this into w_{(i_{t},j_{t})}=\frac{z^{2}\Delta_{e_{i},e_{j}}}{\kappa^{2}} shows that every off-diagonal tt edge has the same weight -u . Similarly, every off-diagonal ss edge has weight -u . Therefore \Sigma_{tt+ss}(n)=\binom{n}{2}(-u)+\binom{n}{2}(-u)=-n(n-1)u. Now use \alpha=\nu|z|^{2}/n : n(n-1)u=n(n-1)\frac{\nu^{2}|z|^{4}}{\kappa^{2}}\left(\frac{\lambda}{n^{3}}+\frac{\mu}{n^{3}(n-1)}\right)=\frac{\alpha^{2}}{\kappa^{2}}\big((n-1)\lambda+\mu\big). Hence \Sigma_{tt+ss}(n)=-\frac{\alpha^{2}}{\kappa^{2}}\big((n-1)\lambda+\mu\big). Step 2: bound \delta_{(S)} . Let G^{\ast} be the graph before deleting vertices in S , but after deleting all diagonal edges (i_{t},i_{s}) for i\in F(\sigma,\tau) . Deleting vertices/edges can only decrease incident absolute mass, so it is enough to bound the weighted degree in G^{\ast} . Take a vertex i_{t} . For j\neq i , |K_{e_{i},e_{j}}|=\frac{\lambda}{n^{3}}+\frac{\mu}{n^{3}(n-1)}\leq\frac{4}{n^{3}} (using \lambda,\mu\leq 2 for \alpha\leq 1/4 ). Thus \sum_{j\neq i}|w_{(i_{t},j_{t})}|\leq(n-1)\frac{\nu^{2}|z|^{4}}{\kappa^{2}}\frac{4}{n^{3}}=\frac{4\alpha^{2}}{\kappa^{2}}\frac{n-1}{n}\leq 16\alpha^{2} (since \kappa\geq 1/2 ). On remaining ts edges we have e_{i}\neq f_{j} , so (S^{-1})_{e_{i},f_{j}}=(\lambda-\mu)(P_{\parallel})_{e_{i},f_{j}} because S^{-1}=\mu I+(\lambda-\mu)P_{\parallel} and off-diagonal entries of I vanish. Hence \sum_{j:(i_{t},j_{s})\in E^{\ast}}|w_{(i_{t},j_{s})}|\leq\frac{\nu|z|^{2}}{\kappa^{2}}|\lambda-\mu|\sum_{j}|(P_{\parallel})_{e_{i},f_{j}}|. For fixed i , (P_{\parallel})_{(r,c),(r^{\prime},c^{\prime})}=\frac{1}{n}\mathbf{1}_{r=r^{\prime}}+\frac{1}{n}\mathbf{1}_{c=c^{\prime}}-\frac{1}{n^{2}}, so at most two j are “special” (same row and/or same column), and one gets \sum_{j}|(P_{\parallel})_{e_{i},f_{j}}|\leq\frac{3}{n}. Also |\lambda-\mu|\leq C\alpha^{2} for \alpha\leq 1/4 . Therefore \sum_{j:(i_{t},j_{s})\in E^{\ast}}|w_{(i_{t},j_{s})}|\leq\frac{\alpha n}{\kappa^{2}}\cdot(2\alpha^{2})\cdot\frac{3}{n}\leq 24\alpha^{3}. It follows that \sum_{e\ni i_{t}}|w_{e}|\leq 16\alpha^{2}+24\alpha^{3}\leq 40\alpha^{2}. By symmetry the same bound holds for every i_{s} . Hence for every reduced graph, \delta_{(S)}\leq 40\alpha^{2}. Step 3: bound the linear sum \sum_{e\in E^{(S)}}w_{e} . Let s:=|S| . Decompose: \sum_{e\in E^{(S)}}w_{e}=\Sigma_{tt+ss}^{(S)}+\Sigma_{ts}^{(S)}. There are n-s t -vertices and n-s s -vertices left, so \Sigma_{tt+ss}^{(S)}=-2\binom{n-s}{2}u=-(n-s)(n-s-1)u. Thus \Sigma_{tt+ss}^{(S)}-\Sigma_{tt+ss}(n)=u\big[n(n-1)-(n-s)(n-s-1)\big]=us(2n-s-1) . Since u\leq C\alpha^{2}/n , we get \Sigma_{tt+ss}^{(S)}\leq\Sigma_{tt+ss}(n)+C\alpha^{2}s. For the ts part, we have \Sigma_{ts}^{(S)}\leq|\Sigma_{ts}^{(S)}|\leq\frac{\nu|z|^{2}}{\kappa^{2}}|\lambda-\mu|\sum_{(i,j)\in I_{S}}|(P_{\parallel})_{e_{i},f_{j}}|, where I_{S} is the set of remaining allowed ts pairs. Removing vertices/edges only decreases the sum, so \sum_{(i,j)\in I_{S}}|(P_{\parallel})_{e_{i},f_{j}}|\leq\sum_{i=1}^{n}\sum_{j=1}^{n}|(P_{\parallel})_{e_{i},f_{j}}|\leq n\cdot\frac{3}{n}=3. Hence |\Sigma_{ts}^{(S)}|\leq\frac{\alpha n}{\kappa^{2}}\cdot(2\alpha^{2})\cdot 3\leq C\alpha^{3} . Therefore \sum_{e\in E^{(S)}}w_{e}=\Sigma_{tt+ss}^{(S)}+\Sigma_{ts}^{(S)}\leq\Sigma_{tt+ss}(n)+C\alpha^{2}|S|+C\alpha^{3}n. This proves the lemma. ∎ Lemma 20 . There exist absolute c_{0},C>0 such that if \alpha\leq c_{0} , then \log\mathbb{E}_{\sigma,\tau}[Z_{\sigma,\tau}]\leq\Sigma_{tt+ss}(n)+w_{\mathrm{diag}}+C\alpha^{3}n. Proof. Fix (\sigma,\tau) and S\subset F(\sigma,\tau) . By Lemma 19 , \delta_{(S)}\leq C\alpha^{2} . For \alpha\leq c_{0} small, \delta_{(S)}\leq 1/(4e) , so Lemma 17 applies to Z_{\sigma,\tau}^{(S)} . Then 3 3 3 The following inequalities are between real-valued quantities, since the weights in the partition function are real. The cluster expansion with the KP condition ensures Z_{\sigma,\tau}^{(S)}>0 . \log Z_{\sigma,\tau}^{(S)}\leq\sum_{e\in E^{(S)}}w_{e}+Cn\delta_{(S)}^{2}\leq\sum_{e\in E^{(S)}}w_{e}+Cn\alpha^{4}. Using Lemma 19 , \log Z_{\sigma,\tau}^{(S)}\leq\Sigma_{tt+ss}(n)+C\alpha^{2}|S|+C\alpha^{3}n. Exponentiating and summing via Lemma 18 gives \displaystyle Z_{\sigma,\tau} \displaystyle\leq\exp\left(\Sigma_{tt+ss}(n)+C\alpha^{3}n\right)\sum_{S\subset F(\sigma,\tau)}(w_{\mathrm{diag}}e^{C\alpha^{2}})^{|S|} \displaystyle=\exp\left(\Sigma_{tt+ss}(n)+C\alpha^{3}n\right)(1+w_{\mathrm{diag}}e^{C\alpha^{2}})^{m}. Using m=\operatorname{fix}(\tau^{-1}\sigma) and averaging in (\sigma,\tau) , we get by Lemma 7 that \mathbb{E}_{\sigma,\tau}(1+w_{\mathrm{diag}}e^{C\alpha^{2}})^{m}\leq\exp(w_{\mathrm{diag}}e^{C\alpha^{2}}). Hence \log\mathbb{E}_{\sigma,\tau}[Z_{\sigma,\tau}]\leq\Sigma_{tt+ss}(n)+w_{\mathrm{diag}}e^{C\alpha^{2}}+C\alpha^{3}n. Because w_{\mathrm{diag}}\leq C\alpha n and e^{C\alpha^{2}}=1+O(\alpha^{2}) , w_{\mathrm{diag}}e^{C\alpha^{2}}=w_{\mathrm{diag}}+O(\alpha^{2}w_{\mathrm{diag}})=w_{\mathrm{diag}}+O(\alpha^{3}n). The conclusion then follows. ∎ Theorem 21 . There exist absolute constants c,C>0 such that if \alpha:=\nu|z|^{2}/n\leq c , then \log\mathbb{E}|X_{W}^{(2)}(z)|^{2}\leq C\frac{\nu^{3}|z|^{6}}{n^{2}}. Proof. We have \mathbb{E}|X_{W}^{(2)}(z)|^{2}=M(-za,-\overline{z}a)\kappa^{2n}\mathbb{E}_{\sigma,\tau}[Z_{\sigma,\tau}] , so \log\mathbb{E}|X_{W}^{(2)}(z)|^{2}\leq-\frac{1}{2}\log\det(S)+(n\beta+2n\log\kappa+w_{\mathrm{diag}})+\Sigma_{tt+ss}(n)+C\alpha^{3}n. We can now show how terms at order \alpha^{2}n cancel out, giving the desired O(\alpha^{3}n) bound. Using \det(S)=(1-\alpha^{2})^{2n-1}\left(1-\frac{\alpha^{2}}{(n-1)^{2}}\right)^{(n-1)^{2}}, one gets -\frac{1}{2}\log\det(S)=\alpha^{2}n+O(\alpha^{4}n) . By Lemma 19 , \Sigma_{tt+ss}(n)=-\frac{\alpha^{2}}{\kappa^{2}}((n-1)\lambda+\mu). Since \lambda=1+O(\alpha^{2}) , \mu=1+O(\alpha^{2}/(n-1)^{2}) , and 1/\kappa^{2}=1+2\alpha+O(\alpha^{2}) , we find that \Sigma_{tt+ss}(n)=-\alpha^{2}n+O(\alpha^{3}n) . Hence by cancellation we obtain -\frac{1}{2}\log\det(S)+\Sigma_{tt+ss}(n)=O(\alpha^{3}n). Also, for any coordinate e , \Gamma_{e,e}=\nu\left(\mu+(\lambda-\mu)\left(\frac{2}{n}-\frac{1}{n^{2}}\right)\right)=\nu(1+O(\alpha^{2}/n)), so w_{\mathrm{diag}}=\frac{|z|^{2}\Gamma_{e,e}}{\kappa^{2}}=\frac{\alpha n}{\kappa^{2}}+O(\alpha^{3}). Recalling the definition of \beta and \kappa from ( 13 ), we let \psi(\alpha):=\frac{\alpha}{1-\alpha}+2\log\frac{1-2\alpha}{1-\alpha}+\frac{\alpha}{\left(\frac{1-2\alpha}{1-\alpha}\right)^{2}}. and observe that n\beta+2n\log\kappa+\frac{\alpha n}{\kappa^{2}}=n\psi(\alpha)=O(\alpha^{3}n) because, by explicit Taylor series expansion, \psi(\alpha)=\frac{4}{3}\alpha^{3}+O(\alpha^{4}) near 0. Thus, \log\mathbb{E}|X_{W}^{(2)}(z)|^{2}=O(\alpha^{3}n). ∎ 5.2 Zero-free region and other applications Corollary 22 . Fix \beta\in(0,1/3) and set R_{n}:=\frac{n^{1/3-\beta}}{\sqrt{\nu}}. Then for every fixed \varepsilon\in(0,1) and all sufficiently large n , \mathbb{P}[G_{W}\text{ has a zero in }\mathbb{D}(0,(1-\varepsilon)R_{n})]=O_{\varepsilon}(n^{-6\beta}). On this event, for every \rho\in\mathbb{C} with |\rho|^{-1}<(1-\varepsilon)R_{n} , Barvinok interpolation outputs a deterministic e^{\pm\eta} -multiplicative approximation to \per(\rho J+W) in time n^{O(m)} , where m=O\left(\frac{1}{\varepsilon}\log\left(\frac{n}{\eta\varepsilon}\right)\right). That is, the mean-shift scale improves to |\rho|\geq(1-\varepsilon)^{-1}\sqrt{\nu}n^{-1/3+\beta} . Proof. Plugging in z=Re^{i\theta} and averaging over \theta , the previous theorem gives \mathbb{E}_{\theta}\log\mathbb{E}|X_{W}^{(2)}(Re^{i\theta})|^{2}\leq C\frac{\nu^{3}R^{6}}{n^{2}}. So the expected number of zeros can be bounded by Jensen’s formula ( 6 ), using that \mathbb{E}_{\theta}\mathbb{E}\log|X_{W}^{(2)}(Re^{i\theta})|^{2}\leq\mathbb{E}_{\theta}\log\mathbb{E}|X_{W}^{(2)}(Re^{i\theta})|^{2} by Jensen’s inequality. Finally, the high-probability statement follows from Markov’s inequality. ∎ 5.2.1 Second-order expansion From the above analysis, we directly have a simple approximate formula for the log-permanent in the regime |z|\ll n^{1/3} . This formula is somewhat analogous to the TAP approximation in spin glass theory [ 63 , 3 ] , which was also originally derived from diagrammatic expansions. Corollary 23 (Second-order log-permanent expansion) . Let W be as defined above, and suppose z\in\mathbb{C} depends on n such that \nu^{3}|z|^{6}/n^{2}\to 0 as n\to\infty . Then X_{W}^{(2)}(z) converges in probability to 1 : X_{W}^{(2)}(z)\xrightarrow{\mathbb{P}}1. Consequently, the log-permanent admits the asymptotic expansion \log\per(J+zW)=\log(n!)+zD_{1}(W)+\frac{z^{2}}{2}D_{2}(W)+O_{\mathbb{P}}\left(\frac{\nu^{3/2}|z|^{3}}{n}\right), where the implicit constant in the O_{\mathbb{P}} term depends only on the absolute constants from the second moment bound. Proof. By construction, \mathbb{E}[X_{W}^{(2)}(z)]=1 . The preceding theorem establishes that \log\mathbb{E}\big|X_{W}^{(2)}(z)\big|^{2}\leq C\frac{\nu^{3}|z|^{6}}{n^{2}} for some absolute constant C>0 . Since \nu^{3}|z|^{6}/n^{2}=o(1) by assumption, we can exponentiate this bound to find the variance: \operatorname{Var}\big(X_{W}^{(2)}(z)\big)=\mathbb{E}\big|X_{W}^{(2)}(z)\big|^{2}-\big|\mathbb{E}[X_{W}^{(2)}(z)]\big|^{2}\leq\exp\left(C\frac{\nu^{3}|z|^{6}}{n^{2}}\right)-1=O\left(\frac{\nu^{3}|z|^{6}}{n^{2}}\right). Because the variance vanishes as n\to\infty , Chebyshev’s inequality immediately yields X_{W}^{(2)}(z)\xrightarrow{\mathbb{P}}1 . More precisely, it gives the fluctuation bound X_{W}^{(2)}(z)=1+O_{\mathbb{P}}\left(\frac{\nu^{3/2}|z|^{3}}{n}\right). Expanding the definition of X_{W}^{(2)}(z) , we have X_{W}^{(2)}(z)=\exp\left(-zD_{1}(W)-\frac{z^{2}}{2}D_{2}(W)\right)G_{W}(z), where G_{W}(z)=\frac{1}{n!}\per(J+zW) . Taking the principal branch of the logarithm on both sides (which is well-defined with probability approaching 1 since X_{W}^{(2)}(z)\xrightarrow{\mathbb{P}}1 ), and using the Taylor expansion \log(1+x)=x+O(x^{2}) for small x , we obtain \log X_{W}^{(2)}(z)=O_{\mathbb{P}}\left(\frac{\nu^{3/2}|z|^{3}}{n}\right). Substituting the definition of X_{W}^{(2)}(z) into the logarithm yields \log G_{W}(z)-zD_{1}(W)-\frac{z^{2}}{2}D_{2}(W)=O_{\mathbb{P}}\left(\frac{\nu^{3/2}|z|^{3}}{n}\right). Rearranging and replacing \log G_{W}(z) with \log\per(J+zW)-\log(n!) completes the proof. ∎ Corollary 24 (Central limit theorem) . Provided that z_{n}=o(n^{1/3}) , we have the following convergence in distribution as n\to\infty : \frac{\log\per(J+z_{n}W)-\log(n!)}{z_{n}}\xrightarrow{d}\mathcal{N}_{\mathbb{C}}(0,\nu). Proof. By Corollary 23 , we have the asymptotic expansion \log\per(J+z_{n}W)-\log(n!)=z_{n}D_{1}(W)+\frac{z_{n}^{2}}{2}D_{2}(W)+O_{\mathbb{P}}\left(\frac{|z_{n}|^{3}}{n}\right). Dividing by z_{n} , we obtain \frac{\log\per(J+z_{n}W)-\log(n!)}{z_{n}}=D_{1}(W)+\frac{z_{n}}{2}D_{2}(W)+O_{\mathbb{P}}\left(\frac{|z_{n}|^{2}}{n}\right). By definition, D_{1}(W)=\frac{1}{n}\sum_{i,j}W_{ij} . Because the entries W_{ij} are i.i.d. circularly symmetric \mathcal{N}_{\mathbb{C}}(0,\nu) variables, their scaled sum satisfies D_{1}(W)\sim\mathcal{N}_{\mathbb{C}}(0,\nu) for all n . For the second-order term, D_{2}(W)=w^{T}Bw is a holomorphic quadratic form. Since W is circularly symmetric, \mathbb{E}[W_{ij}^{2}]=0 , giving \mathbb{E}[D_{2}(W)]=0 . Its variance is given by \nu^{2}\operatorname{Tr}(B^{2})=4\nu^{2}/n , meaning D_{2}(W)=O_{\mathbb{P}}(n^{-1/2}) . Therefore, for z_{n}=o(n^{1/3}) , the relative contribution of the second-order term is \frac{z_{n}}{2}D_{2}(W)=O_{\mathbb{P}}(|z_{n}|n^{-1/2})=o_{\mathbb{P}}(n^{-1/6})=o_{\mathbb{P}}(1). Similarly, the remainder term is O_{\mathbb{P}}\left(\frac{|z_{n}|^{2}}{n}\right)=o_{\mathbb{P}}(n^{-1/3})=o_{\mathbb{P}}(1). Since all higher-order terms vanish in probability, the asymptotic distribution is purely determined by the leading term D_{1}(W)\sim\mathcal{N}_{\mathbb{C}}(0,\nu) . ∎ 5.2.2 Approximation algorithm Proposition 25 (Coefficient bound, Proposition 56 of Appendix C ) . Let P_{n}(z):=\frac{1}{n!}\per(J+zW),\qquad\log P_{n}(z)=\sum_{k\geq 1}b_{k,n}z^{k}, where W=(W_{ij})_{1\leq i,j\leq n} has i.i.d. standard complex Gaussian entries, W_{ij}\sim\mathcal{N}_{\mathbb{C}}(0,1) . Then there exists an absolute constant C>0 such that for every integer k\geq 1 , letting C_{k}=\exp\!\bigl(C\,k\,2^{k}\log k\bigr) we have that \mathbb{E}|b_{k,n}|^{2}\leq C_{k}\,n^{1-k}\qquad\text{for all }n\geq 1. Lemma 26 (Quantitative fixed-degree truncation for d\geq 2 ) . Let P_{n}(z):=\frac{1}{n!}\per(J+zW),\qquad\log P_{n}(z)=\sum_{k\geq 1}b_{k,n}z^{k}, where W\in\mathbb{C}^{n\times n} has i.i.d. entries W_{ij}\sim\mathcal{N}_{\mathbb{C}}(0,1) . Fix d\geq 2 and \beta\in(0,1/3) , and set L_{n}:=n^{1/3-\beta} . Let M be any fixed integer such that M>\max\!\left\{d,\frac{2}{\beta}-1\right\}. Then there exists a constant A_{\beta}>0 such that for all sufficiently large n and all t>0 , \mathbb{P}\!\left[\sup_{|z|\leq L_{n}}\left|\log P_{n}(z)-\sum_{k=1}^{d}b_{k,n}z^{k}\right|>t+\frac{n(2n^{-\beta/2})^{M+1}}{(M+1)(1-2n^{-\beta/2})}\right] \leq A_{\beta}n^{-3\beta}+\frac{M-d}{t^{2}}\sum_{k=d+1}^{M}C_{k}\,n^{\,1-k/3-2\beta k}, where C_{k}=\exp\!\bigl(C\,k\,2^{k}\log k\bigr) are the constants from Proposition 56 . Proof. Set T_{d,n}(z):=\sum_{k=1}^{d}b_{k,n}z^{k}. Apply the zero-free corollary with \beta/2 in place of \beta and \varepsilon=1/2 . Then there exists a constant A_{\beta}>0 such that, for all sufficiently large n , \mathbb{P}(E_{n}^{c})\leq A_{\beta}n^{-3\beta} , where E_{n} denotes the event that P_{n} has no zeros in \mathbb{D}(0,r_{n}) with r_{n}:=\frac{1}{2}\,n^{1/3-\beta/2} . On E_{n} , we may factor P_{n}(z)=\prod_{j=1}^{n}\left(1-\frac{z}{\rho_{j}}\right),\qquad|\rho_{j}|\geq r_{n}, and hence for |z|\frac{2}{\beta}-1 , we have n\rho_{n}^{M+1}=2^{M+1}n^{\,1-\frac{\beta}{2}(M+1)}\to 0. It follows that, on E_{n} , uniformly for |z|\leq L_{n} , \displaystyle\left|\sum_{k>M}b_{k,n}z^{k}\right| \displaystyle\leq\sum_{k>M}\frac{n}{k}\left(\frac{|z|}{r_{n}}\right)^{k} \displaystyle\leq\sum_{k>M}\frac{n}{k}\rho_{n}^{k}\leq\frac{n\,\rho_{n}^{M+1}}{(M+1)(1-\rho_{n})}=\frac{n(2n^{-\beta/2})^{M+1}}{(M+1)(1-2n^{-\beta/2})}. Thus it remains to control the finite block \sum_{k=d+1}^{M}b_{k,n}z^{k}. By the triangle inequality, \sup_{|z|\leq L_{n}}\left|\sum_{k=d+1}^{M}b_{k,n}z^{k}\right|\leq\sum_{k=d+1}^{M}|b_{k,n}|\,L_{n}^{k}. Hence, by Cauchy–Schwarz and Markov’s inequality, \displaystyle\mathbb{P}\!\left[\sup_{|z|\leq L_{n}}\left|\sum_{k=d+1}^{M}b_{k,n}z^{k}\right|>t\right] \displaystyle\qquad\leq\frac{1}{t^{2}}\mathbb{E}\!\left(\sum_{k=d+1}^{M}|b_{k,n}|L_{n}^{k}\right)^{2}\leq\frac{M-d}{t^{2}}\sum_{k=d+1}^{M}\mathbb{E}|b_{k,n}|^{2}\,L_{n}^{2k}. By Proposition 56 , \mathbb{E}|b_{k,n}|^{2}\leq C_{k}n^{1-k} , where C_{k}=\exp\!\bigl(C\,k\,2^{k}\log k\bigr) . Since L_{n}=n^{1/3-\beta} , we obtain \mathbb{E}|b_{k,n}|^{2}\,L_{n}^{2k}\leq C_{k}n^{1-k}n^{2k/3-2\beta k}=C_{k}\,n^{\,1-k/3-2\beta k}. Therefore \mathbb{P}\!\left[\sup_{|z|\leq L_{n}}\left|\sum_{k=d+1}^{M}b_{k,n}z^{k}\right|>t\right]\leq\frac{M-d}{t^{2}}\sum_{k=d+1}^{M}C_{k}\,n^{\,1-k/3-2\beta k}. Combining this with the deterministic tail bound on E_{n} , and then adding the probability of E_{n}^{c} , yields \mathbb{P}\!\left[\sup_{|z|\leq L_{n}}\left|\log P_{n}(z)-\sum_{k=1}^{d}b_{k,n}z^{k}\right|>t+\frac{n(2n^{-\beta/2})^{M+1}}{(M+1)(1-2n^{-\beta/2})}\right] \leq A_{\beta}n^{-3\beta}+\frac{M-d}{t^{2}}\sum_{k=d+1}^{M}C_{k}\,n^{\,1-k/3-2\beta k}, which proves the lemma. ∎ Theorem 27 (Degree–accuracy tradeoff for the truncated log expansion) . Let P_{n}(z):=\frac{1}{n!}\per(J+zW),\qquad\log P_{n}(z)=\sum_{k\geq 1}b_{k,n}z^{k}, where W\in\mathbb{C}^{n\times n} has i.i.d. entries W_{ij}\sim\mathcal{N}_{\mathbb{C}}(0,1) . Fix \beta\in(0,1/3) . For each integer d\geq 2 , define \Gamma_{d,\beta}:=\frac{d+1}{6}+\beta(d+1)-\frac{1}{2}. Then for every d\geq 2 , every \gamma<\Gamma_{d,\beta} , and every \delta\in(0,1) , there exists N=N(\beta,d,\gamma,\delta) such that for all n\geq N , with probability at least 1-\delta , the branch of \log P_{n} determined by \log P_{n}(0)=0 is well-defined on \mathbb{D}\!\bigl(0,n^{1/3-\beta}\bigr) , and satisfies \sup_{|z|\leq n^{1/3-\beta}}\left|\log P_{n}(z)-\sum_{k=1}^{d}b_{k,n}z^{k}\right|\leq n^{-\gamma}. In particular, to obtain an additive n^{-\gamma} -approximation to \log P_{n}(z) uniformly for |z|\leq n^{1/3-\beta} , taking d=\lceil 6\gamma+3\rceil , the corresponding degree- d truncation gives the desired additive approximation in time n^{O(\gamma)} . Proof. Apply Lemma 26 . Choose M sufficiently large so that the deterministic tail term in that lemma is O(n^{-\gamma}) . Since \gamma<\Gamma_{d,\beta} , the probabilistic contribution coming from the block k=d+1,\dots,M is also o(1) when evaluated at threshold t=n^{-\gamma}/2 . Hence, after increasing N if necessary, the lemma implies that with probability at least 1-\delta , \sup_{|z|\leq n^{1/3-\beta}}\left|\log P_{n}(z)-\sum_{k=1}^{d}b_{k,n}z^{k}\right|\leq n^{-\gamma}. This proves the approximation statement. The runtime claim is immediate from the fact that b_{1,n},\dots,b_{d,n} are recovered from the first d coefficients of P_{n} , and these can be computed exactly in time n^{O(d)} by summing permanents of k\times k submatrices for k\leq d . ∎ 5.3 Second-order monomer-dimer analysis Hardcore model on the line graph of K_{n,n} . Let G=(V,E) be a finite graph. Recall that the hardcore partition function on G with vertex fugacities x=(x_{v})_{v\in V}\in\mathbb{C}^{V} is Z_{G}(x):=\sum_{I\in\mathcal{I}(G)}\prod_{v\in I}x_{v}, where \mathcal{I}(G) denotes the collection of independent sets of G . In the present section we take G_{n}:=L(K_{n,n}), the line graph of the complete bipartite graph K_{n,n} . In other words, we consider the monomer-dimer model on K_{n,n} . We identify the vertex set of G_{n} with the edge set of K_{n,n} , namely V(G_{n})=[n]\times[n], and two vertices (i,j) and (i^{\prime},j^{\prime}) are adjacent in G_{n} iff they share a row or a column: (i,j)\sim(i^{\prime},j^{\prime})\qquad\Longleftrightarrow\qquad i=i^{\prime}\text{ or }j=j^{\prime}. Under this identification, independent sets in G_{n} are exactly matchings in K_{n,n} . Therefore the hardcore partition function on G_{n} is precisely the matching generating polynomial of K_{n,n} : Z_{G_{n}}(x)=\sum_{M\ \mathrm{matching\ in}\ K_{n,n}}\prod_{e\in M}x_{e}. We study this partition function under random complex fugacities x=zW , where W=(W_{ij})_{1\leq i,j\leq n} has i.i.d. entries W_{ij}\sim\mathcal{N}_{\mathbb{C}}(0,1) , together with its second-order reweighting F_{n}^{(2)}(x):=Z_{G_{n}}(x)\exp\!\bigl(-L_{1}(x)-L_{2}(x)\bigr). Theorem 28 (Second-order bound on L(K_{n,n}) , Theorem 61 ) . There exist absolute constants c,C>0 such that the following holds. Let G_{n}:=L(K_{n,n}),\qquad F_{n}^{(2)}(x):=Z_{G_{n}}(x)\exp\!\bigl(-L_{1}(x)-L_{2}(x)\bigr), where L_{1}(x):=\sum_{(i,j)\in[n]\times[n]}x_{ij},\qquad L_{2}(x):=-\frac{1}{2}\sum_{(i,j)}x_{ij}^{2}-\sum_{(i,j)\sim(i^{\prime},j^{\prime})}x_{ij}x_{i^{\prime}j^{\prime}}. Let W=(W_{ij}) have i.i.d. entries W_{ij}\sim\mathcal{N}_{\mathbb{C}}(0,1) , and define X_{n}^{(2)}(z):=F_{n}^{(2)}(zW). If n|z|^{2}\leq c , then \log\mathbb{E}\bigl[|X_{n}^{(2)}(z)|^{2}\bigr]\leq C\,n^{4}\,|z|^{6}. We defer the proof of this result to Appendix D . From this result the zero-free region follows by the same application of Jensen’s formula. It is also straightforward to derive analogous corollaries in terms of algorithmic guarantees, etc. as in the permanent case — we omit the details. 6 Universality of first-order zero-free region In this section, we show how to prove a zero-free bound for random matrices with general sub-exponential entries. This requires a new argument, because some of the approximations for the log-permanent obtained earlier are not universal — see the discussion in Section 6.4 . Setup. Let W be an n\times n complex random matrix with i.i.d. entries such that \mathbb{E}[W_{ij}]=0 , \mathbb{E}|W_{ij}|^{2}=\nu , and we have the sub-exponential condition \sup_{\phi\in[0,2\pi)}\|\operatorname{Re}(e^{-i\phi}W_{ij})\|_{\psi_{1}}\leq K\sqrt{\nu}. In particular, this covers complex Gaussians and all real sub-exponential distributions. Let S_{W}:=\frac{1}{n}\sum_{i,j}W_{ij} and define G_{W}(z):=\frac{1}{n!}\per(J+zW),\quad X_{W}(z):=e^{-zS_{W}}G_{W}(z). Notice that the zeros of G_{W} and X_{W} coincide. Define M(u):=\mathbb{E}[e^{uW_{ij}+\overline{u}\overline{W_{ij}}}] and consider the tilted expectation \mathbb{E}_{u}[F(W)]:=\frac{\mathbb{E}[F(W)e^{uW_{ij}+\overline{u}\overline{W_{ij}}}]}{M(u)}. Then set \mu(u):=\mathbb{E}_{u}[W],\quad\sigma^{2}(u):=\mathbb{E}_{u}[|W-\mu(u)|^{2}]. Note that \mu(u)=\partial_{u}\Psi(u) and \sigma^{2}(u)=\partial_{u}\partial_{\overline{u}}\Psi(u) where \Psi(u)=\log M(u) . 6.1 Exact formulas Proposition 29 . It holds that \mathbb{E}|X_{W}(z)|^{2}=M(-z/n)^{n^{2}}|1+z\mu(-z/n)|^{2n}\sum_{k=0}^{n}\frac{1}{k!}\left(\frac{|z|^{2}\sigma^{2}(-z/n)}{|1+z\mu(-z/n)|^{2}}\right)^{k}. Proof. Write G_{W}(z)=\frac{1}{n!}\sum_{\sigma\in S_{n}}\prod_{i=1}^{n}(1+zW_{i,\sigma(i)}). Let u:=-z/n . Then \mathbb{E}|X_{W}(z)|^{2}=\frac{1}{(n!)^{2}}\sum_{\sigma,\tau\in S_{n}}\mathbb{E}\left[\prod_{a,b=1}^{n}\exp\left(uW_{a,b}+\overline{u}\overline{W_{a,b}}\right)\prod_{i=1}^{n}(1+zW_{i,\sigma(i)})(1+\overline{z}\overline{W_{i,\tau(i)}})\right]. Fix \sigma and \tau . Let k:=\#\{i\in[n]:\sigma(i)=\tau(i)\} . Each pair (a,b) which is used by neither permutation (there are n^{2}-2n+k such pairs) contributes \mathbb{E}[\exp(uW_{a,b}+\overline{u}\overline{W_{a,b}})]=M(u) to the product. Each pair (a,b) which is used by both permutation (i.e., b=\sigma(a)=\tau(a) ) (there are k such pairs) contributes \displaystyle\mathbb{E}[\exp(uW_{a,b}+\overline{u}\overline{W_{a,b}})|1+zW_{a,b}|^{2}] \displaystyle=M(u)\mathbb{E}_{u}[|1+zW_{a,b}|^{2}] \displaystyle=M(u)\mathbb{E}_{u}[|1+z\mu(u)+z(W_{a,b}-\mu(u))|^{2}] \displaystyle=M(u)(|1+z\mu(u)|^{2}+|z|^{2}\sigma^{2}(u)). Each pair (a,b) which is used by \sigma but not \tau (there are n-k such pairs) contributes \displaystyle\mathbb{E}[\exp(uW_{a,b}+\overline{u}\overline{W_{a,b}})(1+zW)] \displaystyle=M(u)\mathbb{E}_{u}[1+zW] \displaystyle=M(u)(1+z\mu(u)). Similarly, each pair (a,b) which is used by \tau but not \sigma (there are n-k such pairs) contributes M(u)(1+\overline{z}\overline{\mu(u)}). Thus, the expectation term for a fixed pair of permutations (\sigma,\tau) is M(u)^{n^{2}}|1+z\mu(u)|^{2(n-k)}\left(|1+z\mu(u)|^{2}+|z|^{2}\sigma^{2}(u)\right)^{k}=M(u)^{n^{2}}|1+z\mu(u)|^{2n}t^{k}, where t:=1+\frac{|z|^{2}\sigma^{2}}{|1+z\mu(u)|^{2}}. Note that k=\fix(\pi) where \pi=\sigma^{-1}\tau\sim\mathsf{Unif}(S_{n}) , so using the probability generating function for \fix(\pi) from Lemma 7 gives \mathbb{E}|X_{W}(z)|^{2}=M(u)^{n^{2}}|1+z\mu(u)|^{2n}\mathbb{E}_{\pi}[t^{\fix(\pi)}] which yields the desired formula. ∎ Lemma 30 . There exists r_{0}(K)>0 such that F(a,b):=\log\mathbb{E}e^{aW_{ij}+b\overline{W_{ij}}} is holomorphic on the bidisc D:=\{(a,b)\in\mathbb{C}^{2}:|a|\leq r_{0}(K)/\sqrt{\nu},|b|\leq r_{0}(K)/\sqrt{\nu}\} and has an absolutely convergent power series F(a,b)=\sum_{p+q\geq 2}f_{pq}a^{p}b^{q} where |f_{pq}|\leq\frac{1}{2}r_{0}(K)^{-(p+q)}\nu^{(p+q)/2} . Proof. From the directional sub-exponential condition with \phi=0 and \phi=\pi/2 , we get \|\operatorname{Re}(W_{ij})\|_{\psi_{1}}\leq K\sqrt{\nu},\quad\|\operatorname{Im}(W_{ij})\|_{\psi_{1}}\leq K\sqrt{\nu}. Since |W|\leq|\operatorname{Re}(W_{ij})|+|\operatorname{Im}(W_{ij})| , we get \||W_{ij}|\|_{\psi_{1}}\leq C_{1}K\sqrt{\nu} for some absolute constant C_{1} . By a standard fact about moments of sub-exponential variables, we get \mathbb{E}|W_{ij}|^{m}\leq(C_{3}K\sqrt{\nu}m)^{m}\quad\text{for all }m\geq 1. Fix r>0 and assume a,b\in\mathbb{C} satisfy |a|,|b|\leq r/\sqrt{\nu} . Then |aW_{ij}+b\overline{W_{ij}}|\leq(|a|+|b|)|W_{ij}|\leq\frac{2r}{\sqrt{\nu}}|W_{ij}|. Using m!\geq(m/e)^{m} , we get \frac{\mathbb{E}|aW_{ij}+b\overline{W_{ij}}|^{m}}{m!}\leq\frac{(2r/\sqrt{\nu})^{m}(C_{3}K\sqrt{\nu}m)^{m}}{m!}\leq(2eC_{3}Kr)^{m}. Choosing r_{0}(K):=(8eC_{3}K)^{-1} , we have for |a|,|b|\leq r_{0}(K)/\sqrt{\nu} , \sum_{m\geq 0}\frac{\mathbb{E}|aW_{ij}+b\overline{W_{ij}}|^{m}}{m!}\leq\sum_{m\geq 0}2^{-m}<\infty, so M(a,b):=\mathbb{E}e^{aW_{ij}+b\overline{W_{ij}}}=\sum_{m\geq 0}\frac{\mathbb{E}(aW_{ij}+b\overline{W_{ij}})^{m}}{m!} converges absolutely and locally uniformly, so M is holomorphic on D . Because \mathbb{E}W_{ij}=0 , M(a,b)-1=\sum_{m\geq 2}\frac{\mathbb{E}(aW_{ij}+b\overline{W_{ij}})^{m}}{m!}, so |M(a,b)-1|\leq\sum_{m\geq 2}2^{-m}=\frac{1}{2} . Shrinking r_{0}(K) by an absolute factor if needed, we may ensure |M(a,b)-1|\leq 1/4 on D , so that M stays in a simply connected neighborhood of 1. This ensures that F(a,b)=\log M(a,b) is holomorphic on D and hence F admits a power series F(a,b)=\sum_{p,q\geq 0}f_{pq}a^{p}b^{q}. Also, f_{00}=F(0,0)=0 , and f_{10}=\partial_{a}F(0,0)=\frac{\mathbb{E}W_{ij}}{M(0,0)}=0,\quad f_{01}=\partial_{b}F(0,0)=\frac{\mathbb{E}\overline{W_{ij}}}{M(0,0)}=0, so the sum goes over p+q\geq 2 . Applying Cauchy coefficient estimates on D gives |f_{pq}|\leq\sup_{a,b\in D}|F(a,b)|\left(\frac{\sqrt{\nu}}{r_{0}(K)}\right)^{p+q}\leq\frac{1}{2}\left(\frac{\sqrt{\nu}}{r_{0}(K)}\right)^{p+q}, which finishes the proof. ∎ 6.2 Averaged second-moment estimate Theorem 31 . There exist constants c_{\ast}(K),C_{\ast}(K)>0 such that for every R>0 with \nu R^{2}/n\leq c_{\ast}(K) , \mathbb{E}_{\theta}\log\mathbb{E}|X_{W}(Re^{i\theta})|^{2}\leq\frac{C_{\ast}(K)\nu^{2}R^{4}}{n}. Proof. Set z_{\theta}:=Re^{i\theta},\quad u_{\theta}:=-\frac{R}{n}e^{i\theta},\quad\alpha:=\frac{\nu R^{2}}{n}. Using the formula for \mathbb{E}|X_{W}(z)|^{2} and \sum_{k=0}^{n}\frac{t^{k}}{k!}\leq\exp(t) , we have \log\mathbb{E}|X_{W}(z_{\theta})|^{2}\leq n^{2}\Psi(u_{\theta})+2n\log|1+z_{\theta}\mu(u_{\theta})|+\frac{|z_{\theta}|^{2}\sigma^{2}(u_{\theta})}{|1+z\mu(u_{\theta})|^{2}}. By the previous lemma, there exist r_{0}(K)>0 such that \Psi(u)=\sum_{p+q\geq 2}c_{pq}u^{p}\overline{u}^{q} and the series converges absolutely for |u|\leq r_{0}(K)/\sqrt{\nu} and the coefficients satisfy |c_{pq}|\leq\frac{1}{2}r_{0}(K)^{-(p+q)}\nu^{(p+q)/2}. (14) Also, note that c_{11}=\nu and c_{20}=\kappa/2 where \kappa=|\mathbb{E}W^{2}|\leq\nu . Step 1: the n^{2}\Psi term. Averaging over \theta , only the p=q terms survive, so \mathbb{E}_{\theta}[n^{2}\Psi(u_{\theta})]=\nu R^{2}+n^{2}\sum_{m\geq 2}c_{mm}\left(\frac{R}{n}\right)^{2m}. Choose c_{\ast}(K)\leq r_{0}(K)^{2}/4 . By ( 14 ), for all \alpha\leq c_{\ast}(K) , we have \displaystyle\mathbb{E}_{\theta}[n^{2}\Psi(u_{\theta})] \displaystyle\leq\nu R^{2}+\frac{1}{2}n^{2}\sum_{m\geq 2}\left(\frac{\sqrt{\nu}}{r_{0}(K)}\right)^{2m}\left(\frac{R}{n}\right)^{2m} \displaystyle=\nu R^{2}+\frac{1}{2}n^{2}\sum_{m\geq 2}\left(\frac{\alpha}{nr_{0}(K)^{2}}\right)^{m}=\nu R^{2}+O_{K}\left(\frac{\nu^{2}R^{4}}{n^{2}}\right) since \frac{\alpha}{nr_{0}(K)^{2}}\leq\frac{c_{\ast}(K)}{nr_{0}(K)^{2}}\leq\frac{1}{4n}<1 . Step 2: the 2n\log|1+z\mu(u_{\theta})| term. Since \mu(u)=\partial_{u}\Psi(u) , we have \mu(u)=\sum_{p+q\geq 1}m_{pq}u^{p}\overline{u}^{q},\quad m_{pq}:=(p+1)c_{p+1,q}. From ( 14 ) and p+1\leq 2^{p+q+1}, we have |m_{pq}|\leq B_{1}(K)A_{1}(K)^{p+q}\nu^{(p+q+1)/2},\quad p+q\geq 1. Set \eta:=\sqrt{\nu}R/n . We have w_{\theta}:=z_{\theta}\mu(u_{\theta})=\sum_{p+q\geq 1}a_{pq}e^{i(p-q+1)\theta},\quad a_{pq}:=(-1)^{p+q}m_{pq}\frac{R^{p+q+1}}{n^{p+q}}. By the bound on |m_{pq}| , we have |a_{pq}|\leq C_{K}\alpha(C_{K}\eta)^{p+q-1}. The (p,q)=(0,1) term equals a_{01}=-m_{01}\frac{R^{2}}{n}=-c_{11}\frac{R^{2}}{n}=-\alpha , so write w_{\theta}=-\alpha+\widetilde{w}_{\theta},\quad\widetilde{w}_{\theta}:=\sum_{(p,q)\neq(0,1)}a_{pq}e^{i(p-q+1)\theta}. Choose c_{\ast}(K) small enough so that C_{K}\sqrt{c_{\ast}(K)}\leq 1/4 . Then C_{K}\eta=C_{K}\sqrt{\alpha/n}\leq C_{K}\sqrt{\alpha}\leq 1/4 , so \sup_{\theta}|\widetilde{w}_{\theta}|\leq\sum_{(p,q)\neq(0,1)}|a_{pq}|\leq C_{K}\alpha. Also, \mathbb{E}_{\theta}\widetilde{w}_{\theta}=\sum_{(p,q)\neq(0,1),p-q+1=0}a_{pq}=\sum_{p\geq 1}a_{p,p+1}, so \displaystyle|\mathbb{E}_{\theta}\widetilde{w}_{\theta}|\leq\sum_{p\geq 1}|a_{p,p+1}| \displaystyle\leq C_{K}\alpha\sum_{p\geq 1}(C_{K}\eta)^{2p} \displaystyle=O_{K}(\alpha\eta^{2})=O_{K}(\frac{\alpha^{2}}{n})=O_{K}(\alpha^{2}). Therefore, \mathbb{E}_{\theta}\widetilde{w}_{\theta}=O_{K}(\alpha^{2}),\quad\sup_{\theta}|\widetilde{w}_{\theta}|\leq C_{K}\alpha. Since \alpha\leq c_{\ast}(K) , after shrinking c_{\ast}(K) again if needed, we can ensure that \sup_{\theta}|\widetilde{w}_{\theta}|\leq 1/2 . For |w|\leq 1/2 , \log|1+w|=\operatorname{Re}(w)+O(|w|^{2}) . Hence \mathbb{E}_{\theta}\log|1+w_{\theta}|=\operatorname{Re}(\mathbb{E}_{\theta}w_{\theta})+O(\mathbb{E}_{\theta}|w_{\theta}|^{2})=-\alpha+O_{K}(\alpha^{2}). It follows that \mathbb{E}_{\theta}[2n\log|1+z_{\theta}\mu(u_{\theta})|]=-2\nu R^{2}+O_{K}\left(\frac{\nu^{2}R^{4}}{n}\right). Step 3: the rational term. Define T_{3}:=\mathbb{E}_{\theta}\left[\frac{|z_{\theta}|^{2}\sigma^{2}(u_{\theta})}{|1+z\mu(u_{\theta})|^{2}}\right]=R^{2}\mathbb{E}_{\theta}\left[\frac{\sigma^{2}(u_{\theta})}{|1+w_{\theta}|^{2}}\right]. Set \sigma^{2}(u)=\nu+\widetilde{\sigma}(u) , and use \sigma^{2}(u)=\partial_{u}\partial_{\overline{u}}\Psi(u)=\nu+\sum_{p+q\geq 1}s_{pq}u^{p}\overline{u}^{q},\quad s_{pq}:=(p+1)(q+1)c_{p+1,q+1}. From ( 14 ) and (p+1)(q+1)\leq 4^{p+q+1}, we have |s_{pq}|\leq B_{2}(K)A_{2}(K)^{p+q}\nu^{(p+q+2)/2},\quad p+q\geq 1. Also, \widetilde{\sigma}(u_{\theta})=\sum_{p+q\geq 1}b_{pq}e^{i(p-q)\theta},\quad b_{pq}:=(-1)^{p+q}s_{pq}\left(\frac{R}{n}\right)^{p+q}, and |b_{pq}|\leq C_{K}\nu(C_{K}\eta)^{p+q}. By shrinking c_{\ast}(K) if needed, assume that C_{K}\eta\leq 1/4 . Then \displaystyle\sup_{\theta}|\widetilde{\sigma}(u_{\theta})| \displaystyle\leq\sum_{p+q\geq 1}|b_{pq}| \displaystyle\leq C_{K}\nu\sum_{p+q\geq 1}(C_{K}\eta)^{p+q} \displaystyle\leq C_{K}\nu\sum_{m\geq 1}\sum_{p+q=m}(C_{K}\eta)^{m} \displaystyle=C_{K}\nu\sum_{m\geq 1}(m+1)(C_{K}\eta)^{m}=C_{K}\nu\left(\frac{1}{(1-C_{K}\eta)^{2}}-1\right)\leq C^{\prime}_{K}\nu\eta, and \mathbb{E}_{\theta}\widetilde{\sigma}(u_{\theta})=\sum_{p\geq 1}b_{pp}=O_{K}(\nu\eta^{2})=O_{K}\left(\nu\frac{\alpha}{n}\right). For |w|\leq 1/2 , Taylor expansion of D(w):=|1+w|^{-2} gives D(w)=1-(w+\overline{w})+R_{D}(w),\quad|R_{D}(w)|\leq C_{D}|w|^{2}. So \frac{T_{3}}{R^{2}}=A_{0}+A_{1}+A_{2}, where A_{0}:=\mathbb{E}_{\theta}[\nu+\widetilde{\sigma}(u_{\theta})] , A_{1}:=-\mathbb{E}_{\theta}[(\nu+\widetilde{\sigma}(u_{\theta}))(w_{\theta}+\overline{w_{\theta}})] , A_{2}:=\mathbb{E}_{\theta}[(\nu+\widetilde{\sigma}(u_{\theta}))R_{D}(w_{\theta})] . For A_{0} , we have A_{0}=\nu+O_{K}\left(\nu\frac{\alpha}{n}\right). For A_{1} , we write w_{\theta}=-\alpha+\widetilde{w}_{\theta} . We showed before that \mathbb{E}_{\theta}\widetilde{w}_{\theta}=O_{K}(\alpha^{2}) and \sup_{\theta}|\widetilde{w}_{\theta}|\leq C_{K}\alpha , so -\nu\mathbb{E}_{\theta}[w_{\theta}+\overline{w_{\theta}}]=2\nu\alpha+O_{K}(\nu\alpha^{2}). Also, using \mathbb{E}_{\theta}|w_{\theta}+\overline{w_{\theta}}|\leq 2\sup_{\theta}|w_{\theta}|\leq 2\alpha+2\sup_{\theta}|\widetilde{w}_{\theta}|=O_{K}(\alpha) , we get |\mathbb{E}_{\theta}[\widetilde{\sigma}(u_{\theta})(w_{\theta}+\overline{w_{\theta}})]|\leq\sup_{\theta}|\widetilde{\sigma}(u_{\theta})|\,\mathbb{E}_{\theta}|w_{\theta}+\overline{w_{\theta}}|=O_{K}\left(\nu\alpha\sqrt{\frac{\alpha}{n}}\right). Thus A_{1}=2\nu\alpha+O_{K}(\nu\alpha^{2})+O_{K}\left(\nu\alpha\sqrt{\frac{\alpha}{n}}\right). For A_{2} , we use |R_{D}(w_{\theta})|\leq C_{D}|w_{\theta}|^{2} ; then using \mathbb{E}_{\theta}|w_{\theta}|^{2}\leq\sup_{\theta}|w_{\theta}|^{2}=O_{K}(\alpha^{2}) , we have \displaystyle|A_{2}| \displaystyle\leq\left(\nu+\sup_{\theta}|\widetilde{\sigma}(u_{\theta})|\right)C_{D}\mathbb{E}_{\theta}|w_{\theta}|^{2} \displaystyle\leq\nu(1+C_{K}\eta)O_{K}(\alpha^{2}) \displaystyle=O_{K}(\nu\alpha^{2}). Combining, we get \frac{T_{3}}{R^{2}}=\nu+2\nu\alpha+O_{K}\left(\nu\alpha^{2}+\nu\alpha\sqrt{\frac{\alpha}{n}}+\nu\frac{\alpha}{n}\right). By choosing c_{\ast}(K) to be smaller than some absolute constant smaller than 1, \alpha\leq c_{\ast}(K) implies the bracketed terms are O_{K}(\nu\alpha) . Thus, \frac{T_{3}}{R^{2}}=\nu+O_{K}\left(\nu\alpha\right). It follows that T_{3}=\nu R^{2}+O_{K}(\nu\alpha R^{2})=\nu R^{2}+O_{K}(\nu^{2}R^{4}/n) . Step 4: combine. It follows that for all \alpha\leq c_{\ast}(K) , we have \displaystyle\mathbb{E}_{\theta}\log\mathbb{E}|X_{W}(Re^{i\theta})|^{2} \displaystyle=(\nu R^{2})+\left(-2\nu R^{2}+O_{K}\left(\frac{\nu^{2}R^{4}}{n}\right)\right)+\left(\nu R^{2}+O_{K}\left(\frac{\nu^{2}R^{4}}{n}\right)\right) \displaystyle=O_{K}\left(\frac{\nu^{2}R^{4}}{n}\right). This is the desired conclusion. ∎ This gives a zero-free disk with high probability, which we discuss next. 6.3 Zero-free region and algorithm Theorem 32 . Let 00 , with probability 1-O_{\varepsilon}(n^{-4\beta}) , the following holds simultaneously for every z\in\mathbb{C} such that |z|\leq(1-\varepsilon)\frac{n^{1/4-2\beta}}{\sqrt{\nu}}. There is a deterministic algorithm which outputs an n^{-\gamma} -additive approximation to the branch of \log G_{W}(z)=\log\!\left(\frac{1}{n!}\per(J+zW)\right) determined by \log G_{W}(0)=0 , in time n^{O(m)} , where m=\left\lceil\frac{\gamma+1}{\beta}\right\rceil. This algorithm is based on the degree- m truncated Taylor series of \log G_{W} . Proof. Set R_{n}:=\frac{n^{1/4-\beta}}{\sqrt{\nu}},\qquad r_{n}:=(1-\varepsilon/2)R_{n},\qquad L_{n}:=(1-\varepsilon)n^{-\beta}R_{n}=\frac{(1-\varepsilon)n^{1/4-2\beta}}{\sqrt{\nu}}. By the previous theorem, for all sufficiently large n , \mathbb{P}\!\left[G_{W}\text{ has a zero in }\mathbb{D}(0,r_{n})\right]=O_{\varepsilon}(n^{-4\beta}). Condition on the complementary event. Then G_{W} is zero-free on \mathbb{D}(0,r_{n}) , so there is a holomorphic branch f(z):=\log G_{W}(z)=\sum_{k\geq 1}a_{k}z^{k} on \mathbb{D}(0,r_{n}) , normalized by f(0)=0 . Now fix z with |z|\leq L_{n} . Then \frac{|z|}{r_{n}}\leq\frac{(1-\varepsilon)n^{-\beta}R_{n}}{(1-\varepsilon/2)R_{n}}=\rho_{\varepsilon}\,n^{-\beta},\qquad\rho_{\varepsilon}:=\frac{1-\varepsilon}{1-\varepsilon/2}<1. Let T_{m}(z):=\sum_{k=1}^{m}a_{k}z^{k} be the degree- m truncation of the Taylor series of \log G_{W} . By Barvinok interpolation [ 9 ] , |f(z)-T_{m}(z)|\leq\frac{n}{m+1}\,\frac{(\rho_{\varepsilon}n^{-\beta})^{m+1}}{1-\rho_{\varepsilon}n^{-\beta}}. Choose m=\left\lceil\frac{\gamma+1}{\beta}\right\rceil. Then \beta(m+1)\geq\gamma+1+\beta , so for all sufficiently large n , \frac{n}{m+1}\,\frac{(\rho_{\varepsilon}n^{-\beta})^{m+1}}{1-\rho_{\varepsilon}n^{-\beta}}\leq C_{\varepsilon,\beta,\gamma}\,n^{1-\beta(m+1)}\leq n^{-\gamma}. Hence |\log G_{W}(z)-T_{m}(z)|\leq n^{-\gamma}. Next, write G_{W}(z)=\sum_{k=0}^{n}g_{k}z^{k},\qquad g_{0}=1. As before, g_{k}=\frac{(n-k)!}{n!}\sum_{\begin{subarray}{c}I,J\subseteq[n]\\ |I|=|J|=k\end{subarray}}\per(W_{I,J}), so g_{0},\dots,g_{m} can be computed exactly in time n^{O(m)} , because each k\times k permanent is computable in O(k2^{k}) time via Ryser’s formula, and there are \binom{n}{k}^{2} choices of (I,J) . The coefficients a_{1},\dots,a_{m} are then recovered from kg_{k}=\sum_{j=1}^{k}ja_{j}g_{k-j}, that is, a_{k}=g_{k}-\frac{1}{k}\sum_{j=1}^{k-1}ja_{j}g_{k-j}, in additional polynomial time in m . Therefore T_{m}(z) is an n^{-\gamma} -additive approximation to \log G_{W}(z) on the specified branch. The total running time is n^{O(m)} , which is n^{O(\gamma/\beta)} . ∎ 6.4 Discussion: some non-universal formulas When the entries of W are no longer circular complex Gaussian, there are distribution-dependent corrections which appear in \log\per(J+zW) . What happens is that the first-order reweighting X_{W}(z):=e^{-zS_{W}}G_{W}(z) is no longer exactly centered at 1 : already its first moment acquires a nontrivial quadratic correction. The easiest way to see this is in the case of real Gaussian entries. Example: real Gaussian. Suppose W=(W_{ij})_{1\leq i,j\leq n} has i.i.d. entries W_{ij}\sim N(0,1) , and let \xi\sim N(0,1) denote a single scalar entry. Set u:=-\frac{z}{n}. Since G_{W}(z)=\frac{1}{n!}\sum_{\sigma\in S_{n}}\prod_{i=1}^{n}(1+zW_{i,\sigma(i)}), we have \mathbb{E}[X_{W}(z)]=\frac{1}{n!}\sum_{\sigma\in S_{n}}\mathbb{E}\!\left[\prod_{a,b=1}^{n}e^{uW_{ab}}\prod_{i=1}^{n}(1+zW_{i,\sigma(i)})\right]. Fix a permutation \sigma\in S_{n} . By independence, the expectation factors over the matrix entries. Each entry (a,b) not used by \sigma contributes \mathbb{E}[e^{u\xi}]=e^{u^{2}/2}. Each entry (a,\sigma(a)) used by \sigma contributes \mathbb{E}[e^{u\xi}(1+z\xi)]=\mathbb{E}[e^{u\xi}]+z\,\mathbb{E}[\xi e^{u\xi}]=e^{u^{2}/2}(1+uz), where we used Stein’s lemma in the form \mathbb{E}[\xi e^{u\xi}]=u\,\mathbb{E}[e^{u\xi}] . There are n^{2}-n unused entries and n used entries, so every permutation contributes \bigl(e^{u^{2}/2}\bigr)^{n^{2}-n}\bigl(e^{u^{2}/2}(1+uz)\bigr)^{n}=e^{n^{2}u^{2}/2}(1+uz)^{n}. Therefore \mathbb{E}[X_{W}(z)]=e^{n^{2}u^{2}/2}(1+uz)^{n}=\exp\!\left(\frac{z^{2}}{2}\right)\left(1-\frac{z^{2}}{n}\right)^{n}\to e^{-z^{2}/2} as n\to\infty . So even for Gaussian entries, the first-order reweighting is not exactly centered unless one is in the circular complex Gaussian setting. The general mechanism, which we can guess from the cluster expansion (consider the mean of the second-order term), is that the leading discrepancy is governed by the holomorphic second moment \kappa:=\mathbb{E}[\xi^{2}]. For a real standard Gaussian, \kappa=1 , which produces the quadratic correction above. For a circular complex Gaussian, \kappa=0 , and in fact \mathbb{E}[X_{W}(z)]=1 exactly. The next lemma makes this precise. Note that this lemma is included for expository purposes — it is not used in the proof of any other results. Lemma 36 (Quadratic correction to the first moment) . Let \xi be a complex-valued random variable with \mathbb{E}[\xi]=0 , and assume that the holomorphic moment generating function M(u):=\mathbb{E}[e^{u\xi}] is analytic and nonvanishing in a neighborhood of u=0 . Define K(u):=\log M(u),\qquad\kappa:=\mathbb{E}[\xi^{2}], where the branch of \log is chosen so that K(0)=0 . Let W=(W_{ij})_{1\leq i,j\leq n} be an n\times n random matrix with i.i.d. entries distributed as \xi , and set G_{W}(z):=\frac{1}{n!}\per(J+zW),\qquad S_{W}:=\frac{1}{n}\sum_{i,j=1}^{n}W_{ij},\qquad X_{W}(z):=e^{-zS_{W}}G_{W}(z). Then, for all z sufficiently close to 0 , \mathbb{E}[X_{W}(z)]=\exp\!\Bigl(n^{2}K(-z/n)+n\log\!\bigl(1+zK^{\prime}(-z/n)\bigr)\Bigr). In particular, \log\mathbb{E}[X_{W}(z)]=-\frac{\kappa}{2}z^{2}+O(z^{3}). Proof. Write G_{W}(z)=\frac{1}{n!}\sum_{\sigma\in S_{n}}\prod_{i=1}^{n}(1+zW_{i,\sigma(i)}). Let u:=-z/n . Then \mathbb{E}[X_{W}(z)]=\frac{1}{n!}\sum_{\sigma\in S_{n}}\mathbb{E}\!\left[\prod_{a,b=1}^{n}e^{uW_{ab}}\prod_{i=1}^{n}(1+zW_{i,\sigma(i)})\right]. Fix \sigma\in S_{n} . Each entry (a,b) not used by \sigma contributes \mathbb{E}[e^{u\xi}]=M(u) . Each used entry contributes \mathbb{E}[e^{u\xi}(1+z\xi)]=M(u)+z\,\mathbb{E}[\xi e^{u\xi}]=M(u)\bigl(1+zK^{\prime}(u)\bigr), since K^{\prime}(u)=\frac{M^{\prime}(u)}{M(u)}=\frac{\mathbb{E}[\xi e^{u\xi}]}{\mathbb{E}[e^{u\xi}]}. Therefore every permutation contributes the same quantity, M(u)^{n^{2}}\bigl(1+zK^{\prime}(u)\bigr)^{n}, and so \mathbb{E}[X_{W}(z)]=M(u)^{n^{2}}\bigl(1+zK^{\prime}(u)\bigr)^{n}. Taking logarithms gives \log\mathbb{E}[X_{W}(z)]=n^{2}K(-z/n)+n\log\!\bigl(1+zK^{\prime}(-z/n)\bigr). Now K(0)=0 , K^{\prime}(0)=\mathbb{E}[\xi]=0 , and K^{\prime\prime}(0)=\mathbb{E}[\xi^{2}]=\kappa . Expanding near 0 , K(u)=\frac{\kappa}{2}u^{2}+O(u^{3}),\qquad K^{\prime}(u)=\kappa u+O(u^{2}). Substituting u=-z/n , we get n^{2}K(-z/n)=\frac{\kappa}{2}z^{2}+O(z^{3}/n) and zK^{\prime}(-z/n)=-\frac{\kappa}{n}z^{2}+O(z^{3}/n^{2}) . Hence n\log(1+zK^{\prime}(-z/n))=-\kappa z^{2}+O(z^{3}/n), and combining the two terms yields \log\mathbb{E}[X_{W}(z)]=-\frac{\kappa}{2}z^{2}+O(z^{3}). This proves the claim. ∎ 7 Hardcore model with random fugacities In the next two sections, we move on from the permanent and consider hardcore models on general graph. As a reminder (see the Overview), the permanent is roughly analogous to the hardcore model on the line graph of the complete bipartite graph K_{n,n} , which has maximum degree n and {n\choose 2} many vertices. So while K_{n,n} is very dense, its line graph is somewhat sparser — it has degree proportional to square-root of the number of vertices. On general graphs, this relative sparsity will play a crucial role in the analysis. 7.1 Model on a general graph Let G=(V,E) be a finite graph with maximum degree \Delta\geq 2 , with vertex fugacities \lambda_{v}\in\mathbb{C} . Recall from earlier that the hardcore partition function Z is the sum of the weights of all valid independent sets: Z=\sum_{I\in\mathcal{I}(G)}\prod_{v\in I}\lambda_{v} (15) and the corresponding cluster expansion of the log partition function is given by: \log Z=\sum_{\mathbf{m}\neq\mathbf{0}}\frac{1}{\mathbf{m}!}\phi(H[\mathbf{m}])\prod_{v\in V}\lambda_{v}^{m_{v}} (16) where \mathbf{m}!=\prod_{v\in V}m_{v}! , and \phi(H) is the Ursell function. For any graph H=(W,E_{H}) , the Ursell function evaluates the sum over all its connected spanning subgraphs: \phi(H)=\sum_{\begin{subarray}{c}A\subseteq E_{H}\\ (W,A)\text{ is connected}\end{subarray}}(-1)^{|A|} (17) Random fugacities. We now focus on the case where \lambda_{v}=\lambda W_{v} and each W_{v} is an i.i.d. mean zero complex-valued random variable. The cluster expansion becomes: \sum_{k=1}^{\infty}\lambda^{k}\sum_{|\mathbf{m}|=k}\frac{1}{\mathbf{m}!}\phi(H[\mathbf{m}])\prod_{v\in V}W_{v}^{m_{v}}=\sum_{k=1}^{\infty}a_{k}\lambda^{k} 7.2 First-order reweighting Let G=(V,E) be a finite graph with maximum degree \Delta\geq 1 . We consider the hardcore model partition function with complex random fugacities \lambda W_{v} , where W_{v}\sim\mathcal{N}_{\mathbb{C}}(0,1) are i.i.d. standard complex Gaussians. We define the reweighted partition function as: X(\lambda)=Z(\lambda W)\exp\left(-\lambda\sum_{v\in V}W_{v}\right) (18) Theorem 37 . Let G=(V,E) be a finite graph with maximum degree \Delta\geq 1 , and let Z(\lambda W)=\sum_{I\in\mathcal{I}(G)}\lambda^{|I|}\prod_{v\in I}W_{v} be the hardcore partition function with random fugacities \lambda W_{v} , where W_{v}\sim\mathcal{N}_{\mathbb{C}}(0,1) are i.i.d. standard complex Gaussians. Define X(\lambda):=Z(\lambda W)\exp\!\Bigl(-\lambda\sum_{v\in V}W_{v}\Bigr). Let (G_{n})_{n\geq 1} be a sequence of graphs with vertex sets V_{n} and maximum degrees \Delta_{n} , and let \lambda_{n}\in\mathbb{C} be a sequence such that |\lambda_{n}|^{4}\Delta_{n}|V_{n}|=o(1). Then \mathbb{E}\bigl[\,|X(\lambda_{n})|^{2}\,\bigr]=1+o(1). Proof. We first expand X(\lambda) as a polynomial in the Gaussian variables (W_{v})_{v\in V} . Step 1: Coefficient formula. Write Z(\lambda W)=\sum_{I\in\mathcal{I}(G)}\lambda^{|I|}W^{I},\qquad W^{I}:=\prod_{v\in I}W_{v}, and \exp\!\Bigl(-\lambda\sum_{v\in V}W_{v}\Bigr)=\prod_{v\in V}\Bigl(\sum_{r_{v}\geq 0}\frac{(-\lambda W_{v})^{r_{v}}}{r_{v}!}\Bigr). For a multi-index m=(m_{v})_{v\in V}\in(\mathbb{Z}_{\geq 0})^{V} , let |m|:=\sum_{v\in V}m_{v},\qquad m!:=\prod_{v\in V}m_{v}!,\qquad\operatorname{supp}(m):=\{v\in V:\ m_{v}>0\}. Collecting the coefficient of W^{m}:=\prod_{v}W_{v}^{m_{v}} gives X(\lambda)=\sum_{m\in(\mathbb{Z}_{\geq 0})^{V}}\lambda^{|m|}\frac{(-1)^{|m|}}{m!}\Biggl(\sum_{\begin{subarray}{c}I\in\mathcal{I}(G)\\ I\subseteq\operatorname{supp}(m)\end{subarray}}\prod_{v\in I}(-m_{v})\Biggr)W^{m}. The inner sum is exactly the hardcore partition function on the induced subgraph G[\operatorname{supp}(m)] with vertex fugacities (-m_{v})_{v\in\operatorname{supp}(m)} , namely Z_{G[\operatorname{supp}(m)]}(-m):=\sum_{I\in\mathcal{I}(G[\operatorname{supp}(m)])}\prod_{v\in I}(-m_{v}). Therefore X(\lambda)=\sum_{m\in(\mathbb{Z}_{\geq 0})^{V}}\lambda^{|m|}\frac{(-1)^{|m|}}{m!}Z_{G[\operatorname{supp}(m)]}(-m)\,W^{m}. (19) Step 2: Exact second-moment formula. Since the W_{v} are independent standard complex Gaussians, \mathbb{E}\bigl[W^{m}\overline{W}^{\,m^{\prime}}\bigr]=0\qquad\text{unless }m=m^{\prime}, and \mathbb{E}\bigl[|W^{m}|^{2}\bigr]=\prod_{v\in V}\mathbb{E}\bigl[|W_{v}|^{2m_{v}}\bigr]=\prod_{v\in V}m_{v}!=m!. Thus, taking the expectation of the absolute square of ( 19 ), all off-diagonal terms vanish and we obtain \mathbb{E}\bigl[|X(\lambda)|^{2}\bigr]=\sum_{m\in(\mathbb{Z}_{\geq 0})^{V}}|\lambda|^{2|m|}\frac{1}{m!}\bigl|Z_{G[\operatorname{supp}(m)]}(-m)\bigr|^{2}. (20) Every summand is nonnegative, and the m=0 term is equal to 1 . Step 3: Factorization over connected components. Fix m . Let S:=\operatorname{supp}(m) , and let G[S]=C_{1}\sqcup\cdots\sqcup C_{r} be its decomposition into connected components. Since the hardcore partition function factorizes over disjoint unions, Z_{G[S]}(-m)=\prod_{i=1}^{r}Z_{G[C_{i}]}(-m_{C_{i}}), where m_{C_{i}} denotes the restriction of m to C_{i} . Also, |\lambda|^{2|m|}\frac{1}{m!}=\prod_{i=1}^{r}\left(|\lambda|^{2|m_{C_{i}}|}\frac{1}{m_{C_{i}}!}\right). Hence the summand in ( 20 ) factors over connected components. For a connected vertex set C\subseteq V and a multiplicity vector m_{C}\in(\mathbb{Z}_{\geq 1})^{C} , define the polymer weight w(C,m_{C}):=|\lambda|^{2|m_{C}|}\frac{1}{m_{C}!}\bigl|Z_{G[C]}(-m_{C})\bigr|^{2}. Then ( 20 ) is exactly the partition function of a hard-core polymer gas: \mathbb{E}\bigl[|X(\lambda)|^{2}\bigr]=\sum_{\Gamma\ \text{compatible}}\ \prod_{(C,m_{C})\in\Gamma}w(C,m_{C}), where “compatible” means that the vertex sets of the polymers are pairwise disjoint. Since all polymer weights are nonnegative, forgetting the compatibility constraint only enlarges the sum, and therefore \mathbb{E}\bigl[|X(\lambda)|^{2}\bigr]\leq\prod_{\begin{subarray}{c}C\subseteq V\\ C\ \text{connected}\end{subarray}}\ \prod_{m_{C}\in(\mathbb{Z}_{\geq 1})^{C}}\bigl(1+w(C,m_{C})\bigr)\leq\exp\!\Biggl(\sum_{\begin{subarray}{c}C\subseteq V\\ C\ \text{connected}\end{subarray}}\ \sum_{m_{C}\in(\mathbb{Z}_{\geq 1})^{C}}w(C,m_{C})\Biggr). (21) Let \mathcal{W}:=\sum_{\begin{subarray}{c}C\subseteq V\\ C\ \text{connected}\end{subarray}}\ \sum_{m_{C}\in(\mathbb{Z}_{\geq 1})^{C}}w(C,m_{C}). It remains to show that \mathcal{W}=o(1) . Step 4: Contributions of connected sets of size 1 . If C=\{v\} , then Z_{G[\{v\}]}(-m_{v})=1-m_{v} . Hence the contribution of a single vertex is \sum_{m\geq 1}|\lambda|^{2m}\frac{|1-m|^{2}}{m!}=\sum_{m\geq 2}|\lambda|^{2m}\frac{(m-1)^{2}}{m!}. For |\lambda|\leq 1 , this is bounded by |\lambda|^{4}\sum_{m\geq 2}\frac{(m-1)^{2}}{m!}\leq c_{1}|\lambda|^{4} for some absolute constant c_{1}>0 . Summing over v\in V gives \mathcal{W}_{1}\leq c_{1}|V|\,|\lambda|^{4}. Step 5: Contributions of connected sets of size 2 . If C=\{u,v\} is connected, then necessarily u\sim v , and Z_{G[C]}(-m_{u},-m_{v})=1-m_{u}-m_{v} . Therefore \sum_{m_{u},m_{v}\geq 1}|\lambda|^{2(m_{u}+m_{v})}\frac{|1-m_{u}-m_{v}|^{2}}{m_{u}!m_{v}!}\leq c_{2}|\lambda|^{4} for some absolute constant c_{2}>0 and all sufficiently small |\lambda| . Summing over edges, \mathcal{W}_{2}\leq c_{2}|E|\,|\lambda|^{4}\leq\frac{c_{2}}{2}|V|\Delta\,|\lambda|^{4}. Step 6: Contributions of connected sets of size at least 3 . Let C\subseteq V be connected with |C|=k\geq 3 . By the triangle inequality, |Z_{G[C]}(-m_{C})|\leq\sum_{I\in\mathcal{I}(G[C])}\prod_{v\in I}m_{v}\leq\sum_{S\subseteq C}\prod_{v\in S}m_{v}=\prod_{v\in C}(1+m_{v}). Hence w(C,m_{C})\leq\prod_{v\in C}\left(|\lambda|^{2m_{v}}\frac{(1+m_{v})^{2}}{m_{v}!}\right). Summing over m_{v}\geq 1 independently, \sum_{m_{C}\in(\mathbb{Z}_{\geq 1})^{C}}w(C,m_{C})\leq\left(\sum_{m\geq 1}|\lambda|^{2m}\frac{(1+m)^{2}}{m!}\right)^{k}. For |\lambda|\leq 1 , the one-variable sum is bounded by \sum_{m\geq 1}|\lambda|^{2m}\frac{(1+m)^{2}}{m!}\leq c_{3}|\lambda|^{2} for some absolute constant c_{3}>0 . Therefore \sum_{m_{C}\in(\mathbb{Z}_{\geq 1})^{C}}w(C,m_{C})\leq(c_{3}|\lambda|^{2})^{k}. Now fix k\geq 3 . The number of connected induced subgraphs of G with k vertices containing a given vertex is at most (e\Delta)^{k-1} , so the total number of connected k -vertex subsets of V is at most \frac{|V|}{k}(e\Delta)^{k-1}\leq|V|(e\Delta)^{k-1}. Hence \mathcal{W}_{\geq 3}\leq|V|\sum_{k\geq 3}(e\Delta)^{k-1}(c_{3}|\lambda|^{2})^{k}=\frac{|V|}{e\Delta}\sum_{k\geq 3}(c_{3}e\Delta|\lambda|^{2})^{k}. We claim that \Delta|\lambda|^{2}\to 0 under the hypothesis |\lambda|^{4}\Delta|V|=o(1). Indeed, since every graph satisfies |V|\geq\Delta+1 , we have |\lambda|^{4}\Delta^{2}\leq|\lambda|^{4}\Delta|V|=o(1) , and therefore \Delta|\lambda|^{2}=o(1) . So for all sufficiently large n , c_{3}e\Delta|\lambda|^{2}\leq\frac{1}{2} . Thus the geometric series is bounded by a constant multiple of its first term: \mathcal{W}_{\geq 3}\leq c_{4}|V|\Delta^{2}|\lambda|^{6} for some absolute constant c_{4}>0 . Step 7: Conclusion. Combining the three estimates, \mathcal{W}\leq c_{1}|V||\lambda|^{4}+\frac{c_{2}}{2}|V|\Delta|\lambda|^{4}+c_{4}|V|\Delta^{2}|\lambda|^{6}. By the hypothesis, |V|\Delta|\lambda|^{4}=o(1) , and also |V|\Delta^{2}|\lambda|^{6}=\bigl(|V|\Delta|\lambda|^{4}\bigr)\bigl(\Delta|\lambda|^{2}\bigr)=o(1). Hence \mathcal{W}=o(1) . Returning to ( 21 ), \mathbb{E}\bigl[|X(\lambda)|^{2}\bigr]\leq\exp(\mathcal{W})=1+o(1). On the other hand, the m=0 term in ( 20 ) is 1 , and all other terms are nonnegative, so \mathbb{E}\bigl[|X(\lambda)|^{2}\bigr]\geq 1 . Therefore \mathbb{E}\bigl[|X(\lambda_{n})|^{2}\bigr]=1+o(1), as claimed. ∎ To illustrate how this theorem is applied, we show how to recover a weaker version of the result from Theorem 61 . Corollary 38 (Weaker version of Theorem 61 ) . Let G_{n}=L(K_{n,n}) be the line graph of the complete bipartite graph, and let W_{ij}\sim\mathcal{N}_{\mathbb{C}}(0,1) . Let X_{n}(\lambda)=P_{n}(\lambda)\exp(-\lambda\sum_{i,j}W_{ij}) . If |\lambda_{n}|=o(n^{-3/4}) , then \mathbb{E}[|X_{n}(\lambda_{n})|^{2}]=1+o(1) . Proof. The independent sets of L(K_{n,n}) correspond exactly to the matchings of K_{n,n} . For the line graph G_{n}=L(K_{n,n}) , the number of vertices is |V_{n}|=n^{2} . The maximum degree is the number of edges adjacent to a given edge in K_{n,n} , which is \Delta_{n}=2n-2 . Applying Theorem 37 , the sufficient condition for the relative variance to vanish is |\lambda_{n}|^{4}(2n-2)(n^{2})=o(1) , which is equivalent to |\lambda_{n}|^{4}n^{3}=o(1) , or |\lambda_{n}|=o(n^{-3/4}) . ∎ 8 Universality of the zero-free region for the hardcore model We now prove an analogue of Theorem 37 for general i.i.d. complex vertex weights, without assuming rotational symmetry. The key input is cancellation after averaging over the phase \theta , together with a cluster expansion for a suitable pair model representing the second moment. Part of the technical estimate for the auxiliary cluster expansion is deferred to Lemma 61 at the end. Theorem 39 . Let G_{n}=(V_{n},E_{n}) be a sequence of finite graphs with maximum degree \Delta_{n} . Let W_{v} be i.i.d. complex random variables with \mathbb{E}[W_{v}]=0,\qquad\mathbb{E}|W_{v}|^{2}=\nu, and assume that for some K>0 , \sup_{\phi\in[0,2\pi)}\bigl\|\operatorname{Re}(e^{-i\phi}W_{v})\bigr\|_{\psi_{1}}\leq K\sqrt{\nu}. For \lambda\in\mathbb{C} , define Z_{G}(\lambda W):=\sum_{I\in\mathcal{I}(G)}\lambda^{|I|}\prod_{v\in I}W_{v},\qquad X_{W}(\lambda):=Z_{G}(\lambda W)\exp\!\Bigl(-\lambda\sum_{v\in V}W_{v}\Bigr). If R_{n}>0 satisfies \nu^{2}R_{n}^{4}(1+\Delta_{n})|V_{n}|=o(1), then \mathbb{E}_{\theta}\log\mathbb{E}_{W}\bigl|X_{W}(R_{n}e^{i\theta})\bigr|^{2}=o(1), where \theta\sim\mathrm{Unif}[0,2\pi) . Lemma 40 . There exist constants r_{0}=r_{0}(K)>0 and A_{K},B_{K}>0 , depending only on K , such that F(a,b):=\log\mathbb{E}e^{aW+b\overline{W}} is holomorphic on the bidisc D:=\left\{(a,b)\in\mathbb{C}^{2}:\ |a|,|b|\leq\frac{r_{0}}{\sqrt{\nu}}\right\}, and has an absolutely convergent expansion F(a,b)=\sum_{p+q\geq 2}c_{pq}a^{p}b^{q} with |c_{pq}|\leq A_{K}\,B_{K}^{\,p+q}\,\nu^{(p+q)/2}. Moreover, c_{11}=\nu . Proof. Write W=X+iY . Taking \phi=0 and \phi=\pi/2 in the hypothesis gives \|X\|_{\psi_{1}}\leq K\sqrt{\nu},\qquad\|Y\|_{\psi_{1}}\leq K\sqrt{\nu}. Since |W|\leq|X|+|Y| , we obtain \|W\|_{\psi_{1}}\leq C_{K}\sqrt{\nu}, for some constant C_{K} depending only on K . Hence the standard sub-exponential moment bound yields \mathbb{E}|W|^{m}\leq(C_{K}\sqrt{\nu}\,m)^{m},\qquad m\geq 1. Set M(a,b):=\mathbb{E}e^{aW+b\overline{W}}. For s:=|a|+|b| , we have \sum_{p,q\geq 0}\frac{|a|^{p}|b|^{q}}{p!\,q!}\,\mathbb{E}|W|^{p+q}=\sum_{m\geq 0}\frac{s^{m}}{m!}\,\mathbb{E}|W|^{m}\leq 1+\sum_{m\geq 1}\frac{(C_{K}\sqrt{\nu}\,ms)^{m}}{m!}. Using m!\geq(m/e)^{m} , we obtain \frac{(C_{K}\sqrt{\nu}\,ms)^{m}}{m!}\leq(eC_{K}s\sqrt{\nu})^{m}. Therefore the series converges absolutely whenever s\leq c_{K}/\sqrt{\nu} for c_{K}>0 sufficiently small. In particular, M(a,b) is holomorphic on a neighborhood of a bidisc \bigl\{|a|,|b|\leq 2r_{0}/\sqrt{\nu}\bigr\} for some r_{0}=r_{0}(K)>0 . Shrinking r_{0} if necessary, the same estimate gives |M(a,b)-1|\leq\sum_{m\geq 1}(eC_{K}(|a|+|b|)\sqrt{\nu})^{m}\leq\frac{1}{2} throughout |a|,|b|\leq 2r_{0}/\sqrt{\nu} . Thus M has no zeros there, and the principal branch F(a,b):=\log M(a,b) is holomorphic on that bidisc. Moreover |F(a,b)|\leq C_{K} there. Now apply Cauchy’s estimate on the smaller bidisc D=\left\{|a|,|b|\leq\frac{r_{0}}{\sqrt{\nu}}\right\}. If F(a,b)=\sum_{p,q\geq 0}c_{pq}a^{p}b^{q}, then |c_{pq}|\leq C_{K}\Bigl(\frac{\sqrt{\nu}}{r_{0}}\Bigr)^{p+q}=A_{K}\,B_{K}^{\,p+q}\,\nu^{(p+q)/2}. Since M(0,0)=1 , we have F(0,0)=0 . Since \mathbb{E}W=0 , \partial_{a}F(0,0)=\mathbb{E}W=0,\qquad\partial_{b}F(0,0)=\mathbb{E}\overline{W}=0, so there are no linear terms. Finally, c_{11}=\partial_{a}\partial_{b}F(0,0)=\partial_{a}\partial_{b}\log M(0,0)=\mathbb{E}|W|^{2}-(\mathbb{E}W)(\mathbb{E}\overline{W})=\nu. This proves the lemma. ∎ Proof of Theorem 39 . Write N:=|V_{n}| , \Delta:=\Delta_{n} , and R:=R_{n} . Since \nu^{2}R_{n}^{4}(1+\Delta_{n})|V_{n}|=o(1), we in particular have \nu R_{n}^{2}=o(1) . Hence for all sufficiently large n , R_{n}\leq\frac{r_{0}}{\sqrt{\nu}}, so Lemma 40 is applicable. It therefore suffices to prove the claimed estimate for all large n . Fix such an n , and set G=(V,E),\qquad N:=|V|,\qquad\lambda=Re^{i\theta},\qquad u:=-\lambda. Define M(a,b):=\mathbb{E}e^{aW+b\overline{W}},\qquad F(a,b):=\log M(a,b), and \mu(a,b):=\partial_{a}F(a,b),\qquad\tau(a,b):=\partial_{a}\partial_{b}F(a,b)+\partial_{a}F(a,b)\partial_{b}F(a,b). Equivalently, \mu(a,b)=\frac{\mathbb{E}\!\left[We^{aW+b\overline{W}}\right]}{M(a,b)},\qquad\tau(a,b)=\frac{\mathbb{E}\!\left[|W|^{2}e^{aW+b\overline{W}}\right]}{M(a,b)}. Along the slice b=\overline{a} , abbreviate \Psi(u):=F(u,\overline{u}),\qquad\mu(u):=\mu(u,\overline{u}),\qquad\tau(u):=\tau(u,\overline{u}). Step 1: exact pair-model representation. By definition, X_{W}(\lambda)=Z_{G}(\lambda W)\exp\!\Bigl(-\lambda\sum_{v\in V}W_{v}\Bigr), hence |X_{W}(\lambda)|^{2}=\sum_{I,J\in\mathcal{I}(G)}\lambda^{|I|}\overline{\lambda}^{\,|J|}\Bigl(\prod_{v\in I}W_{v}\Bigr)\Bigl(\prod_{v\in J}\overline{W_{v}}\Bigr)\exp\!\Bigl(u\sum_{v\in V}W_{v}+\overline{u}\sum_{v\in V}\overline{W_{v}}\Bigr). Taking expectation and using independence across vertices, \displaystyle\mathbb{E}_{W}|X_{W}(\lambda)|^{2} \displaystyle=\sum_{I,J\in\mathcal{I}(G)}\prod_{v\in V}\mathbb{E}\Bigl[e^{uW_{v}+\overline{u}\,\overline{W}_{v}}(\lambda W_{v})^{\mathbf{1}}_{v\in I}(\overline{\lambda}\,\overline{W}_{v})^{\mathbf{1}}_{v\in J}\Bigr] \displaystyle=M(u,\overline{u})^{N}\sum_{I,J\in\mathcal{I}(G)}a_{L}(u,\lambda)^{|I\setminus J|}a_{R}(u,\lambda)^{|J\setminus I|}a_{B}(u,\lambda)^{|I\cap J|}, where a_{L}(u,\lambda):=\lambda\,\mu(u),\qquad a_{R}(u,\lambda):=\overline{\lambda}\,\overline{\mu(u)},\qquad a_{B}(u,\lambda):=|\lambda|^{2}\,\tau(u). Thus \mathbb{E}_{W}|X_{W}(\lambda)|^{2}=e^{N\Psi(u)}\,Z_{\mathrm{pair}}\bigl(a_{L}(u,\lambda),a_{R}(u,\lambda),a_{B}(u,\lambda)\bigr), (22) where Z_{\mathrm{pair}} is the pair-model partition function from Lemma 41 . Step 2: local expansions and size bounds. By Lemma 40 , F(a,b)=\sum_{p+q\geq 2}c_{pq}a^{p}b^{q},\qquad|c_{pq}|\leq A_{K}B_{K}^{p+q}\nu^{(p+q)/2},\qquad c_{11}=\nu. Hence \Psi(u)=\sum_{p+q\geq 2}c_{pq}u^{p}\overline{u}^{\,q}. Differentiating term-by-term, \mu(a,b)=\partial_{a}F(a,b)=\sum_{p+q\geq 1}m_{pq}a^{p}b^{q},\qquad m_{pq}=(p+1)c_{p+1,q}. Using (p+1)\leq 2^{p+1} , we may absorb the factor p+1 into the geometric constant and obtain |m_{pq}|\leq A^{\prime}_{K}(B^{\prime}_{K})^{p+q+1}\nu^{(p+q+1)/2}. In particular, m_{01}=c_{11}=\nu. Similarly, \partial_{a}\partial_{b}F(a,b)=\nu+\sum_{p+q\geq 1}d_{pq}a^{p}b^{q},\qquad|d_{pq}|\leq A^{\prime}_{K}(B^{\prime}_{K})^{p+q+2}\nu^{(p+q+2)/2}. Since \partial_{a}F and \partial_{b}F have no constant term, their product also has an absolutely convergent expansion whose coefficients obey the same type of geometric bound after enlarging constants if necessary. Thus \tau(a,b)=\nu+\sum_{p+q\geq 1}t_{pq}a^{p}b^{q},\qquad|t_{pq}|\leq A^{\prime\prime}_{K}(B^{\prime\prime}_{K})^{p+q+2}\nu^{(p+q+2)/2}. Therefore, after shrinking the allowed radius once more if necessary, there is a constant c_{K}>0 such that whenever |u|\leq c_{K}/\sqrt{\nu} , |a_{L}(u,\lambda)|+|a_{R}(u,\lambda)|+|a_{B}(u,\lambda)|\leq C_{K}\nu R^{2}. (23) Indeed, for |u|\leq c_{K}/\sqrt{\nu} the above series are dominated by geometric series in B_{K}\sqrt{\nu}|u| . Step 3: angular averages and quadratic cancellation. The e^{N\Psi(u)} term. Since u=-Re^{i\theta} , \Psi(-Re^{i\theta})=\sum_{p+q\geq 2}c_{pq}(-1)^{p+q}R^{p+q}e^{i(p-q)\theta}. Averaging over \theta , only the diagonal terms p=q survive: \mathbb{E}_{\theta}\Psi(-Re^{i\theta})=\sum_{p\geq 1}c_{pp}R^{2p}. Using c_{11}=\nu and the geometric bound on c_{pp} , we get \mathbb{E}_{\theta}\Psi(-Re^{i\theta})=\nu R^{2}+O_{K}(\nu^{2}R^{4}). (24) The a_{L} term. We have a_{L}(u,\lambda)=\lambda\mu(u), so a_{L}(-Re^{i\theta},Re^{i\theta})=\sum_{p+q\geq 1}(-1)^{p+q}m_{pq}R^{p+q+1}e^{i(p-q+1)\theta}. After averaging over \theta , only the resonant modes p-q+1=0 survive. The leading one is (p,q)=(0,1) , which contributes (-1)^{1}m_{01}R^{2}=-\nu R^{2}. All other resonant terms satisfy p+q+1\geq 4 , hence \mathbb{E}_{\theta}a_{L}(-Re^{i\theta},Re^{i\theta})=-\nu R^{2}+O_{K}(\nu^{2}R^{4}). (25) By complex conjugation, \mathbb{E}_{\theta}a_{R}(-Re^{i\theta},Re^{i\theta})=-\nu R^{2}+O_{K}(\nu^{2}R^{4}). (26) The a_{B} term. Since a_{B}(u,\lambda)=R^{2}\tau(u) , we have \tau(-Re^{i\theta})=\nu+\sum_{p+q\geq 1}t_{pq}(-1)^{p+q}R^{p+q}e^{i(p-q)\theta}. Averaging over \theta kills all off-diagonal terms, giving \mathbb{E}_{\theta}\tau(-Re^{i\theta})=\nu+\sum_{p\geq 1}t_{pp}R^{2p}=\nu+O_{K}(\nu^{2}R^{2}). Therefore \mathbb{E}_{\theta}a_{B}(-Re^{i\theta},Re^{i\theta})=\nu R^{2}+O_{K}(\nu^{2}R^{4}). (27) Step 4: application of the KP lemma. By ( 23 ), \rho(\theta):=\max\{|a_{L}|,|a_{R}|,|a_{B}|\}\leq C_{K}\nu R^{2}. We can apply our cluster expansion estimate (Lemma 41 below), provided that \nu R^{2}\Delta=o(1). This follows from the hypothesis, since \Delta\leq N for every finite graph, and therefore (\nu R^{2}\Delta)^{2}=\nu^{2}R^{4}\Delta^{2}\leq\nu^{2}R^{4}\,\Delta N\leq\nu^{2}R^{4}(1+\Delta)N=o(1). Hence for all sufficiently large n , \rho(\theta)\leq\frac{c_{\mathrm{KP}}}{\Delta} uniformly in \theta , and Lemma 41 gives \log Z_{\mathrm{pair}}(a_{L},a_{R},a_{B})=N(a_{L}+a_{R}+a_{B})+\mathcal{R}(\theta), with |\mathcal{R}(\theta)|\leq C_{K}N\Delta(\nu R^{2})^{2}=C_{K}N\Delta\nu^{2}R^{4}. (28) Combining this with ( 22 ), we obtain \log\mathbb{E}_{W}|X_{W}(\lambda)|^{2}=N\Psi(u)+N(a_{L}+a_{R}+a_{B})+\mathcal{R}(\theta). Step 5: averaging in \theta . Taking \mathbb{E}_{\theta} and using ( 24 ), ( 25 ), ( 26 ), ( 27 ), and ( 28 ), we get \displaystyle\mathbb{E}_{\theta}\log\mathbb{E}_{W}|X_{W}(Re^{i\theta})|^{2} \displaystyle=N\bigl(\nu R^{2}+O_{K}(\nu^{2}R^{4})\bigr) \displaystyle\quad+N\bigl(-\nu R^{2}-\nu R^{2}+\nu R^{2}+O_{K}(\nu^{2}R^{4})\bigr)+O_{K}(N\Delta\nu^{2}R^{4}). The quadratic terms cancel, leaving \mathbb{E}_{\theta}\log\mathbb{E}_{W}|X_{W}(Re^{i\theta})|^{2}=O_{K}(N\nu^{2}R^{4})+O_{K}(N\Delta\nu^{2}R^{4})=O_{K}\bigl(N(1+\Delta)\nu^{2}R^{4}\bigr). Applying this to G=G_{n} , N=|V_{n}| , \Delta=\Delta_{n} , and R=R_{n} , the assumption \nu^{2}R_{n}^{4}(1+\Delta_{n})|V_{n}|=o(1) implies \mathbb{E}_{\theta}\log\mathbb{E}_{W}\bigl|X_{W}(R_{n}e^{i\theta})\bigr|^{2}=o(1). This proves the theorem. ∎ 8.1 Cluster expansion of pair model We explain in detail the cluster-expansion estimate for the pair model used above. Lemma 41 . There exist absolute constants c_{\mathrm{KP}},C_{\mathrm{KP}}>0 such that the following holds. Let G=(V,E) be a finite graph with maximum degree \Delta , and let a_{L},a_{R},a_{B}\in\mathbb{C}. Consider the finite-state spin model on V with local states \{0,L,R,B\} , vertex weights w(0)=1,\qquad w(L)=a_{L},\qquad w(R)=a_{R},\qquad w(B)=a_{B}, and hard-core constraints that • adjacent vertices may not both lie in \{L,B\} , • and adjacent vertices may not both lie in \{R,B\}. Let Z_{\mathrm{pair}}(a_{L},a_{R},a_{B}) denote its partition function given by the weighted sum over all valid configurations in \{0,L,R,B\}^{V} . If \rho:=\max\{|a_{L}|,|a_{R}|,|a_{B}|\}\leq\frac{c_{\mathrm{KP}}}{\Delta}, then \log Z_{\mathrm{pair}}(a_{L},a_{R},a_{B})=|V|(a_{L}+a_{R}+a_{B})+\mathcal{R}, with |\mathcal{R}|\leq C_{\mathrm{KP}}\,|V|\,\Delta\,\rho^{2}. Proof. We rewrite the model as an abstract polymer gas and then apply the Kotecký–Preiss (KP) criterion. See [ 27 , 49 ] for background on the terminology used. 1. Polymer representation. Let us call a site occupied if its spin lies in \{L,R,B\} , and vacant if its spin is 0 . For two nonzero labels s,t\in\{L,R,B\} , write s\sim_{\mathrm{adm}}t if the pair (s,t) is allowed across an edge. By the stated constraints, the only allowed adjacent nonzero pairs are (L,R)\quad\text{and}\quad(R,L). Indeed, L - L , R - R , L - B , B - L , R - B , B - R , and B - B are all forbidden. A polymer is a pair \gamma=(S,\sigma) where: • S\subseteq V is nonempty and connected in G ; • \sigma:S\to\{L,R,B\} ; • \sigma is internally admissible on S , meaning that for every edge xy\in E(G[S]) , the pair (\sigma(x),\sigma(y)) is allowed. The activity of \gamma=(S,\sigma) is z(\gamma):=\prod_{v\in S}a_{\sigma(v)}. In particular, |z(\gamma)|\leq\rho^{|S|}. Two polymers \gamma=(S,\sigma) and \gamma^{\prime}=(T,\tau) are said to be compatible , written \gamma\sim\gamma^{\prime} , if \operatorname{dist}_{G}(S,T)\geq 2. Equivalently, they are compatible iff S\cap T=\varnothing and there is no edge of G joining a vertex of S to a vertex of T . We claim that Z_{\mathrm{pair}}(a_{L},a_{R},a_{B})=\sum_{\Gamma\ \mathrm{compatible}}\prod_{\gamma\in\Gamma}z(\gamma), where the sum runs over all finite compatible families of polymers. To see this, start from a spin configuration \eta:V\to\{0,L,R,B\} satisfying the edge constraints, and let U:=\{v\in V:\eta(v)\neq 0\} be its occupied set. Decompose U into connected components in the graph G : U=S_{1}\sqcup\cdots\sqcup S_{m}. For each component S_{i} , the restricted labeling \eta|_{S_{i}} is internally admissible, so \gamma_{i}:=(S_{i},\eta|_{S_{i}}) is a polymer. Since S_{i},S_{j} are distinct connected components of U , there is no edge between them, hence \operatorname{dist}_{G}(S_{i},S_{j})\geq 2 ; thus the polymers \gamma_{1},\dots,\gamma_{m} are pairwise compatible. Conversely, any compatible family of polymers determines a unique admissible spin configuration by placing the given nonzero labels on the supports of the polymers and putting 0 elsewhere. The weight factorizes multiplicatively, which proves the identity. 2. A counting bound. Fix a vertex x\in V . For k\geq 1 , the number of connected k -vertex subsets S\subseteq V containing x is at most (e\Delta)^{k-1} . For each such support S , there are at most 3^{k} choices of the labeling \sigma:S\to\{L,R,B\} , and hence at most 3^{k} polymers with support S . Therefore \sum_{\begin{subarray}{c}\gamma\ni x\\ |\gamma|=k\end{subarray}}|z(\gamma)|e^{|\gamma|}\leq(e\Delta)^{k-1}\,3^{k}\,\rho^{k}\,e^{k}=3e\rho\,(3e^{2}\Delta\rho)^{k-1}. Summing over k\geq 1 , we obtain \sum_{\gamma\ni x}|z(\gamma)|e^{|\gamma|}\leq 3e\rho\sum_{k\geq 1}(3e^{2}\Delta\rho)^{k-1}. (29) Hence, provided 3e^{2}\Delta\rho\leq\frac{1}{2} , the geometric series converges and yields \sum_{\gamma\ni x}|z(\gamma)|e^{|\gamma|}\leq C_{0}\,\rho (30) for an absolute constant C_{0} . Now let \gamma=(S,\sigma) be a fixed polymer. If \eta=(T,\tau) is incompatible with \gamma , then \operatorname{dist}_{G}(S,T)\leq 1 , so in particular T contains some vertex of the closed neighborhood N[S]:=S\cup\{y\in V:\exists x\in S,\ xy\in E\}. Thus, using ( 30 ), \displaystyle\sum_{\eta\not\sim\gamma}|z(\eta)|e^{|\eta|} \displaystyle\leq\sum_{x\in N[S]}\sum_{\eta\ni x}|z(\eta)|e^{|\eta|} \displaystyle\leq|N[S]|\,C_{0}\,\rho \displaystyle\leq(\Delta+1)|S|\,C_{0}\,\rho. (31) 3. Verification of the KP condition. Set a(\gamma):=|\gamma|=|S|. Choose c_{\mathrm{KP}}>0 small enough so that whenever \rho\leq\frac{c_{\mathrm{KP}}}{\Delta}, both 3e^{2}\Delta\rho\leq\frac{1}{2} and (\Delta+1)C_{0}\rho\leq 1 hold. Then ( 31 ) gives \sum_{\eta\not\sim\gamma}|z(\eta)|e^{a(\eta)}\leq a(\gamma)\qquad\text{for every polymer }\gamma. This is precisely the Kotecký–Preiss criterion for the abstract polymer gas. Therefore the cluster expansion for \log Z_{\mathrm{pair}} converges absolutely: \log Z_{\mathrm{pair}}=\sum_{\mathcal{X}}\phi^{T}(\mathcal{X})\prod_{\gamma}z(\gamma)^{\mathcal{X}(\gamma)}, where the sum is over all finitely supported polymer multisets \mathcal{X} , and \phi^{T}(\mathcal{X}) denotes the usual truncated cluster coefficient. 4. Extraction of the linear term. The singleton clusters are exactly the one-polymer clusters \mathcal{X}=\{\gamma\} , and their contribution is \sum_{\gamma}z(\gamma) . Among these, the polymers of size 1 are exactly (\{v\},L),\qquad(\{v\},R),\qquad(\{v\},B),\qquad v\in V, with activities a_{L},a_{R},a_{B} . Hence \sum_{|\gamma|=1}z(\gamma)=|V|(a_{L}+a_{R}+a_{B}). So it remains to show that all other contributions are O(|V|\Delta\rho^{2}) . Write \mathcal{R}:=\log Z_{\mathrm{pair}}-|V|(a_{L}+a_{R}+a_{B})=R_{\geq 2}^{(1)}+R_{\mathrm{clust}}, where R_{\geq 2}^{(1)}:=\sum_{|\gamma|\geq 2}z(\gamma) is the contribution of one-polymer clusters of size at least 2 , and R_{\mathrm{clust}} is the sum of all clusters involving at least two polymers. Bound on R_{\geq 2}^{(1)} . Using the same counting estimate as above, \displaystyle\sum_{|\gamma|\geq 2}|z(\gamma)| \displaystyle\leq\sum_{x\in V}\ \sum_{\begin{subarray}{c}\gamma\ni x\\ |\gamma|\geq 2\end{subarray}}|z(\gamma)| \displaystyle\leq|V|\sum_{k\geq 2}(e\Delta)^{k-1}3^{k}\rho^{k} \displaystyle=|V|\,3\rho\sum_{k\geq 2}(3e\Delta\rho)^{k-1}. If c_{\mathrm{KP}} is chosen smaller if necessary, then 3e\Delta\rho\leq 1/2 , and therefore |R_{\geq 2}^{(1)}|\leq C_{1}|V|\,\Delta\,\rho^{2} for an absolute constant C_{1} . Bound on R_{\mathrm{clust}} . A standard corollary of the KP theorem [ 49 ] gives the estimate |R_{\mathrm{clust}}|\leq C_{2}\sum_{\gamma}|z(\gamma)|e^{a(\gamma)}\sum_{\eta\not\sim\gamma}|z(\eta)|e^{a(\eta)}, (32) for an absolute constant C_{2} . Using ( 31 ), \sum_{\eta\not\sim\gamma}|z(\eta)|e^{a(\eta)}\leq C_{0}(\Delta+1)|\gamma|\rho. Therefore |R_{\mathrm{clust}}|\leq C_{3}\Delta\rho\sum_{\gamma}|\gamma|\,|z(\gamma)|e^{|\gamma|}. Now \sum_{\gamma}|\gamma|\,|z(\gamma)|e^{|\gamma|}=\sum_{x\in V}\sum_{\gamma\ni x}|z(\gamma)|e^{|\gamma|}\leq|V|\,C_{0}\,\rho by ( 30 ). Hence |R_{\mathrm{clust}}|\leq C_{4}|V|\,\Delta\,\rho^{2}. Combining the bounds for R_{\geq 2}^{(1)} and R_{\mathrm{clust}} , we obtain |\mathcal{R}|\leq C_{\mathrm{KP}}\,|V|\,\Delta\,\rho^{2} for a suitable absolute constant C_{\mathrm{KP}} , as claimed. ∎ 8.2 Zero-free region and algorithm We now record the zero-free consequence of Theorem 39 . For a holomorphic function f\not\equiv 0 , write N_{f}(r) for the number of zeros of f in \mathbb{D}(0,r) , counted with multiplicity. For a fixed weighted instance W=(W_{v})_{v\in V} , define G_{W}(\lambda):=Z_{G}(\lambda W)=\sum_{I\in\mathcal{I}(G)}\lambda^{|I|}\prod_{v\in I}W_{v}. Since X_{W}(\lambda)=G_{W}(\lambda)\exp\!\Bigl(-\lambda\sum_{v\in V}W_{v}\Bigr), the functions G_{W} and X_{W} have exactly the same zeros. Theorem 42 (Quantitative zero-count bound) . There exist constants c_{\ast}(K),C_{\ast}(K)>0 , depending only on K , such that the following holds. Let G=(V,E) be a finite graph with maximum degree \Delta , and let W_{v} be i.i.d. complex random variables satisfying the assumptions of Theorem 39 . Let 00 . Let G_{n}=(V_{n},E_{n}) be a sequence of finite graphs with maximum degree \Delta_{n} , and assume \mathbb{P}\!\left[Z_{G_{n}}(\lambda W)\text{ has a zero in }\mathbb{D}\!\bigl(0,(1-\varepsilon/2)R_{n}\bigr)\right]=O_{\varepsilon,K}\!\left(M_{n}^{-4\beta}\right), where M_{n}:=(1+\Delta_{n})|V_{n}|,\qquad R_{n}:=\frac{1}{\sqrt{\nu}}\,M_{n}^{-1/4-\beta}. Then with probability 1-O_{\varepsilon,K}\!\left(M_{n}^{-4\beta}\right), the following holds simultaneously for every \lambda\in\mathbb{C} such that |\lambda|\leq(1-\varepsilon)\frac{1}{\sqrt{\nu}}\,M_{n}^{-1/4-2\beta}. There is a deterministic algorithm which outputs an |V_{n}|^{-\gamma} -additive approximation to the branch of \log Z_{G_{n}}(\lambda W) determined by \log Z_{G_{n}}(0)=0 , in time \min\!\Bigl\{\,|V_{n}|^{\,O(m)},\;|V_{n}|\,\exp\!\bigl(O_{\Delta_{n}}(m)\bigr)\Bigr\},\qquad m=\Bigl\lceil\frac{\gamma+1}{\beta}\Bigr\rceil. Equivalently, since X_{W}(\lambda) differs from Z_{G_{n}}(\lambda W) by a known exponential factor, the same holds for \log X_{W}(\lambda) . Proof. On the event that Z_{G_{n}}(\lambda W) is zero-free on \mathbb{D}(0,(1-\varepsilon/2)R_{n}) , there is a holomorphic branch f(\lambda):=\log Z_{G_{n}}(\lambda W)=\sum_{k\geq 1}a_{k}\lambda^{k} on that disk, normalized by f(0)=0 . Now fix \lambda with |\lambda|\leq L_{n}:=(1-\varepsilon)\frac{1}{\sqrt{\nu}}\,M_{n}^{-1/4-2\beta}. Then \frac{|\lambda|}{(1-\varepsilon/2)R_{n}}=\frac{1-\varepsilon}{1-\varepsilon/2}\,M_{n}^{-\beta}=\rho_{\varepsilon}M_{n}^{-\beta},\qquad\rho_{\varepsilon}:=\frac{1-\varepsilon}{1-\varepsilon/2}<1. Let T_{m}(\lambda):=\sum_{k=1}^{m}a_{k}\lambda^{k} be the degree- m truncation of the Taylor series of f . By the standard Barvinok interpolation estimate, |f(\lambda)-T_{m}(\lambda)|\leq\frac{|V_{n}|}{m+1}\,\frac{(\rho_{\varepsilon}M_{n}^{-\beta})^{m+1}}{1-\rho_{\varepsilon}M_{n}^{-\beta}}. Choose m=\left\lceil\frac{\gamma+1}{\beta}\right\rceil. Since M_{n}\geq|V_{n}| , for all sufficiently large n , \frac{|V_{n}|}{m+1}\,\frac{(\rho_{\varepsilon}M_{n}^{-\beta})^{m+1}}{1-\rho_{\varepsilon}M_{n}^{-\beta}}\leq C_{\varepsilon,\beta,\gamma}\,|V_{n}|\,M_{n}^{-\beta(m+1)}\leq|V_{n}|^{-\gamma}. Hence |\log Z_{G_{n}}(\lambda W)-T_{m}(\lambda)|\leq|V_{n}|^{-\gamma}. It remains to compute T_{m} , equivalently the first m Taylor coefficients of \log Z_{G_{n}}(\lambda W) . For the general graph G_{n} , write Z_{G_{n}}(\lambda W)=\sum_{k=0}^{|V_{n}|}b_{k}\lambda^{k},\qquad b_{k}=\sum_{\begin{subarray}{c}I\in\mathcal{I}(G_{n})\\ |I|=k\end{subarray}}\prod_{v\in I}W_{v}. Thus b_{0},\dots,b_{m} can be computed exactly by enumerating all subsets of size at most m and checking independence, which takes time |V_{n}|^{O(m)} . The coefficients a_{1},\dots,a_{m} are then recovered recursively from k\,b_{k}=\sum_{j=1}^{k}j\,a_{j}\,b_{k-j},\qquad k\geq 1, with b_{0}=1 . On the other hand, for bounded-degree graphs one may instead use the standard bounded-degree coefficient algorithm for independence polynomials, which computes the first m coefficients in time |V_{n}|\,\exp\!\bigl(O_{\Delta_{n}}(m)\bigr); see [ 9 , 47 ] . Therefore the first m coefficients, and hence T_{m}(\lambda) , can be computed deterministically in time \min\!\Bigl\{\,|V_{n}|^{\,O(m)},\;|V_{n}|\,\exp\!\bigl(O_{\Delta_{n}}(m)\bigr)\Bigr\}. This gives the claimed approximation algorithm. ∎ 9 Stability, hardness, and anticoncentration 9.1 Optimized permanent hardness reduction from [ 26 ] In Theorem 22 of [ 26 ] , the authors formally showed that being able to approximate the permanent of a random matrix with mean of order o(1/n) implies a good approximation for the permanent of a random matrix with zero mean. By slightly optimizing their analysis, we can see that the same result holds if the mean is of order o(1/\sqrt{n}) . For completeness, we formally state and prove the optimized version. Theorem 45 . Let \Delta=\per(W+J\mu)-\per(W) , where W is a matrix with i.i.d. entries of mean zero and variance one, and suppose that |\mu|=\frac{c}{\sqrt{n}} for some c<1 . Then \mathbb{E}|\Delta|^{2}\leq(n!)\frac{c^{2}}{1-c^{2}} so by Markov’s inequality, for any t>0 \Pr\left(|\Delta|^{2}>(n!)\frac{c^{2}t}{1-c^{2}}\right)\leq 1/t. Proof. By direct computation (see Lemma 23 of [ 26 ] ), one obtains \mathbb{E}|\Delta|^{2}=(n!)^{2}\sum_{k=1}^{n}\frac{|\mu|^{2k}}{(n-k)!}, and then we conclude \mathbb{E}|\Delta|^{2}\leq(n!)^{2}\sum_{k=1}^{n}\frac{|\mu|^{2k}}{(n-k)!}=(n!)\sum_{k=1}^{n}|\mu|^{2k}n(n-1)\cdots(n-k+1)\leq(n!)\sum_{k=1}^{n}(|\mu|^{2}n)^{k}\leq(n!)\frac{c^{2}}{1-c^{2}} by summing the geometric series. ∎ Since \mathbb{E}|\per(W)|^{2}=n! , if we can take c=o(1) in this theorem we directly get an additive approximation to the permanent of W which is o(1) standard deviations away from the truth. See [ 1 , 26 ] for discussion of further reductions under conjectured anticoncentration of the permanent. 9.2 Anticoncentration conjecture and zeros This section serves as a kind of “warm-up” to the next one, where we prove a related unconditional result. Here, we show that under the standard anti-concentration conjecture for the permanent [ 1 ] , only O_{\epsilon}(\log n) many of the zeros of the permanent \per(W+zJ) are within a ball of radius (1-\epsilon)\sqrt{1/n} around the origin. Combined with our previous (unconditional) analysis, this tells us that under the PACC the bulk of the zeros, i.e. n-o(n) many of them, are at scale \sqrt{1/n} . Because the PACC is specific to the case where W is an n\times n matrix with N(0,1)_{\mathbb{C}} entries, in this section we focus on the complex Gaussian case. Conjecture 46 (Permanent Anti-Concentration Conjecture (PACC) [ 1 ] ) . There exists a polynomial p such that for all n and \delta>0 , \Pr(|\per(W)|<\frac{\sqrt{n!}}{p(n,1/\delta)})<\delta. where W is an n\times n matrix with i.i.d. N(0,1)_{\mathbb{C}} entries. It follows from the work of Tao and Vu [ 61 , 62 ] that with probability at least 1-o(1) , \log|\per(W)|=(n/2)\log(n)\pm o(n\log(n)). The difficulty in analyzing the scale of \log|\per(W)| is the lower-tail bound rather than the upper-tail. For the upper tail, we have \mathbb{E}|\per(W)|^{2}=n! , so by Markov’s inequality \Pr(|per(W)|^{2}\geq n!/\delta)\leq\delta ). So, under the PACC we have the much more precise asymptotic \log|\per(W)|=(1/2)\log(n!)\pm O(\log(n/\delta))=(1/2)(n\log n-n)\pm O(\log(n/\delta)) (33) with probability at least 1-\delta . Here the second equality is Stirling’s approximation. If we assume this asymptotic holds, we can prove a strong anticoncentration result for the zeros of the permanent: Theorem 47 . Suppose that the PACC conjecture holds. Let n(r) be the number of zeros of the function \per(W+Jz/\sqrt{n}) with |z|R>r , it holds with probability 1-\delta that n(r)\leq\frac{-\log(1-R^{2})}{2\log(R/r)}+O(\log(n/\delta)/\log(R/r)). In particular, by taking R=(1+r)/2 , this yields that n(r)=O_{r}(\log(n/\delta)) for any r<1 . Proof. By Jensen’s formula, we have for any R>r that n(r)\log(R/r)\leq\frac{1}{2\pi}\int_{0}^{2\pi}\log|\per(W+JRe^{i\theta}/\sqrt{n})|d\theta-\log|\per(W)|. By Jensen’s inequality, n(r)\log(R/r)\leq\log\frac{1}{2\pi}\int_{0}^{2\pi}|\per(W+JRe^{i\theta}/\sqrt{n})|d\theta-\log|\per(W)| (34) By Markov’s inequality, \Pr\left(\frac{1}{2\pi}\int_{0}^{2\pi}|\per(W+JRe^{i\theta}/\sqrt{n})|d\theta>\frac{t}{2\pi}\int_{0}^{2\pi}\mathbb{E}|\per(W+JRe^{i\theta}/\sqrt{n})|d\theta\right)\leq 1/t where the randomness is over the matrix W . Letting \Delta_{\theta}=\per(W+JRe^{i\theta}/\sqrt{n})-\per(W) , we can compute that under the requirement 1>R>r , \displaystyle\frac{1}{2\pi}\int_{0}^{2\pi}\mathbb{E}|\per(W)+\Delta_{\theta}|d\theta \displaystyle\leq\sqrt{\frac{1}{2\pi}\int_{0}^{2\pi}\mathbb{E}|\per(W)+\Delta_{\theta}|^{2}d\theta} (35) \displaystyle=\sqrt{\frac{1}{2\pi}\int_{0}^{2\pi}[\mathbb{E}|\per(W)|^{2}+\mathbb{E}|\Delta_{\theta}|^{2}]d\theta} (36) \displaystyle\leq\sqrt{n![1+R^{2}/(1-R^{2})]}=\sqrt{n!/(1-R^{2})} (37) where we used that \frac{1}{2\pi}\int\Delta_{\theta}=0 to show the crossterm is zero, and then we used that \mathbb{E}|\per(W)|^{2}=n! and Theorem 45 . So setting t=2/\delta , we have with probability at least 1-\delta/2 that \frac{1}{2\pi}\int_{0}^{2\pi}|\per(W+JRe^{i\theta}/\sqrt{n})|d\theta\leq\frac{2}{\delta}\sqrt{n!/(1-R^{2})}. Under this event, we therefore have n(r)\log(R/r)\leq\log(2/\delta)+\frac{\log(n!)-\log(1-R^{2})}{2}-\log|\per(W)|. Now assuming the PACC, we can use the asymptotic ( 33 ) to get n(r)\log(R/r)\leq\frac{-\log(1-R^{2})}{2}+O(\log(n/\delta)) as desired. ∎ Recall that by the fundamental theorem of algebra, the polynomial \per(W+Jz/\sqrt{n}) must have n zeros (counted with multiplicity). Corollary 48 . Under the PACC, with probability at least 1-\delta the bulk of the zeros (i.e., 1-o(1) portion of the n total zeros) of \per(W+Jz/\sqrt{n}) lie in the annulus \{z:|z|\in(1-o(1),O_{\delta}(1))\} Proof. Combine the previous theorem with Markov’s inequality applied to the basic estimate discussed in Section 2 (which follows from our results, but for which the results of [ 26 ] are also sufficient). ∎ 9.3 Unconditional anticoncentration for zeros We can prove an unconditional variant of the anticoncentration of zeros based on the following inductive argument. Lemma 49 . Let W_{n} be an n\times n matrix with i.i.d. complex Gaussian entries W_{ij}\sim\mathcal{CN}(0,1) , and define Z_{n}:=\per(W_{n}). Then for every n\geq 1 , \mathbb{E}\log|Z_{n}|^{2}\geq\log(n!)-\gamma n, where \gamma\approx 0.577 denotes Euler’s constant. Proof. We argue by recursion. Expanding the permanent along the last row, Z_{n}=\sum_{j=1}^{n}W_{nj}C_{j}, where C_{j} is the permanent of the (n-1)\times(n-1) minor obtained by deleting row n and column j . Conditional on the first n-1 rows, the cofactors C_{1},\dots,C_{n} are deterministic complex numbers, while the last-row entries W_{n1},\dots,W_{nn} remain independent \mathcal{CN}(0,1) random variables. Since Z_{n}=\sum_{j=1}^{n}W_{nj}C_{j}, it follows that Z_{n}\mid\mathcal{F}_{n-1} is a complex Gaussian random variable. Indeed, a linear combination of independent centered complex Gaussians is again centered complex Gaussian, and \mathbb{E}\!\left[Z_{n}\mid\mathcal{F}_{n-1}\right]=0, while \mathbb{E}\!\left[|Z_{n}|^{2}\mid\mathcal{F}_{n-1}\right]=\sum_{j,k=1}^{n}C_{j}\overline{C_{k}}\,\mathbb{E}\!\left[W_{nj}\overline{W_{nk}}\right]=\sum_{j=1}^{n}|C_{j}|^{2}=:S_{n}, because \mathbb{E}[W_{nj}\overline{W_{nk}}]=\delta_{jk} . Thus Z_{n}\,\big|\,\mathcal{F}_{n-1}\sim\mathcal{CN}(0,S_{n}). Now if G\sim\mathcal{CN}(0,1) , then Z_{n}\mid\mathcal{F}_{n-1} has the same law as \sqrt{S_{n}}\,G . Therefore \log|Z_{n}|^{2}=\log S_{n}+\log|G|^{2}\qquad\text{in distribution conditional on }\mathcal{F}_{n-1}. Taking conditional expectation gives \mathbb{E}\!\left[\log|Z_{n}|^{2}\mid\mathcal{F}_{n-1}\right]=\log S_{n}+\mathbb{E}\log|G|^{2}. Finally, since G\sim\mathcal{CN}(0,1) , the random variable |G|^{2} is exponential with mean 1 , so \mathbb{E}\log|G|^{2}=\int_{0}^{\infty}(\log x)e^{-x}\,dx=-\gamma. Hence \mathbb{E}\!\left[\log|Z_{n}|^{2}\mid\mathcal{F}_{n-1}\right]=\log S_{n}-\gamma. Taking expectation gives \mathbb{E}\log|Z_{n}|^{2}=-\gamma+\mathbb{E}\log S_{n}. Now by concavity of \log , \log S_{n}=\log\!\left(\sum_{j=1}^{n}|C_{j}|^{2}\right)\geq\frac{1}{n}\sum_{j=1}^{n}\log\bigl(n|C_{j}|^{2}\bigr)=\log n+\frac{1}{n}\sum_{j=1}^{n}\log|C_{j}|^{2}. Taking expectation and using that each C_{j} has the same distribution as \per(W_{n-1}) , we obtain \mathbb{E}\log|Z_{n}|^{2}\geq-\gamma+\log n+\mathbb{E}\log|Z_{n-1}|^{2}. Iterating from 1 to n , and using Z_{1}=W_{11} with \mathbb{E}\log|Z_{1}|^{2}=\mathbb{E}\log|W_{11}|^{2}=-\gamma, yields \mathbb{E}\log|Z_{n}|^{2}\geq\sum_{k=1}^{n}(\log k-\gamma)=\log(n!)-\gamma n. ∎ Theorem 50 . Let f_{n}(z):=\per\!\left(W+\frac{z}{\sqrt{n}}J\right), where W is an n\times n matrix with i.i.d. complex Gaussian entries W_{ij}\sim\mathcal{CN}(0,1) , and J is the all-ones matrix. Let n(r) denote the number of zeros of f_{n} in the disk \{z:|z|0 such that for every r\in(0,r_{0}) , there exists N=N(\varepsilon,\eta,r) with the following property: for all n\geq N , \Pr\!\bigl(n(r)\leq\varepsilon n\bigr)\geq 1-\eta. Proof. Fix \varepsilon,\eta\in(0,1) , and set R:=\frac{1}{2} . Let 0\frac{\gamma}{2\varepsilon\eta}. Then for every r\in(0,r_{0}) , \frac{\gamma/2}{\log(1/(2r))}<\varepsilon\eta. Since \frac{1}{2}\log\frac{4}{3} is a constant, for each such r there exists N=N(\varepsilon,\eta,r) such that for all n\geq N , \mathbb{E}\,n(r)\leq\varepsilon\eta\,n. The conclusion follows from Markov’s inequality. ∎ Acknowledgements. Some simulations were performed on the University of Chicago’s Data Science Institute cluster. Appendix A Numerical simulations Zeros. In Figure 3 , we located the zeros of the (rescaled) random polynomial z\mapsto\operatorname{per}(zJ/\sqrt{n}+W) (41) by computing the magnitude of the permanent via Ryser’s exact formula [ 53 ] , for small values of n . Here J is the all-ones matrix and W is an n\times n random matrix with standard complex Gaussian entries. For each size n , we ran 3 independent simulations which correspond to the rows of the figure. All computations were executed at 64-bit floating point precision. As we can see from the figure, in the experiments all of the zeros of ( 41 ) had real and imaginary parts of magnitude at most 3 . Recall from the discussion in Section 2 that asymptotically as n\to\infty , all but o(1) fraction of the zeros of ( 41 ) must be magnitude O(1) , which is the motivation for the 1/\sqrt{n} scaling factor. Figure 3: Complex magnitude of the n\times n permanent ( 41 ) with random complex Gaussian entries. Colors correspond to the log-magnitude of the permanent at a particular point in \mathbb{C} , with dark blue corresponding to smaller permanents (more negative log-permanent) and bright yellow to larger values (more positive log-permanent). In each case, the locations of the zeros can be visually seen as dark-blue dots in the plot. We also performed the same experiment with complex Laplace (symmetrical exponential) distributed entries, instead of Gaussian. The results are similar to the Gaussian case. In Figure 5 , we show the results with real i.i.d. Gaussian entries, which exhibit reflection symmetry across the real-axis but otherwise broadly appear similar. Figure 4: Complex magnitude of the n\times n permanent ( 41 ) with random complex Laplace entries. As before, the zeros are visible as dark blue dots. The results appear qualitatively similar to the Gaussian case (Figure 3 ). Figure 5: Complex magnitude of the n\times n permanent ( 41 ) with real Gaussian entries. As before, the zeros are visible as dark blue dots. Because the coefficients are real-valued, and therefore invariant under complex conjugation (which maps i to -i ), the roots exhibit symmetry across the real axis. Figure 6: Relative error of the Taylor series approximation ( 42 ) for \per(zJ/\sqrt{n}+A) as a function of the complex parameter z ( n=14 ). Each subplot represents an increasing degree of the Taylor series approximation (0 through 9) about z=\infty . The color scale is logarithmic, representing the relative deviation |1-\per_{\text{approx}}/\per_{\text{exact}}| . Remark 51 . If we consider the analogue of ( 41 ) with determinant instead of permanent, we will see totally different behavior. By the determinant rank-one update formula, \det(zJ/\sqrt{n}+W)=\det(W)(1+z\operatorname{Tr}(JW^{-1})/\sqrt{n}) so the determinantal version is a degree-one polynomial — it has one zero instead of n . Error of Taylor series approximation. The approximation to ( 41 ) is calculated by rewriting the log-permanent in terms of w=1/z : \log\per\left(z\frac{J}{\sqrt{n}}+A\right)=n\log z+\log\per\left(\frac{J}{\sqrt{n}}+wA\right) (42) The second term is expanded as a Taylor series in w around the value 0 (which corresponds to z=\infty ). Truncating this series at degree D yields: \log\per\left(\frac{J}{\sqrt{n}}+wA\right)\approx\log\left(\frac{n!}{n^{n/2}}\right)+\sum_{k=1}^{D}q_{k}w^{k} (43) where the coefficients q_{k} are computed using the sum of k\times k subpermanents of A . As illustrated in Figure 6 , the Taylor series approximation exhibits a distinct convergence region that expands as the degree of the expansion increases. Because the approximation is derived as an expansion in powers of 1/z , the relative error is negligible for large |z| , but diverges significantly as z approaches the origin. Specifically, the dark purple regions indicate areas where the approximation achieves high precision, while the bright yellow center denotes the singularity where the 1/z terms dominate, leading to a breakdown of the polynomial fit. Notably, by increasing the degree from 0 to 9, the radius of the reliable convergence zone grows, allowing for accurate permanent estimation progressively closer to the center of the complex plane, but this region can never expand beyond the permanental zeros. Appendix B Connection to Bethe approximation heuristic This section is mostly of interest to those familiar with Bethe approximation. We explain a loose connection between our second-order reweighting and the Bethe approximation to the permanent, in that the reweighting is close to a formal second-order Taylor series expansion of the Bethe approximation. We include this since there has been a lot of study of Bethe approximation in the specific context of the permanent, and there are connections between Bethe approximation and diagrammatic expansions [ 63 ] . We otherwise do not use Bethe approximation in any way. B.1 A brief introduction to the Bethe approximation The permanent of a nonnegative n\times n matrix \theta=(\theta_{ij}) can be viewed as the partition function of the perfect matching model on the complete bipartite graph K_{n,n} : \per(\theta)=\sum_{\sigma\in S_{n}}\prod_{i=1}^{n}\theta_{i,\sigma(i)}. The Bethe approximation is a standard mean-field approximation to such partition functions. For the permanent, it can be formulated variationally over the Birkhoff polytope \Gamma_{n}:=\Bigl\{\gamma=(\gamma_{ij})\in\mathbb{R}_{\geq 0}^{n\times n}:\sum_{j}\gamma_{ij}=1\ \forall i,\ \sum_{i}\gamma_{ij}=1\ \forall j\Bigr\}, whose elements may be interpreted as “soft” doubly stochastic approximations to permutation matrices. For a positive matrix \theta , the Bethe free energy is F_{B}(\gamma;\theta):=-\sum_{i,j}\gamma_{ij}\log\theta_{ij}+\sum_{i,j}\gamma_{ij}\log\gamma_{ij}-\sum_{i,j}(1-\gamma_{ij})\log(1-\gamma_{ij}),\qquad\gamma\in\Gamma_{n}. (44) One then defines the Bethe permanent by \per_{B}(\theta):=\exp\!\Bigl(-\inf_{\gamma\in\Gamma_{n}}F_{B}(\gamma;\theta)\Bigr). B.2 Quadratic expansion of Bethe approximation We now consider a perturbation A=J+H with J the all-ones matrix and H small. For the purpose of the heuristic calculation, we will allow H to be complex-valued, even though this is not so consistent with the variational interpretation. If H=0 , then A=J is maximally symmetric, and the corresponding Bethe variational problem is symmetric under permutations of rows and columns. The distinguished point in the Birkhoff polytope is therefore the uniform doubly stochastic matrix \gamma_{0}:=\frac{1}{n}J. This is the natural mean-field candidate around which to linearize. To compare with our exact second derivative, it is convenient to introduce \Phi_{B}(\gamma;A):=-F_{B}(\gamma;A)=\sum_{i,j}\gamma_{ij}\log A_{ij}-\sum_{i,j}\gamma_{ij}\log\gamma_{ij}+\sum_{i,j}(1-\gamma_{ij})\log(1-\gamma_{ij}). Then \log\per_{B}(A)=\sup_{\gamma\in\Gamma_{n}}\Phi_{B}(\gamma;A). A tangent vector to the Birkhoff polytope at \gamma_{0} has the form u\in\mathbb{R}^{n\times n},\qquad u\mathbf{1}=0,\qquad\mathbf{1}^{T}u=0. Thus the tangent space is exactly the subspace \mathcal{H}_{m}=\{M\in\mathbb{R}^{n\times n}:M\mathbf{1}=0,\ \mathbf{1}^{T}M=0\} that also appears in our exact decomposition. In particular, if \gamma=\gamma_{0}+u , then the free variational directions live only in \mathcal{H}_{m} . Quadratic expansion of the Bethe functional. Let f(x):=-x\log x+(1-x)\log(1-x). Then the entropy part of \Phi_{B} is \sum_{i,j}f(\gamma_{ij}) , and f^{\prime}(x)=-\log x-\log(1-x)-2,\qquad f^{\prime\prime}(x)=-\frac{1}{x}+\frac{1}{1-x}. Evaluating at x=1/n gives f^{\prime\prime}(1/n)=-n+\frac{n}{n-1}=-\frac{n(n-2)}{n-1}. It is therefore convenient to set q_{n}:=-f^{\prime\prime}(1/n)=\frac{1}{1/n}-\frac{1}{1-1/n}=n-\frac{n}{n-1}=\frac{n(n-2)}{n-1}. Now write L:=\log A noting that here we are taking the entrywise logarithm , so L=H-\frac{1}{2}H^{\circ 2}+O(\|H\|^{3}). Expanding \Phi_{B} around \gamma_{0} , we obtain \Phi_{B}(\gamma_{0}+u;A)=\Phi_{B}(\gamma_{0};A)+\langle u,L\rangle-\frac{q_{n}}{2}\|u\|_{F}^{2}+O(\|u\|^{3}). Since u\in\mathcal{H}_{m} , only the \mathcal{H}_{m} -component of L couples: \langle u,L\rangle=\langle u,P_{m}L\rangle. “Optimizing” the quadratic approximation over u\in\mathcal{H}_{m} by setting the derivative to zero gives u_{*}=\frac{1}{q_{n}}P_{m}L+O(\|L\|^{2}), and therefore \log\per_{B}(J+H)-\log\per_{B}(J)=\frac{1}{n}\sum_{i,j}L_{ij}+\frac{1}{2q_{n}}\|P_{m}L\|_{F}^{2}+O(\|H\|^{3}). Substituting L=H-\frac{1}{2}H^{\circ 2}+O(\|H\|^{3}) and keeping only quadratic terms yields \log\per_{B}(J+H)-\log\per_{B}(J)=\frac{1}{n}\sum_{i,j}H_{ij}-\frac{1}{2n}\sum_{i,j}H_{ij}^{2}+\frac{1}{2q_{n}}\|P_{m}H\|_{F}^{2}+O(\|H\|^{3}). Since \|H\|_{F}^{2}=\|P_{\parallel}H\|_{F}^{2}+\|P_{m}H\|_{F}^{2}, we can rewrite this as \log\per_{B}(J+H)-\log\per_{B}(J)=\frac{1}{n}\sum_{i,j}H_{ij}+\frac{1}{2}\big\langle H,\,\Bigl(-\frac{1}{n}P_{\parallel}+\Bigl(-\frac{1}{n}+\frac{1}{q_{n}}\Bigr)P_{m}\Bigr)H\big\rangle+O(\|H\|^{3}). Using \frac{1}{q_{n}}=\frac{n-1}{n(n-2)},\qquad-\frac{1}{n}+\frac{1}{q_{n}}=\frac{1}{n(n-2)}, the prediction for the quadratic operator is B_{\mathrm{Bethe}}=-\frac{1}{n}P_{\parallel}+\frac{1}{n(n-2)}P_{m}. (45) Comparison with the exact second derivative. By direct combinatorial computation, our exact second derivative at J is B_{\mathrm{exact}}=-\frac{1}{n}P_{\parallel}+\frac{1}{n(n-1)}P_{m}. (46) Comparing ( 45 ) and ( 46 ), we find: • the expansion of the Bethe heuristic around the saddle point J predicts the same splitting \mathbb{C}^{n\times n}=\mathcal{H}_{0}\oplus\mathcal{H}_{r}\oplus\mathcal{H}_{c}\oplus\mathcal{H}_{m}; • it gets the coefficient of P_{\parallel} exactly right; • For \mathcal{H}_{m} , it predicts \frac{1}{n(n-2)}\quad\text{instead of the exact}\quad\frac{1}{n(n-1)}. Of course, these two quantities are quite close for large n . Appendix C Low-degree coefficient bounds The following coefficient bounds for the low-degree terms in the taylor series of \log Z are not used in the proofs for zero-free regions. They can be helpful to optimize the precise degree of truncation needed for our algorithm. The proofs are much shorter and more elegant in the hardcore model, where the bounds are a simple consequence of the cluster expansion formula. For the permanent, the series expansion of \log Z is approximately given by a similar formula (recall the connection from the Overview) so intuitively similar bounds should still hold; making this precise requires a lot more work. C.1 Lattice animal bound The following lemma is a standard counting estimate which is used in polymer expansion arguments (see, e.g., [ 27 , 49 ] ). We give a self-contained proof below. Lemma 52 . Let G=(V,E) be a finite graph on n vertices with maximum degree at most \Delta . For s\geq 1 , let N_{s}(G) denote the number of connected vertex subsets U\subseteq V with |U|=s . Then N_{s}(G)\leq n\,(e\Delta)^{s-1}. More precisely, for each fixed vertex v\in V , the number of connected sets U\subseteq V such that v\in U and |U|=s is at most \frac{1}{s}\binom{\Delta s}{s-1}\leq(e\Delta)^{s-1}. Proof. Fix a vertex v\in V , and let \mathcal{C}_{s}(v) denote the collection of connected vertex sets U\subseteq V with v\in U and |U|=s . It suffices to show that |\mathcal{C}_{s}(v)|\leq\frac{1}{s}\binom{\Delta s}{s-1}. For each U\in\mathcal{C}_{s}(v) , choose a spanning tree T_{U} of the induced subgraph G[U] , rooted at v . We now encode T_{U} by a word of length \Delta s containing exactly s-1 ones. Consider the rooted tree T_{U} . List the vertices of U in the order in which they are first discovered by a depth-first search starting from v . Every vertex other than v has a unique parent in T_{U} , so T_{U} has exactly s-1 oriented tree edges pointing from a parent to a child. For each vertex x\in U , choose once and for all an ordering of the at most \Delta incident edges of G . Thus the set U contributes s vertex slots, each with at most \Delta possible edge positions, for a total of at most \Delta s positions. Mark those positions corresponding to the s-1 parent-to-child edges of T_{U} . This produces a 0 - 1 word of length at most \Delta s with exactly s-1 ones. This encoding is injective once the root v is fixed: indeed, from the marked positions one recovers, for each discovered vertex, which children it has in the rooted tree and in which order they are explored, hence the whole rooted tree T_{U} , and therefore also its vertex set U . Accordingly, |\mathcal{C}_{s}(v)|\leq\binom{\Delta s}{s-1}. To gain the extra factor 1/s , note that in the above exploration code every connected set U\in\mathcal{C}_{s}(v) is counted at least s times when one allows the root to vary over the s vertices of U . Equivalently, summing the rooted count over all v\in U overcounts each connected set of size s by exactly s . Hence the number of connected sets of size s is N_{s}(G)=\frac{1}{s}\sum_{v\in V}|\mathcal{C}_{s}(v)|\leq\frac{n}{s}\binom{\Delta s}{s-1}. In particular, for each fixed v , |\mathcal{C}_{s}(v)|\leq\frac{1}{s}\binom{\Delta s}{s-1}. Finally, using the standard binomial estimate \binom{M}{k}\leq(eM/k)^{k} , we obtain \frac{1}{s}\binom{\Delta s}{s-1}\leq\frac{1}{s}\left(\frac{e\Delta s}{s-1}\right)^{s-1}\leq(e\Delta)^{s-1}, since s\leq 2(s-1) for s\geq 2 , and the case s=1 is trivial. Therefore N_{s}(G)\leq n\,(e\Delta)^{s-1}, as claimed. ∎ C.2 Hardcore model Lemma 53 (Explicit second-moment bound for the k th cluster coefficient) . Let G=(V,E) be a finite graph with |V|=n and maximum degree at most \Delta\geq 2 . Let (W_{v})_{v\in V} be i.i.d. standard complex Gaussians, W_{v}\sim\mathcal{N}_{\mathbb{C}}(0,1) , and define random fugacities \lambda_{v}=\lambda W_{v} . Write the cluster expansion of the hardcore partition function as \log Z(\lambda W)=\sum_{k\geq 1}a_{k}\lambda^{k}, where a_{k}=\sum_{|\mathbf{m}|=k}\frac{1}{\mathbf{m}!}\,\phi(H[\mathbf{m}])\prod_{v\in V}W_{v}^{m_{v}}. Then for every integer k\geq 1 , \mathbb{E}|a_{k}|^{2}\leq\frac{1}{e\sqrt{2}}\,n\,\Delta^{k-1}\,k^{2k-4}\Bigl(\frac{2e}{\log 2}\Bigr)^{k}\leq n\,\Delta^{k-1}\,k^{2k}\Bigl(\frac{3e}{\log 2}\Bigr)^{k} Proof. By definition, a_{k}=\sum_{|\mathbf{m}|=k}c_{\mathbf{m}}\prod_{v\in V}W_{v}^{m_{v}},\qquad c_{\mathbf{m}}:=\frac{1}{\mathbf{m}!}\phi(H[\mathbf{m}]). Hence \mathbb{E}|a_{k}|^{2}=\sum_{|\mathbf{m}|=k}\sum_{|\mathbf{m}^{\prime}|=k}c_{\mathbf{m}}\overline{c_{\mathbf{m}^{\prime}}}\,\mathbb{E}\!\left[\prod_{v\in V}W_{v}^{m_{v}}\overline{W_{v}}^{\,m_{v}^{\prime}}\right]. Since the variables (W_{v}) are independent and rotationally invariant, \mathbb{E}\!\left[W_{v}^{p}\overline{W_{v}}^{\,q}\right]=0\qquad\text{unless }p=q. Therefore all off-diagonal terms vanish, and we obtain \mathbb{E}|a_{k}|^{2}=\sum_{|\mathbf{m}|=k}\frac{|\phi(H[\mathbf{m}])|^{2}}{(\mathbf{m}!)^{2}}\prod_{v\in V}\mathbb{E}|W_{v}|^{2m_{v}}. For a standard complex Gaussian W\sim\mathcal{N}_{\mathbb{C}}(0,1) , \mathbb{E}|W|^{2r}=r! for any r\geq 0 . Thus \mathbb{E}|a_{k}|^{2}=\sum_{|\mathbf{m}|=k}|\phi(H[\mathbf{m}])|^{2}\prod_{v:m_{v}>0}\frac{1}{m_{v}!}. Now group the sum according to the support S=\{v\in V:m_{v}>0\},\qquad s:=|S|. If H[\mathbf{m}] is connected, then G[S] must also be connected, since an edge of H[\mathbf{m}] only joins copies of equal or adjacent vertices in G . Therefore \mathbb{E}|a_{k}|^{2}\leq\sum_{s=1}^{k}\sum_{\begin{subarray}{c}S\subseteq V\\ |S|=s\\ G[S]\text{ connected}\end{subarray}}\ \sum_{\begin{subarray}{c}(m_{v})_{v\in S}\in\mathbb{Z}_{\geq 1}^{S}\\ \sum_{v\in S}m_{v}=k\end{subarray}}|\phi(H[\mathbf{m}])|^{2}\prod_{v\in S}\frac{1}{m_{v}!}. For each such \mathbf{m} , the graph H[\mathbf{m}] has exactly k vertices counting multiplicity. By the spanning tree bound (Lemma 6 ), |\phi(H[\mathbf{m}])|\leq k^{k-2}. Hence \mathbb{E}|a_{k}|^{2}\leq k^{2k-4}\sum_{s=1}^{k}N_{s}(G)\sum_{\begin{subarray}{c}m_{1},\dots,m_{s}\geq 1\\ m_{1}+\cdots+m_{s}=k\end{subarray}}\frac{1}{m_{1}!\cdots m_{s}!}, where N_{s}(G) is the number of connected vertex subsets of G of size s . Next, we bound N_{s}(G) . A standard exploration argument (Lemma 52 ) yields N_{s}(G)\leq n\,(e\Delta)^{s-1}. Substituting, \mathbb{E}|a_{k}|^{2}\leq n\,k^{2k-4}\sum_{s=1}^{k}(e\Delta)^{s-1}\sum_{\begin{subarray}{c}m_{1},\dots,m_{s}\geq 1\\ m_{1}+\cdots+m_{s}=k\end{subarray}}\frac{1}{m_{1}!\cdots m_{s}!}. Since s\leq k , we may bound (e\Delta)^{s-1}\leq(e\Delta)^{k-1} , obtaining \mathbb{E}|a_{k}|^{2}\leq n\,\Delta^{k-1}\,e^{k-1}\,k^{2k-4}\sum_{s=1}^{k}\sum_{\begin{subarray}{c}m_{1},\dots,m_{s}\geq 1\\ m_{1}+\cdots+m_{s}=k\end{subarray}}\frac{1}{m_{1}!\cdots m_{s}!}. It remains to estimate the composition sum. Define b_{k}:=\sum_{s=1}^{k}\sum_{\begin{subarray}{c}m_{1},\dots,m_{s}\geq 1\\ m_{1}+\cdots+m_{s}=k\end{subarray}}\frac{1}{m_{1}!\cdots m_{s}!}. Its generating function is \sum_{k\geq 1}b_{k}x^{k}=\sum_{s\geq 1}\Bigl(\sum_{m\geq 1}\frac{x^{m}}{m!}\Bigr)^{s}=\sum_{s\geq 1}(e^{x}-1)^{s}=\frac{e^{x}-1}{2-e^{x}}. Fix r:=\frac{\log 2}{2}. Since the power series has nonnegative coefficients, Cauchy’s estimate gives b_{k}\leq\frac{1}{r^{k}}\,\frac{e^{r}-1}{2-e^{r}}. Now e^{r}=\sqrt{2} , so \frac{e^{r}-1}{2-e^{r}}=\frac{\sqrt{2}-1}{2-\sqrt{2}}=\frac{1}{\sqrt{2}}. Therefore b_{k}\leq\frac{1}{\sqrt{2}}\Bigl(\frac{2}{\log 2}\Bigr)^{k}. Substituting this bound, \mathbb{E}|a_{k}|^{2}\leq n\,\Delta^{k-1}\,e^{k-1}\,k^{2k-4}\,\frac{1}{\sqrt{2}}\Bigl(\frac{2}{\log 2}\Bigr)^{k}=\frac{1}{e\sqrt{2}}\,n\,\Delta^{k-1}\,k^{2k-4}\Bigl(\frac{2e}{\log 2}\Bigr)^{k}. This proves the first bound. The second displayed bound is a softer simplification: since k^{2k-4}\leq k^{2k} and \frac{1}{e\sqrt{2}}\cdot\frac{2e}{\log 2}<\frac{3e}{\log 2}, we may enlarge constants and write \mathbb{E}|a_{k}|^{2}\leq n\,\Delta^{k-1}\,k^{2k}\Bigl(\frac{3e}{\log 2}\Bigr)^{k}.\qed C.3 Permanent In order to argue that the Taylor series for the log-permanent decays similarly to the idealized model, we use the following representation of the “correction term” describing the discrepancy between (n-m)!/n! and 1/n^{m} . Intuitively, this correction should be negligible for low-degree coefficients since this corresponds to small m . Lemma 54 (Finite binomial-basis representation of the cardinality correction) . Fix an integer k\geq 1 . For each n\geq 1 , define \rho_{n}(m):=\frac{(n-m)!}{n!}\,n^{m}=\prod_{t=0}^{m-1}\Bigl(1-\frac{t}{n}\Bigr),\qquad 0\leq m\leq n. Then there exist coefficients \theta_{q,n} , 0\leq q\leq k , such that \log\rho_{n}(m)=\sum_{q=0}^{k}\theta_{q,n}\binom{m}{q}\qquad\text{for all }m=0,1,\dots,k whenever n\geq k . Moreover \theta_{0,n}=\theta_{1,n}=0 , and there is an absolute constant C>0 such that for every fixed k\geq 1 , |\theta_{q,n}|\leq(Ck)^{k}\,n^{-(q-1)},\qquad 2\leq q\leq k, for all n\geq k . Consequently, if we set \xi_{q,n}:=e^{\theta_{q,n}}-1, then, after possibly enlarging C , |\xi_{q,n}|\leq(Ck)^{k}\,n^{-(q-1)},\qquad 2\leq q\leq k, and for every m\in\{0,1,\dots,k\} , \rho_{n}(m)=\exp\!\Bigl(\sum_{q=2}^{k}\theta_{q,n}\binom{m}{q}\Bigr)=\prod_{\begin{subarray}{c}S\subseteq[m]\\ 2\leq|S|\leq k\end{subarray}}(1+\xi_{|S|,n}). Proof. Fix k . Since the functions m\longmapsto\binom{m}{q},\qquad q=0,1,\dots,k, form a basis of the space of functions on \{0,1,\dots,k\} , there exist unique coefficients \theta_{q,n} such that \log\rho_{n}(m)=\sum_{q=0}^{k}\theta_{q,n}\binom{m}{q}\qquad(0\leq m\leq k). Because \rho_{n}(0)=\rho_{n}(1)=1 , we have \log\rho_{n}(0)=\log\rho_{n}(1)=0 , which forces \theta_{0,n}=\theta_{1,n}=0 . To bound the coefficients, write \log\rho_{n}(m)=\sum_{t=0}^{m-1}\log\Bigl(1-\frac{t}{n}\Bigr)=-\sum_{\ell\geq 1}\frac{1}{\ell n^{\ell}}\sum_{t=0}^{m-1}t^{\ell}. Now use the standard identity (see, e.g., [ 57 ] ) \sum_{t=0}^{m-1}t^{\ell}=\sum_{r=0}^{\ell}r!\,S(\ell,r)\binom{m}{r+1}, where S(\ell,r) is the Stirling number of the second kind. Therefore \theta_{q,n}=-\sum_{\ell\geq q-1}\frac{(q-1)!\,S(\ell,q-1)}{\ell\,n^{\ell}}. Using the crude bound (q-1)!\,S(\ell,q-1)\leq(q-1)^{\ell}, we obtain |\theta_{q,n}|\leq\sum_{\ell\geq q-1}\frac{(q-1)^{\ell}}{\ell\,n^{\ell}}. If n\geq 2k , then since q-1\leq k , |\theta_{q,n}|\leq\sum_{\ell\geq q-1}\Bigl(\frac{k}{n}\Bigr)^{\ell}\leq 2\Bigl(\frac{k}{n}\Bigr)^{q-1}\leq(2k)^{k}n^{-(q-1)}. For the finitely many n with k\leq n<2k , the same bound follows after enlarging the constant, since k is fixed. This proves |\theta_{q,n}|\leq(Ck)^{k}\,n^{-(q-1)}. The bound on \xi_{q,n}=e^{\theta_{q,n}}-1 follows similarly after enlarging C , since |\theta_{q,n}|\leq(Ck)^{k} for fixed k , and for large n one has |e^{u}-1|\leq 2|u| when |u|\leq 1 . Finally, \exp\!\Bigl(\sum_{q=2}^{k}\theta_{q,n}\binom{m}{q}\Bigr)=\prod_{q=2}^{k}\prod_{\begin{subarray}{c}S\subseteq[m]\\ |S|=q\end{subarray}}e^{\theta_{q,n}}=\prod_{\begin{subarray}{c}S\subseteq[m]\\ 2\leq|S|\leq k\end{subarray}}(1+\xi_{|S|,n}), since \binom{m}{q} is the number of q -subsets of [m] . ∎ Lemma 55 (Connected decorated-hypergraph expansion) . Let V be a finite set, and for each finite X\subseteq V let \mathcal{H}(X) be a family of decorated hypergraphs on vertex set X , with weight w(H)\in\mathbb{C} , such that: 1. every H\in\mathcal{H}(X) decomposes uniquely into connected components H_{1},\dots,H_{r} on a partition X=X_{1}\sqcup\cdots\sqcup X_{r}; 2. the weight is multiplicative across connected components: w(H)=\prod_{j=1}^{r}w(H_{j}). Define A(X):=\sum_{H\in\mathcal{H}(X)}w(H),\qquad C(X):=\sum_{H\in\mathcal{H}_{\mathrm{conn}}(X)}w(H), where \mathcal{H}_{\mathrm{conn}}(X)\subseteq\mathcal{H}(X) denotes the connected hypergraphs on X . Then one has the formal identity 1+\sum_{\varnothing\neq X\subseteq V}A(X)\prod_{x\in X}y_{x}=\exp\!\Bigl(\sum_{\varnothing\neq X\subseteq V}C(X)\prod_{x\in X}y_{x}\Bigr). Proof. Expanding the exponential on the right-hand side and collecting the coefficient of \prod_{x\in X}y_{x} , one obtains \sum_{\pi\in\Pi(X)}\prod_{B\in\pi}C(B), where \Pi(X) denotes the set of set partitions of X . By the assumptions, choosing for each block B\in\pi a connected decorated hypergraph H_{B}\in\mathcal{H}_{\mathrm{conn}}(B) is equivalent to choosing a decorated hypergraph H\in\mathcal{H}(X) together with its connected-component decomposition, and the weights multiply accordingly. Thus A(X)=\sum_{\pi\in\Pi(X)}\prod_{B\in\pi}C(B), which is exactly the claimed identity. ∎ Proposition 56 (Second moment bound for the true logarithmic coefficients) . Let P_{n}(z):=\frac{1}{n!}\per(J+zW),\qquad\log P_{n}(z)=\sum_{k\geq 1}b_{k,n}z^{k}, where W=(W_{ij})_{1\leq i,j\leq n} has i.i.d. standard complex Gaussian entries, W_{ij}\sim\mathcal{N}_{\mathbb{C}}(0,1) . Then there exists an absolute constant C>0 such that for every fixed integer k\geq 1 , one can choose C_{k}\leq\exp\!\bigl(C\,k\,2^{k}\log k\bigr) so that \mathbb{E}|b_{k,n}|^{2}\leq C_{k}\,n^{1-k}\qquad\text{for all }n\geq 1. Proof. Fix k\geq 1 . For n0 such that for all sufficiently small t=|z|^{2} , the following hold: 1. if |U|=1 , then w(U;z)\leq Ct^{3}; 2. if |U|=2 and U is connected, then w(U;z)\leq Ct^{3}. Proof. Define f(s):=(1+s)e^{-s+s^{2}/2}. Since \log f(s)=\log(1+s)-s+\frac{s^{2}}{2}=\frac{s^{3}}{3}-\frac{s^{4}}{4}+\frac{s^{5}}{5}-\cdots , we have f(s)=1+O(s^{3})\qquad(s\to 0). If U=\{e\} , then F_{U}^{(2)}(y_{e})=(1+y_{e})e^{-y_{e}+y_{e}^{2}/2}=f(y_{e}), so \mathcal{C}_{U}(y_{e})=f(y_{e})-1. Every monomial in \mathcal{C}_{U} has degree at least 3 , hence w(U;z)=\mathbb{E}\bigl[|\mathcal{C}_{U}(zW_{e})|^{2}\bigr]\leq Ct^{3}. Now let U=\{e,f\} with e\sim f . The only matchings in H_{U} are \varnothing,\{e\},\{f\} , so Z_{H_{U}}(y_{e},y_{f})=1+y_{e}+y_{f}. Also, -\sum_{u\in U}y_{u}+\frac{1}{2}\sum_{u\in U}y_{u}^{2}+\sum_{u\sim v}y_{u}y_{v}=-(y_{e}+y_{f})+\frac{1}{2}(y_{e}+y_{f})^{2}. Therefore F_{U}^{(2)}(y_{e},y_{f})=f(y_{e}+y_{f}). The exact-support part is \mathcal{C}_{U}(y_{e},y_{f})=f(y_{e}+y_{f})-f(y_{e})-f(y_{f})+1. Again, since f(s)-1 has no terms of degree 1 or 2 , every monomial in \mathcal{C}_{U} has total degree at least 3 . Hence w(U;z)\leq Ct^{3}. This proves the lemma. ∎ Lemma 60 (Weighted local bound) . There exist absolute constants c_{0},C_{0}>0 such that the following holds. Let U\subseteq[n]\times[n] be connected, with m:=|U|\geq 3 . Write r_{i}(U):=\deg_{H_{U}}(i,\cdot),\qquad c_{j}(U):=\deg_{H_{U}}(\cdot,j). If t=|z|^{2} satisfies nt\leq c_{0} , then w(U;z)\leq(C_{0}t)^{m}\prod_{i:\,r_{i}(U)\geq 1}(r_{i}(U)-1)!\prod_{j:\,c_{j}(U)\geq 1}(c_{j}(U)-1)!. Proof. By Lemma 58 , it is enough to bound \bigl\|\partial_{U}F_{U}^{(2)}(zW)\bigr\|_{L^{2}}^{2}. Write s_{i}(W):=\sum_{j:(i,j)\in U}W_{ij},\qquad t_{j}(W):=\sum_{i:(i,j)\in U}W_{ij}. A direct algebraic identity gives \frac{1}{2}\sum_{e\in U}(zW_{e})^{2}+\sum_{\begin{subarray}{c}e,f\in U\\ e\sim f\end{subarray}}zW_{e}\,zW_{f}=-\frac{1}{2}z^{2}\sum_{e\in U}W_{e}^{2}+\frac{z^{2}}{2}\sum_{i}s_{i}(W)^{2}+\frac{z^{2}}{2}\sum_{j}t_{j}(W)^{2}. Hence \displaystyle F_{U}^{(2)}(zW) \displaystyle=Z_{H_{U}}(zW)\exp\!\Bigl(-z\sum_{e\in U}W_{e}-\frac{z^{2}}{2}\sum_{e\in U}W_{e}^{2}+\frac{z^{2}}{2}\sum_{i}s_{i}(W)^{2}+\frac{z^{2}}{2}\sum_{j}t_{j}(W)^{2}\Bigr). Introduce independent real standard Gaussians (g_{i}) and (h_{j}) , indexed by the touched rows and columns of U , and set \eta_{ij}:=g_{i}+h_{j}-1. Using e^{\frac{z^{2}}{2}u^{2}}=\mathbb{E}_{g}[e^{zgu}] , we obtain the Hubbard–Stratonovich representation [ 33 ] F_{U}^{(2)}(zW)=\mathbb{E}_{g,h}\!\left[Z_{H_{U}}(zW)\prod_{e=(i,j)\in U}\exp\!\Bigl(z\eta_{ij}W_{ij}-\frac{z^{2}}{2}W_{ij}^{2}\Bigr)\right]. Now expand Z_{H_{U}}(zW)=\sum_{M\in\mathcal{M}(H_{U})}\prod_{e\in M}zW_{e}, where \mathcal{M}(H_{U}) denotes the matchings in H_{U} . For each fixed matching M , differentiating once in every variable W_{e} yields the following. If e\notin M , then \partial_{W_{e}}\exp\!\Bigl(z\eta_{e}W_{e}-\frac{z^{2}}{2}W_{e}^{2}\Bigr)=z(\eta_{e}-zW_{e})\exp\!\Bigl(z\eta_{e}W_{e}-\frac{z^{2}}{2}W_{e}^{2}\Bigr). If e\in M , then \partial_{W_{e}}\Bigl(zW_{e}\,\exp\!\bigl(z\eta_{e}W_{e}-\tfrac{z^{2}}{2}W_{e}^{2}\bigr)\Bigr)=z\bigl(1+z\eta_{e}W_{e}-z^{2}W_{e}^{2}\bigr)\exp\!\Bigl(z\eta_{e}W_{e}-\frac{z^{2}}{2}W_{e}^{2}\Bigr). Define A_{e}:=|z|\,|\eta_{e}-zW_{e}|\,\exp\!\Bigl(\Re\!\bigl(z\eta_{e}W_{e}-\tfrac{z^{2}}{2}W_{e}^{2}\bigr)\Bigr), B_{e}:=|z|\,|1+z\eta_{e}W_{e}-z^{2}W_{e}^{2}|\,\exp\!\Bigl(\Re\!\bigl(z\eta_{e}W_{e}-\tfrac{z^{2}}{2}W_{e}^{2}\bigr)\Bigr). Then \bigl|\partial_{U}F_{U}^{(2)}(zW)\bigr|\leq\mathbb{E}_{g,h}\!\left[\sum_{M\in\mathcal{M}(H_{U})}\prod_{e\notin M}A_{e}\prod_{e\in M}B_{e}\right]\leq\mathbb{E}_{g,h}\!\left[\prod_{e\in U}(A_{e}+B_{e})\right]. By Jensen, \bigl\|\partial_{U}F_{U}^{(2)}(zW)\bigr\|_{2}^{2}\leq\mathbb{E}_{g,h}\mathbb{E}_{W}\!\left[\prod_{e\in U}(A_{e}+B_{e})^{2}\right]. Since the W_{e} ’s are independent, this factors as \bigl\|\partial_{U}F_{U}^{(2)}(zW)\bigr\|_{2}^{2}\leq\mathbb{E}_{g,h}\prod_{e\in U}J_{t}(\eta_{e}), where J_{t}(\eta):=\mathbb{E}_{W\sim\mathcal{N}_{\mathbb{C}}(0,1)}\!\left[(A+B)^{2}\right] with \eta held fixed. We now estimate J_{t}(\eta) . First we make an observation based on rotational invariance. Write z=\sqrt{t}\,e^{i\theta} , and define \widetilde{W}:=e^{i\theta}W . Since \widetilde{W}\sim\mathcal{N}_{\mathbb{C}}(0,1) , and since W=e^{-i\theta}\widetilde{W} , we have zW=\sqrt{t}\,\widetilde{W},\qquad z^{2}W^{2}=t\,\widetilde{W}^{2}. Therefore |\,\eta-zW\,|=|\,\eta-\sqrt{t}\,\widetilde{W}\,|,\qquad|\,1+z\eta W-z^{2}W^{2}\,|=|\,1+\sqrt{t}\,\eta\,\widetilde{W}-t\,\widetilde{W}^{2}\,|, and also \Re\!\Bigl(z\eta W-\frac{z^{2}}{2}W^{2}\Bigr)=\Re\!\Bigl(\sqrt{t}\,\eta\,\widetilde{W}-\frac{t}{2}\,\widetilde{W}^{2}\Bigr). It follows that J_{t}(\eta) depends only on t , not on the phase of z . Thus, by rotational invariance, it suffices to assume that z=\sqrt{t}>0 is real. Write W=\frac{X+iY}{\sqrt{2}},\qquad X,Y\stackrel{{\scriptstyle\mathrm{i.i.d.}}}{{\sim}}N(0,1). Then 2\Re\!\Bigl(\sqrt{t}\,\eta\,W-\frac{t}{2}W^{2}\Bigr)=\sqrt{2}\,\sqrt{t}\,\eta\,X-\frac{t}{2}(X^{2}-Y^{2}). Hence e^{2\Re(\sqrt{t}\,\eta\,W-\frac{t}{2}W^{2})}\,d\mu(W)=K_{t}(\eta)\,d\nu_{t,\eta}(X,Y), where d\mu(W) is the standard complex Gaussian law, and K_{t}(\eta)=\frac{1}{\sqrt{1-t^{2}}}\exp\!\Bigl(\frac{t\eta^{2}}{1+t}\Bigr), while under \nu_{t,\eta} , the variables X and Y are independent Gaussians with X\sim N\!\Bigl(\frac{\sqrt{2}\,\sqrt{t}\,\eta}{1+t},\frac{1}{1+t}\Bigr),\qquad Y\sim N\!\Bigl(0,\frac{1}{1-t}\Bigr). Using J_{t}(\eta)\leq 2\mathbb{E}[A^{2}]+2\mathbb{E}[B^{2}] , we first estimate \mathbb{E}[A^{2}] . Since A=\sqrt{t}\,|\eta-\sqrt{t}\,W|\,e^{\Re(\sqrt{t}\,\eta\,W-\frac{t}{2}W^{2})}, we have \mathbb{E}[A^{2}]=t\,K_{t}(\eta)\,\mathbb{E}_{\nu_{t,\eta}}\!\left[\,|\eta-\sqrt{t}\,W|^{2}\right]. Now |\eta-\sqrt{t}\,W|^{2}=\Bigl(\eta-\sqrt{\frac{t}{2}}\,X\Bigr)^{2}+\frac{t}{2}\,Y^{2}. Since under \nu_{t,\eta} , \mathbb{E}[X]=\frac{\sqrt{2}\,\sqrt{t}\,\eta}{1+t},\qquad\operatorname{Var}(X)=\frac{1}{1+t},\qquad\operatorname{Var}(Y)=\frac{1}{1-t}, it follows that \mathbb{E}_{\nu_{t,\eta}}\!\left[\,|\eta-\sqrt{t}\,W|^{2}\right]\leq C(1+\eta^{2}) for all 0\leq t\leq t_{0} with t_{0}<1 fixed. Hence \mathbb{E}[A^{2}]\leq Ct(1+\eta^{2})e^{Ct\eta^{2}}. Next, since B=\sqrt{t}\,|1+\sqrt{t}\,\eta\,W-tW^{2}|\,e^{\Re(\sqrt{t}\,\eta\,W-\frac{t}{2}W^{2})}, we get \mathbb{E}[B^{2}]=t\,K_{t}(\eta)\,\mathbb{E}_{\nu_{t,\eta}}\!\left[\,|1+\sqrt{t}\,\eta\,W-tW^{2}|^{2}\right]. Using the inequality |1+u+v|^{2}\leq 3(1+|u|^{2}+|v|^{2}) , we obtain |1+\sqrt{t}\,\eta\,W-tW^{2}|^{2}\leq C\Bigl(1+t\eta^{2}|W|^{2}+t^{2}|W|^{4}\Bigr). Under \nu_{t,\eta} , the moments of W satisfy \mathbb{E}_{\nu_{t,\eta}}[|W|^{2}]\leq C(1+t\eta^{2}),\qquad\mathbb{E}_{\nu_{t,\eta}}[|W|^{4}]\leq C(1+t\eta^{2}+t^{2}\eta^{4}), uniformly for 0\leq t\leq t_{0} . Therefore \mathbb{E}[B^{2}]\leq Ct\,K_{t}(\eta)\bigl(1+t\eta^{2}+t^{2}\eta^{4}\bigr). Since K_{t}(\eta)\leq Ce^{Ct\eta^{2}} and 1+t\eta^{2}+t^{2}\eta^{4}\leq C(1+\eta^{2})e^{Ct\eta^{2}} , it follows that \mathbb{E}[B^{2}]\leq Ct(1+\eta^{2})e^{Ct\eta^{2}}. Combining the two bounds yields J_{t}(\eta)\leq Ct(1+\eta^{2})e^{Ct\eta^{2}}. Substituting this into the previous display, we obtain \bigl\|\partial_{U}F_{U}^{(2)}(zW)\bigr\|_{2}^{2}\leq(Ct)^{m}\mathbb{E}_{g,h}\!\left[\prod_{e=(i,j)\in U}(1+\eta_{ij}^{2})e^{Ct\eta_{ij}^{2}}\right]. We now estimate the auxiliary Gaussian expectation. Since \eta_{ij}=g_{i}+h_{j}-1 , 1+\eta_{ij}^{2}\leq C(1+g_{i}^{2})(1+(h_{j}-1)^{2}), and e^{Ct\eta_{ij}^{2}}\leq C\,e^{Ctg_{i}^{2}}e^{Ct(h_{j}-1)^{2}} . Therefore \prod_{e=(i,j)\in U}(1+\eta_{ij}^{2})e^{Ct\eta_{ij}^{2}}\leq C^{m}\prod_{i}(1+g_{i}^{2})^{r_{i}(U)}e^{Ct\,r_{i}(U)g_{i}^{2}}\prod_{j}(1+(h_{j}-1)^{2})^{c_{j}(U)}e^{Ct\,c_{j}(U)(h_{j}-1)^{2}}. Taking expectation and using independence gives \displaystyle\mathbb{E}_{g,h}\!\left[\prod_{e\in U}(1+\eta_{e}^{2})e^{Ct\eta_{e}^{2}}\right] \displaystyle\leq C^{m}\prod_{i}\mathbb{E}\!\left[(1+G^{2})^{r_{i}(U)}e^{\lambda_{i}G^{2}}\right]\prod_{j}\mathbb{E}\!\left[(1+(H-1)^{2})^{c_{j}(U)}e^{\mu_{j}(H-1)^{2}}\right], where G,H\sim N(0,1) and \lambda_{i}:=Ct\,r_{i}(U),\qquad\mu_{j}:=Ct\,c_{j}(U). Since r_{i}(U),c_{j}(U)\leq n and nt\leq c_{0} , by choosing c_{0} small enough we may assume that 0\leq\lambda_{i},\mu_{j}\leq\lambda_{\ast} for some fixed \lambda_{\ast}<1/2 . Hence, for every integer r\geq 1 , \mathbb{E}[(1+G^{2})^{r}e^{\lambda G^{2}}]\leq C^{r}r!,\qquad 0\leq\lambda\leq\lambda_{\ast}, since \lambda_{\ast}<1/2 and \mathbb{E}[e^{\lambda G^{2}}]<\infty uniformly on [0,\lambda_{\ast}] , while (1+G^{2})^{r}\leq 2^{r}(1+|G|^{2r}) and \mathbb{E}|G|^{2r}\leq C^{r}r! . Similarly, \mathbb{E}[(1+(H-1)^{2})^{r}e^{\lambda(H-1)^{2}}]\leq C^{r}r!,\qquad 0\leq\lambda\leq\lambda_{\ast}, because H-1\sim N(-1,1) has density \frac{1}{\sqrt{2\pi}}e^{-(x+1)^{2}/2}, so \mathbb{E}[(1+(H-1)^{2})^{r}e^{\lambda(H-1)^{2}}]=\frac{1}{\sqrt{2\pi}}\int_{\mathbb{R}}(1+x^{2})^{r}e^{\lambda x^{2}-(x+1)^{2}/2}\,dx. Since \lambda x^{2}-\frac{(x+1)^{2}}{2}=-\Bigl(\frac{1}{2}-\lambda\Bigr)x^{2}-x-\frac{1}{2}\leq-\Bigl(\frac{1}{2}-\lambda_{\ast}\Bigr)x^{2}+|x|, and \lambda_{\ast}<1/2 , the integrand is bounded by C(1+x^{2})^{r}e^{-cx^{2}} for some absolute constants c,C>0 . Therefore \mathbb{E}[(1+(H-1)^{2})^{r}e^{\lambda(H-1)^{2}}]\leq C^{r}\int_{\mathbb{R}}(1+x^{2})^{r}e^{-cx^{2}}\,dx\leq C^{r}r!. Thus \mathbb{E}_{g,h}\!\left[\prod_{e\in U}(1+\eta_{e}^{2})e^{Ct\eta_{e}^{2}}\right]\leq C^{m}\prod_{i}r_{i}(U)!\prod_{j}c_{j}(U)!. Combining the estimates gives \bigl\|\partial_{U}F_{U}^{(2)}(zW)\bigr\|_{2}^{2}\leq(Ct)^{m}\prod_{i}r_{i}(U)!\prod_{j}c_{j}(U)!. Finally, for every integer r\geq 1 , r!\leq 2^{r-1}(r-1)!. Since \sum_{i}r_{i}(U)=m=\sum_{j}c_{j}(U) , we obtain \prod_{i}r_{i}(U)!\prod_{j}c_{j}(U)!\leq 4^{m}\prod_{i}(r_{i}(U)-1)!\prod_{j}(c_{j}(U)-1)!. Absorbing the factor 4^{m} into the constant proves the lemma. ∎ Theorem 61 (Second-order bound on L(K_{n,n}) ) . There exist absolute constants c,C>0 such that the following holds. Let G_{n}:=L(K_{n,n}),\qquad F_{n}^{(2)}(x):=Z_{G_{n}}(x)\exp\!\bigl(-L_{1}(x)-L_{2}(x)\bigr), where L_{1}(x):=\sum_{(i,j)\in[n]\times[n]}x_{ij},\qquad L_{2}(x):=-\frac{1}{2}\sum_{(i,j)}x_{ij}^{2}-\sum_{(i,j)\sim(i^{\prime},j^{\prime})}x_{ij}x_{i^{\prime}j^{\prime}}. Let W=(W_{ij}) have i.i.d. entries W_{ij}\sim\mathcal{N}_{\mathbb{C}}(0,1) , and define X_{n}^{(2)}(z):=F_{n}^{(2)}(zW). If n|z|^{2}\leq c , then \log\mathbb{E}\bigl[|X_{n}^{(2)}(z)|^{2}\bigr]\leq C\,n^{4}\,|z|^{6}. Proof. Write E_{n}=[n]\times[n] . Decompose F_{n}^{(2)}(x)=\sum_{A\subseteq E_{n}}\mathcal{C}_{A}(x_{A}), where \mathcal{C}_{A} is the exact-support part on A . Then X_{n}^{(2)}(z)=F_{n}^{(2)}(zW)=\sum_{A\subseteq E_{n}}\mathcal{C}_{A}(zW_{A}). By orthogonality of complex Gaussian monomials, \mathbb{E}\bigl[|X_{n}^{(2)}(z)|^{2}\bigr]=\sum_{A\subseteq E_{n}}\mathbb{E}\bigl[|\mathcal{C}_{A}(zW_{A})|^{2}\bigr]. If A=U_{1}\sqcup\cdots\sqcup U_{k} is the decomposition of A into connected components in G_{n}=L(K_{n,n}) , then F_{A}^{(2)} factorizes over the components, and therefore so does the exact-support piece: \mathcal{C}_{A}=\prod_{\ell=1}^{k}\mathcal{C}_{U_{\ell}}. Hence, for connected U\subseteq E_{n} , if we define w(U;z):=\mathbb{E}\bigl[|\mathcal{C}_{U}(zW_{U})|^{2}\bigr], then \mathbb{E}\bigl[|X_{n}^{(2)}(z)|^{2}\bigr]=\sum_{\Gamma\ \mathrm{compatible}}\prod_{U\in\Gamma}w(U;z), where \Gamma runs over finite families of pairwise compatible connected supports. We now forget compatibility. For e\in E_{n} , set S_{e}(z):=\sum_{\begin{subarray}{c}U\ni e\\ U\text{ connected}\end{subarray}}w(U;z). For each connected U\subseteq E_{n} , fix once and for all a representative edge \rho(U)\in U , for example the lexicographically smallest edge of U . If \Gamma=\{U_{1},\dots,U_{k}\} is a compatible family of connected supports, then the sets U_{1},\dots,U_{k} are pairwise disjoint, hence the representative edges \rho(U_{1}),\dots,\rho(U_{k}) are distinct. Therefore the monomial \prod_{U\in\Gamma}w(U;z) appears among the terms in the expansion of \prod_{e\in E_{n}}(1+S_{e}(z)), namely by choosing from the factor indexed by e=\rho(U) the summand w(U;z) for each U\in\Gamma , and choosing 1 from all other factors. Since all weights are nonnegative, \mathbb{E}\bigl[|X_{n}^{(2)}(z)|^{2}\bigr]=\sum_{\Gamma\ \mathrm{compatible}}\prod_{U\in\Gamma}w(U;z)\leq\prod_{e\in E_{n}}(1+S_{e}(z)). Hence, using \log(1+s)\leq s for s\geq 0 , \log\mathbb{E}\bigl[|X_{n}^{(2)}(z)|^{2}\bigr]\leq\sum_{e\in E_{n}}\ \sum_{\begin{subarray}{c}U\ni e\\ U\text{ connected}\end{subarray}}w(U;z). Fix a root edge e_{0}\in E_{n} . By Lemma 59 , \sum_{\begin{subarray}{c}U\ni e_{0}\\ U\text{ connected}\\ |U|=1\end{subarray}}w(U;z)\leq Ct^{3}. Also, there are at most 2n-2 connected supports of size 2 containing e_{0} , so \sum_{\begin{subarray}{c}U\ni e_{0}\\ U\text{ connected}\\ |U|=2\end{subarray}}w(U;z)\leq Cn\,t^{3}. Now let m\geq 3 . By Lemma 60 and Proposition 57 , \displaystyle\sum_{\begin{subarray}{c}U\ni e_{0}\\ U\text{ connected}\\ |U|=m\end{subarray}}w(U;z) \displaystyle\leq(Ct)^{m}\sum_{\begin{subarray}{c}U\ni e_{0}\\ U\text{ connected}\\ |U|=m\end{subarray}}\prod_{i}(r_{i}(U)-1)!\prod_{j}(c_{j}(U)-1)!\leq(Ct)^{m}\mathrm{Cat}_{m}n^{m-1}. Using \mathrm{Cat}_{m}\leq 4^{m} , \sum_{\begin{subarray}{c}U\ni e_{0}\\ U\text{ connected}\\ |U|=m\end{subarray}}w(U;z)\leq(C^{\prime}t)^{m}n^{m-1}. Therefore \sum_{m\geq 3}\sum_{\begin{subarray}{c}U\ni e_{0}\\ U\text{ connected}\\ |U|=m\end{subarray}}w(U;z)\leq n^{2}t^{3}\sum_{m\geq 3}(C^{\prime\prime}nt)^{m-3}. If nt\leq c with c>0 sufficiently small, the geometric series is bounded by an absolute constant, so \sup_{e_{0}\in E_{n}}\sum_{\begin{subarray}{c}U\ni e_{0}\\ U\text{ connected}\end{subarray}}w(U;z)\leq Cn^{2}t^{3}. Finally, since |E_{n}|=n^{2} , \log\mathbb{E}\bigl[|X_{n}^{(2)}(z)|^{2}\bigr]\leq n^{2}\cdot Cn^{2}t^{3}=Cn^{4}t^{3}=Cn^{4}|z|^{6}. This proves the theorem. ∎