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.
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
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 . The proof makes use of the famous identity , 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 .
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.
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 Jacobian of a finite graph is a finite abelian group whose cardinality is equal to the number of spanning trees of . In this earlier post, I discussed a family of combinatorial bijections between elements of and the set of spanning trees of . I also discussed the fact that for plane graphs, these Bernardi bijections come from a natural simply transitive action of on (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 on 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 as an intermediate object rather than . The latter is canonically isomorphic (as a -torsor) to the set of break divisors on ; the former is isomorphic to the circuit-cocircuit reversal system, which we now introduce.Continue reading
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
I recently gave three lectures at Yale University for the Hahn Lectures in Mathematics. The unifying theme of my talks was the notion of break divisor, a fascinating combinatorial concept related to the Riemann-Roch theorem for graphs. Some applications of break divisors to algebraic geometry will be discussed in a follow-up post.
Break divisors on graphs
Let be a connected finite graph of genus , where . Our central object of study will be the notion of a break divisor on . Recall that a divisor on a graph is an assignment of an integer to each vertex of . The divisor is called effective if for all ; in this case, we often visualize by placing “chips” at . And the degree of is the sum of over all vertices , i.e., the total number of chips. By analogy with algebraic geometry, we write divisors on as formal sums , i.e., as elements of the free abelian group on .
A break divisor on is an effective divisor of degree such that for every connected subgraph of , the degree of restricted to is at least . In other words, there are total chips and each connected subgraph contains at least genus-of- of these chips. One surprising fact, proved in this paper (referred to henceforth as [ABKS]), is that the number of break divisors on is equal to the number of spanning trees of . Continue reading
I’m speaking tomorrow in the AMS Current Events Bulletin about the work of Adiprasito, Huh, and Katz on the Rota-Welsh conjecture and Hodge theory for matroids. See this previous post for an introduction to their work. [Note added 9/21/17: My write-up for the Current Events Bulletin can be found here.]
Here’s an excerpt from the last section of my slides which I may or may not have time to discuss in tomorrow’s talk. It concerns this recent paper of June Huh and Botong Wang. (Note added: As anticipated I did not have time to cover this material! Here are the slides themselves: ceb_talk)
My thesis advisor Robert Coleman passed away two years ago today (see this remembrance on my blog). One of the things I learned from Robert is that p-adic numbers have many unexpected applications (see, for example, this blog post). Today I want to share one of my favorite surprising applications of p-adic numbers, to a simple problem in Euclidean geometry. Continue reading
In Part I of this post, we defined hyperrings and hyperfields, gave some key examples, and introduced matroids over (doubly distributive) hyperfields in terms of Grassman-Plücker functions. If is a finite set and is a field, we saw that a -matroid on is the same thing as a linear subspace of , and if is the Krasner hyperfield then a -matroid on is the same thing as a matroid in the usual sense. Matroids over the hyperfield of signs are the same thing as oriented matroids, and matroids over the tropical hyperfield are the same thing as valuated matroids. In this post we will give some “cryptomorphic” axiomatizations of matroids over hyperfields, discuss duality theory, and then discuss the category of hyperrings in a bit more detail. Continue reading
What is the probability that two randomly chosen integers have no prime factors in common? In honor of Pi Day, I’d like to explain the surprising answer: .
The hero of this story is Leonhard Euler, who worked out this astonishing connection between prime numbers and through a series of brilliant insights. In the spirit of Euler, I will be rather cavalier about issues of convergence and rigor here, focusing on the key underlying ideas.
In this post and its sequel, I’d like to explain a new perspective on matroid theory which was introduced in this recent preprint which I wrote with Nathan Bowler. The main observation is that by working with algebraic structures called hyperfields, in which addition is allowed to be multi-valued, linear subspaces, matroids, valuated matroids, and oriented matroids become special cases of a single general concept. In the process of explaining this observation, I also hope to advertise how natural hyperfields are, for example in the context of tropical geometry.
The notion of an algebraic structure in which addition is allowed to be multi-valued goes back to Frédéric Marty, who introduced hypergroups in 1934. Later on, in the mid-1950’s, Marc Krasner developed the theory of hyperrings and hyperfields in the context of approximating non-Archimedean fields, and in the 1990’s Murray Marshall explored connections to the theory of real spectra and spaces of orderings. For the most part, however, the theory of hyperstructures was largely ignored by the mathematical community at large until Connes and Consani started advocating its potential utility in connection with -geometry and the Riemann hypothesis. There now seems to be a reappraisal of sorts going on within the math community of the “bias” against multi-valued operations. Continue reading
In January 2016, my colleague Josephine Yu and I are organizing a workshop called Hodge Theory in Combinatorics. The goal of the workshop is to present the recent proof of a 50-year-old conjecture of Rota by Karim Adiprasito, June Huh, and Eric Katz. In this post, I want to explain what the conjecture says and give a brief outline of its marvelous proof. I will follow rather closely this paper by Adiprasito-Huh-Katz (henceforth referred to as [AHK]) as well as these slides from a talk by June Huh. Continue reading
In my current position as Director of Undergraduate Studies for the Georgia Tech School of Mathematics, I’ve been heavily involved with revamping our linear algebra curriculum. So I’ve spent a lot of time lately reading through various linear algebra books. The goal of this post is to give a self-contained proof of the existence and uniqueness of the Jordan Canonical Form which is somewhat different from the ‘usual’ proofs one finds in textbooks. I’m not claiming any novelty — I’m sure this approach has been discovered before — but I don’t know a good reference so I thought I’d record the details here.
The proof I give here does not use properties of polynomials (e.g. the Chinese Remainder Theorem), nor does it rely on the classification of finitely generated modules over a PID, so it might be of some pedagogical interest. The proof I give for the Generalized Eigenvector Decomposition is based on an auxiliary result — the Fitting Decomposition — which in my opinion ought to be better known. The proof I give of the structure theorem for nilpotent operators comes from these lecture notes of Curt McMullen (Theorem 5.19). It is particularly concise compared to some other arguments I’ve seen. Continue reading
Yesterday marked the second anniversary of my blog, and today is the 239th birthday of the U.S. In celebration of Independence Day, I want to explain what matroids are. Matroids were invented by Hassler Whitney (and independently by Takeo Nakasawa) to abstract the notion of linear independence from vector spaces to a much more general setting that includes acyclicity in graphs. Other pioneering early work on matroids was done by Garrett Birkhoff and Saunders MacLane. Matroid theory is a rich subject about which we will only scratch the surface here. In particular, there are many different (“cryptomorphic“) ways to present the matroid axioms which all turn out to be (non-obviously) equivalent to one another. We will focus on just a couple of ways of looking at matroids, emphasizing their connections to tropical geometry. Continue reading