How to get from Chebyshev to Ihara?

I have competing answers on my question about "Returning Paths on Cubic Graphs Without Backtracking". Assuming Chris is right the following should work. Up to one thing:

The number of returning paths on 3-regular graphs of length $r$ without backtracking may be written as $2^{-r/2}p_r(x/\sqrt{2})$ which is a Chebyshev Polynomial of the Second Kind $U_r(x)$.

The linked MathWorld page also says that

the defining generating function of the Chebyshev polynomials of the second kind is
$$ g(t,x)=\frac1{1-2xt+t^2}=\sum_{r=0}^\infty U_r(x) t^r \tag{8,9} $$

So, if we substitute $U_r(x)$ with $2^{-r/2}p_r(x)$, next $x$ with $x/\sqrt{2}$ and sum up over $r$ we get $$ \sum_r \left(\frac t{\sqrt 2}\right)^r \cdot p_r\left(\frac x{\sqrt{2}}\right) \tag{10} $$

Now we plug in the eigenvalues $a_k$ of $G$'s adjacency matrix $A$ for $x$. Then the result should equal $$ \frac1{\operatorname{det}(I-\text{Diag}(a_k)t+\frac {t^2}2I)}\tag{11}. $$ where the denominator can be transformed, so that it overall represents a polynomial $$P_{\text{Diag}(a_k)}(t)=P_{A}(t).$$

To match

Ihara $\zeta$ function: If $G$ is $3$-regular with adjacency matrix $A$ then $$ \zeta_G(t) = \frac{(1-t^2)^{1-\chi(G)}}{\det(I - At + 2t^2I)} \tag{12} $$ where $\chi(G)$ is the circuit rank, which is $r=m-n+c$ where m is the number of edges in G, n is the number of vertices, and c is the number of connected components.

$G$ is cubic and shall have one component, so $2m=3n$ and $c=1$ and $\chi(G)-1=r-1=\frac32n-n+1-1=\frac12n$. The numerator is $(1-t^2)^{n/2}$ then and let's say call $Q_A(t)=\det((1+2t^2)I - At)={t^{-n}}\det((t^{-1}+2t)I - A)={t^{-n}}Q^\prime_A(t)$.

Question:

Did I go wrong somewhere or is it possible to prove:

that $$ \begin{eqnarray*} (1-t^2)^{n/2}P_A(t)&=&Q_A(t)\\ (1-t^2)^{n/2}P_A(t)&=&{(t^2)^{-n/2}}Q^\prime_A(t)\\ (t^2)^{n/2}(1-t^2)^{n/2}P_A(t)&=&Q^\prime_A(t)\\ (t^2-t^4)^{n/2}P_A(t)&=&Q^\prime_A(t) \end{eqnarray*} $$ is independant of $A$?

or

where is difference between $({11})$ and $(12)$?

Solution 1:

You ask "Did I go wrong somewhere...?" I'm having trouble following at a number of points in your post, which may be a sign that something is wrong, or at least of some things that ought to be clarified.

You say

The number of returning paths on 3-regular graphs of length $r$ without backtracking may be written as $2^{-r/2}p_r(x/\sqrt{2})$ which is a Chebyshev Polynomial of the Second Kind $U_r(x)$.

But shouldn't you instead say that the number of returning paths on $3$-regular graphs of length $r$ without backtracking is a diagonal element of $p_r(A)$, where $p_r(x)$ is the polynomial generated by the recurrence in Chris Godsil's answer and $A$ is the adjacency matrix of the graph? I'm not sure what your original phrasing could mean, since you haven't defined $x$.

Chris Godsil's post makes the claim that $2^{-r/2}p_r(x/\sqrt{2})=U_r(x)$, where $U_r(x)$ is the Chebyshev polynomial of the second kind. As I've pointed out in comments to that post, the claim is not correct for a couple of reasons.

Assuming that something like the claim is true, and pressing forward, we come to the generating function for Chebyshev polynomials that you quote from the MathWorld page. As I understand it, you plug in the adjacency matrix $A$ for $x$. If you do this, the polynomials become polynomials in $A$, which are therefore matrix valued, and the generating function, which is a sum of matrix valued polynomials with scalar coefficients $t^r$, is also matrix valued. But then you write

Then the result should equal $$ \frac1{\operatorname{det}(I-At+\frac {t^2}2I)}\tag{11}. $$ where the denominator represents a polynomial $P_{A}(t)$.

In this expression, the denominator is a determinant, which is a scalar, not a matrix. So something seems inconsistent here. I'm not even sure where the determinant is coming from: there is no determinant in the MathWorld formula you quote.

Added: It's not clear to me what connection between the generating function of Chebyshev polynomials and the Ihara zeta function you are trying to make. Perhaps expanding on this point would help. One issue that I can see is that returning paths without backtracking are not exactly the same as the paths that occur in the definition of the Ihara zeta function, $$ \zeta_G(t)=\prod_P(1-t^{L(P)})^{-1}, $$ where $L(P)$ is the length of $P$. The index $P$ in the product runs, not over backtrackless returning paths, but rather over equivalence classes of such paths, where two paths are considered equivalent if one is a cyclic permutation of the other. Since the paths enumerated by the Chebyshev expression have specified starting and ending vertices (even in the returning case), equivalent paths will be counted multiple times in that enumeration, rather than only once.

