What is the Möbius analoge for Ihara's $\zeta$ function?

Solution 1:

The essence of this answer is contained in the answer of reuns, but that answer, unfortunately, also contains some incorrect claims regarding the nature and finitude of primes in graphs.

The answers at the link in your original question are also relevant: a Möbius function can be defined wherever you have a partially ordered set. In particular, the number theory Möbius function is closely related to the Möbius function of the partial ordering of finite submultisets of a multiset, ordered by inclusion, and so is the Möbius function for the Ihara zeta function.

In the number theory context, as a consequence of unique factorization, any positive integer $n$ may be identified with the multiset of its prime factors. So $1$ is identified with $\{\}$, $2$ with $\{2\}$, $4$ with $\{2,2\}$, $12$ with $\{2,2,3\}$, and so on. The number theory Möbius function, regarded as a function of a multiset $M$ of primes, is then $$ \mu(M)=\begin{cases}0 & \text{if $M$ contains any element more than once,}\\ 1 & \text{if $M$ contains an even number of elements, all distinct,}\\ -1 & \text{if $M$ contains an odd number of elements, all distinct.} \end{cases} $$

One can do exactly the same thing in the graph context. The graph theory analogs of the integers $n$ are the multisets, $M$ whose elements are equivalence classes of prime circuits. From this it follows that $$ \sum_M u^{L(M)}\mu(M)=\prod_p \left(1-u^{L(p)}\right)=\frac{1}{\zeta_G(u)}, $$ where $L(M)$ is the sum of the lengths of the elements of $M$. Note that if the graph has at least two circuits, then it has infinitely many prime circuits. The elements of $M$ need not intersect, so it cannot be assumed that they can be concatenated to form a single circuit. Furthermore, the elements of $M$ are equivalence classes of prime circuits, so there would be no uniquely specified concatenation point even when they do intersect. This means that the multisets $M$ cannot be straightforwardly identified with something so simple as circuits in the graph.

To answer your question about what happens when a vertex occurs more than once, it is perfectly possible to have $\mu(M)\ne0$ in this situation: different primes may contain the same vertex. Different primes may even contain all the same vertices. As a simple example, if $p$ is a prime circuit, then traversing the edges of $p$ in the opposite order gives a different prime circuit.

Added in response to comment about finitude of number of terms in $1/\zeta_G(u)$:
From the determinant formulas of Ihara, Sunada, Hashimoto, and Bass it is evident that $1/\zeta_G(u)$ is indeed a polynomial in $u$, but that doesn't mean that the sum $\sum_Mu^{L(M)}\mu(M)$ has only finitely many nonzero terms. It just means that there are cancellations. Of course, it is the case that there are plenty of $M$ for which $\mu(M)=0$, namely those $M$ that contain some prime more than once. But there are also infinitely many $M$ for which $\mu(M)=\pm1$. Similarly, in the product form $$ \frac{1}{\zeta_G(u)}=\prod_p \left(1-u^{L(p)}\right) $$ the product does not contain only finitely many factors.

Revisiting an example from an earlier comment thread, consider the $4$-regular graph with one vertex and two loops. This graph has adjacency matrix $A_G=\begin{bmatrix}4\end{bmatrix}$. From the Ihara-Sunada-Bass determinant formula, $$ \frac{1}{\zeta_G(u)}=(1-u^2)^{r_G-1}\det(I-uA_G+u^2Q_G),\tag{1} $$ where $r_G$ is the circuit rank of the graph and $Q_G$ is the diagonal matrix whose $(i,i)$ element is $\deg(\text{vertex $i$})-1$, one obtains $$ \frac{1}{\zeta_G(u)}=(1-u^2)(1-4u+3u^2)=1-4u+2u^2+4u^3-3u^4 $$ for this graph. Either by brute-force enumeration, or by the edge-matrix method described below, one computes the numbers of equivalence classes of primitive, nonbacktracking closed walks of a given length. $$ \begin{array}{l|ccccccccccc} \text{length} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11\\ \hline \text{classes} & 4 & 4 & 8 & 18 & 48 & 116 & 312 & 810 & 2184 & 5880 & 16104 \end{array} $$ Evaluating the product $$ \begin{aligned}&(1-u)^4(1-u^2)^4(1-u^3)^8(1-u^4)^{18}(1-u^5)^{48}(1-u^6)^{116}(1-u^7)^{312}\\ &\quad\times(1-u^8)^{810}(1-u^9)^{2184}(1-u^{10})^{5880}(1-u^{11})^{16104}\ ,\end{aligned} $$ one finds that it equals $(1-u^2)(1-4u+3u^2)+O(u^{12})$. As the number of factors in the product is increased, the product can be made to differ from the polynomial by an expression proportional to an arbitrarily high power of $u$. Since the polynomial has roots at $-1$, $1$, and $\frac{1}{3}$, it should also be possible to show that the product converges for all $\lvert u\rvert<\frac{1}{3}$.

