John Nash and the theory of games

John Forbes Nash and his wife Alicia nashwere 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 GaussGauss, 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.

Continue reading

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:

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

Lindemann

Ferdinand von Lindemann

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 \alpha is a nonzero complex number and e^\alpha is algebraic, then \alpha must be transcendental.  Since e^{i \pi} = -1 is algebraic, this suffices to establish the transcendence of \pi (and setting \alpha = 1 it shows that e 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

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

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

Excerpts from the Grothendieck-Serre Correspondence

Like many fellow mathematicians, I was very sad to hear the news that Alexander Grothendieck passed away yesterday.  grothendieckThe word “genius” is overused; or rather, does not possess sufficiently fine gradations.  I know quite a few mathematical geniuses, but Grothendieck was a singularity.  His ideas were so original, so profound, and so revolutionary – and he had so many of them! – that I will not even attempt to summarize his contributions to mathematics here.  Rather, I thought that I would share some of my favorite passages from the fascinating Grothendieck-Serre Correspondence, published in a bilingual edition by the AMS and SMF.   They illuminate in brief flashes what made Grothendieck so extraordinary — but also human.  They also illustrate how influential Serre was on Grothendieck’s mathematical development.  Before I begin, here is a quote from another wonderful book, Alexander Grothendieck: A Mathematical Portrait, edited by Leila Schneps:

…the features which constitute in some sense his personal mathematical signature… are very familiar to those who know Grothendieck’s work: the search for maximum generality, the focus on the harmonious aspects of structure, the lack of interest in special cases, the transfer of attention from objects themselves to morphisms between them, and—perhaps most appealingly—Grothendieck’s unique approach to difficulties that consisted in turning them, somehow, upside down, and making them into the actual central point and object of study, an attitude which has the power to subtly change them from annoying obstacles into valuable tools that actually help solve problems and prove theorems… Of course, Grothendieck also possessed tremendous technical prowess, not even to mention a capacity for work that led him to concentrate on mathematics for upward of sixteen hours a day in his prime, but those are not the elements that characterize the magic in his style. Rather, it was the absolute simplicity (in his own words, “nobody before me had stooped so low”) and the total freshness and fearlessness of his vision, seemingly unaffected by long-established views and vantage points, that made Grothendieck who he was.

Continue reading

Conference on p-adic methods in number theory

After somewhat of a hiatus, I’m back to blogging again.  The purpose of this post is to advertise the conference “p-adic Methods in Number Theory”, which will be held in Berkeley, CA from May 26-30, 2015.  The conference, which I am helping to organize, is in honor of the mathematical legacy of Robert Coleman.  Please spread the word!  Here is the current version of the conference poster, which will be mailed out soon to a math department near you:

Coleman Conference Poster

Many thanks to Janet Ziebell of the Georgia Tech College of Sciences for her help creating this poster, and to Ken McMurdy for designing the conference website.

Here is a memorial article about Robert which I co-authored with Barry Mazur and Ken Ribet.   I encourage you to read it!  It will be published in the new open access journal Research in the Mathematical Sciences, in a special volume dedicated to Robert.

You can find other interesting links related to Robert Coleman’s life and work here, and in this older blog post of mine.

Real Numbers and Infinite Games, Part II

In my last post, I wrote about two infinite games whose analysis leads to interesting questions about subsets of the real numbers.  In this post, I will talk about two more infinite games, one related to the Baire Category Theorem and one to Diophantine approximation.  I’ll then talk about the role which such Diophantine approximation questions play in the theory of dynamical systems.

The Choquet game and the Baire Category Theorem

The Cantor game from Part I of this post can be used to prove that every perfect subset of {\mathbf R} is uncountable.  There is a similar game which can be used to prove the Baire Category Theorem.  Let X be a metric space.   In Choquet’s game, Alice moves first by choosing a non-empty open set U_1 in X.  Then Bob moves by choosing a non-empty open set V_1 \subseteq U_1.  Alice then chooses a non-empty open set U_2 \subseteq V_1, and so on, yielding two decreasing sequences U_n and V_n of non-empty open sets with U_n \supseteq V_n \supseteq U_{n+1} for all n.  Note that \bigcap U_n = \bigcap V_n; we denote this set by U.  Alice wins if U is empty, and Bob wins if U is non-empty. 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

The Mathematics of Marriage

linking-wedding-ringsIt’s been a while since my last blog post — one reason being that I recently got married.  In honor of that occasion, and my return to math blogging, here is a post on Hall’s Marriage Theorem.

Consider the following game of solitaire: you deal a deck of cards into 13 piles of 4 cards each, and your goal is to select one card from each pile so that no value (Ace through King) is repeated.  It is a beautiful mathematical fact that this can always been done, no matter how the cards were originally dealt!

We will deduce this from a more general result due to Philip Hall commonly known as Hall’s Marriage Theorem.  Suppose you are given finite sets A_1, A_2,\ldots, A_n and you wish to find distinct elements x_1 \in A_1,\ldots, x_n \in A_n.  (In our solitaire example, take A_j to be the values of the cards in the j^{\rm th} pile.)  Such a collection is called a transversal or SDR (system of distinct representatives).  Under what conditions is this possible?  Well, for a transversal to exist it is necessary that for each subset J \subset \{ 1,\ldots, n \}, the set A_J:= \bigcup_{j \in J} A_j contains at least \#J elements.  Hall’s theorem asserts that these conditions are also sufficient. Continue reading

Newton polygons and Galois groups

Issai Schur

Issai Schur

A famous result of David Hilbert asserts that there exist irreducible polynomials of every degree n over {\mathbf Q} having the largest possible Galois group S_n.  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 n^{\rm th} Laguerre polynomial L_n(x) = \sum_{j=0}^n (-1)^j \binom{n}{j} \frac{x^j}{j!} is irreducible and has Galois group S_n over {\mathbf Q}.

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:

Continue reading

Effective Chabauty

One of the deepest and most important results in number theory is the Mordell Conjecture, proved by Faltings (and independently by Vojta shortly thereafter). It asserts that if X / {\mathbf Q} is an algebraic curve of genus at least 2, then the set X({\mathbf Q}) of rational points on X is finite. At present, we do not know any effective algorithm (in theory or in practice) to compute the finite set X({\mathbf Q}). The techniques of Faltings and Vojta lead in principle to an upper bound for the number of rational points on X, but the bound obtained is far from sharp and is difficult to write down explicitly. In his influential paper Effective Chabauty, Robert Coleman combined his theory of p-adic integration with an old idea of Chabauty and showed that it led to a simple explicit upper bound for the size of X({\mathbf Q}) provided that the Mordell-Weil rank of the Jacobian of X is not too large.  (For a memorial tribute to Coleman, who passed away on March 24, 2014, see this blog post.)

Continue reading

Robert F. Coleman 1954-2014

I am very sad to report that my Ph.D. advisor, Robert Coleman, died last night in his sleep at the age of 59.  His loving wife Tessa called me this afternoon with the heartbreaking news.  Robert was a startlingly original and creative mathematician who has had a profound influence on modern number theory and arithmetic geometry.  He was an inspiration to me and many others and will be dearly missed.

Robert and Bishop in Paris

Robert and Bishop in Paris

Robert was born on November 22, 1954 and earned a mathematics degree from Harvard University.  He subsequently completed Part III of the mathematical tripos at Cambridge, where he worked with John Coates and made important contributions to local class field theory.  By the time he entered graduate school at Princeton, Robert had essentially already written his doctoral dissertation, but his formal thesis advisor was Kenkichi Iwasawa.  He began teaching at UC Berkeley in 1983 and was a recipient of a MacArthur “Genius” Fellowship in 1987.   Robert published 63 papers, including 8 papers in the prestigious journal Inventiones Mathematicae and 5 in the Duke Mathematical Journal.   He had an amazing intuition for everything p-adic.  Long before the invention of Berkovich spaces, Robert could somehow visualize paths and structures in p-adic geometry which no one else in the world saw as keenly or as profoundly.  I rarely saw him reading papers or books.  He seemed to figure out whatever he needed to know almost from scratch, which often made his papers quite difficult to read but this went hand in hand with his brilliance and originality.

When I was a graduate student at Berkeley, Robert hosted an invitation-only wine and cheese gathering in his office every Friday afternoon code-named “Potatoes”.  Among the regular attendees were Loïc Merel and Kevin Buzzard, who were postdocs at the time.  It was a wonderful tradition.  In the summer of 1997, while I was still a graduate student, Robert invited me to accompany him for three weeks in Paris to a workshop  on p-adic Cohomology at the Institut Henri Poincare.  That was the first time I met luminaries like Faltings, Fontaine, and Mazur.  Since the workshop was (a) totally in French and (b) on a topic I knew almost nothing about, I was in completely over my head.  But I fell in love with Paris (which I’ve since returned to many times) and my best memories from that trip are of dining with Robert and seeing the city with him.

The trip also taught me to appreciate the significant challenges which Robert, who had Multiple Sclerosis, bravely faced every day.  I remember helping Robert check into his hotel room near the Luxembourg Gardens, only to find out that his wheelchair did not fit in the elevator.  We had to find another hotel room for him, which was not so easy given the level of our French!  Curbs were a constant challenge for Robert, as finding on- and off- ramps for wheelchairs in Paris was like trying to get a vegan meal in rural Arkansas.

Continue reading