Return to Question

It all started with Chris' answer saying returning paths on cubic graphs without backtracking can be expressed by the following recursion relation:

$$p_{r+1}(a) = ap_r(a)-2p_{r-1}(a)$$

$a$ is an eigenvalue of the adjacency matrix $A$. Chris mentions Chebyshev polynomials there. It was Will who found the generating function for the given recursion to be:

$$G(x,a)=\frac{1-x^2}{1-ax+2x^2} $$

and just recently Hamed put Chebyshev back on the table:

$$ \frac{1-x^2}{1-ax +2x^2} \xrightarrow{x=t/\sqrt{2}}\frac{1-\frac{t^2}2}{1-2\frac{a}{\sqrt 8} t+t^2}=\left[1-\frac{t^2}{2}\right]\sum_{r=0}^\infty U_r\left(\frac{a}{\sqrt{8}}\right)t^r\\ =\sum_{r=0}^\infty \left(U_r\left(\frac{a}{\sqrt{8}}\right)-\frac12 U_{r-2}\left(\frac{a}{\sqrt{8}}\right)\right)t^r\\ $$ $$ \Rightarrow p_r(t)=\begin{cases}1 & \text{if $r=0$,}\\ 2^{r/2}\left(U_r(t/\sqrt{8})-\frac12U_{r-2}(t/\sqrt{8})\right) & \text{if $r\ge1$.}\end{cases} $$ The final line as taken from Will's community answer...

My question how to relate Ihara's $\zeta$ function and Chebyshev seems therefore mostly settled, but...:

Is it just a funny coincidence that the scaling factor of $\sqrt 8$ coincides with $\lambda_1\leq 2\sqrt 2$, which is the definition of cubic Ramanujan graphs.

And, there is another interesting thing:

As observed by Sunada, a regular graph is a Ramanujan graph if and only if its Ihara zeta function satisfies an analogue of the Riemann hypothesis.

What does this connection between Chebyshev, Ramanujan, Ihara and Riemann mean?

EDIT

I thought maybe something like a corollary could be possible:

1. For Ramanujan graphs, the Ihara $\zeta$ function can be related to Chebyshev functions of the second kind, since the scaled eigenvalues of $A$ lie inside the range of convergence.
2. A Ramanujan graph $G$ obeys the Riemann Hypothesis.
3. Roots of the Ihara $\zeta$ function lie on the critical strip.

• The bunch of people above have contributed to $1\leftarrow 2$.
• $2 \leftrightarrow 3$ is proven here: Eigenvalues are of the form $\lambda=2\sqrt 2\cos(b\log 2)$
• $3\overset{\rightarrow ?}{\leftarrow} 1$ would be nice...

It all started with Chris' answer saying returning paths on cubic graphs without backtracking can be expressed by the following recursion relation:

$$p_{r+1}(a) = ap_r(a)-2p_{r-1}(a)$$

$a$ is an eigenvalue of the adjacency matrix $A$. Chris mentions Chebyshev polynomials there. It was Will who found the generating function for the given recursion to be:

$$G(x,a)=\frac{1-x^2}{1-ax+2x^2} $$

and just recently Hamed put Chebyshev back on the table:

$$ \frac{1-x^2}{1-ax +2x^2} \xrightarrow{x=t/\sqrt{2}}\frac{1-\frac{t^2}2}{1-2\frac{a}{\sqrt 8} t+t^2}=\left[1-\frac{t^2}{2}\right]\sum_{r=0}^\infty U_r\left(\frac{a}{\sqrt{8}}\right)t^r\\ =\sum_{r=0}^\infty \left(U_r\left(\frac{a}{\sqrt{8}}\right)-\frac12 U_{r-2}\left(\frac{a}{\sqrt{8}}\right)\right)t^r\\ $$ $$ \Rightarrow p_r(a)=\begin{cases}1 & \text{if $r=0$,}\\ 2^{r/2}\left(U_r(a/\sqrt{8})-\frac12U_{r-2}(a/\sqrt{8})\right) & \text{if $r\ge1$.}\end{cases} $$ The final line as taken from Will's community answer...