Turning to the sum form that Möbius inversion gives, we will see that the vanishing of the coefficients of powers of $u$ greater than $4$ comes about due to cancellation, and not to the vanishing of all the relevant $\mu(M)$. Using the coefficient of $u^5$ as an example, we need to find all ways of forming a multiset of equivalence classes of prime walks such that the sum of the lengths is $5$. One way is for $M$ to contain a single equivalence class length-$5$ walks, in which case there is a contribution of $\mu(M)=-1$ to the sum. The table above shows that there are $48$ such equivalence classes. Another way is for $M$ to consist of a class of length-$4$ walks and a class of length-$1$ walks, or of class of length-$3$ walks and a class of length-$2$ walks. A third way is for $M$ to consist of one class of length-$3$ walks and two classes of length-$1$ walks, or of two classes of length-$2$ walks and one class of length-$1$ walks. A final way is for $M$ to consist of one class of length-$2$ walks and three classes of length-$1$ walks. (If $M$ consists of five classes of length-$1$ walks then $\mu(M)$ always equals $0$ since there are only four different classes of length-$1$ walks and therefore $M$ must contain at least one class twice.)

Using the numbers of equivalence classes from the table above, and omitting contributions with $\mu(M)=0$, we find that the coefficient of $u^5$ is $$ -48+18\cdot4+8\cdot4-8\cdot\binom{4}{2}-\binom{4}{2}\cdot4+4\cdot\binom{4}{3}=-48+72+32-48-24+16=0. $$

The table below summarizes all nonzero contributions to the terms up to $u^5$. The notation for the walks listed in the $M$ column is explained below. $$ \begin{array}{c|l|c|c|c} L(M) & M & \mu(M) & \text{subtotal} & \text{total}\\ \hline 0 & \{\} & 1 & 1 & 1\\ \hline 1 & \{1\},\{\bar{1}\},\{2\},\{\bar{2}\} & -1 & -4 & -4\\ \hline 2 & \{12\},\{1\bar{2}\},\{\bar{1}2\},\{\bar{1}\bar{2}\} & -1 & -4 & \\ & \{1,\bar{1}\},\{1,2\},\{1,\bar{2}\},\{\bar{1},2\},\{\bar{1},\bar{2}\},\{2,\bar{2}\} & 1 & \binom{4}{2} & 2\\ \hline 3 & \{112\},\{11\bar{2}\},\{122\},\{1\bar{2}\bar{2}\},\{\bar{1}\bar{1}2\},\{\bar{1}\bar{1}\bar{2}\},\{\bar{1}22\},\{\bar{1}\bar{2}\bar{2}\} & -1 & -8 & \\ & \{1,12\},\{1,1\bar{2}\},\ldots\{\bar{2},\bar{1}\bar{2}\} & 1 & 4\cdot4 & \\ & \{\bar{1},2,\bar{2}\},\{1,2,\bar{2}\},\{1,\bar{1},\bar{2}\},\{1,\bar{1},2\} & -1 & -\binom{4}{3} & 4\\ \hline 4 & \{1112\},\{111\bar{2}\},\ldots, & -1 & -18 & \\ & \{1,112\},\{1,11\bar{2}\},\ldots & 1 & 4\cdot8 & \\ & \{12,1\bar{2}\},\{12,\bar{1}2\},\ldots & 1 & \binom{4}{2} & \\ & \{1,\bar{1},12\},\{1,\bar{1},1\bar{2}\},\ldots & -1 & -\binom{4}{2}\cdot4 & \\ & \{1,\bar{1},2,\bar{2}\} & 1 & \binom{4}{4} & -3\\ \hline 5 & \{11112\},\{1111\bar{2}\},\ldots & -1 & -48 & \\ & \{1,1112\},\{1,111\bar{2}\},\ldots & 1 & 4\cdot18 & \\ & \{12,112\},\{12,11\bar{2}\},\ldots & 1 & 4\cdot8 & \\ & \{1,12,1\bar{2}\},\{1,12,\bar{1}2\},\ldots & -1 & -4\cdot\binom{4}{2} & \\ & \{1,\bar{1},112\},\{1,\bar{1},11\bar{2}\},\ldots & -1 & -\binom{4}{2}\cdot8 & \\ & \{1,\bar{1},2,12\},\{1,\bar{1},2,1\bar{2}\},\ldots & 1 & \binom{4}{3}\cdot4 & 0\\ \end{array} $$

