What’s new in the world of addition?

May 5, 2011

I gave a talk at the Mathematics Teachers’ Circle of Austin on the distribution of carries in adding numbers in a given base. (The full title “Dizzying the memory of arithmetic” is supposed to be a play of words on a phrase in Macbeth…)

The question is this. Take x_1,…,x_k some n digit numbers, say in base 10. When you add them with the usual elementary school algorithm some of the columns of k digits will contribute a carry, a number in the range 0 to k-1, to the next column. What is the distribution of these carries for random x_i for large n?

The question has an interesting answer, which I won’t spoil but refer you to the original beautiful paper by J. Holte (mathscinet).

Surprisingly, Diaconis and Fulman found a connection between this question and card shuffling, Foulkes characters, symmetric functions,…

I love it when we discover something new and interesting in things right under our noses.


Limiting distribution of Betti numbers I

April 27, 2011

I gave a talk in the algebra seminar at Georgia Tech on April 11, 2011 with this title. The basic question is this: how are the Betti numbers of a discrete family of algebraic varieties distributed as we approach large values of the parameters? After appropriately shifting and scaling, is there a limiting distribution?

The question arose from our joint work with Hausel on the geometry of character varieties. We later found and instance of this phenomenon already discussed by Reineke archiv (see below).

I presented three examples.

1. The Grassmanian G_n,k. Here for large n and k the Betti numbers are distributed as a Gaussian. No surprise perhaps; by Poincare duality the distribution is symmetric and by the Hard Lefschetz theorem it increases up to the middle of the range and then decreases.

2. The Hilbert scheme of n points on the plane. Here the Betti numbers are distributed as partitions of n according to length (by Goettsche’s work). There is a limiting distribution as proved by Erdos and Lehner. It is the Gumbel distribution exp(-exp(-x)) that appears as an universal distribution for max(x_1,…,x_n) of independent, identically distributed random variables x_i (given the known height of a river for the past 10 years how high could we expect it to get this year?) You can see the case n=500 and the corresponding limit case in the notes of the talk. The distribution is no longer symmetric.

3. The toric hyperkaehler variety (Hausel-Sturmfels archiv) associated to the complete graph K_n. Here the Betti numbers are given by the coefficients of the reliability polynomial of K_n. These are known to have a limiting distribution: the Airy distribution (the same as that appearing in Reineke’s case mentioned above.) This distribution appears in a number of different other contexts (hashing algorithms, area of Brownian motion, large graphs with fixed genus, etc.)

It is remarkable that the distributions in 2 and 3 (Gumbel and Airy respectively) are in fact very close (scaling and shifting appropriately) to each other but are definitely not the same. (In the early stages we thought that perhaps we always got the Gumbel distribution; it makes you wonder how much to read in the comparison of continuous graphs to discrete data.)

Is there some kind of universality?

After the talk Stavros Garoufalidis mentioned that the Airy distribution also appears in various matrix models in Physics.