Proof of J. Friedman of Alon’s conjecture

If \(\Gamma\) is a finite graph with \(v\) vertices and \(a\) edges, we write \[\begin{equation} \mathbb{E}_{N}( \sharp\text{ of copies of } \Gamma \text{ in } G_{N}) = \frac{N^{v-a}}{d^{a}} \frac{ (1-\frac{1}{N}) (1-\frac{2}{N}) \dots ( 1- \frac{v-1}{N} )}{ (1-\frac{1}{dN} ) (1- \frac{3}{dN}) \dots (1-\frac{2a-1}{dN}) } (d(d-1))^{a} \end{equation}\]

We have

1. \(g_{a}(x) = (1-x)(1-2x)\dots (1-ax)\) where \(a \in \mathbb{Z}_{\geq 1}\), We write this as \[\begin{equation} g_{a}(x) = 1 - xQ_{1}(a) + x^{2} Q_{2}(a) - \dots, \end{equation}\] where \(Q_{k}(a)\) is a polynomial en \(a\) and bounded as \(|Q_{k}(a)| \leq a^{2k }k!\).

2. We have \[\begin{align} h_a(x) & = (1-x)^{-1} ( 1-3x)^{-1} \dots (1-(2a-1)x)^{-1} \\ & =1 + x R_{1}(a) + \dots x^{k} R_{k}(a) + \dots + x^{n+1} \tilde{R}_{n+1}(x,a), \end{align}\] where \(R_{k}(a)\) is a polynomial in \(a\) bounded by \(|R_{k}(a)| \leq k! a^{2k}\). The remaining \(|x^{n+1} \tilde{R}_{n+1}(x,a)| \leq x^{n+1} (n+1)! a^{2(n+1)}\) such that \(|x a^{2}|\) (\(x=\frac{1}{N}\)).

By doing some combinatorics with pictures (see above), we observe that \[\begin{align} & \mathbb{E}_{N}( \sharp\text{ of primitive periodic geod. of length }k) \\ = & \sum_{\substack{\Gamma \text{ graph } \\ \text{ with at most $k$ vertices }}}^{} \mathrm{Comb}(\Gamma) \mathbb{E}_{N}( \sharp\text{ of copies of } \Gamma) \cdot \sharp{ \text{ p.p. geod. of length $k$ on $\Gamma$}} \\ = & \sum_{F \text{ shape }}^{} \mathrm{Comb}(F) \sum_{\vec{l}}^{} \sum_{\substack{\vec{m} \\ \vec(l) \cdot \vec{m} = k }}^{} \mathbb{E}_{N} ( \sharp\text{ of copies of } F(\vec(l))) g(\vec(m)) \end{align}\] Here \(g(\vec{m}) \neq \Phi^{-1}(\vec{m})\) and \(l(\gamma) = \sum l_{j} m_{j} = \vec{l} \cdot \vec{m}\).

Then, we find that \[\begin{align} \mathbb{E}_{N} = & \sum_{ F \text{ shape }}^{} \frac{\mathrm{Comb}(F)}{N^{b(F) - 1}} \Big( \sum_{r=1}^{R} \frac{ f_{r}(|\vec{l}|) }{ N^{r} }(d-1)^{|\vec{l}|} + O_{k+1} ( \frac{|\vec{l}|}{N^{k+1}}(d-1)^{|\vec{l}|}) \cdot g(\vec{m}) \Big) \end{align}\] Here the inner sum \(\sum_{ \substack{\vec{l},\vec{m} \\ \vec{l} \cdot \vec{m} = k}}\) turned into the polynomial \(f_{r}\) which is a polynomial of degree \(2r\).

We have \(\vec{l} = (l_{1},\dots,l_{m})\) and \(|\vec{l}| = l_{1} + \dots + l_{n}\). Then we have the crude bound \[\begin{equation} | g(\vec{m}) | \leq \sharp\text{ of geod. of length } | \vec{m} | \text{ on } F = O(\lambda_{F}^{m}), \end{equation}\] where \(\lambda_{F}\) is the Perron-Frobenious eigenvalue of the Hashimoto matrix of \(F\).

We have \[\begin{equation} g(\vec{m}) \leq (d-1)^{| \vec{m}|} \leq (d-1)^{k}, \end{equation}\] since \(\lambda_{F} \leq (d-1) = q\).

Polyexponential functions and the “dot convolution”

Let \(f,g : \mathbb{N}^{n} \rightarrow \mathbb{C}\) and let \[f *g(k) = \sum_{ \vec{l} \cdot \vec{m} = k} f(\vec{l})g(\vec(m)).\] This is the so-called “dot convolution” named by J. Friedman.

Then, if we assume that \[f(l_{1},\dots,l_{n}) = \underbrace{p(\lambda_{1}, \dots, \lambda_{n}) \beta_{1}^{l_{1}} \dots \beta_{n}^{l_{n}}}_{\text{ Poly-exponential }}.\]

One has \(\beta_{1},\dots,\beta_{n} \leq B\) are some fixed numbers and \(\beta_{d} = d-1\) (eigenvalue of Arialis). Then \[\begin{equation} \max_{\vec{\rho} \cdot \vec{m} = M} |g(\vec{m})| \leq (\rho + \varepsilon)^{M} \forall \varepsilon > 0. \end{equation}\]