Enumerating equivalence classes of prime walks. Now for an explanation of how the numbers of equivalence classes of primitive, nonbacktracking closed walks were computed. Label one of the loops in the graph $1$ and the other $2$. The loops may be traversed in either direction, so we arbitrarily choose one of the directions on each loop to be the forward direction, and denote the reverse directions $\bar{1}$ and $\bar{2}$. Two closed walks, written as words on the alphabet $\{1,\bar{1},2,\bar{2}\}$, are equivalent if they are cyclic shifts of each other. A word is nonprimitive if it equals a nonzero cyclic shift of itself. To be nonbacktracking, the letters $1$ and $\bar{1}$ may not be adjacent, with a similar restriction on the letters $2$ and $\bar{2}$. So the walks of length $1$ are $1$, $\bar{1}$, $2$, $\bar{2}$, and the walks of length $2$ are $12$, $1\bar{2}$, $\bar{1}2$, $\bar{1}\bar{2}$.

For length three, the walks are of the form $aab$ or $abb$, where $a\in\{1,\bar{1}\}$ and $b\in\{2,\bar{2}\}$, which implies eight walks. For length four, we have the forms $aaab$, $aabb$, $abbb$, giving $12$ walks, and, in addition, walks of the form $aba'b'$, where $a,a'\in\{1,\bar{1}\}$, $b,b'\in\{2,\bar{2}\}$, $a'$ is possibly equal to $a$, and $b'$ is possibly equal to $b$. The latter would seem to produce $16$ walks, but some are disallowed and some are equivalent to others. The disallowed walks are those of the form $abab$ since they are not primitive. This eliminates $2\cdot2=4$ walks. The remaining eight walks satisfy the equivalences $$ \begin{aligned} 121\bar{2}&\sim1\bar{2}12,\\ 12\bar{1}2&\sim\bar{1}212,\\ 12\bar{1}\bar{2}&\sim\bar{1}\bar{2}12,\\ 1\bar{2}\bar{1}2&\sim\bar{1}21\bar{2},\\ 1\bar{2}\bar{1}\bar{2}&\sim\bar{1}\bar{2}1\bar{2},\\ \bar{1}2\bar{1}\bar{2}&\sim\bar{1}\bar{2}\bar{1}2. \end{aligned} $$ Hence there are $(16-4)/2=6$ equivalence classes. In total there are $12+6=18$ classes. For lengths greater than four, the numbers of equivalence classes were initially obtained by exhaustive enumeration on a computer.

A better method, however, is to use Hashimoto's edge adjacency matrix, which is called the $0,1$ edge matrix $W_1$ in Definition 2.2 of of What are zeta functions of graphs and what are they good for? by Matthew D. Horton, H. M. Stark, and Audrey A. Terras. First we enumerate the number nonbacktracking closed walks. Let $$ W_1=\begin{bmatrix}1 & 0 & 1 & 1\\ 0 & 1 & 1 & 1\\ 1 & 1 & 1 & 0\\ 1 & 1 & 0 & 1\end{bmatrix}, $$ where rows and columns are both indexed by the letters $1$, $\bar{1}$, $2$, $\bar{2}$. (This matrix was called $B$ in the earlier comment thread.) The number of nonbacktracking closed walks (cyclic words with $\bar{1}$ never adjacent to $1$ and $\bar{2}$ never adjacent to $2$) of length $\ell$ is then $\mathrm{Tr}\,W_1^\ell=\sum \lambda_j^\ell$, where $\lambda_j$ are the eigenvalues of $W_1$, namely $3$, $1$, $1$, $-1$. The result is $3^\ell+2+(-1)^\ell$.

