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

elucasThe 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 DHLehmerof 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

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 →

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.

Before formulating the combinatorial analogue of this result which Norine and I discovered, I want to briefly reminisce about how this result came about.  In the summer of 2006, my Georgia Tech REU (Research Experience for Undergraduates) student Dragos Ilas worked on a graph-theoretic conjecture which I had made some time earlier.  Dragos spent eight weeks working on the problem and compiled a lot of experimental evidence toward my conjecture.  He gave a talk about the problem one Friday toward the end of the summer in an REU Mini-Conference that I was organizing at Georgia Tech.  Serguei Norine (then a postdoc working with my colleague Robin Thomas) was in the audience.  On Monday morning, Serguei knocked on my office door and showed me an extremely clever proof of my conjecture.  I told Serguei about my real goal, which was to prove a graph-theoretic analogue of the Riemann-Roch theorem.  I outlined what I had in mind and within a week, we had exactly the kind of Riemann-Roch formula that I had hoped for… thanks in large part to Serguei’s amazing combinatorial mind! Continue reading →

The Jacobian of the skeleton and the skeleton of the Jacobian

My new Georgia Tech colleague Joe Rabinoff and I recently posted this paper to the arXiv, entitled The skeleton of the Jacobian, the Jacobian of the skeleton, and lifting meromorphic functions from tropical to algebraic curves.  In this post I will attempt to give some context and background for that paper.

Suppose X is an algebraic variety over a complete non-Archimedean field K.  For simplicity of exposition, I will assume throughout that K is algebraically closed and that the value group \Lambda = {\rm val} (K^\times) is nontrivial.  The set of points X(K) possesses a natural (Hausdorff) analytic topology, but X(K) is totally disconnected and not even locally compact in this topology.  This is bad for all sorts of reasons.  Over the years there have been many attempts at “fixing” this problem, beginning with the Tate-Grothendieck theory of rigid analytic spaces.  One of the most successful and elegant solutions to the problem is Berkovich’s theory of non-Archimedean analytic spaces.  One can associate to X, in a natural and functorial way, an analytic space X^{\rm an} which contains X(K) as a dense subspace but has much nicer topological properties.  For example, X^{\rm an} is a locally compact Hausdorff space which is locally contractible, and is arcwise connected if X is connected.  As in the theory of complex analytic spaces, X^{\rm an} is compact if and only if X^{\rm an} is proper.  For much more information about Berkovich analytic spaces, see for example these course notes of mine.

One of the nice features of Berkovich’s theory (established in full generality only very recently, by Hrushovski and Loeser) is that the space X^{\rm an} always admits a deformation retraction onto a finite polyhedral complex \Sigma.  In general, there is no canonical choice for \Sigma.  However, in certain special cases there is, e.g. when X is a curve of positive genus or X is an abelian variety.  (More generally, the existence of canonical skeleta is closely tied in with the Minimal Model Program in birational algebraic geometry, see for example this recent paper of Mustata and Nicaise.)  For the rest of this post, I will focus on the special cases of curves and abelian varieties. Continue reading →

Attracting cycles and post-critically finite maps

A theme which I hope to pursue in multiple posts on this blog is that even if one is interested mainly in complex dynamics, it is often useful to employ p-adic (or more generally non-Archimedean) methods.  There are a number of relatively recent research papers which illustrate and support this thesis.  The one I want to talk about today is this beautiful paper of Benedetto, Ingram, Jones, and Levy, henceforth referred to as [BIJL].

From a complex dynamicist’s point of view, the main result of [BIJL] is the following theorem:

Theorem 1: For any fixed integers d ≥ 2 and B ≥ 1, there are only finitely many conjugacy classes of post-critically finite rational maps of degree d which can be defined over a number field of degree at most B, except (when d is a perfect square) for the infinite family of flexible Lattès maps.

To explain the terms used in the statement, suppose f is a rational map of degree d with complex coefficients.  We say that f is post-critically finite (henceforth denoted PCF) if the orbit of the critical points of f under iteration is finite.  PCF maps play a fundamental role in complex dynamics, roughly speaking because many dynamical features of f can be read off from the behavior of the critical points under iteration.  One source of examples are the flexible Lattès maps, which can be defined whenever d=m2 is a perfect square: these consist of all degree m rational maps obtained as the map on x-coordinates induced by multiplication-by-m on some elliptic curve.  (McMullen calls such maps affine in the paper cited below.)

As an illustration of the theorem, the only quadratic polynomials of the form z2 + c with c a rational number which are PCF are z2, z2-1, and z2-2, and every quadratic polynomial is conjugate to a polynomial of this form. Continue reading →

Quadratic reciprocity and Zolotarev’s Lemma

I want to explain a beautiful proof of the Law of Quadratic Reciprocity from c. 1874 due to Egor Ivanovich Zolotarev (1847-1878). Some time ago I reformulated Zolotarev’s argument (as presented here) in terms of dealing cards and I posted a little note about it on my web page. After reading my write-up (which was unfortunately opaque in a couple of spots), Jerry Shurman was inspired to rework the argument and he came up with this elegant formulation which I think may be a “proof from the book”.  The following exposition is my own take on Jerry’s argument.  The proof requires some basic facts about permutations, all of which are proved in this handout.

Let m and n be odd relatively prime positive integers.  You have a stack of mn playing cards numbered 0 through mn-1 and you want to deal them onto the table in an m \times n rectangular array.  Consider the following three ways of doing this:

Row deal (\rho) : Deal the cards into rows, going left to right and top to bottom.

rho Continue reading →