I’ve been thinking a bit about applying Tom Leinster’s methodology for Euler characteristics to certain kinds of infinite categories, namely categories freely generated by directed graphs with cycles in them. The problem is that the zeta operator is defined in terms of the number of morphisms (here, paths) between objects, which in this case is infinite.
The obvious way to approach this is to downgrade the weight of longer paths by some factor for paths of length , do our totalling, inversion, summing, etc, and then let at the end, hoping to get out something finite. The last time I tried this, all I proved was that, yep, the zeta operator sure does have a lot of infinities in it. But this time round I seem to have done a bit better.
Let’s try a simple cyclical graph with two vertices and two edges between them, one pointing each way:
The paths going from the lefthand vertex to itself are of lengths , , , etc, so lets total them up, but multiplying each by where is its length, getting .
This is the same for the paths from the righthand vertex to itself. Finally, from the lefthand vertex to the righthand vertex, or vice versa, we have the same, but with one extra, initial edge.
So let’s say our zeta operator is
The determinant is .
So the inverse is . Letting and summing all matrix entries (or vice versa!) we get . Which is correct for the Euler characteristic of the graph. So far, so good …
Now we try adding an extra arrow from left to right:
This time, there are two ways to get from left to right, so the numbers of paths are of length , of length , of length , of length and generally of length . So totalling, we get .
So we get a zeta operator
We can actually let already to get and invert to give us
Totalling entries gives an Euler characteristic of , which is correct for the graph.
In the same way, if we have some general number of arrows going to the right, we can see we get a cycle factor of and a zeta operator of
, with determinant and inverse
.
Letting , we get
.
Totalling, we get . Which, again, is correct for the graph.
If we also have some number arrows going to the left, then each zigzag back and forth multiplies the number of paths by , giving a cycle factor of , a zeta operator
with inverse
and Euler characteristic , which is again right for the graph.
Now it should be clear that the inverse matrix is still equal to the identity minus the adjacency matrix (possibly mutiplied by a factor ), . And it is easy to see why: inverting this gives which gives the summed weighting over all paths, or in other words the deformed zeta operator.
Now let’s just look at a couple of examples with three vertices.
First, a bunch of cycles round the graph in the same direction: edges from ; edges from ; and edges from .
The cycle gives us a term . For each vertex, we have a term for the path (and its catenations with all cycles), a term in for the path to the next vertex (and its catenations with all cycles) and a term in for the path to the next vertex but one (and its catenations with all cycles).
Thus our zeta operator is
The determinant is and laboriously inverting gives us
This is simply (where the bold is the adjacency matrix as usual).
One final example: in the above, add arrows going back from to . I’m afraid I’m too lazy and timid to work out the zeta operator from scratch: instead I’ll invert . Thus we take
The determinant is . Inverting gives us
.
OK, that’s enough of that—I think we can see the pattern clearly enough.
Now let’s take another look at that last determinant.
Notice the clever way that it counts the number of 2- and 3- cycles and assigns the results as coefficients of and . After calculating a lot of determinants, I’ve come to the conclusion that this is generally true, except that it’s a bit more complicated. What’s really going on is that the determinant is counting allowed permutations of the vertices under the action of the graph edges. An allowed permutation of vertices is constructed thus: for each vertex, pick either the identity, or one of the (directed) edges which has its source at the vertex. Then send that vertex to either itself (if we chose the identity) or to the destination vertex of the edge. Each allowed permutation has a cycle decomposition; we add up the lengths of the cycles in the decomposition (counting the identity as 0
length), and that gives the power of to which the permutation contributes.
Obviously, primitive graph cycles which share vertices can’t act simultaneously, but completely disjoint cycles can, so, e.g. if we have two disjoint 3-cycles in the graph, we will get terms , the two terms arriving when we choose the 3-cycle edges on one cycle and the identities on the other, and the term resulting from running both 3-cycles simultaneously. In this case, the polynomial will always factorise, simply because the permutation group itself factorises (… I think).
The reciprocal of the determinant is the determinant of the zeta operator and is a sort of zeta function, or at least a zeta functioney sort of thingy, ish. It’s quite similar to the Ihara zeta function, but there are some differences: the Ihara zeta function is applied to undirected graphs, so we need to remember we are always counting cycles in both directions; and the Ihara zeta function has a quadratic term in its argument (my ) which I think is intended to discount backtracking 2-cycles, and has the interesting effect of (almost) turning it into the reciprocal of the determinant of the Laplacian. (I think this
technique for knocking out certain 2-cycles can be adapted to eliminate the effect of longer cycles too—e.g. if we wanted to take into account the homotopic contractibility of some polygonal 2-cell that we had inserted into the graph; but I haven’t investigated that in detail.) There may be other differences, because I haven’t looked at the Ihara zeta function as hard as I would have liked to do. Actually, I’m sadly quite confused about it.
I also wanted to try and use this approach on the Euler characteristic of the automorphism groups of individual vertices. Let’s try a cyclic group of order . We start by choosing a graph with one vertex and one (directed) edge. This gives, as its graph category, the free category on one generator, with its deformed zeta operator (which is a number, since we only have one vertex) being equal to . This gives an Euler characteristic of as expected. Now we quotient out by the subcategory generated by the th power of the edge, whose zeta operator is presumably . So dividing the first by the
second, we get a zeta operator for the cyclic group of . Obviously the inverse of this zeta operator is just the reciprocal of this expression, and clearly as we get .
So far, so good!
We can extend this to other finite abelian groups easily enough. We take the graph with one vertex and edges. Forcing everything to be abelian, the universal covering graph of this is the -dimensional lattice over and we get a zeta operator of . We can then quotient out each dimension separately, getting , ending up with a product of -deformed integers which tends to the order of the group as . Hence the Euler characteristic comes out as the reciprocal of the group size. And we get a zeta function for the group into the bargain. (Although I’m tempted to assign a different variable for each generator … but let’s not go there … )
OK so far …
For a non-abelian group , although it’s clear in principle what to do, the graph approach doesn’t really make things clearer than the algebraic approach. For a presentation with generators, we have a graph with vertex and edges. The universal covering graph is an infinite -ary tree. The zeta operator will be . It’s when we try to take a quotient that things get a bit hairy. In principal, it’s obvious what we need to do: we take each element of the group, express it as a product of generators, write down a term , add them up, take the reciprocal, and get something that tends to as . In practice, we might as well just miss out the intermediate steps and take the Baez-Dolan approach from the start. On the other hand, in even more principled principle, I find myself wanting to pick different variables for each generator, stop them from commuting, and in fact actually take them from some
representation of the group, and, umm, … do something intelligent with them …
As usual, I’m sure this has all been worked over before now by somebody other than me, somewhere; but I’m learning new stuff.
Re: This Week’s Finds in Mathematical Physics (Week 244)
BBC Radio 4’s series “In Our Time” had an interesting program about Indian Mathematics a few weeks ago, which you can still listen to from the BBC website.