A construction of strongly regular Cayley graphs and their applications to codebooks

1.   Introduction

Let $\Gamma$ be a strongly regular graph with $v$ vertices and parameters $k$, $\lambda$ and $\mu$. Then $\Gamma$ is defined as follows: (1) For any two adjacent vertices $x$ and $y$, there are exactly $\lambda$ vertices adjacent to both $x$ and $y$; (2) for any two nonadjacent vertices $x$ and $y$, there are exactly $\mu$ vertices adjacent to both $x$ and $y$. For a more detailed introduction on strongly regular graphs, please refer to ^[1,2].

Cayley graphs are an effective tool constructing strongly regular graphs. Let $(G, +)$ be a finite abelian group and $S$ be a subset of $G\setminus \{0\}$ such that $S = -S$, where $0$ is the identity of $G$. The Cayley graph Cay$(G, S)$ is defined as the graph $\Gamma(G, E)$ where two vertices $a$ and $b$ are adjacent if and only if $a-b\in S$. Let $\widehat{G}$ be the character group of $G$ consisting of all characters of $G$. The eigenvalues of Cay$(G, S)$ are given by $\phi(S) = \sum_{x\in S}\phi(x)$, where $\phi\in \widehat{G}$. It is well known that Cay$(G, S)$ is strongly regular if and only if $\phi(S)$ with $\phi\in \widehat{G}\setminus \{1_{\widehat{G}}\}$ take exactly two values, where $1_{\widehat{G}}$ is the identity of $\widehat{G}$. By the determination of Cayley graphs in the additive groups of finite fields, strongly regular cayley graphs were proposed in ^[3,4,5,6].

It should be noted that strongly regular graphs are related to some combinational objects, such as linear codes, two-intersection sets and partial difference set ^[7,8]. For these connections, we are inspired to construct asymptotically optimal codebooks by using the connection set $S$ of Cay($G, S$). An $(N, K)$ codebook $\mathcal{C}$ is defined to be a set $\{\mathbf{c}_i\}_{i = 0}^{N-1}$ of $N$ units norm $1\times K$ complex vectors $\mathbf{c}_i$, and $\mathbf{c}_i$ ($0\leq i\leq N-1$) are called codewords of the codebook $\mathcal{C}$. As an important measure of performance of a codebook $\mathcal{C}$ in code-division multiple access system, the maximum correlation amplitudes $I_{\max}(\mathcal{C})$ is defined by

where $\mathbf{c}_j^{H}$ denotes the conjugate transpose of a complex vector $\mathbf{c}_j$.

Minimizing $I_{\max}(\mathcal{C})$ is a meaningful problem as it can optimize some performance metrics such as average signal-to-noise ratio and outage probability. Hence, for a given $K$, it is desirable to construct codebooks with $N$ as large as possible and $I_{\max}(\mathcal{C})$ as small as possible simultaneously. Unfortunately, there is a tradeoff among the parameters $N$, $K$ and $I_{\max}(\mathcal{C})$. Let $I_{w}(\mathcal{C}) = \sqrt{(N-K)/\left((N-1)K\right)}$, we know $I_{\max}(\mathcal{C})\geq I_w(\mathcal{C})$ ^[9]. If $\mathcal{C}$ achieves the Welch bound, that is, $I_{\max}(\mathcal{C}) = I_w(\mathcal{C})$, then $C$ is referred to as a Welch-bound-equality codebook. In ordinary circumstance, it is extremely difficult to construct codebooks achieving the Welch bound. As a consequence, researchers attempt to construct codebooks asymptotically meeting the Welch bound, that is, $I_{\max}(\mathcal{C})$ is slightly higher than $I_{w}(\mathcal{C})$, but $\lim_{N\rightarrow \infty}I_{\max}(\mathcal{C})/I_{w}(\mathcal{C}) = 1$ ^[10,11,12].

This paper is organized as follows. Some interesting mathematical foundations will be introduced in Section II. Based on these related character sums, a class of strongly regular graphs and nearly optimal codebooks are presented in Section III. In addition, these constructed codebooks have new parameters.

For convenience, we use the following notations in the following sequel.

● $m$, $s$ are positive integers and $n = ms$.

● $p$ is an odd prime and $q = p^n$.

