Codes with a Poset Metric

Richard A. Brualdi, Janine Graves and K. Mark Lawrence

Department of Mathematics University of Wisconsin Madison, WI 53706

June 10, 1995

Abstract Niederreiter generalized the following classical problem of coding theory: given a finite field F_{q} and integers n > k ≥ 1, find the largest minimum distance achievable by a linear code over F_{q} of length n and dimension k. In this paper we place this problem in the more general setting of a partially ordered set and define what we call poset-codes. In this context, Niederreiter’s setting may be viewed as the disjoint union of chains. We extend some of Niederreiter’s bounds and also obtain bounds for posets which are the product of two chains.

1 Introduction

Let F_{q} be a finite field and let F_{q}^{m} be the vector space of m-tuples over F_{q}. Let n be a positive integer. One of the basic problems of coding theory [MS77, P89] is to determine the largest integer d such that there exist n vectors h_{1}, h_{2}, …, h_{n} in F_{q}^{m} every d − 1 of which are linearly independent. Let H be the m by n matrix over F_{q} whose columns are the vectors h_{1}, h_{2}, …, h_{n}. Then H is the parity check matrix of a linear code of length n and dimension n−m with minimum distance d. The problem of determining d was generalized by Niederreiter [N87, N91, N92] as follows.

Let n_{1}, n_{2}, …, n_{s} be positive integers and let

H = {h_{(i,j)} : 1 ≤ i ≤ s, 1 ≤ j ≤ n_{i}}  (1)

be a system of n_{1} + n_{2} + ⋯ + n_{s} vectors in F_{q}^{m} partitioned into s ordered sets of vectors of cardinalities n_{1}, n_{2}, …, n_{s}, respectively. Define

d(H) = min ∑_{i=1}^{s} d_{i}

where the minimum is extended over all integers d_{1}, d_{2}, …, d_{s} such that 0 ≤ d_{i} ≤ n_{i} (1 ≤ i ≤ s) and ∑_{i=1}^{s} d_{i} is positive, for which the set of vectors

{h_{(i,j)} : 1 ≤ i ≤ s, 1 ≤ j ≤ d_{i}}

is linearly dependent. If there are no such integers d_{1}, d_{2}, …, d_{s} (implying that n_{1} +n_{2} +⋯+n_{s} ≤ m), then d(H) is defined to be n_{1} +n_{2} +⋯+n_{s} +1.^{1} Equivalently, d(H) equals 1 plus the maximum integer t such that for all partitions of t into nonnegative parts t_{1}, t_{2}, …, t_{s} with t_{i} ≤ n_{i} (1 ≤ i ≤ s), the vectors {h_{(i,j)} : 1 ≤ i ≤ s, 1 ≤ j ≤ t_{i}} are linearly independent. The problem raised and studied by Niederreiter is to find, or at least study, the number

d_{q}(n_{1}, n_{2}, …, n_{s}; m) = max d(H)

where the maximum is taken over all systems H of the form (1). If n_{1} = n_{2} = ⋯ = n_{s} = 1, then we have the fundamental problem of coding theory described above.

One can view Niederreiter’s problem in the setting of a partially ordered set, henceforth abbreviated poset, in the following way. We are given a poset

P (n_{1}, n_{2}, …, n_{s}) = {(i, j) : 1 ≤ i ≤ s, 1 ≤ j ≤ n_{i}}

consisting of s disjoint chains N_{1}, N_{2}, …, N_{s} of sizes n_{1}, n_{2}, …, n_{s}, respectively. Recall that an ideal I of a poset is a subset of its elements with the property that x ∈ I and y < x imply that y ∈ I. An ideal of P (n_{1}, n_{2}, …, n_{s}) is obtained by choosing for each i, all elements of N_{i} at or below a specified element x_{i} of N_{i}. Thus the ideals of size t of P (n_{1}, n_{2}, …, n_{s}) are in oneto-one correspondence with partitions t_{1}, t_{2}, …, t_{s} of t for which 0 ≤ t_{i} ≤ n_{i} for each i = 1, 2, …, s. We are asked to assign vectors of F_{q}^{m} to the elements of the poset P (n_{1}, n_{2}, …, n_{s}) in such a way that the vectors assigned to each ideal of size t form a linearly independent set and t is maximum (the number d_{q}(n_{1}, n_{2}, …, n_{s}; m) is then one more than this maximum value). If we take n_{i} = 1 for each i, then N_{i} is a chain with only one element and P (1, 1, …, 1) is a trivial poset in which no two elements are comparable, that is, P (1, 1, …, 1) is an antichain. The above viewpoint suggests the posssibility of extending Niederreiter’s problem, and thus the fundamental problem of coding theory, to an arbitrary (finite) poset. We first introduce the idea of a poset metric.

1In this case Niederreiter defines d(H) to be m + 1.

Let P be an arbitrary poset of cardinality n whose partial order relation is denoted as usual by ≤. If A ⊆ P, then ⟨A⟩ denotes the smallest ideal of P which contains A (since the intersection of ideals is an ideal, ⟨A⟩ is the intersection of all ideals of P containing A). Consider the vector space F_{q}^{n} of n-tuples over F_{q}. Without loss of generality we assume that P = {1, 2, …, n} and thus the coordinate positions of vectors in F_{q}^{n} are in one to one correspondence with the elements of P. Let x = (x_{1}, x_{2}, …, x_{n}) be a vector in F_{q}^{n}. We define the P -weight of x to be the cardinality

w_{P} (x) = |⟨supp(x)⟩|

of the smallest ideal of P containing the support of x where supp(x) = {i : x_{i} ≠ 0}. Note that if x′ is obtained from x by changing one or more nonzero coordinates to zero, then it is possible that w_{P} (x′) = w_{P} (x). If x and y are two vectors in F_{q}^{n}, then their P -distance is

d_{P} (x, y) = w_{P} (x − y).

If P is an antichain, then P -weight and P -distance are, respectively, Hamming weight and Hamming distance of classical coding theory.

Lemma 1.1 If P is a poset of n elements, then P -distance d_{P} (·, ·) is a metric on F_{q}^{n}.

