Quantum ergodicity on large regular graphs

Introduction and main results

It has been suggested by Kottos and Smilansky that graphs are a good ground of exploration of the ideas of “quantum chaos” . This means that the spectrum of the laplacian, as well as its eigenfunctions, should exhibit universal features that depend only on qualitative geometric properties of the graph. Whereas spectral statistics have been extensively studied, both numerically and analytically, the localization of eigenfunctions have (to our knowledge) only been investigated in a few models : the star graphs (both metric and discrete) , the large regular discrete graphs , and a family of metric graphs arising from measure preserving $1$-dimensional dynamical systems . For the latter, a version of the “Quantum Ergodicity theorem” (also known as Shnirelman theorem) has been established. For star graphs, the paper shows on the opposite that “Quantum Ergodicity” holds neither in the high frequency limit nor in the large graph limit. Furthermore it shows there are eigenfunctions that localise on two bonds of the graph. Spectral properties of large regular discrete graphs have been studied in but eigenfunctions have attracted attention only recently. A statistical study of the auto-correlations and the level sets of eigenvectors appeared in the papers that introduce a random wave model (see also for a random wave model on metric graphs). The paper has pioneered the study of quantum ergodicity on large regular graphs – that is to say, the study of the spatial distribution of eigenfunctions of the laplacian. The result of shows some form of delocalization of eigenfunctions :

Let $(G_{n})$ be a sequence of $(q+1)$-regular graphs (with $q$ fixed), $G_{n}=(V_{n},E_{n})$ with $V_{n}=\{1,\ldots,n\}$. Assume that This assumption holds in particular if the injectivity radius is $\geq c\ln n$. The interest of the weaker assumption is that it holds for typical random regular graphs . there exists $c>0,\delta>0$ such that, for any $k\leq c\ln n$, for any pair of vertices $x,y\in V_{n}$,

Fix $\epsilon>0$. Then, if $\phi$ is an eigenfunction of the discrete laplacian on $G_{n}$ and if $A\subset V_{n}$ is a set such that

then $|A|\geq n^{\alpha}$ — where $\alpha>0$ is given as an explicit function of $\epsilon,\delta$ and $c$.

A similar form of delocalization (but on weaker scales) is established when the degree $q=q_{n}$ goes to infinity in . We also refer to the papers where various forms of delocalization have been established for eigenvectors of random Wigner matrices and random band matrices.

In this paper, our aim is to establish for large regular graphs a result which reads like an analogue of the “quantum ergodicity theorem” on manifolds. Compared to Theorem 1.1 it pertains to a different definition of delocalization : delocalization is now tested by averaging an observable and comparing with the average along the uniform measure. As a motivation, let us recall the Quantum Ergodicity theorem in its original form.

Let $a$ be a continuous function on $M$ such that $\int_{M}a(x)d\operatorname{Vol}(x)=0$. Then

where the normalizing factor is $N(\lambda)=|\{n,\lambda_{n}\leq\lambda\}|.$ Here $\langle\psi_{n},a\psi_{n}\rangle_{L^{2}(M)}=\int_{M}a(x)|\psi_{n}(x)|^{2}d\operatorname{Vol}(x).$

(Note that (1.2) is true even for a function $a$ with non-zero mean.)

for every pseudodifferential operator $A$ of order $0$ on $M$. On the right-hand side, $\sigma^{0}(A)$ is the principal symbol of $A$, that is a function on the unit cotangent bundle $S^{*}M$, and $L$ is the normalized Liouville measure (uniform measure), arising naturally from the symplectic structure of the cotangent bundle.

We consider the stochastic operator acting on $\Gamma_{n}$-invariant functions,

where $x\sim y$ means that $x$ and $y$ are neighbours in the tree This is also the (normalized) adjacency matric of the graph $G_{n}$, but note that this definition allows $G_{n}$ to have loops and multiple edges.. It is related to the discrete laplacian by $A-I=\Delta.$

Whereas the Shnirelman theorem deals with the high frequency asymptotics ($\lambda_{n}\longrightarrow+\infty$), there is no such asymptotic régime for discrete graphs since the laplacian is a bounded operator. We will instead work (like in ) in the large spatial scale régime $n\longrightarrow+\infty$.

We will assume the following conditions on our sequence of graphs :

(EXP) The sequence of graphs is a family of expanders. More precisely, there exists $\beta>0$ such that the spectrum of $A$ on $L^{2}(G_{n})$ is contained in $\{1\}\cup[-1+\beta,1-\beta]$ for all $n$.

(EIIR) For all $R$, $\frac{|\{x\in V_{n},\rho(x)<R\}|}{n}\longrightarrow 0$ where $\rho(x)$ is the injectivity radius at $x$ (meaning the largest $\rho$ such that the ball $B(x,\rho)$ in $G_{n}$ is a tree).

(EIIR) is equivalent to saying that there exists $R_{n}\longrightarrow+\infty$ and $\alpha_{n}\longrightarrow 0$ such that

In particular, it is satisfied if the injectivity radius goes to infinity (with $R_{n}$ taken to be the minimal injectivity radius and $\alpha_{n}=0$).

Condition (EXP) replaces the ergodicity assumption in the usual quantum ergodicity theorem.

