p-adic Numbers and Dissections of Squares into Triangles

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

A p-adic proof that pi is transcendental

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

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

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