>From njas@research.att.com Wed May  7 23:18:09 1997
Received: from ns.research.att.com by hera.cwi.nl with SMTP
	id <AA22269@cwi.nl>; Wed, 7 May 1997 23:18:05 +0200
Received: from research.att.com ([135.205.32.20]) by ns; Wed May  7 17:17:04 EDT 1997
Received: from fry.research.att.com ([135.205.36.20]) by research; Wed May  7 17:16:51 EDT 1997
Received: (from njas@localhost)
	by fry.research.att.com (8.8.5/8.8.5) id RAA09402;
	Wed, 7 May 1997 17:16:50 -0400 (EDT)
Date: Wed, 7 May 1997 17:16:50 -0400 (EDT)
From: "N. J. A. Sloane" <njas@research.att.com>
Message-Id: <199705072116.RAA09402@fry.research.att.com>
To: Patric.Ostergard@hut.fi, aeb@cwi.nl
Status: R

\documentclass[12pt]{article}
\usepackage{latexsym}
%% \documentstyle[a4,12pt]{article}
\setcounter{footnote}{1}
\title{Bounds on Mixed Binary/Ternary Codes}
\author{A. E. Brouwer, Heikki O. H\"am\"al\"ainen,\\
Patric R. J. \"Osterg\aa rd\thanks{Research supported by the
Academy of Finland.} (Member, IEEE),\\
N. J. A. Sloane (Fellow, IEEE)}
\date{May 6, 1997}
%% version 34 from njas
\begin{document}
\maketitle

