Newton’s sums, necklace congruences, and zeta functions

The goal of this post is to give a purely combinatorial proof of Newton’s sums which would have interrupted the flow of the previous post. Recall that, in the notation of the previous post, Newton’s sums (also known as the first Newton-Girard identity) state that

.

One way to motivate a combinatorial proof is to recast the generating function interpretation appropriately. Given a polynomial with non-negative integer coefficients and , let be the reciprocals of the roots of . Then

.

The left hand side of this identity suggests a particular interpretation in terms of the combinatorial species described by . Today we’ll describe this species when is a polynomial with non-negative integer coefficients and then describe it in the general case, which will handle the extension to the symmetric function case as well.

The method of proof used here is closely related to a post I made previously about the properties of the Frobenius map, and at the end of the post I’ll try to discuss what I think might be going on.

The magic of the Frobenius map II

Once upon a time I discussed some interesting uses of the Frobenius map to solve some Putnam-style problems. Unfortunately, I wrote that post before becoming really interested in combinatorics, so I neglected to develop that particular side of the story, which I’d like to do now.

The beginning of this story is the folklore combinatorial proof of Fermat’s little theorem: for any positive integer and prime , we have

.

The proof is simple but powerful. Consider the set of possible ways to color beads with colors. The cyclic group acts on this set in the obvious way. (One says that the beads are “on a necklace.”) The great thing about actions of a prime cyclic group is that elements arrange themselves into two kinds of orbits: fixed points and orbits of size . (This is just a special case of the orbit-stabilizer theorem.) The total number of colorings is , but if we only want to work it suffices to count the number of fixed points under the action of . These are precisely the colorings using only one color, of which there are , and the result follows.

The standard generalization of this result to finite fields is as follows: and is generated by the Frobenius map . Does this result also have a combinatorial proof?

The Catalan numbers, regular languages, and orthogonal polynomials

I’ve been inspired by The Unapologetic Mathematician (and his pages and pages of archives!) to post more often, at least for the remainder of the summer. So here is a circle of ideas I’ve been playing with for some time.

Let be the ordinary generating function for the ordered rooted trees on vertices (essentially we ignore the root as a vertex). This is one of the familiar definitions of the Catalan numbers. From a species perspective, ordered rooted trees are defined by the functional equation

.

The generating function describes the species of sequences. So what this definition means is that, after tossing out the root, an ordered rooted tree is equivalent to a sequence of ordered rooted trees (counting their roots) in the obvious way; the roots of these trees are precisely the neighbors of the original root. Multiplying out gets us a quadratic equation we can use to find the usual closed form of , but we can instead recursively apply the above to obtain the beautiful continued fraction

.

Today’s discussion will center around this identity and some of its consequences.

Dynkin diagrams and the Mahler measure problem

Funnily enough, a few days after I wrote the previous post, I was linked to a graph theory paper where one of the first results cited, which was clearly well-known to the authors, is the following remarkable generalization of what I tried to do:

Theorem: The only connected simple graphs with spectral radius less than or equal to are the induced subgraphs of the Dynkin diagrams .

I have to admit, I really didn’t suspect that the classification result I was going after was both so simple and so interesting! Certainly there are heuristic reasons why the above classification makes sense: as I forgot to note in the previous post, there really can’t be too many vertices of degree in a graph with . But I really can’t fathom why spectral radius can be used to define the Dynkin diagrams, considering their relationship to

- simply laced Lie groups,

- binary polyhedral groups and the Platonic solids,

- quiver representations, or

- the octonions (okay, this one is stretching it a little).

Anyone know any good references?

In any case, I’d like to discuss the McKee-Smyth paper because it has some interesting ideas I’d thought about independently.

The spectral radius of a simple graph

I’ve decided not to port over the posts from AoPS. Among other things, I’d prefer to preserve the comments on older posts as they are.

So here’s something I’ve been thinking about. Given a simple connected graph , define to be its largest positive eigenvalue; in other words, if counts the number of walks (equivalently, closed walks) of length on , then