I’m organizing a reading seminar this semester on Lorentzian polynomials, mainly following this paper by Brändén and Huh but also covering some of the work of Anari et. al. In this post, I’d like to give a quick introduction to this active and beautiful subject. I’ll concentrate on the basic theory for now, and in a follow-up post I’ll discuss some of the striking applications of this theory.
One major goal of the theory of Lorentzian polynomials is to provide new techniques for proving that various naturally-occurring sequences of non-negative real numbers are log-concave, meaning that for all . More generally, the authors consider homogeneous multivariate polynomials with non-negative coefficients and study certain natural extensions of log-concavity to this setting. (For some background on log-concave sequences, see this survey paper which I wrote for the Bulletin of the AMS.) So let me begin by introducing two “classical” methods for proving (an even sharper version of) log-concavity of the coefficients of certain polynomials.
Method #1 (Newton): Let be real-rooted univariate polynomial with non-negative coefficients. Then the sequence of coefficients of is ultra-log-concave (ULC), meaning that
Note that ultra-log-concavity is stronger than log-concavity (simple exercise).
Slick proof of Newton’s theorem: The idea is to reduce to the case of quadratic polynomials, where the result follows immediately from the fact that the discriminant of a real-rooted quadratic must be non-negative, using the following two operations which preserve real-rootedness:
(1) Differentiation: If is real-rooted, then by Rolle’s theorem so is . (In fact, the roots of interlace the roots of , but we won’t explicitly need this fact.)
(2) Reciprocation: If is real-rooted, then so is the reciprocal polynomial (This is clear once you realize that )
The proof is now easy: fix and differentiate times in order to get rid of all the coefficients with . Now form the reciprocal polynomial of and differentiate it times in order to get rid of all the coefficients with . What remains is the real-rooted quadratic polynomial Applying the inequality and doing some routine algebra gives the desired ultra-log-concavity. Q.E.D.
A couple of quick observations about this argument:
(1) The “routine algebra” at the end, as well as the apparent cleverness required to think of the reciprocation trick, disappears if we instead consider homogeneous polynomials of the form If we assume that (or, equivalently, ) is real-rooted, then differentiating times with respect to and times with respect to gives a cleaner-looking homogeneous quadratic polynomial whose discriminant must be non-negative, yielding immediately (with no extra algebraic manipulations) log-concavity of the sequence , which is easily seen to be equivalent to ultra-log-concavity of the sequence For this reason and others, we will always work in what follows with homogenous polynomials written in “exponential generating function” form.
(2) The argument does not actually require that be real-rooted, just that after any suitable sequence of partial differentiations we end up with a real-rooted quadratic. This observation will help motivate the definition of Lorentzian polynomials below.
Method #2 (Cauchy, Sylvester): Suppose is a symmetric quadratic form with for all and having Lorentzian signature (i.e., the symmetric matrix has one positive and negative eigenvalues). Then every minor of has Lorentzian signature as well, and in particular we have for all .
Proof: By Cauchy’s interlacing theorem, the eigenvalues of every principal minor of interlace the eigenvalues of . In particular, must have signature either or . However, the former is impossible since the trace of and are both positive. By induction, it follows that every minor of has Lorentzian signature. Applying this to the minor of corresponding to rows and , it follows that , hence the stated inequality. Q.E.D.
Note that in both the Newton and Cauchy-Sylvester methods, log-concavity is ultimately proved by reducing to the case of homogeneous polynomials of degree 2. We will describe a general class of homogenous polynomials for which one can reduce log-concavity considerations to the case of Lorentzian quadratic forms via partial differentiation. In order to do this, we must first fix some notation.
(1) Let be the set of homogenous polynomial of degree in variables , where , and .
(2) Let be the set of all having positive coefficients, and let be the set of all homogeneous quadratic forms such that the Hessian matrix has Lorentzian signature.
(3) For , let be the set of all such that for all . We call such polynomials strictly Lorentzian.
(4) Let be the closure of in the finite-dimensional vector space . We call the set of Lorentzian polynomials. Note that the coefficients of a Lorentzian polynomial must all be non-negative.
Although it’s not obvious, it turns out (and should at least seem plausible at this point) that the coefficients of a Lorentzian polynomial have the following generalized ultra-log-concavity property:
Theorem (Brändén-Huh): If is Lorentzian, then for all , where is the standard basis vector in .
In addition, being Lorentzian implies a strong log-concavity property for the values of the polynomial:
Theorem (Brändén-Huh): If is Lorentzian, then is a concave function on the positive orthant In fact, a homogeneous polynomial with non-negative coefficients is Lorentzian if and only if is a concave function on for all
In particular, if we can verify that a given homogeneous polynomial is Lorentzian, we obtain a whole suite of interesting inequalities satisfied by not only the coefficients of but also the values of . Because of the closure operation, however, it is not obvious from the definition how to check whether a polynomial is Lorentzian. We will turn to this issue next, after presenting a few examples and non-examples of Lorentzian polynomials. (Note: some of the following assertions are easy to check and others are much harder, but all are explained in the paper of Brändén-Huh.)
Example #1: (n=2) A bivariate homogenous polynomial of degree with non-negative coefficients is Lorentzian if and only if the coefficients form an ULC sequence, i.e., they satisfy Newton’s inequalities. Note that this is more general than being real-rooted: for example, is Lorentzian but not real-rooted.
Example #2 (d=2): A homogeneous quadratic form in variables with non-negative coefficients is Lorentzian if and only if the Hessian of has exactly one positive eigenvalue.
Example #3: (A warning) For , being Lorentzian is not the same thing as checking that all partial derivatives of order are Lorentzian quadratic forms. (In other words, the closure operation does not “commute” with taking partial derivatives.) For example, one can show (see below) that is not Lorentzian despite the fact that both and are.
Example #4: A homogenous polynomial with non-negative coefficients is called stable if is real-rooted for all affine-linear maps with positive gradient (i.e., with and ). It turns out that a homogeneous stable polynomial is automatically Lorentzian. It was known prior to the work of Brändén-Huh et. al. that the coefficients of a stable polynomial are log-concave, so the new work can be viewed as a far-reaching generalization of this fact.
Example #5: If are convex subsets of some Euclidean space , the function given by (where addition denotes Minkowski sum) is a Lorentzian polynomial.
Example #6: The product of two Lorentzian polynomials is again Lorentzian.
In my follow-up post, I will give a several more non-trivial examples. But to conclude the present post, I’d like to focus on the important question of how to easily determine whether a polynomial with non-negative coefficients actually belongs to or not.
It turns out that there is a purely combinatorial condition on the support of (i.e., the set of such that ) which guarantees that taking closures in does, in a suitable sense, commute with taking partial derivatives. Somewhat miraculously, the combinatorial condition turns out to be intimately related to the notion of a matroid. (The reason this is so remarkable is that the definition we’ve given for Lorentizan polynomials would seem to have nothing whatsoever to do with matroids, it involves just basic linear algebra and multivariable calculus.)
More precisely, a subset is called M-convex (or, equivalently, is the set of bases of a polymatroid) if for every and every index such that , there exists an index with such that and both belong to .
Theorem (Brändén-Huh): The support of any Lorentzian polynomial is M-convex, and conversely every M-convex set is the support of a non-empty collection of Lorentzian polynomials.
A few remarks:
(1) If , then is M-convex if and only if is the set of bases of a matroid. Thus M-convex sets are to matroids as multisets are to sets.
(2) From the theorem, we can see immediately why the polynomial from Example #3 above is not Lorentzian: its support is “missing” the monomials and needed for M-convexity.
(3) An earlier theorem of Brändén asserts that the Fano matroid is not the support of any stable polynomial. So the intimate relationship between M-convexity and Lorentzian polynomials is only a one-way implication if we replace “Lorentzian” by “stable”.
Because there is no Euclidean closure in the statement, the following theorem leads to a straightforward algorithm for determining whether or not a given polynomial is Lorentzian:
Theorem (Brändén-Huh): Let be the set of all homogeneous polynomials whose support is M-convex. Then where is the set of all with non-negative coefficients whose Hessian has exactly one positive eigenvalue (see Example #2 above).
- The notion of Lorentzian polynomial was independently discovered by Anari, Oveis Garan, and Vinzant at the same time as Brändén-Huh. Some of the applications given in these authors’ papers are similar to those of Brändén-Huh and some are quite different. I will discuss some of these applications in my next post.
- The notion of M-convexity is due to Kazuo Murota, see this survey paper for further context. M-convex subsets of are “cryptomorphically” equivalent to discrete polymatroids, which can be defined as non-decreasing submodular functions from
- Somewhat paradoxically, it is often easier (when true) to prove that a given polynomial is Lorentzian than to directly establish the strictly weaker fact that the polynomial is log-concave on the positive orthant. This type of “paradox”, where to prove a given statement it is often useful to prove something stronger, is rather ubiquitous in mathematics.