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

# Matroids over Hyperfields, Part II

In Part I of this post, we defined hyperrings and hyperfields, gave some key examples, and introduced matroids over 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

# 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: .

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.

# Matroids over Hyperfields, Part I

In this post and its sequel, I’d like to explain a new perspective on **matroid theory** which was introduced in this recent preprint of mine. 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**.

**Hyperstructures**

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

# Hodge Theory in Combinatorics

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

# 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

# A Celebration of Independence

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

# 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

# John Nash and the theory of games

John Forbes Nash and his wife Alicia were tragically killed in a car crash on May 23, having just returned from a ceremony in Norway where John Nash received the prestigious Abel Prize in Mathematics (which, along with the Fields Medal, is the closest thing mathematics has to a Nobel Prize). Nash’s long struggle with mental illness, as well as his miraculous recovery, are depicted vividly in Sylvia Nasar’s book “A Beautiful Mind” and the Oscar-winning film which it inspired. In this post, I want to give a brief account of Nash’s work in game theory, for which he won the 1994 Nobel Prize in Economics. Before doing that, I should mention, however, that while this is undoubtedly Nash’s most influential work, he did many other things which from a purely mathematical point of view are much more technically difficult. Nash’s Abel Prize, for example (which he shared with Louis Nirenberg), was for his work in non-linear partial differential equations and its applications to geometric analysis, which most mathematicians consider to be Nash’s deepest contribution to mathematics. You can read about that work here. Continue reading

# The Sign of the Quadratic Gauss Sum and Quadratic Reciprocity

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.

# Post-Cherylmania wrap-up

My last post was about “Cheryl’s birthday puzzle”, which recently became an internet sensation. I mentioned several additional puzzles in that post and promised solutions; here they are.

Let me begin, though, with a “cryptography” variant of the Cheryl puzzle which was sent to me by my friend and puzzle guru Pete Winkler:

Cheryl’s birthday possibilities are now May 14 or 15, June 15 or 16, July 16 or 17 or August 14 or 17. Albert gets the month and Bernard the day as before, and they both want to find out the birthday. But Eve, who’s listening in, mustn’t find out. How can A and B, who’ve never met before (and aren’t cryptographers), accomplish this mission?

Think about it, it’s a fun little puzzle! [Pete writes in addition: “You can also do this with a cycle of 5 months (10 dates total) but then you need a coin to flip.”]

My *Meta-Cheryl Challenge* (as revised on April 20) was to come up with a list of dates for which the following puzzle will have a unique solution:

# 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 p-adic proof that pi is transcendental

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 motivated and simple proof that pi is irrational

Today is 3/14/15 — Super Pi Day — so was I telling my 7-year-old son all about the number this afternoon. When I told him that 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.

# Spooky inference and the axiom of choice

A large crowd had gathered in Harvard Square, and I was curious what all the cheering and gasping was about. Working my way through the crowd, I saw a street performer who (according to the handwritten red letters on his cardboard sign) went by the name “Zorn the Magnificent”. He displayed a large orange, borrowed an extremely sharp knife from his assistant, and proceeded to chop the orange into five exotic-looking pieces while standing on one hand. Working with almost unfathomably deft precision, he rearranged the pieces into two oranges, each the same size as the original one. The oranges were given out for inspection and the crowd cheered wildly. I clapped as well — even though I was familiar with the old Banach-Tarski paradox — since it was nevertheless an impressive display of skill and I had never seen it done one-handed before. I heard a man with a long white beard whisper to the woman next to him “He hides it well, but I know that he’s secretly using the Axiom of Choice.” Continue reading