Approximating permanents and hafnians

Main results: permanents

We discuss analytic methods of efficient approximation of permanents and hafnians of real and complex matrices as well as of their multi-dimensional versions, objects of considerable interest in connection with problems in combinatorics , , quantum physics , , and computational complexity , .

Let $A=\left(a_{ij}\right)$ be an $n\times n$ real or complex matrix. The permanent of $A$ is defined as

where $S_{n}$ is the symmetric group of permutations of the set $\{1,\ldots,n\}$. It is a $\#P$-hard problem to compute the permanent of a given 0-1 matrix $A$ exactly , although a fully polynomial randomized approximation scheme is constructed for non-negative matrices . The permanent of an $n\times n$ non-negative matrix $A$ can be approximated within a factor of $e^{n}$ in deterministic polynomial time and the factor was improved to $2^{n}$ in (with a conjectured improvement to $2^{n/2}$). If one assumes that

More precisely, we prove the following result.

For any $0<\delta\leq 1$ there exists $\gamma=\gamma(\delta)>0$ such that for any positive integer $n$ and any $0<\epsilon<1$ there exists a polynomial $p=p_{n,\delta,\epsilon}$ in the entries $a_{ij}$ of an $n\times n$ matrix $A$ such that $\deg p\leq\gamma\left(\ln n-\ln\epsilon\right)$ and

for all $n\times n$ real matrices $A=\left(a_{ij}\right)$ satisfying

We show that the polynomial $p$ can be computed in quasi-polynomial time $n^{O(\ln n-\ln\epsilon)}$, where the implied constant in the “$O$” notation depends on $\delta$ alone.

Our approach continues a line of work started in and continued in , and . The main idea is to relate approximability of a polynomial with its complex zeros. For a complex number $z=a+ib$, we denote by $\Re\thinspace z=a$ and $\Im\thinspace z=b$, the real and imaginary parts of $z$ correspondingly. In what follows, we always choose the standard branch of $\arcsin x$, $\arccos x$ and $\arctan x$ for real $x$, so that

We deduce Theorem 1.1 from the following result.

Let $Z=\left(z_{ij}\right)$ be an $n\times n$ complex matrix such that

In this paper, we prove the following results.

Let $Z=\left(z_{ij}\right)$ be an $n\times n$ complex matrix such that

For every $0\leq\eta<0.5$ there exists a constant $\gamma=\gamma(\eta)>0$ such that for every positive integer $n$ and every real $0<\epsilon<1$ there exists a polynomial $p=p_{n,\eta,\epsilon}$ in the entries of an $n\times n$ complex matrix $A=\left(a_{ij}\right)$ such that $\deg p\leq\gamma\left(\ln n-\ln\epsilon\right)$ and

for $n\times n$ complex matrices $A=\left(a_{ij}\right)$ satisfying

Moreover, the polynomial $p$ can be computed in $n^{O(\ln n-\ln\epsilon)}$ time, where the implied constant in the “$O$” notation depends on $\eta$ alone.

A version of Theorem 1.3 with a weaker bound of $0.195$ instead of $0.5$ and a more complicated proof was obtained in . Theorem 1.4 is also implicit in . We present its proof here since it serves as a stepping stone for the proof of Theorem 1.1.

It is not known whether the bound $0.5$ in Theorems 1.3 and 1.4 can be increased, although one can show (see Section 4) that it cannot be increased to $\sqrt{2}/2\approx 0.707$.

Let $\alpha\approx 0.278$ be the real solution of the equation $\alpha e^{1+\alpha}=1$. Let $Z=\left(z_{ij}\right)$ be an $n\times n$ complex matrix such that

For every $0\leq\eta<\alpha/4$, where $\alpha\approx 0.278$ is the constant in Theorem 1.5, there exists a constant $\gamma=\gamma(\eta)>0$ such that for every positive integer $n$ and every real $0<\epsilon<1$ there exists a polynomial $p=p_{n,\eta,\epsilon}$ in the entries of an $n\times n$ matrix $A=\left(a_{ij}\right)$ such that $\deg p\leq\gamma(\ln n-\ln\epsilon)$ and

for $n\times n$ complex matrices $A=\left(a_{ij}\right)$ satisfying

Again, the polynomial $p_{n,\eta,\epsilon}$ can be constructed in $n^{O(\ln n-\ln\epsilon)}$ time, where the implied constant in the “$O$” notation depends on $\eta$ only. Note that Theorem 1.6 is applicable to 0-1 matrices having not too many (not more than $7\%$) zeros in every row and column as well as to real matrices with some positive and some negative entries. It is not known whether the bound in Theorems 1.5 and 1.6 are optimal.

Main results: hafnians

Some of our results immediately extend from permanents to hafnians.

Let $A=\left(a_{ij}\right)$ be a $2n\times 2n$ symmetric real or complex matrix. The hafnian of $A$ is defined as