● ${\operatorname{Tr}}_m^{n}$ denotes the trace function from $\mathbb{F}_{p^n}$ to $\mathbb{F}_{p^m}$.

● $\beta$ is a primitive element of $\mathbb{F}_{p^n}$.

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

● $\eta_n$ and $\eta_m$ denote the quadratic characters of $\mathbb{F}_{p^n}$ and $\mathbb{F}_{p^m}$, separately.

● $\chi_n$ and $\chi_m$ denote the canonical additive characters of $\mathbb{F}_{p^n}$ and $\mathbb{F}_{p^m}$, separately.

● $\mu_a$ denotes an additive character of $\mathbb{F}_{p^n}$ for $a\in \mathbb{F}_{p^n}$.

2.   Preliminaries

In this section, we start with characters of finite fields. To prove the main results of this letter, we need a number of results on exponential sums that are derived for the proofs.

For an odd prime $p$, let $q = p^n$ and $\mathbb{F}_q$ denote the finite field with $q$ elements. Then ${\operatorname{Tr}}_m^{n}$ is defined by

and ${\operatorname{Tr}}_m^{n}$ is called the trace function from $\mathbb{F}_{p^n}$ to $\mathbb{F}_{p^m}$.

An additive character of $\mathbb{F}_{p^n}$ is a homomorphism $\chi$ from the additive group of $\mathbb{F}_{p^n}$ to the multiplicative group of complex numbers of absolute value $1$. The function

defines an additive character of $\mathbb{F}_{p^n}$ and $\chi_n$ is called the canonical additive character of $\mathbb{F}_{p^n}$. For $a\in\mathbb{F}_{p^n}$, define

Obviously, $\mu_a$ is also an additive character of $\mathbb{F}_{p^n}$. And every additive character of $\mathbb{F}_{p^n}$ can be obtained in this way ^[13]. Its orthogonality relation is given by

Let $\beta$ be a primitive element of $\mathbb{F}_q$. For a fixed integer $j$, $0\leq j\leq q-2$, the function

defines a multiplicative character of $\mathbb{F}_q$. In this paper, we use $\eta_n$ to denote the quadratic character $\chi_{(q-1)/2}$ of $\mathbb{F}_q$. And the quadratic character $\eta_n$ is extended by letting $\eta_n(0) = 0$. The orthogonality relation for quadratic characters is given by

where $\eta_k$ is the quadratic character of $\mathbb{F}_{p^k}$ and $k$ is a positive integer.

The Gauss sum $G(\eta_m, \chi_m)$ over $\mathbb{F}_{p^m}$ is defined by ^[13]

where $\eta_m$ and $\chi_m$ are the quadratic and canonical additive characters of $\mathbb{F}_{p^m}$, respectively.

The Gauss sum $G(\eta_m, \chi_m)$ can be evaluated explicitly and the result on $G(\eta_m, \chi_m)$ is given in the following lemma.

Lemma 1. [13, Theorem 5.15] Let $\mathbb{F}_{p^m}$ be the finite field with $p^m$ element, where $p$ is an odd prime. Then

where $p^* = \left(\frac{-1}{p}\right)p$.

Hence, we shall abbreviate $G(\eta_m, \chi_m)$ to $G_m$. The following lemma establishes a relationship between the quadratic character $\eta_m$ and the canonical additive character $\chi_m$ of $\mathbb{F}_{p^m}$.

Lemma 2. [13, p. 195] With symbols and notations above, we have

Let $f(x)$ be a function from $\mathbb{F}_q$ to $\mathbb{F}_p$. The Walsh transform of $f$ is defined by

for $\beta\in \mathbb{F}_q$. The following lemma states a property of the Walsh transform of $f(x) = \alpha x^2$, where $\alpha\in \mathbb{F}_{q}^{*}$.

Lemma 3. ^[14] For $\alpha\in \mathbb{F}_{q}^{*}$, the Walsh transform coefficient of ${\operatorname{Tr}}_1^{n}(\alpha x^2)$ is equal to

where $\beta\in \mathbb{F}_q$ and $p^* = \left(\frac{-1}{p}\right)p$.

Below we give a few results which are used to obtain the main results of this paper.

Lemma 4. Let symbols be the same as before. Then we have:

(1) If $s\geq2$ is even, then $\eta_n(z) = 1,$ for $z\in \mathbb{F}_{p^m}^{*}$.

