Newton’s sums, necklace congruences, and zeta functions II

In a previous post I gave essentially the following definition: given a discrete dynamical system, i.e. a space and a function , and under the assumption that has a finite number of fixed points for all , we define the dynamical zeta function to be the formal power series

.

What I didn’t do was motivate this definition, mostly because I hadn’t really worked out the motivation myself. Now that we have an important special case worked out, we can discuss the general case, which will give a purely combinatorial proof of the second half of the Newton-Girard identities.

The Euler product and the exponential formula

From the above definition we know that is an exponential generating function, i.e. the coefficient of is an integer. What we don’t know is whether this coefficient is always divisible by , i.e. whether is also an ordinary generating function. In fact, this is always true.

Because the zeta function ignores infinite orbits, we can suppose that every element of is in a finite orbit, i.e. for all there exists such that . The period of is defined to be the smallest such and will be denoted . The orbit of is the set and we will write for the size of an orbit.

Theorem (Euler product):

where the product runs over all orbits of . Equivalently, the coefficient of in counts the number of multisets of orbits of with total points.

As in the previous post, one can give a proof using Mobius inversion, but this is unenlightening. A more combinatorial approach is through the exponential formula, or at least through what we know about the cycle index polynomials of the symmetric groups. If we write , then we know that

where is the number of cycles of length in . In words, the coefficient of is the number of ways to assign to each cycle of length in a permutation of elements a sequence of points such that . This is because a point of period dividing uniquely determines its cycle.

It follows that any such assignment is uniquely determined by its points, which are a collection of not necessarily distinct points of each given a unique label from . Now here’s the important step: acts freely on labels, so in fact is an integer which counts the number of multisets of points of which are closed under the action of . We may group each point with its orbit (which will in general not be the same as its cycle), and then we have a multiset of orbits with total points as desired.

Note how nicely this generalizes the result from the previous post. If then a multiset of points closed under conjugation is precisely a monic polynomial with coefficients in , which is in turn precisely the generator of a maximal ideal of . More generally, if is a variety over then a multiset of points closed under conjugation is what is known as an effective divisor in algebraic geometry, and they form a free abelian monoid generated by the orbits. The Euler product is then the statement of “unique factorization” in this monoid.

Note also that this factorization is equivalent to the necklace congruences.

Complete homogeneous symmetric functions

The case we are interested in now is the case that is the set of aperiodic closed walks with a distinguished starting point on a finite graph with adjacency matrix and moves the starting point. Then counts the number of (not necessarily aperiodic) closed walks of length , hence . Note that these are the power symmetric functions of the eigenvalues of . Can we write down a similar expression describing the complete homogeneous symmetric functions in terms of combinatorial data?

In fact, we can. One way to define the complete homogeneous symmetric functions of the eigenvalues of a graph is as , the trace of the symmetric power of . It can be described combinatorially as follows: if has vertices , construct a new graph with vertices the set of all multisets of vertices of , where the edges between two multisets are precisely the -tuples of edges of sending one multiset to another. (This is precisely the description of the action of on the symmetric powers of the free vector space spanned by the vertices.) This gives the complete homogeneous symmetric functions as polynomial functions in terms of the entries of .

It then follows that is the number of closed walks of length on , i.e. the number of -tuples of edges that fix a multiset of vertices. But now grouping vertices by connecting the edges, we get a decomposition of the vertex set into a multiset of aperiodic closed walks. (That they are aperiodic is a consequence of the fact that different copies of the same vertex are treated as the same.) And these are precisely the multisets of points of closed under the action of . Combined with what we know about the zeta function, we have proven the following using only combinatorics.

Proposition: .

Taking derivatives now gives the second Newton-Girard identity, but we know from experience that this is equivalent to a pointing argument, which is as follows: in any multiset of aperiodic closed walks, fix a total order on the different copies of the same closed walk and point to a vertex . This vertex is contained in copies of some aperiodic closed walk , and it determines an arbitrary closed walk as follows: trace out the copies of starting from which are at least as large as the copy in which sits. Removing this closed walk gives an arbitrary multiset of aperiodic closed walks, and every multiset of aperiodic closed walks with a distinguished vertex arises uniquely in this way. It follows that

,

which is the second Newton-Girard identity. Note how this proof is nicely dual to the pointing proof of the first Newton-Girard identity.

The last step

The secret goal of this entire discussion was to push through a combinatorial proof of the identity

.

Unfortunately, I don’t quite see how to prove

with no further assumptions on , although it’s obvious by series manipulation. Here’s what I do know:

1. Foata gives a combinatorial proof in which (*) is done using the MacMahon Master Theorem. Unfortunately, I have yet to see a clear statement of this theorem, or at least one phrased in the language of walks on graphs.
2. On MathOverflow I asked a more general question about combinatorial interpretations of the symmetric functions of eigenvalues of a matrix. I was directed to the thesis of Andrius Kulikauskas, and this thesis agrees that (*) is very closely related to the MacMahon Master Theorem. Unfortunately, I have not yet had a chance to work through this paper, which is a shame since it’s exactly what I’ve been looking for; Lyndon words seem to be his primary tool as well.
3. One way to think about (*) is as the statement that in the determinant of , which counts all walks on , the cancellation of the terms is such that what’s left precisely describes multisets of aperiodic closed walks. Joel Lewis and I spent some time this summer trying to prove this using the Gessel-Viennot lemma, but to no avail. It’s possible a more general application of the involution principle or inclusion-exclusion might succeed.

In the style of the previous post, here’s a proof using tilings. Once more let describe tilings with tiles of length , so that is the companion matrix of . Then describes the number of tilings of length . We can think of tilings as words where letters can take up more than one position. With that philosophy, totally order the tiles. This defines the Lyndon words on tiles, and tilings then factor uniquely into a nondecreasing product of Lyndon words. But since here is the set of aperiodic tilings with a distinguished starting point, counts the multisets of Lyndon words of total length , and these two counts agree. It follows that

.

In particular, any tiling has a unique last tile, so we have shown that

which is precisely the identity in disguise. Once more we can now use the trick of lifting the to formal variables and setting them to be the elementary symmetric functions of another set of formal variables.