Proof. Clearly, P -distance is symmetric and positive definite. To prove that d_{P} (x, y) ≤ d_{P} (x, z) + d_{P} (z, y) for all x, y and z it suffices to show that P -weight satisfies the triangle inequality w_{P} (x + y) ≤ w_{P} (x) + w_{P} (y). Since supp(x + y) ⊂ supp(x) ∪ supp(y) and since the union of two ideals is also an ideal, we have

w_{P} (x + y) ≤ |⟨supp(x)⟩ ∪ ⟨supp(y)⟩|
≤ |⟨supp(x)⟩| + |⟨supp(y)⟩|
= w_{P} (x) + w_{P} (y).
□

We call the metric d_{P} (·, ·) on F_{q}^{n} a poset-metric. If F_{q}^{n} is endowed with a poset-metric, then we call a subset C of F_{q}^{n} a poset-code. If the poset-metric corresponds to a poset P, then C is a P -code. We follow the usual notation of coding theory. Thus if C is linear, that is, C is a subspace of F_{q}^{n} of dimension k, then C is an [n, k] poset-code. If d_{P} is the minimum P -distance between distinct codewords of C (if C is linear, this is the same as the minimum P - weight of a nonzero codeword), then C is an [n, k, d_{P}] poset-code. Let x be a vector in F_{q}^{n} and let r be a nonnegative integer. The P -sphere with center x and radius r is the set

S_{P} (x; r) = {y ∈ F_{q}^{n} : d_{P} (x, y) ≤ r}

of all vectors in F_{q}^{n} whose P -distance to x is at most equal to r. The number of vectors in F_{q}^{n} whose distance to the zero vector is exactly i equals

