Discrete Space-Time Wave Kernels and Trace Identities on Regular Graphs

Amar Bašić University of Sarajevo, Faculty of Electrical Engineering, Zmaja od Bosne bb, Sarajevo, 71000, Bosnia and Herzegovina abasic@etf.unsa.ba ORCID: https://orcid.org/0000-0002-3213-4527 , Lejla Smajlović University of Sarajevo, Department of Mathematics and Computer Science, Zmaja od Bosne 33-35, Sarajevo, 71000, Bosnia and Herzegovina University of Sarajevo, School of Economics and Business, Trg oslobodjenja - Alija Izetbegović 1, Sarajevo, 71000, Bosnia and Herzegovina lejlas@pmf.unsa.ba ORCID: https://orcid.org/0000-0002-2709-5535 and Zenan Šabanac University of Sarajevo, Department of Mathematics and Computer Science, Zmaja od Bosne 33-35, Sarajevo, 71000, Bosnia and Herzegovina zsabanac@pmf.unsa.ba ORCID: https://orcid.org/0000-0001-8122-496X

Abstract.

We study the discrete space-time wave equation on a $(q+1)$ -regular graph $X$ associated with the affine Laplace-type operator. For the forward time-difference scheme we derive explicit formulas for the two fundamental solutions (wave kernels) in terms of discrete modified Bessel functions and the non-backtracking walk counts on $X$ thus providing a direct and explicit link between wave propagation and combinatorial graph data. Utilizing uniqueness property of the wave kernel, we prove a new trace-type formula associated to the affine Laplace-type operator on $X$ and apply it to deduce many combinatorial identities. For example, we derive a closed-form expression for evaluation of some trigonometric sums twisted by an additive character as well as evaluations of finite sums of Chebyshev polynomials twisted by binomial coefficients.

Key words and phrases:

discrete wave equation, discrete space-time wave kernels, regular graphs, graph Laplacian, non-backtracking walks, discrete Bessel functions, wave trace identities

2020 Mathematics Subject Classification:

39A12, 05A19, 05C81, 33C10

1. Introduction and main results

The wave equation on a simple, regular graph provides a fundamental framework for studying discrete wave propagation, bridging classical continuum mechanics with discrete structures. Physically, this equation models the dynamics of vibrations in complex mechanical networks, acoustic waveguides, and quantum particles that transition across lattice structures [10, 46], where the traditional spatial derivative is replaced by the graph Laplacian operator [17, 28] or its linear perturbation [38, 42] so that the bottom of its spectrum is equal to zero. See also [16] for a study of properties of solutions of the semilinear wave equation on networks and [15, 47] for recent advances related to the wave equation on trees in continuous time.

Space-time discretization is a standard procedure in physics. An interested reader is referred to [34] and the references therein for motivation stemming from quantum gravitational considerations. More recently, discrete space-time wave equations are used in the study of graph neural networks [50] (the so called graph wave networks). The discretization of time in [50] proved to be particularly useful for numerical computations that are shown to be constantly stable. There are, of course, different possibilities for time discretization, the most common ones being the forward difference as in [9, 42], the backward difference [8, 36] or the symmetric timescale difference, see [19, 31].

1.1. Our setup

In this paper we study the (generalized) discrete space-time wave equation

\Delta_{X}^{a,b}W(x_{0},x;t)+\partial_{t}^{2}W(x_{0},x;t)=0.

(1.1)

on a connected, undirected $(q+1)$ -regular graph $X$ with a finite or countably infinite set of vertices $V(X)$ . Here

\Delta_{X}^{a,b}:=b\Delta_{X}-aI,

is the generalization of the combinatorial Laplacian $\Delta_{X}$ , acting on functions $f:V(X)\to\mathbb{R}$ , by

\Delta_{X}f(x)=(q+1)\,f(x)-\sum_{x\sim y}f(y).

We assume that the real parameters $a,\,b$ satisfy $b\neq 0$ and the spectral-edge condition

a\leq\begin{cases}0,&\text{if }b>0\\ -|b|\max\{\delta_{X={\textrm{finite}}}\lambda_{\max},(\sqrt{q}+1)^{2}\},&\text{if }b<0,\end{cases}

(1.2)

where $\lambda_{\max}$ is the largest eigenvalue of $\Delta_{X}$ if $X$ is finite ( $\delta_{X={\textrm{finite}}}=1$ if $X$ is finite and $0$ , otherwise). Trivially, (1.2) ensures non-negativity of $\Delta_{X}^{a,b}$ on a finite graph. Moreover, when $X$ is $(q+1)$ -regular tree $T_{q+1}$ , (1.2) yields the inequality $b(q+1)-a\geq 2|b|\sqrt{q}$ , which ensures non-negativity of $\Delta_{X}^{a,b}$ on $T_{q+1}$ .

Furthermore, $\partial_{t}$ , for $t\in\ \mathbb{N}_{0}$ , denotes the forward difference operator

\partial_{t}u(t)=u(t+1)-u(t)\quad\text{and}\quad\partial_{t}^{2}u(t)=u(t+2)-2u(t+1)+u(t).

The generalized Laplacian $\Delta_{X}^{a,b}$ specializes to Laplace-type operators studied in [4, 12, 22, 23, 38, 42] for appropriately chosen values of $a,\,b$ satisfying (1.2).

The discrete time wave kernels associated with the operator $\Delta_{X}^{a,b}$ on the graph $X$ are two fundamental solutions $W_{X}^{a,b},\,V_{X}^{a,b}:V(X)\times V(X)\times\mathbb{N}_{0}\to\mathbb{R}$ of (1.1) satisfying the following initial conditions:

W_{X}^{a,b}(x_{0},x;0)=\begin{cases}1,&\text{if }x=x_{0},\\ 0,&\text{if }x\neq x_{0},\end{cases}\text{ and }\partial_{t}W_{X}^{a,b}(x_{0},x;0)=0,\,\,\forall x\in V(X),

(1.3)

and

V_{X}^{a,b}(x_{0},x;0)=0\text{ and }\partial_{t}V_{X}^{a,b}(x_{0},x;0)=\begin{cases}1,&\text{if }x=x_{0},\\ 0,&\text{if }x\neq x_{0},\end{cases}\,\,\forall x\in V(X).

(1.4)

1.2. Main results

Our first main result is an explicit evaluation of the discrete time wave kernels on any $(q+1)$ -regular graph in terms of the combinatorial graph data and the discrete $I$ -Bessel functions. The second main result is a trace-type formula which stems from the uniqueness of the wave kernel, by identifying the discrete time spectral realization of the wave kernel with its geometric/combinatorial evaluation.

1.2.1. Wave kernels on regular graphs

Let us first introduce some notation. Fix a base vertex $x_{0}\in V(X)$ . For any $x\in V(X)$ , let $c_{m}(x)$ be the number of non-backtracking walks of length $m$ from $x_{0}$ to $x$ , as defined in [13, Section 2.1]. For any $x\in V(X)$ let

b_{0}(x)=c_{0}(x),\qquad b_{1}(x)=c_{1}(x).

For $m\geq 2$ , let

b_{m}(x):=c_{m}(x)+(1-q)\big(c_{m-2}(x)+c_{m-4}(x)+\dots+c_{*}(x)\big),

(1.5)

where

c_{*}(x):=\begin{cases}c_{0}(x),&\text{if $m$ is even},\\ c_{1}(x),&\text{if $m$ is odd}.\end{cases}

(1.6)

If $X$ is vertex-transitive, let $N_{m}(x_{0})$ denote the number of non-backtracking walks of length $m$ from $x_{0}$ to itself without tails (meaning there is no immediate backtracking at the beginning or end of the walk, see [13, Section 2.1]). Our first main result is the following theorem.

Theorem 1.1.

Let $X$ be a $(q+1)$ -regular graph with a fixed base point $x_{0}$ . Let $a\in\mathbb{R}$ and $b\in\mathbb{R}\setminus\{0\}$ be such that (1.2) holds, and set $c_{a,b}=\dfrac{2b\sqrt{q}}{b(q+1)-a}$ and $d_{a,b}=b(q+1)-a$ . Then the discrete-time wave kernels $W_{X}^{a,b}(x_{0},x;t)$ and $V_{X}^{a,b}(x_{0},x;t)$ , associated with the operator $\Delta_{X}^{a,b}$ and satisfying the initial conditions (1.3) and (1.4), respectively, are given for $x\in V(X)$ and $t\in\mathbb{N}_{0}$ by

W_{X}^{a,b}(x_{0},x;t)=\sum_{k=0}^{\lfloor\tfrac{t}{2}\rfloor}(-1)^{k}\,\binom{t}{2k}\,d_{a,b}^{k}\sum_{m=0}^{k}(-1)^{m}b_{m}(x)\,q^{-\tfrac{m}{2}}\,I_{m}^{c_{a,b}}(k),

(1.7)

V_{X}^{a,b}(x_{0},x;t)=\sum_{k=0}^{\lfloor\tfrac{t-1}{2}\rfloor}(-1)^{k}\,\binom{t}{2k+1}\,d_{a,b}^{k}\sum_{m=0}^{k}(-1)^{m}b_{m}(x)\,q^{-\tfrac{m}{2}}\,I_{m}^{c_{a,b}}(k),

(1.8)

where $I_{m}^{c_{a,b}}$ denotes the discrete $I$ -Bessel function defined by (2.1) below.

Furthermore, if $x=x_{0}$ (so that $|x|=0$ ) and $X$ is vertex-transitive, then for all $t\in\mathbb{N}_{0}$ we have

W_{X}^{a,b}(x_{0},x_{0};t)=\sum_{k=0}^{\lfloor t/2\rfloor}(-1)^{k}\,\binom{t}{2k}\,d_{a,b}^{k}\bigg(\sum_{m=0}^{k}(-1)^{m}N_{m}(x_{0})\,q^{-\frac{m}{2}}\,I_{m}^{c_{a,b}}(k)\\ +(1-q)\sum_{j=1}^{\lfloor k/2\rfloor}q^{-j}I_{2j}^{c_{a,b}}(k)\bigg),

