# Is there an analogue of the Lefschetz fixed point theorem for discrete dynamical systems?

## Background/Motivation

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)}$.

## Questions

• 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?

• 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

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.

• 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-Álvarez Jan 5 '10 at 3:12

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