- 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/2001Entry Accepted: 01/03/2001Entry Last Modified: 01/03/2001Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.