(1.9)

and

V_{X}^{a,b}(x_{0},x_{0};t)=\sum_{k=0}^{\lfloor(t-1)/2\rfloor}(-1)^{k}\,\binom{t}{2k+1}\,d_{a,b}^{k}\bigg(\sum_{m=0}^{k}(-1)^{m}N_{m}(x_{0})\,q^{-\tfrac{m}{2}}\,I_{m}^{c_{a,b}}(k)\\ +(1-q)\sum_{j=1}^{\lfloor k/2\rfloor}q^{-j}I_{2j}^{c_{a,b}}(k)\bigg).

(1.10)

1.2.2. Trace-type formula on regular graphs

Trace formulas on regular graphs, motivated by the Selberg trace formula on hyperbolic spaces [43] have been extensively studied in the past 40 years, see [1, 30, 40, 48, 49]. In this paper we obtain a ”physical” pre-trace formula which is based on utilizing the uniqueness of bounded solutions to the discrete wave equation in timescale $\mathbb{T}=\mathbb{Z}$ (see [44, Theorem 3.1.], or [2] and [21] for a general timescale analogue). The pre-trace formula is then refined using the explicit representation of the coefficients $b_{m}(x)$ obtained in Lemma 2.1 to deduce the following theorem.

Theorem 1.2.

Let $X$ be a finite $(q+1)$ -regular graph on $N=|V(X)|$ vertices with a fixed base point $x_{0}$ and let $0=\lambda_{1}\leq\ldots\leq\lambda_{N}=\lambda_{\max}$ be the eigenvalues of the combinatorial Laplacian $\Delta_{X}$ with the corresponding orthonormal eigenfunctions $\psi_{1},\ldots,\psi_{N}$ . Let $a\in\mathbb{R}$ and $b\in\mathbb{R}\setminus\{0\}$ be such that (1.2) holds true. Then, with the notation as above, for any positive integer $k$ and any $x\in V(X)$ we have the following identity:

\begin{split}\sum_{j=1}^{N}&\mu_{j}^{k}\psi_{j}(x_{0})\overline{\psi_{j}(x)}=d_{a,b}^{k}\sum_{m=0}^{k}(-1)^{m}b_{m}(x)\,q^{-\tfrac{m}{2}}\,I_{m}^{c_{a,b}}(k)\\ &=d_{a,b}^{k}\left(\delta_{x_{0}=x}I_{0}^{c_{a,b}}(k)+2\sum_{m=1}^{k}(-1)^{m}\Bigl[T_{m}\left(\frac{A}{2\sqrt{q}}\right)\delta_{x_{0}}\Bigr](x)\,I_{m}^{c_{a,b}}(k)\right),\end{split}

(1.11)

where $\mu_{j}=b\lambda_{j}-a\geq 0$ , $j=1,\ldots,N$ , $A$ is the adjacency matrix of $X$ , $T_{m}$ is the Chebyshev polynomial of the first kind and $\delta_{x_{0}}$ is the column vector of $N$ elements with all entries equal to $0$ , except for the entry corresponding to the vertex $x_{0}$ , which is equal to $1$ . For a column vector $\mathbf{a}$ and $x\in V(X)$ , $\mathbf{a}(x)$ denotes the entry of $\mathbf{a}$ corresponding to the vertex $x$ .

Moreover, if $X$ is vertex-transitive, then

\sum_{j=1}^{N}\mu_{j}^{k}=d_{a,b}^{k}\left(NI_{0}^{c_{a,b}}(k)+2\sum_{m=1}^{k}(-1)^{m}\mathrm{Tr}\Bigl[T_{m}\left(\frac{A}{2\sqrt{q}}\right)\Bigr]\,I_{m}^{c_{a,b}}(k)\right).

(1.12)

Remark 1.3.

The trace-type formula (1.11) is of a similar type as Theorem C of [30], meaning that it relates the spectrum of the Laplacian to the number of non-backtracking walks on a regular graph. Our trace formula does not involve a test function; however, it applies to a larger family of operators (generalized Laplacians $\Delta_{X}^{a,b}$ ). Moreover, it is of a different, ”physical” origin - it stems from the wave propagation properties, so we view it as a physical trace-type formula. An interested reader is referred to [13] for a trace formula stemming from the heat diffusion on a regular graph.

1.3. Applications

We present three applications of Theorem 1.2: to the discrete cycle on $n$ vertices, the complete graph on $n$ vertices and a $d$ -dimensional Hamming cube. In all three cases, we deduce interesting combinatorial identities.

An application to the discrete cycle on $n$ vertices yields the following two identities. For every $\ell\in\{1,\ldots,n-1\}$ , every positive integer $k$ , and every real number $c$ , one has

\frac{1}{n}\sum_{j=0}^{n-1}e^{-2\pi ij\ell/n}\left(2c\sin^{2}\!\left(\frac{\pi j}{n}\right)+1-c\right)^{k}=\underset{n\mid m\pm\ell}{\sum_{m\in\{1,\ldots,k\}}}(-1)^{m}I_{m}^{c}(k).

(1.13)

Moreover,

\frac{1}{n}\sum_{j=0}^{n-1}\left(2c\sin^{2}\!\left(\frac{\pi j}{n}\right)+1-c\right)^{k}=I_{0}^{c}(k)+2\sum_{s=1}^{\lfloor k/n\rfloor}(-1)^{sn}I_{sn}^{c}(k).

(1.14)

Trigonometric sums of the type (1.14) and (1.13) appear in many physical and combinatorial settings. For example, they arise in describing a system of coupled oscillators under acceleration [33] or in one-dimensional Ising model with nearest neighbor interactions [37, Chapter III]. In this paper, we provide another ”physical” interpretation/realization of these sums as a (pre-)trace of the wave kernel on a discrete cycle in discrete time which, in view of an explicit ”geometric” expression for the kernel, yields their explicit evaluation.

In [9, Remark 5.2], it is shown that

I_{m}^{1}(k)=2^{-k}\binom{2k}{k-m},\qquad 0\leq m\leq k.

(1.15)

Hence, (1.13) and (1.14), with $c=1$ , coincide with the formula obtained in [14, Corollary 11] for $\beta=0$ , and in this sense generalize the combinatorial results of [24, 25, 39]. See also [35] for a physical approach to secant and cosecant sums arising from heat diffusion.

Results similar to (1.14) and (1.13) can be obtained by applying Theorem 1.2 to any circulant graph. They will be studied in a follow-up paper.

An application to the complete graph on $n\geq 3$ vertices yields combinatorial identities relating Chebyshev polynomials and the discrete $I$ -Bessel functions. For example, for every real number $c$ , every $n\geq 3$ , and every $k\in\mathbb{N}$ , we prove that

\sum_{m=1}^{k}T_{m}\!\left(\frac{1}{2\sqrt{n-2}}\right)I_{m}^{c}(k)=\frac{1}{2}\left(1+\frac{c}{2\sqrt{n-2}}\right)^{k}-\frac{1}{2}I_{0}^{c}(k).

(1.16)

Taking $c=1$ in (1.16), using (1.15), and multiplying by $2^{k+1}$ we obtain an identity

2\sum_{m=1}^{k}\binom{2k}{k-m}T_{m}\!\left(\frac{1}{2\sqrt{n-2}}\right)=\left(2+\frac{1}{\sqrt{n-2}}\right)^{k}-\binom{2k}{k}.

Finally, when applying our results to the $d$ -dimensional hypercube, we deduce identities involving Chebyshev polynomials, discrete $I$ -Bessel functions and binomial coefficients. For example, Corollary 5.9 below with $c=2(d-1)^{-1/2}$ yields the following identity, which holds for all $d\geq 2$ , $1\leq r\leq d$ , and $k\in\mathbb{N}$ :

\sum_{j=0}^{d}K_{j}(r;d)\left(\frac{2j-1}{d-1}\right)^{k}=2\sum_{m=1}^{k}(-1)^{m}\sum_{s=0}^{d}K_{s}(r;d)T_{m}\!\left(\frac{d-2s}{2\sqrt{d-1}}\right)I_{m}^{\frac{2}{\sqrt{d-1}}}(k),

where

K_{j}(r;d)=\sum_{\ell=0}^{j}(-1)^{\ell}\binom{r}{\ell}\binom{d-r}{j-\ell}

is the $j$ -th Krawtchouk polynomial. (Recall that, by definition, $\binom{n}{k}=0$ for all non-negative integers $k,\,n$ such that $k>n$ .)

2. Preliminaries

In this section we introduce discrete Bessel functions, describe further notation needed in the sequel and prove a representation formula for the combinatorial quantities $b_{m}(x)$ related to numbers of non-backtracking walks of length $m$ .

2.1. Discrete Bessel functions

Discrete Bessel functions are introduced in [11] and further generalized and studied in [8, 13, 20, 21, 36, 45] in discrete timescales, including forward and backward difference operators. In this paper, we use the discrete $I$ -Bessel function on the timescale $\mathbb{Z}$ associated with the forward difference operator. This function can be expressed as

I^{c}_{n}(t)=\sum_{\ell=0}^{\lfloor(t-n)/2\rfloor}\frac{t!}{\ell!\,(t-2\ell-n)!\,(n+\ell)!}\left(\frac{c}{2}\right)^{2\ell+n},

(2.1)

for $t,n\in\mathbb{N}_{0}$ with $n\leq t$ , and $c\in\mathbb{C}$ . By convention, $I_{n}^{c}(t)=0$ for $n>t$ .

We refer the interested reader to the above references for further properties of discrete Bessel functions.

2.2. Wave kernels on a $(q+1)$ -regular tree

