On the minimum average distance of binary codes: Linear programming approach (Q5939230)

\textit{R. Ahlswede} and \textit{G. Katona} [Discrete Math. 17, 1-22 (1977; Zbl 0368.05001)] posed the following problem: For given \(n\) and \(M\) with \(1 \leq M \leq 2^n\), determine the minimum average Hamming distance \(\beta (n,M)\) of binary codes with length \(n\) and size \(M\). In graph-theoretic terms, this is the minimum average distance between \(M\) vertices of an \(n\)-cube. In the current paper, linear programming is used to obtain new lower bounds, which are used to determine \(\beta (n,M)\) for several families of parameters, including \(M \in \{2^{n-2}, 2^{n-2}\pm 1, 2^{n-1}\pm 2,2^{n-1}+2^{n-2}, 2^{n-1}+2^{n-2}\pm 1,2^n-2\}\). An upper bound is obtained as well, based on combining codes of size \(2^{k_i}\) and length \(k_i\) (that is, cubes), where \(M = 2^{k_1}+2^{k_2}+\cdots\) and \(k_1 > k_2 > \cdots\). This gives optimal codes -- that is, codes attaining \(\beta (n,M)\) -- in many cases but not always, since if \(M \leq n+1\) and \(M\) is large enough, then one can take the all-zero word and \(M-1\) words of weight 1 to get better codes.