Pi and the AGM

In celebration of Pi Day 2024, I would like to explain how the “Arithmetic-Geometric Mean” of Gauss and Legendre can be used to give a rapid method for computing the digits of $\pi$ . By “rapid” here, I mean that the algorithm exhibits quadratic convergence: the number of correct digits roughly doubles with each iteration. I will mainly follow the exposition in Donald J. Newman’s 1985 paper “A Simplified Version of the Fast Algorithms of Brent and Salamin”.

Continue reading →

Algebraic Values of Transcendental Functions at Algebraic Points

In honor of Pi Day 2023, I’d like to discuss Hilbert’s 7th Problem, which in an oversimplified (and rather vague) form asks: under what circumstances can a transcendental function take algebraic values at algebraic points?

The connection with $\pi$ is that Lindemann proved in 1882 that the transcendental function $f(z) = e^z$ takes transcendental values at every nonzero algebraic number. Since $e^{\pi i} = -1$ by Euler’s formula, this proves that $\pi i$ , and hence $\pi$ itself, is transcendental. In light of this theorem, it is natural to wonder what if anything is special here about the function $f(z) = e^z$ and the point $z=0$ .

One thing that’s special about $z=0$ is that if $\alpha \neq 0$ is algebraic and $e^\alpha$ is also algebraic, then both $n\alpha$ and $e^{n \alpha}$ are algebraic for all $n \in {\mathbb Z}$ , and these numbers are all distinct. So one might be led to speculate that if $f$ is a transcendental entire function then there are only finitely many algebraic numbers $\alpha$ for which $f(\alpha)$ is also algebraic.

Unfortunately, as Hilbert knew, this is completely false. For example, the function $f(z) = e^{2\pi iz}$ is transcendental but it takes the rational value 1 at every integer. In 1886, Weierstrass had given an example of a transcendental entire function that takes rational values at all rational numbers; later, in 1895, Stäckel showed that there is a transcendental entire function that takes rational values at all algebraic points. However, the functions of Weierstrass and Stäckel, are in some sense “pathological”; they have large growth rates and do not occur “in nature”. The challenge is to make this intuitive feeling more precise, and also to distinguish $e^z$ from $e^{2\pi iz}$ .

One thing that is special about $e^z$ , which is not shared by any of the other functions mentioned in the previous paragraph, is that it satisfies a linear differential equation with rational coefficients (namely $f'(z) = f(z)$ ). The existence of such a (not necessarily linear) differential equation turns out to be the key idea needed to generalize Lindemann’s theorem in a substantial way.

Another fruitful generalization is to rephrase our original question as an unlikely intersection problem: given two algebraically independent entire functions $f_1(z)$ and $f_2(z)$ satisfying suitable hypotheses, can we conclude that there are only finitely many complex numbers $\alpha$ such that $f_1(\alpha)$ and $f_2(\alpha)$ are simultaneously algebraic? This generalizes our original question by letting $f_1(z) = z$ and $f_2(z) = f(z)$ .

Continue reading →

Linear algebra over rings

Test your intuition: is the following true or false?

Assertion 1: If $A$ is a square matrix over a commutative ring $R$ , the rows of $A$ are linearly independent over $R$ if and only if the columns of $A$ are linearly independent over $R$ .

(All rings in this post will be nonzero commutative rings with identity.)

And how about the following generalization?

Assertion 2: If $A$ is an $m \times n$ matrix over a commutative ring $R$ , the row rank of $A$ (the maximum number of $R$ -linearly independent rows) equals the column rank of $A$ (the maximum number of $R$ -linearly independent columns).

If you want to know the answers, read on…

Continue reading →

Fitting ideals of modules

In my previous post, I presented a proof of the existence portion of the structure theorem for finitely generated modules over a PID based on the Smith Normal Form of a matrix. In this post, I’d like to explain how the uniqueness portion of that theorem is actually a special case of a more general result, called Fitting’s Lemma, which holds for arbitrary commutative rings.

We begin by proving that one can characterize the diagonal entries in the Smith Normal Form of a matrix $A$ over a PID in an intrinsic way by relating them to the GCD of the $k \times k$ minors of $A$ for all $k$ . Actually, since the GCD isn’t defined for general rings, we will instead consider the ideal generated by the $k \times k$ minors (which makes sense for any ring, and is the ideal generated by the GCD in the case of a PID).

Continue reading →

Finitely generated modules over a P.I.D. and the Smith Normal Form

I’m teaching Graduate Algebra this semester, and I wanted to record here the proof I gave in class of the (existence part of the) structure theorem for finitely generated modules over a PID. It’s a standard argument, based on the existence of the Smith Normal Form for a matrix with entries in a PID, but it’s surprisingly hard to find a concise and accessible reference.

We assume familiarity with basic definitions in the theory of modules over a (commutative) ring. Our goal is to prove the following:

Theorem: Let $R$ be a principal ideal domain and let $M$ be a finitely generated $R$ -module. Then $M$ is isomorphic to a direct sum of cyclic $R$ -modules. More precisely, there are a non-negative integer $r$ (called the rank of $M$ ) and elements $d_1,\ldots,d_n \in M$ (called the invariant factors of $M$ ) such that $d_i \mid d_{i+1}$ for all $i=1,\ldots,n-1$ and $M \cong R^r \oplus R/(d_1) \oplus R/(d_2) \oplus \cdots \oplus R/(d_n)$ .

Continue reading →

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).

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 →

Matt Baker's Math Blog

Thoughts on number theory, graphs, dynamical systems, tropical geometry, pedagogy, puzzles, and the p-adics

Pi and the AGM

Algebraic Values of Transcendental Functions at Algebraic Points

Linear algebra over rings

Fitting ideals of modules

Finitely generated modules over a P.I.D. and the Smith Normal Form

A Fields Medal for June Huh

Counting with martingales

The Eudoxus reals

Calendar Calculations with Cards

Firing games and greedoid languages

Quadratic Reciprocity via Lucas Polynomials

Generalizations of Fermat’s Little Theorem and combinatorial zeta functions

An April Fools’ Day to Remember

A Very Meta Monday

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this: