Let’s call a function a near-endomorphism of if there is a constant such that for all . The set of near-endomorphisms of will be denoted by . We put an equivalence relation on by declaring that iff the function is bounded, and let denote the set of equivalence classes.
It’s not difficult to show that defining in terms of pointwise addition and in terms of composition of functions turns into a commutative ring. And it turns out that this ring has a more familiar name… Before reading further, can you guess what it is?
Today is the 10th anniversary of the death of Martin Gardner. His books on mathematics had a huge influence on me as a teenager, and I’m a fan of his writing on magic as well, but it was only last year that I branched out into reading some of his essays on philosophy, economics, religion, literature, etc. In this vein, I highly recommend “The Night Is Large”, a book of collected essays which showcases the astonishingly broad range of topics about which Martin had something interesting to say. It’s out of print, but it’s easy to find an inexpensive used copy if you search online.
Thinking back on my favorite Martin Gardner columns, my all-time favorite has to be the April 1975 issue of Scientific American. In that issue, Martin wrote an article about the six most sensational discoveries of 1974. The whole article was an April Fools’ Day prank: among the discoveries he reported were a counterexample to the four-color problem and an artificial-intelligence computer chess program that determined, with a high degree of probability, that P-KR4 is always a winning move for white. The article also contained the following:
First of all, I’d like to express my sympathies to everyone who is enduring hardships due to COVID-19. Stay well and be strong.
In this previous post, I discussed two important classical results giving examples of polynomials whose roots interlace:
Theorem 1: The roots of a real-rooted polynomial and its derivative interlace.
Theorem 2: (Cauchy’s interlacing theorem) The eigenvalues of a real symmetric matrix interlace with those of any principal minor.
In this post, I’d like to explain a general method, based on partial fraction expansions of rational functions, which gives a unified approach to proving Theorems 1 and 2 and deserves to be better known.
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.
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.