Hyperbolicity and stable polynomials in combinatorics and probability

Introduction

These lectures concern the development and uses of two properties, hyperbolicity and stability. Hyperbolicity has been used chiefly in geometric and analytic contexts, concerning wave-like partial differential equations, lacunas, and generalized Fourier transforms. Stability has its origins in control theory but has surfaced more recently in combinatorics and probability, where its algebraic properties, such as closure under various operations, are paramount. We begin with the definitions.

A non-homogeneous $d$-variable polynomial $q$ with leading homogeneous part $p$ is said to be hyperbolic if and only if $p({\bf x})\neq 0$ and there is some $t_{0}>0$ such that

The complex polynomial $q$ is said to be stable if and only if

A real stable polynomial is one that is both real and stable.

The following relation holds between these two definitions.

A real homogeneous polynomial $p$ is stable if and only if it is hyperbolic in direction $\xi$ for every $\xi$ in the positive orthant.

The notion of hyperbolicity for polynomials has been around since its introduction by L. Gårding sixty years ago [Går51].Gårding credits many of the ideas to I. G. Petrovsky in his seminal paper [Pet45]. The notion of stability for real or complex polynomials in several variables goes back at least to multivariate versions of Hurwitz stability in the 1980’s, but appears to have become established as tools for combinatorialists only in the last five years [COSW04, Brä07, BBL09, Gur08]. These two related notions have now been applied in several seemingly unrelated fields.

In control theory, a continuous-time (respectively discrete-time) system whose transfer function is rational will be stable if its poles all lie in the open left half-plane (respectively the open unit disk). Accordingly, we say a univariate polynomial is Hurwitz stable (respectively Schur stable) if its zeros are all in the open left half-plane (respectively the open unit disk). Multivariate generalizations of Hurwitz and Schur stability have arisen in a variety of problems. The development of these generalizations splits into two veins. The review paper [Sok05] surveys a number of “hard” results on zero-free regions, meaning results that give good estimates on zero-free regions that depend on specific parameters of the models or graphs from which the polynomial is formed. Most relevant to the applications in Sections 6 and 7 are “soft” results, which give simple domains free of zeros (such as products of half planes), valid for all graphs or for wide classes of graphs.

The development of this vein of multivariate stable function theory took place mainly in the area of statistical physics and combinatorial extensions thereof. Multivariate Schur stability arises in the celebrated Lee–Yang Theorem for ferromagnetic Ising models [YL52, LY52], where it implies the absence of phase transitions at nonzero magnetic field. Likewise, multivariate Hurwitz stability arises in electrical circuit theory [FB85, COSW04, Sok11] and matroid generalizations thereof [COSW04, Brä07, WW09], and has applications to combinatorial enumeration [Wag06, Wag08]. It also arises in generalizations of the Lee–Yang Theorem [LS81] and in the Heilmann-Lieb Theorem for matching polynomials (also known as monomer-dimer models) [HL72, COSW04]. It should be noted that Hurwitz stability [Hur96], differs from the notion in Definition 1.2 in that the zero-free region is the right half-plane rather than the upper half-plane. For general complex polynomials the two notions are equivalent under a linear change of variables, but for real polynomials the two notions are very different. Except for brief portions of Sections 4 and 5, our concern will be with stability as defined in Definition 1.2

Multivariate stability behaves nicely under certain transformations. The closure properties were investigated further by Borcea and Brändén [BB09a]. These closure properties turn out to have powerful implications for systems of negatively dependent random variables, as worked out in 2009 by Borcea, Brändén and Liggett [BBL09]. My second brush with this subject was when I needed to apply some of their results to determinantal point processes [PP11].

These two encounters with hyperbolic/stable polynomials in seemingly dissimilar areas of mathematics prompted my search for a unified understanding. As pointed out at the end of the introduction of [BBL09], such a viewpoint was taken 25 years ago by Gian-Carlo Rota.

“The one contribution of mine that I hope will be remembered has consisted in just pointing out that all sorts of problems of combinatorics can be viewed as problems of the locations of zeros of certain polynomials…”

to which we would add “and also problems in differential equations, number theory, probability, and perhaps many more areas.”

Presently, the greatest interest in the subject of hyperbolic/stable polynomials seems to be its potential for unlocking some combinatorial conjectues concerning determinants such as the Bessis–Moussa–Villani conjecture, Lieb’s “permanent on top” conjecture and extensions of the van der Waerden conjecture, proved in 1979, but still an active subject (see, e.g., [Gur06]). The distances between areas of mathematics in which hyperbolicity plays a role are such that it was difficult to find a primary subject classification for these lectures. It also poses a unique challenge for me, as I am an expert in none of these, save for applications to analytic combinatorics. I therefore apologize in advance for any historical inaccuracies perpetrated here, or for idiosyncratic viewpoints arising from my personal history with the subject. Here follows an attempt to lay out its two main pillars, hyperbolicity and stability, and to follow their progress up to the present day.

Origins, definitions and properties

on the halfspace $\{{\bf x}:{\bf x}\cdot\xi\geq 0\}$ may be interpreted as the evolution of $g$ under the equation $D[q](f)=0$ with initial condition $g$. One would expect $m-1$ further initial conditions, such as $(\partial^{j}/\partial x_{\xi}^{j})f=g_{j}$ for $1\leq j\leq m-1$, where $(\partial/\partial x_{\xi})$ denotes a derivative in direction $\xi$ and $m$ is the degree of $q$.

The differential equation (2.1) is stable in direction $\xi$ if and only if $q$ is hyperbolic in direction $\xi$.

Let us assume without loss of generality that $\xi=(0,\ldots,0,1)$. If $q(\xi)=0$ then $f_{\xi}$ is a solution to $D[q](f)=0$. If $q$ is not hyperbolic in direction $\xi$ then there is some $(r_{1},\ldots,r_{d-1})$ such that the $d$ solutions to $q(r_{1},\ldots,r_{d-1},t)=0$ include at least one conjugate pair of values that are not real. Denoting by $r_{d}$ the one with the negative imaginary part, we see that $f_{\bf r}({\bf x})$ grows exponentially as $x_{d}$ increases. By homogeneity, $f_{\lambda{\bf r}}$ grows at $\lambda$ times the exponential rate. Choose $c_{\lambda}$ so that $c_{\lambda}f_{\lambda{\bf r}}(0,\ldots,0,1)=1$. Then $f_{n{\bf r}}\to 0$ on the hyperplane $H_{\xi}$ in the topology of uniform convergence (due to periodicity, no compact set restriction is required), while $f_{n{\bf r}}\equiv 1$ at $(0,\ldots,0,1)$, proving the contrapositive, namely that lack of hyperbolicity implies lack of stability. $\hfill\Box$

Removing all the handwaving takes considerable work, beyond our scope here. The key is the construction of the Riesz kernel, which is interesting enough to merit a brief digression. Suppose that $q$ is $m$-homogeneous and hyperbolic in direction ${\bf x}$ and let $\alpha$ is any complex number. Define the Riesz kernel $Q_{\alpha}$ by

