Cayley sum graphs and their applications to codebooks

Abstract

In this paper we first provide two new constructions for Cayley sum graphs, namely, norm-coset graphs and trace-coset graphs, and determine their second largest eigenvalues using Gaussian sums. Next, a connection between Cayley sum graphs and complex codebooks is established. Based on this, infinite families of asymptotically optimal complex codebooks are explicitly constructed. The derived Cayley sum graphs and codebooks either include some known constructions as special cases or provide flexible new parameters.

1 Introduction

The Cayley sum graph, also known as the addition Cayley graph, is a variant of the well-studied Cayley graph, see [1, 10, 21] for example.

Let $\varGamma =(V(\varGamma ),E(\varGamma ))$ be a graph with n vertices which might contain loops, i.e., edges that connect a vertex to itself. We say $\varGamma$ is K-regular if every vertex is incident to exactly K edges, where each loop is counted only once. The adjacency matrix of $\varGamma$, denoted by $A(\varGamma )$, is a square matrix whose columns and rows are indexed by vertices of $\varGamma$ such that the (u, v)-entry is equal to the number of edges incident to u and v. Eigenvalues of $A(\varGamma )$ are called eigenvalues of $\varGamma$ as well. It is readily seen that $A(\varGamma )$ is a symmetric real matrix and thus all eigenvalues of $\varGamma$ are real numbers. By the Perron-Frobenius theorem, it can be proved that if $\varGamma$ is a K-regular graph, then all eigenvalue of $\varGamma$ are in the interval $[-K, K]$ and the largest eigenvalue is exactly K, which is also called the trivial eigenvalue of $\varGamma$. For notation convenience, let $K=\lambda _1 \ge \lambda _2 \ge \cdots \ge \lambda _n \ge -K$ denote all the eigenvalues of $\varGamma$ and let

$$\begin{aligned} \lambda (\varGamma ):=\max _{2 \le i \le n}|\lambda _i| \end{aligned}$$

denote the second largest eigenvalue (in absolute value) of $\varGamma$. In what follows, $\varGamma$ is always assumed to be a regular graph.

Here we would like to mention that the value $\lambda (\varGamma )$ can be seen as a measure of “randomness” of $\varGamma$ in graph theory. Indeed, if $\lambda (\varGamma )$ is relatively smaller than the largest eigenvalue of $\varGamma$, then $\varGamma$ has various properties as those of Erdős-Rényi random graphs, which is a consequence of the well-known expander-mixing lemma. This is a fundamental fact in the theory of pseudo-random graphs. For further details of pseudo-random graphs, see a survey paper [26]. On the other hand, if $\lambda (\varGamma )$ is relatively smaller than the largest eigenvalue of $\varGamma$, then accordingly the Cheeger constant of $\varGamma$ is large, implying that $\varGamma$ is highly-connected. To be precise, the Cheeger constant $h(\varGamma )$ of $\varGamma$ is defined as

$$\begin{aligned} h(\varGamma ):=\min _{\begin{array}{c} S \subset V(\varGamma )\\ 0<|S|\le \frac{n}{2} \end{array}}\frac{|\partial S|}{|S|}, \end{aligned}$$

where $\partial S$ denotes the set of edges such that one vertex of the edge lies in S and another vertex in $V(\varGamma )\setminus S$. A relationship between Cheeger constant and the eigenvalue $\lambda (\varGamma )$ is established by the following Cheeger inequality (see e.g. [24, Theorem 2.4]).

$$\begin{aligned} h(\varGamma ) \ge \frac{K-\lambda (\varGamma )}{2}. \end{aligned}$$

(1)

This is a significant attribution of expander graphs and has wide applications in coding theory [45]; cryptography [55]; communication networks [5]; and more. For more details on expander graphs, see e.g. [24].

Constructing regular graphs with small nontrivial eigenvalues (in absolute value) is one of the central issues in the study of pseudo-random graphs and expander graphs. It typically provides important examples (or counterexamples) to various problems in graph theory and combinatorics [2, 3, 22, 27, 37]. In fact, the Cayley sum graph is a good candidate of generically constructing such desired regular graphs.

Definition 1

(Cayley sum graphs) Let $(G,\oplus )$ be an abelian group and $D \subseteq G$. Then the Cayley sum graph CayS(G, D) is a graph with vertex set G such that two vertices x, y are adjacent if and only if $x\oplus y \in D$.

Here we would like to follow the terminology Cayley “sum” graphs as in the literature (see e.g. [6]). However, as we mentioned before, the operation $\oplus$ could be specifically expressed as addition “$+$”, multiplication “$\cdot$”, or their combinations.

In this paper, we provide two new constructions for Cayley sum graphs, namely norm-coset graphs and trace-coset graphs, and determine their second largest eigenvalues using the evaluation of the modulus of Gaussian sums. It is also shown that the new constructions include some existing graphs (e.g. projective norm graph in [3]) as special cases. Furthermore we establish a connection between Cayley sum graphs and the maximum cross-correlation amplitude of complex codebooks. Based on the newly constructed graphs and newly established connection, infinite families of complex codebooks are derived. The resulted codebooks have flexible new parameters (see Table 1) and asymptotically achieve the Welch bound or Levenshtein bound accordingly. In addition, the alphabet size of these codebooks is rather small. Moreover, by virtue of a number-theoretic result, we show that the provided constructions (as well as many existing constructions) can produce asymptotically optimal codebooks with almost all possible length.

Table 1 The parameters of codebooks, where q is a power of a prime p

The remainder of this paper is organized as follows. In Sect. 2, we present preliminary notations and results in finite fields. Sections 3 and 4 are devoted to explicitly constructing Cayley sum graphs and estimating their second largest eigenvalues. In Sect. 5, a relationship between complex codebooks and Cayley sum graphs is establish. Asymptotically optimal complex codebooks and some discussions are provided in Sect. 6. Finally this paper is concluded in Sect. 7.

2 Preliminaries

In this section we recall some mathematical foundations which are useful in the subsequent statements.

Let $(G,\oplus )$ be an abelian group of order |G| such that $a\oplus b=b\oplus a$ for any $a,b\in G$. We also simply use G rather than $(G,\oplus )$ to denote a group if the operation $\oplus$ is clear or not necessarily claimed. A character $\chi$ on G is a group homomorphism from G to the multiplicative group of the complex field $\mathbb {C}^*$ such that $\forall \, a,b\in G$, we have $\chi (a\oplus b) = \chi (a)\chi (b)$ and $|\chi (a)|=1$. For every $a\in G$, let $\ominus a$ denote the inverse element of a in G and thus $a\oplus b=c$ is equivalent to $a=c\ominus b$. Moreover we have $\chi (\ominus a)=\overline{\chi (a)}$ for each character $\chi$. If a character $\chi$ such that for any $a\in G$, $\chi (a)=1$, then $\chi$ is called the principal character of G and denoted by $\chi _0$. The set of all characters of G forms an abelian group, called the character group of G and denoted by $\widehat{G}$. The inverse of $\chi$ in $\widehat{G}$ is ${\overline{\chi }}$ where ${\overline{\chi }}(g):=\overline{\chi (g)}$ for all $g \in G$. It is well-known that $|\widehat{G}|=|G|$. The reader is also referred to [4] for more details of group theory. We remark that in the sequel the operation $\oplus$ could specifically be addition “$+$", multiplication “$\cdot$", or their combinations in the corresponding settings.

Let $\mathbb {F}_q$ denote the finite field with q elements, where q is a prime power. Let $\mathbb {F}_q^+$ and $\mathbb {F}_q^*$ be the additive and multiplicative group of $\mathbb {F}_q$ respectively, where $\mathbb {F}_q^*=\mathbb {F}_q\backslash \{0\}=\{g^i: 0\le i\le q-2\}$ is a cyclic group of order $q-1$ and g is called a primitive element of $\mathbb {F}_q$. For $t \ge 1$, let $\mathbb {F}_{q^t}$ denote an extension field of $\mathbb {F}_q$, which has the same structure as a linear space over $\mathbb {F}_q$ of dimension t. Let $\text {Tr}_{q^t/q}$ be the trace function from $\mathbb {F}_{q^t}$ to $\mathbb {F}_{q}$ defined as

