A conjecture on the minimum length of binary linear codes
DOI:
https://doi.org/10.55630/mem.2026.55.423-432Keywords:
Griesmer bound, optimal code, divisible codeAbstract
We give a new conjecture on D_{2,k}, where D_{q,k} denotes the largest d such that a linear code of dimension k with minimum weight d meeting the Griesmer bound does not exist. We also prove that D_{2,11} = 1632, which yields that our conjecture is valid for dimensions k <= 11.
References
B. I. BELOV, V. N. LOGACHEV, and V. P. SANDIMIROV. Construction of a class of linear binary codes achieving the Varshamov–Griesmer bound. Problems of Information Transmission, 10(3):211–217, 1974.
I. BOUYUKLIEV, D. B. JAFFE, and V. VAVREK. The smallest length of eight-dimensional binary linear codes with prescribed minimum distance. IEEE Transactions on Information Theory, 46:981–985, 2002.
A. E. BROUWER and M. van EUPEN. The correspondence between projective codes and 2-weight codes. Designs, Codes and Cryptography, 11:261–266, 1997.
S. M. DODUNEKOV. Optimal Linear Codes. PhD thesis, Bulgarian Academy of Sciences, Sofia, 1985.
J. H. GRIESMER. A bound for error-correcting codes. IBM Journal of Research and Development, 4:532–542, 1960.
R. HILL. Optimal linear codes. In CHRIS MITCHELL, editor, Cryptography and Coding II, pages 75–104. Oxford University Press, Oxford, 1992.
R. HILL and E. KOLEV. A survey of recent results on optimal linear codes. In F. C. HOLROYD, K. A. S. QUINN, C. ROWLEY, and B. S. WEBB, editors, Combinatorial Designs and their Applications, Research Notes in Mathematics, pages 127–152. Chapman and Hall/CRC, Boca Raton, 1999.
W. C. HUFFMAN and V. PLESS. Fundamentals of Error-Correcting Codes. Cambridge University Press, Cambridge, 2003.
Y. INOUE and T. MARUTA. Construction of new Griesmer codes of dimension 5. Finite Fields and Their Applications, 55:231–237, 2019.
A. KATO, T. MARUTA, and K. NOMURA. On the construction of optimal linear codes of dimension four. Bulletin of the Korean Mathematical Society, 60:1237–1252, 2023.
D. KAWABATA, T. MARUTA, and K. YASUFUKU. A conjecture on the minimum length of linear codes over finite fields. Designs, Codes and Cryptography, 93:5039–5054, 2025.
T. KÖRNER and S. KURZ. Lengths of divisible codes with restricted column multiplicities. Advances in Mathematics of Communications, 18(2):505–534, 2024.
T. MARUTA. On the nonexistence of q-ary linear codes of dimension five. Designs, Codes and Cryptography, 22:165–177, 2001.
T. MARUTA. Construction of optimal linear codes by geometric puncturing. Serdica Journal of Computing, 7:73–80, 2013.
M. TAKENAKA, K. OKAMOTO, and T. MARUTA. On optimal non-projective ternary linear codes. Discrete Mathematics, 308:842–854, 2008.
H. van TILBORG. The smallest length of binary 7-dimensional linear codes with prescribed minimum distance. Discrete Mathematics, 33:197–207, 1981.
H. N. WARD. Divisibility of codes meeting the Griesmer bound. Journal of Combinatorial Theory, Series A, 83:79–93, 1998.
