Ramanujan graphs and expander families constructed from p-ary bent functions

Abstract

We present a method for constructing an infinite family of non-bipartite Ramanujan graphs. We mainly employ p-ary bent functions of $(p-1)$-form for this construction, where p is a prime number. Our result leads to construction of infinite families of expander graphs; this is due to the fact that Ramanujan graphs play as base expanders for constructing further expanders. For our construction we directly compute the eigenvalues of the Ramanujan graphs arsing from p-ary bent functions. Furthermore, we establish a criterion on the regularity of p-ary bent functions in m variables of $(p-1)$-form when m is even. Finally, using weakly regular p-ary bent functions of $\ell$-form, we find (amorphic) association schemes in a constructive way; this resolves the open case that $\ell = p-1$ for $p >2$ for finding (amorphic) association schemes.

1 Introduction

Expanders (or expander graphs) have a great deal of applications in various areas such as computer science, network design, coding theory, cryptography, and even in pure mathematics (for instance, refer to [8, 10, 11, 13, 16, 24, 27]). Briefly speaking, an expander is a highly connected sparse graph; this means that every subset of their vertices has a large set of neighbors. It is well known that Ramanujan graphs are “good” expanders achieving the spectral bound. In fact, a connected k-regular graph is called Ramanujan if it satisfies $|\theta | \le 2 \sqrt{k-1}$ for every eigenvalue $\theta \ne \pm k$ of its adjacency matrix; this definition is motivated by the result that $\liminf _{n\rightarrow \infty }\lambda _2(G_{n,k})\ge 2\sqrt{k-1}$, where $\lambda _2(G_{n,k})$ denotes the second largest eigenvalues of the $G_{n,k}$ being a k-regular graph with n vertices. Furthermore, the spectral gap $k-\lambda _2(G_{n,k})$ should be as large as possible for having expanders of good quality; however, the spectral gap cannot be too large asymptotically as proved by Alon-Boppana [1]. This means that a Ramanujan graph is a connected regular graph whose second largest eigenvalue in absolute value is asymptotically the smallest possible. In general, computation of the eigenvalues of graphs is a hard task. In spectral graph theory, there are some invariants related to eigenvalues of regular graphs such as the cheeger constant, the size of the largest independent sets, the chromatic number and the diameter of regular graphs [31].

For construction of expanders, a graph product, called the zig-zag graph product, is introduced in [26]. The zig-zag product yields simple explicit constructions of constant-degree expanders of arbitrary size, starting from one constant size expander. Therefore, the role of base expanders is very crucial to construction of expanders. We point out that Ramanujan graphs can play as base expanders. We are therefore highly motivated to work on constructing Ramanujan graphs.

Recently, there has been a great deal of developments on construction of Ramanujan graphs. First of all, constructions of Ramanujan graphs with a fixed degree $p+1$ (that is, $(p+1)$-regular Ramanujan graphs) were independently given in [17, 21], where p is an “odd” prime number, and the $(p^m+1)$-regular Ramanujan graphs were studied in [23], where m is a positive integer. Furthermore, the cubic version (that is, $p=2$) of Ramanujan graphs was later studied in [6]. We note that these graphs have a fixed degree and increasing number of vertices.

Furthermore, in [3, 22], they showed that the Cayley graphs associated with some quasi-perfect Lee codes are Ramanujan graphs of degree $p^m+1$ with $p^{2m}$ vertices. All of these constructions used a Weil-Deligne bound on estimation of associated character sums instead of directly computing eigenvalues of the graphs. On the other hand, in [2] they found constructions of bipartite Ramanujan graphs of degree p (respectively, $p^m-1$) with $2p^2$ vertices (respectively, $2p^m d$ vertices, d being a positive integer) by direct computation of eigenvalues of their graphs.

We present a method for constructing an infinite family of non-bipartite Ramanujan graphs of degrees $p^{m-1} \pm \varepsilon (p,m)$ with $p^m$ vertices, where $\varepsilon (p,m)$ is an explicit formula involved with p and m, p is a prime number, and m is a positive integer (Theorems 4.1 and 4.4). We mainly employ p-ary bent functions of $(p-1)$-form for this construction. Our result leads to construction of infinite families of expander graphs with a fixed degree and increasing number of vertices; this is due to the fact that Ramanujan graphs play as base expanders for construction of further expanders. For our construction we directly compute the eigenvalues of the Ramanujan graphs arising from p-ary bent functions. Furthermore, we establish a criterion on the regularity of p-ary bent functions in m variables of l-form when m is even and $l=p-1$; the case that m is even and $l\ne p-1$ for $p>3$ is treated in [12]. We also derive an algebraic formula for the diameter of a Cayley graph. Finally, using weakly regular p-ary bent functions of $(p-1)$-form, we find (amorphic) association schemes in a constructive way; this resolves the open case that $\ell = p-1$ for $p >3$ for finding (amorphic) association schemes.

2 Preliminaries

In this section we introduce the basic definitions and notations regarding p-ary bent functions, strongly regular graphs, Ramanujan graphs, expander graphs and (amorphic) association schemes.

Throughout this paper, m is a positive integer and p is an odd prime number.

2.1 Bent functions

Let $\mathbb {F}_{p^m}$ be the finite field of order $p^m$. For a subset S of $\mathbb {F}_{p^m}$, we denote by $S^*$ the set of nonzero elements of S.

A p-ary functionf in m variables is just a function from $\mathbb {F}_{p^m}$ to $\mathbb {F}_p$. We say that a p-ary function f is even if $f(-x)=f(x)$ for any $x\in \mathbb {F}_{p^m}$. We define $D_{f,i}$ to be the set

$$\begin{aligned} D_{f,i}=\{\beta \in \mathbb {F}^*_{p^m}:f(\beta )=i\}. \end{aligned}$$

For some $l\in \mathbb {F}^*_p$, we say that a p-ary function f in m variables is an l-form if $f(ax)=a^lf(x)$ for any $a\in \mathbb {F}^*_p$ and $x\in \mathbb {F}_{p^m}$.

The Walsh–Hadamard transform$W_f$ of a p-ary function f in m variables is a complex-valued function of $\mathbb {F}_{p^m}$ defined by

$$\begin{aligned} W_f(\beta )=\sum \limits _{x\in \mathbb {F}_{p^m}}\zeta ^{f(x)-\text {Tr}(\beta x)}_p, \end{aligned}$$

where $\zeta _p=e^{\frac{2\pi \sqrt{-1}}{p}}$ is a primitive pth root of unity, and $\text {Tr}^k_1$ is the trace function from $\mathbb {F}_{p^k}$ to $\mathbb {F}_{p}$ defined by $\sum _{j=0}^{k-1}x^{p^j}$. Throughout this paper, let $\text {Tr}$ denote $\text {Tr}^m_1.$

The inverse Walsh–Hadamard transform of a p-ary function f is given by

$$\begin{aligned} \zeta ^{f(\beta )}_p=p^{-m}\sum \limits _{x\in \mathbb {F}_{p^m}}W_f(x)\zeta ^{\text {Tr}(\beta x)}_p. \end{aligned}$$

The Fourier transform$\hat{f}$ of a p-ary function f in m variables is a complex-valued function of $\mathbb {F}_{p^m}$ defined by

$$\begin{aligned} \hat{f}(\beta )=\sum \limits _{x\in \mathbb {F}_{p^m}}f(x)\zeta ^{\text {Tr}(\beta x)}_p. \end{aligned}$$

We say that a p-ary function f in m variables is $bent$ if $|W_f(\beta )|^2=p^m$ for any $\beta \in \mathbb {F}_{p^m}$. In this case, it is known [15] that

