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.

Advertisements

Symmetric Functions 0

June 14, 2007

I’ll be gone on vacation until the end of the month and won’t be posting. When I come back I plan to write more about symmetric functions, starting from scratch and hopefully reaching eventually something about Macdonald polynomials. I will be teaching a graduate class on representation theory of finite groups this Fall and I see this project as preparing the lectures for the second half of the course.

The standard reference (“the scriptures” as Schiffmann put it in his talk at AIM) is Ian G. Macdonald’s book: Symmetric functions and Hall polynomials. Second edition. Oxford Mathematical Monographs. Oxford Science Publications. The Clarendon Press, Oxford University
Press, New York, 1995. x+475 pp. ISBN 0-19-853489-2. (The second edition is more that just a cosmetic change of the first.)

This book is truly amazing. There’s absolutely no fat in it. This, however, can make it a bit hard to get into. In my case, the motivation to read it came from needing his description of the irreducible characters of GL_n (k), with k a finite field (chapter IV), which is in turn based on the original description by Green. I was hooked.

Symmetric functions are at the very least a fantastic computational tool. They can be used to package quite a bit of information in a very concise form. Typically this information is combinatorial or related to representations of certain finite groups (the symmetric group, obviosuly, but also, as mentioned above, GL_n(k) and so on). This is already evident in the description by Frobenius of the irreducible characters of the symmetric groups. In a situation that is quite typical the values of the characters (the character table) appear as the transition matrix (i.e. a change of basis matrix) between two natural bases of the ring \Lambda of symmetric functions in infinitely many variables: the power sums and the Schur functions. (I can’t refrain from quoting Macdonald to the effect that elements of \Lambda, itself a limit of polynomial rings, are neither polynomials nor functions but we have to call them something! See his paper “A new class of symmetric functions”, Publ. IRMA Strasbourg, 1988 372/S-20, Actes 20e Seminaire Lotharingien, p. 131-171, were he introduces the Macdonald polynomials. )

We also know from the work of Haiman that symmetric functions are relevant to the geometry of Hilbert schemes. My experience with our work with Hausel and Letellier is that they are also crucial to understanding the cohomology of character varieties. I am convinced that tough we use them mostly as a computational device the connection goes well beyond that.

Non-sequitur: Farshid Hajir pointed out during my talk in Amherst last Fall that Frobenius appeared in it in three different forms: 1) the Frobenius substitution, the absolute bread and butter of Number Theory, 2) the trace formula expressing the number of points of a character variety over a finite field in terms of irreducible characters of the target group and 3) Frobenius algebras, the building block of topological field theories. Frobenius was just amazing! I highly recommend his Collected Works; I would bet money that there’s still a lot to be dug up from them.

For the history on how Frobenius developed the theory of characters (a pretty convoluted one and hard to fathom from modern accounts) I recommend Representations of Finite Groups: A Hundred Years, Part I by T. Y. Lam.