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

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

It’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

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:

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

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

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.

The BSD conjecture is true for most elliptic curves

This past weekend I had the privilege to speak at the Southern California Number Theory Day along with Manjul Bhargava, Elena Fuchs, and Chris Skinner.  Manjul and Chris spoke about a series of remarkable results which, when combined, prove that at least 66.48% of elliptic curves over $\mathbf Q$ satisfy the (rank part of the) Birch and Swinnerton-Dyer (BSD) Conjecture (and have finite Shafarevich-Tate group).  Bhargava’s work with Arul Shankar also proves that at least 20.6% of elliptic curves over $\mathbf Q$ have rank 0, at least 83.75% have rank at most 1, and the average rank is at most 0.885.  Conjecturally, 50% of elliptic curves have rank 0, 50% have rank 1, and 0% have rank bigger than 1, and thus the average rank should be 0.5.  (And conjecturally, 100% of elliptic curves satisfy the BSD conjecture. :))  Before the work of Bhargava-Shankar and Bhargava-Skinner (which makes use of recent results of Skinner-Urban. Wei Zhang, and the Dokchitser brothers among others), the best known unconditional results in this direction were that at least 0% of elliptic curves have rank 0, at least 0% have rank 1, the average rank is at most infinity, and at least 0% of curves satisfy the BSD conjecture.

