Series analyzed in Lubotzky–Phillips–Sarnak "Ramanujan Graphs"

Question

In the LPS paper "Ramanujan graphs" the adjacency matrix of $X^{p,q}$, for simplicity say that $p,q\equiv1\mod{4}$ and $\left(\frac{p}{q}\right)=1$ (so, nonbipartite) and $n=\lvert X^{p,q}\rvert$, is considered with spectrum $p+1=\lambda_0>\lambda_1\ge\cdots\ge\lambda_{n-1}>-(p+1)$. Then, the "angle" $\theta_j$ is introduced as $\lambda_j=2\sqrt{p}\cos\theta_j$, where $$\theta\in\begin{cases}[0,\pi] & \text{$\lambda$ is in the bulk of the spectrum} \\\ i\mathbb{R}_+ & \lambda>2\sqrt{p} \\\ \pi+i\mathbb{R} & \lambda<-2\sqrt{p}.\end{cases}$$ I think it is implicitly used that "$\cos$" is really $\cos(x)=\frac{1}{2}(e^{ix}+e^{-ix})$ and $\sin(x)=\frac{1}{2i}(e^{ix}-e^{-ix})$, in order to allow for $\lambda$ outside of the bulk.

I am looking at Case ii. in the proof of Theorem 4.1, on pgs. 13/14 of the linked PDF version. The crucial expression ends up being (for even $k$) $$\sum\limits_{0\le j<n}\frac{\sin((k+1)\theta_j)}{\sin\theta_j}.$$ It is claimed without explanation that this sum equals $$\frac{2}{p^{\frac{k}{2}}}\frac{p^{k+1}-1}{p-1}+o(p^\frac{k}{2}).$$ My first question is: Where does this asymptotic evaluation come from?

Then, the paper reaches the conclusion that $$\sum\limits_{0<j<n}\frac{\sin((k+1)\theta_j)}{\sin\theta_j}\in O(p^{k\epsilon})$$ (having already resolved the trivial eigenvalue) and claims then that $\theta_j\in\mathbb{R}$ as a consequence. My second question is: Why does this consequence hold? My best guess for this is that for $\lambda$ not in the bulk, the corresponding $\theta$ has $t:=e^{i\theta}=\frac{\lambda}{2\sqrt{p}}\pm\sqrt{\frac{\lambda^2}{4p}-1}$ (the sign agreeing with $\lambda$'s) satisfying $\lvert t\rvert>1$ and we can compute that $$\frac{\sin((k+1)\theta)}{\sin\theta}=\frac{1}{t^k}(1+t^2+t^4+\cdots+t^{2k})$$ so that for very large (still even) $k$ and small $\epsilon$, this positive term would dominate. However I am not sure how correct this is.

Answer 1

1. Regarding your first question, we have $e^{i\theta_0}=p^{-1/2}$ as emphasized two lines below (4.11). Therefore, $$\frac{\sin((k+1)\theta_0)}{\sin\theta_0}= \frac{e^{-i(k+1)\theta_0}-e^{i(k+1)\theta_0}}{e^{-i\theta_0}-e^{i\theta_0}} =\frac{p^{(k+1)/2}-p^{-(k+1)/2}}{p^{1/2}-p^{-1/2}},$$ so that $$\frac{2p^{k/2}}{n}\cdot\frac{\sin((k+1)\theta_0)}{\sin\theta_0}=\frac{2(p^{k+1}-1)}{n(p-1)}.\tag{1}$$ In contrast, for $j\in\{1,\dots,n-1\}$ we have $$|e^{i\theta_j}+e^{-i\theta_j}|=2|\cos\theta_j|=|\lambda_j/\sqrt{p}|<p^{1/2}+p^{-1/2},$$ which eventually yields that $p^{-1/2}<|e^{i\theta_j}|\leq 1$ by the line below (4.11). So in this case $$\frac{\sin((k+1)\theta_j)}{\sin\theta_j}= \frac{e^{-i(k+1)\theta_j}-e^{i(k+1)\theta_j}}{e^{-i\theta_j}-e^{i\theta_j}} =o(p^{k/2}),\qquad k\to\infty,$$ whence also $$\frac{2p^{k/2}}{n}\cdot\frac{\sin((k+1)\theta_j)}{\sin\theta_j}=o(p^k),\qquad k\to\infty.\tag{2}$$ Combining $(1)$ and $(2)$, we get $$\frac{2p^{k/2}}{n}\sum_{j=0}^{n-1}\frac{\sin((k+1)\theta_j)}{\sin\theta_j}=\frac{2(p^{k+1}-1)}{n(p-1)}+o(p^k),\qquad k\to\infty.$$ In the light of (4.16), this implies the display above (4.20).

2. Regarding your second question, let us start from $$\sum_{j=1}^{n-1}\frac{\sin((k+1)\theta_j)}{\sin\theta_j}=O(p^{k\epsilon}).$$ We can rewrite this as $$\sum_{j=1}^{n-1}\frac{e^{-i(k+1)\theta_j}-e^{i(k+1)\theta_j}}{e^{-i\theta_j}-e^{i\theta_j}}=O(p^{k\epsilon}).\tag{3}$$ Note that here $|e^{i\theta_j}|\leq 1\leq|e^{-i\theta_j}|$ by the line below (4.11). Let us record the smallest of these positive numbers as $$r:=\min\left(|e^{i\theta_1}|,\dots,|e^{i\theta_{n-1}}|\right).$$ By $(3)$, the power series $$f(z):=\sum_{k=0}^\infty z^k\sum_{j=1}^{n-1}\frac{e^{-i(k+1)\theta_j}-e^{i(k+1)\theta_j}}{e^{-i\theta_j}-e^{i\theta_j}}$$ converges in the open disk $D(0,p^{-\epsilon})$ for any $\epsilon>0$, hence also in the union of these disks, which is $D(0,1)$. In particular, $f(z)$ is a holomorphic function in $D(0,1)$. On the other hand, in the smaller open disk $D(0,r)$ we can evaluate $f(z)$ as \begin{align*} f(z)&=\sum_{j=1}^{n-1}\sum_{k=0}^\infty\frac{z^k e^{-i(k+1)\theta_j}-z^k e^{i(k+1)\theta_j}}{e^{-i\theta_j}-e^{i\theta_j}}\\ &=\sum_{j=1}^{n-1}\frac{e^{-i\theta_j}(1-ze^{-i\theta_j})^{-1}-e^{i\theta_j}(1-ze^{i\theta_j})^{-1}}{e^{-i\theta_j}-e^{i\theta_j}}\\ &=\sum_{j=1}^{n-1}\frac{1}{(z-e^{i\theta_j})(z-e^{-i\theta_j})}.\end{align*} So the right-hand side extends holomorphically from $D(0,r)$ to $D(0,1)$, which means that its poles $e^{\pm i\theta_j}$ cannot lie in $D(0,1)$. So each $e^{i\theta_j}$ lies on the unit circle (rather than in the open unit disk), whence $\theta_j\in\mathbb{R}$.