\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}

.
