Quadratic and symmetric bilinear forms over finite fields and their association schemes
Algebraic Combinatorics, Volume 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,BX, 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.

Received: 2018-06-01
Revised: 2019-06-14
Accepted: 2019-06-21
Published online: 2020-02-12
DOI: https://doi.org/10.5802/alco.88
Classification: 05E30,  15A63,  11T71,  94B15
Keywords: Association scheme, symmetric bilinear form, quadratic form, code, distance distribution
@article{ALCO_2020__3_1_161_0,
     author = {Schmidt, Kai-Uwe},
     title = {Quadratic and symmetric bilinear forms over finite fields and their association schemes},
     journal = {Algebraic Combinatorics},
     publisher = {MathOA foundation},
     volume = {3},
     number = {1},
     year = {2020},
     pages = {161-189},
     doi = {10.5802/alco.88},
     language = {en},
     url = {alco.centre-mersenne.org/item/ALCO_2020__3_1_161_0/}
}
Schmidt, Kai-Uwe. Quadratic and symmetric bilinear forms over finite fields and their association schemes. Algebraic Combinatorics, Volume 3 (2020) no. 1, pp. 161-189. doi : 10.5802/alco.88. https://alco.centre-mersenne.org/item/ALCO_2020__3_1_161_0/

[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 1501952 | Zbl 0018.34202

[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 | Article | MR 3708518 | Zbl 1405.11134

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

[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 | Article | MR 290857 | Zbl 0211.51304

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

[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 411978 | Zbl 0353.42010

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

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

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

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

[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 | Article | MR 2413879 | Zbl 1144.05073

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

[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 1835658 | Zbl 0974.05081

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

[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 3719015 | Zbl 1420.94112

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

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

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

[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 | Article | MR 2677670 | Zbl 1232.05244

[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 | Article | MR 3369571 | Zbl 1319.05155

[22] Schmidt, Miriam Rank metric codes (2016) (Masters thesis)

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

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

[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 | Article | MR 1971743 | Zbl 1017.05108