where the sum is taken over $(2n)!/2^{n}n!$ unordered partitions of the set $\{1,\ldots,2n\}$ into $n$ pairwise disjoint unordered pairs $\{i_{1},j_{1}\},\ldots,\{i_{n},j_{n}\}$, see for example, Section 8.2 of . Just as the permanent of the biadjacency matrix of a bipartite graph enumerates the perfect matchings in the graph, the hafnian of the adjacency matrix of a graph enumerates the perfect matchings in the graph. In fact, for any $n\times n$ matrix $A$ we have

and hence computing the permanent of an $n\times n$ matrix reduces to computing the hafnian of a symmetric $2n\times 2n$ matrix.

In this paper, we prove the following versions of Theorem 1.1 and 1.2.

For any $0<\delta\leq 1$ there exists $\gamma=\gamma(\delta)>0$ such that for any positive integer $n$ and any $0<\epsilon<1$ there exists a polynomial $p=p_{n,\delta,\epsilon}$ in the entries $a_{ij}$ of a $2n\times 2n$ symmetric matrix $A$ such that $\deg p\leq\gamma(\ln n-\ln\epsilon)$ and

for all $2n\times 2n$ real symmetric matrices $A=\left(a_{ij}\right)$ satisfying

The polynomial $p_{n,\delta,\epsilon}$ can be computed in $n^{O(\ln n-\ln\epsilon)}$ time, where the implied constant in the “$O$” notation depends on $\delta$ alone. Consequently, we obtain a deterministic quasi-polynomial algorithm to approximate the hafnian of a positive matrix $A=\left(a_{ij}\right)$ satisfying (1.1.1) within any given relative error $\epsilon>0$.

As is the case with permanents, we deduce Theorem 2.1 from a result on the complex zeros of the hafnian.

Let us fix a real $0\leq\eta<1$ and and let

Let $Z=\left(z_{ij}\right)$ be an $2n\times 2n$ symmetric complex matrix such that

We also obtain the following versions of Theorems 1.3 and 1.4.

Let $Z=\left(z_{ij}\right)$ be an $2n\times 2n$ symmetric complex matrix such that

For any $0\leq\eta<0.5$ there exists $\gamma=\gamma(\eta)>0$ and for any positive integer $n$ and real $0<\epsilon<1$ there exists a polynomial $p=p_{n,\eta,\epsilon}$ in the entries of $2n\times 2n$ complex symmetric matrix $A=\left(a_{ij}\right)$ such that $\deg p\leq\gamma(\ln n-\ln\epsilon)$ and

As before, the polynomial $p_{n,\eta,\epsilon}$ can be computed in $n^{O(\ln n-\ln\epsilon)}$ time, where the implied constant in the “$O$” notation depends on $\eta$ alone.

Our approach can be extended to a variety of partition functions , . In Section 3, we show how to extend it to multi-dimensional permanents of tensors.

Main results: multi-dimensional permanents

Let $A=\left(a_{i_{1}\ldots i_{d}}\right)$ be a $d$-dimensional $n\times\ldots\times n$ array (tensor) filled with $n^{d}$ real or complex matrices. We define the permanent of $A$ by

We define a slice of $A$ as the array of $n^{d-1}$ entries of $A$ with one of the indices $i_{1},\ldots,i_{d}$ fixed to a particular value and the remaining $(d-1)$ indices varying arbitrarily. Hence $A$ has altogether $nd$ slices. If $d=2$ and $A$ is a matrix then a slice is a row or a column.

We note that for $d>2$ there are several different notions of the permanent of a tensor, cf., for example, .

We obtain the following extension of Theorem 1.3.

for some $\theta=\theta_{d}>0$ such that $(d-1)\theta\ <\ 2\pi/3$. Hence $0<\eta_{d}<1$ and we can choose $\eta_{2}=0.5$, $\eta_{3}=\sqrt{6}/9\approx 0.272$, $\eta_{4}\approx 0.184$ and $\eta_{d}=\Omega\left(\frac{1}{d}\right)$.

Let $Z=\left(z_{i_{1}\ldots i_{d}}\right)$ be a $d$-dimensional complex $n\times\ldots\times n$ array such that

A version of Theorem 3.1 with weaker bounds $\eta_{2}=0.195$, $\eta_{3}=0.125$ and $\eta_{4}=0.093$ and a more complicated proof was obtained in .

For an integer $d\geq 2$, let us choose $0\leq\eta<\eta_{d}$, where $\eta_{d}$ is the constant in Theorem 3.1. Then there exists $\gamma=\gamma(d,\eta)>0$ and for every integer $n$ and real $0<\epsilon<1$ there exists a polynomial $p=p_{d,\eta,\epsilon,n}$ in the entries of a $d$-dimensional $n\times\ldots\times n$ complex tensor $A=\left(a_{i_{1}\ldots i_{d}}\right)$ such that $\deg p\leq\gamma(\ln n-\ln\epsilon)$ and