The graph $G_{n}$ can be chosen uniformly at random among the $(q+1)$-regular graphs with $n$ vertices (see section 2.4 for an introduction to this model). We can then take $R_{n}=k$ and $n\alpha_{n}=40Akq^{k}$ for any $k=k(n)$ such that $kq^{k}n^{-1}\mathop{\longrightarrow}\limits_{n\to+\infty}0$, and $A=A(n)$ such that $A\geq c>1$ (see , Theorem 4). For instance, we can take $k=(1-\delta)\log_{q}(n)$, with $0<\delta<1$, and $A=2$. In this case we have $R_{n}=(1-\delta)\log_{q}(n)$ and $\alpha_{n}=80(1-\delta)\log_{q}(n)n^{-\delta}$. For this choice of parameters, (EIIR) is satisfied with a probability tending to $1$ when $n\longrightarrow+\infty$. More precisely, this probability is greater than $1-e^{-Cn^{1-\delta}}$, for some constant $C>0$ independent of $n$.

Condition (EXP) is also satisfied by these sequences of random graphs : proves an equivalence between having a uniform spectral gap and having a uniform Cheeger constant. The latter condition was shown to hold generically in . In , a spectral gap estimate that is close to optimal is established.

An explicit example of sequence of $(q+1)$-regular graphs to which our results apply is given by the construction of Ramanujan graphs of for prime $q$. The sequence obtained satisfies conditions (EXP) and (EIIR) even more strongly than the sequences of random graphs of Example 1. A method for obtaining bi-partite Ramanujan graphs of arbitrary degrees has appeared recently in .

Eigenvalues of $A$ on a $(q+1)$-regular graph may be parameterized by their “spectral parameter” $s$ thanks to the relation

In what follows, $(r_{n})$ will be a sequence satisfying $r_{n}+2\leq R_{n}$ and $q^{r_{n}}\alpha_{n}\longrightarrow 0$. The sequence $(\delta_{n})$ will be assumed to satisfy $\delta_{n}^{K}r_{n}^{K-4}\longrightarrow+\infty$, for some integer $K$. We also assume that $\delta_{n}\longrightarrow 0$, although it is not necessary for the general proof of section 4.

Let $(G_{n})$ be a sequence of $(q+1)$-regular graphs, $G_{n}=(V_{n},E_{n})$ with $V_{n}=\{1,\ldots,n\}$. Assume that $(G_{n})$ satisfies (EIIR) and (EXP). Fix $s_{0}\in(0,\tau)$ and let $I_{n}=[s_{0}-\delta_{n},s_{0}+\delta_{n}]$. Call $(s^{(n)}_{1},\ldots,s^{(n)}_{n})$ the spectrum of $A$ on $G_{n}$, and $(\psi^{(n)}_{1},\ldots,\psi^{(n)}_{n})$ a corresponding orthonormal eigenbasis.

If $a_{n}$ does not have zero mean, then by applying the theorem to $a_{n}-\overline{a_{n}}$ (where $\overline{a_{n}}=\frac{1}{n}\sum_{x\in V_{n}}a_{n}(x)$) we obtain

If we exclude the case $s_{0}=\tau/2$ in Theorem 1.3, we can assume, instead of (EXP), the following weaker condition : there exists $\beta>0$ such that the spectrum of $A$ on $L^{2}(G_{n})$ is contained in $\{1\}\cup[-1,1-\beta]$ for all $n$. In particular, the theorem applies for bipartite regular graphs in this case.

We can also say something in the case $s_{0}=\tau/2$ for bipartite expander graphs, that is if there exists $\beta>0$ such that the spectrum of $A$ on $L^{2}(G_{n})$ is contained in $\{-1,1\}\cup[-1+\beta,1-\beta]$ for all $n$. We need to strengthen the condition on the functions $a_{n}(x)$ in the theorem for the conclusion to apply : if $V_{n}=V_{n}^{1}\sqcup V_{n}^{2}$ is the bi-partition of $V_{n}$, then we need that

The theorem then tells us that we have equidistribution of most eigenfunctions with eigenvalue near $\tau/2$ on each set $V_{n}^{1}$ and $V_{n}^{2}$, without providing information on the relative weight of these two sets.

The proof will show that we can weaken condition (EXP), by allowing the spectral gap $\beta$ to decay with $n$ “not too fast” ($\beta\gg r_{n}^{-2/9}$ is enough). See Section 6.

Since random $(q+1)$-regular graphs satisfy both (EXP) and (EIIR) , our theorem applies to them with the values of $R_{n},\alpha_{n}$ given in Example 1.

Choose $(G_{n})$ uniformly at random amongst the $(q+1)$-regular graphs $G_{n}=(V_{n},E_{n})$ such that $V_{n}=\{1,\ldots,n\}$. Choose $j$ uniformly at random in $N(I_{n},G_{n})$.

The statement of Theorem 1.3 is the exact analogue of the Shnirelman theorem in its form (1.1). However, we do not have a statement analogous to the convergence of measures (1.2), because our sequence of measures does not live on a single space; instead, it is defined on the sequence of graphs $G_{n}$. We do not know of a notion that would be adapted to describe the limit of the family $(G_{n})$ endowed with the probability measure $(|\psi^{(n)}_{j}(x)|^{2})_{x\in V_{n}}.$

We can generalize Theorem 1.3 by replacing the function $a$ with any finite range operator :

