Optimization Online


Improved linear programming bounds for antipodal spherical codes

Kurt M. Anstreicher (kurt-anstreicher***at***uiowa.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society