Nalini’s lecture 7

I was very jet-lagged during this lecture so many details may be missing. Apologies!

Polynomial method

To show strong spectral convergence of random $d$-regular graphs Let $d=q+1$. We recall the results of Chen-Garza-Vargas-Tropp-Van Handel for the permutation model of random graphs.

Here we take the configuration model. Let $G_{N} = (V_{N},E_{N})$ and let $N = |V_{N}|$. We have the test function which takes $\varphi: \mathbb{Z} \rightarrow \mathbb{C}$ even and supported in $[-L,L]$. Then $\widehat{\varphi}$ is defined as in the bottom row of the picture (I could not copy).

We have $\varphi(l)=$ coefficients of $P$ in the Chebyshev basis of polynomials. We saw the existence of asymptotic expansions.

\[\begin{equation} \mathbb{E}_{N} \left( \mathrm{Tr}P(\tfrac{A_{N}}{\sqrt{q}})\right) = N \int_{-2}^{2} P(x)\underbrace{\, \mathrm{d}m(x)}_{\text{ Keston-McKay measure}} + \sum_{r=0}^{R} \tfrac{1}{N^{r}} \mu_{r}(P) + \frac{1}{N^{R+1}} (\text{Rest}_{R+1,N}(P)). \end{equation}\]

C-GV-T-VH use the normalized trace $\mathrm{tr}_{N} = \frac{1}{N} \mathrm{Tr}_{N}$. So \[\begin{equation} \mathbb{E}_{N} (\mathrm{tr}_{N}( P( \frac{A}{\sqrt{q}} ))) = \int_{-2}^{2} P(x)\, \mathrm{d}m(x) + \sum_{r=0}^{R} \frac{1}{N^{r+1}} \mu_{r}(P) + \frac{1}{N^{R+2}} \text{Rest}(P) \end{equation}\]

C-GV-T-VH

(R=0) The term $\text{Rest}_{1,N} \in \mathcal{D}(\mathbb{R})$ and $|\text{Rest}_{1,N}(P)| \leq C$ with $\|P\|_{C^{g}([]-x_{*},x_{*})}$ suffices for strong convergence and the fact that $\gamma_{0}$ can be a distribution supported in $[-2,2]$.

We approximate $P \sim h \in \mathcal{C}_{c}^{\infty}(\mathbb{R})$, where $h=0$ in $[-2-\varepsilon/2,2+\varepsilon/2]$ and $h=1$ outside $[-2-\varepsilon,2+\varepsilon]$.

We have \[\begin{equation} \mathbb{E}_{N}( \mathrm{Tr}P (\frac{A}{\sqrt{q}})) = N \int_{ -2}^{2} P(x)\, \mathrm{d}m(x) + \delta_{0}(P) + \gamma_{0}(P) + \tfrac{1}{N}( O (|P|_{C^{\infty}([-x_{*},x_{*}])})). \end{equation}\]

We have \[\begin{equation} \mathbb{E}( \mathrm{Tr}( h(\frac{A}{\sqrt{q}}))) \leq \mathbb{E}( \mathrm{Tr}( h( \frac{A}{\sqrt{q}}))) = O( \frac{\varepsilon^{-g}}{N}) . \end{equation}\] and $P^{m} * Q^{m}$ is of degree $n+m+1$.

(Refined version) ($R$ arbitrary)

$\text{ Rest }_{R+1,N}$ is a distribution of order $4(R+2)+1 = 4 R + 9$.
$\mu_{r}$ ($\dots$) is of order $4(r+1)+1 = 4r+5$ and has support in $[-x_{*},x_{*}]$.
To have $r \leq R_{c}$, $\mathrm{supp}\gamma_{r} \subseteq [-2,2]$ like before.
$R_{c} < r < \tfrac{q}{2}-1$ and $\mathrm{supp}\gamma_{r} \subset [x_{*},x_{*}]$ and $x_{r} = \frac{2r+1}{\sqrt{q}} + \frac{\sqrt{q}}{2r+1}$ $(x= \lambda/\sqrt{q})$.

