Random Packings and Coverings of the Unit n-Sphere

A problem in coding theory for the Gaussian channel is the determination of Mp{n, 6), the maximum number of points which may be placed on the surface of a unit ?i-sphere such that the spherical caps with centers at these points and half angle 6 are disjoint (the "packing" problem). This quantity, though unknown, has been estimated by upper and lower bounds.5 In this paper, we give a proof of the known lower bound by a "random coding'' argument. It is felt that this new method is of interest in itself. A related problem is the "covering" problem, the determination of M0{n, 6), the minimum number of caps of half angle 6 required to cover the surface of a unit n-sphere. This problem is of interest when one wants to quantize an ??-dimensional Gaussian vector with inde2111 2112 T H E BELL SYSTEM TECHNICAL JOURNAL, NOVEMBER 1007 pendent components (which with very high probability lies near the surface of an ?t-sphere). In this paper, Mc{n, 0) is estimated with upper and lower bounds which are "exponentially" tight. The upper bound is also proved by a "random coding" argument. The random coding arguments owe much to Shannon.3-4 The random covering theorem in particular is similar to his approximation theorem in the latter reference. R. Graham has called my attention to the work of Rogers, 1,2 who has considered the problem of covering a large n-dimensional cube with spheres of a unit radius. Rogers' methods and result parallel those given here. Let x, y with and without subscripts denote points on S,, , the surface of a unit sphere in n-dimensional Euclidean space.