« The cyclotomic identity and Lyndon words
I don’t trust uncountable sets »

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

November 4, 2009

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

\displaystyle \zeta_X(t) = \exp \sum_{n \ge 1} (\text{Fix } f^n) \frac{x^n}{n}.

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 \zeta_X(t) is an exponential generating function, i.e. the coefficient of \frac{x^n}{n!} is an integer. What we don’t know is whether this coefficient is always divisible by n!, i.e. whether \zeta_X(t) 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 X is in a finite orbit, i.e. for all x \in X there exists n such that f^n(x) = x. The period of x is defined to be the smallest such n and will be denoted |x|. The orbit of x is the set P_x = \{ x, f(x), ... f^{|x|-1}(x) \} and we will write |P_x| = |x| for the size of an orbit.

Theorem (Euler product): \displaystyle \zeta_X(t) = \prod_P \frac{1}{1 - t^{|P|}}

where the product runs over all orbits of X. Equivalently, the coefficient of t^n in \zeta_X(t) counts the number of multisets of orbits of X with n 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 f_n = \text{Fix } f^n, then we know that

\displaystyle \exp \left( \sum_{n \ge 1} \frac{f_n}{n} t^n \right) = \sum_{n \ge 0}\left( \sum_{\pi \in S_n} f_1^{c_1} f_2^{c_2} ... \right) \frac{t^n}{n!}

where c_i is the number of cycles of length i in \pi. In words, the coefficient of \frac{t^n}{n!} is the number of ways to assign to each cycle of length k in a permutation of n elements a sequence of points x, f(x), ... f^{k-1}(x) such that f^k(x) = x. This is because a point x of period dividing k uniquely determines its cycle.

It follows that any such assignment is uniquely determined by its points, which are a collection of n not necessarily distinct points of X each given a unique label from \{ 1, 2, ... n \}. Now here’s the important step: S_n acts freely on labels, so in fact \displaystyle \frac{1}{n!} \sum_{\pi \in S_n} f_1^{c_1} f_2^{c_2} ... is an integer which counts the number of multisets of n points of X which are closed under the action of f. 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 n total points as desired.

Note how nicely this generalizes the result from the previous post. If X = \overline{ \mathbb{F}_q } then a multiset of points closed under conjugation is precisely a monic polynomial with coefficients in \mathbb{F}_q, which is in turn precisely the generator of a maximal ideal of \mathbb{F}_q[x]. More generally, if X is a variety over \mathbb{F}_q 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 X is the set of aperiodic closed walks with a distinguished starting point on a finite graph G with adjacency matrix \mathbf{A} and f moves the starting point. Then \text{Fix } f^n counts the number of (not necessarily aperiodic) closed walks of length n, hence \text{Fix } f^n = \text{tr } \mathbf{A}^n. Note that these are the power symmetric functions of the eigenvalues of \mathbf{A}. 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 h_n = \text{tr Sym}^n \mathbf{A}, the trace of the n^{th} symmetric power of \mathbf{A}. It can be described combinatorially as follows: if G has vertices v_1, ... v_k, construct a new graph \text{Sym}^n G with vertices the set of all multisets of n vertices of G, where the edges between two multisets are precisely the n-tuples of edges of G sending one multiset to another. (This is precisely the description of the action of \mathbf{A} on the symmetric powers of the free vector space V spanned by the vertices.) This gives the complete homogeneous symmetric functions as polynomial functions in terms of the entries of \mathbf{A}.

It then follows that h_n is the number of closed walks of length 1 on \text{Sym}^n G, i.e. the number of n-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 X closed under the action of f. Combined with what we know about the zeta function, we have proven the following using only combinatorics.

Proposition: \displaystyle \sum_{n \ge 0}\left( \text{tr Sym}^n \mathbf{A} \right) t^n = \exp \sum_{n \ge 1} \left( \text{tr } \mathbf{A}^n \right) \frac{t^n}{n}.

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 v. This vertex is contained in c copies of some aperiodic closed walk w, and it determines an arbitrary closed walk as follows: trace out the copies of w starting from v which are at least as large as the copy in which v 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

p_k + h_1 p_{k-1} + ... = kh_k,

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

\displaystyle \frac{1}{\det (\mathbf{I} - \mathbf{A} t)} = \exp \sum_{n \ge 1} \left( \text{tr } \mathbf{A}^n \right) \frac{t^n}{n}.

Unfortunately, I don’t quite see how to prove

\displaystyle (*) \frac{1}{\det (\mathbf{I} - \mathbf{A} t)} = \sum_{n \ge 0} \left( \text{tr Sym}^n \mathbf{A} \right) t^n

with no further assumptions on G, 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 (\mathbf{I} - \mathbf{A} t)^{-1}, which counts all walks on G, 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 G describe tilings with c_i tiles of length i, so that \mathbf{A} is the companion matrix of t^n - c_1 t^{n-1} - .... Then \frac{1}{\det(\mathbf{I} - \mathbf{A}t)} = \frac{1}{1 - c_1 t - c_2 t^2 - ...} describes the number of tilings of length n. 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 X here is the set of aperiodic tilings with a distinguished starting point, h_n counts the multisets of Lyndon words of total length n, and these two counts agree. It follows that

\displaystyle \frac{1}{1 - c_1 t - c_2 t^2 - ...} = \sum_{n \ge 0} \left( \text{tr Sym}^n \mathbf{A} \right) t^n.

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

h_n = c_1 h_{n-1} + c_2 h_{n-2} + ...

which is precisely the identity h_n e_0 - h_{n-1} e_1 \pm ... = 0 in disguise. Once more we can now use the trick of lifting the c_i to formal variables and setting them to be the elementary symmetric functions of another set of formal variables.

This entry was posted on November 4, 2009 at 6:55 am and is filed under algebraic combinatorics.

Tags: , , , , ,

Leave a Reply