In this previous post, I described the basic theory of Lorentzian polynomials d’après Brändén and Huh. Now I’d like to describe some of the powerful applications of this theory, culling together results from papers by several different sets of authors. Our first application will be Mason’s Ultra-Log-Concavity Conjecture from 1972, established independently by Brändén-Huh and Anari-Liu-Oveis Gharan-Vinzant in 2018.
A special case of this result (which seems to be no easier to prove than the general case) is the following: Let be a set of vectors in some finite-dimensional vector space, and let denote the number of -element linearly independent subsets of . Then the sequence is ULC.
Here is a brief outline of the proof, following a hybrid of [BH] and [ALOV3]. Let be the collection of independent sets of , and let be the homogenous generating function of , i.e., . One shows that is Lorentzian by first using a straightforward deletion-contraction argument to reduce to the rank 2 case and then applying Cauchy-Schwartz to verify the Lorentzian property of the resulting quadratic form. Now, it is a general fact (see Theorem 2.10 of [BH] or Lemma 2.2 of [ALOV3]) that specializations of Lorentzian polynomials, where we set certain variables equal to each other, are again Lorentzian. Setting all equal to , we see that the bivariate polynomial is Lorentzian, and in particular its coefficients form an ULC sequence.
As another application of Lorentzian polynomials, we now turn to the Mihail-Vazirani conjecture, which asserts that the expansion constant of the basis exchange graph of any matroid is at least 1. Here is a concrete special case of the conjecture (which again seems to be no easier to prove than the general case). Let be a set of vectors in some finite-dimensional vector space, and let be the vector space spanned by . A basis of is a basis for contained in . Let be the graph whose vertices correspond to bases of , and whose edges correspond to bases whose symmetric difference has size 2. In this situation, the Mihail-Vazirani conjecture says that for every subset of vertices of , the number of edges connecting to its complement is at least .
Theorem ([ALOV2]): The Mihail-Vazirani conjecture is true for every matroid .
The proof of this result in [ALOV2] goes through the theory of Markov chains. Every matroid of rank on gives rise to a natural Markov chain , where is the uniform probability distribution on the bases of . The Markov chain corresponds to the random walk on the set of bases of where, given a basis , we first choose a random element of and then choose a basis uniformly at random from the set of all bases containing . It is shown in [ALOV2] that the probability distribution is Lorentzian, meaning that its homogeneous generating polynomial
is Lorentzian. This implies, according to [ALOV2], that the Markov chain mixes rapidly, i.e., the Monte Carlo Markov chain method produces rapid convergence of any initial state to the stationary distribution . This rapid mixing implies, via a well-known argument, the Mihail-Vazirani conjecture.
More precisely, it is shown in [ALOV2] that if denotes the transition matrix of the Markov chain and is the number of -element independent subsets of , then has at most eigenvalues larger than for each . In particular, has spectral gap at least . It follows from standard spectral theory arguments that for any and any basis of , the mixing time of , where denotes the distribution of the Markov chain at time starting at , is at most .
The rapid mixing of for any matroid has other interesting consequences in addition to the Mihail-Vazirani conjecture. For example, while counting the number of bases in a matroid is known to be #P-complete, the rapid mixing of implies that there is a probabilistic algorithm to approximately count the number of bases in a matroid, up to a multiplicative error factor of , in polynomial time. More precisely:
Theorem ([ALOV2]): There is a randomized algorithm which, for any rank matroid on given by an independent set oracle, and any , counts the number of bases of up to a multiplicative factor of with probability at least , with running time which is polynomial in
In [ALOV1], Anari et. al. give a different algorithm for approximately counting the number of bases of a matroid which is deterministic but has a slightly worse multiplicative error factor of rather than . This algorithm also relies on the theory of Lorentizan polynomials, but in a different way: they use the fact that is concave as a function on the positive orthant to show that there is a convex program whose solution yields a good approximation to the number of bases of . (Convex programming is a far-reaching generalization of linear programming which, like linear programming, provides efficient algorithms for solving certain types of optimization problems.) We refer to [ALOV1] for further details.
Here is one more application of Lorentzian polynomials, this time to the representation theory of the general linear group . Let be a partition of , identified with its corresponding Young diagram, and let be the collection of all semistandard Young tableaux with shape and entries in . For , let be the number of appearances of among the entries of . The vector is called the weight of . The classical Schur polynomial corresponding to is generating function where . The coefficients are called Kostka numbers; they are special cases of what is known in representation theory as Littlewood-Richardson coefficients. The normalized Schur polynomial is the corresponding exponential generating function
Theorem ([HMMS]): For every partition , the normalized Schur polynomial is Lorentzian. In particular, for any weight and any we have
This result verifies a special case of a conjecture of a conjecture of Okounkov about log-concavity of Littlewood-Richardson coefficients. In contrast to the applications of Lorentzian polynomials given in [BH], the theorem of [HMMS] makes use of non-trivial results from algebraic geometry. It would be interesting to have an “elementary” proof that normalized Schur polynomials are Lorentzian. The connection with representation theory is that the Schur module , which is an irreducible representation of with highest weight , has a canonical weight decomposition with . See [HMMS] for additional results and conjectures related to Kostka numbers and their generalizations.
- The paper [BES] by Backman, Eur, and Simpson uses the theory of Lorentzian polynomials, together with a novel presentation for the Chow ring of a matroid, to give a new proof of Rota’s log-concavity conjecture. Their proof is simpler than the original proof by Adiprasito, Huh, and Katz in several key ways; for example, it avoids the technical notions of order filters and flips, and in the process replaces the intricate double induction in [AHK] with a single induction.
- Additional applications of Lorenztian polynomials are given in [BH] and in the paper [EH] by Eur and Huh.
- For more information about Lorentzian polynomials, I highly recommend this series of three videos by June Huh delivered as part of the MIT Simons Lectures.
- One can find a number of conjectures about log-concave sequences in this survey article by Richard Stanley. Some of these have now been settled using the theory of Lorentzian polynomials; it is natural to wonder which others might also now be within reach.