The polynomial $p_{d,\eta,\epsilon,n}$ can be computed in $n^{O(\ln n-\ln\epsilon)}$ time, where the implied constant in the “$O$” notation depends only on $d$ and $\eta$.

While we were unable to obtain exact equivalents of Theorems 1.1 and 2.1, our approach produces the following approximation result for multi-dimensional permanents.

so that $\eta_{2}=1$, $\eta_{3}=\sqrt{2}-1\approx 0.414$, $\eta_{4}=2-\sqrt{3}\approx 0.268$, etc.

For any $0\leq\eta<\eta_{d}$ there is a constant $\gamma=\gamma(d,\eta)$ and for any positive integer $n$ and real $0<\epsilon<1$ there is a polynomial $p=p_{d,\eta,\epsilon,n}$ is the entries of a $d$-dimensional $n\times\cdots\times n$ tensor such that $\deg p\leq\gamma(\ln n-\ln\epsilon)$ and

for any $d$-dimensional $n\times\ldots\times n$ real tensor $A=\left(a_{i_{1}\ldots i_{d}}\right)$ satisfying

For an integer $d\geq 2$, let $\eta_{d}$ be the constant of Theorem 3.3. Let us fix a real $0\leq\eta<\eta_{d}$ and let

Let $Z=\left(z_{i_{1}\ldots i_{d}}\right)$ be a $d$-dimensional tensor of complex numbers such that

for all $1\leq i_{1},\ldots,i_{d}\leq n$.

Finally, we obtain multi-dimensional versions of Theorems 1.5 and 1.6.

Let $\alpha\approx 0.278$ be the real solution of the equation $\alpha e^{1+\alpha}=1$. For an integer $d\geq 2$, let

Let $Z=\left(z_{i_{1}\ldots i_{d}}\right)$ be a $d$-dimensional complex $n\times\ldots\times n$ array such that the sum of $\left|1-z_{i_{1}\ldots i_{d}}\right|$ over each slice of $Z$ does not exceed $\eta_{d}n^{d-1}$.

For every integer $d\geq 2$ and every $0\ \leq\ \eta\ <\ \eta_{d}$, where $\eta_{d}$ is the constant of Theorem 3.5, there exists a constant $\gamma=\gamma(d,\eta)>0$ such that for any positive integer $n$ and real $0<\epsilon<1$ there is a polynomial $p=p_{d,\eta,\epsilon,n}$ in the entries of a $d$-dimensional $n\times\ldots\times n$ tensor such that $\deg p\leq\gamma(\ln n-\ln\epsilon)$ and

for any $d$-dimensional $n\times\ldots\times n$ tensor $A=\left(a_{i_{1}\ldots i_{d}}\right)$ for which the sum of $\left|1-a_{i_{1}\ldots i_{d}}\right|$ over each slice of $A$ does not exceed $\eta n^{d-1}$.

Again, the polynomial $p_{d,\eta,\epsilon,n}$ can be computed in $n^{O(\ln n-\ln\epsilon)}$ time, where the implied constant in the “$O$” notation depends on $d$ and $\eta$ alone. Theorem 3.6 is applicable to 0-1 tensors $A$, which contain a small (and exponentially decreasing with $d$) fraction of 0s in each slice.

In Section 4, we prove Theorems 1.3, 2.3 and 3.1.

In Section 5, we prove Theorems 1.2, 2.2 and 3.3.

In Section 6, we prove Theorems 1.5 and 3.5.

In Section 7, we prove Theorems 1.4, 1.6, 2.4, 3.2 and 3.6.

In Section 8, we prove Theorems 1.1, 2.1 and 3.3.

Finally, in Section 9, we discuss possible ramifications and open questions.

Proofs of Theorems 1.3, 2.3 and 3.1

and by $|\cdot|$ the corresponding Euclidean norm (the modulus of a complex number).

Let $\alpha_{1},\ldots,\alpha_{n}$ and $\beta_{1},\ldots,\beta_{n}$ be complex numbers such that

Then $v\neq 0$, $w\neq 0$ and the angle between $v$ and $w$ does not exceed

Let us consider the orthogonal projection of each vector $u_{j}$ onto the bisector of $K$. Then the length of the projection of $u_{j}$ is at least $|u_{j}|\cos(\theta/2)$ and hence the length of the orthogonal projection of $u$ onto the bisector of $K$ is at least

Since the length of $u$ is at least as large as the length of its orthogonal projection, the proof of Part (1) follows.

From Part (1), we conclude that $|v-u|<|u|$. Therefore, $v=(v-u)+u\neq 0$ and the angle between $v$ and $u$ does not exceed

Similarly, $w=(w-u)+u\neq 0$ and the angle between $w$ and $u$ does not exceed

Therefore, the angle between $v$ and $w$ does not exceed

and the proof of Part (2) follows. $\hfill\square$

For a positive integer $n$, let $\mathcal{U}_{n}$ be the set of $n\times n$ complex matrices $Z=\left(z_{ij}\right)$ such that

