Some new lower bounds for ternary covering codes

Laurent Habsieger^{1}

Submitted: February 23, 1995; Accepted: January 22, 1996

To Dominique Foata, on the occasion of his sixtieth birthday

Mailing address: Laboratoire d’Algorithmique Arithmétique CNRS UMR 9936 Université Bordeaux 1 351 cours de la Libération 33405 Talence Cedex FRANCE

e-mail: habsiege@ceremab.u-bordeaux.fr

Abstract: 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.

1partially supported by the EC grant CHRX-CT93-0400 and the “PRC maths-info”

1. Introduction

Let 𝔽_{3} be the finite field with three elements and n be some positive integer. Let us put H = (𝔽_{3})^{n} and define the Hamming distance between two elements x = (x_{1}, …, x_{n}) and y = (y_{1}, …, y_{n}) of H by d(x, y) = |{i ∈ {1, …, n} : x_{i} ≠ y_{i}}|. For x ∈ H and r ∈ ℤ, the sphere of center x and radius r is denoted S_{r}(x) and is defined by S_{r}(x) = {y ∈ H : d(x, y) = r}. Note that S_{r}(x) = ∅ if r ∉ {0, …, n}, and

|S_{r}(x)| = 2^{r}\binom{n}{r} ,  (1)

if r ∈ {0, …, n}. The ball of center x and radius r is denoted B_{r}(x) and is defined by B_{r}(x) = \{y ∈ H : d(x, y) ≤ r\}. We have |B_{R}(x)| = ∑_{r=0}^{R} 2^{r}\binom{n}{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:

∀x ∈ H , ∃y ∈ C : d(x, y) ≤ R .  (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 ≡ 2 mod 3 and n ≡ 0 mod 3, 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.

2. Preliminary lemmas

Let F be a real function defined on H. For i ∈ ℤ, let us introduce the function F_{i} defined by

F_{i}(x) = ∑_{y∈S_{i}(x)} F (y) .

Note that F_{i} = 0 if i ∉ {0, …, n}, F_{0} = F and ∑_{0≤i≤n} F_{i} = |F |, where

|F | = ∑_{x∈H} F (x) .

It is also clear, by definition and by (1), that

|F_{i}| = 2^{i}\binom{n}{i}|F | .  (3)

We shall make extensive use of the following lemma.

Lemma 1. For i, j ∈ ℤ, we have

(F_{i})_{j} = ∑_{k∈ℕ} ( ∑_{m=0}^{i} \binom{k}{i − m}\binom{n − k}{m}\binom{i − m}{i + j − k − 2m}2^{m}) F_{k} .

Proof . By definition and by using the isometric property of the translations and permutations for the Hamming distance, we get

(F_{i})_{j}(x) = ∑_{d(x,y)=j} ∑_{d(y,z)=i} F (z)

= ∑_{k∈ℕ} ∑_{d(x,z)=k} |{y ∈ H : d(x, y) = j and d(y, z) = i}|F (z)

= ∑_{k∈ℕ} |{y ∈ H : d(y, 0) = j and d(y, z_{k}) = i}|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 ∈ 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 α_{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 α_{0} + α_{1} + α_{2} = k. Moreover the conditions d(x, 0) = j and d(y, z_{k}) = i may be stated as α_{1} + α_{2} = j − m and α_{0} + α_{2} = i − m. Thus (α_{0}, α_{1}, α_{2}) satisfies to the system

\{ \begin{matrix}α_{0} + α_{1} + α_{2} = k \\ α_{1} + α_{2} = j − m \\ α_{0} + α_{2} = i − m \end{matrix}

We find this way (α_{0}, α_{1}, α_{2}) = (k + m − j, k + m − i, i + j − k − 2m). The number of such codewords is

\frac{(α_{0} + α_{1} + α_{2})!}{α_{0}!α_{1}!α_{2}!} = \frac{k!}{(k + m − j)!(k + m − i)!(i + j − k − 2m)!} .

Since the number of codewords of length n − k with m nonzero coordinates is \binom{n−k}{m}2^{m}, we get

|{y ∈ H : d(x, 0) = j and d(y, z_{k}) = i}|

= ∑_{m=0}^{i} \frac{k!}{(k + m − j)!(k + m − i)!(i + j − k − 2m)!}\binom{n − k}{m}2^{m} ,

and the lemma follows. □

Let us apply this lemma to an easy case.

Lemma 2. For j ∈ ℤ, we have

(F_{0} + F_{1})_{j} = 2(n − j + 1)F_{j−1} + (j + 1)(F_{j} + F_{j+1}) .

Proof . We use Lemma 1 with i = 0, 1 to obtain

(F_{0} + F_{1})_{j} = F_{j} + ∑_{k∈ℕ} F_{k} ∑_{m=0}^{1} \binom{k}{1 − m}\binom{n − k}{m}\binom{1 − m}{1 + j − k − 2m}2^{m}

= F_{j} + ∑_{k∈ℕ} F_{k} (k\binom{1}{j − k + 1} + 2(n − k)\binom{0}{j − k − 1})

= F_{j} + (j + 1)F_{j+1} + jF_{j} + 2(n − j + 1)F_{j−1} ,

and the result is proved. □

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:

∀x ∈ H , (A_{0} + ⋯ + A_{R})(x) ≥ 1 .

As in [5], put δ = A_{0} + ⋯ + A_{R} − 1, so that δ is a function defined on H that takes nonnegative integer values. As usual, we put Z = {x ∈ H : δ(x) > 0}. The function δ is closely related to the theory of excesses, since δ(x) just equals the excess on {x}. Moreover, by (3), we have

|δ| = (∑_{r=0}^{R} 2^{r}\binom{n}{r}) |C| − 3^{n} .  (4)

Let us first study the case R = 1.

3. General lemmas for covering radius one

In this case Lemma 2 gives the general form for the δ_{i}’s:

δ_{i} = 2(n + 1 − i)A_{i−1} + (i + 1)(A_{i} + A_{i+1}) − 2^{i}\binom{n}{i} .  (5)

For instance we have

\{ \begin{matrix}δ_{1} & = 2nA_{0} + 2(A_{1} + A_{2}) − 2n , \\ δ_{2} & = 2(n − 1)A_{1} + 3(A_{2} + A_{3}) − 2n(n − 1) , \end{matrix}

which already shows that δ_{1} is always even. We shall now give several other properties of the delta function.

Lemma 3. For any element x in H such that δ(x) is odd, we have the inequality

(\frac{δ_{1}}{2} + δ_{2}) (x) ≥ n .

Proof . Let y be in S_{1}(x). Let ȳ denote the unique element of S_{1}(x) ∩ S_{1}(y). Since δ_{1}(y) is even, we have

0 ≡ δ_{1}(y) ≡ 1 + δ(ȳ) + ∑_{z∈S_{2}(x)∩S_{1}(y)} δ(z) mod 2 ,

which implies that

δ(ȳ) + ∑_{z∈S_{2}(x)∩S_{1}(y)} δ(z) ≥ 1 .

Summing over y gives the property

2n ≤ ∑_{y∈S_{1}(x)} δ(ȳ) + ∑_{y∈S_{1}(x)} ∑_{z∈S_{2}(x)∩S_{1}(y)} δ(z)

= δ_{1}(x) + ∑_{z∈S_{2}(x)} ∑_{y∈S_{1}(x)∩S_{1}(z)} δ(z) = δ_{1}(x) + ∑_{z∈S_{2}(x)} 2δ(z)

= δ_{1}(x) + 2δ_{2}(x) ,

and the lemma is proved. □

Lemma 4.

\frac{δ_{1}}{2} + δ_{2} ≥ \binom{A_{1}}{2} .

Proof . We shall use the notations of the preceeding proof. Let us put

E_{1} = {{x_{1}, x_{2}} ⊂ S_{1}(x) ∩ C : x_{2} = x̄_{1}} and E_{2} = {{x_{1}, x_{2}} ⊂ S_{1}(x) ∩ C : x_{2} ≠ x̄_{1}} .

For {x_{1}, x_{2}} ∈ E_{1}, the points x, x_{1} and x_{2} are collinear. This implies that δ(y) ≥ 1 for y ∈ {x, x_{1}, x_{2}}, which shows that

\frac{δ(x_{1}) + δ(x_{2})}{2} ≥ 1 .

For {x_{1}, x_{2}} ∈ E_{2}, the point x_{1} + x_{2} − x belongs to S_{2}(x) ∩ S_{1}(x_{1}) ∩ S_{1}(x_{2}), which shows that δ(x_{1} + x_{2} − x) ≥ 1.

Combining these results gives the inequalities

\begin{aligned}\binom{A_{1}(x)}{2} = ∑_{\{x_{1},x_{2}\}⊂S_{1}(x)∩C} 1 & ≤ ∑_{\{x_{1},x_{2}\}∈E_{1}} \frac{δ(x_{1}) + δ(x_{2})}{2} + ∑_{\{x_{1},x_{2}\}∈E_{2}} δ(x_{1} + x_{2} − x) \\ & ≤ \frac{δ_{1}(x)}{2} + δ_{2}(x) , \end{aligned}

and the lemma is proved. □

Lemma 5. For any element x of H such that δ(x) is even and δ_{2}(x) = 1, we have δ_{1}(x) ≥ 2.

Proof . The proof proceeds as in the previous lemma and we use again the notations of Lemma 3. If δ_{2}(x) equals 1, there exists y ∈ S_{2}(x) such that δ(y) = 1. For z ∈ S_{1}(x) ∩ S_{1}(y), we have δ_{1}(z) = δ(x) + δ(z̄) + 1 ≡ 1 + δ(z̄) ≡ 0 mod 2, which shows that δ_{1}(x) ≥ δ(z̄) ≥ 1. Since δ_{1}(x) is even, the lemma is proved. □

Lemma 6. For any element x of C, we have δ_{1}(x) ≥ 2δ(x).

Proof . For x in C, we have δ(x) = A_{1}(x) and δ_{1}(x) = 2(A_{1}(x) + A_{2}(x)), which makes the lemma obvious. □

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 ∈ C : d(c, C \ {c}) ≥ 3} = {c ∈ C : A_{1}(c) = A_{2}(c) = 0} .

By definition we have the estimate

|C_{0}| ≤ A_{3}(n, 3) .  (6)

4. Applications to the football pool problem

In this section, we shall first study the case n ≡ 0 mod 3, then the case n ≡ 2 mod 3, 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

φ = 2δ + 3\frac{δ_{1}}{2} + δ_{2} .

By (5), we also have φ = (3n + 2)A_{0} + (2n + 3)A_{1} + 6A_{2} + 3A_{3} − 2n^{2} − n − 2, which shows that

φ ≡ 1 − A_{0} mod 3 .  (7)

We shall use this property to prove the following crucial lemma.

Lemma 7. For x in H \ C, we have φ(x) ≥ 4.

Proof . For x in H \ C, we already know by (7) that φ ≡ 1 mod 3. If φ(x) equals 1, we must have, by definition, δ(x) = δ_{1}(x) = 0 and δ_{2}(x) = 1, which is impossible by Lemma 5. Therefore φ(x) is greater than one, and one concludes by using (7). □

We need one more lemma before estimating the size of |C|.

Lemma 8. For y in Z, we have 2A_{0} + \frac{3}{2}A_{1} + A_{2} ≥ \frac{7}{2}.

Proof . For y ∈ (H \C)∩Z, the conditions δ(y) ≥ 1 and δ_{1}(y) ≥ 0 imply the lower bounds A_{1}(y) ≥ 2 and (A_{1} + A_{2})(y) ≥ n, which show that (2A_{0} + \frac{3}{2}A_{1} + A_{2})(y) ≥ n + 1 ≥ \frac{7}{2}.

For y ∈ C ∩ Z, the condition δ(y) ≥ 1 implies that A_{1}(y) ≥ 1. We therefore have 2A_{0} + \frac{3}{2}A_{1} + A_{2} ≥ 2 + \frac{3}{2} = \frac{7}{2} and the proof of the lemma is complete. □

Let us now use these results to obtain a lower bound for |C|.

Theorem 9. Let n be a positive integer, with n ≡ 0 mod 3. Then we have

K_{3}(n, 1) ≥ \frac{(4n^{2} + 2n + 5)3^{n}}{(2n + 1)(4n^{2} + 2n − 3) + 8} .

Proof . Let us put S = ∑_{x∈H\C} φ(x). By definitions, we obtain

S = ∑_{x∈H\C} (2δ + 3\frac{δ_{1}}{2} + δ_{2}) (x)

= ∑_{y∈H} δ(y) (2|S_{0}(y) ∩ (H \ C)| + \frac{3}{2}|S_{1}(y) ∩ (H \ C)| + |S_{2}(y) ∩ (H \ C)|)

= ∑_{y∈Z} δ(y) (2n^{2} + n + 2 − (2A_{0} + \frac{3}{2}A_{1} + A_{2}) (y)) .

We then use Lemma 8 and formula (4) to get

S ≤ (2n^{2} + n + 2 − \frac{7}{2}) |δ| = (2n^{2} + n − \frac{3}{2}) ((2n + 1)|C| − 3^{n}) .

Since Lemma 7 ensures us that S ≥ 4|H \ C| = 4(3^{n} − |C|), we have

8(3^{n} − |C|) ≤ 2S ≤ (4n^{2} + 2n − 3)((2n + 1)|C| − 3^{n}) ,

and the theorem follows. □

This theorem gives the following improvements. We indicate in parenthesis the former best previous bound, according to [2].

\begin{aligned}K_{3}(9, 1) & ≥ 1060  (1048) \\ K_{3}(12, 1) & ≥ 21531  (21395) \end{aligned}

Theorem 9 can be refined by a much closer analysis of the size of φ(x), according to the possible values of A_{1}(x). We can prove the following inequality

(4n^{2} + 2n − 3)|δ| ≥ 8(3^{n} − |C|) + 2(n − 3)|(H \ C) ∩ Z| ,

which extends the last inequality in the proof of Theorem 9. However, it does not seem easy to get a non-trivial estimate for |(H \ C) ∩ Z|. Indeed, when n ≢ 0 mod 3, for instance n = 4, 5, we can have Z ⊂ C for an optimal covering code C.

Let us now study the case n ≡ 2 mod 3.

Let n be a positive integer with n ≡ 2 mod 3. In this case we introduce the nonnegative function

φ = δ + \frac{3}{2}δ_{1} + δ_{2} .

By (5) we have φ = (3n + 1)A_{0} + 2(n + 1)A_{1} + 6A_{2} + 3A_{3} − 2n^{2} − n − 1, which shows that

φ ≡ 1 + A_{0} mod 3 .  (8)

We shall need the following crucial lemma.

Lemma 10. We have

φ(x) ≥ \{ \begin{matrix}4 \\ 2 \\ 5 \end{matrix} \begin{matrix}if x ∈ H \ C, \\ if x ∈ C_{0}, \\ if x ∈ C \ C_{0}. \end{matrix}

Proof . For x in H \ C, we have φ(x) ≡ 1 mod 3, by (8). If φ(x) equals 1, either (δ(x), δ_{1}(x), δ_{2}(x)) = (1, 0, 0) or (δ(x), δ_{1}(x), δ_{2}(x)) = (0, 0, 1). The first case is impossible by Lemma 3, as is the second by Lemma 5. Therefore we have φ(x) ≥ 4.

For x in C, we have φ(x) ≡ 2 mod 3, by (8). This shows that φ(x) ≥ 2. Moreover, for x ∈ C \ C_{0}, we know that (δ + δ_{1})(x) is a positive integer. By Lemma 6, we cannot have both δ(x) > 0 and δ_{1}(x) = 0. This implies that, for x ∈ C \ C_{0}, δ_{1}(x) > 0 and thus φ(x) ≥ 3. By (8) this proves that φ(x) ≥ 5 for any x ∈ C \ C_{0}. □

Let us apply this lemma to get a lower bound for |C|.

Theorem 11. Let n be a positive integer, with n ≡ 2 mod 3. Then we have

K_{3}(n, 1) ≥ \frac{(2n^{2} + n + 5)3^{n} − 3A_{3}(n, 3)}{(2n + 1)(2n^{2} + n + 1) − 1} .

Proof . We compute |φ|:

|φ| = ∑_{x∈H\C} φ(x) + ∑_{x∈C\C_{0}} φ(x) + ∑_{x∈C_{0}} φ(x)
≥ 4(3^{n} − |C|) + 2|C_{0}| + 5(|C| − |C_{0}|) by Lemma 10,
≥ 4.3^{n} + |C| − 3A_{3}(n, 3) by (6).

Moreover we have

|φ| = (2n(n − 1) + 3n + 1)|δ| = (2n^{2} + n + 1)((2n + 1)|C| − 3^{n}) ,

by (3-4) and the definition of φ. A straightforward calculation then completes the proof of the theorem. □

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].

\begin{aligned}K_{3}(8, 1) & ≥ 397  (393) \\ K_{3}(11, 1) & ≥ 7822  (7767) \\ K_{3}(14, 1) & ≥ 166526  (165775) \end{aligned}

We give below an updated list of the best lower bounds for K_{3}(n, 1) when n ≤ 14. We consider only those values of n for which K_{3}(n, 1) is still unknown. The bound K_{3}(6, 1) ≥ 63 was stated without proof in [9] ; we proved in [3] the lower bound K_{3}(6, 1) ≥ 60.

n Lower bound for K_{3}(n, 1) Reference
6  63  [9]
7  153  [4]
8  397  Theorem 11
9  1060  Theorem 9
10  2818  [3]
11  7822  Theorem 11
12  21531  Theorem 9
14  166526  Theorem 11

5. General results for covering radii greater than one

Let R be an integer greater than one. Let us recall that δ = A_{0} + ⋯ + A_{R} − 1. Lemma 1 gives

δ_{1} = 2n(A_{0} + ⋯ + A_{R−1} − 1) + 2RA_{R} + (R + 1)A_{R+1} ,

δ_{2} = 2n(n − 1)(A_{0} + ⋯ + A_{R−2} − 1) + 2(R − 1)(2n − R)A_{R−1}

+ 2R(n − 1)A_{R} + 3\binom{R + 1}{2}A_{R+1} + \binom{R + 2}{2}A_{R+2} .

This shows that

\begin{aligned}2δ + δ_{1} & = 2(n + 1)(A_{0} + ⋯ + A_{R−1} − 1) + (R + 1)(2A_{R} + A_{R+1}) \\ & ≡ 2(n + 1)(A_{0} + ⋯ + A_{R−1} − 1) mod (R + 1) . \end{aligned}

Let us put ϵ = (R + 1)⌈2(n + 1)/(R + 1)⌉ − 2(n + 1), where ⌈t⌉ denotes the least integer greater than or equal to t. We then have ϵ ∈ {0, …, R} and

2δ + δ_{1} ≡ ϵ(1 − A_{0} − ⋯ − A_{R−1}) mod (R + 1) .  (9)

Let us put

T = {x ∈ H : A_{0}(x) = ⋯ = A_{R−1}(x) = 0} = {x ∈ H : B_{R−1}(x) ∩ C = ∅} .

We have

|T | = ∑_{x∈T}(1−A_{0}−⋯−A_{R−1}) ≥ ∑_{x∈H}(1−A_{0}−⋯−A_{R−1}) = 3^{n}−(∑_{r=0}^{R−1} 2^{r}\binom{n}{r}) |C| , (10)

by (3). Moreover, for x ∈ T, we have (2δ+δ_{1})(x) ≡ ϵ mod (R+1) and thus (2δ+δ_{1})(x) ≥ ϵ, since ϵ belongs to {0, …, R}. For x ∈ H \ T, we know that

ϵ(1 − A_{0} − ⋯ − A_{R−1})(x) ≤ 0 ≤ (2δ + δ_{1})(x) .

Therefore we have

2δ + δ_{1} ≥ ϵ(1 − A_{0} − ⋯ − A_{R−1}) ,  (11)

which gives a lower bound for |C|. When ϵ is greater than one, we shall study the properties (9) and (11) on spheres of radius one. When ϵ 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].

Lemma 12. For n ≥ (R + 1)/2, we have

|S_{1}(y) ∩ (H \ T)| ≥ \{ \begin{matrix}R & if y ∈ H, \\ R + 1 & if y ∈ Z. \end{matrix}

Proof . Let y be in H. There exists c in C ∩ B_{R}(y).

Then we have

|S_{1}(y) ∩ (H \ T)| ≥ |S_{1}(y) ∩ B_{R−1}(c)| = \{ \begin{matrix}R & if d(y, c) = R, \\ 2(R − 1) & if d(y, c) = R − 1, \\ 2n & if d(y, c) ≤ R − 2, \end{matrix}

which shows that |S_{1}(y) ∩ (H \ T)| ≥ R. If y ∈ Z, there exists another element d in C ∩ 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)∩(B_{R−1}(d)\B_{R−1}(c)). If d(y, d) ≤ R −2, we already know that |S_{1}(y)∩B_{R−1}(c)| ≥ 2n ≥ R + 1. Thus, in every case we have |S_{1}(y) ∩ (H \ T)| ≥ R + 1 for y ∈ Z. □

6. Applications with R ≥ 2

Let us start with R = 2 and n ≡ 3 mod 6. In this case, we have

δ = A_{0} + A_{1} + A_{2} − 1 ,
δ_{1} = 2n(A_{0} + A_{1} − 1) + 4A_{2} + 3A_{3} ,
δ_{2} = 2n(n − 1)(A_{0} − 1) + 4(n − 1)(A_{1} + A_{2}) + 9A_{3} + 6A_{4} ,

which gives the congruence δ_{1} + 2δ ≡ 1 − A_{0} − A_{1} mod 3. Here we have ϵ = 1.

Theorem 14. Let n be a positive integer with n ≡ 3 mod 6. Then we have

K_{3}(n, 2) ≥ \frac{(2n^{2} + 1)3^{n}}{(2n^{2} − n − 2)(2n^{2} + 1) + (n + 3)(2n + 1)} .

Proof . Let n be a positive integer with n ≡ 3 mod 6. Let us introduce the nonnegative function φ defined by

φ = \frac{1}{3}(δ + 2δ_{1} + 2(A_{0} + A_{1} − 1)) = (4\frac{n}{3} + 1) (A_{0} + A_{1} − 1) + 3A_{2} + 2A_{3} .

We get

\begin{aligned}φ_{1} & = \frac{1}{3}(4(n − 1)(A_{0} − 1) + 4(n + 1)δ + 3δ_{1} + 4δ_{2}) \\ & = 2n (4\frac{n}{3} + 1) (A_{0} − 1) + (26\frac{n}{3} − 4) A_{1} + 20\frac{n}{3}A_{2} + 15A_{3} + 8A_{4} . \end{aligned}

From these expressions we deduce

\frac{5}{2}δ + \frac{1}{2}φ + φ_{1} = (8\frac{n}{3}(n + 1) + 3) (A_{0} − 1) + (28\frac{n}{3} − 1) A_{1} + (20\frac{n}{3} + 4) A_{2} + 16A_{3} + 8A_{4} ,

which gives the congruence

\frac{5}{2}δ + \frac{1}{2}φ + φ_{1} ≡ 5(1 − A_{0} − A_{1}) mod 8 .

We therefore have \frac{5}{2}δ + \frac{1}{2}φ + φ_{1} ≥ 5(1 − A_{0} − A_{1}), which can be expressed as

δ_{2} + δ_{1} + (n + 3)δ ≥ (n + 3)(1 − A_{0}) − 4A_{1} .

Let us study what happens on T.

For x ∈ T ∩ (H \ Z), we know that δ_{2} + δ_{1} ≥ n + 3. For x ∈ T ∩ Z, we have A_{2}(x) ≥ 2. Let z_{1}, z_{2} be in S_{2}(x) ∩ C. From the property S_{1}(z_{1}) ∩ S_{1}(z_{2}) ∩ S_{2}(x) ≠ ∅, we deduce that δ_{2}(x) > 0, for any element x in T. This in turn implies that (δ_{2} + δ_{1})(x) ≥ 6, by using the congruence property δ_{2} + δ_{1} ≡ 0 mod 6. Therefore, for any x in T, we get

δ_{2} + δ_{1} + (n − 3)δ ≥ n + 3 .

Summing over T gives

\begin{aligned}(n + 3)|T | & ≤ ∑_{x∈T}(δ_{2} + δ_{1} + (n − 3)δ)(x) \\ & = ∑_{y∈Z} δ(y) (|S_{2}(y) ∩ T | + |S_{1}(y) ∩ T | + (n − 3)|S_{0}(y) ∩ T |) . \end{aligned}

Let us introduce the function F defined on H by F (x) = |S_{1}(x) ∩ (H \ T)| − 2. By Lemma 12, we know that F is nonnegative. From Lemma 1 we obtain

2|S_{2}(y) ∩ (H \ T)| + |S_{1}(y) ∩ (H \ T)| + 2n|S_{0}(y) ∩ (H \ T)| = F_{1} + 4n ≥ 4n .

By Lemma 12, we also know that |S_{1}(y) ∩ (H \ T)| ≥ 3 for any y in Z. Combining these two last inequalities gives, for any y in Z,

2 (|S_{2}(y) ∩ (H \ T)| + |S_{1}(y) ∩ (H \ T)| + (n − 3)|S_{0}(y) ∩ (H \ T)|)

≥ 4n + 3 − 6|S_{0}(y) ∩ (H \ T)| ≥ 4n − 3 ,

which implies that

(n + 3)|T | ≤ ∑_{y∈Z} δ(y)(|S_{2}(y)| + |S_{1}(y)| + (n − 3)|S_{0}(y)| − (2n − 1)) = (2n^{2} − n − 2)|δ| .

From (4) and (10), we obtain

(n + 3)(3^{n} − (2n + 1)|C|) ≤ (2n^{2} − n − 2)((2n^{2} + 1)|C| − 3^{n}) ,

and the theorem follows. □

This theorem provides the lower bound K_{3}(9, 2) ≥ 130, 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) ≥ 12193 given in [6].

Theorem 15. K_{3}(14, 2) ≥ 12204.

Proof . In this case, Lemma 1 provides the formulas

δ = A_{0} + A_{1} + A_{2} − 1 ,
δ_{1} = 28A_{0} + 28A_{1} + 4A_{2} + 3A_{3} − 28 ,
δ_{2} = 364A_{0} + 52A_{1} + 52A_{2} + 9A_{3} + 6A_{4} − 364 ,
δ_{3} = 312A_{1} + 72A_{2} + 73A_{3} + 16A_{4} + 10A_{5} − 2912 ,

which imply the properties

\begin{aligned}3δ_{3} + 2δ_{2} + \frac{δ_{1}}{3} + \frac{26}{3}δ & = 746A_{0} + 1058A_{1} + 330A_{2} + 240A_{3} + 60A_{4} + 30A_{5} − 9482 \\ & ≡ 28 − 4A_{0} − 22A_{1} mod 30 . \end{aligned}

This shows that, for any element x in T, we have

(3δ_{3} + 2δ_{2} + \frac{1}{3}δ_{1} + \frac{26}{3}δ)(x) ≥ 28 .  (12)

Let us introduce the function F defined on H by F (x) = |S_{1}(x) ∩ (H \ T)| − 2. By Lemma 12, we know that F is nonnegative. From Lemma 1 we obtain, for any y ∈ Z,

\begin{matrix}2|S_{2}(y) ∩ (H \ T)| + |S_{1}(y) ∩ (H \ T)| + 28|S_{0}(y) ∩ (H \ T)| = F_{1} + 56 ≥ 56 \\ 3|S_{3}(y) ∩ (H \ T)| + 2|S_{2}(y) ∩ (H \ T)| + 26|S_{1}(y) ∩ (H \ T)| = F_{2} + 728 ≥ 728 . \end{matrix}

We deduce from these inequalities that

3|S_{3}(y)∩(H \T)|+2|S_{2}(y)∩(H \T)|+ \frac{1}{3}|S_{1}(y)∩(H \T)|+ \frac{26}{3}|S_{0}(y)∩(H \T)| ≥ 18 , (13)

the equality holding if and only if the quadruple (|S_{3}(y)∩(H \T)|, |S_{2}(y)∩(H \T)|, |S_{1}(y)∩ (H \ T)|, |S_{0}(y) ∩ (H \ T)|) equals (0, 0, 28, 1). We now sum the inequality (12) over T and we use (13) to obtain

S = ∑_{x∈T}(3δ_{3} + 2δ_{2} + \frac{1}{3}δ_{1} + \frac{26}{3}δ)(x)

= ∑_{y∈Z} δ(y) (3|S_{3}(y) ∩ T | + 2|S_{2}(y) ∩ T | + \frac{1}{3}|S_{1}(y) ∩ T | + \frac{26}{3}|S_{0}(y) ∩ T |)

≤ ∑_{y∈Z} δ(y) (3|S_{3}(y)| + 2|S_{2}(y)| + \frac{1}{3}|S_{1}(y)| + \frac{26}{3}|S_{0}(y)| − 18)

= 9464|δ| = 28 × (338|δ|) ,

and S ≥ 28|T | ≥ 28(3^{14} − 29|C|). In this way we find

|C| ≥ \frac{(338 + 1)3^{14}}{338 × 393 + 29} = 12203.747 …,

and the theorem is proved. □

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].

Theorem 16. K_{3}(13, 3) ≥ 611.

Proof . In this case, Lemma 1 provides the formulas

δ = A_{0} + A_{1} + A_{2} + A_{3} − 1 ,
δ_{1} = 26A_{0} + 26A_{1} + 26A_{2} + 6A_{3} + 4A_{4} − 26 ,
δ_{2} = 312A_{0} + 312A_{1} + 92A_{2} + 72A_{3} + 18A_{4} + 10A_{5} − 312 ,
δ_{3} = 2288A_{0} + 528A_{1} + 440A_{2} + 200A_{3} + 136A_{4} + 40A_{5} + 20A_{6} − 2288 ,

which imply the properties

\begin{aligned}δ_{3} + δ_{1} + 14δ & = 2328A_{0} + 568A_{1} + 480A_{2} + 220A_{3} + 140A_{4} + 40A_{5} + 20A_{6} − 2328 \\ & ≡ 12(1 − A_{0} − A_{1}) mod 20 . \end{aligned}

Let us put T′ = {x ∈ H : A_{0}(x) = A_{1}(x) = 0}, so that |T′| ≥ 3^{13}−27|C|, by analogy with (10). Moreover, for any element x of T′, we have the congruence (δ_{3} + δ_{1} + 14δ)(x) ≡ 12 mod 20. This shows the weaker congruence (δ_{3} + δ_{1} + 4δ)(x) ≡ 2 mod 10. Therefore we get either (δ_{3} + δ_{1} + 4δ)(x) = 2 or (δ_{3} + δ_{1} + 4δ)(x) ≥ 12. The first case is impossible, since it implies δ(x) = 0 and contradicts the congruence (δ_{3} + δ_{1} + 14δ)(x) ≡ 12 mod 20. Thus we have proved that, for any element x of T′, the inequality (δ_{3} + δ_{1} + 4δ)(x) ≥ 12 holds. Summing this last inequality over T′ gives

(2288 + 26 + 4)|δ| ≥ 12|T′| ≥ 12(3^{13} − 27|C|) ,

which in turn provides the lower bound

|C| ≥ \frac{(2318 + 12)3^{13}}{2318 × 2627 + 12 × 27} = 610.0081 …,

and the theorem follows. □

Let us improve the bound K_{3}(14, 4) ≥ 254 given by Lo and Zhang [6].

Theorem 17. K_{3}(14, 4) ≥ 255.

Proof . In this case we have

δ = A_{0} + A_{1} + A_{2} + A_{3} + A_{4} − 1 ,
δ_{1} = 28(A_{0} + A_{1} + A_{2} + A_{3} − 1) + 8A_{4} + 5A_{5} ,
δ_{2} = 364(A_{0} + A_{1} + A_{2} − 1) + 144A_{3} + 104A_{4} + 30A_{5} + 15A_{6} ,

which gives the properties

\begin{aligned}δ_{2} + δ & = 365(A_{0} + A_{1} + A_{2} − 1) + 145A_{3} + 105A_{4} + 30A_{5} + 15A_{6} \\ & ≡ 10(1 − A_{0} − A_{1} − A_{2}) − 5A_{3} mod 15 . \end{aligned}

We now introduce the nonnegative function

\begin{aligned}φ & = \frac{δ_{2} + δ + 10(A_{0} + A_{1} + A_{2} − 1) + 5A_{3}}{15} \\ & = 25(A_{0} + A_{1} + A_{2} − 1) + 10A_{3} + 7A_{4} + 2A_{5} + A_{6} . \end{aligned}

Lemma 1 gives us

φ_{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φ_{1} + 15φ + δ_{1} + 12δ ≡ 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φ_{1} + 15φ + δ_{1} + 12δ ≥ 5(1 − A_{0} − A_{1} + 3A_{2} + 3A_{3}) .  (14)

If 3(A_{2} + A_{3}) − A_{0} − A_{1} is greater than 5, we get A_{2} + A_{3} ≥ 2 from which we deduce δ_{1} + 12δ ≥ 40(A_{2} + A_{3} − 1) ≥ 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) ≥ 0 .

Summing this last inequality over H provides the following lower bound

|C| ≥ \frac{112}{2108208}3^{14} = 254.098 …,

and the theorem follows. □

References

[1] W. Chen and I. S. Honkala, Lower bounds for q-ary covering codes, IEEE Trans. Inform. Theory 36 (1990), 664–671.

[2] G. D. Cohen, S. N. Litsyn, A.C. Lobstein and H. F. Mattson, Covering radius 1985–1994, preprint.

[3] L. Habsieger, Lower bounds for q-ary covering codes, J. Combin. Theory Ser. A 67 (1994), 199–222.

[4] L. Habsieger, A new lower bound for the football pool problem for 7 matches, preprint.

[5] L. Habsieger, Binary codes with covering radius one: some new lower bounds, Discrete Mathematics, submitted.

[6] C. Lo and Z. Zhang, New lower bounds for K_{3}(n, R) from linear inequalities, IEEE Trans. Inform. Theory, submitted.

[7] 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),Discrete Applied Mathematics 45 (1993), 71–87.

[8] G. J. M. van Wee, Some new lower bounds for binary and ternary covering codes, IEEE Trans. Inform. Theory 39 (1993), 1422–1424.

[9] G. J. M. Weber, On the football pool problem for 6 matches: a new upper bound, J. Combin. Theory Ser. A 35 (1983), 106–108.