Let $(G_{n})$ be a sequence of $(q+1)$-regular graphs, $G_{n}=(V_{n},E_{n})$ with $V_{n}=\{1,\ldots,n\}$. Assume that $(G_{n})$ satisfies (EIIR) and (EXP). Fix $s_{0}\in(0,\tau)$ and let $I_{n}=[s_{0}-\delta_{n},s_{0}+\delta_{n}]$. Call $(s^{(n)}_{1},\ldots,s^{(n)}_{n})$ the spectrum of the laplacian on $G_{n}$, and $(\psi^{(n)}_{1},\ldots,\psi^{(n)}_{n})$ a corresponding orthonormal eigenbasis.

Let $N(I_{n},G_{n})=\left|\{j\in\{1,\ldots,n\},s^{(n)}_{j}\in I_{n}\}\right|$.

Assume that $\sup_{x,y\in V_{n}}|K_{n}(x,y)|\leq 1.$

Then there exists a number $\overline{A_{n}}(s_{0})$ such that

With the notation of §3.2, we can write $A_{n}=\operatorname{Op}(a_{n})$, $a_{n}\in S_{o}^{D}$; and we have the expression $\overline{A_{n}}(s_{0})=\frac{1}{n}\sum_{x\in D_{n}}\int_{\Omega}a_{n}(x,\omega,s_{0})d\nu_{x}(\omega)$.

Quantitative statements (i.e. rates of convergence) will be given in Section 6.

Theorem 1.3 : outline of the proof in the case s0=τ/2s_{0}=\tau/2

We first give a proof in the special case $s_{0}=\tau/2$. The reason for treating this case separately is that one can give a proof which is exactly parallel to that of the Shnirelman theorem on manifolds . The case of arbitrary $s_{0}$ requires additional arguments and will be treated in Section 4.

Fix an integer $T>0$. Let $\chi$ be a smooth cut-off function supported in $$and taking the constant value$1$on$[-1/2,1/2]$. We write

so that $\chi_{n}\equiv 1$ on $I_{n}$. We use the pseudodifferential calculus and the notation defined in Section 3, taking the cut-off parameter $r$ equal to $r_{n}$ (from condition (EIIR), as explained before the statement of Theorem 1.3).

To simplify the notation, we will write $\psi_{j}=\psi_{j}^{(n)}$, $s_{j}=s_{j}^{(n)}$, and $a=a_{n}$. The observable $a$ is a function on $G_{n}$, in other words a $\Gamma_{n}$-invariant function on ${\mathfrak{X}}$. Let $\Omega$ be the boundary of ${\mathfrak{X}}$ (see section 3), then $a$ extends to a function on ${\mathfrak{X}}\times\Omega\times[0,\tau]$ that does not depend on the last two coordinates. The notation $\operatorname{Op}(a)$ is then defined in section 3.

Thanks to Lemma 3.10 and to the “Egorov property” Corollary 3.9, we have To prove the extended Theorem 1.7, we also need Lemma 3.11.

where $a^{T}:=\frac{1}{T}\sum_{k=0}^{T-1}a\circ\sigma^{2k}$ and $\sigma:{\mathfrak{X}}\times\Omega\longrightarrow{\mathfrak{X}}\times\Omega$ is the shift (see §3.4).

We also know from the Kesten-McKay law (Section 5, Corollary 5.2) that

Our choices of $r=r_{n}$ and $\delta_{n}$ imply that the last four terms vanish as $n$ goes to infinity while $T$ is fixed.

2. Expansion and ergodicity

where $y\in\mathfrak{X}$ and $d(x,y)=k$. Then $\omega\mapsto a\circ\sigma^{k}(x,\omega)$ is constant on $\Omega(x,y)$ for every $y\in\mathfrak{X}$ such that $d(x,y)=k$, and $\nu_{x}(\Omega(x,y))=\frac{1}{(q+1)q^{k-1}}$. We have

where $S_{0}=\text{Id}$ and for all $k\geq 1$, $S_{k}$ is the stochastic operator defined as follows by its kernel on the tree ${\mathfrak{X}}$ :

On the quotient $G_{n}$, the spectrum of $S_{k}$ is the set $\left\{\phi_{s_{j}}(k),j=1,\ldots,n\right\}$ where $\phi_{s}$ is the spherical function,

and $\{s_{j},j=1,\ldots,n\}$ are the spectral parameters for the operator $A$ defined by (1.4).

Using the parameterization (1.5) of the spectrum, the eigenvalue $\lambda=1$ corresponds to

Because of the (EXP) condition, the other untempered eigenvalues satisfy $is\in(0,\frac{1}{2}-\beta)$ or $is+i\frac{\pi}{\ln q}\in(0,\frac{1}{2}-\beta)$, for some $\beta>0$ independent of $n$. It follows that $|\phi_{s_{j}}(k)|\leq Cq^{-\beta k}$ with $C,\beta$ independent of $n$. The eigenvalues of the self-adjoint stochastic operator $\frac{1}{T^{2}}\sum_{k=0}^{T-1}\sum_{j=0}^{T-1}S_{2|k-j|}$ are therefore bounded by

in modulus. They are contained in $\{1\}\cup\left[-\frac{C}{T\beta},\frac{C}{T\beta}\right]$ for some $C$, independent of $n,T,\beta$ (the eigenvalue $1$ has multiplicity $1$, corresponding to the constant function).

Thus, if $a$ satisfies $\sum_{x\in V_{n}}a(x)=0$ and $\sup_{x}|a(x)|\leq 1$, we have

3. Conclusion

We obtain, using the results of the previous sections and the Kesten-McKay law (Corollary 5.2),