$$\text{ Tr}_{q^t/q}(x):=x+x^{q}+\cdots +x^{q^{t-1}}$$

for any $x\in \mathbb {F}_{q^t}$. This is a linear mapping from $\mathbb {F}_{q^t}$ to $\mathbb {F}_{q}$, that is, for any $x, y \in \mathbb {F}_{q^{t}}$ and $\alpha \in \mathbb {F}_q$, we have $\text {Tr}_{q^t/q}(x) \in \mathbb {F}_q$, $\text {Tr}_{q^t/q}(x+y)=\text {Tr}_{q^t/q}(x)+\text {Tr}_{q^t/q}(y)$ and $\text {Tr}_{q^t/q}(\alpha x)=\alpha \text {Tr}_{q^t/q}(x)$. Let $\text {Nr}_{q^t/q}$ denote the norm function from $\mathbb {F}_{q^t}$ to $\mathbb {F}_{q}$ such that

$$\text{ Nr}_{q^t/q}(x):=x^{1+q+q^2+\cdots +q^{t-1}}$$

for any $x\in \mathbb {F}_{q^t}$. This is a group homomorphism from $\mathbb {F}_{q^t}^*$ to $\mathbb {F}_{q}^*$, that is, for any $x, y \in \mathbb {F}_{q^{t}}^*$, we have $\text {Nr}_{q^t/q}(x) \in \mathbb {F}_q^*$ and $\text {Nr}_{q^t/q}(xy)=\text {Nr}_{q^t/q}(x)\text {Nr}_{q^t/q}(y)$. Notice that both $\text {Tr}_{q^t/q}$ and $\text {Nr}_{q^t/q}$ are surjective.

Definition 2

• (1) An additive character $\psi$ of $\mathbb {F}_q$ is a homomorphism from $\mathbb {F}^+_q$ to $\mathbb {C}^*$ such that $\psi (x+y)=\psi (x)\psi (y)$ for any $x,y\in \mathbb {F}_q$. Denote the set of all additive characters of $\mathbb {F}_q$ as $\widehat{\mathbb {F}_q^+}$.

• (2) A multiplicative character $\chi$ of $\mathbb {F}_q$ is a homomorphism from $\mathbb {F}^*_q$ to $\mathbb {C}^*$ such that $\chi (xy)=\chi (x)\chi (y)$ for any $x,y\in \mathbb {F}^*_q$. Denote the set of all multiplicative characters of $\mathbb {F}_q$ as $\widehat{\mathbb {F}_q^*}$.

In addition, if $\psi (x)=1$ (resp. $\chi (x)=1$) for all $x\in \mathbb {F}_q$, then we call it the principal additive (resp. multiplicative) character of $\mathbb {F}_q$, denoted by $\psi _0$ (resp. $\chi _0$). More generally, suppose that $q=p^s$ where p is a prime and $s \ge 1$ is an integer. Let $\zeta _n$ denote a primitive nth complex root of unity and g denote a primitive element of $\mathbb {F}_q$. Then we have $\widehat{\mathbb {F}_q^+}=\{\psi _a(x)=\zeta _p^{\text {Tr}_{p^s/p}(ax)} : a \in \mathbb {F}_q\}$ and $\widehat{\mathbb {F}_q^*}=\{\chi _b(g^i)=\zeta _{q-1}^{bi} : 0 \le b \le q-2\}$. Clearly, $|\widehat{\mathbb {F}_q^+}|=|\mathbb {F}_q^+|=q$ and $|\widehat{\mathbb {F}_q^*}|=|\mathbb {F}_q^*|=q-1$.

Definition 3

Let $\psi \in \widehat{\mathbb {F}_q^+}$ and $\chi \in \widehat{\mathbb {F}_q^*}$. Then the Gaussian sum $\mathcal {G}_q(\psi , \chi )$ is defined as

$$\begin{aligned} \mathcal {G}_q(\psi , \chi ):=\sum _{x \in \mathbb {F}_q^*}\psi (x)\chi (x). \end{aligned}$$

(2)

Lemma 1

[33]

• (a) If $\psi$ and $\chi$ are principal, then $\mathcal {G}_q(\psi , \chi )=q-1$.

• (b) If $\psi$ is principal and $\chi$ is non-principal, then $\mathcal {G}_q(\psi , \chi )=0$.

• (c) If $\psi$ is non-principal and $\chi$ is principal, then $\mathcal {G}_q(\psi , \chi )=-1$.

• (d) If $\psi$ and $\chi$ are non-principal, then $|\mathcal {G}_q(\psi , \chi )|=\sqrt{q}$.

2.1 The second largest eigenvalue of Cayley sum graphs

From Definition 1, it is readily seen that CayS(G, D) is |D|-regular and each vertex is involved in at most one loop. The following lemma, which is well known in graph theory (e.g. [1, 6, 29]), shows that $\lambda (CayS(G, D))$ could be expressed by character sums over G. We provide a complete proof of this result below for the reader’s convenience.

Lemma 2

Let $(G,\oplus )$ be an abelian group of order n and $D \subseteq G$. Then

$$\begin{aligned} \lambda (CayS(G, D))=\max _{\chi \in \widehat{G} \setminus \{\chi _0\}}|\chi (D)|. \end{aligned}$$

(3)

Proof

We first claim that each eigenvalue of CayS(G, D) can be expressed by a character sum. Let $A=A(CayS(G,D))$ be the adjacency matrix of CayS(G, D) and for each character $\chi \in \widehat{G}$, let $\textbf{v}_\chi =(\chi (g))_{g \in G}^T$. Then we have

$$\begin{aligned} A\textbf{v}_\chi =\biggl (\sum _{d \in D}\chi (d\ominus g) \biggr )^T_{g \in G} =\biggl (\sum _{d \in D}\chi (d) \overline{\chi (g)} \biggr )^T_{g \in G} =\biggl (\sum _{d \in D}\chi (d)\biggr )\overline{\textbf{v}_\chi } =\chi (D) \overline{\textbf{v}_\chi } \end{aligned}$$

(4)

where $\overline{\textbf{v}_\chi }=\Bigl (\overline{\chi (g)} \Bigr )_{g \in G}^T$. Similarly,

$$\begin{aligned} A\overline{\textbf{v}_\chi }= \biggl (\sum _{d \in D} \overline{\chi (d)}\biggr ) \textbf{v}_\chi = \overline{\chi (D)} \textbf{v}_\chi . \end{aligned}$$

(5)

Now we obtain

$$\begin{aligned} A^2\textbf{v}_\chi = A(A\textbf{v}_\chi ) \overset{4}{=} \chi (D) A\overline{\textbf{v}_\chi } \overset{(5)}{=} \bigl |\chi (D)\bigr |^2 \textbf{v}_\chi , \end{aligned}$$

which means that $|\chi (D)|^2$ is an eigenvalue of $A^2$ and $\textbf{v}_{\chi }$ is an eigenvector with respect to $|\chi (D)|^2$. Notice that $A^2$ is symmetric and the set of vectors $\{\textbf{v}_\chi \}_{\chi \in \widehat{G}}$ forms an orthogonal basis of $\mathbb {C}^n$. This implies that the multiset $\{|\chi (D)|^2\ : \chi \in \widehat{G}\}$ comprises all eigenvalues of $A^2$. Equivalently, every eigenvalue of A (in absolute value) could be expressed in the form of $|\chi (D)|$. Also notice that $\chi _0(D)=|D|$ corresponds to the largest eigenvalue, then the lemma follows. $\square$

As a consequence of the proof of Lemma 2 we can obtain the whole spectrum of CayS(G, D) (see also [29, Propositions 1 and 2]).

Corollary 1

Let $I_1=\{\chi \in \widehat{G} :\chi (D)=0\}$, $I_2=(\widehat{G}\setminus \{\chi _0\})\setminus I_1$. Then the multiset of all eigenvalues of CayS(G, D) are

$$\begin{aligned} \{\chi _0(D)\} \cup \{\chi (D)=0 :\chi \in I_1\} \cup \{\pm |\chi (D)| :\chi \in I_2\}. \end{aligned}$$

