A class of nearly optimal codebooks and their applications in strongly regular Cayley graphs

1.   Introduction

To distinguish the signals between different users in CDMA communication systems, codebooks are required to have small inner-product correlation. An $(N, K)$ codebook $\mathcal{C}$ is a vector set $\{\mathbf{c}_i\}_{i = 0}^{N-1}$, where $\mathbf{c}_i$ is a unit norm $1\times K$ complex vector over an alphabet $A$. As an important performance measure of a codebook, the maximum cross-correlation amplitude of $\mathcal{C}$ is defined by

where $\mathbf{c}_j^{H}$ denotes the conjugate transpose of $\mathbf{c}_j$. For a given $K$, it is preferable to construct codebooks with $N$ being as large as possible and $I_{\max}(\mathcal{C})$ being minimal simultaneously. However, the Welch bound demonstrates that there is a tradeoff between $N$, $K$ and $I_{\max}(\mathcal{C})$ of a codebook.

Lemma 1. (Welch bound, ^[1]) For any $(N, K)$ codebook $\mathcal{C}$ with $N\geq K$, then

The equality in (1.1) achieves if and only if

for all pairs of $(i, j)$ with $i\neq j$.

If the equality in (1.1) holds, then $\mathcal{C}$ is called a maximum-Welch-bound-equality (MWBE) codebook. MWBE codebooks are applied in many practical fields, such as CDMA communications systems, compressed sensing and space-time codes. Unfortunately, it is very difficult to construct MWBE codebooks, and only a few MWBE codebooks are known in the literature ^{[2,3,4,5,6,7,8,9]}. Hence, a lot of attempts are made to construct codebooks which nearly meet the Welch bound, i.e., $\lim_{N\rightarrow +\infty} I_{\max}(\mathcal{C})/I_{w}(\mathcal{C}) = 1$ for an $(N, K)$ codebook $\mathcal{C}$ with $N\geq K$. Many classes of known nearly optimal codebooks have been produced for the past few years ^{[10,11,12,13,14,15,16,17,18]}.

In this paper, we are concerned with two purposes. The first objective is to give a new construction of codebooks which are nearly optimal with respect to the Welch bound. The other objective is to provide a new construction of strongly regular Cayley graphs using the set $D$ in (3.1). It should be pointed out that these presented codebooks have new parameters.

This paper is arranged as follows. Some basic definitions and results on exponential sums are given in Sect. Ⅱ. The constructions of nearly optimal codebooks and strongly regular Cayley graphs are ordered in Sect. Ⅲ. We make a conclusion in Sect. Ⅳ.

2.   Preliminaries

In this section, we present some basic concepts and a number of lemmas on exponential sums. Some symbols and notations are given as follows.

$-$ $m_1$ and $m_2$ are two integers.

$-$ $n_1 = p^{m_1}+1$ and $n_2 = p^{m_2}+1$.

$-$ $q_1 = p^{2m_1}$, $q_2 = p^{2m_2}$ and $p$ is an odd prime.

$-$ $\zeta_p = e^{\frac{2\pi\sqrt{-1}}{p}}$ is a primitive $p$-th root of unity.

$-$ ${\operatorname{Tr}}_1$ denotes the trace function from $\mathbb{F}_{q_1}$ to $\mathbb{F}_p$.

$-$ ${\operatorname{Tr}}_2$ denotes the trace function from $\mathbb{F}_{q_2}$ to $\mathbb{F}_p$.

$-$ $\chi_1$ denotes the canonicial additive character of $\mathbb{F}_p$.

$-$ $\eta_1$ denotes the quadratic character of $\mathbb{F}_p$.

Let $G$ be a finite Abelian group with order $n$, and $U$ be the multiplicative group of complex numbers of absolute value $1$. A character $\chi$ of $G$ is a homomorphism from $G$ to $U$ with $\chi(ab) = \chi(a)\chi(b)$ for all $a, b\in G$. Given two characters $\chi$, $\chi^{'}$ of $G$, we can get a product character $\chi\chi^{'}$ by letting $\chi\chi^{'}(a) = \chi(a)\chi^{'}(a)$ for all $a\in G$. It can be easily seen that the set $G^{\wedge}$ consisting of all characters of $G$ forms an Abelian group under the multiplication of characters.