The first three statements allow to reinforce the previous argument $r \leq R_{c}$ and $\mathbb{E}( \#\{ j , \frac{\lambda_{j}}{ \sqrt{ q}} \notin [-2 - \varepsilon, 2 + \varepsilon] \}) = O( \frac{\varepsilon^{-4r+9}}{N^{r+1}})$ .

The fourth statement allows us to choose the next $R \leq r \leq \frac{q}{2}-1$ to get

Let $\gamma \in \mathcal{D}(\mathbb{R})$ have compact support ($ ()$). Let \[\begin{equation} \rho= \overline{ \lim }_{L \xrightarrow[]{} + \infty} |\gamma (x^{L})|^{\frac{1}{L}}. \end{equation}\] Then $\mathrm{supp}\gamma \subseteq [- \rho, \rho]$.

Let us write a proof of the fourth assertion. We take $\gamma_{r}(x^{L})$ where \[\begin{equation} x^{L} = \sum_{l=0}^{L} \underbrace{\varphi_{L}(l)}_{\geq 0}^{{\text{ coefficients of the base $T_{l}$ }}} T_{l}(x), \end{equation}\] Where we have have $T_{l}(t +\frac{1}{t}) = t^{l} + \frac{1}{t^{l}}$.

After this there are some more details that I failed to copy. Please see the video.

Proof of the first two statements

We know that $\mathbb{E}_{N}(\mathrm{Tr}(P(A)))$ is in fact a rational polynomial in $\frac{1}{N}$.

Detail: When $B_{N}$ is the Hashimoto matrix, we have \[\begin{equation} \mathbb{E}_{N}(\mathrm{Tr}(B_{N}^{L})) = \frac{P_{L}(\frac{1}{N})}{ Q_{L}(\frac{1}{Nd})} \end{equation}\] where $Q_{L}(X) = (1-X)(1-3X) \dots (1-(2L-1)X)$ with $\deg P_{L} \leq L$. So \[\begin{equation} \mathrm{Tr}(\frac{A}{\sqrt{q}})^{L} = \sum_{j=1}^{N} (q^{i s_{j}} + q^{- i s_{j}})^{L} = \sum_{\substack{l=0 \\ l \equiv L (2)}}^{L} \binom{L}{\frac{l+L}{2}} ( \mathrm{Tr}B^{L} - \frac{N (d-2)}{2} \frac{(1 + (-1)^{k})}{ \sqrt{q^{l}}} ). \end{equation}\]

Conclusion

\[\begin{equation} \mathbb{E}_{N}( \mathrm{Tr}_{N} A^{L} ) = \frac{\tilde{P_{L}}(\frac{1}{N})}{ Q_{L}(\frac{1}{Nd})} \end{equation}\] For a $h \in \mathbb{C}_{L}[X]$ we can write \[\begin{equation} \mathbb{E}_{N}( \mathrm{Tr}( h(\frac{A}{\sqrt{q}}))) = \frac{\varphi_{h}(\frac{1}{N})}{ Q_{L}(\frac{1}{N_{d}})} = \psi_{h}(\frac{1}{N}) \end{equation}\] By the Taylor expansion, it is \[\begin{equation} = \psi_{h}(0) + \sum_{r=1}^{R+1} \frac{1}{r! N^{r}} \psi_{h}^{(r)}(0) + \frac{1}{N^{R+2}} \int_{0}^{1} \frac{(1-t)^{R+1}}{(R+1)!}\, \mathrm{d}t \end{equation}\]

We need to bound the derivatives of $\psi_{h}$ on an arbitrary small interval $[0,a]$.

Using the inequality of Markov brothers

For $h \in \mathbb{C}_{L}[X]$ on $[0,a]$, one has \[\begin{equation} \|h^{(m)}\|_{\mathcal{C}^{0}([0,a])} \leq \frac{1}{(2m-1)!!} (\frac{ L^{2}}{a})^{m} \|h\|_{C^{0}([0,a])}. \end{equation}\]