If we choose the sequences $r=r_{n}$ and $\delta_{n}$ satisfying $q^{r}\alpha_{n}\longrightarrow 0$ and $\frac{r^{3}}{\delta_{n}(r\delta_{n})^{K}}\longrightarrow 0$ for some integer $K$, we finally have

As the left-hand side of the equality does not depend on $T$, we take the limit $T\longrightarrow\infty$ to obtain

Elements of pseudodifferential calculus

In §3.1–3.2 we recall some of the tools of pseudodifferential calculus that were introduced in . However, the following important remark has to be made : in order for Theorems 1.3 and 1.7 to have full strength, we should not impose on the symbols $a$ too strong regularity conditions, that would have the effect of making the theorems trivial consequences of the (EXP) condition. Thus, we pay attention to only use from the properties that do not require regularity of $a$ with respect to the $x$-variable.

In the following sections we try to construct a pseudodifferential calculus on the quotient.

the kernel of $\operatorname{Op}_{\mathfrak{X}}(a)$.

2. Class of symbols

From , we know that the fact that $K_{\mathfrak{X}}(x,y;a)=0$ for $d_{\mathfrak{X}}(x,y)>D$ is equivalent to the four following conditions on $a$ :

$a$ extends to a $2\tau$-periodic entire function of exponential type $D$ uniformly in $\omega$; i.e. for all $x$ there exists $C(x)>0$ such that

$a$ is a $D$-cylindrical function, that is : if the two half-geodesics $[x,\omega)=(x_{0},x_{1},x_{2},\ldots)$ and $[x^{\prime},\omega^{\prime})=(x^{\prime}_{0},x^{\prime}_{1},x^{\prime}_{2},\ldots)$ satisfy $x_{j}=x^{\prime}_{j}$ for $0\leq j\leq D$, then $a(x,\omega,s)=a(x^{\prime},\omega^{\prime},s)$.

We shall denote by $S_{o}^{D}({\mathfrak{X}})$ the class of such functions. In , another class of symbols was considered :

Here $\mathcal{E}_{n}^{x}a(x,\omega,s)$ is the projection of $a(x,\omega,s)$ on functions depending only on the first $n$ vertices of the half-geodesic $[x,\omega)$ (see for a formula). In particular, $\mathcal{E}_{n}^{x}a(x,s)=a(x,s)$ if $a$ does not depend on $\omega$.

It is proven in that $S({\mathfrak{X}})$ endowed with usual addition and multiplication is an algebra. This makes it more suitable for semiclassical analysis than the class $S_{o}^{D}({\mathfrak{X}})$. It also has the property, crucial for us, that

where $\sigma$ is the shift, $\sigma(x,\omega)=(x_{1},\omega)$ if $[x,\omega)=(x_{0},x_{1},x_{2},\ldots)$. It is proven in that

for any $M$, where $\lVert a\rVert_{\Omega,M}=\sup_{(x,\omega,s)}\sup_{n}(1+n)^{M}|a-\mathcal{E}_{n}^{x}a|(x,\omega,s)$, and that as a consequence, $\operatorname{Op}_{\mathfrak{X}}(a)$ extends to a bounded operator on $L^{2}({\mathfrak{X}})$ if $a\in S({\mathfrak{X}})$.

If $a(x,\omega,s)=a(x)$ depends only on $x$, then $\operatorname{Op}_{\mathfrak{X}}(a)$ is the operator of multiplication by $a$. At several places we will use the fact that

if $\varphi=\varphi(s)$ only depends on the last variable and $a(x,\omega,s)\in S(\mathfrak{X})$, say.

3. Definition of OpGn⁡(a)\operatorname{Op}_{G_{n}}(a) on a finite graph.

Recall that $G_{n}$ is written as a quotient $\Gamma_{n}\backslash{\mathfrak{X}}$, where $\Gamma_{n}$ is a group of automorphisms of ${\mathfrak{X}}$, whose elements act without fixed points.

Let us now assume that $a$ is $\Gamma_{n}$-invariant, meaning that $a(\gamma\cdot x,\gamma\cdot\omega,s)=a(x,\omega,s)$ for all $(x,\omega,s)$ and all $\gamma\in\Gamma_{n}$ (where the action of $\Gamma_{n}$ on the boundary $\Omega$ is obtained by extending its action on ${\mathfrak{X}}$). For a $\Gamma_{n}$-invariant symbol, we have

for all $x,y\in{\mathfrak{X}}$ and $\gamma\in\Gamma_{n}$. The proof of this fact is identical to the proof of Proposition 1.1 in .

We now define $\operatorname{Op}(a)$ on the quotient.

Assume the sequence $(G_{n})$ satisfies (EIIR). Let $r=r_{n}$ be a positive number.

If $a$ is $\Gamma_{n}$-invariant, we define $\operatorname{Op}_{G_{n}}(a)$ to be the operator with $\Gamma_{n}$-bi-invariant kernel

Here $\chi$ is a cut-off function that satisfies the conditions of §2.1 (although it need not be the same cut-off as in §2.1, we use the same notation).