Let $p$ be an odd prime and $q = p^n$ with $n\in \mathbb{N}$. Let $\mathbb{F}_q$ be the finite field with $q$ elements and ${\operatorname{Tr}}$ the trace function from $\mathbb{F}_q$ to $\mathbb{F}_p$. For a finite field $\mathbb{F}_q$, there are two finite abelian groups, i.e., the additive group $\mathbb{F}_q^{+}$ and the multiplicative group $\mathbb{F}_q^{*}$ of $\mathbb{F}_q$. In both cases, explicit formulas for the characters are given as follows.

Definition 1. The canonical additive character of $\mathbb{F}_q^{+}$ is defined by $\chi(x) = \zeta_p^{{\operatorname{Tr}}(x)}$ for all $x\in \mathbb{F}_q$. For $b\in \mathbb{F}_q$, the function $\mu_b$ with $\mu_b(x) = \chi(bx)$ is an additive character of $\mathbb{F}_q$ and every additive character of $\mathbb{F}_q$ can be obtained in this way.

Definition 2. Let $\alpha$ be a fixed primitive element of $\mathbb{F}_q^{*}$. For each $0\leq j\leq q-2$, the function $\varphi_j$ with

defines a multiplicative character of $\mathbb{F}_q^{*}$. For $j = (q-1)/2$, the character $\varphi_{(q-1)/2}$, denoted by $\eta$, is called the quadratic character of $\mathbb{F}_q$ and is extended by setting $\eta(0) = 0$.

The Gauss sum $G(\eta, \chi)$ over $\mathbb{F}_q$ is defined by

The explicit values of $G(\eta, \chi)$ are determined in ^[19].

Lemma 2. (^[19], Theorem 5.15) With the symbols and notations above, we have

Briefly, we use $G(\eta)$ to denote $G(\eta, \chi)$. The following identities on Gauss sums will be employed in the sequel.

Lemma 3. (Theorem 5.12 , ^[19]) For $y\in \mathbb{F}_{q}$, we obtain

Gauss sums are the most significant types of exponential sums, since they govern the transition from the multiplicative to the additive structure.

Lemma 4. (^[19], p.195) With the symbols and notations above, we have

The following several lemmas are useful in the next section.

Lemma 5. (^[20]) Let $n = 2m$ for a positive integer $m$ and $N = p^{m}+1$ for an odd prime $p$. Assume $z\in \mathbb{F}_{p}^{*}$ and $a\in \mathbb{F}_{q}$. Then

Lemma 6. (^[21], Theorem 2) Assume that $n = 2m$ for a positive integer $m$ and $N = p^{m}+1$ for an odd prime $p$. For $z\in \mathbb{F}_{p}^{*}$, we have

Lemma 7. (^[22], Lemma 3.12) Let $\mathbb{F}_{q_1}$ and $\mathbb{F}_{q_2}$ denote the finite fields with $q_1$ and $q_2$ elements, respectively. Then there is an isomorphism

From this lemma, we know

where $\mu_{a, b}(x, y) = \zeta_p^{{\operatorname{Tr}}_1(ax)+{\operatorname{Tr}}_2(by)}$ for $(x, y)\in \mathbb{F}_{q_1} \times\mathbb{F}_{q_2}$.

3.   Proofs and main results

In this section, we give a construction of nearly optimal codebooks, introduce their parameters and give the proofs. Then we analyse the strongly regular Cayley graphs derived from the presented codebooks.

Define

where $\mathbb{F}_p^{*2} = \langle \beta^2\rangle$ and $\beta$ is a primitive element of $\mathbb{F}_{p}^{*}$.

The codebook $\mathcal{C}_D$ is given by

where

and $|D|$ denotes the cardinality of the set $D$.

To prove the main results of this paper, we introduce the sets $E$ and $F$, which are defined by (3.3) and (3.4), respectively. Let

Regarding the set $D$, we have the following two lemmas.

Lemma 8. With the symbols and notations above, we have

Proof. From Lemma 6, we obtain

Hence, we have

It can be easily checked that

By Lemma 4, we obtain

where the last equality follows from Lemma 6. From the fact that $\sum_{z\in \mathbb{F}_{p}^{*}}\eta_1(z) = 0$, we have

Then the desired conclusion follows from (3.5)–(3.7). □

