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

Primitive roots, discrete logarithms, and p-adic numbers

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

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