Compared to the case of manifolds, a difficulty we meet is that we are not able to prove that $\operatorname{Op}_{G_{n}}(a)$ is bounded on $L^{2}(V_{n})$ independently of $n$ (actually, inspection of simple examples show that our conditions on $a$ are not sufficient to ensure this). Note however that we are only interested in $\operatorname{Op}_{G_{n}}(a)\psi^{(n)}_{j}$ for $\lambda^{(n)}_{j}$ in the tempered spectrum; more precisely, we shall only need to estimate quantities such as $\frac{1}{N(I_{n},G_{n})}\sum_{s^{(n)}_{j}\in I_{n}}\left|\langle\psi^{(n)}_{j},\operatorname{Op}_{G_{n}}(a)\psi^{(n)}_{j}\rangle\right|^{2}.$ For that purpose it will be sufficient to know that the Hilbert-Schmidt norm of $\operatorname{Op}_{G_{n}}(a)$ does not grow too fast :

We split the sum into two parts, whether $\rho(x)\geq r$ or not. If $\rho(x)\geq r$, then the sum over $\gamma\in\Gamma_{n}$ is reduced to only one term, thanks to the cut-off function. If $\rho(x)\leq r$, then there are at most $q^{r}$ terms in the sum over $\gamma\in\Gamma_{n}$, and we can use Cauchy-Schwarz inequality to bound it as follows

Plancherel formula for the Fourier-Helgason transform, applied to $y\mapsto K_{\mathfrak{X}}(x,y;a)$ with $x$ fixed, converts this last expression to

4. “Egorov”-type properties

For Quantum Ergodicity on manifolds, the Egorov theorem is a statement saying that the matrix elements $\langle\psi_{j},\operatorname{Op}(a)\psi_{j}\rangle$ remain almost invariant when transporting $a$ along the geodesic flow, when $\psi_{j}$ are the eigenfunctions of the Laplace-Beltrami operator $\Delta$. This is proven by showing that taking the bracket $[\Delta,\operatorname{Op}(a)]$ amounts to differentiating $a$ along the geodesic flow (up to some “negligible” error term). Here we try to perform a similar calculation.

If $a$ and $b$ are compactly supported functions, we have

in other words $L$ is the adjoint of $U$ on the Hilbert space $L^{2}({\mathfrak{X}}\times\Omega,\sum_{x}\delta_{x}d\nu_{x}(\omega))$. In addition, we also have $LU=I$, reflecting the fact that $U$ is an isometry of $L^{2}({\mathfrak{X}}\times\Omega,\sum_{x}\delta_{x}d\nu_{x}(\omega))$. The operators $U$ and $L$ preserve the $\Gamma_{n}$-invariant functions. If $a$ and $b$ are a $\Gamma_{n}$-invariant functions, we still have

Recall that $D_{n}$ is a fundamental domain for the action of $\Gamma_{n}$ on ${\mathfrak{X}}$.

If $a\in S({\mathfrak{X}})$ is $\Gamma_{n}$-invariant, then

where $c\in S({\mathfrak{X}})$ is a symbol given by

Since $\langle\psi_{j},[\Delta,\operatorname{Op}_{G_{n}}(a)]\psi_{j}\rangle=0$ for every laplacian eigenfunction $\psi_{j}$, this implies

An exact analogue of the usual Egorov theorem on manifolds would require an estimate of $\lVert\operatorname{Op}(c)\rVert_{L^{2}}$ and show that it is $0$ up to a vanishing remainder term. Here, due to our use of the Hilbert-Schmidt norm, we will only show this for the average

which is sufficient to prove our theorem.

Let us denote by $K_{G_{n}}(x,y;[.])$ the kernel of $[\Delta,\operatorname{Op}_{G_{n}}(a)]$. We know from that $K_{\mathfrak{X}}(x,y;c)$ is the kernel of $[\Delta,\operatorname{Op}_{\mathfrak{X}}(a)]$. We are interested in the difference $K_{G_{n}}(x,y;[.])-K_{G_{n}}(x,y;c)$, which is the kernel of the operator $R$.

Because of the cut-off functions, the sum (3.5) only runs on those $\gamma\in\Gamma_{n}$ for which $d(x,\gamma\cdot y)\leq r+1$; and in (3.6) we have $K_{\mathfrak{X}}(x,y)=K_{\mathfrak{X}}(x,y){\mathchoice{1\mskip-4.0mu{\rm{l}}}{1\mskip-4.0mu{\rm{l}}}{1\mskip-4.5mu{\rm{l}}}{1\mskip-5.0mu{\rm{l}}}}_{\{d(x,y)\leq r+1\}}$.

In the first sum of the right-hand side of equality (3.6), $d(z,y)=d(x,y)\pm 1$, because $x$ and $z$ are neighbours. In the second sum $d(x,z)=d(x,y)\pm 1$, because $z$ and $y$ are neighbours. Since $\chi$ is a smooth function, both $\chi\left(\frac{d(z,y)}{r}\right)$ and $\chi\left(\frac{d(x,z)}{r}\right)$ are equal to $\chi\left(\frac{d(x,y)}{r}\right)+O\left(\frac{1}{r}\right)$, and we have

Now if we go back to (3.5) we get $K_{G_{n}}(x,y;[.])=K_{G_{n}}(x,y;c)+K_{G_{n}}(x,y;R)$, where $K_{G_{n}}(x,y;R)$ is the kernel of the operator $R$, given by

We estimate the Hilbert-Schmidt norm of $R$ by first writing

We then use Cauchy-Schwarz and reason along the same lines as in lemma 3.3, to bound the former expression by

In what follows, Proposition 1 will be translated into an invariance property of the type

Recall that symbol $c$ of proposition 1 is given by

If we replace $a$ with $q^{is}Ua$ we have

