A Fields Medal for June Huh

Congratulations to all of the winners of the 2022 Fields Medal! The only one I know personally, and whose work I have studied in detail, is June Huh.

I’m happy both for June himself and for the field of combinatorics more broadly, which at one point was not taken seriously enough by the mathematics community to merit Fields Medal level consideration. I’m particularly interested in connections between combinatorics and algebraic geometry, and that is certainly something that June’s work has taken to new heights.

I thought it might be useful for me to post links to my previous blog posts about June’s work here, along with some related links.

Continue reading

Counting with martingales

In this post I will provide a gentle introduction to the theory of martingales (also called “fair games”) by way of a beautiful proof, due to Johan Wästlund, that there are precisely n^{n-2} labeled trees on n vertices.

Apertif: a true story

In my early twenties, I appeared on the TV show Jeopardy! That’s not what this story is about, but it’s the reason I found myself in the Resorts Casino in Atlantic City, where the Jeopardy! tryouts were held (Merv Griffin owned both the TV show and the casino). At the time, I had a deep ambivalence (which I still feel) toward gambling: I enjoyed the thrill of betting, but also believed the world would be better off without casinos preying on the poor and vulnerable in our society. I didn’t want to give any money to the casino, but I did want to play a little blackjack, and I wanted to be able to tell my friends that I had won money in Atlantic City. So I hatched what seemed like a failsafe strategy: I would bet $1 at the blackjack table, and if I won I’d collect $1 and leave a winner. If I lost the dollar I had bet in the first round, I’d double my bet to $2 and if I won I’d stop playing and once again leave with a net profit of $1. If I lost, I’d double my bet once again and continue playing. Since I knew the game of blackjack reasonably well, my odds of winning any given hand were pretty close to 50% and my strategy seemed guaranteed to eventually result in walking home with a net profit of $1, which is all I wanted to accomplish. I figured that most people didn’t have the self-discipline to stick with such a strategy, but I was determined.

Here’s what happened: I lost the first hand and doubled my bet to $2. Then I lost again and doubled my bet to $4. Then I lost again. And again. And again. In fact, 7 times in a row, I lost. In my pursuit of a $1 payoff, I had just lost $127. And the problem was, I didn’t have $128 in my wallet to double my bet once again, and my ATM card had a daily limit which I had already just about reached. And frankly, I was unnerved by the extreme unlikeliness of what had just happened. So I tucked my tail between my legs and sheepishly left the casino with a big loss and nothing to show for it except this story. You’re welcome, Merv.

Martingales

Unbeknownst to me, the doubling strategy I employed (which I thought at the time was my own clever invention) has a long history. It has been known for hundreds of years as the “martingale” strategy; it is mentioned, for example, in Giacomo Casanova‘s memoirs, published in 1754 (“I went [to the casino of Venice], taking all the gold I could get, and by means of what in gambling is called the martingale I won three or four times a day during the rest of the carnival.”) Clearly not everyone was as lucky as Casanova, however (in more ways than one). In his 1849 “Mille et un fantômes”, Alexandre Dumas writes, “An old man, who had spent his life looking for a winning formula (martingale), spent the last days of his life putting it into practice, and his last pennies to see it fail. The martingale is as elusive as the soul.” And in his 1853 book “Newcomes: Memoirs of a Most Respectable Family”, William Makepeace Thackeray writes, “You have not played as yet? Do not do so; above all avoid a martingale if you do.” (For the still somewhat murky origins of the word ‘martingale’, see this paper by Roger Mansuy.)

Continue reading

The Eudoxus reals

Let’s call a function f : {\mathbb Z} \to {\mathbb Z} a near-endomorphism of \mathbb Z if there is a constant C>0 such that |f(a+b)-f(a)-f(b)| \leq C for all a,b \in \mathbb Z. The set of near-endomorphisms of \mathbb Z will be denoted by N. We put an equivalence relation \sim on N by declaring that f \sim g iff the function f-g is bounded, and let {\mathbb E} denote the set of equivalence classes.

It’s not difficult to show that defining f+g in terms of pointwise addition and f \cdot g in terms of composition of functions turns {\mathbb E} 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?

Continue reading

Calendar Calculations with Cards

As readers of this previous post will know, I’m rather fond of mental calendar calculations. My friend Al Stanger, with whom I share a passion for recreational mathematics, came up with a remarkable procedure for finding the day of the week corresponding to any date in history using just a handful of playing cards. What’s particularly noteworthy about Al’s algorithm is that it involves no calculations whatsoever, and the information which needs to be looked up can be cleanly displayed on one of the cards.

When you work through Al’s procedure, it will feel like you’re performing a card trick on yourself – you will be amazed, surprised, and will likely have no idea how it works. I’ve never seen anything quite like this before, and I’m grateful to Al for allowing me to share his discovery with the public for the first time here on this blog.

