On the Failing Cases of the Johnson Bound for Error-Correcting Codes

Abstract

A central problem in coding theory is to determine $A_q(n,2e+1)$, the maximal cardinality of a $q$-ary code of length $n$ correcting up to $e$ errors. When $e$ is fixed and $n$ is large, the best upper bound for $A(n,2e+1)$ (the binary case) is the well-known Johnson bound from 1962. This however simply reduces to the sphere-packing bound if a Steiner system $S(e+1,2e+1,n)$ exists. Despite the fact that no such system is known whenever $e\geq 5$, they possibly exist for a set of values for $n$ with positive density. Therefore in these cases no non-trivial numerical upper bounds for $A(n,2e+1)$ are known.

In this paper the author demonstrates a technique for upper-bounding $A_q(n,2e+1)$, which closes this gap in coding theory. The author extends his earlier work on the system of linear inequalities satisfied by the number of elements of certain codes lying in $k$-dimensional subspaces of the Hamming Space. The method suffices to give the first proof, that the difference between the sphere-packing bound and $A_q(n,2e+1)$ approaches infinity with increasing $n$ whenever $q$ and $e\geq 2$ are fixed. A similar result holds for $K_q(n,R)$, the minimal cardinality of a $q$-ary code of length $n$ and covering radius $R$. Moreover the author presents a new bound for $A(n,3)$ giving for instance $A(19,3)\leq 26168$.