Example 1. Let $p = 5$ and $(m_1, m_2) = (2, 1)$. By the Magma program, we get that the cardinality $|D|$ of the set $D$ is $6200$, which accords with Lemma 8.

Example 2. Let $p = 7$ and $(m_1, m_2) = (2, 2)$. By Lemma 8, we get $|D| = 2469600$, which is consistent with the numerical computation by Magma.

Lemma 9. For $(a, b)\in \mathbb{F}_{q_1} \times \mathbb{F}_{q_2}$ and $(a, b)\neq(0, 0)$, we have

Proof. By definition, we have

where the set $E$ is given in (3.3). Note that

if $(a, b)\in \mathbb{F}_{q_1}\times \mathbb{F}_{q_2}\setminus \{(0, 0)\}$. Hence, we get

where the set $F$ is given in (3.4). Together with Lemma 5, we derive

For $z\in \mathbb{F}_{p}^{*}$, from the map $-\frac{1}{4z }\rightarrow z$, we get

From Lemma 4, we obtain

where the last equality follows from Lemma 5. For $z\in \mathbb{F}_{p}^{*}$, from the map $-\frac{1}{4z}\rightarrow z$, we get

where the last equality follows from Lemmas 2 and 3. The desired conclusion follows from (3.8)–(3.10). □

Theorem 10. Let

Then the set $\mathcal{C}_D$ defined in (3.2) is a $[p^{2m_1+2m_2}, K]$ codebook with $I_{\max}(\mathcal{C}_D) = p^{m_1+m_2-1}(p+1)/(2K)$.

Proof. From the definition of the codebook $\mathcal{C}_D$ and Lemma 8, we deduce that $\mathcal{C}_D$ is a $[p^{2m_1+2m_2}, K]$ codebook. Given two codewords $\mathbf{c}_{a, b}$ and $\mathbf{c}_{c, d}$ with $(a-c, b-d)\neq (0, 0)$, we have

By Lemma 9, we obtain that

Hence, we have

□

Theorem 11. The codebook $\mathcal{C}_D$ constructed in Theorem 10 is nearly optimal with respect to the Welch bound.

Proof. By Theorem 10, we derive that

Therefore, we deduce that

Obviously,

which implies that $\mathcal{C}_D$ is nearly optimal with respect to the Welch bound. □

Table 1 lists some parameters of the codebooks defined in (3.2). From this table, we can derive that $I_{\max}(\mathcal{C}_D)$ is very close to $I_{w}(\mathcal{C}_D)$, as the odd prime $p$ increases. This accords with Theorems 10 and 11 and also guarantees the correctness of our main results.

For $(p, m_1, m_2) = (199, 6, 6)$, it can be easily checked that $I_{\max}/I_w = 1.0050$. This implies that the ratio $I_{\max}/I_w$ is much closer to $1$, if $p$ is a larger prime.

Motivated by the work in ^[23], we use the set $D$ defined in (3.1) to give a construction of strongly regular Cayley graphs. The definition of strongly regular graphs is given below.

Definition 3 (^[4]) A strongly regular graph $(v, k, \lambda, \mu)$ is a graph with $v$ vertices which is not complete or edgeless and which has the following properties:

(1) The graph is regular of valency $k$, i.e., each vertex is adjacent to $k$ vertices.

(2) There are exactly $\lambda$ vertices adjacent to both $x$ and $y$, if $x$ and $y$ are two adjacent vertices.

(3) There are exactly $\mu$ vertices adjacent to both $x$ and $y$, if $x$ and $y$ are two nonadjacent vertices.

One of the most efficient approaches to construct strongly regular graphs is the Cayley graph construction. Let $G$ be a finite Abelian group and $D$ be a subset of $G$ satisfying that $0\not\in D$ and $-D = \{-d:d\in D\} = D$. The Cayley graph on $G$ with connection set $D$, written as Cay($G, D$), is the graph with the elements of $G$ as vertices; two vertices $x$ and $y$ are adjacent if and only if $x-y\in D$.

For the set $D$ given in (3.1), it is clear that $0\not\in D$ and $-D = D$. Here and hereafter, we use Cay($\mathbb{F}_{q_1}\times \mathbb{F}_{q_2}, D$) to denote the Cayley graph on $\mathbb{F}_{q_1}\times \mathbb{F}_{q_2}$ with connection set $D$. For $(a, b)\in \mathbb{F}_{q_1}\times \mathbb{F}_{q_2}$, let