I will attempt to briefly summarize some of the main ideas from their talks; see these papers by Bhargava-Skinner and Bhargava-Shankar for more details and references.  (The paper of Bhargava, Skinner, and Wei Zhang showing 66.48% is forthcoming. [Note added 7/8/14: that paper has now appeared at http://arxiv.org/abs/1407.1826.]) Continue reading

The Pentagon Problem

In this post I’ll talk about another favorite recreational math puzzle, the (in)famous “Pentagon Problem”.  First, though, I wanted to provide a solution to the Ghost Bugs problem from my last blog post.  The puzzle is the following:

You are given four lines in a plane in general position (no two parallel, no three intersecting in a common point). On each line a ghost bug crawls at some constant velocity (possibly different for each bug). Being ghosts, if two bugs happen to cross paths they just continue crawling through each other uninterrupted.  Suppose that five of the possible six meetings actually happen. Prove that the sixth does as well.

Here is the promised solution.  The idea (like in Einstein’s theory of general relativity) is to add an extra dimension corresponding to time.  We thus lift the problem out of the page and replace the four lines by the graph of the bugs’ positions as a function of time.  Since each bug travels at a constant speed, each of the four resulting graphs $g_i$ is a straight line.  By construction, two lines $g_i$ and $g_j$ intersect if and only if the corresponding bugs cross paths.

Suppose that every pair of bugs cross paths except possibly for bugs 3 and 4.  Then the lines $g_1, g_2, g_3$ each intersect one another (in distinct points) and therefore they lie in a common plane.  Since line $g_4$ intersects lines $g_1$ and $g_2$ in distinct points, it must lie in the same plane.  The line $g_4$ cannot be parallel to $g_3$, since their projections to the page (corresponding to forgetting the time dimension) intersect.  Thus $g_3$ and $g_4$ must intersect, which means that bugs 3 and 4 do indeed cross paths.

Cool, huh?  As I mentioned in my last post, I can still vividly remember how I felt in the AHA! moment when I discovered this solution more than 15 years ago.

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

Riemann-Roch theory for graph orientations

In this post, I’d like to sketch some of the interesting results contained in my Ph.D. student Spencer Backman’s new paper “Riemann-Roch theory for graph orientations”.

First, a bit of background.  In a 2007 paper, Emeric Gioan introduced the cycle-cocycle reversal system on a (finite, connected, unoriented) graph G, which is a certain natural equivalence relation on the set of orientations of G.  Recall that an orientation of G is the choice of a direction for each edge.  A cycle flip on an orientation ${\mathcal O}$ consists of reversing all the edges in a directed cycle in ${\mathcal O}$.  Similarly, a cocycle flip consists of reversing all the edges in a directed cocycle in ${\mathcal O}$, where a directed cocycle (also called a directed cut) is the collection of all oriented edges connecting a subset of vertices of G to its complement.  The cycle-cocycle reversal system is the equivalence relation on the set of orientations of G generated by all cycle and cocycle flips.  In his paper, Gioan proves (via a deletion-contraction recursion) the surprising fact that the number of equivalence classes equals the number of spanning trees in G.  A bijective proof of this result was subsequently obtained by Bernardi. Continue reading

Reduced divisors and Riemann-Roch for Graphs

In an earlier post, I described a graph-theoretic analogue of the Riemann-Roch theorem and some of its applications.  In this post, I’d like to discuss a proof of that theorem which is a bit more streamlined than the one which Norine and I gave in our original paper [BN].  Like our original proof, the one we’ll give here is based on the concept of reduced divisors. Continue reading

Lucas sequences and Chebyshev polynomials

This is a sequel to last week’s blog post “Two applications of finite fields to computational number theory“.  The main reason I decided to write a follow-up is that I’ve learned a lot about Concluding Observations #1 and #6 from that post during the last week.   In Observation #1, I mentioned without further comment a recursive procedure for computing square roots modulo a prime; it turns out that this procedure is essentially equivalent to Cipolla’s algorithm, but was discovered independently by Lehmer (who it seems did not know about Cipolla’s work).  I learned this from the wonderful book “Édouard Lucas and Primality Testing” by Hugh C. Williams, which I highly recommend to anyone interested in the history of mathematics.  In explaining the connection between the algorithms of Cipolla and Lehmer, I’ll make a digression into the general theory of Lucas sequences, which I had some vague knowledge of before but which I’ve learned a lot about in the last week from reading Williams’ book.  In Observation #6, I asked if there was a conceptual explanation for the fact that the Chebyshev polynomial $x^2 - 2$ shows up in the Lucas-Lehmer test; Greg Kuperberg sent me just such an explanation and I will expand on his comments below. 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.

The 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 of 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

Primitive roots, discrete logarithms, and p-adic numbers

This morning I attended Martin Hellman’s stimulating keynote address at the 2013 Georgia Tech Cyber Security Summit. Martin Hellman is the co-inventor, with Whitfield Diffie, of the Diffie-Hellman Key Exchange Protocol, which began the (public) public-key cryptography revolution.  Among the interesting things I learned during Martin Hellman’s talk are:

1. Hellman feels that Ralph Merkle deserves equal credit for inventing public-key cryptography and refers to his own invention as the Diffie-Hellman-Merkle key exchange protocol.  (Merkle was the director of the Georgia Tech Information Security Center from 2003-2006.)

2. Hellman came up with the famous “double padlock” thought experiment after the invention of the Diffie-Hellman-Merkle key exchange protocol, as a way to explain it to others.  The mathematics came first.  (I had always wondered about this.)

3. Most interestingly, Hellman said that he got the idea to use modular exponentiation/discrete logarithms as a “one-way function” from the engineer and mathematician John Gill (who I never heard of before this morning).  John Gill’s other suggestion was to use multiplication/factoring, which forms the basis of RSA!  It’s all the more amazing that I’ve never heard of John Gill because he earned his bachelor’s degree in Applied Mathematics from Georgia Tech (where I now teach) and his Ph.D. in Mathematics from U.C. Berkeley (where I got my Ph.D.)!  Hellman also recounted a conversation in which Gill (who is African-American) mentioned having encountered very little racial intolerance during his undergraduate studies in the 1960’s — apparently Georgia Tech was (relatively speaking) an oasis of tolerance among southern universities during that time.

Now on to the mathematical part of this post, which is an unusual proof of the existence of primitive roots modulo primes which I came up with recently while preparing a lecture for my course on Number Theory and Cryptography.  The proof is much less elementary than every other proof I’ve seen, but I would argue that it nevertheless has some merit.   Continue reading

Riemann-Roch for Graphs and Applications

I plan to write several posts related to the Riemann-Roch Theorem for Graphs, which was published several years ago in this paper written jointly with Serguei Norine.  In this post I want to explain the statement of the theorem, give some anecdotal background, and mention a few applications which have been discovered in recent years.

The Riemann-Roch Theorem

The (classical) Riemann-Roch Theorem is a very useful result about analytic functions on compact one-dimensional complex manifolds (also known as Riemann surfaces).  Given a set of constraints on the orders of zeros and poles, the Riemann-Roch Theorem computes the dimension of the space of analytic functions satisfying those constraints.  More precisely, if $D$ denotes the set of constraints and $r(D)$ is the dimension of the space of analytic functions satisfying those constraints, then the Riemann-Roch theorem asserts that

$r(D) - r(K-D) = {\rm deg}(D) + 1 - g$

where $g$ is the genus (“number of holes”) of the Riemann surface $X$, ${\rm deg}(D)$ is the total number of constraints, and $K$ is the “canonical divisor” on $X$.  See the Wikipedia page for much more information.