We prove by induction on $n$ the following statement:

The statement obviously holds for $n=1$. Assuming that the statement holds for matrices in $\mathcal{U}_{n-1}$ with $n\geq 2$, let us consider two matrices $A,B\in\mathcal{U}_{n}$ that differ in one row or in one column only. Since the permanent of a matrix does not change when the rows or columns of the matrix are permuted or when the matrix is transposed, without loss of generality we assume that $B$ is obtained from $A$ by replacing the entries $a_{1j}$ of the first row by complex numbers $b_{1j}$ for $j=1,\ldots,n$. Let $A_{j}$ be the $(n-1)\times(n-1)$ matrix obtained from $A$ by crossing out the first row and the $j$-th column. Then

which concludes the induction step. $\square$

One can observe that $\eta=0.5$ is the largest value of $\eta$ for which the equation

has a solution $\theta<2\pi/3$ and hence the induction in Section 4.1 can proceed. It is not known whether the constant $0.5$ in Theorem 1.3 can be increased. Since

the value of $0.5$ in Theorem 1.3 cannot be replaced by $\sqrt{2}/2\approx 0.707$. Moreover, as Boris Bukh noticed , we have

where $A$ is a matrix as above, $m$ is odd and $J_{m}$ is an $m\times m$ matrix filled with 1s.

2 Proof of Theorem 2.3

The statement obviously holds for $n=1$. Suppose that $n>1$. Since the hafnian of the matrix does not change under a simultaneous permutation of rows and columns, without loss of generality we may assume that $A$ and $B$ differ in the first row and first column only. Instead of the Laplace expansion (4.1.2), we use the recurrence

where $A_{j}$ is the $(2n-2)\times(2n-2)$ matrix obtained from $A$ by crossing out the first row and the first column and the $j$-th row and the $j$-th column. We observe that, up to a simultaneous permutation of rows and columns, any two matrices $A_{j_{1}}$ and $A_{j_{2}}$ differ only in the $k$-th row and $k$-th column for some $k$ and the induction proceeds as in Section 4.1. $\square$

3 Proof of Theorem 3.1

By and large, the proof proceeds as in Section 4.1. For a positive integer $n$, we define $\mathcal{U}_{n}$ as the set of $n\times\ldots\times n$ complex arrays $Z=\left(z_{i_{1}\ldots i_{d}}\right)$ such that

We prove by induction on $n$ the following statement:

and the statement holds. Assuming that $n\geq 2$, let us consider two tensors $A,B\in\mathcal{U}_{n}$ that differ in one slice only. Without loss of generality, we assume that $B$ is obtained from $A$ by replacing the “top slice” numbers $a_{1i_{2}\ldots i_{d}}$ with numbers $b_{1i_{2}\ldots i_{d}}$. We use a $d$-dimensional version of the Laplace expansion:

Proofs of Theorems 1.2, 2.2 and 3.4

As in Section 4, we start with a simple geometric lemma.

for some complex numbers $\alpha_{1},\ldots,\alpha_{n}$ and $\beta_{1},\ldots,\beta_{n}$.

Suppose that $\alpha_{1},\ldots,\alpha_{n}$ are non-negative real and that $\beta_{1},\ldots,\beta_{n}$ are real such that

Suppose that $\alpha_{1},\ldots,\alpha_{n}$ and $\beta_{1},\ldots,\beta_{n}$ are real such that

for some $0\leq\eta<1$. Then $v\neq 0$, $w\neq 0$ and the angle between $v$ and $w$ does not exceed $2\arctan\eta$.

for some $0\leq\eta<1$ and some $0\leq\tau<1-\eta$. Then $v\neq 0$, $w\neq 0$ and the angle between $v$ and $w$ does not exceed

It follows that $v\neq 0$, $w\neq 0$ and that the angle between $v$ and $w$ is

with the equality attained when $|v|^{2}=|w|^{2}=|u|^{2}+|x|^{2}$ and $x$ is orthogonal to $u$. Hence for given $|u|$ and $|x|$ the largest angle of

between $v$ and $w$ is attained when $x$ is orthogonal to $u$ and is equal to

By Part (2), $v^{\prime}\neq 0$, $w^{\prime}\neq 0$ and the angle between $v^{\prime}$ and $w^{\prime}$ does not exceed $\theta=2\arctan\eta$. Since

Since $0\leq\tau<1-\eta$, we have $v=v^{\prime}+iv^{\prime\prime}\neq 0$, $w=w^{\prime}+iw^{\prime\prime}\neq 0$ and the angle between $v$ and $v^{\prime}$ and the angle between $w$ and $w^{\prime}$ do not exceed

Therefore the angle between $v$ and $w$ does not exceed $\theta+2\omega$ and the proof of Part (3) follows. $\square$

For a positive integer $n$, let $\mathcal{U}_{n}$ be the set of $n\times n$ complex matrices $Z=\left(z_{ij}\right)$ such that