Second addition: From the recurrence $$ p_{n+1}(x)=xp_n(x)-2p_{n-1}(x), $$ which holds for $n\ge2$, and the initial conditions $p_0(x)=1$, $p_1(x)=x$, and $p_2(x)=x^2-3$, one can obtain the generating function for $p_n(x)$. Let $$ G(t,x)=p_0(x)+p_1(x)t+p_2(x)t^2+p_3(x)t^3+\ldots. $$ Then $$ \begin{aligned} G(t,x)-txG(t,x)+2t^2G(t,x)=&p_0(x)+p_1(x)t+p_2(x)t^2+p_3(x)t^3+\ldots\\ &-(xp_0(x)t+xp_1(x)t^2+xp_2(x)t^3+\ldots)\\ &+(2p_0(x)t^2+2p_1(x)t^3+2p_2(x)t^4+\ldots)\\ =&p_0(x)+[p_1(x)-xp_0(x)]t+[p_2(x)-xp_1(x)+2p_0(x)]t^2\\ &+[p_3(x)-xp_2(x)+2p_1(x)]t^3+[p_4(x)-xp_3(x)+2p_2(x)]t^3+\ldots\\ =&1-t^2. \end{aligned} $$ Division gives $$ G(t,x)=\frac{1-t^2}{1-xt+2t^2}. $$ This is not the same as your expression, but its validity does not depend on the resolution of the discrepancy between Chris Godsil's and my expressions for $p_n(x)$ in terms of Chebyshev polynomials; it derives entirely from the recurrence and initial conditions in Chris Godsil's post, and uses neither his nor my closed form expression. It is intriguing that the denominator is now much more similar to what appears in the determinant formula for the Ihara zeta function.

Third addition: To address your question in the comments about why the generating function above is different from the generating function for Chebyshev polynomials of the second kind, one possible answer is that $p_n(x)$, although related to the Chebyshev polynomial of the second kind, is not the Chebyshev polynomial of the second kind, and therefore has a different generating function. As I interpreted your question, however, it was asking why, starting from the MathWorld generating function for Chebyshev polynomials of the second kind and performing the manipulations you performed, you didn't end up with the same expression I did. In answer to this, several things need to be said. The answer is threefold:

1. because there is an error in Chris Godsil's change of variable that relates $p_n(x)$ to Chebyshev polynomials;
2. because your computation based on Chris Godsil's expression contained a further error, at least if you were trying to do what I think you were trying to do;
3. because $p_n(x)$, after the change of variable, satisfies different initial conditions than do Chebyshev polynomials of the second kind.

First make sure you understand the general idea behind my derivation above of the rational function expression for the generating function for $p_n(x)$. You can see that the coefficients of $t^0$, $t^1$, $t^2$ in the denominator of the rational function are going to be the same as the coefficients of $p_{n+1}$, $p_n$, $p_{n-1}$ in the recurrence. This is a general statement: the coefficients in the recurrence determine the form of the denominator; the numerator is determined by the initial conditions.

So in the rational generating function for $U_n$, the coefficients of $t^0$, $t^1$, $t^2$ in the denominator are $1$, $-2x$, $1$; in the recurrence for $p_n$, these coefficients are $1$, $-x$, $2$. We need to explain why you get the coefficients $1$, $-x$, $1/2$, which are different from either. This stems from two errors. One is that Chris Godsil states that $2^{-n/2}p_n(x/\sqrt{2})$ is a Chebyshev polynomial of the second kind, which is the wrong change of variable (and also reflects wrong initial conditions, but that's a separate issue). Let's suppose, for the moment, that this expression were correct (or that $p_n(x)$ were some other function that were related to Chebyshev polynomials of the second kind in this way). That would mean, by a derivation similar to the one above, that the function $$ H(t,x)=p_0(x/\sqrt{2})+2^{-1/2}tp_1(x/\sqrt{2})+2^{-1}t^2p_2(x/\sqrt{2})+\ldots $$ would be equal to a rational function with denominator $1-2xt+t^2$. What if you now wanted to find the generating function for $p_n(x)$,
$$ G(t,x)=p_0(x)+tp_1(x)+t^2p_2(x)+\ldots? $$ (I assume that this is what you want to compute; the generating function for $p_n(A)$ seems the most likely quantity to be related to the Ihara zeta function since it is $p_n(A)$ and not the polynomials you get by changing variable that relate to the actual paths.) You should be able to see that $G(t,x)=H(2^{1/2}t,2^{1/2}x)$, and therefore that $G(t,x)$ will be a rational function with denominator $1-4xt+2t^2$. The reason you didn't get this is that you replaced $t$ and $x$ in $H(t,x)$ with $2^{-1/2}t$ and $2^{-1/2}x$ rather than with $2^{1/2}t$ and $2^{1/2}x$.

But the change of variable wasn't correct in the first place. It is the function $2^{-n/2}p_n(2^{3/2}x)$ that satisfies the Chebyshev recurrence, not $2^{-n/2}p_n(x/\sqrt{2})$. Hence the denominator of the rational generating function for $p_n(x)$ will be equal to that of $H(2^{1/2},2^{-3/2}x)$. You can check that this denominator is $1-xt+2t^2$, as in my derivation above.

Finally, we need to explain why the numerator in my expression is $1-t^2$ rather than $1$. You can see from the derivation that this is because $p_2(x)-xp_1(x)+2p_0(x)$ doesn't equal $0$, but rather $-1$, which stems from the fact that $p_2(x)$ is not related to $p_1(x)$ and $p_0(x)$ by the same recurrence as $p_n(x)$ is related to $p_{n-1}(x)$ and $p_{n-2}(x)$ for $n>2$. (See the derivation above: all expressions $p_n(x)-xp_{n-1}(x)+2p_{n-2}(x)$ with $n>2$ vanish.)

Sorry if it seems that I keep harping on the same points over and over again. I'm not sure why we have not been able to iron these issues out.