Here for $\chi \in I_1$, eigenvectors corresponding to $\chi (D)$ are $\textbf{v}_{\chi }$ and $\overline{\textbf{v}_{\chi }}$, and for $\chi \in I_2$, eigenvectors corresponding to $\pm |\chi (D)|$ are $\textbf{u}_{\chi }^{\pm }:=|\chi (D)|\textbf{v}_{\chi }\pm \chi (D)\overline{\textbf{v}_{{\chi }}}$ respectively.

Remark 1

To enumerate all eigenvalues with multiplicity, we shall enumerate characters consisting of (1) $\chi _0$, (2) $\chi$ with $\chi (D)=0$, (3) $\chi$ such that $\chi ={\overline{\chi }}$, (4) one of $\{\chi , {\overline{\chi }}\}$ with $\chi \ne {\overline{\chi }}$. In fact, when $I_2$ contains a character $\chi$ with $\chi ={\overline{\chi }}$, then $\chi (D)$ is a non-zero real number and only one of $\{|\chi (D)|, -|\chi (D)|\}$ can be an eigenvalue since if $\chi (D)>0$ (resp. $\chi (D)<0$) then $-|\chi (D)|$ (resp. $|\chi (D)|$) cannot be an eigenvalue since the corresponding eigenvector is $\textbf{0}$. Also if $\chi \ne {\overline{\chi }}$ then $\textbf{u}_{\chi }^{\pm }$ and $\textbf{u}_{{\overline{\chi }}}^{\pm }$ are in fact linearly dependent since

$$\begin{aligned}&u_{{\overline{\chi }}}^{+} = |\overline{\chi (D)}|\textbf{v}_{{\overline{\chi }}}+ \overline{\chi (D)}\overline{\textbf{v}_{{\overline{\chi }}}} =|{\chi (D)}|\overline{\textbf{v}_{\chi }}+ \overline{\chi (D)}\textbf{v}_{\chi } =\frac{|\chi (D)|}{\chi (D)}u_{\chi }^{+},\\&u_{{\overline{\chi }}}^{-} = |\overline{\chi (D)}|\textbf{v}_{{\overline{\chi }}}- \overline{\chi (D)}\overline{\textbf{v}_{{\overline{\chi }}}} =|{\chi (D)}|\overline{\textbf{v}_{\chi }}-\overline{\chi (D)}\textbf{v}_{\chi } =-\frac{|\chi (D)|}{\chi (D)}u_{\chi }^{-}. \end{aligned}$$

3 Norm-coset graphs

In this section, we present our first construction of Cayley sum graphs, namely, norm-coset graphs, and investigate their second largest eigenvalues.

First we define norm-coset graphs and then prove that they are Cayley sum graphs. For notations, we will use the capital letter to denote an element in the extension field (i.e. $Y\in \mathbb {F}_{q^{t-1}}$) in order to distinguish it with the lowercase letter denoting $x\in \mathbb {F}_q$.

Definition 4

Let q be a prime power and $t\ge 2$ be an integer. Let v be a divisor of $q-1$ and $H^{\times }$ be a subgroup of order v of the multiplicative group $\mathbb {F}_q^*$. Then the norm-coset graph $N\varGamma ^{\times }_{q, v, t, H^{\times }}$ is a graph with vertex set $(\mathbb {F}_q^*/H^{\times }) \times \mathbb {F}_{q^{t-1}}^+ =\{({\overline{x}}, Y): {\overline{x}} \in \mathbb {F}_q^*/H^{\times }, Y \in \mathbb {F}_{q^{t-1}}^+\}$ such that two vertices $(\overline{x_1}, Y_1)$, $(\overline{x_2}, Y_2)$ are adjacent if and only if $\text {Nr}_{q^{t-1}/q}(Y_1+Y_2) \in \overline{x_1}\; \overline{x_2}=\overline{x_1x_2}$.

We would like to mention that the norm-coset graphs defined above actually include several known graphs as special cases, as described below.

• (1) If the subgroup $H^{\times }$ is of order one (i.e., $v=1$), the graph $N\varGamma ^{\times }_{q, v, t, H^{\times }}$ turns out to be the so-called projective norm graph $NG_{q, t}$, which was introduced by Alon, Ronyai and Szabó [3] and provides good bounds for Turán numbers and Ramsey numbers [2, 3].

• (2) If $t=2$, the graph $N\varGamma ^{\times }_{q, v, t, H^{\times }}$ turns out to be the so-called product-coset graph $G^{\times }$, which was introduced by Lentz and Mubayi and used to prove sharp bounds for multicolored Ramsey numbers [27].

• (3) If $t=2$ and $H^{\times }$ is of order one (i.e., $v=1$), the graph $N\varGamma ^{\times }_{q, v, t, H^{\times }}$ turns out to be the so-called sum-product graph $SP_q$, which was defined by Solymosi [46] and employed to prove Garaev’s theorem [19] in additive combinatorics.

To the best of our knowledge, these known graphs have been independently considered in graph theory and additive combinatorics, which have not yet been pointed out and investigated in terms of Cayley sum graphs. In the following Proposition 1 we will show that these known graphs (as special cases of norm-coset graphs) are in fact Cayley sum graphs over the corresponding abelian groups, which provides a unified view to compute their eigenvalues as well. In particular, our result improves upon the existing eigenvalue estimation on $\lambda (SP_q)$ for sum-product graphs. Precisely, Solymosi proved that $\lambda (SP_q) < \sqrt{3q}$ in [46], while the Proposition 1 below yields that $\lambda (SP_q) = \sqrt{q}$.

In the following proposition, we claim that $N\varGamma _{q, v, t, H^{\times }}$ is a Cayley sum graph and determine the exact value of $\lambda (N\varGamma _{q, v, t, H^{\times }})$ accordingly.

Proposition 1

Suppose that $G=(\mathbb {F}_q^*/H^{\times }) \times \mathbb {F}_{q^{t-1}}^+$ and $D=\{({\overline{x}}, Y) \in (\mathbb {F}_{q}^*/H^{\times }) \times \mathbb {F}_{q^{t-1}}^+ : \text {Nr}_{q^{t-1}/q}(Y) \in {\overline{x}}\}$. Then $N\varGamma ^{\times }_{q, v, t, H^{\times }}$ is a Cayley sum graph CayS(G, D), and $\lambda (N\varGamma ^{\times }_{q, v, t, H^{\times }})=q^{\frac{t-1}{2}}$.

Proof

It is easy to see that $G=(\mathbb {F}_{q}^*/H^{\times }) \times \mathbb {F}_{q^{t-1}}^+$ is an abelian group of order $q^{t-1}(q-1)/v$ under the operation $(\overline{x_1},Y_1)\oplus (\overline{x_2},Y_2)=(\overline{x_1}\;\overline{x_2},Y_1+Y_2)=(\overline{x_1x_2},Y_1+Y_2)$. By Definition 4, two vertices $(\overline{x_1},Y_1)$ and $(\overline{x_2},Y_2)$ are adjacent if and only if $(\overline{x_1},Y_1)\oplus (\overline{x_2},Y_2)=(\overline{x_1x_2}, Y_1+Y_2) \in D$, that is, $\text {Nr}_{q^{t-1}/q}(Y_1+Y_2) \in \overline{x_1x_2}$. Thus according to Definition 1, $N\varGamma ^{\times }_{q,v,t,H^{\times }}$ is a Cayley sum graph CayS(G, D). Now we claim that for each non-zero $Y \in \mathbb {F}_{q^{t-1}}^+$, there exists a unique corresponding $(\bar{x},Y)\in D$. Indeed, given Y, the value $y=\text {Nr}_{q^{t-1}/q}(Y) \in \mathbb {F}_q^*$ could be first uniquely determined; next, for each $y \in \mathbb {F}_q^*$, there exists a unique coset $\bar{x}=\bar{y}\in \mathbb {F}_q^*/H^{\times }$ containing y, since all the cosets in $\mathbb {F}_q^*/H^{\times }$ form a partition of $\mathbb {F}_q^*$. Based on this, we have $|D|=|\mathbb {F}_{q^{t-1}}^+\setminus \{0\}|=q^{t-1}-1$, which is the degree of each vertex in $N\varGamma ^{\times }_{q, v, t, H^{\times }}$.

