Some Mathematical Gems from John Conway

John Horton Conway died on April 11, 2020, at the age of 82, from complications related to COVID-19. See this obituary from Princeton University for an overview of Conway’s life and contributions to mathematics. Many readers of this blog will already be familiar with the Game of Life, surreal numbers, the Doomsday algorithm, monstrous moonshine, Sprouts, and the 15 theorem, to name just a few of Conway’s contributions to mathematics. In any case, much has already been written about all of these topics and I cannot do justice to them in a short blog post like this. So instead, I’ll focus on describing a handful of Conway’s somewhat lesser-known mathematical gems.

Continue reading →

COVID-19 Q&A

My friend Joshua Jay, who is one of the world’s top magicians, emails me from time to time with math questions. Sometimes they’re about card tricks, sometimes other things. Last night he sent me an excellent question about COVID-19, and I imagine that many others have wondered about this too. So I thought I’d share my response, in case it’s helpful to anyone.

JJ: Since the government is predicting between 100k – 240k deaths from COVID-19, let’s for argument’s sake split the difference and call it 170k projected deaths. They’re ALSO telling us they believe the deaths will “peak” something like April 20th. Am I wrong in assuming, then, that if we assume 170k total deaths, and the halfway point is a mere two weeks away, then they’re projecting 85k deaths before (and after) April 20th?

When I start to think about the idea of of 85k deaths between now and April 20th, and we’ve only experienced 5k so far, it means that 80k people are projected to die in the next two weeks. Surely that can’t be correct, or else it would be dominating the news cycle, right?

I’m not asking whether you think those projections are accurate… I’m just trying to wrap my head around the relationship between total projected deaths (whatever it is) and the projected peak of the curve. 

Continue reading →

Zero Knowledge Identification and One-Way Homomorphisms

Imagine logging into a secure web server which, instead of asking you to type in your password, merely asks you questions about your password until it’s convinced that you really do know it and therefore are who you say you are. Moreover, imagine that your answers to the server’s questions provide no information whatsoever which could be used by a malicious hacker, even if all communications between you and the server are being intercepted. Finally, imagine that the server in question not only does not store any information about your password, it has never at any point asked you for information about your password.

Sounds too good to be true, right?

In fact, such password schemes do exist, and they’re quite easy to implement. They are known as zero knowledge authentication systems. In this post, I’ll explain the main idea behind such protocols using the notion of a “one-way homomorphism”. Before diving into the technicalities, though, here’s a useful thought experiment which conveys the main idea.

Continue reading →

Interlacing via rational functions and spectral decomposition

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.

Continue reading →

Complementary sets of natural numbers and Galois connections

In this post, I’d like to discuss a beautiful result about complementary sets of natural numbers due to Lambek and Moser. I first learned about their theorem as a high school student (from Ross Honsberger’s delightful book “Ingenuity in Mathematics”), but it’s only more recently that I learned about the “Galois” connection.

To motivate the discussion, consider the following question. Let F = \{ 0,1,4,9,16,25,\ldots \} be the sequence of squares, and let G = \{ 2,3,5,6,7,8,10,\ldots \} be its complement in {\mathbb N} = \{ 0,1,2,3,\ldots \}. What is the n^{\rm th} term of the sequence G? In other words, can we give a formula for the n^{\rm th} non-square? One might imagine that no simple formula exists, but in fact Lambek and Moser showed that the n^{\rm th} non-square is equal to n + \{ \sqrt{n} \}, where \{ x \} denotes the closest integer to x. Similarly, if T = \{ 0,1,3,6,10,\ldots \} denotes the set of triangular numbers, the n^{\rm th} element of the complement of T is equal to n + \{ \sqrt{2n} \}.

Figure by Scott Kim
Continue reading →

Lorentzian Polynomials II: Applications

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.

Theorem: Let M be a matroid on n elements, and let I_k(M) denote the number of independent sets of size k in M. Then the sequence I_k(M) is ultra-log-concave.

A special case of this result (which seems to be no easier to prove than the general case) is the following: Let E be a set of n vectors in some finite-dimensional vector space, and let I_k denote the number of k-element linearly independent subsets of E. Then the sequence I_k is ULC.

Continue reading →

Lorentzian polynomials I: Theory

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 a_k are log-concave, meaning that a_k^2 \geq a_{k-1} a_{k+1} for all k. More generally, the authors consider homogeneous multivariate polynomials p(x_1,\ldots,x_n) 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.

Continue reading →

Infinitely many primes via generating functions

A few years ago I discovered an amusing proof of Euclid’s theorem that there are infinitely many primes which I thought I’d record here for posterity. (I subsequently learned that a similar argument appears in this paper by Paul Pollack.)

To motivate the proof, and illustrate its working in an (admittedly silly) special case, suppose that there were just two prime numbers, called p and q. Then by the fundamental theorem of arithmetic (i.e., unique factorization into primes) we would have the following identity between generating functions:

\sum_{n=2}^\infty z^n = \sum_{k=1}^\infty z^{kp} + \sum_{k=1}^\infty z^{kq} - \sum_{k=1}^\infty z^{kpq}.

Indeed, there is precisely one term z^n for each integer n \geq 2 on the left-hand side, and the same is true for the right-hand side (consider separately the cases where p \mid n but q \nmid n, q \mid n but p \nmid n, and pq \mid n). Using the formula for the sum of a geometric series, we can rewrite our formula as an identity between complex-analytic functions valid on the open unit disc {\mathbb D} = \{z \in {\mathbb C} \; : \; |z|<1 \}:

\frac{z^2}{1-z} = \frac{z^p}{1-z^p} + \frac{z^q}{1-z^q} - \frac{z^{pq}}{1-z^{pq}}.