The requirement that our nonbacktracking closed walks be primitive can be imposed using Möbius inversion. Let $\phi(\ell)$ be the number of primitive, nonbacktracking closed walks. Then $\sum_{d\mid \ell}\phi(d)=3^\ell+2+(-1)^\ell$. The Möbius inversion formula then implies that $\phi(\ell)=\sum_{d\mid\ell}\mu(\ell/d)(3^d+2+(-1)^d)$. Since equivalence classes of primitive, nonbacktracking length-$\ell$ walks contain $\ell$ elements, the number of equivalence classes of primitive, nonbacktracking closed length-$\ell$ walks is $\phi(\ell)/\ell$. One can verify that this reproduces the sequence $4$, $4$, $8$, $18$, $48$, $116$, $312$, $\ldots$ in the first table above.

It is worth noting that $W_1$ appears to play an important role in the theory of the Ihara zeta function. K. Hashimoto gave the formula $$ \frac{1}{\zeta_G(u)}=\det(I-uW_1),\tag{2} $$ which already shows that $1/\zeta_G(u)$ is a polynomial in $u$. The paper of Horton, Stark, and Terras gives a short proof of this formula, which arises as an intermediate step in their presentation of a proof of H. Bass's generalization of the determinant formula of Ihara and Sunada (Equation (1) above).

Their proof of (2) involves generalizing $W_1$ by replacing the elements $1$ with complex variables to obtain a matrix $W$. The sum over prime walks is then reorganized to eliminate

1. the restriction to primitive walks, and

2. the restriction to a single representative of each equivalence class.

So now we have a sum over nonbacktracking closed walks rather than over primes. The contribution to the sum of walks of length $\ell$ is $\mathrm{Tr}\,W^\ell$, which is similar to the expression we arrived at above. Some matrix calculus is used to relate this sum to a determinant. Finally, the complex variables are replaced with $1$s so that $W$ reduces to $W_1$.

Solution 2:

for a graph $G$ : $p$ are the prime cycles, that is a cycle in the graph that doesn't pass through the same vertex two times (I think they did a mistake about that on wiki). $L(c)$ is the length of a cycle. two cycles are considered the same if they are the concatenation of the same prime cycles, each the same number of times, but in different order.

because each cycle is a concatenation of prime cycles, there length will be $L(p_i) + L(p_j) + \cdots$ and your zeta function computes :

$$\zeta_G(u) = \sum_{c \in G} u^{L(C)} = \sum_{n} b_G(n) u^n$$

where $c$ are the cycles of $G$. the coefficients of this analytic function are $b_G(n) = \sum_{L(c) = n} 1$ which depend on the graph. there is an infinity of cycles because once you got one, you can concanate it with itself anytimes you want. so $\zeta_G(u)$ converges at most for $|u| < 1$. it means that $\lim_{n \to \infty} b_G(n) \ne 0$.

now we look at it's inverse, which is a simple polynomial if the graph is finite :

$$\frac{1}{\zeta_G(u)} = \sum_{c \in G} \mu(c) u^{L(C)} = \sum_{n} a_G(n) u^n$$

where $\mu(c) = (-1)^k$ if $c$ is composed of $k$ different prime cycles, and $\mu(c) = 0$ if there is a prime cycle appearing two times or more in it.

the sequence $a_G(n) = \sum_{L(c) = n} \mu(c)$ is the convolution inverse of the sequence $b_G(n)$ :

$$( a_G \ast b_G)(n) = \sum_{k=0}^n a_G(k) b_G(n-k) = \delta(n)$$

note that it is normal convolution, additive, not the multiplicative one as for the Riemann zeta function with $\sum_{d | n}$. your $\zeta$ is additive because we considered addition of cycle lengths, not multiplication. that makes a huge difference between additive and multiplicative zeta function.

now if it's a normal graph, your $\frac{1}{\zeta_G(u)} = \sum_{n} a_G(n) u^n$ is a polynomial because there is only a finite number of different prime cycles.

thus $\frac{1}{\zeta_G(u)}$ is holomorphic on the whole complex plane, and $\zeta_G(u)$ is holomorphic on the whole complex plane except at a finite number of poles (the zeros of the polynomial $\frac{1}{\zeta_G(u)}$).

I guess you can also consider a $\zeta$ function for a non-finite graph (Riemann surface topology ?), which maybe (I don't know because I didn't understand it) could take you into the wonderful world of Selberg zeta functions for hyperbolic surfaces...