I posted this question in <https://math.stackexchange.com/questions/1142698/picking-codewords-that-are-close> a week back.


Let $[n,k,d]$ be a linear code over $\Bbb F\_q$ with minimum distance $d$ and number of minimum weight codewords $N\_d$.


How many ways can you select codewords $c\_1,\dots,c\_T$ (assume $T\ll q^k$) such that there are two non-equal codewords in collection at a distance $d$ from each other ($c\_i\neq c\_j$, $|c\_i-c\_j|=d$)?


Presumably answer is $2^{\lambda T}$. If so what is correct estimate to $\lambda$?


Atleast could we say something when code is MDS (cases where weight enumerators known).



Picking codewords that are close
Edited:


@Turbo: You're right. I was assuming that the two codewords must be nonzero. In general, when one codeword is zero, one gets a weaker lower bound of the form
$N\_d {q^k \choose T}$
and the rest of the argument follows with a linear $N\_d$ instead of a quadratic factor $N\_d^2/2.$


A special case (original answer):


In the specific case of a binary linear code $C$ the nonzero values of the weight distribution coefficients $A\_w=\#\{c \in C:wt(c)=w \}$ are $A\_0=1,A\_d=N\_d,\ldots$. Now assume the code contains the all $1$ vector as a codeword. Then $A\_{n-d}$ is also nonzero and $A\_{n-d}\geq A\_d=N\_d$ since the sums (or differences) $(1,1,\ldots,1)+c$ are also codewords in $C.$


Thus there are at least $N\_d(N\_d-1)/2$ pairs $c\_i,c\_j$ in $C$ which satisfy $|c\_i-c\_j|=d$.
For each one of these pairs, you can select the remaining $T-2$ codewords (assumed distinct) arbitrarily provided $T-2 \leq 2^k.$ So you have approximately


$$ (N\_d^2/2) {2^k \choose T} \qquad (1)$$


which should be at least $O(2^k)$ provided $T$ is small enough compared to $2^k.$ Of course, if the code is also cyclic, then $N\_d \geq n$ and this helps extend the validity regime of the lower bound. i seem to recall there are some sporadic linear codes with $N\_d=3,$ and $n$ long, but can't think of the reference right now.


If you're interested in asymptotics, quite a few linear codes have weight distribution that is "asymptotically normal". This means that
$$A\_i/2^k \approx 2^{-n} {n \choose d}$$
and this should help refine the estimate in (1) above when you let $i=d$. See Chapter 9, especially section 10 of McWilliams and Sloane for more.


There should be obvious generalizations of this argument to nonbinary characteristic, such as assuming any Hamming weight $n$ codeword belongs to $C.$