My question how to relate Ihara's $\zeta$ function and Chebyshev seems therefore mostly settled, but...:

Is it just a funny coincidence that the scaling factor of $\sqrt 8$ coincides with $\lambda_1\leq 2\sqrt 2$, which is the definition of cubic Ramanujan graphs.

And, there is another interesting thing:

As observed by Sunada, a regular graph is a Ramanujan graph if and only if its Ihara zeta function satisfies an analogue of the Riemann hypothesis.

What does this connection between Chebyshev, Ramanujan, Ihara and Riemann mean?

EDIT

I thought maybe something like a corollary could be possible:

1. For Ramanujan graphs, the Ihara $\zeta$ function can be related to Chebyshev functions of the second kind, since the scaled eigenvalues of $A$ lie inside the range of convergence.
2. A Ramanujan graph $G$ obeys the Riemann Hypothesis.
3. Roots of the Ihara $\zeta$ function lie on the critical strip.

• The bunch of people above have contributed to $1\leftarrow 2$.
• $2 \leftrightarrow 3$ is proven here: Eigenvalues are of the form $\lambda=2\sqrt 2\cos(b\log 2)$
• $3\overset{\rightarrow ?}{\leftarrow} 1$ would be nice...

It all started with Chris' answer saying returning paths on cubic graphs without backtracking can be expressed by the following recursion relation:

$$p_{r+1}(a) = ap_r(a)-2p_{r-1}(a)$$

$a$ is an eigenvalue of the adjacency matrix $A$. Chris mentions Chebyshev polynomials there. It was Will who found the generating function for the given recursion to be:

$$G(x,a)=\frac{1-x^2}{1-ax+2x^2} $$

and just recently Hamed put Chebyshev back on the table:

$$ \frac{1-x^2}{1-ax +2x^2} \xrightarrow{x=t/\sqrt{2}}\frac{1-\frac{t^2}2}{1-2\frac{a}{\sqrt 8} t+t^2}=\left[1-\frac{t^2}{2}\right]\sum_{r=0}^\infty U_r\left(\frac{a}{\sqrt{8}}\right)t^r\\ =\sum_{r=0}^\infty \left(U_r\left(\frac{a}{\sqrt{8}}\right)-\frac12 U_{r-2}\left(\frac{a}{\sqrt{8}}\right)\right)t^r\\ $$ $$ \Rightarrow p_r(t)=\begin{cases}1 & \text{if $r=0$,}\\ 2^{r/2}U_r(t/\sqrt{8})-2^{(r-2)/2}U_{r-2}(t/\sqrt{8}) & \text{if $r\ge1$.}\end{cases} $$ The final line as taken from Will's community answer...

My question how to relate Ihara's $\zeta$ function and Chebyshev seems therefore mostly settled, but...:

Is it just a funny coincidence that the scaling factor of $\sqrt 8$ coincides with $\lambda_1\leq 2\sqrt 2$, which is the definition of cubic Ramanujan graphs.

And, there is another interesting thing:

As observed by Sunada, a regular graph is a Ramanujan graph if and only if its Ihara zeta function satisfies an analogue of the Riemann hypothesis.

What does this connection between Chebyshev, Ramanujan, Ihara and Riemann mean?

EDIT

I thought maybe something like a corollary could be possible:

1. For Ramanujan graphs, the Ihara $\zeta$ function can be related to Chebyshev functions of the second kind, since the scaled eigenvalues of $A$ lie inside the range of convergence.
2. A Ramanujan graph $G$ obeys the Riemann Hypothesis.
3. Roots of the Ihara $\zeta$ function lie on the critical strip.

• The bunch of people above have contributed to $1\leftarrow 2$.
• $2 \leftrightarrow 3$ is proven here: Eigenvalues are of the form $\lambda=2\sqrt 2\cos(b\log 2)$
• $3\overset{\rightarrow ?}{\leftarrow} 1$ would be nice...