The universal cover of any $(q+1)$ -regular graph is a $(q+1)$ -regular tree (also known as the Bethe lattice with coordination number $q+1$ ), which is a connected $(q+1)$ -regular graph with no cycles. We denote such a tree by $T_{q+1}$ . In this section, we recall the main result of [9] in which the wave kernels on $T_{q+1}$ are explicitly computed. Given that $T_{q+1}$ is distance-transitive, the kernels depend only on the radial distance $r=d(x_{0},x)=|x|$ from the root $x_{0}$ . The solutions $W_{q+1}^{a,b}(r;t)$ and $V_{q+1}^{a,b}(r;t)$ of the wave equation (1.1) satisfying the initial conditions (1.3) and (1.4) are given by

W_{q+1}^{a,b}(r;t)=\sum_{k=0}^{\left\lfloor t/2\right\rfloor}(-1)^{k+r}\binom{t}{2k}d_{a,b}^{k}\bigg(q^{-\frac{r}{2}}I_{r}^{c_{a,b}}(k)\\ -(q-1)\sum_{\ell=1}^{\left\lfloor(k-r)/2\right\rfloor}q^{-\frac{r+2\ell}{2}}I_{r+2\ell}^{c_{a,b}}(k)\bigg),

(2.2)

and

V_{q+1}^{a,b}(r;t)=\sum_{k=0}^{\left\lfloor(t-1)/2\right\rfloor}(-1)^{k+r}\binom{t}{2k+1}d_{a,b}^{k}\bigg(q^{-\frac{r}{2}}I_{r}^{c_{a,b}}(k)\\ -(q-1)\sum_{\ell=1}^{\left\lfloor(k-r)/2\right\rfloor}q^{-\frac{r+2\ell}{2}}I_{r+2\ell}^{c_{a,b}}(k)\bigg),

where $c_{a,b}=\dfrac{2b\sqrt{q}}{b(q+1)-a}$ and $d_{a,b}=b(q+1)-a$ . These expressions provide the fundamental building blocks for our analysis on general $(q+1)$ -regular graphs.

2.3. Graph coverings

Recall that a graph $\widetilde{X}$ is called a covering graph of $X$ if there exists a map

\pi:V(\widetilde{X})\to V(X)

which locally preserves adjacency: for every vertex $\widetilde{x}\in V(\widetilde{X})$ , the neighbors of $\widetilde{x}$ are mapped bijectively onto the neighbors of $\pi(\widetilde{x})$ in $X$ .

In particular, if $X$ is a connected $(q+1)$ -regular graph, then its universal cover is the $(q+1)$ -regular tree $T_{q+1}$ with covering map

\pi:V(T_{q+1})\to V(X),

see sections 5 and 6 of [18] for more details.

Fix a lift $\widetilde{x}_{0}\in V(T_{q+1})$ of the base vertex $x_{0}\in V(X)$ . The covering map $\pi$ preserves adjacency locally, and therefore, for every $r\geq 0$ and every $x\in V(X)$ , the number of vertices $\widetilde{x}\in\pi^{-1}(x)$ satisfying

d_{T_{q+1}}(\widetilde{x}_{0},\widetilde{x})=r

is equal to the number $c_{r}(x)$ of non-backtracking walks in $X$ from $x_{0}$ to $x$ of length $r$ .

2.4. A representation formula for $b_{m}(x)$

The number $c_{m}(x)$ of non-backtracking walks of length $m$ from $x_{0}$ to $x$ is a well studied object in graph theory. Its generating function was deduced in [26], the exponential generating function was deduced and studied in [5] (see also [6] for a corresponding weighted graph result and [41] for the distributional result). However, despite an extensive literature search we could not find an expression for the coefficients $b_{m}(x)$ , though it might be folklore in graph theory. For this reason, we derive an explicit expression for the coefficients $b_{m}(x)$ directly in terms of the adjacency operator and Chebyshev polynomials.

Recall that $\delta_{x_{0}}$ is the column vector of $|V(X)|$ elements with zeros at all positions except at the one corresponding to $x_{0}$ , where it is equal to $1$ , and that for any column vector $\mathbf{a}$ we denote by $\mathbf{a}(x)$ the entry corresponding to the vertex $x$ . With this notation, we have the following lemma.

Lemma 2.1.

Let $X$ be a finite $(q+1)$ -regular graph with adjacency matrix $A$ and a fixed root $x_{0}\in V(X)$ . Let $c_{m}(x)$ be the number of non-backtracking walks of length $m$ from $x_{0}$ to $x$ . Then, for $m\geq 1$

b_{m}(x)=\left[2q^{m/2}T_{m}\!\left(\frac{A}{2\sqrt{q}}\right)\delta_{x_{0}}\right](x),

where $T_{m}(x)$ are Chebyshev polynomials of the first kind.

Proof.

For each $m\geq 0$ , let $\mathbf{c}_{m}=(c_{m}(x))_{x\in V(X)}$ denote the column vector whose $x$ -th component is the number of non-backtracking walks of length $m$ from $x_{0}$ to $x$ . Then

\mathbf{c}_{0}=\delta_{x_{0}},\qquad\mathbf{c}_{1}=A\delta_{x_{0}}.

Moreover, the vectors $\mathbf{c}_{m}$ satisfy the standard recurrence for non-backtracking walks on a $(q+1)$ -regular graph (see [13, Section 2.1]):

\mathbf{c}_{2}=A\mathbf{c}_{1}-(q+1)\mathbf{c}_{0},

and, for $m\geq 3$ ,

\mathbf{c}_{m}=A\mathbf{c}_{m-1}-q\mathbf{c}_{m-2}.

For $m\geq 0$ , let $\mathbf{b}_{m}$ denote the column vector whose $x$ -th component is $b_{m}(x)$ . Substituting the recurrence for $\mathbf{c}_{m}$ into the definition of $\mathbf{b}_{m}$ and collecting terms gives

\mathbf{b}_{m}=A\mathbf{b}_{m-1}-q\mathbf{b}_{m-2},\qquad m\geq 3,

with initial values

\mathbf{b}_{1}=A\delta_{x_{0}},\qquad\mathbf{b}_{2}=(A^{2}-2qI)\delta_{x_{0}}.

On the other hand, using the classical recurrence relation $T_{m}(x)=2xT_{m-1}(x)-T_{m-2}(x)$ [32, formula 8.941.1] for the Chebyshev polynomials of the first kind with $x=s/(2\sqrt{q})$ , we obtain that

\begin{split}P_{m}(s)&:=2q^{m/2}T_{m}\!\left(\frac{s}{2\sqrt{q}}\right)=2q^{m/2}\left[2\frac{s}{2\sqrt{q}}T_{m-1}\!\left(\frac{s}{2\sqrt{q}}\right)-T_{m-2}\!\left(\frac{s}{2\sqrt{q}}\right)\right]\\ &=sP_{m-1}(s)-qP_{m-2}(s).\end{split}

Moreover, since $T_{1}(x)=x$ and $T_{2}(x)=2x^{2}-1$ , we have

P_{1}(s)=s,\qquad P_{2}(s)=s^{2}-2q.

Substituting $s=A$ and multiplying by $\delta_{x_{0}}$ yields

P_{m}(A)\delta_{x_{0}}=A\,P_{m-1}(A)\delta_{x_{0}}-q\,P_{m-2}(A)\delta_{x_{0}}.

This proves that the sequence $\mathbf{u}_{m}:=P_{m}(A)\delta_{x_{0}}$ satisfies the recurrence

\mathbf{u}_{m}=A\mathbf{u}_{m-1}-q\mathbf{u}_{m-2},\quad m\geq 3.

Moreover,

\mathbf{u}_{1}=P_{1}(A)\delta_{x_{0}}=A\delta_{x_{0}}=\mathbf{b}_{1},

and

\mathbf{u}_{2}=P_{2}(A)\delta_{x_{0}}=(A^{2}-2qI)\delta_{x_{0}}=\mathbf{b}_{2}.

Therefore the sequences $\{\mathbf{u}_{m}\}$ and $\{\mathbf{b}_{m}\}$ satisfy the same second-order linear recurrence and have identical initial values. By uniqueness of solutions of the recurrence, it follows that

\mathbf{b}_{m}=P_{m}(A)\delta_{x_{0}},\qquad m\geq 1.

The proof is complete. ∎

For vertex-transitive graphs, combining Lemma 2.1 with a result of [13] yields the following formula.

Corollary 2.2.

Let $X$ be a finite vertex-transitive $(q+1)$ -regular graph. Then, for every $m\geq 2$ ,

N_{m}(x_{0})=\left[2q^{m/2}T_{m}\!\left(\frac{A}{2\sqrt{q}}\right)\delta_{x_{0}}\right](x_{0})+(q-1)\frac{1+(-1)^{m}}{2}.

(2.3)

Moreover, if $X$ is also bipartite then

\operatorname{Tr}T_{2m+1}\!\left(\frac{A}{2\sqrt{q}}\right)=0,

for all non-negative integers $m$ .

Proof.

By [13, Lemma 2.3(3)], one has $b_{0}(x_{0})=N_{0}(x_{0})=1$ , and for $m\geq 1$ ,

b_{m}(x_{0})=\begin{cases}N_{m}(x_{0})+(1-q),&\text{if $m$ is even},\\ N_{m}(x_{0}),&\text{if $m$ is odd},\end{cases}

(2.4)

which is equivalent to

N_{m}(x_{0})=b_{m}(x_{0})+(q-1)\frac{1+(-1)^{m}}{2},\quad m\geq 1.

Now, (2.3) follows from Lemma 2.1 with $x=x_{0}$ .

If $X$ is bipartite, every closed walk, and hence every closed non-backtracking walk without tails, on $X$ has even length. Therefore $N_{2m+1}(x_{0})=0$ for $m\geq 0$ . Since $X$ is vertex-transitive, every diagonal entry of $T_{m}(A/(2\sqrt{q}))$ is the same, hence