Next we are going to determine the value of $\lambda (N\varGamma ^{\times }_{q, v, t, H^{\times }})$. Notice that $\widehat{G}=\{(\nu \otimes \psi ): \nu \in \widehat{\mathbb {F}^*_{q}/H^{\times }}, \psi \in \widehat{\mathbb {F}_{q^{t-1}}^+}\}$ where $(\nu \otimes \psi )({\overline{x}},Y)=\nu ({\overline{x}})\psi (Y)$ for all $({\overline{x}},Y)\in G$. According to Lemma 2, we have

$$\begin{aligned}{} & {} \lambda (N\varGamma ^{\times }_{q, v, t, H^{\times }}) \\ {}{} & {} =\max \Bigl \{ \Bigl | \sum _{({\overline{x}},Y)\in D} (\nu \otimes \psi )({\overline{x}}, Y) \Bigr | : \nu \in \widehat{\mathbb {F}_{q}^*/H^{\times }}, \psi \in \widehat{\mathbb {F}_{q^{t-1}}^+}, \nu \otimes \psi \ne \nu _0 \otimes \psi _0\Bigr \}. \end{aligned}$$

By the assumption of D,

$$\begin{aligned} \begin{aligned} \sum _{({\overline{x}},Y)\in D}(\nu \otimes \psi )({\overline{x}}, Y)&=\sum _{({\overline{x}},Y)\in D}\nu ({\overline{x}})\psi (Y)\\&=\sum _{\begin{array}{c} Y\in \mathbb {F}_{q^{t-1}}^+\setminus \{0\},\\ y=\text {Nr}_{q^{t-1}/q}(Y) \end{array}} \nu ({\overline{y}}) \psi (Y)\\&=\sum _{Y\in \mathbb {F}_{q^{t-1}}^*}\nu (\overline{\text {Nr}_{q^{t-1}/q}(Y)}) \psi (Y). \end{aligned} \end{aligned}$$

Now we define a new multiplicative character $\chi '$ of $\mathbb {F}_q$ by letting $\chi '(x):=\nu ({\overline{x}})$. This is well-defined since for any $x, y \in \mathbb {F}_q^*$ and $\nu \in \widehat{\mathbb {F}_{q}^*/H^{\times }}$, we have $\chi '(xy)=\nu ({\overline{xy}})=\nu ({\overline{x}}\cdot {\overline{y}})=\nu ({\overline{x}})\nu ({\overline{y}})=\chi '(x)\chi '(y)$. It follows by the definition of D that the condition $({\overline{x}}, Y) \in D$ implies that ${\overline{x}}=\overline{\text {Nr}_{q^{t-1}/q}(Y)}$ in the quotient group $\mathbb {F}^*_{q}/H^{\times }$. Then we have

$$\begin{aligned} \sum _{Y\in \mathbb {F}_{q^{t-1}}^*}\nu (\overline{\text {Nr}_{q^{t-1}/q}(Y)}) \psi (Y){} & {} =\sum _{Y\in \mathbb {F}_{q^{t-1}}^*}\chi '(\text {Nr}_{q^{t-1}/q}(Y)) \psi (Y)\nonumber \\{} & {} =\sum _{Y\in \mathbb {F}_{q^{t-1}}^*}(\chi ' \circ \text {Nr}_{q^{t-1}/q})(Y) \psi (Y) \end{aligned}$$