\newtheorem{Theorem} {Theorem} [section]
\newtheorem{Proposition} [Theorem] {Proposition}
\newtheorem{Lemma} [Theorem] {Lemma}
\newcommand{\Proof}{ \noindent{\bf Proof:}\quad }
\newcommand{\qed  }{\hfill$\Box$\medskip}
\newcommand{\Ff}{{\bf F}}
\newcommand{\ff}[2]{{\makebox[#1pt][r]{}#2\makebox[#1pt][l]{}}}
\newcommand{\zlr}[2]{{\makebox[0pt][#2]{$^{\mbox{\scriptsize\it #1}}$}}}
\newcommand{\zl}[1]{{\zlr{#1}{l}}}
\newcommand{\zr}[1]{{\zlr{#1}{r}}}
\newcommand{\zz}[1]{{$^{#1}$}}
\newcommand{\nlsp}{{\vspace{3pt}\\}}

\begin{abstract}
Upper and lower bounds are presented for the maximal possible size
of mixed binary/ternary error-correcting codes.
A table up to length 13 is included.
The upper bounds are obtained by applying the linear programming
bound to the product of two association schemes.
The lower bounds arise from a number of different constructions.
\end{abstract}

\section{Introduction}
Let $X = \Ff^{n_2}\Ff^{n_3}$ be the set of all vectors with $n_2$
binary and $n_3$ ternary coordinates (in this order).
Let $d(.,.)$ denote Hamming distance on $X$.
We study the existence of large packings in $X$, i.e., we study the
function $N(n_2,n_3,d)$ giving the maximal possible size of a code $C$
in $X$ with $d(c,c') \ge d$ for any two (distinct) codewords $c,c' \in C$.
The dual version of this problem, the existence of small
coverings in $X$, has been discussed in \cite{HR,OH}.
Both of these problems were originally motivated by the football pool
problem (see \cite{HHLO2}).

\medskip

We begin by describing the use of product schemes to get upper bounds
on $N(n_2,n_3,d)$, and then discuss various constructions and computer searches
that provide lower bounds. Among the codes constructed, there are a few
(with $n_2 = 0$) that improve the known lower bounds for ternary codes.

\medskip

The paper concludes with a table of $N(n_2,n_3,d)$ for $n_2 + n_3 \le 13$.
The first and fourth authors produced a version of this table
in 1995 (improving and extending various tables already in
the literature, for example that in \cite{vLvW}).
These results were then combined with those of the second and
third authors, who had used computer search and various constructions
to obtain lower bounds (many of which were tabulated by
the second author already in 1991).

\section{Products of association schemes}
Let $(X',{\cal R}')$ and $(X'',{\cal R}'')$ be two association schemes,
with ${\cal R'} = \{R_{i'} \mid i' \in I'\}$ and
${\cal R''} = \{R_{i''} \mid i'' \in I''\}$.
(For definitions and notation, see \cite[Chapter 2]{BCN}.)
We get a new association scheme $(X,{\cal R})$, the {\em product} of these two,
by taking $X = X' \times X''$ for the point set, and
${\cal R} = \{R_{i'i''} \mid i' \in I',~ i'' \in I''\}$, where,
for $x = (x',x'')$ and $y = (y',y'')$, we have $(x,y) \in R_{i'i''}$
if and only if $(x',y') \in R_{i'}$ and $(x'',y'') \in R_{i''}$.

It is trivial to verify that this product scheme indeed is an association
scheme. The intersection numbers are given by
$p_{ij}^k = p_{i'j'}^{k'} p_{i''j''}^{k''}$, where $i = (i',i'')$, etc.,
and the dual intersection numbers by
$q_{ij}^k = q_{i'j'}^{k'} q_{i''j''}^{k''}$.
The adjacency matrices are given by $A_i = A_{i'} \otimes A_{i''}$,
the idempotents by $E_i = E_{i'} \otimes E_{i''}$,
and for the eigenmatrix $P$ and dual eigenmatrix $Q$ (defined by
$A_j = \sum_i P_{ij} E_i$ and $E_j = {1 \over |X|} \sum_i Q_{ij} A_i$)
we have $P_{ij} = P_{i'j'}P_{i''j''}$ and $Q_{ij} = Q_{i'j'}Q_{i''j''}$.

Products of more than two schemes can be defined in an analogous way
(and the multiplication of association schemes is associative).

Although product schemes are well known, we cannot
find an explicit discussion of their properties or applications.
There is a short reference in Godsil \cite[p. 231]{Godsil},
and an only slightly longer one in Dey \cite[\S 5.10.7]{Dey}.
[We wrote this in 1995. In the meantime several other applications of
product schemes have come to our attention. See for example
\cite{Heijnen}, \cite{Jaffe}, \cite{Martin}, \cite{Simonis},
\cite{SStufken}.] Another recent paper dealing with mixed codes is \cite{EG93}.

Our interest in product schemes in the present context
stems from the fact that the set of
mixed binary/ternary vectors with $n_2$ binary and $n_3$ ternary
coordinate positions does not in general form an
association scheme with respect to Hamming distance,
and so Delsarte's linear programming bound cannot be directly
applied there.  This was a source of worry to the fourth author
for many years.  However, this set does have the
structure of a product scheme, and so a version of the
linear programming bound can be obtained for both designs
(cf. \cite{SStufken}) and codes.

The linear programming bound for codes in an arbitrary
association scheme can be briefly described as follows.
If $C$ (the code we want to study) is a nonempty subset of an association
scheme, we can define its {\em inner distribution} $a$ by
$a_i = | (C \times C) \cap R_i | / | C |$, the average number
of codewords at `distance' $i$ from a codeword.
Clearly, $a_0 = 1$ (if $R_0$ is the identity relation),
and $\sum a_i = |C|$.
A 1-line proof\footnote{Let $\chi$ be the characteristic vector of $C$. Then,
since $E_j$ is idempotent,
$$|C|(aQ)_j = |C|\sum_i a_i Q_{ij} = \sum_i Q_{ij} \chi^\top A_i \chi
= \chi^\top E_j \chi = || E_j \chi ||^2 \ge 0 .$$}
shows that one has $aQ \ge 0$
(that is, $(aQ)_j \ge 0$ for all $j$), and thus we obtain
the linear programming bound:
$$|C| \le \max ~\{ \sum a_i \mid a_0 = 1 {\rm ~ and ~} aQ \ge 0 \} .$$
The upper bound obtained this way will be referred to as the
`pure LP' bound. As we shall see, slightly better results can sometimes be
obtained by adding other inequalities that $a$ is known to satisfy.

\subsection{The Hamming scheme}

Of course, the usual Hamming scheme $H(n,q)$ also carries the structure
of a product scheme, for $n \ge 2$, and it is sometimes useful to study
non-mixed codes using this
product scheme setting, getting separate information on the
weights in the head and in the tail of the codewords, as in
the split weight enumerator of a code (cf. \cite[pp. 149--150]{McWS}).

Consider the Hamming scheme $H(m+n,q)$ as being obtained from the
product of $H(m,q)$ and $H(n,q)$ by merging all relations $R_{i',i''}$
with $i'+i'' = i$ into one relation $R_i$. We have
$A_i = \sum_{i'+i''=i} A_{i'i''}$,
$E_i = \sum_{i'+i''=i} E_{i'i''}$ and
$Q_{ij} = \sum_{j'+j''=j} Q_{i'j'} Q_{i''j''}$ for any pair $(i',i'')$ with $i' + i'' = i$.
Indeed, the first holds by definition, the second follows from the
third, and the third follows as soon as we have shown that the right
hand side does not depend on the choice of the pair $(i',i'')$.
But that follows by viewing all three association schemes involved
as merged versions of powers of $H(1,q)$: we must show that
$Q_{i j} = \sum_{{\rm wt}({\bf j}) = j} Q_{i_1j_1} Q_{i_2j_2} ...$ for
any 0-1 vector ${\bf i}$ with ${\rm wt}({\bf i}) = i$. However,
since such vectors
${\bf i}$ are equivalent under the symmetric group on the coordinates,
the right hand side is independent of ${\bf i}$, and the equality follows.

Here we did not need to actually compute the $Q_{ij}$, but since
in $H(1,q)$ we have $Q = \left( \begin{array}{cc}
1 & q-1 \\
1 & -1
\end{array} \right)$, it follows immediately that in $H(n,q)$
$$Q_{ij} = \sum_{r+s = j} (-1)^r (q-1)^s {i \choose r} {n-i \choose s} .$$

The `detailed' linear programming bound obtained in the above manner
always implies the `ordinary' linear programming bound:
given any solution $a$ of the detailed system
$\sum a_{i'i''} Q_{i'j'} Q_{i''j''} \ge 0$ for all $j',j''$
it follows by summing over the pairs $(j',j'')$ with $j' + j'' = j$ that
$\sum a_i Q_{ij} \ge 0$, where of course $a_i = \sum_{i'+i''=i} a_{i'i''}$.

Conversely, given any solution $a$ of the ordinary system
$\sum a_i Q_{ij} \ge 0$, we find a solution of the detailed system
by letting $a_{i'i''} = a_i {m \choose i'} {n \choose i''}/{m+n \choose i}$
for $i = i' + i''$. Indeed, this follows if we again go `to the bottom',
express everything in terms of $H(1,q)$, and use the symmetric group
on the coordinates.

Thus the two systems are equivalent over ${\bf R}$. However, the detailed
system can be useful (i) if it is known that the $a_i$ are integral,
e.g. because $C$ is linear, or (ii) when one can add further
constraints, e.g. because one has information on a residual code.
Jaffe \cite{Jaffe} has recently obtained a number of
new bounds for binary linear codes by recursive applications of this approach.


\section{Comparison with earlier results and the case $d = 3$}
\label{compar}
\subsection{Counting}

In the final section we give tables of upper and lower bounds for codes
in the mixed binary/ternary scheme.
A table with upper bounds was given in Van Lint jr. \& Van Wee \cite{vLvW}.
Pure linear programming agrees with or improves all the values in
their table with four exceptions, namely the parameter sets
$(n_2,n_3,d) = (3,6,3)$, $(5,5,3)$, $(7,6,3)$, $(8,4,3)$,
where \cite{vLvW} gives 345, 465, 4515, 1184, while the pure LP bound
yields the upper bounds 356, 469, 4560, 1209, respectively.
The upper bound used in these cases in \cite{vLvW}
is due to Van Wee \cite[Theorem 17]{vW},
and states that if $d = 3$, $n_2 = b$ and $n_3 = t$, then
$|C| \le 2^b 3^t / (|{\rm ball}| + \varepsilon)$, where
$|{\rm ball}| = 2t+b+1$, and $\varepsilon = b/(2t+b)$ if $b$ is even
or $\varepsilon = 2t/(2t+b-1)$ if $b$ is odd.\footnote{Gerhard van Wee
has pointed out to us that there is a typographical error
in the statement of this bound in Theorem 17 of \cite{vW}.
The bound given here (which follows at once
from Theorem 9 of \cite{vLvW}) is the correct version.}
In fact a stronger result is true:

\begin{Proposition}
\label{bigsphere}
If $b > 0$, and $b$ is even or $t > 0$, then
$N(b,t,3) \le 2^b 3^t / (2t+b+2)$.
\end{Proposition}

\Proof
Let $C$ be a $(b,t,3)_N$ code.
Count paths $(u,v,w)$ with $d(u,v) = d(v,w) = 1$,
$d(u,C) = 2$, $w \in C$, where $v-w$ is nonzero
at a binary coordinate position if $b$ is even,
and at a ternary coordinate position if $b$ is odd.
Put $a := b$ if $b$ is even, and $a := 2t$ if $b$ is odd.
For $w$ we have $N$ choices; given $w$ there are $a$ choices
for $v$; given $w$ and $v$ there is at least one choice for $u$.
The number of paths is therefore at least $Na$.
On the other hand, there are at most
$2^b 3^t - N(2t+b+1)$ choices for $u$, and given $u$ there are
at most $a$ choices for $(v,w)$, so
the number of paths is at most $(2^b 3^t - N(2t+b+1))a$.
\qed

In the four cases mentioned, this yields the bounds
343, 457, 4443, 1152, respectively. We shall see below
(in Proposition \ref{bsequality}) that the last mentioned
bound in fact holds with equality.

\subsection{Linear programming with additional inequalities}

The preceding results were obtained by studying what happens
close to the code. In general one should
obtain at least as strong results by adding analogous constraints on the
$A_{i,j}$ with small $i+j$ to the linear program (note that we change
notation here from what is usual in association scheme theory
to what is common in coding theory, and write $A_{i,j}$ where
the previous section had $a_{i,j}$).

What are the obvious inequalities to add when $d = 3$?
Well, no two words of weight 3 can agree in two nonzero coordinates,
so we have a packing problem for triples in a $(b+2t)$-set, with
a prespecified matching of size $t$, where the triples may not
cover any edge of the matching. The extra inequalities are found
by counting triples, point--triple incidences, and pair--triple incidences.
Starting with the latter, there are ${b \choose 2}$ pairs in the binary set,
$2t(t-1)$ available pairs in the ternary set, and $2bt$ pairs between
the two sets. This yields the inequalities
$$3A_{3,0} + A_{2,1} \le b(b-1)/2 ,$$
$$2A_{2,1} + 2A_{1,2} \le 2bt ,$$
$$A_{1,2} + 3A_{0,3} \le 2t(t-1) .$$
Next, counting point--triple incidences, we find
$$3A_{3,0} + 2A_{2,1} + A_{1,2} \le b \lfloor (2t+b-1)/2 \rfloor ,$$
$$A_{2,1} + 2A_{1,2} + 3A_{0,3} \le 2t \lfloor (2t+b-2)/2 \rfloor .$$
Finally, counting triples, we obtain
$$A_{3,0} + A_{2,1} + A_{1,2} + A_{0,3} \le \lfloor ((2t+b)(2t+b-1) - 2t
- b\varepsilon_b -2t\varepsilon_t)/6 \rfloor$$
where $\varepsilon_b, \varepsilon_t \in \{0,1\}$ with
$\varepsilon_b = (2t+b-1) \bmod 2$ and $\varepsilon_t = (2t+b-2) \bmod 2$.
Of course, the last three inequalities only contribute when
rounding down occurs.

As a test case, let us compute the improved LP bound in the four
cases mentioned above. We find 347, 459, 4491, 1178, respectively.
This improves the pure LP bound (of course), and three of the four
bounds from \cite{vLvW}. However, Proposition \ref{bigsphere}
is stronger --- it really encodes information about distance 4,
and we would have to add inequalities involving $A_{i,j}$ with $i+j=4$
to approach or beat it.

Precisely the same ideas work for larger $d$. We have
$$\sum_{i=0}^d {i \choose j } {d-i \choose r-j } A_{i,d-i} \le
2^{r-j} {n_2 \choose j} {n_3 \choose r-j} N(n_2-j, n_3-r+j,d-r,d) ,$$
for $0 \le r \le d$ and all $j$, where
$N(b,t,w,d)$ is the maximal number of words of constant weight $w$
and mutual distance $d$ with $b$ binary and $t$ ternary coordinates.
A bound for $N(b,t,w,d)$ can be computed from the starting values
$$N(b,t,w,d) \le \left\{ \begin{array}{ll}
1 & \mbox{if $d > 2w,$} \\
\lfloor (b+t)/w \rfloor & \mbox{if $d = 2w,$} \\
\end{array} \right.$$
and the induction
$$N(b,t,w,d) \le \lfloor (b N(b-1,t,w-1,d) + 2t N(b,t-1,w-1,d))/w \rfloor$$
(if $w > 0$). (The inequalities given earlier for $d = 3$ are special cases
of those obtained here.)
Occasionally also
$$N(b,t,w,d) \le \lfloor (b N(b-1,t,w,d) + t N(b,t-1,w,d))/(b+t-w) \rfloor$$
(if $w < b+t$) might be useful.

\subsection{Further inequalities}

The inequalities discussed above described constraints
on what happens close to a given codeword.
We can also add constraints on the words that differ from
a given word in (almost) all binary and/or ternary coordinates.
First of all we have

$$\sum_{i+j \le e} A_{n_2-i,j} \le 1 , \eqno (L2)$$
where $e = \lfloor (d-1)/2 \rfloor$.

\medskip
For a property $P$,
let $\delta(P) = 1$ if $P$ holds, and $\delta(P) = 0$ otherwise.
If $d = n_3+1 > 2$ and $n_2 > 1$, we have
$$A_{n_2-1,n_3} \le \left\{ \begin{array}{ll}
1 & \mbox{if $A_{n_2,n_3} = 1$,} \\
\min(n_2,1+\delta(d \le 3)) & \mbox{if $A_{n_2,n_3-1} = 1$,} \\
\min(n_2,2+2\delta(d \le 4)) & \mbox{if $A_{n_2,n_3} = A_{n_2,n_3-1} = 0$.}
\end{array} \right.$$
This can be captured in one inequality:
$$(m_2-1)A_{n_2,n_3} + (m_2-m_1)A_{n_2,n_3-1} + A_{n_2-1,n_3} \le m_2 \eqno (L4)$$
where $m_1, m_2$ are the above minima.

\medskip
If $d = n_3+1$ and $n_2 > n_3 > 1$, then we have
$$A_{n_2-1,n_3-1} \le \left\{ \begin{array}{ll}
n_3 & \mbox{if $A_{n_2,n_3} = 1$,} \\
\min(n_2,2n_3) & \mbox{if $A_{n_2,n_3} = 0$.}
\end{array} \right.$$
This can be captured in one inequality:
$$(m-n_3)A_{n_2,n_3} + A_{n_2-1,n_3-1} \le m
 \eqno (L5)$$
where $m$ is the above minimum.

\medskip
Known bounds on $A_2(n,d)$ (the maximal size of a binary
code of length $n$ and minimum distance $d$) can be used:
$$A_{0,n_3} \le A_2(n_3,d) \mbox{~~and~~} A_{n_2,n_3} \le A_2(n_3,d) .
 \eqno (L6)$$

\medskip
More precise information about $A_{0,n_3}$ and $A_{0,n_3-1}$ can sometimes be
obtained using Plotkin's argument (cf. \cite[Chapter 2]{McWS},
\cite{Mack} and Proposition \ref{plotkin} below).
Instead of presenting the somewhat
messy general details, we give here only the extra inequality used to show
$N(0,11,7) \le 50$, which is
$$A_{0,11} + \frac{4}{11} A_{0,10} \le 4 . \eqno (L7)$$
Suppose there are $r$ words of weight $(0,n_3)$ and $s$ words of weight
$(0,n_3-1)$, and write $t = r+s$.
The sum of all distances between these $t$ words is at least ${t \choose 2}d$.
On the other hand, each column (coordinate position) without a 0
contributes at most
$\lfloor {t \over 2} \rfloor . \lceil {t \over 2} \rceil$,
and each 0 adds at most $\lceil {t \over 2} \rceil - 1$ to this
(namely when it is the only 0 in the column).
Thus we have ${t \choose 2}d \le
n_3 . \lfloor {t \over 2} \rfloor . \lceil {t \over 2} \rceil +
s (\lceil {t \over 2} \rceil - 1)$.
For each given $s$, this yields an upper bound on $t$ (when $2d-n_3 > 0$),
and $s$ itself is then bounded by $s \le t$ (when $2d-n_3 > 2$).
We now find an inequality $A_{0,n_3} + \alpha A_{0,n_3-1} \le \beta$
which is satisfied by all pairs $(r,s)$ found.
This argument can be sharpened a little by noticing that
if equality holds in this Plotkin bound, then every pair of codewords
are at the same distance apart.
This is impossible if $r \ge 3$ and $d$ is odd.

\medskip
Sometimes one can make use of the fact that $|C| A_{i,j}$ must be an integer.
For example, pure linear programming gives $N(1,7,3) \le 243$,
with an optimal solution that mentions $A_{0,4} = 34.5$.
However, if $|C| = 243$, then either $A_{0,4} \le 8383/243 = 34.497...$
or $A_{0,4} \ge 8384/243 = 34.502...$.
But in both cases adding the extra inequality to the program
gives $|C| < 243$.  It follows that $N(1,7,3) \le 242$.
See also Lemma \ref{perfect}.

\section{Further bounds}

It is easy to determine $N(n_2,n_3,d)$ for very small or very large $d$.
(We shall always assume that $n_2$ and $n_3$ are nonnegative, and that
$d$ is positive, and all three are integral.)

\begin{Proposition}
\label{easy}
(i) $N(b,t,1) = 2^b 3^t$.

(ii) $N(b,t,2) = \left\{ \begin{array}{ll}
1 & \mbox{if $b = t = 0$,}\\
2^{b-1} & \mbox{if $b > 0$, $t = 0$,}\\
2^b 3^{t-1} & \mbox{if $t > 0$.}
\end{array} \right.$ 

(iii) If $d > b+t$, then $N(b,t,d) = 1$.

(iv) $N(b,t,b+t) = \left\{ \begin{array}{ll}
2 & \mbox{if $b > 0$,} \\
3 & \mbox{if $b = 0$, $t > 0$.}
\end{array} \right.$

(v) $N(b,t,b+t-1) = \left\{ \begin{array}{ll}
2 & \mbox{if $b > 3$,} \\
3 & \mbox{if $b \le 3$ and $b + t/2 > 3$,} \\
\mbox{see table} & \mbox{otherwise.}
\end{array} \right.$

\center{$\begin{array}{c|ccccccc}
b \backslash t & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\
\hline
0 & - & - & 9 & 9 & 9 & 6 & 4 \\
1 & - & 6 & 6 & 6 & 4 \\
2 & 4 & 4 & 4 \\
3 & 4
\end{array}$}

\end{Proposition}

It is easy to give an explicit description of the codes achieving these bounds.

\medskip
Below we shall see that for very small codes the Plotkin bound describes
the situation completely. Let us state the Plotkin bound in our case.

\begin{Proposition}
\label{plotkin}
{\rm (`Plotkin bound')}
If $N(b,t,d) \ge M$, then
$$d {M \choose 2} \le b M_2^0 M_2^1 + t (M_3^0 M_3^1 + M_3^0 M_3^2 + M_3^1 M_3^2) ,$$
where $M_q^i = \lfloor (M+i)/q \rfloor$.
When equality holds, any $(b,t,d)_M$ code is equidistant.
\end{Proposition}

We omit the proof, which is analogous to that for the binary case.
(A slightly incorrect\footnote{For example, the bound in \cite{Mack}
gives $N(0,6,5) \le 3$, whereas in fact $N(0,6,5) = 4$.}
version of this bound for pure ternary codes was given in \cite{Mack}.)

Given a code, there are various obvious ways of deriving other codes
from it.

\begin{Proposition}
\label{deriv}
For nonnegative $b$ and $t$ we have:

(i) $N(b,t,d) \le N(b+1,t,d)$.

(ii) $N(b+1,t,d) \le 2N(b,t,d)$.

(iii) $N(b+1,t,d) \le N(b,t+1,d)$.

(iv) $N(b,t+1,d) \le (3/2)N(b+1,t,d)$.

(v) $N(b,t+1,d) \le N(b+2,t,d)$.

(vi) $N(b,t+1,d) \le N(b,t,d-1)$ and $N(b+1,t,d) \le N(b,t,d-1)$.

\end{Proposition}

(The inequalities $N(b,t,d) \le N(b,t+1,d)$ and $N(b,t+1,d) \le 3N(b,t,d)$
follow from (i),(iii) and (ii),(iv), respectively.)

\medskip
We know precisely where the very small values of $N(b,t,d)$ will occur.

\begin{Proposition}
\label{prop1234}
(i) $N(b,t,d) = 1$ precisely when $b+t < d$.

(ii) $N(b,t,d) = 2$ precisely when $\frac{2}{3}b + t < d \le b+t$.

(iii) $N(b,t,d) = 3$ precisely when $(4b+5t)/6 < d \le \frac{2}{3}b + t$.

(iv) $N(b,t,d) = 4$ precisely when $(3b+4t)/5 < d \le (4b+5t)/6$
or $(b,t,d) = (2+10j,0,1+6j)$ or $(b,t,d) = (2+5j,1,2+3j)$ or
$(b,t,d) = (9+10j,2,7+6j)$ for some $j \ge 0$.

(v) In all other cases $N(b,t,d) \ge 6$.
\end{Proposition}
\Proof
The upper bounds follow from the Plotkin bound,
the lower bounds from juxtaposition (see below).
All the necessary ingredients for making these codes exist, except in the
explicitly listed cases under (iv), where we cannot find codes of size 5 or 6,
even though the Plotkin bound would permit them.
Why are these codes impossible?
In the cases $(b,t,d) = (2+5j,1,2+3j)$ and $(b,t,d) = (9+10j,2,7+6j)$
a code of size 5 or 6 would have equality in the Plotkin bound,
hence would be equidistant. Since $\lceil 5 \times 4 / 9 \rceil = 3$,
we can make the ternary coordinate positions binary by selecting a
subcode of size at least 3. But in a binary Hamming space an
equilateral triangle has an even side. This eliminates $(b,t,d) = (9+10j,2,7+6j)$
and $(b,t,d) = (7+10j,1,5+6j)$. The case $(b,t,d) = (2+10j,1,2+6j)$
does not occur since shortening would yield a $(b,t,d) = (2+10j,0,1+6j)$ code.
In this latter code, at most two distances differ from $1+6j$, so we can
again throw out two codewords and obtain an equilateral triangle of odd
side. \qed

Sometimes it is possible to show that a code cannot be obtained
by truncation (as in Proposition \ref{deriv} (vi)).
For example, if a code of minimum distance $d-1$ is obtained by
removal of a binary (ternary) coordinate position in a code of
minimum distance $d$, then the distance-$(d-1)$ graph on its
codewords does not contain a triangle ($K_4$, respectively).
In the Lemma below an integrality argument is used.
First we need some preparation.

The following result may be well-known. The proof is almost identical
to the proofs for the binary case in \cite{BB}.

\begin{Proposition}
Let $q | n$. Any $q$-ary 1-error-correcting code of
length $n$ has size at most $q^n/(n(q-1)+q)$, and the
inner distribution of any code meeting this bound is uniquely
determined. In particular, this holds for any code with the
parameters of the singly shortened perfect $q$-ary Hamming code.
\end{Proposition}
\Proof
For the $q$-ary Hamming scheme of length $n$ we have
$P_{i0} = 1$, $P_{i1} = n(q-1) - qi$ and
$P_{i2} = (q-1)^2 {n \choose 2} - \frac{1}{2}qi[q(2n-1)-2n+2] +
\frac{1}{2} i^2 q^2$. Assume that $q | n$. Then
$2 P_{i2} + 2(q-1)P_{i1} + (q-1)nP_{i0} =
(qi-(q-1)n-q)(qi-(q-1)n) \ge 0$.
Now let $C$ be a $q$-ary code of length $n$, minimum distance 3,
and size $M$, and with inner distribution $a$.
Let $u^\top = (n(q-1),2(q-1),2,0,...,0)$. Then, since $PQ = q^n I$
and $(aQ)_0 = M$, we find
$n(q-1)q^n = aQPu \ge Mn(q-1)(n(q-1)+q)$, so that
$M \le q^n/(n(q-1)+q)$. If equality holds, then $(aQ)_j = 0$ for
$j \ne 0, (q-1)n/q-1, (q-1)n/q$, and hence, by \cite[Corollary 3.1]{BB},
the inner distribution $a$ is uniquely determined.
\qed

\begin{Lemma}
\label{perfect}
$N(0,13,4) < 3^9$.
\end{Lemma}
\Proof
We prove more generally that no ternary code with the parameters
of a singly shortened Hamming code of word length $n$, where
$n = \pm 2 \bmod 5$, is the truncation of a distance-4 ternary code.

By the above proposition, and \cite[Theorem 4.2.5]{BB}, it follows
that the inner distribution of any $(0,13,4)_M$ code with $M = 3^9$
is uniquely determined.
Doing the computation, we find $A_5 = n(n-1)(n-4)(n-5)/30$.
But then $M A_5$ is not an integer, contradiction. \qed

Finally, the following special upper bound follows from
an argument mostly due to Mario Szegedy (personal communication).

\begin{Lemma}
\label{szegedy}
$N(0,7,4) \le 46$.
\end{Lemma}
\Proof
Let $C$ be a $(0,7,4)_M$ code, and construct a bipartite
graph with two sets of nodes, one set labeled $\{ c \mid c \in C \}$ and
the other labeled $\{u \mid u \in U = \Ff_3^5 \}$.
To each node $c \in C$ we associate the set $N_c$ consisting
of the 84 vectors in $V = \Ff_3^7$ at distance exactly 2 from $c$,
and to each $u$ we associate the set $S_u$ consisting
of the nine vectors $u\alpha\beta \in V$ with $\alpha, \beta \in \Ff_3$.
We also define three kinds of edges: $c = v \alpha \beta \in C$ (with
$v \in U$ and $\alpha, \beta \in \Ff_3$) is joined to $u$
by a blue edge if $u = v$,
by a red edge if $d_H (u,v) = 1$ and
by a white edge if $d_H (u,v) = 2$.
Then $| N_c \cap S_u |$ is 4, 4 or 1 in the three cases.
It is easy to see that:
(i) each node $c$ is incident with exactly one blue edge, 10 red edges
and 40 white edges;
(ii) the possibilities for blue and red
edges meeting $u$ are just the following:
one blue edge and no red edges (there are exactly $M$ such nodes $u$),
no blue edges and 0, 1, 2 or 3 red edges (we denote the numbers of such nodes
by $t_0$, $t_1$, $t_2$, $t_3$ respectively).
Let there be $n_B$, $n_R$ and $n_W$ blue, red and white edges, respectively.

We will evaluate the sum
$$4n_B + 4n_R + n_W = \sum_{c \in C, u \in U} | N_c \cap S_u |$$
in two ways. On the one hand, each $c \in C$ contributes 84, so that
the sum is equal to $84M$. On the other hand, let us group the terms
in the sum according to the number of blue and red edges meeting $u$.
A small clique-finding program shows that in the five cases mentioned,
there are at most 8, 13, 12, 8, 6 white edges at $u$.
[We may take $u = {\bf 0}$. Let $W$ be the set of vectors
$w \alpha \beta$ where $w$ has weight 2. (These are the words that
will get a white edge to $u$ if they are in $C$.)
If $u$ meets a blue edge, we may assume that ${\bf 0} \in C$.
Otherwise, if $u$ meets $i$ red edges, we may assume that the
first $i$ of 1000000, 0100011, 0010022 are in $C$.
Now find the largest subset of $W$ with all mutual distances,
and all distances to the known codewords at least 4.]
This means that in the five cases mentioned, the sum
$s_u = \sum_{c \in C} | N_c \cap S_u |$
is at most $4+8$, $13$, $4+12$, $4+4+8$, $4+4+4+6$.
We can also compute the total contribution of all vectors $u$
incident with a blue edge in a different way. These vectors $u$
contribute $4M$ plus the number of pairs (white edge, blue edge)
incident on the points of $U$. This latter number equals the number
of ordered pairs of code words $(u \alpha \beta, v \gamma \delta)$
with $d_H(u,v) = 2$. And this equals the number of unordered pairs
of red edges incident on the points of $U$, that is, $t_2 + 3t_3$.

Altogether we have found the following system of (in)equalities:
\begin{eqnarray*}
M + t_0 + t_1 + t_2 + t_3 & = & 243 \\
t_1 + 2t_2 + 3t_3 & = & 10M \\
4M + t_2 + 3t_3 & \le & 12M \\
4M + 13t_0 + 16t_1 + 17t_2 + 21t_3 & \ge & 84M
\end{eqnarray*}
Combining these with coefficients $-18$, $2$, $-3$, $1$ yields
$$-5t_0 \ge 94M - 4374$$
so that $M \le 4374/94 < 47$. \qed


\section{Constructions}

\subsection{Juxtaposition}
\label{juxta}
Let $\pi_C = \{ C_i \mid 1 \le i \le m \}$ be a partition of
a code $C$, and $\pi_D = \{ D_j \mid 1 \le j \le n \}$
a partition of a code $D$.
Let $(C / \pi_C) | (D / \pi_D)$ denote the code consisting of all
codewords $(c_i | d_i)$ with $c_i \in C_i$ and $d_i \in D_i$,
for $i = 1,..., \min(m,n)$,
where here $|$ denotes concatenation (juxtaposition).
The size of this code is $\sum_{i=1}^{\min(m,n)} |C_i| . |D_i|$
(which is equal to $|C| . |D_j|$ if all $D_j$ have the same size
and $n \ge m$).
Its minimum distance is at least
$\min ~\{~ d_C + d_D, d_{C_i}, d_{D_i} \mid 1 \le i \le \min(m,n) \}$
(where of course $d_Z$ denotes the minimum distance of a code $Z$).
This construction is indicated by $jb$ in the tables below.
(It is essentially Construction X4 of \cite[p. 584]{McWS}.)

The partition $\pi_C$ of $C$ will often be a partition into
translates of a subcode $E$ of $C$. In this case we write
$C/E$ instead of $C/\pi_C$.

Let $(n_2,n_3,d)_M$ denote a mixed code with $n_2$
binary and $n_3$ ternary coordinates, minimum distance $d$ and
$M$ codewords.
Let $[n,k,d]_q$ denote a $q$-ary linear code of length $n$,
dimension $k$ and minimum distance $d$, where we omit $q$ if $q = 2$.

\medskip
The following are examples of the juxtaposition construction: \nlsp
(i) $N(3,3,3) \ge 18$ because of
$([3,3,1]/[3,1,3]) | ([3,2,2]_3/[3,1,3]_3)$. \nlsp
(ii) $N(4,2,4) \ge 6$ from
$([4,3,2]/[4,1,4]) | ([2,1,2]_3/[2,0,\infty]_3)$. \nlsp
(iii) $N(8,4,4) \ge 384$ from
$([8,7,2]/[8,4,4]) | ([4,3,2]_3/[4,1,4]_3)$. \nlsp
(iv) $N(9,4,4) \ge 540$ from
$([4,3,2]_3/[4,1,4]_3) | (D/\pi_D))$
where $\pi_D = \{ D_0 + u \mid u \in U \}$
for an even weight $(9,0,4)_{20}$ code\footnote{See \cite{Best},
\cite[p. 57]{McWS}, \cite[p. 140]{CS}.} $D_0$, where
$U$ is a set of nine even weight vectors with all pairwise distances 2
such as $\{ 0 \} \cup \{ e_1 + e_j \mid 2 \le j \le 9 \}$.\nlsp
(v) $N(8,6,4) \ge 2304$ (and hence $N(7,6,4) \ge 1152$).
Indeed, we construct $([8,7,2]/[8,4,4]) | (D/\pi_D)$
where $\pi_D = \{ D_0 + u \mid u \in U \}$
for some $(0,6,4)_{18}$ code $D_0$ contained in the zero-sum
$[6,5,2]_3$ ternary code $E$, where $U$ is a
set of at least eight vectors in $E$ with pairwise distance
at most 3. In fact it is easy to find a $U$ of size 11:
take $\{ 0 \} \cup \{ \pm (e_1 - e_j) \mid 2 \le j \le 6 \}$.
One way to construct $D_0$ is to take the 18 words of weight 6
in the hexacode given in \cite{CS}, p. 82, Eq. (64),
and rename the symbols (from $1,\omega,\bar{\omega}$ to $0,1,2$).
Then $D_0$ contains the three multiples of ${\bf 1}$,
and 15 words with symbol distribution $0^2 1^2 2^2$,
so that it is contained in $E$.
For later use we remark that $D_0$ is invariant under
translation by ${\bf 1}$ (since the hexacode is invariant
under multiplication by $\omega$), so that we have a partition
$(0,6,4)_{18}/(0,6,6)_3$.\nlsp
For further examples, see also Section \ref{zerosum} below.

\medskip
If $\pi_C$ is the partition into singletons, we write $C$
instead of $C / \pi_C$.
This construction is indicated by $jc$ in the tables.
(It is Construction X of \cite[p. 581]{McWS}.)
Examples:\nlsp
(i) $[3,2,2] | ((0,6,4)_{18}/(0,6,6)_3) = (3,6,6)_{12}$. \nlsp
(ii) $[4,3,2] | ((0,6,4)_{18}/(0,6,6)_3) = (4,6,6)_{18}$. \nlsp
(iii) $(1,3,3)_6 | ([8,4,4]/[8,1,8]) = (9,3,7)_{12}$. \nlsp
(iv) $(0,4,3)_9 | ([8,4,4]/[8,1,8]) = (8,4,7)_{16}$. \nlsp
(v) $(0,4,3)_9 | ((9,0,4)_{18}/(9,0,8)_2) = (9,4,7)_{18}$.
(There is a binary constant weight code with length 9, weight 4,
minimum distance 4 and size 18 (\cite{BSSS}); but any such code has
distance distribution $0^1 4^{12} 6^{4} 8^1$, and so can be partitioned
into $(9,0,8)_2$ codes.) \nlsp
(vi) $(0,2,2)_3 | ([12,4,6]/[12,2,8]) = (12,2,8)_{12}$. \nlsp
(vii) $(2,4,4)_8 | ([8,4,4]/[8,1,8]) = (10,4,8)_{16}$. \nlsp
(viii) $(0,5,4)_6 | ([8,4,4]/[8,1,8]) = (8,5,8)_{12}$.

\medskip
If $\pi_D$ is also the partition into singletons,
we have ordinary juxtaposition
(pasting two codes side by side, as in \cite[p. 49]{McWS}).
This construction is indicated by $j$ in the tables.
Its main use is the construction of codes of size 4 or 6
and large minimum distance (cf. Proposition \ref{prop1234}).
We do not list all applications.
Examples are:\nlsp
$(3,0,2)_4 | (3,0,2)_4 | (2,2,3)_4 = (8,2,7)_4$. \nlsp
$(1,3,3)_6 | (4,2,4)_6 = (5,5,7)_6$. \nlsp
$(10,0,6)_6 | (1,2,2)_6 = (11,2,8)_6$. \nlsp
$(0,5,4)_6 | (2,6,6)_6 = (2,11,10)_6$.

\medskip
Sometimes it is possible to adjoin further words after performing
the juxtaposition construction. The Steiner system $S(5,6,12)$
is a binary code of length 12, constant weight 6, minimum distance 4
and size 132.
It has a partition into six $(12,0,6)_{22}$ Hadamard codes.
So $(1,2,2)_6 | ((12,0,4)_{132}/(12,0,6)_{22}) = (13,2,6)_{132}$.
Adding ${\bf 0}$ and ${\bf 1}$ shows $N(13,2,6) \ge 134$.
If we shorten once or twice before adding ${\bf 0}$ and ${\bf 1}$,
we find $N(12,2,6) \ge 68$ (hence $N(12,1,5) \ge 68$)
and $N(11,2,6) \ge 38$. (The $(1,2,2)_6$ code must not contain
000 or 111.)

To see why this partition of the Steiner system exists, we remark that
the extended ternary Golay code has 24 words of weight 12, and
if we normalize so that ${\bf 1}$ and ${\bf 2}$ are in the code,
then the other 22 words form a Hadamard code. Adding ${\bf 1}$
we see that the places where these 22 words take a fixed value
are the supports of codewords of weight 6, that is, belong to $S(5,6,12)$.
This produces one Hadamard code inside $S(5,6,12)$. Its stabilizer in
$M_{12}$ is $2 \times M_{11}$, of index 6, so we find six pairwise
disjoint copies.

\subsection{Partitions of zero-sum codes}
\label{zerosum}
As a special case of the juxtaposition construction, suppose
$C$ is an $(n_2,n_3,2)_M$ code with a partition $\pi_C$ into 8 parts,
each with minimum distance (at least) 3.
Then $(C/\pi_C)|([7,7,1]/[7,4,3])$ is an $(n_2+7,n_3,3)_{16M}$ code.
In this way we find $N(7,5,3) \ge 1296$,
$N(9,4,3) \ge 1728$, $N(8,5,3) \ge 2544$ and $N(7,6,3) \ge 3792$
using $(0,5,2)_{81}$, $(2,4,2)_{108}$, $(1,5,2)_{159}$ and $(0,6,2)_{237}$
codes $C$ with appropriate partitions.

Motivated by this construction, we investigate distance-2 codes
and their partitions into distance-3 codes. As a consequence we will show that
$N(1,6,4) = 33$, $N(2,6,3) \ge 134$,
$N(2,7,3) \ge 396$ and $N(4,6,3) \ge 486$.

\begin{Lemma}
Let $t \ge 1$. There is (up to translation and sign change at
some coordinate positions) a unique $(0,t,2)_M$ code $C$ with
$M = N(0,t,2) = 3^{t-1}$, namely the code consisting of the
words with zero coordinate sum.
(In other words, any $(0,t,2)_M$ code $C$ is of the form
$C = \{ u \in \Ff_3^t \mid u \cdot c = \gamma \}$ for some `parity check'
vector $c \in \{1,2\}^t$ and $\gamma \in \Ff_3$.)
\end{Lemma}
\Proof
Induction on $t$. For $t = 1$ the statement is obvious.
Assume $t > 1$. By induction we may assume that the subcode of
$C$ consisting of the words ending in 0 is a zero-sum code.
If $a1 \in C$ and $d_H (a,b) = 1$ (for some $a,b \in \Ff_3^{t-1}$),
then precisely one of $b0$, $b1$, $b2$ occurs in $C$, but not $b1$,
and $b0$ only if $\sum b = 0$. Consequently, if $\sum a \ne 0$ and
$\sum b \ne 0$ and $d_H(a,b) = 1$ then $a1 \in C$ if and only if
$b2 \in C$. But the distance-1 graph on the non-zerosum vectors
in $\Ff_3^{t-1}$ is connected, so a single choice determines
all of $C$. By a sign change in the last coordinate, if necessary,
we can force one zero-sum vector that ends in 1 or 2, and then $C$ is
the zero-sum code. \qed

\noindent
For optimal $(b,t,2)$ codes with $b > 0$ the classification
is much more messy, and we shall not try to write down the details.

Parts of a partition of an optimal $(0,t,2)$ code into distance-3 codes
are often smaller than arbitrary $(0,t,3)$ codes.
Indeed, contrast $N(0,4,3) = 9$, $N(0,5,3) = 18$, $N(0,6,3) \ge 38$
with the following result.

\begin{Lemma}

(i) Any zero-sum $(0,4,3)_M$ code has $M \le 4$, and there is
(up to coordinate permutation and translation by a zero-sum vector)
a unique optimal code, namely
$\{ 0000, 0111, 2220, 1122 \}$.

(ii) Any zero-sum $(0,5,3)_M$ code has $M \le 11$, and there is
a unique optimal code, namely
$\{ 00000, (01221)_5, (02112)_5 \}$,
where $(u)_5$ denotes the five codewords obtained from $u$
by cyclic coordinate permutations.

(iii) Any zero-sum $(0,6,3)_M$ code has $M \le 33$, and there is
a unique optimal code, namely
$\{ aaaaaa, a(abccb)_5 \mid \{a,b,c\} = \{0,1,2\} \}$.
\end{Lemma}

These codes can be found inside the ternary Golay code $G$:
let $a$ be a codeword of weight 5 with support $A$.
Pick the 33 words of $G$ that have weight at most 1 on $A$
and discard the coordinate positions in $A$ to get a zero-sum
$(0,6,3)_{33}$ code.
If $\bar{G}$ is the extended (self-dual) ternary Golay code,
and $1a \in \bar{G}$, then taking the 33 words of $\bar{G}$
that have weight at most 1 on $A$ and deleting the coordinate positions
in $A$ we get a $(1,6,4)_{33}$ code after arbitrarily changing
the check position in the three codewords where it is 0.
Consequently $N(1,6,4) \ge 33$. (In fact $N(1,6,4) = 33$,
since exhaustive search shows that $N(2,4,3) \le 22$.)

\begin{Lemma} $N(2,7,3) \ge 396$.
\end{Lemma}
\Proof
Let $U = \{ 000000, 2(00001)_5 \}$. Let $C$ be a zero-sum
$(0,6,3)_{33}$ code. Then the six translates $C + u$ for $u \in U$
are pairwise disjoint. Thus we can construct
$((2,1,1)_{12} / (2,1,3)_2) | ((0,6,2)_{198} / (0,6,3)_{33}) =
(2,7,3)_{396}$. \qed

\begin{Lemma} $N(2,6,3) \ge 134$.
\end{Lemma}
\Proof
Let $U = \{ 00000, (11112)_5 \}$. Let $C$ be a zero-sum
$(0,5,3)_{11}$ code. Then the six translates $C + u$ for $u \in U$
are pairwise disjoint. We can add the (non zero-sum) word
11111 to $C$ and obtain a partition $\pi$ of a $(0,5,2)_{67}$
code into six distance-3 codes. Now the required code is
constructed as
$((2,1,1)_{12} / (2,1,3)_2) | ((0,5,2)_{67} / \pi) = (2,6,3)_{134}$.
\qed

\begin{Lemma}
The $(0,5,2)_{81}$ zero-sum code has a partition into eight
distance-3 codes.
\end{Lemma}
\Proof
Take $C_0 = \{ 00000, (01221)_5, (02112)_5 \}$ of size 11,
and seven codes of size 10, namely
$C_1 = \{ (00012)_5, (02211)_5 \}$,
$C_2 = \{ (00021)_5, (01122)_5 \}$,
$C_3 = \{ 00111, 00222, 11010, 22020, 11121, 22212, 12102, 21201,
10200, 02010 \}$,
$C_{3+j} = \sigma^j C_3$ $(j = 0,1,2,3,4)$ where $\sigma$ is
the cyclic coordinate permutation.
\qed

\noindent
As a consequence we find $N(7,5,3) \ge 1296$, as announced.

\begin{Lemma} $N(4,6,3) \ge 486$.
\end{Lemma}
\Proof
Let $\pi$ be the partition constructed in the previous lemma.
Then $((4,1,1)_{48}/(4,1,3)_6) | ((0,5,2)_{81} / \pi) =
(4,6,3)_{486}$. Note that the former ingredient exists:
we can construct $(4,1,3)_6$ as $([4,3,2]/[4,1,4])|(0,1,1)_3$,
and then use translates by the eight coset leaders of $[4,1,4]$.
\qed

We have not found a partition of the $(0,6,2)_{243}$ zero-sum code
into eight distance-3 codes, but can come close.
First notice that a partition of a zero-sum $(0,6,2)_{3M}$ code
into distance-3 codes that are invariant under translation by ${\bf 1}$
is equivalent to a partition of a zero-sum $(0,5,2)_M$ code
into codes in which the distances 2 and 5 do not occur.

Thus we find a partition of a zero-sum $(0,6,2)_{237}$ code from\nlsp

\noindent
{\scriptsize
\{
\{00111, 00222, 01002, 02010, 10200, 11211, 12021, 12102, 20001, 21120, 22212\},~
\{00102, 00210, 01020, 02121, 10011, 11112, 12000, 12222, 20022, 21201, 22110\},~
\{00120, 01200, 02001, 02112, 10101, 11022, 12210, 20010, 20202, 21111, 22221\},~
\{00000, 01122, 02211, 10221, 12012, 12120, 20112, 21021, 21210, 22101\},~
\{00021, 01110, 02202, 10122, 11001, 11220, 12111, 20100, 21012, 22020\},~
\{01212, 02022, 02100, 10002, 11010, 11121, 12201, 20220, 21102, 22011\},~
\{00201, 01011, 10020, 10212, 11100, 20121, 21222, 22002\},~
\{00012, 01101, 02220, 10110, 11202, 20211, 21000, 22122\}
\}.

}

\smallskip
\noindent
As a consequence we find $N(7,6,3) \ge 3792$.

Shortening this yields a good partition of a $(1,5,2)_{158}$ code.
An explicit code does slightly better. The code below is a good
partition of a $(1,5,2)_{159}$ code, and if we delete the words
that have a 2 at the second position, we obtain a good partition
of a $(2,4,2)_{108}$ code. (This last one is optimal: $N(2,4,2) = 108$.)
As a consequence we find $N(8,5,3) \ge 2544$ and $N(9,4,3) \ge 1728$.\nlsp

\noindent
{\scriptsize
\{
\{000122, 001100, 001211, 002021, 010010, 011222, 012101, 020201, 021002, 022112,
  022220, 100001, 100220, 101012, 102110, 110102, 111200, 112022, 112211, 120212,
  121121, 122000\},~
\{000002, 000110, 001121, 002201, 010220, 011000, 012011, 012122, 020021, 021212,
  022100, 100211, 101102, 102020, 111110, 111221, 112202, 120122, 120200, 121001,
  122111\},~
\{000101, 001112, 002000, 002222, 010202, 011021, 012110, 020012, 020120, 021200,
  022211, 100022, 101120, 101201, 102011, 110000, 110111, 111212, 112220, 120221,
  121010\},~
\{000020, 000212, 001001, 010121, 011012, 012200, 020102, 021110, 021221, 022022,
  100100, 101210, 102002, 102221, 110222, 111020, 111101, 112112, 120011, 121202,
  122120\},~
\{000011, 001220, 002102, 010022, 010100, 011111, 012212, 020210, 021122, 022001,
  100112, 101021, 102200, 110201, 111002, 112010, 112121, 120020, 121100, 122222\},~
\{000221, 001022, 002210, 010112, 011120, 011201, 012002, 021011, 022121, 100202,
  101000, 101111, 102122, 110021, 110210, 112100, 120101, 121220, 122012\},~
\{000200, 002012, 002120, 010001, 011102, 011210, 012221, 020111, 021020, 022202,
  100010, 101222, 102101, 110120, 111011, 120002, 121112, 122021, 122210\},~
\{001010, 001202, 002111, 010211, 012020, 020000, 020222, 021101, 100121, 102212,
  110012, 111122, 112001, 120110, 121211, 122102\}
\}.

}

\subsection{The $(u,u+v)$ construction}
Given two codes $U$ and $V$, consider the code $C$ whose
codewords are $(u,u+v)$, for $u \in U$, $v \in V$.
(Here $+$ must act coordinatewise, and satisfy $a+0=0+a=a$,
and $a+b \ne a+c$ when $b \ne c$. In particular, there is no
problem adding binary and ternary coordinates -- just view them
all as ternary coordinates.)
By calculating the parameters of the resulting code
(cf. \cite[p. 76]{McWS}) we obtain:

\begin{Proposition}
\label{uuplusv}
$N(b,t,d) \ge N(b_1,t_1,d_1) N(b_2,t_2,d_2)$ for
$d = \min(2d_1,d_2)$,
$b+t = b_1+t_1 + \max(b_1+t_1,b_2+t_2)$ and
$t = t_1 + \max(t_1,t_2)$.
\end{Proposition}

\noindent
For example, $N(1,12,4) \ge N(0,6,2) N(1,6,4) \ge 3^5 . 33 = 8019$.

\medskip
There are similar constructions that combine more than two codes.
For example, given three mixed binary/ternary codes $U$, $V$, $W$,
consider the code $C$ whose
codewords are $(u,u-v,(u+v)+w)$, where the coordinate positions
that $U$ and $V$ have in common are interpreted as ternary coordinates.
We obtain

\begin{Proposition}
\label{uvw}
$N(b,t,d) \ge N(b_1,t_1,d_1) N(b_2,t_2,d_2) N(b_3,t_3,d_3)$ for
$d = \min(3d_1,2d_2,d_3)$,
$b+t = b_1+t_1 + m + \max(m,b_3+t_3)$ and
$t = t_1 + \max(t_1,t_2) + \max(t_1,t_2,t_3)$,
where $m = \max(b_1+t_1,b_2+t_2,b_1+b_2+\min(t_1,t_2))$.
\end{Proposition}

If $d$ is not even, or not a multiple of 3, then small
modifications are slightly more efficient. For example, we find
$N(0,16,3) \ge N(0,5,1) N(0,6,2) N(0,5,3) = 3^5 . 3^5 . 18 = 1062882$
by taking $(u,u-v,u+v+w,v_0)$ for $u \in U$, $vv_0 \in V$, $w \in W$.
(Giving the two copies of $V$ a common coordinate position results in
$2d_2-1$ instead of $2d_2$ in the expression for the minimum distance.)

\subsection{Constructions from the binary Hamming code}
\label{binham}
The following result is useful for constructing codes with minimum
distance 3 or 4.

\begin{Proposition}
\label{binhamprop}
Let $C$ be an $(n_2,n_3,3)_M$ code and assume that
$u$ is a vector of weight $3$ on the binary coordinates
and weight $0$ on the ternary coordinates such that
$C = C+u$. Then we can construct an $(n_2-3,n_3+1,3)_N$ code $D$ with
$N \ge \frac{3}{8} M$ by taking three of the four patterns
$000$, $001$, $010$, $100$ on the support of $u$, and replacing
those by ternary symbols $0$, $1$, $2$.
\end{Proposition}

Since the binary $[15,11,3]$ Hamming code is perfect (and linear),
it is a good starting point for constructions.

The picture below shows the distribution of codewords in
the $[15,11,3]$ binary Hamming code $H$
with respect to five codewords $u_j$
($1 \le j \le 5$) of weight 3 with pairwise disjoint supports.
The rows are numbered from 0 to 5.
Each left son in row $j$ gives the number of codewords counted
by its father that have the pattern 000 on the support of $u_j$,
the right son gives the number of codewords with one of the
patterns 001, 010 or 100. Thus the entry for the father is
twice the sum of the entries for the sons.
For rows 1, 2, 3 the entries are determined because the positions
are independent, and all patterns occur equally often.
For rows 4 and 5 the zero entries are caused by the fact that $H$
has minimum distance 3, and they determine the remaining entries.
\smallskip
\begin{center}
\begin{tabular}{ccccccccccc}
& & & & & 2048 \\
& & & & 256 & & 768 \\
& & & 32 & & 96 & & 288 \\
& & 4 & & 12 & & 36 & & 108 \\
& 2 & & 0 & & 6 & & 12 & & 42 \\
1 & & 0 & & 0 & & 3 & & 3 & & 18
\end{tabular}
\end{center}

We now start with $H$ and repeatedly apply Proposition \ref{binhamprop},
obtaining codes showing that $N(12,1,3) \ge 768$, $N(9,2,3) \ge 288$,
$N(6,3,3) \ge 108$, $N(3,4,3) \ge 42$ and $N(0,5,3) \ge 18$.
That $N(3,4,3) \ge 42$ was shown earlier by Karl-G\"oran V\"alivaara.

\medskip
A similar construction can be used starting from the
$[16,11,4]$ extended binary Hamming code $\bar{H}$.
Let $u$ be a codeword of weight 4, and replace the four
binary coordinate positions in its support by two ternary
positions, replacing 1000, 0100, 0010, 1001, 0101, 0011
by 00, 11, 22, 01, 12, 20, respectively.
We see that $N(12,2,4) \ge \frac{6}{16} \times 2048 = 768$
so that $N(11,2,4) \ge 384$. (In fact equality holds in both
cases since $N(12,0,3) = 256$.)

\begin{Proposition}
\label{bsequality}
$N(8,4,3) = 1152$.
\end{Proposition}
\Proof
The upper bound follows from Proposition \ref{bigsphere}.
The lower bound can be established using the
juxtaposition construction $(C/\pi_C) | ([4,4,1]_3/[4,2,3]_3)$
where $\pi_C$ is a partition of the zero-sum $(8,0,2)_{128}$ code
into eight distance-3 codes. (Such a partition is equivalent to
a perfect 1-error-correcting code with one octal
coordinate, eight binary coordinates, and 128 codewords.)
The partition $\pi_C$ can be obtained using the construction
of Section \ref{zerosum} in reverse:
Let $S$ be the set of coordinate positions of $H$.
Fix a codeword $a$ of weight 8 in $H^{\perp}$,
and let $A$ be its support. We find the $(8,0,2)_{128}$ code $C$
by discarding the coordinate positions in $S \setminus A$.
The discarded tails of a codeword $c \in C$ form a coset
of the $[7,4,3]$ code $D$ formed by the codewords of $H$ with
support in $S \setminus A$, and we can define the partition
$\pi_C$ by letting the eight parts correspond to the eight
cosets of $D$. \qed


\subsection{Constructions from the ternary Golay code}
\label{tergol}
Most of the lower bounds for $d=5$ and $d=6$ are derived from
the $[12,6,6]_3$ extended ternary Golay code.
We saw in Section \ref{zerosum} how to obtain $N(1,6,4) \ge 33$
using this code.

\begin{Lemma} $N(6,6,6) \ge 66$, $N(8,4,6) \ge 32$ and $N(9,3,6) \ge 26$.
\end{Lemma}
\Proof
Take the $[12,6,6]_3$ extended ternary Golay code $\bar{G}$
and let $A$ be the support of some codeword of weight 6.
There are 3, 0, 6, 6, 18, 30, 66 codewords whose support meets
$A$ in a given subset of size 0, 1, 2, 3, 4, 5, 6 (respectively).
Taking the 66 codewords that do not vanish on $A$, we see
that $N(6,6,6) \ge 66$. If we pick two or three more positions outside $A$,
and require that the codewords do not vanish there either, we
find $N(8,4,6) \ge 32$ and $N(9,3,6) \ge 26$.
\qed

\begin{Lemma} $N(6,7,5) \ge 342$.
\end{Lemma}
\Proof
Take the $[11,6,5]_3$ ternary Golay code $G$.
In the last two coordinates replace each ternary digit by
two binary digits (e.g., replace 0, 1, 2 by 00, 01, 10).
Discard all words that have a 0 in either of the first
two coordinates. We now have a $(6,7,5)_{324}$ code $G'$.
There are precisely 36 words at distance 5 from $G'$
(all ending in $...1111$), forming four cosets of the subcode
$Z$ of $G$ consisting of the codewords that are 0 on the first
two and the last two coordinates.
The four cosets are permuted transitively by
the four-group generated by
multiplication by $-1$ and the element $\sigma$ of $M_{11}$
that interchanges the first two coordinates and fixes the last two,
so that there are three
different ways of taking the union of two cosets. These unions
have minimum distances 1, 4, 5 (corresponding to $-\sigma$, $-1$, $\sigma$,
respectively).
Taking this latter union together with $G'$ yields the
required code of size $342 = 324 + 18$.
\qed

\begin{Lemma} $N(7,6,5) \ge 234$.
\end{Lemma}
\Proof
Take the $[11,6,5]_3$ ternary Golay code $G$, chosen in
such a way that $c = 00011111100$ is a codeword.
In the last two coordinates replace each ternary digit by
two binary digits (e.g., replace 0, 1, 2 by 00, 01, 10).
Discard all words that have a 0 in one of the first
three coordinates. We now have a $(7,6,5)_{216}$ code $G''$.
There are precisely 54 words at distance 5 from $G''$
(all ending in $...1111$).
Inspection using a small clique--finding program shows
that there is a set of 18 (invariant under negation and
under translation by $c$) among these 54 that have mutual
distances at least 5. Adding these to $G''$ yields the
required code.
\qed

\subsection{Some cyclic codes}
\label{cyclic}
Let $C_1$ be the smallest length 13 ternary code which is invariant
under translation by {\bf 1} and under cyclic
coordinate permutations, and which contains the vector
0121122221121. Let $C_2 = -C_1$.
Both are equidistant $(0,13,8)_{39}$ codes, and $C_1 \cup C_2$
is a $(0,13,7)_{78}$ code.
If we now replace the first coordinate of all words in $C_1$
by 0 and in $C_2$ by 1, we get a code $C$ with minimum distance 7,
so $N(1,12,7) \ge 78$.

Let $C_3$ be the smallest code which is invariant under
negation and under translation by {\bf 1}, and contains
\{{\bf 0}, 001212010122, 001221122100, 010120201212, 012120012120\}.
Then $C_3$ is a $(0,12,7)_{27}$ code.

We construct a code proving that $N(0,13,7) \ge 105$ by taking $C$
and adding the words from $C_3$, each prefixed by a 2.

The code $C_1$ already improves the old bound $N(0,13,8) \ge 36$,
but we can do even better. Indeed, we find $N(0,13,8) \ge 42$ by
taking the smallest cyclic code containing
\{{\bf 0}, {\bf 1}, {\bf 2}, 0000122121221, 0021102220112,
0120220210121\}.

Similarly, we get $N(0,12,7) \ge 51$ from the smallest cyclic code containing
\{{\bf 0}, {\bf 1}, {\bf 2}, 000011202121, 001222102211,
002020121122, 002201110101\}.

Finally, one obtains $N(0,14,9) \ge 31$ from the smallest cyclic code
containing \{{\bf 0}, {\bf 1}, {\bf 2}, 00001122102121, 00222011102012\}.

\subsection{Constructions using a union of cosets}
\label{cosets}
We give the codes in humanly readable format, and
the coset leaders in compressed format: the binary
part in hexadecimal, the ternary part in base 9,
both right justified.
If the linear code is the direct sum of a binary part of dimension $b$
and a ternary part of dimension $t$, then we arrange the code
generators so that there is a binary identity matrix of order $b$
in front, and a ternary identity matrix of order $t$ at the back,
and the coset leaders are zero on these $b+t$ positions, so that
we need give only the remaining $n_2-b+n_3-t$ coordinates.

\medskip
{\footnotesize
(i) $N(11,2,3) \ge 832$.
Use 52 cosets of a 4-dimensional binary code.

\noindent
\smallskip
{\scriptsize
\begin{tabular}{c}
matrix\\
\hline
1000110000000\\
0100101100000\\
0010101010000\\
0001101001000\\
\end{tabular}
\begin{tabular}{l}
\multicolumn{1}{c}{cosets}\\
\hline
190, 240, 3F0, 420, 001, 271, 2A1, 311, 5D1, 6C1, 0B2, 172, 1C2, 2D2, 502, \\
612, 662, 7A2, 033, 143, 293, 2E3, 583, 653, 064, 0D4, 1A4, 3C4, 414, 6B4, \\
704, 774, 205, 365, 3B5, 475, 4A5, 086, 326, 356, 4F6, 7E6, 1F7, 447, 537, \\
627, 797, 058, 0E8, 238, 388, 498.
\end{tabular}}

\smallskip
(ii) $N(4,5,3) \ge 186$. This improves the bound $N(4,5,3) \ge 178$
found by Seppo Rankinen. Use 62 cosets of a 1-dimensional ternary code.

\noindent
\smallskip
{\scriptsize
\begin{tabular}{c}
matrix\\
\hline
000011001\\
\end{tabular}
\begin{tabular}{l}
\multicolumn{1}{c}{cosets}\\
\hline
900, 201, E02, A03, 104, D05, 406, F07, 010, B11, 712, 313, 814, 415, D16, \\
F20, 523, 826, 627, 328, 330, 831, 432, 033, B34, 735, E36, 537, 938, C40, \\
F43, 146, A47, 648, E51, 252, 653, D54, 155, B56, 057, C58, 560, C63, 367, \\
A68, A70, 171, D72, 973, 274, E75, 776, C77, 078, 781, 882, 484, B85, 286, \\
987, 588.
\end{tabular}}

\smallskip
(iii) $N(5,5,3) \ge 342$.
Use 57 cosets of the direct sum of a 1-dimensional ternary code
and a 1-dimensional binary code.

\noindent
\smallskip
{\scriptsize
\begin{tabular}{c}
matrix\\
\hline
0000011001\\
1111000000\\
\end{tabular}
\begin{tabular}{l}
\multicolumn{1}{c}{cosets}\\
\hline
700, A02, B04, 605, 006, D08, 410, 311, F12, E13, 814, 515, 916, 218, D20, \\
022, 124, C25, 626, B28, 830, F31, 332, 233, 434, 536, 937, E38, B40, 041, \\
C42, 143, D44, A47, 651, 955, F56, 458, 160, C61, D63, 065, A66, 768, 672, \\
773, A75, C76, 178, E80, 981, 582, 483, 284, F85, 386, 888.
\end{tabular}}

\smallskip
(iv) $N(3,7,3) \ge 684$.
Use 76 cosets of a 2-dimensional ternary code.

\noindent
\smallskip
{\scriptsize
\begin{tabular}{c}
matrix\\
\hline
0001100010\\
0002111101\\
\end{tabular}
\begin{tabular}{l}
\multicolumn{1}{c}{cosets}\\
\hline
1000, 4005, 5012, 7014, 3016, 0021, 2023, 6028, 6032, 2034, 5036, 4041, 1043, 2048, 3050, \\
1057, 2060, 7065, 3072, 0074, 6076, 7081, 4083, 0088, 6101, 0103, 2108, 6115, 5117, 4122, \\
3124, 7126, 3132, 1134, 6136, 2141, 4143, 1148, 5150, 0155, 7155, 4157, 0162, 4164, 3166, \\
1171, 7173, 4178, 6180, 2187, 3201, 6203, 1208, 0215, 6217, 2222, 5224, 4226, 5231, 3233, \\
4238, 0240, 7240, 5245, 3247, 1252, 6254, 2256, 4260, 2265, 0267, 7267, 6272, 5276, 1283, \\
3288.
\end{tabular}}

\smallskip
(v) $N(4,7,3) \ge 1332$.
Use 74 cosets of the direct sum of a 2-dimensional ternary code
and a 1-dimensional binary code.

\noindent
\smallskip
{\scriptsize
\begin{tabular}{c}
matrix\\
\hline
00001100010\\
00002111101\\
11110000000\\
\end{tabular}
\begin{tabular}{l}
\multicolumn{1}{c}{cosets}\\
\hline
6001, 3003, 0008, 1010, 2015, 3017, 4022, 5024, 6026, 3031, 6038, 7040, 4045, 1052, 2053, \\
7057, 4060, 7065, 5067, 5072, 6074, 0076, 0081, 1083, 3088, 2100, 1105, 0114, 5116, 7122, \\
4123, 2127, 5132, 7134, 4136, 4141, 6143, 7148, 0150, 3155, 1157, 1160, 2165, 0167, 0172, \\
5174, 3176, 6181, 7183, 5188, 5201, 6203, 3208, 4210, 7215, 6217, 2222, 3224, 0226, 0232, \\
2234, 1236, 1241, 3243, 2248, 6250, 5255, 4257, 4264, 7266, 2271, 1278, 5280, 6285.
\end{tabular}}

\smallskip
(vi) $N(7,2,4) \ge 26$.
Use 13 cosets of a 1-dimensional binary code.

\noindent
\smallskip
{\scriptsize
\begin{tabular}{c}
matrix\\
\hline
111100000\\
\end{tabular}
\begin{tabular}{l}
\multicolumn{1}{c}{cosets}\\
\hline
0F0, 120, 240, 291, 3E1, 3B3, 0C5, 175, 225, 0A7, 147, 277, 3D8.
\end{tabular}}


\smallskip
(vii) $N(10,3,4) \ge 400$.
Use 25 cosets of a 4-dimensional binary code.

\noindent
\smallskip
{\scriptsize
\begin{tabular}{c}
matrix\\
\hline
1000111000000\\
0100110100000\\
0010101100000\\
0001011100000\\
\end{tabular}
\begin{tabular}{l}
\multicolumn{1}{c}{cosets}\\
\hline
0C00, 1A01, 3101, 2B04, 1505, 2606, 3D06, 0308, 0210, 2412, 3F12, 3013, 0E14, 1914, 1717, \\
0D18, 2A18, 2721, 1622, 2922, 0123, 3E23, 3325, 1B26, 1C27.
\end{tabular}}

\smallskip
(viii) $N(5,5,4) \ge 108$.
Use 54 cosets of a 1-dimensional binary code.

\noindent
\smallskip
{\scriptsize
\begin{tabular}{c}
matrix\\
\hline
1111000000\\
\end{tabular}
\begin{tabular}{l}
\multicolumn{1}{c}{cosets}\\
\hline
4003, 1008, E015, D016, 9021, 2022, 5031, 3033, A040, 7048, C054, 0056, A068, 1070, 6071, \\
5085, F087, E101, 4112, 2113, 9115, F123, 5127, 9136, 2137, 5143, 6150, 1152, A155, 7162, \\
B164, C165, D171, E176, 0184, 3186, B202, D204, 6208, 7210, 0217, A226, 8231, E233, B247, \\
C248, D250, 7254, 2260, 5266, 8273, 3275, E282, 9288.
\end{tabular}}

\smallskip
(ix) $N(6,5,4) \ge 208$.
Use 52 cosets of a 2-dimensional binary code.

\noindent
\smallskip
{\scriptsize
\begin{tabular}{c}
matrix\\
\hline
10111000000\\
01110100000\\
\end{tabular}
\begin{tabular}{l}
\multicolumn{1}{c}{cosets}\\
\hline
D005, 1016, A017, 6022, B030, C031, 3044, 4045, E056, 9057, F067, 8068, 7070, 0071, 2083, \\
5084, 2100, 5101, B113, C114, 8126, F128, 7136, 0137, F141, 8142, D153, 6154, E163, 9164, \\
3178, 4176, 1180, A181, 3207, 4208, E210, 9211, 7223, 0224, 1233, A234, 2246, 5247, 4250, \\
3252, D260, 6261, 8273, F275, B286, C287.
\end{tabular}}

\smallskip
(x) $N(2,6,4) \ge 51$.
Use 17 cosets of a 1-dimensional ternary code.

\noindent
\smallskip
{\scriptsize
\begin{tabular}{c}
matrix\\
\hline
00111111\\
\end{tabular}
\begin{tabular}{l}
\multicolumn{1}{c}{cosets}\\
\hline
1017, 3022, 2044, 1053, 0061, 3066, 0106, 3148, 2150, 1170, 3184, 3213, 2227, 3231, 0235, \\
2272, 1288.
\end{tabular}}

\smallskip
(xi) $N(3,6,4) \ge 87$.
Use 29 cosets of a 1-dimensional ternary code.

\noindent
\smallskip
{\scriptsize
\begin{tabular}{c}
matrix\\
\hline
000111111\\
\end{tabular}
\begin{tabular}{l}
\multicolumn{1}{c}{cosets}\\
\hline
7002, 4011, 1026, 5033, 3040, 0045, 2057, 0060, 7074, 4088, 0108, 5115, 3117, 2120, 3135, \\
4146, 7151, 4164, 7166, 1182, 5207, 4223, 4232, 7248, 1254, 3261, 5270, 0277, 2285.
\end{tabular}}

\smallskip
(xii) $N(4,7,4) \ge 360$.
Use 40 cosets of a 2-dimensional ternary code.

\noindent
\smallskip
{\scriptsize
\begin{tabular}{c}
matrix\\
\hline
00001110010\\
00001001101\\
\end{tabular}
\begin{tabular}{l}
\multicolumn{1}{c}{cosets}\\
\hline
3004, 6006, 8007, D014, 4035, D036, 6074, 8075, F078, 4080, B080, 1115, E117, 7120, 9121, \\
0126, 2133, B137, A142, C143, 5158, 9163, 7165, C168, 5171, 3176, 2181, F201, 5203, 2218, \\
A224, 0244, 7247, 9248, 8250, 6252, F253, 0262, A266, D282.
\end{tabular}}

\smallskip
(xiii) $N(5,7,4) \ge 612$.
Use 34 cosets of the direct sum of a 2-dimensional ternary code
and a 1-dimensional binary code.

\noindent
\smallskip
{\scriptsize
\begin{tabular}{c}
matrix\\
\hline
000001110010\\
000002101101\\
111100000000\\
\end{tabular}
\begin{tabular}{l}
\multicolumn{1}{c}{cosets}\\
\hline
9001, 4013, D026, 0030, B036, 8054, F055, 4068, B074, 7076, E081, 6105, 9113, 4121, 3131, \\
6140, A145, 9158, 5160, 2166, 7184, 0185, F200, 8206, C212, 1217, 2224, 5225, E238, 3243, \\
A250, D264, E273, 3288.
\end{tabular}}

\smallskip
(xiv) $N(4,8,4) \ge 891$.
Use 33 cosets of a 3-dimensional ternary code.

\noindent
\smallskip
{\scriptsize
\begin{tabular}{c}
matrix\\
\hline
000011100100\\
000021010010\\
000020101001\\
\end{tabular}
\begin{tabular}{l}
\multicolumn{1}{c}{cosets}\\
\hline
A002, 1011, 4020, 4038, A047, 1056, 7065, D074, A083, F100, 6107, 9107, C116, 3128, 3134, \\
6143, 9143, F148, C155, C161, 3170, 6182, 9182, 0184, 5203, 2215, E224, 8230, 5242, B251, \\
2266, 8278, 5287.
\end{tabular}}

\smallskip
(xv) $N(2,11,4) \ge 5589$ and $N(5,8,4) \ge 1674$.
Use 23 cosets of a 5-dimensional ternary code to find $N(2,11,4) \ge 5589$.
Discarding all codewords $u$ with $u_8 = 0$ or $u_{12} = 0$ or $u_{13} = 0$,
we find $N(5,8,4) \ge 1674$.

\noindent
\smallskip
{\scriptsize
\begin{tabular}{c}
matrix\\
\hline
0011100010000\\
0011010001000\\
0011001000100\\
0011000100010\\
0020111100001\\
\end{tabular}
\begin{tabular}{l}
\multicolumn{1}{c}{cosets}\\
\hline
1085, 2202, 1276, 3323, 3418, 2437, 3460, 1514, 2550, 0561, 2614, 0628, 3635, 1650, 3687, \\
1702, 3741, 0754, 2776, 0803, 1837, 0842, 2885.
\end{tabular}}

\smallskip
(xvi) $N(6,4,5) \ge 24$.
Use 12 cosets of a 1-dimensional binary code.

\noindent
\smallskip
{\scriptsize
\begin{tabular}{c}
matrix\\
\hline
1111110000\\
\end{tabular}
\begin{tabular}{l}
\multicolumn{1}{c}{cosets}\\
\hline
1E08, 1515, 0921, 0726, 0A30, 0437, 0F44, 1352, 1963, 1C71, 1276, 0085.
\end{tabular}}

\smallskip
(xvii) $N(8,4,5) \ge 82$.
Use 41 cosets of a 1-dimensional binary code.

\noindent
\smallskip
{\scriptsize
\begin{tabular}{c}
matrix\\
\hline
111111110000\\
\end{tabular}
\begin{tabular}{l}
\multicolumn{1}{c}{cosets}\\
\hline
0000, 2514, 6215, 4917, 3B18, 3824, 1625, 6E27, 7528, 7634, 4535, 3D37, 6838, 2A41, 3442, \\
7943, 1344, 6746, 5E48, 6151, 1952, 4A53, 2F55, 3256, 0457, 6B64, 3165, 1A67, 2668, 4671, \\
6D72, 3E73, 0875, 1576, 7077, 3781, 7A82, 6483, 5D84, 2986, 4388.
\end{tabular}}
}

\subsection{Explicitly presented codes}
\label{explicit}
In this section we give a number of codes for which we have no better
description than to simply list all the words.
These were found by a variety of techniques:
by hand, by exhaustive search, by
clique--finding using a number of different programs,
or by heuristic search procedures
like those described in Section \ref{HEUR}.

The first few codes are given explicitly.

{\scriptsize
\begin{center}
\begin{tabular}{c}
$N(3,4,5) = 6$ \\
\hline
$001\,0000$ \\
$010\,2101$ \\
$100\,2220$ \\
$110\,0012$ \\
$101\,1111$ \\
$011\,1222$
\end{tabular}
\begin{tabular}{c}
$N(6,3,6) = 6$ \\
\hline
$100\,100\,100$ \\
$010\,010\,010$ \\
$001\,001\,001$ \\
$111\,111\,111$ \\
$000\,111\,222$ \\
$111\,000\,222$
\end{tabular}
\begin{tabular}{c}
$N(8,2,6) = 7$ \\
\hline
0000000000 \\
0000111111 \\
0011001122 \\
0101110022 \\
1011010011 \\
1101011100 \\
1110100101
\end{tabular}
\begin{tabular}{c}
$N(6,6,8) = 7$ \\
\hline
000000000000 \\
000011111111 \\
000101222222 \\
011110001122 \\
101110112200 \\
110110220011 \\
111001002211
\end{tabular}
\begin{tabular}{c}
$N(7,2,5) = 9$ \\
\hline
000000000 \\
000011111 \\
001100112 \\
010101021 \\
011010120 \\
100110022 \\
101111100 \\
110001102 \\
111000011
\end{tabular}
\begin{tabular}{c}
$N(4,4,5) = 9$ \\
\hline
00000000 \\
00011111 \\
00101222 \\
01012022 \\
01102101 \\
10112210 \\
11001120 \\
11010201 \\
11100012
\end{tabular}
\begin{tabular}{c}
$N(6,5,7) = 9$ \\
\hline
00000000000 \\
00001111111 \\
00110011222 \\
01010122012 \\
01101022120 \\
10100122201 \\
11001100222 \\
11110000111 \\
11111111000
\end{tabular}
\begin{tabular}{c}
$N(2,8,7) = 9$ \\
\hline
0000000000 \\
0001111111 \\
0010122222 \\
0112200112 \\
0121212020 \\
1012211200 \\
1102002221 \\
1111120001 \\
1120021110
\end{tabular}
\begin{tabular}{c}
$N(9,4,8) = 9$ \\
\hline
0000000000000 \\
0000011111111 \\
0001100112222 \\
0110101001122 \\
0111010002211 \\
1010111012200 \\
1011011100022 \\
1101101010011 \\
1101110101100
\end{tabular}
\begin{tabular}{c}
$N(4,3,4) = 11$ \\
\hline
0000000 \\
0001111 \\
0010122 \\
0101022 \\
0110011 \\
0111200 \\
1001202 \\
1010210 \\
1011021 \\
1100101 \\
1111112
\end{tabular}
\begin{tabular}{c}
$N(6,4,6) = 12$ \\
\hline
0000000000 \\
0000111111 \\
0001012222 \\
0110001122 \\
0110112200 \\
0111010011 \\
1010100212 \\
1011002101 \\
1011111020 \\
1100102021 \\
1101001210 \\
1101110102
\end{tabular}
\begin{tabular}{c}
$N(5,6,7) = 12$ \\
\hline
00000000000 \\
00001111111 \\
00110011222 \\
00111222001 \\
01010122120 \\
01011200212 \\
10100202112 \\
10101120220 \\
11000221201 \\
11001012022 \\
11110110011 \\
11111001100
\end{tabular}
\begin{tabular}{c}
$N(1,9,7) = 12$ \\
\hline
0000000000 \\
0001111112 \\
0120012222 \\
0122200111 \\
0211212001 \\
0212021120 \\
1011020211 \\
1012102022 \\
1100122101 \\
1101201220 \\
1220221012 \\
1222110200
\end{tabular}
\begin{tabular}{c}
$N(4,8,8) = 12$ \\
\hline
000000000000 \\
000011111111 \\
001100112222 \\
001122220011 \\
010111222200 \\
010122001122 \\
101012021202 \\
101021202120 \\
110002122021 \\
110020210212 \\
111101010101 \\
111110101010
\end{tabular}
\begin{tabular}{c}
$N(3,9,8) = 13$ \\
\hline
000000000000 \\
000011111111 \\
000101222222 \\
001222001122 \\
011012022201 \\
011121110002 \\
011200211210 \\
100222112200 \\
101110202011 \\
110020221102 \\
110102011021 \\
110211000212 \\
111001102120
\end{tabular}
\begin{tabular}{c}
$N(5,4,5) = 14$ \\
\hline
000000000 \\
000011111 \\
000101222 \\
001012022 \\
001102101 \\
001110210 \\
010110021 \\
011000112 \\
100110102 \\
101000221 \\
110001120 \\
110012201 \\
110102012 \\
111111000
\end{tabular}
\begin{tabular}{c}
$N(0,10,7) \ge 14$ \\
\hline
0000000000 \\
0001111111 \\
0010122222 \\
0112200112 \\
0121212020 \\
0222001221 \\
1012211200 \\
1121120201 \\
1202110022 \\
1220102110 \\
2102022011 \\
2120011102 \\
2201202202 \\
2211020120
\end{tabular}
\begin{tabular}{c}
$N(2,6,5) = 15$ \\
\hline
00000000 \\
00011111 \\
00101222 \\
00222012 \\
01012202 \\
01102110 \\
01121001 \\
01220220 \\
10020122 \\
10122200 \\
10200211 \\
10211020 \\
11002021 \\
11110012 \\
11201102
\end{tabular}
\begin{tabular}{c}
$N(2,10,8) = 18$ \\
\hline
000000000000 \\
000011111111 \\
001100112222 \\
001122220011 \\
002211222200 \\
010202021212 \\
010220202121 \\
012112010120 \\
012121101002 \\
101212100102 \\
101221011020 \\
102002201221 \\
102020022112 \\
110011220022 \\
110022112200 \\
111100221100 \\
111111002211 \\
112200110011
\end{tabular}
\begin{tabular}{c}
$N(5,3,4) = 20$ \\
\hline
00000000 \\
00001111 \\
00010122 \\
00100212 \\
00111001 \\
01000221 \\
01011010 \\
01101100 \\
01110111 \\
01111222 \\
10001222 \\
10010011 \\
10011100 \\
10100101 \\
10101010 \\
10110220 \\
11000110 \\
11001001 \\
11010202 \\
11100022
\end{tabular}
\begin{tabular}{c}
$N(5,2,3) = 22$ \\
\hline
0000000 \\
0000111 \\
0001022 \\
0010012 \\
0010120 \\
0011001 \\
0100021 \\
0101100 \\
0110102 \\
0111010 \\
0111121 \\
1000102 \\
1001010 \\
1001121 \\
1010021 \\
1011100 \\
1100012 \\
1100120 \\
1101001 \\
1110000 \\
1110111 \\
1111022
\end{tabular}
\end{center}

}

The remaining codes are given in the compressed format
where the binary portion is in hexadecimal and the ternary portion
in base 9, both right justified.

\medskip
(i) $N(8,1,3) \ge 50$. This improves the bound $N(8,1,3) \ge 49$
found by Mario Szegedy.\nlsp

\noindent
{\scriptsize
000, 0B1, 0C1, 162, 192, 1F0, 232, 260,
2D0, 310, 371, 3A0, 3C2, 442, 471, 490,
4E0, 501, 530, 5A2, 5D1, 621, 682, 6F2,
752, 7E1, 870, 8A2, 8D2, 932, 951, 980,
A02, A91, AE1, B21, BF2, C12, C20, C81,
D61, DB1, DC2, E51, E62, EB0, EC0, F00,
F70, F92.

}

\medskip
(ii) $N(6,2,3) \ge 38$.\nlsp

\noindent
{\scriptsize
070, 1D0, 220, 2C0, 041, 0A1, 291, 351, 012, 1E2, 2F2, 332, 382, 003, 0E3,
313, 3F3, 0D4, 274, 324, 3C4, 175, 195, 245, 2A5, 096, 136, 146, 256, 3A6,
187, 1F7, 207, 2E7, 028, 0C8, 368, 3D8.

}

\medskip
(iii) $N(2,5,3) \ge 52$.\nlsp

\noindent
{\scriptsize
0006, 0035, 0050, 0072, 0115, 0121, 0137, 0160, 0202, 0223, 0241, 0258, 0264,
0276, 1001, 1028, 1046, 1084, 1132, 1144, 1186, 1210, 1233, 1282, 2010, 2025,
2031, 2048, 2063, 2087, 2104, 2126, 2143, 2152, 2168, 2217, 2236, 2254, 2275,
2280, 3014, 3053, 3062, 3100, 3118, 3157, 3171, 3185, 3205, 3221, 3242, 3267.

}

\medskip
(iv) $N(3,5,3) \ge 98$. A code proving $N(3,5,3) \ge 98$
has been published in Norway (see \cite{thor})
as a football pool system.\nlsp

\noindent
{\scriptsize
0000, 7000, 0014, 5015, 6017, 3018, 3024, 6025, 5027, 0028, 4034,
2035, 7037, 1038, 2041, 4042, 6043, 5046, 1051, 7052, 0053, 3056,
1064, 7065, 2067, 4068, 7071, 1072, 3073, 0076, 4081, 2082, 5083,
6086, 5104, 3105, 0107, 6108, 1111, 7112, 4113, 2116, 2121, 4122,
1123, 7126, 3131, 5132, 7133, 4136, 0140, 1145, 6150, 2158, 6161,
0162, 2163, 1166, 5170, 6175, 3177, 4177, 3180, 0184, 7184, 5188,
6204, 0205, 3207, 5208, 4211, 2212, 7213, 1216, 7221, 1222, 2223,
4226, 0231, 6232, 1233, 2236, 3240, 5244, 0248, 7248, 5250, 3255,
4255, 6257, 5261, 3262, 4263, 7266, 6270, 2274, 0280, 1287.

}

\medskip
(v) $N(0,6,3) \ge 38$. This improves an earlier bound
$N(0,6,3) \ge 37$ found by Lohinen \cite{Lohinen},
and by Vaessens et al. \cite{VAvL}.\nlsp

\noindent
{\scriptsize
848, 774, 570, 358, 404, 000, 526, 072,
757, 716, 321, 811, 608, 468, 265, 453,
732, 145, 640, 213, 250, 584, 502, 181,
377, 136, 128, 866, 315, 661, 834, 882,
623, 441, 086, 054, 363, 207.

}

\medskip
(vi) $N(1,6,3) \ge 71$. This improves an earlier bound
$N(1,6,3) \ge 69$ by Seppo Rankinen (personal communication).\nlsp

\noindent
{\scriptsize
0020, 0042, 0077, 0125, 0130, 0144, 0186, 0204, 0218, 0251,
0262, 0273, 0328, 0336, 0354, 0365, 0370, 0413, 0452, 0461,
0478, 0500, 0545, 0587, 0614, 0631, 0682, 0707, 0712, 0735,
0746, 0784, 0823, 0858, 0866, 0871, 1005, 1057, 1060, 1116,
1138, 1153, 1171, 1222, 1240, 1267, 1317, 1332, 1343, 1381,
1420, 1434, 1466, 1485, 1508, 1524, 1556, 1572, 1606, 1655,
1664, 1678, 1728, 1751, 1762, 1773, 1801, 1815, 1833, 1847, 1880.

}

\medskip
(vii) $N(6,3,4) \ge 34$ (found by Mario Szegedy, personal communication).\nlsp

\noindent
{\scriptsize
0006, 0304, 0523, 0610, 0821, 0B16, 0C15, 0D07, 1128, 1202,
1417, 1721, 1914, 1A23, 1C00, 1F05, 2025, 2117, 2320, 2401,
2708, 2903, 2A14, 2D22, 2E26, 3010, 3227, 3315, 3603, 3808,
3B01, 3C24, 3D16, 3E12.

}

\medskip
(viii) $N(4,4,4) \ge 28$.\nlsp

\noindent
{\scriptsize
000, 044, 118, 181, 225, 267, 332, 373, 427, 465, 536, 650,
711, 788, 858, 904, 940, A33, A72, B26, C13, C31, D22, D77,
E08, E84, F45, F60.

}

\medskip
(ix) $N(7,3,5) \ge 20$.\nlsp

\noindent
{\scriptsize
0900, 7000, 3E02, 0603, 5D05, 6305, 1511, 2211, 3B13, 4814, 6516,
0F18, 5218, 5B21, 4422, 2D24, 7624, 1C26, 6A26, 3128.

}

\medskip
(x) $N(10,3,5) \ge 128$ and $N(11,2,5) \ge 96$.
The former is given explicitly, the latter follows by
discarding the words ending in 1.\nlsp

\noindent
{\scriptsize
00500, 04A00, 1BA00, 1F500, 27600, 29F00, 32000, 3C900, 03C02,
0E002, 15F02, 18302, 22B02, 25102, 39402, 3EE02, 0A603, 0DC03,
11903, 16303, 26D03, 2B103, 30E03, 3D203, 01205, 0FB05, 14405,
1AD05, 28805, 2C705, 33705, 37805, 07910, 1C610, 2AC10, 31310,
02211, 05411, 19D11, 1EB11, 24F11, 28111, 33E11, 3F011, 0B712,
10812, 2DA12, 36512, 08B13, 13413, 24013, 3FF13, 0B814, 0E514,
10714, 15A14, 27314, 29614, 32914, 3CC14, 06E15, 1D115, 21D15,
3A215, 01E16, 0F216, 14D16, 1A116, 22716, 2D516, 36A16, 39816,
04318, 08418, 13B18, 1FC18, 23018, 2E918, 35618, 38F18, 09020,
12F20, 2E320, 35C20, 01B21, 0FE21, 14121, 1A421, 23521, 26821,
38A21, 3D721, 0CD22, 17222, 20622, 3B922, 05723, 1E823, 23A23,
38523, 00C24, 0C224, 17D24, 1B324, 2AF24, 2D924, 31024, 36624,
02125, 19E25, 2F425, 34B25, 06426, 0BD26, 10226, 1DB26, 20926,
2CE26, 37126, 3B626, 05828, 0AA28, 11528, 1E728, 27F28, 29328,
32C28, 3C028.

}

\medskip
(xi) $N(9,4,5) \ge 136$.\nlsp

\noindent
{\scriptsize
02200, 0DD00, 16F00, 19000, 01E02, 0E102, 13502, 1CA02, 05303,
0AC03, 17803, 18703, 00905, 0F605, 14405, 1BB05, 15610, 1A910,
01111, 0EE11, 16011, 19F11, 07B12, 08412, 06513, 09A13, 05C14,
0A314, 14B14, 1B414, 12E15, 1D115, 00F16, 0F016, 13316, 1CC16,
04218, 0BD18, 11818, 1E718, 04820, 0B720, 02D21, 0D221, 13A21,
1C521, 10322, 1FC22, 11D23, 1E223, 00624, 0F924, 17724, 18824,
03025, 0CF25, 07E26, 08126, 12426, 1DB26, 05528, 0AA28, 16928,
19628, 0FA30, 11B30, 1E430, 0AF32, 12832, 04E33, 0B133, 13633,
16335, 09737, 0C837, 10D37, 15237, 03C40, 0F541, 12741, 1FF43,
13944, 0A646, 16A46, 02148, 0DE48, 17448, 18E50, 05F51, 0A051,
1EB51, 06652, 02B53, 0BE54, 16C54, 1A555, 0ED56, 14756, 1B856,
0F358, 13F58, 00560, 05062, 1D762, 1C963, 07D65, 08265, 19C65,
03867, 06767, 1A167, 1FE67, 0C370, 00A71, 1D871, 14D72, 1B272,
10073, 07274, 08D74, 1C674, 01775, 0E875, 05976, 19576, 18B78,
17180, 11481, 09982, 0D483, 04184, 19384, 15A85, 01286, 00C88,
1C088.

}

\medskip
(xii) $N(7,4,6) \ge 18$.\nlsp

\noindent
{\scriptsize
0000, 0344, 0588, 1848, 1B80, 1D04, 2884, 2B08,
2D40, 3611, 4E15, 5267, 5453, 6252, 6763, 7115,
7C62, 7F57.

}

\medskip
(xiii) $N(9,4,6) \ge 48$.\nlsp

\noindent
{\scriptsize
00703, 0AA04, 12906, 13607, 1D211, 04B12, 1A413, 03D14, 0B316,
00017, 18F17, 15C18, 16521, 18822, 0D927, 0C628, 17330, 0B932,
1D833, 07E35, 0CC41, 10642, 05747, 1E148, 13C50, 08351, 05052,
1DF52, 0F553, 1B255, 16A57, 00D58, 05D60, 1F462, 03063, 1BF63,
10C64, 0D365, 18266, 0A567, 08973, 12374, 02E76, 1B877, 0FA80,
03782, 15683, 17985.

}

\medskip
(xiv) $N(7,6,6) \ge 99$.\nlsp

\noindent
{\scriptsize
30000, 77013, 1D024, 55032, 42040, 21045, 7C047, 2E053, 3F068,
0C072, 4B085, 09108, 1E116, 6F127, 22137, 4D143, 68152, 56154,
35156, 71164, 2B170, 00183, 63202, 50215, 0A221, 2D231, 1B233,
4E238, 36242, 41257, 14267, 5F271, 72286, 41303, 13312, 4E314,
2D316, 36327, 72335, 14343, 5F356, 0A366, 63377, 58381, 2E402,
55417, 21421, 7C423, 42428, 4B431, 3F444, 0C457, 1D460, 38478,
77482, 56500, 35505, 68507, 22513, 4D522, 00532, 71540, 2B558,
6F563, 09574, 1E585, 2B604, 00617, 71628, 1E631, 6F642, 09650,
4D667, 35671, 68673, 56678, 22682, 5F705, 72711, 14722, 58736,
0A745, 63753, 36763, 41772, 4E780, 2D785, 1B787, 0C803, 4B816,
3F820, 77837, 1D848, 38854, 7C862, 42864, 21866, 2E877, 55883.

}

\medskip
(xv) $N(8,5,7) \ge 20$.\nlsp

\noindent
{\scriptsize
F4018, 4F025, 21035, 97056, EA060, 1C071, 82112, BE124, 7D137,
CC143, 1B163, D1181, 24186, 41216, 56232, B9240, 0A257, 8D268,
E7274, 78285.

}

\medskip
(xvi) $N(6,6,7) \ge 17$.\nlsp

\noindent
{\scriptsize
24006, 12022, 39084, 27175, 3E231, 01240, 0F360, 29438, 16446,
33503, 0C515, 15635, 2A643, 3D710, 04781, 0B827, 30878.

}

\medskip
(xvii) $N(7,6,7) \ge 24$.\nlsp

\noindent
{\scriptsize
21001, 1B026, 6C046, 0F141, 55188, 6F225, 7A261, 08275, 43374,
10437, 5E453, 26465, 69480, 44521, 33552, 3D577, 77637, 59642,
2A654, 16670, 4A708, 3C722, 70813, 05833.

}

\medskip
(xviii) $N(4,7,7) \ge 14$.\nlsp

\noindent
{\scriptsize
00000, 10444, 21158, 31861, 40878, 62463, 72017, 82284,
92708, B0386, C1337, D1170, E0721, F0235.

}

\medskip
(xix) $N(5,7,7) \ge 20$.\nlsp

\noindent
{\scriptsize
121214, 032028, 0E2362, 120782, 051272, 1F0135, 1C2718, 031463, 172867, 081587,
142083, 141431, 1F1520, 002835, 192304, 0B2741, 050724, 111646, 080100, 060546.

}

\medskip
(xx) $N(6,7,7) \ge 28$.\nlsp

\noindent
{\scriptsize
1A0017, 200052, 3D0185, 0C0236, 310410, 320564, 0B0582, 2A0723,
140821, 0F1073, 2B1131, 101186, 021300, 191354, 2C1417, 161548,
331628, 251853, 381872, 352047, 262168, 112205, 3E2350, 292366,
072424, 002674, 0D2742, 1F2867.

}

\medskip
(xxi) $N(3,8,7) \ge 16$.\nlsp

\noindent
{\scriptsize
30242, 40634, 51020, 21887, 72368, 02513, 03382, 53876, 64530,
65174, 35653, 26006, 76524, 17347, 48258, 18702.

}

\medskip
(xxii) $N(4,8,7) \ge 22$.\nlsp

\noindent
{\scriptsize
81356, F1718, 21862, 12010, 62155, 72367, A2514, D2851, 53162,
E3538, 93607, 63620, 34345, 44584, B5286, 86222, D6443, 36784,
E7041, 77203, 08431, C8665.

}

\medskip
(xxiii) $N(5,8,7) \ge 33$.\nlsp

\noindent
{\scriptsize
070342, 0D0467, 110847, 051253, 141321, 092115, 1F2206, 122788,
173087, 183224, 023270, 0D3620, 0A3735, 104038, 1D4272, 174405,
0B4557, 0E5411, 045664, 1B5673, 046128, 116163, 1C6346, 1E6861,
037001, 1A7150, 0E7385, 007444, 077776, 087806, 168245, 018582,
1D8754.

}

\medskip
(xxiv) $N(3,9,7) \ge 26$.\nlsp

\noindent
{\scriptsize
600028, 500562, 701847, 302310, 003153, 404675, 205881, 207706,
408441, 112458, 412823, 014001, 715115, 616270, 116514, 516636,
218365, 220742, 621164, 021576, 323077, 523721, 624350, 425238,
327255, 128160.

}

\medskip
(xxv) $N(4,9,7) \ge 39$.\nlsp

\noindent
{\scriptsize
000000, 001444, 002888, 113045, 114406, 116581, 128623, 213627,
214262, 218146, 226405, 303770, 307358, 312834, 321121, 414853,
417312, 423137, 505211, 507165, 520376, 605363, 620842, 815184,
825332, 827217, 906836, 912712, A08520, A11673, C10504, C26780,
D01627, D22255, E02108, E06054, F13452, F17286, F28474.

}

\medskip
(xxvi) $N(3,10,7) \ge 48$.\nlsp

\noindent
{\scriptsize
000000, 001444, 002888, 043045, 044406, 046581, 083627, 084262,
088113, 113731, 115383, 117017, 126505, 135122, 136776, 151253,
172542, 215204, 216156, 224640, 235377, 237605, 250412, 270873,
322038, 327784, 361321, 363536, 417332, 423576, 434811, 438137,
452663, 471725, 522171, 530358, 563064, 578806, 608520, 634183,
661248, 685355, 686768, 703715, 711567, 742750, 748275, 786251.

}

\medskip
(xxvii) $N(2,11,7) \ge 58$.\nlsp

\noindent
{\scriptsize
0000000, 0001444, 0002888, 0043045, 0044406, 0046581, 0058604, 0078740,
0084087, 0113722, 0115237, 0117365, 0126176, 0133863, 0137212, 0138356,
0170317, 0181530, 0225513, 0242162, 0250757, 1014270, 1025332, 1026225,
1035121, 1063478, 1067837, 1070683, 1108671, 1151713, 1171158, 1204626,
1208133, 1286401, 2023841, 2037183, 2050368, 2065205, 2122055, 2127527,
2145474, 2164648, 2211681, 2241246, 2262420, 2276855, 3010707, 3031552,
3058148, 3077014, 3101264, 3142630, 3176566, 3183020, 3200315, 3233037,
3257370, 3282877.

}

\medskip
(xxviii) $N(6,7,8) \ge 14$.\nlsp

\noindent
{\scriptsize
000000, 011444, 021888, 0D2058, 0F0804, 162115, 1B0372, 272480,
2A2643, 2C1512, 312832, 360337, 380284, 3B1106.

}

\medskip
(xxix) $N(5,8,8) \ge 18$.\nlsp

\noindent
{\scriptsize
000000, 004444, 008888, 070148, 074621, 0B1283, 0B8332, 0D3567,
0D8713, 135516, 157065, 162834, 166480, 190751, 1A3675, 1A7107,
1C1512, 1C5056.

}



\section{Heuristic searches}
\label{HEUR}
Given parameters $n_2$, $n_3$, $M$, $d$, we search for mixed
binary/ternary codes of size $M$, with $n_2$ binary and
$n_3$ ternary coordinate positions, and minimum Hamming distance $d$.
For very small parameters an exhaustive search is possible.
For slightly larger parameters we employed tabu search \cite{Glover}.
Let $\cal S$ be the set of all codes $C$ satisfying the requirements
except possibly that on the minimum distance, that is, the set of all
$M$-subsets of $X := \Ff_2^{n_2}\Ff_3^{n_3}$.
Starting with an arbitrary $C_0 \in \cal S$ we do a walk on $\cal S$
in the hope of encountering a $C \in \cal S$ with minimum distance $d$.
Each step goes from a code $C$ to a neighbor $C'$, that is, to a code
$C'$ obtained from $C$ by replacing a single codeword by one that is
at Hamming distance 1.  We choose the best neighbor, where the badness
of a code $C$ is measured either by
$$\sum_{c \in C} \sum_{c' \in C \setminus \{c\}} \max (0, d-d(c,c'))$$
(this worked well for large $d$ and small $M$) or by
$$\sum_{x \in X} \max (0, c(x)-1)$$
where $c(x)$ measures the number of codewords close to $x$ and
is chosen in such a way that the code has minimum distance $d$
if and only if $c(x) \le 1$ for all $x$ (this worked better for small $d$).
There is some freedom in the choice of the function $c(x)$.
For odd $d$, say $d = 2e+1$, we took $c(x)$ to be the number of
codewords at distance at most $e$ from $x$. For even $d$, say $d = 2e$,
we took $c(x)$ to be the number of codewords at distance at most
$e-1$ from $x$ plus $K^{-1}$ times the number of codewords at distance
$e$ from $x$, where $K \ge \lfloor (n_2+n_3)/e \rfloor$. (We took $K = 10$.)

In order to avoid looping, a so-called tabu list --- after which this
search method is called tabu search --- containing (attributes of)
reverses of recent moves is maintained. Moves in the tabu list are
not allowed within a given number $L$ of steps.

Almost the same methods and programs were used earlier for finding
covering codes \cite{O3,OH}.

\subsection{Searching for codes with a given structure}

Searching for codes by these methods becomes
ineffective if the codes are too large (for $d=3$, when there
are more than about 100 codewords, for example).
However, imposing some structure on the code allows us
to search for larger codes.

A method used by Kamps and Van Lint \cite{kam} and Blokhuis and Lam \cite{blo}
leads to codes that are unions of cosets of linear codes. This method was
originally developed for covering codes. An analogous method that works 
for error-correcting codes was presented in \cite{OK}. Let us formulate
it here for the case of mixed binary/ternary error-correcting codes.
(See also \cite{dav,OH}, where the
method is applied to mixed binary/ternary covering codes.)

Let $A$ be an $n_2 \times m_2$ binary matrix of rank $n_2$
and let $B$ be an $n_3 \times m_3$ ternary matrix of rank $n_3$.
For two words $x = (x_2,x_3)$, $y = (y_2,y_3)$ with
$x_2,y_2 \in \Ff_2^{n_2}$, $x_3,y_3 \in \Ff_3^{n_3}$,
we define the {\em distance between $x$ and $y$ using $A$ and 
$B$\/} to be

\begin{displaymath}
d_{A,B}(x,y) =
\min \{{\rm wt}(t_2)+{\rm wt}(t_3) \mid At_2 = x_2-y_2, Bt_3 = x_3-y_3\},
\end{displaymath}

\noindent
with $t_2 \in \Ff_2^{m_2}$ and $t_3 \in \Ff_3^{m_3}$.
As the matrices $A$ and $B$ have full rank, the distance $d_{A,B}(x,y)$
is always defined. For a set of words $C \subseteq \Ff_2^{n_2}\Ff_3^{n_3}$
we further define $d_{A,B}(C) = \min_{c,c'\in C,c\neq c'} d_{A,B}(c,c')$.

\begin{Proposition}
Let $A$ be a parity check matrix for a binary linear code with
minimum distance $d_2$, let $B$ be
a parity check matrix for a ternary linear code with
minimum distance $d_3$,
and let $C$ be a subset of $\Ff_2^{n_2}\Ff_3^{n_3}$. Then the code
$W = \{(w_2,w_3) \in \Ff_2^{n_2}\Ff_3^{n_3} \mid (Aw_2,Bw_3) \in C \}$ 
has minimum distance $\min\{d_{A,B}(C),d_2,d_3\}$ and
$|W| = 2^{m_2-n_2}3^{m_3-n_3}|C|$.
\end{Proposition}

In searching for codes using this approach, the following idea
from \cite{ost0} was used.
First, we construct a family of inequivalent
matrices $A$ and $B$ with given parameters.
Then the computer search is carried out separately
for all possible combinations of these matrices. 

Most of the codes given in Section \ref{cosets} were found
in this way.


\section{Tables}

Tables of bounds on binary codes can be found in many places --- see, e.g.,
Conway \& Sloane \cite{CS}, Table 9.1 (p. 248).
An improvement was given in \cite{KLV}.

An early table of bounds on $A_3(n,d)$,
the maximal size of a ternary code of length $n$ and minimum distance $d$,
was given in \cite{Mack}. Another table was given in
Vaessens, Aarts \& van Lint \cite{VAvL}.
We know of 19 improvements to the latter table,
and give an updated version in Table A.
(We explain only the entries that have changed, indicated by an asterisk.)
We omit the trivial entries ($A_3(n,1) = 3^n$, and if $n > 0$ then
$A_3(n,2) = 3^{n-1}$ and $A_3(n,n) = 3$).

\newcommand{\ab}[2]{{\mbox{\begin{tabular}{c}$#1$\\$#2$\end{tabular}}}}
% \newcommand{\sd}[1]{{\multicolumn{1}{c}{\ab{}{#1}}}} %% doesnt work
\newcommand{\zzr}[1]{{\makebox[0pt][r]{#1}}}

\begin{center}
Table $A$:~Values of $A_3(n,d)$

\nopagebreak
\quad

\nopagebreak
\noindent\hspace{-30pt}
{\footnotesize
\begin{tabular}{@{}r|@{}c@{}|@{}c@{}|@{}c@{}|@{}c@{}|@{}c@{}|@{}c@{}|@{}c@{}|@{}c@{}|@{}c@{}|@{}c@{}|@{}c@{}|@{}c@{}|@{}c@{}|}
\multicolumn{1}{r}{\zzr{$n \backslash d$}} & \multicolumn{1}{c}{3} \\
\cline{1-2}
\zzr{4} & 9 & \multicolumn{1}{c}{4} \\
\cline{1-3}
\zzr{5} & 18 & 6 & \multicolumn{1}{c}{5} \\
\cline{1-4}
\zzr{6} & \ab{48}{38*} & 18 & 4 & \multicolumn{1}{c}{\ab{}{6}} \\
\cline{1-5}
\zzr{7} & \ab{144}{99} & \ab{46*}{33} & 10 & 3 & \multicolumn{1}{c}{\ab{}{7}} \\
\cline{1-6}
\zzr{8} & \ab{340}{243} & \ab{138*}{99} & 27* & 9 & 3 & \multicolumn{1}{c}{\ab{}{8}} \\
\cline{1-7}
\zzr{9} & \ab{937}{729} & \ab{340}{243} & 81* & 27 & 6 & 3 & \multicolumn{1}{c}{\ab{}{9}} \\
\cline{1-8}
\zzr{10} & \ab{2811}{2187} & \ab{937}{729} & 243 & 81 & \ab{18}{14*} & 6 & 3 & \multicolumn{1}{c}{\ab{}{10}} \\
\cline{1-9}
\zzr{11} & \ab{7029}{6561} & \ab{2561*}{1458} & 729 & 243 & \ab{50*}{36} & 12 & 4 & 3 & \multicolumn{1}{c}{\ab{}{11}} \\
\cline{1-10}
\zzr{12} & 19683 & \ab{7029}{4374} & \ab{1562}{729} & 729 & \ab{138}{51*} & 36 & 9 & 4 & 3 & \multicolumn{1}{c}{\ab{}{12}} \\
\cline{1-11}
\zzr{13} & 59049 & \ab{19682*}{8019} & \ab{4163}{2187} & \ab{1562}{729} & \ab{363}{105*} & \ab{103}{42*} & 27 & 6 & 3 & 3 & \multicolumn{1}{c}{\ab{}{13}} \\
\cline{1-12}
\zzr{14} & \ab{153527}{118098} & \ab{59046*}{24057} & \ab{10736}{6561*} & \ab{3885}{2187} & \ab{836}{243} & \ab{237}{81} & \ab{66*}{31*} & \ab{15}{12} & 6 & 3 & 3 & \multicolumn{1}{c}{\ab{}{14}} \\
\cline{1-13}
\zzr{15} & \ab{434815}{354294} & \ab{153527}{72171} & \ab{29524}{6561} & \ab{10736}{2187} & \ab{2268}{729*} & \ab{711}{243} & \ab{166}{81} & \ab{45}{27*} & 10 & 6 & 3 & 3 & \multicolumn{1}{c}{\ab{}{15}} \\
\cline{1-14}
\zzr{16} & \ab{1304445}{1062882*} & \ab{434815}{216513} & \ab{77217}{19683} & \ab{29524}{6561} & \ab{6643}{729} & \ab{2079}{297} & \ab{451}{243} & \ab{127}{54} & \ab{30}{18} & 9 & 4 & 3 & 3 \\
\hline
\end{tabular}

}
\end{center}
\smallskip

The differences between Table A and the table in \cite{VAvL} are as follows.

Since ternary linear $[14,8,5]$ and $[15,6,7]$ codes exist (\cite{KP,Lizak}),
we have $A_3(14,5) \ge 6561$ and $A_3(15,7) \ge 729$.

In \cite{OK} it was shown that $A_3(16,3) \ge 1062882$
(using a variation on Proposition \ref{uvw}).

Svanstr\"om \cite{Svan} showed that $A_3(15,10) \ge 24$,
and Bitan and Etzion \cite{BE95} improved this to $A_3(15,10) \ge 27$.

In this paper we find that $A_3(6,3) \ge 38$, $A_3(10,7) \ge 14$,
$A_3(12,7) \ge 51$, $A_3(13,7) \ge 105$, $A_3(13,8) \ge 42$
and $A_3(14,9) \ge 31$ (see \S\ref{cyclic}).

Concerning upper bounds, Mario Szegedy (pers. comm.)
proved that $A_3(7,4) \le 47$ (cf. Lemma \ref{szegedy})
and Antti Perttula \cite{Perttula} showed that $A_3(11,7) \le 52$.

In this paper we find $A_3(7,4) \le 46$, $A_3(8,4) \le 138$,
$A_3(11,4) \le 2561$, $A_3(13,4) < 3^9$, $A_3(14,4) < 3^{10}$
(see Lemma \ref{perfect}),
$A_3(8,5) = 27$, $A_3(9,5) = 81$, $A_3(11,7) \le 50$
and $A_3(14,9) \le 66$ (by the linear programming bound, using
the analogue of $(L7)$ for this case).

\medskip
The following tables give lower and upper bounds for $N(n_2,n_3,d)$.
We vary $n_2$ vertically and $n_3$ horizontally.

{\footnotesize
\begin{center}
Table $B_2$:~Values of $N(n_2,n_3,d)$ for $d = 2$

\nopagebreak
\quad

\nopagebreak
\begin{tabular}{c|cccccccccccccc}
$d = 2$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
\hline
 0 & 1 & 1 & 3 & 9 & 27 & 81 & 243 & 729 & 2187 & 6561 \\
 1 & 1 & 2 & 6 & 18 & 54 & 162 & 486 & 1458 & 4374 & 13122 \\
 2 & 2 & 4 & 12 & 36 & 108 & 324 & 972 & 2916 & 8748 & 26244 \\
 3 & 4 & 8 & 24 & 72 & 216 & 648 & 1944 & 5832 & 17496 & 52488 \\
 4 & 8 & 16 & 48 & 144 & 432 & 1296 & 3888 & 11664 & 34992 & 104976 \\
 5 & 16 & 32 & 96 & 288 & 864 & 2592 & 7776 & 23328 & 69984 \\
 6 & 32 & 64 & 192 & 576 & 1728 & 5184 & 15552 & 46656 \\
 7 & 64 & 128 & 384 & 1152 & 3456 & 10368 & 31104 \\
 8 & 128 & 256 & 768 & 2304 & 6912 & 20736 \\
 9 & 256 & 512 & 1536 & 4608 & 13824 \\
10 & 512 & 1024 & 3072 & 9216 \\
11 & 1024 & 2048 & 6144 \\
12 & 2048 & 4096 \\
13 & 4096 \\
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{c|cccccccccccccc}
$d = 2$ & 10 & 11 & 12 & 13 \\
\hline
 0 & 19683 & 59049 & 177147 & 531441 \\
 1 & 39366 & 118098 & 354294 \\
 2 & 78732 & 236196 \\
 3 & 157464 \\
\end{tabular}
\end{center}

}

{\footnotesize
\begin{center}Table $B_3$:~Values of $N(n_2,n_3,d)$ for $d = 3$

\nopagebreak
\quad

\nopagebreak
\begin{tabular}{c|cccccccccccccc}
$d = 3$ & 0 & 1 & \ff{25}{2} & 3 & \ff{25}{4} & \ff{25}{5} & \ff{25}{6} \\
\hline
 0 & 1 & 1 & 1 & 3 & 9 & \zr{d}18 & \zr{x}38--48\zl{L} \\
 1 & 1 & 1 & 2 & 6 & 12\zl{e} & \zr{d}33 & \zr{x}71--96 \\
 2 & 1 & 2 & 4 & 9 & 22\zl{e} & \zr{x}52--66 & \zr{jb}134--178\zl{L} \\
 3 & 2 & 3 & 6\zl{e} & \zr{jb}18 & \zr{H}42--44 & \zr{x}98--126\zl{L2} & 264--343\zl{s} \\
 4 & 2 & \zr{d}6 & 12 & 28--33 & 72--88 & \zr{xc}186--243\zl{s} & \zr{jb}486--631\zl{L2} \\
 5 & 4 & 8\zl{e} & \zr{x}22\zl{e} & 54--65\zl{L} & 144--167\zl{L2} & \zr{xc}342--457\zl{s} & 948--1227\zl{s} \\
 6 & 8 & 16 & \zr{x}38--44 & \zr{H}108--123\zl{s} & 288--322\zl{LX} & 648--863\zl{LX} & 1896--2332\zl{s} \\
 7 & \zr{d}16 & \zr{d}26--30 & 72--85\zl{L2} & 192--230\zl{s} & 576--609\zl{s} & \zr{jb}1296--1612\zl{L2} & \zr{jb}3792--4443\zl{s} \\
 8 & 20\zl{B5} & \zr{x}50--60 & 144--160\zl{L5} & 384--417\zl{L2} & \zr{H}1152\zl{s} & \zr{jb}2544--3110\zl{s} \\
 9 & \zr{d}40 & 96--109\zl{L2} & \zr{H}288--293\zl{L4} & 768--806\zl{L} & \zr{jb}1728--2131\zl{L2} \\
10 & 72--76\zl{K} & 192--213\zl{L} & 512--556\zl{LX} & 1152--1536\zl{s} \\
11 & \zr{d}144--152 & 384 & \zr{xc}832--1049\zl{L2} \\
12 & 256\zl{BB} & \zr{H}768 \\
13 & 512 \\
\end{tabular}
\end{center}

}

{\footnotesize
\begin{center}
\begin{tabular}{c|cccccccccccccc}
$d = 3$ & \ff{25}{7} & 8 & 9 & 10 & 11 & 12 & 13 \\
\hline
 0 & 99--144 & 243--340\zl{L} & 729--937\zl{L} & 2187--2811 & 6561--7029\zl{L} & 19683\zl{L} & \zz{TH}59049 \\
 1 & 198--242\zl{LZ} & 486--680 & 1458--1874 & 4374--4920\zl{L} & 13122--14058 & 39366 \\
 2 & \zr{jb}396--484 & 972--1284\zl{L} & 2916--3514\zl{L} & 8748--9840 & 26244--26790\zl{L} \\
 3 & \zr{xc}684--902\zl{L} & 1944--2464\zl{L2} & 5832--6846\zl{s} & 17496--18589\zl{L} \\
 4 & \zr{xc}1332--1749\zl{s} & 3888--4767\zl{L1} & 11664--12887\zl{L2} \\
 5 & 2592--3259\zl{LX} & 7776--9128\zl{s} \\
 6 & 5184--6362\zl{s} \\
\end{tabular}
\end{center}

}

{\footnotesize
\begin{center}Table $B_4$:~Values of $N(n_2,n_3,d)$ for $d = 4$

\nopagebreak
\quad

\nopagebreak
\begin{tabular}{c|cccccccccccccc}
$d = 4$ & \ff{20}{0} & 1 & 2 & 3 & \ff{25}{4} & \ff{25}{5} & \ff{25}{6} \\
\hline
 0 & 1 & 1 & 1 & 1 & 3 & 6 & \zr{He}18 \\
 1 & 1 & 1 & 1 & 2 & 4 & 12 & \zr{G}33 \\
 2 & 1 & 1 & 2 & 3 & 8 & 22 & \zr{xc}51--66 \\
 3 & 1 & 2 & 3 & 6 & 15\zl{e} & 34--44 & \zr{xc}87--124\zl{L} \\
 4 & 2 & 2 & \zr{jb}6 & \zr{x}11\zl{e} & \zr{x}28--30 & 58--86\zl{L} & 144--242\zl{L} \\
 5 & 2 & 4 & 8\zl{d} & \zr{x}20\zl{e} & 48--60 & \zr{xc}108--167\zl{d} & 288--454\zl{L} \\
 6 & 4 & 8 & 16 & \zr{x}34--40 & 96--120 & \zr{xc}208--319\zl{L6} & 576--863\zl{d} \\
 7 & 8 & 16 & \zr{xc}26--30 & 64--80 & 192--230\zl{L2} & 384--609\zl{d} & \zr{jb}1152--1612\zl{d} \\
 8 & \zr{u}16 & 20\zl{d} & 48--60 & 128--160 & \zr{jb}384--417\zl{d} & 768--1120\zl{L2} \\
 9 & 20 & 40 & 96--109\zl{d} & 256--293\zl{d} & \zr{jb}540--782\zl{L} \\
10 & \zr{B}40 & 72--76\zl{d} & 192--213\zz{d} & \zr{xc}400--556\zl{d} \\
11 & 72--76 & 144--152 & \zr{H}384 \\
12 & \zr{J}144--152 & 256\zl{d} \\
13 & \zr{u}256 \\
\end{tabular}
\end{center}
}

{\footnotesize
\begin{center}
\begin{tabular}{c|cccccccccccccc}
$d = 4$ & \ff{25}{7} & 8 & 9 & \ff{25}{10} & 11 & \ff{23}{12} & 13 \\
\hline
 0 & 33--46\zl{Sz} & \zr{V}99--138 & 243--340\zl{d} & 729--937\zl{d} & 1458--2561\zl{L1} & \zr{u}4374--7029\zl{d} & 8019--19682\zl{t} \\
 1 & 66--92 & 162--242\zl{d} & 486--680 & 972--1749\zl{L1} & 2916--4920\zl{d} & \zr{u}8019--14058 \\
 2 & 108--178\zl{d} & 324--484 & 729--1272\zl{L1} & 1944--3498 & \zr{xc}5589--9777\zl{L1} \\
 3 & 216--343\zl{L1} & 486--902\zl{d} & 1296--2464\zl{d} & 3726--6791\zl{L1} \\
 4 & \zr{xc}360--631\zl{d} & \zr{xc}891--1749\zl{d} & 2484--4767\zl{d} \\
 5 & \zr{xc}612--1223\zl{L} & \zr{xc}1674--3259\zl{d} \\
 6 & 1152--2332\zl{d} \\
\end{tabular}
\end{center}
}

{\footnotesize
\begin{center}Table $B_5$:~Values of $N(n_2,n_3,d)$ for $d = 5$

\nopagebreak
\quad

\nopagebreak
\begin{tabular}{c|cccccccccccccc}
$d = 5$ & \ff{15}{0} & \ff{15}{1} & 2 & \ff{20}{3} & 4 & 5 & 6 \\
\hline
 0 & 1 & 1 & 1 & 1 & 1 & 3 & 4 \\
 1 & 1 & 1 & 1 & 1 & 2 & 3 & 8 \\
 2 & 1 & 1 & 1 & 2 & 3 & 6 & \zr{x}15\zl{e} \\
 3 & 1 & 1 & 2 & 3 & \zr{x}6 & \zr{d}12 & 24--27 \\
 4 & 1 & 2 & 2 & 4 & \zr{x}9\zl{e} & 18\zl{e} & 48--54 \\
 5 & 2 & 2 & 4 & 6\zl{e} & \zr{x}14\zl{e} & 33--36 & 96--108 \\
 6 & 2 & 3 & 6 & 12 & \zr{xc}24--28 & 66--72 & 144--216 \\
 7 & 2 & 4 & \zr{x}9\zl{e} & \zr{x}20--24 & 44--56 & \zr{d}99--144 & \zr{G}234--432 \\
 8 & 4 & 7\zl{e} & \zr{d}16\zl{e} & 32--48 & \zr{xc}82--112 & 156--288 \\
 9 & 6\zl{L} & 12\zl{e} & 26--32 & 64--91\zl{L} & \zr{x}136--224 \\
10 & 12 & 24 & 48--64 & \zr{x}128--170\zl{L2} \\
11 & 24 & \zr{d}38--48 & \zr{x}96--121\zl{L} \\
12 & 32\zl{B5} & \zr{jx}68--86\zl{L2} \\
13 & \zr{NR}64 \\
\end{tabular}
\end{center}
}

{\footnotesize
\begin{center}
\begin{tabular}{c|cccccccccccccc}
$d = 5$ & \ff{20}{7} & 8 & 9 & 10 & 11 & 12 & 13 \\
\hline
 0 & \zr{V}10\zl{e} & 27 & 81 & 243 & \zr{d}729 & 729--1562\zl{L} & \zr{l}2187--4163\zl{L} \\
 1 & 18\zl{e} & 54 & 162 & 486 & 729--1145\zl{L} & 1458--2984\zl{L} \\
 2 & 36 & 108 & 324 & 729--867\zl{L} & 972--2157\zl{L} \\
 3 & 72 & 216 & 486--633\zl{L6} & 729--1567\zl{L} \\
 4 & 144 & 324--432 & 729--1153\zl{L1} \\
 5 & 216--288 & 486--850\zl{L1} \\
 6 & \zr{G}342--576 \\
\end{tabular}
\end{center}
}

{\footnotesize
\begin{center}Table $B_6$:~Values of $N(n_2,n_3,d)$ for $d = 6$

\nopagebreak
\quad

\nopagebreak
\begin{tabular}{c|cccccccccccccc}
$d = 6$ & \ff{10}{0} & \ff{5}{1} & 2 & 3 & 4 & 5 & 6 \\
\hline
 0 & 1 & 1 & 1 & 1 & 1 & 1 & 3 \\
 1 & 1 & 1 & 1 & 1 & 1 & 2 & 3 \\
 2 & 1 & 1 & 1 & 1 & 2 & 3 & 6 \\
 3 & 1 & 1 & 1 & 2 & 3 & 4 & \zr{jc}12 \\
 4 & 1 & 1 & 2 & 2 & 4 & 8 & \zr{jc}18 \\
 5 & 1 & 2 & 2 & 3 & 6\zl{d} & 12\zl{e} & 33--36 \\
 6 & 2 & 2 & 3 & \zr{x}6 & \zr{x}12 & 22--24 & \zr{G}66--72 \\
 7 & 2 & 2 & 4 & 8\zl{e} & \zr{x}18--24 & 44--48 & \zr{x}99--144 \\
 8 & 2 & 4 & \zr{x}7\zl{d} & 16 & \zr{G}32--43\zl{L} & 66--96 \\
 9 & 4 & 6\zl{P} & 12\zl{d} & \zr{G}26--32 & \zr{x}48--77\zl{L} \\
10 & 6 & 12 & 24 & 38--61\zl{L} \\
11 & 12 & 24 & \zr{jx}38--48 \\
12 & \zr{Ha}24 & 32\zl{d} \\
13 & 32 \\
\end{tabular}
\end{center}
}

{\footnotesize
\begin{center}
\begin{tabular}{c|cccccccccccccc}
$d = 6$ & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\
\hline
 0 & 3 & 9 & 27 & 81 & 243 & \zr{G}729 & 729--1562\zl{d} \\
 1 & 6 & 18 & 54 & 162 & 486 & 729--1145\zl{d} \\
 2 & 12 & 36 & 108 & 324 & 729--867\zl{d} \\
 3 & 24 & 72 & 216 & 486--614\zl{L} \\
 4 & 48 & 144 & 324--425\zl{L} \\
 5 & 96 & 216--288 \\
 6 & 144--192 \\
\end{tabular}
\end{center}

}

{\footnotesize
\begin{center}Table $B_7$:~Values of $N(n_2,n_3,d)$ for $d = 7$

\nopagebreak
\quad

\nopagebreak
\begin{tabular}{c|cccccccccccccc}
$d = 7$ & \ff{4}{0} & 1 & 2 & 3 & 4 & 5 & 6 \\
\hline
 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
 1 & 1 & 1 & 1 & 1 & 1 & 1 & 2 \\
 2 & 1 & 1 & 1 & 1 & 1 & 2 & 3 \\
 3 & 1 & 1 & 1 & 1 & 2 & 3 & 4 \\
 4 & 1 & 1 & 1 & 2 & 2 & 3 & 6\zl{P} \\
 5 & 1 & 1 & 2 & 2 & 3 & \zr{j}6 & \zr{x}12 \\
 6 & 1 & 2 & 2 & 3 & 4 & \zr{x}9\zl{e} & \zr{x}17--24 \\
 7 & 2 & 2 & 2 & 4 & 8 & 16\zl{e} & \zr{x}24--45\zl{L4} \\
 8 & 2 & 2 & 4 & 6 & \zr{jc}16 & \zr{x}20--32 \\
 9 & 2 & 3 & 4\zl{e} & \zr{jc}12 & \zr{jc}18--26\zl{L} \\
10 & 2 & 4 & 8 & 16--18 \\
11 & 4 & 6 & 12\zl{e} \\
12 & 4\zl{e} & \zr{jc}12 \\
13 & 8 \\
\end{tabular}
\end{center}
}

{\footnotesize
\begin{center}
\begin{tabular}{c|cccccccccccccc}
$d = 7$ & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\
\hline
 0 & 3 & 3 & 6\zl{P} & \zr{x}14--18 & \zr{d}36--50\zl{L7} & \zz{cy}51--138\zz{L} & \zz{cy}105--363\zz{L} \\
 1 & 3 & \zr{j}6 & \zr{x}12 & 24--36 & 36--100 & \zz{cy}78--251\zz{L} \\
 2 & 4 & \zr{x}9\zl{P} & \zr{d}18--24 & \zr{d}36--72 & \zr{x}58--182\zl{L} \\
 3 & 7\zl{P} & \zr{x}16--18 & \zr{x}26--48 & \zr{x}48--134\zl{L} \\
 4 & \zr{x}14 & \zr{x}22--36 & \zr{x}39--96 \\
 5 & \zr{x}20--28 & \zr{x}33--72 \\
 6 & \zr{x}28--56 \\
\end{tabular}
\end{center}
}

\smallskip

{\footnotesize
\begin{center}Table $B_8$:~Values of $N(n_2,n_3,d)$ for $d = 8$

\nopagebreak
\quad

\nopagebreak
\begin{tabular}{c|cccccccccccccc}
$d = 8$ & 0 & 1 & 2 & \ff{5}{3} & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\
\hline
 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 3 & 3 & \zr{j}6 & 12\zl{P} & \zr{GH}36 & \zr{cy}42--103\zl{L} \\
 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 2 & 3 & 4 & 9\zl{P} & 24 & 36--72 \\
 2 & 1 & 1 & 1 & 1 & 1 & 1 & 2 & 3 & 4 & 7\zl{P} & \zr{x}18 & 36--48 \\
 3 & 1 & 1 & 1 & 1 & 1 & 2 & 3 & 3 & 6\zl{P} & \zr{x}13\zl{e} & 24--36 \\
 4 & 1 & 1 & 1 & 1 & 2 & 2 & 3 & \zr{j}6 & \zr{x}12 & 18--26 \\
 5 & 1 & 1 & 1 & 2 & 2 & 3 & 4 & 8\zl{e} & \zr{x}18--24 \\
 6 & 1 & 1 & 2 & 2 & 3 & 4 & \zr{x}7\zl{P} & \zr{x}14--16 \\
 7 & 1 & 2 & 2 & 2 & 4 & 6\zl{P} & 12\zl{e} \\
 8 & 2 & 2 & 2 & 3 & \zr{j}6 & \zr{jc}12 \\
 9 & 2 & 2 & 3 & 4\zl{d} & \zr{x}9 \\
10 & 2 & 2 & 4 & 6\zl{e} \\
11 & 2 & 4 & \zr{j}6 \\
12 & 4 & 4\zl{d} \\
13 & 4 \\
\end{tabular}
\end{center}
}

{\footnotesize
\begin{center}Table $B_9$:~Values of $N(n_2,n_3,d)$ for $d = 9$

\nopagebreak
\quad

\nopagebreak
\begin{tabular}{c|cccccccccccccc}
$d = 9$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \ff{5}{9} & 10 & 11 & 12 & 13 \\
\hline
 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 3 & 3 & 4 & 9 & \zr{l}27 \\
 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 2 & 3 & 4 & 6\zl{P} & 18 \\
 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 2 & 3 & 3 & 6 & 12 \\
 3 & 1 & 1 & 1 & 1 & 1 & 1 & 2 & 3 & 3 & \zr{j}6 & \zr{x}10\zl{P} \\
 4 & 1 & 1 & 1 & 1 & 1 & 2 & 2 & 3 & 4 & \zr{x}8\zl{P} \\
 5 & 1 & 1 & 1 & 1 & 2 & 2 & 3 & 4 & 6\zl{P} \\
 6 & 1 & 1 & 1 & 2 & 2 & 3 & 4 & 6 \\
 7 & 1 & 1 & 2 & 2 & 2 & 3 & \zr{j}6 \\
 8 & 1 & 2 & 2 & 2 & 3 & 4 \\
 9 & 2 & 2 & 2 & 3 & 4 \\
10 & 2 & 2 & 2 & 4 \\
11 & 2 & 2 & 4 \\
12 & 2 & 3 \\
13 & 2 \\
\end{tabular}
\end{center}

\medskip

\subsection*{Notes on Tables $B_2$ to $B_9$}

All unmarked upper bounds follow from Propositions \ref{easy}, \ref{deriv} or
\ref{prop1234}.

The entries in Table $B_2$ are all given by Proposition \ref{easy}(ii).
Concerning Table $B_5$, the rows of a well-known orthogonal array
($L_{18}$ on page 1153 of \cite{Taguchi}) form a $(1,7,5)_{18}$ code.
In the second part of Table $B_6$ {\em all} lower bounds follow directly from
the extended ternary Golay code.
For $d \ge 9$ the exact values are known. For $d = 10$
we have $N(0,13,10) \le 6$ from the Plotkin bound, so all entries in the table
are at most 6, and follow directly from Proposition \ref{prop1234}.



\medskip

Key to Tables $B_2$--$B_9$.~~ Lower bounds:

\nopagebreak
\quad

\nopagebreak
\begin{tabular}{lp{12cm}}
{\it B} & Best code, see \cite{Best}, \cite{LV}. \\
{\it G} & From the ternary Golay code. \\
{\it GH} & Generalized Hadamard Matrix, see \cite{Mack}. \\
{\it H} & From the binary $[15,11,3]$ Hamming code, see \S\ref{binham}. \\
{\it Ha} & From the Hadamard matrix of order 12. \\
{\it He} & Words of weight 6 in the quaternary $[6,3,4]_4$ hexacode. \\
{\it J} & Julin code, see \cite{Julin} or \cite{McWS}, Ch. 2, \S 7. \\
{\it NR} & From the binary $(15,256,5)$ Nordstrom-Robinson code. \\
{\it TH} & Ternary $[13,10,3]_3$ Hamming code. \\
{\it V} & From \cite{VAvL}. \\
{\it cy} & From a cyclic code, see \S\ref{cyclic}. \\
{\it d} & Follows from lower bound for larger $d$ (Proposition \ref{deriv}(vi)). \\
{\it j} & Juxtaposition, see \S\ref{juxta}. \\
{\it jb} & Juxtaposition, using two partitioned codes, see \S\ref{juxta}. \\
{\it jc} & Juxtaposition, using one partitioned code, see \S\ref{juxta}. \\
{\it jx} & Juxtaposition plus additional words, see \S\ref{juxta}. \\
{\it l} & Linear code. \\
{\it u} & From the $(u,u+v)$ construction (Proposition \ref{uuplusv}). \\
{\it x} & Explicit construction, see \S\ref{explicit}. \\
{\it xc} & Explicit construction by taking a union of cosets, see \S\ref{cosets}.
\end{tabular}

\medskip
Key to Tables $B_2$--$B_9$.~~ Upper bounds:

\nopagebreak
\quad

\nopagebreak
\begin{tabular}{ll}
{\it B5} & See \cite{BBMOS}. \\
{\it BB} & See \cite{BB}. (This also falls under $L2$.) \\
{\it K} & See \cite{KLV}. \\
{\it L} & Pure LP bound, using only the Delsarte inequalities. \\
{\it L1} & LP bound, with additional inequalities for words of weight $d$,
cf. Section \ref{compar}. \\
$L\alpha$ & LP bound, with the additional inequality $(L\alpha)$,
($\alpha = 2,4,5,6,7$). \\
{\it LX} & LP bound, with several of the abovementioned additional inequalities. \\
{\it LZ} & LP bound plus integrality, see Section \ref{compar}. \\
{\it P} & From the Plotkin bound. \\
{\it Sz} & From Lemma \ref{szegedy}. \\
{\it d} & Follows from upper bound for smaller $d$ (Proposition \ref{deriv}(vi)). \\
{\it e} & Exhaustive search. \\
{\it s} & By Lemma \ref{bigsphere}. \\
{\it t} & By Lemma \ref{perfect}.
\end{tabular}
}

\section*{Acknowledgements}
NJAS thanks
David Johnson (see \cite{DSJ}) and Mauricio Resende (see \cite{GRASP})
for assistance with clique-finding programs,
and Mario Szegedy (cf. \cite{ms}) for improving three entries in the tables
(see the text).

\begin{thebibliography}{}

\bibitem{DSJ} D.~Applegate and D.~S.~Johnson, personal communication, 1993.
Their programs can be obtained from
{\tt ftp://dimacs.rutgers.edu/pub/challenge/graph/solvers}

\bibitem{Best} M.~R.~Best,
``Binary codes with a minimum distance of four,''
{\it IEEE Trans. Inform. Theory\/}, vol. 26, pp. 738--742, 1980.

\bibitem{BB} M.~R.~Best and A.~E.~Brouwer,
``The triply shortened binary Hamming code is optimal,''
{\it Discrete Math.\/}, vol. 17, pp. 235--245, 1977.

\bibitem{BBMOS} M.~R.~Best, A.~E.~Brouwer, F.~J.~MacWilliams,
A.~M.~Odlyzko, and N.~J.~A.~Sloane,
``Bounds for binary codes of length less than 25,''
{\it IEEE Trans. Inform. Theory\/}, vol. 24, pp. 81--93, 1978.

\bibitem{BE95} S. Bitan and T. Etzion,
``Constructions for optimal constant weight cyclically permutable codes
and difference families,''
{\it IEEE Trans. Inform. Theory\/}, vol. 41, pp. 77--87, 1995.

\bibitem{blo} A. Blokhuis and C. W. H. Lam,
``More coverings by rook domains,''
{\it J. Combin.\ Theory Ser.\ A\/}, vol. 36, pp. 240--244, 1984.

\bibitem{BCN} A.~E.~Brouwer, A.~M.~Cohen, and A.~Neumaier,
{\it Distance-Regular Graphs\/},
Ergebnisse der Mathematik 3.18, Heidelberg: Springer, 1989.

\bibitem{BSSS} A.~E.~Brouwer, J.~B.~Shearer, N.~J.~A.~Sloane, and W.~D.~Smith,
``A new table of constant weight codes,''
{\it IEEE Trans. Inform. Theory\/}, vol. 36, pp. 1334--1380, 1990.

\bibitem{CS} J.~H.~Conway and N.~J.~A.~Sloane,
{\it Sphere Packings, Lattices and Groups\/}, 2nd ed.,
Grundlehren der math. Wissenschaften 290, New York: Springer, 1993.

\bibitem{dav} R.~Davies and G.~F.~Royle,
``Graph domination, tabu search and the football pool problem,''
{\it Discrete Appl. Math.\/}, to appear.

\bibitem{Dey} A.~Dey,
{\it Theory of Block Designs\/},
New Delhi: Wiley, 1986.

\bibitem{EG93} T.~Etzion and G.~Greenberg,
``Constructions of mixed perfect codes and other covering codes,''
{\it IEEE Trans. Inform. Theory\/}, vol. 39, pp. 209--214, 1993.

\bibitem{GRASP} T.~A.~Feo, M.~G.~C.~Resende, and S.~H.~Smith,
``A greedy randomized adaptive search procedure for maximum
independent set,''
{\it Oper. Res.\/}, vol. 42, pp. 860--878, 1994.

\bibitem{Glover} F.~Glover,
``Tabu search---part I,''
{\it ORSA J. Comput.\/}, vol. 1, pp. 190--206, 1989.

\bibitem{Godsil} C.~D.~Godsil,
{\it Algebraic Combinatorics\/},
New York: Chapman \& Hall, 1993.

\bibitem{HHLO2} H.~H\"am\"al\"ainen, I.~Honkala,
S.~Litsyn, and P.~\"Osterg\aa rd,
``Football pools---a game for mathematicians,''
{\it Amer. Math. Monthly\/}, vol. 102, pp. 579--588, 1995.

\bibitem{HR} H.~H\"am\"al\"ainen and S.~Rankinen,
``Upper bounds for football pool problems and mixed covering codes,''
{\it J. Combin. Theory Ser. A\/}, vol. 56, pp. 84--95, 1991.

\bibitem{Heijnen} P.~W.~Heijnen,
%``Er bestaat geen binaire [33,9,13]-code,''
``There exists no binary [33,9,13]-code'' (in Dutch),
Master's dissertation, Delft Univ. of Technol., 1993.

\bibitem{Jaffe} D.~B.~Jaffe,
``Binary linear codes: new results on nonexistence,''
Technical Report, Dept. of Math. and Statistics,
Univ. of Nebraska, October 1996.
{\tt http://www.math.unl.edu/$\sim$djaffe/codes/code.ps.gz}

\bibitem{Julin} D.~Julin,
``Two improved block codes,''
{\it IEEE Trans. Inform. Theory\/}, vol. 11, p. 459, 1965.

\bibitem{kam} H.~J.~L. Kamps and J. H. van Lint,
``A covering problem,''
{\it Colloq.\ Math.\ Soc.\ J\'anos Bolyai\/}, vol. 4, pp. 679--685, 1970.

\bibitem{KLV} Y.~Klein, S.~Litsyn, and A.~Vardy,
``Two new bounds on the size of binary codes with a minimum distance
of three,''
{\it Des. Codes Cryptogr.\/}, vol. 6, pp. 219--227, 1995.

\bibitem{KP} F.~R.~Kschischang and S.~Pasupathy,
``Some ternary and quaternary codes and associated sphere packings,''
{\it IEEE Trans. Inform. Theory\/}, vol. 38, pp. 227--246, 1992.

\bibitem{vLvW} J.~H.~van~Lint,~jr. and G.~J.~M.~van~Wee,
``Generalized bounds on binary/ternary mixed packing and covering codes,''
{\it J. Combin. Theory Ser. A\/}, vol. 57, pp. 130--143, 1991.

\bibitem{LV} S.~Litsyn and A.~Vardy,
``The uniqueness of the Best code,''
{\it IEEE Trans. Inform. Theory\/}, vol. 40, pp. 1693--1698, 1994.

\bibitem{Lizak} P.~Lizak,
``Minimum distance bounds for linear codes over GF(3) and GF(4),''
Master's dissertation, Maths. and Computer Science Dept.,
Univ. Salford, July 1992.

\bibitem{Lohinen} Lohinen (pseudonym of Olof Lax\'{e}n),
in the Finnish weekly {\it Veikkaus-Lotto\/},
nos. 41 ($N(0,6,3) \ge 37$) and 49 ($N(0,7,3) \ge 99$), 1981.

\bibitem{Mack} C.~Mackenzie and J.~Seberry,
``Maximal ternary codes and Plotkin's bound,''
{\it Ars Combin.\/}, vol. 17A, pp. 251--270, 1984.

\bibitem{McWS} F.~J.~MacWilliams and N.~J.~A.~Sloane,
{\it The Theory of Error-Correcting Codes\/},
Amsterdam: North-Holland, 1977.

\bibitem{Martin} W.~J.~Martin,
``Designs in product association schemes,''
preprint, May 1996.

\bibitem{ost0} P.~R.~J.~\"Osterg\aa rd,
``New upper bounds for the football pool problem for 11 and 12 matches,''
{\it J. Combin.\ Theory Ser.\ A\/}, vol. 67, pp. 161--168, 1994.

\bibitem{O3} P.~R.~J.~\"Osterg\aa rd,
``Constructing covering codes by tabu search,''
{\it J. Combin. Des.\/}, vol. 5, pp. 71--80, 1997.

\bibitem{OH} P.~R.~J.~\"Osterg\aa rd and H.~O.~H\"am\"al\"ainen,
``A new table of binary/ternary mixed covering codes,''
{\it Des. Codes Cryptogr.\/}, vol. 11, pp. 151--178, 1997.

\bibitem{OK} P. R. J. \"Osterg\aa rd and M. K. Kaikkonen,
``New single-error-correcting codes,''
{\it IEEE Trans.\ Inform.\ Theory\/}, vol. 42, pp. 1261--1262, 1996.

\bibitem{Perttula} A. Perttula, personal communication, 1995.

\bibitem{Simonis} J.~Simonis,
``MacWilliams identities and coordinate partitions,''
{\it Linear Algebra Appl.\/}, vol. 216, pp. 81--91, 1995.

\bibitem{SStufken} N.~J.~A.~Sloane and J.~Stufken,
``A linear programming bound for orthogonal arrays with mixed levels,''
{\it J. Statist. Plann. Inference\/}, vol. 56, pp. 295--306, 1996.

\bibitem{Svan} M.~Svanstr\"om,
``A ternary code from orthogonal vectors over the complex numbers,''
in {\it Proceedings of the Fifth International Workshop on Algebraic
and Combinatorial Coding Theory}, June 1 -- June 7, 1996,
Sozopol, Bulgaria, published by Unicorn, Shumen, Bulgaria, 1996,
pp. 266--269.

\bibitem{ms} M.~Szegedy,
``CKit: a toolkit for generating C programs,'' in preparation.

\bibitem{Taguchi} G. Taguchi,
{\it System of Experimental Design\/},
White Plains, New York: UNIPUB/Krause, 1987.

\bibitem{thor} Thor (pseudonym), in {\it Tippernes Systembok 16\/},
published by Tippebladet Tips, Oslo, 1992.

\bibitem{VAvL} 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)$,''
{\it Discrete Appl. Math.\/}, vol. 45, pp. 71--87, 1993.

\bibitem{vW} G.~J.~M.~van~Wee,
``Bounds on packings and coverings by spheres in $q$-ary and mixed
Hamming spaces,''
{\it J. Combin. Theory Ser. A\/}, vol. 57, pp. 117--129, 1991.

\end{thebibliography}


\bigskip
\noindent{\bf A. E. Brouwer}
Department of Mathematics,
Eindhoven University of Technology,
P.O. Box 513, 5600 MB \ Eindhoven, The Netherlands.\\
 e-mail: aeb@cwi.nl

\bigskip
\noindent{\bf Heikki O. H\"am\"al\"ainen}
Lehtotie 28, 41120 Puuppola, Finland.

\bigskip
\noindent{\bf Patric R. J. \"Osterg\aa rd}
Department of Computer Science and Engineering, Helsinki University
of Technology, P.O. Box 1100, 02015 HUT, Finland.\\
 e-mail: Patric.Ostergard@hut.fi

\bigskip
\noindent{\bf N. J. A. Sloane}
Information Sciences Research Center,
AT\&T Labs--Research,
180 Park Avenue, Florham Park, NJ 07932-0971, USA
\\
 e-mail: njas@research.att.com

\end{document}


