Symmetric bilinear forms over finite fields with applications to coding theory

Abstract

Let $q$ be an odd prime power and let $X(m,q)$ be the set of symmetric bilinear forms on an $m$-dimensional vector space over $\mathbb {F}_q$. The partition of $X(m,q)$ induced by the action of the general linear group gives rise to a commutative translation association scheme. We give explicit expressions for the eigenvalues of this scheme in terms of linear combinations of generalized Krawtchouk polynomials. We then study $d$-codes in this scheme, namely subsets $Y$ of $X(m,q)$ with the property that, for all distinct $A,B\in Y$, the rank of $A-B$ is at least $d$. We prove bounds on the size of a $d$-code and show that, under certain conditions, the inner distribution of a $d$-code is determined by its parameters. Constructions of $d$-codes are given, which are optimal among the $d$-codes that are subgroups of $X(m,q)$. Finally, with every subset $Y$ of $X(m,q)$, we associate two classical codes over $\mathbb {F}_q$ and show that their Hamming distance enumerators can be expressed in terms of the inner distribution of $Y$. As an example, we obtain the distance enumerators of certain cyclic codes, for which many special cases have been previously obtained using long ad hoc calculations.

Appendix: computation of the \(Q\)-numbers

We shall now prove Theorem 2.2. We write $Q^{(m)}_{k,\epsilon }(i,\tau )$ for $Q_{k,\epsilon }(i,\tau )$ to indicate dependence on $m$. It will also be convenient to write

$$\begin{aligned} Q^{(m)}_{0,-1}(i,\tau )=0. \end{aligned}$$

(6.1)

We begin with the following recurrence for the $Q$-numbers.

Lemma 6.1

For $k,i\ge 1$, we have

$$\begin{aligned}&Q^{(m)}_{k,\epsilon }(i,\tau )=Q^{(m)}_{k,\epsilon }(i-1,1)\\&\quad -\tfrac{1}{2}q^{m-i}\gamma _q^{i-1} \Big [Q^{(m-1)}_{k-1,\epsilon }(i-1,1)(q-\tau \,\gamma _q)-(-1)^iQ^{(m-1)}_{k-1,-\epsilon }(i-1,1)(q+\tau \,\gamma _q)\Big ]. \end{aligned}$$

Proof

Let $X^{(m)}_{i,\tau }$ be the set of $m\times m$ symmetric matrices of rank $i$ and type $\tau$. Fix $i\in \{1,\ldots ,m\}$ and $\tau \in \{-1,1\}$. Let $S$ be an $m\times m$ diagonal matrix of rank $i$ with diagonal $[z,1,\ldots ,1,0,\ldots ,0]$ such that $\eta (z)=\tau$, and let $S'$ be the $(m-1)\times (m-1)$ diagonal matrix of rank $i-1$ with diagonal $[1,\ldots ,1,0,\ldots ,0]$. From (2.7) and (2.6) we have

$$\begin{aligned} Q^{(m)}_{k,\epsilon }(i-1,1)-Q^{(m)}_{k,\epsilon }(i,\tau )&=\sum _{A\in X^{(m)}_{k,\epsilon }}\big (\langle B,S'\rangle -\langle A,S\rangle \big ) \end{aligned}$$

(6.2)

$$\begin{aligned}&=\sum _{A\in X^{(m)}_{k,\epsilon }}\langle B,S'\rangle \big (1-\chi (za)\big ), \end{aligned}$$

(6.3)

where we write $A$ as

$$\begin{aligned} A=\begin{bmatrix} a&\quad v^T\\ v&\quad B \end{bmatrix} \end{aligned}$$

(6.4)

for some $a\in \mathbb {F}_q$, some $v\in \mathbb {F}_q^{m-1}$, and some $(m-1)\times (m-1)$ symmetric matrix $B$ over $\mathbb {F}_q$. The summand in (6.3) is zero for $a=0$, so assume that $a$ is nonzero. Writing

$$\begin{aligned} L=\begin{bmatrix} 1&\quad -a^{-1}v^T\\ 0&\quad I \end{bmatrix}, \end{aligned}$$

we have

$$\begin{aligned} L^TAL=\begin{bmatrix} a&\quad 0\\ 0&\quad C \end{bmatrix},\quad \text {where}\quad C=B-a^{-1}vv^T. \end{aligned}$$

Note that $L$ is nonsingular. Let $\mathcal {Q}$ and $\mathcal {N}$ be the set of squares and nonsquares of $\mathbb {F}_q^*$, respectively. As $(a,C)$ ranges over

$$\begin{aligned} \mathcal {Q} \times X^{(m-1)}_{k-1,\epsilon } \;\; \cup \;\; \mathcal {N}\times X^{(m-1)}_{k-1,-\epsilon } \end{aligned}$$

and $v$ ranges over $\mathbb {F}_q^{m-1}$, the matrix $A$, given in (6.4), ranges over all elements of $X^{(m)}_{k,\epsilon }$, except for those matrices (6.4) satisfying $a=0$. Hence, using (2.5), the sum (6.3) becomes

$$\begin{aligned} \begin{aligned}&\sum _{a\in \mathcal {Q}}\big (1-\chi (za)\big )\sum _{C\in X^{(m-1)}_{k-1,\epsilon }}\langle C,S'\rangle \sum _{v\in \mathbb {F}_q^{m-1}}\langle a^{-1}vv^T,S'\rangle \\&\qquad +\sum _{a\in \mathcal {N}}\big (1-\chi (za)\big )\sum _{C\in X^{(m-1)}_{k-1,-\epsilon }}\langle C,S'\rangle \sum _{v\in \mathbb {F}_q^{m-1}}\langle a^{-1}vv^T,S'\rangle . \end{aligned} \end{aligned}$$

(6.5)

From (2.7) and (2.6), we have

$$\begin{aligned} \sum _{C\in X^{(m-1)}_{k-1,\epsilon }}\langle C,S'\rangle =Q^{(m-1)}_{k-1,\epsilon }(i-1,1). \end{aligned}$$

(6.6)

Furthermore,

$$\begin{aligned} \sum _{v\in \mathbb {F}_q^{m-1}}\langle a^{-1}vv^T,S'\rangle&=q^{m-i}\sum _{v_1,\ldots ,v_{i-1}\in \mathbb {F}_q}\chi (a^{-1}(v_1^2+\cdots +v_{i-1}^2)) \nonumber \\&=q^{m-i}\Bigg (\sum _{v\in \mathbb {F}_q}\chi (a^{-1}v^2)\Bigg )^{i-1}. \end{aligned}$$

(6.7)

Putting $\eta (0)=0$, the summation becomes

$$\begin{aligned} \sum _{v\in \mathbb {F}_q}\chi (a^{-1}v^2)&=\sum _{y\in \mathbb {F}_q}(1+\eta (y))\chi (a^{-1}y)\\&=\sum _{y\in \mathbb {F}_q}(1+\eta (ay))\chi (y)\\&=\eta (a)\,\gamma _q, \end{aligned}$$

using $\sum _{y\in \mathbb {F}_q}\chi (y)=0$ and the definition (2.9) of the Gauss sum $\gamma _q$. Substitute into (6.7) and then (6.7) and (6.6) into (6.5) to deduce that (6.2) equals

$$\begin{aligned}&q^{m-i}\gamma _q^{i-1}\Big [Q^{(m-1)}_{k-1,\epsilon }(i-1,1)\sum _{a\in \mathcal {Q}}\big (1-\chi (za)\big )\\&\qquad \qquad -(-1)^iQ^{(m-1)}_{k-1,-\epsilon }(i-1,1)\sum _{a\in \mathcal {N}}\big (1-\chi (za)\big )\Big ]. \end{aligned}$$

To complete the proof, recall that $|\mathcal {Q}|=|\mathcal {N}|=(q-1)/2$ and observe that

$$\begin{aligned} \sum _{a\in \mathcal {Q}}\big (1-\chi (za)\big )&=\frac{q-1}{2}-\sum _{a\in \mathbb {F}_q^*}\frac{1+\eta (a)}{2}\chi (za)\\&=\frac{q}{2}-\frac{1}{2}\sum _{a\in \mathbb {F}_q^*}\eta (a)\chi (za)\\&=\frac{q}{2}-\frac{1}{2}\eta (z)\,\gamma _q \end{aligned}$$

and similarly

$$\begin{aligned} \sum _{a\in \mathcal {N}}\big (1-\chi (za)\big )&=\frac{q}{2}+\frac{1}{2}\eta (z)\,\gamma _q, \end{aligned}$$

as required. $\square$

The $Q$-numbers of $X(m,q)$ are determined by the recurrence of Lemma 6.1 together with the initial numbers $Q^{(m)}_{k,\epsilon }(0,1)$ and $Q^{(m)}_{0,1}(i,\tau )$. From (2.7) and (2.6), we find that these initial numbers satisfy

$$\begin{aligned} Q^{(m)}_{0,1}(i,\tau )&=1, \end{aligned}$$

(6.8)

$$\begin{aligned} Q^{(m)}_{k,\epsilon }(0,1)&=v^{(m)}(k,\epsilon ), \end{aligned}$$

(6.9)

where we write $v^{(m)}(i,\tau )$ for $v(i,\tau )$, the number of $m\times m$ symmetric matrices over $\mathbb {F}_q$ of rank $i$ and type $\tau$.

In order to solve the recurrence in Lemma 6.1, we shall first obtain explicit expressions for the numbers

$$\begin{aligned} S^{(m)}_k(i,\tau )&=Q^{(m)}_{k,1}(i,\tau )+Q^{(m)}_{k,-1}(i,\tau ), \end{aligned}$$

(6.10)

$$\begin{aligned} R^{(m)}_k(i,\tau )&=Q^{(m)}_{k,1}(i,\tau )-Q^{(m)}_{k,-1}(i,\tau ) \end{aligned}$$

(6.11)

in the following two lemmas. Since

$$\begin{aligned} 2Q^{(m)}_{k,\epsilon }(i,\tau )=S^{(m)}_k(i,\tau )+\epsilon \,R^{(m)}_{k}(i,\tau ) \end{aligned}$$

we then directly obtain Theorem 2.2. We shall repeatedly use the following elementary identity for the Gauss sum $\gamma _q$, defined in (2.9),

$$\begin{aligned} \gamma _q^2=\eta (-1)q \end{aligned}$$

(6.12)

(see [18], Theorem 5.12], for example).

Lemma 6.2

For $k,i\ge 1$, the numbers $S^{(m)}_k(i,\tau )$ are given by

$$\begin{aligned} S^{(m)}_{2r+1}(2s+1,\tau )&=-q^{2r}F^{(m-1)}_r(s), \end{aligned}$$

(6.13)

$$\begin{aligned} S^{(m)}_{2r}(2s+1,\tau )&=q^{2r}F^{(m-1)}_r(s), \end{aligned}$$

(6.14)

$$\begin{aligned} S^{(m)}_{2r+1}(2s,\tau )&=-q^{2r}F^{(m-1)}_r(s-1)+\tau \,\eta (-1)^sq^{m-s+2r}F^{(m-2)}_r(s-1), \end{aligned}$$

(6.15)

$$\begin{aligned} S^{(m)}_{2r}(2s,\tau )&=q^{2r}F^{(m-1)}_r(s-1)-\tau \,\eta (-1)^sq^{m-s+2r-2}F^{(m-2)}_{r-1}(s-1). \end{aligned}$$

(6.16)

Proof

Write $s=\lfloor i/2\rfloor$ and

$$\begin{aligned} n=\lfloor (m-1)/2\rfloor \quad \text {and}\quad c=q^{(m-1)(m-2)/(2n)}. \end{aligned}$$

From Lemma 6.1 we find that

$$\begin{aligned} S^{(m)}_k(i,\tau )=S^{(m)}_k(i-1,1)-(-\tau )^{i+1}\,q^{m-2s}\gamma _q^{2s}\,S^{(m-1)}_{k-1}(i-1,1). \end{aligned}$$