Then \(f + g(k)\) is polyexponential + some error \(O((\rho' + \varepsilon)^{k})\) where \(\rho' = \max(B^{\frac{1}{2} , \rho})\).

The theorem applies given when \(\lambda \leq \sqrt{d-1}\).

If we want to develop the expression of \(\mathbb{E}_{N}\) upto order \(R\), we don’t need any more than shapes \(F\) such that \(f(F)-1 \leq R\) where \(f(F) = f\) is given (what?)

The shape \(F\) that maximizes \(\lambda_{F}\) is the bouqet of circles. See picture.

So that \(2 b -1 \leq \sqrt{d-1}\), we can apply the theorem for \(b \leq \frac{\sqrt{d-1} + 1}{2}\). Hence, we develop the expression of \(\mathbb{E}_{N}\) upto order \(R\).

Link with the spectral gap

Because of the trace formula, one has for \(q=d-1\), \(N = \sharp V(G_{N})\) \[\begin{equation} \varphi : \mathbb{Z} \rightarrow \mathbb{C}, \widehat{\varphi}(s) = \underbrace{\sum_{l \in \mathbb{Z}}^{} q^{i s l } \varphi(l)}_{\text{trignometric polynomial}}. \end{equation}\]

If \(\lambda_{j}^{(N)}\) is the eigenvalue of the adjacency matrix of a \(d\)-regular graph \(G_{N}\), then \[\begin{equation} \lambda_{j} = q^{\frac{1}{2} + i s_{j}} + q^{\frac{1}{2} - i s_{j}}, \end{equation}\]

One has \[\begin{equation} \mathbb{E}_{N} ( \sum_{j=0}^{N-1} \widehat{\varphi}(s_{j})) = \underbrace{N \int_{}^{} \widehat{\varphi}(s) \, \mathrm{d}m (s)}_{O(N)} + { \mathbb{E}( \sum_{ \gamma \text{ p.p. geod. }}^{} \sum_{n \geq 1}^{} T(\gamma) \frac{\varphi ( n T( \gamma))}{q^{ \frac{n T(\gamma)}{2}}} ) }. \end{equation}\]

We had a bound a propri which was \[\begin{equation} \sharp\{ \gamma \text{ p.p.g, len } \leq k \} \leq N q^{l}, \end{equation}\] whereas the sum \[\begin{equation} \sum_{n \geq 2}^{} = O( N L ) \end{equation}\] We are interested just with \(n=1\).

So we have \[\begin{equation} \mathbb{E} ( \sum_{}^{} \widehat{\varphi}(s_{j})) = O(N ) + \mathbb{E}_{N}( \sum_{ \gamma \text{ p.p.g }}^{} T(\gamma) \frac{\varphi(T(\gamma))}{q^{\frac{T(\gamma)}{2}}}) . \end{equation}\] The second term is \[\begin{equation} \sum_{l=0}^{} \frac{l \varphi(l)}{ q^{l/2}} [ \sum_{r=0}^{R} \frac{F_{r}(k)}{N^{r}} + O( e^{2(k+1} \frac{q^{l}}{N^{k+1}}) ]. \end{equation}\]

Let us suppose that we know that \(F_{r}(l) = p_{2r}(l)q^{l} + O(l^{c} q^{\frac{l}{2}})\) with \(r \leq R\). Then \[\begin{equation} = \sum_{l \geq 0}^{} l \varphi(l) \Big[ \sum_{r=0}^{R} \frac{p_{2r}(l)q^{l/2}}{N^{r}} \Big]. \end{equation}\]

Then \[\begin{equation} \mathbb{E}( \sum_{}^{} \widehat{\varphi}(s_{j})) \geq \varphi(L) \mathbb{E}(q^{L |\Im s_{1}|}) \geq \varphi(L) \cdot q^{L \varepsilon_{0}} \mathbb{P} ( \Im(s_{1}) \geq \varepsilon_{0}). \end{equation}\] The goal is to show that the probability term \(\mathbb{P} \xrightarrow[]{ } 0 \forall \varepsilon_{0}\).

Main idea: Clever choice of the test function. This is what J.F. calls the “sidestepping lemma”. We replace \(\varphi\) by \(\mathcal{D}^{m} \varphi\) where \(\mathcal{D} = a + a^{*} - (q^{\frac{1}{2}} + q^{-\frac{1}{2}})\), where \[\begin{equation} a \varphi (l) = \varphi(l+1) , a^{*}\varphi(l) = \varphi(l-1). \end{equation}\] Then \(\widehat{\varphi(s)}\) becomes \((q^{i s} + q^{-is} - q^{\frac{1}{2} - q^{-\frac{1}{2}}} )^{m}\widehat{ \varphi}\) which cancels in \(s_{0}\).

Suppose we know that \(F_{r}(l) = p_{2r}(l) q^{l} + O(l^{c} q^{l/2})\) for \(r \leq R\). Then \[\begin{equation} \sum_{l \geq 0}^{} \varphi(l) \mathcal{D}^{m} \varphi(l) p_{2r}(l) q^{l/2} = \sum_{}^{} \varphi(l) \mathcal{D}^{m}( \mathbb{I}_{\mathbb{Z}_{+}}) l p_{2r}(l) q^{\frac{l}{2}} \end{equation}\] This is \(O(1)\) for \(m \geq 2r+2\).

The result is that for \(m\) even and \(\geq 2r + 2\) we have \[\begin{equation} \mathbb{E} ( \sum_{}^{} (q^{i s_{j}} + q^{-s_{j}} - q^{\frac{1}{2}} - q^{-\frac{1}{2}})^{m} \widehat{\varphi}) = O( N + L + L^{c} \frac{q^{L/2}}{ N ^{1 + R}} \|\varphi\|)) \end{equation}\]

Note: There is a small part missing here because I had to leave early.