We prove by induction on $n$ the following statement:

2 Proof of Theorem 2.2

Since $\tau<1-\eta$, the statement holds for $n=1$. Suppose that $n>1$. As in Section 4.2, without loss of generality we assume that $A$ and $B$ differ in the first row and column only. Let $A_{j}$ be the $(2n-2)\times(2n-2)$ matrix obtained from $A$ by crossing out the first row and the first column and the $j$-th row and the $j$-th column. As in Section 4.2, we observe that, up to a simultaneous permutation of rows and columns (which does not change the hafnian), any two matrices $A_{j_{1}}$ and $A_{j_{2}}$ differ only in the $k$-th row and $k$-th column for some $k$. Using the expansion (4.2.1), we complete the induction as in Section 5.1. $\square$

3 Proof of Theorem 3.4

By and large, the proof proceeds as in Section 5.1. For a positive integer $n$, we define $\mathcal{U}_{n}$ as the set of $n\times\ldots\times n$ complex arrays $Z=\left(z_{i_{1}\ldots i_{d}}\right)$ such that

for all $1\leq i_{1},\ldots,i_{d}\leq n$. We prove by induction on $n$ the following statement:

Proofs of Theorems 1.5 and 3.5

Since Theorem 1.5 is a particular case of Theorem 3.5 for $d=2$, we prove the latter theorem. We use a combinatorial interpretation of the multi-dimensional permanent in terms of matchings in a hypergraph.

If $|V|<d$ then $H$ has no edges and hence $P_{H}(w)=P_{H-v}(w)=1$. Suppose now that $|V|\geq d$. We observe the following recurrence:

where the $P_{H-\{v\}}(w)$ accounts for the matchings in $H$ not containing $v$ and the sum accounts for the matchings of $H$ containing $v$. By the induction hypothesis, $P_{H-\{v\}}(w)\neq 0$, so we rewrite (6.1.2) as

If there are no edges $e$ containing $v$ then $P_{H}(w)=P_{H-\{v\}}(w)$ and (6.1.1) follows. Otherwise, let $e=\{v,v_{2},\ldots,v_{d}\}$ be an edge containing $v$. Telescoping, we obtain

By the induction hypothesis, each ratio in the right hand side of (6.1.4) does not exceed $d/(d-1)$ in the absolute value, and hence

from which it follows that $P_{H}(w)\neq 0$. Denoting

from (6.1.5) we have a chain of implications

The bound of Lemma 6.1 and to some extent its proof agrees with those of for the roots of the matching polynomial of a graph.

Next, we need a weaker version on an estimate from .

Let $\alpha\approx 0.278$ be the constant of Theorem 3.5, so that $\alpha e^{1+\alpha}=1$. For a positive integer $n$, let

Proof. We observe that if $|z|\leq\alpha$ then

Finally, we need a theorem of Szegő, see for example, Chapter IV of and also for generalizations.

be complex polynomials. We define the Schur product $h=f\ast g$ by

Suppose that $f(z)\neq 0$ whenever $|z|\leq r_{1}$ and $g(z)\neq 0$ whenever $|z|\leq r_{2}$ for some $r_{1},r_{2}>0$.

Then $h(z)\neq 0$ whenever $|z|\leq r_{1}r_{2}$.

2 Proof of Theorem 3.5

Let $H$ be the complete $d$-partite hypergraph with set $V$ of $nd$ vertices, split into $d$ parts and vertices in each part numbered $1$ through $n$. Each edge of $H$ consist of exactly one vertex from each part and we let the weight of edge $\left(i_{1},\ldots,i_{d}\right)$ equal to $w_{i_{1}\ldots i_{d}}=z_{i_{1}\ldots i_{d}}-1$. For $k=1,\ldots,n$, let $W_{k}$ be the total weight of all matchings in $H$ consisting of exactly $k$ edges. We write

Then $f(z)$ is the value of the matching polynomial $P_{H}$ on the scaled weights $zw_{i_{1}\ldots i_{d}}$ and from Lemma 6.1 we conclude that

Let $p_{n}$ be the polynomial of Lemma 6.2. Applying Lemma 6.2 and Theorem 6.1 to the Schur product $h=f\ast p_{n}\ast\cdots\ast p_{n}$ of $f$ and $d-1$ polynomials $p_{n}$, we conclude from (6.2.1) that

Proofs of Theorems 1.4, 1.6, 2.4, 3.2 and 3.6

We need the following simple result first obtained in . For completeness, we give its proof here.

be the Taylor polynomial of $f(z)$ of degree $m$ computed at $z=0$. Then

Using the Taylor series expansion for the logarithm, we obtain

It follows from Lemma 7.1 that as long as the roots of a polynomial $g(z)$ stay at distance at least $\beta$ away from for some fixed $\beta>1$, then to approximate $\ln g(1)$ within an additive error $\epsilon$, we can use the Taylor polynomial of $f(z)=\ln g(z)$ at $z=0$ of degree $m=O(\ln\deg g-\ln\epsilon)$, where the implied constant in the “$O$” notation depends on $\beta$ only.

