On optimal linear codes of dimension 4

  • Nanami Bono
  • Maya Fujii
  • Tatsuya Maruta Osaka Prefecture University
Keywords: Optimal linear codes,Griesmer bound,Geometric method


In coding theory, the problem of finding the shortest linear codes for a fixed set of parameters is central. Given the dimension $k$, the minimum weight $d$, and the order $q$ of the finite field $\bF_q$ over which the code is defined, the function $n_q(k, d)$ specifies the smallest length $n$ for which an $[n, k, d]_q$ code exists. The problem of determining the values of this function is known as the problem of optimal linear codes. Using the geometric methods through projective geometry, we determine $n_q(4,d)$ for some values of $d$ by constructing new codes and by proving the nonexistence of linear codes with certain parameters.


S. Ball, Table of bounds on three dimensional linear codes or (n; r)-arcs in PG(2; q), available at https://web.mat.upc.edu/people/simeon.michael.ball/codebounds.html.

A. Betten, E. J. Cheon, S. J. Kim, T. Maruta, The classification of (42; 6)8 arcs, Adv. Math. Commun. 5 (2011) 209–223.

I. Bouyukliev, Y. Kageyama, T. Maruta, On the minimum length of linear codes over F5, Discrete Math. 338 (2015) 938–953.

A. E. Brouwer, M. van Eupen, The correspondence between projective codes and 2-weight codes, Des. Codes Cryptogr. 11 (1997) 261–266.

M. van Eupen, R. Hill, An optimal ternary [69; 5; 45]3 codes and related codes, Des. Codes Cryptogr. 4 (1994) 271–282.

M. Fujii, Nonexistence of some Griesmer codes of dimension 4, Master Thesis, Osaka Prefecture University (2019).

M. Grassl, "Bounds on the minimum distance of linear codes and quantum codes." Online available at http://www.codetables.de.

J. H. Griesmer, A bound for error-correcting codes, IBM J. Res. Develop. 4 (1960) 532–542.

N. Hamada, A characterization of some [n; k; d; q]-codes meeting the Griesmer bound using a minihyper in a finite projective geometry, Discrete Math., 116 (1993) 229–268.

R. Hill, Optimal linear codes, In: C. Mitchell(Ed.), Cryptography and Coding II, Oxford Univ. Press, Oxford (1992) 75–104.

R. Hill, E. Kolev, A survey of recent results on optimal linear codes, In: Combinatorial Designs and their Applications, F.C. Holroyd et al. Ed., Chapman and Hall/CRC Press Research Notes in Mathematics, CRC Press. Boca Raton (1999) 127–152.

J. W. P. Hirschfeld, Finite Projective Spaces of Three Dimensions, Clarendon Press, Oxford (1985).

J. W. P. Hirschfeld, Projective Geometries over Finite Fields, Clarendon Press, Oxford, second edition (1998).

C. Jones, A. Matney, H. Ward, Optimal four-dimensional codes over GF(8), Electron. J. Combin. 13 (2006) #R43, .

Y. Kageyama, T. Maruta, On the geometric constructions of optimal linear codes, Des. Codes Cryptogr., 81 (2016) 469–480.

R. Kanazawa, T. Maruta, On optimal linear codes over F8, Electronic J. Combin., 18(1) (2011) #P34misc

K. Kumegawa, T. Okazaki, T. Maruta, On the minimum length of linear codes over the field of 9 elements, Electron. J. Combin. 24(1) (2017) #P1.50.

K. Kumegawa, T. Maruta, Nonexistence of some Griesmer codes over Fq, Discrete Math. 339 (2016) 515–521.

K. Kumegawa, T. Maruta, Non-existence of some 4-dimensional Griesmer codes over finite fields, J. Algebra Comb. Discrete Struct. Appl. 5 (2018) 101–116.

I. Landjev, L. Storme, A study of (x(q + 1); x; 2; q)-minihypers, Des. Codes Cryptogr. 54 (2010) 135–147.

T. Maruta, On the minimum length of q-ary linear codes of dimension four, Discrete Math., 208/209 (1999) 427–435.

T. Maruta, On the nonexistence of q-ary linear codes of dimension five, Des. Codes Cryptogr. 22 (2001) 165–177.

T. Maruta, A new extension theorem for linear codes, Finite Fields Appl. 10 (2004) 674–685.

T. Maruta, Optimal 4-dimensional linear codes over F8, Proceedings of 13th International Workshop on Algebraic and Combinatorial Coding Theory (ACCT 2012), Pomorie, Bulgaria (2012) 257–262.

T. Maruta, Construction of optimal linear codes by geometric puncturing, Serdica J. Computing 7 (2013) 73–80.

T. Maruta, Griesmer bound for linear codes over finite fields, available at http://mars39.lomo.jp/opu/griesmer.htm.

T. Maruta, Y. Oya, On optimal ternary linear codes of dimension 6, Adv. Math. Commun. 5 (2011) 505–520.

T. Maruta, M. Shinohara, M. Takenaka, Constructing linear codes from some orbits of projectivities,Discrete Math. 308 (2008) 832–841.

T. Maruta, T. Tanaka, H. Kanda, Some generalizations of extension theorems for linear codes over finite fields, Australas. J. Combin. 60 (2014) 150–157.

T. Maruta, Y. Yoshida, A generalized extension theorem for linear codes, Des. Codes Cryptogr. 62 (2012) 121–130.

M. Takenaka, K. Okamoto, T. Maruta, On optimal non-projective ternary linear codes, Discrete Math. 308 (2008) 842–854.

Y. Yoshida, T. Maruta, An extension theorem for [n; k; d]q codes with gcd(d; q) = 2, Australas. J. Combin. 48 (2010) 117–131.