Character sums and abelian Ramanujan graphs (with an appendix by Keqin Feng and Wen-Ch'ing Winnie Li) (Q1196909): Difference between revisions

Roughly speaking, a Ramanujan graph is a connected regular graph whose nontrivial eigenvalues (i.e. those of its adjacency matrix) are relatively small in absolute value. Some new Ramanujan graphs defined on certain abelian groups are constructed in this paper. Let \(G\) be a finite abelian, say, additive group and \(S\) a \(k\)-element subset of \(G\). Define two directed \(k\)-regular graphs on \(G\), called the sum graph \(X_ s(G,S)\) and the difference graph \(X_ d(G,S)\) as follows: the neighbors (following the out-direction) of a vertex \(x\) in \(X_ s(G,S)\) are \(- x+s\), \(s\in S\), while those of \(x\) in \(X_ d(G,S)\) are \(x+s\), \(s\in S\). For each character \(\psi\) of \(G\) put \(e(\psi,S)=\sum_{s\in S}\psi(s)\). The author shows that the absolute values of the eigenvalues of \(X_ s(G,S)\) and \(X_ d(G,S)\) are the same, they are \(| e(\psi,S)|\) where \(\psi\) runs through all characters of \(G\). Hence the constructions of Ramanujan graphs defined on abelian groups have close relation with the estimates of character sums over the groups. In this paper several estimates on character sums are derived using the Riemann hypothesis for curves over finite fields. In particular, the author establishes an estimate on twisted generalized Kloosterman sums as conjectured by P. Deligne for the case \(n=2\): \[ |\sum_{\chi\in N_ 2}\chi(x)\psi(x)|\leq 2q^{1/2}\quad\text{for all nontrivial characters } (\chi,\psi)\text{ of } N_ 2\times F_{q^ 2}. \] Here \(N_ 2\) consists of norm 1 to \(F_ q\) elements of \(F_{q^ 2}\). Then these character sum estimates are used to prove that some graphs defined on certain abelian groups are Ramanujan graphs.