As is discussed in , the computation of the first $m$ derivatives $f^{(1)}(0),\ldots,f^{(m)}(0)$ of $f(z)=\ln g(z)$ reduces to the computation of the first $m$ derivatives $g^{(1)}(0),\ldots,g^{(m)}(0)$ of $g$. Indeed,

where $g^{(0)}(0)=g(0)\neq 0$. Writing equations (7.1.1) for $k=1,\ldots,m$ we obtain a non-singular triangular system of linear equations in $f^{(k)}(0)$ with numbers $g(0)\neq 0$ on the diagonal from which the values of $f^{(1)}(0),\ldots,f^{(m)}(0)$ can be computed in $O(m^{2})$ time from the values of $g(0),g^{(1)}(0),\ldots,g^{(m)}(0)$. Thus

and, generally, $f^{(k)}(0)$ is a linear combination of expressions of the type

Note that computing $f^{(k)}(0)$ from $g^{(k)}(0)$ is akin to computing cumulants of a distribution from its moments.

2 Proof of Theorem 1.4

Let $J=J_{n}$ be the $n\times n$ matrix filled with 1s and let $A=\left(a_{ij}\right)$ be an $n\times n$ complex matrix satisfying the conditions of the theorem. We define a univariate polynomial

be the Taylor polynomial of degree $m$ computed at $z=0$. It follows from Lemma 7.1 that for some constant $\gamma=\gamma(\eta)>0$ and integer $m\leq\gamma(\ln n-\ln\epsilon)$ we have

It remains to show that $T_{m}(1)$ is a polynomial $p$ in the entries $a_{ij}$ of the matrix $A$ of degree at most $m$. In view of Section 7.1 and the fact that $g(0)=n!$, it suffices to check that $g^{(k)}(0)$ is a polynomial in the entries $a_{ij}$ of the matrix $A$ of degree at most $k$ which can be computed in $n^{O(k)}$ time, where the implied constant in the “$O$” notation is absolute. We have

where the last sum is taken over all ordered sets $(i_{1},\ldots,i_{k})$ of distinct numbers between $1$ and $n$. By symmetry, we can further write

where the last sum is taken over all $(n!/(n-k)!)^{2}\leq n^{2k}$ pairs of ordered sets $(i_{1},\ldots,i_{k})$ and $(j_{1},\ldots,j_{k})$ of distinct numbers between $1$ and $n$. $\square$

It follows that the polynomial $p$ of Theorem 1.4 can be computed in time $n^{O(\ln n-\ln\epsilon)}$, where the implied constant in the “$O$” notation depends on $\eta$ alone.

3 Proof of Theorem 2.4

The proof is very similar to that of Section 7.2. Let $J=J_{2n}$ be the $2n\times 2n$ matrix filled with 1s and let $A=\left(a_{ij}\right)$ be a $2n\times 2n$ symmetric complex matrix satisfying the conditions of theorem. We define a univariate polynomial

where the sum is taken over all $(2n)!/2^{n}n!$ unordered partitions of the set $\{1,2,\ldots,2n\}$ into $n$ pairwise disjoint unordered pairs $\{i_{1},j_{1}\},\ldots,\{i_{n},j_{n}\}$. Hence for $k>0$ we have

where the sum is taken over all unordered collections $\{i_{1},j_{1}\},\ldots,\{i_{k},j_{k}\}$ of pairwise disjoint unordered pairs.

The proof then proceeds as in Section 7.2. $\square$

It follows that the polynomial $p$ of Theorem 2.4 can be computed in time $n^{O(\ln n-\ln\epsilon)}$, where the implied constant in the “$O$” notation depends on $\eta$ alone.

4 Proof of Theorem 3.2

Let $J=J_{n,d}$ be the $d$-dimensional $n\times\ldots\times n$ tensor filled with 1s and let $A$ be the tensor satisfying the conditions of the theorem. We introduce a univariate polynomial

where the last sum is taken over all ordered $k$-tuples $(i_{1},\ldots,i_{k})$ of distinct indices $1\leq i_{j}\leq n$. By symmetry we can write

where the last sum is taken over all $(n!/(n-k)!)^{d}\leq n^{kd}$ collections of $d$ ordered $k$-tuples $\left(i_{1j},\ldots,i_{kj}\right)$ for $j=1,\ldots,d$ of distinct indices $1\leq i_{1j},\ldots,i_{kj}\leq n$. The proof then proceeds as in Section 7.2. $\square$

The polynomial $p$ can be computed in $n^{O(\ln n-\ln\epsilon)}$ time, where the implied constant in the “$O$” notation depends on $\eta$ and $d$ only.

5 Proof of Theorems 1.6 and 3.6

As Theorem 1.6 is a particular case of Theorem 3.6, we prove the latter theorem only. As in Section 7.4, we define the univariate polynomial (7.4.1). By Theorem 3.5, we have

