\input amstex
\font\sm=cmr8
\documentstyle{amsppt}
\hsize5.4in
\magnification=\magstep1
\nologo

\redefine \d{\roman d}
\define \Proof{\noindent {\it Proof\/}.\ \ \ }

\title Ternary covering codes\endtitle
\author laurent habsieger \endauthor

\font\smcp=cmcsc8 
\headline={\ifnum\pageno>1 {\smcp the electronic journal of combinatorics 3 (2) (1996), \#R23\hfill\folio} \fi} 


\centerline{Some new lower bounds for ternary covering codes}

\vskip 1 cm
\centerline{Laurent Habsieger
\footnote{partially supported by the EC grant CHRX-CT93-0400 and the
``PRC maths-info\rq\rq}}
\vskip 12pt
\centerline{\sm Submitted: February 23, 1995; Accepted: January 22, 1996}


\vskip 1.5 cm
\centerline{To Dominique Foata, on the occasion of his sixtieth
birthday}
%\hskip 3.9 cm\hbox{To Dominique Foata, on the occasion of his sixtieth
%birthday}



\vskip 2 cm
\vbox{
\bf Mailing address\rm :

Laboratoire d'Algorithmique Arithm\'etique

CNRS UMR 9936

Universit\'e  Bordeaux 1

351 cours de la Lib\'eration

33405 Talence Cedex

FRANCE}

\vskip 1 cm
\bf e-mail\rm : habsiege\@ceremab.u-bordeaux.fr


\vskip 2 cm

\bf Abstract\rm :
In [5], we studied binary codes with covering radius one
via their characteristic functions. This gave us an easy way
of obtaining congruence properties and of deriving interesting
linear inequalities. In this paper we extend this approach to
ternary covering codes. We improve on lower bounds for ternary
$1$-covering codes, the so-called football pool problem,
when $3$ does not divide $n-1$. We also give new lower bounds
for some covering codes with a covering radius greater than
one.


\newpage


\heading 1. Introduction \endheading

Let $\Bbb F_3$ be the finite field with three elements and $n$ be some
positive integer. Let us put $H=(\Bbb F_3)^n$ and define the Hamming
distance between two elements $x=(x_1,\ldots,x_n)$ and
$y=(y_1,\ldots,y_n)$ of $H$ by
$\d(x,y)=\vert\{i\in\{1,\ldots,n\}\ :\ x_i\neq y_i\}\vert$.
For $x\in H$ and $r\in\Bbb Z$, the sphere of center $x$ and radius $r$
is denoted $S_r(x)$ and is defined by
$S_r(x)=\{y\in H\ :\ \d(x,y)=r\}$.
Note that $S_r(x)=\emptyset$ if $r\notin\{0,\ldots,n\}$, and
$$\vert S_r(x)\vert=2^r{n\choose r}\,,\eqno(1)$$
if $r\in\{0,\ldots,n\}$.
The ball of center $x$ and radius $r$ is denoted $B_r(x)$ and is
defined by $B_r(x)=\{y\in H\ :\ \d(x,y)\le r\}$. We have
$\vert B_R(x)\vert=\sum_{r=0}^R 2^r{n\choose r}$.


Let $R$ be a positive integer.
A ternary code with covering radius $R$ is a subset $C$ of $H$ such
that the following covering condition holds:
$$\forall x\in H\,,\ \exists y\in C\,:\ \d(x,y)\le R\,.\eqno(2)$$
The problem of determining $K_3(n,R)$ the minimal cardinality of
$C$ has been widely studied in the last decade (see [2] for a complete
bibliography).

In [5] we gave an algebraic interpretation of the geometric
theory of excesses for binary covering codes.
In this article we adapt this point of view to ternary covering codes.
We first introduce in Section 2 the formalism that will be used
throughout the paper. In Section 3, we present general characteristics
of our approach when the covering radius equals one, 
the so-called football pool
problem. We then apply it to the cases $n\equiv2\mod3$ and
$n\equiv0\mod3$, in Section 4. In Section 5 we deal with the case
of a covering radius which is greater than one, and give general
properties. We use them in Section 6 to get new lower bounds for some
covering codes, with a covering radius greater than one.


\heading 2. Preliminary lemmas\endheading


Let $F$ be a real function defined on $H$. For $i\in\Bbb Z$,
let us introduce the function $F_i$ defined by
$$F_i(x)=\sum_{y\in S_i(x)} F(y)\,.$$
Note that $F_i=0$ if $i\notin\{0,\ldots,n\}$, $F_0=F$ and
$\sum_{0\le i\le n}F_i=\vert F\vert$, where
$$\vert F\vert=\sum_{x\in H} F(x)\,.$$
It is also clear, by definition and by (1), that
$$\vert F_i\vert=2^i{n\choose i}\vert F\vert\,.\eqno(3)$$

We shall make extensive use of the following lemma.

\proclaim{Lemma 1} For $i,j\in\Bbb Z$, we have
$$(F_i)_j=\sum_{k\in\Bbb N} \left(\sum_{m=0}^i {k\choose i-m}
{n-k\choose m}{i-m\choose i+j-k-2m} 2^m\right)F_k\,.$$
\endproclaim

\Proof By definition and by using the isometric property of the
translations and permutations for the Hamming distance, we get
$$\eqalign{
(F_i)_j(x)&=\sum_{\d(x,y)=j}\sum_{\d(y,z)=i}F(z)\cr
&=\sum_{k\in\Bbb N} \sum_{\d(x,z)=k}
\vert\{y\in H\ :\ \d(x,y)=j\ \hbox{and}\ \d(y,z)=i\}\vert F(z)\cr
&=\sum_{k\in\Bbb N}
\vert\{y\in H\ :\ \d(y,0)=j\ \hbox{and}\ \d(y,z_k)=i\}\vert
F_k(x)\,,}$$
where $z_k$ is the vector of $H$ starting with $k$ $1$'s and ending
with $n-k$ $0$'s. Let us find the shape of 
an element $y\in H$ such that $\d(y,0)=j$ and
$\d(y,z_k)=i$. Let $m$ denote the number of nonzero coordinates
among the $n-k$ last coordinates, and let $\alpha_l$ be the number
of $l$'s among the $k$ first coordinates, for $l=0,1,2$. Since we
are dealing with ternary codes, we must have
$\alpha_0+\alpha_1+\alpha_2=k$. Moreover the conditions $\d(x,0)=j$ and
$\d(y,z_k)=i$ may be stated as $\alpha_1+\alpha_2=j-m$ and 
$\alpha_0+\alpha_2=i-m$. Thus $(\alpha_0,\alpha_1,\alpha_2)$ satisfies
to the system
$$\left\{ \eqalign{&\alpha_0+\alpha_1+\alpha_2=k\cr
&\alpha_1+\alpha_2=j-m\cr
&\alpha_0+\alpha_2=i-m}\right.$$
We find this way $(\alpha_0,\alpha_1,\alpha_2)=(k+m-j,k+m-i,i+j-k-2m)$.
The number of such codewords is 
$${(\alpha_0+\alpha_1+\alpha_2)!\over \alpha_0! \alpha_1! \alpha_2!}
={k!\over (k+m-j)! (k+m-i)! (i+j-k-2m)!}\,.$$
Since the number of codewords of length $n-k$ with $m$ nonzero
coordinates is ${n-k\choose m}2^m$, we get
$$\displaylines{\vert\{y\in H\ :\ \d(x,0)=j\ \hbox{and}\ 
\d(y,z_k)=i\}\vert\hfill\cr\hfill =\sum_{m=0}^i 
{k! \over (k+m-j)! (k+m-i)! (i+j-k-2m)!}{n-k\choose m}2^m\,,}$$
and the lemma follows.
\qed

Let us apply this lemma to an easy case.

\proclaim{Lemma 2} For $j\in\Bbb Z$, we have
$$(F_0+F_1)_j=2(n-j+1)F_{j-1}+(j+1)(F_j+F_{j+1})\,.$$
\endproclaim

\Proof We use Lemma 1 with $i=0,1$ to obtain
$$\eqalign{
(F_0+F_1)_j&=F_j+\sum_{k\in\Bbb N}F_k\sum_{m=0}^1
{k\choose 1-m}{n-k\choose m}{1-m\choose 1+j-k-2m} 2^m\cr
&=F_j+\sum_{k\in\Bbb N}F_k\left(k{1\choose j-k+1}
+2(n-k){0\choose j-k-1}\right)\cr
&=F_j+(j+1)F_{j+1}+jF_j+2(n-j+1)F_{j-1}\,,}$$
and the result is proved.
\qed

Let $R$ be a positive integer and $C$ be a $R$-covering code of $H$,
i. e. a subset of $H$ that satisfies (2).
Let $A$ denote its characteristic function. Then the
covering condition (2) becomes:
$$\forall x\in H\,,\ (A_0+\cdots+A_R)(x)\ge1\,.$$
As in [5], put $\delta=A_0+\cdots+A_R-1$, so that $\delta$ is a
function defined on $H$ that takes nonnegative integer values.
As usual, we put $Z=\{x\in H\ :\ \delta(x)>0\}$. The function $\delta$
is closely related to the theory of excesses, since $\delta(x)$ just
equals the excess on $\{x\}$. Moreover, by (3), we
have
$$\vert\delta\vert=\left(\sum_{r=0}^R 2^r{n\choose r}\right)
\vert C\vert-3^n\,.\eqno(4)$$
Let us first study the case $R=1$.


\heading 3. General lemmas for covering radius one\endheading


In this case Lemma 2 gives the general form for the $\delta_i$'s:
$$\delta_i=2(n+1-i)A_{i-1}+(i+1)(A_i+A_{i+1})-2^i{n\choose i}
\,.\eqno(5)$$
For instance we have
$$\left\{\aligned
\delta_1&=2nA_0+2(A_1+A_2)-2n\,,\cr
\delta_2&=2(n-1)A_1+3(A_2+A_3)-2n(n-1)\,,\endaligned\right.$$
which already shows that $\delta_1$ is always even.
We shall now give several other properties of the delta function.

\proclaim{Lemma 3} For any element $x$ in $H$ such that $\delta(x)$
is odd, we have the inequality
$$\left({\delta_1\over2}+\delta_2\right)(x)\ge n\,.$$
\endproclaim

\Proof Let $y$ be in $S_1(x)$. Let ${\bar y}$ denote the unique
element of $S_1(x)\cap S_1(y)$. Since $\delta_1(y)$ is even, we have
$$0\equiv \delta_1(y)\equiv 1+\delta({\bar y})+
\sum_{z\in S_2(x)\cap S_1(y)}\delta(z) \ \mod2\,,$$
which implies that
$$\delta({\bar y})+\sum_{z\in S_2(x)\cap S_1(y)}\delta(z)\ge1\,.$$
Summing over $y$ gives the property
$$\eqalign{
2n&\le \sum_{y\in S_1(x)}\delta({\bar y})+
\sum_{y\in S_1(x)}\sum_{z\in S_2(x)\cap S_1(y)}\delta(z)\cr
&=\delta_1(x)+\sum_{z\in S_2(x)} \sum_{y\in S_1(x)\cap
S_1(z)}\delta(z)=\delta_1(x)+\sum_{z\in S_2(x)}2\delta(z)\cr
&=\delta_1(x)+2\delta_2(x)\,,}$$
and the lemma is proved.
\qed

\proclaim{Lemma 4} $${\delta_1\over2}+\delta_2\ge{A_1\choose2}\,.$$
\endproclaim

\Proof We shall use the notations of the preceeding proof. Let us put
$$E_1=\left\{ \{x_1,x_2\}\subset S_1(x)\cap C\ :\ x_2={\bar
x_1}\right\}\ \hbox{and}\ E_2=\left\{ \{x_1,x_2\}\subset
S_1(x)\cap C\ :\ x_2\neq{\bar x_1}\right\}\,.$$
For $\{x_1,x_2\}\in E_1$, the points $x$, $x_1$ and $x_2$ are collinear.
This implies that $\delta(y)\ge1$ for $y\in\{x,x_1,x_2\}$, which shows
that
$${\delta(x_1)+\delta(x_2)\over2}\ge1\,.$$
For $\{x_1,x_2\}\in E_2$, the point $x_1+x_2-x$ belongs to
$S_2(x)\cap S_1(x_1)\cap S_1(x_2)$, which shows that
$\delta(x_1+x_2-x)\ge1$.

Combining these results gives the inequalities
$$\eqalign{
{A_1(x)\choose 2}=\sum_{\{x_1,x_2\}\subset S_1(x)\cap C} 1
&\le \sum_{\{x_1,x_2\}\in E_1}{\delta(x_1)+\delta(x_2)\over2}
+\sum_{\{x_1,x_2\}\in E_2}\delta(x_1+x_2-x)\cr
&\le {\delta_1(x)\over2}+\delta_2(x)\,,}$$
and the lemma is proved.
\qed

\proclaim{Lemma 5} For any element $x$ of $H$ such that $\delta(x)$ is
even and $\delta_2(x)=1$, we have $\delta_1(x)\ge2$.\endproclaim

\Proof The proof proceeds as in the previous lemma and we use
again the notations of Lemma 3.
If $\delta_2(x)$ equals $1$, there exists $y\in S_2(x)$ such
that $\delta(y)=1$. For $z\in S_1(x)\cap S_1(y)$, we have
$\delta_1(z)=\delta(x)+\delta({\bar z})+1\equiv1+\delta({\bar
z})\equiv0\mod2$, which shows that $\delta_1(x)\ge\delta({\bar
z})\ge1$. Since $\delta_1(x)$ is even, the lemma is proved.
\qed

\proclaim{Lemma 6} For any element $x$ of $C$, we have $\delta_1(x)
\ge 2\delta(x)$.\endproclaim

\Proof For $x$ in $C$, we have $\delta(x)=A_1(x)$ and
$\delta_1(x)=2(A_1(x)+A_2(x))$, which makes the lemma obvious.
\qed

 We shall also need the quantity $A_3(n,3)$, the maximum cardinality
of a subset of $H$ such that any two distinct elements of this subset
have distance at least $3$. This quantity also equals the maximum
number of disjoint spheres of radius one in $H$. Let us put
$$C_0=\{c\in C\ :\ \d(c,C\setminus\{c\})\ge3\}
=\{c\in C\ :\ A_1(c)=A_2(c)=0\}\,.$$
By definition we have the estimate
$$\vert C_0\vert\le A_3(n,3)\,.\eqno(6)$$


\heading 4. Applications to the football pool problem\endheading

In this section, we shall first study the case $n\equiv0\mod3$, then
the case $n\equiv2\mod3$, and we shall end with an updated table
of the best lower bounds of which the author is aware.

Let $n$ be a positive multiple of $3$. We introduce the
nonnegative function 
$$\varphi=2\delta+3{\delta_1\over2}+\delta_2\,.$$
By (5), we also have
$\varphi=(3n+2)A_0+(2n+3)A_1+6A_2+3A_3-2n^2-n-2$, which shows that
$$\varphi\equiv 1-A_0\mod3\,.\eqno(7)$$
We shall use this property to prove the following crucial lemma.

\proclaim{Lemma 7} For $x$ in $H\setminus C$, we have
$\varphi(x)\ge4$. \endproclaim

\Proof For $x$ in $H\setminus C$, we already know by (7) that
$\varphi\equiv1\mod3$. If $\varphi(x)$ equals $1$, we must have,
by definition, $\delta(x)=\delta_1(x)=0$ and $\delta_2(x)=1$,
which is impossible by Lemma 5. Therefore $\varphi(x)$ is
greater than one, and one concludes by using (7).
\qed

We need one more lemma before estimating the size of $\vert C\vert$.

\proclaim{Lemma 8} For  $y$ in $Z$, we have
$2A_0+{3\over2}A_1+A_2\ge{7\over2}$.\endproclaim

\Proof For $y\in (H\setminus C)\cap Z$, the conditions $\delta(y)\ge1$
and $\delta_1(y)\ge0$ imply the lower bounds $A_1(y)\ge2$ and
$(A_1+A_2)(y)\ge n$, which show that $(2A_0+{3\over2}A_1+A_2)(y)\ge
n+1\ge{7\over2}$.

For $y\in C\cap Z$, the condition $\delta(y)\ge1$ implies that
$A_1(y)\ge1$. We therefore have $2A_0+{3\over2}A_1+A_2\ge2+{3\over2}=
{7\over2}$ and the proof of the lemma is complete.
\qed

Let us now use these results to obtain a lower bound for $\vert
C\vert$.

\proclaim{Theorem 9} Let $n$ be a positive integer, with
$n\equiv0\mod3$. Then we have
$$K_3(n,1)\ge {(4n^2+2n+5)3^n\over(2n+1)(4n^2+2n-3)+8}\,.$$
\endproclaim

\Proof Let us put $S=\sum_{x\in H\setminus C}\varphi(x)$. By
definitions, we obtain
$$\eqalign{
S&=\sum_{x\in H\setminus C}\left(2\delta+3{\delta_1\over2}+\delta_2
\right)(x)\cr
&=\sum_{y\in H}\delta(y) \left(2\vert S_0(y)\cap(H\setminus C)\vert+
{3\over2}\vert S_1(y)\cap(H\setminus C)\vert+
\vert S_2(y)\cap(H\setminus C)\vert\right)\cr
&=\sum_{y\in Z} \delta(y)\left(2n^2+n+2-\left(2A_0+{3\over2}A_1+A_2
\right)(y)\right)\,.}$$
We then use Lemma 8 and formula (4) to get
$$S\le \left(2n^2+n+2-{7\over2}\right)\vert\delta\vert
=\left(2n^2+n-{3\over2}\right)((2n+1)\vert C\vert-3^n)\,.$$
Since Lemma 7 ensures us that $S\ge 4\vert H\setminus C\vert
=4(3^n-\vert C\vert)$, we have
$$8(3^n-\vert C\vert)\le 2S\le (4n^2+2n-3)((2n+1)\vert
C\vert-3^n)\,,$$
and the theorem follows.
\qed

This theorem gives the following improvements. We indicate in
parenthesis the former best previous bound, according to [2].
$$\eqalign{
K_3(9,1)&\ge 1060 \qquad(1048)\cr
K_3(12,1)&\ge 21531\qquad(21395)}$$
Theorem 9 can be refined by a much closer analysis of the
size of $\varphi(x)$, according to the possible values of $A_1(x)$.
We can prove the following inequality
$$(4n^2+2n-3)\vert\delta\vert\ge8(3^n-\vert C\vert)+
2(n-3)\vert (H\setminus C)\cap Z\vert\,,$$
which extends the last inequality in the proof of Theorem 9.
However, it does not seem easy to get a non-trivial estimate for
$\vert (H\setminus C)\cap Z\vert$. Indeed, when $n\not\equiv0\mod3$,
for instance $n=4,5$, we can have $Z\subset C$ for an optimal covering
code $C$.

Let us now study the case $n\equiv2\mod3$.

Let $n$ be a positive integer with $n\equiv2\mod3$. In this case
 we introduce
the nonnegative function 
$$\varphi=\delta+{3\over2}\delta_1+\delta_2\,.$$
By (5) we have $\varphi=(3n+1)A_0+2(n+1)A_1+6A_2+3A_3-2n^2-n-1$,
which shows that
$$\varphi\equiv 1+A_0\mod3\,.\eqno(8)$$

We shall need the following crucial lemma.

\proclaim{Lemma 10} We have
$$\varphi(x)\ge\left\{\aligned &4\cr &2\cr &5\cr\endaligned\qquad
\aligned
&\hbox{if $x\in H\setminus C$,}\cr
&\hbox{if $x\in C_0$,}\cr
&\hbox{if $x\in C\setminus C_0$.}\cr\endaligned\right.$$
\endproclaim

\Proof For $x$ in $H\setminus C$, we have $\varphi(x)\equiv 1\mod3$,
by
(8). If $\varphi(x)$ equals $1$, either $(\delta(x),\delta_1(x),
\delta_2(x))=(1,0,0)$ or
$(\delta(x),\delta_1(x),\delta_2(x))=(0,0,1)$.
The first case is impossible by Lemma 3, as is the second by
Lemma 5. Therefore we have $\varphi(x)\ge4$.

For $x$ in $C$, we have $\varphi(x)\equiv 2\mod3$, by (8). This shows
that $\varphi(x)\ge 2$. Moreover, for $x\in C\setminus C_0$, we know
that $(\delta+\delta_1)(x)$ is a positive integer. By Lemma 6, we
cannot have both $\delta(x)>0$ and $\delta_1(x)=0$. This implies that,
for $x\in C\setminus C_0$, $\delta_1(x)>0$ and thus $\varphi(x)\ge3$.
By (8) this proves that $\varphi(x)\ge5$ for any $x\in C\setminus
C_0$.
\qed


Let us apply this lemma to get a lower bound for $\vert C\vert$.

\proclaim{Theorem 11} Let $n$ be a positive integer, with
$n\equiv2\mod3$. Then we have
$$K_3(n,1)\ge {(2n^2+n+5)3^n-3A_3(n,3)\over(2n+1)(2n^2+n+1)-1}\,.$$
\endproclaim

\Proof We compute $\vert\varphi\vert$:
$$\eqalign{
\vert\varphi\vert&=\sum_{x\in H\setminus C}\varphi(x)+
\sum_{x\in C\setminus C_0}\varphi(x)+\sum_{x\in C_0}\varphi(x)\cr
&\ge 4(3^n-\vert C\vert)+2\vert C_0\vert+5(\vert C\vert-\vert
C_0\vert)\qquad\hbox{by Lemma 10,}\cr
&\ge 4.3^n+\vert C\vert-3 A_3(n,3)\qquad\hbox{by (6).}}$$
Moreover we have
$$\vert\varphi\vert=(2n(n-1)+3n+1)\vert\delta\vert=
(2n^2+n+1)((2n+1)\vert C\vert-3^n)\,,$$
by (3-4) and the definition of $\varphi$. A straightforward
calculation then completes the proof of the theorem.
\qed

This theorem, together with the upper
bounds for $A_3(n,3)$ to be found in [7], gives the following improvements. 
We indicate in
parenthesis the former best lower bound for $K_3(n,1)$,
according to [1,2,6].
$$\eqalign{
K_3(8,1)&\ge 397 \qquad(393)\cr
K_3(11,1)&\ge 7822\qquad(7767)\cr
K_3(14,1)&\ge166526\qquad(165775)}$$


We give below an updated list of the best lower bounds for
$K_3(n,1)$ when $n\le14$. We consider only those values of $n$
for which $K_3(n,1)$ is still unknown. The bound $K_3(6,1)\ge63$
was stated without proof in [9] ; we proved in [3] the lower
bound
$K_3(6,1)\ge60$.
$$\matrix n  &\hbox{Lower bound for $K_3(n,1)$} &\hbox{Reference} \cr
6  &63 &[9] \cr
7 &153 &[4] \cr
8 &397 &\hbox{Theorem 11}\cr
9 &1060 &\hbox{Theorem 9}\cr
10&2818&[3]\cr
11&7822&\hbox{Theorem 11}\cr
12&21531&\hbox{Theorem 9}\cr
14&166526&\hbox{Theorem 11}\endmatrix$$


\heading 5. General results for covering radii greater than
one\endheading


Let $R$ be an integer greater than one.
Let us recall that $\delta=A_0+\cdots+A_R-1$. Lemma 1 gives
$$\eqalign{
&\delta_1=2n(A_0+\cdots+A_{R-1}-1)+2RA_R+(R+1)A_{R+1}\,,\cr
&\delta_2=2n(n-1)(A_0+\cdots+A_{R-2}-1)+2(R-1)(2n-R)A_{R-1}\cr
&\hskip 5cm+2R(n-1)A_R+3{R+1\choose2}A_{R+1}+{R+2\choose2}A_{R+2}\,.}$$
This shows that
$$\eqalign{
2\delta+\delta_1&=2(n+1)(A_0+\cdots+A_{R-1}-1)+(R+1)(2A_R+A_{R+1})\cr
&\equiv2(n+1)(A_0+\cdots+A_{R-1}-1)\mod(R+1)\,.}$$
Let us put $\epsilon=(R+1)\lceil2(n+1)/(R+1)\rceil-2(n+1)$, where
$\lceil t\rceil$ denotes the least integer greater than or equal to
$t$. We then have $\epsilon\in\{0,\ldots,R\}$ and
$$2\delta+\delta_1\equiv\epsilon(1-A_0-\cdots-A_{R-1})\mod(R+1)\,.
\eqno(9)$$
Let us put
$$T=\{x\in H\ :\ A_0(x)=\cdots=A_{R-1}(x)=0\}=\{x\in H\ :\ B_{R-1}(x)
\cap C=\emptyset\}\,.$$
We have
$$\vert T\vert=\sum_{x\in T}(1-A_0-\cdots-A_{R-1})\ge
\sum_{x\in H}(1-A_0-\cdots-A_{R-1})=3^n-\left(\sum_{r=0}^{R-1}
2^r{n\choose r}\right)\vert C\vert\,,\eqno(10)$$
by (3). Moreover, for $x\in T$,
we have $(2\delta+\delta_1)(x)\equiv\epsilon\mod(R+1)$ and thus
$(2\delta+\delta_1)(x)\ge\epsilon$, since $\epsilon$ belongs to
$\{0,\ldots,R\}$. For $x\in H\setminus T$, we know that
$$\epsilon(1-A_0-\cdots-A_{R-1})(x)\le0\le(2\delta+\delta_1)(x)\,.$$
Therefore we have
$$2\delta+\delta_1\ge\epsilon(1-A_0-\cdots-A_{R-1})\,,\eqno(11)$$
which gives a lower bound for $\vert C\vert$. When $\epsilon$ is
greater than one, we shall study the properties (9) and (11) on
spheres of radius one. When $\epsilon$ equals one,
the inequality (11) can be refined, as will be
shown in the next section. Before doing so, we shall need
to estimate the number of elements of $T$ in spheres or balls.
The next lemma gives lower bounds for the number of elements in
spheres which are not in $T$ and is analogous to Lemma 2 in [1].

\proclaim{Lemma 12} For $n\ge (R+1)/2$, we have
$$\vert S_1(y)\cap(H\setminus T)\vert\ge\cases R&\text{if $y\in
H$,}\cr R+1&\text{if $y\in Z$.}\endcases$$
\endproclaim

\Proof Let $y$ be in $H$. There exists $c$ in $C\cap B_R(y)$.

Then we have
$$\vert S_1(y)\cap(H\setminus T)\vert\ge
\vert S_1(y)\cap B_{R-1}(c)\vert
=\cases R&\text{if $\d(y,c)=R$,}\cr
2(R-1)&\text{if $\d(y,c)=R-1$,}\cr
2n&\text{if $\d(y,c)\le R-2$,}\endcases$$
which shows that $\vert S_1(y)\cap(H\setminus T)\vert\ge R$.
If $y\in Z$, there exists another element $d$ in $C\cap B_R(y)$.
If $\d(y,d)=\d(y,c)=R$ or $\d(y,d)=\d(y,c)+1=R$, there is a coordinate
of $d$ which is different
from the same coordinate for $y$ and $c$. This provides
an element in $S_1(y)\cap (B_{R-1}(d)\setminus B_{R-1}(c))$.
If $\d(y,d)\le R-2$, we already know that
$\vert S_1(y)\cap B_{R-1}(c)\vert\ge 2n\ge R+1$. Thus, in every case
we have $\vert S_1(y)\cap(H\setminus T)\vert\ge R+1$ for $y\in Z$.
\qed


\heading 6. Applications with $R\ge2$\endheading


Let us start with $R=2$ and $n\equiv3\mod6$. In this case, we have
$$\eqalign{
&\delta=A_0+A_1+A_2-1\,,\cr
&\delta_1=2n(A_0+A_1-1)+4A_2+3A_3\,,\cr
&\delta_2=2n(n-1)(A_0-1)+4(n-1)(A_1+A_2)+9A_3+6A_4\,,}$$
which gives the congruence $\delta_1+2\delta\equiv1-A_0-A_1\mod3$.
Here we have $\epsilon=1$.

\proclaim{Theorem 14} Let $n$ be a positive integer with
$n\equiv3\mod6$. Then we have
$$K_3(n,2)\ge{ (2n^2+1)3^n\over (2n^2-n-2)(2n^2+1)+(n+3)(2n+1)}\,.$$
\endproclaim

\Proof Let $n$ be a positive integer with $n\equiv3\mod6$.
Let us introduce the nonnegative function $\varphi$ defined by
$$\varphi={1\over3}(\delta+2\delta_1+2(A_0+A_1-1))
=\left(4{n\over3}+1\right)(A_0+A_1-1)+3A_2+2A_3\,.$$
We get
$$\eqalign{\varphi_1&={1\over3}(4(n-1)(A_0-1)
+4(n+1)\delta+3\delta_1+4\delta_2)\cr
&=2n\left(4{n\over3}+1\right)(A_0-1)+\left(26{n\over3}-4\right)A_1+
20{n\over3}A_2+15A_3+8A_4\,.}$$
 From these expressions we deduce
$${5\over2}\delta+{1\over2}\varphi+\varphi_1=
\left(8{n\over3}(n+1)+3\right)(A_0-1)+\left(28{n\over3}-1\right)A_1
+\left(20{n\over3}+4\right)A_2+16A_3+8A_4\,,$$
which gives the congruence
$${5\over2}\delta+{1\over2}\varphi+\varphi_1\equiv5(1-A_0-A_1)\mod8\,.$$
We therefore have
${5\over2}\delta+{1\over2}\varphi+\varphi_1\ge5(1-A_0-A_1)$, which can
be expressed as
$$\delta_2+\delta_1+(n+3)\delta\ge(n+3)(1-A_0)-4A_1\,.$$
Let us study what happens on $T$.

For $x\in T\cap(H\setminus Z)$, we know that $\delta_2+\delta_1\ge
n+3$.
For $x\in T\cap Z$, we have $A_2(x)\ge2$. Let $z_1$, $z_2$ be in
$S_2(x)\cap C$. From the property
$S_1(z_1)\cap S_1(z_2)\cap S_2(x)\neq\emptyset$,
we deduce that $\delta_2(x)>0$, for any element $x$ in $T$. 
This in turn implies that
$(\delta_2+\delta_1)(x)\ge6$, by using the congruence property
$\delta_2+\delta_1\equiv0\mod6$.
Therefore, for any $x$ in $T$, we get
$$\delta_2+\delta_1+(n-3)\delta\ge n+3\,.$$

Summing over $T$ gives
$$\eqalign{(n+3)\vert T\vert&\le
\sum_{x\in T}( \delta_2+\delta_1+ (n-3)\delta)(x)\cr
&=\sum_{y\in Z}\delta(y)\left(\vert S_2(y)\cap T\vert+
\vert S_1(y)\cap T\vert+(n-3)\vert S_0(y)\cap T\vert\right)\,.}$$
Let us introduce the function $F$ defined on $H$ by $F(x)=
\vert S_1(x)\cap(H\setminus T)\vert-2$. By Lemma 12, we know that
$F$ is nonnegative. From Lemma 1 we obtain
$$2\vert S_2(y)\cap(H\setminus T)\vert+\vert S_1(y)\cap(H\setminus
T)\vert+2n\vert S_0(y)\cap(H\setminus T)\vert=F_1+4n\ge4n\,.$$
By Lemma 12, we also know that $\vert S_1(y)\cap(H\setminus
T)\vert\ge3$ for any $y$ in $Z$. Combining these two last
inequalities gives, for any $y$ in $Z$,
$$\displaylines{2\left(\vert S_2(y)\cap(H\setminus T)\vert+
\vert S_1(y)\cap(H\setminus T)\vert+(n-3)\vert S_0(y)\cap(H\setminus
T)\vert\right)\hfill\cr\hfill\ge 4n +3-6\vert S_0(y)\cap(H\setminus T)
\vert\ge4n-3\,,}$$
which implies that
$$(n+3)\vert T\vert\le \sum_{y\in Z}\delta(y)(
\vert S_2(y)\vert+\vert S_1(y)\vert+(n-3)\vert S_0(y)\vert-(2n-1))
=(2n^2-n-2)\vert\delta\vert\,.$$
 From (4) and (10), we obtain
$$(n+3)(3^n-(2n+1)\vert C\vert)\le (2n^2-n-2)((2n^2+1)\vert
C\vert-3^n)\,,$$
and the theorem follows.
\qed

This theorem provides the lower bound $K_3(9,2)\ge130$,
which improves on the lower bound $128$ given in [2].

Let us give a first special case, which improves on the bound
$K_3(14,2)\ge12193$ given in [6].

\proclaim{Theorem 15} $K_3(14,2)\ge12204$.\endproclaim

\Proof In this case, Lemma 1 provides the formulas
$$\eqalign{
&\delta=A_0+A_1+A_2-1\,,\cr
&\delta_1=28A_0+28A_1+4A_2+3A_3-28\,,\cr
&\delta_2=364A_0+52A_1+52A_2+9A_3+6A_4-364\,,\cr
&\delta_3=312A_1+72A_2+73A_3+16A_4+10A_5-2912\,,}$$
which imply the properties
$$\eqalign{
3\delta_3+2\delta_2+{\delta_1\over3}+{26\over3}\delta
&=746A_0+1058A_1+330A_2+240A_3+60A_4+30A_5-9482\cr
&\equiv28-4A_0-22A_1\mod{30}\,.}$$
This shows that, for any element $x$ in $T$, we have
$$(3\delta_3+2\delta_2+{1\over3}\delta_1+{26\over3}\delta)(x)\ge28\,.
\eqno(12)$$
Let us introduce the function $F$ defined on $H$ by $F(x)=
\vert S_1(x)\cap(H\setminus T)\vert-2$. By Lemma 12, we know that
$F$ is nonnegative. From Lemma 1 we obtain, for any $y\in Z$,
$$\eqalign{
&2\vert S_2(y)\cap(H\setminus T)\vert+\vert S_1(y)\cap(H\setminus T)
\vert+28\vert S_0(y)\cap(H\setminus T)\vert=F_1+56\ge56\,\cr
&3\vert S_3(y)\cap(H\setminus T)\vert+2\vert S_2(y)\cap(H\setminus T)
\vert+26\vert S_1(y)\cap(H\setminus T)\vert=F_2+728\ge728\,.}$$
We deduce from these inequalities that
$$3\vert S_3(y)\cap(H\setminus T)\vert+2\vert S_2(y)\cap(H\setminus T)
\vert+{1\over 3}\vert S_1(y)\cap(H\setminus T)\vert+{26\over 3}
\vert S_0(y)\cap(H\setminus T)\vert
\ge 18\,,\eqno(13)$$
the equality holding if and only if the quadruple
$(\vert S_3(y)\cap(H\setminus T)\vert, 
\vert S_2(y)\cap(H\setminus T)\vert, 
\vert S_1(y)\cap(H\setminus T)\vert,
\vert S_0(y)\cap(H\setminus T)\vert)$ equals $(0,0,28,1)$.
We now sum the inequality (12) over $T$ and we use (13) to obtain
$$\eqalign{
S&=\sum_{x\in T}
(3\delta_3+2\delta_2+{1\over3}\delta_1+{26\over3}\delta)(x)\cr
&=\sum_{y\in Z}\delta(y)\left(3\vert S_3(y)\cap T\vert+
2\vert S_2(y)\cap T\vert+{1\over 3}\vert S_1(y)\cap T\vert+{26\over 3}
\vert S_0(y)\cap T\vert\right)\cr
&\le \sum_{y\in Z}\delta(y)\left(3\vert S_3(y)\vert+
2\vert S_2(y)\vert+{1\over 3}\vert S_1(y)\vert+{26\over 3}
\vert S_0(y)\vert-18\right)\cr
&=9464\vert\delta\vert=28\times(338\vert\delta\vert)\,,}$$
and $S\ge28\vert T\vert\ge28(3^{14}-29\vert C\vert)$. In this way we find
$$\vert C\vert\ge {(338+1)3^{14}\over 338\times393+29}
=12203.747\ldots\,,$$
and the theorem is proved.
\qed

Let us prove another partial result, for $R=3$ and $n=13$. In this case
we have the following lower bound, which improves on the lower
bound $609$ given in [2].

\proclaim{Theorem 16} $K_3(13,3)\ge611$.\endproclaim

\Proof In this case, Lemma 1 provides the formulas
$$\eqalign{
&\delta=A_0+A_1+A_2+A_3-1\,,\cr
&\delta_1=26A_0+26A_1+26A_2+6A_3+4A_4-26\,,\cr
&\delta_2=312A_0+312A_1+92A_2+72A_3+18A_4+10A_5-312\,,\cr
&\delta_3=2288A_0+528A_1+440A_2+200A_3+136A_4+40A_5+20A_6-2288\,,}$$
which imply the properties
$$\eqalign{
\delta_3+\delta_1+14\delta&=2328A_0+568A_1+480A_2+220A_3+140A_4+40A_5+20A_6
-2328\cr
&\equiv12(1-A_0-A_1)\mod{20}\,.}$$
Let us put $T'=\{x\in H\ :\ A_0(x)=A_1(x)=0\}$, so that $\vert T'\vert
\ge 3^{13}-27\vert C\vert$, by analogy with (10). Moreover, for any
element $x$ of $T'$, we have the congruence
$(\delta_3+\delta_1+14\delta)(x)
\equiv12\mod{20}$. This shows the weaker congruence
$(\delta_3+\delta_1+4\delta)(x)\equiv2\mod{10}$. 
Therefore we get either $(\delta_3+\delta_1+4\delta)(x)=2$ or
$(\delta_3+\delta_1+4\delta)(x)\ge12$. The first case is impossible,
since
it implies $\delta(x)=0$ and contradicts the congruence
$(\delta_3+\delta_1+14\delta)(x)\equiv12\mod{20}$.
Thus we have proved that, for any element $x$ of $T'$, the inequality
$(\delta_3+\delta_1+4\delta)(x)\ge12$ holds.
Summing this last inequality over $T'$ gives
$$(2288+26+4)\vert\delta\vert\ge12\vert T'\vert\ge12(3^{13}-27
\vert C\vert)\,,$$
which in turn provides the lower bound
$$\vert C\vert\ge{(2318+12)3^{13}\over 2318\times2627+12\times27}=
610.0081\ldots\,,$$
and the theorem follows.
\qed

Let us improve the bound $K_3(14,4)\ge254$ given by Lo and Zhang [6].

\proclaim{Theorem 17} $K_3(14,4)\ge255$.\endproclaim

\Proof In this case we have
$$\eqalign{&\delta=A_0+A_1+A_2+A_3+A_4-1\,,\cr
&\delta_1=28(A_0+A_1+A_2+A_3-1)+8A_4+5A_5\,,\cr
&\delta_2=364(A_0+A_1+A_2-1)+144A_3+104A_4+30A_5+15A_6\,,}$$
which gives the properties
$$\eqalign{\delta_2+\delta&=365(A_0+A_1+A_2-1)+145A_3+105A_4+30A_5
+15A_6\cr
&\equiv 10(1-A_0-A_1-A_2)-5A_3\mod{15}\,.}$$
We now introduce the nonnegative function
$$\eqalign{\varphi&={\delta_2+\delta+10(A_0+A_1+A_2-1)+5A_3\over15}\cr
&=25(A_0+A_1+A_2-1)+10A_3+7A_4+2A_5+A_6\,.}$$
Lemma 1 gives us
$$\varphi_1=700(A_0+A_1-1)+340A_2+259A_3+108A_4+63A_5+18A_6+7A_7\,,$$
from which we deduce the congruence property
$$5\varphi_1+15\varphi+\delta_1+12\delta\equiv 5(1-A_0-A_1+3A_2+3A_3)
\mod{35}\,.$$
If $3(A_2+A_3)-A_0-A_1$ is less than or equal to $5$, we get
$5(1-A_0-A_1+3A_2+3A_3)<35$ and therefore
$$5\varphi_1+15\varphi+\delta_1+12\delta\ge 5(1-A_0-A_1+3A_2+3A_3)\,.
\eqno(14)$$
If $3(A_2+A_3)-A_0-A_1$ is greater than $5$,
we get $A_2+A_3\ge2$ from which we deduce
$\delta_1+12\delta\ge 40(A_2+A_3-1)\ge 5+15(A_2+A_3)$ 
and (14) is still true. Expressed in terms of the $A_i$'s, the
inequality (14) becomes
$$A_7+3A_6+10A_5+19A_4+42A_3+60A_2+112(A_0+A_1-1)\ge0\,.$$
Summing this last inequality over $H$ provides the following
lower bound
$$\vert C\vert\ge {112\over 2108208}3^{14}=254.098\ldots\,,$$
and the theorem follows.
\qed



\heading References\endheading


\medskip\noindent
[1] {\smc W. Chen and I. S. Honkala}, Lower bounds for $q$-ary
covering
codes, {\it IEEE Trans. Inform. Theory} {\bf 36} (1990), 664--671.

\medskip\noindent
[2] {\smc G. D. Cohen, S. N. Litsyn, A.C. Lobstein and H. F. Mattson},
Covering radius 1985--1994, preprint.

\medskip\noindent
[3] {\smc L. Habsieger}, Lower bounds for $q$-ary covering codes,
{\it J. Combin. Theory Ser. A} {\bf 67} (1994), 199--222.

\medskip\noindent
[4] {\smc L. Habsieger}, A new lower bound for the football pool
problem for $7$ matches, preprint.

\medskip\noindent
[5] {\smc L. Habsieger}, Binary codes with covering radius one: some
new lower bounds, {\it Discrete Mathematics}, submitted.

\medskip\noindent
[6] {\smc C. Lo and Z. Zhang}, New lower bounds for $K_3(n,R)$ from
linear inequalities, {\it IEEE Trans. Inform. Theory}, submitted.

\medskip\noindent
[7] {\smc 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
Applied Mathematics} {\bf 45} (1993), 71--87.

\medskip\noindent
[8] {\smc G. J. M. van Wee}, Some new lower bounds for binary and
ternary covering codes, {\it IEEE Trans. Inform. Theory} {\bf 39} 
(1993), 1422--1424.

\medskip\noindent
[9] {\smc G. J. M. Weber}, On the football pool problem for $6$
matches: a new upper bound, {\it J. Combin. Theory Ser. A} {\bf 35} 
(1983), 106--108.



\end

-----------------------------------------------------------------------------

.