This chapter of Handbook of Coding Theory deals with packing and some related problems for a class of polynomial metric spaces X including finite and compact infinite ones, in particular, Hamming space, Johnson space, the unit Euclidean sphere, and real, complex and quaternionic projective spaces. We are interested in bounds on parameters of finite subsets (codes) C of X which are universal in the following sense. First the bounds are valid for any code C ⊆ X as distinguished from the existential bounds valid only for some codes. Moreover they are valid for any polynomial metric space X, in particular, for the above mentioned metric spaces. The method considered for obtaining universal bounds is based on a description of all nonnegative definite functions F(x,y) on X which depend only on the distance d(x,y) using a system of orthogonal polynomials. Every such function gives a universal upper bound on the size |C| of a code C ⊆ X with minimal distance d(C) between its distinct points. The problem is to choose such a nonnegative definite function which gives rise to the best bound.

polynomial spaces, code, design, universal bounds, linear programming, orthogonal polynomials.

Mathematical problems and theory of numerical methods