$$\begin{aligned} W_f(\beta )=\left\{ \begin{array}{ll} \pm p^{\frac{m}{2}}\zeta ^{g(\beta )}_p &{} \text{ if } \; m \text{ even, } \text{ or } m \text{ odd } \text{ and } p\equiv 1~(\text{ mod } 4),\\ \pm \sqrt{-1}p^{\frac{m}{2}}\zeta ^{g(\beta )}_p &{} \text{ if } m \text{ odd } \text{ and } p\equiv 3~(\text{ mod } 4) \end{array}\right. \end{aligned}$$

for some p-ary function g in m variables. We denote by $1_S$ the characteristic function of a subset S of $\mathbb {F}_{p^m}$. Then the Walsh–Hadamard transform of a p-ary bent function f can be written as

$$\begin{aligned} W_f(\beta )=(-1)^{1_S(\beta )}(p^*)^{\frac{m}{2}}\zeta ^{g(\beta )}_p, \end{aligned}$$

where S is a subset of $\mathbb {F}_{p^m}$, $p^*=(-1)^{(p-1)/2}p$, and g is a p-ary function in m variables. A p-ary bent function f is weakly regular if there is a complex $\alpha$ with unit magnitude such that $W_f (\beta ) = \alpha p^{\frac{m}{2}}\zeta ^{\tilde{f}(\beta )}_p$ for some p-ary function $\tilde{f}$ in m variables. That is, if S is the ambient space or an empty set, then f is weakly regular bent. In this case, we call $\tilde{f}$ the dual off. In particular, when $\alpha =1$ (or $S=\emptyset$), we say that f is regularp-ary bent. When f is weakly regular bent, we have

$$\begin{aligned} W_{\tilde{f}} (\beta ) = \left( \frac{-1}{p}\right) ^m(-1)^{1_S(\beta )} (p^*)^{\frac{m}{2}}\zeta ^{f(-\beta )}_p, \end{aligned}$$

(1)

where $\left( \frac{\cdot }{\cdot }\right)$ is the Legendre symbol. This shows that the dual $\tilde{f}$ of a weakly regular p-ary bent function f is also weakly regular p-ary bent and $\tilde{\tilde{f}}(x)=f(-x)$ for all $x\in \mathbb {F}_{p^m}$.

Let $\mathcal {B}_l(m,p)$ (respectively, $\mathcal {B}^w_l(m,p)$) be the set of p-ary bent functions (respectively, weakly regular p-ary bent functions) in m variables of l-form, where $(l-1,p-1)=1$ and $f(0)=0$. In this paper, we mainly deal with $\mathcal {B}_{p-1}(m,p)$; for the case that $l \ne p-1$, $\mathcal {B}_l(m,p)$ were studied by the authors in [12].

We introduce a family of p-ary bent functions in m variables of $(p-1)$-form, which can be found in [29] as follows.

Firstly, we consider the case that $m = 2k$ and p is an odd prime number. A p-ary function f from $\mathbb {F}_{p^m}$ to $\mathbb {F}_p$ defined by

$$\begin{aligned} f (x) =\sum _{i=1}^{p^k-1}\text {Tr}^m_1(c_ix^{i(p^k-1)})+\text {Tr}^l_1\left( \alpha x^{\frac{p^m-1}{e}}\right) , \end{aligned}$$

is known to be regular bent of $(p-1)$-form, called Dillon-type bent, where $e \mid (p^k + 1)$, $c_i \in \mathbb {F}_{p^m}$ for $0 \le i \le p^k-1$, $\alpha$ in $\mathbb {F}_{p^l}$ and l is the smallest positive integer such that $l \mid m$ and $e \mid (p^l -1)$. On the other hand, there is a sporadic example of a ternary bent function which is not weakly regular bent, that is, $f(x) = \text {Tr}(\zeta ^7_3 x^{98})$ in $\mathbb {F}_{3^6}$.

Secondly, we consider the case that m is odd and p is an odd prime number. Regarding an example of a p-ary monomial bent function of $(p-1)$ form, to the best of our knowledge, a ternary monomial bent function of 2 form is the only example which is known so far. Weakly regular bent functions of Coulter-Matthews class are $f(x)=\text {Tr}(cx^{\frac{3^i+1}{2}})$, where $c\in \mathbb {F}^*_3$, i is odd and $(i,m)=1$.

The character sum$\chi _{\beta }(S)$ of S with respect to $\beta \in \mathbb {F}_{p^m}$ for a subset of $\mathbb {F}_{p^m}$ is defined by

$$\begin{aligned} \chi _{\beta }(S)=\sum \limits _{x\in S}\zeta ^{\text {Tr}(\beta x)}_p. \end{aligned}$$

2.2 Strongly regular Cayley graphs, Ramanujan graphs and expander graphs

We can refer to [9, 14] for this subsection. Let G be a simple undirected graph, that is, an undirected graph without loops and parallel edges. The degree of a vertex is the number of edges adjacent to its vertex. A graph G is called k-regular if every vertex has degree k. The distance$d_G(x,y)$ between two vertices x and y in G is the number of edges in the shortest path from x to y. The diameter of a graph is the maximum among distances between every pair of vertices of G.

The adjacency matrixA of a graph with rows and columns indexed by its vertices is defined by

$$\begin{aligned} A_{xy}=\left\{ \begin{array}{c l} 1 &{} \text{ if } x \text { is adjacent to } y,\\ 0 &{} \text{ otherwise. } \end{array}\right. \end{aligned}$$

Any eigenvalue $\theta$ of A is real because A is symmetric, and $|\theta |\le k$ whenever a graph is k-regular. A connected k-regular graph is called Ramanujan if it satisfies

$$\begin{aligned} |\theta |\le 2\sqrt{k-1} \end{aligned}$$

for every eigenvalue $\theta \ne \pm k$ of its adjacency matrix. A k-regular graph is bipartite if and only if $-k$ is also an eigenvalue of its adjacency matrix. In [20], it is shown that for every $k\ge 3$, there is a bipartite k-regular Ramanujan graph using a nonconstructive method.

A k-regular graph G with v vertices is said to be strongly regular (SRG) with parameters $(v,k,\lambda ,\mu )$ if there are integers $\lambda$ and $\mu$ such that any two adjacent vertices have $\lambda$ common neighbors, and any two non-adjacent vertices have $\mu$ common neighbors. The complete graph and disjoint unions of complete graphs are the only SRG’s with two eigenvalues. Otherwise, the adjacency matrix of a SRG has precisely two distinct restricted eigenvalues (eigenvectors perpendicular to the all-ones vector), say, $\theta _{1}$ and $\theta _{2}$. There are relations between them as follows; $\mu -k=\theta _1\theta _2$ and $\lambda -\mu =\theta _1+\theta _2$. A connected regular graph with only two or three eigenvalues is strongly regular. We say that a SRG with parameters $(n^2, r(n+\delta ),-\delta n+r^2 +3\delta r, r^2 +\delta r)$ is of Latin square type if $\delta =-1$ and of negative Latin square type if $\delta = 1$.

Let S be a subset of $\mathbb {F}_{p^m}$ such that $0\notin S$ and $S=-S$. The Cayley graph$G={\text {Cay}}(\mathbb {F}_{p^m},S)$ has a vertex set $\mathbb {F}_{p^m}$, and two vertices $\alpha$ and $\beta$ in $\mathbb {F}_{p^m}$ are joined by an edge if and only if $\alpha -\beta \in S$. Then the Cayley graph G is a simple undirected graph, |S|-regular and vertex-transitive. Moreover, G is connected if and only if S generates $\mathbb {F}_{p^m}$.

Result 1

[9] Let S be a subset of $\mathbb {F}_{p^m}$ such that $S=-S$ and $0\not \in S$. Then the set $\{\chi _{\beta }(S):\beta \in \mathbb {F}_{p^m}\}$ is precisely the set of eigenvalues of the adjacency matrix of ${\text {Cay}}(\mathbb {F}_{p^m},S)$.

In order to construct Ramanujan graphs from the Cayley graph ${\text {Cay}}(\mathbb {F}_{p^m},S)$, we require an inequality that

$$\begin{aligned} |\chi _{\beta }(S)|\le 2\sqrt{|S|-1} \end{aligned}$$

for all $\beta \in \mathbb {F}^*_{p^m}$.

Finally, we introduce the expander families of k-regular graphs. The isoperimetric constanth(G) of a graph G with a vertex set V is defined by

$$\begin{aligned} h(G)=\min \{|\partial F|/|F|:F\subset V \text { and } |F|\le |V|/2\}, \end{aligned}$$

where $\partial F$, called the boundary of F, is the set of edges connecting F to $V\setminus F$.

Let k be a positive integer. Let $(G_n)$ be a sequence of k-regular graphs with $|G_n|\rightarrow \infty$ as $n\rightarrow \infty$. We say that $(G_n)$ is an expander family if the sequence $(h(G_n))$ is bounded away from zero, that is, there is a real number $\varepsilon >0$ such that $h(G_n)\ge \varepsilon$ for all n.

Let $(G_n)$ be a sequence of k-regular graphs with $|G_n|\rightarrow \infty$ as $n\rightarrow \infty$. Then $(G_n)$ is an expander family if and only if the sequence

$$\begin{aligned} (k-(\text {the second largest eigenvalue of } G_n)/k \end{aligned}$$

is bounded away from zero.

We say that G is a $(v,k,\varepsilon )$-expander if it is a k-regular expander graph with v vertices such that there is a constant $\varepsilon >0$ provided that

$$\begin{aligned} (\text {the second largest eigenvalue of } G)/k\le \varepsilon . \end{aligned}$$

Reingold et al. in [26] proved the following result which allows us to construct the families of expander graphs with constant degree.

Result 2

Let G be a $(v_1,k_1,\varepsilon _1)$-expander and H be a $(k_1,k_2,\varepsilon _2)$-expander. Then the zig-zag product $G\circ _Z H$ is a $(v_1k_1,k_2^2,\varepsilon _1+\varepsilon _2+\varepsilon ^2_2)$-expander, where for the definition of zig-zag product, see [26].

Using this result, they provided a simple combinatorial construction of constant-degree expander graphs. See Theorem 1.4 of [26].

2.3 Association schemes

Let X be a finite set. A symmetric d-class association scheme$(X, \{R_l\})_{l=0}^d$ is a partition of $X\times X$ into binary relations (or classes) $R_0,R_1,\ldots ,R_d$ with the properties that

• $R_0=\{(x,x):x\in X\};$

• $R_l$ is symmetric for $l=1,2,\ldots ,d,$ that is, $(x,y)\in R_l$ if and only if $(y,x)\in R_l;$

• for all i, j, k in {0,1,...,d} there is an integer $c^k_{ij}$ such that for all $(u,v)\in R_k$,

  $$\begin{aligned} c^k_{ij}=|\{w\in X:(u,w)\in R_i \text{ and } (w,v)\in R_j\}|. \end{aligned}$$

Zinoviev and Ericson in [32] proved the following result.

Result 3

Let $P=P_0|P_1|\ldots |P_d$ be a partition of $\mathbb {F}_{p^m}$, where $P_0=\{0\}$, and let $R_i$ be a partition of $\mathbb {F}_{p^m}\times \mathbb {F}_{p^m}$ defined by

$$\begin{aligned} (\alpha ,\beta )\in R_i \Leftrightarrow \alpha -\beta \in P_i, i=0,1,\ldots ,d. \end{aligned}$$

Then $(\mathbb {F}_{p^m}, \{R_l\})_{l=0}^d$ is a symmetric association scheme on $\mathbb {F}_{p^m}$ if and only if there is another partition $Q=Q_0|Q_1|\ldots ,|Q_d$ such that for any $i,j\in \{0,1,\ldots ,p-1\}$, the sum $\chi _{\alpha }(P_i)$ does not depend on the choice of $\alpha \in Q_j$, and the sum $\chi _{\beta }(Q_i)$ does not depend on the choice of $\beta \in P_j$.

Each symmetric relation $R_l$$(1\le l\le d)$ corresponds to an undirected Cayley graph $G_l={\text {Cay}}(X,R_l)$ [9] with a vertex set X and an edge set $R_l$, where $R_l$ is defined by the following: uv is an edge of $G_l$ if and only if $(u,v)\in R_l$. We thus regard an association scheme $(X, \{R_l\})_{l=0}^d$ as an edge-decomposition of the complete graph on X into graphs $G_l$ such that for all i, j, k in $\{1,2,\ldots , d\}$ and for all $uv\in E(G_k),$

$$\begin{aligned} |\{w\in X : uw\in E(G_i) \text{ and } wv\in E(G_j)\}|=c^k_{ij}, \end{aligned}$$

where $E(G_l)$ denotes the edge set of $G_l$. The Cayley graphs $G_l$ will be called the graphs of the association scheme$(X, \{R_l\})_{l=1}^d$. Each Cayley graph $G_l$ of the association scheme $(X, \{R_l\})_{l=0}^d$ is regular with valency (or degree) $c^0_{ll}$; that is, each vertex of $G_l$ is adjacent to exactly $c^0_{ll}$ edges.

An association scheme is amorphic if any of the union of its classes is also an association scheme. van Dam proved the following result in [30]:

Result 4

[30] Let X be a finite set and $\{G_1, G_2,\ldots , G_d\}$ be an edge-decomposition of the complete graph on X, where each $G_l$ is a strongly regular graph on X. If the $G_l$ are all of Latin square type or all of negative Latin square type, then the decomposition is a d-class amorphic association scheme on X.

3 Auxiliary results

In this section, we introduce basic results on the p-ary bent functions of $(p-1)$-form which will be used in the next sections. In particular, we provide a characterization of p-ary bent functions of $(p-1)$-form in terms of strongly regular graphs. We also develop an algebraic formula of a Cayley graph by computing its diameter.

Lemma 3.1

Let $S_1$ and $S_2$ be nonempty subsets of $\mathbb {F}_{p^m}$. Then the following statements hold.

• (i) If $\chi _{\beta }(S_1)=\chi _{\beta }(S_2)$ for all $\beta \in \mathbb {F}_{p^m}$, then $S_1=S_2$.

• (ii) $\chi _{\beta }(S_1)^{\sigma _a}=\chi _{\beta }(aS_1)=\chi _{a\beta }(S_1)$ for all $a\in \mathbb {F}^*_{p}$, where $\sigma _a$ is a Galois automorphism defined by $\sigma _a(\zeta _p)=\zeta ^{a}_p$.

Proof

(i):

The result follows from [12], Lemma IV.2].

(ii):

It follows that for $a\in \mathbb {F}^*_{p}$,

$$\begin{aligned} \chi _{\beta }(S_1)^{\sigma _a}=\sum _{x \in S_1}\zeta _p^{\text {Tr}(\beta a x)} =\sum _{x\in a S_1}\zeta _p^{\text {Tr}(\beta x)}=\chi _{\beta }(aS_1). \end{aligned}$$

$\square$

Lemma 3.2

Let $f\in \mathcal {B}_l(m,p)$. We write $W_f(\beta )$ as $W_f(\beta )=(-1)^{1_S(\beta )}(p^*)^{\frac{m}{2}}\zeta ^{g(\beta )}_p$ for all $\beta \in \mathbb {F}_{p^m}$. Then $g(0)=0$.

Proof

The result follows from the same argument of the proof in [29, Proposition 4]. $\square$

In the following proposition, we provide a characterization for p-ary bent functions of $(p-1)$-form. It will be exploited in Lemmas 3.4 and 3.7.

Proposition 3.3

Let $f\in \mathcal {B}_l(m,p)$. Then the following statements are equivalent.

• (i) Every eigenvalue of ${\text {Cay}}(\mathbb {F}_{p^m},D_{f,i})$$(0\le i\le p-1)$ is a rational integer, where f is even.

• (ii) $aD_{f,i}=D_{f,i}$ for all $a\in \mathbb {F}^*_p$ and $i=0,1,\ldots ,p-1$.

• (iii) f is $(p-1)$-form, i.e., $f(ax)=f(x)$ for all $(a,x)\in \mathbb {F}^*_p\times \mathbb {F}_{p^m}$.

Proof

$(i)\Rightarrow (ii)$; by the assumption and Result 1, the sum $\chi _{\beta }(D_{f,i})$ is a rational integer for all $\beta \in \mathbb {F}_{p^m}$ and $i=1,2,\ldots ,p-1$. By Lemma 3.1-(ii), we have that

$$\begin{aligned} \chi _{\beta }(D_{f,i})=\chi _{\beta }(D_{f,i})^{\sigma _a}=\chi _{\beta }(a D_{f,i}) \end{aligned}$$

for all $a\in \mathbb {F}^*_{p}$. The result follows from Lemma 3.1-(i).

$(ii)\Rightarrow (iii)$; let $W_f(\beta )=(-1)^{1_S(\beta )}(p^*)^{\frac{m}{2}}\zeta ^{g(\beta )}_p$. Then by the assumption and Lemma 3.1-(ii), we have that for $a\in \mathbb {F}^*_p$,

$$\begin{aligned} (-1)^{1_S(a\beta )}(p^*)^{\frac{m}{2}}\zeta ^{g(a\beta )}_p= & {} W_f(a\beta )=\sum _{i=0}^{p-1}\chi _{a\beta }(D_{f,i})\zeta ^i_p =\sum _{i=0}^{p-1}\chi _{\beta }(a D_{f,i})\zeta ^i_p\\= & {} \sum _{i=0}^{p-1}\chi _{\beta }(D_{f,i})\zeta ^i_p =(-1)^{1_S(\beta )}(p^*)^{\frac{m}{2}}\zeta ^{g(\beta )}_p, \end{aligned}$$

so that $g(a\beta )=g(\beta )$ and $1_S(a\beta )=1_S(\beta )$ for all $(a,\beta )\in \mathbb {F}^*_p\times \mathbb {F}_{p^m}$. This implies that $W_f(a\beta )=W_f(\beta )$ for all $(a,\beta )\in \mathbb {F}^*_p\times \mathbb {F}_{p^m}$. It then follows from the inversion formula of $W_f(\beta )$ that for $(a,\beta )\in \mathbb {F}^*_p\times \mathbb {F}_{p^m}$,

$$\begin{aligned} \zeta ^{f(a\beta )}_p= & {} p^{-m}\sum _{x\in \mathbb {F}_{p^m}}W_f(x)\zeta ^{\text {Tr}(a\beta x)}_p =p^{-m}\sum _{x\in \mathbb {F}_{p^m}}W_f(a^{-1}x)\zeta ^{\text {Tr}(\beta x)}_p\\= & {} p^{-m}\sum _{x\in \mathbb {F}_{p^m}}W_f(x)\zeta ^{\text {Tr}(\beta x)}_p =\zeta ^{f(\beta )}_p. \end{aligned}$$

The result follows.

$(iii)\Rightarrow (ii)$; let $x\in aD_{f,i}$ for $a\in \mathbb {F}^*_p$. Then $x=ay$ for some $y\in D_{f,i}$, and so by the assumption, $f(x)=f(ay)=f(y)=i$. Thus $x\in D_{f,i}$. Conversely, let $x\in D_{f,i}$. By the assumption, for $a\in \mathbb {F}^*_p$, we have $f(a^{-1}x)=f(x)=i$, and so $a^{-1}x\in D_{f,i}$. Thus $x\in aD_{f,i}$.

$(ii)\Rightarrow (i)$; it follows from Lemma 3.1-(ii) and the assumption that $\chi _{\beta }(D_{f,i})^{\sigma _a}=\chi _{\beta }(aD_{f,i})=\chi _{\beta }(D_{f,i})$ for all $(a,\beta )\in \mathbb {F}^*_p\times \mathbb {F}_{p^m}$, where $\sigma _a$ is a Galois automorphism. Thus $\chi _{\beta }(D_{f,i})$ is a rational integer. $\square$

Lemma 3.4

Let m be a positive even integer. Let $f\in \mathcal {B}_l(m,p)$ with $l=p-1$ and $W_f(\beta )=(-1)^{1_S(\beta )}p^{\frac{m}{2}}\zeta ^{g(\beta )}_p$ for all $\beta$ in $\mathbb {F}_{p^m}$. Then ${\text {Cay}}(\mathbb {F}_{p^m},D_{f,i})$ has at most five eigenvalues for all $i=0,1,\ldots ,p-1$ as follows:

$$\begin{aligned} |D_{f,0}|&=p^{m-1}+(-1)^{1_S(0)} p^{\frac{m}{2}-1}(p-1)-1, \\ |D_{f,i}|&=p^{m-1}-(-1)^{1_S(0)} p^{\frac{m}{2}-1}~(1\le i\le p-1),\\ \chi _{\beta }(D_{f,i})&={\left\{ \begin{array}{ll} (-1)^{1_S(\beta )} p^{\frac{m}{2}-1}(p-1)&{} \text { if } i=g(\beta ),\beta \ne 0,\\ -(-1)^{1_S(\beta )} p^{\frac{m}{2}-1}&{} \text { if } i \not = g(\beta ), \beta \ne 0. \end{array}\right. } \end{aligned}$$

Proof

We use the set $\{1,\zeta _{p},\zeta _p^2,\ldots ,\zeta _p^{p-2}\}$, which is linearly independent over $\mathbb {Q}$. Let us put $D_i=D_{f,i}$ for a simplicity of notation.

Since m is even, we can write $W_f(\beta )$ as $W_f(\beta )=(-1)^{1_S(\beta )} p^{\frac{m}{2}} \zeta _p^{g(\beta )}$, where S is a subset of $\mathbb {F}_{p^m}$ and g is a p-ary function in m variables. Applying the equation $\sum _{i=0}^{p-1}\zeta _{p}^i=0$, we have that

$$\begin{aligned} (-1)^{1_S(\beta )} p^{\frac{m}{2}} \zeta _p^{g(\beta )}=W_{f}(\beta )=\sum _{i=0}^{p-1}\chi _{\beta }(D_i)\zeta _p^{i} =\sum _{i=0}^{p-2}(\chi _{\beta }(D_i)-\chi _{\beta }(D_{p-1}))\zeta _p^i. \end{aligned}$$

(2)

It then follows from Lemma 3.2 that for $\beta =0$,

$$\begin{aligned} (-1)^{1_S(0)} p^{\frac{m}{2}}=\sum _{i=0}^{p-2}(|D_i|-|D_{p-1}|)\zeta _p^i, \end{aligned}$$

which implies that

$$\begin{aligned} |D_i|-|D_{p-1}|&=0,~~ 1\le i\le p-2, \\ |D_0|-|D_{p-1}|&=(-1)^{1_S(0)} p^{\frac{m}{2}}. \end{aligned}$$

Solving these equations together with $\sum _{i=0}^m|D_i|=p^m-1$, we have the first two parts. To demonstrate the last part, we consider the following two cases with $\beta \in \mathbb {F}^*_{p^m}$. Firstly, assume that $g(\beta )\not =p-1$. It follows from (2) and Proposition 3.3 that

$$\begin{aligned} \chi _{\beta }(D_i)-\chi _{\beta }(D_{p-1})&=0,~ i \not =g(\beta ),\\ \chi _{\beta }(D_i)-\chi _{\beta }(D_{p-1})&=(-1)^{1_S(\beta )} p^{\frac{m}{2}} \zeta _p^{g(\beta )},~ i =g(\beta ). \end{aligned}$$

Solving these equations together with $\sum _{i=0}^{p-1}\chi _{\beta }(D_i)=1$, we get the last part. Secondly, assume that $g(\beta )=p-1$. It follows from (2) that

$$\begin{aligned} -(-1)^{1_S(\beta )} p^{\frac{m}{2}}\sum _{i=0}^{p-2}\zeta _p^i =\sum _{i=0}^{p-2}(\chi _{\beta }(D_i)-\chi _{\beta }(D_{p-1}))\zeta _p^i, \end{aligned}$$

which implies by Proposition 3.3 that

$$\begin{aligned} \chi _{\beta }(D_i)-\chi _{\beta }(D_{p-1})=-(-1)^{1_S(\beta )} p^{\frac{m}{2}},~ 0\le i \le p-2. \end{aligned}$$

Solving these equations together with $\sum _{i=0}^{p-1}\chi _{\beta }(D_i)=1$, we also have the last part. These complete the lemma. $\square$

Corollary 3.5

Let m be a positive even integer and $f\in \mathcal {B}^w_l(m,p)$ with $l=p-1$. Then the following statements are true.

• (i) If $p>3$, then f must be regular bent.

• (ii) ${\text {Cay}}(\mathbb {F}_{p^m},D_{f,0})$ is a strongly regular graph with parameters

  $$\begin{aligned} (p^m,p^{m-1}+(p-1)p^{\frac{m}{2}-1}-1,p^{m-2}+(p-1)p^{\frac{m}{2}-1}-2,p^{m-2}+p^{\frac{m}{2}-1}) \end{aligned}$$

  (3)

  and ${\text {Cay}}(\mathbb {F}_{p^m},D_{f,i})$ is a strongly regular graph with parameters

  $$\begin{aligned} (p^m,p^{m-1}- p^{\frac{m}{2}-1},p^{m-2}+ p^{\frac{m}{2}-1}(p-3),p^{m-2}- p^{\frac{m}{2}-1}) \end{aligned}$$

  (4)

  for all $i=1,\ldots ,p-1$.

Proof

(i):

Assume that f is weakly p-ary regular bent, which is not regular bent. It follows from Lemma 3.4 with $S=\mathbb {F}_{p^m}$ and Preliminaries 2.2 that we can compute the parameters of ${\text {Cay}}(\mathbb {F}_{p^m},D_{f,i})$ for $i=1,\ldots ,p-1$ as follows:

$$\begin{aligned} (p^m,p^{m-1}+p^{\frac{m}{2}-1},p^{m-2}-p^{\frac{m}{2}-1}(p-3), p^{m-2}+ p^{\frac{m}{2}-1}). \end{aligned}$$

Notice that $\Delta =\sqrt{(\lambda -\mu )^2+4(k-\mu )}=p^m$, which is a square. Applying Ma’s result [18, Theorem 6.8] under condition that $\Delta$ is a square, their degrees are divided by $p-1$. This implies that $p=3$, a contradiction. This proves (i).

(ii):

By using Proposition 3.4 with $S=\emptyset$ and Preliminaries 2.2, the result follows.

$\square$

Remark 3.6

A SRG with parameters (2) which is known in [5] is of Latin square type. A SRG with parameters (3) which do not occur in [29] is also of Latin square type. When $p=3$, the parameters (2) and (3) coincide with those of the result in [28]. However, for the case that $p \ne 3$, it is hard to check if SRG’s with parameters (3) is new since there are too many SRG’s of Latin square type [4] constructed from the block graphs [7] of orthogonal arrays.

Lemma 3.7

Let m be a positive odd integer. Let $f\in \mathcal {B}_l(m,p)$ with $l=p-1$ and $W_f(\beta )=(-1)^{1_S(\beta )}(p^*)^{\frac{m}{2}}\zeta ^{g(\beta )}_p$ for all $\beta$ in $\mathbb {F}_{p^m}$. Then ${\text {Cay}}(\mathbb {F}_{p^m},D_{f,i})$ has at most four eigenvalues for all $i=0,1,\ldots ,p-1$ as follows:

$$\begin{aligned} |D_{f,i}|&= {\left\{ \begin{array}{ll} p^{m-1}-1 &{} \text { if } i=0, \\ p^{m-1}+ (-1)^{1_S(0)} p^{\frac{m-1}{2}} &{} \text { if } i \not = 0 \text { and } \Big (\frac{i}{p}\Big )=1,\\ p^{m-1} -(-1)^{1_S(0)} p^{\frac{m-1}{2}} &{} \text { if } i \not = 0\text { and } \Big (\frac{i}{p}\Big )=-1, \end{array}\right. }\\ \chi _{\beta }(D_{f,i})&= {\left\{ \begin{array}{ll} 0 &{} \text { if } i=g(\beta ), \beta \ne 0,\\ (-1)^{1_S(\beta )}p^{\frac{m-1}{2}}&{} \text { if } i \not = g(\beta ), \beta \ne 0, \text { and } \Big (\frac{i-g(\beta )}{p}\Big )=1,\\ -(-1)^{1_S(\beta )}p^{\frac{m-1}{2}}&{} \text { if } i \not = g(\beta ), \beta \ne 0, \text { and } \Big (\frac{i-g(\beta )}{p}\Big )=-1, \end{array}\right. } \end{aligned}$$

where $\Big (\frac{i}{p}\Big )$ stands for the Legendre symbol.

Proof

We use the set $\{1,\zeta _{p},\zeta _p^2,\ldots ,\zeta _p^{p-2}\},$ which is linearly independent over $\mathbb {Q}$. Let us put $D_i=D_{f,i}$ for a simplicity of notation.

Note that

$$\begin{aligned} \sum _{i=0}^{p-1}\zeta _p^{i^2}= {\left\{ \begin{array}{ll} \sqrt{p} &{} \text { if } p\equiv 1 \pmod {4},\\ \sqrt{-p} &{} \text { if } p\equiv 3 \pmod {4}. \end{array}\right. } \end{aligned}$$

We then have that

$$\begin{aligned} (-1)^{1_S(\beta )} \Bigg (\sum _{i=0}^{p-1}\zeta _p^{i^2}\Bigg ) p^{\frac{m-1}{2}} \zeta _p^{g(\beta )} =W_{f}(\beta )=\sum _{i=0}^{p-1}\chi _{\beta }(D_i)\zeta _p^{i}. \end{aligned}$$

(5)

Set $T:=\{i \in \mathbb {Z}_p : i\equiv a^2 \pmod {p},~ a \in \mathbb {Z}^*_p\}$. Then the left hand side of (4) is written as follows:

$$\begin{aligned} (-1)^{1_S(\beta )}p^{\frac{m-1}{2}} \Bigg ( \zeta _p^{g(\beta )}+2 \sum _{i \in T} \zeta _p^{i+g(\beta )}\Bigg )&= (-1)^{1_S(\beta )} p^{\frac{m-1}{2}} \nonumber \\&\quad \times \Bigg (-\sum _{i=0, i \not = g(\beta )}^{p-1}\zeta _{p}^i+ 2 \sum _{i \in T} \zeta _p^{i+g(\beta )}\Bigg ) \end{aligned}$$

(6)

because $-\sum _{i=0, i \not = g(\beta )}^{p-1}\zeta _{p}^i=\zeta _p^{g(\beta )}$. On the other hand, the right hand side of (4) is equal to

$$\begin{aligned} \sum _{i=0, i \not =g(\beta )}^{p-1} \Big ( \chi _{\beta }(D_i)-\chi _{\beta }(D_{g(\beta )})\Big )\zeta _p^i. \end{aligned}$$

(7)

We now use the linearly independence of $\{1,\zeta _{p},\ldots ,\zeta ^{g(\beta )-1},\zeta ^{g(\beta )+1},\ldots ,\zeta _p^{p-1}\}$ over $\mathbb {Q}$. By comparing (5) with (6) and using Proposition 3.3, we get the following:

$$\begin{aligned} \chi _{\beta }(D_i)-\chi _{\beta }(D_{g(\beta )})&=(-1)^{1_S(\beta )} p^{\frac{m-1}{2}} \text { if } \Big ( \frac{i-g(\beta )}{p}\Big )=1 \text { and } i\ne g(\beta ), \end{aligned}$$

(8)

$$\begin{aligned} \chi _{\beta }(D_i)-\chi _{\beta }(D_{g(\beta )})&=-(-1)^{1_S(\beta )} p^{\frac{m-1}{2}} \text { if } \Big ( \frac{i-g(\beta )}{p}\Big )=-1 \text { and }i\ne g(\beta ). \end{aligned}$$

(9)

From (7) and (8), we have that

$$\begin{aligned} \sum _{i=0, i \not =g(\beta )}^{p-1}( \chi _{\beta }(D_i)-\chi _{\beta }(D_{g(\beta )})=0. \end{aligned}$$

(10)

The second part of this lemma follows from solving Eqs. (7–9) together with $\sum _{i=0}^{p-1}\chi _{\beta }(D_i)=1$ for $\beta \in \mathbb {F}^*_{p}$.

Now, we consider the case that $\beta =0$. By Lemma 3.2 we have that $g(0)=0$. It follows from (7) and (8) that

$$\begin{aligned} |D_i|-|D_{0}|&=(-1)^{1_S(0)} p^{\frac{m-1}{2}}\;\text {if}\;\Big (\frac{i}{p}\Big )=1, \end{aligned}$$

(11)

$$\begin{aligned} |D_i|-|D_{0}|&=-(-1)^{1_S(0)} p^{\frac{m-1}{2}} \;\text {if}\;\Big (\frac{i}{p}\Big )=-1. \end{aligned}$$

(12)

The first part of this lemma follows from solving Eqs. (10) and (11) together with $\sum _{i=0}^{p-1}|D_i|=p^m-1$. $\square$

To derive an algebraic formula for the diameter of a Cayley graph, we require the following lemma.

Lemma 3.8

Let $\gamma$ be contained in $\mathbb {F}_{p^m}$ and let S be a nonempty subset of $\mathbb {F}_{p^m}$. Then the number of t-tuples $(\alpha _1,\alpha _2,\ldots ,\alpha _t)\in S^t$ such that $\alpha _1+\alpha _2+\cdots +\alpha _t=\gamma$ is equal to

$$\begin{aligned} \sum _{\beta \in \mathbb {F}_{p^m}}\chi _{\beta }(-S)^t\zeta ^{\text {Tr}(\beta \gamma )}_p. \end{aligned}$$

Proof

We compute the following sum:

$$\begin{aligned} \sum _{\alpha _1\ldots ,\alpha _t\in \mathbb {F}_{p^m}}1_S(\alpha _1)\ldots 1_S(\alpha _t)1_{\{\gamma \}}(\alpha _1+\cdots +\alpha _t). \end{aligned}$$

Then this sum becomes

$$\begin{aligned}&\frac{1}{p^m}\sum _{\alpha _1\ldots ,\alpha _t\in \mathbb {F}_{p^m}}1_S(\alpha _1)\ldots 1_S(\alpha _t) \sum _{\delta \in \mathbb {F}_{p^m}}\hat{1}_{\{\gamma \}}(\delta )\zeta ^{-\text {Tr}((\alpha _1+\alpha _2+\cdots +\alpha _t)\delta )}_p\\&\quad = \frac{1}{p^m}\sum _{\delta \in \mathbb {F}_{p^m}}\hat{1}_{\{\gamma \}}(\delta )\prod _{i=1}^t \sum _{\alpha _i\in \mathbb {F}_{p^m}}1_S(\alpha _i)\zeta ^{-\text {Tr}(\alpha _i\delta )}_p\\&\quad = \frac{1}{p^m}\sum _{\delta \in \mathbb {F}_{p^m}}\zeta ^{\text {Tr}(\delta \gamma )}_p\chi _{\delta }(-S)^t. \end{aligned}$$

The result thus follows. $\square$

Proposition 3.9

Let S be a nonempty subset of $\mathbb {F}_{p^m}$ with $S=-S$ and $0\notin S$. Then the diameter of $G={\text {Cay}}(\mathbb {F}_{p^m},S)$ is the smallest integer $t>1$ such that

$$\begin{aligned} \sum _{\beta \in \mathbb {F}_{p^m}}\chi _{\beta }(S)^t\zeta ^{\text {Tr}(\beta \gamma )}_p \end{aligned}$$

does not vanish for all $\gamma \in \mathbb {F}_{p^m}$.

Proof

Notice that the diameter of G is the smallest integer $t>1$ such that $\mathbb {F}_{p^m}=S+S+\cdots +S$ (t times), where $S+S=\{\alpha +\beta :\alpha ,\beta \in S\}$, and the result follows from Lemma 3.8. $\square$

4 Ramanujan graphs

Let $f\in \mathcal {B}_l(m,p)$ with $l=p-1$. Recall from Lemmas 3.4 and 3.7 that each Cayley graph generated by $D_{f,i}$ for $i=0,1,\ldots ,p-1$ has at most four eigenvalues when m is odd, or five eigenvalues when m is even. In this section, using these lemmas, the regularity of f is characterized in terms of strongly regular graphs as in [12, 28], and (strongly regular) Ramanujan graphs are also derived. It allows us to construct the families of expander graphs using the zig-zag construction introduced in [26]. We divide this section into two subsections depending on m being even or odd.

4.1 Even dimensional cases

Theorem 4.1

Let m be a positive even integer. Let $f\in \mathcal {B}_l(m,p)$ with $l=p-1$ and $W_f(\beta )=(-1)^{1_S(\beta )}p^{\frac{m}{2}}\zeta ^{g(\beta )}_p$ for all $\beta$ in $\mathbb {F}_{p^m}$. Then

• (i) ${\text {Cay}}(\mathbb {F}_{p^m},D_{f,0})$ is a Ramanujan graph if and only if $0\in S$ and $p=3,5$$(m\ge 4)$, or $0\notin S$ and $p=3$$(m\ge 4)$, $p=5$$(m\ge 2)$, where its degree is given in Lemma 3.4.

  Further, if $f\in \mathcal {B}^w_l(m,p)$ and either of the above cases holds, then it has diameter 2.

• (ii) ${\text {Cay}}(\mathbb {F}_{p^m},D_{f,i})$ is a Ramanujan graph of diameter 2 for all $i=1,2,\ldots ,p-1$ if and only if $0\in S$ and $p=3,5$$(m\ge 2)$, or $0\notin S$ and $p=3$$(m\ge 2)$, $p=5$$(m\ge 4)$, where their degrees are given in Lemma 3.7.

Proof

To check if it is a Ramanujan graph, we need to find p and m satisfying that $\Omega _{\beta }(D_{f,i}):=4(|D_{f,i}|-1)-\chi _{\beta }(D_{f,i})^2\ge 0$ for any $\beta \in \mathbb {F}^*_{p^m}$.

(i):

It follows from Lemma 3.4 that

$$\begin{aligned} 0\le \min _{\beta \in \mathbb {F}^*_{p^m}}{\Omega _{\beta }(D_{f,0})}= & {} 4(p^{m-1}+(-1)^{1_S(0)}p^{\frac{m}{2}-1}(p-1)-2)-p^{m-2}(p-1)^2\\= & {} p^{m-2}(-p^2+6p-1)+4(-1)^{1_S(0)}p^{\frac{m}{2}-1}(p-1)-8. \end{aligned}$$

(ii):

It follows from Lemma 3.4 that for $i=1,2,\ldots ,p-1$,

$$\begin{aligned} 0\le \min _{\beta \in \mathbb {F}^*_{p^m}}{\Omega _{\beta }(D_{f,0})}= & {} 4(p^{m-1}-(-1)^{1_S(0)}p^{\frac{m}{2}-1}-1)-p^{m-2}(p-1)^2\\= & {} p^{m-2}(-p^2+6p-1)-4(-1)^{1_S(0)}p^{\frac{m}{2}-1}-4. \end{aligned}$$

Let us now determine the diameter of ${\text {Cay}}(\mathbb {F}_{p^m},D_{f,i})$ for $i=0,1,\ldots ,p-1$. It follows from Lemma 3.4 that

$$\begin{aligned} E_i(\gamma )&:=\sum _{\beta \in \mathbb {F}_{p^m}}\chi _{\beta }(D_{f,i})^2\zeta ^{\text {Tr}(\beta \gamma )}_p\nonumber \\&=|D_{f,i}|^2+\sum _{\beta \in \mathbb {F}_{p^m}\setminus \{0\}} \chi _{\beta }(D_{f,i})^2\zeta _p^{\text {Tr}(\beta \gamma )}\nonumber \\&=|D_{f,i}|^2+\sum _{\begin{array}{c} \beta \in \mathbb {F}_{p^m}\setminus \{0\}\\ g(\beta )=i \end{array}} p^{m-2}(p-1)\zeta _p^{\text {Tr}(\beta \gamma )}+\sum _{\begin{array}{c} \beta \in \mathbb {F}_{p^m}\setminus \{0\}\\ g(\beta )\not =i \end{array}} p^{m-2}\zeta _p^{\text {Tr}(\beta \gamma )}. \end{aligned}$$

(13)

Since $\sum _{\beta \in \mathbb {F}_{p^m}}\zeta _p^{\text {Tr}(\beta \gamma )}=0$ for $\gamma \not =0$, $E_i(\gamma )$ is equal to

$$\begin{aligned}&|D_{f,i}|^2-p^{m-2}+\sum _{\begin{array}{c} \beta \in \mathbb {F}_{p^m}\setminus \{0\}\\ g(\beta )=i \end{array}} p^{m-2}(p-1)\zeta _p^{\text {Tr}(\beta \gamma )}-\sum _{\begin{array}{c} \beta \in \mathbb {F}_{p^m}\setminus \{0\}\\ g(\beta ) =i \end{array}} p^{m-2}\zeta _p^{\text {Tr}(\beta \gamma )}\nonumber \\&\quad =|D_{f,i}|^2-p^{m-2}+p^{m-2}(p-2)(\chi _{\gamma }(D_{g,i})+\delta _{g,i}), \end{aligned}$$

(14)

where $\delta _{g,i}={\left\{ \begin{array}{ll}1 &{} \text {if }0 \in D_{g,i}, \\ 0 &{} \text {if }0 \not \in D_{g,i}.\end{array}\right. }$

From the fact that g is also a weakly regular bent function and $f(-\beta )=f(\beta )$ for any $\beta \in \mathbb {F}_p$, using (1), we have that

$$\begin{aligned} W_{g}(\beta )= (-1)^{1_S(\beta )}\sqrt{p}^m \zeta _p^{f(\beta )}. \end{aligned}$$

(15)

In the case that $\gamma \not =0$ and $f(\gamma )\not =0$, $E_i(\gamma )$ is equal to

$$\begin{aligned}&|D_{f,i}|^2-p^{m-2}+p^{m-2}(p-2)(\chi _{\gamma }(D_{g,i})+\delta _{g,i})\nonumber \\&\quad = {\left\{ \begin{array}{ll} (p^{m-1}-(-1)^{1_S(0)}p^{\frac{m}{2}-1})^2-p^{m-2}+p^{m-2}(p-2)((-1)^{1_S(\gamma )} p^{\frac{m}{2}-1}(p-1)+\delta _{g,i})\\ \text { if } i\not =0 \text { and }i =f(\gamma ), \\ (p^{m-1}-(-1)^{1_S(0)}p^{\frac{m}{2}-1})^2-p^{m-2}+p^{m-2}(p-2)(-(-1)^{1_S(\gamma )} p^{\frac{m}{2}-1}(p-1)+\delta _{g,i})\\ \text { if } i\not =0 \text { and }i \not =f(\gamma ), \\ (p^{m-1}-(-1)^{1_S(0)}p^{\frac{m}{2}-1}(p-1)-1)^2-p^{m-2}+p^{m-2}(p-2)(-(-1)^{1_S(\gamma )} p^{\frac{m}{2}-1}(p-1)+\delta _{g,i})\\ \text { if } i=0 \text { and }i \not =f(\gamma ). \end{array}\right. } \end{aligned}$$

(16)

In the case that $\gamma \not =0$ and $f(\gamma )=0$, $E_i(\gamma )$ is equal to

$$\begin{aligned}&|D_{f,i}|^2-p^{m-2}+p^{m-2}(p-2)(\chi _{\gamma }(D_{g,i})+\delta _{g,i})\nonumber \\&\quad = {\left\{ \begin{array}{ll} (p^{m-1}-(-1)^{1_S(0)}p^{\frac{m}{2}-1}(p-1)-1)^2-p^{m-2}+p^{m-2}(p-2)((-1)^{1_S(\gamma )} p^{\frac{m}{2}-1}(p-1)+\delta _{g,i})\\ \text { if } i=0, \\ (p^{m-1}+ (-1)^{1_S(0)} p^{\frac{m}{2}-1})^2 -p^{m-2}+p^{m-2}(p-2)(-(-1)^{1_S(\gamma )} p^{\frac{m}{2}-1}(p-1)+\delta _{g,i})\\ \text { if } i \not =0. \end{array}\right. } \end{aligned}$$

(17)

We note that

$$\begin{aligned} E_i(0)&=|D_{f,i}|^2+\sum _{\begin{array}{c} \beta \in \mathbb {F}_{p^m}\setminus \{0\}\\ g(\beta )=i \end{array}} p^{m-2}(p-1)+\sum _{\begin{array}{c} \beta \in \mathbb {F}_{p^m}\setminus \{0\}\\ g(\beta )\not =i \end{array}} p^{m-2}\nonumber \\&=|D_{f,i}|^2+p^{m-2}(p-1)(|D_{g,i}|-\delta _{g,i})+p^{m-2}(p^m-|D_{g,i}|-\delta _{g,i}+1). \end{aligned}$$

(18)

It follows from Lemma 3.7 that

$$\begin{aligned} E_i(0)&=|D_{f,i}|^2+p^{2m-2}+p^{m-2}+p^{m-2}(p-2)|D_{g,i}|-p^{m-1}\delta _{g,i}\nonumber \\&= {\left\{ \begin{array}{ll} (p^{m-1}+(-1)^{1_S(0)}p^{\frac{m}{2}-1}(p-1)-1)^2+p^{2m-2}+p^{m-2}\\ +p^{m-2}(p-2)(p^{m-1}+(-1)^{1_S(0)}p^{\frac{m}{2}-1}(p-1)-1)-p^{m-1}\delta _{g,i} &{} \text { if } i=0, \\ (p^{m-1}+ (-1)^{1_S(0)} p^{\frac{m}{2}-1})^2+p^{2m-2}+p^{m-2}\\ +p^{m-2}(p-2)(p^{m-1}+ (-1)^{1_S(0)} p^{\frac{m}{2}-1}) -p^{m-1}\delta _{g,i}&{} \text { if } i \not =0. \end{array}\right. } \end{aligned}$$

(19)

We can see from (16)–(19) that $E_i(\gamma )\not =0$ for any $\gamma \in \mathbb {F}_{p^m}$. This completes the proof by using Proposition 3.9. $\square$

As pointed out in preliminaries, a family of weakly regular p-ary bent functions of $(p-1)$-form exists. This leads to the following corollary, which is a direct consequence of Corollary 3.5 and Theorem 4.1. It can be obtained from the result of [28] as well when $p=3$.

Corollary 4.2

Let m be a positive even integer, and let $f\in \mathcal {B}^w_l(m,p)$ with $l=p-1$. If $p\in \{3,5\}$, then ${\text {Cay}}(\mathbb {F}_{p^m},D_{f,i})$ is a strongly regular Ramanujan graph for all $i=0,1,2,\ldots ,p-1$ and $m\ge 4$.

In [28], a characterization for weakly regularity of a ternary bent function was given, and it was generalized [12] to a p-ary bent function f of l-form except when f is not of $(p-1)$-form.

We now study the regularity of a p-ary bent function of $(p-1)$-form in the following theorem.

Theorem 4.3

Let m be a positive even integer, and let $f\in \mathcal {B}_l(m,p)$ with $l=p-1$. Then the following statements are equivalent.

• (i) f is regular bent.

• (ii) ${\text {Cay}}(\mathbb {F}_{p^m},D_{f,i})$ is a strongly regular graph for some $i=0,1,\ldots ,p-1$.

Further, if (ii) holds, then ${\text {Cay}}(\mathbb {F}_{p^m},D_{f,i})$ is a strongly regular graph for all $i=0,1,\ldots ,p-1$.

Proof

• $(i)\Rightarrow (ii)$; this follows from Corollary 3.5.

• $(ii)\Rightarrow (i)$; let $W_f(\beta )=(-1)^{1_S(\beta )} p^{\frac{m}{2}} \zeta _p^{g(\beta )}$, where S is a subset of $\mathbb {F}_{p^m}$ and g is a p-ary function in m variables. It follows from Lemma 3.4 that $G_{f,i}={\text {Cay}}(\mathbb {F}_{p^m},D_{f,i})$ has at most five eigenvalues for all $i=0,1,\ldots ,p-1$. However, by our assumption, $G_{f,i}$ has two or three eigenvalues. Consequently, S must be either the empty set or the ambient set, that is, f is weakly regular bent. It follows from Corollary 3.5-(i) that f is regular bent. $\square$

4.2 Odd dimensional cases

Theorem 4.4

Let m be a positive odd integer. Let $f\in \mathcal {B}_l(m,p)$ and $W_f(\beta )=(-1)^{1_S(\beta )}(p^*)^{\frac{m}{2}}\zeta ^{g(\beta )}_p$ for all $\beta$ in $\mathbb {F}_{p^m}$.

• (i) ${\text {Cay}}(\mathbb {F}_{p^m},D_{f,0})$ is a Ramanujan graph for all $m\ge 3$.

• (ii) Assume $\Big (\frac{i}{p}\Big )=1$ for $i = 1,2, \ldots , p-1$. Then ${\text {Cay}}(\mathbb {F}_{p^m},D_{f,i})$ is a Ramanujan graph if and only if $0 \in S$ and $m\ge 3$, or $0\notin S$ and $m\ge 1$.

• (iii) Assume $\Big (\frac{i}{p}\Big )=-1$ for $i = 1,2, \ldots , p-1$. Then ${\text {Cay}}(\mathbb {F}_{p^m},D_{f,i})$ is a Ramanujan graph if and only if $0\in S$ and $m\ge 1$, or $0\notin S$ and $m\ge 3$.

In particular, if $f\in \mathcal {B}^w_l(m,p)$, then ${\text {Cay}}(\mathbb {F}_{p^m},D_{f,i})$ has diameter 2 for $i=0,1,\ldots ,p-1$ and $m\ge 3$.

Proof

In order to check if ${\text {Cay}}(\mathbb {F}_{p^m},D_{f,i})$ is a Ramanujan graph, we have to determine p and m satisfying that $\Omega _{\beta }(D_{f,i}):=4(|D_{f,i}|-1)-\chi _{\beta }(D_{f,i})^2\ge 0$ for any $\beta \in \mathbb {F}^*_{p^m}$.

(i):

It follows from Lemma 3.7 that

$$\begin{aligned} 0\le \min _{\beta \in \mathbb {F}^*_{p^m}}{\Omega _{\beta }(D_{f,0})}=3p^{m-1}-8. \end{aligned}$$

(ii), (iii):

They follow from Lemma 3.7 that for $i=1,2,\ldots ,p-1$ and $\Big (\frac{i}{p}\Big )=1$,

$$\begin{aligned} 0\le \min _{\beta \in \mathbb {F}^*_{p^m}}{\Omega _{\beta }(D_{f,i})}=3p^{m-1}+4(-1)^{1_S(0)}p^{\frac{m-1}{2}}-4, \end{aligned}$$

and for $\Big (\frac{i}{p}\Big )=-1$,

$$\begin{aligned} 0\le \min _{\beta \in \mathbb {F}^*_{p^m}}{\Omega _{\beta }(D_{f,i})}=3p^{m-1}-4(-1)^{1_S(0)}p^{\frac{m-1}{2}}-4. \end{aligned}$$

For $\gamma \in \mathbb {F}_{p^m}$ and $i=0,1,\ldots ,p-1$, we define

$$\begin{aligned} E_i(\gamma )=\sum _{\beta \in \mathbb {F}_{p^m}}\chi _{\beta }(D_{f,i})^2\zeta ^{\text {Tr}(\beta \gamma )}_p. \end{aligned}$$

To prove that ${\text {Cay}}(\mathbb {F}_{p^m},D_{f,i})$ has the diameter 2, we show that $E_i(\gamma )\not =0$ for any $\gamma \in \mathbb {F}_{p^m}$. We note that

$$\begin{aligned} E_i(\gamma )&=\sum _{\beta \in \mathbb {F}_{p^m}}\chi _{\beta }(D_{f,i})^2\zeta ^{\text {Tr}(\beta \gamma )}_p =|D_{f,i}|^2+\sum _{\beta \in \mathbb {F}_{p^m}\setminus \{0\}} \chi _{\beta }(D_{f,i})^2\zeta _p^{\text {Tr}(\beta \gamma )}\nonumber \\&=|D_{f,i}|^2+p^{m-1}\sum _{\begin{array}{c} \beta \in \mathbb {F}_{p^m}\setminus \{0\}\\ g(\beta )\not =i \end{array}} \zeta _p^{\text {Tr}(\beta \gamma )}. \end{aligned}$$

(20)

We first assume that $\gamma \not =0$. It follows from $\sum _{\beta \in \mathbb {F}_{p^m}}\zeta _p^{\text {Tr}(\beta \gamma )}=0$ that

$$\begin{aligned} E_i(\gamma )=|D_{f,i}|^2-\sum _{\begin{array}{c} \beta \in \mathbb {F}_{p^m}\\ \beta =0 \text { or } g(\beta ) =i \end{array}} p^{m-1}\zeta _p^{\text {Tr}(\beta \gamma )}=|D_{f,i}|^2-p^{m-1}(\chi _{\gamma }(D_{g,i})+\delta _{g,i}),\qquad \end{aligned}$$

(21)

where $\delta _{g,i}={\left\{ \begin{array}{ll}0 &{} \text {if }0 \in D_{g,i}, \\ 1 &{} \text {if }0 \not \in D_{g,i}.\end{array}\right. }$

From the fact that the dual function g of f is also a weakly regular bent function and $f(-\beta )=f(\beta )$ for any $\beta \in \mathbb {F}_p$, using (1), we have that

$$\begin{aligned} W_{g}(\beta )=(-1)^{\frac{p-1}{2}+ 1_S(\beta )} \sqrt{p^*}^m \zeta _p^{f(\beta )}. \end{aligned}$$

(22)

We have two cases to consider. Assume $f(\gamma )\not =0$. It follows from (22) and Lemma 3.7, we have that

$$\begin{aligned} E_i(\gamma )&=|D_{f,i}|^2-p^{m-1}(\chi _{\gamma }(D_{g,i})+\delta _{g,i})\nonumber \\&= {\left\{ \begin{array}{ll} (p^{m-1}-1)^2-p^{m-1}(w_{\gamma }(i)p^{\frac{m-1}{2}}+\delta _{g,i}) &{} \text { if }i \not = f(\gamma )\text { and } i=0, \\ (p^{m-1}+ u_0(i) p^{\frac{m-1}{2}})^2-p^{m-1}\delta _{g,i} &{} \text { if } i=f(\gamma )\text { and } i \not =0, \\ (p^{m-1}+ u_0(i) p^{\frac{m-1}{2}})^2-p^{m-1}(w_{\gamma }(i) p^{\frac{m-1}{2}}+\delta _{g,i}) &{} \text { if }i\not =f(\gamma ) \text { and } i \not =0, \end{array}\right. } \end{aligned}$$

(23)

where $w_{\gamma }(i)= {\left\{ \begin{array}{ll}(-1)^{\frac{p-1}{2}+1_S(\gamma )}(\frac{i-f(\gamma )}{p}) &{} \text { if } \gamma \not =0,\\ (-1)^{\frac{p-1}{2}+1_S(0)}(\frac{i}{p}) &{} \text { if } \gamma =0. \end{array}\right. }$

In the case that $f(\gamma )=0$, we have

$$\begin{aligned} E_i(\gamma )&=|D_{f,i}|^2-p^{m-1}(\chi _{\gamma }(D_{g,i})+\delta _{g,i})\nonumber \\&= {\left\{ \begin{array}{ll} (p^{m-1}-1)^2&{} \text { if } i=0, \\ (p^{m-1}+ u_0(i) p^{\frac{m-1}{2}})^2-p^{m-1}(w_0(i) p^{\frac{m-1}{2}}+\delta _{g,i}+1) &{} \text { if } i \ne 0.\end{array}\right. } \end{aligned}$$

(24)

Finally, in the case that $\gamma =0$, we find from (20) that

$$\begin{aligned} E_i(0)&=|D_{f,i}|^2+p^{m-1}\sum _{\begin{array}{c} \beta \in \mathbb {F}_{p^m}\setminus \{0\}\\ g(\beta )\not =i \end{array}} 1\nonumber \\&=|D_{f,i}|^2+p^{m-1}(p^m-|D_{g,i}|-\delta _{g,i}+1). \end{aligned}$$

(25)

It then follows from (22) and Lemma 3.7 that

$$\begin{aligned} E_i(0) = {\left\{ \begin{array}{ll} (p^{m-1}-1)^2+p^{m-1}(p^m-p^{m-1}+2+\delta _{g,i}) &{} \text { if } i=0, \\ (p^{m-1}+ u_0(i)p^{\frac{m-1}{2}})^2+p^{m-1}(p^m-p^{m-1}-w_0(i) p^{\frac{m-1}{2}}+\delta _{g,i}+1) &{} \text { if } i\ne 0.\end{array}\right. } \end{aligned}$$

(26)

We can see from (23) and (26) that $E_i(\gamma ) \not =0$ for any $\gamma \in \mathbb {F}_p^m$ with $m \ge 3$. This completes the proof by using Proposition 3.9. $\square$

5 Association schemes

There are several results [5, 12, 25, 28] on constructing (amorphic) association schemes from $f\in \mathcal {B}^w_l(m,p)$. In [28], they constructed amorphic association schemes from $f\in \mathcal {B}^w_l(m,3)$. This result was extended [5, 12] to the weakly regular p-ary bent functions in $\mathcal {B}^w_l(m,p)$.

In [25], they proved the existence of association schemes from $f\in \mathcal {B}^w_l(m,p)$ by using a non-constructive proof method. In those cases, the intersection number of the association scheme is independent of l. In the following Theorem 5.2 we also constructed association schemes from $f\in \mathcal {B}^w_l(m,p)$; we used a constructive proof method.

In [12], we constructed amorphic association schemes from $f\in \mathcal {B}^w_l(m,p)$ whose intersection numbers depend on l, where $l\ne p-1$ and $p>3$; the case that $l = p-1$ for $p > 2$ was open. In the following Theorem 5.1 we solve this open case that $\ell = p-1$ for $p >2$.

5.1 Even dimensional cases

Theorem 5.1

Let m be a positive even integer, and let $f\in \mathcal {B}^w_l(m,p)$ with $l=p-1$. Then the decomposition

$$\begin{aligned} \{D_{f,0},D_{f,1},\ldots ,D_{f,p-1}\} \end{aligned}$$

is a p-class amorphic association scheme.

Proof

It is straightforward from Result 4 and Remark 3.6. $\square$

5.2 Odd dimensional cases

Theorem 5.2

Let m be a positive odd integer, and let $f\in \mathcal {B}^w_l(m,p)$ with $l=p-1$. Let $P=\{0\}|D_{f,0}|D_{f,1}|\ldots |D_{f,p-1}$ be a partition of $\mathbb {F}_{p^m}$. Then the set of relations $\{R_{f,-1},R_{f,0},\ldots ,R_{f,p-1}\}$ is a p-class association scheme, where $R_{f,-1}=\{(0,0)\}$ and $R_{f,i}$ is defined by

$$\begin{aligned} (\alpha ,\beta )\in R_{f,i} \text{ if } \text{ and } \text{ only } \text{ if } \alpha -\beta \in D_{f,i}. \end{aligned}$$

Proof

Let f be a weakly regular bent function with its dual $\tilde{f}$. Then by Lemma 3.7 and $\tilde{\tilde{f}}(x)=f(-x)=f(x)$, we see that for any $i,j\in \{0,1,\ldots ,p-1\}$, the sum $\chi _{\alpha }(D_{f,i})$ does not depend on the choice of $\alpha \in D_{\tilde{f},j}$, and the sum $\chi _{\beta }(D_{\tilde{f},i})$ does not depend on the choice of $\beta \in D_{f,j}$. The proof follows immediately from Result 3. $\square$

The first and second eigenmatrices (for the definition, we refer to [19]) of the schemes in Theorems 5.1 and 5.2 can be computed explicitly by using Lemmas 3.4 and 3.7, respectively.