and the proof follows as in Section 7.4. $\square$

Proofs of Theorems 1.1, 2.1 and 3.3

Lemma 7.1 allows us to approximate the value of $\ln g(1)$ by a low degree Taylor polynomial of $\ln g(z)$ at $z=0$ provided the polynomial $g(z)$ does not have zeros in a disc of radius $\beta>1$ centered at $z=0$. In view of Theorems 1.2, 2.2 and 3.4, we would like to construct a similar approximation under a weaker assumption that $g(z)\neq 0$ for $z$ in some neighborhood of the interval $$in the complex plane. To achieve that, we first construct a polynomial$\phi$such that$\phi(0)=0$,$\phi(1)=1$and such that$\phi$maps the disc$|z|\leq\beta$for some$\beta>1$inside the neighborhood. We then apply Lemma 7.1 to the composition$g(\phi(z))$. The following lemma provides an explicit construction of such a polynomial$\phi$.

Then $\phi(z)$ is a polynomial of degree $N$ such that $\phi(0)=0$, $\phi(1)=1$,

Proof. Clearly, $\phi(z)$ is a polynomial of degree $N$ such that $\phi(0)=0$ and $\phi(1)=1$. It remains to prove that $\phi$ maps the disc $|z|\leq\beta$ into the strip $-\rho\leq\Re\thinspace z\leq 1+2\rho$, $\left|\Im\thinspace z\right|\leq 2\rho$.

the function $F_{\rho}(z)$ is well-defined by the choice of a branch of the logarithm, which we choose so that

Combining (8.0.1), (8.0.2) and (8.0.3), we conclude that for $|z|\leq\beta$ we have

Substituting $z=1$ in (8.0.3) and using (8.0.2), we conclude that

where $\rho P_{N}(\alpha)$ is positive real, which by (8.0.5) satisfies

Let $A=\left(a_{ij}\right)$ be an $n\times n$ real matrix satisfying the conditions of the theorem and let $J=J_{n}$ be the $n\times n$ matrix filled with 1s. As in Section 7.2, we define a univariate polynomial

for some $\xi>0$ and $\zeta>0$. Then the entries $b_{ij}$ of the matrix $B=J+z(A-J)$ satisfy

and then choose $\zeta=\zeta(\delta)>0$ such that

By Theorem 1.2, we have $r(z)\neq 0$ for $z$ satisfying (8.1.1).

Using Lemma 8.1, we construct a univariate polynomial $\phi$ of some degree $N=N(\delta)$ such that $\phi(0)=0$, $\phi(1)=1$ and $\phi$ maps the disc $\{z:\ |z|\leq\beta\}$ inside the strip (8.1.1), where $\beta=\beta(\delta)>1$. Let

Then $g(z)$ is a univariate polynomial such that $\deg g\ \leq\ Nn$,

where we chose the branch of the logarithm such that $f(0)=\ln n!$ is real. Let $T_{m}(z)$ be the Taylor polynomial of $f(z)$ of degree $m$ computed at $z=0$. By Lemma 7.1, we have

for some $m\leq\gamma(\ln n-\ln\epsilon)$ where $\gamma=\gamma(\delta)>0$ is a constant depending on $\delta$ alone. It remains to show that $T_{m}(1)$ is a polynomial in the entries of $A$ of degree not exceeding $m$.

For a univariate polynomial $p(z)$, let $p_{[m]}$ be the polynomial obtained from $p$ by discarding all monomials of degree higher than $m$. Since $\phi(0)=0$, the constant term of of $\phi$ is and therefore

In words: to compute the polynomial $g_{[m]}$ obtained from $g$ by discarding the monomials of degree higher than $m$, it suffices to compute the polynomials $r_{[m]}$ and $\phi_{[m]}$ obtained from $r$ and $\phi$ respectively by discarding the monomials of degree higher than $m$, and then discard the monomials of degree higher than $m$ in the composition $r_{[m]}(\phi_{[m]})$.

From Section 7.2, it follows that $r^{(k)}(0)$ is a polynomial of degree $k$ in the entries of the matrix $A$. It follows then that $g^{(k)}(0)$ is a polynomial in the entries of $A$ of degree at most $k$ that can be computed in $n^{O(k)}$ time (the implied constant in the “$O$” notation is absolute). From Section 7.1 it follows then that $f^{(k)}(0)$ is a polynomial in the entries of $A$ of degree at most $k$, which completes the proof. $\square$

2 Proof of Theorem 2.1

Given a $2n\times 2n$ real symmetric matrix $A$ satisfying the conditions of the theorem, we define the univariate polynomial $r(z)$ by

where $J=J_{2n}$ is the $2n\times 2n$ matrix filled with 1s and the proof then proceeds as in Section 8.1, only that the reference to Theorem 1.2 is replaced by the reference to Theorem 2.2 and the reference to Section 7.2 is replaced by the reference to Section 7.3. $\square$

