Semidefinite programming bounds for Lee codes

Abstract

For $q,n,d\in \mathbb{N}$, let $A_q^L(n,d)$ denote the maximum cardinality of a code $C\subseteq {\mathbb{Z}}_q^n$ with minimum Lee distance at least $d$, where ${\mathbb{Z}}_q$ 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 $A_q^L(n,d)$. The technique also yields an upper bound on the independent set number of the $n$-th strong product power of the circular graph $C_{d,q}$, which number is related to the Shannon capacity of $C_{d,q}$. Here $C_{d,q}$ is the graph with vertex set ${\mathbb{Z}}_q$, 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$.

14 pages. The text of the section "Preliminaries on representation theory" (Section 2, except for subsection 2.2) is the same as Section 2 of arXiv:1703.05171 (which contains similar preliminaries as in arXiv:1602.02531). This is mentioned in the paper