# Cycling through the Zeta Garden: Zeta functions for graphs, cycle index polynomials, and determinants

Zeta functions abound in mathematics. Audrey Terras describes in Zeta Functions and Chaos three zeta functions--the zeta fct. of a projective non-singular algebraic variety; the Artin-Mazur zeta function; and a special Reulle (aka dynamical systems or Smale) zeta function, the Ihara zeta function for a graph $$G$$--all can be expressed in the same basic form:

$$\zeta(u)=\exp\left ( \sum_{m\geq 1} \frac{N_mu^m}{m} \right ).$$

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 edge adjacency matrix. For a vertex adjacency matrix $$A_n$$, also $$N_m = \operatorname{tr}[A_n^m]$$ (e.g., A054878 and A092297). (Edited per draks' comment.)

You can use the general heuristic $$O=KPK^{-1}\Leftrightarrow P=K^{-1}OK$$ to obtain

$$\operatorname{tr}(A)=\ln[\operatorname{det}[\exp(A)]] \Leftrightarrow \operatorname{det}(A)=\exp[\operatorname{tr}[\ln(A)]]$$

and then

$$\operatorname{det}(I-uA_n)=\exp[\operatorname{tr}[\ln(I-uA_n)]]=\exp\left( -\sum_{m\geq 1} \frac{\operatorname{tr}(A_n^m)u^m}{m} \right)$$ $$=\exp\left (-\sum_{m\geq 1} \frac{N_mu^m}{m} \right ),$$

so

$$\zeta(u;G_n)=\frac{1}{\operatorname{det}(I-uA_n)}=\exp\left(\sum_{m\geq 1} \frac{\operatorname{tr}(A_n^m)u^m}{m} \right)=\exp\left(-:\ln(1-ua): \right).$$ where $$a^k=a_k=\operatorname{tr}(A_n^k)$$ for $$k>0$$.

This last expression is the umbral form for the exponential generating function for the cycle index polynomials (OEIS-A036039) for the symmetric group (mod signs).

The Appell sequence in MO-Q111165 incorporating the Riemann zeta function reverses the last relation in some sense:

$$\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$$.

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)]$$

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.

For example, for such a 3x3 matrix the char polynomial is

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

Picture a triangle with the vertices ($$v$$) labelled 1 to 3. Make an orbit/cycle/closed loop, or path, traversing the triangle from $$v_1$$ through $$v_2$$ and $$v_3$$ and then to $$v_1$$. Denote this 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)$$.

Similarly, consider a square with labeled vertices and edges between all pairs of vertices. With cycles/orbits/closed paths of opposing circulation considered distinct cycles, the associated 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)$$.

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?

[Nov. 15, 2013 update: Replacing $$p_1(x)=x+\gamma$$ by $$x$$ and the $$\zeta(n)$$ by $$1$$ gives the characteristic polynomials (mod signs) of the adjacency matrix of the complete n-graph (see A055137).]

• Aren't your "adjacency" matrices just symmetric matrices? In that case, a polynomial can be generated if and only if its roots are all real. – Will Sawin Nov 8 '12 at 2:23
• By "adjacency" matrix I really mean the matrix of indeterminates $a_{ij}$ with $a_{ii}=0$ on the main diagonal. It can be thought of as an "adjacency" matrix from which the char polynoms, in $\sigma$ and the indeterminates, can be formed, which will not have a $\sigma^{n-1}$ term since the trace is zero (neither do the p_n(x)). The question is really whether I can make the transformation as indicated from these indeterminates in the char polynoms to the appropriate $\zeta(j)$ amplitudes to obtain the $p_n(x)$. That might lead to physical/geometric interpretations of these zeta terms. – Tom Copeland Nov 8 '12 at 11:02
• To assign values to the $a_{ij}$ indeterminates before the transformation is made would be like taking the derivative of a function by first assigning a numerical value to the independent variable at some point. The derivative would always return a zero then. However, we are free to fix parameters to determine the function we are interested in, same as making the main diagonal null. – Tom Copeland Nov 8 '12 at 11:24
• Call it a pseudo-adjacency matrix since assigning ones to all the off-diagonal elements would give the adjacency matrix for a complete n-graph and a characteristic polynomial with the coefficients oeis.org/A055137, which appear in the $p_n(x)$ as noted in mathoverflow.net/questions/111165/…. – Tom Copeland Nov 8 '12 at 11:55
• @Draks, see oeis.org/A263916 and oeis.org/A127672 along with the Damianou and Damianou and Evripidou links. – Tom Copeland Nov 10 '15 at 0:49