where we used the fact that $U$ preserves the $L^{2}$ and $L^{\infty}$ norms. ∎

The idea is then to invert $(q^{2is}U-I)$. As the series $\sum_{k}q^{2iks}U^{k}$ is a formal inverse to $(q^{2is}U-I)$, we apply Corollary 3.5 to $a=\sum_{k=0}^{N-1}q^{2iks}U^{k}b:=b_{N-1}$, where $b\in S(\mathfrak{X})$ and $N$ is an arbitrary integer. We obtain

We apply Corollary 3.5 to $a=\sum_{k=0}^{N-1}q^{2iks}U^{k}b:=b_{N-1}$ and use the identity

combined with the fact that $U$ preserves the $L^{2}$ and $L^{\infty}$ norms. ∎

If we apply Corollary 3.5 to $a=\frac{1}{N}\sum_{k=0}^{N-1}b_{k}$, we obtain

where $b^{(s,N)}=\frac{1}{N}\sum_{k=0}^{N-1}q^{2isk}U^{k}b$.

Note that the “remainder term” $q^{2is}U(U-I)b^{(s,N)}$ is not small in the symbol norm : in Section 4, the (EXP) assumption will be used to show that it is small in the $L^{2}$-norm. This is a major difference with the Egorov theorem on manifolds, where no ergodicity assumption is needed.

We know from the proof of the previous corollary that

It follows that $(I-q^{2is}U)\frac{1}{N}\sum_{k=0}^{N-1}b_{k}=b-q^{2is}Ub^{(s,N)},$ and

Combining with the Hilbert-Schmidt estimate, Lemma 3.3, we get

The first term on the right-hand side is estimated by Corollary 3.7. We estimate the last term thanks to Lemma 3.3, and we use the fact that $U$ preserves the $L^{2}$ norm by $U$ :

As already mentioned, the value $s_{0}=\tau/2$ is special and the previous corollaries may be replaced by the following, simpler one. In case the support of $a$ shrinks around $s_{0}=\tau/2$, this is a closer analogue of the Egorov theorem on manifolds in the sense that no ergodicity or expanding assumption is needed to show that the remainder term goes to $0$.

We replace the symbol $a$ in proposition 1 with $q^{is}a\circ\sigma$. As $L(a\circ\sigma)=a$, the symbol $b$ becomes $b=a-Ta$, where

and we have $\sum_{j}|\langle\psi_{j},\operatorname{Op}(a)-\operatorname{Op}(Ta)\psi_{j}\rangle|^{2}\leq\lVert R\rVert^{2}_{HS},$ where

Recalling that $s_{0}=\frac{\pi}{2\ln q}$, we have

5. Two more formulas about OpGn⁡(χn)\operatorname{Op}_{G_{n}}(\chi_{n})

if $s_{j}\in[0,\tau]$ (tempered eigenfunctions).

First note that $\psi_{j}^{(n)}$ is associated to a $\Gamma_{n}$-invariant eigenfunction of the laplacian on the tree ${\mathfrak{X}}$, that we will still denote by $\psi_{j}^{(n)}$. We have on the tree

and $K_{{\mathfrak{X}}}(x,y;\chi_{n})\chi\left(\frac{d(x,y)}{r}\right)$ depends only on $d(x,y)$ because $\chi_{n}$ does not depend on $(x,\omega)$. We thus have

where $f(s_{j})$ is given by the spherical transform of the kernel

and $\phi_{s_{j}}$ is the spherical function associated to $s_{j}$ defined in (2.3). Now

Because $\chi_{n}\in S({\mathfrak{X}})$, according to the rapid decay property of the kernel of pseudodifferential operators (3.1), we have

Fix an integer $D$. Let $a$ be such that $K_{\mathfrak{X}}(x,y;a)=0$ for $d_{\mathfrak{X}}(x,y)>D$ (in other words, $a\in S_{o}^{D}({\mathfrak{X}})$) and $\varphi=\varphi(s)$. We have

The kernel $K_{G_{n}}(x,z;a\varphi)$ of $\operatorname{Op}_{G_{n}}(a\varphi)$ is obtained by the periodization

Because $\varphi$ only depends on $s$, we note that

After $\Gamma_{n}$-periodization, we note that $\sum_{\gamma\in\Gamma_{n}}\sum_{y\in{\mathfrak{X}}}K_{{\mathfrak{X}}}(x,y;a)K_{{\mathfrak{X}}}(y,\gamma\cdot z;\varphi)\chi\left(\frac{d(y,\gamma\cdot z)}{r}\right)$ is the kernel of $\operatorname{Op}_{G_{n}}(a)\operatorname{Op}_{G_{n}}(\varphi)$ (as soon as $D<r$). Using Cauchy-Schwarz and the fact that $K_{{\mathfrak{X}}}(x,y;a)$ is supported near the diagonal, the Hilbert-Schmidt norm of the operator with kernel

The proof for arbitrary s0s_{0}

Fix an integer $T>0$. Let $\chi$ be a smooth cut-off function supported in $$and taking the constant value$1$on$[-1/2,1/2]$. We write

so that $\chi_{n}\equiv 1$ on $I_{n}$. We use the pseudodifferential calculus and the notation defined in Section 3, taking the cut-off parameter $r$ equal to $r_{n}$ (from condition (EIIR), as explained before the statement of theorem 1.3).