\{ \begin{matrix}1 & if i = 0 \\ ∑_{j=1}^{i}(q − 1)^{j}q^{i−j}Ω_{j}(i) & if i > 0 \end{matrix}  (2)

where Ω_{j}(i) equals the number of ideals of P with cardinality i having exactly j maximal elements. Since d_{P} (x, y) = d_{P} (0, y−x), it follows that the number of vectors in a sphere of radius r does not depend on its center and equals

1 + ∑_{i=1}^{r} ∑_{j=1}^{i}(q − 1)^{j}q^{i−j}Ω_{j}(i).  (3)

In particular, if q = 2 the number of vectors in a sphere of radius r equals

1 + ∑_{i=1}^{r} ∑_{j=1}^{i} 2^{i−j}Ω_{j}(i).

Example Let q = 2 and n = 8, and consider the poset P with elements {1, 2, 3, 4, 5, 6, 7, 8} in which 1 < i for each i = 2, 3, …, 8 and these are the only strict comparabilities. Let C be the [8, 4, 4] binary code contained in F_{2}^{8} obtained by adding an overall parity check to the [7, 4, 3] binary Hamming code. Then a parity check matrix for C is

H = [ \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \end{matrix} ] .

The code C has weight distribution A_{0} = 1, A_{4} = 14, A_{8} = 1 where A_{i} is the number of codewords with Hamming weight i.^{2}

We now consider C to be a P -code. Since 1 < i in P for each i = 2, 3, …, n, the only vector in F_{2}^{8} with P -weight equal to 1, is the vector (1, 0, 0, 0, 0, 0, 0, 0). Every other vector in F_{2}^{8} with Hamming weight equal to 1 has P -weight equal to 2. Of the 14 codewords of C with Hamming weight equal to 4, exactly 7 have a 1 in position 1. Hence the P -weight distribution of C is A(P)_{0} = 1, A(P)_{4} = 7, A(P)_{5} = 7, A(P)_{8} = 1. In particular, the minimum P -distance of C equals 4. The number of vectors in a sphere of radius 2 equals 1+1+2(7) = 16 = 2^{4}. We claim that the P -spheres of radius 2 about distinct codewords c′ and c are pairwise disjoint. To show this it suffices to assume that c′ = 0. Thus c ≠ 0 and c has P -weight at least 4. Suppose that there exists a vector x ∈ F_{2}^{8} such that d_{P} (0, x) ≤ 2 and d_{P} (c, x) ≤ 2. Thus w_{P} (x) ≤ 2 and without loss of generality x = (a, b, 0, 0, 0, 0, 0, 0) where a and b are 0 or 1. Then w_{P} (c) ≥ 4 implies that c has 1’s in at least two of the positions 3, 4, …, 8. But then d_{P} (c, x) ≥ 3, a contradiction. Thus the P - spheres about distinct codewords are disjoint and each contains 2^{4} vectors. Since there are 2^{4} codewords, the P -spheres of radius 2 about codewords perfectly cover F_{2}^{8}. We conclude that C is a perfect code in the P -metric!^{3}□

2We follow the usual practice in coding theory of not listing the A_{i} which equal 0.

We now generalize Niederreiter’s problem. Let P be a poset with elements {1, 2, …, n}. Let

H = {h_{i} : 1 ≤ i ≤ n}  (4)

be a system of vectors in F_{q}^{m} indexed by the elements of P. Define d_{P} (H) to be the minimum positive integer d such that there exists an ideal I of P of size d such that the vectors {h_{i} : i ∈ I} are linearly dependent. If there is no such ideal (implying that n ≤ m), then d_{P} (H) is defined to be n + 1. Since every set of m + 1 vectors in F_{q}^{m} is linearly dependent, we have d_{P} (H) ≤ m + 1. Viewing H as a parity check matrix of an [n, n − m] linear code C, we see that d_{P} (H) is the minimum P -weight of a nonzero codeword of C (equivalently, the minimum P -distance between distinct codewords). Let

d_{q}(P; m) = max d_{P} (H)

where the maximum is taken over all systems (4). Thus d_{q}(P; m) is the largest minimum P -distance attainable by an [n, n − m] P -code over F_{q}. Clearly, d_{q}(P; m) ≤ m + 1; furthermore, by choosing a system H of nonzero vectors we see that d_{q}(P; m) ≥ d_{P} (H) ≥ 2. Hence

2 ≤ d_{q}(P; m) ≤ m + 1.

Problem Determine d_{q}(P; m) for different posets P.

3This is in contrast to the classical situation in which the [7, 4, 3] Hamming code is perfect but the extended code C is not.

In the next section we discuss perfect codes in certain P -metrics, and in particular we show that the extended binary Hamming codes and the extended binary Golay code are perfect codes in the P -metric where P is a poset generalizing the poset in the preceding example. In the last section we first review the bounds on d_{q}(n_{1}, n_{2}, …, n_{s}; m) = d_{q}(P (n_{1}, n_{2}, …, n_{s}); m) obtained by Niederreiter and then extend some of these bounds. We also discuss bounds on d_{2}(P; m) for another natural poset P.

2 Perfect P -codes

Let P be a poset with elements {1, 2, …, n}, and let C be a code in F_{q}^{n} whose coordinate positions are indexed by the elements of P. Then C is a perfect P -code provided there exists an integer r such that the P -spheres of radius r with centers at the codewords of C are pairwise disjoint and their union is F_{q}^{n}.

We first characterize perfect P -codes in the case that P is a chain.

Theorem 2.1 Let P be the poset with elements {1, 2, …, n} where 1 < 2 < ⋯ < n, and let C be a code in F_{q}^{n}. Then C is a perfect P -code if and only if there exists an integer k with 0 ≤ k ≤ n such that |C| = q^{k} and the set of all vectors (x_{n−k+1}, …, x_{n}) such that (x_{1}, …, x_{n−k}, x_{n−k+1}, …, x_{n}) ∈ C for some (x_{1}, …, x_{n−k}) ∈ F_{q}^{n−k} equals F_{q}^{k}. In particular, the linear code C_{k} of dimension k consisting of all vectors (0, …, 0, a_{n−k+1}, …, a_{n}) in F_{q}^{n} whose first n − k coordinates equal 0 is a perfect P -code with minimum P -distance equal to n − k + 1.

Proof. We first show that the codes specified in the theorem are perfect. It follows from their defining properties that these codes have cardinality q^{k} and minimum P -distance n − k + 1 and that there is a unique codeword with any prescribed last k coordinates. Thus each vector (y_{1}, …, y_{n}) in F_{q}^{n} is contained in the P -sphere of radius n−k about some codeword of the form (x_{1}, …, x_{n−k}, y_{n−k+1}, …, y_{n}), but is not contained in the P -sphere of radius n − k + 1 about any other codeword. Hence C_{k} is a perfect P -code.

Conversely, assume that C is a perfect P -code. Let r be an integer such that the P -spheres of radius r about the codewords of C are pairwise disjoint and their union is F_{q}^{n}. The P -spheres of radius r have cardinality q^{r}, and hence |C| = q^{n−r}. Let y = (y_{1}, y_{2}, …, y_{n}) be a vector in F_{q}^{n}. Then there exists a codeword c such that y is in S_{P} (c; r) and hence a codeword c of the form c = (c_{1}, …, c_{r}, y_{r+1}, …, y_{n}). Hence C has the form given in the theorem with r = n − k. □

In contrast to the previous theorem, we now show that there are no perfect P -codes if P is a union of two disjoint chains of equal size.

Theorem 2.2 Let n = 2ℓ be an even positive integer. Let P be the poset consisting of two disjoint chains N and N′ of the same size ℓ. Then the only perfect P -codes C in F_{q}^{n} are C = F_{q}^{n} and C = {x} for each vector x in F_{q}^{n}.

Proof. Clearly the codes C = F_{q}^{2ℓ} and C = {x} are perfect P -codes. We now show that there are no other perfect P -codes. Let the elements of N be {1, 2, …, ℓ} where 1 < 2 < ⋯ < ℓ, and let the elements of N′ be {1′, 2′, …, ℓ′} where 1′ < 2′ < ⋯ < ℓ′. Suppose to the contrary that C is a perfect P -code where 1 < |C| < q^{2ℓ}. Let r be the integer such that the P -spheres of radius r with centers at the codewords of C are pairwise disjoint and cover F_{q}^{2ℓ}. Then 1 ≤ r ≤ 2ℓ − 1.

First assume that r ≥ ℓ. Let x = (x_{1}, …, x_{ℓ}, x_{1′}, …, x_{ℓ′}) and y = (y_{1}, …, y_{ℓ}, y_{1′}, …, y_{ℓ′}) be any two vectors in F_{q}^{2ℓ}. Then the vector (x_{1}, …, x_{ℓ}, y_{1′}, …, y_{ℓ′}) is contained in S_{P} (x; r) ∩ S_{P} (y; r). In particular, the P -spheres of radius r about any two codewords overlap. Since |C| ≥ 2, this contradicts the assumption that C is perfect.

Now assume that 1 ≤ r < ℓ. We first compute the cardinalities of P - spheres of radius r. Let i be an integer with 1 ≤ i ≤ ℓ. It follows from (2) that the number of vectors whose distance to a given vector x in F_{q}^{n} equals i is

α_{i} = 2(q − 1)q^{i−1} + (i − 1)(q − 1)^{2}q^{i−2} = (q − 1)q^{i−2}[(i + 1)q − i + 1].

Hence for each vector x we have

|S_{P} (x; r)| = 1 + ∑_{i=1}^{r} α_{i}.

It follows by induction that

|S_{P} (x; r)| = q^{r−1}[r(q − 1) + q].  (5)

Since C is perfect, q^{2ℓ} = |C||S_{P} (x; r)|. Hence there exists a positive integer j such that r(q − 1) + q = q^{j}. Thus |S_{P} (x; r)| = q^{r+j−1}. Moreover,

r = \frac{q^{j} − q}{q − 1} ,

and since r ≥ 1, we have j ≥ 2. Thus r = q(1+q +⋯+q^{j−2}) ≥ 2(j −1) ≥ j. We have

|C| = q^{2ℓ−r−j+1} = q^{2(ℓ−r)+r−(j−1)},

and since r > j − 1, it follows that |C| > q^{2(ℓ−r)}. By the pigeon-hole principle, there exist distinct codewords x = (x_{1}, …, x_{ℓ}, x_{1′}, …, x_{ℓ′}) and y = (y_{1}, …, y_{ℓ}, y_{1′}, …, y_{ℓ′}) such that x_{i} = y_{i} and x_{i′} = y_{i′} for i = r + 1, …, ℓ. Since the vector (x_{1}, …, x_{ℓ}, y_{1′}, …, y_{ℓ′}) is contained in S_{P} (x; r) ∩ S_{P} (y; r), the P -spheres of radius r about the codewords x and y overlap, again contradicting the assumption that C is perfect. □

We now generalize the example in section 1 and show that there are simple posets P such that the extended binary Hamming codes and the extended Golay codes are perfect P -codes.

Theorem 2.3 For each positive integer n let P_{n} denote the poset with elements {1, 2, …, n} in which 1 < i for each i = 2, 3, …, n and these are the only strict comparabilities. Then for each positive integer m the extended binary Hamming H(m) code with parameters [n = 2^{m}, 2^{m}−m−1, 4] is a perfect P_{n}-code. In addition, the extended binary Golay code G_{24} with parameters [24, 12, 8] is a perfect P_{24}-code, and the extended ternary Golay code G_{12} with parameters [12, 6, 6] is a perfect P_{12}-code.

Proof. The proof that H(m) is a perfect P_{n}-code follows as in the example in section 1. Indeed the spheres of radius 2 about the 2^{2^{m}−m−1} codewords each contain 2^{m+1} vectors and are pairwise disjoint, and hence they perfectly cover F_{2}^{2^{m}}. The argument is similar for the extended Golay codes. We give the argument only for the ternary Golay code. The number of codewords of G_{12} equals 3^{6}. Each P_{12}-sphere of radius 3 contains

1 + 2 + 2(3)(11) + 2^{2}3\binom{11}{2} = 729 = 3^{6}

vectors. Let x be a vector whose P_{12}-distance to 0 is at most 3. Then at most 2 of coordinates 2, 3, …, 12 of x are nonzero. Let c be a nonzero codeword. Since each nonzero codeword of G_{12} has Hamming weight at least 6, w_{P_{12}}(x) ≥ 6. Hence at least 5 of coordinates 2, 3, ⋯, 12 of c are nonzero. This implies that d_{P_{12}}(c, x) ≥ 4. We conclude that the P_{12}-spheres of radius 3 about codewords are pairwise disjoint, and hence G_{12} is a perfect P_{12}-code. □

3 Bounds for d_{q}(P; m)

Throughout this section we use the following notation. Let m be a positive integer and consider the vector space F_{q}^{m} over the finite field F_{q}. Let n_{1}, n_{2}, …, n_{s} be positive integers such that n_{1} ≥ n_{2} ≥ ⋯ ≥ n_{s}. If n_{1} + n_{2} + ⋯ + n_{s} ≤ m, then clearly d_{q}(n_{1}, n_{2}, …, n_{s}; m) = n_{1} + n_{2} + ⋯ + n_{s} + 1. As a result we henceforth assume that

n_{1} + n_{2} + ⋯ + n_{s} > m.  (6)

The following basic results are proved by Niederreiter [N87]:

(N1) 2 ≤ d_{q}(n_{1}, n_{2}, …, n_{s}; m) ≤ m + 1;

(N2) d_{q}(n′_{1}, n′_{2}, …, n′_{s}; m) ≤ d_{q}(n_{1}, n_{2}, …, n_{s}; m) if n_{i} ≤ n′_{i} for i = 1, 2, …, s;

(N3) Let n′_{i} = min{n_{i}, m} for i = 1, 2, …, s. Then d_{q}(n_{1}, n_{2}, …, n_{s}; m) = d_{q}(n′_{1}, n′_{2}, …, n′_{s}; m);

(N4) If s ≤ q + 1, then d_{q}(n_{1}, n_{2}, …, n_{s}; m) = m + 1;

(N5) Assume that m ≥ 2. Let ω_{m} be the smallest integer such that n_{1} + ⋯ + n_{ω_{m}} ≥ m. If s ≥ q + max{ω_{m}, 2}, then

d_{q}(n_{1}, n_{2}, …, n_{s}; m) ≤ m.

In addition, using constructions based on linear recurrence relations, Niederreiter [N91] obtained lower bounds for d_{q}(n_{1}, n_{2}, …, n_{s}; m) and also obtained the following results:

(N6) If m ≥ 2 and s ≤ (q^{m} − 1)/(q − 1), then d_{q}(n_{1}, n_{2}, …, n_{s}; m) ≥ 3, and if s > (q^{m} − 1)/(q − 1), then d_{q}(n_{1}, n_{2}, …, n_{s}; m) = 2;

(N7) Assume that q + 2 ≤ s ≤ (q^{m} − 1)/(q − 1). If n_{1} ≥ m + 2 − ⌊log_{q}((q − 1)(s − 1) + 1)⌋, then

d_{q}(n_{1}, n_{2}, …, n_{s}; m) ≤ m + 2 − ⌊log_{q}((q − 1)(s − 1) + 1)⌋.

If n_{1} ≤ m + 1 − ⌊log_{q}((q − 1)(s − 1) + 1)⌋, then

d_{q}(n_{1}, n_{2}, …, n_{s}; m) ≤ m + 2 − ⌊log_{q}((q − 1)(s − ω_{m} + 1) + 1)⌋.

In this section we extend some of the bounds given above. In what follows, for each integer j with 1 ≤ j ≤ n_{1} + ⋯ + n_{s}, ω_{j} denotes the smallest integer t such that n_{1} + ⋯ + n_{t} ≥ j.

Let H = {h_{(i,j)} : 1 ≤ i ≤ s, 1 ≤ j ≤ n_{i}} be a system of vectors in F_{q}^{m}. The vector h_{(i,j)} is assigned to the jth element of the ith chain of the poset P (n_{1}, n_{2}, …, n_{s}). If I is an ideal of P (n_{1}, n_{2}, …, n_{s}), then H_{I} denotes the set of vectors from H assigned to the elements of I.

Lemma 3.1 Let H = {h_{(i,j)} : 1 ≤ i ≤ s, 1 ≤ j ≤ n_{i}} be a system of n vectors in F_{q}^{m}. Let r be an integer with 1 ≤ r ≤ m − 2. Assume that ω_{m−r} ≥ 2 and that

s ≥ ω_{m−r} + q^{r+1} − q^{2} + q.  (7)

Also assume that H_{I} is linearly independent for every ideal I of size m − r of P = P (n_{1}, n_{2}, …, n_{s}). Then there exists an ideal J of P of size m having exactly ω_{m−r} + r maximal elements such that H_{J} is linearly independent.

Proof. Let u = (m − r) − ∑_{i=1}^{ω_{m−r}−1} n_{i}. The set

I = {(i, j) : 1 ≤ i < ω_{m−r}, 1 ≤ j ≤ n_{i}} ∪ {(ω_{m−r}, j) : 1 ≤ j ≤ u}

is an ideal of P of size m − r, and hence H_{I} is linearly independent. Let b_{i} = h_{(i,n_{i})} for 1 ≤ i < ω_{m−r} and b_{ω_{m−r}} = h_{(ω_{m−r},u)} be the vectors from H assigned to the maximal elements of I. Let c_{i} = h_{(i+ω_{m−r},1)} (1 ≤ i ≤ s−ω_{m−r}) be the vectors assigned to the minimal elements of the last s − ω_{m−r} chains of P. We extend H_{I} to a basis H_{I} ∪ {v_{1}, …, v_{r}} of F_{q}^{m}. Let ĉ_{i} denote the projection of c_{i} onto the subspace V of F_{q}^{m} spanned by {v_{1}, …, v_{r}}.

We first show that the number t of c_{i} whose projection ĉ_{i} is the zero vector is at most q − 1. Assume to the contrary that t > q − 1. Let i be an integer with 1 ≤ i ≤ s − ω_{m−r} and suppose that ĉ_{i} = 0. The set (H_{I} \ {b_{j}}) ∪ {c_{i}} is the set of vectors assigned to an ideal of size m − r and hence is linearly independent for j = 1, …, ω_{m−r}. Since ĉ_{i} = 0, it follows that the projection β_{ij} of c_{i} onto b_{j} is not zero for each j. Since ω_{m−r} ≥ 2, we may take j equal to 1 and 2 in turn. Thus α_{i} = β_{i1}/β_{i2} is defined and nonzero. Since there are only q − 1 possible values for the α_{i}, it follows that there exist k and l such that ĉ_{k} = ĉ_{l} = 0 and α_{k} = α_{l}. It follows that β_{l2}c_{k} − β_{k2}c_{l} is a linear combination of the vectors in H_{I} \ {b_{1}, b_{2}}. Then (H_{I} \ {b_{1}, b_{2}}) ∪ {c_{k}, c_{l}} is a linearly dependent set of vectors assigned to an ideal of size m − r, a contradiction. Hence t ≤ q − 1.

We now claim that the set S = {ĉ_{i} : 1 ≤ i ≤ s − ω_{m−r}} spans V. Assume the claim is false. Since the dimension of V is r, it follows that S is contained in some r −1 dimensional subspace of V and hence that |S| ≤ q^{r−1}. Consider the c_{i} such that ĉ_{i} ≠ 0. By (7), s−ω_{m−r} > q^{r+1}−q^{2}+q−1 and since t ≤ q−1, it now follows that the number s−ω_{m−r}−t of these c_{i} is greater than q^{r+1}−q^{2}. Let U be the subspace of F_{q}^{m} spanned by V ∪ {b_{1}, b_{2}}. Since there are q^{2} vectors in the subspace spanned by {b_{1}, b_{2}} and at most q^{r−1} − 1 projections of these c_{i} into V, it follows that there are at most q^{2}(q^{r−1} − 1) = q^{r+1} − q^{2} possible projections of these c_{i} into U. We conclude that not all of these c_{i} have distinct projections into U. Hence there exist c_{k} and c_{l} with k ≠ l whose projections into U are equal. It follows that c_{k} − c_{l} is a linear combination of the vectors in H_{I} \ {b_{1}, b_{2}}. Then (H_{I} \ {b_{1}, b_{2}}) ∪ {c_{k}, c_{l}} is a linearly dependent set of vectors assigned to an ideal of size m − r, a contradiction. Hence S spans V.

Let S′ be a basis of V consisting of vectors in S. Then H_{J} = H_{I} ∪ {c_{i} : ĉ_{i} ∈ S′} is a set of linearly independent vectors corresponding to an ideal J of size m having exactly ω_{m−r} + r maximal elements. □

We now extend Niederreiter’s result (N5) above. We first consider the case q = 2.

Theorem 3.2 Let r and m be integers with 0 ≤ r ≤ m − 2. Assume that

ω_{m−r} ≥ 2r + 2.  (8)

Also assume that

s ≥ \{ \begin{matrix}ω_{m} + 2 & if r = 0, \\ ω_{m−1} + 3 & if r = 1, \\ ω_{m−r} + 2^{r+1} − 2 & if r ≥ 2. \end{matrix}  (9)

Then

d_{2}(n_{1}, n_{2}, …, n_{s}; m) ≤ m − r.  (10)

Proof. If r = 0 the result is a consequence of (N5). Now assume that r ≥ 1. Suppose to the contrary that d_{2}(n_{1}, n_{2}, …, n_{s}; m) > m − r. Then there exists a system H = {h_{(i,j)} : 1 ≤ i ≤ s, 1 ≤ j ≤ n_{i}} of vectors in F_{2}^{m} such that H_{I} is linearly independent for every ideal I of size m − r of the poset P = P (n_{1}, n_{2}, …, n_{s}). It follows from (9) that (7) holds for q = 2 and that

s − ω_{m−r} − r ≥ 2  (11)

holds for all r ≥ 1. By Lemma 3.1, there exists an ideal J of P of size m having exactly ω_{m−r} + r maximal elements such that H_{J} is linearly independent and thus is a basis of F_{2}^{m}. For ease of notation we denote these basis vectors by b_{1}, b_{2}, …, b_{m}. Let

T = {i : 1 ≤ i ≤ s and (i, 1) ∈ J}

be the set of indices of the chains which have a nonempty intersection with J and let \overline{T} be the set of indices of the remaining chains. Then |T | = ω_{m−r} + r and by (11), |\overline{T} | = s − |T | ≥ 2. Let Jmax be the set of the ω_{m−r} + r maximal elements of J. Let a_{i} = (i, 1) be the minimal element of the ith chain of P (1 ≤ i ≤ s), and write

a_{i} = ∑_{l=1}^{m} β_{il}b_{l} (i ∈ \overline{T}).

Let M be any subset of Jmax with |M| = r + 1. Let i ∈ \overline{T} and consider the ideal I = (J \ M) ∪ {a_{i}} of size m − r. Thus H_{I} is linearly independent, and it follows that β_{il} ≠ 0 for at least one l such that b_{l} ∈ H_{M}. Since M was an arbitrary subset of Jmax of cardinality r + 1, it follows that β_{il} = 0 for at most r values of l with b_{l} ∈ H_{Jmax}. Since |\overline{T} | ≥ 2 there exist distinct elements j and k in \overline{T}, and for any such j and k, there exist at least |Jmax| − 2r = ω_{m−r} − r ≥ r + 2 values of l with b_{l} ∈ H_{Jmax} such that both β_{jl} ≠ 0 and β_{kl} ≠ 0. Here the last inequality is a consequence of hypothesis (8). Since we are working over the binary field, it follows that β_{jl} = β_{kl} = 1 for at least r + 2 indices l with b_{l} ∈ H_{Jmax}. Without loss of generality, β_{jl} = β_{kl} for l = 1, 2, …, r + 2. We then have

a_{j} − a_{k} = ∑_{l=r+3}^{m}(β_{jl} − β_{kl})b_{l}.

It follows that {b_{r+3}, …, b_{m}, a_{j}, a_{k}} is a linearly dependent set of vectors corresponding to an ideal of P of size m − r, a contradiction. Hence (10) holds. □

We now obtain the conclusion of Theorem 3.2 for arbitrary q. Note that the assumptions of Theorem 3.3 when q = 2 are not identical to the assumptions of Theorem 3.2.

Theorem 3.3 Let r and m be integers with 0 ≤ r ≤ m − 2. Assume that

ω_{m−r} ≥ r + 2.  (12)

Also assume that (7) holds and that

s ≥ ω_{m−r} + r + \binom{2r + 2}{r + 2}(q − 1)^{r+1} + 1.  (13)

Then

d_{q}(n_{1}, n_{2}, …, n_{s}; m) ≤ m − r.  (14)

Proof. The first part of the proof follows closely the first part of the proof of the previous theorem. If r = 0 the result is a consequence of (N5). Now assume that r ≥ 1. Suppose to the contrary that d_{q}(n_{1}, n_{2}, …, n_{s}; m) > m − r. Then there exists a system H = {h_{(i,j)} : 1 ≤ i ≤ s, 1 ≤ j ≤ n_{i}} of vectors in F_{q}^{m} such that H_{I} is linearly independent for every ideal I of size m − r of the poset P = P (n_{1}, n_{2}, …, n_{s}). It follows from (13) that

s − ω_{m−r} − r > \binom{2r + 2}{r + 2}(q − 1)^{r+1}  (15)

holds for all r ≥ 1. By Lemma 3.1, there exists an ideal J of P of size m having exactly ω_{m−r} + r maximal elements such that H_{J} is linearly independent and thus is a basis of F_{q}^{m}. For ease of notation we denote these basis vectors by b_{1}, b_{2}, …, b_{m}. Let

T = {i : 1 ≤ i ≤ s and (i, 1) ∈ J}

be the set of indices of the chains which have a nonempty intersection with J and let \overline{T} be the set of indices of the remaining chains. Then |T | = ω_{m−r} + r and by (15), |\overline{T} | = s − |T | > \binom{2r+2}{r+2}(q − 1)^{r+1}. Let Jmax be the set of the ω_{m−r} + r maximal elements of J. By (12), |Jmax| ≥ 2r + 2, and we fix a subset K of Jmax of cardinality 2r + 2. Let a_{i} = (i, 1) be the minimal element of the ith chain of P (1 ≤ i ≤ s), and write

a_{i} = ∑_{l=1}^{m} β_{il}b_{l} (i ∈ \overline{T}).

Let M be any subset of Jmax with |M| = r + 1. Let i ∈ \overline{T} and consider the ideal I = (J \ M) ∪ {a_{i}} of size m − r. Thus H_{I} is linearly independent, and it follows that β_{il} ≠ 0 for at least one l such that b_{l} ∈ H_{M}. Since M was an arbitrary subset of Jmax of cardinality r + 1, it follows that β_{il} = 0 for at most r values of l with b_{l} ∈ H_{Jmax} and hence for at most r values of l with b_{l} ∈ H_{K}. Thus β_{il} ≠ 0 for at least r + 2 values of l with b_{l} ∈ H_{K}. For each i ∈ \overline{T} we choose a set C_{i} of any r + 2 such l’s. It follows from (13) that |\overline{T} | = s − ω_{m−r} − r > \binom{2r+2}{r+2}(q − 1)^{r+1}. Hence there exists a subset Z of \overline{T} of cardinality strictly greater than (q−1)^{r+1} such that C_{i} = C_{j} = C for all i and j in Z. Without loss of generality we may assume that C = {1, 2, …, r + 2}. Thus β_{ij} ≠ 0 for 1 ≤ j ≤ r + 2 and i ∈ Z. Hence

α_{ij} = \frac{β_{ij}}{β_{i,r+2}} (1 ≤ j ≤ r + 1)

is defined and nonzero for each i in Z. Since |Z| > (q − 1)^{r+1}, it follows that there exist distinct i and k in Z such that

(α_{i1}, α_{i2}, …, α_{i,r+1}) = (α_{k1}, α_{k2}, …, α_{k,r+1}).

We then have

β_{k,r+2}a_{i} − β_{i,r+2}a_{k} = ∑_{l=r+3}^{m}(β_{k,r+2}β_{il} − β_{i,r+2}β_{kl})b_{l}.

It follows that {b_{r+3}, …, b_{m}, a_{i}, a_{k}} is a linearly dependent set of vectors corresponding to an ideal of P of size m − r, a contradiction. Hence (14) holds. □

We now consider d_{2}(Q_{k}, m) for the poset Q_{k} defined as follows. Let k be a positive integer. Then Q_{k} is the poset whose set of elements is

{(i, j) : i ≥ 0, j ≥ 0, i + j ≤ k − 1},

having the componentwise partial order given by

(i, j) ≤ (i′, j′) if and only if i ≤ i′ and j ≤ j′.

The set of elements of Q_{k} is partitioned into k level sets L_{0}, L_{1}, …, L_{k−1} where

L_{t} = {(i, j) : i ≥ 0, j ≥ 0, i + j = t} (0 ≤ t ≤ k − 1).

The number of elements of Q_{k} is

n = \frac{k(k + 1)}{2}.

Note that the smallest size of an ideal which contains the element (i, j) is (i + 1)(j + 1). The poset Q_{k} is a subposet (the ‘bottom half’) of the product of a chain of size k with itself.

If n ≤ m, then d_{2}(Q_{k}; m) = n + 1. We henceforth assume that n > m.

Theorem 3.4 If m ≤ 7, then d_{2}(Q_{k}; m) = m+1. If m ≥ 8 and k(k+1)/2 ≥ m + 2, then d_{2}(Q_{k}; m) ≤ m.

Proof. It is not hard to show that d_{2}(Q_{k}; m) = m + 1 if m ≤ 7. For instance, suppose that m = 7. If k ≥ 7, then the union of the ideals of Q_{k} of size 7 contains exactly 16 elements. Let e_{1}, e_{2}, …, e_{7} be a basis of F_{2}^{7}. Then the following assigment of vectors of F_{2}^{7} to these 16 elements of Q_{k} has the property that the vectors assigned to each ideal of size 7 are linearly independent and hence d_{2}(Q_{k}; 7) = 8:

\begin{matrix}(0, 0) ← e_{1} & (2, 1) ← e_{4} + e_{7} \\ (0, 1) ← e_{2} & (3, 0) ← e_{7} \\ (1, 0) ← e_{3} & (0, 4) ← e_{7} \\ (0, 2) ← e_{4} & (4, 0) ← e_{6} \\ (1, 1) ← e_{4} + e_{5} + e_{6} + e_{7} & (0, 5) ← e_{5} \\ (2, 0) ← e_{5} & (5, 0) ← e_{4} \\ (0, 3) ← e_{6} & (0, 6) ← e_{3} \\ (1, 2) ← e_{5} + e_{6} & (6, 0) ← e_{2} \end{matrix} .

Now assume that m ≥ 8 and k(k + 1)/2 ≥ m + 2. We show that it is impossible to find a system

H = {h_{(i,j)} : i ≥ 0, j ≥ 0, i + j ≤ k − 1}

of vectors of F_{2}^{m} with the property that the set H_{I} of vectors assigned to each ideal I of size m is linearly independent.

Assume to the contrary that we have such a system H. There exists an integer j ≤ k − 1 and an ideal J of size m containing L_{0} ∪ ⋯ ∪ L_{j−1} and contained in L_{0} ∪ ⋯ ∪ L_{j−1} ∪ L_{j}. We may choose such a J so that for some integer t, {(0, j), (1, j − 1), …, (t, j − t)} = L_{j} ∩ J. We now distinguish two elements c and d of J. Let d = (t, j − t), and let c = (t − 1, j − t + 1) if t > 0 and let c = (j − 1, 0) if t = 0. We also distinguish two elements a and b of Q_{k} not in J. If t ≤ j − 2, let a = (t + 1, j − t − 1) and b = (t + 2, j − t − 2); if t = j − 1, let a = (j, 0) and b = (0, j + 1); if t = j, let a = (0, j + 1) and b = (1, j). Since m ≥ 8, it follows that J ∪ {a, b} is an ideal of Q_{k} of size m + 2 in which each of a, b, c and d is a maximal element.

Since J is an ideal of size m, H_{J} is linearly independent and hence is a basis of F_{2}^{m}. Thus each vector in F_{2}^{m} is a sum of a subset of the vectors in H_{J}. Let u be the vector of H_{J} assigned to c and let v be the vector of H_{J} assigned to d. Let x be the vector of F_{2}^{m} assigned to a and let y be the vector assigned to b. Since (J \ {c}) ∪ {a} and (J \ {d}) ∪ {a} are both ideals of size m, both u and v occur in writing x as a sum of vectors of H_{J}. Similarly, both u and v occur in writing y as a sum of vectors of H_{J}. Therefore x − y is a linear combination of the vectors of H_{J} \ {u, v}, and hence (H_{J} \ {u, v}) ∪ {x, y} is a linearly dependent set of vectors assigned to the ideal (J \ {c, d}) ∪ {a, b} of size m, a contradiction. □

Theorem 3.5 If m ≥ 26 and k(k + 1)/2 ≥ m + 2, then d_{2}(Q_{k}; m) ≤ m − 1.

Proof. Assume that m ≥ 26 and k(k + 1)/2 ≥ m + 2. We show that it is impossible to find a system

H = {h_{(i,j)} : i ≥ 0, j ≥ 0, i + j ≤ k − 1}

of vectors of F_{2}^{m} with the property that the set H_{I} of vectors assigned to each ideal I of size m − 1 is linearly independent. Assume to the contrary that we have such a system.

[figure: (0,0); (1,0); (2,0); (3,0); (4,0); (5,0); (6,0); (0,1); (0,2); (0,3); (0,4); (0,5); (0,6); 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21; 22; 23; 24; 25; c_{1}; c_{2}; c_{3}; c_{4}; a_{1}; a_{2}; a_{3}]

Figure 1.

Using a construction similar to that in the proof of Theorem 3.4 and the assumption that m ≥ 26, we can find an ideal I of size m − 1 containing four elements c_{1}, c_{2}, c_{3}, c_{4} and an additional three elements a_{1}, a_{2}, a_{3} not in I such that I′ = I ∪ {a_{1}, a_{2}, a_{3}} is an ideal of Q_{k} of size m + 2 in which each of c_{1}, c_{2}, c_{3}, c_{4}, a_{1}, a_{2}, and a_{3} is a maximal element (see Figure 1 for the case m = 26). We first focus on two of the c’s, say c_{3} and c_{4}, and two of the a’s, say a_{2} and a_{3} in order to produce an ideal J of size m contained in I′ such that H_{J} is linearly independent and thus is a basis of F_{2}^{m}. Since I is an ideal of size m − 1, H_{I} is linearly independent. Let v_{m} be a vector such that H_{I} ∪ {v_{m}} is a basis of F_{2}^{m}. Let u, v, y and z be the vectors from H assigned to c_{3}, c_{4}, a_{2} and a_{3}, respectively. Each of the vectors y and z is a sum of a subset of the basis vectors. Since (I \ {c_{3}}) ∪ {a_{2}} is an ideal of size m − 1, H_{(I\{c_{3}})∪{a_{2}}} is linearly independent and hence either u or v_{m} occurs in writing y as a sum of the basis vectors. Since (I \ {c_{4}}) ∪ {a_{2}} is also an ideal of size m − 1, either v or v_{m} also occurs in y. Hence if v_{m} does not appear in y, then both u and v do. Similarly, if v_{m} does not appear in z, then both u and v do. If v_{m} appears in neither y nor z, then y − z is a linear combination of the vectors of H_{I\{c_{3},c_{4}}} assigned to the ideal I \ {c_{3}, c_{4}} and hence H_{(I\{c_{3},c_{4}})∪{a_{2},a_{3}}} is a linearly dependent set of vectors assigned to the ideal (I \ {c_{3}, c_{4}}) ∪ {a_{2}, a_{3}} of size m − 1. Therefore v_{m} appears in at least one of y and z, say z. Then J = I ∪ {a_{3}} is an ideal contained in I′ such that H_{J} is a basis of F_{2}^{m}.

Each of the elements of M = {c_{1}, c_{2}, c_{3}, c_{4}, a_{3}} is a maximal element of the ideal J and for ease of notation, we relabel the vectors assigned to these elements as u_{1}, u_{2}, u_{3}, u_{4}, u_{5}, respectively. Let x denote the vector assigned to a_{1} and as above, let y denote the vector assigned to a_{2}. Consider the ideals of size m−1 obtained from J by removing any two elements of M and adjoining a_{1}. Since the sets of vectors assigned to these ideals are linearly independent, we conclude that given any two of the vectors u_{1}, …, u_{5}, at least one appears in writing x as a sum of the basis vectors. It follows that at least four of these vectors appear in x. Similarly, at least four occur in y. Hence at least three appear in both, say u_{1}, u_{2}, u_{3}. Then x − y is a linear combination of the m − 3 vectors in H_{J\{c_{1},c_{2},c_{3}}} and so (J \ {c_{1}, c_{2}, c_{3}}) ∪ {a_{1}, a_{2}} is an ideal of size m − 1 whose assigned vectors are linearly dependent, a contradiction. □

We now obtain a more general bound for d_{2}(Q_{k}; m).

Theorem 3.6 Let r be an integer with r ≥ 2 and let f(r) = 2^{2r+1} + r2^{r+2} − 2^{r} + 2r^{2} + 2r + 2. If m ≥ f(r) and k ≥ 2^{r+1} + 2r, then d_{2}(Q_{k}; m) ≤ m − r.

Proof. Assume that m ≥ f(r) and k ≥ 2^{r+1} + 2r. We show that it is impossible to find a system

H = {h_{(i,j)} : i ≥ 0, j ≥ 0, i + j ≤ k − 1}

of vectors of F_{2}^{m} with the property that the set H_{I} of vectors assigned to each ideal I of size m − r is linearly independent. Assume to the contrary that we have such a system.

Since k ≥ 2^{r+1} + 2r, the level set L_{2^{r+1}+2r−1} contains exactly 2^{r+1} + 2r elements. We now use a construction similar to that in the proof of Theorem 3.4. Since

m − r ≥ f(r) − r = ( ∑_{i=1}^{2^{r+1}+2r−1} i) + 2r + 2 = ( ∑_{i=0}^{2^{r+1}+2r−2} |L_{i}|) + 2r + 2,

we can find an ideal I of size m−r containing 2r +2 elements c_{1}, c_{2}, …, c_{2r+2} and an additional 2^{r+1} − 2 elements a_{1}, a_{2}, …, a_{2^{r+1}−2} not in I such that I′ = I ∪{a_{1}, a_{2}, …, a_{2^{r+1}−2}} is an ideal of Q_{k} of size m−r +2^{r+1} −2 in which each of c_{1}, c_{2}, …, c_{2r+2}, a_{1}, a_{2}, …, a_{2^{r+1}−2} is a maximal element. This fact allows us to mimic the proof^{4} of Lemma 3.1 and obtain an ideal J of size m containing I and r of the elements a_{1}, a_{2}, …, a_{2^{r+1}−2}, say a_{3}, …, a_{r+2}, such that H_{J} is linearly independent and hence a basis of F_{2}^{m}. Note that since J ⊂ I′, each of the 3r + 2 elements of M = {c_{1}, c_{2}, …, c_{2r+2}, a_{3}, …, a_{r+2}} is a maximal element of J.

We now proceed as in the proof of Theorem 3.5. We label the vectors assigned to the elements of M as u_{1}, u_{2}, …, u_{3r+2}, respectively. Let x denote the vector assigned to a_{1} and let y denote the vector assigned to a_{2}. Consider the ideals of size m − r obtained from J by removing any r + 1 elements of M and adjoining a_{1}. The sets of vectors assigned to these ideals are linearly independent, and so given any r + 1 of the vectors u_{1}, u_{2} …, u_{3r+2}, at least one appears in writing x as a sum of the basis vectors of H_{J}. Hence at least 2r + 2 of these vectors appear in x and similarly, at least 2r + 2 occur in y. Hence at least r + 2 appear in both, say u_{1}, u_{2}, …, u_{r+2}. Then x − y is a linear combination of the m − r − 2 vectors in H_{J\{c_{1},c_{2},...,c_{r+2}}} and therefore (J \{c_{1}, c_{2}, …, c_{r+2}})∪{a_{1}, a_{2}} is an ideal of size m−r whose assigned vectors are linearly dependent, a contradiction. □

References

[MS77] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Vols. I and II, North-Holland, Amsterdam, 1977.

[N87] H. Niederreiter, Point sets and sequences with small discrepancy, Monatsh. Math. 104 (1987), 273-337.

[N91] H. Niederreiter, A combinatorial problem for vector spaces over finite fields, Discrete Math. 96 (1991), 221-228.

[N92] H. Niederreiter, Orthogonal arrays and other combinatorial aspects in the theory of uniform point distributions in unit cubes, Discrete Math. 106/107 (1992), 361-367.

[P89] V. Pless, Introduction to the Theory of Error-Correcting Codes, second edition, Wiley, New York, 1989.

4The hypothesis in Lemma 3.1 that ω_{m−r} ≥ 2 ensured that I had at least two maximal elements, and this conclusion holds in the current situation since 2r + 2 ≥ 6. The hypothesis (7) in Lemma 3.1 ensured the existence of at least q^{r+1} − q^{2} + q elements (i + ω_{m−r}, 1), (1 ≤ i ≤ s − ω_{m−r}); in the current situation the role of these elements is played by a_{1}, a_{2}, …, a_{2^{r+1}−2}.