%TO APPEAR IN DISCRET MATHEMATICS
% 13 October 1993
 \documentstyle[12pt]{article}
\begin{document}
\setlength{\textwidth}{6.0in}
\setlength{\textheight}{8.12in}
\newtheorem{lemma}{Lemma}[section]
\newtheorem{theorem}[lemma]{Theorem}
\newtheorem{proposition}[lemma]{Proposition}
\newtheorem{corollary}[lemma]{Corollary}

\title{Codes with a Poset Metric}
\author{Richard~A.~Brualdi, Janine~Graves and K.~Mark Lawrence\\
    Department of Mathematics\\
    University of Wisconsin\\
    Madison, WI  53706}

\maketitle
\begin{abstract}
Niederreiter generalized the following classical problem of coding theory:
given a finite field $F_q$ and integers $n>k\geq 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.
\end{abstract}

\section{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 \cite{MS77,P89}
is to determine the largest integer $d$ such that
there exist $n$ vectors $h_1,h_2,\ldots,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,\ldots,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  \cite{N87,N91,N92}  as follows. 

Let $n_1,n_2,\ldots,n_s$ be positive integers
and let 
\begin{equation} \label{eq:system}
 H=\{h_{(i,j)}: 1\leq i\leq s, 1\leq j\leq n_i\}
\end{equation}
be a system of $n_1+n_2+\cdots+n_s$
 vectors in $F_q^m$ partitioned into $s$ ordered
sets of vectors of cardinalities $n_1,n_2,\ldots,n_s$, respectively. Define
\[d(H)=\min\, \sum_{i=1}^s d_i\]
where the minimum is extended over all integers $d_1,d_2,\ldots,d_s$ such
that $0\leq d_i\leq n_i$ $ (1\leq i\leq s)$ and
$\sum_{i=1}^s d_i$ is positive, for which the set of vectors
\[ \{h_{(i,j)}: 1\leq i\leq s, 1\leq j\leq d_i\}\]
is linearly dependent. If there are no such integers $d_1,d_2,\ldots,d_s$
(implying that $n_1+n_2+\cdots +n_s\leq m$),
 then $d(H)$ is defined to be $n_1+n_2+\cdots +n_s+1$.\footnote{In this
case Niederreiter defines $d(H)$ to be $m+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,\ldots,t_s$
with $t_i\leq n_i\, (1\leq i\leq s)$, the vectors $\{h_{(i,j)}:
 1\leq i\leq s, 1\leq j\leq 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,\ldots,n_s;m)=\max\, d(H)\]
where the maximum is taken over all systems $H$ of the form
(\ref{eq:system}). If $n_1=n_2=\cdots=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 {\it poset}, in the following way. We are given
a poset
\[ P(n_1,n_2,\ldots,n_s)
 =\{(i,j): 1\leq i\leq s, 1\leq j\leq n_i\}\]
consisting of $s$ disjoint chains $N_1,N_2,\ldots,N_s$
 of sizes $n_1,n_2,\ldots,n_s$,
respectively. Recall that an {\it ideal} $I$ of a poset is a
subset of its elements with the property that $x\in I$ and $y< x$ imply
that $y\in I$.  An  ideal  of $P(n_1,n_2,\ldots,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,\ldots,n_s)$
  are in one-to-one
correspondence with partitions $t_1,t_2,\ldots,t_s$ of $t$ for which
$0\leq t_i\leq n_i$ for each $i=1,2,\ldots,s$. We are asked to assign
vectors of $F_q^m$ to the elements of the poset $P(n_1,n_2,\ldots,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,\ldots,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,\ldots,1)$ is a
trivial poset in which no two elements are comparable, that is, $P(1,1,\ldots,
1)$ is an {\it 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.

Let $P$ be an arbitrary poset of cardinality $n$
whose partial order relation is denoted as usual by $\leq$. 
If $A\subseteq P$, then $\langle A\rangle$ denotes the smallest ideal
of $P$ which contains $A$ (since the intersection of ideals is an ideal,
$\langle A\rangle$ 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,\ldots,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,\ldots,x_n)$ be a vector in $F_q^n$. We define the
{\it $P$-weight} of $x$ to be the cardinality
\[w_P(x)=|\langle \mbox{supp}(x) \rangle|\]
of the smallest ideal of $P$ containing the {\it support} of $x$ where 
$\mbox{supp}(x) =\{i:x_i\neq 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
{\it $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.

\begin{lemma}
\label{th:metric}
If $P$ is a poset of $n$ elements, then $P$-distance $d_P(\cdot,\cdot)$
 is a metric on $F_q^n$.
\end{lemma}

\noindent
{\bf Proof.}  Clearly, $P$-distance is symmetric and positive definite.
To prove that $d_P(x,y)\leq d_P(x,z)+d_P(z,y)$ for all $x,y\mbox{ and }z$
it suffices to show that $P$-weight satisfies the triangle inequality
$w_P(x+y)\leq w_P(x)+w_P(y)$. Since $\mbox{supp}(x+y)\subset
\mbox{supp}(x)\cup\mbox{supp}(y)$ and since the union of two ideals is
also an ideal, we have
\begin{eqnarray*}
w_P(x+y)&\leq& |\langle\mbox{supp}(x)\rangle\cup\langle
\mbox{supp}(y)\rangle |\\
&\leq&
|\langle\mbox{supp}(x)\rangle|+|\langle\mbox{supp}(y)\rangle|\\
&=&w_P(x)+w_P(y).
\end{eqnarray*}
\hfill{$\Box$}

\medskip
We call the  metric $d_P(\cdot,\cdot)$  on $F_q^n$ a {\it poset-metric}.
If $F_q^n$ is endowed with a poset-metric,
 then we call a subset $C$ 
of $F_q^n$ a {\it poset-code}. If the poset-metric corresponds to a poset
$P$, then $C$ is a {\it $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 {\it $P$-sphere} with {\it center} $x$ and {\it radius} $r$ is  the
set
\[S_P(x;r)=\{y\in F_q^n: d_P(x,y)\leq 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{equation}
\label{eq:omega}
\left\{
\begin{array}{cl}
1&\mbox{ if $i=0$}\\
\sum_{j=1}^i (q-1)^j q^{i-j}\Omega_j(i) &\mbox{ if $i>0$}\end{array}
\right.
\end{equation}
where $\Omega_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
\begin{equation}
\label{eq:Omega}
 1+ \sum_{i=1}^r \sum_{j=1}^i (q-1)^j q^{i-j}\Omega_j(i).
\end{equation}
In particular, if $q=2$ the number of vectors in a sphere of radius $r$
equals 
 \[1+\sum_{i=1}^r \sum_{j=1}^i 2^{i-j}\Omega_j(i).\]
 
\bigskip\noindent
{\bf 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,\ldots,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=\left[\begin{array}{cccccccc}
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{array}\right].\]
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$.\footnote{We follow the
usual practice in coding theory of not listing the $A_i$ which equal 0.}

We now consider $C$ to be a $P$-code. 
Since $1<i$ in $P$ for each $i=2,3,\ldots,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\neq 0$ and $c$ has $P$-weight at least 4. Suppose that
there exists a vector $x\in F_2^8$ such that $d_P(0,x)\leq 2$ and
$d_P(c,x)\leq 2$. Thus $w_P(x)\leq 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)\geq 4$ implies
that $c$ has 1's in at least two of the positions $3,4,\ldots,8$. 
But then $d_P(c,x)\geq 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!\footnote{This is in contrast to the classical situation in
which the $[7,4,3]$ Hamming code is perfect but the extended code $C$
is not.}\hfill{$\Box$}

\bigskip
We now generalize Niederreiter's problem. Let $P$ be a poset with elements
$\{1,2,\ldots,n\}$. Let
\begin{equation}
\label{eq:parity}
H=\{h_i:1\leq i\leq n\}
\end{equation}
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\in I\}$ are linearly dependent.
If there is no such ideal (implying that $n\leq 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)\leq 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 (\ref{eq:parity}). 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)\leq m+1$; furthermore, by choosing  a system
$H$ of nonzero vectors we see that $d_q(P;m)\geq d_P(H)\geq 2$.
Hence 
\[2\leq d_q(P;m)\leq m+1.\]

\bigskip\noindent
{\bf Problem}\, {\it Determine $d_q(P;m)$ for different posets $P$.}

\bigskip

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,\ldots,n_s;m)=d_q(P(n_1,n_2,\ldots,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$.


\section{Perfect $P$-codes}

Let $P$ be a poset with elements $\{1,2,\ldots,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 {\it 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.

\begin{theorem}
\label{th:chain}
Let $P$ be the poset with elements $\{1,2,\ldots,n\}$ where
$1<2<\cdots <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\leq k\leq n$
such that  $|C|=q^{k}$ and the set of all vectors
$(x_{n-k+1},\ldots,x_n)$ such that 
$(x_1,\ldots,x_{n-k},x_{n-k+1},\ldots,x_n)\in C$
for some $(x_1,\ldots,x_{n-k})\in F_q^{n-k}$
equals $F_q^{k}$.
In particular, the linear code $C_k$ of dimension $k$
 consisting
of all vectors $(0,\ldots,0,a_{n-k+1},\ldots,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$.
\end{theorem}

\medskip
\noindent
{\bf 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,\ldots,y_n)$ in $F_q^n$ is contained in the
$P$-sphere of radius $n-k$ about some codeword of the form
 $(x_1,\ldots,x_{n-k},y_{n-k+1},\ldots, 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,\ldots,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,\ldots,c_r, y_{r+1},\ldots,y_n)$. 
Hence $C$ has the form given in the theorem with $r=n-k$.\hfill{$\Box$}

\medskip
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.

\begin{theorem}
\label{th:2chains}
Let $n=2\ell$ be an even positive integer. 
Let $P$ be the poset consisting of two disjoint chains $N$ and $N'$
of the same size $\ell$. 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$.
\end{theorem}

\noindent
{\bf Proof.} Clearly the
 codes $C=F_q^{2\ell}$ 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,\ldots,\ell\}$ where
$1<2<\cdots<\ell$, and let the elements of $N'$ be $\{1',2',\ldots,\ell'\}$
where $1'<2'<\cdots <\ell'$.
 Suppose to the contrary that
$C$ is a perfect $P$-code where $1<|C|<q^{2\ell}$.  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\ell}$. 
Then $1\leq r\leq 2\ell -1$.  

First assume that $r\geq \ell$.  
Let $x=(x_1,\ldots,x_{\ell},x_{1'},\ldots,x_{\ell'})$ and\\
 $y=(y_1,\ldots,y_{\ell},y_{1'},\ldots,y_{\ell'})$ be any two vectors in
$F_q^{2\ell}$. Then the vector\\
$(x_1,\ldots,x_{\ell},y_{1'},\ldots,y_{\ell'})$ is contained in 
$S_P(x;r) \cap S_P(y;r)$. In particular, the $P$-spheres 
of radius $r$ about any two codewords overlap.
Since $|C|\geq 2$, this contradicts the assumption that $C$ is perfect.

Now assume that $1\leq r<\ell$. We first compute the cardinalities of
$P$-spheres of radius $r$.
Let $i$ be an integer with $1\leq i\leq \ell$. It follows
from (\ref{eq:omega}) that 
 the number  of vectors whose distance
to a given  vector $x$ in $F_q^n$ equals $i$ is
\[\alpha_i=2(q-1)q^{i-1} +(i-1)(q-1)^2q^{i-2}=(q-1)q^{i-2}[(i+1)q-i+1].\]
Hence for each vector $x$  we have
\[|S_P(x;r)|=1+\sum_{i=1}^r \alpha_i.\] 
It follows by induction that
\begin{equation}
\label{eq:main}
|S_P(x;r)|=q^{r-1}[r(q-1)+q].
\end{equation}
Since $C$ is perfect, $q^{2\ell}=|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\geq 1$, we have $j\geq 2$.
Thus  $r=q(1+q+\cdots +q^{j-2})\geq 2(j-1)\geq j$.
We have
\[|C|=q^{2\ell-r-j+1}=q^{2(\ell-r)+r-(j-1)},\]
and since $r>j-1$, it follows that  $|C|>q^{2(\ell -r)}$.
By the pigeon-hole principle, there exist distinct codewords 
 $x=(x_1,\ldots,x_{\ell},x_{1'},\ldots,x_{\ell'})$ and
 $y=(y_1,\ldots,y_{\ell},y_{1'},\ldots,y_{\ell'})$ such that
$x_i=y_i$ and $x_{i'}=y_{i'}$ for $i=r+1,\ldots,\ell$.
Since the vector
$(x_1,\ldots,x_{\ell},y_{1'},\ldots,y_{\ell'})$ is contained in 
$S_P(x;r) \cap 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.\hfill{$\Box$}

\medskip
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.

\begin{theorem}
\label{th:hamgol}
For each positive integer $n$ let $P_n$ denote the poset with elements
$\{1,2,\ldots,n\}$ in which $1<i$ for each $i=2,3,\ldots,n$ and these are
the only strict comparabilities. Then for each positive integer $m$ 
the extended binary Hamming ${\cal 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.
\end{theorem}

\noindent
{\bf Proof.} The proof that ${\cal 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{11\choose 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,\ldots,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)\geq 6$. Hence
at least $5$ of coordinates $2,3,\cdots,12$ of $c$ are nonzero. This
implies that $d_{P_{12}}(c,x)\geq 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. \hfill{$\Box$}

\section{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,\ldots,n_s$ be positive integers such that  $n_1\geq n_2\geq
\cdots\geq n_s$. If $n_1+n_2+\cdots +n_s\leq m$, then clearly 
$d_q(n_1,n_2,\ldots,n_s;m)=n_1+n_2+\cdots +n_s+1$.
 As a result we henceforth assume that
\begin{equation}
\label{eq:strict}
n_1+n_2+\cdots +n_s>m.
\end{equation}
The following basic results are proved by Niederreiter \cite{N87}:
\begin{enumerate}
\item[(N1)] $2\leq d_q(n_1,n_2,\ldots,n_s;m)\leq m+1$;
\item[(N2)] $d_q(n'_1,n'_2,\ldots,n'_s;m)\leq d_q(n_1,n_2,\ldots,n_s;m)$
if $n_i\leq n'_i$ for $i=1,2,\ldots,s$;
\item[(N3)] Let $n'_i=\min\{n_i,m\}$ for $i=1,2,\ldots,s$. Then
$d_q(n_1,n_2,\ldots,n_s;m)=d_q(n'_1,n'_2,\ldots,n'_s;m)$;
\item[(N4)] If $s\le q+1$, then $d_q(n_1,n_2,\ldots,n_s;m)=m+1$;
\item[(N5)]  Assume that $m\geq 2$. Let $\omega_m$ be the smallest integer
such that $n_1+\cdots+n_{\omega_m}\geq m$. If $s\geq q+\max\{\omega_m,2\}$, then
\[d_q(n_1,n_2,\ldots,n_s;m)\leq m.\]
\end{enumerate}
In addition, using constructions based on linear recurrence relations,
Niederreiter \cite{N91}
obtained lower bounds for $d_q(n_1,n_2,\ldots,n_s;m)$ 
and also obtained the following results:
\begin{enumerate}
\item[(N6)] If $m\ge 2$ and $s\leq (q^m-1)/(q-1)$, then
$d_q(n_1,n_2,\ldots,n_s;m)\geq 3$, and if $s>(q^m-1)/(q-1)$, then
$d_q(n_1,n_2,\ldots,n_s;m)=2$;
\item[(N7)] Assume that $q+2\leq s\leq (q^m-1)/(q-1)$. If 
$n_1\ge m+2-\lfloor\log_q ((q-1)(s-1)+1)\rfloor$, then
\[d_q(n_1,n_2,\ldots,n_s;m)\leq m+2-\lfloor\log_q((q-1)(s-1)+1)\rfloor.\]
If $n_1\le m+1-\lfloor\log_q ((q-1)(s-1)+1)\rfloor$, then
\[d_q(n_1,n_2,\ldots,n_s;m)\leq m+2-\lfloor\log_q((q-1)(s-\omega_m
+1)+1)\rfloor.\]
\end{enumerate}

In this section we extend some of the bounds given above.
In what follows, for each integer $j$ with
$1\leq j\leq n_1+\cdots+n_s$, 
$\omega_{j}$ denotes the smallest integer $t$ such that
$n_1+\cdots +n_t\geq j$.

 Let $H=\{h_{(i,j)}: 1\leq i\leq s, 1\leq j\leq n_i\}$ be a system of 
vectors in $F_q^m$. The vector $h_{(i,j)}$ is assigned to the $j$th element
of the $i$th  chain of the poset  $P(n_1,n_2,\ldots,n_s)$.
 If $I$ is an ideal of $P(n_1,n_2,\ldots,n_s)$, then
$H_{I}$ denotes the set of vectors from $H$ assigned to the elements of $I$.

\begin{lemma}
\label{th:lemma}
 Let $H=\{h_{(i,j)}: 1\leq i\leq s, 1\leq j\leq n_i\}$
 be a system of $n$
vectors in $F_q^m$.  Let $r$ be an integer with $1\leq r\leq m-2$. 
Assume  that $\omega_{m-r}\geq 2$ and that
\begin{equation}
\label{eq:omegaa}
s\geq \omega_{m-r} +q^{r+1}-q^2+q.
\end{equation}
Also assume that $H_I$ is linearly independent for every ideal $I$ of size
$m-r$ of $P=P(n_1,n_2,\ldots,n_s)$.
Then there exists an ideal $J$ 
of $P$ of size $m$ having exactly $\omega_{m-r}+r$
maximal elements such that $H_J$  is linearly independent.
\end{lemma}

\noindent
{\bf Proof.}   Let $u 
=(m-r)-\sum_{i=1}^{\omega_{m-r}-1}n_i$.
The set
\[I=\{(i,j):1\leq i<\omega_{m-r},1\leq j\leq
n_i\}\cup\{(\omega_{m-r},j):1\leq j\leq 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\leq i<\omega_{m-r}$ and $b_{\omega_{m-r}}=
h_{(\omega_{m-r},u)}$ be the vectors from $H$
 assigned to the maximal elements of $I$. Let
$c_i=h_{(i+\omega_{m-r},1)}\, (1\leq i\leq s-\omega_{m-r})$
be the vectors assigned to the minimal elements of the last
$s-\omega_{m-r}$ chains of $P$. We extend $H_I$ to a basis $H_I\cup\{v_1,\ldots,
v_{r}\}$ of $F_q^m$. Let $\hat{c_i}$ denote the projection of $c_i$ onto 
the subspace $V$ of $F_q^m$ spanned by $\{v_1,\ldots,v_{r}\}$.

We first show that the number $t$ of $c_i$ whose projection $\hat{c_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\leq i\leq s-\omega_{m-r}$
and suppose that $\hat{c_i}=0$.
The set $(H_I\setminus\{b_j\})\cup\{c_i\}$ is the set of vectors assigned to
an ideal of size $m-r$ and hence is linearly independent for
$j=1,\ldots,\omega_{m-r}$.
Since $\hat{c_i}= 0$, it follows that the projection  $\beta_{ij}$
of $c_i$ onto $b_j$ is not zero for  each $j$.
Since $\omega_{m-r}\geq 2$, we may take $j$
equal to 1 and 2 in turn. 
Thus $\alpha_i=\beta_{i1}/ \beta_{i2}$ is defined and nonzero.
  Since there are only $q-1$
possible values for the $\alpha_i$, it follows  that  there exist
$k$ and $l$ such that $\hat{c_k}=\hat{c_l}=0$ and $\alpha_k=\alpha_l$.
It follows that $\beta_{l2}c_k-\beta_{k2}c_l$ is a linear combination
of the vectors in $H_I\setminus\{b_1,b_2\}$. Then 
$(H_I\setminus\{b_1,b_2\})\cup \{c_k,c_l\}$  is a linearly dependent set
of vectors assigned to an ideal of size $m-r$, a contradiction. Hence
$t\leq q-1$. 

We now claim that the set $S=\{\hat{c_i}:1\leq i\leq s-\omega_{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|\leq q^{r-1}$.
Consider the $c_i$ such that $\hat{c_i}\neq 0$.
By (\ref{eq:omegaa}), $s-\omega_{m-r}>q^{r+1}-q^2+q-1$ and
since $t\leq q-1$, it now follows that the number  $s-\omega_{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\cup\{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\neq l$ whose projections into $U$
are equal. 
It follows that $c_k-c_l$ is a linear combination
of the vectors in $H_I\setminus\{b_1,b_2\}$. Then 
$(H_I\setminus\{b_1,b_2\})\cup \{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\cup\{c_i:\hat{c_i}\in S'\}$ is a set of linearly independent
vectors corresponding to an ideal $J$ of size $m$ having 
exactly $\omega_{m-r}+r$ maximal elements. \hfill{$\Box$}



\medskip
We now extend Niederreiter's result (N5) above. We first consider the case
$q=2$.

\begin{theorem}
\label{th:2}
Let $r$ and $m$ be integers with $0\leq r\leq m-2$. Assume that 
\begin{equation}
\label{eq:richard}
\omega_{m-r}\geq 2r+2.
\end{equation}
  Also assume that
\begin{equation}
\label{eq:new}
s\geq \quad \left\{\begin{array}{ll}
\omega_{m}+2 &\mbox{ if $r=0$},\\
\omega_{m-1} +3&\mbox{ if $r=1$},\\
\omega_{m-r}+2^{r+1}-2&\mbox{ if $r\geq 2$.}\end{array}\right. 
\end{equation}
Then
\begin{equation}
\label{eq:janine}
d_2(n_1,n_2,\ldots,n_s;m)\leq m-r.
\end{equation}
\end{theorem}

\noindent
{\bf Proof.}  If $r=0$ the result is a consequence of (N5).
Now assume that $r\geq 1$. Suppose to the contrary that 
$d_2 (n_1,n_2,\ldots,n_s;m)>m-r$. Then there exists a system
$H=\{h_{(i,j)}:1\leq i\leq s,1\leq j\leq  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,\ldots,n_s)$.
It follows from (\ref{eq:new}) that (\ref{eq:omegaa}) holds for $q=2$ and 
that
\begin{equation}
\label{eq:mark}
s-\omega_{m-r}-r\geq 2
\end{equation}
 holds for all $r\geq 1$.
By Lemma \ref{th:lemma}, there exists an ideal $J$ 
of $P$ of size $m$ having exactly $\omega_{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,\ldots,b_m$. 
Let 
\[T=\{ i:1\leq i\leq s \mbox{ and }(i,1)\in 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|=\omega_{m-r}+r$ and by (\ref{eq:mark}), $|\overline{T}|=s-|T|\geq 2$.  Let $J_{\mbox{max}}$ be the set of 
the $\omega_{m-r}+r$ maximal elements of $J$. Let
 $a_i=(i,1)$ be the minimal element of the $i$th chain of $P$ $(1\leq i\leq
 s)$,  and  write
\[a_i=\sum_{l=1}^m \beta_{il}b_l \quad (i\in \overline{T}).\]
Let $M$ be any subset of $J_{\mbox{max}}$ with $|M|=r+1$. Let $i\in
\overline{T}$ and consider the ideal $I=(J\setminus M)\cup \{a_i\}$
of size $m-r$.   Thus $H_I$ is linearly independent, and it follows that
$\beta_{il}\neq 0$ for at least one $l$ such that $b_l\in H_M$.
Since $M$ was an arbitrary subset of 
 $J_{\mbox{max}}$ of cardinality $r+1$, it follows that $\beta_{il}=0$
for at most $r$ values of $l$ with $b_l\in H_{J_{\mbox{max}}}$.
Since $|\overline{T}|\geq 2$ there exist distinct elements $j$ and $k$ in
$\overline{T}$, and for any such $j$ and $k$,
there exist at least
 $|J_{\mbox{max}}|-2r=\omega_{m-r}-r\geq r+2$ 
values of $l$ with $b_l\in H_{J_{\mbox{max}}}$
 such that both $\beta_{jl}\neq 0$ and $\beta_{kl}\neq 0$.
Here the last inequality is a consequence of
hypothesis (\ref{eq:richard}).  Since  we are working over the binary
field, it follows that $\beta_{jl}=\beta_{kl}=1$ for at least $r+2$
indices $l$ with $b_l\in H_{J_{\mbox{max}}}$.  Without loss of generality,
$\beta_{jl}=\beta_{kl}$ for $l=1,2,\ldots,r+2$.  We then have
\[a_j-a_k =\sum_{l=r+3}^m (\beta_{jl}-\beta_{kl}) b_l.\]
It follows that $\{b_{r+3},\ldots,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 (\ref{eq:janine}) holds. \hfill{$\Box$}




\medskip
We now obtain the conclusion of Theorem \ref{th:2} for arbitrary $q$.
Note that  the assumptions of Theorem \ref{th:q} when $q=2$ are not
identical to the assumptions of Theorem \ref{th:2}.

\begin{theorem}
\label{th:q}
Let $r$ and $m$ be integers with $0\leq r\leq m-2$. Assume that 
\begin{equation}
\label{eq:richardq}
\omega_{m-r}\geq r+2.
\end{equation}
 Also assume that $(\ref{eq:omegaa})$ holds and that
\begin{equation}
\label{eq:newq}
s\geq \omega_{m-r}+r +{2r+2\choose r+2} (q-1)^{r+1}+1.
\end{equation}
Then
\begin{equation}
\label{eq:janineq}
d_q(n_1,n_2,\ldots,n_s;m)\leq m-r.
\end{equation}
\end{theorem}

\noindent
{\bf 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\geq 1$. Suppose to the contrary that 
$d_q (n_1,n_2,\ldots,n_s;m)>m-r$. Then there exists a system
$H=\{h_{(i,j)}:1\leq i\leq s,1\leq j\leq  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,\ldots,n_s)$.
It follows from (\ref{eq:newq})
that
\begin{equation}
\label{eq:markq}
s-\omega_{m-r}-r > {2r+2\choose r+2} (q-1)^{r+1}
\end{equation}
 holds for all $r\geq 1$.
By Lemma \ref{th:lemma}, there exists an ideal $J$ 
of $P$ of size $m$ having exactly $\omega_{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,\ldots,b_m$. 
Let 
\[T=\{ i:1\leq i\leq s \mbox{ and }(i,1)\in 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|=\omega_{m-r}+r$ and by (\ref{eq:markq}), $|\overline{T}|=s-|T|>
{2r+2\choose r+2} (q-1)^{r+1}$.
 Let $J_{\mbox{max}}$ be the set of 
the $\omega_{m-r}+r$ maximal elements of $J$. By (\ref{eq:richardq}),
$|J_{\mbox{max}}|\geq 2r+2$, and we fix a subset $K$ of $J_{\mbox{max}}$
of cardinality $2r+2$.  Let
 $a_i=(i,1)$ be the minimal element of the $i$th chain of $P$ $(1\leq i\leq
 s)$,  and  write
\[a_i=\sum_{l=1}^m \beta_{il}b_l \quad (i\in \overline{T}).\]
Let $M$ be any subset of $J_{\mbox{max}}$ with $|M|=r+1$. Let $i\in
\overline{T}$ and consider the ideal $I=(J\setminus M)\cup \{a_i\}$
of size $m-r$.   Thus $H_I$ is linearly independent, and it follows that
$\beta_{il}\neq 0$ for at least one $l$ such that $b_l\in H_M$.
Since $M$ was an arbitrary subset of 
 $J_{\mbox{max}}$ of cardinality $r+1$, it follows that $\beta_{il}=0$
for at most $r$ values of $l$ with $b_l\in H_{J_{\mbox{max}}}$ and hence
for at most $r$ values of $l$ with $b_l\in H_{K}$. Thus $\beta_{il}\neq 0$
for at least $r+2$ values of $l$ with $b_l\in H_{K}$.
For each $i\in\overline{T}$ we choose a set
$C_i$ of  any $r+2$   such $l$'s. It follows from (\ref{eq:newq}) that
$|\overline{T}|=s-\omega_{m-r}-r>{2r+2\choose 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,\ldots,r+2\}$.  Thus
$\beta_{ij}\neq 0$ for  $1\leq j\leq r+2$ and $i\in Z$.
Hence
\[\alpha_{ij}=\frac{\beta_{ij}}{\beta_{i,r+2}} \quad (1\leq j\leq 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
\[(\alpha_{i1},\alpha_{i2},\ldots,\alpha_{i,r+1})=
(\alpha_{k1},\alpha_{k2},\ldots,\alpha_{k,r+1}).\]
We then have
\[\beta_{k,r+2} a_i- \beta_{i,r+2}
a_k =\sum_{l=r+3}^m (\beta_{k,r+2}\beta_{il}-\beta_{i,r+2}\beta_{kl}) b_l.\]
It follows that $\{b_{r+3},\ldots,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 (\ref{eq:janineq}) holds. \hfill{$\Box$}

\medskip
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\geq 0,j\geq 0,i+j\leq k-1\},\]
having the componentwise partial order given by
\[(i,j)\leq (i',j')\mbox{ if and only if } i\leq i'\mbox{ and }
j\leq j'.\]
The set of elements of $Q_k$ is partitioned into $k$ {\it level sets}
$L_0,L_1,\ldots,L_{k-1}$ where
\[ L_t=\{(i,j):i\geq 0,j\geq 0,i+j=t\}\quad (0\leq t\leq 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\leq m$, then $d_2(Q_k;m)=n+1$. We henceforth assume that
$n>m$.

\begin{theorem}
\label{th:little}
If $m\leq 7$, then $d_2(Q_k;m)=m+1$. If $m\geq 8$ and $k(k+1)/2\geq m+2$,
 then $d_2(Q_k;m)\leq m$.
\end{theorem}

\noindent
{\bf Proof.} It is not hard to show that $d_2(Q_k;m)=m+1$ if $m\leq 7$.
For instance, suppose that $m=7$. If $k\geq 7$, then 
the union of the ideals of $Q_k$ of size 7 contains
exactly $16$ elements.  Let $e_1,e_2,\ldots,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{array}{ll}
(0,0) \leftarrow e_1 & (2,1)\leftarrow e_4+e_7\\  
(0,1) \leftarrow e_2 & (3,0)\leftarrow e_7\\  
(1,0) \leftarrow e_3 & (0,4)\leftarrow e_7\\  
(0,2) \leftarrow e_4 & (4,0)\leftarrow e_6\\  
(1,1) \leftarrow e_4 +e_5+e_6+e_7 & (0,5)\leftarrow e_5\\  
(2,0) \leftarrow e_5 & (5,0)\leftarrow e_4\\  
(0,3) \leftarrow e_6 & (0,6)\leftarrow e_3\\  
(1,2) \leftarrow e_5+e_6 & (6,0)\leftarrow e_2\end{array}.\]



Now assume that $m\geq 8$ and $k(k+1)/2\geq m+2$. 
 We show that it is impossible to
find a system 
\[H=\{h_{(i,j)}:i\geq 0,j\geq 0, i+j\leq 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\leq k-1$ and an  ideal  $J$ of size $m$
containing $L_0\cup\cdots\cup L_{j-1}$ and contained in
$L_0\cup\cdots\cup L_{j-1}\cup L_j$.   We may choose such a $J$ so that
for some integer $t$, $\{(0,j),(1,j-1),\ldots,(t,j-t)\}=L_j\cap 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\leq 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\geq 8$, it follows that
$J\cup \{a,b\}$ is an ideal of $Q_k$ of size $m+2$ in which each of
$a,b,c\mbox{ 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\setminus\{c\})\cup\{a\}$ and
$(J\setminus\{d\})\cup\{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\setminus \{u,v\}$,
and hence $(H_J\setminus\{u,v\})\cup\{x,y\}$ is a linearly dependent set of
vectors assigned to the ideal $(J\setminus\{c,d\})\cup\{a,b\}$ of size $m$,
a contradiction.\hfill{$\Box$}



\begin{theorem}
\label{th:littlemore}
If $m\geq 26$ and $k(k+1)/2\geq m+2$,
 then $d_2(Q_k;m)\leq m-1$.
\end{theorem}


\noindent
{\bf Proof.}  Assume that $m\geq 26$ and $k(k+1)/2\geq m+2$.
 We show that it is impossible to
find a system 
\[H=\{h_{(i,j)}:i\geq 0,j\geq 0, i+j\leq 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.

{\small
\setlength{\unitlength}{1cm}
\newcounter{ir}
\newcounter{il}
\begin{picture}(8,8)
%\multiput(6.5,0)(-1,1){7}{\stepcounter{il}\line(1,1){6-\arabic{il}}% positive slope
%\multiput(6.5,0)(1,1){7}{\line(-1,1){7}}% negative slope
% Draw the positive slope lines:
\put(6.5,0){\line(1,1){6}}
\put(5.5,1){\line(1,1){5}}
\put(4.5,2){\line(1,1){4}}
\put(3.5,3){\line(1,1){3}}
\put(2.5,4){\line(1,1){2}}
\put(1.5,5){\line(1,1){1}}
% Draw the negative slope lines:
\put(6.5,0){\line(-1,1){6}}
\put(7.5,1){\line(-1,1){5}}
\put(8.5,2){\line(-1,1){4}}
\put(9.5,3){\line(-1,1){3}}
\put(10.5,4){\line(-1,1){2}}
\put(11.5,5){\line(-1,1){1}}
% Draw vertex points at nodes
\multiput(6.5,0)(1,1){7}{\circle*{.1}}
\multiput(5.5,1)(1,1){6}{\circle*{.1}}
\multiput(4.5,2)(1,1){5}{\circle*{.1}}
\multiput(3.5,3)(1,1){4}{\circle*{.1}}
\multiput(2.5,4)(1,1){3}{\circle*{.1}}
\multiput(1.5,5)(1,1){2}{\circle*{.1}}
\put(0.5,6){\circle*{.1}}
% number the vertex
\put(6.1,-0.9){(\normalsize 0,0)}
% number right hand edge
\multiput(7.8,.4)(1,1){6}{\stepcounter{ir}\makebox(0,0)[l]{(\normalsize
\arabic{ir},0)}}
% number left hand edge
\multiput(4.4,.4)(-1,1){6}{\stepcounter{il}\makebox(0,0)[l]{(\normalsize 0,\arabic{il})}}
% number intermediate points
\put(6.4,-.35){1} % level 0
\put(5.3,.7){2}\put(7.5,.7){3}  % level 1
\put(4.3,1.7){4}\put(6.4,1.6){5}\put(8.5,1.7){6} % level 2
\put(3.3,2.7){7}\put(5.4,2.6){8}\put(7.4,2.6){9}\put(9.5,2.7){10} % level 3
\put(2.15,3.7){11}\put(4.3,3.6){12}\put(6.3,3.6){13}\put(8.3,3.6){14}
\put(10.5,3.7){15} %level 4
\put(1.1,4.7){16}\put(3.3,4.55){17}\put(5.3,4.55){18}\put(7.3,4.55){19}
\put(9.3,4.55){20}\put(11.5,4.7){21} % level 5
\put(0.1,5.7){22}\put(2.3,5.55){23}\put(4.3,5.55){24}\put(6.3,5.55){25}% lev 6
\put(0.3,6.4){\Large\bf $c_1$}\put(2.3,6.4){\Large\bf $c_2$}\put(4.3,6.4)
{\Large\bf $c_3$}\put(6.3,6.4){\Large\bf $c_4$}\put(8.3,6.4){\Large\bf $a_1$}
\put(10.3,6.4){\Large\bf $a_2$}\put(12.3,6.4){\Large\bf $a_3$} % top letters 
\end{picture}}


\bigskip\bigskip\bigskip
\centerline{Figure 1.}
\medskip
\bigskip

Using a construction similar to that in the proof of Theorem
\ref{th:little} and the assumption that $m\geq 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\cup\{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,\mbox{ 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\cup\{v_m\}$ is a basis of $F_2^m$.  Let $u,v,y \mbox{ and }z$ be the
vectors from $H$ assigned to $c_3,c_4,a_2\mbox{ and }a_3$, respectively.
Each of the vectors $y$ and $z$ is a sum of a subset of the basis vectors.
Since $(I\setminus \{c_3\})\cup \{a_2\}$ is an ideal of size $m-1$,
$H_{(I\setminus \{c_3\})\cup \{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\setminus\{c_4\})\cup\{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\setminus \{c_3,c_4\}}$ assigned to the ideal
$I\setminus\{c_3,c_4\}$ and hence 
$H_{(I\setminus\{c_3,c_4\})\cup \{a_2,a_3\}}$ is a linearly dependent set
of vectors assigned to the ideal
$(I\setminus\{c_3,c_4\})\cup \{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\cup\{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,\ldots,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\setminus\{c_1,c_2,c_3\}}$
and  so
$(J\setminus\{c_1,c_2,c_3\})\cup \{a_1,a_2\}$ is an ideal of size 
$m-1$ whose assigned vectors are linearly  dependent, a contradiction.
\hfill{$\Box$}


\medskip
We now obtain a more general bound for $d_2(Q_k;m)$.


\begin{theorem}
\label{th:alotmore}
Let $r$ be an integer with $r\geq 2$ and let $f(r)=2^{2r+1}+r2^{r+2}-2^r
+2r^2+2r+2$. If $m\geq f(r)$ and $k\geq 2^{r+1}+2r$, then $d_2(Q_k;m)\leq
m-r$.
\end{theorem}


\noindent
{\bf Proof.}
Assume that $m\geq f(r)$ and $k\geq 2^{r+1}+2r$.
We show that it is impossible to
find a system 
\[H=\{h_{(i,j)}:i\geq 0,j\geq 0, i+j\leq 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\geq 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
\ref{th:little}. Since
\[ m-r\geq f(r)-r=\left(\sum_{i=1}^{2^{r+1}+2r-1}i\right)+2r+2 =
\left(\sum_{i=0}^{2^{r+1}+2r-2}|L_i|\right) +2r+2,\]
 we can find an ideal $I$ of size $m-r$ containing
$2r+2$  elements $c_1,c_2,\ldots,c_{2r+2}$  and an additional
$2^{r+1}-2$ elements
$a_1,a_2,\ldots,a_{2^{r+1}-2}$
 not in $I$ such that $I'=I\cup \{a_1,a_2,\ldots,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,\ldots,c_{2r+2},a_1,a_2,\ldots,a_{2^{r+1}-2}$
is a maximal element.
This fact allows us to mimic the proof\footnote{The hypothesis in Lemma
\ref{th:lemma} that
$\omega_{m-r}\geq 2$ ensured that $I$
had at least two maximal elements, and this conclusion holds in the 
current situation since $2r+2\geq 6$.  The hypothesis (\ref{eq:omegaa})
in Lemma \ref{th:lemma} ensured the existence of at least $q^{r+1}-q^2+q$
elements $(i+\omega_{m-r},1), (1\leq i\leq s-\omega_{m-r})$; in the current
situation the role of these elements is played by
$a_1,a_2,\ldots,a_{2^{r+1}-2}$.} of Lemma \ref{th:lemma} 
and obtain an ideal $J$ of size $m$ containing $I$
and  $r$ of the elements $a_1,a_2,\ldots,a_{2^{r+1}-2}$, say
$a_3,\ldots,a_{r+2}$,
 such that $H_J$ is linearly independent
and hence  a basis of $F_2^m$.  
Note that since $J\subset I'$, each of the $3r+2$ elements  of
$M=\{c_1,c_2,\ldots,c_{2r+2},a_3,\ldots,a_{r+2}\} $ is a maximal element
of $J$.

We now proceed as in the proof of Theorem \ref{th:littlemore}.
We label the vectors assigned to the elements of $M$
 as $u_1,u_2,\ldots,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\ldots,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,\ldots,u_{r+2}$. Then $x-y$ is a linear
combination of the $m-r-2$ vectors in $H_{J\setminus\{c_1,c_2,\ldots,c_{r+2}\}}$
and  therefore
$(J\setminus\{c_1,c_2,\ldots,c_{r+2}\})\cup \{a_1,a_2\}$ is an ideal of size 
$m-r$ whose assigned vectors are linearly dependent, a contradiction.
\hfill{$\Box$}


\bibliographystyle{alpha}
\begin{thebibliography}{N87}


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

\bibitem[N87]{N87} H.~Niederreiter, Point sets and sequences with small
discrepancy, {\it Monatsh. Math.} 104 (1987), 273-337.

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

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

\bibitem[P89]{P89} V.~Pless, {\it Introduction to the Theory of
Error-Correcting Codes}, second edition, Wiley, New York, 1989.

\end{thebibliography}


\end{document}



