% DESI891 Variant 1
% 24.11.99 P\"O
\documentstyle[12pt]{article}

\textwidth 150mm
\textheight 225mm
\oddsidemargin 2.5mm 
\evensidemargin 2.5mm
\topmargin -10mm

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{conjecture}{Conjecture}
\newtheorem{example}{Example}
 
%\newenvironment{proof}{\noindent {\em Proof.}}{\hspace*{\fill} $\Box $\newline}

\def\mathbf{\bf}
\newenvironment{proof}{\noindent {\em Proof.}}{  \hspace*{\fill} $\rule{1.7mm}{2.1mm} $\newline} 
%\newenvironment{proof1}{\noindent {\em First proof.}}{	\hspace*{\fill} $\rule{1.7mm}{2.1mm} $\newline}
%\newenvironment{proof2}{\noindent {\em Second proof.}}{  \hspace*{\fill} $\rule{1.7mm}{2.1mm} $\newline}

\begin{document}

\title{Error-Correcting Codes\\ over an Alphabet of Four Elements}

\author
{ Galina T. Bogdanova\\
  Institute of Mathematics and Informatics\\
  Bulgarian Academy of Sciences\\
  P.O.\ Box 323, 5000 V. Tarnovo, Bulgaria\\
  E-mail: {\tt lpmivt@vt.bia-bg.com}
    \and
  Andries E.  Brouwer\\
  Department of Mathematics\\
  Eindhoven University of Technology\\
  P.O.\ Box 513, 5600 MB   Eindhoven, The Netherlands\\
  E-mail: {\tt andries.brouwer@cwi.nl}
    \and
  Stoian N. Kapralov\\
  Department of Mathematics\\
  Technical University\\
  5300 Gabrovo, Bulgaria\\
  E-mail: {\tt kapralov@tugab.bg}
    \and
  Patric R. J. \"Osterg\aa rd\\
  Department of Computer Science and Engineering\\
  Helsinki University of Technology\\
  P.O.\ Box 5400, 02015 HUT, Finland\\
  E-mail: {\tt patric.ostergard@hut.fi}
}

\date{}

\maketitle

\footnotetext[1]{This work was partially supported by
    the Bulgarian National Science Fund % under Grant I--618/96
    and  by the Academy of Finland.}

\newpage

\begin{abstract}
   The problem of finding the
   values of $A_q(n,d)$---the maximum size of
   a code of length $n$ and minimum distance $d$ over an alphabet 
   of $q$ elements---is considered. 
   Upper and lower bounds on $A_4(n,d)$ are presented
   and some values of this function are settled. 
   A table of best known bounds on $A_4(n,d)$ is given for 
   $n \leq 12$. When $q \leq M < 2q$, all parameters for which
   $A_q(n,d) = M$ are determined.
\end{abstract}

%\newpage
\noindent
{\bf Keywords:} Bounds on codes, designs, 
error-correcting codes, nonlinear codes, quaternary codes
% at most five keywords!!!

%\newpage
\bigskip
\section{Introduction}

Let $Z_q$ denote the set $\{ 0,1,\ldots ,q-1 \}$
and let $Z_q^n$ be the set of all 
$n$-tuples (vectors) over $Z_q$. 
If $q$ is a prime power and we want the set to be
the finite field of order $q$,
we use the notations $F_q$ and $F_q^n$ instead.

