  


Improved linear programming bounds for antipodal spherical codes
Kurt M. Anstreicher (kurtanstreicheruiowa.edu) Abstract: Let $S\subset[1,1)$. A finite set $C=\{x_i\}_{i=1}^M\subset\Re^n$ is called a {\em spherical Scode} 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 wellknown 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 Modify/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  