\left[T_{m}\!\left(\frac{A}{2\sqrt{q}}\right)\delta_{x_{0}}\right](x_{0})=\frac{1}{|V(X)|}\operatorname{Tr}T_{m}\!\left(\frac{A}{2\sqrt{q}}\right).

(2.5)

Thus, $N_{2m+1}(x_{0})=0$ combined with (2.3) proves the second statement. ∎

Remark 2.3.

For vertex-transitive graphs, Corollary 2.2 is consistent with Corollary 2 of [40]. More precisely, Corollary 2 of [40] gives the total number $\operatorname{\textbf{g}p}_{m}$ of closed non-backtracking walks of length $m\geq 1$ without tails on a regular graph as

\begin{split}\operatorname{\textbf{g}p}_{m}&=2q^{m/2}\sum_{j=1}^{|V(X)|}T_{m}\!\left(\frac{\theta_{j}}{2\sqrt{q}}\right)+\frac{1+(-1)^{m}}{2}(q-1)|V(X)|\\ &=2q^{m/2}\operatorname{Tr}T_{m}\!\left(\frac{A}{2\sqrt{q}}\right)+\frac{1+(-1)^{m}}{2}(q-1)|V(X)|,\end{split}

(2.6)

where $\theta_{j}$ , $j=1,\ldots,|V(X)|$ are the eigenvalues of the adjacency matrix.

If the graph is vertex-transitive, for $m\geq 1$ we have that $\operatorname{\textbf{g}p}_{m}=|V(X)|N_{m}(x_{0})$ , hence (2.6) may be rewritten as

N_{m}(x_{0})=\frac{2q^{m/2}}{|V(X)|}\operatorname{Tr}T_{m}\!\left(\frac{A}{2\sqrt{q}}\right)+(q-1)\frac{1+(-1)^{m}}{2}.

In view of (2.5), we deduce that Mnëv’s formula (2.6) is equivalent to (2.3).

Remark 2.4.

It is well known that formulas for the numbers of closed non-backtracking walks on regular graphs can also be obtained from the Ihara–Bass determinant formula and the spectral theory of the non-backtracking (Hashimoto) matrix; see, for example, [3, 27, 29]. The approach developed in this section is different, since it derives these quantities directly from the recurrence relation for non-backtracking walks and the resulting Chebyshev representation.

3. Proof of Theorem 1.1

Let $X$ be any $(q+1)$ -regular graph, and let $T_{q+1}$ denote its universal cover with the covering map $\pi$ . Fix a lift $\tilde{x}_{0}\in T_{q+1}$ of the vertex $x_{0}\in X$ . This covering map allows us to relate the wave kernels $W_{X}^{a,b}(x_{0},x;t)$ and $V_{X}^{a,b}(x_{0},x;t)$ on $X$ to the wave kernels on $T_{q+1}$ via

W_{X}^{a,b}(x_{0},x;t)=\sum_{\tilde{x}\in\pi^{-1}(x)}W^{a,b}_{q+1}(\tilde{x}_{0},\tilde{x};t),\quad V_{X}^{a,b}(x_{0},x;t)=\sum_{\tilde{x}\in\pi^{-1}(x)}V^{a,b}_{q+1}(\tilde{x}_{0},\tilde{x};t).

(3.1)

The number of vertices $\tilde{x}\in\pi^{-1}(x)$ at distance $r$ from $\tilde{x}_{0}$ equals the number $c_{r}(x)$ of non-backtracking walks of length $r$ from $x_{0}$ to $x$ in $X$ . In other words, $W^{a,b}_{q+1}(\tilde{x}_{0},\tilde{x};t)=W^{a,b}_{q+1}(r;t)$ and $V^{a,b}_{q+1}(\tilde{x}_{0},\tilde{x};t)=V^{a,b}_{q+1}(r;t)$ for exactly $c_{r}(x)$ vertices $\tilde{x}\in\pi^{-1}(x)$ , hence (3.1) becomes

W_{X}^{a,b}(x;t)=\sum_{r\geq 0}c_{r}(x)\,W^{a,b}_{q+1}(r;t),\quad V_{X}^{a,b}(x;t)=\sum_{r\geq 0}c_{r}(x)\,V^{a,b}_{q+1}(r;t),

(3.2)

where we write $W_{X}^{a,b}(x;t):=W_{X}^{a,b}(x_{0},x;t)$ and $V_{X}^{a,b}(x;t):=V_{X}^{a,b}(x_{0},x;t)$ since $x_{0}$ is fixed. Note that the sum in (3.2) is finite for each $t\in\mathbb{N}_{0}$ , because $W^{a,b}_{q+1}(r;t)=V^{a,b}_{q+1}(r;t)=0$ whenever $r>t$ .

We now prove equation (1.7); the proof of (1.8) is analogous. Equation (2.2) yields

W_{X}^{a,b}(x;t)=\sum_{r\geq 0}c_{r}(x)\sum_{k=0}^{\infty}(-1)^{k+r}\binom{t}{2k}d_{a,b}^{k}\bigg[q^{-\tfrac{r}{2}}I_{r}^{c_{a,b}}(k)\\ -(q-1)\sum_{\ell=1}^{\lfloor(k-r)/2\rfloor}q^{-\tfrac{r+2\ell}{2}}I_{r+2\ell}^{c_{a,b}}(k)\bigg].

Fix $m\in\mathbb{N}_{0}$ . For a given $k\geq m$ , the term $I_{m}^{c_{a,b}}(k)$ in the above sum appears when $m=r$ , as well as for all $\ell\in\{1,\dots,\lfloor(k-r)/2\rfloor\}$ such that $r+2\ell=m$ . This means that $I_{m}^{c_{a,b}}(k)$ collects contributions from walks of length $m$ that are either non-backtracking walks of length $m$ or are obtained from shorter non-backtracking walks by adding $2\ell$ extra steps.

Hence, the coefficient of $I_{m}^{c_{a,b}}(k)$ is given by

b_{m}(x)=c_{m}(x)+(1-q)\big(c_{m-2}(x)+c_{m-4}(x)+\dots+c_{*}(x)\big),

where $b_{m}(x)$ and $c_{*}(x)$ are as in (1.5)–(1.6).

Finally, if $X$ is $(q+1)$ -regular and vertex-transitive, combining (1.7) and (2.4) yields (1.9). The proof of (1.10) is analogous, so we omit it. ∎

4. Proof of Theorem 1.2

We start by recalling that, by the spectral theorem for self-adjoint operators (see, e.g., [17, Chapter 1]), the graph Laplacian admits an orthonormal basis of eigenfunctions $\{\psi_{j}\}$ with the corresponding eigenvalues $\{\lambda_{j}\}$ . Consequently,

\Delta_{X}^{a,b}=\sum_{j}(b\lambda_{j}-a)\,\psi_{j}\psi_{j}^{T}.

For $x,y\in V(X)$ let us define

\mathcal{W}_{X}^{a,b}(x,y;t)=\frac{1}{2}\sum_{j}\left[\left(1+i\sqrt{\mu_{j}}\right)^{t}+\left(1-i\sqrt{\mu_{j}}\right)^{t}\right]\psi_{j}(x)\overline{\psi_{j}(y)}.

(4.1)

(Recall that, by (1.2) we have $\mu_{j}\geq 0$ , $j=1,\ldots,N$ ). We have

\begin{split}\partial_{t}^{2}\mathcal{W}_{X}^{a,b}(x_{0},x;t)=&-\frac{1}{2}\sum_{j}\mu_{j}\left[\left(1+i\sqrt{\mu_{j}}\right)^{t}+\left(1-i\sqrt{\mu_{j}}\right)^{t}\right]\psi_{j}(x_{0})\overline{\psi_{j}(x)}\\ &=-\Delta_{X}^{a,b}\mathcal{W}_{X}^{a,b}(x_{0},x;t),\end{split}

where we used the fact that $\psi_{j}$ is the eigenfunction of $\Delta_{X}^{a,b}$ with the real eigenvalue $\mu_{j}$ . Therefore, $\mathcal{W}_{X}^{a,b}(x_{0},x;t)$ satisfies the wave equation (1.1). Moreover, $\mathcal{W}_{X}^{a,b}(x_{0},x;0)=\sum\limits_{j}\psi_{j}(x_{0})\overline{\psi_{j}(x)}=\delta_{x_{0}=x}$ . Trivially,

\partial_{t}\mathcal{W}_{X}^{a,b}(x_{0},x;t)\big|_{t=0}=\frac{i}{2}\sum_{j}\sqrt{\mu_{j}}\left[\left(1+i\sqrt{\mu_{j}}\right)^{0}-\left(1-i\sqrt{\mu_{j}}\right)^{0}\right]\psi_{j}(x_{0})\overline{\psi_{j}(x)}=0,

hence $\mathcal{W}_{X}^{a,b}(x_{0},x;t)$ also fulfills initial conditions (1.3). From the uniqueness of bounded solutions to the discrete wave equation in timescale $\mathbb{T}=\mathbb{Z}$ (see [44, Theorem 3.1.], or [2] and [21] for a general timescale analogue) we deduce that $\mathcal{W}_{X}^{a,b}(x_{0},x;t)=W_{X}^{a,b}(x_{0},x;t)$ for all $x\in V(X)$ .

By identifying (4.1) with (1.7) and applying the binomial theorem to the spectral side we get

\begin{split}W_{X}^{a,b}(x_{0},x;t)&=\sum_{k=0}^{\lfloor t/2\rfloor}(-1)^{k}\binom{t}{2k}\sum_{j=1}^{N}\mu_{j}^{k}\psi_{j}(x_{0})\overline{\psi_{j}(x)}\\ &=\sum_{k=0}^{\lfloor t/2\rfloor}(-1)^{k}\,\binom{t}{2k}\,d_{a,b}^{k}\sum_{m=0}^{k}(-1)^{m}b_{m}(x)\,q^{-\tfrac{m}{2}}\,I_{m}^{c_{a,b}}(k),\end{split}

