Ramanujan graphs and expander families constructed from \(p\)-ary bent functions (Q2291671): Difference between revisions

A connected \(k\)-regular graph is called Ramanujan if \(|\lambda|\leq 2\sqrt{k-1}\) for every eigenvalue \(\lambda\neq \pm k\) of its adjacency matrix. A function from \(\mathbb{F}_{p^m}\) to \(\mathbb{F}_p\) is called \(p\)-ary bent if \(|\sum_{x\in \mathbb{F}_{p^m}} \zeta_p^{f(x)-Tr(\beta x)}|^2=p^m\) for each \(\beta\in \mathbb{F}_{p^m}\). Set \(D_{f,i}=\{\beta\in\mathbb{F}_{p^m}^\ast:f(\beta)=i \}\) for \(i\in \mathbb{F}_p\). Given a positive integer \(l\) and a \(p\)-ary function \(f\) on \(\mathbb{F}_{p^m}\), if \(f(ax)=a^lf(x)\) for all \(a\in \mathbb{F}_p^\ast\) and \(x\in \mathbb{F}_{p^m}\), then \(f\) is called an \(l\)-form. The main contribution of this paper is the construction of Ramanujan graphs which actually consists of Cayley graphs in the additive group of \(\mathbb{F}_{p^m}\) generated by \(D_{f,i}\), where \(i\in \mathbb{F}_p\), \(f\) is a \(p\)-ary bent function and also an \(l\)-form. The proof is done by computing the eigenvalues of these Cayley graphs based on the Walsh spectrum of \(p\)-ary bent functions.