I think the validity of the algorithm is corroborated by the relation between the trace and determinant of $$m$$-dimensional square matrices $$A$$ inherent in the Cayley-Hamilton theorem applied to the characteristic polynomial of $$A$$ as explained in Wikipedia.

The relation between the $$\det A$$ and $$(\operatorname{tr} A^k)^j$$ for $$k,j is precisely that given by the cycle index partition polynomials, and the cycle mapping is clearly shown by Mark Dominus in the link in OEIS/A036039. Substitute $$\zeta(k)^j$$ for $$(\operatorname{tr}(A^k))^j$$ in the Wikipedia entry, just as above, but how to formally prove the relation between the indices mapping above and the cycle mapping still is a mystery to me.

Note that since these are Appell polynomials,

$$\frac{d}{d\sigma} q_n(\sigma) = n q_{n-1}(\sigma),$$

implying the abscissas of the zeros of $$q_{n-1}(\sigma)$$ are the same as those for the extrema of $$q_n(\sigma)$$. Further, the coefficient of $$\sigma^{n-1}$$ vanishes for each $$q_n(\sigma)$$ since the characteristic polynomial is formed from a matrix with a null diagonal; therefore, the abscissa of each zero is the negative of the sum of those of the remaining zeros. (Here $$q_n(\sigma)=p_n(\sigma - \gamma)$$.)

• Related: arxiv.org/abs/1502.05771 – Tom Copeland Mar 17 '16 at 20:54
• Related: "Combinatorial aspects of elliptic curves" by Musiker arxiv.org/abs/0707.3179 – Tom Copeland Dec 25 '16 at 7:04
• Article in March comment is "Seiberg Duality, Quiver Gauge Theories, and Ihara Zeta Function" by Da Zhou, Yan Xiao, Yang-Hui He – Tom Copeland Dec 25 '16 at 7:06
• See also p. 38 of "Algebraic and geometric methods in enumerative combinatorics" by Ardila (arxiv.org/abs/1409.2562). – Tom Copeland Jan 2 '17 at 22:25
• Related: pg. 44 of arxiv.org/abs/1707.01770 "Notes on the Riemann Hypothesis" by Ricardo Pérez-Marco – Tom Copeland Aug 12 '18 at 20:25
{"ft_lang_label":"__label__en","ft_lang_prob":0.72331893,"math_prob":0.99980646,"size":3945,"snap":"2019-43-2019-47","text_gpt3_token_len":1348,"char_repetition_ratio":0.12052778,"word_repetition_ratio":0.020576132,"special_character_ratio":0.34727502,"punctuation_ratio":0.083333336,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9999926,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-11-14T06:49:23Z\",\"WARC-Record-ID\":\"<urn:uuid:4fcd42f0-5281-4380-af77-9a60482ebb72>\",\"Content-Length\":\"138147\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:4e357df4-b87f-4c1c-895a-413942c6d647>\",\"WARC-Concurrent-To\":\"<urn:uuid:e770adec-ff27-427c-bb29-26a62d907790>\",\"WARC-IP-Address\":\"151.101.193.69\",\"WARC-Target-URI\":\"https://mathoverflow.net/questions/111770/cycling-through-the-zeta-garden-zeta-functions-for-graphs-cycle-index-polynomi\",\"WARC-Payload-Digest\":\"sha1:IMAPKBCICEOYSQEITTXTU2BMNJKZSNSD\",\"WARC-Block-Digest\":\"sha1:WAEUKJNPABJZAOKGCASFPMTJZD4XH2VV\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-47/CC-MAIN-2019-47_segments_1573496668004.65_warc_CC-MAIN-20191114053752-20191114081752-00161.warc.gz\"}"}