which is a Gaussian sum $\mathcal {G}_{q^{t-1}}(\psi , \chi '\circ \text {Nr}_{q^{t-1}/q})$ since $\chi '\circ \text {Nr}_{q^{t-1}/q}$ is a multiplicative character of $\mathbb {F}_{q^{t-1}}$ as well. Notice that the character $\chi ' \circ \text {Nr}_{q^ {t-1}/q}$ is principal if and only if $\chi '$ is principal. According to the definition of $\chi '$, the multiplicative character $\chi ' \circ \text {Nr}_{q^{t-1}/q}$ is non-principal if and only if $\nu$ is non-principal. Thus by Lemma 1, we have $\lambda (N\varGamma ^{\times }_{q,v,t, H^{\times }})=\max \{0,1,q^{\frac{t-1}{2}}\}=q^{\frac{t-1}{2}}$, as required. $\square$

According to the discussion in the proof, we can determine the whole spectrum of $N\varGamma ^{\times }_{q, v, t, H^{\times }}$, which immediately follows from Lemma 1 and Corollary 1 (with Remark 1).

Corollary 2

Let q be an odd prime power. Then the graph $N\varGamma ^{\times }_{q, v, t, H^{\times }}$ has eigenvalues $q^{t-1}-1$ (with multiplicity 1), $\pm q^{\frac{t-1}{2}}$ (with multiplicity $\frac{1}{2}(q^{t-1}-1)(\frac{q-1}{v}-1)$, respectively), 0 (with multiplicity $\frac{q-1}{v}-1$) and $\pm 1$ (with multiplicity $\frac{1}{2}(q^{t-1}-1)$, respectively).

By Proposition 1 we obtain the following propositions regarding graph-theoretic properties of norm-coset graphs such as diameter (i.e. the maximum length of the shortest path) and Cheeger constant.

Proposition 2

The diameter of $N\varGamma ^{\times }_{q, v, t, H^{\times }}$ is 2.

Proof

Chung [10] proved that if $\varGamma$ is a K-regular graph with n vertices then the diameter of $\varGamma$ is at most $\log (n-1)/\log (K/\lambda (\varGamma ))$. Since $N\varGamma ^{\times }_{q, v, t, H^{\times }}$ is a $(q^{t-1}-1)$-regular graph with $q^{t-1}(q-1)/v$ vertices and $\lambda (N\varGamma ^{\times }_{q, v, t, H^{\times }})=q^{\frac{t-1}{2}}$, the diameter is at most

$$\begin{aligned} \frac{t-\log (v)}{\frac{t-1}{2}+o(1)}=2\cdot \frac{t-\log (v)}{t-1+o(1)}< 3. \end{aligned}$$

Notice that a graph $\varGamma$ has diameter 1 if and only if $\varGamma$ is a complete graph, and hence the diameter of $N\varGamma ^{\times }_{q, v, t, H^{\times }}$ is 2 since it is not a complete graph. $\square$

The following bound of $h(N\varGamma ^{\times }_{q, v, t, H^{\times }})$ immediately follows from the Cheeger inequality (1).

Proposition 3

For the Cheeger constant we have

$$\begin{aligned} h(N\varGamma ^{\times }_{q, v, t, H^{\times }})\ge \frac{q^{t-1}-q^{\frac{t-1}{2}}-1}{2}. \end{aligned}$$

4 Trace-coset graphs

In this section, we present our second construction of Cayley sum graphs, namely, trace-coset graphs, and determine their second largest eigenvalues.

We first define trace-coset graphs and then show that they are Cayley sum graphs.

Definition 5

Let q be a prime power and $t\ge 2$ be an integer. Let u be a divisor of q and $H^{+}$ be a subgroup of order u of the additive group $\mathbb {F}_q^+$. Then the trace-coset graph $T\varGamma ^{+}_{q, u, t, H^{+}}$ is a graph with vertex set $(\mathbb {F}_q^+/H^{+}) \times \mathbb {F}_{q^{t-1}}^* =\{({\overline{x}}, Y): {\overline{x}} \in \mathbb {F}_q^+/H^{+}, y \in \mathbb {F}_{q^{t-1}}^*\}$ such that two vertices $(\overline{x_1}, Y_1)$, $(\overline{x_2}, Y_2)$ are adjacent if and only if $\text {Tr}_{q^{t-1}/q}(Y_1Y_2) \in \overline{x_1}+\overline{x_2}=\overline{x_1+x_2}$.

The trace-coset graph defined above can deduce some known graphs as described below.

• (1) If $t=2$, the trace-coset graph $T\varGamma ^{+}_{q, u, t, H^{+}}$ turns out to be a sum-coset graph $G^+$, which was introduced by Lentz and Mubayi and used to prove sharp bounds for multicolored Ramsey numbers [27].

• (2) If $t=2$ and $H^{+}$ is trivial (i.e., $u=1$), the graph $T\varGamma ^{+}_{q, v, t, H^{+}}$ turns out to be the sum-product graph $SP_q$ [46].

In the following, we claim that $T\varGamma _{q, u, t, H^{+}}$ is a Cayley sum graph and determine the exact value of $\lambda (T\varGamma _{q, u, t, H^{+}})$ as well.

Proposition 4

Suppose that $G=(\mathbb {F}_q^+/H^{+}) \times \mathbb {F}_{q^{t-1}}^*$ and $D=\{({\overline{x}}, Y) \in (\mathbb {F}_{q}^+/H^{+}) \times \mathbb {F}_{q^{t-1}}^* : \text {Tr}_{q^{t-1}/q}(Y) \in {\overline{x}}\}$. Then $T\varGamma ^{+}_{q, v, t, H^{+}}$ is a Cayley sum graph CayS(G, D), and $\lambda (T\varGamma ^{+}_{q, u, t, H^{+}})=q^{\frac{t-1}{2}}$.

Proof

It is easy to see that $G=(\mathbb {F}_{q}^+/H^{+}) \times \mathbb {F}_{q^{t-1}}^*$ is an abelian group of order $q (q^{t-1}-1)/u$ under the operation $(\overline{x_1},Y_1)\oplus (\overline{x_2},Y_2)=(\overline{x_1}+\overline{x_2},Y_1Y_2)=(\overline{x_1+x_2},Y_1Y_2)$. By Definition 5, two vertices $(\overline{x_1},y_1)$ and $(\overline{x_2},y_2)$ are adjacent if and only if $(\overline{x_1},y_1)\oplus (\overline{x_2},y_2)=(\overline{x_1+x_2}, y_1y_2) \in D$, that is, $y_1y_2 \in \overline{x_1+x_2}$. Thus according to Definition 1, $T\varGamma ^{+}_{q,u,t,H^{+}}$ is a Cayley sum graph CayS(G, D). Next we claim that for each $Y \in \mathbb {F}_{q^{t-1}}^*$, there exists a unique corresponding $({\overline{x}},Y)\in D$. In fact, given Y, the value $y=\text {Tr}_{q^{t-1}/q}(Y) \in \mathbb {F}_q^+$ is uniquely determined; also for each $y \in \mathbb {F}_q^+$, there exists a unique coset ${\overline{x}}={\overline{y}}=\mathbb {F}_q^+/H^{+}$ containing y, since all the cosets in $\mathbb {F}_q^+/H^{+}$ form a partition of $\mathbb {F}_q^+$. This implies $|D|=|\mathbb {F}_{q^{t-1}}^*|=q^{t-1}-1$, which is the degree of each vertex in $T\varGamma ^{+}_{q, u, t, H^{+}}$ as well.

Now we would like to determine $\lambda (T\varGamma ^{+}_{q, u, t, H^{+}})$. Notice that $\widehat{G}=\{(\mu \otimes \chi ): \mu \in \widehat{\mathbb {F}^+_{q}/H^{+}}, \chi \in \widehat{\mathbb {F}_{q^{t-1}}^*}\}$ where $(\mu \otimes \chi )({\overline{x}},Y)=\mu ({\overline{x}})\chi (Y)$ for all $({\overline{x}},Y)\in G$. According to Lemma 2, we have

$$\begin{aligned}{} & {} \lambda \left( T\varGamma ^{+}_{q, u, t, H^{+}}\right) \\ {}{} & {} =\max \left\{ \left| \sum _{({\overline{x}},Y)\in D} (\mu \otimes \chi )({\overline{x}}, Y) \right| : \mu \in \widehat{\mathbb {F}_{q}^+/H^{+}}, \chi \in \widehat{\mathbb {F}_{q^{t-1}}^*}, \mu \otimes \chi \ne \mu _0\otimes \chi _0\right\} . \end{aligned}$$

By the assumption of D,

$$\begin{aligned} \begin{aligned} \sum _{({\overline{x}},Y)\in D}(\mu \otimes \chi )({\overline{x}}, Y)&=\sum _{({\overline{x}},Y)\in D}\mu ({\overline{x}})\chi (Y)\\&=\sum _{\begin{array}{c} Y\in \mathbb {F}_{q^{t-1}}^*,\\ y=\text {Tr}_{q^{t-1}/q}(Y) \end{array}}\mu ({\overline{y}}) \chi (Y)\\&=\sum _{Y\in \mathbb {F}_{q^{t-1}}^*}\mu (\overline{\text {Tr}_{q^{t-1}/q}(Y)}) \chi (Y). \end{aligned} \end{aligned}$$

Defining an additive character $\psi '$ of $\mathbb {F}_{q}$ by letting $\psi '(x)=\mu ({\overline{x}})$ we have

$$\begin{aligned} \sum _{Y\in \mathbb {F}_{q^{t-1}}^*}\mu \left( \overline{\text {Tr}_{q^{t-1}/q}(Y)}\right) \chi (Y){} & {} =\sum _{Y\in \mathbb {F}_{q^{t-1}}^*}\psi '(\text {Tr}_{q^{t-1}/q}(Y)) \chi (Y)\nonumber \\{} & {} =\sum _{Y\in \mathbb {F}_{q^{t-1}}^*}\left( \psi ' \circ \text {Tr}_{q^{t-1}/q}\right) (Y) \chi (Y) \end{aligned}$$