To simplify the notation, we will write $\psi_{j}=\psi_{j}^{(n)}$, $s_{j}=s_{j}^{(n)}$, and $a=a_{n}$. Thanks to Lemmas 3.10 and to the “Egorov property” Corollary 3.8, we have To prove the extended Theorem 1.7, we also need Lemma 3.11.

We have seen in Section 2.2 that $\sum_{x\in D_{n}}\int|a^{T}(x,\omega)|^{2}d\nu_{x}(\omega)=O\left(\frac{n}{T\beta}\right)$. The same proof shows that $\sum_{x\in D_{n}}\int|a^{(s,N)}(x,\omega)|^{2}d\nu_{x}(\omega)=O\left(\frac{n}{N\beta}\right)$. A major difference here with the usual Quantum Ergodicity (and with the special proof of §2) is that condition (EXP) is used already to show that the “remainder term” $a^{(s,N)}$ of the Egorov theorem is small in the $L^{2}$-norm.

For $s$ staying away from $\tau/2$, a slightly more careful proof would show that we only need to assume here that the spectrum of $A$ is contained in $\{1\}\cup[-1,1-\beta]$. Hence our Remark 1.5.

Recall also, from the Kesten-McKay law (Section 5, Corollary 5.2) that

and if we choose the sequences $r=r_{n}$ and $\delta_{n}$ as explained in section 5,

As the left-hand side of the equality does not depend on $T$ and $N$, we take the limit $N\longrightarrow\infty$ and then $T\longrightarrow\infty$ to get

Kesten-McKay law for sequences of graphs satisfying (EIIR)

In this section we give an alternative proof of the Kesten-McKay law , which gives the spectral density for large regular graphs satisfying (EIIR) and is analogous to the Weyl law for the spectral density of the laplacian on Riemannian manifolds. Note that we consider the density of eigenvalues in intervals that are allowed to shrink as $n\longrightarrow+\infty$.

In the definition of $\operatorname{Op}_{G_{n}}$, we take $r=r_{n}$ such that $r_{n}+2\leq R_{n}$ and $q^{r_{n}}\alpha_{n}\longrightarrow 0$ (where $R_{n}$ and $\alpha_{n}$ are the quantities occurring in (EIIR)) We can take for example $r_{n}=\min\left\{R_{n}-2,-(1-\epsilon)\frac{\log\alpha_{n}}{\log q}\right\},$ for any $0<\epsilon<1$.. We also assume that there exists an integer $M$ such that

If $\chi_{n}$ is the function defined in (2.1) with $s_{0}\in(0,\tau)$, this ensures that

Assume (EIIR). Let $\chi=\chi_{n}$ be a smooth function satisfying

with $\delta_{n}r_{n}\longrightarrow+\infty$, such that $\frac{1}{\delta_{n}^{M+1}r_{n}^{M-3}}\longrightarrow 0$ for some $M$.

Under the assumptions of Theorem 1.3, we have

where $|c(s_{0})|^{-2}$ is the density of the Plancherel measure at $s_{0}$.

Quantitative statement

In this section we will give explicit upper bounds on the rate of convergence, first in terms of the parameters $R_{n}$ and $\alpha_{n}$ associated with the sequence of graphs $(G_{n})$ in condition (EIIR), then depending only on $n$ for sequences of random graphs. These results are certainly not optimal because some of our inequalities were written in a non optimal way.

In the general case $s_{0}\in(0,\tau)$, we have

If $\delta_{n}=r_{n}^{-1+\epsilon}$ for some $0<\epsilon<1$, then we have

where we can take $r_{n}=\min\left\{R_{n}-2,-(1-\epsilon^{\prime})\log_{q}(\alpha_{n})\right\},$ for any $0<\epsilon^{\prime}<1$.

According to the proof of section 4, we have

Take $N=r_{n}^{2/3}$ and $T=r_{n}^{2/9}$ such that $\frac{1}{T}=\frac{T^{2}}{N}=\frac{N^{2}T^{2}}{r_{n}^{2}}=r_{n}^{-2/9}$. For every $M>0$, we have $O\left(\frac{r_{n}^{3}}{\delta_{n}(r_{n}\delta_{n})^{\infty}}\right)=O\left(r_{n}^{3-M}\delta_{n}^{-(1+M)}\right)=O\left(r_{n}^{4-(1+M)\epsilon}\right)$ and this term can be made negligible in comparison with the other terms by taking $M$ sufficiently large. Finally $N^{2}T^{2}q^{r_{n}}\alpha_{n}=r_{n}^{16/9}q^{r_{n}}\alpha_{n}$. ∎

Here we kept the spectral gap $\beta$ fixed, but we see that this could be relaxed to $\beta\gg r_{n}^{-2/9}.$

Let $\delta>1/2$, $\epsilon>0$, and $\delta_{n}=(\log_{q}(n^{1-\delta}))^{1-\epsilon}$. If $G_{n}$ is chosen uniformly at random among the $(q+1)$-regular graphs with $n$ vertices, we have

Take $R_{n}$ and $\alpha_{n}$ as in example 1. Let $1/2<\delta<1$, then $R_{n}=(1-\delta)\log_{q}(n)$ and $\alpha_{n}=80(1-\delta)\log_{q}(n)n^{-\delta}$. In this case, we take

Proof of Theorem 1.7

Most steps of the proof carry over to arbitrary $a\in S_{o}^{D}({\mathfrak{X}})$. Actually, all that needs modifying is the treatment of the expression

