I am getting myself familiar with the background of the non-backtracking operator on a finite graph.
The zeta functions of a finite graph is relevant, though not directly related to my project.
According to Wikipedia, the zeta function of an undirected finite graph $G(V,E)$ is defined as the analytic continuation of the infinite product
\begin{equation}
\zeta_G(u) = \prod_{\gamma \in \Gamma} \frac{1}{1-u^{L(\gamma)}}
\end{equation}
where $\Gamma$ is the set of "primitive cycles" on the graph and $L(\gamma)$ is the length of the primitive cycle $\gamma$.
By the definition on wikipedia, a cycle is a closed path, denoted either by vertex sequence $\{v_1, v_2, \cdots, v_n, v_{n+1}=v_1\}$ or by arc sequence $\{a_1, a_2, \cdots, a_n\}$ such that the end of $a_n$ is the same as the start of $a_1$, satisfies the following properties:
- adjacent arcs in the path are not backtracking, i.e., $v_{i+2} \neq v_i$ or $a_i^{-1} \neq a_{i+1}$ where $a_i^{-1}$ means the opposite arc of the arc $a_i$;
- the cycle can not be obtained by repeating a cycle $m$ times, for some integer $m>1$.
Further note on the definition is that two cycles are considered as equivalent if one can be obtained by a cyclic permutation of another.
So an element of set $\Gamma$ is actually a class of primitive cycles and $L(\gamma)$ is the length of cycles in that class.
I am confused with the second property of "primitive cycles".
Consider the graph depicted by the following figure.
I understand that $C_1 \equiv \{1\to 2\to 3\to 1\}$ and $C_2 \equiv \{1\to 4\to 5\to 1\}$, up to cyclic permutations, are primitive cycles.
Then take $C_1^m C_2^n$ as the cycle composed of $C_1$ and $C_2$.
For example, $C_1^1 C_2^1 \equiv \{1 \to 2 \to 3 \to 1 \to 4 \to 5 \to 1\}$.
My question is: Are cycles composed of multiple primitive cycles also primitive?
If so, the set $\Gamma$ would have infinite elements.
If not, the set $\Gamma$ would only have finite elements.
Which is the case?
Best Answer
The set $\Gamma$ has infinitely many elements. For example, any closed path of the form $C_1^m C_2^n$ with $m,n \ne 0$ is primitive. On the other hand, the closed path $C_1 C_2 C_1 C_2$ is not primitive, since it can be written as $(C_1 C_2)^2$.
The weird thing about this infinite product is that it's equal to the reciprocal of a finite polynomial. So let's see how that happens in the example graph. All primitive cycles will have lengths that are multiples of $3$.
So that gives us the first few factors of $\zeta_G(u)^{-1}$ as $(1 - u^3)^4(1-u^6)^4(1-u^9)^8(1-u^{12})^{18}$, which expands to a long polynomial $$1-4 u^3+2 u^6+4 u^9-3 u^{12}+48 u^{15}-76 u^{18} + \dots + u^{324}$$ and this looks concerning. Especially when you notice that the polynomial we're supposed to get has degree $12$.
But the next case (which you don't want to do by hand) is $48$ primitive cycles of length $15$, and the factor of $(1-u^{15})^{48}$ cancels out the $48u^{15}$ term. We get $$ 1-4 u^3+2 u^6+4 u^9-3 u^{12}+116 u^{18}-152 u^{21} + \dots + u^{1044}. $$ Similarly, in the next case, we'll have $116$ primitive cycles of length $18$, and the factor of $(1 - u^{18})^{116}$ cancels out the $116 u^{18}$ term. After we include that factor, we get $$ 1-4 u^3+2 u^6+4 u^9-3 u^{12}+312 u^{21}-438 u^{24} + \dots + u^{3132}. $$ From now on, we will always keep the initial bit $1-4 u^3+2 u^6+4 u^9-3 u^{12}$, and this is the polynomial given to us by the formula $\zeta_G(u)^{-1}={(1-u^{2})^{|E|-|V|}\det(I-uA+u^2[D-I])}$. The more factors we include, the more of the other terms we cancel. So at least as a formal infinite product, $\zeta_G(u)^{-1}=\prod_{\gamma \in \Gamma} (1 - u^{L(\gamma)})$ simplifies to a polynomial.
As to convergence issues, certainly the polynomial is defined for all $u$, and $\prod_{\gamma \in \Gamma} (1 - u^{L(\gamma)})$ will not converge for all $u$. It will converge for some small $u$ depending on the growth rate of the sequence $4, 4, 8, 18, 48, 116, \dots$. In particular, this sequence is bounded by $4^k$ for all $k$, so the product defining $\zeta_G(u)^{-1}$ is no worse at converging than $$\prod_{k=1}^\infty (1 - u^{3k})^{4^k}$$ which converges for $|u| < \frac1{2^{2/3}}$. But note that $\zeta_G(u)$ is defined as the analytic continuation of the infinite product $\prod_{\gamma \in \Gamma} (1 - u^{L(\gamma)})^{-1}$, so it actually is the reciprocal of that polynomial everywhere.