Category Archives: Pedagogy

Torsors as proportion spaces

A torsor (or principal homogeneous space) is, informally speaking, a mathematical structure quite similar to a group, but without a natural identity element. More formally, if G is a group, a G-torsor is a set X on which G acts simply and transitively, i.e., for every x,y \in X, there is a unique g \in G such that g \cdot x = y. Torsors are ubiquitous in mathematics, see for example this blog post by John Baez.

I noticed that one can define the notion of torsor without ever mentioning groups, and then recover the notion of a group from this, rather than vice-versa. I’ve never seen this formalized before, so I thought I’d take the time to write it down here. Please let me know if you’re aware of a reference! (Note added 9/18/23: Ben Steinberg points out that this is closely related to the notion of a heap — see below for additional details.)

I will coin a new term — proportion space — for the concept I’m about to describe. But we’ll see that a proportion space X has an associated group G_X which acts simply and transitively on X, making X into a G_X-torsor, and conversely every torsor X for a group G is naturally a proportion space (with associated group isomorphic to G). So the concepts of torsor and proportion space are essentially equivalent, except for the fact that simply transitive group actions which differ by an automorphism of G correspond to the same proportion structure on X.

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 →

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 →

Probability, Primes, and Pi

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: 6/\pi^2.

The hero of this story is Leonhard Euler, who worked out this astonishing connection between prime numbers and \pi 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.

18th century mathematician Leonhard Euler

Continue reading →

The Jordan Canonical Form

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 →

Number Theory and Cryptography: A Distance Learning Course for High School Students

The following post was originally published on the AMS Blog “On Teaching and Learning Mathematics”.  I have reproduced it here with the permission of the AMS.

Last year, I began offering an online Number Theory and Cryptography course for gifted high school students through Georgia Tech.  Fourteen high school seniors from metro Atlanta took the course in Fall 2014, and overall I would say it was a big success.  We will be offering the course again in Fall 2015 and are expecting roughly double the number of students.  After describing the structure of the course, I will relate some of my experiences and describe some of the things I learned along the way.  I hope this article stimulates others to think outside the box about using technology in education without necessarily following the standard “MOOC” model.
Continue reading →

Cherylmania

Many of you have undoubtedly heard by now the math puzzle about Cheryl’s birthday which has been sweeping across the internet.  I appeared on CNN on Wednesday to explain the solution — here is a link to the problem and my explanation.  Since that appearance, I’ve received dozens of emails about the problem and/or my explanation of it.   I thought I’d share a few of my thoughts following this flurry of activity. Continue reading →

A motivated and simple proof that pi is irrational

Liana Tang pieToday is 3/14/15 — Super Pi Day — so was I telling my 7-year-old son all about the number \pi this afternoon.  When I told him that \pi keeps on going forever and ever he asked “How do you know that?”  Although I don’t know a proof that I could explain to a 7-year-old, I wanted to record the following proof which uses only basic calculus.  It is essentially Niven’s famous proof, as generalized by Alan Parks, but I have tried to write it in a way which is more motivated than the usual treatments.  As a bonus, the proof also shows that e is irrational.

Continue reading →

Real Numbers and Infinite Games, Part I

Georg Cantor

Georg Cantor

In this post I’d like to illustrate how one can use infinite games to prove theorems about the real numbers.  I’ll begin with a game-theoretic proof that the set of real numbers is uncountable, following the exposition in this paper of mine.  This will lead us somewhat unexpectedly into the realm of descriptive set theory, where we will discuss how games are used in cutting-edge explorations of the Axiom of Choice, the Continuum Hypothesis, and the foundations of second-order arithmetic.   In a sequel post I will discuss how infinite games can be used to study Diophantine approximation, with applications to complex dynamics.

Countable versus uncountable infinities

When my daughter was 5 years old, she asked me if there is just one infinity.  I proudly kissed her on the forehead and told her what an excellent question that was.  I told her no, infinity comes in many different flavors.  I pretty much left it at that, but since she’s 10 now, here are some more details for her.  (The reader familiar with the basics of set theory can move on to the next section.) Continue reading →

Beauty and explanation in mathematics

I just moved into a new house and haven’t had time to blog much lately.  But I did want to advertise my friend Manya Raman-Sundström’s upcoming Workshop on Beauty and Explanation in Mathematics at Umeå University in Sweden: http://mathbeauty.wordpress.com/wbem/

The list of invited speakers includes Hendrik Lenstra, one of my graduate school teachers.  (If you haven’t see it before, you should check out Lenstra’s lovely short article Profinite Fibonacci Numbers.) Continue reading →

Two applications of finite fields to computational number theory

In this post I’d like to discuss how finite fields (and more generally finite rings) can be used to study two fundamental computational problems in number theory: computing square roots modulo a prime and proving primality for Mersenne numbers.  The corresponding algorithms (Cipolla’s algorithm and the Lucas-Lehmer test) are often omitted from undergraduate-level number theory courses because they appear, at first glance, to be relatively sophisticated.  This is a shame because these algorithms are really marvelous — not to mention useful — and I think they’re more accessible than most people realize. I’ll attempt to describe these two algorithms assuming only a standard first-semester course in elementary number theory and familiarity with complex numbers, without assuming any background in abstract algebra.  These algorithms could also be used in a first-semester abstract algebra course to help motivate the practical utility of concepts like rings and fields.

Anecdotal Prelude

In researching this blog post on Wikipedia, I learned a couple of interesting historical tidbits that I’d like to share before getting on with the math.

elucasThe French mathematician Edouard Lucas (of Lucas sequence fame) showed in 1876 that the 39-digit Mersenne number 2^{127}-1 is prime.  This stood for 75 years as the largest known prime.  Lucas also invented (or at least popularized) the Tower of Hanoi puzzle and published the first description of the Dots and Boxes game.  He died in quite an unusual way: apparently a waiter at a banquet dropped what he was carrying and a piece of broken plate cut Lucas on the cheek. Lucas developed a severe skin inflammation and died a few days later at age 47.

Derrick Henry Lehmer was a long-time professor of mathematics at U.C. Berkeley.  In 1950, Lehmer was one DHLehmerof 31 University of California faculty members fired for refusing to sign a loyalty oath during the McCarthy era.  In 1952, the California Supreme Court declared the oath unconstitutional, and Lehmer returned to Berkeley shortly thereafter.  Lehmer also built a number of fascinating mechanical sieve machines designed to factor large numbers. Continue reading →