The Riesz kernels with parameters $\alpha$ and $\alpha-1$ are related by a differential identity as long as $\alpha\neq 1$. When $\alpha=1$, the Riesz kernel is called the fundamental solution by reason of a result of Gårding. This is explained more fully in Theorem 2.8 below, but the short statement, found for instance in [Gül97, Theorem 2.2], is that the solution of

exists, is unique, and is supported on the dual cone, $C^{*}$.

2 Homogeneous hyperbolic polynomials

Many of the properties of hyperbolic polynomials are easier to state, prove and understand in the homogeneous case. Throughout this section, therefore, we deal only with homogeneous polynomials. We will use $p$ rather than $q$ as a visual cue when speaking about homogeneous polynomials. Hyperbolicity is easily seen to be equivalent to the equivalent to the following “real root” property.

Denote by $t_{k}({\bf x},{\bf y})$ the roots of $t\mapsto p({\bf y}+t{\bf x})$. Then

By Proposition 2.2, when $p$ is hyperbolic in direction $\xi$, all values $t_{k}({\bf x},{\bf y})$ are real, hence, setting $t=0$, we see that $p/p({\bf x})$ is a real polynomial. We see that little generality is lost in restricting our discussion of homogeneous polynomials to those with real coefficients.

The two nontrivial examples of hyperbolic polynomials given in Gårding’s original paper, namely Lorentzian quadratics and the determinant, provide much of the intuition as to the meaning of hyperbolicity. We now discuss these. A preliminary observation is that, trivially, all real homogeneous polynomials of degree one are hyperbolic in all directions in which they do not vanish. Next, observe that hyperbolicity of the homogeneous polynomial $p$ in direction $\xi$ is preserved when $p$ and $\xi$ are transformed by the same invertible real linear map. This allows us to classify all nondegenerate quadratics: it suffices to consider all polynomials of the form $\sum_{j=1}^{d}\pm x_{j}^{2}$, hyperbolicity evidently being determined by signature. A necessary and sufficient condition for hyperbolicity is Lorentzian signature, that is precisely one sign different from the others.

Let $p({\bf x}):=x_{1}^{2}-\sum_{j=2}^{d}x_{j}^{2}$. Real vectors $\xi$ may be classified as time-like, light-like or space-like according to whether $p(\xi)$ is respectively positive, zero or negative. The time-like vectors form the open convex cone $\{{\bf x}:(x_{2}/x_{1})^{2}+\cdots+(x_{d}/x_{1})^{2}<1\}$. Fix any time-like vector $\xi$. If $\eta=\lambda\xi$ then the line $t\mapsto\eta+t\xi$ contains a doubled root of $p$ at the origin. For any other real $\eta$, the line $\eta+t\xi$ intersects the hyperplane $H_{\xi}$ orthogonal to $\xi$ at some point other than the origin and $p$ takes a negative value there. On the other hand, the quadratic $p(\eta+t\xi)$ has positive leading term, so goes to $+\infty$ at $t=\pm\infty$. Hence the line intersects the zero set of $p$ twice. The degree of $p$ is two, hence for any $\eta$, the polynomial $t\mapsto p(\eta+t\xi)$ has all real roots. Hence $p$ is hyperbolic. Replacing $p$ by $-p$ does not affect hyperbolicity. Hence homogeneous quadratics with signature 1 or $d-1$ are hyperbolic in timelike directions.

For the converse, elliptic quadratics have lines in every direction with no real roots, hence are obviously not hyperbolic. If $d>4$ and there are at least two positive and two negative directions, the any line on which $p$ has a minimum may be translated in a positive direction not on the line so that the minimum becomes positive, and similarly any line on which $p$ has a maximum may be translated so that the maximum becomes negative. We conclude there are no directions of hyperbolicity.

The other classical example is as follows.

where $(bA)^{1/2}$ is the Hermitian positive definite square root of $bA$. If this quantity is equal to zero then $-i$ is an eigenvalue of $(bA)^{-1/2}(aA+M)(bA)^{-1/2}$ which is impossible because this matrix is Hermitian.

There are several ways to construct new hyperbolic functions from old ones. Note that the first does not require homogeneity.

Let $q_{1}$ and $q_{2}$ be hyperbolic with respect to ${\bf x}$. Then $q_{1}q_{2}$ is also hyperbolic with respect to ${\bf x}$.

Let $p$ be homogeneous of degree $m$ and hyperbolic with respect to ${\bf x}$. Let $p_{0},\ldots,p_{m}$ be the coefficients of $p({\bf y}+t{\bf x})$ as a polynomial in $t$:

Then $p_{k}$ is hyperbolic with respect to ${\bf x}$ for all $0\leq k\leq m$.

Now consider the expansion (2.4) of $p({\bf y}+t{\bf x})$ into homogeneous parts. The parts are given by

Hyperbolicity in direction ${\bf x}$ is stable under $D_{\bf x}$, which shows that $p_{k}$ is hyperbolic in direction ${\bf x}$. $\hfill\Box$

3 Cones of hyperbolicity for homogeneous polynomials

Hyperbolic polynomials have associated with them certain convex cones. In the homogeneous case the definition is simple and is contained in the following proposition. This was proved first in [Går51] and reproduced many times; the proof below follows [Gül97]. Let $p$ be a (complex) homogeneous hyperbolic polynomial, hyperbolic in direction $\xi$. Dividing by a real multiple of $p(\xi)$ we may assume, cf. (2.3), that $p$ is real and $p(\xi)=1$.

$p$ is hyperbolic in direction ${\bf x}$ for every ${\bf x}\in K(p,\xi)$.

The set $K(p,\xi)$ is an open convex cone; we call this a cone of hyperbolicity for $p$.

$K(p,\xi)$ is equal to the set $K$ of vectors ${\bf x}$ for which all roots of $t\mapsto p({\bf x}+t\xi)$ are real and negative, which (by hyperbolicity of $p$ in direction $\xi$) is the same as the set of vectors ${\bf x}$ for which no root of this polynomial is real and nonnegative.

Next we check that for ${\bf v}\in K$, ${\bf x}$ real, and $s$ and $t$ complex,

First, suppose $\Im(s)<0$. If $u\geq 1$ then the polynomial

is nonvanishing for real $t$ because this is $p$ evaluated at the sum of a real vector and a complex multiple of $\xi$ with nonzero imaginary part. As $u\to\infty$, the number of roots of (2.6) in the lower half-plane remains constant. The limit at $u=\infty$ is $t\mapsto p(t{\bf v}-i\xi)$. This has roots in the upper half-plane because its roots are $-i$ divided by the roots of $t\mapsto p({\bf v}+t\xi)$, the latter of which we have seen to be negative real. We conclude that for $u=1$ there are no roots in the lower half-plane, in other words,

To see that this also holds for $\Im(s)=0$ and $\Im(t)<0$, note that $K$ is open, so ${\bf v}-\epsilon\xi\in K$ for some $\epsilon>0$, whence

which is nonzero by (2.7). This completes the verification of (2.5).

Setting $s=0$ in (2.5) shows that any root of $t\mapsto p({\bf x}+t{\bf v})$ satisfies $\Im(t)\geq 0$. Because $p$ is real, complex conjugation may be applied to the entire argument, showing that also $\Im(t)\leq 0$, and hence that all roots of $t\mapsto p({\bf x}+t{\bf v})$ are real. The vector ${\bf v}$ was chosen arbitrarily in $K$. We conclude that $p$ is hyperbolic with respect to every ${\bf v}\in K$. It follows that $K$ is star convex with respect to ${\bf v}$ as well, and since ${\bf v}\in K$ is arbitrary, that $K$ is convex. $\hfill\Box$

Because the cones of hyperbolicity are characterized as components of the nonzero set in real space, it follows that the cones of hyperbolicity of $pq$ are pairwise intersections of the cones of hyperbolicity of $p$ with the cones of hyperbolicity of $q$.

Each coordinate function $z_{j}$ is homogeneous of degree 1, therefore hyperbolic in every direction not contained in the plane $\{z_{j}=0\}$. The cones of hyperbolicity are the two half spaces bounded by this plane. It follows that the product $\prod_{j=1}^{d}z_{j}$ is hyperbolic in every direction in which no coordinate vanishes, and that the cones of hyperbolicity are the orthants. This is also obvious from Figure 5.

where $\delta_{\bf x}$ is a delta function at ${\bf x}$.

Suppose the homogeneous polynomial $p$ is hyperbolic in direction $\xi$. Then there exists a unique distribution $E$ solving (2.8) and its support is the cone $K(p,\xi)^{*}$ dual to the cone of hyperbolicity of $p$ containing $\xi$. In fact $E$ is given as in inverse Fourier transform:

where $p_{-}(y)^{-1}:=\lim_{t\downarrow 0}p({\bf y}-it\nu)^{-1}$ as distributions and $\nu$ is any element of $K(p,\xi)$. $\hfill\Box$

Although there is no time here to explore the properties of hyperbolic polynomials as barrier functions, I will mention this example briefly, as it has proved to be of some importance to convex programming.

The interior point method for convex programming problems (see, e.g. [NN93]) is based on finding such a function for a given region, $Q$. There is a universal construction but it is not always useful for computations. Also, properties beyond those satisfied by the universal construction are required for long term stability of the interior point method. Such properties will depend on the region $Q$. When $Q$ is the cone of hyperbolicity for a homogeneous polynomial $p$, it turns out that the function $F({\bf x}):=-\log p({\bf x})$ is a logarithmically homogeneous self-concordant barrier function with a number of other useful properties. These are detailed in [Gül97].

Delving into the relation between hyperbolicity in the homogeneous and non-homogeneous cases, (definitions both given in Definition 1.1, we begin by looking at the homogeneous parts of a polynomial, $f$. Sorting the terms of $f$ by total degree, the highest degree part will be denoted $LT(f)$ for “leading term(s)”. The lowest degree is called the localization and will be discussed further in the next section. If $f$ is hyperbolic, then both the leading term and the localization are hyperbolic as well (respectively [ABG70, Lemma 3.20] and [ABG70, Lemma 3.42]). By definition, the cones of hyperbolicity of a non-homogeneous polynomial $f$ are the cones of hyperbolicity of $LT(f)$. When $f$ is hyperbolic, these cones still characterize the directions of stable propagation of PDE’s and supports of solutions to these.

Because hyperbolicity is easier to understand in the homogeneous case, Gårding looked for a converse to these and came up with a criterion for homogeneous polynomials called strong hyperbolicity. This is most naturally stated using the equivalent definition of hyperbolicity from Proposition 2.2: the roots of $p({\bf y}+t{\bf x})$ must not only be real but also distinct (except when ${\bf y}$ is a multiple of ${\bf x}$, when all the zeros coincide perforce). We then have:

If $A$ is strongly hyperbolic then $f$ is hyperbolic for any $f$ such that $LT(f)=A$.

This is proved as (3.9) of [ABG70] and in fact is already in [Går51] after the statement and proof of Lemma 2.5. Necessary and sufficient conditions for $f$ to be hyperbolic are given in [Hör83, Theorem 12.4.6]; these were conjectured by Gårding and proved first by Svensson [Sve68].

Semi-continuity and Morse deformations

Given a function $f$ analytic on a neighborhood of the origin, its order of vanishing is the least total degree of a nonvanishing term in its Taylor series. The sum of all such terms is called the homogeneous part of $f$ at the origin and denoted $\mbox{\elevenss hom}(f)$. For any ${\bf x}$ we let

denote the homogeneous part of $f$ at ${\bf x}$. When ${\bf x}\neq 0$, Atiyah et al. [ABG70] define this by taking the $t=0$ term of $t^{m}f(t^{-1}{\bf x}+{\bf y})$ as a function of ${\bf y}$, where $m-\deg(f)$, and they refer to this as the localization of $f$ at ${\bf x}$.

Proof: This follows from the conclusion (3.45) of [ABG70, Lemma 3.42]. Because the development there is long and complicated, we give here a short, self-contained proof, provided by J. Borcea [BP11, Proposition 2.8]. If $Q$ is a polynomial whose degree at zero is $k$, we may recover its leading homogeneous part $\mbox{\elevenss hom}(Q)$ by

The limit is uniform as ${\bf y}$ varies over compact sets. Indeed, monomials of degree $k$ are invariant under the scaling on the right-hand side, while monomials of degree $k+j$ scale by $\lambda^{-j}$, uniformly over compact sets.

Apply this with $Q(\cdot)=p({\bf x}+\cdot)$ and ${\bf y}+t{\bf u}$ in place of ${\bf y}$ to see that for fixed ${\bf x},{\bf y}$ and ${\bf u}$,

Let $p$ be a hyperbolic homogeneous polynomial and let $B$ be a cone of hyperbolicity for $p$. If $p({\bf x})=0$, define

As mentioned in passing in Section 2, a homogeneous polynomial $p$ is said to be strongly hyperbolic if the roots of $p({\bf y}+t{\bf x})$, in addition to being real, are distinct. Equivalently, the projective variety ${\cal V}:=\{{\bf x}:q({\bf x})=0\}$ is smooth. In this case, for each nonzero ${\bf x}$, the localization $\mbox{\elevenss hom}(p,{\bf x})$ has degree one. The cones of hyperbolicity $K^{p,B}({\bf x})$ are halfspaces whose common tangent hyperplane is tangent to $B$ at ${\bf x}$; the convexity of $B$ implies that the tangent hyperplane is a support hyperplane to $B$ at ${\bf x}$, and we see that indeed $K^{p,B}({\bf x})$ contains $B$.

Suppose ${\bf x}_{n}\to{\bf x}$. It is not in general true that $\mbox{\elevenss hom}(f,{\bf x}_{n})\to\mbox{\elevenss hom}(f,{\bf x})$. However, it is true that

for $n$ sufficiently large. This implies that if $p$ is homogeneous and hyperbolic with cone of hyperbolicity $B$, then $K^{p,B}({\bf x})$ is semi-continuous in ${\bf x}$:

This is proved in [ABG70, Lemma 5.9]. We will want a version of this valid for polynomials that are not necessarily homogeneous. If $q$ is hyperbolic but not homogeneous, the cone $K^{q,B}({\bf x})$ has not been defined. To do this, at least for some points ${\bf x}$, we need the notion of the amoeba of $q$.

2 Amoeba boundaries

The amoeba of any polynomial $q$ is defined to be the image of the zero set ${\cal V}:=\{{\bf z}:q=0\}$ of $q$ under the coordinatewise log modulus map ${\rm ReLog\,}({\bf z}):=(\log|z_{1}|,\ldots,\log|z_{d}|)$. We denote this image by ${\mbox{\elevenss amoeba}}(q)$.

The following result, proved in [BP11, Proposition 2.12], defines a family of cones via localizations on the boundary of an amoeba.

Let $q$ be any polynomial and let $B$ be a component of the complement of ${\mbox{\elevenss amoeba}}(q)$. Denote the boundary of $B$ by $\partial B$. Fix ${\bf x}\in\partial B$ and let $f=q\circ\exp$ so that $f$ vanishes at some point ${\bf x}+i{\bf y}$. Let $f_{\bf y}:=\mbox{\elevenss hom}(f,{\bf x}+i{\bf y})$. Then each $f_{\bf y}$ is hyperbolic (meaning hyperbolic in at least one direction) and one of its cones of hyperbolicity contains $B$. We denote this cone by $K^{q,B}({\bf y})$. (The point ${\bf x}$ is considered fixed and is suppressed from the notation.) $\hfill\Box$

One may extend semi-continuity for localizations beyond the homogeneous case, to the families in Proposition 3.5.

If $B$ is a component of ${\mbox{\elevenss amoeba}}(q)^{c}$ and ${\bf x}\in\partial B$, then the family of cones $K^{q,B}({\bf y})$ defined in Proposition 3.5 satisfies

The fact that localizations of any polynomial to points on the amoeba boundary are hyperbolic allows us to give numerous examples fo hyperbolic polynomials beyond the classic ones: planes, quadrics, and the determinant function. For example, the homogeneous polynomial variety shown in Figure 7 is a localization of the famous so-called fortress generating function denominator.

It is instructive to see what role hyperbolicity plays in Theorem 3.6 by considering the counterexample $f(x,y,z)=xy+z^{3}$ as in Figure 8. As ${\bf y}$ varies over a neighborhood $U$ of the origin, is it possible to choose open convex cones $\{K({\bf y}):{\bf y}\in U\}$ over ${\bf y}$ in such a way that $K({\bf y})$ varies semi-continuously with ${\bf y}$ and each $K({\bf y})$ is, locally, a subset of $\{{\bf y}:f({\bf y})\neq 0\}$?

The points ${\bf y}=(0,y,0)$ are forced to choose whether $K({\bf y})$ contains points with positive ${\bf x}$ components or negative ${\bf x}$ components. One of these violates semi-continuity with cones $K(0,y,\epsilon)$ as $\epsilon\downarrow 0$ while the other violates semi-continuity with cones $K(0,y,-\epsilon)$ as $-\epsilon\uparrow 0$. The key to avoiding this in Theorem 3.6 is that $f_{\bf y}$ must be hyperbolic, and this cannot happen with hyperbolic functions.

3 Morse deformations

Over any compact set $S$ a section $\{{\bf v}({\bf y}):{\bf y}\in S\}$ may be chosen continuously with ${\bf v}({\bf y})>0$ for all ${\bf y}\in S$.

Proof: Given ${\bf y}$, we may choose ${\bf v}$ in the interior of $K({\bf y})$ with ${\bf v}\cdot{\bf r}>0$, whence by semi-continuity, ${\bf v}\in K({\bf y}^{\prime})$ for all ${\bf y}^{\prime}$ in some neighborhood of ${\bf y}$ which we denote ${\cal N}({\bf y},{\bf v})$. We may cover the compact set $S$ with finitely many of these neighborhoods, $\{{\cal N}({\bf y}^{(k)},{\bf v}^{(k)}):1\leq k\leq m\}$. Let $\{\psi^{(k)}:1\leq k\leq m\}$ be a partition of unity subordinate to this cover and for any ${\bf y}\in S$ define

It is clear that ${\bf r}\cdot{\bf v}({\bf y})>0$ for all ${\bf y}\in S$. For each ${\bf y}\in S$, if $\psi^{(k)}({\bf y})>0$ then ${\bf v}^{(k)}\in K({\bf y})$. By convexity of $K({\bf y})$, it follows that ${\bf v}({\bf y})\in K({\bf y})$. $\hfill\Box$

If the homogeneous polynomial $q$ is strongly hyperbolic then its zero set is the cone over a smooth projective hypersurface and each $K({\bf y})$ is a halfspace (see Example 3.3). The condition that every $K({\bf y})$ contain a vector ${\bf v}$ with ${\bf r}\cdot{\bf v}>0$ is the same as requiring that ${\bf r}$ not be the outward normal to the bounding hyperplane of $K({\bf y})$. In other words, ${\bf r}$ may not be on the boundary of the dual cone to $B$.

With these vector fields in hand we have enough to carry out the programs of [ABG70] and [BP11]. I will briefly describe the former, then go into a little more detail on the latter. Let $q$ be a homogeneous polynomial, strongly hyperbolic in the direction ${\bf x}$. We wish to compute its inverse Fourier transform, which we have called the Riesz kernel, $Q_{\alpha}$. We recall that its value at ${\bf y}$ is given by

We set ${\bf r}=-{\bf y}$ and assume ${\bf r}$ not to be on the boundary of $B^{*}$, the dual cone of the cone $B$ of hyperbolicity of $q$ that contains ${\bf x}$. As we have seen in Example 3.9, this guarantees the existence of the 1-homogeneous vector field ${\bf v}(\cdot)$. The sets $K({\bf y})$ are convex and each contains both ${\bf x}$ and ${\bf v}({\bf y})$. Therefore, each contains the line segment joining ${\bf x}$ to ${\bf v}({\bf y})$. Define a homotopy by

4 Asymptotics of Taylor coefficients

Let $F=P/Q=\sum_{\bf r}a_{\bf r}{\bf Z}^{\bf r}$ be a Laurent series expansion converging on the component $B$ of ${\mbox{\elevenss amoeba}}(Q)^{c}$. The coefficients $\{a_{\bf r}\}$ of $F$ may be recovered via Cauchy’s formula

Exact evaluation of the Cauchy integral (3.3) is not easy but some methods are known for evaluating it asymptotically. In the case where the pole variety ${\cal V}:=\{{\bf z}:Q({\bf z})=0\}$ is smooth, a formula was given in [PW02]; a coordinate free version is given in [BBBP08]. Normal self-intersection in ${\cal V}$ can also be dealt with [PW04]. A number of examples from combinatorics and statistical physics have generating functions whose pole variety has a singularity with nontrivial monodromy. In the remainder of this section I will explain how hyperbolicity and the resulting deformations allow explicit asymptotic evaluation of some of these generating functions.

So as to keep the conversation more concrete, we consider as a running example the generating function for the probability of a Northgoing diamond in a uniform random tiling of the Aztec Diamond. This example is taken from [BP11, Section 4]. We have

where $a_{rst}$ is the probability that the domino covering the square $(r,s)$ in the order $t$ Aztec Diamond is oriented in a Northgoing direction. Figure 9 illustrates the Aztec Diamond shape of order 4 and the macroscopic features of a random tiling by dominoes of a larger Aztec Diamond (order 47).

The zero set of this homogeneous polynomial is shown in Figure 10.

The Northgoing placement probabilities $\{a_{rst}\}$ for the Aztec Diamond are asymptotically given by

when $(r,s,t)$ is in the cone $\{(r,s,t):t^{2}>2r^{2}+2s^{2}\}$ and $r+s+t$ is odd.

The way the generating function is indexed, $a_{rst}=0$ when $r+s+t$ is even. Asymptotics in the corners of the diamond outside the inscribed circle are given by $a_{rst}\to 1$ in one corner and $a_{rst}\to 0$ in the other three, where convergence occurs at an exponential rate as $t\to\infty$.

We now turn to the notion of stability. As we will see in Sections 4.3 and 5, the most useful properties of stability are closure properties: stability is preserved by a wealth of operations that are natural from an algebraic or probabilistic point of view. Stability is defined for general multivariate complex polynomials. Some of these properties or their proofs simplify when restricted to certain subclasses, such as polynomials whose coefficients are real or positive, or multi-affine polynomials, whose degrees in each variable never exceed 1. Even in these cases, however, some properties are proved only by going through the more general setting of complex coefficients.

Stability theory in one variable

As usual, the univariate theory is older and simpler. As with hyperbolicity, the origins of stability theory are in differential equations and control theory. After discussing this, we turn to combinatorial uses of the univariate theory. Stable generating polynomials produce coefficient sequences satisfying Newton’s inequalities, implying, among other things, log-concavity. We end the section on univariate stability with a discussion of stability preserving operations and the so-called Laguerre–Pólya class.

In this section we will begin by thinking more generally of polynomials that avoid roots in some region $\Omega$. We will call these $\Omega$-stable. Throughout the remainder of this paper we will let

denote the open upper half-plane. I will always use the term “stable” to mean ${\cal H}$-stable, as in Definition 1.2, and will use “Hurwitz stable” or “$\Omega$-stable” for other notions of stability. Recalling G.-C. Rota’s philosophical observation, one might keep in mind that the Riemann Hypothesis is equivalent to $\Omega$-stability where $\Omega=\{z:\Re\{z\}\neq 1/2\}$. This may seem like a strained connection, but in fact some of the literature we review in Section 7 is explicitly motivated by the desire to understand the zeta function.

Statistical physicists have a different motive for understanding regions free of zeros. To explain this, we examine some graph theoretic models, paraphrasing the exposition in [Sok01]. Let $G=(V,E)$ be a finite graph and let $q$ be a positive integer. Define a polynomial in variables $\{x_{e}:e\in E\}$

where $\sigma$ ranges over $q$-colorings of the vertices, that is, all maps from $V$ to $\{1,\ldots,q\}$. This is elementarily seen to be equivalent to the alternative definition

where $k(E^{\prime})$ denotes the number of connected components in the subgraph $(V,E^{\prime})$. The last formulation makes it obvious that $Z$ is a polynomial in $q$ as well as in $\{x_{e}\}$. When $x_{e}=-1$ for all $e$ this specializes to the chromatic polynomial $\chi(q)$; more generally, taking $x_{e}=x$ for all $e$ gives the bivariate Tutte polynomial.

The polynomial $Z$ is also the partition function for the $q$-state Potts model. Statistical physicists are interested in phase transitions where the behavior of the system depends non-analytically on its parameters. Being a polynomial, $Z$ is of course analytic in all its parameters. Typically though, one is interested in infinite-volume limits such as the free energy

One such theorem was proved by D. Wagner in 2000. The reliability polynomial $R_{G}$ of the graph $G=(V,E)$ is the probability that the graph is connected when each edge is kept or deleted independently with probability $x$, which is a polynomial in the parameter $x$. Brown and Colbourn conjectured [BC92] that all zeros of $R_{G}(x)$ are in the closed disk $\{z:|z-1|\leq 1\}$. In other words, $R_{G}$ is ${\cal D}^{c}$-stable where ${\cal D}:=\{z:|z-1|\leq 1\}$. This was proved for the class of series-parallel graphs in [Wag00, Theorem 0.2]. A simpler proof was found by Sokal [Sok01, Section 4.1, Remark 3], who actually proved the stronger multivariate stability result. On the other hand, Royle and Sokal [RS01] showed that the original univariate conjecture is false for general graphs; they also showed that multivariate ${\cal D}^{c}$-stability of $R_{G}$ holds if and only if $G$ is series-parallel. Sokal [Sok11] has recently conjectured that $R_{G}$ is (univariate) ${\cal D}^{c}$-stable for the complete graphs, $K_{n}$.

The association of zero-free regions with the term “stability” originated in ODE’s and control theory. Its use is attributed to Hurwitz. In fact, $\Omega$-stability with $\Omega=\{z:\Re\{z\}\geq 0\}$ is sometimes called “Hurwitz stability”. In ODE’s, it is easy to see the physical significance of Hurwitz stability. Let $M$ be a matrix and consider the linear system ${\bf y}^{\prime}=M{\bf y}$. Hurwitz stability is equivalent to all eigenvalues of $M$ having negative real parts, which is equivalent to all homogeneous solutions decaying, and hence good control over the system ${\bf y}^{\prime}-M{\bf y}={\bf v}(t)$. One may also consider discrete-time analogues, such as the system ${\bf y}^{(n+1)}-Q{\bf y}^{(n)}={\bf v}^{(n)}$ where $Q$ would correspond to the exponential of $M$ in the previous system. Now decay of homogeneous solutions is equivalent to $\Omega$-stability when $\Omega$ is the complement of the open unit disk; polynomials whose zeros are all in the open unit disk are said to be Schur-stable.

For a less trivial example we turn to control theory. Following [Hen91, Section 10.3], we consider systems which turn an input signal $f(t)$ into an output $u(t)$. Many systems, and in particular those built from networks of impedances, are not only linear but also time homogeneous, that is, the map $f\mapsto u$ commutes with time translation. In terms of Laplace transforms, this means that the system acts multiplicatively, meaning that if ${\cal L}$ denotes the Laplace transform, then such systems obey the law

To check whether the system with transfer function $g$ is stable, it suffices to test it on inputs of the form $f(t)=e^{i\omega t}$, the Laplace transform of which is $({\cal L}f)(s)=1/(s-i\omega)$. Let the poles of the rational function $g$ be $a_{1},\ldots,a_{r}$. The ${\cal L}u=g\cdot{\cal L}f$ has poles $a_{1},\ldots,a_{r},i\omega$. We may write ${\cal L}u$ in a partial fraction expansion resulting in $\sum_{j=0}^{r}p_{j}/(s-a_{j})$ for some polynomials $\{p_{j}\}$; here we have set $a_{0}:=i\omega$. Inverting the Laplace transform gives a sum $\sum_{j=1}^{r}P_{j}(t)e^{a_{j}t}$ for some collection $\{P_{j}\}$ of polynomials. This is bounded if and only if each $a_{j}$ is either in the open left half-plane or is imaginary and a simple zero. But when $g$ has an imaginary zero $a_{j}$, then setting $a_{0}=a_{j}$ (that is, taking the input to be $e^{ia_{j}t}$) produces a doubled root and an unbounded output. Hence, bounded inputs produce bounded outputs if and only if all poles of $g$ lie strictly in the left half-plane.

We conclude that stable behavior of the system corresponds to Hurwitz stability of the denominator of the transfer function $g$. For example, in the L-C-R circuit above, the denominator of $g$ is a quadratic with positive coefficients. The real parts of the roots are always negative, whence such a system always behaves stably.

Differential equations of order $d$ may be transformed into first order systems in $d$ variables by the well known trick of representing the first $d-1$ derivatives as new variables. It is not surprising, therefore, that Hurwitz stability also arises in the stability analysis of order-$d$ linear differential equation with constant coefficients. Given $d$ initial conditions and an inhomogeneous term, we may write such an equation as

with initial conditions $f^{(j)}(0)=b_{j}$ for $0\leq j\leq d-1$. Assuming $H$ to grow at most exponentially, a Laplace transform exists near the origin. We may take the Laplace transfrom of both sides of (4.2). Using linearity and the rule ${\cal L}f^{\prime}(s)=s{\cal L}f(s)-f(0^{+})$ and denoting $g:={\cal L}f$ gives inductively

Plugging this and the boundary conditions into (4.2) yields the following equation for $g$:

Letting $p(s):=s^{d}+a_{d-1}s^{d-1}+\cdots+a_{0}$ denote the characteristic polynomial of the equation (4.2), and $p_{k}(s)$ denote the shifted polynomial $s^{k}+a_{d-1}s^{k-1}+\cdots+a_{d-k}$, we may rewrite the equation for $g$ as

Again, poles of $g$ with positive real part produce unbounded output, as do purely imaginary poles $i\omega$ when the driving term is taken to be $e^{i\omega t}$, whose Laplace transform ${\cal L}H$ has a pole at $i\omega$. Thus, again, Hurwitz stability is equivalent to bounded output on bounded input.

2 Real roots and Newton’s inequalities

I will now return, permanently, to upper half-plane stability, which will be called, simply, “stability”. In one variable, when the coefficients of $f$ are real, the zeros come in conjugate pairs. Stability, therefore, is equivalent to having only real zeros. When the coefficients are nonnegative, a strictly positive zero is impossible, whence stability is further equivalent to having all zeros on the negative half line.

Combinatorialists have long sought to exploit the properties of stable generating functions. The universal problem in combinatorial enumeration is to count a family of structures indexed by one or more positive integer parameters. In the case of one parameter, say $n$, the sequence $\{a_{n}\}$ of counts and the corresponding generating function $f(z):=\sum_{n}a_{n}z^{n}$ are of fundamental interest. In the setting of probability generating functions, the coefficients $a_{n}$ are nonnegative and sum to one. In this case, if $f$ has only real roots, then the distribution which gives probability $a_{n}$ to the value $n$ is representable as the sum of independent random variables each taking the value 0 or 1 (Bernoulli random variables). There may or may not be a natural interpretation for these Bernoulli variables; see [HKPV09, Example 23] for an example in which there can be no natural interpretation.

Often it is intuitively plausible that the sequence $\{a_{n}\}$ is unimodal, meaning that for some $k$, we have $a_{0}\leq\cdots\leq a_{k}\geq a_{k+1}\geq a_{k+2}\geq\cdots$. The enumeration literature is littered with examples in which unimodality is conjectured (see for example the survey [Sta89] and the follow-up to this [Bre94]), but a proof is often elusive for the reason that there is no obvious theoretical framework within which to prove unimodality. There are, however some stronger properties for which natural avenues of proof exist.

A finite or infinite sequence $\{a_{k}\}$ of nonnegative numbers is said to have no internal zeros if the indices of the nonzero terms form an interval $[r,s]$. The sequence is said to be log-concave if it has no internal zeros and if

for $k\in[r+1,s-1]$. The sequence $\{a_{r},\ldots,a_{r+k}\}$ with no internal zeros is said to be ultra log-concave if

It is immediate that ultra log-concavity implies log-concavity which implies unimodality. While ultra log-concavity appears to be the least natural of these properties, it was shown three centuries ago by Newton to follow from stability of the generating function.

Suppose $f(z):=\sum_{k=0}^{n}a_{k}z^{k}$ is a real stable polynomial. Then for $1\leq k\leq n-1$,

If furthermore the coefficients $a_{k}$ are all nonnegative then the roots of $f$ are all nonpositive and the sequence is ultra log-concave.

Proof: By Rolle’s Theorem, if a univarite polynomial $f$ has only real zeros then so does its derivative. This observation will be useful many times below. We use it now to deduce that

has only real zeros. Reversing a sequence of coefficients via $R(z):=z^{n-k+1}Q(1/z)$ also preserves the property of having all real roots. By Rolle’s Theorem again, $S(z):=(d/dz)^{n-k+1}R(z)$ has all real roots. But $S(z)$ is the trinomial

and the theorem follows from the discriminant test for quadratics. $\hfill\Box$

A curious result in a similar vein was proved by Gurvits [Gur08, Lemma 3.2]; the proof, which is a few lines of calculus, is omitted.

Let $f$ be a probability generating polynomial of degree $d$ and let $C:=\inf f(t)/t$. If $f$ is stable then

Equality holds if and only if $f=(1-q+qt)^{d}$ generates a binomial distribution. The value $[(d-1)/d]^{d-1}$ increases to $e^{-1}$ as $d\to\infty$; for infinite series, the bound $a_{1}\geq e^{-1}C$ holds with equality if and only if $f(t)=e^{\lambda(t-1)}$ is the generating function for a Poisson distribution. $\hfill\Box$

There are a number of techniques that can be used to establish stability (also known, in the univariate case, as the real root property). In some cases one has a sequence $\{f_{n}\}$ where $f_{n}$ has degree $n$ and the roots of $f_{n-1}$ interlace the roots of $f_{n}$, meaning that each interval between roots of $f_{n}$ contains a root of $f_{n-1}$. If this is true, then often it is possible to prove it by induction. The following example from [Sta89] illustrates this.

The Hermite polynomials are a sequence of polynomials defined by

The are orthogonal with respect to the Gaussian measure $e^{-x^{2}}\,dx$. They satisfy the recursion

Assume for induction that $H_{n-1}(z)$ has $n-1$ real zeros. It is clear from this that $H_{n}$ has $n-2$ zeros interlacing the zeros of $H_{n-1}$. To see that $H_{n}$ also has a zero less than all the zeros of $H_{n-1}$, observe that $e^{-z^{2}}H_{n-1}$ tends to zero as $z\to-\infty$, therefore $e^{-z^{2}}H_{n-1}$ has an extreme value to the left of its leftmost zero, which is a zero of $H_{n}$. Similarly, $H_{n}$ has a zero greater than the greatest zero of $H_{n-1}$, and the induction is established.

There is a more methodical way that often works to prove interlacing by induction. If $f$ and $g$ are real polynomials of respective degrees $n$ and $n-1$ having all real roots and the zeros of $g$ interlace the zeros of $f$, it may be seen elementarily that $f+\lambda g$ has $n$ real zeros for any real $\lambda$. A simple application of this idea is to the sequence $\{g_{n}\}$ defined by the three-term recurrence

which include the Chebyshev polynomials and Laguerre polynomials ($a$ and $b$ depending on $n$ in the latter case). The same idea is the basis for a theorem independently proved by Heilmann and Lieb [HL72], by Gruber and Kunz [GK71] and, in part, by Nijenhuis [Nij76]. A matching on a finite weighted graph or multi-graph is a subset $M$ of the edge set such that any two edges in $M$ are disjoint (share no vertex). Fix a graph $G=(V,E)$ and let $\{W(e):e\in E\}$ be a set of nonnegative weights. Let $a_{j}$ denote the number of matchings with $j$ edges, counted by weight, where the weight of a matching is the product of the weights of the edges in the matching; by convention we take $a_{0}:-1$. In the simplest case, $W(e)\equiv 1$ and $a_{j}$ simply counts matchings of size $j$, size being the number of edges.

If we are allowed to set $W(e)=0$ for some edges, then the complete graph is universal. We therefore assume that $G=K_{n}$ for some $n$.

The number of weighted matchings of $K_{n}$ enumerated by size is ultra log-concave.

Proof: We show stability of a certain generating function, the most convenient being

This is monic, of degree $n$, and is odd or even depending on $n$. If we show $Q_{n}$ is stable and has $n$ distinct roots, then letting $Q_{n}(z)=R_{n}(z^{2})$ in the even case and $Q_{n}(z)=zR_{n}(z^{2})$ in the odd case, it follows that $R_{n}(-z)$ has $\lfloor n/2\rfloor$ negative real roots, hence is stable; it is also the generating function for matchings by size, hence the proof will be complete.

Taking limits at the end, we may assume without loss of generality that the weights $W(e)$ are all strictly positive. To see that $Q_{n}$ is stable, let $Q_{n}^{S}$ denote the generating function defined by (4.5) on the graph $K_{n}\setminus S$. We use the recursion

which is obvious from the definition. The induction hypothesis is that $Q_{n}^{u}$ is stable with distinct roots, which are interlaced by the roots of $Q_{n}^{u,v}$ for any $v\neq u$.

To verify the induction, we consider the sign of $Q_{n}$ at the $n-1$ zeros of $Q_{n}^{u}$ in decreasing order. By the interlacing property, the sign of each $Q_{n}^{u,v}$ alternates, starting out positive because $Q_{n}^{u,v}(+\infty)=+\infty$. Therefore, $zQ_{n}^{u}-\sum_{v}W(u,v)Q_{n}^{u,v}$ alternates, starting out negative. This implies the existence of $n-2$ roots of $Q_{n}$ interlaced by the roots of $Q_{n}^{u}$. But also there is one root of $Q_{n}$ to the right of every root of $Q_{n}^{u}$ because $Q_{n}$ is negative at the rightmost root of $Q_{n}^{u}$ and positive at $+\infty$. Similarly there is one root of $Q_{n}$ to the left of every root of $Q_{n}^{u}$. This completes the inductive proof. $\hfill\Box$

A second method by which one can establish univariate stability is via closure properties of the class of univariate stable polynomials. This topic will be expanded in the next section, but for now we mention a result from [Bre89], whose proof we will omit. Let $(x)_{i}$ denote the falling product $x(x-1)\cdots(x-i+1)$ and let $(x)^{i}$ denote the rising product $x(x+1)\cdots(x+i-1)$.

Let $f(x):=\sum_{k=0}^{n}a_{k}x^{k}$ be real stable with nonnegative coefficients. Then the polynomials $\sum_{k=0}^{n}a_{k}(x)_{k}$ and $\sum_{k=0}^{n}a_{k}(x)^{k}$ are real stable as well. $\hfill\Box$

In the following example, a function from the set $\{1,\ldots,n\}$ to itself is represented as a directed graph with an edge from $j$ to $f(j)$ for each $j$.

Let $b(n,k)$ be the number of functions from the set $\{1,\ldots,n\}$ to itself whose directed graph has precisely $k$ components. It is elementary, cf. [GJ83, Example 3.3.28], that

where $c(i,k)$ is a signless Stirling number of the first kind. Multiplying by $x^{k}$ and summing over $k$ gives

The corresponding sum replacing $(x)^{i}$ by $x^{i}$ has the short closed form

Evidently this has only real zeros, so applying the conclusion of Theorem 4.6, we see that $f_{n}$ is stable as well.

A third method is an equivalent characterization for ultra log-concave that is due to Edrei [Edr53]. This relies on the notion of total positivity, a theme developed at length by Karlin [Kar68] and for which a number of combinatorial applications are given in [Bre95].

$(i)$ An infinite matrix is said to be totally positive (TP) if all of its minors are nonnegative.

$(ii)$ A sequence $\{a_{n}\}$ is said to be a Pólya frequency sequence (PF-sequence) if the matrix $A_{nk}:=a_{n-k}$ is totally positive. Here we take $a_{i}:=0$ if $i<0$ or the sequence $\{a_{n}\}$ is finite and has length less than $i$.

A proof of the following equivalence may be found in in [Kar68, Theorem 5.3].

The nonnegative sequence $(a_{0},\ldots,a_{d})$ is a PF-sequence if and only if the generating polynomial $\sum_{k=0}^{d}a_{k}z^{k}$ is stable. $\hfill\Box$

Brenti [Bre94, Section 3] points out that only the $2\times 2$ minors are required for log-concavity, hence unimodality. Nevertheless, nonnegativity of all minors has a combinatorial interpretation which is given in [Bre95, Theorem 3.5]. This interpretation is somewhat abstract, but in special cases the interpretation can be more concrete.

A permutation of $\{1,\ldots,n\}$ is said to be an $r$-derangement if all its cycles have length at least $r$. Thus a 1-derangement is any permutation, a 2-derangement is a classical derangement, and so forth. Let $b(n,r)$ count the number of $r$-derangements of $\{1,\ldots,n\}$. Brenti [Bre95, Corollary 5.9] shows that $f_{n}:=\sum_{r=1}^{n}b(n,r)z^{r}$ is stable. To do so, he shows that a related sequence $\{c_{r}(n)\}$ is a PF-sequence, hence stable, then applies Theorem 4.6 to recover the result with $b(n,r)$ in place of $c_{r}(n)$.

We end this section with one more example of a stable generating polynomial, this one taken from [Sta89]. Recall from Example 2.4 that if $A$ is a real symmetric matrix and $B$ is real positive semi-definite then $f(z):={\rm Det\,}(A+zB)$ is a real stable polynomial.

Let $G$ be a finite graph with possibly multiple edges and let

where the sum is over all spanning forests $F$ of $G$ such that $F$ has precisely $k$ components, where $\gamma(F)$ is the product of the cardinalities (numer of vertices) of the $k$ components. The factor of $\gamma$ changes the eumeration from forests to rooted forests. Following [Sta89, Proposition 4], let us see that the polynomial $f_{G}:=\sum_{k}a_{k}(G)z^{k}$ is stable. Let $A$ be the matrix whose rows and columns are indexed by the vertices of $G$ with entry $A_{ij}:=\deg(u)$ if $u=v$ and otherwise equal to $-N(i,j)$ where $N(i,j)$ is the number of edges between $i$ and $j$. It is known that $f_{G}={\rm Det\,}(A+zI)$. It follows that $f_{G}$ is stable. Therefore, the number of rooted forests enumerated by components is ultra log-concave, hence unimodal. Stanley attributes the identity $f_{G}={\rm Det\,}(A+zI)$ to Kelmans.

3 The Laguerre–Pólya class

Suppose we transform a polynomial $f(z)=\sum_{k=1}^{n}a_{k}z^{k}$ by multiplying each coefficient $a_{k}$ by a specified constant $\lambda_{k}$. We may ask which sequences ${\boldsymbol{\lambda}}:=\{\lambda_{k}\}$ are multiplier sequences, meaning that the resulting operator $T_{\boldsymbol{\lambda}}$ preserves the class of real stable polynomials. A classical theorem due to Pólya and Schur [PS14] gives a complete and beautiful characterization of multiplier sequences.

Let ${\boldsymbol{\lambda}}=\{\lambda_{n}:n\geq 0\}$ be a sequence of real numbers and let $T_{\boldsymbol{\lambda}}$ denote the linear operator defined by

${\boldsymbol{\lambda}}$ is a multiplier sequence;

$\Phi$ is an entire function and is the limit, uniformly on compact sets, of the polynomials with all zeros real and of the same sign;

$\Phi$ is entire and either $\Phi(z)$ or $\Phi(-z)$ has a representation

where $n$ is a nonnegative integer, $C$ is real, and $\alpha_{k}$ are real, nonnegative and summable.

For all nonnegative integers $n$, the polynomial $T_{\boldsymbol{\lambda}}[(1+z)^{n}]$ is real stable with all roots of the same sign.

We will not prove the general Pólya-Schur theorem here, proving only some special cases later as we need them. Some examples and remarks will clarify its meaning and possible uses. Condition $(iv)$ may be thought of as saying that the polynomials $(1+z)^{n}$ are universal test cases for stability preserving: a multiplier sequences preserving stability of these will preserve stability of all real stable polynomials.

If $b$ is a nonnegative integer, setting $\lambda_{k}:=b^{k}$ produces the operator $T_{\boldsymbol{\lambda}}f(z)=f(bz)$. Clearly this preserves stability. The representation in $(iii)$ is obvious because $\Phi(z)=e^{bz}$.

If $n\geq 1$ is an integer then the sequence $\lambda_{k}:=(n)_{k}:=n!/(n-k)!$, defined to vanish when $k>n$, produces the exponential generating function $\Phi(z)=(1+z)^{n}$. By criterion $(iii)$ this is a multiplier sequence. Dividing by the constant $n!$ we see that $\lambda_{k}=1/(n-k)!$ for $k\leq n$ and zero for $k>n$ defines a multiplier sequence. For real polynomials of degree $n$, stability of $f$ is equivalent to stability of the inversion $z^{n}f(1/z)$, hence $\lambda_{k}=1/k!$ defines a multiplier sequence on polynomials of degree $n$. This is true for every $n$, whence $\{1/k!\}_{k=0}^{\infty}$ is a multiplier sequence. This result is due to Laguerre.

Applying the previous example to a polynomial $g(z)=\sum_{k=0}^{n}a_{k}z^{k}$ with negative real roots shows that $\sum_{k=0}^{n}(a_{k}/k!)z^{k}$ also has negative real roots. Setting $\lambda_{k}:=a_{k}$ for $k\leq n$ and zero for $k>n$ we see that its exponential generating function $\Phi(z)=\sum_{k=0}^{n}a_{k}z_{k}/k!$ is of the form in $(iii)$ with $\alpha_{0}=0$. We conclude that $\{a_{k}\}$ is a multiplier sequence. In other words, if we multiply term by term the coefficient sequences of two real rooted polynomials, at least one of which has nonnegative coefficients, we get another real rooted coefficient sequence. Thus the real root property for polynomials with nonnegative coefficients is closed under Hadamard products.

A related notion to that of a multiplier sequence is the notion of a complex zero decreasing sequence (CZDS). Let $Z_{c}(f)$ denote the number of non-real zeros of $f$. Say that a finite or infinite sequence $\{a_{k}\}$ is a CZDS if for any real polynomial $f(z)=\sum_{k=0}^{n}b_{k}z^{k}$,

In particular, in order for $\{a_{k}\}$ to be a CZDS, a value of zero on the right of (4.7) (no non-real zeros) implies no non-real zeros on the left, so any CZDS is a multiplier sequence. The converse, however, is not true.

To see that there is any nontrivial CZDS, we observe that the operator $z(d/dz)$ is represented by the sequence $a_{k}:=k$ and can never increase the number of non-real zeros. Although not every multiplier sequences is a CZDS, each multiplier sequence leads to a CZDS via the following result going back to Laguerre.

Let $\Phi\in{\cal L}-{\cal P}$ have zeros only in $(-\infty,0]$. Then the sequence $\{\Phi(k):k\geq 0\}$ is a CZDS. $\hfill\Box$

Related to the notions of multiplier sequences and CZDS is the notion of a multiplier sequence for the property of being nonnegative on real inputs. Say that $\{c_{k}\}$ is a $\Lambda$-sequence if multiplication of coefficients term by term preserves the property of being everywhere nonnegative:

Note that negative values are allowed for the numbers $c_{k}$. The following classical relationship is proved in [Wid41].

If $\{a_{k}\}$ is a CZDS then $\{a_{k}^{-1}\}$ is a $\Lambda$-sequence. $\hfill\Box$

Multivariate stability

Let ${\cal H}$ denote the open upper half-plane; thus stability is equivalent to having no zeros in the region ${\cal H}^{d}$. We remark on some connections to other notions of stability. For homogeneous polynomials, the zero set is invariant under multiplication by $e^{i\theta}$ in each coordinate, therefore all notions of half-plane stability coincide. Any circular region (the interior or exterior of a circle) is transformed into ${\cal H}$ by a Möbius transformation, which allows the theory of $\Omega$-stable functions to be mapped to the ordinary theory of stable functions via a bi-rational change of variables whenever $\Omega$ is the product of circular regions. This mapping acts nicely with respect to some aspects such as closure properties but not as nicely with respect to coefficient sequences. Thus, for example, it may shown that Schur-stability, where $\Omega={\cal D}^{d}$ and ${\cal D}$ is the open unit disk, has an unexpected closure property: if $f$ and $g$ are multi-affine Schur-stable polynomials then the Hadamard product $f\bullet g$ is Schur-stable as well; here the Hadamard product of $\sum_{S}a(S){\bf z}^{S}$ and $\sum_{S}b(S){\bf z}^{S}$ is defined to be $\sum_{S}a(S)b(S){\bf z}^{S}$. Our principal interest is in ${\cal H}$-stable polynomials and their coefficients. We will not henceforth consider notions of stability other than upper half-plane stability.