where $\mu_{a, b}\in \left(\mathbb{F}_{q_1}\times \mathbb{F}_{q_2}\right)^{\wedge}$. The eigenvalues of Cay($\mathbb{F}_{q_1}\times \mathbb{F}_{q_2}, D$) are defined by $\mu_{a, b}(D)$. When $(a, b) = (0, 0)$, we have $\mu_{0, 0}(D) = |D| = K$, which is called the trivial eigenvalue of Cay($\mathbb{F}_{q_1}\times\mathbb{F}_{q_2}, D$). It is known that Cay($\mathbb{F}_{q_1}\times \mathbb{F}_{q_2}, D$) is strongly regular if and only if $\mu_{a, b}(D)$ with $(a, b)\neq (0, 0)$ has exactly two distinct values.

Theorem 12. Let $D$ be the set given in (3.1), and $K$ is the integer given in (3.11). Then we have

(1) Cay($\mathbb{F}_{q_1}\times \mathbb{F}_{q_2}, D$) has two distinct nontrivial eigenvalues, $p^{m_1+m_2-1}(1+p)/2$ and $p^{m_1+m_2-1}(1-p)/2$.

(2) Cay($\mathbb{F}_{q_1}\times \mathbb{F}_{q_2}, D$) is strongly regular with parameters

Proof. (1) By Lemma 9, we know

for $(a, b)\in \mathbb{F}_{q_1}\times \mathbb{F}_{q_2}\setminus \{(0, 0)\}$. This implies that Cay($\mathbb{F}_{q_1}\times \mathbb{F}_{q_2}, D$) has precisely two distinct nontrivial eigenvalues $p^{m_1+m_2-1}(1+p)/2$ and $p^{m_1+m_2-1}(1-p)/2$.

(2) From the definition of Cay($\mathbb{F}_{q_1}\times \mathbb{F}_{q_2}, D$) and the first part of this theorem, we get that Cay($\mathbb{F}_{q_1}\times \mathbb{F}_{q_2}, D$) has $p^{2m_1+2m_2}$ vertices and Cay($\mathbb{F}_{q_1}\times \mathbb{F}_{q_2}, D$) is regular of valency $|D|$. Let $k$ denote the valency of Cay($\mathbb{F}_{q_1}\times \mathbb{F}_{q_2}, D$). Then

Let $r$ and $s$ denote the two nontrivial eigenvalues of Cay($\mathbb{F}_{q_1}\times \mathbb{F}_{q_2}, D$). By Theorem 9.1.2 in ^[24], the parameters $\lambda$ and $\mu$ of the strongly regular graph can be computed by $\lambda = s+r+k+sr$ and $\mu = k+sr$. Then the second part of this theorem follows. □

As a comparison, the parameters of some known strongly regular graphs and the newly presented ones are listed in Table 2.

4.   Conclusions

In this paper, a class of codebooks is constructed using the combination of the quadratic character over $\mathbb{F}_p$ and the trace functions over finite fields. Main results show that they are nearly optimal with respect to the Welch bound. Their applications in Cayley graphs are investigated and a kind of strongly regular Cayley graphs is obtained by the use of set $D$. Some interesting nearly optimal codebooks were presented in ^{[10,12,13,14,15,16,17,18]}. The parameters of the codebooks obtained in this paper were not found in the literature. This means that $\mathcal{C}_D$ has new parameters.

Author contributions

The authors contributed equally to the writing of this paper. All authors have read and agreed to the published version of the manuscript.

Use of AI tools declaration

The authors declare that they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This work is supported by the Humanities and Social Sciences Youth Foundation of Ministry of Education of China (No. 22YJC870018), the Science and Technology Development Fund of Tianjin Education Commission for Higher Education (No. 2020KJ112, KYQD1817), and Science and Technology Project of Putian City (No. 2021R4001-10), Haihe Lab. of Information Technology Application Innovation (No. 22HHXCJC00002), the Open Project of Tianjin Key Laboratory of Autonomous Intelligence Technology and Systems (No. TJKL-AITS-20241004, No. TJKL-AITS-20241006).

Conflict of interest

The authors declare no conflicts of interest.