3 Proof of Theorem 3.3

Given a $d$-dimensional $n\times\ldots\times n$ tensor $A$ satisfying the conditions of the theorem, we define the univariate polynomial $r(z)$ by

where $J=J_{d,n}$ is the $d$-dimensional $n\times\ldots\times n$ tensor filled with 1s. Suppose that (8.1.1) holds for some $\xi>0$ and $\zeta>0$. Then the entries $b_{i_{1}\ldots i_{d}}$ of the tensor $B=J+z(A-J)$ satisfy

and then choose $\zeta=\zeta(\eta)>0$ such that

By Theorem 3.4, we have $r(z)\neq 0$ for $z$ satisfying (8.1.1) with $\xi$ and $\zeta$ so chosen. The proof then proceeds as in Section 8.1, only that the reference to Section 7.2 is replaced by the reference to Section 7.4. $\square$

Concluding remarks

2 Connections to the Szegő curve

Kontorovich and Wu noticed that the location of the complex zeros of $r(z)$, which is crucial for our analysis of the approximation of the permanent, for $A=nI$ can be determined from a result of Szegő, who showed in 1922 that as $n\longrightarrow\infty$, the zeros of the polynomial

3 Connections to the mixed characteristic polynomial

In their solution of the Kadison - Singer problem, Marcus, Spielman and Srivastava introduced and studied the mixed characteristic polynomial of $n$ Hermitian $n\times n$ matrices $Q_{1},\ldots,Q_{n}$,

where $W_{k}(A)$ is the sum of permanents of the $k\times k$ submatrices of $A$, so up to a sign and a substitution $x\longmapsto-1/x$, the polynomial $p_{A}$ is the matching polynomial of Section 6 (and the fact that the roots of $p_{A}$ are non-negative real is a particular case of the Heilmann - Lieb Theorem ). On the other hand,

The relation between $p$ and $r$ is essentially used in the proof of Theorem 3.5, which was absent in the version of the paper the referee commented on, but was obtained before the author received the comment.

On the other hand, the general mixed characteristic polynomial may appear useful for approximating the mixed discriminant of $Q_{1},\ldots,Q_{n}$, which, up to a sign is just the constant term of $p_{Q_{1},\ldots,Q_{n}}$.

4 Approximation of general polynomials

As another example, we consider the independence polynomial of graph. Let $G=(V,E)$ be a graph (undirected, without loops or multiple edges) with set $V$ of vertices and set $E$ of edges. A set $S\subset V$ is called independent if no two vertices in $S$ span an edge of $G$ (the empty set $S=\emptyset$ is considered independent). The independence polynomial of $G$ is defined as

Then $p_{G}(1)$ is the number of all independent sets in $G$, a quantity of considerable combinatorial interest. On the other hand, the value of the derivative $p_{G}^{(k)}(0)$ can be computed in $|V|^{O(k)}$ time by a direct inspection of all $k$-subsets $S\subset V$.

Suppose we know that $p_{G}(z)\neq 0$ provided $|z|\leq\beta$ for some $\beta>0$ (for example, $\beta$ can be the Dobrushin bound, see and ). Lemma 7.1 then implies that for any $0\leq\lambda<1$, fixed in advance, the value of $p_{G}(z)$ can be approximated within a relative error $0<\epsilon<1$ in quasi-polynomial time $|V|^{O(\ln|V|-\ln\epsilon)}$ provided $|z|\leq\lambda\beta$, see for many examples of this nature and also and for algorithms based on the “correlation decay” idea.

On the other hand, for a general graph $G$ there cannot be such a sleeve $S$ unless NP-complete problems admit a quasi-polynomial time algorithm. Indeed, generally, it is an NP-hard problem to approximate $p_{G}(z)$ for a real $z>\lambda\beta$, where $\lambda>0$ is some absolute constant and $\beta$ is the Dobrushin lower bound on the absolute value of the roots of $p_{G}(z)$ . This means that for a general graph $G$ one can expect the complex roots of $p_{G}(z)$ to “surround” the origin, so that there is no possibility to squeeze a sleeve between them to connect 0 and 1.

Since the first version of this paper appeared as a preprint, this general direction was pursued further in .

5 Approximating multi-dimensional permanents better

It would be interesting to extend the class of polynomials for which a version of Theorems 1.1 and 2.1 can be obtained. While we failed to obtain such a version for the multi-dimensional permanent (see Section 3), there does not seem to be a computational complexity obstacle for such an extension to exist. In it is shown that the $d$-dimensional permanent of a $n\times\ldots\times n$ tensor with positive entries between an arbitrarily small $\delta>0$, fixed in advance, and 1 can be approximated within an $n^{O(1)}$ factor in polynomial time, where the implicit constant in the “$O$” notation depends only on $d$ and $\delta$, which can be viewed as an indirect evidence that Theorem 1.1 can indeed be extended to multi-dimensional permanents.