which is a Gaussian sum $\mathcal {G}_{q^{t-1}}(\psi '\circ \text {Tr}_{q^{t-1}/q}, \chi )$ since $\psi '\circ \text {Tr}_{q^{t-1}/q}$ is in fact an additive character of $\mathbb {F}_{q^{t-1}}$. Notice that the character $\psi ' \circ \text {Tr}_{q^ {t-1}/q}$ is principal if and only if $\psi '$ is principal. By the definition of $\psi '$, the additive character $\psi ' \circ \text {Tr}_{q^{t-1}/q}$ is non-principal if and only if $\mu$ is non-principal. Thus by Lemma 1, we have $\lambda (T\varGamma ^+_{q,u,t, H^{+}})=\max \{0,1,q^{\frac{t-1}{2}}\}=q^{\frac{t-1}{2}}$, as required. $\square$

As in Corollary 2 we can determine the whole spectrum of $T\varGamma ^+_{q,u,t, H^{+}}$.

Corollary 3

Let q be an odd prime power. Then the graph $T\varGamma ^+_{q,u,t, H^{+}}$ has eigenvalues $q^{t-1}-1$ (with multiplicity 1), $\pm q^{\frac{t-1}{2}}$ (with multiplicity $\frac{1}{2}(q^{t-1}-2)(\frac{q}{u}-1)$, respectively), 0 (with multiplicity $q^{t-1}-2$) and $\pm 1$ (with multiplicity $\frac{1}{2}(\frac{q}{u}-1)$, respectively).

The following propositions determine the diameter and estimate the Cheeger constant of $T\varGamma ^+_{q,u,t, H^{+}}$.

Proposition 5

The diameter of $T\varGamma ^+_{q,u,t, H^{+}}$ is 2.

Proof

Since $T\varGamma ^+_{q,u,t, H^{+}}$ is a $(q^{t-1}-1)$-regular graph with $(q^{t-1}-1)(q/u)$ vertices and $\lambda (T\varGamma ^+_{q,u,t, H^{+}})$ $=q^{\frac{t-1}{2}}$, the diameter is at most

$$\begin{aligned} \frac{t-\log (u)}{\frac{t-1}{2}+o(1)}=2\cdot \frac{t-\log (u)}{t-1+o(1)}<3. \end{aligned}$$

Notice that a graph G has diameter 1 if and only if G is a complete graph, and hence the diameter of $T\varGamma ^+_{q,u,t, H^{+}}$ is 2 since it is not a complete graph. $\square$

According to the Cheeger inequality (1), we have

Proposition 6

For the Cheeger constant we have

$$\begin{aligned} h\left( T\varGamma ^+_{q,u,t, H^{+}}\right) \ge \frac{q^{t-1}-q^{\frac{t-1}{2}}-1}{2}. \end{aligned}$$

5 A connection between codebooks and Cayley sum graphs

In this section, we recall the basics of codebooks and establish a connection between codebooks and Cayley sum graphs.

5.1 Codebooks

An (N, K) codebook $\mathcal {C}=\{\textbf{c}_1,\ldots ,\textbf{c}_N\}\subseteq \mathbb {C}^K$ consists of N complex vectors of length K over an alphabet such that $\Vert \textbf{c}_i\Vert _2 =1$ for all $1\le i\le N$, which is also termed as a signal set or a frame. The alphabet size of $\mathcal {C}$ refers to the number of elements in the alphabet. Define the maximum cross-correlation amplitude $I_{max}(\mathcal {C})$ of an (N, K) codebook $\mathcal {C}$ as

$$\begin{aligned} I_{max}(\mathcal {C}):=\max _{1 \le i<j \le N} |\langle {\textbf {c}}_i, {\textbf {c}}_j \rangle |, \end{aligned}$$

(6)

where $\langle \textbf{c}_i, \textbf{c}_j \rangle$ denotes the inner product of the complex vectors $\textbf{c}_i$ and $\textbf{c}_j$. For a given K, it is desirable to construct an (N, K) codebook $\mathcal {C}$ with as large N and small $I_{max}(\mathcal {C})$ as possible due to the practical applications in a variety of areas such as code-division multiple-access communication systems [20, 36]; quantum computing [39]; compressed sensing [8, 17, 30,31,32, 42, 44, 53]; coding theory [7, 13]; and many more. In the literature, a lower bound on $I_{max}(\mathcal {C})$ with respect to N and K was proved in [50], known as the Welch bound.

Theorem 1

([50], Welch bound) For any (N, K)-codebook $\mathcal {C}$ with $N\ge K$, we have

$$\begin{aligned} I_{max}(\mathcal {C}) \ge I_{wel}(N, K):= \sqrt{\frac{N-K}{(N-1)K}}, \end{aligned}$$

(7)

where the equality holds if and only if $\big |\textbf{c}_i \textbf{c}^H_j \big | = \sqrt{\frac{N-K}{(N-1)K}}$ for all $1\le i\ne j\le N$.

A codebook achieving the Welch bound is usually called a maximum-Welch-bound-equality (MWBE) codebook [52]. It is also known as the equiangular tight frame [9] in frame theory and equivalent to the line packing in Grassmannian spaces [11]. In the literature, certain families of MWBE codebooks were deterministically constructed via discrete Fourier transform matrices [40, 52]; extended codes from any ideal two-level auto-correlation sequences [20, 52, 54]; conference matrices [11, 47]; difference sets in groups [14, 15, 25, 52]; Steiner systems [18], and so on.

As pointed out by Sarwate in [40], it is very hard to explicitly construct MWBE codebooks in general. Hence there have been a number of attempts to construct codebooks nearly meeting the Welch bound, that is, the maximum cross-correlation amplitude $I_{max}(\mathcal {C})$ is slightly higher than the corresponding Welch bound, but asymptotically achieves it when N is large enough. In this paper, we say an infinite family of $(N,K_N)$-codebooks $\{\mathcal {C}_N\}_{N \ge 1}$ is asymptotically optimal with respect to the Welch bound if $\lim _{N\rightarrow \infty } I_{max}(\mathcal {C})/I_{wel}(N, K) =1$. In the literature, asymptotically optimal codebooks have been constructed by using codes and signal sets [40]; almost difference sets [14,15,16, 56, 57]; binary sequences [54]; multivariate polynomials over finite fields [41]; and so forth.

In [47], it was proved that if $N>K^2$, no complex (N, K)-codebook could achieve the Welch bound $I_{wel}(N, K)$ in (7). Regarding this case, an improved lower bound on $I_{max}(\mathcal {C})$ was provided in [28], which is termed as the Levenshtein bound in the literature.

Theorem 2

([28], Levenshtein bound) For a complex (N, K)-codebook $\mathcal {C}$ with $N>K^2$,

$$\begin{aligned} I_{max}(\mathcal {C}) \ge I_{lev}(N, K):= \sqrt{\frac{2N-K^2-2K}{(N-1)(K+1)}}. \end{aligned}$$

(8)

We say an infinite family of $(N,K_N)$ codebooks $\{\mathcal {C}_N\}_{N \ge 1}$ is asymptotically optimal with respect to the Levenshtein bound if $\lim _{N\rightarrow \infty } I_{max}(\mathcal {C})/I_{lev}(N, K) =1$. In the literature, there are known constructions of optimal or asymptotically optimal codebooks with respect to the Levenshtein bound, see [23, 35, 38, 41, 49, 51, 58, 59] for example.

5.2 A generic construction of codebooks from abelian groups

In this subsection we briefly review a constructing method for codebooks proposed by Ding and Feng in [15] and widely adopted such as in [16, 25, 52, 56, 57]. Define a set of n vectors in $\mathbb {C}^K$ by virtue of an abelian group and its K-element subset described as follows.

Definition 6

([15]) Suppose that G is an abelian group of order n and $\widehat{G}=\{\chi _0, \chi _1, \ldots ,$ $\chi _{n-1}\}$ is its character group, where $\chi _0$ is the principal character. Let $D=\{d_1, d_2, \ldots , d_{K}\} \subseteq G$. Then define the set of n vectors in $\mathbb {C}^K$ as

$$\begin{aligned} \mathcal {C}(G,D):= \{\varvec{c}_{0}, \varvec{c}_{1}, \ldots , \varvec{c}_{n-1}\} \end{aligned}$$

(9)

where

$$\begin{aligned} \varvec{c}_{i} := \frac{1}{\sqrt{K}}(\chi _i(d_1), \chi _i(d_2), \ldots , \chi _i(d_K))^T, \ \ \ \forall \,0 \le i \le n-1. \end{aligned}$$

(10)

It was proved in [15] that $I_{max}(\mathcal {C}(G,D))$ can be calculated by character sums.

Theorem 3

([15])

$$\begin{aligned} I_{max}(\mathcal {C}(G,D))&=\max \limits _{0 \le i \ne j \le n-1} \frac{|(\chi _i \bar{\chi _j})(D)|}{K} =\max \limits _{\chi \in \widehat{G}\setminus \{\chi _0\}}\frac{|\chi (D)|}{K} \end{aligned}$$

(11)

where for a character $\chi$ of G, $\chi (D):=\sum _{d\in D}\chi (d)$.

A slight modification of the construction in Definition 6 was also appeared in the literature such as [23, 34, 35, 41, 49, 58]. Here we provide a general expression and analysis of it. Let $\varvec{e}_i=(0, \ldots , 0, 1, 0, \ldots , 0) \in \{0,1\}^K$ denote a unit-norm vector such that the ith coordinate of $\varvec{e}_i$ is 1 and all the other coordinates are 0. Denote $\mathcal {E}_K:= \{\varvec{e}_i: 1\le i\le K\}$, which forms a standard basis of the K-dimensional Hilbert space.

Lemma 3

The set $\mathcal {C}(G,D) \cup \mathcal {E}_K$ is an $(n+K, K)$-codebook such that

$$\begin{aligned} I_{max}(\mathcal {C}(G,D) \cup \mathcal {E}_K) = \max \left\{ \frac{1}{\sqrt{K}},\; \max \limits _{\chi \in \widehat{G}\setminus \{\chi _0\}}\frac{|\chi (D)|}{K} \right\} . \end{aligned}$$

(12)

Proof

Let $\textbf{a}$ and $\textbf{b}$ be two distinct vectors in $\mathcal {C}(G,D) \cup \mathcal {E}_K$. In terms of $|\langle \textbf{a}, \textbf{b}\rangle |$, there are three possible cases as follows.

• (1) If $\textbf{a},\textbf{b}\in \mathcal {C}(G,D)$, then according to Theorem 3, we have $|\langle \textbf{a}, \textbf{b}\rangle |\le \frac{1}{K}\max \limits _{\chi \in \widehat{G}\setminus \{\chi _0\}}|\chi (D)|$.

• (2) If $\textbf{a},\textbf{b}\in \mathcal {E}_K$, it is easy to see that $|\langle \textbf{a}, \textbf{b}\rangle |=0$.

• (3) If $\textbf{a}\in \mathcal {C}(G,D)$ and $\textbf{b}\in \mathcal {E}_K$, without loss of generality, we may assume that

  $$\begin{aligned} \textbf{a}=\varvec{c}_i=(\chi _i(d_1), \chi _i(d_2), \ldots , \chi _i(d_K))^T/\sqrt{K} \end{aligned}$$

  and $\textbf{b}=\varvec{e}_j$, where $0\le i\le N-1$ and $1\le j\le K$. Since $\chi$ is a character, we have $|\chi _i(d_j)|=1$ and hence $|\langle \textbf{a}, \textbf{b}\rangle |=|\varvec{c}_i \varvec{e}_j^T|=|\chi _i(d_j)/\sqrt{K}|=1/\sqrt{K}$.

Thus the lemma follows. $\square$

In terms of this framework, it is required to find appropriate abelian groups G and the corresponding subsets D such that the value $I_{max}(\mathcal {C}(G,D))$ or $I_{max}(\mathcal {C}(G,D) \cup \mathcal {E}_K)$ is small enough to meet the Welch bound or Levenshtein bound. However it is in general not an easy task. In the next subsection we provide a feasible way to find such pairs (G, D) from a graph theoretic perspective.

5.3 A connection between codebooks and Cayley sum graphs

In this subsection we establish a connection between complex codebooks and Cayley sum graphs in terms of eigenvalues.

According to each Cayley sum graph CayS(G, D) we could exploit the pair G and D to construct a set $\mathcal {C}(G,D)$ of n vectors in $\mathbb {C}^K$ by using Definition 6. From Lemma 2 and Theorem 3 we could see that evaluating the maximum cross-correlation amplitude $I_{max}(\mathcal {C}(G,D))$ of the codebook $\mathcal {C}(G,D)$ is in fact equivalent to estimating the eigenvalue $\lambda (CayS(G,D))$ of the Cayley sum graph CayS(G, D). Specifically we have

Corollary 4

Let G be an abelian group and D be a K-element subset of G. Then the codebook $\mathcal {C}(G,D) \cup \mathcal {E}_K$ satisfies that

$$\begin{aligned} I_{max}(\mathcal {C}(G,D) \cup \mathcal {E}_K) = \max \Bigl \{\frac{1}{\sqrt{K}},\; \frac{\lambda (CayS(G,D))}{K} \Bigr \}. \end{aligned}$$

Here we would like to remark that Corollary 4 could also be obtained from Cayley (directed) graph Cay(G, D), which is a directed graph with vertex set G and edge set $\{(x, y) : x\ominus y \in D\}$, by using a similar argument of that every eigenvalue of Cay(G, D) could be expressed by the form of $\chi (D)$ for $\chi \in \widehat{G}$.

It is worth noting that Corollary 4 shows an interesting relationship between the maximum cross-correlation amplitude of a complex codebook and the second largest eigenvalue of a Cayley sum graph. For a positive integer n, let $G_n$ be an abelian group of order n and $D_n$ be a $K_n$-element subset of $G_n$. It follows by the Welch bound and the Levenshtein bound that for an infinite family $\{(G_n, D_n)\}_{n \ge 1}$ such that $|D_n|=K_n=o(n)$ as $n \rightarrow \infty$, we have

$$\begin{aligned} I_{max}(\mathcal {C}\bigl (G_n,D_n)\cup \mathcal {E}_K \bigr )=\varOmega \Bigl (\frac{1}{\sqrt{K_n}} \Bigr ) . \end{aligned}$$

(13)

On the other hand, if $K_n=o(n)$, we could have the following bound (see e.g. [26, p. 217])$:$

$$\begin{aligned} \lambda (CayS(G_n, D_n))=\varOmega (\sqrt{K_n}). \end{aligned}$$

(14)

By Corollary 4, we could see that in the regime of $K_n=o(n)$ the Cayley sum graph $CayS(G_n, D_n)$ achieves the optimal order of magnitude with respect to the bound (14) if and only if the codebook $\mathcal {C}\bigl (G_n,D_n)$ attains the optimal order of magnitude with respect to the bound (13). This implies that

$$\begin{aligned} \liminf \limits _{n\rightarrow \infty } \frac{I_{max}(\mathcal {C}(G_n,D_n)\cup \mathcal {E}_K)}{I_{wel}(n+K_n, K_n)}=\kappa _1, \end{aligned}$$

or

$$\begin{aligned} \liminf \limits _{n\rightarrow \infty } \frac{I_{max}(\mathcal {C}(G_n,D_n) \cup \mathcal {E}_K)}{I_{lev}(n+K_n, K_n)}=\kappa _2, \end{aligned}$$

where $\kappa _1$ and $\kappa _2$ are constants such that $\kappa _1\ge 1$ and $\kappa _2 \ge 1$ according to Theorems 1 and 2 respectively. Recall that if $\kappa _1=1$ (resp. $\kappa _2=1$), the codebook $\mathcal {C}(G_n,D_n)\cup \mathcal {E}_K$ is said to be asymptotically optimal with respect to the Welch bound (resp. Levenshtein bound), which, however, is not easy to be deterministically constructed in general.

Remark 2

According to Ding and Feng [15], the codebook $\mathcal {C}(G, D)$ with a difference set D of G is optimal with respect to the Welch bound. Hence any Cayley sum graph CayS(G, D) with difference set D of G gives rise to an optimal codebook. On the other hand there seems to be no known construction of optimal codebooks with respect to the Levenshtein bound via specific Cayley sum graphs, which would be an interesting open problem.

6 Explicit codebooks from Cayley sum graphs

In this section we derive asymptotically optimal codebooks based on the newly constructed Cayley sum graphs in Sects. 3 and 4 as well as the established relationship between Cayley sum graphs and codebooks in Sect. 5. The derived codebooks include some existing codebooks as special cases. Furthermore, a discussion on the derived codebooks is also provided based on a number-theoretic result.

6.1 Codebooks from norm-coset graphs

By means of norm-coset graphs, Proposition 1 and Corollary 4 bring forth the Construction 5 below.

Construction 5

Let $t \ge 2$ be an integer, q be a power of a prime p and v be a divisor of $q-1$. Let $H^{\times }$ be a subgroup of order v of the multiplicative group $\mathbb {F}_q^*$. Suppose that $G=(\mathbb {F}_q^*/H^{\times }) \times \mathbb {F}_{q^{t-1}}^+$ and $D=\{({\overline{x}}, Y) \in (\mathbb {F}_{q}^*/H^{\times }) \times \mathbb {F}_{q^{t-1}}^+: \text {Nr}_{q^{t-1}/q}(Y) \in {\overline{x}}\} \subseteq G$. Then, the codebook $\mathcal {C}(G,D) \cup \mathcal {E}_K$ is an $(n+K, K)$-codebook such that $n=(q^t-q^{t-1})/v$, $K=q^{t-1}-1$ and

$$\begin{aligned} I_{max}(\mathcal {C}(G,D) \cup \mathcal {E}_K)=\frac{q^{\frac{t-1}{2}}}{q^{t-1}-1}. \end{aligned}$$

The alphabet size of the codebook $\mathcal {C}(G,D) \cup \mathcal {E}_K$ is $p(q-1)/v+2$.

Remark 3

Concerning $n+K=(q^t-q^{t-1})/v+q^{t-1}-1$ and $K=q^{t-1}-1$, the Welch bound in Theorem 1 gives

$$\begin{aligned} I_{wel}(n+K, K)= \sqrt{\frac{q^t-q^{t-1}}{(q^t+(v-1)q^{t-1}-2v)(q^{t-1}-1)}}. \end{aligned}$$

If $t \ge 3$ is fixed and $v=o(q)$ as $q \rightarrow \infty$, the complex codebooks from Construction 5 are asymptotically optimal in the sense that

$$\begin{aligned} \lim \limits _{n\rightarrow \infty } \frac{I_{max}(\mathcal {C}(G,D)\cup \mathcal {E}_K )}{I_{wel}(n+K, K)} =\lim \limits _{q\rightarrow \infty } \frac{\frac{q^{\frac{t-1}{2}}}{q^{t-1}-1}}{\sqrt{\frac{q^t-q^{t-1}}{(q^t+(v-1)q^{t-1}-2v)(q^{t-1}-1)}}} =1. \end{aligned}$$

Table 2 below shows numerical examples of codebooks from Construction 5.

Table 2 Codebooks from Construction 5 when $q=p$ is a prime, $t=3$ and $v=2$

We also remark that by virtue of sum-product graphs (i.e. norm-coset graphs with $t=2$ and $v=1$), the above Construction 5 can deduce codebooks as obtained in [49], which are asymptotically optimal with respect to the Levenshtein bound.

6.2 Codebooks from trace-coset graphs

Now we present our second construction for codebooks based on Proposition 4 and Corollary 4.

Construction 6

Let $t \ge 2$ be an integer, q be a prime power and u be a divisor of q. Let $H^{+}$ be a subgroup of order u of the additive group $\mathbb {F}_q^+$. Suppose that $G=(\mathbb {F}_q^+/H^{+}) \times \mathbb {F}_{q^{t-1}}^+$ and $D=\{({\overline{x}}, Y) \in (\mathbb {F}_{q}^+/H^{+}) \times \mathbb {F}_{q^{t-1}}^*: \text {Tr}_{q^{t-1}/q}(Y) \in {\overline{x}}\} \subseteq G$. Then, the codebook $\mathcal {C}(G,D) \cup \mathcal {E}_K$ is an $(N+K, K)$-codebook such that $N=(q^t-q)/u$, $K=q^{t-1}-1$ and

$$\begin{aligned} I_{max}(\mathcal {C}(G,D) \cup \mathcal {E}_K)=\frac{q^{\frac{t-1}{2}}}{q^{t-1}-1}. \end{aligned}$$

The alphabet size of the codebook $\mathcal {C}(G,D) \cup \mathcal {E}_K$ is $p(q^{t-1}-1)+2$.

Remark 4

Concerning $n=(q^t-q)/u$ and $K=q^{t-1}-1$, the Welch bound in Theorem 1 gives

$$\begin{aligned} I_{wel}(n+K, K)=\sqrt{\frac{q^t-q}{(q^t+uq^{t-1}-uq-2u)(q^{t-1}-1)}}. \end{aligned}$$

If $t \ge 3$ is fixed and $u<q$ (equivalently, $u=o(q)$ as $q \rightarrow \infty$), the complex codebooks from Construction 6 are asymptotically optimal in the sense that

$$\begin{aligned} \lim \limits _{n\rightarrow \infty } \frac{I_{max}(\mathcal {C}(G,D)\cup \mathcal {E}_K)}{I_{wel}(n+K, K)} =\lim \limits _{q\rightarrow \infty } \frac{\frac{q^{\frac{t-1}{2}}}{q^{t-1}-1}}{\sqrt{\frac{q^t-q}{(q^t+uq^{t-1}-uq-2u)(q^{t-1}-1)}}} =1. \end{aligned}$$

Table 3 below presents numerical examples of codebooks derived from Construction 6.

Table 3 Codebooks from Construction 6 when q is a square of a prime p and $t=3$, $u=p$

As in the first construction, by virtue of sum-product graphs (i.e. trace-coset graphs with $t=2$ and $u=1$), the above Construction 6 can produce asymptotically optimal codebooks with respect to the Levenshtein bound as in [49].

6.3 A further discussion

In this section, we shall further discuss the parameters of asymptotically optimal codebooks derived from Cayley sum graphs (Constructions 5 and 6) with the aid of a number-theoretic result. Specifically, we have the following result.

Theorem 7

Let $p_i$ denote the ith prime (where $p_1=2,p_2=3,p_3=5,\ldots$) and $t\ge 3$ be a fixed integer. Suppose that $p_i-p_{i-1}=o((p_{i-1})^l)$ $(i \rightarrow \infty )$ for some real number $0<l<1/2$. Then for sufficiently large i and every K with $(p_{i-1})^{t-1}-1<K\le (p_{i})^{t-1}-1$, we have a $((p_i)^t-1, K)$ codebook which is asymptotically optimal with respect to the Welch bound.

By the following theorem on prime gaps, we see that Theorem 7 provides asymptotically optimal codebooks for almost all possible length K.

Lemma 4

[12] For each real number $0<l\le 1/2$ and sufficiently large $x>0$, the number of primes $p_i \le x$ such that $p_{i}-p_{i-1}<(p_{i-1})^l$ is at least $x/(\log x)-O(x^{1-(3/2)l+\varepsilon })$ where $\varepsilon >0$ is an arbitrarily small real number.

To prove Theorem 7, we need the following lemma which is a direct consequence of Lemma 3.

Lemma 5

Let G be an abelian group of order n and $D \subseteq G$. Let $1 \le k \le K$ and $D' \subseteq D$ with $|D'|=k$. Then $\mathcal {C}(G,D \setminus D') \cup \mathcal {E}_{K-k}$ is an $(n+K-k, K-k)$-codebook such that

$$\begin{aligned} I_{max}(\mathcal {C}(G,D \setminus D') \cup \mathcal {E}_{K-k}) \le \max \Bigl \{\frac{1}{\sqrt{K-k}},\; \max \limits _{\chi \in \widehat{G}\setminus \{\chi _0\}}\frac{|\chi (D)|+k}{K-k} \Bigr \}. \end{aligned}$$

Proof of Theorem 7

For simplicity, we shall focus on Construction 5 for the case that $v=1$. According to this construction, there exist asymptotically optimal $(n_i+K_i,K_i)$ codebooks with

$$\begin{aligned} n_i=(p_i)^t-(p_i)^{t-1},\ \ K_i=(p_i)^{t-1}-1. \end{aligned}$$

Let $G_i=\mathbb {F}_{p_i}^* \times \mathbb {F}_{(p_i)^{t-1}}^+$ and $D_i=\{(x, Y) \in (\mathbb {F}_{p_i}^*) \times \mathbb {F}_{(p_i)^{t-1}}^+ : \text {Nr}_{(p_i)^{t-1}/p_i}(Y)=x\}$. Let k be any integer with $1\le k<(p_i)^{t-1}-(p_{i-1})^{t-1}$ and $D' \subset D_i$ with $|D'|=k$. By the assumption of $p_i$, we have $k=o((p_i)^{\frac{t-1}{2}})$. It suffices to prove that the $(n_i+K_i-k, K_i-k)$ codebook $\mathcal {C}(G_i,D_i \setminus D') \cup \mathcal {E}_{K_i-k}$ is asymptotically optimal with respect to the Welch bound. In fact, it follows from Lemma 5 that

$$\begin{aligned} I_{max}(\mathcal {C}(G_i,D_i \setminus D') \cup \mathcal {E}_{K_i-k}) \le \frac{(p_i)^{\frac{t-1}{2}}+o((p_i)^{\frac{t-1}{2}})}{(p_i)^{t-1}-o((p_i)^{\frac{t-1}{2}})}, \end{aligned}$$

where the right-hand side is asymptotically equal to $1/(p_i)^{\frac{t-1}{2}}$ as $i \rightarrow \infty$. Thus a simple calculation shows that

$$\begin{aligned} \limsup \limits _{i\rightarrow \infty } \frac{I_{max}(\mathcal {C}(G_i,D_i \setminus D') \cup \mathcal {E}_{K_i-k})}{I_{wel}(n_i+K_i-k, K_i-k)} =1, \end{aligned}$$

proving the theorem. $\square$

We remark that similarly to the above argument, the desired codebooks in Theorem 7 can be derived from Construction 6 and many existing constructions as well.

7 Conclusion

In this paper we constructed two families of Cayley sum graphs and estimated their second largest eigenvalues based on Gaussian sums. Next we established a connection between complex codebooks and Cayley sum graphs. Accordingly, infinite families of complex codebooks were derived, which have flexible new parameters, small alphabet size, and are asymptotically optimal with respect to the Welch bound or the Levenshtein bound. It would be of interest to explore more on the established relationship between Cayley sum graphs and codebooks, such as to consider explicitly constructing good Cayley sum graphs in the spirit of complex codebooks.