(2) If $s\geq2$ is odd, then $\eta_n(z) = \eta_m(z),$ for $z\in \mathbb{F}_{p^m}^{*}$.

Proof. Assume that $\mathbb{F}_{p^n}^{*} = \langle \beta\rangle$, we get $\mathbb{F}_{p^m}^{*} = \langle \beta^{\frac{p^n-1}{p^m-1}} \rangle$. For $n = ms$, we have

This means that the parity of $(p^n-1)/(p^m-1)$ is the same as $s$. Hence, we have

for $z\in \mathbb{F}_{p^m}^{*}$. □

Lemma 5. [13, Theorem 5.12] For $y\in \mathbb{F}_{p^m}$, we obtain

3.   Proofs and main results

In this section, we provide a construction of strongly regular Cayley graphs and a family of asymptotically optimal codebooks. For $\alpha\in \mathbb{F}_{q}^{*}$, let

The following lemma gives the cardinality of the special subset $D_\alpha$ of $\mathbb{F}_q$.

Lemma 6. Let symbols be the same as before. Then the cardinality $|D_\alpha|$ of $D_\alpha$ is given by:

(1) If $s$ is even, then

(2) If $s$ is odd, then

Proof. In order to determine the cardinality of $D_\alpha$, we firstly compute the values of the following two equalities:

It is clear that

Note that

By Lemmas 3 and 4, we get

Hence, we obtain

Now we determine the values of $A_2$. By Lemma 2, we have

where the last equality follows from the fact that $\sum_{a\in \mathbb{F}_{p^m}^*}\eta_m(a) = 0$ and Lemma 4. By definition, we deduce that

The results of this lemma follow from (3.4)–(3.6). □

Example 1. Let $p = 5$, $n = 4$, $m = 2$ and $s = 2$. If $\alpha$ is a primitive element of $\mathbb{F}_{5^4}^{*}$, by Lemma 6 we get $|D_\alpha| = 288$, which agrees with numerical computations by Magma. If $\alpha = 1$, then $|D_1| = 240$, which is consistent with Magma program computation.

Example 2. Let $p = 7$, $n = 3$, $m = 1$ and $s = 3$. If $\alpha$ is a primitive element of $\mathbb{F}_{7^3}^{*}$, by Lemma 6 we get $|D_\alpha| = 168$, which agrees with Magma program. If $\alpha = 1$, then $|D_1| = 126$, which coincides with numerical results by Magma program computation.

Lemma 7. For $a, \alpha\in \mathbb{F}_{p^n}^{*}$, define

(1) If $s$ is an even integer, then

where $A = \frac{(-1)^{n-1}\eta_n(-\alpha)(p^*)^{\frac{n}{2}}}{p^m}$.

(2) If $s$ is an odd integer, then

where $B = \frac{(-1)^{n+m}(p^*)^{\frac{m+n}{2}}\eta_n(-\alpha)}{p^m}$.

Proof. For $a\in\mathbb{F}_{p^n}^{*}$, by the orthogonality relation of $\mu_a$ we get

By Lemma 3, we get

From the map $z\mapsto -\frac{1}{z}$, we obtain

When $s$ is even, from Lemmas 4 and 5, we have the result (1) of this lemma.

When $s$ is odd, the desired result follows from Lemmas 4 and 5.

□

Lemma 8. For $a, \alpha\in \mathbb{F}_{p^n}^{*}$, let

(1) If $s$ is even, then

where $A = \frac{(-1)^{n-1}(p^*)^{\frac{n}{2}}\eta_n(-\alpha)}{p^m}$.

(2) If $s$ is odd, then

where $B = \frac{(-1)^{n+m}(p^*)^{\frac{m+n}{2}}\eta_n(-\alpha)}{p^m}$.

Proof. It follows from Lemma 2 that

From the map $z\mapsto -\frac{1}{z}$, we derive that

The desired result follows from (3.8), Lemmas 4 and 5.

□

Theorem 9. Let symbols be the same as before and $s\geq2$ be even. Then the Cayley graph Cay$(\mathbb{F}_{p^n}, D_\alpha)$ is strongly regular with non-trivial eigenvalues $-(p^*)^{\frac{n}{2}}\left(p^m+1\right)\eta_n(-\alpha)/(2p^m)$ and $(p^*)^{\frac{n}{2}}\left(p^m-1\right)\eta_n(-\alpha)/(2p^m)$.