Continue reading

Firing games and greedoid languages

In an earlier post, I described the dollar game played on a finite graph G, and mentioned (for the “borrowing binge variant”) that the total number of borrowing moves required to win the game is independent of which borrowing moves you do in which order. A similar phenomenon occurs for the pentagon game described in this post.

In this post, I’ll first present a simple general theorem due to Mikkel Thorup which implies both of these facts (and also applies to many other ‘chip firing games’ in the literature). Then, following Anders Björner, Laszlo Lovasz, and Peter Shor, I’ll explain how to place such results into the context of greedoid languages, which have interesting connections to matroids, Coxeter groups, and other much-studied mathematical objects.

Continue reading

Quadratic Reciprocity via Lucas Polynomials

In this post, I’d like to explain a proof of the Law of Quadratic Reciprocity based on properties of Lucas polynomials. (There are over 300 known proofs of the Law of Quadratic Reciprocity in the literature, but to the best of my knowledge this one is new!)

In order to keep this post as self-contained as possible, at the end I will provide proofs of the two main results (Euler’s criterion and the Fundamental Theorem of Symmetric Polynomials) which are used without proof in the body of the post.

Lucas polynomials

The sequence of Lucas polynomials is defined by L_0(x)=2, L_1(x)=x, and L_n(x)=xL_{n-1}(x)+L_{n-2}(x) for n \geq 2.

The next few terms in the sequence are L_2(x)=x^2+2, L_3(x)=x^3+3x, L_4(x)=x^4 + 4x^2 + 2, and L_5(x)=x^5+5x^3+5x.

By induction, the degree of L_n(x) is equal to n. The integers L_n(1) are the Lucas numbers, which are natural “companions” to the Fibonacci numbers (see, e.g., this blog post).

Edouard Lucas (source: Wikipedia)

The polynomials H_n(x)

It’s easy to see that for n odd, L_n(x) is divisible by x and L_n(x)/x has only even-power terms. Thus L_n(x)/x = H_n(x^2) for some monic integer polynomial H_n(x) of degree (n-1)/2. We will be particularly interested in the polynomials H_p(x) for p prime.

If n is even (resp. odd), a simple induction shows that the constant term (resp. the coefficient of x) in L_n(x) is equal to n. In particular, for n odd we have H_n(0)=n.

Continue reading

Generalizations of Fermat’s Little Theorem and combinatorial zeta functions

Everyone who studies elementary number theory learns two different versions of Fermat’s Little Theorem:

Fermat’s Little Theorem, Version 1: If p is prime and a is an integer not divisible by p, then a^{p-1} \equiv 1 \pmod{p}.

Fermat’s Little Theorem, Version 2: If p is prime and a is any integer, then a^{p} \equiv a \pmod{p}.

as well as the following extension of Version 1 of Fermat’s Little Theorem to arbitrary positive integers n:

Euler’s Theorem: If n is a positive integer and (a,n)=1, then a^{\phi(n)} \equiv 1 \pmod{n}, where \phi is Euler’s totient function.

My first goal in this post is to explain a generalization of Version 2 of Fermat’s Little Theorem to arbitrary n. I’ll then explain an extension of this result to m \times m integer matrices, along with a slick proof of all of these results (and more) via “combinatorial zeta functions”.

Continue reading

An April Fools’ Day to Remember

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:

Continue reading

A Very Meta Monday

Usually my blog posts are rather tightly focused, but today I’d just like to post a few stream-of-consciousness thoughts.

(1) My blog was recently featured in the AMS Blog on Math Blogs. Perhaps by mentioning this here I can create some sort of infinite recursion which crashes the internet and forces a reboot of the year 2020.

Continue reading

Mental Math and Calendar Calculations

In this previous post, I recalled a discussion I once had with John Conway about the pros and cons of different systems for mentally calculating the day of the week for any given date. In this post, I’ll present two of the most popular systems for doing this, the “Apocryphal Method” [Note added 5/3/20: In a previous version of this post I called this the Gauss-Zeller algorithm, but its roots go back even further than Gauss] and Conway’s Doomsday Method. I personally use a modified verison of the apocryphal method. I’ll present both systems in a way which allows for a direct comparison of their relative merits and let you, dear reader, decide for yourself which one to learn.

Continue reading

Colorings and embeddings of graphs

My previous post was about the mathematician John Conway, who died recently from COVID-19. This post is a tribute to my Georgia Tech School of Mathematics colleague Robin Thomas, who passed away on March 26th at the age of 57 following a long struggle with ALS. Robin was a good friend, an invaluable member of the Georgia Tech community, and a celebrated mathematician. After some brief personal remarks, I’ll discuss two of Robin’s most famous theorems (both joint with Robertson and Seymour) and describe the interplay between these results and two of the theorems I mentioned in my post about John Conway.

Continue reading

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