for all integers $t\geq 0$ . The above identity is the identity between two binomial transforms. In view of the fact that the binomial transform is an involution, applying Lemma 2.1 for $m\geq 1$ and using that $b_{0}(x)=\delta_{x=x_{0}}$ , we immediately deduce (1.11).

When $X$ is vertex-transitive, we take $x=x_{0}$ in (1.11) and sum over all $x_{0}\in V(X)$ . Given that the basis $\{\psi_{j}\}_{j=1}^{N}$ is orthonormal, the left-hand side of (1.11) becomes $\sum_{j=1}^{N}\mu_{j}^{k}$ . Using (2.5), it is trivial to see that the sum over $x=x_{0}\in V(X)$ of the right-hand side of (1.11) equals the right-hand side of (1.12). The proof is complete. ∎

5. Applications of the trace-type formula

In this section, we apply Theorem 1.2 to three classes of finite vertex-transitive graphs: the cycle graph $C_{n}$ , the complete graph $K_{n}$ , and the $d$ -dimensional hypercube $Q_{d}$ . The spectral side of the trace type formula in those three cases is known. Using Lemma 2.1 we will be able to express coefficients $b_{m}(x)$ and $N_{m}(x_{0})$ in a closed form and derive interesting identities.

5.1. Cycle $C_{n}$

For the cycle graph $C_{n}$ on $n$ vertices, the coefficients $b_{m}(x_{\ell})$ and the numbers $N_{m}(x_{0})$ can be obtained directly from the definition of non-backtracking walks. We label the vertices of $C_{n}$ by $x_{j}=j$ , $j=0,\ldots,n-1$ . Trivially, $C_{n}$ is $2$ -regular, hence $q=1$ . A non-backtracking walk, once it chooses an initial direction, either clockwise or counterclockwise, is forced to continue in that direction, since the only alternative at each step would be an immediate backtracking move, which is forbidden.

Since $q=1$ for $C_{n}$ , the correction term in (1.5) vanishes. Thus, for every $x_{\ell}\in V(C_{n})$ , we have

b_{m}(x_{\ell})=c_{m}(x_{\ell}).

Moreover, a non-backtracking walk from $x_{0}$ to $x_{\ell}$ is forced to move in one of the two directions around the cycle. Hence

b_{m}(x_{\ell})=\begin{cases}1,&m=0,\ \ell=0,\\ 0,&m=0,\ \ell\neq 0,\\ \mathbf{1}_{m\equiv\ell\;(\mathrm{mod}\,n)}+\mathbf{1}_{m\equiv-\ell\;(\mathrm{mod}\,n)},&m\geq 1.\end{cases}

(5.1)

In particular, for $x_{\ell}=x_{0}$ , this gives the number of closed non-backtracking walks based at $x_{0}$ . Therefore, a closed non-backtracking walk returns to $x_{0}$ if and only if its length is a multiple of $n$ . In that case there are exactly two such walks, one in each direction, and no others. Together with the convention $N_{0}(x_{0})=1$ , we obtain

N_{m}(x_{0})=\begin{cases}1,&m=0,\\ 2,&n\mid m,\ m\geq 1,\\ 0,&\text{otherwise}.\end{cases}

(5.2)

Note that, for $\ell=0$ , the formula (5.1) reduces exactly to (5.2); hence $b_{m}(x_{0})=N_{m}(x_{0})$ for all $m\geq 0$ .

The following corollary gives an explicit representation of the discrete-time wave kernel on $C_{n}$ .

Corollary 5.1.

The discrete-time wave kernel on $C_{n}$ satisfying the initial condition (1.3) for all $t\in\mathbb{N}_{0}$ and $a\in\mathbb{R}$ , $b\in\mathbb{R}\setminus\{0\}$ satisfying (1.2) is given by

\begin{split}W_{C_{n}}^{a,b}(x_{0},x_{0};t)=\sum_{k=0}^{\lfloor t/2\rfloor}(-1)^{k}\binom{t}{2k}(2b-a)^{k}\Bigg(I_{0}^{\frac{2b}{2b-a}}(k)+2\sum_{j=1}^{\lfloor k/n\rfloor}(-1)^{jn}I_{jn}^{\frac{2b}{2b-a}}(k)\Bigg),\end{split}

(5.3)

and

\begin{split}W_{C_{n}}^{a,b}(x_{0},x_{\ell};t)=\sum_{k=0}^{\lfloor t/2\rfloor}(-1)^{k}\binom{t}{2k}(2b-a)^{k}\underset{n\mid m\pm\ell}{\sum_{m\in\{1,\ldots,k\}}}(-1)^{m}I_{m}^{\frac{2b}{2b-a}}(k),\end{split}

(5.4)

for $\ell\in\{1,\ldots,n-1\}$ .

Proof.

Using (5.2) in Theorem 1.1 with $q=1$ yields (5.3).

For $\ell\in\{1,\ldots,n-1\}$ , Theorem 1.1 gives

W_{C_{n}}^{a,b}(x_{0},x_{\ell};t)=\sum_{k=0}^{\lfloor t/2\rfloor}(-1)^{k}\binom{t}{2k}(2b-a)^{k}\sum_{m=0}^{k}(-1)^{m}b_{m}(x_{\ell})I_{m}^{\frac{2b}{2b-a}}(k).

Since $\ell\neq 0$ , we have $b_{0}(x_{\ell})=0$ . For $m\geq 1$ , by (5.1), only the indices $m$ that satisfy $m\equiv\ell\pmod{n}$ or $m\equiv-\ell\pmod{n}$ contribute to the sum. Therefore,

\sum_{m=0}^{k}(-1)^{m}b_{m}(x_{\ell})I_{m}^{\frac{2b}{2b-a}}(k)=\underset{n\mid m\pm\ell}{\sum_{m\in\{1,\ldots,k\}}}(-1)^{m}I_{m}^{\frac{2b}{2b-a}}(k).

(5.5)

Substituting this into the preceding identity yields (5.4).

∎

The explicit formulas obtained in Corollary 5.1 may now be combined with the Theorem 1.2 in order to derive spectral identities for the cycle graph $C_{n}$ .

Corollary 5.2.

Let $C_{n}$ be the cycle graph and $\ell\in\{1,\ldots,n-1\}$ . Then, for every $k\in\mathbb{N}_{0}$ and every real number $c$ the identities (1.13) and (1.14) hold.

Proof.

For the cycle graph $C_{n}$ , we have $|V(C_{n})|=n$ and $q=1$ . The normalized eigenfunctions of the combinatorial Laplacian are $\psi_{j}(x_{r})=\frac{1}{\sqrt{n}}e^{2\pi ijr/n}$ , $j,r=0,\ldots,n-1$ , hence

\psi_{j}(x_{0})\overline{\psi_{j}(x_{\ell})}=\frac{1}{n}e^{-2\pi ij\ell/n}.

Moreover, the eigenvalues of the combinatorial graph Laplacian on $C_{n}$ are $\lambda_{j}=4\sin^{2}\!\left(\frac{\pi j}{n}\right)$ , $j=0,\ldots,n-1$ ; hence the eigenvalues of $\Delta_{C_{n}}^{a,b}=b\Delta_{C_{n}}-aI$ are

\mu_{j}=4b\sin^{2}\!\left(\frac{\pi j}{n}\right)-a,\qquad j=0,\ldots,n-1.

Let $a\in\mathbb{R}$ and $b\in\mathbb{R}\setminus\{0\}$ be such that (1.2) holds. From (1.11) combined with (5.1) and (5.5), by setting $c=\frac{2b}{2b-a}$ we obtain (1.13). The identity (1.14) follows from the same argument with $x=x_{0}$ , using (5.2) in place of (5.1).

This proves (1.13) and (1.14) for $c=\frac{2b}{2b-a}$ where $a,\,b\neq 0$ satisfy (1.2). In view of (2.1), both sides of identities (1.13) and (1.14) are polynomials in $c$ which are equal for infinitely many values of $c$ , hence they are equal for all $c\in\mathbb{R}$ by the identity theorem for polynomials. ∎

Taking $c=1$ in (1.13) and (1.14) and using (1.15) we immediately deduce the following corollary.

Corollary 5.3.

For every $k\in\mathbb{N}$ and $\ell=1,\ldots,n-1$ , one has

\sum_{j=0}^{n-1}e^{-2\pi ij\ell/n}\sin^{2k}\!\left(\frac{\pi j}{n}\right)=\frac{n}{2^{2k}}\underset{n\mid m\pm\ell}{\sum_{m\in\{1,\ldots,k\}}}(-1)^{m}\binom{2k}{k-m}.

Moreover, for every $k\in\mathbb{N}$ , one has

\sum_{j=0}^{n-1}\sin^{2k}\!\left(\frac{\pi j}{n}\right)=\frac{n}{2^{2k}}\left(\binom{2k}{k}+2\sum_{\ell=1}^{\lfloor k/n\rfloor}(-1)^{\ell n}\binom{2k}{k-\ell n}\right).

5.2. Complete graph $K_{n}$

Let $n\geq 3$ . For the complete graph $K_{n}$ we have

|V(K_{n})|=n,\qquad\deg(x_{0})=n-1,\qquad q=n-2.

The adjacency matrix of $K_{n}$ is $A=J-I$ , where $J$ denotes the $n\times n$ matrix with all entries equal to one and $I$ is the $n$ -dimensional identity matrix. The spectrum of the adjacency matrix is given by

\sigma(A)=\{n-1\ (\text{multiplicity }1),\ -1\ (\text{multiplicity }n-1)\};

see, for example, [17, Chapter 1].

In the following lemma we give explicit formulas for $b_{m}(x_{\ell})$ and $N_{m}(x_{0})$ on the complete graph $K_{n}$ in terms of the Chebyshev polynomials $T_{m}$ .