that is used in §2.2 (for $s=0$) and Section 4 (for $s$ close to $s_{0}$). Equation (7.1) is also

was rewritten as $\sum_{x\in D_{n}}S_{j}a(x)a(x)$ using the fact that $a$ did not depend on $\omega$ – thus establishing a link between the shift $\sigma$ and the laplacian. We need to adapt that argument to the case when $a(x,\omega)$ depends on the first $D$ coordinates of the half geodesic $[x,\omega)=(x,x_{1},x_{2},\ldots)$.

When $D=2$, $a(x,\omega)=a(x,x_{1})$, so that $a$ is a function on the set $B$ of directed bonds of $G=G_{n}$ Note that $B$ has cardinality $n(q+1)$ if $G$ has $n$ vertices and is $(q+1)$-regular.. We use the notation of : if $e$ is an element of $B$, we shall denote by $o(e)\in V_{n}$ its origin, $t(e)\in V_{n}$ its terminus, and $\hat{e}\in B$ the reversed bond.

where $M^{\sharp}$ is a bistochastic matrix indexed by $B$, defined by

if $o(e^{\prime})=t(e)$ and $e^{\prime}\not=\hat{e}$; and $M^{\sharp}(e,e^{\prime})=0$ otherwise. This is (up to normalization) the matrix appearing in §3 of . It is the (normalized) adjacency matrix of the $q$-regular directed graph, whose vertices are the directed bonds of $G$, and where we draw an edge between two bonds if they are consecutive without allowing back-tracking. What we need is an explicit relation between the spectrum of $M^{\sharp}$ and the spectrum of the discrete laplacian on $G$, in other words, of the matrix $A$. The relation between the eigenvalues is formula (44) in , but since we also need relations between the eigenfunctions, we shall be more explicit below. We did not write all the detailed calculations because they are lengthy but basic. We assume these relations must already be known but did not find any reference.

Both $A$ and $M^{\sharp}$ have $1$ in their spectrum, corresponding to the constant eigenfunction. The matrix $A$ has $-1$ in its spectrum iff the graph $G$ is bi-partite, in which case $M^{\sharp}$ also trivially has $-1$ in its spectrum.

each eigenvalue $\lambda\not=\pm 1$ of $A$ gives rise to the two eigenvalues

in addition, $M^{\sharp}$ admits the eigenvalue $1/q$ with multiplicity $b:=|E_{n}|-|V_{n}|+1$ (the rank of the fundamental group of $G$); and the eigenvalue $-1/q$ with multiplicity $b-1$ if $-1$ is not an eigenvalue of $A$, or $b$ if $-1$ is an eigenvalue of $A$. Or, equivalently, if the graph is bi-partite.

In particular, the eigenvalue $1$ of $M^{\sharp}$ has multiplicity $1$. The tempered spectrum of $A$ corresponds to eigenvalues of $M^{\sharp}$ of modulus $1/\sqrt{q}$; the untempered spectrum of $A$ contained in $[-1,1-\beta]$ gives rise to real eigenvalues of $M^{\sharp}$ contained in $[-1,1-\beta^{\prime}]$ with

Since $M^{\sharp}$ is not normal, the knowledge of its spectrum is not sufficient to control the growth of $M^{\sharp k}$ in a precise manner (we need a bound that is independent of the size of the matrix, in other words, independent of $n$). Below, we describe explicitly the eigenvectors of $M^{\sharp}$ in terms of those of $A$; these eigenvectors do not form an orthogonal family but this is compensated by the fact that one can compute their scalar products explicitly.

an eigenfunction $\phi$ of $A$ for the eigenvalue $\lambda\not=\pm 1$ gives rise to the two eigenfunctions of $M^{\sharp}$,

where $\epsilon_{1},\epsilon_{2}$ are the two roots of $q\epsilon^{2}-(q+1)\lambda\epsilon+1=0$ (in what follows we index them so that $|\epsilon_{1}|\leq|\epsilon_{2}|$). Special attention has to be paid to the case $\lambda=\pm\frac{2\sqrt{q}}{q+1}$, for which $\epsilon_{1}=\epsilon_{2}$ (see below).

the eigenvalues $\pm 1/q$ of $M^{\sharp}$ correspond, respectively, to odd and even Odd means $f(\hat{e})=-f(e)$ and even means $f(\hat{e})=f(e)$, for every bond $e$. solutions of $\sum_{o(e)=x}f(e)=0$ (for every vertex $x$). For the eigenvalue $1/q$, an explicit basis of eigenfunctions is indexed by generators of the fundamental group, $(\gamma_{1},\ldots,\gamma_{b})$ : every closed circuit $\gamma$ made of consecutive edges $(e_{1},\ldots,e_{k})$ gives rise to an odd eigenfunction

If $G$ is bi-partite, then all circuits have even length and we have an explicit basis of even eigenfunctions for the eigenvalue $-1/q$, again indexed by generators of the fundamental group :

if $\gamma$ is a closed circuit made of consecutive edges $(e_{1},\ldots,e_{k})$. If $G$ is not bi-partite, there are closed circuits of odd lengths, in which case $g_{\gamma}$ is not an eigenfunction of $M^{\sharp}$. Nevertheless, if $\gamma,\gamma^{\prime}$ are two circuits of odd lengths, $g_{\gamma}-g_{\gamma^{\prime}}$ is now an eigenfunction of $M^{\sharp}$ for the eigenvalue $-1/q$.