Semidefinite programming bounds for Lee codes

For q, n, d ∈N, let ALq(n,d) denote the maximum cardinality of a code C ⊆ Znq with minimum Lee distance at least d, where Zq denotes the cyclic group of order q. We consider a semidefinite programming bound based on triples of codewords, which bound can be computed efficiently using symmetry reductions, resulting in several new upper bounds on ALq(n,d). The technique also yields an upper bound on the independent set number of the nth strong product power of the circular graph Cd,q, which number is related to the Shannon capacity of Cd,q. Here Cd,q is the graph with vertex set Zq, in which two vertices are adjacent if and only if their distance (mod q) is strictly less than d. The new bound does not seem to improve significantly over the bound obtained from Lovász theta-function, except for very small n.

• View at Publisher

Full Text ( Final Version , 535kb )

See Also
techReport Semidefinite programming bounds for Lee codes S.C. Polak (Sven)