Lemma 5.4.

Let $K_{n}$ be the complete graph with vertices $x_{0},x_{1},\ldots,x_{n-1}$ . Then, $b_{0}(x_{\ell})=1$ if and only if $\ell=0$ and equal to zero, otherwise. For $m\geq 1$ we have that

b_{m}(x_{\ell})=\frac{2(n-2)^{m/2}}{n}\left[T_{m}\!\left(\frac{n-1}{2\sqrt{n-2}}\right)+\eta_{\ell}T_{m}\!\left(-\frac{1}{2\sqrt{n-2}}\right)\right],

(5.6)

where

\eta_{\ell}=\begin{cases}n-1,&\ell=0,\\ -1,&\ell=1,\ldots,n-1,\end{cases}

and

\begin{split}N_{m}(x_{0})&=\frac{2(n-2)^{m/2}}{n}\left[T_{m}\!\left(\frac{n-1}{2\sqrt{n-2}}\right)+(n-1)T_{m}\!\left(-\frac{1}{2\sqrt{n-2}}\right)\right]\\ &\qquad+\frac{1+(-1)^{m}}{2}(n-3).\end{split}

(5.7)

Proof.

The spectral projection decomposition of the adjacency matrix $A$ is

A=(n-1)P_{0}-P_{1},

where

P_{0}=\frac{1}{n}J,\qquad P_{1}=I-\frac{1}{n}J

are orthogonal projection matrices. Hence, for any polynomial $p$ ,

p(A)=p(n-1)P_{0}+p(-1)P_{1}.

By Lemma 2.1 we have

	$\displaystyle b_{m}(x)$	$\displaystyle=\left[2(n-2)^{m/2}T_{m}\!\left(\frac{A}{2\sqrt{n-2}}\right)\delta_{x_{0}}\right](x)$
		$\displaystyle=2(n-2)^{m/2}\left[T_{m}\!\left(\frac{n-1}{2\sqrt{n-2}}\right)P_{0}\delta_{x_{0}}+T_{m}\!\left(\frac{-1}{2\sqrt{n-2}}\right)P_{1}\delta_{x_{0}}\right](x).$

Equation (5.6) follows by observing that

P_{0}\delta_{x_{0}}(x_{\ell})=\frac{1}{n},\qquad P_{1}\delta_{x_{0}}(x_{\ell})=\delta_{\ell,0}-\frac{1}{n}.

Now we deduce (5.7). Taking $\ell=0$ in (5.6) gives

b_{m}(x_{0})=\frac{2(n-2)^{m/2}}{n}\left[T_{m}\!\left(\frac{n-1}{2\sqrt{n-2}}\right)+(n-1)T_{m}\!\left(-\frac{1}{2\sqrt{n-2}}\right)\right].

Combining this with Corollary 2.2 with $q=n-2$ yields (5.7) for $m\geq 2$ . For $m=1$ , the right-hand side of (5.7) becomes

\begin{split}\frac{2\sqrt{n-2}}{n}\left[\frac{n-1}{2\sqrt{n-2}}+(n-1)\left(-\frac{1}{2\sqrt{n-2}}\right)\right]=0.\end{split}

Given that there are no closed non-backtracking walks of length $1$ in $K_{n}$ , $N_{1}(x_{0})=0$ , hence the identity (5.7) holds true for all $m\geq 1$ . ∎

Using the eigenfunctions of the combinatorial Laplacian on $K_{n}$ , Lemma 5.4 yields the following identities giving closed summation formulas for sums of products of Chebyshev polynomials and discrete $I$ -Bessel functions.

Corollary 5.5.

Let $n\geq 3$ . Then, for every $k\in\mathbb{N}_{0}$ and every real number $c$ , one has

\begin{split}\sum_{m=1}^{k}(-1)^{m}&\left(T_{m}\!\left(\frac{n-1}{2\sqrt{n-2}}\right)-T_{m}\!\left(-\frac{1}{2\sqrt{n-2}}\right)\right)I_{m}^{c}(k)\\ &\qquad=\frac{1}{2}\left[\left(1-\frac{(n-1)c}{2\sqrt{n-2}}\right)^{k}-\left(1+\frac{c}{2\sqrt{n-2}}\right)^{k}\right],\end{split}

(5.8)

and

\begin{split}\sum_{m=1}^{k}&(-1)^{m}\left(T_{m}\!\left(\frac{n-1}{2\sqrt{n-2}}\right)+(n-1)T_{m}\!\left(-\frac{1}{2\sqrt{n-2}}\right)\right)I_{m}^{c}(k)\\ &\quad=\frac{1}{2}\left[\left(1-\frac{(n-1)c}{2\sqrt{n-2}}\right)^{k}+(n-1)\left(1+\frac{c}{2\sqrt{n-2}}\right)^{k}\right]-\frac{n}{2}I_{0}^{c}(k).\end{split}

(5.9)

Proof.

An orthonormal basis of eigenfunctions of the combinatorial Laplacian on $K_{n}$ is given by

\psi_{j}(x_{\ell})=\frac{1}{\sqrt{n}}e^{2\pi ij\ell/n},\qquad j,\ell=0,\ldots,n-1.

Here $\psi_{0}$ corresponds to the eigenvalue $0$ , while $\psi_{j}$ , $j=1,\ldots,n-1$ , correspond to the eigenvalue $n$ . Hence the eigenvalues of $\Delta_{K_{n}}^{a,b}=b\Delta_{K_{n}}-aI$ are

\mu_{0}=-a,\qquad\mu_{j}=bn-a,\quad j=1,\ldots,n-1.

Moreover,

\psi_{j}(x_{0})\overline{\psi_{j}(x_{\ell})}=\frac{1}{n}e^{-2\pi ij\ell/n}.

Substituting this into (1.11) with $x=x_{\ell}$ and $q=n-2$ yields that for every $k\in\mathbb{N}_{0}$ , $a\in\mathbb{R}$ , $b\in\mathbb{R}\setminus\{0\}$ satisfying (1.2) and $\ell=0,\ldots,n-1$ ,

\sum_{j=0}^{n-1}e^{-2\pi ij\ell/n}\mu_{j}^{k}=n(b(n-1)-a)^{k}\sum_{m=0}^{k}(-1)^{m}b_{m}(x_{\ell})(n-2)^{-m/2}I_{m}^{c_{a,b}(n)}(k).

Substituting the coefficients $b_{m}(x_{\ell})$ from (5.6) into this identity and simplifying gives that

\sum_{j=0}^{n-1}e^{-2\pi ij\ell/n}\mu_{j}^{k}=n(b(n-1)-a)^{k}\Bigg[\delta_{\ell,0}I_{0}^{c_{a,b}(n)}(k)\\ \quad+\frac{2}{n}\sum_{m=1}^{k}(-1)^{m}\left(T_{m}\!\left(\frac{n-1}{2\sqrt{n-2}}\right)+\eta_{\ell}T_{m}\!\left(-\frac{1}{2\sqrt{n-2}}\right)\right)I_{m}^{c_{a,b}(n)}(k)\Bigg].

(5.10)

For $\ell\in\{1,\ldots,n-1\}$ , we have $\eta_{\ell}=-1$ . Moreover,

\sum_{j=1}^{n-1}e^{-2\pi ij\ell/n}=-1.

Since $\mu_{0}=-a$ , $\mu_{j}=bn-a$ for $j=1,\ldots,n-1$ , it follows that

\sum_{j=0}^{n-1}e^{-2\pi ij\ell/n}\mu_{j}^{k}=(-a)^{k}-(bn-a)^{k}.

Taking $\ell\in\{1,\ldots,n-1\}$ in (5.10), we obtain

\sum_{m=1}^{k}(-1)^{m}\left(T_{m}\!\left(\frac{n-1}{2\sqrt{n-2}}\right)-T_{m}\!\left(-\frac{1}{2\sqrt{n-2}}\right)\right)I_{m}^{c_{a,b}(n)}(k)=\frac{(-a)^{k}-(bn-a)^{k}}{2(b(n-1)-a)^{k}}.

Taking $\ell=0$ in (5.10) and observing that $\eta_{0}=n-1$ , and

\sum_{j=0}^{n-1}\mu_{j}^{k}=(-a)^{k}+(n-1)(bn-a)^{k},

we obtain

\sum_{m=1}^{k}(-1)^{m}\left(T_{m}\!\left(\frac{n-1}{2\sqrt{n-2}}\right)+(n-1)T_{m}\!\left(-\frac{1}{2\sqrt{n-2}}\right)\right)I_{m}^{c_{a,b}(n)}(k)\\ =\frac{(-a)^{k}+(n-1)(bn-a)^{k}}{2(b(n-1)-a)^{k}}-\frac{n}{2}I_{0}^{c_{a,b}(n)}(k).

Now put $D=b(n-1)-a$ and $c=\frac{2b\sqrt{n-2}}{D}$ . Then

-a=D\left(1-\frac{(n-1)c}{2\sqrt{n-2}}\right),\qquad bn-a=D\left(1+\frac{c}{2\sqrt{n-2}}\right).

Substituting these relations into the last two displayed identities gives the stated formulas valid in the range of $c$ for which $a,\,b$ satisfy (1.2). This range contains infinitely many $c$ , and hence extension to all real $c$ follows from the fact that both sides of equations (5.8) and (5.9) are polynomials in $c$ . ∎

Proof of (1.16). The identity follows by subtracting (5.8) from (5.9), dividing by $n$ , and using that $T_{m}(-x)=(-1)^{m}T_{m}(x)$ .

5.3. $d$ -dimensional hypercube $Q_{d}$