This is impossible, however, as we see by letting z approach a primitive pq^{\rm th} root of unity, since each term stays bounded except for \frac{z^{pq}}{1-z^{pq}}, which tends to infinity.

Continue reading →

The Drunkard’s Walk and Catalan Numbers

In this post, I’d like to present an amusing and off-the-beaten-path solution to the classical “Drunkard’s Walk” problem which at the same time derives the well-known generating function for the Catalan numbers.  This solution evolved from a suggestion by my former undergraduate student Stefan Froehlich during a discussion in my Math 4802 (Mathematical Problem Solving) class at Georgia Tech in Fall 2007.

In case you’re not familiar with it, here’s the problem (in a formulation I learned from this book by Frederick Mosteller):

A drunken man standing one step from the edge of a cliff takes a sequence of random steps either away from or toward the cliff. At any step, his probability of taking a step away from the cliff is p (and therefore his probability of taking a step toward the cliff is 1-p). What is the probability that the man will eventually fall off the cliff?

Continue reading →

The Stern-Brocot tree, Hurwitz’s theorem, and the Markoff uniqueness conjecture

My goal in this post is to describe a surprising and beautiful method (the Stern-Brocot tree) for generating all positive reduced fractions. I’ll then discuss how properties of the tree yield a simple, direct proof of a famous result in Diophantine approximation due to Hurwitz.  Finally, I’ll discuss how improvements to Hurwitz’s theorem led Markoff to define another tree with some mysterious (and partly conjectural) similarities to the Stern-Brocot tree.

Continue reading →

The Balanced Centrifuge Problem

Next week I start a new position as Associate Dean for Faculty Development in the Georgia Tech College of Sciences.  One of the things I’m looking forward to is getting to know more faculty outside the School of Mathematics and learning about their research. My knowledge of biology, in particular, is rather woeful, but I love reading about the latest developments in Quanta Magazine and elsewhere.

The other day I took my 14-year-old daughter, who is hoping to study genetics, to visit the lab of a Georgia Tech colleague in the School of Biology.  During the visit we discussed how expensive it can be not just to purchase but also to maintain certain kinds of lab equipment, for example centrifuges.  This reminded me about a blog post I’ve been meaning to write for a long time now…

Back in 2011-12, I spent a year as a faculty member at UC Berkeley and I became friends with some biologists there.  One weekend afternoon I was chatting with a cancer researcher named Iswar Hariharan at a barbecue, and when he heard that I was a number theorist he told me about a problem he had been thinking about on and off for more than 15 years.   The problem concerns balancing centrifuges. Continue reading →

Circles, the Basel Problem, and the Apparent Brightness of Stars

On Pi Day 2016, I wrote in this post about the remarkable fact, discovered by Euler, that the probability that two randomly chosen integers have no prime factors in common is \frac{6}{\pi^2}.  The proof makes use of the  famous identity \sum_{n=1}^\infty \frac{1}{n^2} = \frac{\pi^2}{6}, often referred to as the “Basel problem”, which is also due to Euler.  In the 2016 post I presented Euler’s original solution to the Basel problem using the Taylor series expansion for \frac{\sin(x)}{x}.

In honor of Pi Day 2018, I’d like to explain a simple and intuitive solution to the Basel problem due to Johan Wästlund.  (Wästlund’s paper is here; see also this YouTube video, which is where I first heard about this approach – thanks to Francis Su for sharing it on Facebook!)  Wästlund’s approach is motivated by physical considerations (the inverse-square law which governs the apparent brightness of a light source) and uses only basic Euclidean geometry and trigonometry.

Continue reading →

GAGS 2018

The 2018 Georgia Algebraic Geometry Symposium is a wrap!  This was the first time that the annual conference was held at Georgia Tech, and I thought it went very well.  Each of the eight talks seems to have been well-received, and some spectacular new results were announced.  Here’s a quick summary of (what I remember about) the talks: Continue reading →

The Circuit-Cocircuit Reversal System and Torsor Structures on Spanning Trees

The Jacobian of a finite graph G is a finite abelian group whose cardinality is equal to the number of spanning trees of G.  In this earlier post, I discussed a family of combinatorial bijections between elements of {\rm Jac}(G) and the set {\mathcal T}(G) of spanning trees of G.  I also discussed the fact that for plane graphs, these Bernardi bijections come from a natural simply transitive action of {\rm Jac}(G) on {\mathcal T}(G) (or, more precisely, a natural isomorphism class of such actions).

In the present post, I’d like to discuss a different family of simply transitive actions of {\rm Jac}(G) on {\mathcal T}(G) discovered by myself, Spencer Backman (a former student of mine), and Chi Ho Yuen (a current student of mine).  One virtue of our construction is that it generalizes in a natural way from graphs to regular matroids.  (We will mostly stick to the graphical case in this post, but will insert some comments about extensions to regular and/or oriented matroids.  A regular matroid can be thought of, rather imprecisely, as the smallest natural class of objects which contain graphs and admit a duality theory generalizing duality for planar graphs. Regular matroids are special cases of the more general concept of oriented matroids.)

One of the main new ideas in [BBY] (as we will henceforth refer to our paper) is to use the torsor {\rm Pic}^{g-1}(G) as an intermediate object rather than {\rm Pic}^{g}(G).  The latter is canonically isomorphic (as a {\rm Jac}(G)-torsor) to the set of break divisors on G; the former is isomorphic to the circuit-cocircuit reversal system, which we now introduce.

Continue reading →

The Geometry of Break Divisors

I’d like to continue this discussion of break divisors on graphs & tropical curves by describing an interesting connection to algebraic geometry.  In this post, I’ll explain a beautiful connection to the theory of compactified Jacobians discovered by Tif Shen, a recent Ph.D. student of Sam Payne at Yale. Continue reading →