The Hamming weight of a word, wt$(x)$, is the number of 
nonzero coordinates. The Hamming distance between two words 
is $d(x,y) = \mbox{wt}(x-y)$. The minimum distance of a code
is $d = d(C) = \min_{c,c'\in C, c\neq c'} d(c,c')$.

An $(n,M,d)_q$ code is a code over $Z_q$ that has length $n$, 
size $M$, and minimum distance $d$. One of the main problems 
in combinatorial
coding theory is to find the largest possible value of $M$ when
the other parameters have been fixed; this value is denoted by
$A_q(n,d)$ and corresponding codes are called {\em optimal\/}.
If one is not able to calculate the exact value of this
function, one may try to produce as good lower and upper bounds as
possible.

The function $A_2(n,d)$ has been thoroughly studied along the years, 
and exact values of this function are known for $n \leq 15$. 
A table on $A_2(n,d)$ can be found, for example, in \cite{BSSS1},
with some recent improvements in \cite{kai,ost3}.
Ternary codes and the function $A_3(n,d)$ have been considered
in \cite{BHOS1,VL1}.

{\em Linear\/} quaternary codes have earlier been considered,
for example, in \cite{ksc}.
Except for some preliminary results of this work, which were presented 
in \cite{GB1}, only sporadic results have been published earlier in
the general quaternary case. We denote by $[n,k,d]_q$ a linear code of
length $n$, dimension $k$, and minimum distance $d$ over $F_q$.
Obviously an $[n,k,d]_q$ code is an $(n,q^k,d)_q$ code.

In Section 2 we give some combinatorial bounds on $A_q(n,d)$, and
prove that for $q \le M< 2q$, $A_q(n,d)=M$ exactly when

\begin{displaymath}
\frac{(M+1)^2-3(M+1)+2q}{(M+1)^2-(M+1)}n < d
     \le \frac{M^2-3M+2q}{M^2-M}n.
\end{displaymath}

Methods for constructing codes and obtaining lower bounds
on $A_4(n,d)$ are discussed in Section 3. The codes found by
the various methods are also listed.
Finally, in Section 4, we tabulate the best known upper and lower 
bounds on $A_4(n,d)$ for $n \leq 12$.

\section{General Bounds on $A_q(n,d)$}

For $d = 1,2$, the value of $A_q(n,d)$ is given by the 
following theorem, which
is not difficult to prove,
so we consider only codes with minimum distance $d \geq 3$
in this paper.

\begin{theorem}
\hspace*{5mm}\\
\begin{tabular}{@{}ll}
(i) & $A_q(n,1) = q^n$,\\
(ii) & $A_q(n,2) = q^{n-1}$.
\end{tabular}
\end{theorem}

The following bounds are well-known and their proofs are direct.

\begin{theorem}
\label{trivial}
\hspace*{5mm}\\
\begin{tabular}{@{}ll}
(i) & $A_q(n,n) = q$,\\
(ii) & $A_q(n-1,d-1) \ge  A_q(n,d)$,\\
(iii) & $A_q(n,d-1) \ge  A_q(n,d)$,\\
(iv) & $A_q(n,d) \le qA_q(n-1,d)$.
\end{tabular}
\end{theorem}

It is possible to determine which small values can be
attained by $A_q(n,d)$ and when this happens. It is shown in
\cite{VL1} that $A_3(n,d) = 3$ exactly when 
$\frac{5}{6}n < d \leq n$; in \cite{BHOS1} this
result is further extended. We shall here determine when 
$A_q(n,d) = M$ for arbitrary $q$ and $M < 2q$. 
In the solution of this problem, the Plotkin bound and the 
juxtaposition construction are central.

The $q$-ary version of the Plotkin bound \cite{Pl1} is
proved next. We need the following lemma, which is the discrete version
of the Cauchy-Schwarz inequality.

\begin{lemma}
\label{cs}
Let $\sum_{i=0}^{n-1}a_i = A$, where the variables $a_i$ are nonnegative 
integers. Then $\sum_{i=0}^{n-1}a_i^2$ attains its smallest value when
$a_i = \lfloor (A+i)/n \rfloor$.
\end{lemma}

\begin{proof}
We first show that the smallest value cannot be
attained if there exist $i$ and $j$ such that 
$a_i - a_j \geq 2$. Namely, then we can substitute
the values $a_i$ and $a_j$ by $a_i-1$ and $a_j+1$, 
respectively, to get an even smaller value, since 
$(a_i-1)^2 + (a_j+1)^2 = a_i^2 + a_j^2 + 2(a_j-a_i+1) <
a_i^2 + a_j^2$. 
The unique solution (up to permutation of the indices)
to $\sum_{i=0}^{n-1}a_i = A$, $|a_i - a_j| \leq 1$ for all $i,j$,
is $a_i = \lfloor (A+i)/n \rfloor$.
\end{proof}

\begin{theorem}
\label{plotkin}
If there exists an $(n,M,d)_q$ code, then
$$M(M-1)d \le 2n \sum_{i=0}^{q-2} \sum_{j=i+1}^{q-1} M_iM_j ,$$
where $M_i = \lfloor (M+i)/q \rfloor$.
\end{theorem}

\begin{proof}
As in the proof of the binary case \cite{Pl1}, we sum the distances 
between all ordered pairs of codewords in two different ways. An arbitrary
column contributes with $\sum_{i=0}^{q-1} m_i(M-m_i)
= M\sum_{i=0}^{q-1}m_i - \sum_{i=0}^{q-1}m_i^2 =
M^2 - \sum_{i=0}^{q-1} m_i^2$ to this sum, where
$m_i$ is the number of codewords with value $i$ in this coordinate. 
Using Lemma \ref{cs}, this value attains its largest value when 
$m_i = M_i = \lfloor (M+i)/q \rfloor$, and this value is 
$2\sum_{i=0}^{q-2}\sum_{j=i+1}^{q-1}M_iM_j$. Summing over all coordinates
gives $2n\sum_{i=0}^{q-2}\sum_{j=i+1}^{q-1}M_iM_j$.

On the other hand, all pairwise distances between codewords are
greater than or equal to
$d$, and summing the distances in this way gives a total sum of at least
$M(M-1)d$. The theorem is now proved by combining this lower bound
and the previously obtained upper bound.
\end{proof}

Equality in Theorem \ref{plotkin} implies that the
code is equidistant. The Plotkin bound for codes with
both binary and ternary coordinates was previously given in
\cite{BHOS1}, where it is also pointed out that the version for
ternary codes given in \cite{mac} is erroneous. The $q$-ary
version of the Plotkin bound given in \cite[Ch.\ 1, Theorem 11.2]{bla},
\cite[Theorem 5.2.4]{van},
and other places in the literature
is inferior to the bound in Theorem \ref{plotkin} since the sum 
$\sum_{i=0}^{q-1}m_i^2$ is bounded from below by $M^2/q$ in the proof
of that version.

Note that the maximum $M$ which satisfies Theorem \ref{plotkin}
only depends on the ratio $d/n$.

In the juxtaposition construction,
copies of a given $(n,M,d)_q$ code are pasted side by side.
The following version of this construction is sufficient for
our needs.

\begin{theorem}
\label{juxta}
If there exists an $(n,M,d)_q$ code, then there exists
a $(\lambda n,M,\lambda d)_q$ code for all integers
$\lambda \geq 1$.
\end{theorem}

Combining Theorems \ref{plotkin} and \ref{juxta}, we
get the following result.

\begin{corollary}
Let $M'$ be the largest integer $M$ that satisfies 
the inequality in the Plotkin bound (Theorem \ref{plotkin}).
If $A_q(n,d) = M'$, then $A_q(\lambda n,\lambda d) = M'$
for all integers $\lambda \geq 1$.
\end{corollary}

To prove the main result, we need the following connection 
between $q$-ary codes and
resolvable pairwise block designs (PBDs). The theorem generalizes
a result from \cite{zin}.

\begin{theorem}
\label{pbd}
Suppose we have a resolvable PBD$(v=M,K;\lambda)$
with $n$ parallel classes, where each parallel class has
at most $q$ blocks. Then there exists an equidistant 
$(n,M,n-\lambda)_q$ code.
\end{theorem}

\begin{proof}
 With the alphabet $Z_q$, let the $i$th codeword
 have symbol $j-1$ in the $k$th position whenever the $i$th point is
 in the $j$th block of the $k$th parallel class. Since each pair
 of points occurs in $\lambda$ blocks of the PBD, the distance between
 any two codewords is $n-\lambda$.
\end{proof}

Note that there are no restrictions on the block sizes in $K$;
blocks need not have the same size, and block size 
1 is allowed. The main theorem is as follows.

\begin{theorem}
\label{main}
 Let $q < M \leq 2q$. Then an $(n,M,n-\lambda)_q$ code exists
 if and only if $n/\lambda \leq M(M-1)/2(M-q)$.
 For $M \ne 2q-1$ equality implies that such a code is optimal.
\end{theorem}

\begin{proof} 
 Write $b = M-q$ so that $0 < b \leq M/2$. Write $a = M-2b$.
 Following Baranyai \cite{bar}, there exists a collection of $n$ 1-factors
 of an $M$-set, where each 1-factor contains $a$ singletons and
 $b$ pairs, and each pair occurs precisely $\lambda$ times if and only if
 $2nb = \lambda M(M-1)$. Now put $q=a+b$ and apply Theorem \ref{pbd} to find
 the required code. The code obtained has equality in the Plotkin
 bound, and hence is optimal, unless $M(M-1)/(M-q) = (M+1)M/(M+1-q)$
 which happens precisely for $M=2q-1$.
\end{proof}

\begin{corollary}
For $q \le M < 2q$, $A_q(n,d)=M$ exactly when

\begin{displaymath}
\frac{(M+1)^2-3(M+1)+2q}{(M+1)^2-(M+1)}n < d
     \le \frac{M^2-3M+2q}{M^2-M}n.
\end{displaymath}

\end{corollary}

The right-to-left implication in Theorem \ref{main} for $M = q+1$
was obtained earlier in \cite[Lemma 5.2]{VL1}. For $q=4$, bounds
for small $M$ are summarized in the following theorem; for these 
results we also use the existence of
a $(6,9,5)_4$ code to be constructed in Section \ref{cyc}.

\begin{theorem}
$A_4(n,d) = 4$ precisely when $\frac{9}{10}n < d \leq n$,
$A_4(n,d) = 5$ precisely when $\frac{13}{15}n < d \leq \frac{9}{10}n$,
$A_4(n,d) = 6$ precisely when $\frac{6}{7}n < d \leq \frac{13}{15}n$,
$A_4(n,d) = 8$ precisely when $\frac{5}{6}n < d \leq \frac{6}{7}n$, and
$A_4(n,d) = 9$ when $\frac{37}{45}n < d \leq \frac{5}{6}n$.
\end{theorem}

In the same way, we can get the following infinite families of 
optimal codes.

\begin{theorem}
\label{inf}
Let $\lambda \geq 1$. Then
$A_4(11\lambda ,9\lambda) = 12$ and
$A_4(5\lambda ,4\lambda) = 16$.
\end{theorem}

\begin{proof}
Follows from the Plotkin bound and the existence
of $(11,12,9)_4$ and $(5,16,4)_4$ codes. The former code
follows from the existence of a 
$2$-$(12,3,2)$ RBIBD (see, for example, \cite{fur})
and Theorem \ref{pbd}. The latter code is obtained by
shortening a $(6,64,4)_4$ code \cite{ass1}.
\end{proof}

As for the upper bounds, in addition to those presented in this
section, the {\em Hamming bound\/} \cite{hamm} and 
the {\em linear programming bound\/} \cite{del} will be used. These
general bounds are also described in standard references in coding 
theory \cite{mac1}.

\section{Finding Lower Bounds on $A_q(n,d)$}

Lower bounds on $A_q(n,d)$ are obtained by constructing
corresponding codes. Some combinatorial constructions 
were given in the previous section. Here we start by giving
a geometric formulation, and then discuss searching for codes
by computer.

An exhaustive search is for all but the smallest parameters
out of question. To search for codes, we therefore have
to use stochastic methods and/or prescribe a structure of
the codes to restrict the search. The stochastic methods used
in this work are the {\em noising method\/} \cite{CH1} and
{\em tabu search\/} \cite{glo}.

As for the structure of the codes, four different methods are 
used. These give additive codes, lexicographically minimal codes,
codes that consist of orbits of words under the action
of a permutation group, and codes that consist of cosets
of a linear code, respectively.

\subsection{Additive codes over $Z_2 \times Z_2$}
\label{additive}
If we give the alphabet $Q$ of size 4 the structure of additive group,
then we can talk about additive codes, that is, codes that are invariant
under vector addition. (A code that is additive over a cyclic group
of prime order is linear, and in particular binary and ternary additive
codes are linear, but in the quaternary case being linear is stronger
than being additive.)

There are two different groups of order 4, the cyclic group $Z_4$
and $Z_2 \times Z_2$. The latter one seems to give the best results.
In fact, whenever a lower bound in the table we give below
is a power of two, it is achieved by a code that is additive
over $Z_2 \times Z_2$.
An additive code of length $n$ over this group (let us just
write `additive code' in the rest of this section)
is equivalent to a binary linear code of length $2n$ with coordinate
positions $0,1,...,0',1',...$ and with a distance function
that compares code words and counts 1 difference for each pair of
coordinate positions $i,i'$ where they differ.

The dual of such a binary linear code of length $2n$ and dimension $k$
is a binary linear code of length $2n$ and dimension $2n-k$ with
the property that the coordinate positions in at most $d-1$ pairs
are independent. Viewing the coordinate positions as points in
the projective space $PG(2n-k-1,2)$ we see that our code is
equivalent to a collection of $n$ lines in $PG(2n-k-1,2)$
such that any $d-1$ of them span a $PG(2d-3,2)$.

Thus, we see that an additive code of length $n$ and dimension $k$
and minimum distance 3 is equivalent to a collection of $n$ pairwise
disjoint lines in $PG(2n-k-1,2)$, and hence exists precisely when
$n \le (2^{2n-k}-e)/3$ where $e = 1$ when $k$ is even,
and $e = 4$ when $k$ is odd. Thus, there exists an additive
$(9,2^{13},3)$ code (but there is no additive $(10,2^{15},3)$ code),
and it follows that for these parameters we have an additive code
that is twice as large as the best linear code.

The 13 vectors below generate a $(12,2^{13},5)$ code.
(The four symbols 00,01,10,11 of $Z_2 \times Z_2$ are written 0,1,2,3.)

\begin{center}
{\small
\begin{tabular}{cc}
111110000000 & 130102100001 \\
110001110000 & 110020201000 \\
101001001100 & 011121021001 \\
010100101010 & 101100102200 \\
211001000001 & 000121002020 \\
022001101000 & 131121002002 \\
021200001001 \\
\end{tabular}}
\end{center}

\subsection{Lexicographic Codes}

\label{lex}
{\em Lexicographic codes\/} of length $n$ and
Hamming distance $d$ are obtained  by 
considering all $q$-ary vectors in lexicographic order,
and adding them to the code if they are at a distance greater 
than or equal to $d$ from the words that were added earlier. 
Many interesting codes
can be obtained in this way \cite {CS1}.

There are several variants of lexicographic codes. One
may, for example, consider the $q$-ary vectors in an order different
from the standard lexicographic order \cite {BP1}. Also,
one may start with one or several words in the code; such codes are
called {\em lexicographic codes with seeds}. The following new
codes can be obtained as lexicographic codes with
seeds (in both cases, the seed consists of a single word).

\vspace{5mm}
\noindent
\begin{tabular}{@{}ll}
$A_4(11,8) \geq 32$: & Seed $\{21100332113\}$.\\
$A_4(12,9) \geq 24$: & Seed $\{303311333233\}$.
\end{tabular}

\subsection{Cyclic Codes}

\label{cyc}
Many of the best known codes with a large minimum distance
have a symmetry generated by a single permutation. 
(More general permutation groups were not considered in this
work.) If this
permutation consists of a single cycle, the code is called
{\em cyclic\/}, and if the permutation consists of several cycles of
equal length and acts on all coordinates, the code is called
{\em quasi-cyclic\/}. A code may have one or several fixed
coordinates on which the permutation does not act. 

In searching for codes with the aforementioned symmetries, we first
fix the permutation group and the parameters $n$ and $d$, 
and then transform the search
problem into an instance of the {\em maximum-weight clique problem\/}.

The orbits of words under the action of the permutation group
become the vertices of a graph, discarding orbits that contain
words with mutual distance less than $d$. The weight
of a vertex is the length of---the number of vertices in---the
corresponding orbit. Finally, an edge is inserted between two vertices
iff all words in one orbit are at a distance greater than or equal
to $d$ from the words in the other orbit. 

The instances of the maximum-weight clique problem were solved
exactly using the program {\em wclique\/} \cite{ost1}, which is
available in C at 
$<$URL:http://\hspace{0pt}www.tcs.hut.fi/\hspace{0pt}$\sim$pat/\hspace{0pt}wclique.html$>$. 
For each code in the following list, we give the 
base blocks on which the permutation acts. The permutation
is indicated by the parentheses.

\vspace{5mm}
\noindent
\begin{flushleft}
$A_4(6,5) \geq 9$: (201)(131), (230)(322), (321)(300).\\
$A_4(7,4) \geq 128$: (0000000), (1113310), (1232000), (1303120), (1311200), (2021100), (2102300), (2122111), (2222222), (2223010), (2231330), (2312130), (2332321), (3011010), (3132210), (3201220), (3213100), (3233311), (3322020), (3330300).\\
$A_4(8,5) \geq 70$: (00000000), (10311200),
(11111111), (12022110), (21232000), (22312231), (23301110),
(32201300), (32333020), (33131230), (33323211).\\
$A_4(8,6) \geq 32$: (0000000)2, (1111111)1, (1330210)3,
(2213010)0, (2222222)3, (3123200)1, (3231120)2, (3333333)0.\\
$A_4(9,7) \geq 18$: (321323200), (330211010).\\
\end{flushleft}

\vspace{5mm}
In some instances where a group generated by a single permutation
leads to a maximum-weight clique instance that cannot be solved
within reasonable time, we tried to impose also the following
symmetry: if $c$ is a codeword, then so is $c + {\mathbf 1}$
(${\mathbf 1}$ is the all-one word), $c + {\mathbf 2}$, and
$c + {\mathbf 3}$. This approach led to the following lower
bounds. 

\vspace{5mm}
\noindent
$A_4(10,7) \geq 40$: (3311310100).\\
$A_4(11,7) \geq 92$: (00000000000), 
(31330123100), (33113203000).

\subsection{A Matrix Construction}

\label{matrix}
The last two codes in the previous subsection can be seen
as unions of cosets of the linear code 
$\{{\mathbf 0},{\mathbf 1},{\mathbf 2},{\mathbf 3}\} \subseteq F_q^n$.
More generally, one may consider codes that are unions of
cosets of arbitrary linear codes. Such codes are obtained by
the following construction \cite{kab,ost2}.

We consider codes over the field $F_q$. 
Let $A = [a_1\ a_2\ \cdots\ a_n]$ be an 
$r \times n$ matrix with column vectors $a_i$ from 
$F_q^r$, and let $S \subseteq F_q^r$. For two words
$x,y \in F_q^r$ we define the {\em distance between $x$ and $y$
using $A$\/} as $d_A(x,y) = \min \{wt(t) \mid
At = x-y,\ t\in F_q^n\}$.
If $At = x-y$ has no solution, then $d_A(x,y) = r$.
We further define $d_A(S) = \min_{s,s'\in S,s\neq s'} d_A(s,s')$,
and utilize these concepts in the following theorem 
\cite[Theorem 1]{ost2}.

\begin{theorem}
\label{mat}
Let $A$ be a parity check matrix for a linear code with 
minimum distance
$d'$. Then the code $W = \{w \in F^n_q \mid Aw \in S \}$ 
has minimum distance $\min\{d_A(S),d'\}$.
\end{theorem}

Using this result and tabu search---more details regarding the
search can be found in \cite{BHOS1}---we found the following
codes. For all codes, the matrix $A$ contains the columns
of the $r \times r$ identity matrix.
The column vectors in $A$ are given first, with the vectors
of the identity matrix omitted. The words in $S$ are given after
the semicolon. We denote $F_4 = \{0,1,2=\alpha ,3={\alpha}^2\}$, 
where $\alpha$ is a primitive element.

\vspace{5mm}
\noindent
$A_4(9,3) \geq 8192$: 1100, 1010, 1001, 0111, 1111;
0013, 0301, 1020, 1332, 2112, 2200, 3121, 3233.\\
$A_4(10,3) \geq 17408$: 11000, 10100, 01010, 01101, 00021;
00130, 00322, 01103, 02231, 03010, 10112, 11333, 12001, 13220, 
21111, 21232, 22023, 23302, 32213, 32320, 33032, 33101.\\
$A_4(8,4) \geq 320$: 11100, 32100, 10011; 00200, 03323, 11022, 
20131, 32112.

\section{A Table of $A_4(n,d)$}

Bounds on $A_4(n,d)$ for $ 3 \le  d \le n \le 12 $ are presented in
Table 1. If only one number occurs in a position of this table, then 
this is the exact value; if two numbers are given, the upper one denotes 
the best known upper bound and the lower one the best known lower bound.
The indices indicate where the bounds come from. We omit the index
when the bound follows from Theorem \ref{trivial}.

\vspace{1cm}
\noindent
INSERT TABLE 1 HERE.
\vspace{1cm}

\begin{thebibliography}{99}
\bibitem{ass1} E. F. Assmus, Jr., and H. F. Mattson, Jr., 
  On weights in quadratic-residue codes, {\em Discrete
  Math.\/}, Vol.~3 (1972) pp.~1--20.
\bibitem{bar} Zs. Baranyai, On the factorization of the complete 
  uniform hypergraph, {\em Infinite and Finite Sets, I, Colloq. Honour Paul 
  Erd\H{o}s, Keszthely 1973, Colloq. Math. Soc. J\'anos Bolyai}, Vol.~10
  (1995) pp.~91--108. 
\bibitem{bla} I. F. Blake and R. C. Mullin, {\em The Mathematical
  Theory of Coding}, Academic Press, New York (1975).
\bibitem{GB1}  G. Bogdanova,
  Optimal codes over an alphabet of 4 elements,
  {\em Proc.\ Fifth International 
  Workshop on Algebraic and Combinatorial Coding Theory, Sozopol,
  June 1--6, 1996\/},
  Unicorn, Shumen, Bulgaria (1996) pp.~46--53. 
\bibitem{BHOS1} A. E. Brouwer, H. O. H\"{a}m\"{a}l\"{a}inen,
  P. R. J. \"{O}sterg{\aa}rd, and N. J. A. Sloane,
  Bounds on mixed binary/ternary codes, 
  {\em IEEE Trans. Inform. Theory\/},
  Vol.~44 (1998) pp.~140--161.
\bibitem{BSSS1} A. E. Brouwer, J. B. Shearer, N. J. A. Sloane, and 
  W. D. Smith, A new table of constant weight codes,
  {\em IEEE Trans. Inform. Theory\/},
  Vol.~36 (1990) pp.~1334--1380.
\bibitem{BP1} R. A. Brualdi and V. S. Pless, Greedy codes,
  {\em J. Combin. Theory Ser. A.\/}, Vol.~64 (1993) pp.~10--30.
\bibitem{CS1} J. H. Conway and N. J. A. Sloane,
  Lexicographic codes: Error-correcting codes from game theory,
  {\em IEEE Trans. Inform. Theory\/},
  Vol.~32 (1986) pp.~337--348.
\bibitem{CH1} I. Charon and O. Hudry, The noising method: A new method for
  combinatorial optimization, {\em Oper. Res. Lett.\/}, 
  Vol.~14 (1993) pp.~133--137.
\bibitem{del} P. Delsarte, Bounds for unrestricted codes,
  by linear programming, {\em Philips Res.\ Rep.\/},
  Vol.~27 (1972) pp.~47--64.
% \bibitem{DLW1} J. H. Dinitz, E. R. Lamken, and W. D. Wallis,
%   Scheduling a tournament, {\em The CRC Handbook of Combinatorial 
%   Designs\/} (C. J. Colbourn and J. H. Dinitz, eds.), CRC Press, Boca Raton 
%   (1996) pp. 565--578.
\bibitem{EB} Y. Edel and J. Bierbrauer, Inverting construction Y1,
{\em IEEE Trans.\ Inform.\ Theory\/}, Vol.~44 (1998), p.~1993.
\bibitem{fur} S. Furino, Y. Miao, and J. Yin, {\em Frames and 
  Resolvable Designs: Uses, Constructions, and Existence,}
  CRC Press, Boca Raton (1996). 
\bibitem{glo} F. Glover, Tabu search---Part I,
  {\em ORSA J. Comput.\/}, Vol.~1 (1989) pp.~190--206.
\bibitem{ham} H. O. H\"am\"al\"ainen, Two new binary codes 
  with minimum distance three, {\em IEEE Trans.\ Inform.\ 
  Theory\/}, Vol.~34 (1988) p.~875.
\bibitem{hamm} R. W. Hamming, Error detecting and error
  correcting codes, {\em Bell System Tech. J.\/},
  Vol.~29 (1950) pp.~147--160.
\bibitem{kab} G. A. Kabatyanskii and V. I. Panchenko, Unit 
  sphere packings and coverings of the Hamming space,
  (in Russian), {\em Probl.\ Peredach.\ Inform.,\/} Vol.~24
  (1988) pp.~3--16. English translation in {\em Probl.\
  Inform.\ Trans.,\/} Vol.~24 (1988) pp.~261--272.
\bibitem{kai} M. Kaikkonen, Codes from affine permutation
  groups, {\em Des. Codes Cryptogr.\/}, Vol.~15 (1998)
  pp.~183--186.
\bibitem{kap} K. S. Kapralov, Optimal Quaternary Two-Error-Correcting
  Codes of Length 7 have 32 Codewords, preprint, Dec. 1999.
\bibitem{ksc} F. R. Kschischang and S. Pasupathy,
  Some ternary and quaternary codes and associated sphere 
  packings, {\em IEEE Trans.\ Inform.\ Theory\/},
  Vol.~38 (1992) pp.~227--246.
\bibitem{van} J. H. van Lint, {\em Introduction to Coding Theory,}
  Springer-Verlag, New York (1982).
\bibitem{mac} C. Mackenzie and J. Seberry, Maximal ternary
  codes and Plotkin's bound, {\em Ars Combin.\/},
  Vol.~17A (1984), pp.~251--270.
\bibitem{mac1} F. J. MacWilliams and N. J. A. Sloane,
  {\em The Theory of Error-Correcting Codes,}
  North-Holland, Amsterdam (1977).
\bibitem{ost3} P. R. J. \"Osterg\aa rd, T. Baicheva, and E. Kolev,
  Optimal binary one-error-correcting codes of length 10 
  have 72 codewords, {\em IEEE Trans. Inform. Theory\/}, 
  Vol.~45 (1999) pp.~1229--1231.
\bibitem{ost1} P. R. J. \"Osterg\aa rd, A new algorithm for the
  maximum-weight clique problem, submitted for publication.
\bibitem{ost2} P. R. J. \"Osterg\aa rd and M. K. Kaikkonen, 
  New single-error-correcting codes, {\em IEEE Trans. Inform.
  Theory\/}, Vol.~42 (1996) pp.~1261--1262.
\bibitem{Pl1} M. Plotkin,  Binary codes with specified minimum distance,
  {\em IRE Trans. Inform. Theory\/}, Vol.~6 (1960) pp.~445--450.
\bibitem{zin} N. V. Semakov and V. A. Zinov'ev, Equidistant
  $q$-ary codes with maximal distance and resolvable balanced incomplete 
  block designs, (in Russian), {\em Probl.\ Peredach.\ Inform.,\/} Vol.~4,
  No.~2 (1968) pp.~3--10.
%\bibitem{SD75} G. J. Simmons and J. A. Davis, Pair designs,
%  {\it Commun. Stat.}, Vol. 4 (1975) pp. 255--272.
\bibitem{ste1} J. M. Stein and V. K. Bhargava, Two quadratic residue
  codes, {\em Proc. IEEE\/}, Vol.~63 (1975) pp.~202.
\bibitem{VL1} R. J. M. Vaessens, E. H. L. Aarts, and J. H. van Lint,
  Genetic algorithms in coding theory---A table for $A_3(n,d)$,
  {\em Discrete Appl.\ Math.\/}, Vol.\ 45 (1993) pp.~71--87.
\end{thebibliography}

\pagebreak

\noindent
TABLE CAPTIONS LIST \& KEYS

\vspace{12mm}
\noindent
Table 1\@. Bounds on $A_4(n,d)$ for $n \leq 12$.

\vspace{6mm}
\noindent
Key to Table 1.\\
\begin{tabular}{@{}l@{ --- }p{12cm}}
\multicolumn{2}{@{}l}{Unmarked bounds are from Theorem \ref{trivial}.}\\
\multicolumn{2}{@{}l}{Lower bounds:}\\
$a$ & From a $(12,2^{13},5)$ additive code (Section \ref{additive})\\
$b$ & Extended quadratic residue (QR) code \cite{ass1}\\
$c$ & From $[18,9,8]_4$ extended QR code \cite{ste1}\\
$d$ & From $[17,13,4]_4$ linear code (elliptic quadric in $PG(3,4)$) \cite{ksc}\\
$h$ & From $[21,18,3]_4$ Hamming code\\
$j$ & Juxtaposition (Theorem \ref{juxta})\\
$k$ & H\"am\"al\"ainen \cite{ham} and Kabatyanskii and Panchenko \cite{kab}\\
$m$ & Code from matrix construction (Section \ref{matrix})\\
$r$ & From RBIBD (Theorems \ref{pbd}, \ref{inf})\\
$t$ & Theorem \ref{main}\\
$x$ & Lexicographic code (Section \ref{lex})\\
$y$ & (Quasi)-Cyclic code (Section \ref{cyc})\\
$z$ & Cyclic code and its translates (Section \ref{cyc})\\
\multicolumn{2}{@{}l}{Upper bounds:}\\
$h$ & Hamming bound \cite{hamm}\\
$k$ & K. S. Kapralov \cite{kap}\\
$l$ & Linear programming bound \cite{del}\\
$p$ & Plotkin bound (Theorem \ref{plotkin})
\end{tabular} 

\pagebreak

\noindent
TABLE 1.
\vspace{1cm}

\noindent
\begin{flushleft}
{ \scriptsize
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
&&&&&&&&&&\\
$n\backslash d$&3&4&5&6&7&8&9&10&11&12\\
&&&&&&&&&&\\
\hline
~~~~~&~~~~~&~~~~~&~~~~~&~~~~~&~~~~~&~~~~~&~~~~~&~~~~~&~~~~~&~~~~~\\
3&4&&&&&&&&&\\
%&&&&&&&&&&\\
\hline
&&&&&&&&&&\\
4&16&4&&&&&&&&\\
%&&&&&&&&&&\\
\hline
&&&&&&&&&&\\
5&$64^h$&16&4&&&&&&&\\
%&&&&&&&&&&\\
\hline
&$179^{l}$&&&&&&&&&\\
6&&$64_b$&$9_y^p$&4&&&&&&\\
&$164_k$&&&&&&&&&\\
\hline
&$614^{l}$&179&&&&&&&&\\
7&&&$32^{k}$&$8^p$&4&&&&&\\
&512&$128_y$&&&&&&&&\\
\hline
&$2340^{l}$&614&128&&&&&&&\\
8&&&&$32_y$&$5^p$&4&&&&\\
&2048&$320_m$&$70_y$&&&&&&&\\
\hline
&$9362^{h}$&2340&512&128&20&&&&&\\
9&&&&&&5&4&&&\\
&$8192_m$&1024&256&64&$18_y$&&&&&\\
\hline
&$30427^{l}$&9362&$2048$&512&80&&&&&\\
10&&&&&&$16_j^p$&$5_t$&4&&\\
&$17408_m$&4096&1024&256&$40_z$&&&&&\\
\hline
&$109226^{l}$&30427&$6241^{l}$&2048&320&64&&&&\\
11&&&&&&&$12_r^p$&4&4&\\
&65536&16384&4096&1024&$92_z$&$32_x$&&&&\\
\hline
&$419430^{l}$&109226&$20852^{l}$&6241&1280&$242^{l}$&48&&&\\
12&&&&&&&&$9_j^p$&4&4\\
&$262144_h$&$65536_d$&$8192_a$&$4096_b$&$256_c$&$64_c$&$24_x$&&&\\
\hline
\end{tabular}

}
\end{flushleft}

\end{document}