Let $d\geq 2$ . The $d$ -dimensional hypercube $Q_{d}$ is a $d$ -regular graph with $|V(Q_{d})|=2^{d}$ vertices. We identify its vertex set with $\{0,1\}^{d}$ . The eigenvalues of the combinatorial Laplacian on $Q_{d}$ are $\lambda_{j}=2j$ , $j=0,1,\ldots,d$ , with multiplicity $\binom{d}{j}$ . Hence the eigenvalues of $\Delta_{Q_{d}}^{a,b}=b\Delta_{Q_{d}}-aI$ are

2bj-a,\qquad j=0,1,\ldots,d,

with multiplicity $\binom{d}{j}$ .

We fix $x_{0}=(0,\ldots,0)$ . In the following lemma, for all $x\in V(Q_{d})$ we explicitly compute the combinatorial quantities $b_{m}(x)$ and $N_{m}(x_{0})$ .

Lemma 5.6.

Let $Q_{d}$ be the $d$ -dimensional hypercube. For $x\in V(Q_{d})$ , let $r=d(x_{0},x)=|x|$ . For every $m\geq 1$ ,

b_{m}(x)=\frac{(d-1)^{m/2}}{2^{d-1}}\sum_{j=0}^{d}K_{j}(r;d)T_{m}\!\left(\frac{d-2j}{2\sqrt{d-1}}\right),

(5.11)

where $K_{j}(r;d)$ is the $j$ -th Krawtchouk polynomial.

In particular, for every $m\geq 1$ , the number $N_{m}(x_{0})$ of closed non-backtracking walks of length $m$ without tails starting at $x_{0}$ is

N_{m}(x_{0})=\frac{(d-1)^{m/2}}{2^{d-1}}\sum_{j=0}^{d}\binom{d}{j}T_{m}\!\left(\frac{d-2j}{2\sqrt{d-1}}\right)+\frac{1+(-1)^{m}}{2}(d-2).

(5.12)

Proof.

For $\alpha=(\alpha_{1},\ldots,\alpha_{d})\in\{0,1\}^{d}$ , define

\psi_{\alpha}(x)=(-1)^{\alpha\cdot x},\qquad\alpha\cdot x=\alpha_{1}x_{1}+\cdots+\alpha_{d}x_{d}.

Then the family $\{2^{-d/2}\psi_{\alpha}\}_{\alpha\in\{0,1\}^{d}}$ is an orthonormal basis of eigenfunctions of the adjacency operator on $Q_{d}$ . A direct computation shows that

A\psi_{\alpha}=(d-2|\alpha|)\psi_{\alpha},

where $|\alpha|=\alpha_{1}+\cdots+\alpha_{d}$ . For $m\geq 1$ , by Lemma 2.1

b_{m}(x)=\left[2(d-1)^{m/2}T_{m}\!\left(\frac{A}{2\sqrt{d-1}}\right)\delta_{x_{0}}\right](x).

Using the spectral decomposition of $A$ with respect to the basis $\{2^{-d/2}\psi_{\alpha}\}_{\alpha\in\{0,1\}^{d}}$ , we obtain

b_{m}(x)=\frac{(d-1)^{m/2}}{2^{d-1}}\sum_{\alpha\in\{0,1\}^{d}}T_{m}\!\left(\frac{d-2|\alpha|}{2\sqrt{d-1}}\right)(-1)^{\alpha\cdot x}.

Grouping the terms according to $j=|\alpha|$ , we obtain

b_{m}(x)=\frac{(d-1)^{m/2}}{2^{d-1}}\sum_{j=0}^{d}T_{m}\!\left(\frac{d-2j}{2\sqrt{d-1}}\right)\sum_{|\alpha|=j}(-1)^{\alpha\cdot x}.

If $|x|=r$ , then $\alpha\cdot x$ equals the number of coordinates at which both $\alpha$ and $x$ are equal to $1$ . If this number is $\ell$ , then there are $\binom{r}{\ell}\binom{d-r}{j-\ell}$ such vectors $\alpha$ , and in this case $(-1)^{\alpha\cdot x}=(-1)^{\ell}$ . Therefore

\sum_{|\alpha|=j}(-1)^{\alpha\cdot x}=\sum_{\ell=0}^{j}(-1)^{\ell}\binom{r}{\ell}\binom{d-r}{j-\ell}=K_{j}(r;d),

where $K_{j}(r;d)$ is the $j$ -th Krawtchouk polynomial of the binary Hamming scheme (see, e.g., [7, Section 3.2]). This proves the formula for $b_{m}(x)$ .

Taking $x=x_{0}$ , we have $r=0$ , and hence $K_{j}(0;d)=\binom{d}{j}$ . Therefore

b_{m}(x_{0})=\frac{(d-1)^{m/2}}{2^{d-1}}\sum_{j=0}^{d}\binom{d}{j}T_{m}\!\left(\frac{d-2j}{2\sqrt{d-1}}\right).

Since $Q_{d}$ is vertex-transitive and $q=d-1$ , Corollary 2.2 gives the formula for $N_{m}(x_{0})$ for $m\geq 2$ . For $m=1$ , the right-hand side of (5.12) is zero, which agrees with the fact that $Q_{d}$ has no loops. Hence (5.12) holds for all $m\geq 1$ . ∎

As an immediate consequence of the bipartite structure of the hypercube, together with (5.12) and Corollary 2.2, one obtains the following identity for Chebyshev polynomials.

Corollary 5.7.

For every $d\geq 2$ and every $m\geq 0$ , one has

\sum_{j=0}^{d}\binom{d}{j}T_{2m+1}\!\left(\frac{d-2j}{2\sqrt{d-1}}\right)=0.

Remark 5.8.

The identity of the previous corollary can also be derived directly from the spectrum of the hypercube. Indeed, the adjacency eigenvalues of $Q_{d}$ are $\theta_{j}=d-2j$ , $j=0,1,\ldots,d$ , with multiplicity $\binom{d}{j}$ . Since

\theta_{d-j}=-(d-2j)=-\theta_{j}\quad\text{and}\quad\binom{d}{d-j}=\binom{d}{j},

the spectrum is symmetric with respect to the origin. Moreover, $T_{2m+1}$ is an odd polynomial. Consequently, the terms corresponding to $j$ and $d-j$ cancel pairwise, which yields the identity.

Using the formula for $b_{m}(x)$ in (1.11) and grouping the spectral side by Hamming weights, we obtain the following twisted Krawtchouk–Chebyshev identity.

Corollary 5.9.

Let $d\geq 2$ and let $1\leq r\leq d$ . Then, for every $k\in\mathbb{N}$ and every real number $c$ , one has

\sum_{j=0}^{d}K_{j}(r;d)\left(1+\frac{2j-d}{2\sqrt{d-1}}\,c\right)^{k}=2\sum_{m=1}^{k}(-1)^{m}\sum_{s=0}^{d}K_{s}(r;d)T_{m}\!\left(\frac{d-2s}{2\sqrt{d-1}}\right)I_{m}^{c}(k).

(5.13)

Proof.

We want to apply (1.11) to the hypercube $Q_{d}$ . Choose $x\in V(Q_{d})$ such that $|x|=r$ . For any $\alpha\in\{0,1\}^{d}$ , the corresponding eigenvalue of $\Delta_{Q_{d}}^{a,b}$ is $\mu_{\alpha}=2b|\alpha|-a$ . Therefore, after multiplying by $2^{d}$ , the spectral side of (1.11) becomes

\sum_{\alpha\in\{0,1\}^{d}}(2b|\alpha|-a)^{k}(-1)^{\alpha\cdot x}=\sum_{j=0}^{d}(2bj-a)^{k}K_{j}(r;d),\qquad k\geq 0.

Hence (1.11) yields

\sum_{j=0}^{d}K_{j}(r;d)(2bj-a)^{k}=2^{d}(bd-a)^{k}\sum_{m=0}^{k}(-1)^{m}b_{m}(x)(d-1)^{-m/2}I_{m}^{c_{a,b}(d)}(k),

for all $a,\,b$ satisfying (1.2), where $c_{a,b}(d)=\frac{2b\sqrt{d-1}}{bd-a}$ . Since $r>0$ , we have $b_{0}(x)=0$ . Substituting (5.11) into the above identity and simplifying, we obtain

\sum_{j=0}^{d}K_{j}(r;d)(2bj-a)^{k}=2(bd-a)^{k}\sum_{m=1}^{k}(-1)^{m}\sum_{s=0}^{d}K_{s}(r;d)T_{m}\!\left(\frac{d-2s}{2\sqrt{d-1}}\right)I_{m}^{c_{a,b}(d)}(k).

Dividing by $(bd-a)^{k}$ and introducing $c=\frac{2b\sqrt{d-1}}{bd-a}$ , we obtain

2bj-a=(bd-a)\left(1+\frac{2j-d}{2\sqrt{d-1}}\,c\right),

and therefore (5.13) holds true for all $c=\frac{2b\sqrt{d-1}}{bd-a}$ for which $a,\,b$ satisfy (1.2). This range contains infinitely many $c$ , and hence extension to all real $c$ follows from the fact that both sides of the identity (5.13) are polynomials in $c$ . ∎

References

