On the failing cases of the Johnson bound for error-correcting codes (Q1010772)

Summary: 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 [\textit{S. M. Johnson}, IRE Trans. Inform. Theory IT-8, 203--207 (1962; Zbl 0102.34602)]. 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\).