On Linear Programming Bounds for Codes in Polynomial Metric Spaces

We describe a general approach for studying the possibilities for improvements of the best known universal linear programming bounds on the cardinality and the minimum distance of codes in a polynomial metric space $\mathcal M$ (finite or infinite). We introduce functions $P_j(\mathcal M,s)$ having the property that $P_j(\mathcal M,s)<0$ for some $j$ if and only if the universal linear programming bound (1) can be improved by linear programming. A formula for $P_j(\mathcal M,s)$ depending on the zonal spherical functions (corresponding to $\mathcal M$) and $s$ is given. Applications in different polynomial metric spaces are considered with special emphasis on the Euclidean spheres and the binary Hamming space. Methods for obtaining new bounds (when $P_j(\mathcal M,s)<0$ for some $j$) on the size of codes and the code distance are presented. An algorithm for computer calculations of $P_j(\mathcal M,s)$ is described.