It all started with Chris' answer saying returning paths on cubic graphs without backtracking can be expressed by the following recursion relation:

$$p_{r+1}(a) = ap_r(a)-2p_{r-1}(a)$$

$a$ is an eigenvalue of the adjacency matrix $A$. Chris mentions Chebyshev polynomials there. It was Will who found the generating function for the given recursion to be:

$$G(x,a)=\frac{1-x^2}{1-ax+2x^2} $$

and just recently Hamed put Chebyshev back on the table:

$$ \frac{1-x^2}{1-ax +2x^2} \xrightarrow{x=t/\sqrt{2}}\frac{1-\frac{t^2}2}{1-2\frac{a}{\sqrt 8} t+t^2}=\left[1-\frac{t^2}{2}\right]\sum_{r=0}^\infty U_r\left(\frac{a}{\sqrt{8}}\right)t^r\\ =\sum_{r=0}^\infty \left(U_r\left(\frac{a}{\sqrt{8}}\right)-\frac12 U_{r-2}\left(\frac{a}{\sqrt{8}}\right)\right)t^r\\ $$ $$ \Rightarrow p_r(t)=\begin{cases}1 & \text{if $r=0$,}\\ 2^{r/2}\left(U_r(t/\sqrt{8})-\frac12U_{r-2}(t/\sqrt{8})\right) & \text{if $r\ge1$.}\end{cases} $$ The final line as taken from Will's community answer...

My question how to relate Ihara's $\zeta$ function and Chebyshev seems therefore mostly settled, but...:

Is it just a funny coincidence that the scaling factor of $\sqrt 8$ coincides with $\lambda_1\leq 2\sqrt 2$, which is the definition of cubic Ramanujan graphs.

And, there is another interesting thing:

As observed by Sunada, a regular graph is a Ramanujan graph if and only if its Ihara zeta function satisfies an analogue of the Riemann hypothesis.

What does this connection between Chebyshev, Ramanujan, Ihara and Riemann mean?

EDIT

I thought maybe something like a corollary could be possible:

1. For Ramanujan graphs, the Ihara $\zeta$ function can be related to Chebyshev functions of the second kind, since the scaled eigenvalues of $A$ lie inside the range of convergence.
2. A Ramanujan graph $G$ obeys the Riemann Hypothesis.
3. Roots of the Ihara $\zeta$ function lie on the critical strip.

• The bunch of people above have contributed to $1\leftarrow 2$.
• $2 \leftrightarrow 3$ is proven here: Eigenvalues are of the form $\lambda=2\sqrt 2\cos(b\log 2)$
• $3\overset{\rightarrow ?}{\leftarrow} 1$ would be nice...

It all started with Chris' answer saying returning paths on cubic graphs without backtracking can be expressed by the following recursion relation:

$$p_{r+1}(a) = ap_r(a)-2p_{r-1}(a)$$

$a$ is an eigenvalue of the adjacency matrix $A$. Chris mentions Chebyshev polynomials there. It was Will who found the generating function for the given recursion to be:

$$G(x,a)=\frac{1-x^2}{1-ax+2x^2} $$

and just recently Hamed put Chebychev back on the table:

$$ \frac{1-x^2}{1-ax +2x^2} \xrightarrow{x=t/\sqrt{2}}\frac{1-\frac{t^2}2}{1-2\frac{a}{\sqrt 8} t+t^2}=\left[1-\frac{t^2}{2}\right]\sum_{r=0}^\infty U_r\left(\frac{a}{\sqrt{8}}\right)t^r\\ =\sum_{r=0}^\infty \left(U_r\left(\frac{a}{\sqrt{8}}\right)-\frac12 U_{r-2}\left(\frac{a}{\sqrt{8}}\right)\right)t^r\\ $$ $$ \Rightarrow p_r(t)=\begin{cases}1 & \text{if $r=0$,}\\ 2^{r/2}U_r(t/\sqrt{8})-2^{(r-2)/2}U_{r-2}(t/\sqrt{8}) & \text{if $r\ge1$.}\end{cases} $$ The final line as taken from Will's community answer...

