Improved linear programming bounds for antipodal spherical codes

Kurt M. Anstreicher (kurt-anstreicheruiowa.edu)

Abstract: Let $S\subset[-1,1)$. A finite set $C=\{x_i\}_{i=1}^M\subset\Re^n$ is called a {\em spherical S-code} if $||x_i||=1$ for each $i$, and $x_i^T x_j\in S$, $i\ne j$. For $S=[-1,.5]$ maximizing $M=|C|$ is commonly referred to as the {\em kissing number} problem. A well-known technique based on harmonic analysis and linear programming can be used to bound $M$. We consider a modification of the bounding procedure that is applicable to {\em antipodal} codes; that is, codes where $x\in C\implies -x\in C$. Such codes correspond to packings of lines in the unit sphere, and include all codes obtained as the collection of minimal vectors in a lattice. We obtain nontrivial improvements in upper bounds for kissing numbers attainable by antipodal codes in dimensions up to $n=24$. We also show that for $n=4$, 6 and 7 the antipodal codes with maximal kissing numbers are essentially unique, and correspond to the minimal vectors in the laminated lattices $\Lambda_n$.

Keywords: Spherical codes, kissing problem, antipodal codes, line packing, linear programming bounds

Category 1: Applications -- Science and Engineering (Basic Sciences Applications )

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: Working paper, Dept. of Management Sciences, University of Iowa, Iowa City, IA 52242, December 2000

Download: [Postscript]

Entry Submitted: 01/03/2001
Entry Accepted: 01/03/2001
Entry Last Modified: 01/03/2001

Modify/Update this entry