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?
In an earlier post, I described the dollar game played on a finite graph , 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.
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:
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.
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.
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 be the sequence of squares, and let be its complement in . What is the term of the sequence ? In other words, can we give a formula for the non-square? One might imagine that no simple formula exists, but in fact Lambek and Moser showed that the non-square is equal to , where denotes the closest integer to . Similarly, if denotes the set of triangular numbers, the element of the complement of is equal to .
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:
Indeed, there is precisely one term for each integer on the left-hand side, and the same is true for the right-hand side (consider separately the cases where but , but , and ). 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 :
This is impossible, however, as we see by letting approach a primitive root of unity, since each term stays bounded except for , which tends to infinity.
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 →
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.
Today marks the birthday of Karl Friedrich Gauss, the “Prince of Mathematicians”, who was born on April 30, 1777. In honor of Gauss’s 238th birthday, I thought I would blog about one of Gauss’s favorite theorems — the Law of Quadratic Reciprocity — and its relation to the sign of the quadratic Gauss sum, which we will determine using the Discrete Fourier Transform. Our exposition mostly follows this paper by Ram Murty. Regarding the sign of the quadratic Gauss sum, Gauss conjectured the correct answer in his diary in May 1801, but it took more than four years until he was able to find a proof in August 1805. Gauss wrote to his friend W. Olbers that seldom had a week passed for four years that he had not tried in vain to prove his conjecture. Then:
Finally, two days ago, I succeeded – not on account of my hard efforts, but by the grace of the Lord. Like a sudden flash of lightning, the riddle was solved. I am unable to say what was the conducting thread that connected what I previously knew with what made my success possible.
In my last blog post, I discussed a simple proof of the fact that pi is irrational. That pi is in fact transcendental was first proved in 1882 by Ferdinand von Lindemann, who showed that if is a nonzero complex number and is algebraic, then must be transcendental. Since is algebraic, this suffices to establish the transcendence of (and setting it shows that is transcendental as well). Karl Weierstrass proved an important generalization of Lindemann’s theorem in 1885.
The proof by Lindemann that pi is transcendental is one of the crowning achievements of 19th century mathematics. In this post, I would like to explain a remarkable 20th century proof of the Lindemann-Weierstrass theorem due to Bezivin and Robba [Annals of Mathematics Vol. 129, No. 1 (Jan. 1989), pp. 151-160], which uses p-adic analysis in a key way. Their original argument was made substantially more elementary by Beukers in this paper; we refer the reader to [American Mathematical Monthly Vol. 97 Issue 3 (Mar. 1990), pp. 193-197] for a lovely exposition of the resulting proof, which rivals any of the usual approaches in its simplicity. But I’d like to focus here on the original Bezivin-Robba proof, which deserves to be much better known than it is. In the concluding remarks, we will briefly discuss a 21st century theorem of Bost and Chambert-Loir that situates the Bezivin-Robba approach within a much broader mathematical framework. Continue reading →
A famous result of David Hilbert asserts that there exist irreducible polynomials of every degree over having the largest possible Galois group . However, Hilbert’s proof, based on his famous irreducibility theorem, is non-constructive. Issai Schur proved a constructive (and explicit) version of this result: the Laguerre polynomial is irreducible and has Galois group over .
In this post, we give a simple proof of Schur’s result using the theory of Newton polygons. The ideas behind this proof are due to Robert Coleman and are taken from his elegant paper On the Galois Groups of the Exponential Taylor Polynomials. (Thanks to Farshid Hajir for pointing out to me that Coleman’s method applies equally well to the Laguerre polynomials.) Before we begin, here is a quote from Ken Ribet taken from the comments section of this post: