Quadratic and symmetric bilinear forms over finite fields and their association schemes

Schmidt, Kai-Uwe

Algebraic Combinatorics, Tome 3 (2020) no. 1, pp. 161-189.

Let $𝒬(m,q)$ and $𝒮(m,q)$ be the sets of quadratic forms and symmetric bilinear forms on an $m$-dimensional vector space over ${𝔽}_q$, respectively. The orbits of $𝒬(m,q)$ and $𝒮(m,q)$ under a natural group action induce two translation association schemes, which are known to be dual to each other. We give explicit expressions for the eigenvalues of these association schemes in terms of linear combinations of generalised Krawtchouk polynomials, generalising earlier results for odd $q$ to the more difficult case when $q$ is even. We then study $d$-codes in these schemes, namely subsets $X$ of $𝒬(m,q)$ or $𝒮(m,q)$ with the property that, for all distinct $A,B\in X$, the rank of $A-B$ is at least $d$. We prove tight bounds on the size of $d$-codes and show that, when these bounds hold with equality, the inner distributions of the subsets are often uniquely determined by their parameters. We also discuss connections to classical error-correcting codes and show how the Hamming distance distribution of large classes of codes over ${𝔽}_q$ can be determined from the results of this paper.

Classification : 05E30, 15A63, 11T71, 94B15
Mots-clés : Association scheme, symmetric bilinear form, quadratic form, code, distance distribution

[1] Albert, Adrian A. Symmetric and alternate matrices in an arbitrary field. I, Trans. Am. Math. Soc., Volume 43 (1938) no. 3, pp. 386-436 | MR | Zbl

[2] Bachoc, Christine; Serra, Oriol; Zémor, Gilles An analogue of Vosper’s theorem for extension fields, Math. Proc. Camb. Philos. Soc., Volume 163 (2017) no. 3, pp. 423-452 | DOI | MR | Zbl

[3] Bannai, Eiichi; Ito, Tatsuro Algebraic combinatorics I: Association schemes, The Benjamin/Cummings Publishing Co., Inc., Menlo Park, CA, 1984 | Zbl

[4] Berlekamp, Elwyn R. The weight enumerators for certain subcodes of the second order binary Reed–Muller codes, Inf. Control, Volume 17 (1970), pp. 485-500 | DOI | MR | Zbl

[5] Delsarte, Philippe An algebraic approach to the association schemes of coding theory, Philips Res. Rep. Suppl. (1973) no. 10, p. vi+97 | MR | Zbl

[6] Delsarte, Philippe Properties and applications of the recurrence $F(i+1,k+1,n+1)=q^{k+1}F(i,k+1,n)-q^{k}F(i,k,n)$, SIAM J. Appl. Math., Volume 31 (1976) no. 2, pp. 262-270 | MR | Zbl

[7] Delsarte, Philippe; Goethals, Jean-Marie Alternating Bilinear Forms over GF$\left(q\right)$, J. Comb. Theory, Ser. A, Volume 19 (1975) no. 1, pp. 26-50 | DOI | MR | Zbl

[8] Delsarte, Philippe; Levenshtein, Vladimir I. Association Schemes and Coding Theory, IEEE Trans. Inf. Theory, Volume 44 (1998) no. 6, pp. 2477-2504 | DOI | MR | Zbl

[9] Dickson, Leonard Eugene Linear groups: With an exposition of the Galois field theory, Dover Publications, Inc., New York, 1958 | Zbl

[10] Egawa, Yoshimi Association schemes of quadratic forms, J. Comb. Theory, Ser. A, Volume 38 (1985) no. 1, pp. 1-14 | DOI | MR | Zbl

[11] Feng, Rongquan; Wang, Yangxian; Ma, Changli; Ma, Jianmin Eigenvalues of association schemes of quadratic forms, Discrete Math., Volume 308 (2008) no. 14, pp. 3023-3047 | DOI | MR | Zbl

[12] Grassl, Markus Bounds on the minimum distance of linear codes and quantum codes, Online available at http://www.codetables.de, 2007 | Zbl

[13] Hou, Xiang-dong The eigenmatrix of the linear association scheme on $R(2,m)$, Discrete Math., Volume 237 (2001) no. 1-3, pp. 163-184 | MR | Zbl

[14] Kasami, Tadao The weight enumerators for several classes of subcodes of the $2$nd order binary Reed-Muller codes, Inf. Control, Volume 18 (1971), pp. 369-394 | DOI | MR | Zbl

[15] Li, Shuxing The minimum distance of some narrow-sense primitive BCH codes, SIAM J. Discrete Math., Volume 31 (2017) no. 4, pp. 2530-2569 | MR | Zbl

[16] Lint, J. H. van; Wilson, R. M. A course in combinatorics, Cambridge University Press, Cambridge, 2001 | Zbl

[17] MacWilliams, F. Jessie Orthogonal matrices over finite fields, Am. Math. Mon., Volume 76 (1969), pp. 152-164 | DOI | MR

[18] MacWilliams, F. Jessie; Sloane, Neil J. A. The Theory of Error-Correcting Codes, Amsterdam, The Netherlands: North Holland, 1977 | Zbl

[19] McEliece, Robert Quadratic forms over finite fields and second-order Reed-Muller codes, JPL Space Programs Summary 37-58, Volume III (1969), pp. 28-33

[20] Schmidt, Kai-Uwe Symmetric bilinear forms over finite fields of even characteristic, J. Comb. Theory, Ser. A, Volume 117 (2010) no. 8, pp. 1011-1026 | DOI | MR | Zbl

[21] Schmidt, Kai-Uwe Symmetric bilinear forms over finite fields with applications to coding theory, J. Algebr. Comb., Volume 42 (2015) no. 2, pp. 635-670 | DOI | MR | Zbl

[22] Schmidt, Miriam Rank metric codes, Masters thesis, University of Bayreuth (Germany) (2016)

[23] Stanton, Dennis Some $q$-Krawtchouk polynomials on Chevalley groups, Am. J. Math., Volume 102 (1980) no. 4, pp. 625-662 | DOI | MR | Zbl

[24] Stanton, Dennis A partially ordered set and $q$-Krawtchouk polynomials, J. Comb. Theory, Ser. A, Volume 30 (1981) no. 3, pp. 276-284 | DOI | MR | Zbl

[25] Wang, Yangxian; Wang, Chunsen; Ma, Changli; Ma, Jianmin Association schemes of quadratic forms and symmetric bilinear forms, J. Algebr. Comb., Volume 17 (2003) no. 2, pp. 149-161 | DOI | MR | Zbl