Is there an analogue of the Lefschetz fixed point theorem for discrete dynamical systems? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T19:14:30Z http://mathoverflow.net/feeds/question/10764 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/10764/is-there-an-analogue-of-the-lefschetz-fixed-point-theorem-for-discrete-dynamical Is there an analogue of the Lefschetz fixed point theorem for discrete dynamical systems? Qiaochu Yuan 2010-01-05T01:38:23Z 2010-01-08T05:19:00Z <h2>Background/Motivation</h2> <p>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 <strong>dynamical (Artin-Mazur) zeta function</strong> $\zeta_f$ is given by</p> <p>$\displaystyle \zeta_f(t) = \exp \left( \sum_{n \ge 1} \frac{\text{Fix } f^n}{n} t^n \right)$.</p> <p>The coefficients of $\zeta_f(t)$ have a <a href="http://qchu.wordpress.com/2009/11/04/newtons-sums-necklace-congruences-and-zeta-functions-ii/" rel="nofollow">nice combinatorial interpretation</a> 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 <strong>local zeta function</strong>, since $\text{Fix } f^n$ is precisely the number of points of the variety over $\mathbb{F}_{p^n}$.</p> <p>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 <a href="http://en.wikipedia.org/wiki/Fixed_point_index" rel="nofollow">index</a> 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 <strong>Lefschetz zeta function</strong> by</p> <p>$\displaystyle \zeta_f(t) = \exp \left( \sum_{n \ge 1} \frac{L(f^n)}{n} t^n \right)$.</p> <p>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 <a href="http://en.wikipedia.org/wiki/Weil_conjectures" rel="nofollow">Weil conjectures</a>. This was eventually done, and is known as <a href="http://en.wikipedia.org/wiki/%C3%89tale_cohomology" rel="nofollow">etale cohomology</a>.</p> <p>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</p> <p>$\displaystyle \zeta_f(t) = \frac{1}{\det(\mathbf{I} - \mathbf{A}t)}$.</p> <p>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!</p> <p><strong>Edit, 1/8/10:</strong> 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</p> <p>$\displaystyle \zeta_f(t) = \frac{\det(\mathbf{I} - \mathbf{B}t)}{\det(\mathbf{I} - \mathbf{A}t)}$.</p> <h2>Questions</h2> <ul> <li><p>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)$?</p></li> <li><p>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?</p></li> </ul> http://mathoverflow.net/questions/10764/is-there-an-analogue-of-the-lefschetz-fixed-point-theorem-for-discrete-dynamical/10765#10765 Answer by Ilya Nikokoshev for Is there an analogue of the Lefschetz fixed point theorem for discrete dynamical systems? Ilya Nikokoshev 2010-01-05T01:58:23Z 2010-01-05T02:24:39Z <p>I think this is how you can construct the required homology theory:</p> <ul> <li>$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)</li> <li>boundary comes from the natural boundary operator on $[n]$ which leaves exactly one point and takes the alternating sum</li> </ul> <p>With these definitions, you have $d^2 = 0$ as usual.</p> <p>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. <strong>Update:</strong> we have to write definition of a chain more carefully, since it's not clear that this chain is closed.</p> <p>As for Lefschetz, it holds for the computation since your map $f$ takes a vector of points $P$ into $\mathbf AP$.</p> <p><hr /></p> <p>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$.</p> <p>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.</p> http://mathoverflow.net/questions/10764/is-there-an-analogue-of-the-lefschetz-fixed-point-theorem-for-discrete-dynamical/10792#10792 Answer by eric for Is there an analogue of the Lefschetz fixed point theorem for discrete dynamical systems? eric 2010-01-05T07:01:51Z 2010-01-05T07:01:51Z <p>I aint so sure of why you only get aperiodic walks -- not necessarily true.</p>