Take the 2-minute tour ×


Let $(X, f)$ be a discrete dynamical system. For now, $X$ is just a set and $f$ is just a function $f : X \to X$. Suppose that $f^n$ has a finite number of fixed points for every $n$. Then the dynamical (Artin-Mazur) zeta function $\zeta_f$ is given by

$\displaystyle \zeta_f(t) = \exp \left( \sum_{n \ge 1} \frac{\text{Fix } f^n}{n} t^n \right)$.

The coefficients of $\zeta_f(t)$ have a nice combinatorial interpretation that seems to have homological significance. A particularly famous case of this construction is that $X$ is the set of points of a variety over $\overline{ \mathbb{F}_p }$ and $f$ is the Frobenius map; then $\zeta_f$ is a local zeta function, since $\text{Fix } f^n$ is precisely the number of points of the variety over $\mathbb{F}_{p^n}$.

Now give $X$ the additional structure of a compact triangulable space and let $f$ be continuous. Again suppose that $f^n$ has a finite number of fixed points for every $n$ and let $i(f, x)$ denote the index of a fixed point $x$, and let $L(f)$ be the sum of the indices $i(f, x)$ over all fixed points of $x$. Thus $L(f)$ generalizes the number $\text{Fix } f$ to the case that the indices are not all equal to $1$. Similarly one defines the Lefschetz zeta function by

$\displaystyle \zeta_f(t) = \exp \left( \sum_{n \ge 1} \frac{L(f^n)}{n} t^n \right)$.

The Lefschetz fixed point theorem is then equivalent to the statement that $\zeta_f$ is equal to the alternating product of the characteristic polynomial of the induced action of $f$ on the singular homology groups $H_k(X, \mathbb{Q})$; in particular, $\zeta_f$ is rational because there are finitely many such groups. Weil famously suggested that if one could define an analogue of singular homology for varieties over finite fields, an analogue of the Lefschetz fixed point theorem would prove the Weil conjectures. This was eventually done, and is known as etale cohomology.

However, I'm interested in a simpler dynamical system than a variety over a finite field. Let $G$ be a finite (directed, possibly with loops) graph, let $X(G)$ be the set of aperiodic closed walks on $G$ with a distinguished vertex, and let $f : X(G) \to X(G)$ be the function which sends the distinguished vertex of an aperiodic closed walk to the next vertex in the walk. (An aperiodic closed walk is analogous to a point together with all of its Galois conjugates, and $f$ is conjugation.) Then $\text{Fix } f^n$ is precisely the number of closed walks of length $n$ on $G$. A basic result in algebraic combinatorics then tells us that $\text{Fix } f^n = \text{tr } \mathbf{A}^n$, where $\mathbf{A}$ is the adjacency matrix of $G$, and this is equivalent to the statement that

$\displaystyle \zeta_f(t) = \frac{1}{\det(\mathbf{I} - \mathbf{A}t)}$.

What this suggests to me is that there is an analogue of the Lefschetz zeta function at work and that it is telling me that $X(G)$ has one nontrivial homology group on which $f$ acts as $\mathbf{A}$, but I don't know if this is a reasonable interpretation. Hence my questions!

Edit, 1/8/10: Let me give an example where I can introduce another "homology group." Let $H$ be a proper subgraph of $G$, and let $X(G, H)$ denote the set of aperiodic closed walks on $G$ with a distinguished vertex and with the property that at least one edge or vertex of the closed walk is not in $H$; $f$ is the same as above. If $\mathbf{B}$ denotes the adjacency matrix of $H$, it then follows that $\text{Fix } f^n = \text{tr } \left( \mathbf{A}^n - \mathbf{B}^n \right)$, hence

$\displaystyle \zeta_f(t) = \frac{\det(\mathbf{I} - \mathbf{B}t)}{\det(\mathbf{I} - \mathbf{A}t)}$.


  • What is a sensible definition of the (say, integral) homology of a discrete dynamical system without any further structure? What conditions on $X$ are necessary to ensure that there are only finitely many homology groups, and do they hold for $X(G)$ and/or $X(G, H)$?

  • Under what conditions does an analogue of the Lefschetz fixed point theorem hold for this homology theory, and can it be made to correctly reproduce the $X(G)$ and $X(G, H)$ computations above?

share|improve this question
I was recently reading an article by J.W. Hoffman, "Remarks on the zeta function of a graph", and I thought you might find it interesting. –  Gjergji Zaimi Jul 18 '10 at 3:50
It sounds similar to something my colleague, Ian Putnam, has worked on (math.uvic.ca/faculty/putnam/r/0804_main.pdf) –  Anthony Quas Mar 24 '11 at 15:40

2 Answers 2

I think this is how you can construct the required homology theory:

  • $n$-chains = maps of chain graphs $[n] = 0 \to 1 \to \dots\to n$ into your graph (where, perhaps, one edge of $[n]$ maps to many edges of your graph)
  • boundary comes from the natural boundary operator on $[n]$ which leaves exactly one point and takes the alternating sum

With these definitions, you have $d^2 = 0$ as usual.

Example computation for a circle of $n$ points: chain that wraps the circle is not exact, since the wrapping number of $d$ of any chain is 0. Update: we have to write definition of a chain more carefully, since it's not clear that this chain is closed.

As for Lefschetz, it holds for the computation since your map $f$ takes a vector of points $P$ into $\mathbf AP$.

It looks like you're constructing a nerve of the category of (vertices, paths); the geometric realization $\mathcal X$ of that nerve should have cohomology that indeed describe your dynamic system. Your incidence matrix naturally defines a correspondence $f\subset\mathcal X\times \mathcal X$ with fixed points of $f^n$ being exactly cycles of length $n$.

I think one can see that this $f$ acts as identity on all homology, so it seems that your fixed points formula has the required form.

share|improve this answer
I don't see how the boundary operator as you defined it takes n-chains to (n-1)-chains. Could you be more explicit? –  Qiaochu Yuan Jan 5 '10 at 2:51
It takes the chain 0-1-2 to an alternating sum of 1-2, 0-2 and 0-1. I'm not entirely sure about the construction though. Also, you need to allow points to map not only to the vertices, but also to the edges, I think. –  Ilya Nikokoshev Jan 5 '10 at 2:59
The nerve construction should work though in any case, it's a standard one. –  Ilya Nikokoshev Jan 5 '10 at 3:00
You can do this construction for the category generated by the graph (when you say that the boundary "leaves exactly one point [out]" you really want to say "it replaces a pair of adjacent arrows by their composition") –  Mariano Suárez-Alvarez Jan 5 '10 at 3:12

I aint so sure of why you only get aperiodic walks -- not necessarily true.

share|improve this answer
please link this to overall comments. –  eric Jan 5 '10 at 7:02
Sorry, I'm not sure what you mean. –  Qiaochu Yuan Jan 5 '10 at 14:31
I am not proposing an answer, so I'd be grateful if someone could link this to the question. My concern is based on your assumption of aperiodic "closed" walks. I am not sure what "closed" means. Maybe it refers to cycles ? What condition makes sure that these are aperiodic walks ? And how do YOU define aperiodic. –  eric Jan 5 '10 at 19:13
A walk is a sequence of vertices and edges such that the edges connect adjacent vertices. I make no assumption as to the repetition of edges or vertices. A closed walk is a walk whose first and last vertex coincide, and an aperiodic closed walk whose sequence of vertices-and-edges together is not periodic. For example v_1-e_1-v_2-e_2-v_1-e_1-v_2-e_2-v_1 is closed but periodic. –  Qiaochu Yuan Jan 5 '10 at 22:38

Your Answer