Proof. For $a\in \mathbb{F}_{p^n}^{*}$, we deduce that

where the last equality follows from that $\eta_m(0) = 0$. Then the desired conclusions follow from Lemmas 7 and 8. □

Remark 1. Let $s > 1$ be an odd integer. Then the eigenvalues of the Cayley graph Cay$(\mathbb{F}_{p^n}, D_\alpha)$ can also be computed by a similar method given in Theorem 9. It can be easily checked that

where $a\in \mathbb{F}_{p^n}^{*}$ and $B = (-1)^{n+m}\eta_n(-\alpha)(p^*)^{\frac{m+n}{2}}/p^m$. This means that the Cayley graph Cay$(\mathbb{F}_{p^n}, D_\alpha)$ is not strong regular if $s$ is odd.

Motivated by the work in ^[15], we give a construction of asymptotically optimal codebooks based on the strongly regular Cayley graph Cay$(\mathbb{F}_{p^n}, D_\alpha)$ defined in Theorem 9. For $\alpha\in \mathbb{F}_{p^n}^{*}$, let

where $\mathbf{c}_{\alpha, a} = \left(\frac{1}{\sqrt{|D_\alpha|}}\mu_a(x)\right)_{x\in D_\alpha}$.

Theorem 10. Let

and let $s\geq2$ be a fixed even integer. Then $\mathcal{C}_\alpha$ defined by (3.9) is an asymptotically optimal codebook with parameters $[p^n, K]$.

Proof. By the definition of $\mathcal{C_\alpha}$ and Lemma 6, we deduce that $\mathcal{C}_\alpha$ is a $[p^n, K]$ codebook. For any two distinct codewords $\mathbf{c}_a$ and $\mathbf{c}_b$ in $\mathcal{C}_\alpha$ (i.e., $a\neq b \in \mathbb{F}_{p^n}$), it can be easily checked that

It follows from Theorem 9 that

which implies that

According to the Welch bound, we have

It is easy to check that

which means that the codebook $\mathcal{C}_\alpha$ is asymptotically optimal with respect to the Welch bound.

□

Remark 2. Many readers may wonder what parameters the codebook $\mathcal{C}_\alpha$ has when $s$ is an odd integer and whether it is asymptotically optimal. If $s$ is odd, then by Theorems 6 and 9 we know the codebook $\mathcal{C}_\alpha$ defined in (3.9) has parameters

It can be verified that

which implies that $\mathcal{C}$ is not asymptotically optimal.

In Table 1, we assume that $\alpha$ is a primitive element of $\mathbb{F}_{p^n}^*$, $p = 3$ and $s = 4$. And we show some parameters of the codebook $\mathcal{C}_\alpha$ in this table. From Table 1, it can be seen that $\mathcal{C}_\alpha$ is asymptotically optimal with respect to the Welch bound for sufficiently large $N$. This also agrees with the result of Theorem 10.

To give a comparison, we present the parameters $(N, K)$ of some known asymptotically optimal codebooks and the codebook defined in (3.9) in Table 2. From this table, we can conclude that $\mathcal{C}_\alpha$ has new parameters.

4.   Conclusions

In this paper, we propose a method for constructing strongly regular graphs. Then we use the connection set $D_\alpha$ ($\alpha\in \mathbb{F}_{p^n}^*$) of the strongly regular graph Cay($\mathbb{F}_{p^n}^{*}, D_\alpha$) to give a class of codebook $\mathcal{C}_\alpha$. In addition, the parameters $[N, K]$ and $I_{\max}(\mathcal{C}_\alpha)$ of the codebook $\mathcal{C}_\alpha$ are determined in Theorem 10. Table 1 demonstrates that these proposed codebooks are asymptotically optimal according to the Welch bound.

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 was supported by the Innovation Project of Engineering Research Center of Integration and Application of Digital Learning Technology (No.1221049), 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, 2022KJ075), Haihe Laboratory of Information Technology Application Innovation (No. 22HHXCJC00002), the National Natural Science Foundation of China (Grant No. 12301670).

Conflict of interest

The authors declare no conflicts of interest.