\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \newtheorem{definition}{Definition} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf The Number of Inequivalent $(2R+3,7)R$ Optimal Covering Codes } \vskip 1cm \large Gerzson K\'eri\footnote{Supported in part by the Hungarian National Research Fund, OTKA, Grant No.\ T043276.}\\ Computer and Automation Research Institute\\ Hungarian Academy of Sciences\\ Kende u.\ 13--17 \\ H-1111 Budapest \\ Hungary\\ \href{mailto:keri@sztaki.hu}{\tt keri@sztaki.hu} \vskip .3cm Patric R. J. \"Osterg\aa rd\footnote{Supported in part by the Academy of Finland, Grants No.\ 107493 and 110196.}\\ Department of Electrical and Communications Engineering\\ Helsinki University of Technology\\ P.O.\ Box 3000\\ 02015 TKK \\ Finland\\ \href{mailto:patric.ostergard@tkk.fi}{\tt patric.ostergard@tkk.fi} \\ \end{center} \vskip .2 in \begin{abstract} Let $(n,M)R$ denote any binary code with length $n$, cardinality $M$ and covering radius $R$. The classification of $(2R+3,7)R$ codes is settled for any $R=1,2,\dots$, and a characterization of these (optimal) codes is obtained. It is shown that, for $R=1,2,\dots$, the numbers of inequivalent $(2R+3,7)R$ codes form the sequence $1,3,8,17,33,\dots$ identified as A002625 in the \emph{Encyclopedia of Integer Sequences} and given by the coefficients in the expansion of $1/({(1-x)^3(1-x^2)^2(1-x^3)})$. \end{abstract} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}{Proposition}[section] \newtheorem{corollary}{Corollary}[section] \newtheorem{lemma}{Lemma}[section] \newcommand{\wt}{\mbox{wt}} \section{Introduction} Let $(n,M)R$ denote a binary code of length $n$, cardinality $M$ and covering radius $R$. Throughout the paper, unless otherwise mentioned, we assume that $R$ is an arbitrary positive integer. We assume familiarity with basic concepts of coding theory; the Hamming weight of a word $x$ is denoted by $\wt(x)$ and the Hamming distance between two words $x,y$ is denoted by $d(x,y)$. For an introduction to coding theory in general and covering codes in particular, see \cite{MS} and \cite{CHLL:Book}, respectively. We shall here focus on $(2R+3,7)R$ codes, that is, 7-word binary codes in the Hamming space $Z_2^{2R+3}$ with covering radius $R$. Cohen et al.\ \cite{CLS:Further} proved that $(2R+3,7)R$ codes exist and that $(2R+3,6)R$ codes do not exist. Denoting the minimum number of codewords in any binary code $C$ of length $n$ and covering radius $R$ by $K(n,R)$, this means that $K(2R+3,R)=7$ for all $R \geq 1$. Our goal is to settle the classification of $(2R+3,7)R$ codes and characterize the optimal codes for any $R \geq 1$, thereby providing a solution to \mbox{\cite[Research Problem 7.31]{Kaski:Book}}. Two binary codes are \emph{equivalent} if one can be obtained from the other by a permutation of the coordinates followed by a transposition of the coordinate values in some of the coordinates. It will be shown that, for $R=1,2,\dots$, the number of equivalence classes of $(2R+3,7)R$ codes coincides with the coefficients of $x^{R-1}$ in the expansion of \[ \frac{1}{(1-x)^3(1-x^2)^2(1-x^3)}. \] This integer sequence, starting with $1,3,8,17,33,58,97,153,233,\dots$, is sequence \seqnum{A002625} in the \emph{Encyclopedia of Integer Sequences}. \section{Some Old Results with an Extension} \label{old} We first review some partial results for the classification of \mbox{$(2R+3,7)R$} codes. In fact, very few classification results are known for optimal binary covering codes in general; the following list \cite[Sect.~7.2.6]{Kaski:Book} summarizes the sets of parameters that have been settled: (a) $M<7$ and arbitrary $n$; (b) $M=7$ and $1 \leq R \leq 3$; and (c) the six sporadic cases $K(6,1)=12$, $K(7,1)=16$, $K(8,1)=32$, $K(8,2)=12$, $K(9,2)=16$ and $K(23,3)=4096$. The optimal $(5,7)1$, $(7,7)2$ and $(9,7)3$ codes have been classified by Stanton and Kalbfleisch \cite{SK}; \"Osterg{\aa}rd and Weakley \cite{OW} (with misprinted codes; the codes are reproduced in correct form by Bertolo, \"Osterg{\aa}rd and Weakley \cite{BOW}); and Kaski and \"Osterg{\aa}rd \cite{Kaski:Book}, respectively. The main result of the current paper relies on the classifications of $(5,7)1$ and $(7,7)2$ codes; the numbers of such codes are 1 and 3, respectively. We shall now describe the structure of the $(5,7)1$ and $(7,7)2$ codes. For this purpose we consider the following $(1,7)0$ codes $C_i$ (the codewords are labelled, so we present the codes as tuples rather than multisets of words): \pagebreak \begin{equation}\label{CiDi} \begin{array}{ccccccc} C_1&=&( 0, 0, 0, 1, 1, 1, 1),\\ C_2&=&( 0, 0, 1, 0, 1, 1, 1),\\ C_3&=&( 0, 1, 0, 0, 1, 1, 1),\\ C_4&=&( 0, 1, 1, 1, 0, 0, 1),\\ C_5&=&( 0, 1, 1, 1, 0, 1, 0),\\ C_6&=&( 0, 1, 1, 1, 1, 0, 0). \end{array} \end{equation} Using the notation $|.|.|$ for coordinate-wise concatenation of codes or words, the optimal $(5,7)1$ and $(7,7)2$ codes can be described as follows, up to equivalence. \begin{theorem}\label{constr-1-2} (a) The unique $(5,7)1$ code is $C=|C_1|C_2|C_3|C_4|C_5|$.\\ (b) The three $(7,7)2$ codes are $|C|C_1|C_1|$, $|C|C_4|C_4|$ and $|C|C_6|C_6|$. \end{theorem} An inspection of the equivalence classes of the three $(7,7)2$ codes gives a result that is needed later. \begin{corollary} \label{cor} \emph{All} $(7,7)2$ codes of the form $|C_1|C_2|C_3|C_4|C_5|D|$ that contain the all-zero word are obtained by letting $D = |C_i|C_j|$ with $i = j$ or $i = 6$ or $j = 6$. \end{corollary} The codes discussed so far may also be presented using the following alternative notation, which disregards the order of the coordinates. Let $C(n_1,n_2,n_3,n_4,n_5,n_6)$ denote the code that is the concatenation of $C_1$ taken $n_1$ times, $C_2$ taken $n_2$ times, and so on. Note that different presentations may lead to equivalent codes. The automorphism group of $|C_1|C_2|C_3|C_4|C_5|C_6|$ is generated by the following permutations of coordinates: $(1\ 2)$, $(1\ 2\ 3)$, $(4\ 5)$, $(4\ 5\ 6)$ and $(1\ 4)(2\ 5)(3\ 6)$. These permutations acting on the indices $n_i$ of $C(n_1,n_2,n_3,n_4,n_5,n_6)$ then give equivalent codes. This observation will be used later in the proof of Theorem \ref{correspond}. For example, the codes in Theorem \ref{constr-1-2} can be presented as \begin{eqnarray*} C& \equiv &C(1,1,1,1,1,0),\\ |C|C_1|C_1|& \equiv &C(3,1,1,1,1,0),\\ |C|C_4|C_4|& \equiv &C(1,1,1,3,1,0),\\ |C|C_6|C_6|& \equiv &C(1,1,1,1,1,2). \end{eqnarray*} Observe that for these codes exactly five of the values of $n_i$ are odd, and their covering radius is $(\sum_{i=1}^6 n_i -3)/2$. In fact, these examples are covered by the following general result. \begin{theorem}\label{suff-theor} Let $n=\sum_{i=1}^6 n_i$ be an odd integer where $n_1,n_2,n_3,n_4,n_5,n_6$ are non-negative integers. Then, the covering radius of $C(n_1,n_2,n_3,n_4,n_5,n_6)$ is $(n-3)/2$ if and only if exactly one of $n_1,n_2,n_3,n_4,n_5,n_6$ is even. \end{theorem} \begin{proof} Let us assume first that exactly one of the $n_i$s is even. Then, it can be assumed that $n_1,n_2,n_3,n_4,n_5$ are odd and $n_6$ is even, by symmetry. Let $x = |x_1|x_2|x_3|x_4|x_5|x_6|$ be any word in the binary Hamming space $Z_2^n$ where $x_i \in Z_2^{n_i}$ and $x$ is partitioned according to the structure of $C(n_1,n_2,n_3,n_4,n_5,n_6)$, the $i$th codeword of which we denote by $c_i$. Let $w_i$ be the weight of $x_i$. Then we have \[ \begin{array}{l} d(x,c_1)=w_1+w_2+w_3+w_4+w_5+w_6,\\ d(x,c_2)=w_1+w_2+(n_3-w_3)+(n_4-w_4)+(n_5-w_5)+(n_6-w_6),\\ d(x,c_3)=w_1+(n_2-w_2)+w_3+(n_4-w_4)+(n_5-w_5)+(n_6-w_6),\\ d(x,c_4)=(n_1-w_1)+w_2+w_3+(n_4-w_4)+(n_5-w_5)+(n_6-w_6),\\ d(x,c_5)=(n_1-w_1)+(n_2-w_2)+(n_3-w_3)+w_4+w_5+(n_6-w_6),\\ d(x,c_6)=(n_1-w_1)+(n_2-w_2)+(n_3-w_3)+w_4+(n_5-w_5)+w_6,\\ d(x,c_7)=(n_1-w_1)+(n_2-w_2)+(n_3-w_3)+(n_4-w_4)+w_5+w_6, \end{array} \] and consequently \begin{equation} \label{sum} d(x,C)\leq \frac{2d(x,c_1)+\sum_{i=2}^7 d(x,c_i)}{8}= \frac{4\sum_{i=1}^6 n_i}{8}=n/2. \end{equation} Assume that $d(x,C) > (n-3)/2$. Then $d(x,C) = (n-1)/2$ (since $n$ is odd and $d(x,C)\leq n/2$). As $\wt(c_1)$, $\wt(c_6)$, $\wt(c_7)$ have the same parity and $\wt(c_2)$, $\wt(c_3)$, $\wt(c_4)$, $\wt(c_5)$ have the same parity---this can be seen by looking at the parities of $n_i$---consequently also $d(x,c_1)$, $d(x,c_6)$, $d(x,c_7)$ have the same parity and $d(x,c_2)$, $d(x,c_3)$, $d(x,c_4)$, $d(x,c_5)$ have the same parity. The sum of the eight distances $d(x,c_1)$ (taken twice), $d(x,c_2)$, $d(x,c_3)$, \ldots, $d(x,c_7)$ is $4n$, cf.\ (\ref{sum}), and each of these is at least $(n-1)/2$, so we get that exactly four of these must be $(n-1)/2$ and the other four must be $(n+1)/2$, from which it follows that $d(x,c_1)=d(x,c_6)=d(x,c_7)$ and $d(x,c_2)=d(x,c_3)=d(x,c_4)=d(x,c_5)$. Then \begin{eqnarray*} 3n & = & d(x,c_1)+2d(x,c_4)+d(x,c_5)+d(x,c_6)+d(x,c_7)\\ & = & 5n_1-4w_1+3n_2+3n_3+3n_4+3n_5+3n_6\\ & = & 3n + (2n_1-4w_1), \end{eqnarray*} so $2n_1-4w_1=0$ and thereby $w_1 = n_1/2$, which is not possible since $n_1$ is odd. If $w_i=\left\lceil\frac{n_i}{2}\right\rceil$ for $i=1,2,\dots,6$, then $d(x,C) = (n-3)/2$, so the covering radius is exactly $(n-3)/2$. To prove the sufficiency, suppose that the number of even $n_i$s is greater than 1, that is, 3 or 5. We may assume that either $n_1$, $n_2$, $n_3$; or $n_1$, $n_2$, $n_4$; or $n_1$, $n_2$, $n_3$, $n_4$, $n_5$ are even and the remaining $n_i$s are odd, again by symmetry. In all cases, let $w_i=\left\lfloor\frac{n_i}{2}\right\rfloor$ for $i=1,2,3,5$ and $w_i=\left\lceil\frac{n_i}{2}\right\rceil$ for $i=4,6$, where $w_i$ is again the weight of $x_i$ in a partitioned word $x = |x_1|x_2|x_3|x_4|x_5|x_6|$. For each case, we obtain $d(x,C) \geq (n-1)/2$, so the covering radius of $C$ cannot be $(n-3)/2$. \end{proof} \section{Classification and Characterization} We prove in this section that any $(2R+3,7)R$ code is equivalent to a code that belongs to the family examined in Theorem \ref{suff-theor} by the help of a classification result regarding surjective codes. \begin{definition} A binary code $C$ is called\/ $2$-surjective if each of the four pairs of bits $($$00$, $01$, $10$ and $11$$)$ occurs in at least one codeword, for any pair of coordinates. \end{definition} It is known \cite{KGOH,KS:Fami} that no $2$-surjective $M$-word code exists of length \[ n > {M-1 \choose {\lfloor (M-2)/2 \rfloor}}. \] For $M=7$ this means that no $2$-surjective code exists if $n>15$. As regards the case when $M=7$ and $5 \leq n \leq 15$, a classification of all such $2$-surjective codes has been carried out \cite{KO}. It turns out \cite[Table 1]{KO} that the only \mbox{$(2R+3,7)R$} code that is $2$-surjective is the unique $(5,7)1$ code. \begin{theorem}\label{nonsur} For $R \geq 2$, there are no $2$-surjective $(2R+3,7)R$ codes. \end{theorem} We are now prepared to prove the main theorem of this paper. \begin{theorem}\label{necess} If $C^{(R)}$ is a $(2R+3,7)R$ code where $R \geq 2$, then \begin{equation}\label{back} C^{(R)} \equiv C(n_1,n_2,n_3,n_4,n_5,n_6) \end{equation} where exactly one of $n_1,n_2,n_3,n_4,n_5,n_6$ is even. \end{theorem} \begin{proof} The code $C^{(R)}$ is not 2-surjective according to Theorem \ref{nonsur}, and consequently $\label{onestep} C^{(R)} \equiv |C^{(R-1)}|X|$ where $C^{(R-1)}$ is of length $2R+1$ and $X$ is of length 2 with a nonzero covering radius. As the covering radius of a partitioned code cannot be less than the sum of the covering radii of its parts, the covering radius of $C^{(R-1)}$ has to be $R-1$ (it cannot be $R-2$ \mbox{\cite[Theorem 7]{KO}}) and the covering radius of $X$ has to be 1. By a repeated application of this argument we obtain that \begin{equation}\label{back2} C^{(R)} \equiv |C^{(1)}|X^{(1)}|X^{(2)}|\cdots |X^{(R-1)}| \end{equation} where $C^{(1)}$ is of length 5 and covering radius 1 and each $X^{(i)}$ is of length 2 and covering radius 1. Then the covering radius of $|C^{(1)}|X^{(i)}|$ has to be 2 for $i=1,2,\ldots ,R-1$ (since the order of the parts $X^{(i)}$ is arbitrary), so by Theorem \ref{constr-1-2}, \begin{equation} C^{(1)} \equiv |C_1|C_2|C_3|C_4|C_5| = C, \end{equation} and then \begin{equation}\label{back3} C^{(R)} \equiv |C|Y^{(1)}|Y^{(2)}|\cdots |Y^{(R-1)}|, \end{equation} where $|C|Y^{(i)}|$ is a $(7,7)2$ code for all $i$ and (having transposed coordinate values, if necessary) $|C|Y^{(1)}|Y^{(2)}|\cdots |Y^{(R-1)}|$ contains the all-zero word. But then Corollary \ref{cor} tells that all $Y^{(i)}$ have the form $|C_j|C_k|$ and so $C^{(R)} \equiv C(n_1,n_2,n_3,n_4,n_5,n_6)$ for some values of $n_i$. By Theorem \ref{suff-theor}, such a code has covering radius $(n-3)/2$ if and only if exactly one of $n_1,n_2,n_3,n_4,n_5,n_6$ is even. \end{proof} By \cite[Theorem 7]{KO}, Theorem \ref{necess} characterizes all optimal binary covering codes of size 7. \begin{theorem} \label{correspond} For any positive integer $R$, the number $Q(R)$ of inequivalent $(2R+3,7)R$ codes is equal to (a) the number of different integer solutions of the system \begin{equation}\label{compound} \begin{array}{l} m_1+m_2+m_3+m_4+m_5+m_6=R-1,\\ m_1 \geq m_2 \geq m_3 \geq 0,\\ m_4 \geq m_5 \geq 0,\\ m_6 \geq 0; \end{array} \end{equation} (b) the coefficient of $x^{R-1}$ in the expansion \begin{equation}\label{expfinal} \sum_{R=1}^{\infty} Q(R)x^{R-1}=\frac{1}{(1-x)^3(1-x^2)^2(1-x^3)}. \end{equation} \end{theorem} \begin{proof} (a) By Theorems \ref{suff-theor} and \ref{necess}, a code is a $(2R+3,7)R$ code if and only if it is equivalent to a code of form \begin{equation} \label{final} C(2m_1+1,2m_2+1,2m_3+1,2m_4+1,2m_5+1,2m_6), \end{equation} where $m_1,m_2,m_3,m_4,m_5,m_6$ are non-negative integers and $\sum_{i=1}^6 m_i = R-1$. By the discussion in Section \ref{old} it follows that a code like this is equivalent to another code of similar form $C(2m_1^{\prime}+1,2m_2^{\prime}+1,2m_3^{\prime}+1,2m_4^{\prime}+1,2m_5^{\prime}+1,2m_6^{\prime})$ if and only if $\{m_1,m_2,m_3\}=\{m_1^{\prime},m_2^{\prime},m_3^{\prime}\}$, $\{m_4,m_5\}=\{m_4^{\prime},m_5^{\prime}\}$ and $m_6=m_6^{\prime}$ (using set notation for multisets). (b) If we originate $Q(R)$ from (a), then clearly \begin{equation}\label{pr1} Q(R)=\sum_{\begin{array}{c}N_1+N_2+N_3=R-1\\N_1,N_2,N_3 \geq 0\end{array}} P(N_1,1)P(N_2,2)P(N_3,3), \end{equation} where $P(N,t)$ denotes the number of different partitions of $N$ with at most $t$ positive parts, for which it is well known \cite{Andrews} that \begin{equation}\label{pr2} \sum_{N=0}^{\infty} P(N,t)x^N=\prod_{j=1}^t \frac{1}{1-x^j}. \end{equation} This completes the proof, because (\ref{pr1}) and (\ref{pr2}) imply (\ref{expfinal}). \end{proof} Finally, observe that the full automorphism group of (\ref{final}) is of order $AB(2m_1+1)!(2m_2+1)!\cdots (2m_6)!$, where \[ \begin{array}{l} A = \begin{cases} 6, & \text{if $m_1=m_2=m_3$;}\\ 2, & \text{if $m_1=m_2\neq m_3$ or $m_1=m_3\neq m_2$ or $m_2=m_3\neq m_1$;}\\ 1, & \text{otherwise;} \end{cases} \\[30pt] B = \begin{cases} 2, & \mbox{if $m_4=m_5$;}\\ 1, & \mbox{otherwise.} \end{cases} \end{array} \] \section*{Acknowledgments} The authors thank a referee for useful comments and for pointing out incomplete argumentation in the original manuscript. \begin{thebibliography}{99} \bibitem{Andrews} G. E. Andrews, \emph{The Theory of Partitions}, Addison-Wesley, Reading, 1976. \bibitem{BOW} R. Bertolo, P. R. J. {\"O}sterg{\aa}rd and W. D. Weakley, An updated table of binary/ternary mixed covering codes, \emph{J. Combin. Des.} {\bf 12} (2004), 157--176. \bibitem{CHLL:Book} G. Cohen, I. Honkala, S. Litsyn and A. Lobstein, \emph{Covering Codes}, Elsevier, Amsterdam, 1997. \bibitem{CLS:Further} G. D. Cohen, A. C. Lobstein and N. J. A. Sloane, Further results on the covering radius of codes, \emph{IEEE Trans. Inform. Theory} {\bf 32} (1986), 680--694. \bibitem{Kaski:Book} P. Kaski and P. R. J. \"Osterg\aa rd, \emph{Classification Algorithms for Codes and Designs}, Springer, Berlin, 2006. \bibitem{KGOH} G. O. H. Katona, Two applications (for search theory and truth functions) of Sperner type theorems, \emph{Period. Math. Hungar.} {\bf 3} (1973), 19--26. \bibitem{KO} G. K\'eri and P. R. J. \"Osterg\aa rd, Further results on the covering radius of small codes, \emph{Discrete Math.}, accepted for publication. \bibitem{KS:Fami} D. J. Kleitman and J. Spencer, Families of $k$-independent sets, \emph{Discrete Math.} {\bf 6} (1973), 255--262. \bibitem{MS} F. J. MacWilliams and N. J. A. Sloane, \emph{The Theory of Error-Correcting Codes}, North-Holland, Amsterdam, 1977. \bibitem{OW} P. R. J. {\"O}sterg{\aa}rd and W. D. Weakley, Classification of binary covering codes, \emph{J. Combin. Des.} {\bf 8} (2000), 391--401. \bibitem{SK} R. G. Stanton and J. G. Kalbfleisch, Covering problems for dichotomized matchings, \emph{Aequationes Math.} {\bf 1} (1968), 94--103. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 94B75; Secondary 05B40, 94B25. \noindent \emph{Keywords:} covering radius, classification of codes, integer sequence. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A001399}, \seqnum{A001400}, \seqnum{A001401}, \seqnum{A002625}, and \seqnum{A072921}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received January 11 2006; revised version received September 22 2006 Published in {\it Journal of Integer Sequences}, September 22 2006. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document} \end{document}