Constructive spherical codes near the Shannon bound (Q1934239): Difference between revisions

Let \(X\) be a spherical code of \(\mathbb{R}^n\), i.e., a finite set of points of the unit sphere in a Euclidean space of finite dimension \(n\). If \(\rho\) denotes the Euclidean squared minimum distance of this spherical code, its binary rate is defined by \[ R(\rho):= \limsup{\log_2(|X|)\over n}. \] The lower bound \(R(\rho)\geq R_S(\rho):= 1- (1/2)\log_2(\rho(4-\rho))\) was given by Chabauty in 1953 and Shannon in 1959 (cf. [\textit{C. Chabauty}, C. R. Acad. Sci., Paris 236, 1462--1464 (1953; Zbl 0050.16605); \textit{C. E. Shannon}, ``Probability of error for optimal codes in a Gaussian channel'', Bell. Syst. Tech. J. 38, 611--656 (1959); \textit{G. Lachaud} and \textit{J. Stern}, IEEE Trans. Inf. Theory 40, No. 4, 1140--1146 (1994; Zbl 0813.94024)]). The lower bound on the rate \(R_*(\rho)\) of polynomial time constructible spherical codes \[ R_*(\rho)\geq 0.5R_S(\rho) \] was given by Lachaud and Stern [loc. cit.]. In the present paper the authors give the following lower bound based on nonconstructive lattice packings: \[ R(\rho)\geq R_L(\rho):= -(1/2)\log_2(\rho). \] By direct substitution the authors find that \(R_S(\rho)\geq R_L(\rho)\) for all \(0\leq\rho\leq 4\), and for small \(\rho\) the two curves are very close to each other: \[ R(\rho)- R_L(\rho)= O(\rho^2). \] The authors show that using finite alphabet codes for constructing finite packings is as efficient as using truncation of dense infinite sphere packings. The main result of this work is a lower bound \(R_*(\rho)\geq 0.98R_S(\rho)\) for some very small values of \(\rho\) in the range \(0< \rho\leq 1\). This outperforms the Lachaud-Stern bound almost by a factor of 2.