[1] G. Ahumada, Fonctions périodiques et formule des traces de Selberg sur les arbres, C. R. Acad. Sci. Paris Sér. I Math., 305 (16) (1987), 709–712.
[2] D. Anderson, J. Bullock, L. Erbe, A. Peterson, H. Tran, Nabla dynamic equations on time scales, Panam. Math. J. 13 (2003), no. 1, 1–47.
[3] O. Angel, J. Friedman, S. Hoory, The non-backtracking spectrum of the universal cover of a graph, Trans. Am. Math. Soc. 367 (2015), no. 6, 4287–4318.
[4] J. -P. Anker, P. Martinot, E. Pedon, A. G. Setti, The shifted wave equation on Damek-Ricci spaces and on homogeneous trees, Trends in harmonic analysis, 1–25, Springer INdAM Ser., 3, Springer, Milan, 2013.
[5] F. Arrigo, P. Grindrod, D. J. Higham, V. Noferini, On the exponential generating function for non-backtracking walks, Linear Algebra Appl. 556 (2018), 381–399.
[6] F. Arrigo, D. J. Higham, V. Noferini, R. Wood, Weighted enumeration of nonbacktracking walks on weighted graphs, SIAM J. Matrix Anal. Appl. 45 (2024), no. 1, 397–418.
[7] E. Bannai, T. Ito, Algebraic Combinatorics I: Association Schemes, Benjamin/Cummings Publishing Company, Menlo Park, CA, 1984.
[8] A. Bašić, L. Smajlović, Z. Šabanac, Discrete Bessel functions and discrete wave equation, Results Math. 79 (2024), no. 5, Paper no. 216, 25 pp.
[9] A. Bašić, L. Smajlović, Z. Šabanac, Discrete space–time wave kernels on regular trees, submitted 2026.
[10] H. S. Bhat, B. Osting, Kirchhoff’s Laws as a Finite Volume Method for the Planar Maxwell Equations, IEEE Transactions on Microwave Theory and Techniques, 59 (2) (2011), 235–245.
[11] M. Bohner, T. Cuchta, The Bessel difference equation, Proc. Am. Math. Soc., 145 (4) (2017), 1567–1580.
[12] S. Brooks, E. Lindenstrauss, Non-localization of eigenfunctions on large regular graphs, Israel J. Math. 193 (2013), no. 1, 1–14.
[13] C. A. Cadavid, P. Hoyos, J. Jorgenson, L. Smajlović, J. D. Vélez, Discrete diffusion-type equation on regular graphs and its applications, J. Difference Equ. Appl. 29 (2023), no. 4, 455–488.
[14] C. A. Cadavid, P. Hoyos, J. Jorgenson, L. Smajlović, J. D. Vélez, On an approach for evaluating certain trigonometric character sums using the discrete time heat kernel, Eur. J. Comb. 108 (2023), Article ID 103635, 23 pp.
[15] V. L. Chernyshev, V. E. Nazaikinskii, A. V. Tsvetkova, Lattice equations and semiclassical asymptotics, Russ. J. Math. Phys. 30 (2023), no. 2, 152–164.
[16] M.-J. Choi, A condition for blow-up solutions to discrete semilinear wave equations on networks, Appl. Anal. 101 (2022), no. 6, 2008–2018.
[17] F. R. K. Chung, Spectral Graph Theory, CBMS Regional Conference Series in Mathematics, 1997.
[18] F. Chung, S.-T. Yau, Coverings, heat kernels and spanning trees, Electron. J. Comb. 6 (1999), Research Paper vol. 12, 21 pp.
[19] J. M. Cohen, M. Pagliacci, Explicit solutions for the wave equation on homogeneous trees, Adv. in Appl. Math. 15 (1994), no. 4, 390–403.
[20] T. Cuchta, Discrete analogues of some classical special functions (2015). Doctoral Dissertation, Missouri University of Science and Technology.
[21] T. Cuchta, A. Slavík, Bessel functions on time scales and applications to partial dynamic equations, Monatsh. Math. 209 (2026), no. 4, 563–583.
[22] D. Cvetković, P. Rowlinson, S. K. Simić, Signless Laplacians of finite graphs, Linear Algebra Appl. 423 (2007), no. 1, 155–171.
[23] F. Dörfler, J. W. Simpson-Porco, F. Bullo, Electrical Networks and Algebraic Graph Theory: Models, Properties, and Applications, Proceedings of the IEEE 106 (2018), no. 5, 977–1005.
[24] C. M. da Fonseca, V. Kowalenko, On a finite sum with powers of cosines, Appl. Anal. Discrete Math. 7 (2) (2013), 354–377.
[25] C. M. da Fonseca, M. L. Glasser, V. Kowalenko, Basic trigonometric power sums with applications, Ramanujan J. 42 (2) (2017), 401–428.
[26] J. Friedman, On the second eigenvalue and random walks in random $d$ -regular graphs, Combinatorica 11 (4) (1991), 331–362.
[27] J. Friedman, D. Puder, A note on the trace method for random regular graphs, Israel J. Math. 256 (2023), no. 1, 269–282.
[28] J. Friedman, J.–P. Tillich, Wave equations for graphs and the edge-based Laplacian, Pac. J. Math. 216 (2004), no. 2, 229–266.
[29] C. Glover, M. Kempton, Some spectral properties of the non-backtracking matrix of a graph, Linear Algebra Appl. 618 (2021), 37–57.
[30] Y. Gong, W. Li, S. Liu, Discrete trace formulas and holomorphic functional calculus for the adjacency matrix of regular graphs, Preprint, arXiv:2406.17505 [math.CO] (2026).
[31] F. Gonzalez, A. Nebeker, K. Hallett, A. Sailstad, The Snapshot Problem for Wave Equations on Homogeneous Trees, Preprint, arXiv:2512.19136 (2025).
[32] I. S. Gradschteyn, I. M. Ryzhik, Table of integrals, series, and products, Translated from the Russian. Translation Edited and with a Preface by Alan Jeffrey and Daniel Zwillinger, 7th ed., Elsevier/Academic Press, Amsterdam, 2007.
[33] S. R. Holcombe, Falling coupled oscillators and trigonometric sums, Z. Angew. Math. Phys. 69 (2018), paper 19.
[34] G. ’t Hooft, How quantization of gravity leads to a discrete space-time, J. Phys. Conf. Ser. 701 (2016), 012014.
[35] J. Jorgenson, A. Karlsson, L. Smajlović, The resolvent kernel on the discrete circle and twisted cosecant sums, J. Math. Anal. Appl. 538 (2024), no. 2, Article no. 128454, 23 pp.
[36] N. Kan, K. Shiraishi, Discrete time heat kernel and UV modified propagators with dimensional deconstruction, J. Phys. A, Math. Theor. 56 (2023), no. 24, Article ID 245401, 16 pp.
[37] B. M. McCoy, T. T. Wu, The two-dimensional Ising model, 2nd corrected reprint edition, Dover Publications, Mineola, NY, 2014.
[38] G. Medolla, A. G. Setti, The wave equation on homogeneous trees, Ann. Mat. Pura Appl. (4) 176 (1999), 1–27.
[39] M. Merca, A note on cosine power sums, J. Integer Seq. 15 (5) (2012), Article 12.5.3, 7 pp.
[40] P. Mnëv, Discrete Path Integral Approach to the Selberg Trace Formula for Regular Graphs, Commun. Math. Phys. 274 (2007), 233–241.
[41] I. Oren, U. Smilansky, Periodic walks on large regular graphs and random matrix theory, Exp. Math. 23 (2014), no. 4, 492–498.
[42] C. Peterson, The discrete wave equation with applications to scattering theory and quantum chaos, Preprint, arXiv:2512.03015 (2025).
[43] A. Selberg, Harmonic analysis and discontinuous groups in weakly symmetric Riemannian spaces with applications to Dirichlet series, J. Indian Math. Soc. (N.S.) 20 (1956), 47–87.
[44] A. Slavík, Discrete-space systems of partial dynamic equations and discrete-space wave equation, Qual. Theory Dyn. Syst. 16 (2017), no. 2, 299–315.
[45] A. Slavík, Discrete Bessel functions and partial difference equations, J. Difference Equ. Appl. 24 (2018), no. 3, 425–437.
[46] U. Smilansky, Quantum chaos on discrete graphs, J. Phys. A, Math. Theor. 40 (2007), no. 27, F621–F630.
[47] A. V. Tsvetkova, A. I. Shafarevich, The Cauchy problem for the wave equation on a homogeneous tree, Mat. Zametki 100 (2016), no. 6, 923–931; translation in Math. Notes 100 (2016), no. 5–6, 862–869.
[48] A. A. Terras, D. Wallace, Selberg’s trace formula on the k-regular tree and applications, Int. J. Math. Math. Sci. 2003(8) (2003), 501–526.
[49] A. B. Venkov, A. M. Nikitin, The Selberg trace formula, Ramanujan graphs and some problems in mathematical physics, Algebra i Analiz, 5(3) (1993), 1–76; translation in St. Petersburg Math. J. 5(3) (1994), 419–484.
[50] J. Yue, H. Li, J. Sheng, Y. Guo, X. Zhang, C. Zhou, T. Liu, L. Guo, Graph Wave Networks, Preprint, arXiv:2505.20034v2 (2025).

Discrete Space-Time Wave Kernels and Trace Identities on Regular Graphs

Abstract.

Key words and phrases:

2020 Mathematics Subject Classification:

1. Introduction and main results

1.1. Our setup

1.2. Main results

1.2.1. Wave kernels on regular graphs

Theorem 1.1.

1.2.2. Trace-type formula on regular graphs

Theorem 1.2.

Remark 1.3.

1.3. Applications

2. Preliminaries

2.1. Discrete Bessel functions

2.2. Wave kernels on a (q+1)(q+1)-regular tree

2.3. Graph coverings

2.4. A representation formula for bm​(x)b_{m}(x)

Lemma 2.1.

Proof.

Corollary 2.2.

Proof.

Remark 2.3.

Remark 2.4.

3. Proof of Theorem 1.1

4. Proof of Theorem 1.2

5. Applications of the trace-type formula

5.1. Cycle CnC_{n}

Corollary 5.1.

Proof.

Corollary 5.2.

Proof.

Corollary 5.3.

5.2. Complete graph KnK_{n}

Lemma 5.4.

Proof.

Corollary 5.5.

Proof.

5.3. dd-dimensional hypercube QdQ_{d}

Lemma 5.6.

Proof.

Corollary 5.7.

Remark 5.8.

Corollary 5.9.

Proof.

References

2.2. Wave kernels on a $(q+1)$ -regular tree

2.4. A representation formula for $b_{m}(x)$

5.1. Cycle $C_{n}$

5.2. Complete graph $K_{n}$

5.3. $d$ -dimensional hypercube $Q_{d}$