(6.17)

Hence, by (6.9) and (6.10),

$$\begin{aligned} S_k^{(m)}(1,\tau )=v^{(m)}(k,1)+v^{(m)}(k,-1)-q^m\big [v^{(m-1)}(k-1,1)+v^{(m-1)}(k-1,-1)\big ]. \end{aligned}$$

From Proposition 2.1, we then find that

$$\begin{aligned} S^{(m)}_{2r}(1,\tau )=-S^{(m)}_{2r+1}(1,\tau )=\frac{1}{q^r}\,\frac{(q^m-q)(q^{m}-q^2)\cdots (q^m-q^{2r})}{(q^{2r}-1)(q^{2r}-q^2)\cdots (q^{2r}-q^{2r-2})}, \end{aligned}$$

which we can write as

Apply the identities (2.11) and (2.10) to $F^{(m-1)}_r(0)$ to see that (6.13) and (6.14) hold for $s=0$. Moreover, it is easy to see from (6.1) and (6.8) that (6.14) also holds for $r=0$. Now substitute the recurrence (6.17) into itself and use (6.12) to obtain

$$\begin{aligned} S^{(m)}_k(2s+1,\tau )=S^{(m)}_k(2s-1,1)-cq^{2(n-s+1)}\,S^{(m-2)}_{k-2}(2s-1,1). \end{aligned}$$

Using (2.12), we readily verify by induction that (6.13) and (6.14) hold for all $r,s\ge 0$. The identities (6.15) and (6.16) then follow from (6.17) and (6.12). $\square$

Lemma 6.3

For $k,i\ge 1$, the numbers $R^{(m)}_k(i,\tau )$ are given by

$$\begin{aligned} R^{(m)}_{2r+1}(2s+1,\tau )&=\tau \,\eta (-1)^{r+s}\, q^{m-s+r-1}\,\gamma _q\,F^{(m-1)}_r(s), \end{aligned}$$

(6.18)

$$\begin{aligned} R^{(m)}_{2r}(2s+1,\tau )&=\eta (-1)^rq^rF^{(m)}_r(s), \end{aligned}$$

(6.19)

$$\begin{aligned} R^{(m)}_{2r+1}(2s,\tau )&=0, \end{aligned}$$

(6.20)

$$\begin{aligned} R^{(m)}_{2r}(2s,\tau )&=\eta (-1)^rq^rF^{(m)}_r(s). \end{aligned}$$

(6.21)

Proof

Write

$$\begin{aligned} n=\lfloor m/2\rfloor \quad \text {and}\quad c=q^{m(m-1)/(2n)}. \end{aligned}$$

From (6.9) and (6.11), we have

$$\begin{aligned} R^{(m)}_k(0,1)=v^{(m)}(k,1)-v^{(m)}(k,-1). \end{aligned}$$

From Proposition 2.1, we then find that

$$\begin{aligned} R^{(m)}_{2r+1}(0,1)=0 \end{aligned}$$

and

as in the proof of Lemma 6.2. Hence (6.20) and (6.21) hold for $s=0$. Moreover (6.21) trivially holds for $r=0$. Writing $s=\lfloor (i+1)/2\rfloor$, we find from Lemma 6.1 that

$$\begin{aligned} R^{(m)}_k(i,\tau )=R^{(m)}_k(i-1,1)-(-\tau )^i\,q^{m-2s+1}\gamma _q^{2s-1}\,R^{(m-1)}_{k-1}(i-1,1), \end{aligned}$$

(6.22)

which, after self-substitution, gives

$$\begin{aligned} R^{(m)}_k(2s,\delta )=R^{(m)}_k(2s-2,1)-\eta (-1)\,qc\,q^{2(n-s)}\,R^{(m-2)}_{k-2}(2s-2,1), \end{aligned}$$

using (6.12). With this recurrence, (6.20) immediately follows and (6.21) can be verified by induction, as in the proof of Lemma 6.2. The identities (6.18) and (6.19) then follow from (6.22) and (6.12). $\square$