My question how to relate Ihara's $\zeta$ function and Chebyshev seems therefore mostly settled, but...:

Is it just a funny coincidence that the scaling factor of $\sqrt 8$ coincides with $\lambda_1\leq 2\sqrt 2$, which is the definition of cubic Ramanujan graphs.

And, there is another interesting thing:

As observed by Sunada, a regular graph is a Ramanujan graph if and only if its Ihara zeta function satisfies an analogue of the Riemann hypothesis.

What does this connection between Chebyshev, Ramanujan, Ihara and Riemann mean?

EDIT

I thought maybe something like a corollary could be possible:

1. For Ramanujan graphs, the Ihara $\zeta$ function can be related to Chebyshev functions of the second kind, since the scaled eigenvalues of $A$ lie inside the range of convergence.
2. A Ramanujan graph $G$ obeys the Riemann Hypothesis.
3. Roots of the Ihara $\zeta$ function lie on the critical strip.

• The bunch of people above have contributed to $1\leftarrow 2$.
• $2 \leftrightarrow 3$ is proven here: Eigenvalues are of the form $\lambda=2\sqrt 2\cos(b\log 2)$
• $3\overset{\rightarrow ?}{\leftarrow} 1$ would be nice...

It all started with Chris' answer saying returning paths on cubic graphs without backtracking can be expressed by the following recursion relation:

$$p_{r+1}(a) = ap_r(a)-2p_{r-1}(a)$$

$a$ is an eigenvalue of the adjacency matrix $A$. Chris mentions Chebyshev polynomials there. It was Will who found the generating function for the given recursion to be:

$$G(x,a)=\frac{1-x^2}{1-ax+2x^2} $$

and just recently Hamed put Chebyshev back on the table:

$$ \frac{1-x^2}{1-ax +2x^2} \xrightarrow{x=t/\sqrt{2}}\frac{1-\frac{t^2}2}{1-2\frac{a}{\sqrt 8} t+t^2}=\left[1-\frac{t^2}{2}\right]\sum_{r=0}^\infty U_r\left(\frac{a}{\sqrt{8}}\right)t^r\\ =\sum_{r=0}^\infty \left(U_r\left(\frac{a}{\sqrt{8}}\right)-\frac12 U_{r-2}\left(\frac{a}{\sqrt{8}}\right)\right)t^r\\ $$ $$ \Rightarrow p_r(t)=\begin{cases}1 & \text{if $r=0$,}\\ 2^{r/2}U_r(t/\sqrt{8})-2^{(r-2)/2}U_{r-2}(t/\sqrt{8}) & \text{if $r\ge1$.}\end{cases} $$ The final line as taken from Will's community answer...

My question how to relate Ihara's $\zeta$ function and Chebyshev seems therefore mostly settled, but...:

Is it just a funny coincidence that the scaling factor of $\sqrt 8$ coincides with $\lambda_1\leq 2\sqrt 2$, which is the definition of cubic Ramanujan graphs.

And, there is another interesting thing:

As observed by Sunada, a regular graph is a Ramanujan graph if and only if its Ihara zeta function satisfies an analogue of the Riemann hypothesis.

What does this connection between Chebyshev, Ramanujan, Ihara and Riemann mean?

EDIT

I thought maybe something like a corollary could be possible:

1. For Ramanujan graphs, the Ihara $\zeta$ function can be related to Chebyshev functions of the second kind, since the scaled eigenvalues of $A$ lie inside the range of convergence.
2. A Ramanujan graph $G$ obeys the Riemann Hypothesis.
3. Roots of the Ihara $\zeta$ function lie on the critical strip.

• The bunch of people above have contributed to $1\leftarrow 2$.
• $2 \leftrightarrow 3$ is proven here: Eigenvalues are of the form $\lambda=2\sqrt 2\cos(b\log 2)$
• $3\overset{\rightarrow ?}{\leftarrow} 1$ would be nice...