Cycling through the Zeta Garden: Zeta functions for graphs, cycle index polynomials, and determinants - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T06:22:05Z http://mathoverflow.net/feeds/question/111770 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/111770/cycling-through-the-zeta-garden-zeta-functions-for-graphs-cycle-index-polynomia Cycling through the Zeta Garden: Zeta functions for graphs, cycle index polynomials, and determinants Tom Copeland 2012-11-08T00:52:10Z 2012-11-08T01:05:26Z <p>Zeta functions abound in mathematics. Audrey Terras describes in <a href="http://math.ucsd.edu/~aterras/msripaper.pdf" rel="nofollow">Zeta Functions and Chaos</a> three zeta functions--the <a href="http://en.wikipedia.org/wiki/Local_zeta_function" rel="nofollow">zeta fct. of a projective non-singular algebraic variety</a>; the <a href="http://en.wikipedia.org/wiki/Artin-Mazur_zeta_function" rel="nofollow">Artin-Mazur zeta function</a>; and a special <a href="http://en.wikipedia.org/wiki/Ruelle_zeta_function" rel="nofollow">Reulle (aka dynamical systems or Smale) zeta function</a>, the <a href="http://en.wikipedia.org/wiki/Ihara_zeta_function" rel="nofollow">Ihara zeta function</a> for a graph $G$--all can be expressed in the same basic form:</p> <p>$$\zeta(u)=\exp\left ( \sum_{m\geq 1} \frac{N_mu^m}{m} \right ).$$</p> <p>For graph zeta functions $\zeta(u,G_n)$ typically $N_m$ is the number of closed walks of $m$ steps (with some qualifications) on the graph $G$ with $n$ vertices and is related to the trace of the power of an <a href="http://en.wikipedia.org/wiki/Adjacency_matrix" rel="nofollow">adjacency matrix</a> $A_n$, i.e., $N_m = tr[A_n^m]$ (e.g., <a href="https://oeis.org/A054878" rel="nofollow">A054878</a> and <a href="https://oeis.org/A092297" rel="nofollow">A092297</a>).</p> <p>In this case, you can use the general heuristic $O=KPK^{-1}\Leftrightarrow P=K^{-1}OK$ to obtain </p> <p>$$tr(A)=\ln[det[\exp(A)]] \Leftrightarrow det(A)=\exp[tr[\ln(A)]]$$</p> <p>and then</p> <p>$$det(I-uA_n)=\exp[tr[ln(I-uA_n)]]=\exp\left( -\sum_{m\geq 1} \frac{tr(A_n^m)u^m}{m} \right)$$ $$=\exp\left (-\sum_{m\geq 1} \frac{N_mu^m}{m} \right ),$$</p> <p>so </p> <p>$$\zeta(u;G_n)=\frac{1}{det(I-uA_n)}=\exp\left(\sum_{m\geq 1} \frac{tr(A_n^m)u^m}{m} \right)=\exp\left(-:\ln(1-ua): \right).$$ where $a^k=a_k=tr(A_n^k)$ for $k>0$.</p> <p>This last expression is the umbral form for the exponential generating function for the <a href="http://en.wikipedia.org/wiki/Cycle_index" rel="nofollow">cycle index polynomials</a> (<a href="https://oeis.org/A036039" rel="nofollow">OEIS-A036039</a>) for the symmetric group (mod signs).</p> <p>The Appell sequence in <a href="http://mathoverflow.net/questions/111165/riemann-zeta-function-at-positive-integers-and-an-appell-sequence-of-polynomials" rel="nofollow">MO-Q111165</a> incorporating the Riemann zeta function reverses the last relation in some sense:</p> <p>$$\exp\left (-\beta p_{.}(z)\right )=\exp\left [-(z+\gamma)\beta -\sum_{k=2}^{\infty } \frac{\zeta (k)\beta ^k}{k} \right ]=\exp\left [ :ln(1-b\beta ) :\right ]$$ where $b^1=b_{1}=(z+\gamma)$ and $b^k=b_k=\zeta(k)$ for $k>1$.</p> <p>For easy reference: $$p_{0}(x)=1$$ $$p_{1}(x)=x+\gamma$$ $$p_2(x)=(x+\gamma)^2-\zeta(2)$$ $$p_3(x)=(x+\gamma)^3-3\zeta(2)(x+\gamma)+2\zeta(3)$$ $$p_4(x)=(x+\gamma)^4-6\zeta(2)(x+\gamma)^2+8\zeta(3)(x+\gamma)+3[\zeta^2(2)-2\zeta(4)]$$</p> <p><strong>These polynomials are the first few cycle index polynomials for the symmetric group. I'd like to relate each $p_n(x)$ to the characteristic polynomial of a matrix with a null main diagonal.</strong></p> <p>For example, for such a 3x3 matrix the char polynomial is</p> <p>$$\sigma^3-(a_{12}a_{21}+a_{13}a_{31}+a_{23}a_{32})\sigma+(a_{12}a_{23}a_{31}+a_{13}a_{32}a_{21}).$$</p> <p>Picture a triangle with the vertices (v) labelled 1 to 3. Make a closed loop or path traversing the triangle from v_1 through v_2 and v_3 and then to v_1. Denote this closed transition/loop/path of three steps and length three by $a_{12}a_{23}a_{31}$ and assign it the "moment/transition amplitude" of $\zeta(3)$. Likewise, assign the amplitude $\zeta(2)$ to paths of two steps and length one $a_{12}a_{21}$, an amplitude of $\sigma=x+\gamma$ to a self- or null-loop, and so on. This generates $p_3(x)$. </p> <p>The analogous 4x4 determinant generates six paths each with four steps and length four, e.g., $a_{12}a_{24}a_{43}a_{31}$, that can be assigned an amplitude of $\zeta(4)$ each and three sets of two paths of two steps and length one, e.g., $a_{13}a_{31}a_{24}a_{42}$, that can be assigned an amplitude of $\zeta^{2}(2)$. The algorithm can be continued to the other terms to generate $p_4(x)$. </p> <p><strong>How to prove that the algorithm will work for all $p_n(x)$, i.e., that each $p_n(x)$ can be generated in the above manner from an $n$ by $n$ "adjacency" matrix?</strong></p>